CHAPITRE IV

Triangulation De Delaunay

Table des Matieres :

IV.1 INTRODUCTION *

IV.2 DIAGRAMME DE VORONOÏ *

IV.3 LA TRIANGULATION DE DELAUNAY *

IV.4 LA TRIANGULATION DE DELAUNAY CONTRAINTE *

IV.5 PRINCIPAUX CALCULS DES PARTITIONS *

IV.5.1 METHODES INCREMENTALES *

IV.5.2 MÉTHODES GLOBALES *

IV.6 PARTITIONNEMENT ADAPTÉ AU CONTENU DE L'IMAGE *

IV.6.1 ALGORITHME DE DIVISION ET FUSION *

IV.6.2 ALGORITHME DE DIVISION SIMPLE *

IV.6.3 TRIANGULATION CONTRAINTE PAR LES CONTOURS *

IV.7 CONCLUSION *

IV.1 INTRODUCTION

        Nous avons vu dans le chapitre précédant que différents partitionnements de l’image ont été étudiés de façon à minimiser le nombre de transformations locales et à coder au mieux les similarités inter-blocs. Nous décrivons dans ce chapitre un nouveau type de partitionnement, qui s’adapte au contenu de l’image et qui est calculé à partir d’un ensemble de points positionnés n’importe où sur le support de l’image, c’est le partitionnement de Delaunay.

    En effet, au milieu du 19^ieme siècle, un problème majeur de géométrie, celui des Diagrammes de Proximité, s'était posé dans une motivation mathématique (ex : Démonstration de l'unique réductibilité des formes quadratiques, Dirichlet) ou physique (ex : Croissance et arrangements cristallins)[AUR 91]. Ce fut Voronoï, mathématicien russe, qui formalisa en premier cette notion. Par la suite, Delaunay un autre mathématicien russe qui l'a formalisé et étendu. Ainsi fut définie la Triangulation de Delaunay, obtenue en reliant par une arête les points dont les régions correspondantes dans le diagramme de Voronoï sont adjacentes, que nous détaillerons dans la suite de ce chapitre.

IV.2.1 POINTS, SITES, GERMES 

On désigne par P un ensemble composé de n points P_i de l’espace IR² appelés aussi sites ou germes :

IV.2.2 Arête

Le segment ou l'arête est repéré par deux points d'appui x et y.

IV.2.3 Region de Voronoï 

