Exercício 02
Rotulação de componentes conexas em imagens binárias
Introdução
O objetivo deste exercício é criar um programa que recebe uma imagem binária
no formato PBM ASCII como entrada e faz a rotulação das componentes conexas da
imagem gerando como saída uma imagem em níveis de cinza no formato PGM ASCII,
sendo que cada componente conexa é representada com um nível de cinza
diferente. Para a realização desta tarefa é preciso definir um critério de
vizinhança entre os pixels da imagem. O programa aceita como parâmetro em linha
de comando o critério a ser utilizado (4-vizinhança ou 8-vizinhança).
O formato PBM é basicamente o seguinte:
P1 <= tipo da imagem
512 512 <= no. de colunas e linhas da imagem
0 0 1 0 0 ... <= linha 1 (512 colunas)
0 1 1 1 1 ... <= linha 2 (")
...
0 1 1 1 1 ... <= linha 512 (")
O formato PGM é muito semelhante, como mostrado a seguir:
P2
512 512 255 <= no. de colunas e linhas da imagem / máximo valor dos níveis de cinza
0 0 1 0 0 ... <= linha 1 (512 colunas)
0 1 1 1 1 ... <= linha 2 (")
...
0 1 1 1 1 ... <= linha 512 (")
Método Utilizado
Após a leitura da imagem de entrada e o armazenamento desta numa matriz, todos
os valores 1 da matriz são trocados por valores -1, para permitir a utilização
da mesma matriz para armazenar a imagem com os rótulos, estes iniciando com o
valor 1.
Para realizar a rotulação, foi utilizado o seguinte algoritmo: as linhas da
matriz que representa a imagem binária são percorridas da esquerda para a
direita, até que se encontre um pixel de valor -1. Quando isso ocorre,
atribuímos um rótulo r (inicialmente 1) a esse pixel e adicionamos em uma pilha
as posições dos pixels vizinhos (de acordo com o critério de vizinhança
escolhido). Enquanto houver posições na pilha, desempilhamos a posição do topo,
atribuímos ao pixel desta posição o rótulo r e adicionamos à pilha as posições
dos vizinhos deste pixel. Desta forma, quando a pilha estiver vazia teremos
rotulado todos os pixels desta componente conexa com rótulo r. Continuamos
varrendo a matriz linha a linha da esquerda para a direita até encontrarmos
outro pixel de valor -1, quando então atribuímos a este o rótulo r + 1 (onde r
é o valor do último rótulo atribuído a uma componente conexa) e repetimos o
processo descrito acima para rotular os pixels vizinhos utilizando uma pilha.
Ao terminar o processo, todas as componentes conexas da imagem estarão
rotuladas. A imagem então é salva num arquivo no formato PGM ASCII.
O programa foi escrito na linguagem C. O código pode ser baixado
aqui.
Resultados
A tabela abaixo mostra os resultados obtidos com três imagens de teste
diferentes. A primeira coluna mostra a imagem binária, a segunda coluna
mostra o resultado da rotulação utilizando-se a 4-vizinhança e a terceira
coluna mostra o resultado para a 8-vizinhança. A convenção usada nas imagens
em níveis de cinza é: o menor nível de cinza corresponde ao fundo da imagem.
Já nas imagens binárias, os pixels de valor 0 correspondem ao fundo da imagem,
enquanto os de valor 1 correspondem aos objetos presentes na imagem.
| Imagem binária |
4-vizinhança |
8-vizinhança |
 |
 |
 |
 |
 |
 |
 |
 |
 |
Observando os resultados é possível notar a diferença entre a conexidade com a
4-vizinhança e a 8-vizinhança: no primeiro exemplo, o quadrado e um dos
retângulos pertencem à mesma componente conexa utilizando-se 8-vizinhança
enquanto formam componentes conexas distintas usando-se 4-vizinhança.
No último exemplo, todos os quadrados da imagem formam uma única componente
conexa usando-se 8-vizinhança e 40 componentes conexas diferentes usando-se
4-vizinhança. Já no segundo exemplo não há diferenças.
As imagens de teste e os resultados obtidos podem ser baixados através dos
links abaixo.
Imagens de teste:
Resultados para 4-vizinhança:
Resultados para 8-vizinhança:
Conclusão
O programa mostrou-se eficiente para fazer a rotulação das componentes conexas
em imagens binárias. A utilização de uma pilha ao invés de funções recursivas
para fazer a rotulação evita o problema de estouro da pilha de recursão
quando componentes conexas muito grandes estão presentes na imagem de entrada.
Através das imagens mostradas acima, é possível visualizar a diferença entre
as componentes conexas obtidas utilizando-se diferentes critérios de vizinhança.
Daniel André Vaquero
daniel at linux.ime.usp.br
Sun, 31 Aug 2003 20:51:49 -0300