Split & Merge

5/12/2018 Split & Merge - slidepdf.com

http://slidepdf.com/reader/full/split-merge 1/17

1

Université Mohammed Premier

Faculté des Sciences

Département d’informatique

Oujda

Réalisé par : encadré par :

-Mohammed ELBERKANI Mr. Mohammed Talibi ALAOUI

-Rachid BELMESKINE

-Sara DRIEF

Année universitaire: 2010/2011

Master Spécialisé Ingénierie Informatique

Mini Projet

Segmentation d’une image

SPLIT & MERGE



2

Sommaire : Introduction :………………………………….………………………..……………………...2

Chapitre 1 : segmentation ; ………………………………………………………........………3

1. Segmentation par seuillage ………………………………………………………………....3 1.1. Détection des vallées ………………………………………………….…………….....31.2. Seuillage entropique ……………………………………………………...……………3

2. Segmentation par région ……………………………………………………………………3 2.1. Croissance de régions (région growing) ………………………………………………42.2. Segmentation par division/fusion (split/ merge) ………………………………………4

3. Segmentation par contour ………………………………………………………………..…43.1 Méthode de détection de contour pour les images en niveau de gris...…………...……4

A. Méthodes dérivatives ………………………………………………………………4 B. Les modèles déformables……………………………………………………...……4

3.2. Méthode de détection de contour pour les images couleurs………………………… ..5A. Méthodes dérivatives ………………………………………………………………5 B. Modèle déformable : ……………………………………………………………….5

4. Conclusion : …………...……………………………………………………………………5

Chapitre 2 : Split and merge …………………………………………………………..………6

1. Split : décomposition ………………………………………………………………..……...6

2. Merge : fusion ………………………………………………………………………………7

3. Algorithme : ………………………………………………………………………...………7 4. Evaluation de la segmentation : …………………………………………………………….8

Chapitre 3 : Conception et mise en œuvre : ……………………………….……………..……9

1. Choix ……………………………………………………………………………..…………91.1 Choix technique : ..……………………………………………………………………… 91.2. Mesure d’homogénéité : ………………………………………………………..…………9 1.3. Notion de voisinage : ....…………………………………………………………..………9

2. Split : ………………………………………………………………………………………10

2.1. Structures de données : ………………………………………………………….………10 2.2. Implémentation : …………………………………………………………………...……10

3. merge : ………………………………………………………………………………..……11 3.1. Structures de données : ………………………………………………………….……113.2. Implémentation : ……………………………………………………………...………11

4. Interface utilisateur : ………………………………………………………………………11

Chapitre 4 : Resultats et testes : ……………………………………………...………………12

Conclusion : ……………………………………………………………………………….…15

Références : …………………………………………………………………………….….…16



3

Introduction

La vision avec toutes ses propriétés a connu un grand intérêt avec l’apparition de

l’ordinateur. En effet, le développement technologique a permis de franchir un premier pasvers la vision artificielle : la numérisation de l’image. Cette numérisation est l’étape qui

précède ce qui est connu sous le nom de : traitement d’image. Le traitement d’image qui est

un processus comprenant plusieurs étapes, rentre dans le contexte de la vision artificielle.

Avec l’évolution de la technologie beaucoup de traitements spécifiques ont vu le jour.

Le cadre général dans lequel s'inscrit ce projet est celui de la segmentation d'images. Cetteopération constitue la base de tous les processus d'interprétation d'images et c'est à ce titrequ'elle reste encore l'un des principaux thèmes de recherche en vision artificielle. En

fournissant une description compacte de l'image, la segmentation d'images est une étapeimportante dans un système de traitement d'image qui peut être défini ainsi: "La segmentationd’images consiste à regrouper les pixels de ces images qui partagent une même propriété pour

former des régions connexes".

Les méthodes de segmentation d'images peuvent être classées en deux grandes approches :

La segmentation par détection de contours qui travaillent sur les discontinuités de lafonction d'intensité dans les images afin de déterminer les contours des régions. Et lasegmentation par région qui consiste à rechercher des ensembles de pixels qui partagent des

