Recordemos que una componente conexa es un conjunto de píxeles tal que para cualquier par de píxeles del conjunto, existe un camino digital que los une.
Algoritmo para el cálculo de componentes conexas
Primer algoritmo
Sea S una imagen digital binaria en un mallado cuadrado. Supongamos que queremos localizar las componentes conexas en nego de la imagen con la 4-adyacencia. Si un píxel se encuentra en posición (x,y), recordemos que sus vecinos pueden ser:
Recorremos la imagen de izquierda a derecha y de arriba a abajo.
Durante el primer rastreo, para cada punto que tenga valor 1, examinamos a los vecinos de arriba y a mano izquierda de P; nótese que si existen, acaban de ser visitados por el rastreo, así que si son 1’s, ya han sido etiquetados.
Si ambos son 0’s, damos a P una nueva etiqueta;
si tan sólo uno es 0, le damos a P la etiqueta del otro;
y si ninguno es 0’s, le damos a P (por ejemplo) la etiqueta del de la izquierda, y si sus etiquetas son diferentes, registramos el hecho de que son equivalentes, i.e., pertenecen a la misma componente.
Cuando se completa este rastreo, cada 1 tiene una etiqueta, pero puede que se asignen muchas etiquetas diferentes a puntos en el mismo componente. Ahora ordenamos las parejas equivalentes en clases de equivalencia, y escogemos una etiqueta para representar cada clase. Finalmente, realizamos un segundo rastreo de la imagen y sustituimos cada etiqueta por el representante de cada clase; cada componente ha sido ahora etiquetada de forma única.
Consideremos la siguiente imagen:
El resultado del primer rastreo, usando 4-adyacencia es :
Resultado del segundo rastreo, reemplazando todas las etiquetas equivalentes por una representativa:
Si consideramos al 8-adyacencia para negro, para cada píxel P(x,y) en negro, examinamos los píxeles superiores A(x+1,y-1), B(x,y-1), C(x-1,y-1) y D(x-1,y).
Si todos sus vecinos son blancos, damos al actual píxel una etiqueta nueva.
En otro caso, si uno de sus vecinos es negro, al píxel P le damos la misma etiqueta que la del píxel negro.
Si dos o más píxeles son negros, le damos a P una de las etiquetas y anotamos que dichas etiquetas son equivalentes.
El proceso de equivalencia y re-etiquetado se realiza como en el caso de 4-adyacencia.
Resultados del primer rastreo usando el algoritmo de 8-adyacencia:
Alternativamente, para cada píxel P(x,y) de la imagen, sea blanco o negro, podemos examinar a los vecinos B(x,y-1), C(x-1,y-1) y D(x-1,y). Procedemos como antes si P es 1. Si P es 0, pero dos o más de sus vecinos B, C ó D son 1, anotamos la equivalencia de sus etiquetas.
Resultados del primer rastreo usando la segunda versión del algoritmo de 8-adyacencia:
Segundo algoritmo
Diferentes algoritmos pueden ser ideados para etiquetar componentes en paralelo. Por ejemplo, supongamos que primero le damos a cada 1 una única etiqueta. Entonces podemos realizar repetidamente una operación de máximo local en paralelo, donde el máximo está definido por el orden lexicográfico de los pares de coordenadas;
Los puntos etiquetados 0 permanecen 0.
Usamos el máximo 4-vecino si queremos etiquetar 4-componentes, y 8-vecinos para 8-componentes.
Cuando se itera hasta que no haya más cambios, cada punto de una componente dada está etiquetado con las coordenadas de los puntos más inferiores-derecha.
Ejercicio:
a) Establecer un algoritmo para el cálculo del número de agujeros de una imagen.
Ayuda: El número de agujeros coincide con el número de componentes conexas del fondo de la imagen -1.
b) Establecer algoritmos de etiquetados de componentes conexas para el resto de los mallados.
Una vez que hayamos etiquetado las componentes conexas, sabremos cuántas componentes tiene, ya que es justo el número de etiquetas finales usadas.
Algoritmo de cáculo de número de componentes conexas
Otra forma de contar el número de componentes conexas en negro (usando la (8,4)-adyacencia (8 para negro y 4 para blanco) sería eliminando píxeles de la siguiente forma:
Sea P un píxel de la imagen I. Consideremos los siguientes vecinos:
| P | X |
| Y | Z |
Definamos una función f: I -> I, tal que:
Si P es blanco (0) entonces f(P)=1 si y sólo si X=Y=1.
Si P es negro (1) entonces f(P)=0 si y sólo si X=Y=Z=0 (excepto si P está totalmente aislado, es decir, rodeado de píxeles blancos).
En cualquier otro caso, f(P)=P.
Cualquier componente conexa en negro de la imagen se colapsa al punto cuya coordenada x coincide con la coordenada x del píxel más a la izquierda y cuya coordenada y coincide con la coordenada y del píxel que se encuentra más al norte. Contando los píxeles aislados que quedan al final obtendremos el número de componentes conexas en blanco.
Observemos que con este proceso se ha perdido toda la geometría y topología de la imagen.
Borde de una imagen digital
Dada una imagen con la (p,q)-adyacencia (p-adyacencia para negro y q-adyacencia para blanco), El borde de la imagen (en negro) es el conjunto de píxeles en negro que tienen, al menos un q-vecino en blanco.
Análogamente, el borde de la imagen (en blanco), es el conjunto de píxeles en banco que tienen, al menos, un p-vecino en negro.
Punto simple
Un píxel negro P del borde de la imagen se considera simple si el conjunto de los vecinos en negro de P tienen exactamente una componente conexa que es adyacente a P.
Por otro lado, un punto es final si tiene exactamente un vecino negro; un punto final no es más que un punto extremo de la imagen.
Un algoritmo de adelgazamiento
Básicamente, el procedimiento de adelgazamiento consiste en ir borrando sucesivamente los puntos del borde de la imagen, de forma que se preserve la topología de la figura.
Las condiciones exactas que determinan si un punto se puede borrar están relacionadas con el concepto de punto simple y punto final. Más concretamente, un punto del borde de la imagen se puede eliminar si es simple y no es final.
El borrado de puntos debe seguir un esquema de barridos sucesivos para que la imagen siga teniendo las mismas proporciones que la original y conseguir así que no quede deformada. El borrado en cada rastreo debe hacerse en paralelo, es decir, señalar todos los píxeles "borrables" para eliminarlos todos a la vez.
Ejercicio:
a) Establecer todas las configuraciones posibles de puntos simples y puntos finales que puedan aparecer en el borde de una imagen.
Para practicar: