Upload
jennifer-rollins
View
34
Download
0
Embed Size (px)
DESCRIPTION
Extração de Características. cap 4 – Trucco e Verri. Características de uma imagem. Globais : histograma, conteúdo de freqüências, etc... Locais : regiões com determinada propriedade, arestas, cantos, curvas, etc. Arestas e cantos. Locais de mudanças significativas na intensidade da imagem. - PowerPoint PPT Presentation
Citation preview
Extração de Características
cap 4 – Trucco e Verri
Características de uma imagem
• Globais: histograma, conteúdo de freqüências, etc...
• Locais: regiões com determinada propriedade, arestas, cantos, curvas, etc...
Arestas e cantos
• Locais de mudanças significativas na intensidade da imagem
Edgedels = edge elements
Tipos de arestasdegrau(step) rampa(ramp)
cume(roof) impulso(spike)
Gráfico sem e com ruído
Derivadas e arestas
f(x) f(x)+n(x) | f'(x)+n'(x) | f"(x)+n"(x)
Série de Taylor
)()(2
)()()()()( 3"2
' xOxfxxfxxfxxf
iiii ffff "'1 2
1
Com x=1, f(x)=fi e f(x+x)=fi+1
Com x=-1, f(x)=fi e f(x+x)=fi-1
iiii ffff "'1 2
1
(a)
(b)
Aproximações para derivadas
(a-b) 2/)( 11'
iii fff
(a+b) )2( 11"
iiii ffff
f(x)
x
fi-1fi fi+1
i+1ii-1
Em 2D
y
fx
fyxf ),(
Gradiente
Laplaciano
2
2
2
22 ),(
yf
xfyxf
x
yxfyxfx
yxf mnmn
,,, 1
x
yxfyxfy
yxf mnmn
,,, 1
11
11
Convolution Kernels
1414204141
Laplaciano
)2( 11"
iiii ffff
•Sometimes we are interested only in changing magnitude without regard to the changing orientation.
•A linear differential operator called the Laplacian may be used.
•The Laplacian has the same properties in all directions and is therefore invariant to rotation in the image.
http://www.cee.hw.ac.uk/hipr/html/log.html
http://ct.radiology.uiowa.edu/~jiangm/courses/dip/html/node83.html
Finite differences
11* II x
1
1*II y
IKhurram Hassan-Shafique
Classical Operators
Prewitt’s Operator
111111
11
11
Smooth Differentiate
101101101
111000111
111111
Khurram Hassan-Shafique
Classical Operators
Sobel’s Operator
112211
11
11
SmoothDifferentiate
101202101
121000121
121121
Khurram Hassan-Shafique
• Sobel Edge Detector
Detecting Edges in Image
Image I
101202101
121000121
*
*
Idxd
Idyd
22
I
dydI
dxd
ThresholdEdges
Khurram Hassan-Shafique
Sobel Edge Detector
Idxd
Idyd
I
Khurram Hassan-Shafique
Sobel Edge Detector
I
22
I
dydI
dxd
100 ThresholdKhurram Hassan-Shafique
Marr and Hildreth Edge Operator
• Smooth by Gaussian
• Use Laplacian to find derivatives
IGS * 2
22
2
21
yx
eG
Sy
Sx
S 2
2
2
22
Khurram Hassan-Shafique
Marr and Hildreth Edge Operator
IGIGS ** 222
2
22
22
22
32 2
21
yx
eyxG
Khurram Hassan-Shafique
Marr and Hildreth Edge Operator
2
22
22
22
32 2
21
yx
eyxG
0.0008 0.0066 0.0215 0.031 0.0215 0.0066 0.00080.0066 0.0438 0.0982 0.108 0.0982 0.0438 0.00660.0215 0.0982 0 -0.242 0 0.0982 0.0215
0.031 0.108 -0.242 -0.7979 -0.242 0.108 0.0310.0215 0.0982 0 -0.242 0 0.0982 0.02150.0066 0.0438 0.0982 0.108 0.0982 0.0438 0.00660.0008 0.0066 0.0215 0.031 0.0215 0.0066 0.0008
X
Y
Khurram Hassan-Shafique
Marr and Hildreth Edge Operator
Zero CrossingsDetection
I ImageG2*
IG *2 Edge Image
IG *2 Zero Crossings
Khurram Hassan-Shafique
1
6
3
Khurram Hassan-Shafique
Quality of an Edge Detector
• Robustness to Noise• Localization• Too Many/Too less Responses
Poor robustness to noise Poor localization Too many responses
True Edge
Khurram Hassan-Shafique
Canny Edge Detector• Criterion 1: Good Detection: The optimal
detector must minimize the probability of false positives as well as false negatives.
• Criterion 2: Good Localization: The edges detected must be as close as possible to the true edges.
• Single Response Constraint: The detector must return one point only for each edge point.
Khurram Hassan-Shafique
Hai Tao
The result– General form of the filter (N.B. the filter is odd so h(x) = -h(-x) the
following expression is for x < 0 only)
h x e a x a x e a x a xx x( ) ( sin cos ) ( sin cos ) / 1 2 3 4 1 2
2 052202 91540156939
.
..
aaaa
1
2
3
4
1
014867687170 208755347612446539390 79124465312
....
Camillo J. Taylor
Approximation– Canny’s filter can be approximated by the derivative of a Gaussian
h x ddx
e x ex x
( ) ( )
2
2
2
222
2
Camillo J. Taylor
Derivative of GaussianCanny
Canny Edge Detector
• Convolution with derivative of Gaussian• Non-maximum Suppression• Hysteresis Thresholding
Khurram Hassan-Shafique
Algorithm Canny_Enhancer• Smooth by Gaussian
IGS * 2
22
2
21
yx
eG
Tyx
T
SSSy
Sx
S
22yx SSS
x
y
SS1tan
Khurram Hassan-Shafique
• Compute x and y derivatives
• Compute gradient magnitude and orientation
Canny Edge Operator
IGIGS ** T
yG
xGG
T
Iy
GIx
GS
**
Khurram Hassan-Shafique
Canny Edge Detector
xS
yS
I
Khurram Hassan-Shafique
Canny Edge Detector
I
22yx SSS
25 ThresholdSKhurram Hassan-Shafique
We wish to mark points along the curve where the magnitude is biggest.We can do this by looking for a maximum along a slice normal to the curve(non-maximum suppression). These points should form a curve. There arethen two algorithmic issues: at which point is the maximum, and where is thenext one?
Algorithm Non-Maximum Suppression
Khurram Hassan-Shafique
Non-Maximum Suppression
• Suppress the pixels in ‘Gradient Magnitude Image’ which are not local maximum
edgean tonormaldirection thealong
in of neighbors theare and Sx,yy,xy,x
otherwise0,,&
,, if,, yxSyxS
yxSyxSyxSyxM
yx ,
yx,
yx ,
Khurram Hassan-Shafique
Non-Maximum Suppression
0
12
3
41420tan41422- :3
41422tan :241422tan41420 :1
41420tan41420 :0
.θ.
.θ.θ.
.θ.-
x
y
SS
θ tan
Khurram Hassan-Shafique
Non-Maximum Suppression
22yx SSS M
25ThresholdM
Khurram Hassan-Shafique
Hysteresis Thresholding
Khurram Hassan-Shafique
Hysteresis Thresholding
• If the gradient at a pixel is above ‘High’, declare it an ‘edge pixel’
• If the gradient at a pixel is below ‘Low’, declare it a ‘non-edge-pixel’
• If the gradient at a pixel is between ‘Low’ and ‘High’ then declare it an ‘edge pixel’ if and only if it is connected to an ‘edge pixel’ directly or via pixels between ‘Low’ and ‘ High’
Khurram Hassan-Shafique
Hysteresis Thresholding
M 25ThresholdM
15 35
LowHigh
Khurram Hassan-Shafique
Resultado de algoritmo de histerese
Subpixel Localization– One can try to further localize the position of the edge within a pixel by
analyzing the response to the edge enhancement filter– One common approach is to fit a quadratic polynomial to the filter
response in the region of a maxima and compute the true maximum.
abx
yyya
yyb
cbaycbay
cycbxaxxy
2
);0())1()1((21
));1()1((21)1(
;)1(;)0(
)(
max
2
0 1-1
Derivadas direcionais
yn
yf
xn
xf
nf
x
y
f(x,y)
y
x
nn
n
hpfnhpf
npf
h
)()(lim)(0
yx nyfn
xf
nf
nfnf
y
xyx n
nyf
xf
yfxf
nnnf
nf
nf
2
Detecting corners
– If Ex and Ey denote the gradients of the intensity image, E(x,y), in the x and y directions then the behavior of the gradients in a region around a point can be obtained by considering the following matrix
2
2
yyx
yxxyx
y
x
EEEEEE
EEEE
C
Camillo J. Taylor
Examining the matrix– One way to decide on the presence of a corner is to
look at the eigenvalues of the 2 by 2 matrix C.• If the area is a region of constant intensity we would expect
both eigenvalues to be small• If it contains a edge we expect one large eigenvalue and one
small one• If it contains edges at two or more orientations we expect 2
large eigenvalues
Camillo J. Taylor
Finding corners
– One approach to finding corners is to find locations where the smaller eigenvalue is greater than some threshold
– We could also imagine considering the ratio of the two eigenvalues
Computing Image Gradients
Corner Analysis– The ellipses indicate the eignvalues and eigenvectors
of the C matrices
Juiz Virtual
Tese de Flávio Szenberg
Modelos
F1
F6 F2
F3
F4 F5 F7
F8 F9
F1
F6 F2
F3
F4
F5
F8
F7
F9
Os modelos utilizados na tese:
Modelo de um campo de futebol
Modelo sem simetria
Filtragem para realce de linhas O filtro Laplaciano da Gaussiana (LoG) é aplicado à
imagem, baseado na luminância.
010141
010
121242121
161
filtro gaussiano
filtro laplaciano
Filtragem para realce de linhas Problemas com linhas duplas
Filtragem para realce de linhas A transformação negativa é aplicada entre o cálculo da
luminância e o filtro LoG.
Filtragem para realce de linhas Resultado de uma segmentação (threshold) feita na
imagem filtrada.
(em negativo para visualizar melhor)
Extração de segmentos de retas longos
O objetivo é localizar segmentos de retas longos candidatos a serem linhas da imagem do modelo.
O procedimento é dividido em dois passos:1. Eliminação de pontos que não estão sobre
nenhum segmento de reta. 2. Determinação de segmentos de retas.
Eliminando pontos que não estão sobre um segmento de reta
A imagem é dividida, por uma grade regular, em células retangulares.
Eliminando pontos que não estão sobre um segmento de reta
Para cada célula, os autovalores 1 e 2 (1 2) da matriz de covariância, dada abaixo, são calculados.
Se 2 = 0 ou 1/ 2 > M (dado) então
o autovetor de 1 é a direção predominante
senãoa célula não tem uma direção predominante
n
ii
n
iii
n
iii
n
ii
vvvvuu
vvuuuu
n1
2
1
11
2
1
1
2
vu ,
Eliminando pontos que não estão sobre um segmento de reta
Podemos atribuir pesos i aos pontos (resultado do LoG).
n
ii
n
iii
n
iii
n
ii
vvvvuu
vvuuuu
n1
2
1
11
2
1
n
iii
n
iiii
n
iiii
n
iii
n
ii vvvvuu
vvuuuu
1
2
1
11
2
1
1
Eliminando pontos que não estão sobre um segmento de reta
Células com pontos formando segmentos de retas:
Determinando segmentos de reta
As células são percorridas de modo que as linhas são processadas de baixo para cima e as células em cada coluna são processadas da esquerda para direita. Um valor é dado para cada célula: Se não existe uma direção predominate na célula, o valor é zero. Caso contrário, verifica-se os três vizinhos abaixo e o vizinho à
esquerda da célula corrente. Se algum deles tem uma direção predominante similar ao da célula corrente, quando unidos, então a célula corrente recebe o valor da célula que tem a direção mais similar; senão, um novo valor é usado para a célula corrente.
Determinando segmentos de reta São formados grupos com células de mesmo valor,
representados na figura abaixo por cores distintas.
Extração de segmentos de retaCada grupo fornece um segmento de reta.
A reta de equação v=au+b é encontrada por método de mínimos quadrados:
O segmento é obtido limitando a reta pela caixa envoltória dos pontos usados.
n
iii
n
iiii
n
ii
n
iii
n
iii
n
iii
v
vu
u
uu
ba
1
1
1
11
11
2
v
u
Extração de segmentos de retaOs segmentos de reta que estão sobre a mesma reta suporte são unidos, formando segmentos longos, usando mínimos quadrados.
No final do processo, tem-se um conjunto de segmentos de reta.
a
b
c
d
e
f
f1
f2f3
f4
f5f6
f7
Extração de segmentos de retaSobrepondo as linhas extraída na imagem, temos o seguinte resultado:
Reconhecimento dos segmentos
A partir do conjunto de segmentos, as linhas do modelo são detectadas e o modelo reconhecido [Grimson90].
Método baseado na Transformada de Hough.
Método de reconhecimento baseado em modelo.• Conjunto de restrições
Reconhecimento dos segmentos
F1 F7 F6F5F4F3F2f1:
f2:
F1
F6F2
F3
F4
F5 F7
Modelo
F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2
Árvore de Interpretaçãof1
f2f3
f4
f5f6
f7
Visualização
Método de Reconhecimento baseado em Modelo
O nó {f1: F1, f2:F6 , f3:F3} é discardado por que viola a restrição:
A linha representante de F6 deve estar entres as linhas que representam F1 e F3, na visualização.
F1 F7 F6F5F4F3F2
F1 F7 F6F5F4F3F2f1:
f2:
Árvore de Interpretação
F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2
f3:
Reconhecimento dos segmentosDiscardando nós
F1
F6F2
F3
F4
F5 F7
Modelo
f1
f2
f3
f4
f5
Visualização
f6
f7
Reconhecimento dos segmentosProblema relacionado com a perspectiva
2
1222
122
1222
12
12122
1212
)()()()(
))(())((
vvuuvvuu
vvvvuuuu
ttttssss
ttssttss
8.0121
Reconhecimento dos segmentosProblema relacionado com a perspectiva
f1
f2
f3
Reconhecimento dos segmentosEscolhendo a melhor solução
F1
F6F2
F3
F4
F5 F7
Modelo
• Em geral, existem diversas interpretações possíveis;
• Escolhemos a interpretação onde a soma dos comprimentos dos segmentos representativos é máxima.
f1 : F4 f2 : F3 f3 : f4 : f5 : F6 f6 : F7 f7 : F1 Vencedor
f1
f2f3
f4
f5f6
f7
Visualização
f1 : F4 f2 : f3 : f4 : F3 f5 : F6 f6 : F7 f7 : F1
f1 : F2 f2 : F3 f3 : f4 : f5 : F6 f6 : F5 f7 : F1
f1 : F4 f2 : F3 f3 : f4 : f5 : F6 f6 : F7 f7 : F1
f1
f2f3
f4
f5
f6
f7
Visualização
Reconhecimento dos segmentos
F1
F6F2
F3
F4
F5 F7
ModeloResultado final
F7F1
F6F2
F3
F4
F5
Modelo
ou
Cálculo da transformação projetiva planar Uma transformação projetiva planar H (homografia) correspondente
às linhas reconhecidas é encontrada (usando pontos de interseção e pontos de fuga como pontos de referência).
Modelo reconstruído
H
pontos de interseção
pontos de fuga