propriétés similaires. Notre travail est consacré à l’étude de l’algor ithme « split and merge »

qui rentre dans la deuxième catégorie.Le présent rapport se compose de quatre chapitres :

Le premier chapitre : Traitement d’image.

Le deuxième chapitre : Segmentation par split & merge, ce chapitre décrit l’approche desegmentation par « split and merge » et les différentes méthodes de résolution de ceproblème.

Le troisième chapitre : Conception et mise en œuvre.

Le quatrième chapitre : Tests et résultats, ce chapitre contient les résultats des testseffectués ainsi que l’interprétation de ces résultats.

Et enfin, nous terminons ce document en présentant une conclusion générale et desperspectives sur des améliorations qui pourraient être apportée notre travail.



4

Chapitre 1 : segmentation(1)

La segmentation joue un rôle prépondérant dans le traitement d’image. Elle est réalisée avant les étapes d’analyse et de prise de décision dans plusieurs processus d’analyse d’image, tels que la détection des objets. Elle aide à localiser et à délimiter les entités présentes dansl’image. Plusieurs techniques de segmentation existent et quatre grandes catégories peuvent sedistinguer : la segmentation par seuillage, par régions, par contours et enfin la segmentationpar coopération région-contour.

Dans la première catégorie, l’image est segmentée en plusieurs classes en n'utilisant quel'histogramme. Dans la deuxième catégorie, l’image est segmentée en régions en regroupant les pixels adjacents similaires selon un certain critère d’homogénéité. Quant à la segmentation par contours, elle permet de détecter les transitions entre les régions de l’image. Les résultats de cette segmentation sont les pixels candidats des limites des objets de l’image.

Ces dernières années plusieurs chercheurs s’accordent pour affirmer que la coopération

entre les segmentations par régions et par contours contribue à une meilleure prise en comptedes caractéristiques des entités de l’image.

1. Segmentation par seuillage :

Le seuillage a pour objectif de segmenter une image en plusieurs classes en n'utilisant quel'histogramme. On suppose donc que l'information associée à l'image permet à elle seule lasegmentation. A chaque pic de l'histogramme est associée une classe.

1.1. Détection des vallées :

Cette technique est la plus intuitive. On suppose que chaque classe correspond à une

gamme distincte de niveaux de gris.La position des minima Si de l'histogramme H permet de fixer les (m-1) seuils nécessairespour séparer les m classes. Cette méthode, bien que simple, est très peu appliquée car leshistogrammes traités sont le plus souvent bruités et uni modaux

1.2. Seuillage entropique :

Le seuillage entropique est une technique dérivée de la théorie de l'information. Les seuilssont déterminés de manière à maximiser l'entropie E résultant du découpage de l'histogrammeH en plusieurs classes. Pour un nombre de seuils fixe, on cherche à ce que les classesrésultantes portent le maximum d'information.

2. Segmentation par région :

Les méthodes de l'approche région cherchent à regrouper directement des pixels ayant une propriété commune. L’ensemble des regroupements de pixels définit à la fin une segmentationde l'image.

La croissance de régions, la fusion, la division et la division-fusion sont des techniquescourantes de cette catégorie.

2.1. Croissance de régions (région growing) :

Les méthodes de croissance de régions utilisent la connexité des pixels pour former des

régions homogènes. L'idée est de sélectionner, au début du traitement, plusieurs pixels qu'onappelle germes initiaux ensuite les pixels connexes à un germe respectant un certain critère de



5

similarité (niveau de gris, texture,..) sont intégrés dans le germe. Ce dernier s'étend alors pourdevenir une région. Ce processus est effectué pour tous les germes jusqu'à ce que tous lespixels soient traités. A la fin du traitement, l'image est découpée en un ensemble de régionsissues de la croissance des germes.

2.2. Segmentation par division/fusion (split/ merge) :Tout d’abord, l’image est divisée en régions homogènes, puis les régions adjacentes qui

répondent à des critères de fusion sont fusionnées.

On va détailler cet algorithme dans le chapitre suivant.

3. Segmentation par contour :

