Transformée de Hough
Basile Graf, Christophe Espic
Prof. Jean-Philippe Thiran
Introduction
• La transformée de Hough, utilisée en
segmentation d’images, permet de
détecter des objets bien précis dans une
image.
• Bonne insensibilité au bruit
• Elle permet de détecter des objets
partiellement recouverts
1
Principe
Détection de droites (1)
y b
y = ax+b
x a
y b
b = -ax+y
x a
Espace « image » Espace des paramètres
Principe
Détection de droites (2)
y b
y = ax+b
x a
Les images de tous les points d’une droite se coupent en (a,b) dans le
domaine de Hough
2
Méthode
Détection de droites (3)
1. Appliquer une détection de contours
2. Discrétiser le plan des paramètres (a,b)
3. Initialiser un accumulateur
4. Pour chaque point sur un contour :
1. Déterminer sa droite image dans l’espace des
paramètres
2. Incrémenter l’accumulateur sur les points de cette
droite
5. Recherche de maxima paramètres
Exemple
Détection de droites
Image originale Détection de contours Transformée de Hough
(MATLAB: edge) Recherche de maximum
Le max correspond aux paramètres (a,b) de la droite
3
Défauts
Paramétrisation
• L’espace des paramètres doit être borné
et discrétisé dans une implémentation
réelle
• => Une droite verticale ne peut pas être
représentée (a=∞)
• => Autre paramétrisation que y=ax+b
Espace (s,θ)
y s
θ
x θ
x = s cos(θ)
y = s sin(θ)
x cos(θ) + y sin(θ) – s = 0
4
Espace (s,θ)
y s
x θ
(x1,y1) s= x1 cos(θ) + y1 sin(θ)
Les sinusoïdes correspondant aux points d’une même droite se coupent
au point (s,θ) paramétrisant cette droite
Exemple (s, θ)
Transformée de
Détection de Droites
Hough (s, θ)
bords correspondantes
Maxima locaux
5
Détection de cercles de rayon R
La paramétrisation d’un cercle de centre (a,b) et de rayon R
peut être donnée par
(x-a)2 + (y-b)2 – R2 = 0
y b
x a
Exemple
Transformée de Hough (a,b) Cercle
Détection de bords
Maxima locaux correspondant
6
Généralisation
Détection d’autres types de courbes
Paramétrisation: f(x,a) = 0 VxC la courbe
La dimension de l’accumulateur (espace des paramètres)
est dim(a)
Algorithme
• Détection de bords
• Pour chaque point appartenant à un bord,
calculer f(xi,a) et incrémenter
l’accumulateur en aj lorsque |f(xi,aj)| < ε
• Recherche des maxima locaux de
l’accumulateur
=> Paramétrisation des courbes recherchées
7
Inconvénients
La dimension du domaine transformé est égal aux
nombres de paramètres nécessaires pour décrire la
courbe
=> Le temps de calcul et la mémoire utilisée
deviennent vite conséquents
Exemple: Cercles de rayons différents b
f(x,a) = (x-a)2 + (y-b)2 – r2
x = (x,y) a = (a,b,r) a
r
Conclusion
• La transformée de Hough est utile pour la
détection de contours descriptibles par
peu de paramètres (2, voire 3)
• Elle est robuste (bruit, occlusions)
• On peut envisager des algorithmes plus
efficaces (multirésolution dans l’espace
des paramètres)
