Etiquetado de componentes conectados - Connected-component labeling

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. 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. La extracción de blobs se realiza generalmente en la imagen binaria resultante de un paso de umbral, 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 manchas está relacionada con la detección de manchas, pero es distinta .

Visión general

4-conectividad

8-conectividad

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 .

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. definir 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. 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".

No existe consenso sobre la definición de CCA en la literatura académica. A menudo se usa indistintamente con CCL. Shapiro et al dan una definición más extensa: "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 los pensamientos expresados en.

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 , también existen otras implementaciones.

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 desde 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 (también conocido como el 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 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 comprueban 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?
1. Sí , estamos en la misma región. Asignar la misma etiqueta al píxel actual
2. 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?
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 mínimo de las etiquetas Norte y Oeste, y registre su relación de equivalencia
2. 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?
1. Sí : asigne la etiqueta del píxel norte al píxel actual
2. 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?
1. 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. 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.

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
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. 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
1. 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.

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

El pseudocódigo es:

algorithm TwoPass(data) is
    linked = []
    labels = structure with dimensions of data, initialized with the value of Background
    NextLabel = 0

    First pass
  
    for row in data do
        for column in row do
            if data[row][column] is not Background then
  
                neighbors = connected elements with the current element's value
  
                if neighbors is empty then
                    linked[NextLabel] = set containing NextLabel
                    labels[row][column] = NextLabel
                    NextLabel += 1
  
                else
  
                    Find the smallest label
  
                    L = neighbors labels
                    labels[row][column] = min(L)
                    for label in L do
                        linked[label] = union(linked[label], L)
  
    Second pass
  
    for row in data do
        for column in row do
            if data[row][column] is not Background then
                labels[row][column] = find(labels[row][column])
  
    return labels

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.

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.

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)
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 configurados actualmente.
3. Los píxeles únicos se retienen y los píxeles repetidos se eliminan.
4. 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.

One-Component-at-a-Time(image)
    [M, N] := size(image)
    connected := zeros(M, N)
    mark := value
    difference := increment
    offsets := [-1; M; 1; -M]
    index := []
    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)]
                connected(index) := mark
                while ~isempty(index) do
                    image(index) := 0
                    neighbors := bsxfun(@plus, index, offsets)
                    neighbors := unique(neighbors(:))
                    index := neighbors(find(image(neighbors)))
                    connected(index) := mark
                end while
                mark := mark + difference
            end if
       end for
   end for

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 (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. 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

Referencias

General

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

Languages

In other projects