Transformée de Hough

Utilisation de la direction du gradient pour réduire le nombre de votesEdit

Une amélioration suggérée par O’Gorman et Clowes peut être utilisée pour détecter des lignes si l’on tient compte du fait que le gradient local de l’intensité de l’image sera nécessairement orthogonal au bord. Comme la détection des bords implique généralement le calcul de la magnitude du gradient d’intensité, la direction du gradient est souvent trouvée comme un effet secondaire. Si un point donné de coordonnées (x,y) se trouve effectivement sur une ligne, alors la direction locale du gradient donne le paramètre θ correspondant à ladite ligne, et le paramètre r est alors immédiatement obtenu. (Shapiro et Stockman, 305) La direction du gradient peut être estimée à 20° près, ce qui raccourcit le tracé de la sinusoïde de 180° à environ 45°. Cela réduit le temps de calcul et a l’effet intéressant de réduire le nombre de votes inutiles, améliorant ainsi la visibilité des pics correspondant à des lignes réelles dans l’image.

Transformation de Hough basée sur le noyau (KHT)Edit

Fernandes et Oliveira ont suggéré un schéma de vote amélioré pour la transformée de Hough qui permet à une implémentation logicielle d’atteindre des performances en temps réel même sur des images relativement grandes (par exemple, 1280×960). La transformée de Hough basée sur le noyau utilise le même ( r , θ ) {\displaystyle (r,\theta )}.

paramétrage proposé par Duda et Hart mais opère sur des grappes de pixels approximativement colinéaires. Pour chaque cluster, les votes sont effectués à l’aide d’un noyau elliptique-gaussien orienté qui modélise l’incertitude associée à la ligne la mieux ajustée par rapport au cluster correspondant. Cette approche permet non seulement d’améliorer considérablement les performances du schéma de vote, mais aussi de produire un accumulateur beaucoup plus propre et de rendre la transformation plus robuste à la détection de lignes parasites.

3-D Kernel-based Hough transform for plane detection (3DKHT)Edit

Limberger et Oliveira ont suggéré une technique déterministe pour la détection de plans dans des nuages de points non organisés dont le coût est n log ( n ) {\displaystyle n\log(n)}.

dans le nombre d’échantillons, atteignant des performances en temps réel pour des ensembles de données relativement importants (jusqu’à 10 5 {\displaystyle 10^{5}}.

points sur un CPU de 3,4 GHz). Il est basé sur une stratégie de vote rapide de la transformée de Hough pour les régions planaires, inspirée de la transformée de Hough basée sur un noyau (KHT). Cette transformée de Hough 3D basée sur le noyau (3DKHT) utilise un algorithme rapide et robuste pour segmenter des grappes d’échantillons approximativement coplanaires, et émet des votes pour les grappes individuelles (plutôt que pour les échantillons individuels) sur un ( θ , ϕ , ρ {\displaystyle \theta ,\phi ,\rho }

) accumulateur sphérique en utilisant un noyau gaussien trivarié. Cette approche est plus rapide de plusieurs ordres de grandeur que les techniques existantes (non déterministes) de détection des plans dans les nuages de points, telles que RHT et RANSAC, et s’adapte mieux à la taille des ensembles de données. Elle peut être utilisée avec toute application qui nécessite une détection rapide des caractéristiques planes sur de grands ensembles de données.

Transformée de Hough des courbes, et sa généralisation pour les formes analytiques et non analytiquesEdit

Bien que la version de la transformée décrite ci-dessus ne s’applique que pour trouver des lignes droites, une transformée similaire peut être utilisée pour trouver toute forme qui peut être représentée par un ensemble de paramètres. Un cercle, par exemple, peut être transformé en un ensemble de trois paramètres, représentant son centre et son rayon, de sorte que l’espace de Hough devient tridimensionnel. Des ellipses et des courbes arbitraires peuvent également être trouvées de cette façon, comme toute forme facilement exprimée comme un ensemble de paramètres.

