La transformée de Hough est une technique de reconnaissance de formes inventée en 1959 par Paul Hough., faisant l'objet d'un brevetBrevet US déposé en 1962 sous le nom (Méthodes et moyens de reconnaissance de motifs complexes)., et utilisée dans le traitement d'images numériques.
L'application la plus simple permet de détecter les lignes présentes dans une image, mais des modifications peuvent être apportées à cette technique pour détecter d'autres formes géométriques : c'est la transformée généralisée de Hough développée par Richard Duda et Peter Hart en 1972.
Approche théorique
Le problème posé est celui de la recherche et de la détection de lignes qui seraient éventuellement présentes dans une image analysée malgré les imperfections de l'image : points manquants (la ligne pouvant être partiellement masquée par un objet), bruit. La transformée de Hough consiste à représenter chaque point de contour détecté dans un espace de paramètres à deux dimensions : une droite est caractérisée par deux paramètres, elle est donc représentée par un point dans cet espace de paramètres ; si l'on considère l'ensemble des droites passant par un point, l'image de cet ensemble est une courbe dans l'espace de paramètres. La transformée de Hough d'un point de l'image analysée est la courbe de l'espace des paramètres correspondant à l'ensemble des droites passant par ce point.
Si des points sont colinéaires, alors toutes les courbes de l'espace de paramètres se coupent au point représentant la droite en question.
Du fait des imperfections de l'image, les points détectés ne sont pas parfaitement alignés et donc les courbes ne sont pas parfaitement concourantes. La méthode consiste donc à discrétiser l'espace de paramètres, à le découper en petits rectangles, et à dénombrer pour chaque rectangle le nombre de courbe y passant. On construit ainsi une matrice dite d'accumulation, les maxima locaux de cette matrice correspondant à des droites probables.
L'algorithme comporte donc trois étapes : pour chaque point de contour détecté, détermination de la courbe correspondante dans l'espace des paramètres ; construction de la matrice d'accumulation à partir de ces courbes ; détection de pics dans la matrice d'accumulation.
Approche pratique
vignette |L'équation cartésienne de la droite peut être écrite sous sa forme « normale » qui fait intervenir des coordonnées polaires .
Initialement, Hough a caractérisé les droites par leur pente et leur ordonnée à l'origine. L'inconvénient de cette approche est que la pente tend vers l'infini lorsque la droite tend vers la verticale. En 1972, Duda et Hart ont proposé une paramétrisation par les coordonnées polaires . qui est depuis utilisée de manière universelle.
Une droite peut être caractérisée par des paramètres polaires : est la distance de la droite à l'origine du repère, est l'angle que fait la perpendiculaire à la droite avec l'axe . Les coordonnées des points de cette droite vérifient l'équation dite « normale » :
On suppose tout d'abord que si des lignes ou des segments de droites sont présents dans une image, ils feront partie des contours présents dans l'image. On commence donc dans un premier temps par identifier tous les points de contours de cette image, par exemple à l'aide de techniques de mesures de gradients locaux entre les valeurs des pixels autour de chaque point de l'image comme le filtre de Canny. Les points de l'image présentant les gradients les plus élevés dans leur voisinage, soit globalement pour l'image (seuillage fixe), soit par rapport aux gradients généralement présents dans un voisinage plus large autour du point (seuillage dynamique), sont les plus susceptibles d'appartenir à des contours de cette image.
Chacun des points des contours ainsi identifiés va alors permettre une projection dans un plan (le plan transformé) des coordonnées polaires de toutes les droites passant par ce point. Les équations des droites passant en chacun de ces points sont donc représentées par un couple vérifiant
Au point du contour, on fait donc correspondre une courbe où prend toutes les valeurs possibles de 0 à (0 à ), avec
Cette courbe est une sinusoïde. Dans la pratique, on fait varier de 0 à (0 à ) et on considère un rayon algébrique (positif ou négatif). Le paramètre va prendre des valeurs entre et où est la grande diagonale de l'image : , étant la largeur de l'image et sa hauteur.
Lorsque les courbes correspondant à deux points se rencontrent, le point d'intersection caractérise la droite passant par les deux points.
Donc, dans le plan , on associe à chaque point une densité correspondant au nombre de courbe qui y passent. Plus la densité est importante, plus il y a des points de contour situés sur cette droite. La droite est donc très probablement un segment dans l'image.
En pratique, l'espace transformé de Hough sera représenté par une image dont les abscisses seront les angles , dont les ordonnées les valeurs de et dont l'intensité au point quelconque est le nombre d'occurrences de provenant de l'image d'origine. Aucune hypothèse de continuité des droites ou segments de droite de l'image de départ n'est faite ici, ce qui rend la transformée robuste à l'absence de points : masquage partiel des droites, et au bruit dans l'image.
Les valeurs de peuvent être discrétisées par exemple en degrés (selon la précision souhaitée), et les valeurs de en pixels représentant la distance (toujours inférieure en valeur absolue au diamètre de l'image de départ), la fréquence étant bornée par le nombre de points sélectionnés dans les contours de l'image de départ.
L'algorithme est donc, en pseudo-code : Importe : I % image matricielle J ← contours de I % p.ex. filtre de Canny Définit : δ % pas de discrétisation 1. M ← 0 % initialisation de la matrice d'accumulation 2. pour chaque pixel (x, y) de J faire 3. pour θ allant de 0 à 180 avec le pas δ 4. ρ ← x*cos(θ) + y*sin(θ) 5. M(ρ, θ) ← M(ρ, θ) + 1 6. fin de boucle 7. fin de boucle Détection des pics de M
Représentation
Dans la transformée de Hough, dite aussi transformée standard de Hough ou SHT, chaque ligne est un vecteur de coordonnées paramétriques : : l'angle ; : la norme du vecteur (la longueur du segment perpendiculaire à la droite d'angle et passant par l'origine).
En transformant toutes les lignes possibles qui passent par un point, c’est-à-dire en calculant la valeur de pour chaque , on obtient une sinusoïde unique appelée « espace de Hough ». Si les courbes associées à deux points se coupent, l'endroit où elles se coupent dans l'espace de Hough correspond aux paramètres d'une droite qui relie ces deux points.
Améliorations
La détection de contour fait intervenir la détermination du gradient de contraste de l'image. De fait, la direction de ce gradient est perpendiculaire à la direction du contour. Plutôt que de tracer les sinusoïdes pour variant de 0 à , on peut se restreindre à une plage autour des orientations ainsi trouvées. Cette méthode a été proposée par O'Gorman et Clowes en 1976. et est appelée GHT (, transformée de Hough à partir du gradient).
Fernandes et Oliveira ont proposé une amélioration permettant d'accélérer le traitement au point de pouvoir traiter en temps réel des images jusqu'à × 960 pixels. La méthode est la suivante : ils groupent les pixels de contour détectés en chaînes () formant globalement des segments de droite : ils connectent les pixels de proche en proche afin de former une chaîne, en prenant la droite passant par les extrémités de chaque chaîne, ils déterminent le pixel de la chaîne le plus éloigné et coupent la chaîne en deux ; si les sous-chaînes forment des segment « plus linéaires », la division est conservée ; cette étape est faite de manière récursive en s'arrêtant à une taille minimale ; pour chaque chaîne, par régression linéaire, ils déterminent la droite et la dispersion autour de cette droite : pour éviter le problème lié aux droites verticales, ils se placent dans le repère dont l'axe est la droite reliant les extrémités, les écarts types estimés sur la pente et l'ordonnée à l'origine servent à déterminer les écarts types sur les paramètres et ; pour chaque chaîne, ils effectuent une accumulation de manière classique mais en se restreignant à un « noyau elliptique gaussien » : une ellipse centrée sur le point caractéristique de la droite de régression et dont les petit et grand axes sont déterminés par les écarts types ; le cas d'une ellipse sortant du domaine de définition ([ ; ], [0 ; 180°]) est traité ; la matrice d'accumulation est « lissée » par un produit de convolution avec un noyau gaussien 3 × 3 : ceci permet d'atténuer les très petits pics isolés et de regrouper les petits pics proches. Cette méthode est appelée KHT (, transformée de Hough à partir de noyaux).
Extension à d'autres courbes analytiques
La méthode peut s'appliquer à toute courbe représentée par une équation cartésienne ou paramétrique.
Détection de cercles
La méthode de détection de cercle est également baptisée HCT ().
Dans cette méthode, un cercle est décrit par son équation cartésienne :
où le point de coordonnées est le centre du cercle ; en est le rayon. Dans l'espace , un cercle est caractérisé par un point. L'ensemble des cercles passant par un point donné forme un cône de sommet et d'axe . Un « bon candidat » correspond à l'intersection de plusieurs cônes.
Si le rayon du cercle recherché est connu, on peut alors se placer dans le plan . Dans ce plan, l'ensemble des cercles passant par est décrit par le cercle de centre et de rayon . Un bon candidat est donc à l'intersection de plusieurs cercles. On construit une matrice d'accumulation : chaque élément de la matrice contient le nombre de cercles passant par le point, ou bien par un carré de plusieurs pixels, correspondant à cet élément.
Si le rayon est inconnu, la méthode de recherche consiste à construire une hypermatrice d'accumulation dont chaque cellule correspond à un cube de l'espace , en balayant tous les rayons possible de 1 pixel jusqu'à la dimension de l'image.
Applications
Un cercle est la projection d'un objet sphérique sur un plan, ou bien d'une section circulaire (cylindre, cône, tore) à condition que l'axe de l'objet soit perpendiculaire au plan de projection (sinon la projection est une ellipse). La reconnaissance de formes circulaires peut servir à la détection de têtes, et donc de personnes, sur une photographie ou une image de surveillance vidéo.. Elle peut également servir à détecter des anévrismes sur un angiogramme..
Détection d'ellipses
vignette |upright=2 |Axes de symétrie des paires de points sur une même horizontale ou verticale (Yin et Chen 1994) et détermination du centre de l'ellipse en utilisant les points milieu (Ho et Chen 1995).
vignette |Détermination du centre de l'ellipse à partir de paires de points : la courbure est reliée aux tangentes (Aguado et Nixon 1995), le centre se trouve sur la droite reliant l'intersection de deux tangentes au milieu du segment (Alvarez et coll. 2007).
Une ellipse est caractérisée par cinq paramètres, typiquement : : abscisse de son centre ; : ordonnée de son centre ; : demie longueur du grand axe ; : demie longueur du petit axe ; : inclinaison du grand axe par rapport à l'axe des . Cela signifie que la mise en œuvre directe de la transformée de Hough se fait dans un espace à cinq dimensions ce qui implique une durée de calcul importante et nécessite une grande capacité de mémoire. Plusieurs algorithmes ont été proposés pour diminuer le nombre de paramètres nécessaires.