Visão Computacional
1998

Esqueletonização  e Reconhecimento de Formas

Autor : Luiz Henrique Brillinger

Curso

Introdução ao Tratamento de Imagens e à

Visão Computacional

Luiz Henrique Brillinger

12-Esqueletonização
14-Reconhecimento de Formas

12-Esqueletonização

Introdução

• O que é esqueletonização ?

• Pode ser compreendido como a forma de representar imagens através da extração de suas características pelo processo de afinamento, resultando os pixels essenciais para composição de segmentos lineares com comprimento, tamanho e direção.

• Não é aplicavel à todos os objetos.
• O objetivo dos passos subsequentes muitas vezes indicam a técnica a ser usada.

Transformação do eixo médio

• Blum (1967)
• Trata todos pixels da borda como fonte de uma onda, que excita seus vizinhos com intervalo de tempo proporcional a distância.
• Quando duas ondas se encontram anula-se produzindo o eixo médio ou o esqueleto.
• Para usar este conceito em uma imagem calcula-se a distância de cada pixel até o pixel de borda mais próximo. 
• Pode ser usado a distância Euclidiana, 4-distância ou 8-distância.
• Calcule a distância Laplaciana.
• Os pontos que possuem maior valor pertencem ao esqueleto.

• • 

    4-distância 8-distância Euclidiana

    

Métodos Morfológicos Iterativos

• São baseados na retirada repetitiva de pixels em volta do objeto.
• Um conjunto de regras define quais pixels podem ser removidos.
• Normalmente um esquema de templates é usado para aplicar as regras.
• O processo para quando após duas passadas consecutivas não há retirada de pixel.

Stentiford - 1983

• Usa 4 templates 3x3
• Quando a template "bate" com a imagem o pixel do meio é removido (conectividade ¹ 1).
• Cada template possui uma ordem de procura:

• • M1 - esquerdaé direita, de cimaé baixo.

    M2 - cimaé baixo, da esquerdaé direita.

    M3 - direitaé esquerda, de baixoé cima.

    M4 - cimaé baixo, da direitaé esquerda

• a: remove pixels do topo
• b: remove pixels da esquerda
• c: remove pixels de baixo
• d: remove pixels da direita

• Problemas com algoritmos de erosão:

• • • • 

        a-Rebaixo (Necking) interseção de retas

        b- Cauda (tail) ângulo agudo entre retas

        c- Espúrio (spurious, line fuzzy) sujeiras conectadas

• Steinford sugere preprocessar para minimizar estes problemas.

• Passar smooting

• - Resolve problemas de espúrios.

  - Remove pixels com 2 ou menos vizinhos pretos com conectividade menor que 1.

• Aplicar procedimento chamado "acute angle emphasis" para problemas de necking.

• - Mudar para branco os pixels próximos a interseção usando 2 conjunto de templates.

  - Se na etapa anterior for removido algum pixel, passar novamente as 3 primeiras templates de cada conjunto.

• -Passar a primeira template de cada tipo se foi removido pixel anteriormente.

• • • • 

        Conjunto de templates para pre-processamento.

• Resultado do pre-processamento mais o afinamento. 

• O método é inconstante e não resolve problemas com caracteres largos. 
• O preprocessamento não casa com todas as situações de problemas.

Zhang - 1984

• Mais rápido e simples de ser implementado que o anterior (paralelo).
• O método é dividido em 2 subiterações :

• Primeira:

• 1 - Se a conectividade for 1.
• 2 - Se tem pelo menos 2 vizinhos pretos e não mais que 6.
• 3 - Se pelo menos um deles for branco (i,j+1), (i-1,j) e (i,j-1)
• 4 - Se pelo menos um deles for branco (i-1,j), (i+1,j) e (i,j-1) 
• Marque os pixels e remova no final desta subiteração.

• Segunda:

• repita os passos 1 e 2 anterior
• 3 - Se pelo menos um deles for branco (i-1,j), (i,j+1) e (i+1,j)
• 4 - Se pelo menos um deles for branco (i,j+1), (i+1,j) e (i,j-1) 
• Marque os pixels e remova no final desta subiteração

