48
FERNANDO PORTO CORRÊA LEIDMAR MAGNUS FESTA AVALIAÇÃO DE TÉCNICAS PARA AFINAMENTO DE IMAGENS DIGITAIS Trabalho apresentado ao curso de Bacharelado em Ciência da Computação da Universidade Federal do Paraná, como requisito parcial à obtenção do título de Bacharel em Ciência da Computação. . Orientador : Prof. Dr. Hélio Pedrini CURITIBA 2005 1

Afinamento de Imagens Digitais - Thinning of Digital Images

Embed Size (px)

DESCRIPTION

Monografia sobre a avaliação de métodos de afinamento de imagens digitais

Citation preview

Page 1: Afinamento de Imagens Digitais - Thinning of Digital Images

FERNANDO PORTO CORRÊALEIDMAR MAGNUS FESTA

AVALIAÇÃO DE TÉCNICAS PARAAFINAMENTO DE IMAGENS DIGITAIS

Trabalho apresentado ao curso de Bacharelado em Ciência da Computação da Universidade Federal do Paraná, como requisito parcial à obtenção do título de Bacharel em Ciência da Computação..Orientador : Prof. Dr. Hélio Pedrini

CURITIBA2005

1

Page 2: Afinamento de Imagens Digitais - Thinning of Digital Images

AGRADECIMENTOS

Em primeiro lugar a Cristo que esteve conosco em todos os momentos (naqueles de

cansaço, naqueles de muita energia, na desilusão – quando o algoritmo não funcionava - e na

alegria); pela sua graça (através da qual foi possível terminar em tempo hábil este estudo).

Ao nosso orientador Prof. Dr. Hélio Pedrini que, após algumas conversas, nos incentivou a

dar continuidade ao processo de estudo e sanou várias das dúvidas que surgiram nas

implementações e conceitos dos algoritmos.

Aos nossos familiares e amigos, que demonstraram paciência em vários momentos.

2

Page 3: Afinamento de Imagens Digitais - Thinning of Digital Images

SUMÁRIO

1. INTRODUÇÃO...................................................................................................................8

1 PROBLEMA........................................................................................................................9

1.2 OBJETIVOS.....................................................................................................................9

1.3 ORGANIZAÇÃO DO TRABALHO.................................................................................10

2. CONCEITOS PRELIMINARES .......................................................................................11

2.1 COMPONENTES CONEXOS..................................................................................................11

2.2 VIZINHANÇA DE PIXELS........................................................................................................122.2.1 Vizinhança-4......................................................................................................................122.2.2 Vizinhança-8......................................................................................................................122.2.4 Outras vizinhanças............................................................................................................12

2.3 CÁLCULO DA DISTÂNCIA ENTRE PIXELS............................................................................132.3.1 Métrica Euclidiana.............................................................................................................132.3.2 Métrica Cityblock...............................................................................................................142.3.2 Métrica Chessboard..........................................................................................................15

2.4 TIPOS DE ALGORITMOS DE AFINAMENTO.........................................................................162.4.1 Algoritmos Seqüenciais.....................................................................................................172.3.2 Algoritmos Paralelos..........................................................................................................18

3. PRINCIPAIS MÉTODOS DE ESQUELETIZAÇÃO (OU AFINAMENTO)....................................203.1) Método de Stentiford...........................................................................................................203.2) Método de Zhang-Suen.......................................................................................................213.3) Método de Holt....................................................................................................................223.4) Método de Morfologia Matemática......................................................................................233.5) Método da Poda (Pruning)..................................................................................................243.6) Método MB..........................................................................................................................24

4. RESULTADOS EXPERIMENTAIS..................................................................................26

4.1 CONJUNTO DE IMAGENS......................................................................................................26

4.2 PLATAFORMA HARDWARE E SOFTWARE..........................................................................27

4.3 GRÁFICOS E IMAGENS GERADAS COM O SOFTWARE.....................................................284.3.1 Aplicação do Método Zhang-Suen....................................................................................284.3.2 Combinação dos Métodos Zhang-Suen e Máscaras de Holt (staircase removal).............304.3.3 Aplicação do Método de Stentiford....................................................................................314.3.4 Combinação dos Métodos de Stentiford e Máscaras de Holt (staircase removal).............334.3.5 Aplicação do Método da Morfologia Matemática...............................................................354.3.6 Aplicação do Método MB...................................................................................................374.3.7 Combinação dos Métodos MB e Máscaras de Holt (staircase removal)............................404.3.8 Combinação dos Métodos MB e Stentiford.......................................................................414.3.9 Combinação dos Métodos Morfologia Matemática e Poda ...............................................42

3

Page 4: Afinamento de Imagens Digitais - Thinning of Digital Images

5. CONCLUSÕES................................................................................................................44

APENDICE A.......................................................................................................................47

A.1 IMAGEM BINÁRIA..................................................................................................................47A.1.1 Formato PBM...................................................................................................................47A.1.2 Especificação dos formatos PBM.....................................................................................47

4

Page 5: Afinamento de Imagens Digitais - Thinning of Digital Images

ÍNDICE DE ILUSTRAÇÕESFigura 1.1 - Exemplo de afinamento da letra A …......................................................................... 8Figura 2.1 - Conectividade entre pixels 11Figura 2.2 - Pixels vizinhos 12Figura 2.3 - Exemplos de vizinhanças 13Figura 2.4 - Voxel 13Figura 2.5 - Efeito da Transformada Euclidiana 14Figura 2.6 - Distância Cityblock 15Figura 2.7 - Distância Chessboard 16Figura 2.8 - Afinamentos baseados em MAT 18Figura 2.9 - Nomenclatura usual dos pixels 19Figura 2.10 - Preservação da topologia 19Figura 2.11 - Genealogia do afinamento 19Figura 3.1 - Exemplo simples de afinamento da letra T 20Figura 3.3 - Problemas Gerais de Afinamento 21Figura 3.7 - Máscaras do Método MB 25Figura 4.1 - Amostra para afinamento 1 26Figura 4.2 - Amostra para afinamento 2 27Figura 4.3 - Amostra para Afinamento 3 27Figura 4.4 - Zhang-Suen afina amostra 2 28Figura 4.5 - Zhang-Suen Morfologia dos Objetos 29Figura 4.6 - Zhang-Suen ocorrência de Tailing 29Figura 4.7 - Zhang-Suen Falha ao Afinar Algumas Linhas 29Figura 4.8 - Zhang-Suen com Staircase 30Figura 4.9- Zhang-Suen e Holt Verificação 1 31Figura 4.10 - Comparação da Combinação Holt/Zhang-Suen com Zhang-Suen 31Figura 4.11 - Stentiford Verificação 1 32Figura 4.12 - Stentiford e a Ocorrência de Staircase 32Figura 4.13 - Comparação: Stentiford, Holt e Zhang-Suen 33Figura 4.14 - Staircase Removal: Comparação Geral 33Figura 4.15 - Problemas Gerais de Morfologia e Tailing 33Figura 4.16 - Stentiford e Máscaras de Holt: Verificação 1 34Figura 4.17 - Stentiford combinado com Holt: Ocorrência de Necking 34Figura 4.18 - Stentiford combinado com Holt: uma nova ocorrência de Necking 35Figura 4.19 - Aplicação da Morfologia Matemática: ocorrência de Tailing e ramificações 35Figura 4.20 - Aplicação da Morfologia Matemática: ocorrência ramificações 36Figura 4.21 - Ocorrência de ramificações após a aplicação da Morfologia Matemática 36Figura 4.22 - Comparação entre Stentiford e Morfologia Matemática 36Figura 4.23 - Casos extremos de ramificações 37Figura 4.24 - Método MB Verificação 1 37Figura 4.25 - Método MB Verificação 2 38Figura 4.26 - Problemas com ângulos de 90° com o método MB 38Figura 4.27 - Incoerência no afinamento com MB 39Figura 4.28 - Ilustração das linhas afinadas em 90° com MB 39Figura 4.29 - Melhor performance utilizando o método MB 39Figura 4.30 - Ruídos em algumas linhas afinadas 40Figura 4.31 - Efeito colateral ao combinar MB e Máscaras de Holt 40Figura 4.32 - Verificação do efeito colateral 41Figura 4.33 - Combinação dos métodos MB e Stentiford: Verificação 1 41Figura 4.34 - MB e Stentiford sem problemas de largura de dois pixels 42Figura 4.35 - Combinação dos métodos de Morfologia Matemática e Poda 42Figura 4.36 - Morfologia Matemática e Poda: maior precisão 43Figura 4.37 - Morfologia Matemática e Poda eliminação de boa parte das ramificações 43Figura 5.1 - Exemplo de uma Pré-Classificação para um complemento deste estudo 44Figura A.1 - Exemplo do formato PBM em ASCII 48

5

Page 6: Afinamento de Imagens Digitais - Thinning of Digital Images

LISTA DE TABELAS

Tabela 2.1 - Ditância entre Pixels ................................................................................ …..........17

6

Page 7: Afinamento de Imagens Digitais - Thinning of Digital Images

1. INTRODUÇÃO

Desde os primórdios do surgimento da tecnologia dos computadores, foi possível fazer com que estas máquinas fossem empregadas no reconhecimento de padrões nas mais variadas áreas. Paralelamente a esse fato, havia também a necessidade de reduzir o volume de informações a serem processadas para o reconhecimento de padrões. Os primeiros experimentos em compressão de dados foram realizados nos anos 50, e utilizavam padrões de caracteres alfanuméricos.

O afinamento (ou esqueletização) é uma importante etapa de pré-processamento para vários tipos de algoritmos que realizam alguma análise de imagens. De um modo geral, este processo envolve a remoção dos pixels dos objetos que formam uma imagem, até que cada um destes objetos seja representado por uma linha simples, com largura de um único pixel. O conjunto de linhas que é formado ao final do processamento é chamado de esqueleto da imagem.

Durante os anos 50, a criação de muitos algoritmos para compressão de dados utilizando afinamento fez com que surgisse uma grande variedade de padrões para diferentes propósitos. No início dos anos 60, rapidamente encontrou-se uma aplicação para a técnica do afinamento no campo da biomedicina: tendo como objetivo contar e medir as células brancas do sangue, o algoritmo “Shrink” foi utilizado para identificar células anormais (Preston 1961). Muitas outras aplicações nesta área passaram a existir, desde a análise de cromossomos, análise de imagens de raio-X (Preston e Duff 1979), e de artérias coronárias (Nguyen e Sklansky 1986). Em outras áreas podemos encontrar o afinamento sendo utilizado no processamento de sistemas de reconhecimento de retina, classificação de impressões digitais (Moayer e Fu 1975), análise visual de peças industrializadas (Mundy e Joynson 1977), confecção de placas de circuito impresso (Ye e Danielsson 1988) e muitas outras aplicações.

Desta maneira já se pode ter uma idéia de como é vasta a utilização do processo de afinamento de imagens, já que a redução que ocorre na quantidade de dados a serem processados ao se afinar uma imagem facilita a análise desta. Ao se aplicar este processo, por exemplo, em caracteres alfanuméricos, os padrões utilizados para a análise se aproximam muito da concepção humana e permitem uma análise estrutural simples com uma representação apropriada para os algoritmos de reconhecimento. Como exemplo podemos citar uma imagem que contém uma letra de nosso alfabeto, representada na figura 1.1 (a):

Figura 1.1 – Exemplo de afinamento da uma imagem de um caractere de nosso alfabeto. O esqueleto de uma imagem é considerado um grafo (ou ainda uma representação das partes essenciais) da imagem original.

