A rotulação de componentes conexos (CCL, do inglês connected-component labeling), também conhecida como análise de componentes conexos, extração de blobs, rotulação de regiões ou descoberta de blobs, é uma aplicação algorítmica da teoria dos grafos na qual subconjuntos de componentes conexos são rotulados de forma única com base em uma heurística fornecida. É utilizada em visão computacional para detectar regiões conexas em imagens digitais binárias, embora imagens coloridas e dados de dimensões superiores também possam ser processados. A CCL é distinta da segmentação de imagens, e a extração de blobs está relacionada, porém é diferente da detecção de blobs.
Na prática, a CCL opera sobre um grafo construído a partir dos dados de entrada, em que os vértices representam pixels ou elementos e as arestas indicam conectividade entre vizinhos. Um algoritmo percorre o grafo, atribuindo rótulos aos vértices com base na conectividade e nos valores relativos. Após a rotulação, o grafo pode ser particionado em subconjuntos, permitindo que a informação original seja recuperada e processada para tarefas como contagem, filtragem e rastreamento de blobs.
Definição e Terminologia
O termo rotulação de componentes conexos é usado de forma consistente na literatura acadêmica, enquanto a análise de componentes conexos (CCA, do inglês connected-component analysis) varia tanto na terminologia quanto na definição do problema. Rosenfeld et al. definem CCL como a criação de uma imagem rotulada na qual posições associadas ao mesmo componente conexo da imagem binária de entrada possuem um rótulo único. Shapiro et al. descrevem CCL como um operador cuja entrada é uma imagem binária e cuja saída é uma imagem simbólica em que o rótulo de cada pixel é um inteiro que identifica exclusivamente seu componente conexo.
Não há consenso sobre a definição de CCA; ela é frequentemente usada de forma intercambiável com CCL. Uma definição mais abrangente de Shapiro et al. afirma que a CCA consiste na rotulação de componentes conexos de pixels pretos, seguida pela medição de propriedades das regiões dos componentes e pela tomada de decisões. Este artigo adota uma interpretação mais ampla que incorpora essas perspectivas.
Construção do Grafo e Conectividade
Um grafo é construído a partir dos dados de entrada relevantes, com vértices contendo as informações necessárias para a heurística de comparação e arestas indicando vizinhos conectados. O algoritmo percorre o grafo, rotulando vértices com base na conectividade e nos valores relativos. A conectividade é determinada pelo meio; para grafos de imagem, vizinhanças comuns incluem a 4-conexa (norte, sul, leste, oeste) e a 8-conexa (incluindo diagonais).
Após a rotulação, o grafo pode ser particionado em subconjuntos, após o que a informação original pode ser recuperada e processada. Essa abordagem generaliza-se para dimensões arbitrárias, embora a complexidade de tempo e espaço aumente de acordo.
Algoritmo de Um Componente por Vez
O algoritmo de um componente por vez é rápido, simples de implementar e baseado em métodos de travessia de grafos. Ele faz parte do algoritmo de segmentação por watershed de Vincent e Soille, existindo outras implementações. O método usa uma lista encadeada para manter os índices dos pixels conexos, e a escolha entre busca em profundidade ou busca em largura não tem diferença prática para essa aplicação.
O algoritmo assume uma imagem binária com pixels de primeiro plano e de fundo, com o objetivo de rotular componentes conexos no primeiro plano. Etapas:
- Comece pelo primeiro pixel e defina o rótulo atual como 1.
- Se o pixel for de primeiro plano e não rotulado, atribua o rótulo atual e adicione-o a uma fila; caso contrário, passe para o próximo pixel.
- Remova um elemento da fila, examine seus vizinhos (com base no tipo de conectividade). Se um vizinho for de primeiro plano e não rotulado, atribua o rótulo atual e adicione-o à fila. Repita até que a fila esteja vazia.
- Passe para o próximo pixel e incremente o rótulo atual.
Os pixels são rotulados antes de serem enfileirados, e os vizinhos de cada pixel de primeiro plano são verificados apenas uma vez; os vizinhos de pixels de fundo não são verificados. O pseudocódigo usa duas filas para gerenciar o processamento de pixels, garantindo uma travessia eficiente.
Aplicações em Visão Computacional
A CCL é amplamente utilizada em visão computacional para detectar regiões conexas em imagens binárias, frequentemente após uma etapa de limiarização. A extração de blobs pode ser aplicada também a imagens em tons de cinza e coloridas. Os blobs podem ser contados, filtrados e rastreados, tornando a CCL valiosa em sistemas de reconhecimento de imagens e em interfaces de interação humano-computador.
Por exemplo, em pipelines de aprendizado de máquina, a CCL pode pré-processar imagens para tarefas de detecção de objetos ou segmentação, complementando técnicas como arquiteturas U-Net. Também é utilizada em sistemas de inteligência artificial para análise de imagens médicas, inspeção industrial e direção autônoma, onde a identificação de regiões conexas é crucial.
Conceitos Relacionados e Extensões
A CCL está relacionada, mas é distinta da detecção de blobs, que se concentra em identificar regiões de interesse com base em variações de intensidade. Em contraste, a CCL rotula todos os componentes conexos com base na conectividade. O algoritmo pode ser estendido a dados de dimensões superiores, como volumes 3D em imagens médicas, com custo computacional aumentado.
Avanços recentes em modelos de aprendizado profundo e redes neurais levaram a abordagens aprendidas para segmentação, mas a CCL permanece uma ferramenta fundamental para pós-processamento e análise. Sua simplicidade e eficiência a tornam um elemento básico em bibliotecas e estruturas de visão computacional, frequentemente usada em conjunto com aumento de dados e funções de perda em pipelines de treinamento.
Ver Também
- visão computacional
- segmentação de imagens
- detecção de blobs
- teoria dos grafos