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 , en la que 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 por computadora 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 persona-computadora , el etiquetado de componentes conectados puede operar con una variedad de información. [3] [4] La extracción de blobs se realiza generalmente en la imagen binaria resultante de un paso de umbral, pero también puede ser aplicable a imágenes en escala de grises y en color. Los blobs se pueden contar, filtrar y rastrear.
La extracción de manchas está relacionada con la detección de manchas, pero es distinta .
Descripción general
Un gráfico, que contiene vértices y bordes 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 los bordes indican 'vecinos' conectados. Un algoritmo atraviesa 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 vecindarios conectados con 4 o vecindarios conectados con 8 . [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 tanto en términos de terminología como de definición del problema.
Rosenfeld y col. [6] define 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 de entrada binaria tienen una etiqueta única". Shapiro y col. [7] define 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 usa indistintamente con CCL. [9] [10] Shapiro et al dan una definición más amplia: [7] "El análisis de componentes conectados consiste en el etiquetado de los componentes conectados de los píxeles negros seguido de la medición de las 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, teniendo en cuenta las ideas expresadas en [9] [10] [7] .
Algoritmos
Los algoritmos discutidos pueden generalizarse a dimensiones arbitrarias, aunque con una mayor complejidad temporal y espacial.
Un componente a la vez
Este es un método rápido y muy simple de implementar y comprender. Se basa en métodos de recorrido de grafos en la teoría de grafos. En resumen, una vez que se encuentra el primer píxel de un componente conectado, todos los píxeles conectados de ese componente conectado se etiquetan 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 para definir la lista enlazada especifica el uso de una primera búsqueda en profundidad o en amplitud . Para esta aplicación en particular, no hay diferencia qué estrategia utilizar. El tipo más simple de cola de último en entrar, primero en salir implementado como una lista enlazada individual dará como resultado una estrategia de búsqueda en profundidad primero.
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 como:
- Empiece por el primer píxel de la imagen. Establezca la etiqueta actual en 1. Vaya a (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 en 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.
- Saque un elemento de la cola y mire a 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.
- 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 ponerlos en la cola. La cola solo mantendrá 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.
Dos pasadas
Relativamente simple de implementar y comprender, el algoritmo de dos pasos, [13] (también conocido como el 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 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 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 digamos, el noreste, el norte, el noroeste y el oeste del píxel actual (asumiendo 8- conectividad). La conectividad 4 utiliza solo los vecinos Norte y Oeste del píxel actual. Se verifican las siguientes condiciones para determinar el valor de la etiqueta que se asignará al píxel actual (se supone 4-conectividad)
Condiciones a comprobar:
- ¿El píxel de la izquierda (oeste) tiene el mismo valor que el píxel actual?
- Sí , estamos en la misma región. Asignar la misma etiqueta al píxel actual
- No : marque la siguiente condición
- ¿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?
- Sí : sabemos que los píxeles norte y oeste pertenecen a la misma región y deben fusionarse. Asigne al píxel actual el mínimo de las etiquetas Norte y Oeste, y registre su relación de equivalencia
- No : marque la siguiente condición
- ¿El píxel de la izquierda (oeste) tiene un valor diferente y el del norte el mismo valor que el píxel actual?
- Sí : asigne la etiqueta del píxel norte al píxel actual
- No : marque la siguiente condición
- ¿Los vecinos norte y oeste del píxel tienen valores de píxel diferentes a los del píxel actual?
- Sí : cree una nueva identificación de etiqueta y asígnela al píxel actual
El algoritmo continúa de esta manera y crea nuevas etiquetas de región siempre que 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 rendimiento excelente 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 conjuntos disjuntos , 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 la función 'l'.
Una vez que se completa el registro inicial de etiquetado y equivalencia, la segunda pasada simplemente reemplaza cada etiqueta de píxel con su elemento representativo de 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:
- Iterar a través de cada elemento de los datos por columna, luego por fila (Escaneo Raster)
- Si el elemento no es el fondo
- Obtener los elementos vecinos del elemento actual
- Si no hay vecinos, etiquete de forma única el elemento actual y continúe
- De lo contrario, busque el vecino con la etiqueta más pequeña y asígnelo al elemento actual
- Almacene la equivalencia entre etiquetas vecinas
En el segundo pase:
- Iterar a través de cada elemento de los datos por columna, luego por fila
- Si el elemento no es el fondo
- Vuelva a etiquetar 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 destacados del primer plano . Si se omite la variable de fondo, el algoritmo de dos pasos tratará el fondo como otra región.
Ejemplo gráfico de algoritmo de dos pasos
1. La matriz de la que se extraerán las regiones conectadas se indica a continuación (basada en 8 conectividad).
Primero asignamos diferentes valores binarios a los elementos del gráfico. Los valores "0 ~ 1" en el centro de cada uno de los elementos en el siguiente gráfico son los valores de los elementos, mientras que los valores "1,2, ..., 7" en los siguientes dos gráficos son las etiquetas de los elementos. Los dos conceptos no deben confundirse.
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,
Pon la identificacion | Etiquetas equivalentes |
---|---|
1 | 1,2 |
2 | 1,2 |
3 | 3,4,5,6,7 |
4 | 3,4,5,6,7 |
5 | 3,4,5,6,7 |
6 | 3,4,5,6,7 |
7 | 3,4,5,6,7 |
3. Matriz generada después de que se lleva a cabo la fusión de etiquetas. Aquí, el valor de etiqueta que era el más pequeño para una región dada "inunda" a través de 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.
El pseudocódigo es:
algoritmo TwoPass (datos) es vinculado = [] etiquetas = estructura con dimensiones de datos, inicializada con el valor de Fondo NextLabel = 0 Primer pase para la fila en los datos hacer para la columna en la fila hacer si los datos [fila] [columna] no son Fondo, entonces vecinos = elementos conectados con el valor del elemento actual si los vecinos están vacíos, entonces vinculado [NextLabel] = conjunto que contiene NextLabel etiquetas [fila] [columna] = NextLabel NextLabel + = 1 demás Encuentra la etiqueta más pequeña L = etiquetas de vecinos etiquetas [fila] [columna] = min (L) para la etiqueta en L do vinculado [etiqueta] = unión (vinculado [etiqueta], L) Segundo pase para la fila en los datos hacer para la columna en la fila hacer si los datos [fila] [columna] no son Fondo, entonces etiquetas [fila] [columna] = buscar (etiquetas [fila] [columna]) etiquetas de devolución
Los algoritmos de búsqueda y unión se implementan como se describe en búsqueda de unión .
Algoritmo secuencial
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 a abajo):
- Para cada píxel, verifique el píxel norte y oeste (al considerar la conectividad 4 ) o el píxel noreste , norte , noroeste y oeste para la conectividad 8 para un criterio de región dado (es decir, valor de intensidad de 1 en la imagen binaria, o intensidad similar a píxeles conectados en la imagen en escala de grises).
- Si ninguno de los vecinos se ajusta al criterio, asigne el valor de región del contador de región. Contador de región incremental.
- Si solo un vecino se ajusta al criterio, asigne un píxel a esa región.
- Si varios vecinos coinciden y todos son miembros de la misma región, asigne un píxel a su región.
- Si varios vecinos coinciden y son miembros de diferentes regiones, asigne píxeles 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.
Otros
Algunos de los pasos presentes en el algoritmo de dos pasos se pueden combinar para mayor eficiencia, lo que permite un solo barrido a través 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. [dieciséis]
A principios de la década de 1990, había 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:
- La matriz de componentes conectados se inicializa al tamaño de la matriz de imagen.
- Se inicializa y aumenta una marca para cada objeto detectado en la imagen.
- Se inicializa un contador para contar el número de objetos.
- Se inicia un escaneo de fila principal para toda la imagen.
- Si se detecta un píxel de un objeto, los siguientes pasos se repiten mientras (Índice! = 0)
- Establezca el píxel correspondiente en 0 en Imagen.
- Un vector (índice) se actualiza con todos los píxeles vecinos de los píxeles configurados actualmente.
- Los píxeles únicos se retienen y los píxeles repetidos se eliminan.
- Establezca los píxeles indicados por el índice para marcar en la matriz de componentes conectados.
- 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 : = diferencia de valor : = compensaciones de incremento : = [-1; METRO; 1; -M] índice : = [] no_of_objects : = 0 for i: 1: M do for j: 1: N do if ( image (i, j) == 1) then no_of_objects : = no_of_objects + 1 index : = [((j-1) × M + i)] conectado ( índice ): = marcar mientras ~ está vacío ( índice ) hacer imagen ( índice ): = 0 vecinos : = bsxfun (@plus, índice , compensaciones ) vecinos : = único ( vecinos (:)) índice : = vecinos (buscar ( imagen ( vecinos ))) conectado ( índice ): = marcar final mientras marca : = marcar + diferencia final si final para final para
El tiempo de ejecución del algoritmo depende del tamaño de la imagen y la cantidad de primer plano. La complejidad del tiempo es comparable al algoritmo de dos pasos si el primer plano cubre una parte significativa de la imagen. De lo contrario, la complejidad del tiempo es menor. Sin embargo, el acceso a la memoria está menos estructurado que para el algoritmo de dos pasos, 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 sobre el etiquetado de componentes conectados y casi ninguno de ellos se comparó con los mismos datos. YACCLAB [18] [19] (acrónimo de Yet Another Connected Components Labeling Benchmark) es un ejemplo de marco de código abierto C ++ que recopila, ejecuta y prueba algoritmos de etiquetado de componentes conectados.
Arquitecturas de hardware
La aparición de FPGA con capacidad suficiente para realizar tareas complejas de procesamiento de imágenes también condujo a arquitecturas de alto rendimiento para el etiquetado de componentes conectados. [20] [21] La mayoría de estas arquitecturas utilizan la variante de un solo paso de este algoritmo, debido a los recursos de memoria limitados disponibles en una FPGA . Estos tipos de arquitecturas de etiquetado de componentes conectados pueden procesar varios píxeles de imagen en paralelo, lo que permite lograr un alto rendimiento con una baja latencia de procesamiento.
Ver también
- Extracción de características
- Relleno de inundación
Referencias
- ^ Samet, H .; Tamminen, M. (1988). "Etiquetado de componentes eficiente de imágenes de dimensión arbitraria representadas por bintres lineales". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 10 (4): 579. doi : 10.1109 / 34.3918 .
- ^ 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 .
- ^ Weijie Chen; Maryellen L. Giger; Ulrich Bick (2006). "Un enfoque basado en C-Means difusos (FCM) para la segmentación computarizada de lesiones mamarias en imágenes de resonancia magnética con contraste dinámico". Radiología académica . 13 (1): 63–72. doi : 10.1016 / j.acra.2005.08.035 . PMID 16399033 .
- ^ Kesheng Wu; Wendy Koegler; Jacqueline Chen; Arie Shoshani (2003). "Uso de índice de mapa de bits para la exploración interactiva de conjuntos de datos de gran parte" . SSDBM.
- ^ R. Fisher; S. Perkins; A. Walker; E. Wolfart (2003). "Etiquetado de componentes conectados" .
- ^ Rosenfeld, Azriel; Pfaltz, John L. (octubre de 1966). "Operaciones secuenciales en el procesamiento de imágenes digitales". J. ACM . 13 (4): 471–494. doi : 10.1145 / 321356.321357 . ISSN 0004-5411 .
- ^ a b c Shapiro, Linda G. (1996). "Construcción de gráficos de adyacencia y etiquetado de componentes conectados". Algoritmos topológicos para el procesamiento de imágenes digitales . Inteligencia de máquina y reconocimiento de patrones. 19 . págs. 1-30. doi : 10.1016 / s0923-0459 (96) 80011-5 . ISBN 9780444897541.
- ^ Klaiber, Michael J. (2016). Una arquitectura de análisis de componentes conectados de búsqueda única paralela y eficiente en el uso de recursos para hardware reconfigurable . Universidad de Stuttgart.
- ^ a b Fu, Y .; Chen, X .; Gao, H. (diciembre de 2009). Un nuevo algoritmo de análisis de componentes conectados basado en Max-Tree . 2009 Octava Conferencia Internacional IEEE sobre Computación Confiable, Autonómica y Segura . págs. 843–844. doi : 10.1109 / DASC.2009.150 . ISBN 978-1-4244-5420-4.
- ^ a b Grana, C .; Borghesani, D .; Santinelli, P .; Cucchiara, R. (agosto de 2010). Etiquetado de componentes conectados de alto rendimiento en FPGA . 2010 Talleres 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.
- ^ Vincent, Luc; Soille, Pierre (junio de 1991). "Cuencas hidrográficas en espacios digitales: un algoritmo eficiente basado en simulaciones de inmersión". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 13 (6): 583. doi : 10.1109 / 34.87344 .
- ^ Abubaker, A; Qahwaji, R; Ipson, S; Saleh, M (2007). Técnica de etiquetado de componentes conectados con un solo escaneo . Procesamiento de señales y comunicaciones, 2007. ICSPC 2007. Conferencia Internacional IEEE . pag. 1283. doi : 10.1109 / ICSPC.2007.4728561 . ISBN 978-1-4244-1235-8.
- ^ Shapiro, L .; Stockman, G. (2002). Visión por computadora (PDF) . Prentice Hall. págs. 69–73.
- ^ Introducción a los algoritmos , [1] , pp498
- ^ Lifeng He; Yuyan Chao; Suzuki, K. (1 de mayo de 2008). "Un algoritmo de etiquetado de dos escaneos basado en ejecución". Transacciones IEEE sobre procesamiento de imágenes . 17 (5): 749–756. Código Bibliográfico : 2008ITIP ... 17..749H . doi : 10.1109 / TIP.2008.919369 . PMID 18390379 .
- ^ Kenji Suzuki; Isao Horiba; Noboru Sugie (2003). "Etiquetado de componentes conectados en tiempo lineal basado en operaciones locales secuenciales". Visión por computadora y comprensión de imágenes . 89 : 1–23. doi : 10.1016 / S1077-3142 (02) 00030-9 .
- ^ Yujie Han; Robert A. Wagner (1990). "Un algoritmo de componente conectado en paralelo eficiente y rápido". Revista de la ACM . 37 (3): 626. doi : 10.1145 / 79147.214077 .
- ^ Grana, C .; Bolelli, F .; Baraldi, L .; Vezzani, R. (2016). "YACCLAB - Otro punto de referencia de etiquetado de componentes conectados" (PDF) . 23ª Conferencia Internacional sobre Reconocimiento de Patrones . Cancún.
- ^ "Otro punto de referencia de etiquetado de componentes conectados: Prittt / YACCLAB" . 2019-02-18.
- ^ Bailey, DG; Johnston, CT; Ma, Ni (septiembre de 2008). Análisis de componentes conectados de imágenes transmitidas . 2008 Conferencia Internacional sobre Lógica y Aplicaciones Programables en Campo . págs. 679–682. doi : 10.1109 / FPL.2008.4630038 . ISBN 978-1-4244-1960-9.
- ^ MJ Klaiber; DG Bailey; Y. Baroud; S. Simon (2015). "Una arquitectura de hardware de uso eficiente de los recursos para el análisis de componentes conectados". Transacciones IEEE sobre circuitos y sistemas para tecnología de video . 26 (7): 1334-1349. doi : 10.1109 / TCSVT.2015.2450371 .
General
- Horn, Berthold KP (1986). Visión del robot . Prensa del MIT . págs. 69–71 . ISBN 978-0-262-08159-7.
enlaces externos
- Implementación en C #
- sobre la extracción de objetos de la imagen y el algoritmo de etiquetado de componentes conectados directamente