Após passar por um processo de afinamento, teremos como resultado o esqueleto desta imagem, figura 1.1 (b), o qual é considerado um grafo entre a descrição abstrata desta letra e a representação física deste caractere. Ao obtermos o esqueleto de uma imagem, poderemos eliminar distorções no contorno e ao mesmo tempo mantendo suas propriedades geométricas e topológicas. Em termos mais práticos, pode-se dizer que os esqueletos fazem com que a imagem fique mais nítida (para que os algoritmos possam analisá-la), em especial quando é necessário extrair algumas características críticas desta imagem (como, por exemplo, pontos de conexões

7

Page 8: Afinamento de Imagens Digitais - Thinning of Digital Images

entre objetos diferentes). Naturalmente, para que um algoritmo de afinamento seja realmente eficiente, ele precisa compactar os dados da imagem retendo as características significativas do padrão e eliminar os ruídos sem introduzir distorções.

Rosenfeld (Rosenfeld e Pfaltz 1966) classifica os algoritmos de afinamento em dois grupos: paralelos e seqüenciais. No primeiro grupo, a decisão de remover ou não um pixel na iteração atual é baseada somente no resultado da iteração (passo) anterior, tornando este tipo de algoritmo apropriado para um hardware com mais de um processador. No segundo grupo, para que um pixel seja processado, leva-se em conta o resultado do passo anterior e também do passo atual. Sem dúvida alguma, a resolução que a imagem possui incrementa tempo e complexidade significativos aos algoritmos, já que todos os pixels dela são examinados a cada iteração.

Para que possamos utilizar todas as características anteriormente citadas e produzir algoritmos simples e rápidos, há vários desafios. Vários artigos foram publicados discutindo os mais variados aspectos deste assunto, mas mesmo assim pode-se notar que ainda estamos carentes de uma visão mais elucidativa. Existem alguns artigos nesta área que têm este fim: (Tamura 1978, Milditch 1983, Davies 1981). A intenção aqui não se resume somente a desenvolver um método que contenha as principais características desejáveis, mas também coletar dados (provenientes de testes empíricos e comparações teóricas) sobre os principais algoritmos de afinamento. Tudo isso será discutido tendo em vista um conjunto consistente de informações.

1 PROBLEMA

A existência de vários métodos de afinamento faz com que a escolha de um destes (como parte do processamento de uma imagem digital) se torne uma tarefa confusa. Isso se deve ao fato de que diferentes métodos afetam diferentes características da imagem, podendo, por exemplo, causar perda da forma ou da conectividade dos objetos. Assim sendo, a escolha do método dependerá, em especial, da aplicação-fim através da qual poderemos saber qual das características dos objetos afinados é a mais desejada.

1.2 OBJETIVOS

Como já citado anteriormente, vários estudos e novos métodos são publicados a cada ano sobre este assunto, mas ainda é preciso uma visão mais elucidativa sobre os resultados obtidos com cada um dos algoritmos mais conhecidos nesta área.

A idéia inicial aqui, é utilizar o mesmo conjunto de imagens e realizar testes concisos e coerentes, com diversos métodos de afinamento, buscando assim, destacar as características mais marcantes que cada esqueleto resultante apresentar. Desta maneira, será possível expor isto de forma comparativa.

8

Page 9: Afinamento de Imagens Digitais - Thinning of Digital Images

1.3 ORGANIZAÇÃO DO TRABALHO

CAPÍTULO 2: CONCEITOS PRELIMINARES

Nesta seção, estão sendo expostos todos os conceitos utilizados nesta monografia e grande parte dos conceitos que estão envolvidos no afinamento de imagens. A explanação é motivadora, histórica e explicativa. Iniciamos tudo verificando o conceito de imagem binária, onde uma visão simples e prática é apresentada (mostrando o formato PBM, as razões de sua criação, seus respectivos campos, vantagens e desvantagens).

Após isso, são apresentados os conceitos de pixel em uma imagem binária (obviamente sem entrar em detalhes profundos como representação do sinal digital, armazenamento dentre outros). Assim sendo, seguem os conceitos de corpo e borda de uma imagem, após os quais é possível introduzir também as definições de vizinhança e componentes conexos em imagens. Existe ainda o conceito da distância entre pixels, onde estão descritas algumas das distâncias mais utilizadas, visando à praticidade voltada para o afinamento.

CAPÍTULO 3: MÉTODOS DE ESQUELETIZAÇÃO OU AFINAMENTO

Os tipos de algoritmos que realizam afinamento recebem uma atenção especial nesta seção. Estes são classificados em dois tipos básicos: seqüenciais e paralelos. Existem vários métodos seqüenciais e vários paralelos (os primeiros que se caracterizam por produzirem esqueletos de melhor qualidade mas se tornam lentos durante a execução, ao contrário dos algoritmos paralelos, os quais são executados mais rapidamente, mas produzem esqueletos com uma baixa qualidade).

Os métodos de afinamento mais populares são citados e descritos em detalhes, sendo mostrados passo a passo, com comentários sobre como e porque realizam algumas de suas operações. Estes métodos são: Zhang-Suen, Holt, Stentiford e Morfologia Matemática, os quais são todos pertencentes ao grupo dos algoritmos seqüenciais. A definição formal de esqueletização é então apresentada, incluindo seus principais aspectos e utilizações.

CAPÍTULO 4: RESULTADOS EXPERIMENTAISA metodologia proposta é aplicada no processamento de várias imagens, de modo a

demonstrar a sua validade. Assim sendo, todas as conclusões obtidas sobre o método em questão neste capítulo (principais características, vantagens, desvantagens, melhores aplicações dentre outras) provêm de testes empíricos, os quais foram realizados exaustivamente com diferentes imagens. Todo o conjunto de imagens de teste e resultados obtidos, bem como as especificações de hardware e software utilizados para gerar estes resultados pré e pós-processamento podem ser visualizados nesta seção.

CAPÍTULO 5: CONCLUSÕESAqui temos as conclusões obtidas após os testes com os algoritmos e as figuras

escolhidas, bem como sugestões para melhorar o trabalho.

9

Page 10: Afinamento de Imagens Digitais - Thinning of Digital Images

2. CONCEITOS PRELIMINARES Durante o decorrer deste trabalho, vários conceitos precisaram ser estudados e adaptados

às necessidades do projeto. Abaixo estão listados estes conceitos para facilitar o entendimento global do estudo.

2.1 COMPONENTES CONEXOS

Em uma imagem que possui vários objetos em sua representação, é possível realizar, por exemplo, a contagem destes objetos, verificar a sua localização ou ainda quais pixels compõem estes objetos. Estas tarefas acima citadas, possuem aplicações muito úteis no processamento de uma imagem podendo ser usadas, por exemplo, na contagem de células sangüíneas ou na localização de áreas específicas em um mapa. Em todos estes casos, o conceito de componentes conexos pode ser usado.

Este conceito pode ser ilustrado de uma maneira muito simples. Seja uma imagem binária I, a qual é constituída por pixels com valor 1 (cor preta), os quais formam os objetos existentes na imagem e pixels com valor zero (cor branca) que fazem parte do fundo da imagem. Chamaremos agora o conjunto de pixels com valor 1 de P e o conjunto de pixels com valor zero de B. Assim sendo, um componente conexo na imagem I será um subconjunto de pixels do conjunto P, onde qualquer par de pixels estará conectado.

Dois pixels estarão conectados se, entre eles, existir um caminho de pixels vizinhos (haverá algumas diferenças para vizinhanças 4 e 8). Expressando isso de uma maneira mais clara, podemos dizer que dois pixels X e Y estarão conectados se, entre eles, existir um caminho de pixels (p1, p2, ... pi, ..., pn) onde teremos X = p1, Y = pn e 1 ≤ i ≤ n. Assim pi-1 e pi são vizinhos e compartilham de uma mesma propriedade. É interessante ressaltar que dependendo do tipo de vizinhança considerada para o caminho, haverá uma classificação diferente para este: caminho-8 (caso consideremos vizinhança-8) e caminho-4 (para vizinhança-4). É importante lembrar que um único pixel isolado é um componente conexo.

Na figura 2.1 (a) podemos ver um exemplo de componente conexo, o qual se enquadra em ambas as vizinhanças-4 e 8 (já que os pixels que formam o caminho entre X e Y se encaixam perfeitamente em ambos os conceitos). Já na figura 2.1 (b) verifica-se que o caminho entre X e Y é formado somente por pixels de vizinhança-8. Finalmente, em 2.1 (c) temos vários pixels isolados uns dos outros (X, Y, Z e W), mas cada um destes faz parte de um objeto e, assim sendo, cada pixel é um componente conexo.

Figura 2.1: (a) Conectividade entre pixels neste caso se enquadra para ambas as vizinhanças. (b) os pixels X e Y somente estarão conectados no caso de considerarmos uma vizinhança 8. (c) neste último caso, temos vários pixels isolados uns dos outros mas, mesmo assim, cada um deles é um componente conexo.

Em imagens que não são binárias, a identificação dos componentes conexos pode ser realizada através de características, tais como intensidade de cinza, cor e textura.

10

Page 11: Afinamento de Imagens Digitais - Thinning of Digital Images

2.2 VIZINHANÇA DE PIXELSPara facilitar a compreensão deste conceito e dos relacionados a ele, vamos considerar a

figura 2.2 abaixo e ter em mente que o pixel p1 que será analisado para qualquer fim, é um pixel preto (de valor 1) e que os pixels de sua vizinhança serão nomeados conforme consta na figura 2.2 :

Figura 2.2: Pixels adjacentes a p1

De uma forma resumida, os pixels p2, p3, ... , p9 formam a vizinhança-8 do pixel p1 e são coletivamente denotados por N(p). Dizemos que eles são os 8-adjacentes a p1. Os pixels p2, p4, p6

e p8 formam a vizinhança-4 de p1 e são os 4-adjacentes a p1. O número de pixels pretos em N(p) é denotado por b(p).

Assim, podemos conceituar as vizinhanças como segue abaixo:

2.2.1 Vizinhança-4A vizinhança 4 de um pixel pi engloba os seus dois vizinhos horizontais e os dois vizinhos

verticais. No caso de um pixel p1 possuir as coordenadas (x , y) , então seus dois vizinhos horizontais serão os pixels de coordenadas (x + 1, y) e (x – 1, y). Verticalmente teremos os pixels que possuem as seguintes coordenadas: (x, y + 1) e (x, y - 1). Esta será a vizinhança 4 do pixel p1, a qual pode ser observada na figura 2.3 (a).

2.2.2 Vizinhança-8Neste caso, além dos dois vizinhos horizontais e dois verticais, estarão envolvidos também

os quatro vizinhos diagonais do pixel. Assim sendo, no caso de um pixel p1 possuir as coordenadas (x, y) então sua vizinhança 8 engloba todos os pixels indicados na vizinhança 4 mais os pixels com as seguintes coordenadas: (x-1, y-1), (x-1, y+1), (x+1, y-1) e (x+1, y+1). Isso pode ser observado na figura 2.3 (b).

2.2.4 Outras vizinhançasObservando a figura 2.3, pode-se notar que além das vizinhanças 4 e 8, podemos

identificar também vizinhanças 6, 18 e 26 – respectivamente figura 2.3 (c), (d) e (e). Estes três últimos conceitos são utilizados em imagens tridimensionais, onde o conceito do voxel, o qual pode ser visualizado na figura 2.4, pode ser entendido como sendo um pixel de três dimensões – altura, largura e profundidade.

