RECONHECIMENTO DE OBJETOS EM IMAGENS   POR MEIO DO CONTORNO

RECONHECIMENTO DE OBJETOS EM IMAGENS POR MEIO DO CONTORNO

(Parte 1 de 4)

( Real Academia de Artilharia, Fortificação e Desenho, 1792 ) CURSO DE GRADUAÇÃO EM ENGENHARIA CARTOGRÁFICA

Proposta de um método baseado no Código da Cadeia e estudo de caso para reconhecimento de caracteres utilizados na Cartografia

1º TEN LEANDRO LUIZ SILVA DE FRANÇA ALU EDUARDO JOSÉ DA SILVA JUNIOR

Proposta de um método baseado no Código da Cadeia e estudo de caso para reconhecimento de caracteres utilizados na Cartografia

Trabalho de Iniciação à Pesquisa apresentado ao Curso de Graduação em Engenharia Cartográfica do Instituto Militar de Engenharia, para a obtenção de grau na Verificação Final (VF) de 2014.

Orientador: TC Carlos Frederico de Sá Volotão, D. Sc.

1º TEN LEANDRO LUIZ SILVA DE FRANÇA ALU EDUARDO JOSÉ DA SILVA JUNIOR

Proposta de um método baseado no Código da Cadeia e estudo de caso para reconhecimento de caracteres utilizados na Cartografia

Projeto de Iniciação à Pesquisa apresentada ao Curso de Graduação em

Engenharia Cartográfica do Instituto Militar de Engenharia, como requisito parcial para a obtenção de grau na Verificação Final (VF).

Orientador: TC Carlos Frederico de Sá Volotão, D. Sc. Aprovado em 2014 pela seguinte Banca Examinadora:

Os métodos de reconhecimento de padrões buscam sempre concentrar esforços nos modos de classificação de formas dos objetos presentes na imagem. A representação de uma forma pode ser obtida através de seus contornos usando-se uma técnica chamada de Código da Cadeia. Esta técnica permite representar o contorno da borda de um objeto por meio de uma assinatura da forma que consiste em uma sequência de direções do pixel anterior para o próximo pixel, utilizando-se como código os algarismos de 0 a 7. Uma maneira de se classificar a forma de um objeto é a comparação de sua assinatura com as assinaturas-padrão de diferentes formas obtidas previamente para servir de modelos. Esta comparação pode ser realizada através de diversas técnicas como, por exemplo, o cálculo da norma da diferença entre as assinaturas. Este trabalho visa mostrar que a utilização do Código da Cadeia para representação do contorno de caracteres ou símbolos presentes em um mapa possibilita o reconhecimento automático dos mesmos. Para demonstrar a exiquibilidade desta abordagem procurou-se aplicar este método a caracteres existentes em uma carta topográfica no formato matricial (raster).

Palavras Chave: análise de forma, Código da Cadeia, assinatura da forma, classificação de formas.

The pattern’s recognition methods always seek to focus the efforts on the objects shape’s classification in the images. Shape representation can be obtained using a technique called Chain Code that uses the objects boundary. This technique allows representing the object’s edge using a shape signature which is a direction sequence from the previous pixels to the next one, number from 0 to 7 are used as codes. One way to classify the shape of an object is to compare your signature with the signatures of different standard forms previously obtained to serve as models. This comparison can be done using various techniques, for instance, calculating the difference norm between the signatures. This work aims to show that using Chain Code to represent the boundary of character or symbol in map allows automatic recognition. To demonstrate the feasibility of this approach we attempted to apply this method to existing characters in a topographic map in raster format.

Key words: Shape analysis, Chain Code, shape signature, shape classification

Figura 1.1 Caracteres em um mapa12
Figura 2.1 Regiões de borda14
Figura 2.2 Vizinhança 815
Figura 2.3 Relação das direções com o círculo trigonométrico15
Figura 2.4 Perseguição de borda e representação do Código da Cadeia16
Figura 2.5 Cálculo da assinatura pela distância euclidiana17
Figura 2.6 Cálculo da assinatura utilizando o Código da Cadeia18
Figura 2.7 Reamostragem em imagens20
Figura 2.8 Interpolação pelo Vizinho Mais Próximo20
Figura 2.9 Interpolação Bilinear21
Figura 2.10 Limiarização2
Figura 2.1 Objetos com diferentes níveis de cinza23
Figura 2.12 Histograma da figura 2.123
Figura 3.1 Valores do incremento k para cada situação da direção preferencial26
representação pelas direções congruentes28

Figura 3.2 Execução detalhada do algoritmo de perseguição de borda e

borda29
Figura 3.4 Pixels da borda externa do objeto e suas respectivas assinaturas30
Figura 4.1 Imagem A e perseguição de borda usando o Código da Cadeia3
Figura 4.2 Imagem B e perseguição de borda usando o Código da Cadeia3
Figura 4.3 Imagem C e perseguição de borda usando o Código da Cadeia34

