[image] Watershed (partage des eaux) en niveaux de gris

[pseudocode]

Voici une implémentation Java d'un algorithme personnel de segmentation "watershed" (ligne de partage des eaux) pour les images en niveaux de gris.



Cet algorithme reprend le principe du watershed binaire : l'utilisation d'une liste de pixels à explorer.

Dans le cas des images en niveaux de gris, j'ai utilisé une liste par niveau, soit 256 listes en tout : tableau "explorelist[256]". L'algorithme incrémente progressivement le niveau de l'eau (variable "level" 0->255), et pour chaque niveau explore les pixels stockés dans les listes explorelist[level] à explorelist[level+step]. La variable "step" permet donc d'explorer également les pixels des niveaux voisins, rendant ainsi l'algorithme plus résistant au bruit.

Code java :

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
/**
 * Gray-Level Watershed Segmentation 
 * 
 * @author Xavier Philippeau
 */
public class WatershedGrayLevel {
 
	// original gray-level image
	private int width,height;
	private int[][] image = null;
	private final int GRAYLEVEL = 256;
 
	// region map
	private int[][] rmap = null;
	private int maxid=0;
	private int WATERSHED=-1;
 
	// pixel and list of pixel structure
	class Pixel {
		int x,y,level;
		public Pixel(int x,int y,int l) {
			this.x=x; this.y=y; this.level=l;
		}
	}
	class ListOfPixels extends LinkedList<Pixel> {}
 
	// list of pixels (one per level) to process
	private ListOfPixels[] explorelist;
 
	// offsets of the 8 neighbors 
	private int[] dx8 = new int[] {-1, 0, 1, 1, 1, 0,-1,-1};
	private int[] dy8 = new int[] {-1,-1,-1, 0, 1, 1, 1, 0};
 
	// ---------------------------------------------------
 
	public  WatershedGrayLevel(int[][] image, int width, int height, boolean isBrightOnDark) {
		this.image = image;
		this.width = width;
		this.height = height;
		// negative image if needed
		if (isBrightOnDark)
			for(int y=0;y<height;y++)
				for(int x=0;x<width;x++)
					this.image[x][y]=GRAYLEVEL-1-this.image[x][y];
	}
 
	// ------------------------------------------------------------------------------------
 
	// allocate memory
	private void init() {
		maxid=0;
		this.rmap = new int[this.width][this.height];
		this.explorelist = new ListOfPixels[GRAYLEVEL];
		for(int i=0;i<GRAYLEVEL;i++)
			this.explorelist[i]=new ListOfPixels();
	}
 
	// free memory
	private void clear() {
		this.rmap = null;
		this.explorelist = null;
	}
 
	// ------------------------------------------------------------------------------------
 
	// gray-level watershed algorithm  : return the boolean watershep map
	public boolean[][] process(int step) {
		init();
 
		// flooding level by level
		int level=0,yoffset=0;
		while(level<GRAYLEVEL) {
 
			// extend region by exploring neighbors of known pixels
			while(true) {
				Pixel p = nextPixel(level,step);
				if (p==null) break;
				extend(p);
			}
 
			// find a new seed for this level
			Pixel seed = findSeed(level,yoffset);
			if (seed!=null) {
				// create and assign a new region to this seed
				this.rmap[seed.x][seed.y]=(++maxid);
				yoffset=seed.y;
 
				// add this seed to the list of pixel to explore
				explorelist[level].add(seed);
			} else {
				// no more seed for this level -> next level
				level++;
				yoffset=0;
			}
		}
 
		// build the watershed map
		boolean[][] shedmap = new boolean[this.width][this.height];
		for(int y=0;y<this.height;y++)
			for(int x=0;x<this.width;x++)
				if (this.rmap[x][y]==WATERSHED) shedmap[x][y]=true;
 
		// free memory
		clear();
 
		// return the watershed map
		return shedmap;
	}
 
	// find a seed ( = unassigned pixel ) at the specified level
	private Pixel findSeed(int level,int yoffset) {
		for (int y = yoffset; y < this.height; y++)
			for (int x = 0; x < this.width; x++)
				if (this.image[x][y]==level && this.rmap[x][y]==0)
					return new Pixel(x,y,level);
 
		return null;
	}
 
