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