Upload
pietro-almeida
View
221
Download
4
Embed Size (px)
Citation preview
Transformada de Hough
• Processamento global para a detecção de linhas retas numa imagem
• Nenhum conhecimento é necessário a respeito da posição das linhas
• Método robusto que pode ser generalizado a outras formas geométricas
• Suponha que para uma imagem de n pontos queiramos encontrar subconjuntosdestes pontos que sejam colineares:
Ideia 1: Encontrar todas as linhas determinadas por cada par de pontos e, então,encontrar todos os subconjuntos de pontos constituindo uma linha em particular.
linhas as todasencontrar se para )( i.e., 1)/2,-n(n : 2nOdeComplexidae
linhas as todascom ponto cada de comparação para )( i.e., ],2/)1([ 3nΟnnn
10 retas
Idéia 2: Transformada de Hough (1962)
• Considere um ponto da imagem e a equação geral da reta: ),( ii yx
baxy ii
• Pelo ponto passam infinitas retas (no plano contínuo) com valores de a e b variáveis.
),( ii yx
x
y
ix
iy
Todas estas retas obedecem à equação , com a e b variáveis. baxy ii
Assim, escrevendo a equação da reta na forma:
, ii yaxb
e considerando o plano ab (espaço de parâmetros), definimos uma reta de inclinação e ponto de intersecção ix iy
a
b
iy
inclinação ix
Um outro ponto introduzido no plano xy também terá uma retano espaço ab. Esta reta intersecciona a primeira no ponto (a’, b’) corres-pondente aos parâmetros da reta que une a .
),( jj yx
),( jj yx),( ii yx
a
b
b’
a’
ii yaxb
jj yaxb
x
y
),( ii yx
),( jj yx
inclinação a’
b’
Assim, todos os pontos pertencentes à mesma reta em xy têm intersecção,no plano ab, no ponto (a’,b’).
Implementação
• Subdivide-se o espaço de parâmetros em células acumuladoras
),( e ),( maxminmaxmin bbaa são os valores mínimos e máximos permitidos para ainclinação e intersecção das retas, respectivamente. Cada célula (i,j), com acumuladorA(i,j), guarda o número de ocorrências de . ji ba ,
• Inicialmente, estas células têm valor zero
• Para cada ponto no plano xy, considera-se o parâmetro a igual aos valorespossíveis de a (na subdivisão do espaço ab) e calcula-se b na equação:
kk yx ,
kk yaxb
• Se um valor de resulta em , então A(p,q) = A(p,q)+1 pa qb
• No final, M valores em A(i,j) corresponde a uma reta com M pontos e parâmetros
ji ba , isto é, ji bxay
Obs.: Este método define nk computações, para k incrementos de a e b no planoab, e n pontos da imagem.
Exemplo
x
y
(1,2)
(2,1)
-3
-2
-1012
345
-2 -1 0 1 2
a
b
y = -x + 3
kk yaxb )2,1(),( kk yx
a = -1 b = 3
a = 0 b = 2
a = 1 b = 1
a = 2 b = 0
a = -2 b = 4
11
11
1
)1,2(),( kk yx
a = -2 b = 5
1
a = -1 b = 3
2
a = 0 b = 1
1
a = 1 b = -1
1
a = 2 b = -3
1
espaço de parâmetros
3
Problema:Os valores de a e b tendem para infinito à medida que as retas se tornam verticais.
Alternativa: Considerar a representação normal da reta (em coordenadas polares):
ysenx cos
é a distância perpendicular da reta à origem do plano xy e é o
ângulo desta reta perpendicular, em relação ao eixo x.o90 o90
As curvas obtidas no espaço são senoidais ao invés de retas
o45
Original Contornos
Exemplo 1
Contornos Detecção de linhas
Exemplo 2
Original Contornos
ContornosDetecção de linhas
Generalização
• A transformada de Hough pode ser aplicada a qualquer função da forma g(v,c) = 0,em que v é um vetor de coordenadas e c, o de coeficientes.
Por exemplo, a função 2
32
22
1 )()( ccycx
pode ser considerada para a determinação de círculos na imagem centrados em
),( 21 cc e de raio Neste caso, o espaço de parâmetros define.3c ),,( 321 ccc
o plano tridimensional .321 ccc
• O processo de detecção é o mesmo definido anteriormente: a partir dos pontosx, y, considera-se, por exemplo, os valores de e para se encontrar 1c 2c 3cno plano 321 ccc devidamente subdividido.
Redução da complexidade computacional
• Introduzir a informação do gradiente dos contornos
Algoritmo:
1. A(a,b) = 0
2. calcular ∆x e ∆y (usando o operador Sobel, por exemplo)
3. Se magnitude do gradiente no ponto (x,y) > Limiar, calcular
4. Calcular b = -ax+y
5. Incrementar acumulador: A(a,b)=A(a,b)+1
6. Repetir passos 3-5 para todos os pontos do contorno
7. Pontos de máximo (picos) em A(a,b) representam retas de parâmetro a,b
x
ya
Detecção de bordas em grafos
• Abordagem global de detecção de pontos de borda
• Representa os segmentos de borda em forma de grafos, e realiza buscasde caminhos de custo mínimo associados a contornos significativos.
Um grafo: G = (N,A)
N = conjunto finito, não-vazio de nósA = diferentes pares de N denominados arcos ou arestas),( ji nn
Num grafo orientado, é dito sucessor do nó pai jn inA expansão de um nó identifica os seus eventuais sucessores
Um custo pode ser associado a cada arco do grafo G. ),( ji nnc ),( ji nn
A sequência de nós , com cada sendo um sucessor de , knnn ,...,, 21 in 1iné denominada caminho de a in kn
O custo de um caminho pode ser dado por:
k
iii cncc
21 ),(
elemento de borda
Borda = sequência conexa de elementos de borda
Custo de cada elemento de borda:
(7) imagem da cinza de nível máximo o é H ,)]()([),( qfpfHqpc
Exemplo
p q
convenções do trajeto:
início da borda linha 1final da borda linha 3
O grafo
as bordas
os custos
1
2
3
1 2 3caminho de custo mínimo