11

Page 12: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 2.3: (a) Constiuição da vizinhança 4 do pixel p1. (b) constituição da vizinhança 8 do pixel p1. (c) observando esta a figura podemos notar que ao considerarmos a vizinhança 6 para o voxel de coordenadas (x, y ,z), teremos como viz-inhos os voxels de coordenadas: (x - 1, y, z), (x + 1, y, z), (x, y - 1, z), (x, y+1, z), (x, y, z - 1) e (x, y, z + 1). (d) vizin-hança 18 de um voxel (e) vizinhança 26 de um voxel.

Figura 2.4: Ilustração do conceito de voxel de imagens tridimensionais. Pode-se interpretar este conceito como sendo um pixel com três dimensões (representadas pelos eixos x, y e z ), e dependendo do tipo de vizinhança que se deseja, seus vizinhos serão outros voxels que possuem uma mesma face e/ou aresta em comum.

2.3 CÁLCULO DA DISTÂNCIA ENTRE PIXELSAs aplicações do cálculo das transformadas de distância dentro do processamento de

imagens e da computação gráfica são variadas, podemos citar como exemplo alguns métodos de reconstrução de superfícies, a metamorfose de objetos 3D, e o cálculo de esqueletos de objetos.

Algumas dificuldades são encontradas, como por exemplo transferir os dados do mundo matemático contínuo para o mundo discreto, já que algumas características de um método específico podem diferir nestes dois mundos. A métrica de uma distância (D) entre dois pontos (p e q) deve satisfazer as seguintes propriedades: a) D (p,q) >= 0 b) (D (p,q) = 0, somente se p=q)c) D (p,q) = D (q,p)d) D (p,r) <= D (p,q) + D (q,r)

Dentre as várias métricas existentes, podemos destacar três: a Euclidiana, Chessboard e a Cityblock.

2.3.1 Métrica EuclidianaAqui, temos a distância entre dois pontos p e q definida pela seguinte equação:

12

Page 13: Afinamento de Imagens Digitais - Thinning of Digital Images

onde: p = (p1, p2, ..., pn) e q = (q1, q2, ..., qn) são pontos do espaço n-dimensional.

Note que utilizando esta definição, é possível utilizar esta transformada em objetos que se encontram no mundo contínuo e também no mundo discreto (objetos volumétricos). Alguns problemas surgem ao utilizar este tipo de transformada, começando pela complexidade de sua implementação e pelo esforço computacional necessário para executá-la. A figura 2.5 (a) exibe uma imagem na qual foi aplicada a transformada de distância euclediana, e na figura 2.5 (b) temos o resultado desta operação, onde a cor de cada pixel é relativo a sua distância Euclidiana à borda do objeto.

Figura 2.5: (a) Ilustração da transformada Euclidiana, onde a cor de cada pixel será alterada de acordo com a distância calculada pela fórmula vista anteriormente. (b) resultado da transformada sobre a figura em questão. Note que quanto mais próximo dos pixels da borda, mais escuros ficaram os pixels analisados.

2.3.2 Métrica CityblockAqui, temos a distância entre dois pontos p e q definida pela seguinte equação:

onde: p = (p1, p2, ..., pn) e q = (q1, q2, ..., qn) são pontos do espaço n-dimensional.

Quando o campo de aplicação desta métrica é o discreto, ela possui uma interpretação interessante: considerando uma imagem no plano cartesiano de duas dimensões, assume-se que para sair de um ponto p e ir para um ponto q, somente pode-se utilizar as direções dos eixos principais do sistema de coordenadas no qual o objeto está inscrito (ou seja, vizinhança-4).

Assim sendo, se um pixel p possuir 8 vizinhos, a métrica cityblock determina que a distância de p até q (quando q pertence à vizinhança-4 do pixel p) é igual a distância (p,q) = 1. Caso q pertença a alguma das diagonais da vizinhança de p, então teremos que distância p,q = 2. Temos ainda que para calcular a distância entre dois pixels quaisquer, basta encontrar um caminho entre eles e contar o número de pixels percorridos entre a origem e o destino. Na figura 2.6 (a), podemos verificar que os pixels destacados formam a vizinhança-4 de p. Pode-se visualizar ainda as direções nas quais é permitido realizar a contagem de distância entre dois pixels, note que neste caso, distância (p,q) = 5. Na figura 2.6 (b) é exibido também o resultado do cityblock aplicado sobre a figura 2.5 (a).

13

Page 14: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 2.6: (a) Destaque para a vizinhança-4 de p , verificação da contagem da distância entre p e q , a qual é igual a 5 e também verificação das direções que podem ser utilizadas para realizar a contagem da distância. (b) resultado da aplicação da métrica cityblock à imagem 2.5 (a)

No caso de um voxel, podemos notar pelas figuras 2.3 (c), (d) e (e) que este pode ter até mesmo 26 outros voxels adjacentes, mas somente aqueles que são parte de sua vizinhança-6 é que têm distância 1 (nota-se que neste caso a contagem da distância é feita usando esta vizinhança).

2.3.2 Métrica ChessboardAqui, teremos a distância definida como sendo:

onde: p = (p1, p2, ..., pn) e q = (q1, q2, ..., qn) são pontos do espaço n-dimensional.

Assim como na cityblock, a métrica chessboard tem como objetivo substituir a euclidiana e por este motivo está voltada para as aplicações discretas. Aqui, considerando uma imagem no plano cartesiano de duas dimensões, assume-se que para sair de um ponto p e ir para um ponto q, pode-se utilizar todas as direções nos eixos do sistema de coordenadas no qual o objeto está inscrito (ou seja: vizinhança-8).

Então, considerando um pixel p, a métrica chessboard determina que a distância de p até q (quando q pertence à vizinhança-8 do pixel p) é igual a distância (p,q) = 1. Temos ainda que para calcular a distâncias entre dois pixels quaisquer, basta encontrar um caminho entre eles e contar o número de pixels percorridos entre a origem e o destino.

14

Page 15: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 2.7: (a) Em destaque a vizinhança-8 de p, vale notar que todos os pixels que fazem parte dela tem distância 1 de p. A distância aqui considera as diagonais, sendo que distância (p,q) = 3. (b) resultado obtido ao aplicar a métrica chessboard sobre a imagem 2.5 (a)

Logo acima, na figura 2.7 (a), podemos verificar as direções nas pode-se realizar a contagem de distância entre dois pixels, note que neste caso distância (p,q) = 3. Pode-se ainda visualizar em destaque a vizinhança-8 de p. Na figura 2.7 (b) é exibido o resultado do chessboard aplicado sobre a figura 2.5 (a).

2.4 TIPOS DE ALGORITMOS DE AFINAMENTO

De acordo com a maneira como os algoritmos examinam os pixels de uma imagem, eles podem ser classificados como seqüenciais ou paralelos. Em um algoritmo seqüencial, é realizada uma análise dos pixels para verificar se estes podem ser excluídos. Esta análise possui uma seqüência fixa de operações a cada iteração e o pixel analisado somente será excluído na n-ésima iteração caso os resultados de todas as operações que foram realizadas até aquele momento tenham sido satisfatórios, ou seja, depende do resultado da (n-1)-ésima iteração e também dos pixels que já foram processados na n-ésima iteração. Em contra-partida existem também os algoritmos paralelos, nos quais excluir um pixel na n-ésima iteração depende apenas dos pixels da iteração (n-1). Assim sendo, todos os pixels podem ser analisados independentemente e de uma forma paralela a cada iteração. (Lam et al. 1992).

As maiores diferenças que os algoritmos seqüenciais e paralelos apresentam se referem aos testes que garantem a conectividade dos objetos. Esta propriedade é definida em termos de três características: número de cruzamentos (crossing number), número de conexões (connectivity number) e simplicidade de pixel (pixel simplicity).

Ambos os tipos de algoritmos possuem vantagens, desvantagens, assim sendo devemos ter em mente que iremos utilizar o tipo que melhor se adaptar à nossa necessidade. Para isto, o ponto de partida é saber que as principais características dos algoritmos seqüenciais se resumem à produção de um esqueleto melhor no que diz respeito à conectividade e conservação da topologia dos objetos, mas com um esforço/custo de processamento grande. Ao contrário dos algoritmos paralelos que se caracterizam especialmente pela velocidade de processamento, mas muitas vezes com uma qualidade menor do esqueleto produzido.

A terceira categoria de algoritmos que será introduzida é a dos métodos não-iterativos, os quais não são baseados em pixels e geram o esqueleto do objeto em um único passo sem examinar todos os pixels.

Por fim, estes algoritmos precisam atender às três características básicas para realizar o

15

Page 16: Afinamento de Imagens Digitais - Thinning of Digital Images

afinamento de uma imagem:

1) não remover pontos finais;

2) não desconectar componentes conexos (ou seja, se um componente é conexo antes do afinamento, o esqueleto deve continuar sendo conexo após o afinamento);

3) não causar erosão excessiva no local está sendo afinado.

2.4.1 Algoritmos SeqüenciaisNesta seção vamos considerar alguns aspectos gerais dos algoritmos iterativos de

afinamento, ou mais precisamente, os algoritmos que excluem sucessivamente camadas de pixels dos objetos da imagem até que os pixels que restam sejam somente os pertencentes ao esqueleto. A exclusão ou retenção de um pixel preto p irá depender da configuração dos pixels que estão na vizinhança que contém p.

Usando este tipo de algoritmo, os pixels de borda são analisados para serem excluídos em uma ordem pré-determinada, e isto pode ser realizado de duas maneiras: varredura (raster scans) ou por verificação do contorno (contour following).

Quando um pixel p é analisado, ele poderá ser excluído ou não, dependendo de como está sua N(p). Para evitar a remoção errônea dos pixels (ou seja, para que não haja alterações em N(p) ), os algoritmos seqüenciais normalmente marcam os pixels que precisam ser eliminados, os quais serão excluídos no final da iteração. Isso faz com que somente uma camada de pixels seja removida a cada ciclo.

Para evitar repetições nesta discussão, assumiremos que um pixel p que será analisado (para posterior exclusão) satisfaz todas as propriedades abaixo:1) p é preto2) p NÃO é isolado ou um ponto final, ou seja: b(p) ≥ 23) p é um pixel de borda, ou seja: p tem no mínimo um pixel, de sua vizinhanca-4, branco.

Um dos meios utilizados para se realizar o afinamento é através da determinação dos centros com número máximo de blocos (determination of centers of maximal blocks), ou como é chamada: Transformações de Eixo Médio (Medial Axis Transformation - MAT), onde a redução dos objetos de uma imagem para uma linha única (com largura de um pixel) é considerada como afinamento.

Na definição deste conceito, temos que um objeto O formado por pixels pi (onde i = 1, 2, ..., n) tem uma borda B formada pelos pixels pb (onde i = 1, 2, ..., m). Devemos verificar a distância de cada pi até o pb mais próximo. Todos os pi que possuírem mais do que um pb próximo na mesma distância, então estes pi pertencem ao eixo médio, ou seja, ao esqueleto de O.

Existem vários conceitos para se calcular a distância de pi até pn, na figura 2.8 (a), (b) e (c) temos a representação do esqueleto (linhas pontilhadas) de três objetos utilizando-se a distância Euclidiana.

16

Page 17: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 2.8: Resultados esperados para um algoritmo de afinamento, baseados na técnica MAT e utilizando-se a distância euclidiana. A linha pontilhada representa o esqueleto do objeto.

