Remerciements table des Matières Introduction 1

6. Détection, Chaînage et Segmentation de contours

6.1 But

Toujours dans l'optique de superviser une séquence d'usinage par l'application d'un processus de vision, il a semblé intéressant de mettre en œuvre (outre la détection des Points de fortes courbures) une détection de contours efficace, suivi d'un chaînage et d'une segmentation des contours.

Ces informations sont utiles pour par exemple corréler deux images (une image modèle avec une prise de vue de la scène en cours) et ainsi savoir si la pièce à usinée présente un défaut ( d'usinage ou de positionnement) ou si l'outil utilisé est défectueux.

Ces informations sont également utilisées afin d'améliorer la détection de points de fortes courbures (l'image hystérésis de l'opérateur de filtrage pourra subir une approximation polygonale en vue d'améliorer la localisation des points caractéristiques).

6.2 Codage des contours : Chaînage d'une image

Afin d'extraire les informations précisées ci-dessus, la description matricielle des contours fournis par la détection de contours n'est pas suffisante. Il est alors nécessaire de passer à une description sous forme de liste de contours.

Dans notre application, les contours d'une image sont extraits à l'aide du filtre de Deriche par l'approximation du Laplacien.

Description :

Le codage local permet de stocker une ligne fermée ou non, il caractérise le passage d'un pixel à son successeur. La suite des codes locaux donne le codage d'un contour dans son intégralité.

L'algorithme employé est basé sur l'utilisation d'un tableau de deux lignes dont la largeur est équivalente à celle de l'image. A l'aide de ce tableau, on effectue un balayage de l'image de haut en bas. Lorsque le tableau contient un pixel dans la première ligne, on vérifie que ce pixel est celui qui est le plus à droite, s'il existe des pixels qui lui sont adjacents. Si ce n'est pas le cas, on vérifie que ce pixel possède des voisins immédiats dans la deuxième ligne du tableau.

Cette méthode permet de commencer le chaînage à partir d'une extrémité. Ce processus est important car dans la plupart des algorithmes de chaînage, le processus commence à partir du premier point rencontré, ce qui dans certaines conditions tend à augmenter le nombre de petite chaînes dans le contour traité.

On vérifie donc que le pixel est dans une des quatre configurations suivantes (cf. figure 6.1) :




Figure 6.1 : Configurations possibles de début de chaînage

Le chaînage débute à partir du pixel central, le chaînage est lancé autant de fois qu'une des conditions ci-dessus est vérifiée. Chaque fois qu'un pixel est chaîné, il est supprimé de l'image. Lorsque le chaînage d'un élément de contour est achevé, le balayage reprend là où il s'était arrêté.

Le chaînage proprement dit s'effectue à l'aide d'un tableau de direction donnant le déplacement (x,y) pour les huit directions possibles autour du pixel à chaîner. Afin de favoriser la récupération de grandes chaînes de contours, la convention de direction régulièrement employée est celle de la figure 6.2. Au vue des résultats détaillés ensuite, la convention de direction la plus intéressante semble être celle de la figure 6.3.



Figure 6.2 : Tableau des directions de recherche normalement utilisé



Figure 6.3 : Tableau des directions de recherche optimal

Dans le but de favoriser la continuité des chaînes de pixels dans une direction donnée (pour le cas 1), on effectue une rotation du tableau des directions lorsque la direction de poursuite est supérieure à 2. L'exemple donné par la figure 6.4 montre la rotation du tableau du cas 1, de la position initiale à la position de la direction 3.

Figure 6.4 : Rotation du tableau des directions de la position initiale à la position 3

L'algorithme de chaînage possède la forme suivante :

Xi, Yi, les coordonnées du premier pixel de la chaîne

X,Y, les coordonnées d'un pixel de la fenêtre, au début : X=Xi, Y=Yi

I(X,Y), image contenant les contours issus du filtrage

D=0, direction initiale de parcours de la chaîne

