La transformée de Hough est une technique d'extraction de caractéristiques utilisée en analyse d'images, en vision par ordinateur, en reconnaissance de formes et en traitement numérique des images. Son objectif est de trouver des instances imparfaites d'objets appartenant à une certaine classe de formes par une procédure de vote. Cette procédure de vote est réalisée dans un espace de paramètres, à partir duquel les candidats objets sont obtenus comme des maxima locaux dans un espace d'accumulation explicitement construit par l'algorithme. Mathématiquement, il s'agit de la transformée de Radon dans le plan, connue depuis au moins 1917, mais la transformée de Hough fait spécifiquement référence à son utilisation en analyse d'images.
La transformée de Hough classique concernait l'identification de lignes dans une image, mais elle a depuis été étendue à l'identification de positions de formes arbitraires, le plus souvent des cercles ou des ellipses. La transformée telle qu'elle est universellement utilisée aujourd'hui a été inventée par Richard Duda et Peter Hart en 1972, qui l'ont appelée « transformée de Hough généralisée » après le brevet connexe de Paul Hough de 1962. Elle a été popularisée dans la communauté de la vision par ordinateur par Dana H. Ballard à travers un article de journal de 1981 intitulé « Generalizing the Hough transform to detect arbitrary shapes ».
Histoire
La transformée de Hough a été initialement inventée pour l'analyse automatique de photographies de chambres à bulles par Paul Hough en 1959. Elle a été brevetée sous le brevet américain 3 069 654 en 1962 et attribuée à la Commission de l'énergie atomique des États-Unis sous le nom « Method and Means for Recognizing Complex Patterns ». Ce brevet utilisait une paramétrisation pente-ordonnée à l'origine pour les lignes droites, ce qui conduisait maladroitement à un espace de transformation non borné, car la pente peut tendre vers l'infini.
La paramétrisation rho-thêta universellement utilisée aujourd'hui a été décrite pour la première fois dans un article de 1972 de Richard Duda et Peter Hart, « Use of the Hough Transformation to Detect Lines and Curves in Pictures », publié dans Communications of the ACM. Cette paramétrisation était déjà standard pour la transformée de Radon depuis au moins les années 1930. Frank O'Gorman et M.B. Clowes ont publié une variante en 1976 dans IEEE Transactions on Computers, intitulée « Finding Picture Edges Through Collinearity of Feature Points ». L'histoire de la façon dont la forme moderne a été inventée est détaillée dans l'article de Peter Hart de 2009 « How the Hough Transform was Invented » dans IEEE Signal Processing Magazine.
Théorie
Dans l'analyse automatisée d'images numériques, un sous-problème survient souvent : la détection de formes simples, telles que des lignes droites, des cercles ou des ellipses. Un détecteur de contours peut être utilisé comme étape de prétraitement pour obtenir des points d'image sur la courbe souhaitée. Cependant, en raison d'imperfections dans les données d'image ou du détecteur de contours, il peut y avoir des points manquants ou des écarts spatiaux entre la forme idéale et les points de contour bruités. La transformée de Hough répond à cela en effectuant une procédure de vote explicite sur un ensemble d'objets d'image paramétrés, ce qui permet de regrouper les points de contour en candidats objets.
Détection de lignes
Le cas le plus simple est la détection de lignes droites. En général, une ligne y = mx + b peut être représentée comme un point (b, m) dans l'espace de paramètres, mais les lignes verticales posent problème en raison de valeurs de pente non bornées. Duda et Hart ont proposé d'utiliser la forme normale de Hesse : r = x cos(thêta) + y sin(thêta), où r est la distance de l'origine au point le plus proche sur la ligne, et thêta est l'angle entre l'axe des x et la ligne reliant l'origine à ce point le plus proche. Chaque vecteur sur la ligne est perpendiculaire au segment de ligne de longueur r depuis l'origine. Le point d'intersection est à P0 = (r cos(thêta), r sin(thêta)). Pour tout point P sur la ligne, le vecteur P - P0 doit être orthogonal à P0, ce qui impose (P - P0) · P0 = 0, ce qui se simplifie en r(x cos(thêta) + y sin(thêta)) = r^2(cos^2(thêta) + sin^2(thêta)).
Algorithme et procédure de vote
En pratique, la transformée de Hough discrétise l'espace de paramètres en un tableau d'accumulation. Pour chaque point de contour dans l'image, l'algorithme calcule toutes les valeurs de paramètres possibles (par exemple, r et thêta pour les lignes) qui pourraient correspondre à une forme passant par ce point, et incrémente les cellules d'accumulation correspondantes. Après avoir traité tous les points, les maxima locaux dans l'accumulateur indiquent les candidats de forme probables. Cette procédure de vote est robuste au bruit et aux données manquantes, car elle n'exige pas que tous les points d'une forme soient parfaitement alignés.
Extensions et applications
La transformée de Hough généralisée, introduite par Dana Ballard en 1981, étend la technique à des formes arbitraires en utilisant un point de référence et une table d'orientations de contours. Cela permet la détection de formes complexes au-delà des lignes, des cercles et des ellipses. La transformée a été largement appliquée dans des domaines tels que la conduite autonome, l'imagerie médicale et l'inspection industrielle. Dans les systèmes de Computer vision, elle est souvent combinée avec des algorithmes de détection de contours pour identifier des objets dans les pipelines de traitement d'images numériques. Son fondement mathématique dans la transformée de Radon la relie à des techniques plus larges d'analyse d'images utilisées dans les applications de Machine learning et d'Artificial intelligence.
Limites et variantes
Une limite de la transformée de Hough classique est son coût de calcul, en particulier pour les espaces de paramètres de haute dimension. Des variantes telles que la transformée de Hough probabiliste et la transformée de Hough circulaire ont été développées pour améliorer l'efficacité. La version probabiliste échantillonne un sous-ensemble de points de contour pour réduire le calcul, tandis que la transformée circulaire utilise un espace de paramètres tridimensionnel (centre x, centre y, rayon). Ces variantes sont couramment implémentées dans des bibliothèques comme opencv et sont utilisées dans des systèmes en temps réel, y compris ceux des véhicules autonomes et de la Robotics.
Voir aussi
- transformée de Radon
- détection de contours
- vision par ordinateur
- traitement d'images