Transformée généralisée de Hough

La transformée généralisée de Hough est une technique de reconnaissance de formes utilisée pour le traitement d'images numériques. Développée en 1972 par R. Duda et P. Hart, elle permet d'étendre le principe de la transformée de Hough pour des formes quelconques (i.e. sans représentation analytique simple).

Principe

La transformée généralisée de Hough fonctionne sur le même principe que la transformée de Hough : on recherche la présence d'une courbe, caractérisée par un certain nombre de paramètres ; chaque point de l'image analysée « vote » pour l'ensemble des jeux de paramètres générant des courbes auxquelles il appartient. La présence d'une courbe recherchée est caractérisée par un jeu de paramètres ayant un score élevé.

Algorithme

Considérons une forme qui n'est pas définie par une équation cartésienne ou paramétrique. Elle est définie par un ensemble de points de contour (x_i, y_i).

Caractérisation de la forme recherchée

Dans l'image enregistrée, la forme peut être à un endroit quelconque et selon une orientation quelconque. On choisit donc une position de référence et pour cette position, un point de référence (x_c, y_c). Puis, pour chaque point i de la forme, on détermine :

• les coordonnées cartésiennes dans le repère d'origine (x_c, y_c) : x'_i = x_i – x_c, y'_i = y_i – y_c
• les coordonnées polaires (ρ_i, θ_i) par rapport au repère d'origine (x_c, y_c) ;
• on détermine l'angle α_i = π – θ_i ; on a donc :
  $\left\{{\begin{matrix}x'_{i}=-\rho _{i}\cdot \cos \alpha _{i}\\y'_{i}=-\rho _{i}\cdot \sin \alpha _{i}\end{matrix}}\right.$
  et
  $\left\{{\begin{matrix}x_{\mathrm {c} }=x_{i}+\rho _{i}\cdot \cos \alpha _{i}\\y_{\mathrm {c} }=y_{i}+\rho _{i}\cdot \sin \alpha _{i}\end{matrix}}\right.$

• l'angle que fait la tangente du contour (donc la perpendiculaire au gradient de contraste) avec l'axe des x, φ_i ;
• on crée une table, appelée « table R » (anglais : R-table), qui liste les couples (ρ_i, α_i) pour chaque valeur de φ.

On crée une table R par forme recherchée.

Recherche de la forme dans la même orientation et taille

Nous supposons dans un premier temps que la forme a la même orientation et la même taille que la référence.

Pour chaque point de contour détecté sur l'image, on détermine l'angle φ de la perpendiculaire au gradient de contraste avec l'axe des x. Puis, dans la table R, on extraie tous les couples (ρ(φ), α(φ)) et pour chaque couple, on détermine le point (x_c, y_c) correspondant. La matrice d'accumulation est incrémentée pour ces positions (x_c, y_c).

On transforme donc chaque point de contour détecté sur l'image en un nuage de points dans l'espace des centres (x_c, y_c) et on retient comme candidats les zones ayant une forte densité de centre possibles.

Recherche dans le cas général

Dans le cas général, la forme peut subir une similitude directe, composée d'une homothétie (changement de taille), d'une rotation (changement d'orientation) et d'une translation (changement de place) ; nous n'avons considéré précédemment que les translations. L'homothétie est caractérisée par un facteur s et la rotation par un angle Θ. Dans le repère centré sur la position (x_c, y_c) de référence, le point (x_i', y_i') se transforme en point (x''_i, y''_i) :

$\left\{{\begin{matrix}x''_{i}=s(x'\cos \Theta +y'\sin \Theta )\\y''_{i}=s(x'\sin \Theta +y'\cos \Theta )\end{matrix}}\right.$

et donc

$\left\{{\begin{matrix}x_{\mathrm {c} }=x-s(x'\cos \Theta +y'\sin \Theta )\\y_{\mathrm {c} }=y-s(x'\sin \Theta +y'\cos \Theta )\end{matrix}}\right.$

Pour la recherche, on balaie également les valeurs s et Θ. La matrice d'accumulation représente donc la densité de valeurs dans l'espace (x_c, y_c, Θ, s).

Avantages et inconvénients

Avantages :

• concept simple ;
• rapidité (par échantillonnage stochastique) ;
• robustesse au bruit ;
• aisément extensible à d'autres domaines que l'imagerie.

Inconvénients :

• problème de l'homogénéité de l'espace, de sa quantification ;
• problème de la preuve de convergence de l'algorithme.

Lien externe

• (en) Ballard and Brown, « Generalized Hough Transform (GHT) » [PDF]