L’approche contour consiste à identifier les transitions entre les régions. Une discontinuitédans l'image n'est pas forcément liée à une variation géométrique ou physique de la surfaceobservée mais elle peut être due également à une différence d’éclairage, par exemple un effet

d'ombre. On distingue deux catégories de méthodes : l’une est adaptée pour la détection descontours d’images en niveaux de gris et l’autre est adaptée pour la détection des contoursd’images couleurs.

3.1 Méthode de détection de contour pour les images en niveau de gris :

Dans cette catégorie, on peut distinguer les méthodes dérivatives et les méthodes fondéesur les modèles déformables.

A. Méthodes dérivatives :

Les méthodes dérivatives sont les plus utilisées pour détecter des transitions d’intensité par

différenciation numérique. Ce sont des méthodes locales qui balayent l’image avec un masquedéfinissant la zone d’intérêt. A chaque position, un opérateur est appliqué afin de détecter lestransitions significatives au niveau de l’attribut de discontinuité choisi. Le résultat est uneimage binaire constituée de points de contours et de points non-contours. Etant donné que lesopérateurs de dérivation sont très sensibles au bruit, les images bruitées doivent être lissées aupréalable. Le lissage et la dérivation sont en pratique réunie dans un seul filtre.

De nombreuses techniques d’extraction de contours existent dans la littérature. Ellespeuvent être classées dans les catégories suivantes :

- Les algorithmes basés sur le gradient (ou opérateurs du premier ordre).

- Les algorithmes basés sur le Laplacien (ou opérateurs du second ordre).

- Les algorithmes multi-échelles.

- Les algorithmes utilisant des filtres sophistiqués.

B. Les modèles déformables :

Les algorithmes de segmentation fondés sur les modèles déformables ont l’avantage, par rapport aux méthodes dérivatives, de fournir des contours ou surfaces fermés. Ces méthodessont connues sous le nom du « contour actif » ou « snake ».

Un contour actif est défini comme une courbe minimisant une énergie et évoluant de

manière itérative à partir d’une position initiale proche du contour recherché jusqu’àconvergence (obtention de contour recherché).



6

3.2. Méthode de détection de contour pour les images couleurs :

Dans cette partie nous présentons les différentes méthodes mise en œuvre pour détecter lescontours dans les images couleurs.

A. Méthodes dérivatives :

En imagerie mono-composante, il existe de nombreuses méthodes qui sont abordées afinde pallier au problème de la détection des contours, ces méthodes sont reprises sous deuxstructures pour détecter les contours dans une image multi-composantes. Cette méthodecontient deux approches pour l’extraction des contours dans une image en couleurs :marginale et vectorielle.

B. Modèle déformable :

Pour la détection des contours dans des images en couleurs en utilisant les modèlesdéformables, le même principe que les images en niveaux de gris est appliqué. La différenceréside au niveau du calcul de l’énergie externe où la notion de gradient apparaît.

4. Conclusion :

Dans ce chapitre, quelques notions fondamentales liées à la segmentation et leursdifférentes approches.

Dans le prochain chapitre, on va décrire de manière détaillée une des techniques desegmentation d’image à savoir la segmentation par division/fusion (split & merge).



7

Chapitre 2 : Split and merge(2)

L'algorithme split and merge a été présenté la première fois en 1974 par Pavlidis etHorowitz.

Il est clair que l’algorithme split and merge est composé de deux phases :

1. Split : décomposition

La méthode de découpage de l'image utilisée dans cet algorithme est basée sur la notion de« quadtree ». Cette structure de données est un arbre quaternaire qui permet de stocker l'imageà plusieurs niveaux de résolution. On part d'une région initiale qui est l'image tout entière. Sicette image vérifie un critère d'homogénéité de couleur, l'algorithme s'arrête. Sinon, ondécoupe cette région en quatre parties de même taille et on lance la procédure récursivementdans ces quatre parties. La région initiale va être stockée comme un nœud dans un graphe et

les sous parties comme des fils de ce nœud. La figure 1 montre une image en noir et blanc 8x8et le découpage correspondant à chaque niveau.