	// return the next pixel to explore
	private Pixel nextPixel(int level, int step) {
		// return the first pixel found in the explorelist
		for(int i=level;i<level+step && i<GRAYLEVEL;i++) {
			if (!explorelist[i].isEmpty()) 
				return explorelist[i].remove(0);
		}
		return null;
	}
 
	// explore the 8 neighbors of a pixel and set the region
	private void extend(Pixel p) {
		int region=this.rmap[p.x][p.y];
 
		// this pixel is a watershed => cannot extend it 
		if  (region==WATERSHED) return;
 
		// for each neighbor pixel
		for(int k=0;k<8;k++) {
			int xk = p.x+dx8[k];
			int yk = p.y+dy8[k];
			if (xk<0 || xk>=this.width) continue;
			if (yk<0 || yk>=this.height) continue;
 
			// level and region of neighbor
			int vk = this.image[xk][yk];
			int rk = this.rmap[xk][yk];
 
			// neighbor is a watershed => ignore
			if (rk==-1) continue;
 
			// neighbor as no region assigned => set it
			if (rk==0) {
				this.rmap[xk][yk]=region;
				this.explorelist[vk].add(new Pixel(xk,yk,vk));
				continue;
			}
 
			// neighbor is assigned to the same region => nothing to do
			if (rk==region) continue;
 
			// neighbor is assigned to another region => it's a watershed
			this.rmap[xk][yk]=-1;
		}
	}
}

L'appel de cette classe se fait de la manière suivante

Code java :

1
2
3
4
5
6
7
8
9
10
11
12
int[][] image;          // le tableau contenant les valeurs (entre 0 et 255) de l'image 
int width, height;      // les dimension du tableau ci-avant
boolean isBrightOnDark; // "true" si on cherche des objets clairs sur un fond foncé, sinon "false"
 
// création de l'instance
WatershedGrayLevel ws = new WatershedGrayLevel(image,width,height,isBrightOnDark);
 
// appel de l'algorithme
int step; // nombre des niveaux voisins a explorer à chaque remplissage
boolean shed[][] = ws.process(step);
 
// le tableau shed[][] contient "true" si le pixel correspondant est sur une ligne de partage des eaux

[pseudocode]

Il est possible d'utiliser cet algorithme sur une image couleur en créant une image en niveaux de gris représentant la norme du gradient (ou la variance). Il suffit ensuite d'appliquer l'algorithme sur cette image en niveaux de gris:



a gauche : l'image originale
au milieu : la norme du gradient
à droite : les lignes de partage des eaux surimposées sur l'image originale

Un plugin est disponible dans l'application de Millie.

[tkhchkhiche]

je suis interessé par la methode et je voulais savoir comment utiliser la classe WatershedGrayLevel, si vous pouvez me donner un exemple ou quelque chose qui me facilite l'utilisation de cette classe.
merci d'avance

[pseudocode]

Envoyé par tkhchkhiche

je suis interessé par la methode et je voulais savoir comment utiliser la classe WatershedGrayLevel, si vous pouvez me donner un exemple ou quelque chose qui me facilite l'utilisation de cette classe.
merci d'avance

Vu que j'ai donné un exemple d'utilisation dans le post #1, je ne vois pas ce que je peux faire de plus.

[tkhchkhiche]

slt merci pour ta réponse ce que je voulais savoir c ou est ce que je peux récupérer l'image segmentée? et c quoi l'utilité du tableau des boolean shed[][]?
aussi la valeur que doit prendre step pour mieux gérer le bruit?
Si vous pouvez m'expliquer un peu plus.
dsl pour le dérangement

[pseudocode]

Envoyé par tkhchkhiche

slt merci pour ta réponse ce que je voulais savoir c ou est ce que je peux récupérer l'image segmentée?

Nulle part. Il faut la construire soi-même à partir des lignes de partage (tableau shed[][]).

Tu peux aussi récupérer la carte des régions (le tableau rmap[][]). Pour cela il faut supprimer la ligne "this.rmap = null;" dans la méthode clear() afin de conserver les valeurs une fois le calcul effectué.

et c quoi l'utilité du tableau des boolean shed[][]?

Le tableau shed[][] indique la position des lignes de partage. Si le shed[x][y]=true alors le pixel (x,y) est sur la ligne de partage.

