# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  "Split and Merge" et "croissance de rgions

## Flo.

Bonjour,

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

J'ai russi  crire quelque chose de fonctionnel (le merge est rellement difficile  coder !!!).

Il fonctionne sur des images 24 bits (RGB cods sur 8 bits). Je travaille en RGB (peut-tre HLS serait-il prfrable ... enfin c'est pas le problme).

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



```
critere = sqrt&#40;variance&#40;R&#41; *  variance&#40;R&#41; + variance&#40;G&#41; *  variance&#40;G&#41; + variance&#40;B&#41; *  variance&#40;B&#41;&#41;
```

Pour le merge de 2 noeuds, je vrifie que leur valeurs RGB se trouvent bien dans une fenetre parallpipdique RGB paramtrable centre sur un des 2 noeuds :



```

```

Les 30 sont des paramtres indpendants.

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 mmoriss dans une structure me permettant de tout connaitre de leurs proprits.

en fait il y a pas de problme ... juste je me demande quel est l'intrt par rapport  un algo de croissance de rgions ( part le problme du gradient  ::):  , et quel problme !!! ).

Effectivement, on s'aperoit, que si on met une valeur nulle pour le critre d'acceptabilit du split (sur la variance), le split correspond  l'image ( part si on spcifie une taille de split minimale suprieure  10 pixels par exemple (en dessous, c'est casi l'image elle-mme)). Donc le split donne finalement l'identit. Le merge correspond donc ensuite  un algo de croissance de rgions dans lequel on trouve une graine (seed) (la premiere zone issue du split non encore analyse par le merge) puis on tend la rflexion d'un possible regroupement aux voisins etc. Bref !!! un algo classique de croissance de rgions. En fait j'ai quasiment crit le merge (mise en vidence du voisinage  part), comme un algo classique de croissance de rgions. 

Except cas du problme du gradient (le split and merge, au contraire de l'autre,  ne se heurte pas au problme du bruit sur l'image), quels sont les diffrences entre les 2 algos. Car cette exprience me donne plutot l'impression que le split and merge tient plus de pr-traitement pour un algo de croissance de rgions que comme un algo de segmentation  part entire. 

Donc, si quelqu'un peut clairer ma lanterne    ::D:   .

Merci. A+.

Flo.

----------


## 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

----------


## pseudocode

> juste je me demande quel est l'intrt par rapport  un algo de croissance de rgions ( part le problme du gradient  , et quel problme !!! ).


C'est une TRES bonne question a laquelle je n'ai pas de rponse  ::aie:: .

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

----------


## parp1

> 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

> 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 dlicat 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.

Salut,

dsol, je ne peux pas te donner le code ... tout simplement parce que je l'avais dvelopp dans le cadre d'une socit.

Le merge est la partie la plus sioux. Elle consiste  fusionner les rgions voisines qui se "ressemblent" (mme moyenne RGB par exemple).

Dans la throrie, on te parleras de "graphes d'adjacence" pour merger ces rgions-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 grer le merge comme un algo de croissance de rgions.


Pour le split :

PS1 : REGIONSLIST est une liste d'objets "Regions" qui contient la moyenne RGB par exemple de la rgion
PS2 : REGIONSIMAGE est une image de mmes dimensions que l'image source su Split&Merge. Elle reprsentera la segmentation du split.



```

```

On fait ensuite le merge avec un algo de croissance de rgion. L'image source est REGIONSIMAGE. Le critre de croissance est la moyenne RGB dont l'index dans la liste REGIONSLIST est la valeur des pixels de REGIONSIMAGE.

N'hsite pas  demander des claircissements.

A noter qu'il vaut mieux trabailler en HLS  ::D:  . 

Et de manire gnrale, il est malvenu de demander du code (s'il n'est pas dj mis  disposition) sur un forum qui traite d'algorithmie. Si tu veux du code t'as www.koders.com.

A noter que l'intrt du Split&Merge est de ne pas avoir d' priori sur l'image  segmenter. Pour la croissance de rgions, 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'intrt  ce Split&Merge  ::D:   ::D:   ::D:  .

Flo.

----------


## Rafik_2007

merci beaucoup, c'est trs gentil.................j'ai russit  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




> Salut,
> 
> dsol, je ne peux pas te donner le code ... tout simplement parce que je l'avais dvelopp dans le cadre d'une socit.
> 
> Le merge est la partie la plus sioux. Elle consiste  fusionner les rgions voisines qui se "ressemblent" (mme moyenne RGB par exemple).
> 
> Dans la throrie, on te parleras de "graphes d'adjacence" pour merger ces rgions-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 grer le merge comme un algo de croissance de rgions.
> 
> 
> ...

----------


## Hew

Hello !

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

Voici mon algo (mes images sont carrs, de ct en puissance de 2) :



> Initialisation :
> Une matrice Q qui contient les coordonnes du premier point et la taille de l'image.
> Une matrice S qui est vide.
> 
> Itration :
> Tant que Q n'est pas vide
>    > je prends la premire ligne de Q (= coordonnes d'un noeud+taille rgion) et je regarde si la rgion dfinie par cette premire ligne est homogne
>       > si ce n'est pas le cas
>          je dcoupe Q en 4 -> 4 nouveaux noeuds
> ...


Bon je ne suis pas une star en programmation et en algorithmes, mais a donne un rsultat trs loin de ce que j'esprais  :8O:  .
Est-ce que vous voyez une erreur dans mon algo ou est-ce que c'est plutt la faon dont je l'ai mis en Matlab qui cloche ?

Merci beaucoup pour votre aide,

Ccile

----------


## pseudocode

> Est-ce que vous voyez une erreur dans mon algo


Non. C'est ce que je fais d'habitude: Dcomposition/Fusion




> ou est-ce que c'est plutt la faon dont je l'ai mis en Matlab qui cloche ?


aucune ide...  ::aie:: 




> mes rsultats sont nazes


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

----------


## Hew

Hello pseudocode !

Merci pour la rponse. Je joins une image :
L'image originale est en haut  gauche, aprs je complte l'image pour faire un carr de puissance de 2.
Les petits carrs c'est le rsultat de la segmentation. Pas top non ?  :;): 

Ce qui m'pate surtout c'est qu'on dirait qu'il y a des directions privilgies... J'ai l'impression que je rate plein de carrs avec mon algo.

A+

----------


## pseudocode

> L'image originale est en haut  gauche, aprs je complte l'image pour faire un carr de puissance de 2.
> Les petits carrs c'est le rsultat de la segmentation. Pas top non ?


A priori ton image est le rsultat 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

Oups j'ai oubli de dire que je n'ai pas termin le merge  ::oops:: 
Ca c'est juste le rsultat du split...

----------


## pseudocode

> Ca c'est juste le rsultat du split...


 :8O:  ??

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

----------


## PRomu@ld

Idem, ton split a un srieux problme. 

Tu as le code ici ? Parce que j'ai du mal  voir comment tu ne peux pas avoir une subdivision rgulire.

----------


## Hew

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



```

```

Je me disais que c'tait peut-tre un pb dans ma fonction d'affichage, mais je ne crois pas en fait  ::oops:: 
Je pense que "j'oublie" de dcouper des rgions, mais je ne vois pas pourquoi.

En tous cas merci pour votre aide.

----------


## pseudocode

```

```


 ::aie::

----------


## Hew

:8O: 
Oh l l merciiiiiiiiiiii !!
Et devine quoi a marche !!  ::D: 
(bon cette fois j'ai vraiment un pb d'affichage, ou plutt de classement mais a c'tait fatal avec Matlab et je pense que je devrais y arriver  ::P: )

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

> (bon cette fois j'ai vraiment un pb d'affichage, ou plutt de classement mais a c'tait fatal avec Matlab et je pense que je devrais y arriver )


on dirait que les coordonnes X et Y de l'image sont inverses...  :;):

----------


## Hew

Hello !

C'est bon je me suis fait aider sur le forum de Matlab, il fallait inverser les coordonnes X et Y de la matrice S pour que l'affichage soit correct.
Bon je rvise un exam pour demain et aprs je m'attaque au problme de fusion, donc  bientt pour la suite des aventures  :;): 

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

----------


## Hew

Bien me revoil  ::D: 

Je pensais que j'allais russir toute seule  faire ma fusion, mais non  ::oops::  .
En fait j'ai un peu de mal  voir comment je vais trouver mes rgions adjacentes  une rgion. 

Donc pour l'instant le rsultat de mon tape de dcoupe c'est une matrice avec les coordonnes des coins en haut  gauche de chacune de mes rgions + la taille de la rgion.
Ce que j'ai essay de faire c'est de trier mes rigions par coordonnes x croissantes puis y croissantes, je prends la premire rgion je la compare avec celle qui est en dessous, et si c'est ok je fusionne, j'enlve les deux rgions de ma matrice de rfrence et ainsi de suite jusqu' avoir vid la matrice de rfrence.

Bon a ne marche pas...
Alors ma question, c'est est-ce que je suis oblige de construire un graphe d'adjacence de rgions ? (j'ai vu en parcourant le forum que c'est ce qui se fait pour les problmes de fusion)
Si oui est-ce que je peux le faire facilement  partir de ma matrice de dcoupage ? Parce que c'est pas si simple de connatre les rgions voisines, si ? Enfin vers la droite et le bas a va parce que je connais la taille de ma rgion, mais sinon...  Edit : en fait non mme pas   ::P: 

Merci beacoup si quelqu'un sait, mais je vais continuer  chercher  :;): 

A+ 
Cecile

----------


## pseudocode

> Alors ma question, c'est est-ce que je suis oblige de construire un graphe d'adjacence de rgions ? (j'ai vu en parcourant le forum que c'est ce qui se fait pour les problmes de fusion)


Non tu n'es pas "oblige". C'est juste que le plus performant c'est de construire le graphe d'adjacence, mais on peut s'en passer. 

Pour chaque carrs tu as besoin de 5 informations: x, y, hauteur, largeur, regionid.

"regionid" est le numro qui identifiera la rgion  laquelle appartient le carr. Au dpart, avant la fusion, chaque carr a un "regionid" diffrent. Au fur et  mesure de la fusion, plusieurs carrs auront le mme.

Comme expliqu (tant bien que mal) dans mon tutoriel, tu prends un carr "non examin" (donc ta liste S) et tu testes ses voisins "non examins". S'ils sont homognes tu leurs donne le "regionid" du carr initial. Une fois tous les voisins tests, le carr initial est considr "examin" (donc tu le retires de S)

Pour chercher tous les voisins d'un carr "C", il faut parcourir TOUTE la liste S et trouver les carrs "V" tels que V et C soient adjacents, c'est a dire:

- si V adjacent a droite de C alors: C.x+C.largeur+1=V.x ET C.y<=V.y ET C.y+C.hauteur>=V.y+V.hauteur
- si V adjacent a gauche de C alors: (...)
- si V adjacent en haut de C alors: (...)
- si V adjacent en bas de C alors: (...)

Tu comprends pourquoi on prfre construire une fois pour toute le RAG plutt que de retester a chaque fois toutes la liste S (mme si elle diminue au fur et a mesure).  ::P:

----------


## Hew

Ok je comprends mieux l'intrt, merci !  :;): 
Ca va le faire.

----------


## Hew

Hello, je reviens  ::oops:: 
En fait je ne suis pas sure de comprendre comment a marche un RAG... J'ai regard sur un cours qui avait t mis en lien dans une discussion prcdente du forum ("fusion en imagerie" elle s'appelle je crois), mais je ne comprends pas concrtement comment je vais pouvoir crer mon graphe et m'en servir.

Je fais un blocage ( ::lol:: ) parce que quand je vais fusionner des petits carrs avec des grands je n'aurais plus de carrs, donc je ne sais pas comment reprsenter ces rgions  ::aie::  .
Est-ce que quelqu'un peut m'expliquer comment je peux m'en sortir ? Je cale compltement l en fait  ::?: 

Merci beaucoup !

----------


## pseudocode

> Je fais un blocage () parce que quand je vais fusionner des petits carrs avec des grands je n'aurais plus de carrs, donc je ne sais pas comment reprsenter ces rgions  .


Le RAG est le graphe d'adjacence des *REGIONS*, et pas le graphe d'adjacence des carrs. Il faut donc bien apprhender le concept de "rgion". 

Le fait que les rgions soient composes de un ou plusieurs carrs est un dtail qui ne nous intresse pas (ou trs peu) dans le RAG.

Ce qui nous intresse en particulier c'est que:

1. une rgion Ri peut avoir zro, une ou plusieurs rgions adjacentes (voisines)



```

```

2. on ne peut merger que deux rgions voisines

3. quand on merge deux rgion (Ri+Rj), alors on n'en garde qu'une et que les rgions voisines de l'autre deviennent des rgions voisines de la premire.



```

```

L'algorithme du merge ne manipule que des rgions donc il n'a besoin que du RAG. 

Mais comme, au final, ce qui nous intresse c'est de faire de la segmentation sur des pixels (= des carrs), on va ajouter une information d'association pour savoir quels carrs appartiennent  quelles rgions.

Cette information d'association peut tre 
- un "entier", reprsentant le numro de la rgion, stocke dans chaque carr
- une liste de carrs, stocke dans chaque rgion
- une liste autonome de rgion+carrs (= "table de liaison" en langage BdD)

Il faut bien sr maintenir cette information d'association  jour au fur et  mesure du merge: Quand on merge R1=(R1+R2), tous les carrs associs  R2 sont r-associs  R1.

----------


## Hew

Ok merci pseudocode, c'est dj beaucoup plus clair comme a.
Je vais essayer d'implmenter a tout de suite.

----------


## Hew

Hello !
Voil aprs quelques semaines d'efforts a marche  ::D:  (et comme c'est la premire fois que je fais un truc comme a je suis bien contente  :;):  ).

Par contre, je pense qu'il y a quelques passages que je pourrais amliorer, alors si quelqu'un a une ide : 

*La dcoupe*
Ca a marche bien, donc ok.
A la fin je rcupre un tableau S avec la coordonne du coin en haut  gauche de chacune de mes rgions, la taille de la rgion et le label de la rgion.

*La cration du RAG*
Finalement j'ai fini par en faire un...
Je pense que la faon dont je cherches mes voisines n'est pas terrible, voici comment je fais :


```

```

Je pense que ce n'est pas terrible comme construction :
- parce qu'avec les coins, je ne suis pas sre de rcuprer toutes les rgions et seulement elles...
- parce que a fait beaucoup de boucles (et qu'on m'a toujours dit que moins on en faisait mieux c'tait)

*La fusion*
Comment je fais :


```

```

*La fin*
Ca c'est l'tape o je donne la mme couleur  chacune de mes classes, et c'est la pire (quatre boucles for dont trois imbriques  :8O:  ). En fait je pense qu'il y a moyen de s'en passer.

Pris comme a a marche, mais c'est pas entirement satisfaisant : en fait je rcupre plus de classes de couleurs que je ne le voudrais (genre 160 l o j'en attends 6...). C'est peut-tre juste un problme de critre sur la fusion. 
Donc si quelqu'un est motiv pour m'aider  amliorer mon programme il est le bienvenu  ::D:  . En tous cas je vais continuer, mais comme a marche, merci pour l'aide, pour les liens (j'ai lu plein de trucs du coup  ::lol::  ) et pour les corrections !

