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 reconnaître les lignes d'une image, mais des modifications peuvent être apportées pour reconnaître n'importe quelle forme : 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 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 passent au plus près du schéma attendu.

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.

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]

  • 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]