"Split and Merge" et "croissance de régions

**Flo.** · 21/12/2005, 19h21

Bonjour,

Je me suis penché sur l'algorithme quadtree (split and merge), pour la segmentation d'images.

J'ai réussi à écrire quelque chose de fonctionnel (le merge est réellement difficile à coder !!!).

Il fonctionne sur des images 24 bits (RGB codés sur 8 bits). Je travaille en RGB (peut-être HLS serait-il préférable ... enfin c'est pas le problème).

Pour le critère du split, je prends la distance euclidienne de mes 3 variances RGB :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

critere = sqrt(variance(R) *  variance(R) + variance(G) *  variance(G) + variance(B) *  variance(B))

Pour le merge de 2 noeuds, je vérifie que leur valeurs RGB se trouvent bien dans une fenetre parallépipédique RGB paramétrable centrée sur un des 2 noeuds :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
critere = 
(abs(moyenne(R noeud1) - moyenne(R noeud2)) < 30) &&
(abs(moyenne(G noeud1) - moyenne(G noeud2)) < 30) &&
(abs(moyenne(B noeud1) - moyenne(B noeud2)) < 30)

Les 30 sont des paramètres indépendants.

Donc au final, ça fonctionne pas trop mal. Je suis bien sur de trouver tous les voisins en connectivité 4 ou 8 de chaque noeud. Les segments (labels) sont mémorisés dans une structure me permettant de tout connaitre de leurs propriétés.

en fait il y a pas de problème ... juste je me demande quel est l'intérêt par rapport à un algo de croissance de régions (à part le problème du gradient

, et quel problème !!! ).

Effectivement, on s'aperçoit, que si on met une valeur nulle pour le critère d'acceptabilité du split (sur la variance), le split correspond à l'image (à part si on spécifie une taille de split minimale supèrieure à 10 pixels par exemple (en dessous, c'est casi l'image elle-même)). Donc le split donne finalement l'identité. Le merge correspond donc ensuite à un algo de croissance de régions dans lequel on trouve une graine (seed) (la premiere zone issue du split non encore analysée par le merge) puis on étend la réflexion d'un possible regroupement aux voisins etc. Bref !!! un algo classique de croissance de régions. En fait j'ai quasiment écrit le merge (mise en évidence du voisinage à part), comme un algo classique de croissance de régions.

Excepté cas du problème du gradient (le split and merge, au contraire de l'autre, ne se heurte pas au problème du bruit sur l'image), quels sont les différences entre les 2 algos. Car cette expèrience me donne plutot l'impression que le split and merge tient plus de pré-traitement pour un algo de croissance de régions que comme un algo de segmentation à part entière.

Donc, si quelqu'un peut éclairer ma lanterne

.

Merci. A+.

Flo.

**Rafik_2007** · 24/04/2007, 14h45

salut je suis sur un sujet de stage ou j'ai besoin de cette fonction de split and merge, en plus c'est mon premier programme sur C++. pourrai-tu m'envoyé le code de cette fonction si cela est possible.
Merci

**pseudocode** · 24/04/2007, 16h25

Envoyé par Flo.

juste je me demande quel est l'intérêt par rapport à un algo de croissance de régions (à part le problème du gradient

, et quel problème !!! ).

C'est une TRES bonne question a laquelle je n'ai pas de réponse

.

C'est pour cela que je continue a utiliser un growing-region avec une distance qui resiste au bruit.

**parp1** · 24/04/2007, 16h52

Envoyé par Rafik_2007

salut je suis sur un sujet de stage ou j'ai besoin de cette fonction de split and merge, en plus c'est mon premier programme sur C++. pourrai-tu m'envoyé le code de cette fonction si cela est possible.
Merci

Tu veux que je te redige ton rapport aussi ???

Essaye ou demandes des conseils et la je pense qu'on t'aidera... Si tu n'en est pas convaincu ... lis la charte de DVP.

**Rafik_2007** · 30/04/2007, 13h27

Envoyé par parp1

Tu veux que je te redige ton rapport aussi ???

Essaye ou demandes des conseils et la je pense qu'on t'aidera... Si tu n'en est pas convaincu ... lis la charte de DVP.

n'importe quoi ...moi j'ai demandé cette fonctionne tout simplement par ce que elle consiste pas le coeur de mon travail et j'ai pas voulu perdre beaucoup de temps la dessu en plus c'est délicat de faite de split and merge sur des image couleur alors j'ai voulu avoir quelque chose de sur.............sinon je te demande pas de m'écrire mon rapport........

**Flo.** · 30/04/2007, 14h25

