Etiquetado de componentes conectados

El etiquetado de componentes conectados ( CCL ), el análisis de componentes conectados ( CCA ), la extracción de blobs , el etiquetado de regiones , el descubrimiento de blobs o la extracción de regiones es una aplicación algorítmica de la teoría de grafos , donde subconjuntos de componentes conectados se etiquetan de forma única en función de una heurística dada . El etiquetado de componentes conectados no debe confundirse con la segmentación .

El etiquetado de componentes conectados se utiliza en visión artificial para detectar regiones conectadas en imágenes digitales binarias , aunque también se pueden procesar imágenes en color y datos con mayor dimensionalidad. ^{[ 1 ] [ 2 ]} Cuando se integra en un sistema de reconocimiento de imágenes o en una interfaz de interacción humano-computadora , el etiquetado de componentes conectados puede operar con una variedad de información. ^{[ 3 ] [ 4 ]} La extracción de blobs generalmente se realiza en la imagen binaria resultante de un paso de umbralización, pero también puede aplicarse a imágenes en escala de grises y en color. Los blobs pueden contarse, filtrarse y rastrearse.

La extracción de blobs está relacionada con la detección de blobs, pero es distinta de ella .

Se construye un grafo, que contiene vértices y aristas de conexión , a partir de los datos de entrada relevantes. Los vértices contienen la información requerida por la heurística de comparación, mientras que las aristas indican los "vecinos" conectados. Un algoritmo recorre el grafo, etiquetando los vértices en función de la conectividad y los valores relativos de sus vecinos. La conectividad está determinada por el medio; los grafos de imágenes, por ejemplo, pueden ser de vecindario de 4 conexiones o de vecindario de 8 conexiones . ^{[ 5 ]}

Tras la fase de etiquetado, el grafo puede dividirse en subconjuntos, después de lo cual se puede recuperar y procesar la información original.

El uso del término etiquetado de componentes conectados (CCL, por sus siglas en inglés) y su definición son bastante consistentes en la literatura académica, mientras que el análisis de componentes conectados (CCA, por sus siglas en inglés) varía tanto en la terminología como en la definición del problema.

Rosenfeld et al. ^{[ 6 ]} definen el etiquetado de componentes conectados como la “[c]reación de una imagen etiquetada en la que las posiciones asociadas con el mismo componente conectado de la imagen binaria de entrada tienen una etiqueta única”. Shapiro et al. ^{[ 7 ]} definen CCL como un operador cuya “entrada es una imagen binaria y [...] salida es una imagen simbólica en la que la etiqueta asignada a cada píxel es un entero que identifica de forma única el componente conectado al que pertenece ese píxel”. ^{[ 8 ]}

No existe consenso sobre la definición de CCA en la literatura académica. A menudo se utiliza indistintamente con CCL. ^{[ 9 ] [ 10 ]} Shapiro et al. ofrecen una definición más extensa: ^{[ 7 ]} “El análisis de componentes conectados consiste en el etiquetado de componentes conectados de los píxeles negros, seguido de la medición de propiedades de las regiones de componentes y la toma de decisiones”. La definición de análisis de componentes conectados que se presenta aquí es más general, teniendo en cuenta las ideas expresadas en ^{[ 7 ] [ 9 ] [ 10 ]} .

Los algoritmos analizados pueden generalizarse a dimensiones arbitrarias , aunque con una mayor complejidad temporal y espacial .

Este es un método rápido y muy sencillo de implementar y comprender. Se basa en métodos de recorrido de grafos de la teoría de grafos. En resumen, una vez que se encuentra el primer píxel de un componente conectado, se etiquetan todos los píxeles conectados de dicho componente antes de pasar al siguiente píxel de la imagen. Este algoritmo forma parte del algoritmo de segmentación por cuencas hidrográficas de Vincent y Soille ^{[ 11 ]} , aunque también existen otras implementaciones ^{[ 12 ] .}

Para ello, se crea una lista enlazada que almacena los índices de los píxeles conectados entre sí, como se describe en los pasos (2) y (3) a continuación. El método para definir la lista enlazada especifica el uso de una búsqueda en profundidad o en amplitud . Para esta aplicación en particular, no hay diferencia entre ambas estrategias. La implementación más sencilla de una cola de último en entrar, primero en salir ( LIFO ), como una lista enlazada simple, dará como resultado una estrategia de búsqueda en profundidad.

