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. - ppt carregar
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.
PublicouHugo Portal Alterado mais de 3 anos atrás
Apresentação em tema: "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."— Transcrição da apresentação:
1 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
2 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.
3 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;
4 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.
5 Connected Component Labeling – Como Funciona? FirstPass ( 1ª Passagem ): 2 – (Exemplos Visuais):
6 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;
7 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 responsáveis pelo funcionamento do algoritmo Two Pass.
8 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.
9 Connected Component Labeling – Código da Aplicação - Métodos das Classes: - Main: - main – Chama as operações essenciais da aplicação. - getCPUTime – Obtém o tempo de execução gasto pelo CPU.
10 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.
11 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.
12 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.
13 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:
14 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:
15 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.
16 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.
Carregar ppt "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."
© 2000, António Esteves - Seminários de Ciências da Computação, UM-DI 1 Seminários de Ciências da Computação Partição de Sistemas Digitais em Componentes.