Este tipo de algoritmo tem um custo alto, já que é preciso realizar o cálculo da distância pi até pn. Note que este cálculo é feito para todos os pi em relação a todos os pn, ou seja, são realizados os cálculos das seguintes distâncias:

DISTÂNCIASPi PnP1 p1P1 p2P1 …P1 pmP2 p1P2 …P2 pm… …pn p1pn …pn pm

Tabela 2.1: Distâncias entre pixels pi a pn.

Esta análise ainda é feita em todos os objetos existentes na imagem.

2.3.2 Algoritmos ParalelosNeste tipo de algoritmo, os pixels são examinados para exclusão com base nos resultados

da iteração anterior. Assim, estes algoritmos são apropriados para uma implementação em sistemas de processamento paralelo, onde os pixels que satisfizerem um conjunto de condições podem ser removidos simultaneamente. Infelizmente, os algoritmos que utilizam somente processos paralelos têm dificuldade em preservar a conectividade, como exemplo podemos citar o fato de que um retângulo horizontal que possui dois pixels de largura pode vir a desaparecer durante o processo de afinamento destes algoritmos. Por este motivo, o mais comum é utilizar a vizinhança 3 x 3, mas dividir cada iteração em duas sub-iterações (ou sub-ciclos) nas quais somente um subconjunto dos pixels da borda são considerados para remoção. Ao final de cada sub-iteração, a imagem é atualizada com as novas alterações introduzidas pela sub-iteração. Normalmente, quatro sub-ciclos são utilizados para remover os pixels de borda, ou seja, um sub-ciclo para cada pixel de vizinhança-4 (Stefanelli e Rosenfeld, 1971) e (Davis e Rosenfeld, 1976) (estes pixels são também nomeados conforme mostra a figura 2.9: norte, sul, leste e oeste). Isto também pode ser feito em duas sub-iterações, (Stefanelli e Rosenfeld, 1971), (Zhang e Suen,

17

Page 18: Afinamento de Imagens Digitais - Thinning of Digital Images

1984), onde uma sub-iteração exclui os pixels de contorno norte e leste, e a outra exclui os restantes, por exemplo. Outra abordagem de algoritmos que utilizam dois sub-ciclos foi criada para processar imagens mapeadas em forma de sub-áreas (subfields), semelhantes a um tabuleiro de damas. Recentemente, algoritmos com uma sub-iteração foram implementados, mas estes invariavelmente utilizam uma grande quantidade de informações para preservar a conectividade dos objetos (Lam et al, 1992).

Figura 2.9 – Nomenclatura usual dos pixels em relação à p1 (o pixel central), onde cada pixel da vizinhança-4 é chamado conforme sua posição: p2 é o pixel Leste, p4 o Norte, p6 o Oeste e p8 o Sul.

Os algoritmos paralelos que utilizam duas ou quatro sub-iterações são implementados, em parte, pelas máscaras mostradas na figura 2.10. Stefanelli e Rosenfeld (1971) implementaram dois algoritmos desta maneira e provaram que estes preservam a topologia. Em cada sub-iteração, os pixels marcados (do esqueleto) são armazenados. Para evitar a exclusão dos pixels de contorno, os quais também são pontos finais, todos os pixels de contorno são excluídos primeiramente, logo após isso, os pontos finais são inseridos.

Figura 2.10 – (a) e (b) Condições para preservação da topologia. Os pixels indicados por x ou y podem ter valor 1 ou 0.

A genealogia de alguns métodos de afinamento é apresentada na figura 2.11.

Figura 2.11 – Genealogia dos métodos de afinamento.

18

Page 19: Afinamento de Imagens Digitais - Thinning of Digital Images

3. PRINCIPAIS MÉTODOS DE ESQUELETIZAÇÃO (OU AFINAMENTO)

A operação denominada esqueletização (ou afinamento) de objetos, tem como objetivo remover todos os pixels redundantes de uma imagem produzindo uma simplificação dos objetos, a qual tem largura de um único pixel. Assim, podemos verificar que o maior problema para os algoritmos de afinamento é determinar, com exatidão, quais são os pixels redundantes em uma imagem.

A geração de um esqueleto digital é freqüentemente um dos primeiros passos em sistemas de visão computacional, quando o objetivo é extrair características de um objeto em uma imagem. Um esqueleto de um objeto visa representar a forma do objeto em um número menor de pixels no qual todos eles são necessários. Com essa idéia, o esqueleto deve ter todas as informações contidas na imagem original (tais como posição, orientação e comprimento dos segmentos). Um exemplo ilustrativo é mostrado na figura 3.1.

Figura 3.1 – (a) Representação do objeto original (b) visualização do esqueleto do objeto de (a).

Apesar de parecido (e algumas vezes confundido) com o processo de erosão, o afinamento possui algumas características que o tornam mais eficiente e até mesmo mais preciso do que o primeiro. Resumidamente este método (que consiste em sucessivas “remoções” de pixels dos objetos), é executado da seguinte forma: a) marcar os pixels do objeto a serem removidos;b) remover os pixels marcados;c) repetir os passos A e B até que não hajam mais pixels redundantes, ou seja, até o momento em que os pixels remanescentes sejam aqueles que pertencem ao esqueleto do objeto.

O esqueleto do objeto precisa permanecer intacto e deve respeitar as seguintes propriedades: 1) As regiões afinadas precisam ter um pixel de largura;2) Os pixels que formam o esqueleto precisam permanecer próximos do centro da região de cruzamento de regiões;3) É necessário que os pixels do esqueleto formem o mesmo número de regiões que a imagem original apresentava.

O algoritmo dever respeitar as seguintes propriedades:1) Deve manter a conectividade dos objetos2) Não deve remover pontos extremos3) Não deve causar erosão excessiva

A seguir, estaremos apresentando a descrição dos principais métodos de afinamento (Zhang-Suen, Holt, Stentiford e Morfologia Matemática), suas principais carcterísticas, vantagens e desvantagens.

3.1) Método de StentifordComo acontece na maioria dos algoritmos de afinamento, o algoritmo de Stentiford se

baseia na remoção de pixels por camadas. Várias iterações são feitas para remoção de cada camada. Estas iterações ocorrem até não existirem mais camadas a serem retiradas. O processo de remoção (como e qual é o pixel que será removido) é definido através de algumas regras e máscaras.

19

Page 20: Afinamento de Imagens Digitais - Thinning of Digital Images

X 1 XX 0 XX 0 X M1

X X X0 1 1X X X M2

X 1 XX 1 XX 0 X M3

X X X1 1 0X X X M4

Figura 3.2 – Máscaras do método de Stentiford.

As máscaras acima percorrem a imagem na seguinte ordem:• M1 – esquerda para direita e cima para baixo• M2 – esquerda para direita e baixo para cima• M3 – direita para esquerda e baixo para cima• M4 – direita para esquerda e cima para baixo

O algoritmo segue da maneira abaixo:1. A máscara M1 percorre a imagem até encontrar um pixel coincidente.2. Este pixel é marcado para remoção caso não seja um ponto final, ou seja, um pixel

preto com apenas um vizinho preto, e seu número de conectividade seja 1. Para maiores informações sobre número de conectividade, ver o algoritmo de Zhang-Suen.

3. Máscara M1 continua a percorrer a imagem, eliminando os pixels que satisfizerem as condições acima.

4. A seguir, as máscaras M2, M3 e M4, nesta ordem, percorrem a imagem, cada uma à sua maneira.

5. Remover todos os pixels marcados para remoção, alterando seus valores para 0.6. Se algum ponto foi removido na etapa acima, recomeçar o algoritmo com imagem

resultante. Caso contrário, algoritmo termina.

Este algoritmo possui alguns problemas:a) O sentido em que as máscaras percorrem a imagem não importa, já que os pontos são removidos apenas depois;b) Algumas imagens resultantes apresentam problema de descontinuidade, provavelmente por alguma falha no processo que verifica o número de conectividade dos pixels.c) Necking: uma intersecção de duas linhas, a qual ao ser afinada produz um segmento relativamente longo - figura 3.3 (a). d) Tailing: quando temos duas linhas que se unem, e o ângulo entre estas é relativamente pequeno, surge um segmento reto que não corresponde a nenhuma parte da imagem – figura 3.3 (b).e) Line Fuzz: qualquer pixel que esteja conectado à borda do objeto que está sendo afinado, pode criar um segmento que será considerado como pertencente ao esqueleto – figura 3.3 (c).

Figura 3.3 – Aqui, podemos observar os problemas que normalmente ocorrem com os algoritmos de afinamento de imagens: (a) Necking: onde a intersecção de duas linhas, ao ser afinada, produz um segmento relativamente longo, o qual não pertence à imagem real. (b) Tailing: risco do surgimento de um segmento que não pertence à imagem ao afinar linhas que se cruzam e com ângulo muito pequeno entre elas. (c) Line Fuzz: um pixel qualquer conectado à borda da imagem pode produzir um segmento estranho, que não deveria pertencer ao esqueleto.

3.2) Método de Zhang-Suen

Para realizar o afinamento pelo método de Zhang e Suen (1984), toma-se por base a comparação do pixel que é o “candidato à ser eliminado” sobre os seus oito vizinhos. Existem dois passos a serem seguidos, e dentro de cada um deste passos, há quatro regras que devem

20

Page 21: Afinamento de Imagens Digitais - Thinning of Digital Images

ser aplicadas. Se e somente se as quatro regras forem satisfeitas, o pixel poderá ser eliminado. As quatro regras asseguram que:

a) se o pixel em questão for eliminado não fará com que diferentes regiões ligadas por ele passem a ficar separadas (manutenção da conectividade);b) a eliminação de pixels sempre ocorrerá nas bordas do objeto (evita erosão excessiva).

A idéia básica do método Zhang-Suen é decidir se um determinado pixel será eliminado realizando uma verificação em seus oito vizinhos (vizinhança 8). Antes da descrição do algoritmo, é preciso introduzir duas novas definições:

1) Definição de N(p): N(p) é o número de vizinhos não nulos de p, ou seja N(p) = p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9

2) Definição de S(p): S(p) é o número de transições de branco para preto (0-1) na seqüência ordenada: p2, p3, p4, p5, p6, p7 p8, p9 e p2. Ou seja, nos pixels que circundam p1.

Existem dois passos para decidir se o pixel deve ou não ser removido, e estes estão descritos abaixo:

PASSO 1: aqui, o pixel somente pode ser removido se satisfizer as seguintes condições:a) N(p) é maior ou igual a dois e menor ou igual a seis (esta condição verifica se existem ao menos dois pixels vizinhos pretos ao pixel p1, e não mais do que seis. Esta condição procura remover sucessivamente pixels da borda do objeto, ao invés de suas partes internas);

b) S(p) é igual a 1 (esta condição verifica se o número de conectividade do pixel p1 é igual a 1. Esta condição assegura que um pixel a ser removido pertence a apenas um único objeto);

c) A operação “p2 * p4 * p6” resulta em zero ( esta condição verifica se ao menos um dos pixels vizinhos “ p2, p4 ou p6” é fundo (branco) da imagem);

d) A operação “p4 * p6 * p8” resulta em zero (esta condição verifica se ao menos um dos pixels “p4, p6 ou p8” é fundo da imagem).

PASSO 2: aqui, um pixel p1 é eliminado se todas as condições abaixo forem satisfeitas: a) N(p) é maior ou igual a dois e menor ou igual a seis;

