REPUBLIQUE ALGERIENNE DIMOCRATIQUE ET POPULAIRE

MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERECHE SCIENTIFIQUE

N° d’ordre………...
UNIVERSITE KASDI MERBAH-OUARGLA N° de série………...

FACULTE DES SCIENCES ET TECHNOLOGIE ET SCIENCES DE LA MATIERE

DEPARTEMENT MATHEMATIQUE ET INFORMATIQUE

Mémoire
En vue de l'obtention du Diplôme de
MAGISTER
Spécialité : Informatique
Option : Technologie d’information et de communication

Par : Mme. Naima MERZOUGUI

THÈME

Un algorithme évolutionnaire pour la

segmentation d'images basé sur le
diagramme de Voronoï

Devant le jury :

Dr. Ahmed KORICHI, MCA, Univ.Ouargla Président

Dr. Kamal Eddine MELKEMI, MCA, Univ.Biskra Encadreur
Dr. Ammar LAHLOUHI, MCA, Univ.Batna Examinateur
Dr. Zouhir MOKHTARI, MCA, Univ.Biskra Examinateur

Soutenu publiquement le 28/06/2012

 REMERCIEMENTS

Je tiens à remercier tout d’abords mon encadreur Dr.

Kamal Eddine MELKEMI de m’avoir proposé un tel

intéressant sujet, m’ouvrant ainsi les portes sur un

domaine de recherche assez vivant.

Que les membres du jury Dr. Ahmed KORICHI, Dr.

Ammar LAHLOUHI, et Dr. Zouhir MOKHTARI

trouvent ici mes vifs remerciements d’avoir accepté

évaluer ce travail et pour le temps qu’ils ont consacré

pour la lecture du mémoire.

2
 Dédicace

Mon père, tu m’as offert, le long de ta vie, le modèle idéal que je désirais atteindre.

Ma mère, c’est grâce à ta sagesse que j’ai pu tracer mon chemin dans cette vie.

A mon époux, pour son continuel soutient et ses encouragements qui m'ont

toujours aidé pour avancer.

A ma sœur Ghalia et son époux qui m’a apporté leurs conseils et leurs soutiens,

A mes sœurs et mes frères, merci pour vos encouragements et votre aide

incontournable.

A tous ceux qui ont contribué à l'aboutissement de ce travail.

3
 Table des matières
Table des figures ............................................................................................................ 6
Table des tableaux.......................................................................................................... 8
Table des abréviations.................................................................................................... 9
Introduction générale ................................................................................................... 10
Chapitre 1 Segmentation d’image ........................................................................... 14
1.1 Introduction ............................................................................................................. 14
1.2 Définition de la segmentation d’images .................................................................. 14
1.3 Les approches de segmentation .............................................................................. 14
1.3.1 Approche contour............................................................................................ 15
1.3.1.1 Les méthodes dérivatives ............................................................................ 16
1.3.1.2 Les méthodes analytiques ........................................................................... 17
1.3.1.3 Les méthodes déformables ......................................................................... 18
1.3.2 Approche région .............................................................................................. 18
1.3.2.1 La classification (clustering) ......................................................................... 20
1.3.2.2 Segmentation par croissance de région ...................................................... 21
1.3.2.3 Approche par division-fusion....................................................................... 22
1. Le quad-tree .................................................................................................... 23
2. Le graphe d’adjacence des régions ................................................................. 24
3. Le diagramme de Voronoï ............................................................................... 25
1.3.3 Approche coopérative ..................................................................................... 26
1.4 Conclusion ............................................................................................................... 28
Chapitre 2 Méthodes d'optimisation ........................................................................ 30
2.1 Introduction ............................................................................................................. 30
2.2 Algorithme génétique .............................................................................................. 30
2.3 Recuit Simulé ........................................................................................................... 34
2.4 K-means ................................................................................................................... 37
2.5 Conclusion ............................................................................................................... 38
Chapitre 3 Segmentation d’images et diagramme de Voronoï ................................ 40
3.1 Introduction ............................................................................................................. 40
3.2 Définitions ............................................................................................................... 40
3.3 Propriétés du diagramme de Voronoï ..................................................................... 41
3.4 Triangulation de Delaunay ...................................................................................... 42
3.5 Construction du diagramme de Voronoï ................................................................. 43
3.6 Segmentation d'images par des algorithmes de Voronoï ....................................... 44

4
 3.7 Travaux existants ..................................................................................................... 45
3.8 Conclusion ............................................................................................................... 46
Chapitre 4 Approche proposée ................................................................................ 48
4.1 Introduction ............................................................................................................. 48
4.2 Objectifs ................................................................................................................... 48
4.3 Conception .............................................................................................................. 49
4.3.1 Extraction des points de contour .................................................................... 50
4.3.2 Initialisation, construction et évaluation de diagramme de Voronoï.............. 50
4.3.3 Algorithme Génétique ..................................................................................... 53
4.3.4 Extraction de régions ....................................................................................... 57
4.4 Mise en œuvre ......................................................................................................... 58
4.4.1 Structure de Diagramme de Voronoï .............................................................. 58
4.4.2 Processus de notre approche .......................................................................... 59
4.5 Algorithmes de segmentation implémentés pour la comparaison ......................... 60
4.5.1 Algorithme Recuit Simulé ................................................................................ 60
4.5.2 Algorithme K-means ........................................................................................ 63
4.6 Résultats expérimentaux ......................................................................................... 64
4.6.1 Paramètres d’initialisation............................................................................... 64
4.6.2 Résultats de segmentation .............................................................................. 65
4.6.2.1 Segmentation des images synthétiques ...................................................... 66
1) Image synthétique 1 .................................................................................... 66
2) Image synthétique 2 .................................................................................... 67
3) Image synthétique 3 .................................................................................... 68
4) Image synthétique 4 .................................................................................... 69
5) Image synthétique 5 .................................................................................... 70
6) Synthèse ...................................................................................................... 71
4.6.2.2 Segmentation des images non synthétiques ............................................... 71
1) Segmentation de l’image Muscle ................................................................ 71
2) Segmentation de l’image Maison ................................................................ 72
3) Synthèse ...................................................................................................... 73
4.7 Conclusion ............................................................................................................... 73
Conclusion générale et perspectives ............................................................................ 75
Bibliographie................................................................................................................ 77
ANNEXE ..................................................................................................................... 81

5
 Table des figures
Figure 1.1 : Principales méthodes de segmentation d’image ....................................... 15
Figure 1.2: processus de division de l’image I utilisant le quad-tree........................... 23
Figure 1.3: image d’étiquettes et son graphe d’adjacence ........................................... 24
Figure 1.4: Exemple de diagramme de Voronoï .......................................................... 25
Figure 1.5: Principe de la coopération séquentielle ..................................................... 26
Figure 1.6 : Principe de la coopération des résultats ................................................... 27
Figure 1.7 : Principe de la coopération mutuelle ......................................................... 27
Figure 2.1: Exemple de reproduction grâce aux principaux types de croisement ....... 32
Figure 2.2 : Opérateur de mutation sur un chromosome de 6 bits ............................... 32
Figure 2.3 : Schéma du principe des algorithmes génétiques ...................................... 33
Figure 2.4 : Le principe de l’algorithme de recuit simulé l’accentuation des minima
suite à la décroissance de la température. .................................................................... 35
Figure 2.5 : Schéma du principe de l’algorithme K-means ......................................... 37
Figure 3.1: Schéma d’un diagramme de Voronoi ........................................................ 41
Figure 3.2: Trois arêtes autour d'un sommet de Voronoï............................................. 41
Figure 3.3: Trois arêtes autour d'un sommet de Voronoï............................................. 42
Figure 3.4: Passage du diagramme de Voronoï à la triangulation de Delaunay .......... 42
Figure 3.5 : Principe de la méthode présentée dans [Melkemi, 92]. ............................ 44
Figure 4.1 : Résultat de segmentation par la méthode division-fusion ........................ 49
Figure 4.2 : Initialisation de germes générer aléatoirement qui se diffèrent des points
de contour..................................................................................................................... 51
Figure 4.3 : Diagramme de Voronoï (avec 30 germes) ............................................... 51
Figure 4.4 : l’affectation du pixel à la région adéquate sans destruction du contour .. 52
Figure 4.5 : Schéma du croisement uniforme aux points i=2, j=4 générés
aléatoirement ................................................................................................................ 54
Figure 4.6 : Croisement de deux individus .................................................................. 54
Figure 4.7 : Illustration de la mutation......................................................................... 56
Figure 4.8 : Mémorisation du diagramme de Voronoï sous forme d’une image ......... 58
Figure 4.9 : Processus de notre approche..................................................................... 59
Figure 4.10 : Démonstration de suppression et d’insertion de site .............................. 62
Figure 4.11 : Image synthétique 1................................................................................ 66
Figure 4.12 : Image synthétique 2................................................................................ 67

6
Figure 4.13 : Image synthétique 3................................................................................ 68
Figure 4.14 : Image synthétique 4................................................................................ 69
Figure 4.15 : Image synthétique 5................................................................................ 70
Figure 4.16 : Image Muscle ......................................................................................... 71
Figure 4.17 : Image maison ......................................................................................... 72

7
 Table des tableaux
Tableau 1.1 : Avantages et limites de l’approche par croissance de région ................ 22
Tableau2.1: Algorithme classique de recuit simulé ..................................................... 36
Tableau 4.1 : Résultats de segmentation par contour (Laplacien) ............................... 50
Tableau 4.2 : Algorithme génétique............................................................................. 57
Tableau 4.3 : Procédure Extraction de régions similaires............................................ 57
Tableau 4.4: Algorithme de segmentation d’images par diagramme de Voronoï ....... 60
Tableau 4.5: Procédure GENERER ............................................................................. 61
Tableau 4.6 : Résultats de segmentation de l’image synthétique 1 ............................. 66
Tableau 4.7 : Résultats de segmentation de l’image synthétique 2 ............................. 67
Tableau 4.8 : Résultats de segmentation de l’image synthétique 3 ............................. 68
Tableau 4.9 : Résultats de segmentation de l’image synthétique 4 ............................ 69
Tableau 4.10 : Résultats de segmentation de l’image synthétique 5 ........................... 70
Tableau 4.11 : Résultats de segmentation de l’image muscles .................................... 72
Tableau 4 .12 : Résultats de segmentation de l’image maison .................................... 73

8
 Table des abréviations

S…………..Segmentation

I…………...Image

Ri………….Région numéro i

AG……......Algorithme Génétique

RS………...Recuit Simulé

DV………..Diagramme de Voronoï

DVSEG…..Segmentation d’image par digramme de Voronoï

9
 Introduction générale

L'information visuelle est sans doute la plus riche des différentes sources
d'informations disponibles. Un intérêt sans cesse croissant est suscité par la
conception des systèmes de vision pour l'interprétation automatique de scènes.

Une description compacte d'une image, plus exploitable que l'ensemble des pixels
est engendré par une étape fondamentale dans la plupart des systèmes de vision par
ordinateur. Pour atteindre cet objectif, une grande variété de techniques dites de
«segmentation d'images » ont vu le jour. Elles peuvent être définis ainsi: "La
segmentation des images consiste à rassembler les pixels de ces images qui partagent
une même propriété pour établir des régions connexes" [Sadgal, 05].

Ces techniques sont généralement fondées sur la recherche des discontinuités

locales (détection de contours) ou sur la détection de zones de l'image présentant des
caractéristiques d'homogénéité (extraction de régions) [Mong, 90]. Ces deux
approches sont duales en ce sens qu'une région définit une ligne par son contour et
qu'une ligne fermée définit une région. Elles amènent cependant à des algorithmes
différents et ne fournissent pas les mêmes résultats. Une autre approche, appelée
approche coopérative, consiste en une coopération entre ses deux approches [Chu et
al., 93].

Nous considérons que le problème de la segmentation d'image est un cas

particulier du problème de partitionnement des données. Ce dernier étant un problème
NP-Complet, ces problèmes peuvent être exprimés sous la forme générale d'un
"problème d'optimisation".

Les algorithmes génétiques (AG) [Holland, 75] [Goldberg, 07] et le recuit simulé
(RS) [Kirkpatrick et al., 83] étant deux techniques d'optimisation stochastique
travaillant sur les mêmes types de problèmes, où le recuit simulé converge
généralement plus vite vers la solution optimale lorsque le problème est de taille
raisonnable. Toutefois, il ne donne qu'une solution. A l'inverse, les algorithmes
génétiques fournissent plusieurs solutions quasi-optimales mais au prix d'un temps de
convergence généralement plus long.

10
 Nous avons présenté dans ce mémoire une nouvelle approche de segmentation
d'images, en utilisant un algorithme d’optimisation à savoir l’algorithme génétique.

Notre approche est complémentaire aux méthodes réalisées dans le domaine de

segmentation d'image basée sur une partition en polygone de Voronoï [Melkemi, 92].
Le principe est similaire à celui de la segmentation d'images par construction du
diagramme de Voronoï et se diffère au niveau de la stratégie de détermination d'un
nombre de polygones vérifiant un critère d'homogénéité.

Dans cette approche coopérative, nous avons combiné la méthode du Laplacien

pour la détection des points de contour avec un algorithme d’optimisation
stochastique basé sur le principe de Charles Darwin à savoir : l’algorithme génétique.
Cette approche s’inscrit dans la classe des algorithmes de segmentation
Division/Fusion. Après avoir utilisé une amélioration de l’image, l’étape de division
se fait par une division de l’image à segmenter en polygones de Voronoï guidée par
un processus génétique. Puis une étape d’extraction de régions similaires est
appliquée comme phase de fusion.