Procédure suivi(Xi,Yi,D)

{X=Xi;

Y=Yi;

Chaîne(X,Y);

Tant que (D<=7)

{X = Xi + tab[D];

Y = Yi + tab[D];

Si (I(X,Y) != 0)

{ I(X,Y) = 0;

Chaîne (X,Y);

Si D > 2

{

Rotation (tab, D)

D = 0;

}

}

D = D + 1;

}

}

L'étape suivante est l'approximation polygonale des contours. Cette étape permet de réduire la quantité d'informations à stocker et de lisser les contours. Elle est utilisée ici pour la comparaison des objets d'une scène. Elle pourra être aussi employée pour augmenter la précision de la détection de points caractéristiques.
Dans la partie suivante sont détaillés les résultats obtenus par l'implémentation de cet algorithme.

Les trois images de la figure 6.5 montrent :

• 
  l'image source filtrée par un filtre extracteur de contours
  
• 
  l'image formée par les points n'ayant pas été détectés par l'algorithme de chaînage
  
• 
  et l'image des contours obtenus après chaînage de l'image source.
  

On peut voir que certains points n'ont pas été retenus par l'algorithme de chaînage, ce sont principalement des points isolés ou des points de contours mais appartenant à un contour épais de plus d'un pixel.

Figure 6.5 : Exemple de chaînage obtenu sur image réelle

Des performances de l'étape de chaînage, vont dépendre celles de la vectorisation. Plus les chaînes de contours seront longues, meilleurs seront les vecteurs obtenus. La figure 6.6 montre l'exemple d'une intersection ou triple jonction. Le chaînage III est celui qui aura le plus de chance de correspondre à un chaînage idéal, et donc de récupérer une longue chaîne de contour.

I

III

II

Figure 6.6 : Exemples de chaînages incorrects (I et II) et correct (III)

L'algorithme de chaînage développé tient compte de ce type de difficulté. Cela a permis d'obtenir de bonnes performances par rapport au nombre de chaînes récupérées ainsi que leur longueur.

Résultat : Trois images (cf. figure6.7) ont été employées pour estimer les performances de cet algorithme de chaînage en fonction des deux tableaux de direction employés.

Toutes ces images sont de taille 256 * 256 en 2 niveaux de gris. Les deux premières sont des images de synthèses représentant une image hystérésis. La dernière est une image des contours obtenus après application de l'opérateur Laplacien de Deriche et seuillage par hystérésis.

La méthode 1 correspond à l'application de l'algorithme de chaînage avec le tableau des directions initial, la méthode 2 correspond au même algorithme, mais avec le tableau des directions optimisées.



Image 1

Image 2

Image 3

Figure 6.7 : Echantillon d'images utilisées pour l'évaluation de l'algorithme de chaînage

Les résultats expérimentaux obtenus sont présentés dans le tableau de la figure 6.8 :

L
Figure 6.8 : Résultats expérimentaux obtenus sur images testées

a méthode 2 semble donc plus performante, que ce soit au niveau du nombre de pixel éliminés ou que ce soit au niveau du nombre de chaînes. Ces résultats sont normaux car de par la forme du tableau des directions de la méthode 2, il est simple de comprendre que les directions privilégiées s'échellonnent entre –45° et +45°. Or la plupart des discontinuités d'un contour se trouvent orientées à 90°.

Exemple :

Soit l'image initiale coorespondant à un zoom sur un contour (en noir)

Y

X





Figure 6.9 : Exemple de contour

Pour ce cas simple, l'application de la méthode 1 abouti à 1 chaîne de 12 pixels. Le pixel (70,50) n'est pas chaîné, de par les directions privilégiées du tableau des directions.

L'application de la méthode 2 sur cet exemple permet en outre de récupérer tous les points.

L'étape de chaînage étant primordiale pour la mise en place d'une bonne approximation polygonale, seule la méthode 2 sera utilisée par la suite.