Componentes conexas. Introducción e índice.


Hace tiempo empecé un proyecto en solitario que incluia extraer regiones de color de una cierta imagen. Esto es lo que se conoce como identificación de componentes conexas o blob finding en inglés.

He decidido dedicar los próximos días a escribir algunos tutoriales sobre como llevar a cabo este tipo de operaciones.

Explicaré tres alogoritmos que permiten hacer lo mismo, cada uno útil en un sentido. También haré una muy breve introducción a teoría de grafos con un par de conceptos útiles.

Los tres algoritmos son:

  1. Dados una lista de pares de vértices de un grafo, tales que cada par forma una arista, nuestro algoritmo hallará las componentes conexas del grafo y nos dará información sobre ellas. Disponible aquí.
  2. Este, más dedicado a matrices binarias (de 1 ó 0), etiquetará cada región por recurrencia.
  3. Y el último, equivalente al segundo, se basa en dos pasadas a la matriz para etiquetar todas la zonas.

La programación la intentaré llevar a cabo a la vez en dos lenguajes de programación. El primero es MatLab. Es un lenguaje simple y muy fácil de usar a la hora de trabajar con matrices e implementar algoritmos. Sabiendo programar, interpretar código en matlab es bastante sencillo incluso no conociendo el lenguaje. De hecho, casi se puede leer como si fuera pseudo-código. Es un lenguaje interpretado que se ejecuta sobre el IDE matlab, de mathworks. Es de pago, sin embargo, hay una alternativa libre y perfectamente compatible llamada Octave, disponible para Windows, GNU/Linux y Mac.

El segundo es C, más usado y creo más útil a la hora de desarrollar software. Matlab está más orientado al trabajo de investigación independiente al propio software. Al estilo Mathematica o Maple.

Los archivos de fuente los iré subiendo aquí: http://neowriter.eshost.es/ (clicks en la publicidad tampoco me vendrían mal)

Anuncios
Esta entrada fue publicada en Componentes conexas, Manuales, Manuales largos, Noticias y etiquetada , , , , , , , , , , , . Guarda el enlace permanente.

Una respuesta a Componentes conexas. Introducción e índice.

  1. Pingback: DUO | White-Hat Hacking

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s