Nous avons commencé notre travail par un état de l’art sur les méthodes de
segmentation d’images. Puis nous avons donné une description générale des trois
algorithmes d’optimisation utilisés à savoir l’algorithme génétique, le recuit simulé et
le K-means [Theiler et al., 97]. Ensuite, nous avons étudié les principes des
diagrammes de Voronoï et enfin nous avons présenté la démarche de l’approche
proposée. Nous avons implémenté les trois algorithmes cités en se basant sur une
structure de diagramme de Voronoï pour des raisons de comparaisons.

Ce mémoire est organisé en quatre chapitres :

 Le premier chapitre présente une synthèse bibliographique sur les différentes

approches de segmentation d’image.

 Dans le deuxième chapitre nous décrivons brièvement le principe de base des

méthodes d’optimisation à savoir l’algorithme génétique, le recuit simulé et le
k-means.

 Le troisième chapitre présente le diagramme de Voronoï, son dual, et ses

propriétés, ainsi que son utilisation pour la segmentation d’image.

11
  Le quatrième chapitre décrit la conception de notre approche et son
implémentation en langage C++, suivi par une expérimentation sur quelques
images afin d’évaluer notre approche en comparant les différents résultats
obtenus.

Nous concluons finalement ce modeste travail par l’identification des perspectives

qui s’ouvrent devant notre recherche afin de montrer son étendue.

12
13
 Chapitre 1 Segmentation d’image

1.1 Introduction
La segmentation est le cœur d’un système d’analyse automatique d’images. Elle
intervient dans de nombreuses applications importantes, comme l'indexation d'une
base de données d'images, le suivi et l'estimation de mouvement dans une séquence
vidéo, et l'interprétation automatique d'images biomédicales et satellitaires, etc.

La segmentation d’images est en fait un traitement de bas niveau qui consiste à

partitionner une image en régions (ensembles de pixels) appartenant à une même
structure (objets ou scène). La qualité de la segmentation mesurée par sa précision de
localisation (partition des régions) a une influence directe sur les performances des
applications ultérieures.

Dans ce chapitre, nous présentons un bref survol des techniques existantes en

donnant leur fonctionnement général.

1.2 Définition de la segmentation d’images

Nous pouvons adopter la définition suivante pour la segmentation :

"La segmentation est un traitement de bas niveau qui consiste à créer une partition de
l'image A en sous-ensembles Ri, appelés régions tels qu’aucune région ne soit vide,
l'intersection entre deux régions soit vide et l'ensemble des régions recouvre toute
l'image. Une région est un ensemble de pixels connexes ayant des propriétés
communes qui les différencient des pixels des régions voisines." [Cocquerez et al.,95].

La segmentation d’image sert à fournir des régions homogènes (selon un critère

donné), de réduire le bruit et de localiser de manière précise les contours des régions.

1.3 Les approches de segmentation

Dans la littérature, nous avons trouvé plusieurs méthodes de segmentation qui

s’intègre généralement dans trois approches principales : approche par contours,
approche par régions, et approche coopérative.

14
 Nous avons essayé de proposer une classification de ces méthodes selon le
schéma suivant :

Approches de segmentation d’image

Approche Contour Approche Région Approche Coopérative

Méthodes Coopération
Classification
dérivatives Séquentielle

Division Fusion Coopération

Méthodes
des Résultats
analytiques

Croissance de Coopération
Méthodes Région Mutuelle
déformables

Figure 1.1 : Principales méthodes de segmentation d’image

Dans ce qui suit, on va présenter une description des différentes approches :

1.3.1 Approche contour

Les méthodes basées contours sont parmi les méthodes les plus classiques en
segmentation d’images. Ces méthodes supposent généralement un modèle a priori des
discontinuités recherchées et opèrent de manière très localisée.

Les méthodes de segmentation basées sur l'approche contour ont donc pour
objectif de trouver les lieux de fortes variations du niveau de gris. Un nombre
important de méthodes a été développé. Ces méthodes s'appuient sur la détection des
discontinuités dans l'image et peuvent être divisées en trois classes : les méthodes
dérivatives, les méthodes analytiques et les méthodes déformables.

Nous présentons quelques principales méthodes :

15
 1.3.1.1 Les méthodes dérivatives

 L’approche gradient

Ce type de détecteur se base sur la première dérivée de l’image I en chacun de ces

points dans les deux directions horizontale et verticale. Un point de contours aura une
amplitude A(i,j) et une direction Dir (i,j).

(1.1)

(1.2)

(1.3)

La détermination des points contours est ramenée dans un premier temps à la

recherche de filtre linéaire permettant d’estimer le gradient en chaque point.

De nombreux opérateurs sont ainsi apparus dans la littérature parmi lesquels nous
pouvons citer les masques de Sobel, Prewit, Robert ….etc

La valeur du gradient est ainsi disponible en tout point de l’image permettant

d’effectuer une recherche des maxima locaux. Ceux-ci correspondent aux passages
par zéro de la dérivée seconde dans la direction du gradient ou encore aux points
contours recherchés.

 L’approche Laplacien

Ce type de détection de contour se base sur la dérivée seconde de l’image. Il est

définit par :

(1.4)

Contrairement au gradient, le Laplacien permet d’obtenir des contours fermés et d’un

pixel d’épaisseur, par contre il a l’inconvénient d’être plus sensible au bruit que le
gradient. Le Laplacien est déterminé en chaque point de l’image par filtrage linéaire.
Les points contours sont alors assimilés au passage par zéro du Laplacien.

16
 Ces deux méthodes (Approche Gradient et Laplacien) semblent inefficaces, si
l’amplitude du gradient aux points de contours varie fortement selon les parties de
l’image. Il n’existe pas de seuil s permettant la sélection des points contour sans
sélectionner ceux dus au bruit. Le Laplacien augmente le bruit présent dans l'image
car il s'agit d'une méthode dérivative.

1.3.1.2 Les méthodes analytiques

 Approche de Canny

Canny [Canny, 86], a proposé un filtre déterminé analytiquement à partir de trois

critères :

1. garantir une bonne détection : c'est-à-dire une réponse forte même à de faibles
contours,
2. garantir une bonne localisation,
3. réponse unique : l'opérateur doit donner une réponse unique aux mêmes types de
contours.

La solution qui vérifie ces trois critères, proposée par Canny est la suivante :

(1.5)

Canny a développé une forme mathématique pour les critères concernant la

performance du détecteur.

 Approche de Deriche

Au filtre de Canny, nous préférons souvent le détecteur de Deriche [Deriche, 87], qui
répond exactement aux mêmes critères de qualité que celui de Canny, mais qui
possède une réponse impulsionnelle finie. Il a pu donc être synthétisé de façon
récursive particulièrement efficace. Le filtre de Deriche a une expression générale de
la forme :
(1.6)

a, w et c sont des réels positifs.

17
 1.3.1.3 Les méthodes déformables

Les modèles déformables, introduits par Kass [Kass et al., 87] sont aussi connus
sous les noms de « snakes » ou « contours actifs ».

L’intérêt principal des contours actifs est de détecter des objets dans une image en
utilisant les techniques d’évolution de courbes. L’idée est de partir d’une courbe
initiale, généralement un carré ou un cercle, et de la déformer jusqu’à obtenir le
contour de l’objet.

En effet, celui-ci présente quelques inconvénients tels que la sensibilité à

l'initialisation, au bruit, et le réglage difficile de ses différents paramètres.

1.3.2 Approche région

Contrairement aux techniques d’extraction des contours, La segmentation en

régions homogènes est basée sur les propriétés intrinsèques des régions. Le choix de
ces propriétés détermine ce qu’on appelle ’’critère de segmentation’’. Pour segmenter
l’image en régions, ces critères peuvent être la valeur de niveau de gris [Sezgin et
al.,04], de la couleur [Lucchese et al., 01], de la texture [Materka et al., 98], ou une
combinaison de plusieurs informations [Thai et al., 99].

D’une manière formelle nous pouvons définir la région par l’ensemble connexe
de points répondants au même critère d’homogénéité. Le formalisme de la
régionalisation a été introduit par Horowitz et Pavlidis, et est le fondement de base
d’un grand nombre de techniques de segmentation en régions.

Une segmentation S d’une image I relativement à un prédicat Pred

[Horowitz76] est une partition de I en n ensembles disjoints non vides R1, R2,…., Rn
tels que :

(1.7)

La première condition implique que chaque point de l’image appartient à une

seule région. La deuxième condition est une contrainte de connexité imposée aux

18
régions. La troisième condition demande que les régions de l’image segmentée soient
homogènes. La condition quatre exprime que les régions vérifiant le prédicat
d’homogénéité, ont une taille maximale.

Il est important de remarquer que , , et ne définissent pas une

segmentation unique [Mong, 90].

On désigne par C la fonction caractérisant la qualité globale d’une segmentation

S [Mong90], et par Q une fonction qui caractérise la qualité locale d’une
segmentation (d’une région ou un élément de S). La valeur Q peut être prise comme
la variance des niveaux de gris d’une région :

(1.8)

Où I(r,k) est le niveau de gris du pixel (r,k) de l’image I ,m est la moyenne et

Card(R) désigne la cardinalité de l’ensemble de pixels de la région R.

La fonction C est définie en fonction de Q par :

C(S)= C(Q (R1),…….., Q (Rn)) (1.9)

Nous ajoutons aux axiomes , , et la condition d’optimisation suivante

[Mong, 90]:

. Parmi toutes les segmentations S vérifiant les conditions , , et

présentées dans la définition de la segmentation, on cherche une segmentation Sopt qui
optimise la fonction de qualité C. C’est à dire, trouver Sopt tel que :

(1.10)

Avec S(I) est l’ensemble de toutes les segmentations possibles de I (exemple de

C : la moyenne arithmétique de Q(R1),…Q(Rn)).

La contrainte précédente réduit le problème d’indétermination de la modélisation

donnée par les axiomes , , et .

19
 Remarque concernant le prédicat d’homogénéité :

Il n’est pas facile de déterminer les critères d’homogénéité d’une approche de

segmentation en appliquant à une grande classe d’images. Parmi les critères
utilisés par plusieurs méthodes de segmentation, on cite la variance des niveaux de
gris associé à une région R donnée par :

(1.11)

Où 1 est le seuil.

Le résultat de la segmentation par région est une image « d’étiquettes » dans laquelle
chaque pixel est affecté d’un numéro correspondant au numéro de la région à laquelle
il appartient dans l’image initiale. À partir de cette image « d’étiquettes » et de
l’image originale il est possible de déterminer les divers attributs de chaque région.

Généralement, nous distinguons trois familles d’algorithmes pour l’approche

région : les méthodes de classification qui consistent à regrouper et à classer les pixels
d’une image en classes en fonction de leurs propriétés, les méthodes de croissance de
régions qui agrègent les pixels voisins selon le critère d’homogénéité; et les méthodes
qui divisent ou fusionnent les régions en fonction du critère choisi.

1.3.2.1 La classification (clustering)

Cette méthode consiste à regrouper et à classer les pixels d’une image en classes en
fonction de leurs propriétés. A chaque point de l’image est associé un vecteur
d’attributs. La classification est alors effectuée sur ces vecteurs d’attributs de façon à
aboutir à un nombre restreint de régions homogènes au sein de l’image.

Donc la classification est définie comme une procédure dans laquelle les pixels
similaire d’une image sont identifie et regroupés dans une même classe. Il existe deux
grandes tendances:

 La classification non supervisée : Elle vise à séparer automatiquement l’image

en clusters sans aucune connaissance a priori sur les classes. elle se base sur une
mesure de distance entre les vecteurs d’attributs. Les algorithmes les plus

20
 fréquemment cités dans la littérature pour cette catégorie sont K-means, Isodata,
et Fuzzy c-means…

 La classification supervisée : Elle s’opère à partir de la connaissance de chacune

des classes définies par une approche probabiliste. Elle se base sur
l’apprentissage de propriétés discriminantes sur un échantillon de données déjà
classées. Les algorithmes de cette catégorie sont Minimum-Distance-to-Means,
Likelihood et Parallelopiped.

L’inconvénient des méthodes de classification est qu’elles sont très sensibles au bruit.

1.3.2.2 Segmentation par croissance de région

La croissance s’effectue à partir de pixels initiaux appelés « germes ». Ces germes

peuvent être sélectionnés de façon aléatoire ou automatique [Cocquerez et al., 95].
Lors d’une itération du processus, les pixels voisins à la région sont étudiés. S’ils
vérifient les conditions d’homogénéité (critère défini au préalable), le pixel sera alors
affilié dans la région. Les pixels non intégrés aux régions peuvent générer eux-mêmes
de nouvelles régions ou être quand même adoptés à la région la plus proche (cas du
bruit dans une image par exemple). Généralement, une mesure de similarité peut être
évaluée par un calcul de distance entre les attributs du pixel candidat et ceux de la
région. Lorsqu’une région intègre un nouvel élément, ses attributs sont alors remis à
jour. La croissance de région s’interrompt lorsque tous les pixels voisins aux régions
ont été affectés. Nous citerons dans ce qui suit quelques travaux illustratifs :

Chassery et Garbay [Chassery et al., 84] selon des critères de forme et de couleur, ils
isolent les régions de l’image. Un pixel est fusionné avec une région candidate si la
mesure de différence colorimétrique est inférieure à un certain seuil. Carron
[Carron.,95] propose des critères de fusion des pixels aux régions produits sur des
règles floues. Tremeau et Borel [Tremeau et al., 97] proposent différents critères
d’homogénéité dans l’espace RVB. D’abord, ils génèrent un certain nombre de
régions par le processus de croissance de régions et ensuite ils fusionnent toutes les
régions qui ont la même distribution colorimétrique.

Un algorithme de segmentation d’images couleurs est proposer par Meyer [Meyer,92]

consiste en une croissance de régions à partir de marqueurs identifiant l’intérieur des
régions. Ainsi un pixel est fusionné avec la région la plus proche (i.e. similaire) en se

