Transformée de Hough

La transformée de Hough est une technique de reconnaissance de formes inventée en 1959 par Paul Hough, faisant l'objet d'un brevet, 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

L'équation cartésienne de la droite (D) 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 (D) 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 x.

Les coordonnées (x, y) des points de cette droite vérifient l'équation dite « normale » :

ρ = x ⋅ cos(θ) + y ⋅ sin(θ)

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 (x, y) 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 (x, y) sont donc représentées par un couple (ρ, θ) vérifiant

ρ = x ⋅ cos(θ) + y ⋅ sin(θ)

Au point (x, y) du contour, on fait donc correspondre une courbe ρ = f(θ) où θ prend toutes les valeurs possibles de 0 à 2π rad (0 à 360°), avec

f(θ) = x ⋅ cos(θ) + y ⋅ sin(θ).

Cette courbe est une sinusoïde. Dans la pratique, on fait varier θ de 0 à π rad (0 à 180°) et on considère un rayon algébrique (positif ou négatif). Le paramètre ρ va prendre des valeurs entre -R et +R où R est la grande diagonale de l'image : R = √l² + h² , l étant la largeur de l'image et h 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

Exemple de transformée de Hough.

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 à 180°, 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 (gradient-based Hough transform, 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'à 1 280 × 960 pixels. La méthode est la suivante :

• ils groupent les pixels de contour détectés en chaînes (clusters) 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 x 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 ([-R ; +R], [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 (Kernel-based Hough transform, 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 (Hough circle transform).

Dans cette méthode, un cercle est décrit par son équation cartésienne :

(x – a)² + (y – b)² = r²

où

• le point de coordonnées (a, b) est le centre du cercle ;
• r en est le rayon.

Dans l'espace (a, b, r), un cercle est caractérisé par un point. L'ensemble des cercles passant par un point M(x, y) donné forme un cône de sommet (a = x, b = y, r = 0) et d'axe r. 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 (a, b). Dans ce plan, l'ensemble des cercles passant par M est décrit par le cercle de centre (a = x, b = y) et de rayon r. Un bon candidat est donc à l'intersection de plusieurs cercles. On construit une matrice d'accumulation A : chaque élément A_i,j 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 A_i,j correspond à un cube de l'espace (a, b, r), 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

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).

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 :

• x₀ : abscisse de son centre ;
• y₀ : ordonnée de son centre ;
• a : demie longueur du grand axe ;
• b : demie longueur du petit axe ;
• θ : inclinaison du grand axe par rapport à l'axe des x.

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.

En 1978, Tsuji et Matsumoto proposent d'utiliser le gradient de contraste pour déterminer la perpendiculaire à la tangente. En considérant les points ayant des tangentes parallèles, ils déterminent la position des centres des ellipses. Puis, ils utilisent les propriétés géométriques pour séparer les ellipses des autres objets ayant la même propriété, finalement, les paramètres des ellipses sont déterminés par la méthode des moindres carrés

En 1994, Yin et Chen proposent de sélectionner des groupes de cinq points, nombre suffisant pour déterminer une ellipse. Pour cela, les points sont classés dans des sous-images. L'image des points de contour détectés est appelée F. L'algorithme effectue un balayage de haut en bas par une droite horizontale et prennent les points situés sur cette droite. Il considère les milieux des segments ainsi définis, ces milieux de segments forment une image appelée G. Pour une ellipse donnée, les milieux des segments se situent sur une même droite, la droite dépendant de l'inclinaison du grand axe ; cette droite est appelée « axe de symétrie » car les points sont symétriques non pas par réflexion mais par une similitude de rapport 1. Ces droites sont déterminées par la transformée de Hough classique de G. Puis, l'algorithme crée des sous-images de F formées des points générant une droite donnée de G ; ainsi, les points de F sont classés selon leur appartenance possible à une ellipse ayant un axe de symétrie donné. Chaque sous-image est ensuite traitée séparément. Dans une sous-image, pour chaque paire de points (A, B), l'algorithme détermine cinq points :

• deux points (E, F) « autour de A », c'est-à-dire sur la frontière d'une fenêtre carrée de côté c, tel que l'angle EÂF est compatible avec le sens de courbure de l'ellipse ;
• les deux points symétriques (G, H) ;
• un cinquième point I situé sur la médiatrice de [EG] ou de [FH].

Les paramètres de l'ellipse sont déterminés à partir de ces cinq points et la matrice d'accumulation est mise à jour pour ce jeu de paramètres. les limites de cette méthode sont :

• l'image doit avoir un nombre suffisant de paires de points par ellipse ;
• certaines sous-images générées ne contiennent pas d'ellipse et donc consomment du temps de calcul sans bénéfice ;
• la largeur c de la fenêtre carrée doit être suffisamment grande pour que les cinq points soient espacés, ce qui garantit une bonne précision dans la détermination des paramètres, mais doit être inférieure à la demie longueur du petit axe de chaque ellipse.

En 1995, Ho et Chen créent deux sous-espaces d'une manière similaire à Yin et Chen. Le premier consiste à considérer les paires de points de contour situés sur une même droite horizontale et à prendre les milieux des segments ainsi formés. Le second sous-espace est construit de la même manière mais en considérant les paires de points situés sur une même verticale. L'algorithme effectue ensuite une détection des droites formées par ces points milieu avec la transformée de Hough classique, l'intersection de ces droites donnant les centres des ellipses. Ils déterminent ensuite les trois paramètres restant (détermination du grand et du petit axe).

Une méthode similaire consiste à considérer des paires de points : le gradient permet d'avoir accès à la tangente, si les tangentes ne sont pas parallèles, elles se coupent en un point T. La droite reliant ce point au milieu du segment passe par le cente de l'ellipse.

Avec l'hypothèse que [A₁A₂] est le grand axe, les ellipses sont nécessairement dans le disque gris. Chaque cellule de la matrice d'accumulation (à une seule dimension, b) ne contient qu'au plus deux occurrences donc l'hypothèse « [A₁A₂] est le grand axe » est rejetée (Xie et Ji 2002).

En 2002, Xie et Ji proposent une méthode n'effectuant une recherche que sur un seul paramètre, la longueur de demi petit-axe. Ils prennent une paire de points A₁(x₁, y₁) et A₂(x₂, y₂) suffisamment éloignés et supposent qu'ils sont situés sur le grand axe d'une ellipse. Avec cette hypothèse, le centre de l'ellipse se trouve nécessairement au milieu O de [A₁A₂], la longueur du grand axe est 2a = A₁A₂ et l'inclinaison du grand axe est θ = arctan((y₂ – y₁)/(x₂ – x₁)). Puis, ils considèrent chaque point de contour M : s'il est suffisamment proche de O pour pouvoir être sur une ellipse de grand axe [A₁A₂], alors le point M sert à calculer le demi petit-axe b de l'ellipse. C'est ce paramètre b qui sert à construire la matrice d'accumulation. Si la matrice contient un pic suffisamment grand pour caractériser une ellipse, alors l'ellipse est retenue. Puis, l'algorithme passe à un autre couple (A₁, A₂). L'algorithme consiste donc à faire une transformée de Hough pour chacune des paires de points suffisamment éloignés, mais cette transformée ne se fait que sur un seul paramètre. En revanche, l'image doit faire figurer les extrémités du grand axe pour qu'une ellipse soit détectée.

Applications

Une ellipse est la projection d'une section circulaire sur un plan. La détection d'ellipse permet donc la détection d'objets cylindrique ou torique tels que les pupilles des yeux, les panneaux de signalisation et les roues des véhicules.

Voir aussi

Bibliographie

• [Duda et Hart 1972] (en) R. O. Duda et P. E. Hart, « Use of the Hough Transformation to Detect Lines and Curves in Pictures », Comm. ACM, vol. 15,‎ janvier 1972, p. 11-15.
• [Hart 2009] (en) P. E. Hart, « How the Hough Transform was Invented », IEEE Signal Processing Magazine, vol. 26, n^o 6,‎ novembre 2009, p. 18–22 (lire en ligne).
• [Hough 1959] (en) P.V.C. Hough, « Machine Analysis of Bubble Chamber Pictures », dans Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959.
• [Tarsha-Kurdi et col. 2007] (en) F. Tarsha-Kurdi, T. Landes et P. Grussmeyer, « Hough-Transform and Extended RANSAC Algorithms for Automatic Detection of 3D Building Roof Planes from Lidar Data », International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. 36, n^o 3/W52,‎ 2007, p. 407-412.

Liens externes

• scikit-image Transformation de Hough (droite, cercle, ellipse) dans la bibliothèque scikit-image (Python).

Articles connexes

• Reconnaissance de formes