Se supone que la imagen de entrada es una imagen binaria , donde los píxeles son de fondo o de primer plano, y que se desean los componentes conectados en los píxeles de primer plano. Los pasos del algoritmo se pueden escribir como:

1. Empiece desde el primer píxel de la imagen. Establezca la etiqueta actual en 1. Vaya a (2).
2. Si este píxel es un píxel de primer plano y aún no está etiquetado, asígnele la etiqueta actual y agréguelo como el primer elemento de una cola; luego, vaya al paso (3). Si es un píxel de fondo o ya estaba etiquetado, repita el paso (2) para el siguiente píxel de la imagen.
3. Extrae un elemento de la cola y observa sus vecinos (según cualquier tipo de conectividad). Si un vecino es un píxel en primer plano y aún no está etiquetado, asígnale la etiqueta actual y agrégalo a la cola. Repite el paso (3) hasta que no queden más elementos en la cola.
4. Vaya a (2) para el siguiente píxel en la imagen e incremente la etiqueta actual en 1.

Tenga en cuenta que los píxeles se etiquetan antes de agregarlos a la cola. La cola solo retendrá un píxel para verificar sus vecinos y agregarlos a la cola si es necesario. Este algoritmo solo necesita verificar los vecinos de cada píxel de primer plano una vez y no verifica los vecinos de los píxeles de fondo.

El pseudocódigo es:

algoritmo OneComponentAtATime(datos) entrada  : imageData[xDim][yDim] inicialización  : etiqueta = 0, labelArray[xDim][yDim] = 0, statusArray[xDim][yDim] = false, cola1, cola2; para i = 0 hasta xDim hacer para j = 0 hasta yDim hacer si imageData[i][j] no ha sido procesado hacer si imageData[i][j] es un píxel de primer plano hacer comprueba sus cuatro vecinos (norte, sur, este, oeste): Si el vecino no se procesa , si el vecino es un píxel de primer plano , agregarlo a la cola1 demás Actualizar su estado a procesado fin si labelArray[i][j] = etiqueta (indicar etiqueta) statusArray[i][j] = verdadero (actualizar estado) mientras la cola1 no esté vacía, haga lo siguiente: Para cada píxel en la cola, haga lo siguiente: comprueba sus cuatro vecinos Si el vecino no se procesa , si el vecino es un píxel de primer plano , agregarlo a la cola2 demás Actualizar su estado a procesado fin si darle la etiqueta actual Actualizar su estado a procesado eliminar el elemento actual de la cola1 copiar cola2 en cola1 fin Mientras aumentar la etiqueta fin si no Actualizar su estado a procesado fin si fin si fin si fin para fin para

Relativamente sencillo de implementar y comprender, el algoritmo de dos pasadas, ^{[ 13 ]} (también conocido como algoritmo de Hoshen-Kopelman ) itera a través de datos binarios bidimensionales . El algoritmo realiza dos pasadas sobre la imagen: la primera pasada para asignar etiquetas temporales y registrar equivalencias, y la segunda pasada para reemplazar cada etiqueta temporal por la etiqueta más pequeña de su clase de equivalencia .

Los datos de entrada pueden modificarse in situ (lo que conlleva el riesgo de corrupción de datos ), o bien la información de etiquetado puede mantenerse en una estructura de datos adicional.

Las comprobaciones de conectividad se realizan verificando las etiquetas de los píxeles vecinos (se ignoran los elementos vecinos cuyas etiquetas aún no se han asignado), o, por ejemplo, el noreste, el norte, el noroeste y el oeste del píxel actual (suponiendo conectividad de 8). La conectividad de 4 utiliza solo los vecinos norte y oeste del píxel actual. Se comprueban las siguientes condiciones para determinar el valor de la etiqueta que se asignará al píxel actual (se asume conectividad de 4).

Condiciones a comprobar:

1. ¿El píxel de la izquierda (oeste) tiene el mismo valor que el píxel actual?
   1. Sí , estamos en la misma región. Asigne la misma etiqueta al píxel actual.
   2. No – Compruebe la siguiente condición
2. ¿Los píxeles situados al norte y al oeste del píxel actual tienen el mismo valor que este, pero no la misma etiqueta?
   1. Sí , sabemos que los píxeles norte y oeste pertenecen a la misma región y deben fusionarse. Asigne al píxel actual el valor mínimo de las etiquetas norte y oeste, y registre su relación de equivalencia.
   2. No – Compruebe la siguiente condición
