jueves, 28 de junio de 2012

Redes Complejas y Análisis de Imágenes

La representación, el procesado, el análisis y la clasificación de imágenes digitales son tareas intrínsecamente relacionadas. Algunas de estas tareas, y de las etapas en el análisis de imágenes, pueden resultar difíciles de implementar. Por ejemplo, la tarea de segmentación que tiene como objetivo extraer de manera precisa las regiones que representan los objetos en una escena. Para segmentar imágenes reales se necesitan algoritmos sofisticados que obtienen resultados de segmentación "aproximados" y, a veces, dichos algoritmos requieren un tiempo de ejecución alto.

Las redes complejas, cuyo origen está en la intersección entre la teoría de grafos y la fisica estadística, son  grafos que tienen ciertas propiedades topológicas: en general, son estructuras muy grandes (p.ej. con cientos o miles de nodos), tienen propiedades dinámicas, presentan un alto coeficiente de agrupamiento, también tienen una estructura comunitaria a diferentes escalas, o presentan evidencias de una estructura jerarquizada, etc. Existen tres modelos principales de redes complejas: las redes aleatorias, las redes libres de escala y las redes small-world. En general, este tipo de redes son fuente de inspiración para modelar estructuras (y resolver problemas) que aparecen en problemas del mundo real: por ejemplo, las redes sociales, las redes de información como Internet, los redes de transporte en ciudades (p.ej. redes de metro), las redes que modelan sistemas biológicos (p.ej. modelos de interacción de proteínas), etc. Además, las redes complejas se han aplicado a problemasde carácter multidisciplinar en áreas como las matemáticas, la física, la informática, la biología o la sociología.

Como las imágenes digitales están compuestas por estructuras (p.ej. matrices bidimensionales) de píxeles adyacentes, la teoría de redes complejas se adapta bien a muchos tipos de problemas de análisis de imágenes. El primer paso es decidir cómo representar una imagen digital mediante una red compleja. La solución más directa (aunque puede resultar costosa computacionalmente) consiste en modelar los píxeles de la imagen como nodos de la red y dichos nodos se conectan teniendo en cuenta diferentes criterios como pueden ser la distancia espacial entre los píxeles o algunas propiedades locales (p.ej. diferencias de valores de intensidad entre los nodos). Algunas de las aplicaciones de las redes complejas a problemas de análisis de imágenes son las siguientes: la segmentación basada en regiones mediante el descubrimiento de comunidades en la red compleja, el análisis de texturas basado en el grado jerárquico y en el coefiente de agrupamiento de los nodos, el análisis de formas en imágenes binarias basado en propiedades topológicas del grafo o la detección de puntos de interés en una imagen basándose en medidas de centralidad local de los nodos de la red. Esta última aplicación se muestra con un ejemplo donde el color denota la importancia de los puntos detectados para la imagen "House" (mayor valor del interés en color rojo, interés intermedio en color verde y menor interés en color azul). Los puntos de interés se detectan construyendo a partir de la imagen una red compleja y, después, calculando una medida de centralidad local sobre los nodos de la red (ver figura adjunta).


Finalmente, las posiciones de dichos puntos se "refinan" construyendo un grafo dual de la red compleja inicial e interpolando la posición de los nuevos puntos a partir de las posiciones e importancia de los puntos extremos de cada arco (ver figura adjunta).