Salut,

désolé, je ne peux pas te donner le code ... tout simplement parce que je l'avais développé dans le cadre d'une société.

Le merge est la partie la plus sioux. Elle consiste à fusionner les régions voisines qui se "ressemblent" (même moyenne RGB par exemple).

Dans la thérorie, on te parleras de "graphes d'adjacence" pour merger ces régions-là. A l'époque, cette notion ne m'avait pas beaucoup parlé. Ou alors je n'étais pas parvenu à l'écrire. Je ne sais plus. Alors j'avais trouvé une astuce ; de gérer le merge comme un algo de croissance de régions.

Pour le split :

PS1 : REGIONSLIST est une liste d'objets "Regions" qui contient la moyenne RGB par exemple de la région
PS2 : REGIONSIMAGE est une image de mêmes dimensions que l'image source su Split&Merge. Elle représentera la segmentation du split.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
1- Sous-division de l'image en 4 imagettes
2- Pour chacune des 4 imagettes
       3- calcul de la variance
       4- si variance élevée, split l'imagette en 4 nouvelles imagettes et je passe au split de ce nouveau jeu de 4 imagettes (ou tu finis le jeu en cours et tu mémorises dans une liste ce nouveau jeu de 4 imagettes)
       5- sinon, le split s'arrête-là pour cette imagette
              6- j'ajoute cette nouvelle région homogène dans la liste REGIONSLIST
              7- je remplis la zone correspondante dans REGIONSIMAGE avec la valeur de l'index de la région dans la liste REGIONSLIST

On fait ensuite le merge avec un algo de croissance de région. L'image source est REGIONSIMAGE. Le critère de croissance est la moyenne RGB dont l'index dans la liste REGIONSLIST est la valeur des pixels de REGIONSIMAGE.

N'hésite pas à demander des éclaircissements.

A noter qu'il vaut mieux trabailler en HLS

.

Et de manière générale, il est malvenu de demander du code (s'il n'est pas déjà mis à disposition) sur un forum qui traite d'algorithmie. Si tu veux du code t'as www.koders.com.

A noter que l'intérêt du Split&Merge est de ne pas avoir d'à priori sur l'image à segmenter. Pour la croissance de régions, il faut au moins les seeds. On s'en passe avec le Split&Merge. Le temps passant, j'ai fini par en trouver de l'intérêt à ce Split&Merge

.

Flo.

**Rafik_2007** · 04/05/2007, 17h49

merci beaucoup, c'est trés gentil.................j'ai réussit à le developper mais pas avec les meme critere je te remerci encore une fois et t'as raison de ne pas me donner le code je comprends....
Boncourage

Envoyé par Flo.

Salut,

désolé, je ne peux pas te donner le code ... tout simplement parce que je l'avais développé dans le cadre d'une société.

Le merge est la partie la plus sioux. Elle consiste à fusionner les régions voisines qui se "ressemblent" (même moyenne RGB par exemple).

Dans la thérorie, on te parleras de "graphes d'adjacence" pour merger ces régions-là. A l'époque, cette notion ne m'avait pas beaucoup parlé. Ou alors je n'étais pas parvenu à l'écrire. Je ne sais plus. Alors j'avais trouvé une astuce ; de gérer le merge comme un algo de croissance de régions.

Pour le split :

PS1 : REGIONSLIST est une liste d'objets "Regions" qui contient la moyenne RGB par exemple de la région
PS2 : REGIONSIMAGE est une image de mêmes dimensions que l'image source su Split&Merge. Elle représentera la segmentation du split.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
1- Sous-division de l'image en 4 imagettes
2- Pour chacune des 4 imagettes
       3- calcul de la variance
       4- si variance élevée, split l'imagette en 4 nouvelles imagettes et je passe au split de ce nouveau jeu de 4 imagettes (ou tu finis le jeu en cours et tu mémorises dans une liste ce nouveau jeu de 4 imagettes)
       5- sinon, le split s'arrête-là pour cette imagette
              6- j'ajoute cette nouvelle région homogène dans la liste REGIONSLIST
              7- je remplis la zone correspondante dans REGIONSIMAGE avec la valeur de l'index de la région dans la liste REGIONSLIST

On fait ensuite le merge avec un algo de croissance de région. L'image source est REGIONSIMAGE. Le critère de croissance est la moyenne RGB dont l'index dans la liste REGIONSLIST est la valeur des pixels de REGIONSIMAGE.

N'hésite pas à demander des éclaircissements.

A noter qu'il vaut mieux trabailler en HLS

.