21
basant sur le calcul d’une distance qui représente la différence de couleur entre ce
pixel et les régions voisines.

Dans le tableau suivant, nous présentons quelques avantages et limites de l’approche

par croissance de régions.

Avantages Limites

 D’être simple et rapide.  Une mauvaise sélection des germes

ou un choix du critère de similarité
 Elle permet la segmentation d’objet
mal adapté peuvent entraîner des
à topologie complexe.
phénomènes de sous-segmentation1
 Elle préserve la forme de chaque ou de sur-segmentation2.
région de l’image.
 Il peut y avoir des pixels qui ne
peuvent pas être classés.

Tableau 1.1 : Avantages et limites de l’approche par croissance de région

1.3.2.3 Approche par division-fusion

L’algorithme division-fusion appelé aussi « Split and Merge » a été proposé par
Horowitz et pavlidis [Horowitz, 76], il est encore actuellement un des plus
performants [Bres, 03]. Le processus est décomposé en deux étapes. L'image initiale
peut être une première partition résultant d'une analyse grossière ou bien l'image
brute. Dans la première étape, ou division, on analyse individuellement chaque région
. Si celle-ci ne vérifie pas le critère d'homogénéité, alors on divise cette région en
blocs (le plus généralement en 4 quadrants) et l'on réitère le processus sur chaque
sous-région prise individuellement, le découpage arbitraire peut conduire à ce que
cette partition ne soit pas maximale.

Dans la deuxième étape, ou fusion, on étudie tous les couples de régions voisines
( , ). Si l'union de ces deux régions vérifie le critère d'homogénéité, alors, on
fusionne les régions.

1
Sous-segmentation :intervient lorsqu’une région couvre plusieurs objets d’intérêt de classes différentes.
2
Sur-segmentation : intervient quant les objets d’intérêt sont divisé en plusieurs régions à l’issus de la segmentation ce qui la
rends de moins bonne qualité

22
Nous détaillons trois structures de données permettant d’effectuer cette approche :

1. Le quad-tree

2. Le graphe d’adjacence des régions

3. Le diagramme de Voronoï

1. Le quad-tree

Le quad-tree est une structure de données très commune de part sa simplicité et

d’autre part son faible temps de calcul. Il est une arborescence dont la racine est
l’image toute entière et dont chaque nœud parent (sauf les nœuds terminaux) possède
exactement 4 fils. Il est défini de manière récursive: l’image est partagée d’abord en
quatre blocs. À chacun de ces blocs est ensuite associé un nœud fils de la racine. Puis
le processus de découpage en quatre est itéré pour chacun des fils sans chevauchement
des blocs. L’analyse récursive s’arrête lorsque chaque sous-bloc respecte un prédicat
d’homogénéité. Après cette phase de division des petites régions, certains blocs
adjacents présentent des caractéristiques identiques d’où la nécessité de les fusionner.
Cette fusion s’arrête lorsqu’il n’existe plus de couple qui respecte le prédicat de
fusion.

Figure 1.2: processus de division de l’image I utilisant le quad-tree

Inconvénients :

 La rigidité du découpage carré qu’il impose.

 Il conduit à un partitionnement global de l’image qui ne respecte pas toujours la

forme des régions présentes dans l’image.

23
  La division par quad-tree fournit généralement une sur-segmentation car elle
décompose le bloc en 4 sous-blocs en cas de non-homogénéité. Cependant, dans
les dernières itérations, la décomposition en 4 sous-blocs n'est normalement pas
nécessaire. En effet, parmi les 4 sous-blocs créés, plusieurs sont similaires.

2. Le graphe d’adjacence des régions

La fusion des régions ne s’opère pas nécessairement après un algorithme de

division de l’image, mais peut être accomplie après un algorithme de segmentation
ayant provoqué une sur-segmentation. Les approches de fusion se basent
généralement sur l’analyse du graphe d’adjacence des régions ou RAG (Region
Adjacency Graph). Les régions y sont représentées par les nœuds du graphe et
l’information d’adjacence entre régions est symbolisée par les arêtes.

La figure1.3 représente, à titre d’exemple, une image et son graphe d’adjacence

de régions.

R1 R1 R3

R2
R3
R4 R2 R4

Figure 1.3: image d’étiquettes et son graphe d’adjacence

L’analyse du graphe d’adjacence de régions permet de fusionner des régions

d’une image sur-segmentée. Le procédé consiste à fusionner deux nœuds reliés par
une arête à condition qu’ils respectent un critère de fusion. Les méthodes d’analyse
des graphes d’adjacence de régions se distinguent selon l’ordre de parcours des
différents nœuds du graphe et selon les critères de fusion. A chaque itération, les
régions reliées par l’arête qui porte la valeur minimale sont fusionnées. Les valeurs
des arêtes sont mises à jour en fonction du nombre de pixels appartenant aux régions
associées aux arêtes.

L’algorithme de fusion s’arrête lorsqu’un nombre d’itérations fixé préalablement

est atteint ou lorsque les poids des arêtes atteignent une valeur limite.

24
Les inconvénients de cette méthode se situent à deux niveaux :

 Cette méthode dépend du critère de fusion qui peut influer sur le résultat final de
la segmentation,

 Elle peut introduire l’effet de sous-segmentation.

3. Le diagramme de Voronoï

L’approche basée sur le diagramme de Voronoï peut être considérée comme une
amélioration de la segmentation par analyse du quad-tree. La phase de division n’est
plus réalisée par un découpage en régions de forme carrée, mais par un découpage en
polygones de Voronoï qui s’adaptent aux formes des régions présentes dans l’image.

L’intérêt d’initialiser avec des polygones de Voronoï se justifie par une plus
grande diversité de formes (polygones) vis-à-vis des carrés, tout en conservant un
critère géométrique. Ces polygones sont soumis à des tests fondés sur des critères
d’homogénéité et de similarité.

Le diagramme de Voronoï génère une partition de l’image à partir de germes. À

chaque germe est associé une région de Voronoï constituée par l’ensemble de pixels
les plus proches de ce germe. La décomposition de l’espace ainsi obtenue est connue
sous le nom de partition de Voronoï.

La figure1.4 montre un exemple de diagramme de Voronoï. Dans cette figure, les

germes correspondent aux points rouges. Les pixels les plus proches d’un germe sont
ceux qui sont inscrits dans le polygone noir centré sur le germe.

Figure 1.4: Exemple de diagramme de Voronoï

Inconvénient :
 L’initialisation des germes peut mener à des résultats de segmentation différents.

Nous détaillerons cette structure qui va être la base de notre travail dans le chapitre 3.

25
 1.3.3 Approche coopérative

La segmentation par coopération régions-contours suscite un grand intérêt [Chu et

al.93]. Elle consiste en une coopération entre la segmentation par régions et la
segmentation par contours. Salotti [Salotti, 94] a également proposé une technique de
coopération entre un détecteur de contours et un processus de croissance de régions
par agrégation de pixels.

Globalement, une approche contour permet la localisation des contours non

continus donc difficilement utilisables. En y joignant une approche région dont les
caractéristiques sont l’obtention de zones fermées et homogènes, elle peut ainsi pallier
les faiblesses de chacune des techniques : la faible précision du contour (approche
région) et l’obtention de régions non fermées (approche contour).

Il existe trois formes de coopération région-contour [Sebari et al., 07] :

1. Coopération séquentielle : L’une des techniques de segmentation (région ou

contour) est réalisée en premier lieu; son résultat va être exploité par l’autre
technique pour renforcer la définition des critères ou des paramètres de la
segmentation ; L’intégration de l’information provenant de la segmentation par
contours dans une segmentation par régions est l’une des formes de coopération
les plus courantes (Figure 1.5).

Image
Originale

Segmentation
par Contour

Contour Segmentation
par région

Région

Figure 1.5: Principe de la coopération séquentielle

26
2. Coopération des résultats : Les deux types de segmentation seront réalisés
indépendamment ; la coopération concernera leurs résultats qui seront intégrés
afin d’atteindre une meilleure segmentation (Figure 1.6);

Image
Originale

Segmentation Segmentation
par Contour par Région

Contour Coopération Région

Image
Segmentée

Figure 1.6 : Principe de la coopération des résultats

3. Coopération mutuelle : Les deux types de segmentation coopéreront

mutuellement au cours de leur processus d’exécution (Figure1.7). La
coopération permet de prendre des décisions plus sures et plus fiables.

Image
Originale
Coopération

Segmentation Segmentation
par Contour par Région

Contours Régions

Figure 1.7 : Principe de la coopération mutuelle

27
1.4 Conclusion
Ce que nous avons présenté dans ce chapitre n’est qu’une présentation très
générale et non exhaustive des méthodes de segmentation qui existent. A savoir celles
de l’approche contour, de l’approche région ou de l’approche coopérative.

Nous remarquons d’après l’étude que nous avons fait, que les travaux actuels sur
la segmentation d’image s’orientent vers l’approche coopérative, car elle donne des
résultats plus intéressants par rapport aux deux autres approches (par région et par
contour).

En plus, nous avons vu que le diagramme de Voronoï permet de remplacer la

structure par celle de polygone convexe qui peut prendre diverse formes.

Et comme la segmentation d'une image peut être considérée comme un problème

d’optimisation, dans le chapitre qui suit, nous présenterons quelques méthodes
métaheuristiques pour résoudre ce problème.

28
29
 Chapitre 2 Méthodes d'optimisation

2.1 Introduction

Les méthodes d’optimisation servent à minimiser une fonction objective, où les

"métaheuristiques" d’optimisation sont des algorithmes généraux d’optimisation
applicables à une grande variété de problèmes. Elles sont apparues à partir des années
80, dans le but de résoudre au mieux des problèmes d’optimisation.

L’application des métaheuristiques en traitement d’images a connu un souci

particulier ces dernières années, grâce aux avancées technologiques en matière de
calcul des machines.

Plus particulièrement, les métaheuristiques sont très utilisées ces dernières années
en segmentation d’images. A titre d’exemple, nous citons l’algorithme génétique, le
recuit simulé et le K-means qui sont l’objectif d’étude du présent chapitre.

2.2 Algorithme génétique

L’application des algorithmes génétiques à la segmentation d’images a entrepris

dans les années quatre‐vingt‐dix. A titre d’exemple, l’ouvrage de Bhanu [Bhanu, 94]
et la thèse de Andrey [Andrey, 97] sont entièrement dédiés à ce sujet.

Dans [Bhanu, et al., 95], les auteurs ont proposé un système de segmentation de
scènes qui optimise la qualité de l’image segmentée par le biais d’un algorithme
génétique.

Dans [Andrey, 97], l’auteur a proposé une méthode de segmentation non

supervisée basée sur "la relaxation sélectionniste", qui consiste à faire évoluer des
populations d’unités capables de reconnaître des caractéristiques locales dans l’image.
Au cours de cette évolution induite par un algorithme génétique, les populations
envahissent progressivement, et de manière spécifique, les régions à segmenter.

Dans [Majdi et al., 06] les auteurs proposent un algorithme de segmentation basé
sur l’hybridation d’un algorithme génétique avec un recuit simulé, pour initialiser
l’algorithme EM (Espérance-Maximisation).

30
 De manière générale, les algorithmes génétiques utilisent un même principe. Une
population d’individus (chromosomes) correspondant à des solutions, évoluent en
même temps comme dans l’évolution naturelle en biologie. Un chromosome est
constitué de gènes qui contiennent les caractéristiques héréditaires de l'individu. Pour
chacun des individus, nous mesurons sa faculté d’adaptation au milieu extérieur par le
fitness. Les algorithmes génétiques s’appuient alors sur trois fonctionnalités :

1. Sélection : La sélection permet de favoriser les individus qui ont un meilleur

fitness (pour nous le fitness sera la plus souvent la valeur de la fonction objective
de la solution associée à l’individu).

Dans la littérature nous trouvons plusieurs méthodes de sélection. Dans ce qui suit,
nous allons décrire trois méthodes:

 La roulette : A chacun des individus de la population est associé un secteur

d'une roue. L'angle du secteur étant proportionnel à la qualité de l'individu
qu'il représente. Vous tournez la roue et vous obtenez un individu. Les tirages
des individus sont ainsi pondérés par leur qualité. Et presque logiquement, les
meilleurs individus ont plus de chance d'être sélectionné.

 La sélection par rang: Il faut trier la population en fonction de la qualité des

individus puis leur attribuer à chacun un rang. Les individus de moins bonne
qualité obtiennent un rang faible (à partir de 1). La suite de la méthode
consiste uniquement en l'implémentation d'une roulette basée sur les rangs des
individus. L'angle de chaque secteur de la roue sera proportionnel au rang de
l'individu qu'il représente.

 La sélection par tournoi: Un tournoi consiste en une rencontre entre plusieurs

individus pris au hasard dans la population. Le vainqueur du tournoi est
l'individu de meilleure qualité. Vous pouvez choisir de ne conserver que le
vainqueur comme vous pouvez choisir de conserver les 2 meilleurs individus
ou les 3 meilleurs. A vous de voir, selon que vous souhaitez créer beaucoup de
tournois, ou bien créer des tournois avec beaucoup de participants ou bien
mettre en avant ceux qui gagnent les tournois haut la main.

31
2. Croisement : Le croisement combine deux solutions parents pour former un ou
deux enfants (offspring) en essayant de conserver les “bonnes” caractéristiques des
solutions parents.

Cet opérateur est appliqué avec un taux de probabilité défini à priori. Il existe
différents types de croisement (une illustration est donnée dans la figure 2.1). Le
croisement à un point, détermine aléatoirement un point de coupure et échange la
deuxième partie des deux parents. Le croisement deux points (qui peut être étendu
à x points) possède 2 points (ou x) de coupures qui sont déterminés aléatoirement.
Enfin le croisement uniforme échange chaque bit avec une probabilité fixée à .

