TP 2 : Détection de formes : Transformée de Hough

Introduction

La transformée de Hough est une méthode permettant de détecter des formes dans une image. La méthode « classique » permet de trouver des formes pouvant être décrites de manière paramétrique, comme par exemple les droites ou les cercles. C’est une méthode très utilisée en analyse d’image pour extraire de l’information dans une image. Le principe qui sous-tend la transformée de Hough est qu'il existe un nombre infini de lignes qui passent par un point, dont la seule différence est l'orientation (l'angle).L’objectif de ce TP est d’implémenter la transformée pour détecter des droites, puis d’améliorer le résultats avec un seuillage « intelligent » des droites. Enfin, nous devons étendre ce principe à la détection de cercles.

Principe

Le principe général de la transformée de Hough est d'établir une projection

entre l'espace de l'image et un espace de paramètres représentatifs de la forme

recherchée. Dans le cas d’une droite par exemple, nous allons avoir une orientation et une longueur. Dans ce nouvel espace, nous allons comparer les probabilités de présences des droites dans l’image. Il s’agit donc d’un algorithme dit « brute force », qui teste absolument tous les cas possibles. Sa complexité et son temps de traitement sont donc assez élevé. Il est possible d’utiliser la transformée de Hough pour détecter des formes plus arbitraires, du moment qu’il est possible de décrire cette forme avec un nombre fixé de paramètres. Nous pouvons noter que le nombre de paramètres nous donne la dimension de l’accumulateur de Hough.

Nous allons principalement voir le fonctionnement de l’algorithme sur la détection de droites, celui-ci pouvant se généraliser pour les autres cas. Afin de déterminer que deux points se trouvent sur une même droite potentielle, nous devons créer une représentation de la droite qui permette une comparaison dans ce contexte.

Paramétrisation de droites

La forme la plus classique pour représenter analytiquement une droite est la forme y = ax + b. Elle n’est cependant pas sans problème car pour les droites verticales et horizontales, nous avons des valeurs infinies pour a et b. pour pallier à ce problème, nous allons utiliser une représentation plus puissante pour les droites.

Suivant cette représentation, une droite est définie par rho = x * cos (theta) + y * sin (theta)

L’implémentation de la transformée de Hough est assez directe. Nous utilisons donc des structures de données très classiques provenant de la STL pour nos résultats intermédiaires. Nous pouvons par contre nous attarder sur l’accumulateur de Hough qui est une étape crucial de l’algorithme.

Structure de données

L’accumulateur est un tableau qui va accueillir toutes les droites possibles de l’image. La première chose à faire est donc de déterminer la taille de ce tableau. Pour cela, nous devons considérer les deux variables rho et theta qui nous permettent de paramétrer nos droites. Nous avons vu en cours que parcourir theta de –pi /2 à pi et rho de 0 à la diagonale de l’image permet de décrire complètement l’espace des droites. En effet, par symétrie nous avons tous les cas qui peuvent sembler manquant au premier abord dans cette description. Nous avons l’intervalle à parcourir mais comment allons nous le discrétiser ? Par convention, deux lignes sont différentes dans un espace discret si elle sont espacés de racine de deux. Quand à theta, il s’agit de la tranche totale d’angle parcourue divisé par la diagonale.

Accumulation des droites

Cette étape est très lente et ne doit donc pas être effectué plus d’une fois par image. Il s’agit de parcourir l’image à la recherche de pixels contours, puis pour chaque pixel trouvé, nous allons tester toutes les droites pouvant passer par ce point. Chaque droite se voit crédité d ‘un vote dans l’accumulateur. A la fin de cette étape, chaque case de l’accumulateur représente le nombre de vote totales pour la droite caractérisée. Le résultat peut être visualisé comme une image en niveau de gris visuellement intéressante.

Accumulateur de Hough sur arch1.pgm. Plus un pixel est lumineux, plus la probabilité que la droite associée soit présente est grande.

En calculant la valeur de rho pour chaque theta, nous obtenons une sinosoïde unique appelée espace de Hough. L’image de l’accumulateur peut donc être vue comme une succession de sinusoïdes dont les intersections représentent les droites reliants les 2 points qui sont à l’origine de ces sinusoïdes.

Une propriété intéressante qui en découle est que le nombre de votes pour une droite m correspond au nombre de points contours sur cette droite. Plus la case possède une valeur importante, meilleure est la probabilité que cette droite existe dans l’image. Nous n’avons cependant toujours pas de données exploitables, car nous voyons bien que dessiner la droite associée à chaque case de l’accumulateur possédant au moins 1 vote conduirait à un nombre de droite à dessiner trop important. Comme souvent en analyse d’image, le réflexe qui nous vient à l’esprit est d’effectuer un seuillage qui partitionnera l’espace de Hough en droites valides et droites non retenues.

Seuillage

La représentation en mémoire des droites nous permet de faire notre seuillage facilement. Si une droite a un nombre de vote dans l’accumulateur inférieur au seuil, alors cette droite ne sera pas considérée. Dans notre implémentation, c’est la case de l’accumulateur qui est modifiée ( = 0). Nous conservons une copie de l’accumulateur original pour le cas ou l’utilisateur veut procéder par étapes sur les seuils. Cette méthode est très rapide mais nous donne des résultats mitigés. En effet, par la nature de la distribution des votes dans l’espace de Hough, certaines droites qui sont pourtant évidentes pour l’œil humain ne seront pas prises en compte suivant le seuillage effectué. Nous sommes donc parfois obligé de descendre ce seuil très bas pour pouvoir avec une ligne représentative de chaque droite dans l’image. Cela pose 2 problèmes majeurs. Tout d’abord, plus le seuil est bas, plus le nombre de droites à prendre en compte est important, ralentissant la suite du traitement. Mais surtout, ces droites supplémentaires sont pour la majeur partie, des droites d’un même contour mais non maximum. Ce sont des lignes qui ont un theta très proches. De plus, ce seuillage est manuel, donc difficile à trouver et à systématiser sur différentes images.

Le seuillage permet de ne conserver que quelques droites parmis les centaines voir milliers contenues dans l’accumulateur. Cependant pour obtenir toutes les droites intéressantes, l’abaissement du seuil provoque du bruit localement.

Nous avons donc du mettre en place un autre type de seuillage qui doit permettre de ne pas tenir compte des droites sensiblement proches. Là encore, la représentation dans l’espace de Houghet sa corrélation avec l’espace image nous permettent de trouver localement des maximums dans l’accumulateur pour obtenir un meilleur seuillage des droites. Pour avoir un meilleur contrôle, nous avons laissé le choix de la taille du voisinage à considérer pour un maximum local, ainsi que le nombre de maximum locaux à traiter. Dans la pratique, la meilleur solution consiste à appliquer les deux seuillages l’un après l’autre. La tâche la plus ardue est de trouver la bonne taille de fenêtre avec cette méthode, car si elle est trop grosse, nous risquons d’éliminer un autre maximun.

Le seuillage global permet de ne conserver que les droites significatives. Le seuillage local lui, ne conserve parmi ces droites significatives que celles qui sont des maximums locaux.

Accumulateur sur lequel nous avons appliqué un seuillage local des maximums. Nous pouvons voir l’effet de bloc autour du maximum relatif à la taille du voisinage choisi.

Dessin

Maintenant que nous avons sélectionné nos droites, nous devons repasser dans l’espace de l’image pour pouvoir les tracer, car nous ne connaissons que les couples rho theta symbolisant la droite dans l’espace de Hough. Pour cela, nous allons calculer les intersections des droites avec chacun des bords de l’image. Il est facile de savoir si l’intersection est bonne si le point est effectivement dans l’image. Si la coordonnée dépasse la taille de l’image ou est inférieur à zéro alors l’intersection avec ce bord n’existe pas. Nous avons donc 4 équations à résoudre par droite. Une fois 2 points trouvés, nous traçons une droite sur l’image entre ces 2 points grâce à l’algorithme de Bresenham.

La dernière étape de l’algorithme consiste à rendre des segments plutôt que des droites pour mieux représenter l’information de l’image. Cette étape est relativement délicate. La première idée est de n’afficher les points de la droite que si ils représentent un pixel contour. Malheureusement cette approche n’est pas raisonnable car elle nécessite que les droites détectées par Hough soient parfaites en terme d’orientation, ce qui n’est pas toujours le cas.

Notre approche consiste à garder le concept de points contours. Nous décidons de conserver un pixel si celui-ci est proche d’un contour. Pour pallier aux problèmes de trous qui peuvent survenir, lorsque la détection de contour précédente n’était pas parfaite par exemple, nous calculons la distance euclidienne jusqu’au prochain bon point appartenant à la droite. Si elle est inférieur à un seuil passé en paramètre à la fonction, alors nous comblons le trou en dessinant la droite dans cet intervalle. Dans notre implémentation, nous n’utilisons qu’une fois Bresenham par droite, les points de la droite sont enlevés de la liste quand ils sont refusés.

Généralisation aux cercles

Pour les cercles le principe est identiques, sauf que l’accumulateur n’aura plus 2 dimensions mais 3. En effet, nous pouvons représenter un cercle de manière paramétrique avec 3 valeurs, le rayon, et le centre du cercle en x et y. L’équation d’un cercle est (x – a)² + (y – b)² = r avec a et b le centre du cercle. Nous remplissons donc l’accumulateur de la même manière, seule la méthode de dessin change. Il est possible d’utiliser un algorithme incrémentale, soit Bresenham pour les cercles.

Conclusion

L’algorithme de Hough pour la détection de formes peut donner de bons résultats sur un problème compliqué. Cependant, et peut être devons nous blâmer notre implémentation, la complexité des seuils à fournir en paramètre rend l’algorithme fastidieux. Nous pouvons difficilement avoir des paramètres génériques s’appliquant dans tout type d’image. De même, sa mise en place est particulièrement lourde, que ce soit en mémoire (taille de l’accumulateur) ou en temps de calcul.

Nous aurions aimer pouvoir intégrer une méthode qui prenne en compte le gradient en un point car il est inutile de tester les droites dont l’angle est proche de celui du gradient. L’algorithme de Hough reste pour nous une méthode nécessitant d’effectuer un traitement en sortie pour sélectionner les bonnes droites dans le cas générale. Nous pourrions par exemple l’utiliser pour créer des ensembles de droites choisis suivant leur orientation pour calculer les points de fuite dans une image.

Démonstration