Figura 3.3 Pixels de fundo da imagem verificados no processo de perseguição de

congruentes35

Figura 4.5 Imagem B e perseguição de borda utilizando a técnica das direções

congruentes36
Figura 4.7 Gráfico das Assinaturas de A, B e C utilizando o Código da Cadeia37

Figura 4.6 Imagem C e perseguição de borda utilizando a técnica das direções

congruentes37
Figura 4.9 Menor distância angular entre duas direções37
Figura 4.10 Imagens do mesmo objeto rotacionado em 90º38

Figura 4.8 Gráfico das Assinaturas de A, B e C utilizando as direções

comparação41
Figura 5.2 Modelos para comparação e suas variações de rotação42
Figura 5.3 Modelos para comparação e suas variações de escala43
Figura 5.4 Normalização de uma assinatura maior para uma menor45
Figura 5.5 Normalização de uma assinatura menor para uma maior45

Figura 5.1 Critério para escolha da fonte Arial para geração dos modelos de Figura 6.1 a 6.23 Taxa de acertos utilizando os métodos ....................................... 5

Cadeia34

Tabela 4.1 Cálculo da norma 1 entre A, B e C representadas pelo Código da

congruentes36

Tabela 4.2 Cálculo da norma 1 entre A, B e C representadas pelas direções

Cadeia de Freeman (Algoritmo 1 e 2)47

Tabela 6.1 Tempo médio de perseguição de borda e representação pelo Código da

congruentes (Algoritmo 5)48
Tabela 6.3 Razão entre os tempos da Tabela 6.1 e Tabela 6.2 por caractere49

Tabela 6.2 Tempo médio de perseguição de borda e representação pelas direções

pelas direções congruentes50

Tabela 6.4 Comparação pela norma 1 entre as assinaturas-padrão representadas

assinaturas-padrão representadas pelo Código da Cadeia51

Tabela 6.5 Comparação pela soma das mínimas distâncias angulares entre as Tabela 6.6 Verificação da eficácia dos métodos de reconhecimento....................... 52

LISTA DE ILUSTRAÇÕES5
LISTA DE TABELAS7
1INTRODUÇÃO ..................................................................................................... 9
1.1 Contextualização9
1.2 Objetivo10
1.3 Justificativa1
1.4 Organização12
2FUNDAMENTAÇÃO TEÓRICA ......................................................................... 13
2.1. Borda13
2.2. Código da Cadeia14
2.3. Assinatura16
2.4. Norma 117
2.5. Reamostragem em imagens18
2.5.1 Interpolação pelo Vizinho Mais Próximo19
2.5.2 Interpolação Bilinear20
2.6. Limiarização21
3REPRESENTAÇÃO DE FORMAS PELAS DIREÇÕES CONGRUENTES ....... 24
3.1. Considerações sobre o método das direções congruentes28
4ANTECEDENTES DO PROBLEMA................................................................... 31
4.1. A Norma 1 para comparação entre assinaturas31
4.2. Soma das mínimas distâncias angulares36
4.3. Operações de rotação do Código da Cadeia37
5METODOLOGIA E PROCEDIMENTOS ............................................................. 39
6RESULTADOS E ANÁLISE DOS DADOS ........................................................ 46
6.1. Primeira etapa de resultados46
6.2. Segunda etapa de resultados49
6.3. Terceira etapa de resultados50
6.4. Análise dos resultados52
7CONCLUSÃO .................................................................................................... 6
REFERÊNCIAS BIBLIOGRÁFICAS67

SUMÁRIO APÊNDICES ........................................................................................................... 679

1INTRODUÇÃO

1.1 Contextualização

A maioria das atividades humanas e a interação com meio ambiente é realizada por meio visual, mais precisamente por meio da captura de ondas eletromagnéticas e subsequente processamento pelo sistema da visão até a interpretação dos sinais pelo cérebro. Dada a homogeneidade de cor e textura na maioria dos elementos da natureza, passa-se a dar mais atenção às suas variações entre os objetos, isto é, às fronteiras, delimitando regiões uniformes. De fato, a variedade de geometrias de bordas dos objetos leva ao conceito de forma (COSTA & CESAR, 2009).

A evolução das tecnologias na captura, processamento, análise e classificação de formas tem permitido à humanidade a ampliação e automação dos processos visuais e sua interpretação. Assim, a importância do tema está apoiada nas oportunidades sem precedentes de aplicação destes novos recursos nas diversas áreas do conhecimento.

Dentre as diversas áreas de aplicação, as técnicas de processamento de imagens, assim como de análise de formas, podem ser empregadas em áreas relevantes para Engenharia Cartográfica como, por exemplo, na análise de fotografias aéreas ou imagens de satélite, assim como na área da cartografia através da extração de feições cartográficas (estradas, rios, edificações, etc.), sem contar com o seu emprego na área militar, podendo-se destacar a identificação e rastreamento de alvos para lançamento de mísseis (PEDRINI & SCHWARTZ, 2008).