Et de manière générale, il est malvenu de demander du code (s'il n'est pas déjà mis à disposition) sur un forum qui traite d'algorithmie. Si tu veux du code t'as www.koders.com.

A noter que l'intérêt du Split&Merge est de ne pas avoir d'à priori sur l'image à segmenter. Pour la croissance de régions, il faut au moins les seeds. On s'en passe avec le Split&Merge. Le temps passant, j'ai fini par en trouver de l'intérêt à ce Split&Merge

.

Flo.

**Hew** · 06/02/2008, 12h50

Hello !

J'essaye de faire comme vous de la segmentation couleur avec un alog "découpe-fusion" et une structure de quadtree.
Je code tout ça sous matlab et je me demandais si mon algo de découpe était bon parce qu'autant le dire... mes résultats sont nazes

Voici mon algo (mes images sont carrés, de côté en puissance de 2) :

Initialisation :
Une matrice Q qui contient les coordonnées du premier point et la taille de l'image.
Une matrice S qui est vide.

Itération :
Tant que Q n'est pas vide
> je prends la première ligne de Q (= coordonnées d'un noeud+taille région) et je regarde si la région définie par cette première ligne est homogène
> si ce n'est pas le cas
je découpe Q en 4 -> 4 nouveaux noeuds
j'enlève de Q la ligne du noeud que je viens de traiter
je rajoute dans Q les coordonnées des nouveaux noeuds et la taille des régions
> si c'est le cas
j'enlève de Q la ligne que j'avais selectionnée
je mets dans S les coordonnées du noeud que je viens de traiter

Fin
Je récupère S avec les coordonnées de tous les noeuds et la taille des carrés qui y sont ajoutés.

Bon je ne suis pas une star en programmation et en algorithmes, mais ça donne un résultat très loin de ce que j'espérais

.
Est-ce que vous voyez une erreur dans mon algo ou est-ce que c'est plutôt la façon dont je l'ai mis en Matlab qui cloche ?

Merci beaucoup pour votre aide,

Cécile

**pseudocode** · 06/02/2008, 13h58

Envoyé par Hew

Est-ce que vous voyez une erreur dans mon algo

Non. C'est ce que je fais d'habitude: Décomposition/Fusion

ou est-ce que c'est plutôt la façon dont je l'ai mis en Matlab qui cloche ?

aucune idée...

mes résultats sont nazes

C'est à dire ? Tu peux nous poster une image ou nous en dire un peu plus ?

**Hew** · 06/02/2008, 16h17

Hello pseudocode !

Merci pour la réponse. Je joins une image :
L'image originale est en haut à gauche, après je complète l'image pour faire un carré de puissance de 2.
Les petits carrés c'est le résultat de la segmentation. Pas top non ?

Ce qui m'épate surtout c'est qu'on dirait qu'il y a des directions privilégiées... J'ai l'impression que je rate plein de carrés avec mon algo.

A+

**pseudocode** · 06/02/2008, 16h49

Envoyé par Hew

L'image originale est en haut à gauche, après je complète l'image pour faire un carré de puissance de 2.
Les petits carrés c'est le résultat de la segmentation. Pas top non ?

A priori ton image est le résultat final de la segmentation...

Il faudrait voir une image uniquement du "split", car a mon avis c'est dans le "merge" qu'il doit y avoir un probleme.

**Hew** · 06/02/2008, 17h49

Oups j'ai oublié de dire que je n'ai pas terminé le merge

Ca c'est juste le résultat du split...

**pseudocode** · 06/02/2008, 18h03

Envoyé par Hew

Ca c'est juste le résultat du split...

??

Normalement dans le split on n'obtient que des carrés... hors toi tu as des surfaces "en escalier" qui ne devraient pas exister.

**PRomu@ld** · 06/02/2008, 18h34

Idem, ton split a un sérieux problème.

Tu as le code ici ? Parce que j'ai du mal à voir comment tu ne peux pas avoir une subdivision régulière.

**Hew** · 06/02/2008, 18h46

Oui j'ai le code :

Irgbnew c'est mon image RGB (celle où j'ai rajouté des 0 pour avoir une image de la taille d'une puissance de 2)
n c'est la taille de cette image

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
%% Découpe
I=double(Irgbnew);
Q=[1 1 n n];
S=[];
 
while(isempty(Q)==0)
    x1=Q(1,1); y1=Q(1,2);
    tRx=Q(1,3)-1; tRy=Q(1,4)-1;
    x2=x1+tRx ; y2=y1+tRy ; 
    R=I(x1 : x2,y1 : y2, : ); 
 
    if ( max(max(R(:,:,1)))-min(min(R(:,:,1))) > threshold1 ||...
    max(max(R(:,:,2)))-min(min(R(:,:,2))) > threshold1 ||...
    max(max(R(:,:,3)))-min(min(R(:,:,3))) > threshold1 )
        szx=round(tRx/2);
        szy=round(tRy/2);
 
        if ((szx >= taillem) & (szy >= taillem))
            b1x=x1;
            b1y=y1;
 
            b2x=x1;
            b2y=y1+szy;
 
            b3x=x1+szx;
            b3y=y1;
 
            b4x=szx+x1;
            b4y=szy+x1;
 
            Q(1, : )=[];
            Q=[Q ;[b1x b1y szx szy; b2x b2y szx szy; b3x b3y szx szy; b4x b4y szx szy]];
 
        else
            S=[S; [x1 y1 tRx+1 tRy+1]];
            Q(1, : )=[];
        end
 
    else
        Q(1, : )=[];
        S=[S; [x1 y1 tRx+1 tRy+1]];
    end 
end
 
% Fonction d'affichage des blocs
couleur = strvcat('r','y','g','c','b','m','k','w');
[aS,bS]=size(S);
for k=1:aS
      rectangle('Position',[S(k,1),S(k,2),S(k,3),S(k,4)]);
end
axis tight

Je me disais que c'était peut-être un pb dans ma fonction d'affichage, mais je ne crois pas en fait

Je pense que "j'oublie" de découper des régions, mais je ne vois pas pourquoi.

En tous cas merci pour votre aide.

**pseudocode** · 06/02/2008, 19h00

Code matlab :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(...)
if ((szx >= taillem) & (szy >= taillem))
	b1x=x1;
	b1y=y1;

	b2x=x1;
	b2y=y1+szy;

	b3x=x1+szx;
	b3y=y1;

	b4x=szx+x1;
	b4y=szy+x1; <---------- y1 !!!!! 
(...)

**Hew** · 06/02/2008, 19h06

Oh là là merciiiiiiiiiiii !!
Et devine quoi ça marche !!

(bon cette fois j'ai vraiment un pb d'affichage, ou plutôt de classement mais ça c'était fatal avec Matlab et je pense que je devrais y arriver

)

Voilà ce que ça donne !
Encore merci pseudocode ! Quand je pense que j'ai relu ce code plusieurs fois... Bon je vais pouvoir m'attaquer à la suite, je vous tiendrais au courant.

Merci encore !

**pseudocode** · 06/02/2008, 19h15

Envoyé par Hew

(bon cette fois j'ai vraiment un pb d'affichage, ou plutôt de classement mais ça c'était fatal avec Matlab et je pense que je devrais y arriver

)

on dirait que les coordonnées X et Y de l'image sont inversées...

**Hew** · 06/02/2008, 20h55

Hello !

C'est bon je me suis fait aider sur le forum de Matlab, il fallait inverser les coordonnées X et Y de la matrice S pour que l'affichage soit correct.
Bon je révise un exam pour demain et après je m'attaque au problème de fusion, donc à bientôt pour la suite des aventures

A+ et merci encore pour l'aide, vraiment c'est super.

**Hew** · 07/02/2008, 18h23

Bien me revoilà

Je pensais que j'allais réussir toute seule à faire ma fusion, mais non

.
En fait j'ai un peu de mal à voir comment je vais trouver mes régions adjacentes à une région.

Donc pour l'instant le résultat de mon étape de découpe c'est une matrice avec les coordonnées des coins en haut à gauche de chacune de mes régions + la taille de la région.
Ce que j'ai essayé de faire c'est de trier mes réigions par coordonnées x croissantes puis y croissantes, je prends la première région je la compare avec celle qui est en dessous, et si c'est ok je fusionne, j'enlève les deux régions de ma matrice de référence et ainsi de suite jusqu'à avoir vidé la matrice de référence.

Bon ça ne marche pas...
Alors ma question, c'est est-ce que je suis obligée de construire un graphe d'adjacence de régions ? (j'ai vu en parcourant le forum que c'est ce qui se fait pour les problèmes de fusion)
Si oui est-ce que je peux le faire facilement à partir de ma matrice de découpage ? Parce que c'est pas si simple de connaître les régions voisines, si ? Enfin vers la droite et le bas ça va parce que je connais la taille de ma région, mais sinon... Edit : en fait non même pas

Merci beacoup si quelqu'un sait, mais je vais continuer à chercher

A+
Cecile

"Split and Merge" et "croissance de régions

Traitement d'images

Discussions similaires

Partager

Partager