3. ¿El píxel de la izquierda (oeste) tiene un valor diferente y el del norte el mismo valor que el píxel actual?
   1. Sí – Asignar la etiqueta del píxel norte al píxel actual
   2. No – Compruebe la siguiente condición
4. ¿Los píxeles vecinos al norte y al oeste del píxel actual tienen valores diferentes?
   1. Sí , crea un nuevo ID de etiqueta y asígnalo al píxel actual.

El algoritmo continúa de esta manera y crea nuevas etiquetas de región cuando sea necesario. Sin embargo, la clave para un algoritmo rápido es cómo se realiza esta fusión. Este algoritmo utiliza la estructura de datos de unión-búsqueda que proporciona un rendimiento excelente para mantener un registro de las relaciones de equivalencia. ^{[ 14 ]} La unión-búsqueda esencialmente almacena etiquetas que corresponden al mismo blob en una estructura de datos de conjunto disjunto , lo que facilita recordar la equivalencia de dos etiquetas mediante el uso de un método de interfaz. Por ejemplo: findSet(l). findSet(l) devuelve el valor mínimo de etiqueta que es equivalente al argumento de la función 'l'.

Una vez completado el etiquetado inicial y el registro de equivalencias, la segunda pasada simplemente reemplaza cada etiqueta de píxel con su elemento representativo equivalente del conjunto disjunto.

A continuación se presenta un algoritmo de escaneo más rápido para la extracción de regiones conectadas. ^{[ 15 ]}

En la primera pasada:

1. Iterar a través de cada elemento de los datos por columna y luego por fila (escaneo raster).
2. Si el elemento no es el fondo
   1. Obtener los elementos vecinos del elemento actual.
   2. Si no hay vecinos, asigne una etiqueta única al elemento actual y continúe.
   3. De lo contrario, encuentra el vecino con la etiqueta más pequeña y asígnalo al elemento actual.
   4. Almacenar la equivalencia entre etiquetas vecinas

En la segunda pasada:

1. Recorra cada elemento de los datos por columna y luego por fila.
2. Si el elemento no es el fondo
   1. Reetiqueta el elemento con la etiqueta equivalente más baja.

Aquí, el fondo es una clasificación específica de los datos, que se utiliza para distinguir los elementos relevantes del primer plano . Si se omite la variable de fondo, el algoritmo de dos pasadas tratará el fondo como otra región.

1. A continuación se muestra la matriz de la que se extraerán las regiones conectadas (basada en conectividad de 8).

Primero asignamos diferentes valores binarios a los elementos del gráfico. Los valores "0~1" en el centro de cada elemento del siguiente gráfico representan los valores de los elementos, mientras que los valores "1,2,...,7" en los dos gráficos siguientes son las etiquetas de los elementos. No se deben confundir ambos conceptos.

2. Tras la primera pasada, se generan las siguientes etiquetas:

Se generan un total de 7 etiquetas de acuerdo con las condiciones resaltadas anteriormente.

Las relaciones de equivalencia de etiquetas generadas son:

3. Se genera una matriz después de fusionar las etiquetas. En este caso, el valor de la etiqueta más pequeño de una región determinada se propaga por toda la región conectada, generando dos etiquetas distintas.

4. Resultado final en color para ver claramente dos regiones diferentes que se han encontrado en la matriz.

El pseudocódigo es:

El algoritmo TwoPass(datos) es vinculado = [] etiquetas = estructura con dimensiones de datos, inicializada con el valor de Fondo Siguiente etiqueta = 0 Primer pasepara cada fila en datos hacer para cada columna en fila hacer si data[fila][columna] no es Background entonces vecinos = elementos conectados con el valor del elemento actual Si neighbors está vacío, entonces linked[NextLabel] = conjunto que contiene NextLabel etiquetas[fila][columna] = SiguienteLabel Siguiente etiqueta += 1 demásEncuentra la etiqueta más pequeña L = etiquetas de vecinos etiquetas[fila][columna] = min (L) para etiqueta en L hacer enlazado[etiqueta] = unión (enlazado[etiqueta], L) Segundo pasepara cada fila en los datos hacer para cada columna en la fila hacer si data[row][column] no es Background entonces labels[row][column] = find (labels[row][column]) etiquetas de devolución

Los algoritmos find y union se implementan como se describe en union find .

Crear un contador de región

Escanee la imagen (en el siguiente ejemplo, se supone que el escaneo se realiza de izquierda a derecha y de arriba abajo):

