El etiquetado de componentes conectados (CCL, por sus siglas en inglés), también conocido como análisis de componentes conectados, extracción de manchas, etiquetado de regiones o descubrimiento de manchas, es una aplicación algorítmica de la teoría de grafos en la que subconjuntos de componentes conectados se etiquetan de manera única según una heurística dada. 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 de dimensiones superiores. El CCL es distinto de la segmentación de imágenes, y la extracción de manchas está relacionada pero es diferente de la detección de manchas.
En la práctica, el CCL opera sobre un grafo construido a partir de los datos de entrada, donde los vértices representan píxeles o elementos y las aristas indican conectividad entre vecinos. Un algoritmo recorre el grafo, asignando etiquetas a los vértices según la conectividad y los valores relativos. Después del etiquetado, el grafo se puede particionar en subconjuntos, lo que permite recuperar la información original y procesarla para tareas como contar, filtrar y rastrear manchas.
Definición y Terminología
El término etiquetado de componentes conectados se usa de manera consistente en la literatura académica, mientras que el análisis de componentes conectados (CCA, por sus siglas en inglés) varía tanto en terminología como en definición del problema. Rosenfeld et al. definen el CCL como la creació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. describen el CCL como un operador cuya entrada es una imagen binaria y cuya salida es una imagen simbólica donde la etiqueta de cada píxel es un entero que identifica de manera única su componente conectado.
No hay consenso sobre la definición del CCA; a menudo se usa indistintamente con el CCL. Una definición más extensa de Shapiro et al. establece que el CCA consiste en el etiquetado de componentes conectados de píxeles negros, seguido de la medición de propiedades de las regiones de componentes y la toma de decisiones. Este artículo adopta una interpretación más amplia que incorpora estas perspectivas.
Construcción del Grafo y Conectividad
Se construye un grafo a partir de los datos de entrada relevantes, con vértices que contienen la información necesaria para la heurística de comparación y aristas que indican vecinos conectados. El algoritmo recorre el grafo, etiquetando vértices según la conectividad y los valores relativos. La conectividad está determinada por el medio; para grafos de imagen, las vecindades comunes incluyen la de 4-conectividad (norte, sur, este, oeste) y la de 8-conectividad (incluyendo diagonales).
Después del etiquetado, el grafo se puede particionar en subconjuntos, tras lo cual se puede recuperar y procesar la información original. Este enfoque se generaliza a dimensiones arbitrarias, aunque la complejidad temporal y espacial aumenta en consecuencia.
Algoritmo de un Componente a la Vez
El algoritmo de un componente a la vez es rápido, simple de implementar y se basa en métodos de recorrido de grafos. Forma parte del algoritmo de segmentación por cuencas hidrográficas de Vincent y Soille, y existen otras implementaciones. El método usa una lista enlazada para mantener los índices de píxeles conectados, y la elección entre búsqueda en profundidad o en anchura no tiene diferencia práctica para esta aplicación.
El algoritmo asume una imagen binaria con píxeles de primer plano y fondo, y tiene como objetivo etiquetar componentes conectados en el primer plano. Pasos:
- Comenzar desde el primer píxel, establecer la etiqueta actual en 1.
- Si el píxel es de primer plano y no está etiquetado, asignar la etiqueta actual y añadirlo a una cola; de lo contrario, pasar al siguiente píxel.
- Extraer un elemento de la cola, examinar sus vecinos (según el tipo de conectividad). Si un vecino es de primer plano y no está etiquetado, asignar la etiqueta actual y añadirlo a la cola. Repetir hasta que la cola esté vacía.
- Pasar al siguiente píxel e incrementar la etiqueta actual.
Los píxeles se etiquetan antes de ser puestos en la cola, y los vecinos de cada píxel de primer plano se verifican solo una vez; los vecinos de píxeles de fondo no se verifican. El pseudocódigo usa dos colas para gestionar el procesamiento de píxeles, asegurando un recorrido eficiente.
Aplicaciones en Visión por Computadora
El CCL se usa ampliamente en visión por computadora para detectar regiones conectadas en imágenes binarias, a menudo después de un paso de umbralización. La extracción de manchas también se puede aplicar a imágenes en escala de grises y en color. Las manchas pueden contarse, filtrarse y rastrearse, lo que hace que el CCL sea valioso en sistemas de reconocimiento de imágenes e interfaces de interacción humano-computadora.
Por ejemplo, en pipelines de Machine learning, el CCL puede preprocesar imágenes para tareas de detección de objetos o segmentación, complementando técnicas como arquitecturas U-Net. También se usa en sistemas de Artificial intelligence para analizar imágenes médicas, inspección industrial y conducción autónoma, donde identificar regiones conectadas es crucial.
Conceptos Relacionados y Extensiones
El CCL está relacionado pero es distinto de la detección de manchas, que se centra en identificar regiones de interés basadas en variaciones de intensidad. En contraste, el CCL etiqueta todos los componentes conectados según la conectividad. El algoritmo se puede extender a datos de dimensiones superiores, como volúmenes 3D en imágenes médicas, con un mayor costo computacional.
Los avances recientes en Deep learning y modelos de Neural network han llevado a enfoques aprendidos para la segmentación, pero el CCL sigue siendo una herramienta fundamental para el postprocesamiento y el análisis. Su simplicidad y eficiencia lo convierten en un elemento básico en bibliotecas y marcos de visión por computadora, a menudo usado junto con Data Augmentation y Loss Functions en pipelines de entrenamiento.
Véase También
- visión por computadora
- segmentación de imágenes
- detección de manchas
- teoría de grafos