les contours

Informatique visuelle - vision par ordinateur
Extractions de caract´eristiques - les contours
Elise Arnaud
[email protected]
cours inspir´
e par X. Descombes, J. Ros, A. Boucher, A. Manzanera, E. Boyer, M Black, J.H. Thomas
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours
´etape pr´eliminaire `a de nombreuses applications de l’analyse
d’images
les contours constituent des indices riches, au mˆeme titre que
les points d’int´erˆets, pour toute interpr´etation ult´erieure de
l’image
Les contours dans une image proviennent des :
�
�
discontinuit´es de la fonction de r´eflectance
discontinuit´es de profondeur
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours
Les contours sont caract´eris´es par des discontinuit´es de la
fonction d’intensit´e
Exemple de diﬀ´erents types de contours : rampe, toit et
pointe :
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours
m´ethode en deux ´etapes :
�
la premi`ere permet de localiser les contours `a partir d’un
calcul de Gradient ou de Laplacien dans des directions
privil´egi´ees tout en quantifiant l’importance du contour.
�
La seconde ´etape va permettre d’isoler les contours du reste
de l’image `a partir d’un seuillage judicieux.
Elise Arnaud [email protected]
M2P UFR IMA
Rappel d´eriv´ees
Elise Arnaud [email protected]
M2P UFR IMA
Rappel d´eriv´ees
c
�Jean-Hugh
THOMAS
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours
⇒ ´etude des d´eriv´ees de la fonction d’intensit´e dans l’image
la fonction d’intensit´e au voisinage d’un contour en rampe et
ses d´eriv´ees premi`ere (gradient) et seconde (laplacien).
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours
⇒ ´etude des d´eriv´ees de la fonction d’intensit´e dans l’image
�
les extr´ema locaux du gradient de la fonction d’intensit´e
�
les passages par z´ero du laplacien
�
diﬃcult´e : la pr´esence de bruit dans les images
Elise Arnaud [email protected]
M2P UFR IMA
´
Gradient de l’image - Etude
du signal en 1D
Elise Arnaud [email protected]
M2P UFR IMA
´
Gradient de l’image - Etude
du signal en 1D
Elise Arnaud [email protected]
M2P UFR IMA
´
Gradient de l’image - Etude
du signal en 1D
Le signal de Barbara et sa d´eriv´ee premi`ere
Elise Arnaud [email protected]
M2P UFR IMA
´
Gradient de l’image - Etude
du signal en 1D
Le signal de Barbara et sa d´eriv´ee premi`ere : amplitude des
perturbations
signal liss´e
Elise Arnaud [email protected]
d´eriv´e premi`ere
M2P UFR IMA
D´eriv´ee premi`ere de l’image
Rappel : l’image est une fonction
I:
S → Ω
(x, y) → I(x, y)
gradient de l’image : vecteur qui repr´esente la variation de la
fonction d´ependant de plusieurs param`etres par rapport `a la
variation de ces diﬀ´erents param`etres.
�
�
∂I(x, y) ∂I(x, y) t
∇I =
,
∂x
∂y
Elise Arnaud [email protected]
M2P UFR IMA
Gradient de l’image
∇I =
�
∂I(x, y) ∂I(x, y)
,
∂x
∂y
Elise Arnaud [email protected]
M2P UFR IMA
�t
Gradient de l’image
- le gradient est un
vecteur perpendiculaire
au contour - l’amplitude
du gradient mesure la
force du contour
Le gradient est caract´eris´e par un module m et une direction φ
dans l’image :
m=
�
∂I(x, y) 2 ∂I(x, y) 2
+
∂x
∂y
φ = arctan
�
�1/2
∂I(x, y) ∂I(x, y)
/
∂y
∂x
Elise Arnaud [email protected]
M2P UFR IMA
�
Gradient de l’image
Elise Arnaud [email protected]
M2P UFR IMA
Gradient de l’image
La qualit´e du gradient se d´egrade avec l’accroissement du bruit :
Le gradient d’une image filtr´ee :
∇I � (x, y) = ∇(I(x, y)∗h(x, y)) = ∇I(x, y)∗h(x, y) = I(x, y)∗∇h(x, y).
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours - Approche gradient
Approche 1 : par seuillage du gradient
les points de contour dans une image sont caract´eris´es par des
extr´ema locaux du gradient. Une premi`ere approche consiste donc
`a :
1. calculer la norme du gradient en tous point de l’image,
2. s´electionner les pixels `a l’aide d’un seuil fix´e a priori pour la
norme du gradient.
pbl : ne permet pas de diﬀ´erencier eﬃcacement les points de
contour du bruit.
Elise Arnaud [email protected]
M2P UFR IMA
Gradient de l’image - impl´ementation
D´erivation par diﬀ´erence finies
Une image est discr`ete par nature. Les premi`eres approches ont
donc consist´e `a approximer les d´eriv´ees par diﬀ´erence :
∇x I(x, y) = I(x, y) − I(x − n, v)
ou :
∇x I(x, y) = I(x + n, y) − I(x − n, y)
avec, en g´en´eral n = 1.
Ces d´eriv´ees sont calcul´ees par convolution de l’image avec un
masque de diﬀ´erences.
Elise Arnaud [email protected]
M2P UFR IMA
Gradient de l’image - impl´ementation
c
�Jean-Hugh
THOMAS
Elise Arnaud [email protected]
M2P UFR IMA
Gradient de l’image - impl´ementation
Proposez un masque pour d´etecter les contours diagonaux
(op´erateurs de Roberts (1962))
Elise Arnaud [email protected]
M2P UFR IMA
Gradient de l’image - impl´ementation
D´erivation par diﬀ´erence finies - Op´erateurs de Prewitt et de Sobel


