stringtranslate.com

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 los subconjuntos de componentes conectados se etiquetan de forma única en función de una heurística determinada . 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 una interfaz de interacción hombre-computadora , el etiquetado de componentes conectados puede operar sobre 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 se puede aplicar a imágenes en escala de grises y en color. Los blobs se pueden contar, filtrar y rastrear.

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

Descripción general

4-conectividad
8-conectividad

Un gráfico, que contiene vértices y aristas de conexión , se construye a partir de datos de entrada relevantes. Los vértices contienen información requerida por la heurística de comparación, mientras que las aristas indican "vecinos" conectados. Un algoritmo recorre el gráfico, 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 gráficos de imágenes, por ejemplo, pueden ser de vecindad 4-conectada o de vecindad 8-conectada . [5]

Después de la etapa de etiquetado, el gráfico se puede dividir en subconjuntos, después de lo cual se puede recuperar y procesar la información original.

Definición

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

Rosenfeld et al. [6] definen el etiquetado de componentes conectados como la “creación de una imagen etiquetada en la que las posiciones asociadas con el mismo componente conectado de la imagen de entrada binaria tienen una etiqueta única”. Shapiro et al. [7] definen CCL como un operador cuya “entrada es una imagen binaria y [...] la salida es una imagen simbólica en la que la etiqueta asignada a cada píxel es un número 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 amplia: [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 componentes y la toma de decisiones”. La definición de análisis de componentes conectados que se presenta aquí es más general y tiene en cuenta las ideas expresadas en [7] [9] [10] .

Algoritmos

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

Un componente a la vez

Este es un método rápido y muy sencillo de implementar y comprender. Se basa en los 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 ese componente conectado antes de pasar al siguiente píxel de la imagen. Este algoritmo es parte del algoritmo de segmentación de cuencas hidrográficas de Vincent y Soille [11] , también existen otras implementaciones. [12]

Para ello, se forma una lista enlazada que mantendrá los índices de los píxeles que están conectados entre sí, pasos (2) y (3) a continuación. El método de definición de la lista enlazada especifica el uso de una búsqueda en profundidad o en amplitud . Para esta aplicación en particular, no hay diferencia en qué estrategia utilizar. El tipo más simple de cola de último en entrar, primero en salir implementada 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 , con píxeles 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 de la siguiente manera:

  1. Comience 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 a (3). Si es un píxel de fondo o ya estaba etiquetado, repita (2) para el siguiente píxel de la imagen.
  3. Extraiga un elemento de la cola y observe sus vecinos (según cualquier tipo de conectividad). Si un vecino es un píxel de primer plano y aún no está etiquetado, asígnele la etiqueta actual y agréguelo a la cola. Repita (3) hasta que no haya más elementos en la cola.
  4. Vaya a (2) para el siguiente píxel de la imagen e incremente la etiqueta actual en 1.

Tenga en cuenta que los píxeles se etiquetan antes de colocarlos en la cola. La cola solo conservará 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(data) entrada  : imageData[xDim][yDim] inicialización  : etiqueta = 0, labelArray[xDim][yDim] = 0, statusArray[xDim][yDim] = falso, cola1, cola2; para i = 0 a xDim hacer  para j = 0 a yDim hacer  si imageData[i][j] no ha sido procesado hacer  si imageData[i][j] es un píxel de primer plano hacer Compruébalo cuatro vecinos (norte, sur, este, oeste): Si el vecino no se procesa, haz lo siguiente:  si el vecino es un píxel de primer plano, haz lo siguiente: añadirlo a la cola1 demás  Actualizar su estado como procesado terminar si labelArray[i][j] = etiqueta (dar etiqueta) statusArray[i][j] = true (estado de actualización) mientras queue1 no esté vacía Para cada píxel de la cola, haga lo siguiente: Compruébalo, cuatro vecinos Si el vecino no se procesa, haz lo siguiente:  si el vecino es un píxel de primer plano, haz lo siguiente: añadirlo a la cola2 demás Actualizar su estado como procesado terminar si Dale la etiqueta actual Actualizar su estado como procesado eliminar el elemento actual de la cola1 Copiar cola2 en cola1 Fin Mientras aumentar la etiqueta termina si  no Actualizar su estado como procesado fin si  fin si  fin si  fin para  fin para

Dos pasadas

Relativamente simple de implementar y comprender, el algoritmo de dos pasadas [13] (también conocido como algoritmo 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 equivalencias de registros, 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 se pueden modificar in situ (lo que conlleva el riesgo de corrupción de datos ) o la información de etiquetado se puede mantener en una estructura de datos adicional.

Las comprobaciones de conectividad se llevan a cabo comprobando las etiquetas de los píxeles vecinos (los elementos vecinos cuyas etiquetas aún no están asignadas se ignoran), o, por ejemplo, el noreste, el norte, el noroeste y el oeste del píxel actual (suponiendo una conectividad de 8). La conectividad de 4 utiliza solo los vecinos del norte y el 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 supone una 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. Asigna la misma etiqueta al píxel actual
    2. No – Verificar siguiente condición
  2. ¿Ambos píxeles al norte y al oeste del píxel actual tienen el mismo valor que el píxel actual pero no la misma etiqueta?
    1. Sí . Sabemos que los píxeles norte y oeste pertenecen a la misma región y deben fusionarse. Asigna al píxel actual el mínimo de las etiquetas norte y oeste y registra su relación de equivalencia.
    2. No – Verificar 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 – Verificar siguiente condición
  4. ¿Los vecinos norte y oeste del píxel tienen valores de píxel diferentes que el píxel actual?
    1. Sí : crea una nueva identificación de etiqueta y asígnala 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 union-find que proporciona un excelente rendimiento para realizar un seguimiento de las relaciones de equivalencia. [14] Union-find almacena esencialmente 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 de etiqueta mínimo que es equivalente al argumento de función 'l'.

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

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, luego por fila (escaneo ráster)
  2. Si el elemento no es el fondo
    1. Obtener los elementos vecinos del elemento actual
    2. Si no hay vecinos, etiquete de forma única el elemento actual y continúe
    3. De lo contrario, busque el vecino con la etiqueta más pequeña y asígnelo al elemento actual.
    4. Almacenar la equivalencia entre etiquetas vecinas

En la segunda pasada:

  1. Iterar a través de cada elemento de los datos por columna, luego por fila
  2. Si el elemento no es el fondo
    1. Reetiquetar 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 salientes del primer plano . Si se omite la variable de fondo, el algoritmo de dos pasadas tratará el fondo como otra región.

Ejemplo gráfico de algoritmo de dos pasadas

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

Primero asignamos diferentes valores binarios a los elementos del gráfico. Los valores "0~1" en el centro de cada uno de los elementos del gráfico siguiente son 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 deben confundirse los dos conceptos.

2. Después de 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 la matriz después de realizar la fusión de etiquetas. Aquí, el valor de etiqueta que era el más pequeño para una región dada se "inunda" por toda la región conectada y da dos etiquetas distintas y, por lo tanto, dos etiquetas distintas.

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

Ejemplo de salida gráfica de la ejecución del algoritmo de dos pasadas en una imagen binaria. La primera imagen no está procesada, mientras que la última se ha vuelto a colorear con información de la etiqueta. Los tonos más oscuros indican los vecinos del píxel que se está procesando.

El pseudocódigo es:

El algoritmo TwoPass(datos) es vinculado = [] etiquetas = estructura con dimensiones de datos, inicializada con el valor de Fondo SiguienteEtiqueta = 0 Primer pase  para la fila de datos, hacer  para la columna de la fila, hacer  si datos[fila][columna] no es Fondo, entonces  vecinos = elementos conectados con el valor del elemento actual  Si los vecinos están vacíos, entonces linked[NextLabel] = conjunto que contiene NextLabel etiquetas[fila][columna] = NextLabel Etiqueta siguiente += 1  demás  Encuentra la etiqueta más pequeña  L = etiquetas de vecinos etiquetas[fila][columna] = min (L) para etiqueta en L hacer vinculado[etiqueta] = unión (vinculado[etiqueta], L)  Segundo pase  para fila en datos hacer  para columna en fila hacer  si datos[fila][columna] no es Fondo entonces etiquetas[fila][columna] = find (etiquetas[fila][columna])  etiquetas de devolución

Los algoritmos de búsqueda y unión se implementan como se describe en unión búsqueda .

Algoritmo secuencial

Crear un contador de regiones

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

Otros

Algunos de los pasos presentes en el algoritmo de dos pasadas se pueden fusionar para lograr mayor eficiencia, lo que permite realizar un único barrido de la imagen. También existen algoritmos de múltiples pasadas, algunos de los cuales se ejecutan en tiempo lineal en relación con la cantidad 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 del procesamiento secuencial de cada píxel. [17]

El interés por el algoritmo surge nuevamente con un uso extensivo de CUDA.

Pseudocódigo para el algoritmo de un componente a la vez

Algoritmo:

  1. La matriz de componentes conectados se inicializa al tamaño de la matriz de imagen.
  2. Se inicializa y se incrementa una marca para cada objeto detectado en la imagen.
  3. Se inicializa un contador para contar la cantidad de objetos.
  4. Se inicia un escaneo de fila principal 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 Imagen.
    2. Un vector (índice) se actualiza con todos los píxeles vecinos de los píxeles establecidos actualmente.
    3. Se conservan los píxeles únicos y se eliminan los píxeles repetidos.
    4. Establezca los píxeles indicados por Índice para marcar 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_of_objects  := 0 para i: 1:M  hacer  para j: 1:N  hacer  si ( imagen (i, j) == 1) entonces  no_de_objetos  := no_de_objetos + 1 índice  := [((j-1) × M + i)] conectado ( índice ) := marca  mientras ~isempty( índice ) hacer  imagen ( índice ) := 0 vecinos  := bsxfun(@plus, índice , desplazamientos ) vecinos  := únicos( vecinos (:)) índice  := vecinos (find( imagen ( vecinos ))) conectado ( índice ) := marca  fin mientras  marca  := marca + diferencia  fin si  fin para  fin para

El tiempo de ejecución del algoritmo depende del tamaño de la imagen y de la cantidad de primer plano. La complejidad temporal es comparable a la del algoritmo de dos pasadas si el primer plano cubre una parte significativa de la imagen. De lo contrario, la complejidad temporal es menor. Sin embargo, el acceso a la memoria está menos estructurado que en el algoritmo de dos pasadas, lo que tiende a aumentar el tiempo de ejecución en la práctica.

Evaluación del desempeño

En las últimas dos décadas se han propuesto muchos enfoques novedosos para el etiquetado de componentes conectados, pero casi ninguno de ellos ha sido sometido a una evaluación comparativa de rendimiento utilizando el mismo conjunto de datos. YACCLAB [18] [19] (acrónimo de Yet Another Connected Components Labeling Benchmark) es un ejemplo de un marco de código abierto C++ que recopila, ejecuta y prueba algoritmos de etiquetado de componentes conectados.

Arquitecturas de hardware

La aparición de FPGAs con capacidad suficiente para realizar tareas complejas de procesamiento de imágenes también dio lugar a arquitecturas de alto rendimiento para el etiquetado de componentes conectados. [20] [21] La mayoría de estas arquitecturas utilizan la variante de paso único de este algoritmo, debido a los recursos de memoria limitados disponibles en un FPGA . Estos tipos de arquitecturas de etiquetado de componentes conectados pueden procesar varios píxeles de imagen en paralelo, logrando así un alto rendimiento y una baja latencia de procesamiento.

Véase también

Referencias

  1. ^ Samet, H.; Tamminen, M. (1988). "Etiquetado eficiente de componentes de imágenes de dimensión arbitraria representadas por bintrees lineales". IEEE Transactions on Pattern Analysis and Machine Intelligence . 10 (4): 579. doi :10.1109/34.3918. S2CID  15911227.
  2. ^ Michael B. Dillencourt; Hannan Samet; Markku Tamminen (1992). "Un enfoque general para el etiquetado de componentes conectados para representaciones de imágenes arbitrarias". Revista de la ACM . 39 (2): 253. CiteSeerX 10.1.1.73.8846 . doi :10.1145/128749.128750. S2CID  1869184. 
  3. ^ Weijie Chen; Maryellen L. Giger; Ulrich Bick (2006). "Un enfoque basado en Fuzzy C-Means (FCM) para la segmentación computarizada de lesiones mamarias en imágenes de RM con contraste dinámico". Academic Radiology . 13 (1): 63–72. doi :10.1016/j.acra.2005.08.035. PMID  16399033.
  4. ^ Kesheng Wu; Wendy Koegler; Jacqueline Chen; Arie Shoshani (2003). "Uso de índices de mapa de bits para la exploración interactiva de conjuntos de datos de gran tamaño". SSDBM.
  5. ^ R. Fisher; S. Perkins; A. Walker; E. Wolfart (2003). "Etiquetado de componentes conectados".
  6. ^ Rosenfeld, Azriel; Pfaltz, John L. (octubre de 1966). "Operaciones secuenciales en el procesamiento digital de imágenes". J. ACM . 13 (4): 471–494. doi :10.1145/321356.321357. ISSN  0004-5411. S2CID  7391071.
  7. ^ abc Shapiro, Linda G. (1996). "Etiquetado de componentes conectados y construcción de gráficos de adyacencia". Algoritmos topológicos para el procesamiento de imágenes digitales . Inteligencia artificial y reconocimiento de patrones. Vol. 19. págs. 1–30. doi :10.1016/s0923-0459(96)80011-5. ISBN 9780444897541.
  8. ^ Klaiber, Michael J. (2016). Una arquitectura de análisis de componentes conectados de búsqueda única en paralelo y eficiente en recursos para hardware reconfigurable . Universidad de Stuttgart.
  9. ^ ab Fu, Y.; Chen, X.; Gao, H. (diciembre de 2009). "Un nuevo algoritmo de análisis de componentes conectados basado en Max-Tree". Octava conferencia internacional IEEE de 2009 sobre computación confiable, autónoma y segura . págs. 843–844. doi :10.1109/DASC.2009.150. ISBN 978-1-4244-5420-4.S2CID6805048  .​
  10. ^ ab Grana, C.; Borghesani, D.; Santinelli, P.; Cucchiara, R. (agosto de 2010). "Etiquetado de componentes conectados de alto rendimiento en FPGA". Talleres de 2010 sobre aplicaciones de bases de datos y sistemas expertos . págs. 221–225. doi :10.1109/DEXA.2010.57. ISBN 978-1-4244-8049-4.S2CID6905027  .​
  11. ^ Vincent, Luc; Soille, Pierre (junio de 1991). "Cuencas hidrográficas en espacios digitales: un algoritmo eficiente basado en simulaciones de inmersión". IEEE Transactions on Pattern Analysis and Machine Intelligence . 13 (6): 583. doi :10.1109/34.87344. S2CID  15436061.
  12. ^ Abubaker, A; Qahwaji, R; Ipson, S; Saleh, M (2007). "Técnica de etiquetado de componentes conectados con un solo escaneo". Conferencia internacional IEEE de 2007 sobre procesamiento de señales y comunicaciones . p. 1283. doi :10.1109/ICSPC.2007.4728561. ISBN 978-1-4244-1235-8. Número de identificación del sujeto  10710012.
  13. ^ Shapiro, L.; Stockman, G. (2002). Visión artificial (PDF) . Prentice Hall. págs. 69–73.
  14. ^ Introducción a los algoritmos , [1], pp498
  15. ^ Lifeng He; Yuyan Chao; Suzuki, K. (1 de mayo de 2008). "Un algoritmo de etiquetado de dos escaneos basado en ejecución". IEEE Transactions on Image Processing . 17 (5): 749–756. Bibcode :2008ITIP...17..749H. doi :10.1109/TIP.2008.919369. PMID  18390379.
  16. ^ Kenji Suzuki; Isao Horiba; Noboru Sugie (2003). "Etiquetado de componentes conectados en tiempo lineal basado en operaciones locales secuenciales". Visión artificial y comprensión de imágenes . 89 : 1–23. doi :10.1016/S1077-3142(02)00030-9.
  17. ^ Yujie Han; Robert A. Wagner (1990). "Un algoritmo de componentes conectados en paralelo eficiente y rápido". Revista de la ACM . 37 (3): 626. doi : 10.1145/79147.214077 . S2CID  17867876.
  18. ^ Grana, C.; Bolelli, F.; Baraldi, L.; Vezzani, R. (2016). "YACCLAB - Otro punto de referencia en etiquetado de componentes conectados" (PDF) . 23ª Conferencia Internacional sobre Reconocimiento de Patrones . Cancún.
  19. ^ "Otro punto de referencia para el etiquetado de componentes conectados: Prittt/YACCLAB". GitHub . 18 de febrero de 2019.
  20. ^ Bailey, DG; Johnston, CT; Ma, Ni (septiembre de 2008). "Análisis de componentes conectados de imágenes transmitidas". Conferencia internacional de 2008 sobre lógica programable en campo y aplicaciones . págs. 679–682. doi :10.1109/FPL.2008.4630038. ISBN 978-1-4244-1960-9.S2CID6503327  .​
  21. ^ MJ Klaiber; DG Bailey; Y. Baroud; S. Simon (2015). "Una arquitectura de hardware eficiente en recursos para el análisis de componentes conectados". IEEE Transactions on Circuits and Systems for Video Technology . 26 (7): 1334–1349. doi :10.1109/TCSVT.2015.2450371. S2CID  10464417.

General

Enlaces externos