Figure 2.1: Exemple de reproduction grâce aux principaux types de croisement

3. Mutation : La mutation permet d’ajouter de la diversité à la population en mutant

certaines caractéristiques (gènes) d’une solution.

Cet opérateur permet, aussi, d'éviter une convergence prématurée vers un optimum
local. La mutation la plus simple sur un chromosome change un bit de façon
aléatoire.

Figure 2.2 : Opérateur de mutation sur un chromosome de 6 bits

32
Le principe des algorithmes génétique est simple (voir figure 2.3). Il est basé sur trois
phases :

1. La genèse = l’initialisation aléatoire d’individus pour la population de la

première génération.
2. La reproduction= l’´evolution des individus de la génération courante vers la
suivante.
a. la sélection des individus reproducteurs.
b. le croisement génétique de ces individus pour la création de nouveaux
individus.
c. la mutation de certains individus pour que le pool génétique ne s’affaiblisse
pas.
d. l’´evaluation des individus par le calcul de leur fitness.
3. Recueil du meilleur individu = recherche de l’individu le plus adapté selon les
critères souhaités.

Les sous étapes 2 et 3 se répètent autant de fois qu’il y a besoin de générations

(itérations de l’algorithme) pour satisfaire un critère d’arrêt. Celui-ci est défini avant
que le processus ne commence. La solution est alors représentée par le meilleur
individu de la dernière génération.

Population initiale

Evaluation

Reproduction
Reproduction
Sélection

Croisement Population Suivante

Mutation
Evaluation

Critère d’arrêt
non
oui
Individus Solution

Figure 2.3 : Schéma du principe des algorithmes génétiques

33
2.3 Recuit Simulé
Le recuit simulé (RS) [VanL, 87] est une méthode de recherche locale proposée
par Metropolis [Metr, 53]. Elle a été appliquée aux problèmes d’optimisation par
Kirkpatrick et al [Kirkpatrick et al., 83].

L’algorithme du recuit simulé a été appliqué à la segmentation d’images par

l’approche markovienne pour chercher les configurations les plus acceptables,
correspondant aux états d’énergie minimale [Maitre, 03].

Pour la détection de contours, le recuit simulé a été utilisé par Jamieson et al.
pour trouver les paramètres optimaux d’un modèle de contours basé sur les B‐splines,
[Jamieson et al., 03].

Le RS est une méthode heuristique d'optimisation globale qui distingue entre les
différents optimaux locaux. A partir d'un point initial, l'algorithme fait un pas et la
fonction objective est évaluée. Pour minimiser cette fonction, tout pas en pente est
accepté et le processus répète la même tache à partir du nouveau point. Un pas
ascendant peut être accepté. Donc, l'algorithme peut éviter les optimaux locaux.
Cette décision ascendante est prise par le critère de Métropolis. Comme le processus
d'optimisation fonctionne, la longueur des pas décroît et l'algorithme se rapproche de
l'optimum global. L'algorithme est assez robuste pour les problèmes combinatoires,
car le nombre de suppositions, faites sur la fonction objective, est très limité.

Les quatre étapes de base pour la mise en œuvre du RS sont :

1). La définition de la configuration du système ;

2). Un mécanisme de génération ;

3). Le choix d'une fonction de minimisation du coût (la fonction objective H) qui
est le but de la procédure;

4). Un paramètre de contrôle t appelé température et une procédure de

refroidissement qui nous communiquent après plusieurs changements aléatoires
dans la configuration dans un pas descendant chaque t pris. La tâche assignée à
cette procédure exige la perspicacité plus profonde dans le problème des essais
et erreurs de l'expérience.

34
 Figure 2.4 : Le principe de l’algorithme de recuit simulé l’accentuation des minima
suite à la décroissance de la température.

La Figure 2.4 montre l’évolution énergétique au fur et à mesure de la

décroissance en température. Au départ, toutes les configurations sont équiprobables
puis les minima énergétiques apparaissent et s’accentuent.

L'algorithme du RS peut être formulé comme suit : Au début le processus définit

une configuration initiale, ensuite il passe à exécuter une séquence d'itérations.
Chaque itération est une sélection aléatoire d'une configuration extraite du voisinage
de la configuration courante suivie d’une évaluation de la fonction objective.

Dans notre contexte, le voisinage est défini par le choix d'un mécanisme de
génération, c.-à-d. une "prescription" produit une transition d'une configuration à une
autre par une petite perturbation.

Soit A  la solution faisable.  est l’ensemble des solutions faisables.

Nous appelons GENERER(A,B) une procédure produisant tous B  dans un

certain ordre. La sortie d'une procédure de recherche locale, qui utilise
GENERER(A,B) est appelé un minimum local.

Il est supposé que la procédure GENERER(A,B) génère aléatoirement B  avec

un mécanisme de génération qu’on va définir plus tard.

35
Le principe du critère de Métropolis consiste à itérer les deux étapes suivantes :

- Posons Δ = H(B) - H(A) où H est la fonction objective.

- La probabilité que l'algorithme accepte B comme la nouvelle solution faisable

courante est donnée par :

où t un paramètre appelé température (2.1)

Un algorithme classique du recuit simulé [Colorni et al., 96] peut être présenté par le
code suivant :

t :=t0 ;
Répéter
λ := VRAI; V:= A ;
Répéter
GENERER(A,B);
Si H(B) < H(V) alors V:= B ;
Δ:= H(B) - H(A);
Si Δ < 0 alors A:= B et λ := FAUX Sinon Faire
Générer aléatoirement q selon la loi uniforme sur [0;1];
Si q <e -Δ/t alors A:= B et λ := FAUX
Jusqu’à EQUILIBRE ;
t := g(t) ;
Jusqu’à Δ ;
Extraire l ;

Tableau2.1: Algorithme classique de recuit simulé

Dans ce code : g (t) est la règle de la mise à jour du paramètre t (température), il est
souvent simple t := a.t avec une constante a < l (en pratique a=0.95). EQUILIBRE
est un sous programme utilisé pour décider quand t doit être mis à jour.

Quand l’espace des états est grand, l’algorithme nécessite un grand nombre
d’itérations pour converger, et ça parce que les perturbations sont générer d’une
manière aléatoire. Le fait d’accepter des configurations d’énergie supérieures permet
d’éviter le problème des minima locaux de l’énergie.

36
2.4 K-means
L'algorithme de classification K-means a été développé par J.MacQueen (1967) et
puis par J.A. Hartigan et M.A.Wong autour de 1975.

Dans [Theiler et al., 97], les auteurs ont proposé une approche simple variante de
l’algorithme k-means, qui utilise les propriétés spatiales et spectrales de l'image.

L’algorithme k-means est l’algorithme de clustering le plus connu et le plus

utilisé, du fait de sa simplicité de mise en œuvre. Il partitionne les données d’une
image en K clusters (classes). L’algorithme renvoie une partition des données, dans
laquelle les objets à l'intérieur de chaque cluster sont aussi proches que possible les
uns des autres et aussi loin que possible des objets des autres clusters. Chaque cluster
de la partition est défini par ses objets et son centroïde (le centroïde représente la
moyenne du cluster).

Début

Nombre de
classes K

Calculer les centroïdes

Non

Distances entre chaque Pas de Oui

pixel et tout les centroïdes changement
Fin

Groupement par la
distance minimale

Figure 2.5 : Schéma du principe de l’algorithme K-means

Le k-means est un algorithme itératif qui minimise la somme des distances entre
chaque objet et le centroïde de son cluster. La position initiale des centroïdes
conditionne le résultat final. K-means change les objets de cluster jusqu'à ce que la
somme ne puisse plus diminuer. Le résultat est un ensemble de clusters compacts et

37
clairement séparés, sous réserve d’avoir choisi la bonne valeur K du nombre de
clusters.

Les principales étapes de l’algorithme k-means sont :

1. Choix aléatoire de la position initiale des K clusters.

2. (Ré-)Affecter les objets à un cluster suivant un critère de minimisation des

distances (généralement selon une mesure de distance euclidienne).

3. Une fois tous les objets placés, recalculer les K centroïdes.

4. Réitérer les étapes 2 et 3 jusqu’à ce que plus aucune ré-affectation ne soit faite.

2.5 Conclusion
Il y a une pléthore d’algorithmes de segmentation d’images. La méthode
universelle performante dans tous les cas de figure n’existe pas. Exposer et explorer
toutes les méthodes de segmentation, dépasseraient le cadre de ce travail. Nous nous
sommes intéressés dans nos travaux à l’algorithme génétique et recuit simulé, que
nous devons implémenter dans notre approche.
Nous avons également présenté la méthode de segmentation K-means dans le but
d’avoir une évaluation de la qualité de la segmentation.
Puisque notre approche utilisera ces algorithmes et qui se base sur une structure de
diagramme de Voronoï donc une étude détaillée sur cette structure sera l’objectif du
chapitre suivant.

38
39
 Chapitre 3 Segmentation d’images et diagramme
de Voronoï

3.1 Introduction
Nous avons vu précédemment différents méthodes de segmentation d’image.
Dans ce chapitre nous décrivons un nouveau type de segmentation, 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 la segmentation par diagramme de
Voronoï.

En effet, ce chapitre commence à donner une définition à un diagramme de

Voronoï et ses propriétés. Puis, il présente son dual nommé triangulation de Delaunay
suivi par la présentation des différentes approches de sa construction. Ensuite, il décrit
un algorithme général de segmentation d’image par diagramme de Voronoï. Ce
présent chapitre se termine par la citation de quelques travaux de segmentation basés
sur ce diagramme.

3.2 Définitions

Soit S = {M1, …, Mn} un ensemble de points du plan euclidien R 2.

Nous appelons polygone de Voronoï associé au point Mi, l’ensemble de points du

plan les plus proches de Mi que des autres points de S. On peut écrire :

P(Mi ) = { M R2 / d (M, Mi ) < d (M, Mj ) j j ≠ i} (3.1)

Où d est la distance euclidienne dans R2.

Nous appelons diagramme de Voronoï de S, noté DV(S), le graphe planaire formé par
les frontières des polygones P(Mj).

DV(S) = { M R2 ;  i,j , i ≠ j / M Fr (P(Mi)) et M Fr (P(Mj)) } (3.2)

40
Les frontières sont notées Fr (P(Mi)). Les Mi sont appelées les germes ou les sites -
voir figure 3.1-.

Figure 3.1: Schéma d’un diagramme de Voronoi

3.3 Propriétés du diagramme de Voronoï

Le diagramme de Voronoï vérifie un certain nombre de propriétés importantes pour sa
construction et son exploitation. Parmi ces propriétés, on peut citer :

 Chaque sommet du diagramme de Voronoï est le point de rencontre de trois

arêtes de Voronoï (figure 3.2).

Figure 3.2: Trois arêtes autour d'un sommet de Voronoï.

 Un sommet de Voronoï est équidistant de 3 sites.

 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. Ce cercle est
appelé Cercle de Delaunay(figure 3.3).

41
 Figure 3.3: Trois arêtes autour d'un sommet de Voronoï.

 Une arête de Voronoï est une partie de la médiatrice séparant deux germes de
l’ensemble S.

 Les frontières de deux régions de Voronoï ont au plus une arête commune.

 Une arrête de Voronoï est constituée soit d’un segment de droite reliant deux
sommets soit d’une demi droite dont l’extrémité est un sommet de Voronoï.

 La Triangulation de Delaunay et le Diagramme de Voronoï peuvent être étendus

à un ensemble de sites dans l’espace (3D).

3.4 Triangulation de Delaunay

Nous définissons la triangulation de Delaunay d'un ensemble de points du plan
comme étant le dual du diagramme de Voronoï correspondant.
La construction de la triangulation de Delaunay est réalisée en reliant par un
segment toutes les paires de points dont les régions de Voronoï correspondantes sont
adjacentes (c'est-à-dire séparées par une arête de Voronoï) (figure 3.4).

Figure 3.4: Passage du diagramme de Voronoï à la triangulation de Delaunay

42
La triangulation de Delaunay présente plusieurs propriétés :

 elle est unique ;

 elle est complète ;

 les cercles passant par les trois sommets de chaque triangle ne contiennent
aucun autre point en leur intérieur.

3.5 Construction du diagramme de Voronoï

Il existe principalement deux approches algorithmiques de construction des DV :

 l'approche récursive connue sous le nom de «Divide and Conquere » [Preparata

et al., 88], cette approche est basée sur le paradigme fondamental en
algorithmique stipulant qu'un problème est divisé d'une manière récursive en des
sous-problèmes; la solution du problème original consiste à fusionner les
solutions des sous-problèmes.

Les étapes principales de l’algorithme de cette approche :

1. Division : diviser un problème original en plusieurs sous problèmes ;

2. Construction récursive des sous diagrammes résoudre chacun des sous

problèmes avec la même stratégie ;

3. Fusion : fusionner les solutions de tous les sous problèmes afin d’obtenir la
solution du problème original.

 L'approche itérative (Incrémentation), elle est proposée par Green et Sibson

(en 1975), puis elle était améliorée par Ohya et Murota (en 1984) permet de
construire un nouveau diagramme à partir d'un diagramme déjà existant. Cette
approche est adaptée à l’environnement de construction dynamique où on a
besoin d’ajouter aléatoirement un germe dans un ensemble de germes existants.

L'inconvénient majeur de l'approche récursive réside dans le fait qu'elle ne peut

s'adapter au problème de mise à jour du DV par insertion de nouveaux points.
Contrairement aux algorithmes de la deuxième approche (itérative) qui sont adaptés
pour réaliser la croissance de régions.

43
3.6 Segmentation d'images par des algorithmes de Voronoï
La segmentation d'images par la partition en polygones de Voronoï s'inscrit dans
l'approche de segmentation par divisions-fusions. Ce type d'algorithmes a été suggérer
et valider dans [Melkemi, 92].

