Chapitre 5

Description de contours et de formes

Chapitre rédigé par Henri M A ÎTRE

Dans de nombreuses applications de traitement des images, une fois l’image segmentée (on peut le faire, de la
façon la plus simple, en seuillant l’image [Sahoo et al., 1988, Cham et al., 1998] ou à partir des méthodes décrites
aux chapitres 2 et 3), on essaie de reconnaı̂tre les divers objets qui la composent à partir de leur seule silhouette.
C’est particulièrement vrai dans les applications de tri dans lesquelles on est intéressé à saisir ou trier des objets
arrivant sur un convoyeur1, dans les applications de reconnaissance de caractères, ainsi que pour des applications
de surveillance ou de guidage, par exemple en imagerie militaire.
Il est utile alors que l’utilisateur dispose d’une représentation de la forme vérifiant plusieurs propriétés :
1. une bonne fidélité à la forme initiale,
2. une bonne discrimination de formes différentes,
3. une bonne adaptation aux opérations de reconnaissance des formes, et en particulier une insensibilité aux
déformations qui sont susceptibles d’entacher l’objet,
4. une certaine compacité pour permettre l’archivage de nombreuses formes et potentiellement de ces mêmes
formes sous divers aspects.
De nombreuses représentations des formes ont été développées concurremment, chacune pour répondre à un
problème parfois assez spécifique et donc mettant l’accent sur l’une ou l’autre des propriétés ci-dessus.

5.1 Fonction caractéristique

La représentation naturelle d’une forme dans une image est une représentation par fonction caractéristique,
c’est à dire sous forme d’une image binaire, les seuls pixels non-nulles étant ceux couverts par la forme :

 
!
" 
 !
Dans une image où de nombreux objets existent, on utilise une image d’étiquettes (ou de labels) qui généralise la
notion de fonction caractéristique :

# $&% 
 '(! %

1 Le tri se partage en tri planaire (où les objets sont préalablement mis à plat, généralement sur un tapis roulant), et en tri en vrac, où ils sont

présentés dans un désordre total.

63
64 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES

0
1
22 3 4 5 6

étiquette étiquette
77 initiale pointeur finale
0 0
2 1 1
4 6
7 x
3 z 2 t 2 2
3 2 2
4 3 2
8
5 3
6 2 2

3 7 2 2

2 y 8 4

F IG . 5.1 – Etiquetage d’une image en 4 connexité. L’image de gauche est le résultat du premier passage jus-
qu’au point noté x. Les étiquettes ont été attribuées à chaque point soit en donnant une nouvelle étiquette si les
2 antécédents du point sont à 0, soit en donnant l’étiquette des antécédents si ces antécédents ont une étiquette
semblable différente de 0. En x les étiquettes sont de valeur différente. Le pixel x se voit attribué l’étiquette 2 car
2 = min(2,7), le pixel y l’étiquette 2, le pixel z l’étiquette 3 et le pixel t l’étiquette 2. Le point x crée le pointeur
7 2, y le pointeur 3 2, z 4 3 et t 6 2. Après un second passage sur l’image, on détermine la liste finale
des étiquettes de 0 à 4. Pour recréer une image d’étiquettes en conformité avec cette liste, il faut donc faire un
deuxième passage sur l’image.

Une image d’étiquettes résulte d’une procédure d’étiquetage. Elle se fait par le choix d’une connexité qui
permet de définir les propriétés de topologie des divers objets (4- ou 8- connexité sur les trames carrées, 6-connexité
en trame hexagonale). L’étiquetage vient attribuer une étiquette semblable à tous les points connexes au sens de la
segmentation. Par exemple en 4-connexité un algorithme d’étiquetage fonctionne de la façon suivante (cf. figure
5.1).
1. une liste d’étiquettes est initialisée à 0 ;
2. le balayage (par exemple vidéo) de l’image est initialisé ; au premier point est attribuée l’étiquette 0 ;
3. un point nouveau est pris dans l’ordre du balayage ; on examine sa connexité à son voisin supérieur et à son
voisin de gauche (ses antécédents) :
– si le point courant est connexe à ses deux antécédents (au sens de la segmentation), et si ses deux
antécédents ont la même étiquette, on lui attribue l’étiquette de ces antécédents ;
– si le point courant est est connexe à ses deux antécédents, mais que ses deux antécédents n’ont pas la même
étiquette, on donne au point l’étiquette la plus petite parmi les deux, puis dans la liste des étiquettes, on
crée un pointeur qui renvoie de l’étiquette la plus grande vers l’étiquette la plus petite ;
– si le point courant est connexe à l’un seulement de ses antécédents, on lui attribue l’étiquette de cet
antécédent ;
– si le point courant n’est pas connexe à ses deux antécédents, on incrémente la liste des étiquettes, puis on
attribue au point courant cette nouvelle étiquette ;
4. on retourne en 3 jusqu’à atteindre le dernier point de l’image.
Lorsque l’ensemble de l’image a été ainsi traité (après donc un passage complet sur l’image), on réorganise
l’image des étiquettes. Pour cela on parcourt cette image et chaque valeur d’étiquette est remplacée par l’étiquette
terminale rencontrée en remontant la liste des pointeurs. La liste des étiquettes est alors filtrée de toutes les
%
étiquettes qui possèdent %
au moins un pointeur. On constitue ainsi une liste d’étiquettes qui occupe tous les en-
tiers entre 0 et
 s’il y a
 objets se découpant sur un fond.
5.2. DESCRIPTION DE FORMES 65

5.2 Description de formes

Les descripteurs (ou paramètres) de forme sont des nombres qui représentent chaque forme et permettent de les
classer (par exemple par nuées dynamiques ou plans séparateurs). Ces paramètres ont été abondamment proposés
dans la littérature [Coster et Chermant, 1985], beaucoup étant adaptés à des formes particulières. Citons les plus
utilisés, par exemple :
– le rapport iso-périmétrique, proportionnel au rapport du carré du périmètre de l’objet à sa surface (dans des
images continues, il est maximum pour le cercle) ;
– l’indice d’allongement [Schmitt et Mattioli, 1994], proportionnel au rapport du carré du diamètre géodésique
à la surface de l’objet, (minimal pour les disques au sens du voisinage choisi).
Les paramètres de forme sont bien adaptés pour des objets de taille assez grande car ils ont souvent été définis
pour des formes continues. Pour des objets de petite taille (quelques pixels), la discrétisation du maillage induit
des comportements souvent peu satisfaisants.

5.2.1 Représentation par les moments



