Il s'agit de reprendre la méthode décrite en introduction pour des objets simples (polygones) et de l'appliquer à des images réelles.
Pour cela, on restreint ces images à un ensemble de "points significatifs" beaucoup moins nombreux mais porteurs de l'information géométrique (les symétries éventuelles). Il s'avère que les contours de l'image répondent très bien à ces contraintes.
Ensuite, on considère tous les couples de points et on calcule leur médiatrice. Mais contrairement au cas des objets simples, on ne vérifie pas une invariance par symétrie, même approchée mais on se contente d'accumuler les médiatrices dans l'espace de Hough. Dans le cas idéal, c'est-à-dire celui où il y a un vrai axe de symétrie, il sera accumulé N/2 fois où N est le nombre de points du contour. En effet N/2 points sont les symétriques des N/2 autres par une symétrie axiale dont l'axe est leur médiatrice.
Les autres médiatrices sont réparties de manière à peu près aléatoires dans l'espace. En pratique, si des axes de symétrie existent, ils correspondront donc à des maxima locaux dans l'espace de Hough.
La dernière étape consiste donc à détecter ces zones d'accumulation par des méthodes inspirées des algorithmes de classification et, plus précisément, à donner les droites correspondant à des maxima locaux et donc à des axes de symétrie.
L'objectif du projet n'est pas d'étudier les méthodes de détection des contours. Nous allons juste préciser nos besoins et y confronter les principales techniques. Nos codes C ou MATLAB travaillent à partir des contours calculés par la fonction EDGE de MATLAB.
Comme nous l'avons dit plus haut, nous avons besoin d'un petit nombre de points, pour réduire de manière importante le temps de calcul (ce nombre devant rester significatif pour trouver des axes pertinents). En outre, nous avons besoin de contours fiables, non bruités. Voici sur une photo de Saturne (fig 2.1) les résultats des principales méthodes avec les seuils optimisés par la fonction EDGE (figures 2.1 à 2.6) :
Saturne originale fig 2.1
Sobel, seuil = 0.0810 fig 2.2
Prewitt, seuil = 0.0792 fig 2.3
Roberts, seuil = 0.1141 fig 2.4
Laplacien de gaussienne, seuil = 0.0033 fig 2.5
Passage par zéro, seuil = 0.0033 fig 2.6
Canny, seuil = 0.0938 fig 2.7
Les méthodes de Prewitt et Roberts donnent des contours discontinus peu exploitables car perdant partiellement la symétrie de l'image. Au premier abord, les filtres 2.5 à 2.7 comportent trop de points et Sobel semble être le plus intéressant. Mais si on augmente alors manuellement les seuils des différentes méthodes, on constate que seul Canny fournit des contours stables avec peu de points (fig 2.9) alors qu'avec Sobel, les contours finissent par se déconnecter (fig 2.8).
Sobel, seuil = 0.1 fig 2.8
Canny, seuil = 0.6 fig 2.9
Finalement, nous avons retenu la méthode de Canny avec des seuils typiques de l'ordre de 0,5. Les contours obtenus sont à la fois fidèle à la géométrie originale de l'image et relativement "pauvres" en points, permettant ainsi des calculs rapides.
A ce stade, nous prenons tous les couples de points du contour calculé et déterminons leur médiatrice comme sur la figure 2.10.
fig 2.10
Chaque médiatrice calculée correspond à une case de l'espace de Hough (discrétisé à un degré et un pixel près). Une fois l'accumulation terminée, on obtient le type de représentation de la figure 2.11 :
fig 2.11
A l'oeil, il est facile de repérer deux maxima locaux important dont on peut vérifier qu'ils correspondent à deux axes de symétrie de l'image. En revanche, les trouver de manière automatique est moins évident (la forme en arche de sinusoïde correspond à l'existence d'un point commun à de nombreuses médiatrices, c'est-à-dire un centre de symétrie mais nous ne nous y intéresserons pas dans cette étude).
En pratique, l'accumulateur obtenu (comme celui de la figure 2.11) présente un grand nombre de maximums locaux. Nous voulons ne garder que ceux qui sont statistiquement signifiants et qui appartiennent donc à des régions plus denses en droites. Il faut donc délimiter ces régions, c'est-à-dire faire une classification de la transformée de Hough et en extraire le point le plus "significatif".
A ce stade, la reconnaissance des formes nous fournit de nombreux outils.
Le plus général est l'algorithme isodata. Il permet d'ajuster de manière dynamique et automatique le nombres de classes (de régions) pertinentes dont le centre est le point moyen. Nous l'avons implanté tel quel à ceci près qu'on s'autorise éventuellement une classe de rejet et qu'à l'issue des itérations, on prend comme paramètres des axes les points réalisant le maximum de chaque classe plutôt que le point moyen.
Le découpage obtenu permet d'obtenir des maxima locaux robustes. C'est-à-dire qu'il n'y a jamais deux maxima trop proches correspondant à une erreur près à un même axe.
Cependant, cet algorithme, même si en pratique 2 ou 3 itérations suffisent, est gourmand en calcul, difficile à mettre en oeuvre et requière un grand nombre de paramètres de contrôles. Pour réduire le temps de calcul, on pourrait réduire l'espace de travail par des quadtrees au détriment de la résolution puis affiner au voisinage des maxima des classes.
Mais cette méthode reste bien trop générale pour notre cas particulier et nous avons entrepris de la simplifier. En particulier, nous n'autorisons plus le regroupement de classe et nous n'utilisons qu'un seul paramètre de contrôle : DistMax. A la fin, nous trions les maxima trouvés et retenons ceux de valeur la plus élevée. De plus nous réduisons éventuellement le nombre de points dans l'espace de Hough en effectuant un seuillage éliminant une certaine proportion de ces points.
En outre, les centres des classes ne sont plus les points moyens mais les maxima sur la classe. Enfin, les objets finis ne pouvant avoir deux axes de symétrie parallèle, la distance angulaire devrait suffire à séparer les maxima. Faire intervenir le paramètre Ro dans la distance ne semble pas utile.
L'algorithme est alors le suivant :
initialisation : le maximum global constitue la première classe.
répéter :
pour tous les points d'accumulateur non nul
calculer la distance à toutes les classes existantes
si la plus petite distance est inférieure à DistMax, placer le point dans la classe qui la réalise
sinon, le point est le centre d'une nouvelle classe
remettre à jour les centres de classes
tant que des classes sont crées
trier les centres par valeurs décroissantes
conserver les n premiers centres voulus/pertinents
Il s'avère que cet algorithme est rapide et donne en général les axes attendus. Mais en réalité, il n'interdit pas à deux maxima d'être plus proche que DistMax. On risque alors de détecter deux droites proches correspondant en fait à un même axe. Ce phénomène est décrit dans les figures 2.12 à 2.14.
première itération fig 2.12
deuxième itération fig 2.13
mise à jour des centres fig 2.14
Nous avons ici trois points de valeurs décroissantes (numérotés 1, 2 et 3) ; 1 est un maximum. Dans 2.12, il n'existe qu'une classe "centrée" sur 1 de "rayon" DistMax. Le point 3 est trop loin de 1 pour être intégré à sa classe. Il crée la sienne. A l'itération 2, les points sont classés en fonction de leur distance au centre des classes. Ainsi, le point 3, étant plus près de 2 que de 1, passe dans la classe de 2. Enfin, fig 2.14, on met à jour les centres de classes. Comme 2 est plus grand que 3, il devient le nouveau centre de la classe. On a ainsi définit un processus qui peut générer des maxima (ici 1 et 2) qui peuvent être plus proches que DistMax.
Pour supprimer ce problème, il faudrait autoriser de nouveau les regroupements de classes, ce qui nous ramène à l'algorithme précédent trop lourd.
En fait, nous voulions simplement introduire dans notre algorithme une connaissance a priori sur les axes de symétrie d'une image. En effet, dans une image naturelle, la plupart des objets auront au plus deux axes de symétrie d'angles très différents (à l'exception des roues et autres objets circulaires), ils ont donc des axes bien séparés en angle. On modifie donc l'algorithme précédent pour réellement exclure tout maximum à moins de DistMax d'un maximum plus important.
Quand on a deux axes trop proches on prend ainsi l'axe d'accumulation maximale dans l'espace de Hough.
En pratique cela consiste à initialiser la méthode de la même façon mais de ne plus regarder les points déjà classés. On prend alors comme centre d'une nouvelle classe le maximum sur les points restants. Il est facile de voir que les maxima successifs obtenus sont décroissants. On peut donc interrompre la classification dès qu'on a trouvé le nombres de maxima/axes attendus.
L'algorithme de segmentation définitif est donc :
initialisation : le maximum global constitue la première classe.
répéter :
ClasseCreee = 0
pour tous les points d'accumulateur non nul et non marqués
calculer la distance à toutes les classes existantes
si la plus petite distance est inférieure à DistMax
placer le point dans la classe qui la réalise
marquer le point
sinon,
ClasseCreee = 1
le point est mis dans la classe de rejet
incrémenter le nombre de maxima trouvés
remettre à jour les centres de classes (y compris pour la classe de rejet, son centre devient centre d'une vraie classe)
tant qu'une classe est crée et que le nombre de maxima attendus n'est pas atteint
donner les paramètres des maxima calculés
Cet algorithme a le double avantage de donner de localiser des maxima bien différenciés tout en réduisant l'espace exploré au fur et à mesure des itérations. On a donc un calcul rapide. Donnant en principe des axes fiables
Les résultats de cette méthode sont discutés dans la section suivante.
