Fases do Processo
Detecção
de Bordas
Vetorização
Reconhecimento
Fase 1 - Detecção de Bordas
Objetivos:
•
Distinguir os pixels de borda dos demais
•
Manter os contornos dos objetos conectados (de forma
a contorná-lo passando apenas por pixels “de borda”)
•
Reduzir ao máximo a expessura dos contornos
Gradiente da Luminosidade
L = 0.30R +
0.59G + 0.11B
Gradiente
L=
{
255, L > t
0, L <= t
Kernels para Cálculo de Gradiente
???
Prewitt
t = 60
Sobel
t = 180
•Diferença muito pequena
•O método de Sobel deixa um pouco menos de ruído
t = 240
Uso do Gaussiano antes do Gradiente (Sobel)
Sem Gaussiano
Gaussiano n = 1
Gaussiano n = 2
Gaussiano n = 3
•Faz muita diferença.
•A diferença de ruído entre frames consecutivos diminui a medida
que aplicamos gaussianos com kernels maiores.
•Como o filtro gaussiano borra a imagem, os detalhes são
perdidos (para o caso da detecção de bordas é uma boa, já que
detalhes não são importantes).
Método de Canny
Intensidade
O método tenta pegar o pixel
de máxima intensidade na
direção perpendicular à borda
(direção do gradiente).
Método de Canny
G1
G1
G2
Gy
G
α
G2
G1: Se
>
‘s, então
= borda
G2: Se
>
‘s, então
= borda
Gx
α = arctan(|Gy| / |Gx|)
Método de Canny
Sem Gaussiano
Gaussiano n = 1
Gaussiano n = 2
Gaussiano n = 3
•Parece ser o melhor método até agora.
•Como nos métodos anteriores, a diferença de ruído entre frames
consecutivos diminui a medida que aplicamos gaussianos com
kernels maiores.
•Com uma quantidade de pixels brancos menores, a vetorização
dos segmentos de borda fica mais rápida.
Fase 2 - Vetorização
Processo:
Pixels de
borda
Método M
Idéia: a partir de um pixel inicial
qualquer, percorrer todos os
pixels de borda conectados em
todas as direções até que um
deles saia do limite definido por
duas retas paralelas com uma
distância máxima pré-definida.
Pixels de borda
Método M
p2
p1
θ
θθ
d
p0
d
θ
θ = arcsen(d / dist(p0, p1))
Método M
Otimizações:
•O método percorre os pixels em apenas quatro direções: ,
,  e  evitando assim fazer curvas (e melhorando a
performance).
•O método termina de processar um conjunto conectado de
pixels assim que encontra um ciclo (para simplificar e
melhorar a performance).
Pixels de
borda
Método M
Vantagens:
•O método acha qualquer contorno fechado.
•O método gera segmentos já conectados (grafos) eliminando
a necessidade de um pós-processamento.
Desvantagens:
•O método descarta ciclos possivelmente melhores que os
ciclos escolhidos.
•O método não acha nenhum contorno que não esteja
totalmente conectado.
Erosão Dilatação
A idéia é conectar os
segmentos que tiveram
algum tipo de falha no
processo de detecção
de borda.
Mexendo um pouco
nos parâmetros da
erosão, podemos
conectar segmentos que
não estejam totalmente
alinhados (quase nunca
estarão).
Teste da Técnica de Erosão + Dilatação
Imagem de teste
Resultado
Porcentagem de frames nos
quais o objeto estrela foi
reconhecido corretamente:
Sem dilatação+erosão: 54%
Com dilatação+erosão: 95%
Conclusão: Vale muito a pena!
Fase 3 - Reconhecimento
Problema:
=
=
?
Tabelas de ângulos acumulados
|θ| = arccos(
(X0 - X1) (X2 - X1) + (Y0 - Y1) (Y2 - Y1)
)2
(X0 - X1
(X2, Y2)
)2
+ (Y0 - Y1
)2
)2
(X2 - X1 + (Y2 - Y1
)
Se (Y2 - Y0) (X1 - X0) < (Y1 - Y0) (X2 - X0)
então θ é negativo senão θ é positivo
θ
(X1, Y1)
Exemplo:
(X0, Y0)
Ângulo acumulado = θ1 + θ2
θ1
θ2
Tabelas de ângulos acumulados
A idéia é percorrer todo
o polígono começando
por um ponto qualquer.
A medida que a parte
percorrida vai somando
as porcentagens de
perímetro da tabela,
verificar se o ângulo
acumulado está próximo
do valor correspondente.
% do
perímetro
Ângulo
acumulado
0.15
72º
0.25
-72º
0.35
0º
0.45
-144º
0.55
-72º
0.65
-216º
0.75
-144º
0.85
-288º
0.95
-216º
Outras idéias não testadas ou que não
funcionaram
• Como usar o Laplaciano para detectar bordas (problema
das linhas duplas).
• Vetorização por detecção de cantos (usando os autovalores
da matriz ???) – não deu certo.
• Redução do número de cores da imagem inicial antes de
rodar o algoritmo de detecção de bordas – problemas com
o IM 3.0.
• Pesquisar técnicas para resolver o problema das sombras.
• Outras técnicas de reconhecimento sem vetorização.
Problema das Sombras
A sombra “amortece” a variação de intensidade
fazendo com que o gradiente não detecte a borda.
Conclusão
É difícil!!!
Bibliografia
• Livro do Forsyth
• Some Experiments in Image Vectorization - Javier
Jimenez, Jose L. Navalon
• Line Net Global Vectorization: an Algorithm and Its
Performance Evaluation - Jiqiang Song, Feng Su1, Jibing
Chen, Chiewlan Tai, Shijie Cai1
• Vectorization in Graphics Recognition: To Thin or not
to Thin - Karl Tombre, Salvatore Tabbone