Le tableau rmap[][] représente la carte des régions. La valeur de rmap[x][y] indique le numero de région auquel appartient le pixel (x,y). Si cette valeur vaut WATERSHED (-1) alors le pixel est sur la ligne de partage (et donc n'appartient a aucune région).

aussi la valeur que doit prendre step pour mieux gérer le bruit?

Ca dépend de chaque image, en particulier de sa dynamique (nombre de valeurs différentes). Plus la valeur de 'step' est grande, plus des petits bassins voisins vont se retrouver fusionnés en un seul grand bassin.

[tkhchkhiche]

Merci bcp
je vais essayer

[tkhchkhiche]

si tu me permet de vous déranger un peu plus.
j'ai utilisé le code que tu as posté et ça marche a merveille
Je voulais savoir le principe de la méthode, comment elle marche et que fait la fonction process, findseed et nextPixel.
merci d'avance.

[pseudocode]

Envoyé par tkhchkhiche

si tu me permet de vous déranger un peu plus.
j'ai utilisé le code que tu as posté et ça marche a merveille
Je voulais savoir le principe de la méthode, comment elle marche et que fait la fonction process, findseed et nextPixel.
merci d'avance.

Et bien c'est un algo de type watershed.

La méthode "process" est une boucle qui fait monter le niveau de l'eau. A chaque tour de boucle, cette méthode fait successivement 2 tâches :
- étendre les bassins existant (méthodes nextPixel + extend)
- créer des nouveaux bassins (méthodes findSeed)

A la sortie de la boucle, on construit le tableau contenant les lignes de séparation des eaux.

[Pingumaru]

Bonjour,
J'étudie actuellement les algorithmes de segmentation d'image.
Je te remercie car ton code m'a permis de comprendre la notion d'extension de bassin mais cependant je n'ai pas bien compris la partie où tu recherches de nouveaux bassins :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// find a new seed for this level
Pixel seed = findSeed(level,yoffset);
if (seed!=null) {
	// create and assign a new region to this seed
	this.rmap[seed.x][seed.y]=(++maxid);
	yoffset=seed.y;
			
	// add this seed to the list of pixel to explore
	explorelist[level].add(seed);
} else {
	// no more seed for this level -> next level
	level++;
	yoffset=0;
}

1) A chaque level tu ne récupère qu'un nouveau bassin ? Pourquoi ne pas en chercher autant que possible ?
2) Celui-ci ne sera jamais étendu car il appartient à la liste level alors qu'au prochain tour de boucle tu sera sur la liste level + 1 ?

Edit: En fait je n'ai rien dit, j'avais vu une boucle for au lieu d'une boucle while.
Bon travail et merci beaucoup.

[yousssef]

Bonjour,

J'aimerai savoir le principe de la méthode de la ligne de partage des eaux que vous avez implementé( l'algorithme, la documentation, l'auteur de la méthode etc.)
Merci d'avance.

Envoyé par pseudocode

Et bien c'est un algo de type watershed.

La méthode "process" est une boucle qui fait monter le niveau de l'eau. A chaque tour de boucle, cette méthode fait successivement 2 tâches :
- étendre les bassins existant (méthodes nextPixel + extend)
- créer des nouveaux bassins (méthodes findSeed)

A la sortie de la boucle, on construit le tableau contenant les lignes de séparation des eaux.

[pseudocode]

Envoyé par yousssef

Bonjour,

J'aimerai savoir le principe de la méthode de la ligne de partage des eaux que vous avez implementé( l'algorithme, la documentation, l'auteur de la méthode etc.)
Merci d'avance.

Mon document de référence sur le sujet était :

"The Watershed Transform: Definitions, Algorithms and Parallelization Strategies" , Roerdink and Meijster, 2001

[yousssef]

Bonjour,

Merci pour votre réponse c'est très gentil de votre part.
Juste une qustion bête, sur la doc il ya pas mal d'algorithme de la LPE, lequel vous avez implementé?
Merci

Envoyé par Pingumaru

Bonjour,
J'étudie actuellement les algorithmes de segmentation d'image.
Je te remercie car ton code m'a permis de comprendre la notion d'extension de bassin mais cependant je n'ai pas bien compris la partie où tu recherches de nouveaux bassins :