b) S(p) é igual a 1;

c) A operação “p2 * p4 * p8” resulta em zero;

d) A operação “p2 * p6 * p8” resulta em zero.

Se um ponto satisfizer todas as condições (de a até d), ele deve ser marcado para ser removido. No entanto, o ponto não deve ser efetivamente eliminado até que todos os pontos em cada passo tenham sido processados. Uma vez que o PASSO 1 tenha sido aplicado a todos os pontos, aqueles que tiverem sido marcados para remoção receberão o valor 0 (fundo). Em seguida, o PASSO 2 deve ser aplicado aos pontos resultantes exatamente da mesma maneira que o PASSO 1. Esse procedimento deve ser repetido até que não hajam mais pontos a serem apagados, produzindo o esqueleto do objeto.

3.3) Método de Holt

O efeito chamado serrilhamento (“staircase”) , o qual consiste na formação de “degraus”

21

Page 22: Afinamento de Imagens Digitais - Thinning of Digital Images

durante o afinamento de uma imagem. Este efeito é indesejado pois prejudica a morfologia do esqueleto da imagem. Uma das fases do método implementado por Holt (1987) é chamada de “staircase removal” e elimina este problema através da aplicação de quatro máscaras sobre o esqueleto de imagem. Este tratamento é vantajoso pois pode ser aplicado a qualquer esqueleto (resultante de qualquer método) desde que este possua casos de staircase.

Esta fase se trata de um processo relativamente simples, onde o pixel central das máscaras mostradas a seguir será eliminado caso qualquer um dos pixels indicados por “X” tiver valor 0 (zero) assim sendo, não causará problemas no formato ou na conectividade do objeto.

0 1 X1 1 XX X 0

X 1 0X 1 10 X X

0 X XX 1 1X 1 0

X X 01 1 X0 1 X

Figura 3.4 – Máscaras do método de Holt as quais implementam o “staircase removal”. Estas máscaras são aplicadas após um pré-processamento feito na imagem, no qual a imagem é afinada e após isso estas máscaras são aplicadas para retirar os pixels excedentes.

3.4) Método de Morfologia Matemática

Esse método, talvez o mais eficaz entre os tratados até aqui, segue a aplicação do operador morfológico de afinamento, que implica primeiro em passar uma série de “elementos estruturantes” pela imagem, transformando o pixel central em 1, se o padrão do elemento foi encontrado, ou em 0, caso não o seja, também conhecido como Transformada Hit or Miss. Após isto, é aplicado o operador diferença da imagem original para a imagem transformada. O resultado final deste processo é obtido também pelo algoritmo. A fórmula a seguir demonstra o raciocínio utilizado:

Existe ainda um operador para esqueletização, não usado aqui, pois este operador implica apenas na aplicação sucessiva do operador de erosão, até que reste apenas o esqueleto da imagem. Logo abaixo está o algoritmo de morfologia matemática:

1) Antes de tudo, uma série de oito elementos estruturantes percorrerá a imagem no sentido convencional, ou seja, da esquerda para direita, de cima para baixo. Os elementos são apresentados a seguir:

0 0 0X 1 X1 1 1

M1

X 0 01 1 0X 1 X

M2

1 X 01 1 01 X 0

M3

X 1 X1 1 0X 0 0

M4

1 1 1X 1 X0 0 0

M5

X 1 X0 1 10 0 X

M6

0 X 10 1 10 X 1

M7

0 0 X0 1 1X 1 X

M8

Figura 3.5 – Elementos estruturantes da morfologia matemática

2) O primeiro elemento percorrerá a imagem. Caso a situação do elemento coincida com o pixel analisado, este pixel se torna 1. Caso contrário, torna-se 0. O “X” de cada elemento significa que o valor deste pixel não importa;

22

Page 23: Afinamento de Imagens Digitais - Thinning of Digital Images

3) Realiza-se a operação lógica AND entre o pixel original e o pixel transformado;4) Os dois primeiros passos se repetem para os pixels restantes da imagem;5) O segundo elemento será aplicado sobre o resultado da aplicação do primeiro;6) O terceiro elemento será aplicado sobre o resultado da aplicação do segundo e assim sucessivamente até o oitavo elemento;7) Os pixels alterados são modificados na imagem original;8) Se houveram alterações, recomeça o algoritmo. Caso contrário, foi alcançado o esqueleto da imagem.

3.5) Método da Poda (Pruning)

Como citado na seção anterior, os esqueletos resultantes da Morfologia Matemática possuem ramificações indesejadas as quais foram produzidas por pequenas irregularidades na borda do objeto original. Estas ramificações podem ser removidas através do método da Poda, o qual na verdade não passa de outro meio de afinamento. Os elementos estruturantes para esta operação são mostrados abaixo juntamente com outros dois tipos de elementos:

1 1 1 1 0 0 0 0 0 01 1 1 1 1 1 0 1 0 0 1 01 1 1 1 0 0

( a ) ( b ) ( c ) ( d )

Figura 3.6 – Os elementos estruturantes para o método da Poda.

Na figura 3.6 (a) a máscara somente encontra a borda do objeto analisado e exclui qualquer pixel que pertença ao foreground que não possua no mínimo um vizinho pertencente ao background. Note que a detecção da borda, leva em conta a vizinhança-8. Na figura 3.6 (b), temos o mesmo caso da anterior, mas com vizinhança-4. Finalmente, na figura 3.6 (c) e (d) temos os elementos utilizados para realizar a Poda. Em cada iteração, cada um destes elementos deve ser utilizado em todas as rotações que sejam múltiplos de 90°.

Normalmente a Poda é responsável por apenas algumas iterações extra para conseguir eliminar as ramificações

3.6) Método MB

Este método foi desenvolvido por Manzera et al (1999) e consiste em aplicar três máscaras sobre todos os pixels de valor igual a 1 (pretos) da imagem. Após isso, basta eliminar aqueles que satisfizerem as condições especificadas. Durante os testes foi possível notar que nos esqueletos resultantes houve a preservação da conectividade dos objetos, os quais apresentaram robustez e baixo nível de ruído.

Abaixo apresentamos as máscaras do algoritmo, bem como a maneira de aplica-las à imagem:

23

Page 24: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 3.7 – Padrão das máscaras do algoritmo MB - elas devem ser aplicadas sobre o pixel nesta forma (normal) e após isso devem ser rotacionadas em todos os ângulos múltiplos de 90º.

O algoritmo MB é iterativo e exclui os pontos que correspondem a certas condições de vizinhança. Todo o procedimento é baseado nos padrões de máscaras mostrados na figura 3.7. Nestes padrões, o pixel p1 e os pixels da cor cinza têm valor 1 e fazem parte dos objetos. Os pixels hachurados têm valor zero (brancos) e fazem parte do fundo (background) da imagem. Dada uma certa imagem “A”, onde “a” é um pixel qualquer e “a pertence A” diz-se que o pixel “a” corresponde aos padrões se posicionando as máscaras sobre a imagem, com o pixel p1 sobre “a”, existe uma coincidência exata da imagem com a máscara naqueles pontos. Esta verificação também deve ser realizada rotacionando-se estas três máscaras por todos os múltiplos de 90º.

Estas três máscaras devem ser passadas por toda a figura. A iteração deste método é simples: consiste em remover simultaneamente todos os pixels que condizerem com as máscaras Alfa 1 e Alfa 2 mas NÃO com Beta.

24

Page 25: Afinamento de Imagens Digitais - Thinning of Digital Images

4. RESULTADOS EXPERIMENTAISEste capítulo apresenta os experimentos realizados através dos métodos de afinamento

descritos no capítulo 3, bem como uma comparação de seus resultados em imagens sintéticas e reais.

4.1 CONJUNTO DE IMAGENS

Para realizar estas comparações, serão utilizadas três figuras, as quais são mostradas abaixo. Dentro de todo o capítulo 4 estaremos utilizando fragmentos destas imagens (4.1, 4.2 e 4.3) e colocando-os lado a lado com fragmentos dos resultados dos afinamentos para que tudo possa ser melhor visalizado.

Figura 4.1 – Amostra 1 para afinamento

25

Page 26: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.2 – Amostra 2 para afinamento

Figura 4.3 – Amostra 3 para afinamento

4.2 PLATAFORMA HARDWARE E SOFTWARE

Para visualização das imagens originais e resultantes, foram utilizados os softwares Display (Linux) e Able Graphic Manager (versão 2.4 - Demonstrativa for Windows). Os equipamentos usados para processar e visualizar os modelos foram um computador Intel Pentium III 850 MHz com 192 Mbytes de memória RAM/DIMM 133Mhz, os terminais e servidores dos laboratórios deste curso.

A imagem 4.1 foi gerada a partir do programa Xfig, exportada para o formato JPG e após isso, convertida para o formato PBM atavés do software Xv (ambos os programas em Linux). A imagem 4.2 foi editada manualmente através do editor de textos Vim (em Linux Debian).

Os métodos foram implementados em linguagem C utilizando os editores Vim e Nedit (em Linux). O compilador utilizado foi o Gcc versão 2.5.3

26

Page 27: Afinamento de Imagens Digitais - Thinning of Digital Images

4.3 GRÁFICOS E IMAGENS GERADAS COM O SOFTWARE

4.3.1 Aplicação do Método Zhang-SuenO método de Zhang-Suen, quando comparado com outros (como o MB ou Stentiford) se

torna muito custoso à nível de processamento. Apesar de sua facilidade de implementação, o fato de analisar pixel a pixel verificando cada uma das condições e excluindo os pixels marcados somente ao final da confirmação de todas elas o torna efetivamente ineficiente para uma carga muito grande de arquivos. Abaixo se encontra ao resultado de sua aplicação sobre a figura 4.2:

Figura 4.4 – Afinamento realizado utilizando-se o método Zhang-Suen sobre a figura 4.2. Neste resultado pode-se observar algumas desformidades no esqueleto de alguns dos objetos, como por exemplo o desaparecimento da linha central da letra “E” ou ainda a linha reta que surgiu do lado direito da letra “X”.

O inconveniente mais aparente deste método é a perda da morfologia de alguns objetos, ou seja, a forma do objeto foi alterada durante o processo de afinamento e o esqueleto acabou não o representando com muita fidelidade. Isso ocorreu de diversas formas, como por exemplo :

a) a exclusão de algumas partes essenciais dos objetos durante o processo de afinamento. Como ilustração, podemos citar o objeto “E”, que aparece com mais detalhes na figura 4.13 (o qual após ser processado, passou a assemelhar-se a um caractere “C”, note que a linha central que desapareceu tinha largura de dois pixels). É possível verificar na figura 4.7 (a) e (b) que uma reta vertical (que deveria estar cruzando a reta horizontal para representar o losango) e na figura 4.7 (c) e (d) a parte superior do número “1” (o qual assemelha-se agora ao número “7”) foram eliminadas durante o processamento da imagem;

b) O efeito staircase consiste na formação de um estrutura semelhante à uma escada no esqueleto do objeto afinado. Isto pode ser melhor observado na figura 4.14 (b).

c) o algoritmo teve problemas para afinar algumas linhas retas seguidas de curvas. Estas ocorrências passaram a ser representadas, no esqueleto, por curvas irregulares como é possível observar na figura 4.5, onde a letra “D” passou a ser semelhante a um número “0”;

27

Page 28: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.5 – Exemplo de problemas que podem ocorrer na morfologia dos objetos com o método de Zhang-Suen (a) objeto extraído da figura 4.2 (b) esqueleto, do objeto, extraído da figura 4.3.