La structure d'arbre associée à ce découpage est illustrée figure 2.

F IG . 1. Découpage par quadtree d'une image 8x8.



8

Fig.2.La structure d'arbre associée au découpage précédent.

2. Merge : fusion

La solution, qui correspond à la phase merge de l'algorithme, est de procéder à une fusionde régions après le découpage. L'implémentation la plus simple de cette fusion cherche tousles couples de régions adjacentes dans l'arbre issu du découpage et cherche à les fusionner sileur couleur est assez proche.

Pour réaliser cette fusion, il faut d'abord tenir à jour une liste des contacts entre régions(chaque région dispose d'un pointeur sur une liste chaînée de régions avec lesquelles elle esten contact). On obtient ainsi un graphe d'adjacence de régions ou Région Adjacency GraphEnsuite, l'algorithme va marquer toutes les régions comme non-traitées et choisir la premièrerégion R non traitée disponible.

Les régions en contact avec R sont empilées et sont examinées les unes après les autrespour savoir si elles doivent fusionner avec R. Si c'est le cas, la couleur moyenne de R est miseà jour et les régions en contact avec la région fusionnée son ajoutés à la pile des régions àcomparer avec R. La région fusionnée est marquée « traitée ».

Une fois la pile vide, l'algorithme choisi la prochaine région marquée « non traitée » etrecommence, jusqu'à ce que toutes les régions soient traitées.

3. Algorithme :

i. On commence par le premier bloc B dans la liste des blocs homogène et onl’ajoute à une nouvelle région R

ii. Pour tout bloc B’ voisin à B

Si la réunion de B’ et R est homogène alors :On retire B’ de la liste des blocs homogène ;On ajoute B’ à R ;On recommence l’étape (ii) avec les voisins de B’ ;

iii. S’ils restent des blocs dans la liste des blocs homogènes on recommence àl’étape (i), si non le « Merge» est terminé.



9

Fig.3.Graphe d'adjacence de régions

4. Evaluation de la segmentation :

Soit I_originale notre image qu’on veut segmenter et I_segmente l’mage segmentée.

Soit le nombre des régions dans limage segmentée.

Soit ces régions et la variance de la région correspondante à sur l’image

I_originale ;

Soit ;

L’évaluation de la segmentation est donnée par :



10

Chapitre 3 : Conception et mise en œuvre

1. Choix :

1.1 Choix technique :Nous avons choisi de programmer cet algorithme avec le langage C++ et OpenCV qui est

une bibliothèque graphique libre spécialisée dans le traitement d'images.

Ce langage est réputé pour sa puissance du fait de son rapprochement du langage machine.Nous avons fait en sorte que notre programme soit le moins dépendant possible de librairiesexternes.

Pour la partie "interface utilisateur" nous avons utilisé les MFC. Celle-ci nous permetd'intégrer notre programme avec une interface graphique facile d'utilisation. Notre source enC++ est donc accessible depuis le code de l'interface graphique. Le code de notre programme

est complètement séparé du code de l'interface graphique, il est conçu sous forme d'unebibliothèque réutilisable.

Dans notre projet nous avons regroupé l’ensemble des fonctions dans 3 classes :

La classe Traitement : pour les images couleurs.

La classe Traitement1 : pour les images en niveau de gris.

La classe Prétraitement : qui regroupe les fonctions de prétraitements (étirementd’histogramme, application d’un filtre).

1.2. Mesure d’homogénéité :

Il est nécessaire de définir un critère d’homogénéité, ce critère permet de tester si un bloc

ou une région (ensemble des blocs adjacentes) est homogène il existe plusieurs critères. Onchoisit d’utiliser la variance.

Pour l’opération de split : on calcule la variance pour chaque bloc, si cette variance estinferieur à un seuil donné on dit que ce bloc est homogène.

Pour l’opération de merge : lorsqu’on veut ajouter un bloc à une région, on calcule lavariance entre les deux (sans prendre en considération le nombre de pixel), si cette varianceest inferieur à un seuil donné on ajoute ce bloc à cette région.

1.3. Notion de voisinage :