(
Connaissant l’objet par sa fonction caractéristique , une représentation classique de sa forme consiste à
en mesurer les divers moments : 

 

 

(

En particulier les moments centrés (rapportés au centre de gravité ( ) de la forme) sont invariants par transla-
tion :  

 





 



Sur une image discrète, ces moments s’écrivent :

  "


 


%  
#%(


 
 "# !  
 


 
)(+*-,
Les moments d’inertie (valeurs propres de la matrice d’inertie, matrice $&%'$ de terme courant
 $ )
sont invariants par rotation. Les moments d’inertie normés par la plus grande valeur propre sont invariants par
similitude (rotation et facteur d’échelle). Les moments d’inertie décrivent bien l’allongement de formes régulières
comme des ellipses ou des distributions gaussiennes. Ils sont plus ambigus sur des formes complexes (cf. figure
5.2).

a b c

F IG . 5.2 – Description de formes par : a - ellipse et axes d’inertie, b - boı̂te englobante, c - boı̂te minimale.

5.2.2 Représentation par les moments invariants

Des moments invariants ont été proposés (nommés moments de Hilbert), invariants par translation, rotation et
changement d’échelle (dans la limite de l’approximation par une maille discrète) [Hu, 1962] . Ils se construisent à
66 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES

partir du moment normé : 



   



 


où  

 ( * , &* "
, par les formules :
     
*



  *

    &
   
  
*

   &
  
   
* *
 
    !
   
    
     
  
* * *


    
    
 
     
*
  * * *
    
  
 
     

 * *

  !
 
   
* * *
   !
   
   
     
   

  * * *


  
  
 
     
*
    *  *   * 

5.2.3 Boı̂tes englobantes et boı̂tes minimales

Lorsque les formes sont plus irréguliéres, on préfère souvent des descriptions de l’allongement par la forme de
la boı̂te englobante :
la boı̂te alignée sur les axes et donc simplement définie par ses dimensions (
 "
 ) et (
 



!
– soit



 ),
– soit la boı̂te orientée selon le diamètre minimal de l’objet (de calcul un peu plus complexe) (cf. figure 5.2).

5.3 Polygones de Guzman

" #
C’est l’une des méthodes les plus anciennes [Guzman, 1968]. L’approche de Guzman consiste à envelopper
l’objet à reconstruire dans des boı̂tes de formes de plus en plus précisément adaptées. Elle peut donc s’appliquer
soit à partir d’une image d’étiquettes de la forme à analyser, soit à partir d’une liste des pixels de contour de la
forme. Les formes prototypes auxquelles seront comparées les objets sont construites sur un maillage carré de façon
systématique et se classent en niveaux en fonction de la longueur de leur périmètre. Cette longueur (exprimée en
pixels) étant obligatoirement paire, on décrit chaque niveau par le demi-cardinal du nombre de pixels constituant la

"
$
frontière. Dans chaque niveau, les divers prototypes sont repérés par un indice qui les identifie uniquement. Ainsi,
 (et donc appartient au niveau 2). C’est la forme $  .
% %
la forme la plus simple (le carré unitaire) a une longueur 4
Afin de tenir compte des symétries et des rotations de $ , toutes les formes identiques par rotation modulo $
et toutes les formes identiques par symétrie droite (par rapport à un axe horizontal ou vertical) sont rapportées
à une même prototype du dictionnaire des formes (cf. figure 5.3). Un objet quelconque est donc décrit par une
,* "
succession d’indices ,
décrivant l’objet à divers niveaux de résolution. Deux objets sont généralement identiques
jusqu’à un niveau , puis différents à partir du niveau (cf. figure 5.4).
Cette approche rencontre plusieurs limites :
– pour les ordres grands, les formes deviennent très nombreuses et le dictionnaire trop grand. La recherche du
représentant se faisant par comparaison au prototype devient très longue ;
– les distances d’une forme à un prototype ne s’imposent pas de façon unique (cf. figure 5.5), laissant place à
des classements différents selon le critère adopté ;
5.4. CHAÎNES DE FREEMAN 67

1 2

1 3

1 4
2 3

2 3
5
1 4 5

2 3 4 5
1

11

6 7 8 9 10

12 13 14 15

16 6

F IG . 5.3 – Les premières formes du dictionnaire de Guzman.

" #
– les relations verticales entre niveaux sont complexes et ne permettent pas d’accélérer le parcours de
l’arbre de façon commode ;
– certaines formes se retrouvent identiques dans des niveaux différents, à un facteur d’échelle près (par exemple
le carré élémentaire se retrouve dans tous les niveaux impairs).
















































































































































 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 











































 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


















































































































































A 





 





 


 


 


 


 


 


 


 


 


 


 


 


 


 




























































































 

 

 

 

 

 

 

 

 

 B

 

 

 

 

 

 

























































 (3,1)






















































































 



 

 

 

 

 

 

 

 

 

 

 

 

 

 

























































 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

(14,34) (5,5) (14,51)

F IG . 5.4 – Représentation de Guzman. Les 2 formes A et B sont semblables aux niveaux de représentation 3 et 5,
mais diffèrent au niveau 14, où l’une est représentée par le prototype 34 et l’autre par le prototype 51.

L’approche de Guzman a été abandonnée aujourd’hui, mais elle apporte des concepts intéressants à la descrip-
tion des formes :

" #
– la notion de raffinement de la description,
– la notion de similarité entre tous les objets vus de très loin ,
– la notion d’invariance par rotation, symétrie et changement d’échelle que l’on pourrait étendre éventuellement
à d’autres transformations.

5.4 Chaı̂nes de Freeman

C’est la méthode la plus ancienne de description des contours dans les images et aussi la plus utilisée encore
aujourd’hui [Freeman, 1961, Freeman, 1977]. Si elle est moins utilisée en reconnaissance des formes qu’elle le
fut, elle est très fréquemment utilisée dans des applications récentes comme la transmission des images par zones
(par exemple dans MPEG-).
68 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES






















































































































































































































































































 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 


























A 


















 X








































































































































































 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 






















































































































































































 Z






























 










































































































 X

Y Z

F IG . 5.5 – L’arbitraire de l’approximation des formes : la forme A est l’objet. Les 3 formes X, Y et Z en sont
des approximations. La distance d’une représentation à la forme initiale peut se mesurer par la surface entre les 2

" #
contours. Il y a de nombreuses formes à distance minimale. X est une forme la plus proche en terme de surface et
la plus simple au sens du nombre d’angles droits lorsqu’il y a plusieurs solutions de même distance. Y est la
forme la plus proche par défaut (entièrement contenue dans A), Z est celle par excès. Z et Y sont superposées à
droite.

5.4.1 Définition
C’est une technique de représentation des directions du contour (on code la direction le long du contour dans
un repère absolu lors du parcours du contour à partir d’une origine donnée). Les directions peuvent se représenter
en 4-connexité (codage sur 2 bits) ou en 8-connexité (codage sur 3 bits) 2 .
Le codage d’un contour se fait donc de la façon suivante :
1. transmission des coordonnées absolues du point de départ,
2. transmission de la liste des codes de déplacement d’un point du contour au suivant sur le maillage.
Les codes des contours sont donnés par la figure 5.6.
Dans d’autres techniques, on code de façon différentielle le changement de direction d’un point au suivant.
Cela peut se justifier en codage sur 3 bits si une direction est très dominante par rapport aux autres.
1 3 2 1

2 0 4 0

3 5 6 7

F IG . 5.6 – Les codes de Freeman en 4-connexité (à gauche) et en 8-connexité (à droite).

Deux exemples de codages par chaı̂nes de Freeman sont présentés sur la figure 5.7 (le codage du positionnement

absolu a été omis). Dans le cas de la 4-connexité, le codage de la suite de contours occupe 124 bits ( $ % $ ), tandis
qu’en 8 connexité elle occupe 126 bits ( $ % ). Il n’y a pas de règle générale sur l’efficacité des représentations 
en termes de compression. Si la courbe est très complexe (beaucoup de changements de direction), le codage en
2 des essais ont été faits pour coder également les chaı̂nes de Freeman sur 4 bits en ajoutant les directions reliant le point central à la seconde

couronne des voisins qui ne sont pas dans la direction des voisins de la première couronne. Mais cette approche n’a pas eu un très grand succès.
5.4. CHAÎNES DE FREEMAN 69

8-connexité est généralement plus compact. La qualité du codage est cependant toujours au moins aussi bonne en
8-connexité.
1

A A
X

X = 01000030030303003030303202221222232333033030000000100100100010

Y=100007707707776544434445576777000010101001

F IG . 5.7 – Codage de Freeman. Approximation de la courbe A par la chaı̂ne X (en 4-connexité) et par la chaı̂ne Y
(en 8-connexité).

a
0 1 2 3 4 5 6 7
0 1 2 6 7
1 2 0
2 1 00000303444142000720660500011
3 4 0
3 2 4
4 2 3 5 6
5 6 4 b

6 7 0 4 5
7 0 6
000022442420000066600011

F IG . 5.8 – En 8-connexité, il est possible de simplifier les courbes en remplaçant certains couples de descripteurs
par le descripteur de la table ci-dessus. Dans la figure de droite, la figure b est une simplifiée de la figure a par
remplacement des seuls angles aigus. Il existe plusieurs simplifiées selon l’ordre de substitution que l’on adopte.

5.4.2 Les propriétés des chaı̂nes de Freeman

Les chaı̂nes de Freeman se prêtent à un certain nombre de manipulations commodes.
% %
1. On obtient une dilatation de la courbe d’un facteur en répétant fois chaque descripteur.

% 
2. On ne peut généralement pas réduire une courbe sans distorsion.
, 
% une courbe
3. On fait tourner ,
de %  (dans le cas d’une chaı̂ne de Freeman en connexité) en ajoutant (ou
retranchant) modulo à la chaı̂ne initiale.

4. On mesure la longueur d’une courbe par les formules suivantes :
– en 4-connexité :
– en 8-connexité :


nombre de descripteurs,
nombre de descripteurs pairs + $ nombre de descripteurs impairs.


5. Inversion
 ,d’un
 * chemin 
 ( :
on ,
inverse tous les descripteurs et on inverse la séquence. L’inverse d’un descripteur
est $
exemple en 4-connexité :
.
(" "
$

 
("
$ $ .
 
70 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES

6. Simplification d’un chemin : c’est un chemin dont on a supprimé des détails sans changer globalement
la forme. Cela s’obtient en remplaçant des séquences de descripteurs consécutifs par des descripteurs

équivalents reliant les mêmes points (cf. figure 5.8) :

en 8-connexité :
03 

exemple en 4-connexité :
012 

2 .

1 ,

7. Réduction d’un chemin : c’est l’un des chemins de longueur minimale reliant les 2 extrémités de la courbe

exemple en 4-connexité :

$ $ $

initiale. On associe 2 par 2 des descripteurs inverses de la chaı̂ne et on les supprime.
' " "  "

$  . On obtient tous les chemins réduits en
changeant l’ordre des associations.
en 8-connexité la réduction est un peu plus complexe car il faut aussi regrouper des ensembles de 3 ou 4
descripteurs qui s’annulent : exemple
025  ou
7225  .
8. Fermeture d’un contour : on teste la fermeture d’un contour en vérifiant que la chaı̂ne réduite est nulle.
On ferme un contour en lui ajoutant le chemin inverse d’un de ses chemins réduits. Il y a beaucoup d’autres
fermetures possibles que par addition de l’inverse d’un réduit, mais les fermetures obtenues ainsi sont de
longueur minimale. Il y a d’autres fermetures minimales que celles obtenues par addition de l’inverse d’un
réduit.
9. Courbe qui s’intersecte : pour savoir si une courbe décrite par sa chaı̂ne se recoupe, on procède à une
réduction de chemin systématique en partant de son origine et en testant si chaque nouveau descripteur
possède un inverse dans la chaı̂ne déjà parcourue. Si à un instant la chaı̂ne déjà parcourue se réduit à une
chaı̂ne nulle, on a trouvé un point double.


circulaires des descripteurs modulo .


10. Changement d’origine : le changement de l’origine d’une chaı̂ne de longueur revient à une permutations

11. Sens de parcours d’un contour : le contour fermé d’une forme simplement connexe peut être décrit dans le
sens direct ou dans le sens inverse. Pour connaı̂tre le sens d’un contour fermé, on réduit ce contour jusqu’à
n’avoir que 4 descripteurs. En 4-connexité, il n’existe que 2 chaı̂nes possibles (et celles qui s’en déduisent
par changement d’origine) :
&(" 
– le carré direct :  & $ " ,
– le carré inverse :  
$ .
En 8-connexité les configurations sont un peu plus nombreuses.
12. Surface d’une région simplement connexe : la technique est assez complexe mais ne nécessite pas la recons-
truction de la région [Freeman, 1977].
5.4. CHAÎNES DE FREEMAN 71

X=01033001 Y=0011003333000011 Z=12100112 W=32211232

A=0321

B=0123

X1=0103300323212 Y1=033
T=0010000333221100033332222222111221

%  . 5.9 – Quelques propriétés des chaı̂nes de Freeman : X = chaı̂ne originale, Y = contour double, Z = rotation de
F IG
$ , W = contour inverse. X1 = chaı̂ne originale et Y1 = chaı̂ne réduite. T = exemple de boucle dans une chaı̂ne.
A et B sont les deux contours élémentaires (inverse et direct) en 4-connexité.

5.4.3 Reconnaissance des formes par des chaı̂nes de Freeman

Pour que 2 formes et  soient identiques, il faut tout d’abord qu’elles aient le même nombre de descripteurs.
Puis, comme elles peuvent différer par le sens de description, il faut comparer à  d’une part et à  d’autre
part. Enfin, comme elles peuvent avoir des origines différentes, il convient de tester les deux chaı̂nes descripteur à


descripteur sous toutes les hypothèses de permutation circulaires. Des techniques rapides ont été développées pour
faire ces recherches (d’une complexité sous-linéaire en ), [Boyer et Moore, 1977, Miclet, 1984] 3 .
Dans le cas où l’on ne recherche pas une similarité exacte mais seulement approchée (par exemple pour prendre
en compte la présence du bruit lors de la détection des contours), on est amené à utiliser des techniques de distance
d’édition pour lesquels on chiffre les coûts des erreurs possibles : omission de contours, adjonction de contours,
permutation de descripteurs, etc. On utilise alors généralement des techniques de programmation dynamique (al-
gorithme de Wagner et Fisher [Wagner et Fisher, 1974, Miclet, 1984], élargi pour des substitutions de plusieurs
descripteurs consécutifs dans [Lowrance et Wagner, 1975]) ou de relaxation (algorithme de Davis) pour retrouver
la distance minimale entre et  .
3 Ce sont des automates finis semblables à ceux qui sont utilisés en particulier pour les compilateurs et les éditeurs de texte.
72 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES

5.5 Descripteurs de Fourier

5.5.1 Descripteur par tangente

le contour comme une courbe continue qui peut être décrite par son abscisse
Dans cette approche on considère
curviligne à partir d’une origine choisie (cf. Fig
5.10). On paramètre la courbe par l’angle fait par le vecteur
 point et celui au point origine :  et on crée la variable réduite  qui prend
ses valeurs entre 0
% %

$
tangent en chaque
et $ :  $ , où est la longueur complète du contour. On construit alors la fonction  :

$
$
 

$ %
   $

%
 % % 
 $

( l’enroulement de $ de la tangente pour un tour

de contour.
%
$
le terme correctif prenant en compte La fonction
est une fonction périodique sur $ qui admet donc une série de Fourier :  #   #    . On
appelle descripteurs de Fourier l’ensemble des modules des # :
 #   .
Ils bénéficient des propriétés suivantes :
1. ils sont invariants par translation de la forme,
2. ils sont invariants par changement d’échelle (puisque  est normalisé),
3. ils sont invariants par rotation, puisque l’on a choisi la différence d’angle entre 2 tangentes,



$
par changement d’origine,
$

car passer d’une origine
4. ils sont invariants à une origine revient à :
– retrancher  à toutes les valeurs  ,
– changer  en
    .
 

$
Donc :    $
    !  


$
!  et : # # "
 %
! 
 %$#
Pour comparer des formes on compare leurs% descripteurs par ordre croissant. Si de plus on veut simpli-
fier le contour, il suffit de supprimer les ordres élevés dans le développement. malheureusement, dans cette
représentation, si un contour est fermé, le contour obtenu en filtrant les hautes fréquences ne l’est généralement
plus. C’est pourquoi on préfère souvent les descripteurs de Fourier par représentation complexe qui n’ont pas ce
défaut.

Φ (l)
A
l
M

F IG . 5.10 – A gauche : descripteurs de Fourier par tangente. Le point de départ A est choisi arbitrairement. Son
vecteur tangent sert de référence à la paramétrisation de la courbe. A droite : après troncature du développement
de Fourier, la forme A, initialement fermée devient B, plus régulière, mais non fermée.

5.5.2 Représentation complexe



  de points de contours,
 * 
 . On appelle alors
Dans cette représentation, on décrit la forme par un ensemble et on représente la
forme dans le plan complexe. On attache donc à chaque  un nombre complexe % 
5.6. APPROXIMATIONS POLYNOMIALES 73

descripteurs de Fourier, les coefficients de la TF de % :

#


 


%     $ %  %
# %     * "'   , jouissent d’intéressantes propriétés [Bertrand et al., 1982].
 est le centre de gravité de la forme. Si l’on l’omet, la description est invariante par translation.
Les coefficients , pour $ $
%
1. Pour ,
% "
2. Si tous les # sont nuls sauf pour , la forme est un cercle de rayon  (ou un polygone régulier à
côtés), donc  joue le rôle de facteur d’échelle. La normalisation par  rend la forme invariante par
homothétie.
 
3. Les coefficients # et  # (pour
et
 % # " % #
) jouent des rôles symétriques (mais opposés) de la
% % %  "
% 
façon suivante :
– l’ordre indique
2 actions pour
% le nombre% d’actions
et  
$ , 3 actions pour
%
sur le cercle unité (entre % et $ ) : 1 action pour
et 
$ et
, etc. Ces actions sont réparties
,

régulièrement %  indiquent
autour du cercle unité,
– les valeurs de % des actions de traction sur la courbe, pour la déformer vers l’extérieur du
cercle unité, les valeurs de indiquent des actions de pression sur la courbe, pour creuser la courbe
vers son centre,
– la phase du nombre complexe # :  # exprime le lieu, sur le cercle unité, où s’exerce l’action.
4. Plus les coefficients sont nombreux, plus la forme est complexe. Et plus les coefficients sont élevés plus les
détails sont fins sur la courbe.

M k = xk + i yk


F IG . 5.11 – A gauche : descripteurs de Fourier par représentation complexe. Le point courant # est décrit par ses
coordonnées complexes dans le plan image. A droite : le cercle résulte de la prise en
 , la courbe présentée résulte de l’adjonction d’un coefficient de pression (donc à
% compte du seul coefficient
% %  " %  "
%
), en 1 seul point (donc
$ ou , ici ), de déphasage nul (puisque situé en ).

On voit que les descripteurs de Fourier par représentation complexe ont le même type de comportement que
les descripteurs par tangente. Ils sont mieux adaptés aux formes discrètes puisqu’ils garantissent toujours que la
forme demeure fermée après troncature du développement de Fourier. Ils peuvent être invariants par rotation si
l’on s’intéresse aux seuls modules des coefficients # .
Parmi leurs inconvénients, il faut noter que l’on ne peut pas aisément garantir qu’un contour de forme simple-
ment connexe ne donnera pas, après troncature, un contour qui s’auto-intersectera.

5.6 Approximations polynomiales

Il y a essentiellement 3 types de telles approximations :
74 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES

1. les approximations analytiques par ajustements de nuages de points par des polynômes du premier ordre
(conduisant donc à des polygones) ;
2. les approximations polygonales par des critères géométriques obtenues en parcourant la courbe des points
ordonnés selon une abscisse curviligne ;
3. les approximations par des polynômes de degré
 " et en particulier les approximations par des fonctions
splines.
Les approximations polygonales des formes décrites par des points de contour sont les représentations les
plus employées. Dans les cas les plus simples, on se contente de relier 2 à 2 des points de contour dans un ordre
déterminé au préalable (donc selon une abscisse curviligne croissante). Deux problèmes se posent alors :
– peut-on éliminer d’éventuels points parasites qui n’appartiennent pas au contour ?
– peut-on faire l’économie de certains sommets de la ligne polygonale pour obtenir des formes plus simples ?
Ces problèmes seront abordés dans le paragraphe 5.6.2.
Mais avant d’en arriver à cette situation simple, se posent les problèmes difficiles de déterminer quels points
appartiennent à un même contour et dans quel ordre les relier lorsque ces points sont issus d’un détecteur de
contour par nature local. C’est ce que nous abordons tout d’abord.

5.6.1 Approximation d’un nuage de points par une droite unique

  




C’est un problème bien classique mais qui mérite pourtant un peu d’attention. Soit les points, en
nombre , que l’on cherche à approcher par une droite. Il y a 2 façons de prendre le problème.



Approximation par régression linéaire

C’est une approche aux moindres carrés : on recherche la droite

 *  qui minimise la distance
(cf. Fig 5.12) :


 





 *    (5.1)

par :
La solution est donnée


'
matrice , où ,  et sont donnés par :


  
  , où  dénote la matrice pseudo-inverse de la

 "


"
"  





 
  


    

Ces formules s’étendent très aisément aux espaces de dimensions supérieures, ainsi qu’aux

approximations par des
polynômes d’ordre plus élevé. la distance minimisée est celle mesurée


selon le seul axe . C’est donc une mesure
généralement mal adaptée en traitement d’image, puisque et y jouent habituellement un rôle équivalent. On lui
préfère donc les méthodes par axe d’inertie.
5.6. APPROXIMATIONS POLYNOMIALES 75

∆ ∆

d1
d2
Mi Mi

régression axe d’inertie

F IG . 5.12 – Deux approximations linéaires aux moindres carrés minimisant des distances différentes : à gauche
par régression linéaire, à droite par axe d’inertie.

Approximation par axe principal d’inertie

C’est aussi une approche aux moindres carrés, mais on minimise dans ce cas la somme des distances de tous
les points à la droite :

 
   
 &"
* 

 


  
*


(5.2)

C’est l’équation de l’axe d’inertie des points, qui passe par leur centre de gravité  et qui est donné comme
vecteur propre de plus grande valeur propre de la matrice de forme quadratique :
 


     








Ces équations s’écrivent sans problème en dimensions supérieures (pour estimer des variétés d’ordre variable).
Elles se transcrivent beaucoup plus difficilement à des polynômes d’ordre plus grand car on ne sait pas, en règle
générale, exprimer la distance d’un point courant à une telle fonction.

Estimations robustes

Si l’on repose le problème précédent dans le cadre plus général de l’estimation robuste, on est amené à



considérer ce problème de façon un peu plus complète [Meer et al., 1991, Rousseeuw et Leroy, 1987]. On cherche
ici la meilleure droite représentant au mieux l’ensemble des points sous l’hypothèse d’un bruit entachant la
position des points.
Lorsque le bruit est gaussien, les estimations aux moindres carrés nous assurent d’une bonne qualité de l’es-
timée. Mais il faut souvent tenir compte de la présence, parmi les points, de détections erronées dont les écarts à la
droite ne sont pas gaussiens (ce sont des outliers4 ).
Une première façon de prendre en compte ces points consiste à faire une première estimation aux moindres
carrés, puis à éliminer les points trop éloignés de la droite (par exemple à l’aide d’un test statistique tel celui
de Cramer-von Mises5 . Ces méthodes ont reçu une base théorique dans l’approche dite par moindres carr és

tronqués% (LTS : Least Trimmed Squares) ainsi que toutes ses formes dérivées : moindres quantiles carrés (LQS),
moindre carré (LKS) [Lee et al., 1998].
4 on appelle outlier un point qui n’est pas régi par la même distribution statistique que les points dont on recherche une approximation.
5 Le test de Cramer-von Mises calcule une distance entre la loi gaussienne théorique et la répartition expérimentale des erreurs. Un point est
rejeté si sa distance à la distribution des autres points est trop improbable sous l’hypothèse gaussienne [Saporta, 1990].
76 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES

Mais cette approche est réputée dangereuse (on peut éliminer successivement les points appartenant à la droite
si un outlier est trop éloigné de celle-ci). On lui préfère des techniques d’estimation par médiane ou par médianes


itérées, plus coûteuses en temps de calcul, mais capables d’éliminer beaucoup  plus de points erronés.
et  de l’ensemble. On leur associe une
 
Dans une estimation par médiane, on choisit 2 points quelconques
 
droite qui fournit des coefficients

de coefficients :
  et  
et . Par combinatoire sur l’ensemble des points, on obtient deux ensembles

  . Les ensembles et sont triés séparément et l’on choisit les valeurs

médianes et comme estimateurs des paramètres de la droite. Le filtrage médian peut tolérer jusqu’à

jusqu’à $
d’outliers (
).


d’outliers.  Dans le cas de l’estimation simultanée de deux variables, l’estimation par médiane permet de tolèrer

De nombreux estimateurs robustes ont été calculés à partir de la notion de médiane. Ainsi, le minimum des
médianes des distances quadratiques (LMS Least Median of Squares) détermine le centre d’un nuage de points en
calculant pour chaque point la distance à tous les autres, puis en caractérisant la distance de ce point au nuage par
la valeur moyenne des distances et enfin en choisissant comme centre du nuage celui dont la médiane est minimale
[Rousseeuw et Leroy, 1987].

D’autres approches robustes reviennent

à une estimation
mais en pondérant chaque point par un coefficient  
par filtrage (comme le font la moyenne ou la régression),
qui tend vers 0 pour des points loin de la solution. Une

" #
autre approche consiste à intégrer cette pondération des points lointains directement dans la distance (c’est le cas
des M-estimateurs [Huber, 1981]). Dans ce cas, les distances 6 croı̂ssent moins vite que la loi quadratique ou
décroı̂ssent même pour tendre vers 0 pour les grandes distances. On les appelle des M-estimateurs.
Une autre famille d’estimateurs robustes s’appuie sur des recherches systématiques. c’est par exemple le cas
de la méthode RanSac (Random Sample Consensus) [Fischler et Bolles, 1981]. Cette méthode consiste à choisir
2 points et à adopter la droite qui les joint comme approximation. On mesure alors le nombre de points qui sont
en accord avec cette hypothèse (par exemple à l’aide d’un critère de distance du point à la droite). On choisit
finalement le couple de points qui conduit au plus fort consensus. On montre qu’il n’est pas nécessaire de tester
tous les couples mais qu’un petit nombre choisis aléatoirement (de l’ordre de quelques pourcents) est usuellement
suffisant.

Estimation d’un mélange de droites

,
Si l’on sait que droites existent dans l’ensemble des points, il est possible de faire une classification au sens

 
,
des nuées dynamiques par exemple. Pour cela on initialise le processus en choisissant    "' (issues
droites  , par exemple
de l’ensemble des points par tirage aléatoire) représentées par leurs paramètres
"   . On attribue
pour chaque droite ses paramètres
 
chaque point à la droite qui minimise la distance 5.1 ou mieux 5.2. Après classification de tous les points on estime
  par l’une des méthodes vues ci-dessus. On itère le processus enchaı̂nant
classification et estimation. On converge vers une solution qui dépend assez fortement de l’initialisation.
Une autre famille de méthodes utilise
"
% la version floue des nuées dynamiques
# (les C-moyennes-floues


%(ou Fuzzy-
 
C-means), dans laquelle chaque point % appartient à l’une

%($ "
des droites avec une appartenance  fonction
de sa distance à la droite. Pour tout point , on vérifie :    [Bezdek, 1981].

Extension de l’estimation à des coniques

Dans le cas où l’on recherche des formes représentées par des cercles ou des ellipses, on  peut choisir une

 

paramétrisation matricielle de la forme quadratique les représentant.
par son centre , son rayon et sa matrice d’ellipticité : 
Chaque conique indicée par est alors décrite


  

   
6 Les distances ainsi définies ne vérifient en fait plus les propriétés d’une distance.
5.6. APPROXIMATIONS POLYNOMIALES 77


où est le point courant du plan. La distance d’un point à cette conique s’exprime par :

%( 
#   

#    


 

L’estimation des paramètres se fait de la même façon que précédemment à partir d’une conique initiale souvent
circulaire.

5.6.2 Approximations polygonales, simplification de contours polygonaux

Lorsque l’on dispose d’une courbe continue ou finement échantillonnée et que l’on souhaite la réduire à une
ligne polygonale, on dispose de très nombreux algorithmes qui proposent soit des critères d’approximation soit des
mises en œuvre différents. Le plus connu est l’algorithme de la corde.

Algorithme de la corde (ou de Ramer)

C’est un processus de subdivision qui peut être entrepris soit de façon récursive (chaque segment créé fait
l’objet d’une nouvelle subdivision), soit de façon itérative (la courbe  est considérée globalement à chaque étape).
C’est cette dernière version que nous examinons sur l’exemple de la figure 5.13. Les sommets du polygone sont
choisis successivement comme les points de  les plus éloignés des cordes précédemment tirées. Le processus
s’arrête lorsque la nouvelle distance candidate est inférieure à un seuil  fixé. Très employé dans de nombreuses
applications par la simplicité de sa mise en œuvre, l’algorithme de la corde n’est pas très rapide. Il ne garantit pas
non plus une convergence
,
uniforme vers la courbe ,finale" car, dans son implémentation itérative, il se peut que la
distance à l’étape soit supérieure à celle à l’étape  .
M1

M1
M3 A B

A B
A B
M2

M3

M2

A B


  
 
F IG . 5.13 – Algorithme de la corde. Les
 points et sont successivement sélectionnés pour créer la
ligne polygonale représentant la courbe . Le critère de sélection est la distance maximale à la corde polygonale
précédemment obtenue.

Algorithme de Dunham

Dans cette méthode on cherche à supprimer les cordes successives qui sont presqu’alignées. On se fixe donc
une tolérance angulaire  . Partant de , on couvrira par une même corde tous les points de la courbe qui se
78 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES

trouvent dans la tolérance et l’on choisira le premier point du polygone comme le dernier point de cet ensemble.
Le processus est répété en ce point.

Algorithme de Wahl et Danielsson

Son objectif est de minimiser l’aire laissée entre la courbe et la ligne polygonale.

B
M2
M1

M1
M2
B
A M3

M3
A

 et
  
 
F IG . 5.14 – Algorithme de Dunham, à gauche, les points sont choisis lorsque la tolérance angulaire
 est insuffisante à approximer la courbe. A droite, algorithme de Wahl et Danielsson : il cherche un minimum des
surfaces laissées entre la ligne polygonale et la courbe.

Algorithme progressif

Enfin, un algorithme progressif utilise le critère de distance de tout point de la courbe au segment d’approxi-
mation, mais dans un schéma progressif. Dans ce schéma, partant d’une extrémité, la courbe est parcourue, et le
point courant est retenu comme extrémité d’un segment d’approximation s’il est le dernier point visité permettant
une approximation de tous les points déjà visités, à une tolérance  donnée.

5.6.3 Approximation par des splines

L’approximation d’un ensemble de points de contours par des polynômes d’ordre plus élevé que les droites est
une bonne façon de représenter ce contour [Chalmond, 2000]. Le choix du degré du polynôme se fait généralement
de façon à assurer des propriétés de continuité au contour obtenu :
– les segments de droite (degré 1) assurent la continuité du contour,
– les approximations par polynômes d’ordre 2 permettent d’avoir des dérivées continues,
– les polynômes d’ordre 3 permettent d’avoir des courbures continues.
Les fonctions splines sont de bons candidats pour ce type d’approximation. Nous en avons déjà vu l’usage
à diverses occasions : au chapitre 1.4.2 lorsque nous avons discuté du rééchantillonnage des images, au chapitre
3.5.2 lorsque nous avons estimé des fonctions régulières lors de segmentation par régions. Deux types de fonctions
peuvent être utilisées [Unser et al., 1993a, Unser, 1999] :
1. les fonctions interpolantes qui passent exactement par tous les points de contours qui sont utilisés pour
calculer la spline ;
2. les fonctions approximantes qui ne passent pas nécessairement par les points mais qui s’en approchent de
façon contrôlée.
5.6. APPROXIMATIONS POLYNOMIALES 79

Approximation
%

Dans le cas des( fonctions approximantes, on définit la spline d’ordre par morceaux en fonction d’une variable



 
continue , et des points de contrôle



qui la déterminent.  et sont des fonctions de même dimension :
des vecteurs de  si les points sont définis par leurs coordonnées du plan ou des vecteurs de  dans l’espace.

Le morceau est défini par :
#  

 
$ 

   


 
#
 

(  % * "
(5.3)

Q4
P4

P3
Q3

P1
Q1 Q2
P2

F IG . 5.15 – Dans le cas d’une interpolation spline, les jonctions entre les morceaux de splines sont les points de
contrôle eux-mêmes.
#
#

Les fonctions  sont définies à partir des fonctions  qui ont été introduites au chapitre 1.4.2 équations
1.32 et suivantes :  "
#
$ # 
 


$

Les positions des points de raccord entre splines sont données par dans l’équation 5.3 :
#  

 
 

   


 
#

(5.4)

Il y a de nombreuses façons de définir les variables . La plus naturelle consiste à considérer que les échantillons

curviligne le long du contour), alors

#
$
sont régulièrement distribués en fonction de (attention
#
et #  

" cela
$& conduit à une paramétrisation où n’est pas l’abscisse
, on peut réécrire cette équation [Goshtasby et al., 1990]
sous la forme : #  
  

   


 
#


 #

qui prend la forme d’une convolution :  . Ceci montre que les  sont des points filtrés issus des .

Interpolation

Dans ce cas, les coefficients des splines de l’équation 5.3 sont inconnus et l’équation devient :
#  

 


      
#
 &(

(  % * "
80 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES

et les coefficients inconnus  sont déterminés en contraignant les splines à passer par les points de contrôle  :

#  



$



    
#


dont on a vu au chapitre 1.4.2 les divers modes de résolution soit par inversion de matrice soit par filtrage (cf. figure
5.15).

5.7 Transformation de Hough

La transformation de Hough est un outil de traitement des images dont l’usage déborde largement l’application
pour laquelle nous la présentons maintenant [Ballard, 1978, Sklansky, 1978, Maı̂tre, 1985]. Ces applications seront
vues plus tard. Nous nous intéressons actuellement au sous-problème suivant :


Connaissant un ensemble de pixels (potentiellement bruité) appartenant à une frontière que l’on sait poly-
gonale, comment déterminer le nombre de segments impliqués dans cette ligne polygonale et leur position ?
Exprimé dans les termes que nous avons vus précédemment, on se retrouve devant un difficile problème de
mélange. Les solutions combinatoires (où l’on recherche systématiquement les classes possibles) sont généralement
inacceptables. La transformation de Hough nous propose au contraire une solution élégante.
Elle consiste à transformer un problème inconnu (retrouver des droites) en un problème mieux connu : retrou-

de points. Ceci s’obtient en associant à l’espace de l’image (dénoté et défini par ses variables


ver des nuages
d’espaces
 ), un espace


 dénoté par (dans le cas où l’on recherche des droites représentées

*
de paramètres,
par l’équation , on a
 ). Pour faire cette transformation il y a 2 façons : la transformation de
Hough de 1 à m et la transformation de Hough de m à 1.

5.7.1 Définitions
Transformation de 1 à m



 

Dans cette définition,
 *


on associe à tout point
 de toutes les droites du plan. Elles sont définies




dans par : , ce qui est l’équation
(
d’une droite. A un point de est associée une droite de (d’où
le nom de 1 à m : à 1 point sont associés points, many en anglais) et à un point de une droite de .



Lorsque l’on transforme tous les points de par la transformation, on associe à un ensemble de
droites


qui, idéalement, se coupent en des points # . Le nombre de transformations à faire est . Les
# #


transformés des sont les droites cherchées dans . Ces points s’obtiennent aisément en ne conservant que
les intersections des droites de et en recherchant les nuages d’intersections (figure 5.16).

Transformation de m à 1



  , une droite  de  
 

Dans cette définition, on choisit d’associer à tout bi-point

    qui se transforme
 


7
en un unique point  de . Les coordonnées et


du point  se déduisent immédiatement de l’équation
de  . En combinant tous les couples

 "
  

de points de , on obtient tous les points  de . Le nombre de transfor-


mations à accomplir est . L’espace de Hough est alors constitué de points que l’on identifie
immédiatement aux intersections des droites obtenues par la transformation de 1 à m.
On se ramène donc, comme précédemment, à la recherche des nuages de points les plus denses du plan .

7 la dénomination  m à 1  se traduirait alors précisément par  2 à 1 , attention,   n’a pas la même signification dans les 2 définitions.
5.7. TRANSFORMATION DE HOUGH 81

b
B
y

A
a

Mk

x
∆k



F IG . 5.16 – Transformation de Hough de 1 à m. Un point # est transformé en une droite # de l’espace des
paramètres
 . On a représenté quelques-unes seulement de toutes les droites existantes. Elles définiront fina-
lement 2 points d’intersection, l’un en A, l’autre en B.

Passage d’une TH à l’autre

Il est assez simple de montrer que l’accumulateur de la TH de m à 1 se déduit de celui de la TH de 1 à m par

un seuillage au niveau 1. Ces deux transformations sont donc tout à fait équivalentes dans leurs résultats.

b
y

Mj

Q jk

Mk

 
  #
F IG . 5.17 – Transformation de Hough
de m à 1. Deux points définissent une droite qui se transforme en 1
point   # de l’espace des paramètres .
82 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES

Généralisation

On appellera transformation de Hough associée à une forme paramétrée par les variables
 la transformation 
qui fait passer de l’espace image à l’espace des paramètres .



La transformation est de 1 à m si on associe à un point de la variété de décrivant ( toutes les formes passant

par ce point. La transformation est de m à 1 si l’on associe à toutes les combinaisons points de une seule
forme (donc un point unique de ).
, (
Il existe généralement de, nombreuses transformations de n à m ( ), où l’on se place dans une situation
intermédiaire : en associant points de on limite le sous-espace d’arrivée à une partie de la variété de la trans-
formation de 1 à m. Par exemple, on peut utiliser simultanément la position d’un point de contour et la direction de
la tangente en ce point. Ces problèmes n’étant pas directement liés à la recherche de contours, des exemples seront
vus plus loin.

TH et filtrage adapté

Sklansky [Sklansky, 1978] a démontré qu’il y a équivalence entre la TH et la détection par filtrage adapté (par
 
mais fréquente. Si les seules inconnues d’un problème de détection sont
corrélation) dans une situation particulière
les deux translations du plan ( 
et 
 ), c’est à dire si la forme ne subit ni changement 
d’échelle

($ " ni
rotation,

 ni
transformation perspective. Soit

(
la forme caractéristique de l’objet disponible ( si appar-
tient au contour de l’objet, et 0 sinon). Soit la forme recherchée. Le filtrage adapté conduit à une détection
optimale au sens de l’erreur quadratique moyenne, en recherchant les maximums de la fonction de corrélation :


   (
 

(
  
  (



(
   (




(
Cette démonstration est assez simple si l’on voit que chaque point
 de coordonnées de l’image
est
 
candidat à être associé à un point quelconque de de coordonnées 
  
&
 
si l’on décale du vecteur

(


figure
(cf. 5.18). Cette contribution à l’accumulateur de position vaut exactement :
. Sommé sur toute la courbe on obtient :


$ 
     (
  

(
  
 



 
  
(

Ce qui est bien le résultat cherché. En fait on montre que la TH agit en pratique en inversant l’ordre des
 rapport au filtrage adapté. Celui-ci procède usuellement en calculant l’intégrale ci-dessus pour un
intégrales par
décalage donné, en sommant sur tous les points du plan tandis que la TH choisitun point du plan et incrémente
toutes les intégrales (les compteurs) qui lui sont asssociées par un déplacement quelconque. Cette inversion
des opérations peut permettre de tirer profit d’a prioris importants pour accélerer les calculs.
Grâce à cette propriété la TH peut hériter des nombreux résultats obtenus en filtrage adapté : pour prendre en
compte le rôle du bruit si celui-ci à une densité de probabilité connue, pour déterminer la taille des accumulateurs
lorsque la PSF est connue, etc. [Maı̂tre, 1985, Princen et al., 1992].

5.7.2 Mise en œuvre de la TH

Discrétisation de


   de largeur    est appelée accu-
Dans la pratique le plan est discrétisé. Chaque cellule de position
mulateur. Elle contiendra un nombre d’autant plus important que la droite


  sera plus probable dans
*

.
5.7. TRANSFORMATION DE HOUGH 83

f(x,y)
f

(x−u,y−v) g(u,v)




F IG . 5.18 – Transformation de Hough : le point 
 

de coordonnées de f sera associé au point de g si l’on
fait subir à cette courbe g une translation de  .

Au début de la transformation, tous les accumulateurs sont à zéro. Les points sont alors visités successivement
(individuellement dans la TH de 1 à m, combinatoirement pour les autres). Chaque hypothèse donne naissance à
des votes pour des cellules particulières. Pour chaque vote, l’accumulateur de la cellule est incrémenté de 1.


Lorsque tous les candidats ont voté, on recherche les accumulateurs de de comptes localement maximaux.
Le choix de la taille des accumulateurs est donc un problème délicat.

1. Des accumulateurs trop petits recevront très peu de votes et donneront des statistiques peu significatives.
On ne saura décider de la position d’un maximum entre plusieurs cellules voisines de comptes faibles et
proches.

2. Des accumulateurs trop grands donneront une mauvaise précision dans la détection de la droite.
 

Par ailleurs, la mise en œuvre de la TH nécessite un espace mémoire de taille   
où et représentent les
domaines de variation de et .
Des solutions ont donc été proposées pour adapter localement la taille des accumulateurs (très précis près des
lieux où les votes sont nombreux). Cela peut se faire dynamiquement par des approches de subdivision récursive
des cellules (selon le principe des quad-tree cf. 3.2.4), ou par des passages successifs sur l’ensemble des points de


, le premier passage permettant de dimensionner les cellules.

Ce problème est particulièrement important dans le cas où l’on recherche des formes possédant de nombreux
paramètres, puisque l’espace est l’espace produit de tous ces paramètres. Il est alors de grande dimension.
84 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES

Paramétrisation des formes

Le choix d’une bonne paramétrisation des formes recherchées apparaı̂t immédiatement à la lecture du para-
graphe ci-dessus si l’on souhaite

appliquer
*
la démarche proposée à la recherche de droites. Dans le cas d’une
paramétrisation cartésienne ( ), les domaines de variation de et sont potentiellement de moins l’in-
fini à plus l’infini, conduisant à un insoluble problème de résolution
  (examine
 de cellule. Par ailleurs, si l’on "  la  
variable "'par
pour
 statistiquement, elle décrit $

  , conduisant donc à des cellules qui seront très inégalement remplies si leur taille est uniforme.
exemple, on voit que, des droites du plan pour et $

On peut cependant choisir une paramétrisation

plus*
heureuse pour la droite, par exemple la
paramétrisation
est repérée par la distance  et l’angle .
 
normale (cf. figure 5.19). Dans ce cas la droite
  

*
 

La transformation de 

1 à m s’écrit :  , et la forme associée à un point est donc une sinusoı̈de
dans l’espace  , d’équation :

*

 



*  
avec : 
 
  
*"

. 
 



distances  . Elle fournit également des domaines de variation finis :   * équiprobables,
Cette paramétrisation est tout d’abord homogène puisque les angles
sont a priori
et 
( ainsi que les
$ si L est
 % %
le côté de l’image, puisqu’une droite dont  serait supérieur à la longueur de la diagonale de l’image ne serait pas


visible dans l’image.  
La transformation de m à 1 associe au doublet
 
le point de de coordonnées :

     
        

    
   



      

y ∆i
ρ
Mi
ρ
θ
x
θ





F IG . 5.19 – Transformation de Hough de 1 à m en coordonnées normales. Une droite est repérée par l’angle
et la distance au pied de sa normale  . Dans l’espace , chaque point donne une sinusoı̈de.

5.7.3 Détections par TH

La TH est très souvent utilisée, comme nous l’avons vu précédemment, pour détecter des droites. Les autres
courbes paramétrées détectées par la TH sont :
1. les paraboles (3 paramètres si l’on connaı̂t la direction de leur axe, 5 dans le cas général). Par exemple pour
détecter des côtes dans les radiographies du corps humain) ;
5.8. CONCLUSION 85

2. les cercles (3 paramètres) par exemple pour détecter des cuves ou des citernes en imagerie aérienne. On
paramètre alors le cercle par son centre et son rayon et la forme associée dans cet espace est un cône, centré
au centre du cercle.
3. les ellipses (5 paramètres : les 3 du cercle + la direction de l’axe et l’applatissement ou l’ellipticité),
également utilisée pour détecter des formes circulaires vues en perspectives.
4. des traces sinusoı̈dales (5 paramètres), forme fréquemment recherchée en expérimentation en physique ou
en géologie.
La TH est également utilisée pour suivre des formes quelconques sous des hypothèses de transformations
particulières. Les paramètres sont alors ceux qui caractérisent la déformation : changement d’échelle, rotation à 2
ou 3 D, projection perspective, etc.

5.8 Conclusion
Il n’est pas possible d’épuiser toutes les variétés des représentations et des modélisations qui ont été adoptées
pour décrire les formes des objets en traitement des images. en effet, beaucoup de ces représentations tiren profit
de spécificités attachées à la famille particulière des objets à traiter pour une application donnée dans un contexte
précis. Nous avons cependant vu que toutes les représentations cherchent à marier la simplicité de la description et
la fidélité à la forme. En cela, elles relèvent déjà toutes de la reconnaissance des formes, puisque ces deux objectifs
sont aussi ceux que la reconnaissance des formes se donne.
86 CHAPITRE 5. DESCRIPTION DE CONTOURS ET DE FORMES