DETECTION D'AXES DE SYMETRIE DANS UNE IMAGE PAR TRANSFORMATION DE HOUGH
INTRODUCTION
Objectif
Pour des objets géométriques simples, des polygones par exemple, la notion d'axe de symétrie est bien définie. Soit une droite donnée, elle est axe de symétrie si l'image de l'objet par symétrie d'axe cette droite est identique à lui-même. Mais déjà une première difficulté apparaît : comment détermine-t-on cette droite en premier lieu ?
En essayant de rester général, nous allons prendre les points significatifs de l'objet, ses sommets, deux par deux et prendre leur médiatrice puis tester lesquelles des médiatrices ainsi définies vérifient le critère d'invariance ci-dessus(fig 1.1).
Eventuellement, aucune ne marchera et on en déduira que l'objet n'a pas d'axe de symétrie (fig 1.2). Au contraire, on peut en trouver plusieurs (fig 1.3).
Pour des images réelles, la tâche est plus difficile car elles ne sont en général qu'approximativement symétriques. De plus, que sont les "points significatifs" lorsqu'on n'a pas affaire à un polygone ? Pourtant, il est tentant d'associer des axes de symétrie à de nombreux objets courants (bâtiments, visages,...).
La connaissance de ces axes pourrait, par exemple, servir à retrouver l'orientation d'un objet dans une image et aider au recalage entre différentes images du même objet.
En fait, le but de ce projet est de généraliser l'idée présentée pour les objets simples au cas des images réelles en utilisant la transformation de Hough et de montrer qu'il est possible d'exhiber de manière automatique les éventuels axes de symétrie d'une image.
Transformation de Hough
Cette présentation est tirée du cours de traitement des images de l'E.N.S.T.
Nous nous limitons à la transformation dite "m à 1".
La transformation de Hough est un outil de traitement du signal dont la fonction première est de trouver des droites avec certaines propriétés. Or un problème mieux connu est celui de la détection de nuage de points groupés dans le plan.
Le but de la transformation est alors d'associer à une droite un point dans un espace de paramètre à deux dimensions. Par exemple, à la droite d'équation cartésienne y = ax + b, on associe le point de coordonnées (a,b).
L'application la plus courante pour illustrer la transformation de Hough est alors la suivante. Soit un ensemble de points correspondant au contour bruité d'un polygone, comment retrouver les segments correspondants (fig 1.4) ?
Dans la transformation m à 1, on prend tous les couples de points et on leur associe la droite correspondante dans l'espace de Hough (fig 1.5). Pour N points, il faut donc calculer N(N-1)/2 droites.
On trouve alors deux nuages de points correspondants aux deux segments originaux. Les algorithmes de classification classiques permettent dans déterminer les paramètres des droites cherchées.
fig 1.4
| 
fig 1.5
|
En pratique, l'espace de Hough est discrétisé en cases qui vont comptabiliser le nombre de droites dont les paramètres entrent dans ces cases. On dit que chaque droite vote pour une case particulière.
Différents problèmes apparaissent alors.
Dans un premier temps, quelle discrétisation choisir ? Des cases trop petites accroîtront le nombre de calcul et disperseront les points sur un grand nombre de cellules rendant difficile de trouver la case pertinente (dans l'exemple précédent, celle correspondant à un segment dans l'image). Au contraire, des cases trop grandes réduisent la précision sur les paramètres de la droite.
Dans un deuxième temps, la représentation cartésienne n'est pas homogène au sens où 25% des droites ont un a entre 0 et 1 et 25% entre 1 et l'infini. Une discrétisation uniforme ne serait donc pas adaptée.
En fait, la paramétrisation dite normale des droites (angle de la normale avec l'axe des abscisses, distance à l'origine : fig 1.6) permet de découper l'espace de Hough en accumulateurs identiques car toutes les droites y sont équiréparties.
fig 1.6
|
Nous avons retenu cette représentation, bien qu'elle demande quelques précautions à l'utilisation (notamment pour les droites passant par l'origine pour lesquelles l'angle normal n'est connu qu'à Pi près).
Enfin, pour les images que nous avons étudiées (quelques centaines de points de côté), nous nous sommes donnés une précision du pixel pour la distance à l'origine (limitée par la diagonale de l'image) et de un degré pour l'angle normal (de 0 à 360 degrés). La taille de l'espace de représentation est alors largement à la portée des systèmes de traitement courants.
Retour au sommaire
mars 2001
