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

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 :
  ${\displaystyle \left\{{\begin{matrix}x'_{i}=-\rho _{i}\cdot \cos \alpha _{i}\\y'_{i}=-\rho _{i}\cdot \sin \alpha _{i}\end{matrix}}\right.}$
  et
  ${\displaystyle \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.

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.

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) :

${\displaystyle \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

${\displaystyle \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).