La généralisation de la transformée de Hough pour détecter des formes analytiques dans des espaces ayant n’importe quelle dimensionnalité a été proposée par Fernandes et Oliveira. Contrairement aux autres approches basées sur la transformée de Hough pour les formes analytiques, la technique de Fernandes ne dépend pas de la forme que l’on veut détecter ni du type de données d’entrée. La détection peut être orientée vers un type de forme analytique en changeant le modèle de géométrie supposé où les données ont été encodées (par exemple, espace euclidien, espace projectif, géométrie conforme, etc.), tandis que la formulation proposée reste inchangée. En outre, elle garantit que les formes prévues sont représentées avec le plus petit nombre possible de paramètres, et elle permet la détection simultanée de différents types de formes qui s’adaptent le mieux à un ensemble d’entrées de différentes dimensions et de différentes définitions géométriques (par exemple, la détection simultanée de plans et de sphères qui s’adaptent le mieux à un ensemble de points, de lignes droites et de cercles).

Pour les formes plus compliquées dans le plan (c’est-à-dire, formes qui ne peuvent pas être représentées analytiquement dans un certain espace 2D), la transformée de Hough généralisée est utilisée, ce qui permet à une caractéristique de voter pour une position, une orientation et/ou une mise à l’échelle particulière de la forme en utilisant une table de consultation prédéfinie.La transformée de Hough accumule les contributions de tous les pixels dans le bord détecté.

Processus de détection de cercleModifier

La modification de l’algorithme pour détecter des formes circulaires au lieu de lignes est relativement simple.

• D’abord, nous créons l’espace accumulateur, qui est composé d’une cellule pour chaque pixel. Initialement, chaque cellule est fixée à 0.
• Pour chaque point de bord (i, j) dans l’image, incrémenter toutes les cellules qui selon l’équation d’un cercle ( i – a ) 2 + ( j – b ) 2 = r 2 {\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}.
  

  pourrait être le centre d’un cercle. Ces cellules sont représentées par la lettre a {\displaystyle a}

  

  dans l’équation.

• Pour chaque valeur possible de a {\displaystyle a}
  

  trouvée à l’étape précédente, trouver toutes les valeurs possibles de b {\displaystyle b}

  

  qui satisfont l’équation.

• Recherche des maxima locaux dans l’espace de l’accumulateur. Ces cellules représentent les cercles qui ont été détectés par l’algorithme.

Si l’on ne connaît pas au préalable le rayon du cercle que l’on cherche à localiser, on peut utiliser un espace accumulateur tridimensionnel pour rechercher des cercles de rayon arbitraire. Naturellement, cela est plus coûteux en calcul.

Cette méthode peut également détecter des cercles qui sont partiellement à l’extérieur de l’espace accumulateur, tant qu’une partie suffisante de la surface du cercle est encore présente à l’intérieur de celui-ci.

Détection d’objets 3D (Plans et cylindres)

La transformée de Hough peut également être utilisée pour la détection d’objets 3D dans des données de distance ou des nuages de points 3D. L’extension de la transformée de Hough classique pour la détection de plans est assez simple. Un plan est représenté par son équation explicite z = a x x + a y y + d {\displaystyle z=a_{x}x+a_{y}y+d}.

pour laquelle on peut utiliser un espace de Hough 3D correspondant à un x {\displaystyle a_{x}}.

, a y {\displaystyle a_{y}}

et d {\displaystyle d}

. Cette extension souffre des mêmes problèmes que son homologue 2D, c’est-à-dire que les plans presque horizontaux peuvent être détectés de manière fiable, tandis que les performances se détériorent lorsque la direction du plan devient verticale (grandes valeurs de a x {\displaystyle a_{x}}.

et a y {\displaystyle a_{y}}

amplifient le bruit dans les données). Cette formulation du plan a été utilisée pour la détection de plans dans les nuages de points acquis à partir d’un balayage laser aéroporté et fonctionne très bien car dans ce domaine, tous les plans sont presque horizontaux.

Pour la détection généralisée des plans à l’aide de la transformée de Hough, le plan peut être paramétré par son vecteur normal n {\displaystyle n}.

(en utilisant les coordonnées sphériques) et sa distance à l’origine ρ {\displaystyle \rho }.

résultant en un espace de Hough tridimensionnel. Il en résulte que chaque point des données d’entrée vote pour une surface sinusoïdale dans l’espace de Hough. L’intersection de ces surfaces sinusoïdales indique la présence d’un plan. Une approche plus générale pour plus de 3 dimensions nécessite une heuristique de recherche pour rester réalisable.