Le voisinage d'un pixel est un bloc des pixels situés autour de lui.

Ici on utilise deux types de voisinage.

Voisinage de 8 pixels Voisinage de 4 pixels



11

Voisinage de 8 Voisinage de 4

Fig.4. voisins d’un pixel

2. Split :

2.1. Structures de données :

Voici les structures utilisées qui sont choisies de façon à être les plus performantespossibles :

Un bloc est représenté par un enregistrement qui contient ses coordonnées dans l'image.Nous avons choisi de conserver les coordonnées x1, y1 du coin supérieur gauche et celles dupoint inférieur droite x2, y2, la moyenne, la variance, le nombre des pixels…etc.

Il est important de garder une trace en mémoire des différents blocs homogènes pourl'opération de fusion par la suite, comme solution on conserve ces blocs dans une liste chaînée(Chaque élément de cette liste contient un pointeur vers un bloc). À cette occasion, une listechaînée simple avec accès directe au premier élément a été implémentée ainsi que lesdifférentes fonctions qui la traitent. L'utilisation d'une liste est préférée à l'utilisation d'untableau (que nous pouvons allouer de façon à contenir au maximum un nombre de blocs égalau nombre de pixels dans l'image). En effet, nous verrons qu'outre le gain en mémoire, des

opérations de suppressions des blocs nécessitant des décalages coûteux dans le cas d'untableau.

