Les transformations de Hough sont des outils permettant une représentation paramétrique de l'image à partir de sa représentation spatiale habituelle. Afin d'avoir une idée concrète de ce que cela peut donner, nous commencerons par parler des espace des droites. Nous présenterons ensuite brièvement la mise en pratique de ces transformations.
 

Un exemple d'espace de Hough : espace de droites

     Nous appellerons ici "espace des droites" un plan dont les axes représentent respectivement la pente et l'ordonnée à l'origine des droites.

     De la même manière qu'un point est parfaitement localisé dans un espace de dimension 2 par ses coordonnées (x,y), une droite est parfaitement localisée dans cet espace des droites par ses paramètres a et b, a étant son coefficient directeur et b son ordonnée à l'origine. Le couple (a,b) représente les coordonnées de cette droite dans l'espace des droites.
Il vient alors assez vite l'intuition qu'un point de l'image devrait être représenté par une droite dans l'espace des droites. En effet, on avait, dans le cas d'une droite :

           y = ax + b

a et b étaient des constantes, et la droite était par définition constituée des points dont les coordonnées vérifiaient cette équation.

Dans le cas d'un point, on peut écrire :

           b = -ax + y

Autrement dit, toutes les droites passant par le point (x,y) fixé voient leurs paramètres a et b vérifier cette équation. Or, on reconnait là une équation de droite. C'est cette droite (a,b) qui caractérise dans l'espace des droites le point  (x,y).
 

Remarque :

     Le choix des paramètres a et b pour construire l'espace des droites n'est en fait pas judicieux et pas utilisé. Il pose en effet des problèmes quant à la répartition des valeurs de ces paramètres. En ce qui concerne l'ordonnée à l'origine b, elle doit pouvoir varier de - à + l'infini indépendamment de la taille de l'image. Quant à la valeur du coefficient directeur a, elle a en terme de probabilités autant de chances de se trouver dans l'intervalle [0,1] que dans l'intervalle [1,+infini[.

     On préfèrera donc construire l'espace des droites à partir des paramètres r et theta. r représente la distance de la droite au centre de l'image, et theta l'angle que fait une perpendiculaire à cette droite avec l'axe des abscisses de l'image. Dans ce cas, une droite sera toujours représentée par un point, de coordonnées (r, theta), mais un point sera désormais représenté dans l'espace des droites par une sinusoïde.
 

     La transformation de Hough citée en exemple permet de passer de l'image à un espace de droites associé. Mais on peut très bien imaginer une transformation permettant de passer dans l'espace des cercles (de dimension 3), dans celui des ellipses (de dimension 5), ou dans tout autre qui conviendra au problème posé. Les paramètres servant à construire l'espace de Hough peuvent être de toutes sortes : coefficients, distances, coordonnées, etc ...
 
 
 
 

Mise en pratique des transformations de Hough

     Re venons à l'exemple d'un espace de droites. Comme on l'a expliqué, une droite de l'image est représentée par un point dans l'espace de Hough. Mais la projection de notre image dans cet espace est rarement la finalité de l'opération. Cette transformation est en général utilisée pour effectuer la détection des éventuelles droites présentes dans l'image. Il est en effet plus facile de détecter un point (même dans un espace de Hough) qu'une droite.

     Le problème qui se pose alors est le suivant : comment, à partir d'un paquet de points de l'image censés représenter un droite, obtient-on dans l'espace de Hough le point associé à ladite droite ? Il existe deux méthodes pour y parvenir : la transformation dite de 1 à m et la transformation de m à 1.
 

Transformation de 1 à m

On associe à chaque point de l'image son représentant dans l'espace de Hough, par exemple une droite. Des points alignés seront alors représentés par des droites concourrantes ; le point d'intersection de ces droites représentera dans l'image la droite que l'on veut détecter. On ne conserve donc dans l'espace de Hough que les intersections de droites. On détectera alors les droites de l'image en localisant les nuages d'intersections dans l'espace de Hough.
 

Transformation de m à 1

On prend pour chaque bipoint de l'image la droite qui en est le support, et on place dans l'espace de Hough le point qui représente cette droite. S'il existe une droite dans l'image, une proportion non négligeable de bipoints se trouveront dessus. On obtiendra donc un nuage de points dans l'espace de Hough, qu'il faudra localiser.
 
 
 

     Lors de la mise en pratique des transformations de Hough, deux problèmes apparaissent :

 - même si une très belle droite est présente dans l'image, celle-ci possède en général malgré tout beaucoup de points n'appartenant pas à cette droite. Les amas de points recherchés dans l'espace de Hough risquent donc d'être noyés dans la masse des points non représentatifs de droites réelles.

 - une image comporte en général beaucoup de points, et il est la plupart du temps inenvisageable de les traiter de manière exhaustive.
 

Pour remédier au premier problème, on choisit de discrétiser l'espace de Hough. Celui-ci sera alors constitué de cellules appelées accumulateurs. Lors de la transformation, chaque point qui aurait dû être placé dans l'espace de Hough donne un vote à l'accumulateur dans la zone duquel il se trouve. On ne cherchera alors plus les amas de points, mais les maximas locaux de nombres de votes.
Il conviendra de prêter une attention toute particulière à la taille de ces accumulateurs . Des accumulateurs trop petits feraient renaître le problème qu'ils sont censés éviter, et créeraient un étalement sur plusieurs cellules de l'amas de points recherché. Des accumulateurs trop grands donneront une mauvaise précision dans la détection de la droite.
 

Pour remédier au second problème, on choisit la solution la plus intuitive : on ne traite pas tous les points, et on sélectionne de manière aléatoire les points traités. Des études ont montré qu'un nombre suffisamment élevé de points choisis aléatoirement permettait un traitement rigoureux de l'image.
 
 
 
 
 
 

	Index	Choix d'une transformation de Hough