• O T ficou perfeito e o problema de cauda sumiu.
• Apresenta problema de rebaixo e espúrio.

Uso do Contorno de Objeto

• Consiste em selecionar o pixel do meio entre cada borda (Baruch 1988).
• O método usa uma janela retangular que cobre o objeto a ser esqueletonizado.
• O pixel esqueletal esta no centro da janela.
• A próxima janela é posicionada em função do pixel esqueletal atual.

• Procedimento:

• Escolher um ponto a esquerda (LP) e um a direita (RP) na borda do objeto e construir uma janela com distância fixa a partir de LP e RP.
• O pixel entre LP e RP é esqueletal.
• Localizar LLP e RRP na borda da janela na direção do esqueleto.
• Deslocar a janela para o novo ponto (LP=LLP e RP=RRP).
• Quando um pixel de fundo é encontrado dentro da janela existe uma ramificação.
• Selecionar, na borda da janela o pixel anterior entre LLP e RRP como LRP e o pixel posterior ao pixel de fundo como RLP.
• Recursivamente faça LP=LLP e RP=LRP...
• Quando voltar faça LP=RLP e RP=RRP (do ponto ramificado).

• Os pixels esqueletais são conetados com linhas finas para facilitar a visualização.

Objeto como Polígono

• Martinez-Perez (1987) usa as propriedades geométricas de um polígono, que representa a borda de um objeto, para localizar o esqueleto.
• Criar vetores entre cada pixel e armazena-los no sentido horário.

• Procedimento:

• Se o ângulo entre dois vetores for menor que 180°, uma bissetriz e construída até o lado oposto do polígono.
• Senão uma linha normal é construída no final e no início dos vetores até o lado oposto do polígono.
• O esqueleto inicia no vértice 1 e passa através dos pontos médios das linhas construídas.

• OBS: indicado para objetos finos como caracteres, gráficos, mapas...

• Os vértices 2 e 5 formam ângulo < 180 graus
• Nos outros vértices são traçadas linhas normais

Afinamento baseado na força

• Banda Digital é um conjunto de pixels conectados com as propriedades:

• Todos os pixels estão dentro de uma distância d e uma curva discreta C. A distância mínima entre C e qualquer pixel de borda é d/2.
• O valor de d é muito menor que o comprimento de C.
• A direção associada com cada pixel de borda é aproximadamente a mesma daquele próximo a C.

• Esta definição vale para a maioria das linhas grossas ou finas.
• Segmento digital é um subconjunto da banda extraídos com corte perpendicular a C.
• Um Fragmento é um segmento digital onde há uma brusca mudança na direção em C.
• O fragmento pode ser linear, côncavo ou convexo.
• Cada fragmento possui seu esqueleto, que é localizado através do calculo da força, que os pixels de fundo adjacentes a borda, exercem sobre os pixels do objeto.

• Quanto mais perto o pixel objeto do pixel de fundo maior a força exercida sobre ele.
• O fragmento é mapeado em quadrados e é determinado a ação da força em seus vértices.
• O esqueleto cai dentro dos quadrados onde a ação da força age em direções opostas.
• Estas áreas são subdivididas para o refinamento do esqueleto.

• A força no pixel é a soma de todas as forças de todos os pixels visíveis.

• Todos os pontos do fragmento corrente são considerados esqueletos até encontrar outro esqueleto ou uma borda.
• Verificar quais pontos podem fazem parte da construção do esqueleto.
• Verificar a potencialidade dos pixels do esqueleto serem tbém pixels de início.
• O processo se repete até que não haja mais mudanças ou a força igual a zero.

• a- força aplicada sobre cada pixel
• b- figura original.
• c- afinamento de Zhang-uen.
• d- esqueleto baseado na força.

14-Reconhecimento de formas