Existem diferentes abordagens para análise de formas e reconhecimento de objetos em uma imagem digital, sendo elas pela cor, textura, contorno ou contexto em que o objeto está inserido (VOLOTÃO et al, 2008). A presente pesquisa busca tratar do tema sob a perspectiva da aplicação a contornos usando o Código da Cadeia (FREEMAN, 1974) para representação das bordas de um objeto contido em uma imagem digital através sua representação, sendo ela uma sequência de direções do pixel anterior para o próximo pixel que vão de 0 a 7 (oito possibilidades) que representam a assinatura da forma.

A classificação da forma de um objeto pode ser realizada por meio da comparação entre a sua representação com a de uma forma conhecida (padrão). Supõe-se que esta comparação pode ser executada através do cálculo da norma da diferença entre as assinaturas. Entretanto, as perturbações e irregularidades presentes na imagem causadas por variações de iluminação e ruído (GONZALEZ & WOODS, 1993) podem ocasionar alterações indesejadas no cálculo da norma.

1.2 Objetivo

O objetivo geral deste trabalho é reconhecer objetos em imagens por meio do contorno baseando-se no Código da Cadeia para o caso de caracteres utilizados na Cartografia. Os objetivos específicos são:

Identificar um método de perseguição de borda e representação pelo Código da Cadeia na literatura. o Implementar e testar o algoritmo de detecção de borda apresentado na literatura.

Avaliar e propor modificação ou outro método. o Implementar e testar o algoritmo de detecção de borda proposto neste trabalho.

Gerar imagens dos caracteres que servirão de modelo para comparação.

Aplicar o algoritmo proposto a cada um dos modelos, gerando suas assinaturas-padrão para futura comparação.

Obter a representação do contorno de caracteres que se apresentam em uma carta utilizando o algoritmo proposto e realizar seu reconhecimento através da comparação e classificação em relação ao conjunto de assinaturas-padrão.

Avaliar os resultados obtidos e esboçá-los através de um relatório para as diferentes amostras.

1.3 Justificativa

As novas perspectivas de aplicação de um método baseado no código da cadeia de Freeman, assim como outros métodos de detecção de borda permanecem um ativo campo de pesquisa (SOLOMON & BRECKON, 2013).

Para a Cartografia, o reconhecimento e identificação de símbolos e caracteres podem ser úteis no processo de vetorização de um mapa digital pelo fato de permitir fazer distinção entre a representação das feições, símbolos e caracteres empregados.

Existem diversas possibilidades de aplicação para o reconhecimento de caracteres em mapa, como por exemplo, a possibilidade de associar o nome reconhecido a uma feição e, desta forma, permitir a aquisição automática do seu atributo. Uma situação interessante para um caso como este seria o reconhecimento de todos os pontos de cotas em uma carta topográfica e suas respectivas altitudes.

Todavia, o processo de reconhecimento de caracteres em um mapa tem suas peculiaridades, se comparado com a utilização de softwares Optical Character Recognition (OCR) em uma imagem contendo somente texto, principalmente pelo fato de todos os caracteres não estarem sistematicamente alinhados na imagem e apresentarem variações de rotação e escala (Figura 1.1).

Figura 1.1 Caracteres em um mapa (ROBINSON et al,1995)

Pelos motivos mencionados anteriormente, a metodologia deste trabalho busca direcionar esforços ao desenvolvimento de uma técnica de reconhecimento da forma de caracteres presentes em um mapa considerando algumas das suas peculiaridades como rotação, escala e sobreposição a fundo com diferentes níveis de cinza e texturas, sabendo-se que são fatos pertinentes quando se trabalha com mapas.

1.4 Organização

No segundo capítulo, será apresentado o referencial teórico da pesquisa, destacando-se a abordagem sobre o Código da Cadeia de Freeman, a norma 1, técnicas de reamostragem em imagens e o processo de segmentação por limiarização, que são conceitos básicos para o desenvolvimento desta pesquisa.

O terceiro capítulo apresenta a proposta e desenvolvimento de uma técnica alternativa de perseguição de borda e representação de formas, mostrando também suas vantagens e desvantagens quando comparada à encontrada na literatura.

No quarto capítulo, é estudada uma situação em que a norma 1 não se adéqua a comparação de formas utilizando o contorno do objeto representado pelo Código da Cadeia. Na parte final do capítulo é apresentada mais uma forma de comparação de assinaturas considerando algumas das variações de rotação do objeto da imagem.

No quinto capítulo são apresentados detalhadamente a metodologia e os procedimentos adotados para se verificar a eficácia e eficiência dos métodos apresentados anteriormente.

