Escola Superior de Tecnologia e Gestão de Beja
Engenharia Informática – Ano Lectivo 2010/2011
Estruturas de Dados e Algoritmos
Apresentação do Trabalho de Avaliação
Connected Component Labeling
Realizado por: Eduardo Cardeira nº 6033
Connected Component Labeling – O que é isso ?
- O Connected Component Labeling (Marcação de Componentes
Conexos) é uma aplicação algorítmica da teoria dos grafos (mais
especificamente, a teoria dos Strongly Connected Components).
- Este algoritmo, maioritariamente aplicado na área da Visão por
Computador (Computer Vision), permite processar imagens binárias e
colorir cada uma das áreas conexas que as compõem com cores
diferentes, permitindo identificar facilmente cada uma delas.
- O processo referido permite distinguir, de forma simples, vários
objectos presentes numa imagem, o que torna o algoritmo muito útil
em diferentes áreas da sociedade, como a medicina, o exército, a
robótica ou a astronomia.
- Existem várias formas diferentes do algoritmo, as quais incluem os
métodos TwoPass, OnePass e vários MultiPass.
Connected Component Labeling – Como Funciona?
Passos de Execução ( Segundo o método TwoPass ):
FirstPass ( 1ª Passagem ):
1- Percorrer a imagem binária por colunas e linhas, analisando cada
pixel;
Connected Component Labeling – Como Funciona?
FirstPass ( 1ª Passagem ):
2 – Se o pixel não pertencer à imagem (valor > 0):
1 – Identificar os pixéis vizinhos do actual;
2 – Se não existirem vizinhos, atribuir um novo valor ao
pixel;
3 – Caso contrário, descobrir qual o valor mínimo entre
os vizinhos e atribuir esse valor ao pixel;
4 – Guardar as equivalências entre marcas diferentes
pertencentes a uma mesma área.
Connected Component Labeling – Como Funciona?
FirstPass ( 1ª Passagem ):
2 – (Exemplos Visuais):
Connected Component Labeling – Como Funciona?
SecondPass ( 2ª Passagem ):
1 – Percorrer novamente a imagem binária, analisando cada um
dos pixéis;
2 – Se o pixel não pertencer ao fundo da imagem:
1 – Substituir o valor da marcação do pixel pelo valor
mais pequeno correspondente;
Connected Component Labeling – Código da Aplicação
A estrutura do código desenvolvido é a seguinte:
- Classes do Projecto:
ImageOperations – Métodos para manipulação dum ficheiro de
imagem;
Main – Executa os métodos principais da função;
TwoPass
–
Contém
os
métodos
funcionamento do algoritmo Two Pass.
responsáveis
pelo
Connected Component Labeling – Código da Aplicação
- Métodos das Classes:
- ImageOperations:
- openImage – Abre um ficheiro de imagem.
- saveImage – Guarda um ficheiro de imagem.
- getWidth – Obtém o comprimento da imagem.
- getHeight – Obtém a altura da imagem.
- imageBinarization – Converte a imagem recebida numa
imagem Binária.
Connected Component Labeling – Código da Aplicação
- Métodos das Classes:
- Main:
- main – Chama as operações essenciais da aplicação.
CPU.
- getCPUTime – Obtém o tempo de execução gasto pelo
Connected Component Labeling – Código da Aplicação
- Métodos das Classes:
- TwoPass:
- getNeighborLabels – Devolve um array com as marcas
vizinhas.
- numberOfDifferentLabels – Calcula o número de marcas
vizinhas diferentes.
- getLowestNeighborLabel – Devolve a marca vizinha mais
pequena.
- labelPixel – Marca um pixel com um determinado valor.
Connected Component Labeling – Código da Aplicação
- Métodos das Classes:
- TwoPass:
- getLabel – Devolve a marca de um pixel.
- colorize – Aplica cor a cada uma das áreas de acordo com
o valor da sua marca correspondente.
- generateColors – Gera cores aleatórias para as várias
marcas.
- findSet – Devolve o conjunto da lista de equivalências
que contém o elemento especificado.
Connected Component Labeling – Código da Aplicação
- Métodos das Classes:
- TwoPass:
- setEquivalences – Gera equivalências entre as várias
marcas de uma área conexa.
- setLabelValue – Define o valor de uma marca.
- run – Corre o método do TwoPass.
Connected Component Labeling – Resultados Obtidos
Ao processar três versões de uma mesma imagem com
tamanhos diferentes, e contar o tempo de execução do
algoritmo para cada uma delas, obteve-se a seguinte tabela de
resultados:
Tempos de Execução
Ficheiros de Imagem
tesouras1.jpg
tesouras2.jpg
tesouras3.jpg
484 x 415 pixéis
242 x 207 pixéis
121 x 103 pixéis
1.
374402400 ns
124800800 ns
93600600 ns
2.
452402900 ns
171601100 ns
62400400 ns
3.
436802800 ns
78000500 ns
93600600 ns
4.
436802800 ns
187201200 ns
93600600 ns
5.
390002500 ns
171601100 ns
62400400 ns
6.
390002500 ns
171601100 ns
93600600 ns
7.
468003000 ns
156001000 ns
62400400 ns
8.
436802800 ns
109200700 ns
78000500 ns
9.
390002500 ns
156001000 ns
78000500 ns
10.
405602600 ns
140400900 ns
109200700 ns
Média
418082680 ns
146640940 ns
82680530 ns
Connected Component Labeling – Resultados Obtidos
Os dados da tabela permitiram elaborar o seguinte gráfico que
relaciona a dimensão das imagens em pixéis, com o tempo de
execução do algoritmo:
Connected Component Labeling – Resultados Obtidos
Depois de analisar os vários dados podemos concluir que:
- O tempo de execução do algoritmo é proporcional ao
tamanho da imagem processada;
- Quanto menor for o tamanho da imagem a processar, mais
eficiente se torna o algoritmo;
- Provavelmente, existem métodos mais eficientes do que o
Two Pass para sistematizar o Connected Component Labeling.
Connected Component Labeling – Conclusão
Para terminar, podemos dizer que:
- Os processos de Connected Component Labeling são uma
forma simples e eficaz de produzir distinção entre áreas conexas
de uma imagem;
- São úteis na criação e implementação de vários processos
essenciais em várias áreas da sociedade e uma das bases
principais da Visão por Computador.