• Após identificar borda ou segmentar imagem, os pixels podem ser agrupados por operações de grupo.
• Ao pixel de borda é importante adicionar propriedades como direção da borda, gradiente, contraste de borda etc.
• A seguir são realizadas as operações de grupamento com aqueles de propriedade similar
• É adicionado aos pixels o grupo a que ele pertence.
• Estes grupos são segmentados em simples partes para que uma operação analítica possa ser encaixada.
• Ledley (1964) foi um dois pioneiros a usar esta técnica.

Conectando linhas e bordas

• Conectando linhas e bordas usando informações direcionais, é o processo pelo qual os pixels tem direções suficientemente similares podendo formar seqüências conectadas, de forma a ser identificada como um segmento de arco.
• O processo de procura para identificação dos rótulos é de cima-baixo, esquerda-direita

• Se o rótulo do pixel não foi previamente encontrado em seus vizinhos, então um novo grupo é criado com a direção da borda ou linha.
• Cada grupo é inicalizado com N0s 0

• s 0 - variância.
• N0 - é o peso da variância.

• Se houve dois ou mais rótulos vizinhos encontrados, após o pixel ser agrupado, é feito um teste para determinar se os dois grupos mais próximos a este podem ser unidos.

Segmentação de arcos

• Segmentação de arcos em um simples segmento, é um processo que particiona a seqüência do arco digital, extraído anteriormente, em subseqüências de arco tendo a propriedade que cada arco tem uma seqüência máxima que pode ajustar uma reta, ou uma curva de determinado tipo.
• A base do processo de particionamento é a identificação dos locais que:

• A) Tem curvatura suficientemente alta
• B) É contido por seqüências que podem ajustar uma linha reta ou curvas de um determinado tipo.
• Subseqüências que podem ajustar uma reta apresentam uniformidade de curvatura baixa.
• Subseqüências que podem ajustar uma curva apresentam uniformidade de curvatura alta.

• Exemplo de métodos para segmentação:

• - Ajuste e Corte Iterativo de ponto final.

• -Detecção do Ângulo Tangente

• • \

     

     

Transformação de Hough

• É um método para detectar linhas e curvas em imagens com níveis de cinza.
• A técnica de Hough (1962) procura por objetos na imagem através de fórmulas que os descrevem.
• É um método que pode localizar objetos que não estejam completamente definidos.
• Criar uma vetor somatório A com dimensões igual ao número de parâmetros desconhecidos da equação que está sendo procurada.
• Para a equação y=mx + b cria-se a matriz com dimensão A[m,b].
• A matriz A deve suportar todos os valores possíveis para m e b. 

• Examinando cada pixel e sua vizinhança na imagem, determina se há evidencia de borda naquele pixel, então calcula-se os parâmetros da curva específica que passa naquele pixel.
• A[m,b] é incrementado. Alguns esquemas somam 1 outros a intensidade do gradiente naquele pixel, ou...
• Após todos pixels processados, os maiores valores indicam a linha na imagem.
• Como o vetor A não diz onde começa e termina a linha, uma estrutura PTLIST[m,b] guarda o endereço dos pixels que formaram A[m,b]
• Para localizar o centro do raio de um círculo procede-se de forma semelhante procurando no vetor A o maior pico.

Exemplo de aplicação Hough

• Inspeção de placas de circuito impresso ( Hara et al, 1983 ).

• Tamanho da figura é aproximadamente 1,5 cm².
• Precisão da perfuradora é de 0,025mm.
• Normalmente um sistema CAD controla a perfuração da placa.
• Aqui como exemplo é coletado a imagem da placa com uma câmara.
• Se um quadro fosse captado a 1024 pixel, tería mais que 0,01mm e não teria precisão 0.025mm
• Variações nos padrões na aquisição da imagem.
• A imagem é fotografada em cima de um filme glossy transparente que pode causar reflexos, ruídos.
• Furos com diâmetros diferentes.
• O histrograma bimodal é representado pela figura a direita.
• Considerando a aquisição da imagem limpa facilita a segmentação por limiariadade.