5.3 D´ etecteurs d’´ el´ ements g´ eom´ etriques particuliers
103
Algorithme 2 D´ etecteur de coin de Harris (version discr` ete)
1. Calculer le gradient discret ∇I “ pI x , I y q dans toute l’image , par exemple avec les
formules 3.6 p. 58
2. Pour chaque pixel :
a. Calculer sur un voisinage V du pixel la matrice suivante :
¨
˚
˝
ÿ
V
I x I x
ÿ
V
I x I y
ÿ
V
I x I y
ÿ
V
I y I y
˛
‹
‚.
b. Calculer les valeurs propres λ 1 et λ 2 (avec λ 2 ď λ 1 )
c. Si la valeur propre minimale λ 2 ą seuil, conserver les coordonn´ ees du pixel dans une
liste L (ce sont les coins)
3. Trier L en ordre d´ ecroissant de λ 2
4. Balayer la liste L de haut en bas, pour chaque pixel p i et ´ eliminer les autres pixels qui
appartiennent au voisinage de p i .
La liste finale contient les points saillants pour lesquels λ 2 ą seuil et
dont les voisinages ne se chevauchent pas. Ce sont les pixels les plus faciles `
a
suivre !
5.3.2 Transformation de Hough
La transformation de Hough est utilis´ ee pour d´ etecter de mani` ere syst´ ematique la pr´ esence de relations structurelles sp´ ecifiques entre des pixels dans
une image. Par exemple une image repr´ esentant un site urbain est compos´ ee
de nombreuses lignes droites (immeubles, fenˆ etres) en revanche, une vue de
campagne en est quasiment d´ epourvue [41, 53].
Hough a propos´ e une m´ ethode de d´ etection bas´ ee sur une transformation
d’image permettant la reconnaissance de structures simples (droite, cercle)
liant des pixels entre eux. Pour limiter la charge de calcul, l’image originale
est pr´ ealablement limit´ ee aux contours des objets puis binaris´ ee (2 niveaux
possibles pour coder l’intensit´ e du pixel).
5.3.2.1 Principe de la m´ ethode pour la recherche de ligne droite
Supposons que l’on suspecte la pr´ esence d’une droite Δ reliant un certain
nombre de pixels P i . Soit le pixel P 1 de coordonn´ ees px 1 , y 1 q. Une infinit´ e de
droites d’´ equation : y 1 “ ax 1 ` b peuvent passer par P 1 . Cependant, dans
le plan des param` etres pa, bq, l’´ equation qui s’´ ecrit b “ ´ax 1 ` y 1 devient une
droite unique D 1 (voir figures ci-dessous).
103
Algorithme 2 D´ etecteur de coin de Harris (version discr` ete)
1. Calculer le gradient discret ∇I “ pI x , I y q dans toute l’image , par exemple avec les
formules 3.6 p. 58
2. Pour chaque pixel :
a. Calculer sur un voisinage V du pixel la matrice suivante :
¨
˚
˝
ÿ
V
I x I x
ÿ
V
I x I y
ÿ
V
I x I y
ÿ
V
I y I y
˛
‹
‚.
b. Calculer les valeurs propres λ 1 et λ 2 (avec λ 2 ď λ 1 )
c. Si la valeur propre minimale λ 2 ą seuil, conserver les coordonn´ ees du pixel dans une
liste L (ce sont les coins)
3. Trier L en ordre d´ ecroissant de λ 2
4. Balayer la liste L de haut en bas, pour chaque pixel p i et ´ eliminer les autres pixels qui
appartiennent au voisinage de p i .
La liste finale contient les points saillants pour lesquels λ 2 ą seuil et
dont les voisinages ne se chevauchent pas. Ce sont les pixels les plus faciles `
a
suivre !
5.3.2 Transformation de Hough
La transformation de Hough est utilis´ ee pour d´ etecter de mani` ere syst´ ematique la pr´ esence de relations structurelles sp´ ecifiques entre des pixels dans
une image. Par exemple une image repr´ esentant un site urbain est compos´ ee
de nombreuses lignes droites (immeubles, fenˆ etres) en revanche, une vue de
campagne en est quasiment d´ epourvue [41, 53].
Hough a propos´ e une m´ ethode de d´ etection bas´ ee sur une transformation
d’image permettant la reconnaissance de structures simples (droite, cercle)
liant des pixels entre eux. Pour limiter la charge de calcul, l’image originale
est pr´ ealablement limit´ ee aux contours des objets puis binaris´ ee (2 niveaux
possibles pour coder l’intensit´ e du pixel).
5.3.2.1 Principe de la m´ ethode pour la recherche de ligne droite
Supposons que l’on suspecte la pr´ esence d’une droite Δ reliant un certain
nombre de pixels P i . Soit le pixel P 1 de coordonn´ ees px 1 , y 1 q. Une infinit´ e de
droites d’´ equation : y 1 “ ax 1 ` b peuvent passer par P 1 . Cependant, dans
le plan des param` etres pa, bq, l’´ equation qui s’´ ecrit b “ ´ax 1 ` y 1 devient une
droite unique D 1 (voir figures ci-dessous).