Dans la figure suivante un schéma explique les principales étapes de cet

algorithme :

Initialisation d’un
ensemble de germes par
un processus de Poisson

Attribuer à chaque germe

sa région de Voronoï

Toutes les régions

Région non sont homogènes ?
homogène ?

Si deux régions adjacentes dont

Introduire un nouveau site et la moyenne de couleur divisée
recalculer la région de Voronoï par leurs périmètres dépassent
un seuil alors fusion

Figure 3.5 : Principe de la méthode présentée dans [Melkemi, 92].

Cet algorithme comporte une étape d’initialisation, une étape de division suivie d’une
étape de fusion :

 Initialisation : Des germes sont positionnés et répartis uniformément dans

l’image grâce à un processus de Poisson. A chaque germe est associée une
région dont les frontières sont établies grâce à un diagramme de Voronoï.

 Division : Un prédicat d’homogénéité est calculé pour chaque région et les

régions non homogènes sont divisées par introduction de nouveaux germes. Le
diagramme de Voronoï est remis à jour et le processus de division est réitéré
jusqu’à ce que toutes les régions de Voronoï respectent un prédicat
d’homogénéité.

44
  Fusion : Les germes qui ne correspondent pas à un objet dans l’image sont
éliminés dans cette dernière étape. Ainsi, les régions adjacentes dont les
couleurs moyennes sont proches et pour lesquelles la longueur de la frontière
commune divisée par la somme de leurs périmètres est inférieure à un seuil
sont fusionnées.

Inconvénients :

 Difficulté d’ajustement du seuil de fusion,

 et résultats influencés par l’initialisation des germes.

3.7 Travaux existants

Dans cette section, nous rappelons quelques travaux basés sur l’utilisation du
diagramme de Voronoï [Melkemi, 92].

La géométrie algorithmique est le premier domaine d’application du diagramme

de Voronoï [Toussaint, 80]. En outre, le diagramme de Voronoï est un outil utilisé
également pour résoudre des problèmes d’optimisation géographique, [Asano, 85].
Dans le domaine de reconnaissance de forme, le diagramme de Voronoï et son dual
jouent un rôle important. Le diagramme de Voronoï a été utilisé pour l’identification
de formes présentes dans une image binaire [Kubler, 89]. Dans le domaine de
l’analyse des scènes de biologie, le diagramme représente un outil topographique pour
l’étude de la sociologie cellulaire. Il est exploité pour étudier la distribution et la
dépendance entre les cellules. Nous trouvons dans [Marcelpoil, 91] les détails de cette
approche.

AHUJA [Ahuja, 85], a introduit une technique pour le codage et la compression

d’images binaires. L’image est représentée approximativement par un pavage en
polygones de Voronoï, où chaque polygone reçoit la valeur image majoritaire des
points qu’il contient. Ce travail a été étendu par la suite aux images de niveaux de gris
[Rom, 88]. La triangulation de Delaunay, le ’’dual’’ de diagramme de Voronoï, est
utilisé pour le codage d’images en niveaux de gris.

Dans la thèse [Melkemi, 92], l’auteur utilise le diagramme de Voronoï pour

résoudre le problème de segmentation d’images, ainsi que le problème de détection
d’événements en imagerie multi sources. Il examine deux approches : la première

45
approche fonctionne selon le principe de la méthode Division-Fusion et qui est utilisé
pour détecter les différences entre des images acquises dans différents domaines de
radiométrie. La deuxième approche, il a proposé un algorithme de calcul d’une
approximation du diagramme de Voronoï généralisé, cet algorithme est basé sur
l’approche coopérative entre la détection de contour et la détection de région.

Arbelaez [Arbelaez, 04] a proposé une approche qui consiste à modéliser la

segmentation d'une image comme une partition de Voronoï, il a étudié le problème de
la segmentation de bas niveau pour les images couleur.

3.8 Conclusion
L'intérêt porté aux diagrammes de Voronoï réside dans la simplicité de la définition
du diagramme de Voronoï, les régions de Voronoï se retrouvent dans la nature, ils ont
des propriétés mathématiques intéressantes et surprenantes, et il existe des
algorithmes efficaces pour construire les diagrammes de Voronoï, en plus la structure
duale du diagramme de Voronoï (la triangulation de Delaunay) admet elle aussi de
très bonnes propriétés géométriques et topologiques.

En effet, le Diagramme de Voronoï constitue l’outil de base utilisé pour la réalisation

de notre approche de segmentation, qu’on doit présenter dans le chapitre suivant.

46
47
 Chapitre 4 Approche proposée

4.1 Introduction
Dans ce chapitre nous détaillons notre approche de segmentation d’images que
nous appelons ”DVSEG” (Segmentation par Diagramme de Voronoï), où on doit
présenter un algorithme d’optimisation pour la segmentation d’image, à savoir
algorithme génétique(AG), basé sur une partition de Voronoï.

Nous inspirons des travaux menés par [Melkemi, 92] sur les diagrammes de
Voronoï, et en exploitant les avantages de l’approche coopérative, nous avons intégré
un algorithme de segmentation par contour dans notre approche afin d’améliorer les
résultats de segmentation, et diminuer le temps d’exécution.

Nous avons implémenté aussi deux algorithmes à savoir le recuit simulé (RS) et
le K-means pour raisin de comparaison entre les résultats de ces algorithmes et ceux
de notre approche.

Dans ce chapitre, nous allons commencer par la description du principe de chaque

étape de notre approche. Ensuite nous détaillerons sa mise en œuvre en expliquant la
structure de données que nous avons conçues, ainsi que le processus général de cette
approche. Puis nous expliquerons le principe des algorithmes implémentés. Nous
terminerons par une expérimentation de notre système sur quelques images de test
afin de comparer les résultats obtenus par différents algorithmes à savoir algorithme
génétique(AG), recuit simulé (RS) et le K-means.

4.2 Objectifs
 Utiliser la structure ’’diagramme de Voronoï’’ pour la segmentation d’images.

 Implémenter un algorithme de détection de contour.

 Présenter notre nouvelle approche de segmentation d’images.

 Implémenter les algorithmes AG, RS et le K-means.

 Expérimenter l’application pour faire une étude comparative entre les

algorithmes implémentés.

48
 4.3 Conception

La segmentation en régions de Voronoï provoque une perte d’information dans les

contours. Cette perte pourra être supprimée par coopération de type région-contour.
C’est une amélioration qui devra être importante et complètement adaptée à notre
approche.

Dans la figure suivante l’exemple de segmentation par l’algorithme division-fusion

(cf. paragraphe 3.6) utilisant les diagrammes de Voronoï, nous montre que les
résultats sont meilleurs avec la détection de contour et dans un temps plus court que
celui sans la détection de contour.

Figure 4.1 : Résultat de segmentation par la méthode division-fusion

Les paramètres : 1000 régions, seuil d’homogénéité=20.

Ainsi, notre approche se situe dans l’approche coopérative où on utilise un

algorithme de segmentation par contour (Laplacien), et un algorithme de segmentation
par région guidée par un processus génétique.

Notre approche s’inscrit dans la classe des algorithmes de segmentation

Division/Fusion. Nous commençons par l’extraction des points de contour, l’image
doit être segmentée en première phase par l’algorithme de DV, ceci nécessite une
initialisation des germes, construction puis évaluation du DV à condition que les
germes soit différents des points de contour. Nous appliquons par la suite un
algorithme d’optimisation utilisant le principe des AG. Nous utilisons ensuite une
étape d’extraction de régions similaires comme phase de fusion.

49
 4.3.1 Extraction des points de contour

Nous procédons notre approche par une segmentation par contour pour
déterminer les points de contour dans l’image, qui sont utilisé par la suite dans la
phase construction de diagramme de Voronoï.

Dans le tableau suivant nous voyons le résultat de l’exemple de segmentation par

contour, où nous avons appliqué l’algorithme Laplacien (cf. paragraphe 1.3.1.1). Les
points de contour sont présentés en blanc.

Segmentation par
Image à segmenter
contour

Tableau 4.1 : Résultats de segmentation par contour (Laplacien)

4.3.2 Initialisation, construction et évaluation de diagramme de

Voronoï

A/ Etape initialisation : cette étape consiste à créer une population initiale composée
de m individus S1, S2, … Sm. et chaque individu contient n germes.

Si = (gi1 - gi2 - … - gik - …gin) (4.1)

50
 Où i {1,…, m} et gik est le germe (ou site) k de l’individu i générer
aléatoirement par un processus de Poisson (décrit dans l’ANNEXE), tel que chaque
germe généré doit être différent d’un point de contour.

Figure 4.2 : Initialisation de germes générer aléatoirement qui se diffèrent des points
de contour.

B/ Construction de diagramme de Voronoï : A chaque germe gik est associée une

région (ou cellule) de Voronoï. Une région de Voronoï k est l’ensemble des points
qui sont plus proches du point gik. On appelle cette partition Diagramme de
Voronoï. Pour la tracer on se base sur le fait que la frontière entre les cellules de
Voronoï de deux germes distincts se situe forcément sur la médiatrice qui sépare
ces deux germes. En effet, les points de cette médiatrice sont équidistants des deux
germes.

Nous utilisons notre système DVSEG, nous obtenons le résultat illustré dans la
figure suivante, qui présente une partition de Voronoï (les polygones sont colorés
aléatoirement).

Figure 4.3 : Diagramme de Voronoï (avec 30 germes)

51
 Dans notre cas, nous affectons chaque pixel au site le plus proche tel que le
segment de ligne (présenté par une ligne pointer dans la figure ci-dessous) entre ce
point et ce site ne contient pas un point de contour, afin qu’un contour ne soit pas
détruit par une région. Voici un exemple illustratif :

Figure 4.4 : l’affectation du pixel à la région adéquate sans destruction du contour

Nous n’affectons pas le pixel X au site i, malgré que ce soit le site le plus proche,
et nous l’affectons au site j.

C/ Etape évaluation : Après la construction du DV de chacun de ces individus, une

étape d’évaluation des individus produit est nécessaire, dont le but est l’évaluation
de l’homogénéité des polygones (associé aux sites) pour chaque individu D. pour
ce faire, nous allons utiliser la variance des niveaux de gris associé à une région.
Ce calcul s’effectue de la manière suivante:

(4.2)

Où D = (g1,…,gn) est un individu de la population, Pi est un polygone associé à

gi, I(l,k) est le niveau de gris du pixel (l,k) de l’image I ,m est la valeur moyenne
des niveaux de gris affectés au polygone Pi . Card(Pi) est le nombre maximum de
pixels de Pi.

La fonction d’évaluation H, qui caractérise la qualité globale d’une segmentation

d’une image, est donnée par la relation:

(4.3)

Donc, l’évaluation se fait à deux niveaux : une évaluation locale de chaque

polygone du diagramme et une autre globale de la qualité de la segmentation.

52
 On désigne par NPH le nombre de polygones homogènes du DV associé à
l’individu.

(4.4)

Où 1x est la fonction indicatrice au seuil .

(4.5)

On note par MFE le minimum des valeurs de la fonction d’évaluation des individus
d’une génération. Son expression est la suivante :

(4.6)

Où Si est un individu d'une génération G.

4.3.3 Algorithme Génétique

L’ensemble d’individus générées précédemment représente l’espace des solutions ,

où chaque individu représente une configuration (chaque individu ou solution est
obtenu par l’ensemencement de n points dans l’image).

Nous reproduisons, alors, ces solutions en croisant les meilleurs d’entre elles. Nous
combinons ainsi les solutions partielles pour créer de nouvelles solutions meilleures.

Les étapes de cet algorithme :

A/ Etape de sélection : La sélection est une étape essentielle dans l’algorithme,

puisqu’elle guide l’évolution vers les zones de meilleure fitness. Sans la sélection,
un algorithme génétique ne ferait guère mieux qu’une recherche aléatoire. Les
sélections les plus populaires sont la sélection proportionnelle, par rang linéaire et
de tournoi.

Dans notre étude, nous utilisons la sélection tournoi qui consiste à choisir K
individus au hasard et le meilleur sera sélectionné. Notre choix repose sur le fait
que, d’une part la sélection proportionnelle dans le cadre pratique de populations

53
 de petite taille par rapport à la taille de l’espace, peut bloquer la convergence (le
cas de notre étude). D’autre part, la sélection tournoi donne les mêmes espérances
que la sélection par le rang, mais permet une plus grande variance [Kall99].

B/ Etape du croisement : A chacun des deux parents sélectionnés on applique un

croisement uniforme aux points i et j (i, j {1, ..., n}) générés aléatoirement (Voir
Figures 4.6 et 4.7). Ce type de croisement a été prouvé comme étant plus efficace
dans plusieurs cas.

Figure 4.5 : Schéma du croisement uniforme aux points i=2, j=4 générés aléatoirement.

Exemple: Soient les deux individus 1-2-3-4-5 et a-b-c-d-e. Le croisement des deux
individus (figure 4.7).

Figure 4.6 : Croisement de deux individus A= 1-2-3-4-5 et B=a-b-c-d-e. aux points i=2 et j=4.

54
 Le test après croisement consiste à voir ce que le croisement des descendants
à amélioré la qualité des segmentations de la nouvelle population. Cette
amélioration est provoquée soit par le premier descendant ou par le second
descendant :

H (D1) < MFE ou H (D2) < MFE (4.7)

Si ce test est vérifié l’un des descendants sera inséré à la génération en cours.
Sinon le processus refait la phase de croisement. Après le croisement le MFE
sera mis à jour.

C/ Etape de mutation : La mutation joue le rôle de bruit et empêche l’évolution

de se figer. Elle permet d’assurer une recherche aussi bien globale que locale,
selon le poids et le nombre des gènes mutés. De plus, elle garantit
mathématiquement que l’optimum global peut être atteint.