d) surgimento de um segmento de linha reta (a qual não pertence a parte alguma do objeto) quando o ângulo entre duas linhas é relativamente fechado. É possível visualizar este caso através da figura 4.6, onde os objetos “2” e “X” e a linha com curvas aparecem respectivamente em sua forma normal e logo após afinados. Note que os ângulos entre as duas linhas inferiores do “2”, entre as duas linhas do lado direito do “X” e a curva assinalada em (c), são igualmente fechados. O lado esquerdo do “X” que tem um ângulo levemente mais aberto (diferença de um pixel) não sofreu tamanha alteração.

Figura 4.6 – (a), (b) e (c) Exemplos do problema da inserção de uma linha reta no esqueleto dos objetos com o método de Zhang-Suen. O afinamento de linhas que se cruzam pode causar o surgimento deste efeito colateral indesejado. (a) e (b) são o resultado do afinamento da figura 4.2 e (c) o resultado do afinamento da figura 4.1.

Figura 4.7 – Fragmentos da figura 4.1 e seu afinamento por Zhang-Suen. (a) o losango original (b) afinamento do losango, é possível notar que deveriam existir duas linhas representando este objeto: uma horizontal e outra vertical (c) e (d) temos respectivamente os objetos e seus afinamentos. É possível verificar a falha indicada na figura, onde a parte superior do objeto “1” foi excluída por completo e agora este objeto se assemelha a um número “7”.

Finalmente, ao aplicarmos este método sobre a figura 4.3, é possível observar que o afinamento foi realizado de uma forma satisfatória e que apesar do esqueleto do objeto “4” apresentar um aspecto distorcido, o maior problema aqui foi a ocorrência da staircase. Isto pode ser visto na figura 4.8:

28

Page 29: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.8 – O staircase acabou sendo o problema mais nítido desta vez no resultado de Zhang-Suen

4.3.2 Combinação dos Métodos Zhang-Suen e Máscaras de Holt (staircase removal)

A ênfase aqui será dada às máscaras de Holt, as quais tratam do staircase removal e podem ser utilizadas como pós-processamento sobre o esqueleto resultante de outros métodos. Encontramos nestes resultados várias semelhanças, mas com um diferencial: após a aplicação das máscaras, as formas semelhantes a uma “escada”, são removidas sem afetar o formato ou a conectividade dos objetos. A fórmula de Holt com a staircase removal constitui uma poderosa ferramenta para afinamento, superando os resultados da simples aplicação do algoritmo de Zhang Suen.

Mas todas as outras características dos esqueletos do método anterior são mantidas, como por exemplo: a exclusão de partes essenciais do objeto durante o processamento da imagem, que pode ser observado na figura 4.13 (b), onde a barra mediana horizontal da letra “E” sumiu. Outro problema, apesar de mais suave, é o aparecimento de linhas retas ao se afinar linhas inclinadas que se cruzam com um ângulo relativamente fechado (tailing).

Na figura 4.10 (a) temos um exemplo que mostra como as máscaras de Holt têm um efeito poderoso ao tratar o staircase, note que a morfologia da letra “D” foi mantida e o problema ocorrido anteriormente mostrado na figura 4.5 foi eliminado. Na figura 4.10 (b), verificamos os pixels excluídos pelo tratamento feito através das máscaras, a qual pode ser comparada com a figura 4.6 (a).

29

Page 30: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.9 – Resultado do afinamento da figura 4.2 com o método de Holt

Figura 4.10 – A ação das máscaras de Holt pode ser vista ao se comparar este esqueleto com o das figuras 4.5 e 4.6 (a). Ambos os fragmentos (original e esqueleto) foram extraídos das figuras 4.2 e 4.9 respectivamente.

4.3.3 Aplicação do Método de Stentiford

Aqui podemos observar claramente que dentre as opções de métodos acima citados o de Stentiford é o que preservou a melhor morfologia dos objetos da imagem, ou seja, aquele que fez com que o esqueleto representasse melhor o objeto original. Isso pode ser observado na figura 4.13 (a), na qual o objeto “E” foi afinado com este método e teve sua morfologia preservada. Apesar disso, existe uma grande inconveniência no uso deste algoritmo a qual se deve ao fato de que ao realizar o afinamento de um objeto que contém partes arredondadas ocorre o problema da “staircase”. Pode-se ver este fato na figura 4.14 (d). Aqui, este efeito colateral qual será um pouco diferente do encontrado no método de Zhang-Suen, pois neste caso ao afinar as partes arredondadas, os “degraus” que se formam poderão se tornar um pouco maiores do que os anteriores. Pode-se notar isso olhando-se para o esqueleto do objeto “B” na figura 4.12 (a), o qual ficou parcialmente deformado como indicado.

30

Page 31: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.11 – Resultado do afinamento realizado pelo método de Stentiford na figura 4.2

Aqui tivemos também mais um problema para afinar as partes arredondadas, onde ocorre o surgimento uma linha reta para representá-las, como pode ser visto na figura 4.12 (a). No entanto, isso tudo não representa uma perda muito significativa quando comparado às vantagens deste algoritmo, o qual é mais rápido que os anteriores. É possível verificar na figura 4.12 (b) e (c) a deficiência denominada Line Fuzz, onde qualquer pixel que esteja conectado à borda do objeto que está sendo afinado, pode criar um segmento que será considerado como pertencente ao esqueleto. Estes segmentos surgem em forma de “ramificações”, as quais estão indicadas nesta figura. Apesar de tudo, temos uma boa morfologia dos esqueletos.

Figura 4.12 – (a) Segmentos da figura 4.11 - aqui uma exemplificação do problema de staircase que o afinamento de Stentiford causa no esqueleto (b) e (c) segmentos da figura 4.1 e seus respectivos afinamentos utilizando o método de Stentiford - mostra-se certa deficiência de afinamento, já que no esqueleto surgem segmentos indesejados e que não fazem parte do objeto.

Outra deficiência que ocorre, é o surgimento de um linha reta (tailing) na intersecção de duas linhas quando o ângulo entre elas é muito pequeno. Observando-se a parte inferior do objeto “2” na figura 4.12 (a) poderemos verificar isso.

31

Page 32: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.13 – Fragmentos da figura 4.2 (a) afinamento por Stentiford (b) afinamento por Holt (c) afinamento por Zhang-Suen – até aqui, a melhor morfologia apresentada na maioria dos objetos foi a do método de Stentiford, apesar de inserir “escadas” ao afinar partes as arredondadas dos objetos.

Figura 4.14 - (a) Objeto original, extraído da figura 4.2 (b) afinado por Zhang-Suen (c) afinado por Holt (d) afinado por Stentiford – aqui, temos apresentado o problema da staircase . Nota-se que em (c) este problema foi tratado.

Analisando a figura 4.15 (a), (b) e (c), pode-se notar as dificuldades ao afinar: os círculos da imagem cujo esqueleto foi sempre uma pequena “cruz”, a ocorrência da staircase e de segmentos retos que não pertencem ao esqueleto e a perda da morfologia do objeto “0”. Apesar disso, no geral foi possível manter uma boa forma dos objetos.

Figura 4.15 – (a) O afinamento dos círculos resultou em uma pequena cruz (b) Ao afinar alguns objetos, ocorreu o aparecimento de alguns segmentos de retas que não pertencem ao esqueleto, bem como a staircase (c) Perda da morfologia ao afinar o objeto “0”.

4.3.4 Combinação dos Métodos de Stentiford e Máscaras de Holt (staircase removal)

Como citado anteriormente, ao utilizar o método de Stentiford, haverá um problema de staircase nos afinamentos realizados em objetos que possuírem partes arredondadas. Sabendo disso, podemos realizar um pós-processamento do esqueleto resultante deste método utilizando uma ferramenta já conhecida: as máscaras de Holt. Como visto na seção 3.3, estas máscaras realizam a remoção de pontos que se assemelham a uma escada sem afetar o formato ou mesmo a conectividade do objeto.

Como resultado desta primeira operação (aplicação do Stentiford), teremos primeiramente um esqueleto com todas as deficiências citadas no item 4.3.3: staircase, tailing, a inserção de algumas retas ao realizar o afinamento de partes arredondadas dentre outros. Ao aplicar as máscaras de Holt sobre o esqueleto resultante, teremos a remoção das “escadas”, e uma

32

Page 33: Afinamento de Imagens Digitais - Thinning of Digital Images

melhora significativa da morfologia dos objetos, como pode ser observado na figura 4.16, a qual é o resultado desta mescla de métodos sobre a figura 4.2:

Figura 4.16 - Resultado da aplicação do método de Stentiford seguido das máscaras de Holt à figura 4.2

Pode-se observar um certo problema no afinamento desta imagem no que diz respeito à letra “B” (vide figura 4.16) a qual perdeu um pouco de sua morfologia e agora se assemelha a um número “8”, ou seja, pode-se notar assim que em caso do objeto possuir muitos “degraus” um após o outro e em direções opostas, as máscaras de Holt podem comprometer o seu formato.

Outro problema que aparece (vide destaques da figura 4.17) é o line fuzz (já comentado anteriormente).

Figura 4.17 – Combinação dos métodos de Stentiford e Holt: fragmento da figura 4.1 afinada

Na figura 4.18, fica visível que, aplicando Stentiford+Holt agora na figura 4.3, mais uma vez foi possível resolver o problema da staircase, mas alguns problemas persistem no esqueleto como por exemplo: os segmentos extra que aparecem conectados ao esqueleto e que não representam parte alguma da figura original.

33

Page 34: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.18 – (a) e (b) Demonstração dos problemas de segmentos de retas que apareceram conectados ao esqueleto.

4.3.5 Aplicação do Método da Morfologia MatemáticaAqui, é visível a distorção causada pelo algoritmo quando objetos bem representados

tornam-se de difícil reconhecimento. É o caso do objeto “N” da figura 4.19, o qual ficou deformado pois ocorreu o que chamamos de tailing. Este problema, que consiste na inserção de uma reta onde deveria haver apenas a intersecção de duas linhas, ocorre várias vezes durante a aplicação deste método. Isto acontece duas vezes no objeto “N”.

Figura 4.19 - Resultado da aplicação do método da morfologia em três objetos distintos da figura 4.2. Em (a), temos os objetos originais e em (b) seu esqueleto.

Percebe-se também que o número “2” acabou não seguindo seu tracejado original também por ocorrência de tailing e na letra “H” as retas foram corrompidas onde deveria haver um simples encontro entre as duas retas. Além disso, todas as figuras apresentam ramificações a mais nas extremidades das retas, como visto na figura 4.19:

34

Page 35: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.20 – (a) Fragmento extraído da figura 4.2 (b) pequenos traços a mais no esqueleto da imagem, este é o efeito colateral de se utilizar o afinamento baseado em Morfologia Matemática

Estas deformações são causadas provavelmente pela aplicação dos elementos estruturantes. Uma possível alteração nestes elementos poderia resolver estas deficiências do algoritmo. O aparecimento destes traços nas extremidades pode ser consertado com a aplicação do algoritmo de “Poda” (Pruning) visto na seção 4.3.7, eliminando estas ramificações (que também aparecem na figura 4.21).