La transformée de Hough a également été utilisée pour trouver des objets cylindriques dans des nuages de points en utilisant une approche en deux étapes. La première étape trouve l’orientation du cylindre et la deuxième étape trouve la position et le rayon.

Utiliser des caractéristiques pondéréesModifier

Un détail de variation commun. C’est-à-dire que trouver les bacs avec le plus grand nombre dans une étape peut être utilisé pour contraindre la gamme de valeurs recherchées dans la prochaine.

Espace de paramètres soigneusement choisiEdit

Un espace de paramètres à haute dimension pour la transformée de Hough est non seulement lent, mais s’il est mis en œuvre sans réflexion préalable, il peut facilement dépasser la mémoire disponible. Même si l’environnement de programmation permet l’allocation d’un tableau plus grand que l’espace mémoire disponible par le biais de la mémoire virtuelle, le nombre de changements de page requis pour cela sera très exigeant car le tableau accumulateur est utilisé de manière aléatoire, s’arrêtant rarement dans une mémoire contiguë alors qu’il saute d’indice en indice.

Considérez la tâche de trouver des ellipses dans une image 800×600. En supposant que les rayons des ellipses sont orientés le long des axes principaux, l’espace des paramètres est quadridimensionnel. (x,y) définit le centre de l’ellipse, et a et b désignent les deux rayons. En permettant au centre d’être n’importe où dans l’image, on ajoute la contrainte 0<x<800 et 0<y<600. Si l’on donne aux rayons les mêmes valeurs que les contraintes, ce qui reste est un tableau d’accumulateur peu rempli de plus de 230 milliards de valeurs.

Un programme ainsi conçu a peu de chances d’être autorisé à allouer suffisamment de mémoire. Cela ne signifie pas que le problème ne peut pas être résolu, mais seulement qu’il faut trouver de nouvelles façons de contraindre la taille du tableau d’accumulateurs, ce qui le rend réalisable. Par exemple :

1. S’il est raisonnable de supposer que les ellipses sont chacune contenues entièrement dans l’image, la plage des rayons peut être réduite. Le plus grand des rayons peut être est que le centre de l’ellipse est au centre de l’image, permettant aux bords de l’ellipse de s’étirer vers les bords. Dans ce cas extrême, les rayons ne peuvent être que la moitié de la magnitude de la taille de l’image orientée dans la même direction. Réduire la plage de a et b de cette façon réduit le tableau d’accumulateurs à 57 milliards de valeurs.
2. Trader la précision pour l’espace dans l’estimation de la transformée de Hough accumule les contributions de tous les pixels dans le bord détecté. La transformée de Hough accumule les contributions de tous les pixels du bord détecté. le centre : Si l’on prédit que le centre est décalé de 3 sur les axes x et y, cela réduit la taille du tableau d’accumulateurs à environ 6 milliards de valeurs.
3. Echange de précision contre de l’espace dans l’estimation des rayons : Si les rayons sont estimés être chacun erronés de 5, une nouvelle réduction de la taille du tableau d’accumulateurs se produit, d’environ 256 millions de valeurs.
4. Cadrer l’image sur les zones d’intérêt. Cela dépend de l’image, et est donc imprévisible, mais imaginez un cas où tous les bords d’intérêt d’une image se trouvent dans le quadrant supérieur gauche de cette image. Le tableau d’accumulateurs peut être réduit encore plus dans ce cas en contraignant les 4 paramètres par un facteur de 2, pour un facteur de réduction total de 16.

En appliquant juste les trois premières de ces contraintes à l’exemple énoncé à propos, la taille du tableau d’accumulateurs est réduite par presque un facteur de 1000, le ramenant à une taille qui est beaucoup plus susceptible de tenir dans la mémoire d’un ordinateur moderne.

Algorithme efficace de détection d’ellipseEdit

Yonghong Xie et Qiang Ji donnent une manière efficace d’implémenter la transformée de Hough pour la détection d’ellipse en surmontant les problèmes de mémoire. Comme discuté dans l’algorithme (à la page 2 de l’article), cette approche utilise seulement un accumulateur unidimensionnel (pour le petit axe) afin de détecter les ellipses dans l’image. La complexité est O(N3) dans le nombre de points non nuls dans l’image.