On appelle polygone de Voronoï associé au site P_i la région Vor(P_i) (chaque région étant l'ensemble de points (x,y) les plus proches à un point de P) telle que chaque point de P a pour plus proche site P_i.

ou d représente la distance Euclidienne.

 IV.2.4 Diagramme de Voronoï  [dav 95]

On décrit le diagramme de Voronoï comme l’union des régions de Voronoï de tous les points.

Figure IV. 2 : Diagramme de Voronoï de l'ensemble P formé de N points.

 Chaque sommet du diagramme de Voronoï est le point de rencontre de trois arêtes de Voronoï

‚ Pour chaque sommet S du diagramme de Voronoï, le cercle passant par les trois points voisins à ce sommet, ne contient aucun autre point de P.

Figure IV. 4 : Le cercle ne contient aucun autre point de P, c’est un diagramme de Voronoï.



Figure IV. 5 : Le cercle contient un point de P, ce n’est pas un diagramme de Voronoï.

ƒ Une arête de Voronoï sépare tout point de son plus proche voisin.

 Figure IV. 6 : Une arête sépare un point de son plus proche voisin.

IV.3 LA TRIANGULATION DE DELAUNAY [DAV 95]

On peut à partir du diagramme de Voronoï, en construire le dual (figure IV.7), c’est à dire construire un nouveau diagramme où cette fois, on relie par un segment toutes les paires de sites dont les régions de Voronoï correspondantes sont adjacentes, c’est à dire séparées par une arête de Voronoï.

 Figure IV. 7 : Construction du dual.

Nous donnons alors le théorème fondamental suivant [VOL 92]:

Le dual du diagramme de Voronoï est une triangulation sur l’ensemble des points.

Ce théorème est démontré en vérifiant que ce dual définit une partition du domaine intérieur à l’enveloppe convexe de l’ensemble des points. En ayant remarqué de manière préliminaire qu’à chaque sommet de Voronoï correspondait un triangle du dual, on vérifie pour cela que :

• Un triangle intersectant l’intérieur de l’enveloppe convexe n’est pas plat.
• Pour une paire de sommets de Voronoï donnée, si les cercles associés à ces deux sommets ont une intersection sachant qu’ils ne peuvent être l’un à l’intérieur de l’autre, alors les deux points d’intersections qu’ils définissent forment un segment séparant les deux triangles correspondants.
• Chaque point intérieur à l’enveloppe convexe est aussi contenu dans au moins un triangle.
• On définit la triangulation de Delaunay d’un ensemble de points du plan comme étant la dual du diagramme de Voronoï correspondant (figure IV.8).

Figure IV. 8 : La triangulation de Delaunay, duale du diagramme de Voronoï.

On peut par la dualité et non colinéarité de tous les points et non cocyclicité de quatre points déduire des résultats portant sur le diagramme de Voronoï les propriétés suivantes:

• La triangulation de Delaunay est unique.
• La triangulation de Delaunay est une triangulation complète.
• Les cercles passant par les trois sommets de chaque triangle ne contiennent aucun autre site en leur intérieur.

 Figure IV. 9 : (a) Triangle non-Delaunay – (b) Triangle Delaunay

Cette dernière propriété est essentielle, et elle va être utilisée pour caractériser la triangulation de Delaunay sans avoir à recourir à la dualité avec le diagramme de Voronoï. Elle va aussi être utilisée comme critère de choix des triangles à construire, lors de l’exécution d’une triangulation.

IV.4 La TRIANGULATION DE DELAUNAY CONTRAINTE 

Certaines applications peuvent nécessiter que des arêtes soient imposées dans la triangulation, sans que celles-ci soient nécessairement en accord avec les arêtes de la triangulation de Delaunay. On va alors générer une triangulation qui, tout en respectant ces

arêtes, aura par ailleurs les propriétés d’une triangulation de Delaunay normale. On parle alors de Triangulation de Delaunay Contrainte.

On restreint le critère de validité d’un triangle de Delaunay aux points visibles de tous les sommets du triangle vis-à-vis des arêtes de contrainte (Un point est dit visible d’un autre vis-à-vis d’un objet si on peut les relier entre eux par un segment qui ne coupe pas l’objet). Dans le critère du cercle, cela revient à ne pas prendre en compte l’appartenance de sommets de graphe à la partie du cercle se situant derrière cette arête par rapport au triangle.

 Figure IV. 10 : Triangle de Delaunay Contraint.

Inspiré de la définition de la triangulation non contrainte, Seidel dans son article

[SEI 88] définit la triangulation contrainte comme suit :

Une triangulation de Delaunay contrainte est une triangulation complète pour laquelle chaque contrainte est une arête de la triangulation et que pour chaque autre arête, il existe un cercle tel que :

• Les points extrémités de l’arête se situent sur le cercle.
• Si un point se trouve à l’intérieur du cercle, alors il existe au moins un des deux points extrémités d’arêtes auquel on ne peut le relier par un segment sans couper une contrainte.

IV.5 PRINCIPAUX CALCULS DES PARTITIONS

Il existe différentes techniques pour la construction du diagramme de Voronoï et de Delaunay. Ces techniques se décomposent essentiellement en deux classes :

• Approches incrémentales qui fonctionnent d’une manière dynamique.
• Approches globales appliquées sur un ensemble prédéfini de points.

IV.5.1 Methodes Incrementales

Leur principe est simple : on commence par générer un grand triangle qui inclut tous les points situés sur le support de l’image, puis on "ajoute" ces points un par un par subdivision du triangle dans lequel ils se trouvent et par modification éventuelle des triangles voisins (éventuellement bloquée par une arête de contrainte) .

 Figure IV. 11 : Triangulation incrémentale

Structure de données : La manipulation dynamique des données (l'insertion et la suppression des points) nécessite une structure de données adaptative et efficace pour le parcours des points dans le graphe de Delaunay.

Partant du fait que chaque sommet associé à un triangle admet exactement trois sommets voisins, alors pour chaque sommet on utilise la structure de données suivantes :

 Un champ triangle (formé de trois points).

‚ Trois pointeurs vers les trois sommets voisins.

Cette structure de données est illustrée par la figure suivante.

Figure IV. 92 : Structure de données d'un triangle.

Insertion d'un nouveau point

Pour insérer un nouveau point P_n+1 dans le diagramme de Voronoï VOR_n(P), on suit les étapes suivantes:

 - La recherche du premier sommet à supprimer:

Cette recherche est appliquée au diagramme de Voronoï afin de trouver le sommet dont le triangle dual contient le point P_n+1.

‚ - La recherche de tous les autres sommets à supprimer :

Cette étape consiste à trouver les sommets qui sont plus proches de ce nouveau point P_n+1 que de leur points générateurs ( les points des triangles duaux de ces sommets). Ceci est équivalent à trouver tous les centres des triangles pour lesquels le cercle de Delaunay contient le point P_n+1. Les triangles des sommets à supprimer forment un polygone étoilé. La recherche nécessite le stockage d'une liste de points ordonnés des triangles supprimés.

 

ƒ - Construction de la nouvelle triangulation de Delaunay à l'intérieur du polygone :

Elle consiste à former des triangles à partir du point central P_n+1 et les points des extrémités déjà stockés, et de créer tous les sommets de Voronoï correspondants aux nouveaux triangles ainsi que la mise à jour de leurs relations de voisinage (maj des pointeurs).

La figure ci-dessous montre le changement local de triangulation après l'insertion d'un nouveau point P.

IV.5.2 Méthodes Globales 

La méthode la plus connue est la méthode dénommée "Diviser pour Construire" (divide and conquer). Elle est calculée sur un ensemble de points distribués sur le support de l’image en utilisant un algorithme récursif. Le principe est de décomposer récursivement un grand problème en plusieurs sous problèmes indépendants de plus petite taille et à en rassembler les résultats.

L’inconvénient de cette méthode est qu’elle ne permet pas l’insertion et la suppression des points dans le diagramme de Voronoï ; elle nécessiterait une réévaluation complète du diagramme.

Dans le problème de triangulation, cette méthode est dans la plupart des cas implantée dans des algorithmes où NbPointListe consiste à mailler un unique point, la partition revient à découper l'ensemble des points en deux sous ensembles de taille comparable, séparable par une droite, et la fusion revient à relier deux sous triangulations en une seule par adjonction des triangles intermédiaires.

l'Algorithme de Lee et Schacter

Il est basé sur la méthode "Diviser pour Construire" destiné à construire une triangulation de Delaunay sans contraintes [VOL 92] .

Présentation de l'Algorithme

Le "Diviser pour Construire" est adapté de la triangulation comme suit :

Les différentes étapes de l’algorithme sont les suivantes :

Avant d'entamer la récursion, on trie la liste des points lexicographiquement selon une direction donnée.

Le tri lexicographique correspond à trier les points par comparaison des projections sur un axe de la direction donnée, et en cas d'égalité pour deux points, les comparer sur la direction orthogonale. Ce tri assure la séparabilité de deux demi-ensembles par une droite infiniment peu décalée par rapport à la direction orthogonale au tri, quelle que soit la disposition des points.

2. La partition de la liste des points en deux sous-listes

La partition de l'ensemble des points s'effectue par découpage de la liste de ces points préalablement triée lexicographiquement en deux sous-listes de tailles à peu prés égales.



Figure IV. 126 : La partition en deux sous-listes.

3. La triangulation séparée des deux sous-listes

Il s'agit simplement d'un appel récursif pour trianguler indépendamment les deux sous-listes de points. Cette indépendance est garantie par la séparabilité des deux sous-ensembles par une droite.



Figure IV. 137 : Triangulations.

On obtient donc deux domaines convexes triangulés. Ces deux domaines sont disjoints et séparables comme précédemment par une droite orthogonale à la direction de tri.

4. La fusion des deux sous-triangulations

Il faut ensuite réunir les deux sous-triangulations en une seule par adjonction des triangles dans la "région interne" – qui est la partie interne à la nouvelle enveloppe convexe séparant les deux enveloppes convexes précédentes – est limitée aux extrémités par deux segments reliant les domaines entre eux qui correspondent à l'enveloppe convexe de la réunion des deux domaines, qu'il convient tout d'abord de déterminer.

La fusion s'effectue donc en deux étapes successives :

 - La détermination des deux segments d'enveloppe convexe.

‚ - Le remplissage de l'espace interne qu'ils délimitent.

IV.6 Partitionnement Adapté au Contenu de l'Image

Nous détaillons dans cette partie quelques algorithmes de partitionnement en triangulation de Delaunay du support d’une image en niveaux de gris. Cette partition est qualifiée de souple puisqu’elle retourne la triangulation de l’enveloppe convexe d’un ensemble quelconque de points, distribués sur le support de l’image.

Au cours de la construction de la partition, et lorsque celle-ci est entièrement calculée, chacun des éléments triangulaires est caractérisé par la valeur moyenne et la variance des niveaux de gris qu’il englobe. Ces paramètres peuvent ensuite être utilisés directement au cours du codage par fractales.

IV.6.1 Algorithme de Division et Fusion

Première étape : phase d'initialisation

On dispose d'un ensemble de points distribués régulièrement sur le support de l'image formant un maillage triangulaire. La taille et la forme des triangles, dans cette étape, ne dépendent pas de leurs caractéristiques (variance et moyenne).

Deuxième étape : phase de division

A partir de l'ensemble de triangles initiaux, on insère de nouveaux points sur le barycentre des triangles (annexe A) qui ne vérifient pas le prédicat d'homogénéité (un bloc est déclaré homogène si la variance des niveaux de gris de celui-ci est inférieure à un seuil donné), et on calcule la nouvelle triangulation sur le polygone étoilé généré par l'ensemble des triangles supprimés.

L'algorithme de division est implémenté ci-après:

Troisième étape : phase de fusion

Cette étape consiste à regrouper tous les blocs (triangles) homogènes et de même amplitude ( les triangles sont de même amplitude si la différence maximale entre leur valeur moyenne des niveaux de gris demeure inférieure à un seuil T_amp ).

L'ensemble de ces triangles forme un polygone étoilé. L'intérêt de cette étape est d'éliminer tous les points centraux de ces polygones, ce qui diminue le nombre des triangles après la nouvelle triangulation de tous les polygones étoilés.

La triangulation obtenue après la fusion contient des triangles de grandes tailles sur les régions homogènes de l'image et des autres de petites tailles sur les régions textures ou avec contours.

Une solution très rapide pour calculer une partition de Delaunay adaptée au contenu de l'image consiste à n'opérer qu'une seule étape de fusion après la phase d’initialisation.

IV.6.2 Algorithme de Division Simple

C’est l’algorithme précédent, sauf l’étape de fusion qui n’est pas appliquée.

IV.6.3 Triangulation Contrainte par les Contours

Cette partition est telle qu’en moyenne, les bords des triangles s’appuient sur les frontières d’orientation quelconque de l’image. La plupart des blocs ainsi générés le long d’un même contour se ressemblent et sont homogènes. Le partitionnement est adapté à la forme des objets de l’image.

La triangulation contrainte est calculée sur un ensemble P de points obtenus selon l’algorithme détaillé ci-dessous en quatre points :

 détecter les principaux contours de l’image.

‚ échantillonner les contours en plaçant des points aux endroits de forte courbure.

ƒ ajouter des points régulièrement espacés sur les contours, entre chacun des points précédemment détectés. L’écart entre les points ajoutés est noté d₁.

„ placer des points supplémentaires de chaque coté des contours, perpendiculairement aux segments. L’ajout d’un de ces points se fait dans un contexte de contrôle de proximité vis à vis des autres points déjà insérés.

CONCLUSION