O sexto capítulo é dedicado aos resultados e sua análise que permitirão chegar a conclusões sobre a aplicabilidade dos métodos estudados.

No sétimo e último capítulo, expõe-se uma avaliação que busca destacar os aspectos mais relevantes da pesquisa e sintetizar os resultados que comparam as técnicas levantadas para identificação de formas, apresentando, também, outras possibilidades de aplicação dos métodos pesquisados, pontos fortes e fracos de cada caso e sugestões de oportunidades de melhoria.

2FUNDAMENTAÇÃO TEÓRICA

Neste capítulo, será apresentada a base teórica necessária para o desenvolvimento desta pesquisa, abordando conceitos fundamentais que auxiliarão o entendimento do Código da Cadeia de Freeman, além das técnicas de geração de uma assinatura da forma e um método de comparação entre elas.

Borda corresponde à região limite ou a fronteira entre duas regiões com propriedades relativas distintas de nível de cinza (PEDRINI & SCHWARTZ, 2008).

X ΔΔ X
X ΔΔ X
X ΔΔ X

Na Figura 2.1, o objeto é caracterizado pela imagem cinza ao centro, já o fundo ou background corresponde aos pixels brancos. Os pixels com X são geralmente chamados de pixels da borda externa, assim como os pixels que estão preenchidos com Δ podem ser denominados como pixels da borda interna.

Figura 2.1 Regiões de borda

2.2. Código da Cadeia

O Código da Cadeia, também conhecido como Freeman Chain Codes

(ROBINSON et al, 1995), é uma representação simples e popular, onde, ao invés do contorno ser representado por uma série de coordenadas (x,y) , ele é representado pelo seu ponto inicial e uma sequência de códigos numéricos que representam as direções de um passo para o próximo ao longo do contorno.

Para entender esquematicamente o Código da Cadeia pode-se observar a

Figura 2.2, onde cada pixel tem oito vizinhos, que são numerados de 0 a 7, como é indicado na figura.

Observa-se, também, que esses vizinhos são numerados no sentido antihorário, começando do vizinho da direita.

É interessante salientar que é possível associar a máscara de vizinhança 8 ao círculo trigonométrico, apenas multiplicando seus valores por 4 . Como pode ser verificado na Figura 2.3. Esse raciocínio pode ser usado no processo de perseguição da borda para determinar os pixels da vizinhança conhecendo-se a sua direção.

Figura 2.2 Vizinhança 8 (FREEMAN,1974)

Figura 2.3 Relação das direções com o círculo trigonométrico

Agora, referindo-se a Figura 2.4, observa-se um processo de perseguição de borda para obtenção do Código da Cadeia. O pixel marcado pela letra P é o pixel inicial do contorno, o próximo pixel vizinho no sentido anti-horário é o pixel de baixo. Este processo é repetido até que todo o contorno seja percorrido, ou seja, até que o pixel final seja igual ao inicial.

A representação do Código da Cadeia é dada pela sequência 000012223444456667.

Costa e Cesar (2009) apresentam os algoritmos 1 e 2 para obtenção do

Código da Cadeia de uma forma. O algoritmo 1 realiza uma varredura até achar o primeiro pixel do objeto, quando obtido, realiza-se repetidamente a rotina do algoritmo 2 para determinar os pixels seguintes da borda. A condição de parada é quando o próximo pixel corresponde ao pixel inicial.

Algoritmo 1: Algoritmo de perseguição da borda externa de um objeto

Algoritmo (COSTA & CESAR, 2009) O que está sendo feito?

1. Ache E [1]

2. n 2 3. Seja prox_pixel o segundo pixel do contorno;

4. Seja dcn a direção de E [1] para o próximo pixel;

5. enquanto (prox_pixel E [1]) faça

6E [n]  prox_pixel
7dpc  dcn
8ACHE_PROX( E [n] , dpc ,prox_pixel, dcn)
9n  n+1

- Varredura para determinar as coordenadas do pixel inicial da borda E[1]. - Faz n receber 2 e usa-se o mesmo raciocínio da função do Algoritmo 2 para determinar o 2º pixel (prox_pixel). - Determina a direção do pixel atual (1º pixel) para o próximo (2º pixel). - Enquanto o próximo pixel não é diferente do 1º pixel da cadeia realizar a rotina: - Faz E[n] receber o pixel n

- Faz a direção do pixel anterior para o atual

R receber a direção do atual para o próximo

- Chama a função do Algoritmo 2 que retornará os valores do próximo pixel e a direção do pixel atual para o próximo.

Figura 2.4 Perseguição de borda e representação do Código da Cadeia

Algoritmo 2: Algoritmo da função para achar o próximo pixel Algoritmo (COSTA & CESAR, 2009) O que está sendo feito?

(Parte 1 de 4)

Comentários