Apesar destes defeitos, o algoritmo de morfologia matemática é bastante útil pois mantém boa parte da constituição da imagem intacta, principalmente se compararmos com os métodos anteriores. Um dos principais problemas do método de Stentiford, o mais eficaz até então, é a ocorrência de staircase solucionada apenas com a aplicação das máscaras de Holt. Com a morfologia matemática, esse problema não ocorre. Na figura 4.22, uma comparação entre os resultados do método de Stentiford com Morfologia Matemática.

Figura 4.21– Resultado da aplicação da Morfologia sobre alguns objetos da figura 4.1.

Figura 4.22 – (a) Objeto original, extraídos da figura 4.2 (b) esqueleto após a aplicação do método de Stentiford (c) esqueleto após aplicação do método de Morfologia Matemática - apesar dos defeitos, os resultados da Morfologia Matemática conservam melhor a forma da imagem, ou seja, criam um esqueleto melhor.

35

Page 36: Afinamento de Imagens Digitais - Thinning of Digital Images

Na figura 4.23 (a) e (b) pode-se verificar nos esqueletos dos objetos o aparecimento de ramificações que não fazem parte da imagem e que não a representam. O caso mais crítico aconteceu com esqueleto do objeto “J”, o qual acabou “recebendo” em um dos pontos várias sub-ramificações. Como já mencionado anteriormente, mesmo assim a melhor morfologia dos objetos foi deste algoritmo.

Figura 4.23 - (a) e (b) Ramificações que aparecem nos esqueletos ao utilizarmos este método

4.3.6 Aplicação do Método MB

Nos resultados deste algoritmo foi possível observar, em especial, uma certa dificuldade de afinamento em objetos que possuem poucas linhas em “curvas”, como pode ser observado nos exemplos específicos baseados nas imagens afinadas:

Figura 4.24 – Resultado do afinamento com o método MB realizado na figura 4.2

36

Page 37: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.25 – Resultado do afinamento do método MB realizado na figura 4.1

Note que objetos como “X” e “W” sofreram um bom processo de afinamento, mas em casos extremos, como mostrado na figura 4.26 podemos notar que os objetos “E”, “A” e “H” ainda possuem largura de dois pixels na maior parte de sua extensão. Pode-se notar ainda que este problema aparece quando é preciso afinar linhas que se cruzam (e/ou encontram) formando um ângulo que se aproxima de 90º.

Figura 4.26 – Afinamento com MB resultou em problemas de afinamento, em especial quando existe a junção em 90º de duas linhas (conforme indicado na figura)

Observando a figura 4.27 (a) e (b), respectivamente o polígono o resultado do MB, é possível verificar que houve uma pequena incoerência no afinamento deste objeto (assim como também houve no afinamento de Zhang Suen), pois onde existe somente uma pequena reta vertical deveria haver o cruzamento de duas retas (uma vertical e outra horizontal – vide figura 4.12 (b) e (c): afinamento realizado nestes mesmos objetos utilizando Stentiford). Na figura 4.28 (b) observa-se que o problema de manter a largura de dois pixels am alguns segmentos da figura (onde existe a intersecção de duas linhas com um ângulo de 90º) é inerente à este método.

37

Page 38: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.27 – (a)Polígono original (b) afinamento usando o método MB - pequena incoerência no resultado do afinamento do polígono: somente uma linha reta vertical passou a representá-lo, no entanto deveria haver uma linha horizontal a cruzando.

Figura 4.28 – (a) Segmento da figura 4.1 (b) o mesmo segmento da figura 4.1 afinado com o método MB. Aqui temos o efeito colateral inerente ao método MB quando este afina linhas que se cruzam formando um ângulo de aproximadamente 90º, neste caso então o esqueleto dos segmentos de reta próximos ao encontro passam a ter dois pixels de largura.

Ainda é possível destacar a boa atuação deste método ao afinar os objetos abaixo mostrados. Note que, diferentemente de Stentiford, aqui foi possível obter um esqueleto sem ramificações em sua extensão, assim sendo, os objetos ficaram melhor representados.

Figura 4.29 – Desempenho deste método ao afinar objetos sem deixar as ramificações indesejadas que aparecem no Stentiford

Como pode-se notar na figura 4.30 (a) e (b), o segmento central do esqueleto do objeto “H” possui um pouco de ruído e os esqueletos de alguns dos objetos (como “J”) ficaram com alguns segmentos de reta que não fazem parte do objeto. Na letra (c), podemos ainda observar que a letra “T” ficou com sua parte superior distorcida.

38

Page 39: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.30 – (a) Ruídos na parte central do esqueleto do objeto “H” (b) Segmentos de reta não pertencentes à imagem original (c) parte superior do esqueleto do objeto “T” com incoerência.

Como sempre, a largura de dois pixels em alguns pontos dos esqueletos é inerente ao algoritmo, isto pode também ser observado na figura 4.30 (a) e (b). Apesar disso, note que a morfologia dos objetos foi mantida e que já é possível realizar um reconhecimento dos objetos sem maiores problemas com a aplicação de máscaras.

Nos demais casos, o algoritmo reagiu bem e produziu esqueletos sem deformações no que diz respeito à morfologia dos objetos, com poucos ruídos e com uma boa qualidade.

4.3.7 Combinação dos Métodos MB e Máscaras de Holt (staircase removal)

Nesta mescla de métodos, obtivemos um resultado interessante, onde todos os segmentos de figuras que possuem largura de dois pixels foram processados e passaram a ter uma forma de “dente-de-serra”, ou seja, a conectividade foi mantida somente através dos pixels que se conectam pelas diagonais. Este resultado é mostrado na figura 4.31:

Figura 4.31 – Método de afinamento MB seguido das máscaras de staircase removal de Holt aplicados à figura 4.24

Na figura 4.32 (a) e (b), podemos observar melhor o efeito descrito anteriormente. Note que todos os segmentos do esqueleto que estão na forma de “dente-de-serra” (ou zigue-zague) possuíam uma largura de dois pixels anteriormente. Este efeito abaixo mostrado, e que foi gerado pela lógica da staircase removal, possui uma solução relativamente simples: basta aplicar algumas máscaras as quais eliminam os pixels em diagonais e repõe pixels em linha reta.

39

Page 40: Afinamento de Imagens Digitais - Thinning of Digital Images

Obviamente, é muito mais prático evitar que este efeito ocorra.

Figura 4.32 - (a) e (b) Segmentos da imagem 4.31, a qual foi afinada utilizando-se esta mesma mescla de métodos (afinamento com o método MB seguido da aplicação das máscaras de Holt). Note que em ambos os casos, os objetos sofreram uma transformação interessante, porém indesejada.

4.3.8 Combinação dos Métodos MB e Stentiford

Novamente, uma alternativa para eliminar as deficiências particulares de cada método (largura de dois pixels do MB e ramificações indesejadas do Stentiford) é realizar a mescla (ou mix) destes métodos de afinamento. Para isto, basta aplicar um pós-processamento à imagem resultante do algoritmo MB utilizado o método de Stentiford. A figura 4.33 é a resultante deste pós-processamento, utilizamos como matriz a figura 4.1:

Figura 4.33 – Afinamento da figura 4.2 utilizando-se o método MB seguido de Stentiford: isso vem sanar a maioria dos problemas enfrentados até agora em Stentiford, mas permanece um deles: o staircase

Todos os problemas de segmentos com largura de dois pixels e ramificações indesejadas foram eliminados e o esqueleto passou a ser mais nítido e robusto. Apesar disso, voltamos a um problema que está sempre presente em objetos afinados através de Stentiford: o staircase. Assim sendo, como é possível ser visto na próxima seção, a aplicação das máscaras de Holt no resultado do método acima é bem vinda.

Apesar da manutenção da morfologia dos objetos (ou seja, os segmentos de retas conectadas ao esqueleto ainda persistem), foi possível solucionar o problema da largura de dois

40

Page 41: Afinamento de Imagens Digitais - Thinning of Digital Images

pixels e facilitar um possível pós-processamento da imagem resultante.

Figura 4.34 – (a) e (b) em ambas as figuras, à esquerda está o afinamento por MB2 e à direita a combinação do MB2 com Stentiford. É possível notar claramente a largura de dois pixels à esquerda de (a) e (b), com como o refinamento disto à direita.

4.3.9 Combinação dos Métodos Morfologia Matemática e Poda

Como citado anteriormente, na seção 4.3.4, o método da Morfologia causa um problema bem visível ao esqueleto da imagem: as ramificações. Mas este inconveniente pode ser amenizado através do método da Poda (Pruning). Durante os testes realizados, os resultados obtidos foram satisfatórios e proporcionaram uma das melhores soluções obtidas neste estudo. Na figuras 4.35 (a), (b) e (c) e 4.36 (a) e (b) podemos comparar os alguns dos resultados. É possível notar que após o uso da Poda, todas as características do método da Morfologia foram mantidas, menos as ramificações indesejadas. Apesar da ocorrência de tailing (efeito inerente ao método morfológico), a forma dos objetos foi mantida em um bom padrão e sem ruídos.

Figura 4.35 – (a), (b) e (c) Afinamento da figura 4.2, à esquerda de cada figura temos somente com o método da Morfologia e à direita temos este mesmo afinamento utilizando o pós-processamento da Poda.

41

Page 42: Afinamento de Imagens Digitais - Thinning of Digital Images

Figura 4.36 – Afinamento da imagem 4.1 utilizando a mescla destes métodos (a) imagem afinada somente com a Morfologia (b) utilizando a mescla dos métodos.

Ao verificar as imagens, pode-se notar que em alguns casos as ramificações não são completamente eliminadas, neste caso não há o que fazer, já que: – são algumas excessões que ocorrem ao algoritmo.– estas ramificações remanescentes não influem de maneira impactante em uma pós-análise.

Ao remover as ramificações, é possível obter um bom resultado, isso pode ser visto nos esqueletos dos objetos “g” e “9” na figura 4.37, os quais ainda apresentam a ocorrência de staircase (uma aplicação das máscaras de Holt resolve sem maiores problemas). Na indicação da figura 4.37 (a) podemos notar que persiste o aparecimento de um pequeno segmento de reta, o qual já foi formado no afinamento da Morfologia. No destaque da figura 4.37 (b) um segmento quadrado, o qual é proveniente do afinamento anterior ao pruning.

Figura 4.37 – (a) e (b) Aparecem na seqüência a imagem original, o afinamento por Morfologia e o afinamento de Morfologia seguido por Poda

42

Page 43: Afinamento de Imagens Digitais - Thinning of Digital Images

5. CONCLUSÕES

O processamento de imagens é o estudo da representação e manipulação de informações pitorescas. Este processo é realizado em computadores digitais, os quais manipulam imagens, representando-as em forma de arrays ou matrizes de valores discretos. Os avanços na tecnologia dos computadores têm facilitado cada vez mais a utilização deste tipo de processamento e análise em áreas nas quais seria impossível anteriormente devido à sua alta complexidade, custo computacional, resolução de vídeo e eficiência dos algoritmos dentre outros fatores. Podemos citar algumas destas novas áreas: diagnósticos médicos, controle de qualidade industrial, visão robótica, astronomia, veículos inteligentes / sistemas de auto-estradas computadorizadas.

Muitas técnicas complexas foram desenvolvidas e novos objetivos, que antes não eram tangíveis, podem agora ser alcançados. As novas máquinas passaram a utilizar mais eficientemente as técnicas matemáticas para solucionar problemas complexos, os métodos de convolução passaram a ser mais rápidos através da aplicação das Transformadas de Fourrier.

Com este estudo foi possível observar que as melhores soluções para o afinamento são obtidas na verdade com a mescla (ou combinação) de métodos já existentes, já que assim, um pode compensar as deficiências do outro. As melhores soluções foram obtidas com os seguintes combinações de métodos:

