Presentation de la transformée de Hough.
Next: La transformartion de Hough appliquée aux ellipses Previous: Introduction

Historique et principe

        Dans la détection d'éléments spécifiques, il est des algorithmes qui, pour identifier ces formes élémentaires, entreprennent de suivre les contours pour finalement les lier par des critères plus ou moins complexes afin de remonter jusqu'aux formes recherchées. Une autre approche de ce problème serait de tenter d'accumuler des évidences sur l'existence d'une forme particulière telle qu'une droite, un cercle ou  une ellipse. C'est cette démarche qui a été adoptée dans la transformée de Hough.
        La transformée de Hough a été développé par Paul Hough en 1962, et a été breveté par IBM. Dans les dernieres decennies, la transformée de Hough est devenu un outils standard dans le domaine de la vision artificielle. Elle permet la detection de droites, de cercles ou d'ellipses de facon traditionnelle . Elle peut aussi etre etendue a des cas de description d'objets plus complexes.
 La transformée de Hough permet d'avoir une bonne robustesse contre les discontinuités et les elements manquants d'une structure.
Le principe general de la transformée de Hough est d'etablir une projection entre l'espace de l'image et un espace de parametres representatif de la forme recherchée.

Nous allons illustrer rapidement  le principe de la TH sur l'exemple de la detection des droites.
Nous verrons par la suite comment adapter ce model à la detection des ellipses.

Illustration sur le cas des droites

Une droite est caracterisée par deux parametres a et b tels que  y = ax+b.
La  transformée de Hough va nous permettre de faire un mapping entre les coordonees d'un pixel et l'espace des parametres (a,b). Pour cela deux tactiques possibles. Soit utiliser la transformation de 1 à m, soit de m à 1.
En effet on peut lire l'equation d'une droite de deux manieres. Soit par la lecture traditionnelle qui nous indique que y=ax+b, ce qui veut dire que tous les points (x,y) verifiant cette equation seront associés au meme couple (a,b) dans l'espace de parametres. En l'occurence, il nous faudra simplement un bipoint pour definir completement notre droite.
Soit on peut lire b = -ax + y, alors un couple (x,y) de l'image sera projeté en une droite de l'espace de parametres (a,b).
Ensuite pour etudier l'existence de droites il faut se pencher sur l'espace des parametres. Celui-ci, si tout c'est bien passé, doit presenter des regroupemenst traduisants l'existence de l'objet recherche. Une étude des differents maximum doit etre alors effectuée.Il faut savoir à partir de quel moment un regroupement de point est significatif. Cette etape est en generale delicate, le bruit causé par les autres elements de l'image peuvent perturber la detection des objets recherches. D'autre part si les objets sont trop nombreux on peut aussi avoir du mal a les reperer. Mais nous verrons tout cela plus en details dans le cas particulier de la detection d'ellipse.
Toutefois, il faudrait insiter sur la parametrisation du probleme. En effet, si on reprends le cas de la detection des droites, on se rend compte qu' une ecriture cartesienne n'est pas judicieuse. Pour pouvoir representer completement l'ensemble des droites possibles, a et b doivent varier entre + et - l'infini. D'autre part en terme de probabilité, on a autant de chance d'avoir une droite avec un a compris entre [0..1] et [1..+l'infini]. L'espace des parametres n'est pas homogene.
Il faut donc essayer de trouver une autre parametrisation. Une representation normale semble plus adaptée. La droite est alors repérée par la distance r et l'angle theta. Ainsi, la forme associée a un point est une sinusoide dans l'espace des parametres. Cette parametrisation presente l'avantage d'etre homogene et d'aurer part, elle fournit des domaines de variation finis. En suivant ce lien vous pourrez experimenter par vous meme ce que l'on vient d'expliquer au sujet de la transformée de Hough appliqué aux droites.

Hough par vous-même


 
Next: La transformation de Hough appliquée aux ellipses Previous: Introduction
Vincent Rouilly
Last modified: Wed Mar 29 16:37:56 MET DST 2000