Ccile

----------


## pseudocode

> *La cration du RAG*


C'est plus simple et performant de construire le RAG au moment du split. Quand on dcooupe un carr en 4, c'est assez simple de mettre a jour le RAG.




> *La fusion*


Je ne vois pas trop comment optimiser ce que tu as dj fait





> *La fin*
> Ca c'est l'tape o je donne la mme couleur  chacune de mes classes, et c'est la pire (quatre boucles for dont trois imbriques  ). En fait je pense qu'il y a moyen de s'en passer.


Hum... je vois pas pourquoi tu as autant de boucles pour assigner une couleur  un pixel.  ::koi::

----------


## Hew

> C'est plus simple et performant de construire le RAG au moment du split. Quand on dcooupe un carr en 4, c'est assez simple de mettre a jour le RAG.


Plus performant je te crois, mais plus simple...  ::aie:: 

Par contre j'ai chang quelques trucs :
- dans ma division, quand une rgion est homogne, je donne la valeur moyenne aux pixels de la rgion
- dans ma fusion, je regarde d'abord les rgions les plus grosses
Ca a l'air un peu mieux, par contre j'ai toujours beaucoup trop de classes et surtout j'ai des "trous" dans mon image  :8O: .

Enfin l j'ai trouv un bug : ma fonction ne fonctionne pas avec toutes les valeurs de seuil sur les critres d'homognits  ::aie::  .
Donc je vais d'abord m'occuper de a.




> Hum... je vois pas pourquoi tu as autant de boucles pour assigner une couleur  un pixel.


Je vais y arriver  :;):  Merci en tous cas !

----------


## ImagingAllthe

splimerge.m

http://read.pudn.com/downloads112/so...tmerge.m__.htm



```

```

----------


## ImagingAllthe

je n'ai pas tester pour l'instant ce code.

----------