Dans notre algorithme nous avons au départ un nombre de points tirés

aléatoirement. Les coordonnées sont réarrangées par l’opérateur croisement
qui laisse les données fixes et ne varie pas. Ce qui bloque l’évolution de
l’algorithme. Pour cela, nous allons utiliser une mutation du genre perturbation
aléatoire gaussienne des coordonnées des points (voir figure (4.8)).

Un individu D est sélectionné pour la mutation par la probabilité

.

Cette mutation consiste à changer un ou plusieurs sites suivant le principe de

la perturbation aléatoire gaussienne des coordonnés des points comme suit :

Soit gk=(X(gk),(Y(gk)) le site choisi pour la mutation. Ainsi, la mutation est

donnée par :

(4.8)

55
 Où δx (resp. δy) est générée aléatoirement par la distribution de gausse
N(0,mx.δx2) (resp. N(0,my.δy2)) avec mx et my sont les moyennes, δy2 et δy2 sont
les variances.

Figure 4.7 : Illustration de la mutation.

Après la phase de mutation, la condition H(D0) < MFE sera évaluée. Si cette
condition est vraie l’individu D0 sera inséré dans la population en cours et le
MFE sera mis à jour. Sinon le processus refait toute la phase reproduction
(sélection, croisement).

Le résultat de cet algorithme est présenté par l’individu Dopt, où Dopt vérifie :

(4.9)

La description du principe général de l’algorithme génétique est donnée dans le

tableau suivant :

Algorithme Génétique ;
Début
Initialisation et Construction des DV pour chaque individu ;
Evaluation ;
Tant que ( D P / NPH(D) n ou MFE<C0) Faire
Début
Label: Sélection ;
Croisement ;
Construction des DV ;
Evaluation ;
Si il ya une amélioration Alors MAJ de P et du MFE

56
 Sinon Aller à Label ;
Mutation ;
Construction des DV ;
Evaluation ;
Si il ya une amélioration Alors MAJ de P et du MFE
Sinon Aller à Label ;
Fin;
Fin;

Tableau 4.2 : Algorithme génétique

Tel que : D : un individu de la population P ;

NPH : Nombre de Polygones Homogènes;

MFE : Minimum de la Fonction d’Evaluation;

C0 : seuil d’homogénéité de région ;

4.3.4 Extraction de régions

Après la convergence de l’algorithme appliqué, le processus passera à la phase

extraction de régions similaires.

Cette phase d’extraction est la suivante : à partir d’un polygone initial, nous
effectuons les tests de similarité entre ce polygone et les polygones voisins. Chaque
polygone voisin vérifiant le critère de similarité est inséré dans les régions.

La procédure d'extraction de régions est réalisée à partir du graphe d'adjacence

associé au résultat obtenu comme suit :

Construire le graphe d’adjacence du diagramme de Voronoi;

Pour i:=1..n-1 faire
Début
Pour toute région Rj adjacente et similaire à Ri faire
insérer Rj à Ri ;
MAJ du graphe d’adjacence;
Fin;

Tableau 4.3 : Procédure Extraction de régions similaires

57
 Le graphe d’adjacence de régions est une structure de données permettant de
représenter les régions d’une image par un graphe. Chaque nœud de ce graphe
d’adjacence représente une région et chaque arête une adjacence entre deux régions.
Deux nœuds reliés par une arête sont désignés comme "adjacents".

4.4 Mise en œuvre

4.4.1 Structure de Diagramme de Voronoï

Au niveau de la structure de données du diagramme de Voronoï:

 l’image est représentée par une matrice déterminant les niveaux de gris des pixels
constituant l’image.

 Une liste représente l’ensemble d’individus où chaque individu pointe vers une
liste de ses polygones.

 Dans un individu, chaque polygone est déterminé par un germe, où à chaque germe
est associé un indice permettant de l’identifier.

 L’affectation des pixels au polygone dans un individu est représenté par une
matrice de trois dimensions qui correspond au : numéro d’individu, le X et le Y du
point.

Pour calculer les attributs d’homogénéité associés à chaque polygone, nous générons
le diagramme sous forme d’une image. Nous associons à chaque point d’un polygone
le numéro de son germe. Un exemple d’un tel diagramme est fourni en figure 4.10.

2 2 2 1 1 1 1 1
2 2 2 2 1 1 1 1
2 2 2 2 1 1 * 1
2 2 * 2 2 1 1 1
4 2 2 2 3 3 1 1
4 4 2 2 3 3 3 3
* 4 4 3 3 * 3 3
4 4 4 3 3 3 3 3

Figure 4.8 : Mémorisation du diagramme de Voronoï sous forme d’une image

(*) désigne la position du germe et sa région est l’ensemble des points ayant le numéro du germe.

58
Les attributs caractérisant un polygone sont :

 Le numéro de son germe.

 Le nombre de pixels appartenant à ce polygone.

 La moyenne des niveaux de gris des points situés à l’intérieur.

 Et la variance des niveaux de gris qui caractérise l’homogénéité de polygone.

Un individu d’une génération est caractérisé par :

 Le nombre de régions qui le construit.

 Le nombre de polygones homogènes (NPH).

 La fonction d’évaluation (FE) qui caractérise la qualité globale de segmentation

d’image.

Le test de convergence de l’algorithme dépend au minimum des valeurs de la fonction

d’évaluation des individus (MFE), et au NPH.

4.4.2 Processus de notre approche

Figure 4.9 : Processus de notre approche

59
 Le système de segmentation proposé que nous appelons ”DVSEG”
(Segmentation par Diagramme de Voronoï), dont le processus des différentes étapes
est présenté dans la figure 4.9, est dérivé de l’approche coopérative (contour-région).
Nous intégrons la méthode du Laplacien avec un algorithme basé sur le principe
génétique, on met en œuvre la structure du diagramme de Voronoï pour segmenter des
images en niveau de gris.

La structure générale de notre algorithme peut être décrite comme suit :

Algorithme DVSEG;
Début
Extraction des points de contour;
Initialisation et construction des diagrammes de Voronoï;
Evaluation;
Segmentation par Algorithme Génétique;
Extraction de régions;
Evaluation;
Fin.

Tableau 4.4: Algorithme de segmentation d’images par diagramme de Voronoï

4.5 Algorithmes de segmentation implémentés pour la

comparaison
4.5.1 Algorithme Recuit Simulé

L’algorithme du recuit simulé s’articule autour de deux boucles. La première est

la boucle de décroissance de la température qui, lorsque le système est figé, décroît la
température. La seconde est la boucle de stabilisation qui itère tant que le système
n’est pas figé. Le système est dit figé lorsqu’un nombre prédéfini de modifications
élémentaires consécutives a été rejeté par la règle d’acceptation de Metropolis.

L’algorithme RS débute avec une température très élevée permettant d’accepter

un grand nombre de configuration, la température est diminuée ce qui a pour
conséquence de diminuer le nombre de configurations testées. Le système s’approche
alors petit à petit de sa configuration optimale pour les basses températures, (toutes les
configurations acceptés sont très proches les unes des autres). La configuration finale
représente la solution du problème.

60
 Alors, les paramètres de l’algorithme RS la température initiale et le coefficient
de décroissance de la température ont une influence sur le temps de convergence du
système vers une configuration stable.

Dans notre cas, le mécanisme de génération des configurations consiste à raffiner

la qualité de la segmentation initiale d’une manière accélérée. Cette méthode repose
essentiellement sur une technique de changement locale afin de l’améliorer. Cette
politique du changement locale consiste à remplacer un site jugé mal placé appelé
site inutile donné par un autre site meilleur. Pour ce faire, nous présentons ici une
assise théorique qui assure la faisabilité du changement.

Soit A=(a1, …, an) une configuration ; a1, a2, ..., an sont des sites .

Le changement local de A consiste à supprimer un site inutile et insérer un site

pour diviser un polygone non homogène.

La procédure de génération d’une configuration GENERER est donnée par le

code suivant :
Procédure GENERER
Début
B :=A ;
Chercher et supprimer un site ak inutile ;
MAJ le DV associé à {a1,…,ak-1,ak+1 …,an} ;
Insérer un site s à la configuration A ;
bk :=s ; MAJ du DV associé à B; Evaluer H(B) ;
Fin ;

Tableau 4.5: Procédure GENERER

A/ Suppression d’un site inutile

Soit A=(a1, …, an) P. Nous disons que ak est un site inutile si son polygone
associé P(ak) vérifie les conditions suivantes :

1) Le polygone P(ak) associé au germe ak est homogène (cf. équation 4.2).

2) Si le polygone voisin est homogène alors la différence entre les moyennes du

polygones P(ak) et du polygone voisin est inférieur à un seuil fixé noté α. On
dit que les deux polygones sont similaires.

61
 3) La somme des longueurs des arêtes séparant le polygone P(ak) et les
polygones voisins non homogènes, normalisée par le périmètre est inférieure
à un seuil fixé.

Formellement, ceci se traduit par les conditions :

1) Pred(ak) est vrai.

2) aj {a1, …, ak-1, ak+1 …, an}, aj est un site voisin de ak et Pred(aj) est vrai

alors :

(4.10)

(où (4.10) est le critère de similarité et Pr(ak,aj) = |m(ak)-m(aj)| où m(ak) est la

moyenne des niveaux de gris des pixels du polygone ak : c-à-d les deux
polygones ont le même niveau de gris).

3) Soit aj un site voisin de ak jk.

(4.11)

D’où L(ak,aj) est la longueur de l’arête séparant P(ak) et P(aj). Le seuil est pris
très faible (en pratique [0.01,0.05]) afin d’éviter de générer des grandes
régions non homogènes.

Figure 4.10 : Démonstration de suppression et d’insertion de site

62
 Dans la figure4.10, les sites voisins 1-2-3-4-5-6-7 contient un site inutile1, ils
deviennent R-2-3-4-5-6-7 après suppression du site 1 (voir b) et insertion du site
R (voir c). (H : homogène et NH : non homogène).

B/ Insertion d’un site

Après suppression d’un site inutile et après mis à jour du DV associé à

l’ensemble des sites non supprimés. Soit W={w1,w2,…,wk-1} cette configuration
(wi sont les sites). Nous insérons un autre site dans une position afin d’assurer
l’amélioration de notre fonction objective (voir figure 4.10.b). Nous pouvons
définir plusieurs façons d’insertion du site. Nous allons choisir la manière
suivante (voir Figure4.10.c).

Nous cherchons wj W qui vérifie les deux conditions :

 Pred(wj) est faux.



Nous choisissons un site wl voisin non homogène de wj et nous traçons le

segment wjwl. Nous insérons aléatoirement notre nouveau site wk dans une
position du segment à l’intérieur de P(wj).

4.5.2 Algorithme K-means

Le principe de cet algorithme est comme suit :

Nous affectons chaque pixel à la région la plus proche où la distance entre le pixel et
le germe de cette région est minimale (i.e effectuer une partition de Voronoi).

Puis nous itérons comme suit: les centres des différentes régions sont recalculés et
chaque pixel est de nouveau affecté à une région en fonction du centre le plus proche.
La convergence est atteinte lorsque les centres sont fixes, le processus est comme
suit :

 Mise à jour des centres des classes

Nous recalculons le centre de chaque région ( ); il est donné par :

63
 (4.12)

Tel que :
 n : le nombre de pixel qui appartient à la région k.

 : le pixel i.

 Test de convergence

Nous répétons le processus :

 Calculer la distance.
 Affecter les pixels.
 Mise à jour des centres des régions.

Jusqu'à ce que le critère d’arrêt est satisfait, nous nous arrêtons si :

(4.13)

Tel que :
 k : la région k (k=1,…,K).
 q : l’itération q.

C’est à dire le centre de la région k à l’itération « q » est similaire au centre de la

même région à l’itération « q+1 », donc pas de changement de partition d’une
itération à une autre.

4.6 Résultats expérimentaux

Dans cette section, nous présentons nos résultats numériques. Il s’agit de tester
notre approche de segmentation sur des images en niveau de gris et de mettre en
évidence l’influence des paramètres d’initialisation utilisés.
Des résultats sur plusieurs types d’images seront présentés et des études comparatives
permettront alors de tirer quelques conclusions.

4.6.1 Paramètres d’initialisation

Avant d’entamer la segmentation, il faut expliquer les différents paramètres

nécessaires à cette dernière.

64
  Seuil d’homogénéité d’une région,

 Seuil de similarité entre deux régions voisines.

Ces deux paramètres sont nécessaires pour la construction de diagramme de voronoï.

Le reste des paramètres nécessaires à l’exécution des algorithmes de segmentation
implémentés :

 Nombre d’individus.

 Nombre de régions.

Quelques paramètres de l’algorithme RS nous avons fixé leurs valeurs :

 Température initiale=20.

 Taux de refroidissement=0,9.

 Température finale=0,5.

Nous avons fixé ces paramètres après avoir expérimenter plusieurs valeurs, ceci
dans le but d’obtenir des résultats optimum.

4.6.2 Résultats de segmentation

Dans ce qui suit, nous présentons les résultats de segmentation par les différents
algorithmes implémentés sur différentes images, en indiquant les différents
paramètres de chaque méthode.

Nous avons calculé après l’exécution de chaque algorithme sur différents images :
le pourcentage des polygones homogènes par rapport à tous les polygones générées
(%NPH) qui se diffère selon l’algorithme appliqué et selon le seuil d’homogénéité
qui est déterminé par l’utilisateur. En plus nous avons illustré la valeur de la fonction
objective que nous avons cherché à minimiser (MFE) pour un bon résultat. Nous
avons classé les images utilisés en deux catégories à savoir images synthétique et non
synthétiques.

65
4.6.2.1 Segmentation des images synthétiques

1) Image synthétique 1

Figure 4.11 : Image synthétique 1