• Para cada píxel, compruebe el píxel norte y oeste (cuando se considera la conectividad de 4) o el píxel noreste , norte , noroeste y oeste para la conectividad de 8 para un criterio de región dado (es decir, valor de intensidad de 1 en la imagen binaria, o intensidad similar a los píxeles conectados en la imagen en escala de grises).
• Si ninguno de los vecinos cumple el criterio, entonces asigne a la región el valor del contador de región. Incremente el contador de región.
• Si solo un vecino cumple el criterio, asigne el píxel a esa región.
• Si varios vecinos coinciden y todos pertenecen a la misma región, asigne el píxel a su región.
• Si varios vecinos coinciden y pertenecen a regiones diferentes, asigne el píxel a una de las regiones (no importa cuál). Indique que todas estas regiones son equivalentes.
• Escanee la imagen nuevamente, asignando a todas las regiones equivalentes el mismo valor de región.

Algunos de los pasos presentes en el algoritmo de dos pasadas se pueden combinar para mayor eficiencia, lo que permite un único recorrido de la imagen. También existen algoritmos de múltiples pasadas, algunos de los cuales se ejecutan en tiempo lineal en relación con el número de píxeles de la imagen. ^{[ 16 ]}

A principios de la década de 1990, hubo un interés considerable en paralelizar algoritmos de componentes conectados en aplicaciones de análisis de imágenes , debido al cuello de botella que suponía el procesamiento secuencial de cada píxel. ^{[ 17 ]}

El interés por el algoritmo resurge con el uso extensivo de CUDA .

Algoritmo:

1. La matriz de componentes conectados se inicializa al tamaño de la matriz de la imagen.
2. Se inicializa y se incrementa una marca por cada objeto detectado en la imagen.
3. Se inicializa un contador para contar el número de objetos.
4. Se inicia un escaneo por filas para toda la imagen.
5. Si se detecta un píxel de objeto, se repiten los siguientes pasos mientras (Índice != 0).
   1. Establezca el píxel correspondiente en 0 en la imagen.
   2. Un vector (índice) se actualiza con todos los píxeles vecinos de los píxeles actualmente seleccionados.
   3. Se conservan los píxeles únicos y se eliminan los píxeles repetidos.
   4. Establezca los píxeles indicados por Índice para marcarlos en la matriz de componentes conectados.
6. Incrementa el marcador de otro objeto en la imagen.

Un componente a la vez ( imagen ) [M, N] := tamaño( imagen ) conectado  := ceros(M, N) marca  := valor diferencia  := incremento desplazamientos  := [-1; M; 1; -M] índice  := [] no_de_objetos  := 0 for i: 1:Mdofor j: 1:Ndoif (image(i, j) == 1) thenno_of_objects := no_of_objects + 1 index := [((j-1) × M + i)] connected(index) := markwhile ~isempty(index) doimage(index) := 0 neighbors := bsxfun(@plus, index, offsets) neighbors := unique(neighbors(:)) index := neighbors(find(image(neighbors))) connected(index) := markend whilemark := mark + differenceend ifend forend for

The run time of the algorithm depends on the size of the image and the amount of foreground. The time complexity is comparable to the two pass algorithm if the foreground covers a significant part of the image. Otherwise the time complexity is lower. However, memory access is less structured than for the two-pass algorithm, which tends to increase the run time in practice.

In the last two decades many novel approaches to connected-component labeling have been proposed, but almost none of them have been subjected to a comparative performance assessment using the same data set. YACCLAB ^[18][19] (acronym for Yet Another Connected Components Labeling Benchmark) is an example of C++ open source framework which collects, runs, and tests connected-component labeling algorithms.

The emergence of FPGAs with enough capacity to perform complex image processing tasks also led to high-performance architectures for connected-component labeling.^[20][21] Most of these architectures utilize the single pass variant of this algorithm, because of the limited memory resources available on an FPGA. These types of connected component labeling architectures can process several image pixels in parallel, thereby achieving high throughput and low processing latency.

• Feature extraction
• Flood fill

• Horn, Berthold KP (1986). Visión robótica . MIT Press . págs.  69–71 . ISBN 978-0-262-08159-7.

• Al Bovik (2000). Manual de procesamiento de imágenes y vídeo (PDF) . Academic Press . págs. [37–70]. ISBN 0-12-119790-5.

• Implementación en C#
• Acerca de la extracción de objetos de imágenes y el algoritmo de etiquetado de componentes conectados directos.