Extraction des contours et de la direction des contours
1.Extraction des contours
L'extraction des contours est réalisée grâce à
un masque de sobel, en seuillant la fonction g=|sx|+|sy|. Puis on retire
les pixels qui ne sont pas maxima locaux dans la direction du contours,
pour cela on compare la valeur d'un pixel à ses deux voisins dans
la direction du contour.
La direction du contour est obtenue par le rapport le la reponse du
masque de Sobel dans les deux directions.
Extraction des contours et de la direction des contours
2.Traitement geometrique
Une ellipse est définie comme l'ensemble des points vérifiant l'équation :
La résolution directe de cette equation demande la résolution d'un système de 5 équations non linéaires . L'approche retenue qui consiste a faire une RHT (Randomized Hough Transform) demande que le calcul des paramètres d'une ellipse se fasse linéairemement. Il est aussi possible d'utiliser l'information des tangentes pour n'utiliser que trois points et non pas cinq. On décompose donc le calcul des paramètres d'une ellipse en deux phases : On commence par estimer la position du centre en utilisant une propriété geométrique des tangentes. Ensuite on calcule la forme de l'ellipse.
Position du centre :
Le calcul de la position du centre de l'ellipse utilise la propriété
geométrique de l'ellipse suivante : étant donné deux
tangentes à l'ellipse aux points x1 et x2 se coupant au point L,
le centre de l'ellipse se trouve sur la droite qui passe par le milieu
de x1x2 et L. En considérant trois points on peut donc calculer
la position du centre O de l'ellipse.
Construction du centre d'une ellipse à partir de trois points et tangentes
Remarque : la droite OL partage l'angle (L,x1,x2) en deux, c'est un
moyen d'obtenir le centre sans calculer la position du point m, c'est ce
que nous avons utilisé au debut mais ca s'est avéré
plus sensible au bruit que de calculer la position du point m. La position
des contours est plus fiable que la mesure d'angle.
Nous avons testé une variante de cette methode qui permet d'obtenir
le centre avec seulement deux points: dans un accumulateur de meme taille
que l'image, on incrémente tous les pixels correspondant à
la droite OL.
Forme de l'ellipse :
Une fois la position du centre de l'ellipse connue, on se place dans
le repère lié au centre de l'ellipse. Dans ce repère
l'equation d'une ellipse s'écrit:
Soit en considérant trois point, sous forme matricielle:
Les parametres a,b,c s'obtiennent par inversion du système.
Paramètres utilisés :
Il est plus simple de décrire l'ellipse par le jeu de paramètres
centre, grand axe, petit axe, inclinaision en degré.
Pour obtenir ces parametres a partir de a, b,c il faut écrire la forme quadratique associée à l'ellipse:
Le vecteur prore associé à la plus grande valeur propre de cette matrice donne la direction du grand axe de l'ellipse, la longueur du grand axe et du petit axe sont reliés aux valeurs propres par la relation suivante:
On obtient donc les 5 paramètres d'une ellipse à partir
de trois points dans l'image et non pas 5. L'information de tangente apporte
l'information necessaire.
3.Traitements des donnees
On obtient ainsi un jeu de 5 paramètres décrivant une
ellipse par triplet de points de l'image. Pour pouvoir ensuite obtenir
des statistiques significatives sur ces trilpets il faut (sauf situation
simple) en disposer d'un très grand nombre. Le problème de
l'occupation mémoire de ces données est primodrial.
centre = p,q
grand axe = r1
petit axe = r2
theta = orientation de l'ellipse
+
compteur
UNE CELLULE
3.1 Premières approches du probleme
Nous avons essayé une approche qui utilise deux simples accumulateurs
à deux dimensions pour la position du centre des ellipses et pour
les axes et un accumulateur 1D pour l'orientation de l'ellipse.
Pour chaque triplet on incrèmente un compteur dans les images
hough-centre et hough-axes de même taille que l'image initiale .
On peut ainsi facilement identifier la position des centres
des ellipses et les axes des ellipses comme des maxima locaux de ces accumulateurs
mais le problème est qu'une fois un centre d'ellipse identifié
il faut faire la correspondance entre les trois accumulateurs, ceci
demande de recommencer à tirer des triplets de pixels. Cette approche
s'est avérée très longue et complexe dans des situations
ou plusieurs ellipses ont le même centre.
Exemple d'images d'accumulateur obtenues
3.2 Apporche retenue
L'histogramme classique de la transformée de Hough est remplacé par une structure de liste chainée, les éléments de cette liste sont appelés cellules. Une cellule contient les cinq paramètres d'une ellipse et un compteur. Au debut de l'algorithme cette liste est vide. Après avoir tiré 3 points dans les contours de l'image, on calcule les cinq paramètres associés. On parcours alors la liste chainée à la recherche d'un jeu de paramètres ressemblant avec une certaine tolerance, si un tel 5uple est trouvé on incrémente son compteur, si on ne trouve pas ce 5uple on ajoute le jeu de paramètres courant à la liste.
Cet algorithme peut réclamer une très grande quantité
de memoire si l'image est complexe (une grande partie des contours ne sont
pas dans les ellipses). Pour chaque triplet de points n'étant pas
sur une ellipse des paramètres sont calculés et stockés,
ces triplets ne vont pas s'accumuler et seront stockés en memoire.
Par exemple pour un million de tirages il faut dans le pire des cas
Un arbre ordonné :
Pour aussi bien gagner en espace memoire qu'en temps de recherche,
l'ensemble de 5uples est stocké dans un arbre binaire ordonné.
Cet arbre ne contient des entrées que pour les paramètres
effectivements utilisés par l'image traitée.
Les cellules contiennent cinq paramètres #1 #2 .. #5 . Elles
sont d'abord ordonnées suivant la valeur du premier paramètre
#1, si deux cellules ont la même valeur de #1 à une certaine
tolerance près alors ces deux éléments forment une
nouvelle branche de l'arbre, cette branche est elle même une nouvelle
liste chainée ordonnée suivant la valeur de #2, si dans cette
nouvelle liste deux elements #2 ont la même valeur ils sont regroupés
et forment une nouvelle liste chainée ordonnée suivant la
valeur de #3 et ainsi de suite...
L'interet d'utiliser cette structure de données est dans le
fait qu'elle compresse les données en memoire, la taille de cette
structure s'adapte automatiquement en fonction du pas de quantification
utilisé, du nombre de tirages, du niveau de bruit dans l'image.
Dans le cas extrème ou l'image est très peu bruitée
et qu'il n'y a qu'une ellipse dans l'image (tous les pixels de contours
sont dans cette ellipse), l'arbre ne contiendra qu'un seul chemin, celui
des parametres de l'ellipse.
Structure d'arbre utilisé
Remplissage de l'arbre
La vitesse de remplissage de l'arbre est très variable d'une image à l'autre.
Elle dépend de :
Le facteur limitant de l'algorithme est dans la taille de cet arbre,
il doit contenir des grandes valeurs de compteur pour chaque ellipse que
l'on veut detecter. On peut se contenter d'un faible nombre de tirage pour
les images très simples, en revanche dés que l'image est
plus complexe il faudrait faire plus de tirages que la memoire ne peut
en stocker (essais realisés sur Sun Ultra 5 128Mo de Ram).
Pour determiner le nombre de tirages necessaire pour arriver a distinguer
une ellipse donnée, il faut d'abord choisir à priori le seuil
critique du rapport nb de pixel dans l'ellipse que l'on veut detecter sur
le nombre total de points de contours et faire un nombre de tirages d'autant
plus important que ce rapport est faible et le bruit important.
En pratique, nous avons décidé d'utiliser toute la memoire
disponoble sauf si l'image est très simple. Pour cela tous les 100000
tirages on cherche la valeur max des compteurs présents dans l'arbre
: maxi. Si maxi >100 ou nombre de tirages >3000000 on arrète de
remplir l'arbre.
Exemple du contenu de l'arbre d'accumulation seuillé à
2 :
Trois ellipses et l'arbre correspondant seuillé a 2, Chaque ellipse présente dans l'image a été atteinte par deux triplets
4.Analyse de l'arbre
4.1 Mono-Ellipse
Dans le cas ou on ne cherche qu'une seule ellipse dans l'image il suffit de rechercher la cellule qui a le plus grand compteur. On fait cela par un parcours récursif de l'arbre.
4.2 Multi-Ellipses
La detection de plusieurs ellipses dans l'image se fait en parcourant
plusieurs fois l'arbre :
On commence par determiner le maximum des compteurs = max et on extrait
l'ellipse correspondante.
cmpt=max
Ensuite on reparcours l'arbre en recherchant les parametres qui ont
un compteur = cmpt on conserve l'ellipse correspondante si elle est suffisament
distante des ellipses deja retenues (distance au sens norme euclidienne
en dimension 5 sur les paramètres p,q,r1,r2,theta).
Puis on itère avec cmpt=cmpt-1
On s'arrète quand cmpt a atteint le seuil passé en ligne
de commande.
(Le niveau ou il faut s'arreter depend beaucoup de l'image traitée
- proportion de pixels dans les ellipses - bruit )
5.Resultats
Exemple - cercle+bruit
Exemple - deux cercles
Exemple - 3 ellipses
Exemple - image naturelle
6.Executables et code source
executable
Telecharger executable SUN ou code C
syntaxe
pour station 128Mo