Les paramètres :

 Nombre de régions=3000.
 Nombre d’individus=10.
 Seuil d’homogénéité d’une région=15,
 Seuil de similarité entre deux régions voisins=65.

AG RS KM

Avant
extraction
de région

Après
extraction
de région

NPH%=94,74%, NPH%=93,32%, NPH%=93,61%,

MFE=1838 MFE=2044 MFE=2224

Tableau 4.6 : Résultats de segmentation de l’image synthétique 1

66
 2) Image synthétique 2

Figure 4.12 : Image synthétique 2

Les paramètres :

 Nombre de régions=3000.
 Nombre d’individus=10.
 Seuil d’homogénéité d’une région=4,
 Seuil de similarité entre deux régions voisins=60.

AG RS K-means

Avant
extraction
de région

Après
extraction
de région

NPH=90,9%, NPH=89,1%, NPH=88,4%,

MFE=383 MFE=384 MFE=414

Tableau 4.7 : Résultats de segmentation de l’image synthétique 2

67
 3) Image synthétique 3

Figure 4.13 : Image synthétique 3

Les paramètres :

 Nombre de régions=3000.
 Nombre d’individus=10.
 Seuil d’homogénéité d’une région=8,
 Seuil de similarité entre deux régions voisins=50.

AG RS KM

Avant
extraction
de région

Après
extraction
de région

NPH%=89,92%, NPH%=85,37%, NPH%=86,38%,

MFE=1325 MFE=2021 MFE=2155

Tableau 4.8 : Résultats de segmentation de l’image synthétique 3

68
 4) Image synthétique 4

Figure 4.14 : Image synthétique 4

Les paramètres :

 Nombre de régions=3000.
 Nombre d’individus=10.
 Seuil d’homogénéité d’une région=10,
 Seuil de similarité entre deux régions voisins=8.

AG RS KM

Avant
extraction
de région

Après
extraction
de région

NPH%=72,3%, NPH%=66,4%, NPH%=66,5%,

MFE=224 MFE=235 MFE=256

Tableau 4.9 : Résultats de segmentation de l’image synthétique 4

69
 5) Image synthétique 5

Figure 4.15 : Image synthétique 5

Les paramètres :

 Nombre de régions=2000.
 Nombre d’individus=10.
 Seuil d’homogénéité d’une région=4,
 Seuil de similarité entre deux régions voisins=110.

AG RS KM

Avant
extraction
de région

Après
extraction
de région

NPH%=89,09%, NPH%=86,32%, NPH%=87,41%,

MFE=924 MFE=1199 MFE=1211
Tableau 4.10 : Résultats de segmentation de l’image synthétique 5

70
 6) Synthèse

Nous remarquons que le résultat de l’algorithme AG possède le plus grand nombre de

polygones homogène, il atteint le minimum de la fonction d’évaluation par rapport
aux résultats des autres algorithmes. Alors nous pouvons dire que la qualité de la
segmentation en utilisant l’algorithme génétique est excellente que celle utilisant
l’algorithme recuit simulé, qui est à son tour meilleur que le résultat de K-means.
(Sachant que l’exécution de ce dernier est plus rapide que les autres, et l’algorithme
génétique est plus lente en temps d’exécution).

4.6.2.2 Segmentation des images non synthétiques

1) Segmentation de l’image Muscle

Figure 4.16 : Image Muscle

Les paramètres :

 Nombre de régions=3000.
 Nombre d’individus=10.
 Seuil d’homogénéité d’une région=5,
 Seuil de similarité entre deux régions voisins=8.

AG RS K-means

Avant
Extraction de
Région

71
 Après
Extraction de
Région

NPH%=58,93%, NPH%=54,34%, NPH%=38,18%,

MFE=890 MFE=933 MFE=1158

Tableau 4.11 : Résultats de segmentation de l’image muscles

2) Segmentation de l’image Maison

Figure 4.17 : Image maison

Les paramètres :

 Nombre de régions=3000.
 Nombre d’individus=10.
 Seuil d’homogénéité d’une région=8,
 Seuil de similarité entre deux régions voisins=15.

AG RS K-means

Avant
extraction
de région

72
 Après
extraction
de région

NPH%=60,5%, NPH%=58,6%, NPH%=45,83%,

MFE=458 MFE=515 MFE=690

Tableau 4 .12 : Résultats de segmentation de l’image maison

3) Synthèse

D’après les valeurs de NPH et MFE, nous remarquons que les images segmentées de
cette catégorie sont bonne, mais quand on les compare à celles de la première
catégorie, elles sont moins nettes.

Nous remarquons aussi que les résultats de segmentation par l’algorithme génétique
sont toujours meilleurs que les autres, et le K-means donne des résultats moins
satisfaisant dans un temps d’exécution faible par rapport aux deux autres algorithmes.

Nous devons mentionner une autre remarque qui est que plus il y a de détails dans
l’image plus le temps d’exécution est long et moins les résultats sont satisfaisant.

4.7 Conclusion

Les méthodes de segmentation évolutionnaire basé le diagramme de Voronoï

permet d’obtenir de bons résultats dans différents types d’images surtout pour les
images synthétiques. Ces résultats dépendent grandement du nombre de germes
initiaux, et les paramètres (seuil d’homogénéité et le seuil de similarité) qui se
diffèrent selon le détail de l’image. En effet, le temps de segmentation est très
important et augmente considérablement avec la taille de l’image, le nombre de
germes initiaux et le détail de l’image.

L’avantage de notre approche réside dans l’exploitation, dès l’initialisation, des

informations obtenues par la détection de contour qui permet d’éviter la construction
de régions non homogènes autour des contours, donc une réduction de temps obtenue.

73
 Les algorithmes du Recuit Simulé et Algorithme Génétique présentés dans ce
chapitre sont lentes mais théoriquement optimales. En revanche, l’algorithme K-
means ne garanti pas de la convergence vers un optimum global cependant il permet
une segmentation dans un temps d’exécution très rapide.

De ce fait, nous pouvons conclure que l’algorithme génétique par diagramme de

Voronoï donne d’excellents résultats pour différentes images dans un temps
acceptable notamment en tenant compte de la coopération avec l’approche contour.

74
 Conclusion générale et perspectives

Les problèmes les plus importants en traitement et analyse d’images font suite à
l’isolation des différentes entités qui composent celle-ci. Cette opération,
pratiquement obligatoire dans tous les systèmes de vision artificielle, est la
segmentation. Les nombreux travaux qui lui ont été consacrées sont fortement
conditionnés par la qualité de l’interprétation.

De manière non exhaustive, nous avons présenté dans le premier chapitre un

panorama des diverses méthodes de segmentation utilisées pour segmenter les images
en niveaux de gris. A savoir les méthodes basées contour, les méthodes basées région
et les méthodes coopératives.

Dans le deuxième chapitre, nous avons présenté le principe général de trois

algorithmes d’optimisation à savoir l’algorithme génétique, l’algorithme recuit simulé
et l’algorithme K-means. Comme il existe différentes structures utilisées pour les
algorithmes de segmentation, nous avons choisi les diagrammes de Voronoï que nous
avons détaillé dans le troisième chapitre, en donnant leurs principes et avantages.

Dans le dernier chapitre, nous avons présenté notre approche (DVSEG) de

segmentation d’images basée sur une partition en polygone de Voronoï, qui s’intègre
dans l’approche coopérative. Nous avons implémenté trois algorithmes
d’optimisation, à savoir l’algorithme génétique, recuit simulé et le K-meeans.

Afin d'évaluer la validité et la performance de notre nouvelle approche (DVSEG),

nous avons expérimenté notre système sur différentes images. Les résultats
expérimentaux sont très encourageants et montrent clairement la robustesse d'une telle
approche.

D’après les résultats obtenus par différentes expériences appliquées sur différents
types images, nous avons conclu que la méthode de segmentation de Voronoï est une
méthode qui permet d’obtenir de bons résultats qu’on peut améliorer. Ces résultats
dépendent grandement du nombre de germes initiaux. Cependant la remarque qu’on
doit faire est que le temps de segmentation est important et augmente avec la taille de
l’image et le nombre de germes initiaux.

75
 Les résultats obtenus sont dans leurs globalités acceptables, tout en confirmant la
supériorité de l’algorithme génétique sur les autres algorithmes en termes de qualité
mais ses performances en termes de temps d’exécution en font une cible de critiques.

Notre approche nécessite le réglage de nombreux seuils et paramètres, tels que le

nombre de germes initiaux, le seuil d’homogénéité, le critère de similarité et les
critères d’arrêt. L’ajustement de ces paramètres est délicat, de telle sorte qu’il est
difficile de prévoir si nous aboutirons à une sous-segmentation ou à une sur-
segmentation de l’image.

Ce travail se voit ouvert à plusieurs extensions dont les principales sont les
suivantes :

1. Pour les images complexes, l’approche Laplacien est sensible au bruit et,
généralement, ne produit pas des contours fermés, car il s’agit d’une méthode
dérivative. Pour cela nous proposons de la modifier par l’approche Derish (cf.
paragraphe 1.3.1.2) qui est plus optimale et moins sensible au bruit à cause de sa
propriété d’être paramétrable par un facteur d’échelle α qui contrôle le degré de
lissage.

2. D’après Grenfenstette [Grefenstette,93] mentionne que les algorithmes

génétiques peuvent être combinés avec les techniques de recherche locale, en
plus, il a donnée des exemples de mise en œuvre réussie des algorithmes
génétiques hybrides pour la segmentation d'images. Pour cela, nous proposons de
combiner l’algorithme génétique avec le recuit simulé sur la base de diagramme
de Voronoï, pour améliorer l’aptitude de quelques individus par des changements
locaux d’une façon accélérée.

3. Les algorithmes évolutionnaires sont des algorithmes coûteux en temps de calcul,

mais il est facile de voir que l'étape la plus coûteuse est l'évaluation de la
performance de toute une population, cette étape est constituée de calculs
totalement indépendants entre eux. Il semble donc facile de les paralléliser, soit
par une simple parallélisation du calcul de performance, ou bien la distribution
complète de la population sur les divers processeurs disponibles.

76
 Bibliographie

[Ahuj, 85] N. Ahuja, B. An, B. Schachte. Image representation using Voronoi

tesselation, Comp. Vision Graphics, Image Processing, Vol. 29, 286-
295,(1985).
[Andrey, 97] Andrey, P., Segmentation d'images par algorithmes génétiques.
Thèse de doctorat. Université Paris7. Décembre 1997, Paris.
[Angot, 99] François Angot « Segmentation d’images 2D et 3D, application à la
quantification d’images histologiques et cytologiques obtenues par
microscopie» thêse de Doctorat de l’Université de Caen, Spécialité :
Traitement du signal et des images, soutenue le 2 février 1999.

[Arbelaez, 04] Pablo Andrés Arbeláez , Laurent D. Cohen, « Segmentation d'images

