Transformée de Hough

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La transformée de Hough est une technique de reconnaissance de formes inventée en 1962 par Paul Hough, 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[modifier | modifier le code]

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.

Le principe qui sous-tend la transformée de Hough est qu'il existe un nombre infini de lignes qui passent par un point, dont la seule différence est l'orientation (l'angle). Le but de la transformée est de déterminer lesquelles de ces lignes sont les plus fréquentes dans l'image analysée.

Afin de déterminer que deux points se trouvent sur une même ligne potentielle (attention deux points sont toujours alignés), on doit créer une représentation de la ligne qui permet une comparaison dans ce contexte.

Approche pratique[modifier | modifier le code]

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. 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 représentées par l'équation "normalisée" ρ = x * cos(θ) + y * sin(θ), où θ est l'angle de la droite et ρ la distance de la droite à l'origine (au lieu de y = a *x + b). Au point (x, y) du contour, on fait donc correspondre une courbe [θ, ρ], où θ prend toutes les valeurs possibles de 0 à 2π, ρ prenant la valeur ρ = x * cos(θ) + y * sin(θ). Une fois appliquée à tous les points des contours, et, pour chacun, à tous les angles θ possibles, les points (θ, ρ) de l'espace transformé les plus souvent adressés sont les coordonnées des droites ou des segments de droite les plus représentés dans l'image de départ.

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'occurences 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.

Représentation[modifier | modifier le code]

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) [1]

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.

Exemple de transformée de Hough.

Brevet[modifier | modifier le code]

Brevet US 3 069 654 déposé en 1962 sous le nom « Method and Means for Recognizing Complex Patterns » (Méthodes et Moyens de Reconnaissance de Motifs Complexes).

Notes et références[modifier | modifier le code]

  1. http://en.wikipedia.org/wiki/Hough_transform

Voir aussi[modifier | modifier le code]

Références et bibliographie[modifier | modifier le code]

  • Duda, R. O. et P. E. Hart, « Use of the Hough Transformation to Detect Lines and Curves in Pictures », Comm. ACM, Vol. 15, pp. 11 - 15 (janvier 1972).
  • TARSHA-KURDI, F., LANDES, T. and GRUSSENMEYER, P., 2007. 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, 36(3/W52): 407-412.

Logiciels[modifier | modifier le code]

  • Liquify.eu - démonstration en ligne de la transformée de Hough sur Liquify.eu
  • hough_transform.cpp - code C++ - exemple de la bibliothèque CImg (cf. dossier examples)
  • scikit-image Transformation de Hough (droite, cercle, ellipse) dans la bibliothèque scikit-image (Python).

Articles connexes[modifier | modifier le code]