−1 0 1
h1 = 1/(c+2)  −c 0 c 
−1 0 1


−1 −c −1
0
0 
h2 = 1/(c+2)  0
1
c
1
�
c=1 : op´erateur de Prewitt
�
c=2, op´erateur de Sobel.
�
ces masques eﬀectuent un lissage dans la direction
orthogonale. Ce lissage rend ces masques un peu moins
sensibles au bruit que les pr´ec´edents.
Elise Arnaud [email protected]
M2P UFR IMA
Rappel filtres s´eparables
�
Une r´eponse impulsionnelle h est s´eparable selon x et y ssi :
h(x, y) = hx (x).hy (y)
�
Ce qui se traduit pour le filtrage d’une image par :
I � (x, y) = h(x, y) ∗ I(x, y) = hy (y) ∗ (hx (x) ∗ I(x, y))
�
Avantages d’un filtre s´eparable
�
�
�
Le filtrage d’un signal 2D est ramen´e au filtrage d’un signal 1D
r´eduction du temps de calcul : pour une convolution par un
masque de filtrage de dimension H, la complexit´e est de 2H
au lieu de H 2
Possibilit´e d’impl´ementer r´ecursivement le filtrage
Elise Arnaud [email protected]
M2P UFR IMA
Gradient de l’image - impl´ementation
Op´erateurs de Prewitt et de Sobel s´eparables


 
−1 0 1
1 �
�



h1 = 1/(c + 2) −c 0 c = 1/(c + 2) c  −1 0 1
−1 0 1
1