Code :

1) A chaque level tu ne récupère qu'un nouveau bassin ? Pourquoi ne pas en chercher autant que possible ?
2) Celui-ci ne sera jamais étendu car il appartient à la liste level alors qu'au prochain tour de boucle tu sera sur la liste level + 1 ?

Edit: En fait je n'ai rien dit, j'avais vu une boucle for au lieu d'une boucle while.
Bon travail et merci beaucoup.

[pseudocode]

Envoyé par yousssef

Bonjour,

Merci pour votre réponse c'est très gentil de votre part.
Juste une qustion bête, sur la doc il ya pas mal d'algorithme de la LPE, lequel vous avez implementé?
Merci

Je me suis très largement inspiré de l'algorithme de Vincent-Soille. J'y ai apporté les modifications listées dans le premier post (une liste par niveau + exploration sur plusieurs niveaux).

[yousssef]

Merci et Merci beaucoup pour votre réponse. C'est très gentil.
Bien Cordialement à vous.

Envoyé par pseudocode

Je me suis très largement inspiré de l'algorithme de Vincent-Soille. J'y ai apporté les modifications listées dans le premier post (une liste par niveau + exploration sur plusieurs niveaux).

[yousssef]

Bonjour,

En fait, j'ai bien utilisé votre algorithme pour faire la segmentation, et ça donne des résultats nikel. Je vais faire un rapport dessus. j'aimerais savoir quelle est la référence que je dois mettre pour cette méthode? est ce que celle de Vincent et Soille ? sinon je sais pas si vous avez un algorithme un peut détaillé sur votre méthod?

Cordialement.

[pseudocode]

Envoyé par yousssef

En fait, j'ai bien utilisé votre algorithme pour faire la segmentation, et ça donne des résultats nikel. Je vais faire un rapport dessus. j'aimerais savoir quelle est la référence que je dois mettre pour cette méthode? est ce que celle de Vincent et Soille ? sinon je sais pas si vous avez un algorithme un peut détaillé sur votre méthod?

Cordialement.

Oui, c'est la méthode de Watershed par immersion de Vincent & Soille.

Les modifications que j'ai apporté sont mineures. Le but était de réduire la sur-segmentation directement dans l'algorithme d'immersion, au lieu d'utiliser des pré/post traitement comme c'est habituellement le cas.

[yousssef]

Merci pour votre réponse
Au fait l'algorithme de Vincent et Soille prend deux images en entré, une image de gradient et une image de germe sur lesquels la LPE va croitre, mais le votre ne prend que l'image de gradient en entré. De ce fait, est il toujours possible de mettre comme référence celui de Vincent et Soille?
Merci

Envoyé par pseudocode

Oui, c'est la méthode de Watershed par immersion de Vincent & Soille.

Les modifications que j'ai apporté sont mineures. Le but était de réduire la sur-segmentation directement dans l'algorithme d'immersion, au lieu d'utiliser des pré/post traitement comme c'est habituellement le cas.

[pseudocode]

Envoyé par yousssef

Merci pour votre réponse
Au fait l'algorithme de Vincent et Soille prend deux images en entré, une image de gradient et une image de germe sur lesquels la LPE va croitre, mais le votre ne prend que l'image de gradient en entré. De ce fait, est il toujours possible de mettre comme référence celui de Vincent et Soille?
Merci

Je ne me souvenais plus que l'algo de V&S utilisait des seeds fournis par l'utilisateur. Effectivement, ma version n'utilise pas ce principe et remplit automatiquement tous les bassins ( = ajoute les seeds au fur et a mesure du remplissage, quand il reste des pixels isolés ).

Tu peux toujours mettre Luc Vincent et Pierre Soille en référence, puisque la méthode de remplissage est la même.

[yousssef]

Merci pour vos réponses.
Cordialement.

Envoyé par pseudocode

Je ne me souvenais plus que l'algo de V&S utilisait des seeds fournis par l'utilisateur. Effectivement, ma version n'utilise pas ce principe et remplit automatiquement tous les bassins ( = ajoute les seeds au fur et a mesure du remplissage, quand il reste des pixels isolés ).

Tu peux toujours mettre Luc Vincent et Pierre Soille en référence, puisque la méthode de remplissage est la même.