L'application directe de la transformee de Hough aux cas des ellipses nous
demanderait d'etablir une projection entre l'espace de l'image et un espace
de parametres à 5 dimensions. Or cette approche n'est jamais utilisée
car faire une telle projection dissemine nos representants dans un espace
de parametres beaucoup trop grand pour pouvoir ensuite avoir des accumulations
significatives. Les populations des accumulateurs n'etant plus statistiquement
pertinantes. D'autre part le temps de calcul et la memoire necessaire à cette projection serait enorme (nous verrons dans le cas de notre implementation, ce que enorme peut signifier "enorme")
Ce qui est generalement mis en oeuvre est la découpe de ce probleme
en sous probleme de dimension moindre.
La decomposition est obtenue en utilisant des carateristiques geometriques de l'ellipses.
Ici, nous avons adopté la methode de Yuen et al, qui decoupe le probleme en deux passes. Tout d'abords, nous identifions les centres possibles d'ellipses. Cela nous demande simplement d'effectuer une transformation de Hough dans un esapce a deux dimension. Puis, nous determinons les trois autres parametres lors d'une deuxieme passe par resolution du probleme lineaire associée.
Voici comment les centres des ellipses sont reperés:
Si on considere deux points P et Q sur une ellipse, et qu'on estime les tangentes en ces points. Alors, en conciderant le point T , intersection des deux tangeantes et le point M, milieu du segment [PQ]. Alors, pour une ellipse parfaite, son centre sera situé sur la demie-droite [Tm) hormis le segment [MT].
Transformation de Hough standard:
On prend toutes les paires de pixels appartenant au contour de l'image ,et on construit un
histogramme en 2 dimensions qui servira a enregistrer les droites ainsi
trouver pour chaque paire de pixel tirée. Tout point de l'image
faisant parti d'une de ces droites se voit incrémenter d'un crédit
dans l'histogramme.
Pour être sur de trouver une solution au problème
il est écarte le cas des tangentes étant presque parallèles
ou perpendiculaires.
Les indices qu'on cherche sur
la présence d'une ellipse sont alors représentées
par les maximums locaux présent dans notre histogramme. Il est cependant
a noter que le nombre de lignes qui entrent dans l'histogramme croit approximativement
avec le carré du nombre de pixels dans l'image. Ainsi cette tache
est très coûteuse en matière de temps de calcul.
Dans la transformation de Hough, le critère de choix entre les
maximum locaux est un élément essentiel. C'est lui qui peut
accroître la vitesse, augmenter la précision de la détection.
Transformation de Hough Probabiliste:
Contrairement a l'approche standard qui applique la transformee de Hough
a tous les pixels de l'image, la TH probabiliste l'applique qu'a une proportion
des pixels de l'image. Le travail de Kiryati et al. preconise d'utiliser
une valeur comprise entre 10 et 20% pour que l'histogramme produit soit
comparable a celui obtenu par la methode traditionnelle.
La transformee probabiliste a un avantage intrinseque pour ce qui est
de la charge de calcul et de son temps d'execution.
Amélioration de la transformée de hough par tirage aléatoire:
Nous avons vu que dans la TH standard, une paire de point a pour representation une droite dans l'espace des parametres associés.Ici, dans la TH par tirage aleatoire, il est choisi aleatoirement un triplet de pixels du contour. On definit ainsi, un unique point dans l'espace des parameteres.
Transformation de Hough Hierarchique:
Enfin, une la derniere approche que nous mentionerons ici concerne un traitement hierarchique des données. Un des problemes majeur de la transformé de hough reside dans la quantification de l'espace des parametres, c'est a dire de la taille des accumulateurs. La determination du juste pas est chose delicate. La transformée hierarchique apporte une reponse a ce probleme, cette methode propose de commencer a effectuer une transformée de Hough avec un pas de quantification de l'espace des parametres large, puis elle subdivise les accumulateurs qui ont recu de nombreux votes. Ensuite, elle procede a une autre passe de la transformée de Hough sur cette partie de l'espace des parametres avec cette quantification plus fine. Ces operations sont itérées jusqu'a obtenir une precision désirée. Les problemes liés a cette methode reside dans le faite que s'il y a beaucoup de petits pics dans une partie de l'image, cela va vous empecher de detecter des pics plus larges dans une autre partie de l'image.