−1 −c −1
−1 �
�
0
0  = 1/(c + 2)  0  1 c 1
h2 = 1/(c + 2)  0
1
c
1
1
filtres isotropes ou anisotropes ?
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours - Approche gradient
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours - Approche gradient
Approche 1 : par seuillage du gradient
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours - Approche gradient
Approche 1 : par seuillage du gradient
possibilit´e de calculer le seuil en tenant compte de l’histogramme
du module du gradient
c
�Jean-Hugh
THOMAS
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours - Approche gradient
Approche 2 : par recherche de maxima et seuillage par hyst´er´esis
(1) Extraction des extr´ema locaux du gradient dans la direction
du gradient. Cela revient `a d´eterminer, pour un pixel p donn´e,
les valeurs du gradient sur la droite passant p et de direction
celle de son gradient. On v´erifie ensuite que le gradient en p
est bien localement maximal sur cette droite.
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours - Approche gradient
Approche 2 : par recherche de maxima et seuillage par hyst´er´esis
(2) Seuillage par hyst´er´esis des extr´ema. Cette ´etape repose sur
une hypoth`ese de connexit´e. Le principe est d’utiliser deux
seuils pour la norme du gradient : sb et sh et de s´electionner
les pixels pour lesquels :
1. la norme du gradient est sup´erieure `a sh ,
2. le pixel donn´e est connect´e, par un chemin constitu´e de pixels
dont la norme du gradient est sup´erieure `a sb , `a un pixel pour
lequel la norme du gradient est sup´erieure `a sh .
�
remarque : en g´en´eral, on prend sh /sb = 2
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours - Approche gradient
Approche 2 : par recherche de maxima et seuillage par hyst´er´esis
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours - Approche laplacien
Les points de contour sont caract´eris´es par des passages par z´ero
du laplacien. La d´etection de ces points s’eﬀectue en deux ´etapes :
1. D´etection des passages par z´eros. Les pixels pour lesquels le
laplacien change de signe sont s´electionn´es.
2. Seuillage des passages par z´eros de fortes amplitudes.
Elise Arnaud [email protected]
M2P UFR IMA
D´eriv´ees secondes de l’image : Laplacien
d´eriv´ees secondes
�
∂2I
∂x2
∂2I
∂y∂x
∂2I
∂x∂y
∂2I
∂y 2
�
laplacien de l’image : somme des d´eriv´ees secondes non mixtes
�I = ∇2 I =
Elise Arnaud [email protected]
∂2I
∂2I
+
∂x2 ∂y 2
M2P UFR IMA
D´eriv´ees secondes de l’image : Laplacien
L’estimation du laplacien d’une image se fait de la mˆeme mani`ere
par convolution de l’image avec un masque. Le laplacien est
approch´e par diﬀ´erences finies :

 
 

0 0 0
0 1 0
0 1 0
 1 −2 1  +  0 −2 0  =  1 −4 1 
0 0 0
0 1 0
0 1 0
ou :


1 1 1
 1 −8 1 
1 1 1
Elise Arnaud [email protected]
M2P UFR IMA
D´eriv´ees secondes de l’image : Laplacien
Elise Arnaud [email protected]
M2P UFR IMA
D´eriv´ees secondes de l’image : Laplacien
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours - Approche laplacien
Si � > 0 et l’un des autres �i ≤ 0 ou � < 0 et l’un des autres
�i ≥ 0 alors on consid`ere qu’il ya changement de signe.
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours - Approche laplacien
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de contours
�
d´etecteur de contours de Canny
�
d´etecteur de contours de Deriche
Elise Arnaud [email protected]
M2P UFR IMA
Informatique visuelle - Vision par ordinateur
Extractions de caract´eristiques - les points
d’int´erˆet
Elise Arnaud
[email protected]
cours inspir´
e par X. Descombes, J. Ros, A. Boucher, A. Manzanera, E. Boyer, M Black, J.H. Thomas
Elise Arnaud [email protected]
M2P UFR IMA
une partie de ce cours est tir´ee de ...
Elise Arnaud [email protected]
M2P UFR IMA
"#$%&$'()*+%*&,-,&$#-'.$'/0%.
!
!"#*1*'+%)$'2'%-*+%.*&,-,&$#-'.$'/0%.*-(30.$%.*+,).*45'6,7%*8(0-*6'.%*%)*
&(--%.8()+,)&%*9:";<*-%&()),'..,)&%<*.0'='*96(0=%6%)$;<*>
!
?)*&@%-&@%*.(0=%)$*A*$%&#'()*+),'-.'/#+#&0/*9.(0-&%*+5%--%0-.;*%)*
'+%)$'2',)$*+5,0$-%.*&,-,&$#-'.$'/0%.
!"#$%&'(')*+',*--.&/',"0&('1&2-#$&3/'4567
!
"#$%#&$%#'()*+,-#.'.*+*/,*&#.
"#0&123#&'(#.'*+,-#.'
$140#4,40'24'-&,55*0*
!"#$%&'(')*+',&-./'012&%3'4&3&%3-"+'*+.',&%"5+-3-"+/'067"$.'89:;<
!
"#$%&%'&()**%$+)',-'(%&,.#/-0%$
1%$&$(2'%$&$)'3&,#445*%'3%$&6-'07%&,%&89%:&;))/:&79/#2*%:&<=:&/-#$&)'&
8%93&#,%'3#4#%*&,%$&575/%'3$&$%/>7->7%$<
!"#$%&'(')*+',&-./'012&%3'4&3&%3-"+'*+.',&%"5+-3-"+/'067"$.'89:;<
!
"#$%#&$%#'()*+,#-.'(/0.'1#.'23/4#.
5$26'$)#.-'1#'373#'/8-*+8.'3/14&9'1/'-/211#'(2::9&#0-#'#-'1#':/2-';8)21'
.*2-'#0'</&-2#'$/$%9#'.8&'80#'23/4#=
!"#$%&'(')*+',&-./'012&%3'4&3&%3-"+'*+.',&%"5+-3-"+/'067"$.'89:;<
!
"#$%#&'(')*&+',-.)*+.)*/,#,/('#&)(&01.)
!
!
!
!
!
!
!
!"#$%&'(*2*13.*/,#,/('#&)(&01.*-$/,-.*45)*6-$7,-.8*).#,*%-1)*
#$71)(.*,19*$//-1)&$3)
)*+$,&$*#-*2*:*-,*(#,3)-,(&$3;*-,*#$(,(&$3;*-.*/<,36.=.3(*
+>'/<.--.;*???
."/01'-*2*,1*7#1&(;*,19*/$3+&(&$3)*+>,/01&)&(&$3*+.*->&=,6.;*
:*-,*/$=%#.))&$3;*???
2&1#,&3&*$*'-*2*%.#=.(*+>&+.3(&@&.#*01.-01.)*$7A.()*
)%'/&@&01.)*%,#=&*7.,1/$1%*+>,1(#.)
40$*'&'(*2*%$15$&#*6'3'#.#*7.,1/$1%*+.*/,#,/('#&)(&01.)*
%,#*$7A.(*B*%$#(&$3*+>&=,6.)
5,(#&1&"**2*%$)&(&$3*%#'/&).*+,3)*->&=,6.*B*->$7A.(
677&#$#&'(*2*/,-/1-*#,%&+.*4(.=%)*#'.-8
!"#$%&'(')*++&')#,-&.//$01'2"%/.'3+4/$*/+-'5&/-#$&0('67/-8'67,8'67&+8'9":81';<<='>??@A
!
"#$%#&'('!)*&+,-#&-+./
!
!
0+,-#&-+./!1!2-!3'$4'(#&/
!
!"#$#%"&
!
'($&)*+*&#,-./0(*11*
!
23$&45"3+$#%"&,$55%&*!
0+,-#&-+./!1!2-!%5$($4/(#&/
!
'($&)*+*&#,$55%&*,-.%&#*&4%#/!60!!!-!0!7!89
!
!
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
"#$%&'(#)$*+(%&!,-()-*#+./0&
!
!
!"#$%&'(')*++&')#,-&.//$01'2"%/.'3+4/$*/+-'5&/-#$&0('67/-8'67,8'67&+8'9":81';<<='>??@A
"#$%&'(#)$*+(%&!,-(*().*#+/01&
!
!
!"#$%&'(')*++&')#,-&.//$01'2"%/.'3+4/$*/+-'5&/-#$&0('67/-8'67,8'67&+8'9":81';<<='>??@A
"#$#%&'()(%#!*+,!-.//+,$.0*&0-+,
1/(%2/+!*3#4&)5&%(.0!6!-.//+,$.0*&0-+,!+0%/+!(7&8+,
! )*++,-#*./%.),!"#"$%&'('$"!
""## $
! /"$,)$"-
!
!
0*1+),2324'..,2415$,(%%+-627*)%(28.9%+'%.$2:,%$1+,-32;<%$=2;<5=2;<,.=2>*?=62@AAB2CDDEF
2/*03&*!4!31)5+101
"#$!%&'()*+!&*,!-*./!'01(*,
!
!
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
67(4.3(!8!./,+0/4/
"#$!%&'()'*+,!%(-!.+*,'-!)/0/)'&0*-'*12(-!%/,-!3(-!#!*4/5(-
!
!
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
"#$%&'$!(!&)*+,)%)
-./!0,+12$,!3$4!&)5,$4!3$!&+5*04!6+,,$4&+*3)*04
!
!
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
"#$%&'$!(!&)*+,)%)
-./!011$%2'$,!'$1!3$4#!5%)6$1!&+4,!$*!7+,%$,!4*$!1$4'$
!
!
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
;9)(6&)!1!68/$#8(8
! "#$%&'()!*!#+,$-.#)!/$!0!1
" 2+3)43)#!&)!(5()!6$7/3!.8/,!&),!.)-9!7(8:),
!"#$%&'(##%)*+
#$%$&'()*)&$+,-.+%/)0&.
!
!
,(-.!+$/$0.(*(1"$2$,%&"3(14$561".%"67$0+"7-.+$8+7+!7(.#$"69$8+#!.%'7(.#4$:+%;&"66$56#<$=5#."+*><
;<)(6&)!1!64/$#4(4
! "#$%&'()!*!#+,$-.#)!/$!0!1
" "$-#!2345-)!6$7/89!8#$-:)#!&4!%$//)!2$##),6$/.4/2)
!
#$%&'()*$+','-.+%*$,$*,/(%&'(0(121*
!
!
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
Plan
�
d´etection de points d’int´erˆet
�
mise en correspondance de points
Elise Arnaud [email protected]
M2P UFR IMA
Qu’est ce qu’un point d’int´erˆet ?
- contour : discontinuit´e dans une direction de la fonction d’intensit´e ou de ses
d´eriv´ees - point d’int´erˆet : dans deux directions
Elise Arnaud [email protected]
M2P UFR IMA
Qu’est ce qu’un point d’int´erˆet ?
Avantages des points d’int´erˆet :
�
Sources d’informations plus fiable que les contours car plus de
contraintes sur la fonction d’intensit´e.
�
Robuste aux occultations (soit occult´e compl`etement, soit
visible).
�
Plus facile `a extraire que les contours
�
Pr´esents dans une grande majorit´e d’images (�= contours !).
Elise Arnaud [email protected]
M2P UFR IMA
D´etection de points d’int´erˆet
Diﬀ´erentes approches
1. Approches contours : d´etecter les contours puis extraction des
points d’int´erˆets le long des contours en consid´erants les
points de courbures maximales ainsi que les intersections de
contours.
2. Approches intensit´e : `a partir des niveaux de gris de l’image,
trouver un op´erateur qui est maximal aux points d’int´erˆet
3. Approches `a base de mod`eles : identification des points
d’int´erˆets par mise en correspondance de la fonction
d’intensit´e avec un mod`ele th´eorique de cette fonction des
point d’int´erˆets consid´er´es.
→ Les approches de la deuxi`eme cat´egorie sont celles utilis´ees
g´en´eralement car (a) ind´ependance vis `a vis de la d´etection
de contours (b) ind´ependance vis `a vis du type de points
d’int´erˆets
Elise Arnaud [email protected]
M2P UFR IMA
D´etecteur de Moravec (1980)
Variation moyenne de l’intensit´e pour un petit d´eplacement (x, y)
�
E(x, y) =
w(u, v) |I(x + u, y + u) − I(u, v)|2
u,v
�
w sp´ecifie le voisinage consid´er´ee (valeur 1 `a l’int´erieur de la
fenˆetre et 0 `a l’ext´erieur);
�
I(u, v) est l’intensit´e au pixel (u, v)
Elise Arnaud [email protected]
M2P UFR IMA
D´etecteur de Moravec
A. intensit´e presque constante : E(x, y) ≈ 0
B. contour : E(x, y) ≈ 0 pour des d´eplacement le long du
contour (y �= 0) ; E(x, y) > 0 pour des d´eplacements
perpendiculaires
C. coin : E(x, y) > 0 pour tout (x, y) �= (0, 0)
D. pixel seul : idem coin
Elise Arnaud [email protected]
M2P UFR IMA
D´etecteur de Moravec
⇒ un coin est un maximum local de E
⇒ pbl : la valeur de E est la mˆeme pour un coin que pour un
pixel isol´e
1. pour chaque pixel (u, v), calculer les variations d’intensit´e
E(x, y) pour (x, y) =
{(1, 0), (1, 1), (0, 1), (−1, 1), (−1, 0), (−1, −1), (0, −1), (1, −1)}
2. Construire la carte de “coinit´e” en calculant la mesure C(u, v)
pour chaque pixel (u, v): C(u, v) = min E(x, y)
3. Trouver les maxima de cette carte (correspondent aux points
d’int´erˆet)
Elise Arnaud [email protected]
M2P UFR IMA
D´etecteur de Moravec
Elise Arnaud [email protected]
M2P UFR IMA
D´etecteur de Moravec
Elise Arnaud [email protected]
M2P UFR IMA
Du d´etecteur de Moravec au d´etecteur de Harris (1988)
On consid`ere le developpement de Taylor de la fonction
d’intensit´e I au voisinage du pixel (u, v) :
I(x + u, y + v) = I(u, v) + x
δI
δI
+ y + o(x2 , y 2 )
δx
δy
D’o :
E(x, y) =
�
u,v
�
�2
δI
δI
w(u, v) x + y + o(x2 , y 2 )
δx
δy
En n´egligeant le terme o(x2 , y 2 ) (valide pour les petits
d´eplacements) :
E(x, y) = Ax2 + 2Cxy + By 2 ,
avec:
�
�
2
2
δI
δI
A = δx
⊗ w ; B = δy
⊗w ;
w : fenˆetre gaussienne (+ isotrope)
Elise Arnaud [email protected]
M2P UFR IMA
δI δI
C = ( δx
δy ) ⊗ w
D´etecteur de Harris
E(x, y) = (x, y) · M · (x, y)t ,
avec :
M=
avec:
A=
δI 2
⊗w
δx
;
B=
�
A C
C B
δI 2
⊗w
δy
�
;
C=(
δI δI
)⊗w
δx δy
M : sym´etrique, d´efinie positive ⇒ d´ecompostition en valeurs
propres
Elise Arnaud [email protected]
M2P UFR IMA
D´etecteur de Harris
les valeurs propres de M correspondent aux courbures principales
associ´ees `a E :
A. intensit´e presque constante : les deux courbures sont de
faibles valeurs
B. contour : une des courbures est de forte valeur, l’autre est de
faible valeur
C. point : les deux courbures sont de fortes valeurs
Elise Arnaud [email protected]
M2P UFR IMA
D´etecteur de Harris
valeurs propres de M : λ1 et λ2
Elise Arnaud [email protected]
M2P UFR IMA
D´etecteur de Harris
Plutˆot que de calculer les valeurs propres, il est possible de calculer
det(M ) = AB − C 2 = λ1 + λ2
trace(M ) = A + B = λ1 .λ2
et on calcule la r´eponse :
R = det(M ) − k trace2 (M )
Les valeurs de R sont positives au voisinage d’un coin, n´egatives
au voisinage d’un contour et faibles dans une r´egion d’intensit´e
constante (k = 0.04)
⇒ coins/point d’int´erˆet = max locaux de R
Elise Arnaud [email protected]
M2P UFR IMA
#$%&'%&()*+&*,-))./*0*123'%.233&4&3%
54-6&/*2).6.3-7&/
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
!"
#$%&'%&()*+&*,-))./*0*123'%.233&4&3%
5-6'(6*+(*+$%&'%&()*+&*,-))./
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
!"
#$%&'%&()*+&*,-))./*0*123'%.233&4&3%
5&(.66-7&*+&/*8.9&6/*:'2.3/;
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
!"
#$%&'%&()*+&*,-))./*0*123'%.233&4&3%
5-6.4-*72'-(6
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
!"
#$%&'%&()*+&*,-))./*0*123'%.233&4&3%
5(6&)62/.%.23*/()*7&/*.4-8&/*2).8.3-7&/
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
!"
#$%&'(%)*%)*+,%-,./0)*%)-/.01
!"#$%&'(')*+,$+-'./&,0&$+1"02'3+45+46'78,,&$4/'+4'9*86&/':;#468$<=>
!"
#$%&'%&()*+&*,-))./*0*(%.1.%$
23))&/435+-5'&*&5%)&*.6-7&/*841(/*13.5*+-5/*1&*'3()/9:
43()*1&*!#;*1&*63(<&6&5%;*1-*)&'=&)'=&*+>.6-7&/;*:
!"#$%&'(')*+',*--.&/'01!0'232'4+56&'789&$:-589*86'4('4+56&';85.<:*:/'7=0'>058595?
!"
+,()-().&!/)!0%&&'1!2!3&*3&',(,1
! "#$%&'%#(!)#!&*(%('*#
"#$%&'()*+&),-'-.,/0&1'&2,)$%&)%+-%&1'&$#$%0&%-&
1%+&3'1%4)+&(),()%+&5%&1'&$'-).6%&'4++.
!
!
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
"#$%&$%'(!)%!*+((,-!.!/(0/(,#$#!
1%!)#$%&$%'(!)%!*+((,-!23%-$!/+-!,24+(,+2$!5!63#&7%66%!
!
8%!902&$,022%!/+-!-,!&7+2:%;%2$!)3#&7%66%
!"#$%&'()*&&+&'
(",,-'("$%"./
0"#$'1
!
!
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
"-*+,&+-4$!2!#0345$##$
! "#!$%&'($!)$'!*+,&+-($'!.$,/$((+-(!)01(,$!
&-*+,&+-(!2!#0345$##$
! 6%$/.#$!7!8+,,&'9:+.#+4&$-
!
!
!"#$%&'(')$"*"+,'-'!./,0"+1'23+,$.,34')&,4#$&'5&4&%4"$6',37'5&6%$.84"$61'9&.:/,33'236;'<26$,&*=;
! "#$$%&'(#)*#+%,-
.
"#$%&'#!('!)*+,)%)!($-*(!
.$%#!/
! 0'1!-$,21!3'!4*##,1!
3*21!(5'1.*-'!6+789
! 0'!0*.(*-,'2!'2!:-;'(('
!#H+I*+-'98#"
4*##,1<0*.(*-,'2
F-39**9
"
!#G+??'=#"
!
$%&'()*+,-./(0#1%2-34'5%#67859:'8;#<+=95#)8#2-+*9#78>+?'+8@#78@9?9=@#A)'8@=B%#711C#DEE"
"#
!
!
#$%&'()*)+&$,$-.)/)#01.2$-3)45-.&0.56)+(.6%&()7(6('6$&8).59)7(8'&0:6$&83);(0<1.55)458=)>48&.(,?=
Mise en correspondance
�
Les m´ethodes de corr´elation sont utilis´ees depuis longtemps
pour mettre en correspondance des pixels sur la base
d’informations d’intensit´es.
�
L’id´ee est de d´efinir une mesure de similarit´e entre les pixels
de deux images.
�
Les pixels sont les primitives les mieux adapt´es pour la mise
en correspondance.
�
Les rgions sont en eﬀet mal adapt´ees la mise en
correspondance (la taille d’une r´egion est diﬀ´erente d’une
image une autre), tout comme les contours
Elise Arnaud [email protected]
M2P UFR IMA
Mise en correspondance - principe
Le principe est de consid´erer, pour un pixel p1 de l’image 1, une
fenˆetre rectangulaire centr´ee en p1 et de calculer sa
corr´elation/distance avec une fenˆetre dans la deuxi`eme image. La
fonction de corr´elation est alors maximum en p2 correspondant de
p1 dans la deuxi`eme image (distance minimum)
Elise Arnaud [email protected]
M2P UFR IMA
Mise en correspondance - fonctions de dissimilarit´e
Pour une fenˆetre de taille 2N + 1 × 2P + 1
�
Sum of absolute diﬀerences (SAD)
SAD(p1 (u1 , v1 ), p2 (u2 , v2 )) =
i=N
�
j=P
�
|I1 (u1 +i, v1 +j)−I2 (u2 +i, v2 +j)|
i=−N j=−P
�
Sum of squared diﬀerences (SSD)
SSD(p1 (u1 , v1 ), p2 (u2 , v2 )) =
i=N
�
j=P
�
(I1 (u1 +i, v1 +j)−I2 (u2 +i, v2 +j))2
i=−N j=−P
Elise Arnaud [email protected]
M2P UFR IMA
Mise en correspondance - fonctions de dissimilarit´e
Pour une fenˆetre de taille 2N + 1 × 2P + 1
�
Zero Mean Sum of squared diﬀerences (ZSSD)
ZSSD(p1 (u1 , v1 ), p2 (u2 , v2 ))
=
i=N
�
j=P
�
i=−N j=−P
[(I1 (u1 + i, v1 + j) − I1 (u1 , v1 ))
− (I2 (u2 + i, v2 + j) − I1 (u2 , v2 ))]2
Elise Arnaud [email protected]
M2P UFR IMA
Mise en correspondance - fonctions de similarit´e
Pour une fenˆetre de taille 2N + 1 × 2P + 1
�
Corr´elation Crois´ee (CC) (peut se d´eduire de la SSD)
CC(p1 (u1 , v1 ), p2 (u2 , v2 )) =
i=N
�
j=P
�
I1 (u1 +i, v1 +j).I2 (u2 +i, v2 +j)
i=−N j=−P
Elise Arnaud [email protected]
M2P UFR IMA
Mise en correspondance - fonctions de similarit´e
Pour une fenˆetre de taille 2N + 1 × 2P + 1
�
Zero-Mean normalized cross-correlation (ZNCC)
ZN CC(p1 (u1 , v1 ), p2 (u2 , v2 ))
=
1
σ1 .σ2
i=N
�
j=P
�
i=−N j=−P
(I1 (u1 + i, v1 + j) − I1 (u1 , v1 ))
.(I2 (u2 + i, v2 + j) − I1 (u2 , v2 ))
avec
�
�
�
σ1 = �
i=N
� j=P
�
1
(I1 (u1 + i, v1 + j) − I1 (u1 , v1 ))2
(2N + 1)(2P + 1)
i=−N j=−P
Elise Arnaud [email protected]
M2P UFR IMA
Mise en correspondance - limitations
repose sur des hypoth`eses fortes :
�
Les changements de points de vue n’alt`erent pas l’aspect des
surfaces
�
Pas d’occultations lors de la recherche d’un correspondant.
�
Une r´egion rectangulaire dans l’image 1 correspond `a une
r´egion rectangulaire dans l’image 2.
�
Deux r´egions de couleurs constantes pr´esentent une distance
normalis´ee (ZSAD, ZSSD) nulle. Une solution consiste `a
normaliser non pas la r´egion mais l’ensemble de l?image.
Elise Arnaud [email protected]
M2P UFR IMA
#$%&'()*+%&',-.'()/)0123
!
0123)405678)1&96-%6&')286':-8)3-6&(;$-<=)>?$@8A)BCCDE
!
!
N$:98778)6GG-$5F8)*8)G$%&'()*+%&',-.'()'-O()G$G:76%-8
!
!
!
!
!
F''G/HH@@@I5(I:J5I56HK7$@8HL8MG$%&'(H
%&96-%6&58)G6-),5F8778
%&96-%6&58)G6-)-$'6'%$&
%&96-%6&58)G6-)G$%&')*8)9:8A)
%&96-%6&58)6:P)5$&*%'%$&()*Q,576%-6R8
#$%&'()$-%8&',()/)9678:-()S)985'8:-
!"#$%&'(')*+,-'."/&0'),12,3%2,+&'45*6&'7&*2#$&1'8$"5'!%*9&'43+*$,*321':&;<",321'=>'4?@A>'BCDEF>'ECCG0 !"
#$%&
'()*+),-+./01-2+(,+
(34.-,4+),+-,5-/36-+
7-+8-94-)*5+08-9+
044*.3)45
!"
#$%$&'(%)*')+,-*./,.&$0&,0.1234
566%7&8-.9,0'):(&8-00-
#$0&,0.*-07;.60,*)-,%*./)%-&')7;*.-;.
'-;$;'.&796'-./,.<7)*);$=-
>7,%.0?$0=7%)'89-.&7960-'@.0)%-.0-*.$%')&0-*./)*67;)A0-*.*,%.
8''6BCCDDDE&*E,A&E&$CF07D-CG-H67);'*C
!"
#$%&$'%&$()*+,-$./()01/(21$(3405$
!"#$%&'(')*+,-'."/&0'),12,3%2,+&'45*6&'7&*2#$&1'8$"5'!%*9&'43+*$,*321':&;<",321'=>'4?@A>'BCDEF>'ECCG0 !"