couleur par partitions de Voronoï » traitement du signal
2004_volume 21_numéro spécial L'image numérique couleur.
[Asano, 85] Asano, M.Edahiro, H.Imai, M.Iri and K.Murota, «Practical use of
Bucketing Techniques in Computational Geometry». Computational
geometry. G.T.Toussaint ed.Elsevier Science Publishers (North-
Holland), pp 153-195,1985.
[Aurenhammer, 91] F. Aurenhammer. Voronoï diagrams - a survey of a fundamental
geometric data structure. ACM Computing Surveys, 33(3):345{405,
1991.
[Benois et al., 92] J. Benois and D. Barba, "Image segmentation by region-contour
cooperation for image coding", Proceedings of the 11th IAPR
International Conference on Image, Speech and Signal Analysis, 3,
p. 331--334, 1992.
[Bertin, 94] Eteinne Bertin, « Diagramme de voronoï 2D et 3D : application en
analyse d’image » thêse de doctorat, université Joseph Fourier-
Grenoble I, soutenu le 25 janvier 1994
[Bertin, 95] Etienne Bertin, « Un modèle de partitionnement Optimal en
Imagerie »”le 15ième Collooque Gretsi-Juan-Les-Pins , du 18 au 21
septembre 1995.
[Bhanu, 94] Bhanu, B., Genetic Learning for adaptive image segmentation. USA:
Kluwer Academic Publishers, 1994.
[Bhanu et al., 95] Bhanu, B., Lee, S. and Das, S., Adaptive image segmentation using
genetic and hybrid search methods. IEEE Trans. on Aerospace and
electronic syst. 1995, Vol. 31,4, pp. 1268‐1291.
[Bres,03] S.Bres, J.Jolion et F.Lebourgeois, Traitement et analyse des images
numériques, Sermes Sciencepublication,2003.
[Canny, 86] J. Canny, “A computational approach to edge detection”, IEEE
Trans. On Pattern Analysis and Machine Intelligence, vol. 8, n°6, p.
679-698, novembre 1986.
[Carron, 95] T. Carron , Segmentation d’images couleur dans la base Teinte-
Luminance-Saturation : approche numérique et symbolique. Thèse
de doctorat, Université de Savoie, Décembre 1995.

77
[Chassery et al., 84] J.M. Chassery et C. Garbay, An iterative segmentation method based
on a contextual color and shape criterion. Dans IEEE Trans. PAMI
6, pp. 794-800 1984.
[Chassery et al., 91] Chassery, J. M. et Melkemi, M. Diagnmme de Voronoï appliqué à la
segmentation d'images et à la détection d'événements en imageries
multisources. Traitement du Signal, vol. 8, no 3, p. 155-163, (1991)
[Chu et al., 93] Chu C. C. and Aggarwal J. K. (1993). "The integration of image
segmentation maps using region and edge information". IEEE
Transactions on Pattern Analysis and Machine Intelligence. Vol.
15(12), pp. 1241-1252.
[Cocquerez et al., 95] J.-P. Cocquerez et S. Philipp. « Analyse d’Images : filtrage et
segmentation ». Masson, 1995
[Colorni et al., 96] A. Colorni, M. Dorigo, F. Maffioli, V. Maniezzo, G. Righini, M.
Trubian, Heuristics from nature hard combinatorial optimisation
problems. Published in International Transactions in Operational
Research, 3, 1. 1-21, 1996.
[Deriche, 87] R. Deriche, “Using Canny's criteria to derive a recursively
implemented optimal edge detector”, International Journal of
Computer Vision, p. 167-187, 1987.
[Fontaine, 01] Michaël Fontaine, «Segmentation non supervisée d’images couleur
par analyse de la connexité des pixels » thèse de doctorat, université
de LILLE , Discipline : Automatique et Informatique Industrielle.
Soutenue le 18 décembre 2001.
[Goldberg, 89] D.E.Goldberg, “Genetic Algorithms in Search, Optimization, and
Machine Learning”. Publisher: Addison Wesley , (1989).
[Gonzalez et al., 93] R. Gonzalez et R. Woods, Digital image processing. Dans Addison-
Wesley Publishing Company, Reading, MA 1993.
[Grefenstette, 93] J.J. Grefenstette. Genetic algorithms and machine learning. In
COLT, pages 3–4, 1993.
[Haralick et al., 85] R. Haralick et L. Shapiro, Image segmentation techniques. Computer
Vision Graphics Image Processing, vol. 29, pp. 100-132 1985.
[Holland, 75] Holland J. H., Adaptation in Natural and Artificial Systems,
University of Michigan Press, Ann Arbor, Michigan, 1975.
[Horowitz, 76] S.L. Horowitz et T.PAVLIDIS “Picture segmentation by traversal
algorithm”. J. ACM, 23, 368 – 388, 1976.
[Jamieson et al., 03] Jamieson, M., Fieguth, P. and Lee, L. J., Parametric Contour
Estimation by Simulated Annealing. Proc. of Int. Conf. on Image
Process. (ICIP03). pp. 449-452, Vol. 3, September 14‐17 2003,
Barcelona (Spain).
[Kall, 99] L.Kallel. Convergence des algorithmes génétiques : aspects spatiaux
et temporels. Thèse de doctorat (spécialité : Mathématiques
Appliquées ) de l’école polytechnique sous la direction de Marc
Schoenauer. Soutenue le 5 Février 1999.
[Kanai, 98] Y. Kanai, Image Segmentation Using Intensity and Color
Information. Dans The International Society for Optical Engineering
Proc. SPIE - Visual Communications and Image Processing, vol. 28-
30, pp. 709-720 1998.

78
[Kass et al., 87] Kass, M., Witkin, A. et Terzopoulos, D. (1987). Snakes : active
contour models. International Journal of Computer Vision, 1(4):
321–331.
[Kirkpatrick et al., 83] S. Kirkpatrick, C.D. Gelatt Jr., M.P. Vecchi, "Optimization by
Simulated Annealing," Science, 220, 1983, pp. 671-680.
[Klein, 89] R. Klein. Concrete and abstract Voronoï diagrams. Lecture Notes in
Computer Science, Springer Verlag ed., 1989
[Kubler, 89] O.Kubler, F.Klein, R.Ogniewicz and U.Kienholz, Isolation and
identification of abuting and overlapping objects in binary images»
Proc. Of the 5th Internat. Conf. on Image Analysis and proc., pp 340-
347, 20-22 sept.,1989, Positano, Italy.
[Lucchese et al., 01] Lucchese L. and Mitra S. K. (2001). "Color image segmentation: A
state-of-the-art survey". Proc. of the Indian National Science
Academy (INSA-A). Vol. 67-A(2), pp. 207-221.
[Maitre, 03] Maitre, H. (coordinateur), Le traitement des images. Paris : Hermes,
2003.
[Majdi et al., 06] Majdi. Nasab, Analoui, M. and Delp, E. J., Decomposition
parameters of mixture gaussian model using genetic and maximum
likelihood algorithms on dental images. Pattern Recognition Letters.
2006, Vol. 27, pp. 1522‐1536.
[Marcelpoil, 91] R.Marcepoil, Y.Usson, J.M.Chassery, “Segmentation Morphologique
incluant des paramètres d’ordre et desordre : Quantification par
Diagramme de Voronoi et application à la sociologie cellulaire. 967-
972, AFCET RFIA, 8e Congrès1991.
[Materka et al., 98] Materka A. and Strzelecki M. (1998). "Texture Analysis Methods - A
review". Bruxelles, Technical University of Lodz, Institute of
Electronics.
[Melkemi, 92] Mahmoud Melkemi. ”Approches génétiques par modeles de voronoi
en segmentation d’image”. Université Joseph Fourier Grenoble1,
Fervrier 1992.
[Metr, 53] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller,
"Equation of State Calculation by Fast Computing Machines," J. of
Chem. Physics 21, 1953, pp. 1087-1092.
[Meyer, 92] F. Meyer, Color image segmentation. Dans Proceedings of the 4th
Conference Image Processing and its Applications, pp.303-306 1992.
[Mong, 90] O. Monga. Segmentation d’images : Où en sommes nous ?. Rapport
de recherche n° 1216. INRIA Recquencourt. Avril 1990.
[Nguyen, 09] Giap Nguyen, “Extraction de zones d’intérêts dans une image de
textures”, Rapport de stage, Laboratoire Informatique, Image et
Interaction (L3I), Université de La Rochelle, le 30 aout 2009.
[Ohya et al., 84] Ohya, T.,hi,M., and Murota, K. (1984) A fast Voronoï diagram
algonthrn with quatemary tree bucketing. Information Processing
Letters, vol. 18, p. 227-231.
[Pavlidis, 77] Pavlidis, T. (1977) Structural pattern recognition. Springer Verlag
Editions.
[Preparata et al., 88] F.P. Preparata and M.I.S. Shamos. Computational Geometry, an
Introduction. Springer Verlag, NewYork, 1988.

79
[Rom, 88] H.Rom and S.Peleg Image representation using Voronoi tessellation:
Adaptive and secure., Proceed. Of Computer Vision and pattern
Recognition, Ann Arbon. Michigan, pp 282-285, 1988.
[Sadgal, 05] Mohammed Sadgal, Aziz El Fazziki, Abdellah Ait Ouahman: Aerial
image processing and object recognition. The Visual Computer
21(1-2): 118-123 (2005)
[Salotti, 94] J.M. Salotti, « Gestion des informations dans les premières étapes de
la vision par ordinateur », Thèse de doctorat, Institut National
Polytechnique de Grenoble, 1994.
[Sebari et al., 07] Imane Sebari et Dong-Chen HE « Les approches de segmentation
d’image par coopération régions-contours». Centre d’applications et
de recherches en télédétection (CARTEL), Département de
géomatique appliquée, Université de Sherbrooke, 2500, boulevard de
l’Université, Sherbrooke (Québec), Canada J1K 2R1Revue
Télédétection, 2007, vol. 7, n° 1-2-3-4, p. 499-506.
[Sezgin et al., 04] Sezgin M. and Sankur B. (2004). "Survey over image thresholding
techniques and quantitative performance evaluation". Journal of
Electronic Imaging. Vol. 13(1), pp. 146-165.
[Theiler et al., 97] James Theiler and Galen Gisler, "A contiguity-enhanced k-means
clustering algorithm for unsupervised multispectral image
segmentation", Proc SPIE 3159. pgs 108--118, 1997.
[Toussaint, 80] G.T Toussaint, the relative neighborhood graph of finite planar set,
Pattern Recognition, pp, 1324-1347, 1980.

[Tremeau, 97] A. Tremeau, N. Borel, A Region Growing and Merging Algorithm to

Color Segmentation. Dans Pattern Recognition, vol. 30, no. 7, pp.
1191-1204 1997.
[VanL, 87] P.J.M. Van Laarhoven, E.H.L. Aarts, Simulated Annealing : Theory
and Applications, D. Reidel Publ. Co., 1987.

[Xavier, 08] Xavier Philippeau, « Segmentation en régions » Date de publication :

05/01/2008 disponible au site developpez.com.

[Xavier, 97] Xavier Hüe « Genetic Algorithms for optimisation, Background ans
applications» Edinburgh Parallel Computing Centre, version 1.0
February 1997. available from: http://www.epcc.ed.ac.uk/epcc-
tec/documents/
[Zhaoyang, 89] L.Zhaoyang, Application of Delaunay triangulation in image coding.
The 5th Internat. Conf. on Image Analysis and Processing pp.49-53
Positano, Italy 20-22 sep. 1989.

[Zhang et al., 04] Zhang, X.-W., Song, J., Lyu, M. R. et Cai, S. (2004). Extraction of
karyocytes and their components from microscopic bone marrow
images based on regional color features. Pattern Recognition,
37:351–361.
[Zhu et al., 96] Zhu, S. et Yuille, A. (1996). Region competition: Unifying snakes,
region growing, and bayes/mdl for multiband image segmentation.
IEEE Trans. On Pattern Analysis and Machine Intelligence,
18(9):884–900.

80
 ANNEXE

Le processus de POISSON est défini de la manière suivante :

Définition :

1. Le nombre d’événements, dans une région planaire A d’aire F(A), suit une
distribution de POISSON de paramètre λ.F(A).
2. Etant donnés n événements xi dans une région A, les xi forment un échantillon
de la loi uniforme sur A.

Un algorithme de simulation d’une variable aléatoire suivant la loi de POISSON est

définit en appliquant le théorème suivant :

Théorème :

Soit (Xn) n≥1 une suite de variables aléatoires réelles indépendantes de loi
exponentielle de paramètre λ. On définit une variable N par :

 N=0 si X1>1.
 N=k si X1+X2+...+Xk≤1 et X1+X2+...+Xk+Xk+1>1.

Alors N est une variable aléatoire de la loi de POISSON de paramètre λ. L’algorithme

fondé sur l’application du théorème précédent est décrit de la manière suivante :

int poisson(float λ)
{
int N = -1 ;
float s = -1 ;
float v = 0 ;
float q = exp(-λ) ; // λ est la moyenne de la loi de Poisson
float u = random() ; // tirage d'un nombre compris entre 0 et 1
//suivant la loi uniforme
Tant que s <= u Faire
N = N + 1 ;
v = v + puiss(λ ,N)/fact(N) ; //puiss(λ,N) signifie λ à la
//puissance N et fact(N) est

81
 //la factorielle de N
s = v*q ;
FinTantque
return N ;
}

N est l’observation de POISSON cherchée

82
 Résumé

La segmentation d’images constitue une partie prépondérante d’un système de

reconnaissance. Elle peut être définie comme étant toute technique permettant de
partitionner une image selon un ou des critère(s) d’homogénéité. Elle peut se faire en
se basant sur : La couleur, la texture, la forme…,

Nous avons proposé un système à base des diagrammes de Voronoï à même de

segmenter des images en niveau de gris. Cette approche s’inscrit dans la classe des
algorithmes de segmentation Division/Fusion.

Dans cette approche, nous combinons la méthode du Laplacien pour la

détection des points de contour avec un algorithme d’optimisation stochastique basé
sur le principe de Charles Darwin à savoir : l’algorithme génétique. Après avoir utilisé
une amélioration de l’image, l’étape de division se fait par une division de l’image à
segmenter en polygones de Voronoï guidée par un processus génétique. Puis une
étape d’extraction de régions similaires est appliquée comme phase de fusion.

Nous avons commencé notre travail par un état de l’art sur les méthodes de
segmentation d’images. Puis nous avons donné une description générale des trois
algorithmes d’optimisation utilisés à savoir l’algorithme génétique, le recuit simulé et
le K-means. Ensuite, nous avons étudié les principes des diagrammes de Voronoï et
enfin elle a présenté la démarche de l’approche proposée. La candidate a implémenté
les trois algorithmes cités en se basant sur une structure de diagramme de Voronoï
pour des raisons de comparaisons.

En effet, une étude comparative des premiers résultats obtenus démontre que
l’algorithme génétique donne de bons et acceptables résultats pour différentes images
surtout synthétiques, mais l’algorithme reste lent en matière de temps d’exécution.
Cette étude expérimentale a démontré aussi que les résultats obtenus par le recuit
simulé sont mieux que ceux trouvés avec le K-means ce qui confirme la théorie des
deux méthodes.

Mots clés : segmentation d’image, division et fusion, diagramme de Voronoï,

algorithme génétique.

83
 Abstract

Image segmentation is a major part of a recognition system. It can be defined

as any technique for partitioning an image according to one or many test (s) of
homogeneity. It can be based on: color, texture, shape...

We have proposed a system based on Voronoï diagrams able to segment

images in grayscale. This approach fits in a class of algorithms of segmentation Split /
Merge.

In this approach, we combine the method of the Laplacian for the detection of
edge points with a stochastic optimization algorithm based on the principle of Charles
Darwin namely the genetic algorithm. After using an image enhancement, the division
step is done by a division of the image to be segmented into Voronoï polygons guided
by a genetic process. Then a step of extracting similar regions is applied as fusion
phase.

We started our work by a state of the art on methods of image segmentation.

Then we gave a general description of the three optimization algorithms used namely
genetic algorithms, simulated annealing and the K-means. Then we studied the
principles of Voronoï diagrams and finally we presented the procedure of the
proposed approach. Based on a structure of Voronoï diagram, we have implemented
the three algorithms mentioned above for reasons of comparison.

Indeed, a comparative study of early results showed that the genetic algorithm
gives good and acceptable results for different images mainly synthetic, but the
algorithm remains slow in terms of execution time. This experimental study also
showed that the results obtained by simulated annealing are better than those found
with the K-means, which confirms the theory of the two methods.

Key words: image segmentation, split and merge, Voronoï diagram, genetic
algorithm.

84
 .. :

.
. :

85