- Stentiford seguido das Máscaras de Holt - Morfologia Matemática seguido do Pruning- MB seguido de Stentiford

Para o complemento deste estudo sugerimos a implementação de um “Afinamento Seletivo”, ou seja, define-se uma classificação prévia de tipos de objetos a serem afinados e os respectivos métodos a serem utilizados para este afinamento, por exemplo:

- TIPO 1:Objetos que possuem até 4 cantos quadriculados e nenhuma parte arredondadaAfinamento por Zhang-Suen

- TIPO 2:Objetos que possuem até 4 cantos quadriculados e 4 partes arredondadasAfinamento por Stentiford e Holt

- TIPO 3:Objetos com mais de 5 cantos quadriculados e/ou mais de 5 partes arredondadasAfinamento por MB e Stentiford

Através da aplicação de máscaras sobre a imagem realiza-se uma classificação de todos os objetos a serem afinados (estes objetos serão enquadrados em um dos tipos exemplificados acima). Após esta etapa, basta aplicar o método de afinamento pré-definido para um daqueles tipos. Como exemplo, podemos extrair alguns objetos da figura 4.1 e sua classificação seria como a mostrada na figura 5.1:

Figura 5.1 – Exemplo de uma pré-classificação para alguns dos objetos da figura 4.1. Note que em (a) temos um objeto do TIPO 3, em (b) temos dois objetos do TIPO 1 e em (c) um objeto do TIPO 2.

43

Page 44: Afinamento de Imagens Digitais - Thinning of Digital Images

REFERÊNCIAS BIBLIOGRÁFICASChauhan, M. S., “Hindi Character Recognition”, Department of Computer Science & Engineering – Indyan Inst. of Technology Kanpur”, 2001

Davies E.R., Plummer A.P.N. , “Thinning Algorithms: A Critique and a New Methodology”, Pattern Recogn. , vol 14, nº 1, pp 53-63, 1981.

Gonzalez R. and Woods R., “Digital Image Processing”, Second Edition, Prentice-Hall, 2002.

Hilditch C. J., “Comparison of a Thinning Algorithm in a Parallelprocessor”, Image Vision Comput, vol 1, nº 3, pp 115-132, 1983.

Holt, C. M. et al, “An Improved Parallel Thinning Algorithm”, Communications of the ACM, vol. 30, n° 2, pp 156-160, 1987

Lam L. et al, “Thinning Methodologies – A Comprehensive Survey”, IEEE Trans. On Patt. Analisys and Mach. Intell., vol 4, nº 9, september, 1992.

Manzera A. et al, “Ultra-fast Skeleton Based on Isotropic Fully Parallel Algorithm”, Proc. Of Discrete Geometry for Compuiter Imagery, 1999.

Moayer B. and Fu K.S., “A Sintactic Approach to Fingerprint Pattern Recognition”, Pattern Recogn., vol 7 pp. 1-23, 1975.

Mundy J. L. and Joynson R. E., “Automatic Visual Inspection Using Syntatic Analisys” in Proc. Int. Conf. Patt. Recogn. Image Processing, pp144-147, 1977.

Niblack C.W. et al, “Generating Skeletons and Centerlines from the Distance Transform”, Graphical Models and Image Processing. 54, 5, 420-437, 1992

Nguyen T. V. and Sklansky J., “A Fast Skeleton-Finder for Coronary Arteries” in Proc. 8th Int. Conf. Patt. Recogn. (Paris, France), pp 481 – 483, 1986.

Peixoto A, e Velho L., “Transformadas de Distância” , PUC – Rio. Inf.. MCC 35/00, 2000

Preston K., “The Cellscan System – A Leucocyte Pattern Analyzer”, In Proc. West Join Comput. Conf. (Los Angeles C. A), pp 173-183, 1961

Preston K. and Duff M.J.B., “Basies of Cellular Logic With Some Applications in Medical Image Processing”, Proc IEEE, vol 67 nº 5 , pp 826-857, 1979

Rosenfeld A. and Davis L.S., “A Note for Thinning” , IEEE Trans Syst. Man. Cybern., vol 25, pp 226-228, 1976

Rosenfeld A. and Pfaltz J.L., “Sequential Operations in a Digital Picture Processing”, J. ACM 13, 4 , pp 471-494, October, 1966.

Stefanelli R. and Rosenfeld A., “Some Parallel Thinning Algorithms for Digital Images”, J. ACM, vol. 18 , nº 2, pp 225-264, 1971

Stentiford F.W.M. and Mortimer R.G., “New heuristics for thinning binary handprinted characters for OCR.”, IEEE TRANS. SYS. MAN AND CYBER. Vol. SMC-13, no. 1, pp. 81-84, 1983.

Tamura H., “A Comparison of Line Thinning Algoritms From a Digital Geometry Viewpoint”, in Proc. 4th Int. Conf. Patt. Recogn. (Kyoto – Japan), pp 715-719, 1978.

Ye Q. Z. and Danielsson P. E., “Inspection of Printed Circuit Boards by Connectivity Preserving

44

Page 45: Afinamento de Imagens Digitais - Thinning of Digital Images

Shirinking”, IEEE Trans. Pattern Anal. Mach. Intell. , vol 10, nº 5, pp 737-742, 1988.

Zhang T.Y. and Suen C.Y., “A Fast Parallel Algorithm for Thinning Digital Patterns”, Comm. ACM. ,vol 27, nº 3, pp 236-239, 1984.

45

Page 46: Afinamento de Imagens Digitais - Thinning of Digital Images

APENDICE A

A.1 IMAGEM BINÁRIAO conceito básico de imagem binária diz que esta é uma coleção de valores discretos um

ou zero (os quais significam respectivamente preto ou branco). Esta coleção é melhor representada por uma matriz A , onde cada célula Ai,j possui apenas um único valor discreto. Neste tipo de imagem, os pixels que fazem parte dos objetos são representados pelo valor 1 (preto) e os pixels que compõem o fundo da imagem são os que possuem o valor zero (branco) .

A.1.1 Formato PBMDentro do conceito de imagem PBM (Portable Bitmap) podemos identificar três tipos de

formatos: preto e branco, escala de tons de cinza e em cores. Nenhum destes formatos é comprimido, mas todos apresentam uma estrutura comum1. Os três tipos de formato de imagens são:

• PBM (Portable BitMap) – imagens em preto e branco (sem tons de cinza)• PGM (Portable GrayMap) – imagens em tons de cinza• PPM (Portable PixMap) – imagens em cores

Originalmente, o objetivo destes formatos foi simplesmente o de possibilitar a transmissão de imagens via e-mail (já que há algum tempo atrás os serviços de correio eletrônico não permitiam anexar qualquer tipo de arquivo, fossem estes binários ou não). Isso foi feito de uma maneira muito simples, pois a representação das imagens no formato PBM, PGM e PPM é feita por meio de caracteres ASCII, assim sendo, as imagens podiam ser inseridas nas mensagens de e-mail como se estas fossem um texto comum. Sem dúvida alguma, o maior problema deste tipo de imagem é o seu tamanho relativamente grande (pois como já dito anteriormente, não há compressão). Com o passar do tempo, a definição do formato foi modificada para que fosse possível representa-las de forma binária.

A.1.2 Especificação dos formatos PBMUm arquivo de imagem no formato PBM, é constituído dos campos abaixo especificados

(inclusive nesta mesma ordem):

a) Identificador do tipo de formato: é também chamado de “magic number”, e varia de acordo com o tipo da imagem: Tipo ASCII BinárioPBM P1 P4PGM P2 P5PPM P3 P6

b) Espaço em branco2 c) Largura da imagem: é dada em pixels (e em notação decimal). Está formatada em caracteres ASCIId) Espaço em brancoe) Altura da imagem: é dada em pixels (e em notação decimal). Está formatada em caracteres ASCIIf) Espaço em branco

1 Por isso, estes formatos são muitas vezes todos designados (erroneamente), por PPM.

2 Este espaço pode ser constituído por qualquer número de caracteres “em branco”, fim de linha ou tabulação. Alguns softwares de interpretação podem não suportar caracteres de tabulação.

46

Page 47: Afinamento de Imagens Digitais - Thinning of Digital Images

-- Se a imagem for dos tipos PGM ou PPM, ela possuirá os campos g e h:g) Valor máximo dos tons de cinza (PGM) ou das componentes de cor (PPM) : no formato PGM, este campo é dado em notação decimal e no formato PPM ele se encontra em caracteres ASCII.h) Espaço em branco

-- Para todos os três tipos de formato segue-se:

i) Corpo da imagem: são os valores de cada um dos pixels da imagem. O número total de pixels é dado pela altura da imagem vezes a sua largura, para os tipos PBM e PGM. Nos tipos PPM temos três vezes este número, já que cada pixel é representado pelas três componentes R(red), G(green) e B(blue) da respectiva cor.

Os programas que realizam a exibição do arquivo de imagem, fazem a leitura (ou varredura) deste começando da esquerda para a direita e de cima para baixo, linha a linha. Na figura A.1 (a), é possível verificar como é o formato de um arquivo (em ASCII) de uma imagem PBM e, na figura A.1 (b) podemos verificar (em uma escala ampliada) como esta imagem fica ao ser exibida em um programa de visualização de imagens.

Observando a figura A.1 (a), pode-se notar na primeira linha que o “magic number” tem o valor P1, indicando o tipo PBM. Na segunda linha, pode-se observar que a largura (8) e a altura (10) da imagem são dadas em notação decimal e separadas por um espaço em branco (o qual pode ser substituído por marcas de tabulação ou marcas de fim de linha). As partes restantes do arquivo mostram o valor de cada pixel do corpo da imagem, sendo que cada valor 1 (um) indica um pixel da cor preta, os quais fazem parte dos objetos, e cada valor 0 (zero) indica um pixel da cor branca, ou seja, do fundo da imagem.

Figura A.1 – (a) imagem em formato ASCII, sendo magic number = P1 (indicando o tipo PBM), largura = 8 e altura = 10 (ambas indicadas em notação decimal e equivalendo ao número de pixels). Na terceira linha, tem início a representação do corpo da imagem, onde o valor um indica um pixel preto (que faz parte de um objeto) e o valor zero indica um pixel branco (que faz parte do fundo da imagem).

Para os formatos PGM e PPM, o corpo da imagem é armazenado em caracteres contíguos, ou seja, sem separadores entre os valores consecutivos. No formato PBM, é realizada a combinação dos valores de cada 8 pixels consecutivos em um único caractere (byte). No formato PGM, faz corresponder um caractere a cada pixel e o PPM três caracteres 3.

3 Um caractere (byte) por cada componente RGB do pixel, restringindo assim o valor máximo dos tons de cinza e das componentes de cor a 255.

47

Page 48: Afinamento de Imagens Digitais - Thinning of Digital Images

-- Para as variantes ASCII dos três tipos de formato, aplicam-se ainda as seguintes regras:• É possível realizar a inserção de qualquer comentário em qualquer parte do arquivo. Para isto, basta fazer a indicação do início do comentário utilizando o caractere “#”, assim todo o texto, incluindo este caractere até a indicação de fim de linha será reconhecido como parte do comentário;• Existe uma limitação no tamanho máximo de cada linha, a qual não deve possuir mais de 70 caracteres 4.

4 Esta limitação deriva da especificação inicial visando a transmissão de imagens por e-mail.

48