Les blocs qui sont voisins pourront être fusionnés. Notre but c'est d'éviter des parcourscoûteux dans l'ensemble des blocs pour retrouver ceux qui sont voisins. On pourrait penser àl'utilisation d'un graphe d'adjacence qui relie chaque bloc à ces voisins. Mais cette techniquenécessite la construction du graphe qui entraîne une perte en performances. Comme solutionnous avons utilisé une matrice M à deux dimensions de pointeurs vers des blocs de la mêmetaille que l'image I est allouée. Chaque élément M[i][j] de la matrice, correspondant aupixel I[i][j], pointe vers le bloc qui contient le pixel I[i][j]. Ceci garantit un accès direct à tousles voisins d'un bloc. En effet, ayant un bloc x1, y1, x2, y2, ses voisins gauches sont les blocsM[x1 - 1][y] où y varie de y1 à y2 (en supposant que x1 - 1 reste dans l'image) De la mêmemanière, on obtient les voisins dans les 3 autres cotés ( dans le cas de voisinage de 4 pixels ).De point de vue performance, l'initialisation de la matrice est équivalente à un seul parcoursde la matrice (ou de l'image) et affectation d'une valeur à chaque élément. Plus précisément,pour chaque bloc homogène x1, y1, x2, y2 nouvellement généré, leséléments M[x][y] avec x1 <= x <= x2 et y1 <= y <= y2 reçoivent l'adresse du bloc.

2.2. Implémentation :

Nous pouvons implémenter l'algorithme "Split" de deux manières différentes.

Utiliser une fonction récursive. Utiliser une boucle avec une pile (nous pouvons nous servir de la liste chaînée

comme une pile)



12

Nous avons choisi d'utiliser la récursivité pour sa simplicité. Voici l'algorithme simplifiéde cette fonction :

Choisir un seuil

Split :Si le bloc est homogène on l’ajoute à la liste des blocs homogènes

Si non on le divise en quatre sous-blocs et on applique le split sur chaque sous-blocnon homogène.

3. merge :

3.1. Structures de données : On ajoutant aux structures de données déjà présentées dans la partie de split :

Dans l'algorithme de division, si un bloc homogène est généré, alors il est ajouté de suite àla première région homogène voisine qui reste homogène après l'ajout. On utilise une listechainée pour stocker, et chaque élément de cette liste (région) pointe sur une autre liste desblocs qui apparient à cette région.

3.2. Implémentation :

On construit les régions une à une. Partant d'une région contenant un seul bloc, on l'étenden lui ajoutant progressivement les blocs voisins qui conservent l'homogénéité de la région.

Voici l'algorithme simplifié :

On prend le premier rectangle r libre (qui n’est pas ajouté à une région) et on l’ajoute à

une nouvelle région reg (liste vide)Pour tout rectangle r’ voisin à r

Si {r’} U reg est homogène alors On retire r’ de la liste des rectangles libres

On ajoute r’ à reg On recommence l’étape 2 avec les voisins de r’

S’ils restent des rectangles libres alors on recommence à l’étape 1, sinon le ‘Merge’ est

fini

4. Interface utilisateur :

L'interface graphique a été programmée avec les MFC. Elle permet à un utilisateurd'exploiter facilement les fonctionnalités de notre programme. Voici les possibilités proposéespar l'interface graphique :

-L'ouverture de différents types d'images (pnm, jpeg, png, gif etc.) ;

-Le paramétrage du "Split & Merge" (seuil, type de voisinage…) ;-Choix du type d'affichage : etc.



13

Chapitre 4 : Résultats et testes

Dans ce chapitre nous donnerons des résultats obtenus par notre application ainsil’interface graphique de notre application.

1. Interface graphique :

Fig.5 : interface graphique.



14

2. Tests :

Dans les differents test l’image a gauche est l’image originale et a droite l’image segmentée.

2.1 : Test 1 :

Fig.6 : segmentation split and merge avec seuil=500.

2.2 : Test 2 :




15

2.3 : Test 3 :


3. Résultats :

Le tableau suivant représente les paramètres avec lesquels on a effectué chaque test.

Test 1 Test 2 Test 3

seuil 500 100 10

Nombre des régions 187 628 2474

Evaluation 0,976732 0,978466 0,979682

Temps d’exécution (s) 0,562 0,610 0,719

4. Comparaison :

Nous remarquons que le nombre des régions obtenu et l’évaluation de la segmentation

sont inversement proportionnels à la valeur du seuil choisi.

Alors on peut dire qu’on obtient des bonnes résultats tant que on diminuer la valeur du

seuil.

Donc l’utilisateur peut choisir un seuil de valeur assez grand s’il veut détecter des régions

assez grandes (en gros) dans l’image. Cependant il peut choisir une petite valeur pour le seuil

dans le cas ou il veut détecter des petits objets dans l’image segmentée.



16

Conclusion

Il est évident que le point critique dans l'algorithme "Split and Merge", de point de vue

performance, est la fonction d'homogénéité. En effet, cette fonction est appelée à chaque essaid'ajout d'un quadrant à une région. Pour la fonction utilisant la variance, tous les pixels de larégion doivent être reperceurs. Un allégement est introduit concernant le calcul du nombre depixels et la somme de leurs valeurs puisque ces informations sont sauvegardées avec la régionelle même.

Il apparaît que les traitements des images ayant des grandes régions de couleur uni (unfond noir par exemple) sont les plus gourmands en temps d'exécution. Ceci s'explique par lagénération de grandes régions homogènes qui sont parcourues plusieurs fois. Une solution(implémentée en partie) serait de sauvegarder dans ces régions une autre information quiindiquerait qu'il s'agit d'une région colorée avec la même couleur qui serait mémorisée (le

parcours est alors remplacé par une simple multiplication en général)

Nous constatons que le "Split and Merge" est une méthode de segmentation efficacepuisqu'elle réunie les deux opérations division et fusion. Des algorithmes efficaces grâce auchoix des structures de données nous ont permis d'implémenter cette méthode. Toutefois,nous avons vu que des solutions donnant des résultats moins convenables existent. La solutionfinale adoptée ne donne pas des résultats aussi performants possibles que nous les voulons.Ceci s'explique par la simple raison que le "Split and Merge" commence par l'opération dedivision qui produit des quadrants homogènes plus ou moins bien placés sur les partieshomogènes de l'image (telles que nous les apercevons).



17

Références :

Bibliographie :

[1]: BELAHMRA Hadjira & MELZI Soumia. La segmentation d’image par

croissance des régions (mémoire de fin d’étude). Algerie 2009/2010

[2] : Jean-Christophe Baillie. Traitement d’image et vision artificielle. 2003

Documents

Split & Merge