CHAPITRE IV
Triangulation De Delaunay
Table des Matieres :
IV.3 LA TRIANGULATION DE DELAUNAY *
IV.4 LA TRIANGULATION DE DELAUNAY CONTRAINTE *
IV.5 PRINCIPAUX CALCULS DES PARTITIONS *
IV.6 PARTITIONNEMENT ADAPT� AU CONTENU DE L'IMAGE *
IV.6.1 ALGORITHME DE DIVISION ET FUSION *
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 19ieme 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.
On d�signe par P un ensemble compos� de n points Pi
de l’espace IR2 appel�s aussi sites ou germes : 
Le segment ou l'ar�te est rep�r� par deux points d'appui x et y.
On appelle polygone de Vorono� associ� au site Pi la r�gion Vor(Pi) (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 Pi.
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.
IV.2.5 Propri�t�s du Diagramme de Vorono�
Chaque sommet du diagramme de Vorono� est le point de rencontre de trois ar�tes de Vorono�
Figure IV. 3 : Trois ar�tes autour d'un sommet 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 :
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:
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 :
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 :
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 Pn+1 dans le diagramme de Vorono� VORn(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 Pn+1.
‚ - La recherche de tous les autres sommets � supprimer :
Cette �tape consiste � trouver les sommets qui sont plus proches de ce nouveau point Pn+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 Pn+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 Pn+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.
Figure IV. 103 : Insertion d'un nouveau point.
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.
Si NbPointListe(liste) Alors
Renvoyer(R�sultatListe(liste)); |
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.
Figure IV. 114 : Une �tape de "SousTriangle".
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] .
Le "Diviser pour Construire" est adapt� de la triangulation comme suit :
Si NbPointListe(liste) Alors
Renvoyer(R�sultatListe(liste)); |
Les diff�rentes �tapes de l’algorithme sont les suivantes :
a- Le tri pr�liminaire des points
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.
Figure IV. 15: Tri lexicographique
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.
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.
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.
Figure IV. 148 : La fusion.
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:
- Fixer une surface de subdivision � un
seuil minimal Tsur .
Fsi |
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 Tamp ).
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.
Remarque :
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� d1.
„ 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.
Nous avons d�crit dans ce chapitre les notions du diagramme de Vorono� ainsi que le graphe dual de Delaunay, chacun retournant une partition du support de l'image. L'int�r�t de ces partitionnements est qu'ils sont souples puisqu'ils sont calcul�s sur un ensemble de points pouvant �tre positionn�s � peu pr�s n'importe o� sur le support de l'image.
Nous avons introduit les principales d�finitions et propri�t�s de ces deux mod�les de partitionnement du plan, n�cessaires � la compr�hension du chapitre, ainsi que diff�rents algorithmes du partitionnement triangulaire.
|
� 1999, KADDOUR Chakib
| R�actions ? Commentaires ? Suggestions ?
Cliquez Ici
|
� 1999, KADDOUR Chakib
