Algoritmo de Rotulação de Componentes Conexas

Disciplina: MAC5749
Trabalho: EP2
Data de entrega: 11/09/2003
Aluno: Robson Ribeiro Correia

Introdução

O Problema da Rotulação de Componentes Conexas, dada uma figura binária, consiste em encontrar e rotular todas as Componentes Conexas da figura, tal que para todo pixel pertencente à componente existe um Caminho Conexo para cada um dos pixels também pertencentes à componente.

O conceito de Caminho Conexo entre os pixels varia da mesma forma que varia o conceito de Vizinhança. São geralmente aceitos três conceitos de Vizinhança, dado um pixel P, para os quais utilizamos princípios de geometria discreta:

Vizinhança-4: os pixels exatamente à direita (chamado de V0), acima (V1), à esquerda (V2) e abaixo (V3) do pixel P. I. e., dada as coordenadas (r,s) para P,
V0 = (r, s+1), V1 = (r-1, s), V2 = (r, s-1), e V3 = (r+1, s)

Abaixo uma reprentação espacial da Vizinhança-4:

V1

V2 P V0

V3
Vizinhança-8: além dos pixels contidos em Vizinhança-4, incluem-se os pixels nas diagonais em relação a P, ou seja,
V0 = (r, s+1), V1 = (r-1,s+1), V2 = (r-1, s), V3 = (r-1, s-1), V4 = (r, s-1), V5 = (r+1, s-1), V6 = (r+1, s) e V7 = (r+1, s+1)

Abaixo uma reprentação espacial da Vizinhança-8:

V3 V2 V1

V4 P V0

V5 V6 V7
Vizinhança-m: similar à Vizinhança-8, porém não permite ambiguidade de Caminhos Conexos entre os pixels da Componente Conexa;

O Algoritmo de Rotulação de Componentes Conexas aceita como entrada uma matriz bidimensional binária e apresenta como saída uma matriz bidimensional cujos valores de seus elementos podem variar de 0 a 255. Cada componente conexa será identificada por um rótulo, um valor de 1 a 255, que será o mesmo para todos os pixels pertencentes a ela. A matriz de entrada encontra-se no formato PBM (Portable Bitmap) e a matriz de saída encontra-se no formato PGM (Níveis de Cinza).

Este trabalho está assim estruturado:

Título
Introdução
Métodos
Resultados
Conclusão
Bibliografia

Métodos

O método utilizado para a implementação deste algoritmo foi baseado na sugestão de Gonzalez & Woods. Para cada pixel P pertencente à figura, tomamos um modelo que representa toda a sua vizinhança (vizinhança-4, -8 ou -m). A cada iteração, procuramos então a vizinhança dos pixels vizinhos a P, e fazemos isso sucessivamente até que todos os pixels da componente conexa tenham sido explorados. Esta busca é implementada de forma recursiva, e leva em consideração apenas os pixels que ainda não foram rotulados, ou seja, exclui os que tenham valor `0` (BRANCO) ou que tenham o valor de outro rótulo. Esse método é muito semelhante ao Algoritmo de Preenchimento de Região.

Abaixo há uma sugestão de pseudocódigo para esse algoritmo.

EncontraComponentesConexas(matriz, linhas, colunas)

1  rotulo <- MAXGRAY /* valor máximo permitido para níveis de cinza */
2  para i = 0 até i <= linhas
3     para j = 0 até j <= colunas
4        se matriz[i][j] == PRETO  /* pixel não rotulado */
5           matriz[i][j] <- rotulo  /* rotula o pixel */
6           RotulaVizinhanca8(matriz, i, j, rotulo)
7           se rotulo > 2
8              rotulo <- rotulo -1;
9           senão /* a figura tem mais que 255 componentes conexas */
10             sai do loop

RotulaVizinhanca4(matriz, linha, coluna, rotulo)

1  se (matriz[linha][coluna+1] == PRETO) AND (coluna+1 <= COL) /* VO */
2     matriz[linha][coluna+1] <- rotulo
3     RotulaVizinhanca4(matriz, linha, coluna+1, rotulo)

4  se (matriz[linha-1][coluna] == PRETO) AND (linha-1 >= 0) /* V1 */
5     matriz[linha-1][coluna] <- rotulo
6     RotulaVizinhanca4(matriz, linha-1, coluna, rotulo)

7  se (matriz[linha][coluna-1] == PRETO) AND (coluna-1 >= 0) /* V2 */
8     matriz[linha][coluna-1] <- rotulo
9     RotulaVizinhanca4(matriz, linha, coluna-1, rotulo)

10 se (matriz[linha+1][coluna] == PRETO) AND (linha+1 <=COL) /* V3 */
11    matriz[linha+1][coluna] <- rotulo
12    RotulaVizinhanca4(matriz, linha+1, coluna, rotulo)

Obs.: LIN, número máximo de linhas na matriz;
      COL, número máximo de colunas na matriz;
      RotulaVizinhança8 é similar a RotulaVizinhança4;

Não foi encontrada dificuldade na implementação do algoritmo. Isto significa que o programa implementado encontra as componentes conexas e as rotula corretamente. Porém a implementação contém alguns bugs e limitações, os quais ainda pretendo corrigir. Eles estão explicitados abaixo:

Bugs:
- A imagem PGM gerada está distorcida em relação à imagem original, dando uma impressão de inclinação das figuras;
- A última linha da figura original não pôde ser processada, pois sempre ocorria Segmentation Fault
Limitações:
- O programa não lê ainda o tamanho da imagem do arquivo original. Está processando apenas imagens de tamanho 256x256;
- Os arquivos a serem examinados e gerados também não podem ainda ser indicados na linha de comando;

Você pode encontrar o código dessa implementação aqui.

Resultados

Abaixo temos as figuras no formato PBM e PGM. Os níveis de cinza não podem ser facilmente percebidos na segunda figura, porém uma verificação do arquivo mostra que as componentes foram corretamente rotuladas.

Figuras: squares.pbm, squares.pgm

P1
# Biblioteca de Imagens de Robson Correia (c)2003
256 256
...
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
...

P2
# Biblioteca de Imagens de Robson Correia (c)2003
255 256 256
...
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252   0 
...

Figuras: lines.pbm, lines.pgm

Conclusão

A rotulação de componentes conexas pode ser, e na verdade é aplicada ao reconhecimento de objetos em figuras binárias. Principalmente porque formas podem ser entendidas como conjuntos de pontos conexos. Outra vantagem desse método é que é possível extrair não apenas as formas, mas também a quantidade de objetos encontrados nas figuras.

Bibliografia

Costa & César, Shapes Analysis and Classification: Theory and Practice, CRC Press, 2001.

Gonzales & Woods, Digital Image Processing, 1993.

Hosted by www.Geocities.ws