Remerciements table des Matières Introduction 1

6.3 Approximation Polygonale

Le but de l'approximation polygonale est de construire une représentation polygonale d'un contour ou d'une frontière de région : les points significatifs vont être les sommets de la ligne polygonale.

Les chaînes de contours peuvent être partitionnées dans des segments de courbes qui ont une description connue, telle des lignes droites et des coniques. La plus simple description d'une courbe est la ligne droite mais dans de nombreux cas ce n'est pas suffisant, surtout pour le genre d'application qui nous intéresse (optimisation de la détection des points de fortes courbures), l'utilisation de courbes du deuxième ordre s'avère alors nécessaire.

Dans un premier temps nous allons détailler les méthodes permettant à l'aide d'une chaîne de points de calculer les paramètres d'un segment de droite ou d'un arc de cercle passant par les points de cette chaîne. Dans un deuxième temps nous décrirons une méthode permettant de réaliser un découpage d'une chaîne de points en segments de droite et en arcs de cercle. Ce type de traitement améliore sensiblement la qualité de l'image une fois vectorisée, tout en diminuant de façon importante le nombre de segments par rapport à la seule utilisation de segments de droite. Les algorithmes d'approximation d'un segment par une droite et de découpage sont issus des travaux de T. Pavlidis [PAVLIDIS74].

6.3.1 Approximation d'un segment par une droite

Soit l'équation d'une droite :

[6.1]


Figure 6.10 : La paramétrisation d'une droite utilise la distance à l'origine et l'inclinaison par rapport à l'axe horizontal

La distance du point [xi,yi] à cette droite est :

[6.2]

Le but étant de trouver la droite (les paramètres et d) qui minimise la grandeur :

[6.3]

L'ensemble des paramètres de la droite est la solution du système d'équations :

[6.4]

Après calcul, on obtient pour d et :

[6.5] [6.6]

avec :

[6.7]

[6.8]

[6.9]

[6.10]

[6.11]
Pour qu'une chaîne de points soit correctement approximée par un segment de droite, il faut que la somme des distances des points de la chaîne au segment, soit égale à zéro. Mais ce faisant, on multiplie le nombre de segments de droite de faible dimension. Afin de tenir compte des petites déviations il est nécessaire d'augmenter la marge d'erreur, cela permet d'obtenir des segments de droite de plus grande dimension mais également dans quelque cas d'améliorer la qualité du contour. Pour les images que nous traitons et dans le but de privilégier l'approximation par les segments de droites par rapport aux arcs de cercle, la marge d'erreur appliquée aux segments de droite à été fixée à 1.5 pixels (1 pour les cercles).

6.3.2 Approximation d'un segment par un cercle [HORAUD 95]

La détection d'arcs de cercles à partir d'éléments de contour de forme quelconque est un problème similaire.

Soit l'équation d'un cercle :

[6.12]

Avec les notations suivantes :

A =

B =

C =

L'équation du cercle peut s'écrire alors :

[6.13]

La distance d'un point à un cercle s'écrit :

[6.14]

Cependant ceci conduit à un problème d'optimisation non linéaire. La distance euclidienne d'un point à un cercle peut être remplacée par la distance algébrique :

=

= [6.15]

Le critère à minimiser est :

[6.16]
La solution pour A,B et C est donnée par le système d'équations suivant :


[6.17]

Après dérivation on obtient :

[6.18]

Avec :

et des définitions similaires pour , etc.

On obtient donc un système linéaire à trois inconnues, A, B et C, à partir desquelles on retrouve facilement les paramètres du cercle.
Il est à noter qu'une approximation par segments d'ellipse à aussi été mis en place mais n'a donné aucun résultat concluant. Le principal problème résidant dans l'estimation du point de découpage du segment d'ellipse.

6.3.3 Algorithme de découpage

Aux paragraphes précédents, nous avons détaillé les équations nous permettant d'approximer un segment donné, soit par une droite, soit par un cercle. Pour approximer une chaîne de pixels quelconque, il est nécessaire d'utiliser un algorithme de découpage effectuant une polygonisation à l'aide des deux primitives de base (droite et cercle).

Cet algorithme se présente ainsi :

1. 
   pour une chaîne de points : est-ce un segment de droite ?
   
2. 
   si oui - aller en fin ;
   
3. 
   sinon – est-ce un cercle ?
   
4. 
   si oui – aller en fin ;
   
5. 
   sinon diviser la chaîne en deux sous-chaînes et répeter l'algorithme pour chaque sous-chaîne ;
   
6. 
   fin
   

Le choix du point de division se fait en calculant le point le plus éloigné de la chaîne à la droite passant par les extrémités de la chaîne [A,B] (cf. figure 6.11). On crée ainsi un nouveau sommet C. Le découpage va se poursuivre sur les deux sous-chaînes [A,C] et [C,B].

Par ailleurs, un autre problème peut subvenir :

Etant donné un ensemble de points approximés correctement aussi bien par une droite que par un cercle (cf. figure 6.12), quelle approximation choisir ?

Pour ce problème, on introduit un facteur d'évaluation e :

[6.19]

avec :

n : le nombre de points de la chaîne

k : le nombre de changement de signe de la séquence des vecteurs d'erreur

p : la longueur de la plus grande séquence de vecteurs d'erreurs ayant le même signe.

Dans la figure ci-dessus, k est grand et p est petit pour un cercle, alors que c'est le contraire pour une droite. Dans le cas présenté, on aura :

Ce qui veut dire que l'on préférera approximer ce nuage de pixels par un arc de cercle.

De plus d'autres problèmes peuvent subvenir, tous sont liés aux points de cassure (points extrémités limitant l'arc de cercle ou le segment de droite). C'est pourquoi une étape d'union / intersection entre les segments et arcs approximés est nécessaire après la phase de découpage.

Cette étape n'a pas encore été réalisée.

Pour le moment,

• 
  les segments sont bornés par rapport aux limites en x et en y des chaînes de pixels utilisées
  
• 
  les arcs de cercles sont découpés de la façon suivante (cf. figure 6.13) :
  

1. 
   Calcul de la distance maximale entre deux pixels de la chaîne
   
2. 
   Tracé de la droite entre ces deux pixels et calcul des intersections (P1 et P2) avec le cercle approximé : P1 et P2 seront les points de cassure.
   
3. 
   Récupération de l'arc de cercle entre P1 et P2