[java] Etiquettage de composantes connexes (union-find)

[pseudocode]

Une implémentation de l'algorithme union-find en Java appliqué à l'etiquettage des composantes connexes.


en haut: l'image d'origine en niveaux de gris
en bas: l'image coloriée avec les 19 étiquettes trouvées

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
 
import java.util.ArrayList;
import java.util.List;
 
/**
 * Connected Component Labeling (union-find)
 * 
 * @author Xavier Philippeau
 *
 */
public class CCLabeling {
 
	// original component image/array
	private int[][] image;
	private int width,height;
 
	// graph of nodes
	private int[] roots = null;
	private final int NOROOT=-1;
 
	/**
	 * @param image image filled with component's id
	 * @param width width of the image
	 * @param height height of the image
	 */
	public CCLabeling (int[][] image, int width, int height) {
		this.image = image;
		this.width = width;
		this.height = height;
		this.roots = new int[width*height];
	}
 
	// find the root of the node at position pos 
	private int find(int pos) {
		while(roots[pos]!=pos) pos=roots[pos];
		return pos;
	}
 
	// union of the 2 path formed by the 2 roots
	private int union(int root0, int root1) {
		if (root0==root1) return root0;
		if (root0==NOROOT) return root1;
		if (root1==NOROOT) return root0;
		if (root0<root1) {
			roots[root1]=root0;
			return root0;
		} else {
			roots[root0]=root1;
			return root1;
		}
	}
 
	// set the root of the node at position pos  
	private void add(int pos, int root) {
		if (root==NOROOT) 
			roots[pos]=pos;
		else 
			roots[pos]=root;
	}
 
	// build the connected component labels array
	private int[][] buildLabelArray() {
 
		// remove indirections
		for(int pos=0;pos<(width*height);pos++)
			roots[pos] = find(pos);
 
		// relabel the root
		int label=1;
		for(int pos=0;pos<(width*height);pos++)
			if (roots[pos]==pos)
				roots[pos] = label++;
			else
				roots[pos] = roots[roots[pos]];
 
		System.out.println("labels: "+(label-1));
 
		// copy label to new array
		int[][] labels = new int[width][height];
		for(int y=0,pos=0;y<height;y++)
			for(int x=0;x<width;x++,pos++)
				labels[x][y]=roots[pos];
 
		return labels;
	}
 
	/**
	 * @return the connected component labels array
	 */
	public int[][] compute() {
		int root;
		for(int y=0,pos=0;y<height;y++) {
			for(int x=0;x<width;x++,pos++) {
				root = NOROOT;
 
				if ( (x>0) && (image[x-1][y]==image[x][y]) )
					root = union( find(pos-1) , root);
 
				if ( (x>0 && y>0) && (image[x-1][y-1]==image[x][y]) )
					root = union( find(pos-1-width) , root);
 
				if ( (y>0) && (image[x][y-1]==image[x][y]) )
					root = union( find(pos-width) , root);
 
				if ( (x<(width-1) && y>0) && (image[x+1][y-1]==image[x][y]) )
					root = union( find(pos+1-width) , root);
 
				add( pos, root );
			}
		}
 
		return buildLabelArray();
	}
}

[pseudocode]

Portage en C, suite à une discussion dans le forum:

Code C :

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
 
long *CCroots = NULL;
long CC_NOROOT = -1;
 
void CCinit(int W, int H) {
	CCroots = (long*) malloc(W*H*sizeof(long));
	long i;
}
 
void CCclear() {
	if (CCroots!=NULL) {
		free(CCroots);
		CCroots=NULL;
	}
}
 
long CCfind(long pos) {
	while(CCroots[pos]!=pos) pos=CCroots[pos];
	return pos;
}
 
long CCunion(long root0, long root1) {
	if (root0==root1) return root0;
	if (root0==CC_NOROOT) return root1;
	if (root1==CC_NOROOT) return root0;
	if (root0<root1) {
		CCroots[root1]=root0;
		return root0;
	} else {
		CCroots[root0]=root1;
		return root1;
	}
}
 
long CCadd(long pos, long root) {
	if (root==CC_NOROOT)
		CCroots[pos]=pos;
	else
		CCroots[pos]=root;
	return CCroots[pos];
}
 
void CClabel(int* image, int W, int H) {
	long x,y,root,pos;
 
	pos=0;
	for(y=0;y<H;y++) {
		for(x=0;x<W;x++,pos++) {
			root=CC_NOROOT;
 
			if ( (x>0) && (image[pos-1]==image[pos]) )
				root = CCunion( CCfind(pos-1) , root);
 
			if ( (x>0 && y>0) && (image[pos-1-W]==image[pos]) )
				root = CCunion( CCfind(pos-1-W) , root);
 
			if ( (y>0) && (image[pos-W]==image[pos]) )
				root = CCunion( CCfind(pos-W) , root);
 
			if ( (x<(W-1) && y>0) && (image[pos+1-W]==image[pos]) )
				root = CCunion( CCfind(pos+1-W) , root);
 
			root = CCadd( pos, root );
		}
	}
 
	// remove indirection
	for(pos=0;pos<(W*H);pos++)
		CCroots[pos] = CCfind(pos);
 
	// relabel
	long label=0;
	for(pos=0;pos<(W*H);pos++)
		if (CCroots[pos]==pos)
			CCroots[pos] = label++;
		else
			CCroots[pos] = CCroots[CCroots[pos]];
}

Exemple d'utilisation:

Code C :

1
2
3
4
5
6
7
8
 
int W=123,H=456;
int image[456][123] = /* ... */;
 
CCinit(W,H);
CClabel((int*)image,W,H);
// ** ajouter ici votre traitement du tableau CCroots
CCclear();

[Xav00007]

Bonjour,

J'essaye de labeliser une image binaire, mais je ne comprends pas exactement comment faire pour utiliser les fonctions proposées.
Quelqu'un pourrait m'aider ?

Merci beaucoup,

[pseudocode]

Envoyé par Xav00007

Bonjour,

J'essaye de labeliser une image binaire, mais je ne comprends pas exactement comment faire pour utiliser les fonctions proposées.
Quelqu'un pourrait m'aider ?

Merci beaucoup,

Bah, dans l'implémentation Java il n'y a qu'une seule méthode publique et dans l'implémentation C il y a un exemple d'utilisation. Quel est ton problème exactement ?

[Xav00007]

On définit une matrice 2D pour l'image, mais la fonction prends en argument un int*qui est un vecteur 1D.

Ensuite, comment utiliser le résultat de la fonction ?

[pseudocode]

Envoyé par Xav00007

On définit une matrice 2D pour l'image, mais la fonction prends en argument un int*qui est un vecteur 1D.

Ah. Oui c'est un peu sale mais c'est un avantage du C : un tableau 2D est stocké linéairement en mémoire (donc sous forme de tableau 1D).

"int t2d[456][123]" est équivalent en mémoire à "int t1d[456*123]" et donc l'élément "t2d[y][x]" est équivalent à "t1d[y*123+x]".

(edit : je viens de changer l'ordre des dimensions W,H dans l'exemple pour être cohérent avec cette explication. En fait l'ordre n'a pas d'importance dans cet algo car ca revient a faire tourner l'image de 90°, ce qui ne change pas les composantes)

Ensuite, comment utiliser le résultat de la fonction ?

Le tableau "CCroots" est un tableau de meme taille que l'image. Chaque élément de ce tableau indique le numero de composante pour le pixel correspondant de l'image.

[Xav00007]

Merci pour ces indications, ça marche nickel : -)

Est-ce que tu pourrais m'expliquer brièvement les différentes fonction, et l'idée générale de cette labélisation ?

J'aimerai ajouter quelques fonctionnalités, mais pour cela, il faut que je comprenne mieux les différentes parties.

Merci beaucoup,

[pseudocode]

Envoyé par Xav00007

Est-ce que tu pourrais m'expliquer brièvement les différentes fonction, et l'idée générale de cette labélisation ?

Hum... C'est pas évident d'expliquer pourtant c'est simple . Regarde sur le net s'il n'y a pas un tuto. J'explique en gros le principe

On parcourt chaque pixel (gauche->droite, haut->bas). Pour chaque pixel on regarde les 4 pixels du voisinage qu'on a deja parcouru (NordEst, Nord, NordOuest, Ouest) et on regarde si les pixels sont connectés (= ils ont la meme valeur).

- Pour chaque voisin connecté, on cherche la composante a laquelle il appartient (FIND). A ce stade, on a donc entre 0 et 4 composantes autour du pixel courant, et potentiellement certaines composantes sont les mêmes.

cas 1 : Le pixel courant est connecté a 0 composante => c'est le départ d'une nouvelle composante
cas 2 : Le pixel courant est connecté a une seule composante => il appartient a cette composante
cas 3 : Le pixel courant est connecté différentes composantes => il relie les composantes entre elles (UNION)

L'important dans cette algo est la manière dont on represente la liaison entre un pixel et une composante. On utilise le tableau CCroots (= tableau d'indirection, un peu comme une liste chainée) : chaque case du tableau contient l'indice d'une autre case à laquelle le pixel est lié.

exemple:
- CCroots[256]=140 le pixel n°256 est relié au pixel 140 (ils ont la mm composante)
- CCroots[140]=120 le pixel n°140 est relié au pixel 120
- CCroots[120]=120 le pixel n°120 est relié a lui même. C'est le point de départ de la composante, qu'on appelle la racine

Donc pour trouver la "racine" d'une composante il suffit de faire une boucle "tant que" l'indice change. (c'est le code de la fonction FIND)

Pour la fonction UNION entre 2 composantes, on trouve les 2 racines et ont fait pointer l'une sur l'autre.

[Xav00007]

Merci pour ces explications :-).

Comment se passe la 'relabelisation' (dernière boucle for)?

[pseudocode]

Envoyé par Xav00007

Merci pour ces explications :-).

Comment se passe la 'relabelisation' (dernière boucle for)?

ca se passe en 2 temps.

Première étape : on retire les indirections, c'est a dire que chaque case du tableau CCroots pointe directement sur la racine (sans faire de "rebond" intermédiaire). A ce stade, le tableau CCroots contient un numero unique de composante pour chaque pixel. Mais ce numéro n'est pas un un numéro d'ordre (1, 2, 3, ...), c'est juste l'indice du pixel "racine".

Deuxième étape : on parcours le tableau d'indice et on remplace le numéro des racines par un numero d'ordre. On doit également "propager" ce numéro d'ordre aux autres cases qui pointent sur la racine. On peut faire cela en une seule passe car on est sûr de toujours changer une racine avant de changer les cases qui pointent sur la racine.

[Xav00007]

Nickel, j'ai réussi à faire ce que je voulais...

Merci beaucoup pour ton aide!

[jojo_ol76]

Bonsoir,

Puis je l'avoir en langage matlab?

Car je n'ai pas réussi à le transcrire.

[chuck00]

Bonjour,

Il existe la fonction bwlabel sous matlab qui permet de faire exactement la meme chose. Je te laisse regarder la doc officielle pour plus de details.
Je te conseille de regarder regionsprops aussi qui va de paire avec bwlabel et qui te permet de ressortir automatiquement pleins d'infos utiles sur les regions ettiquetées (nombre de pixel, centre de gravité, etc etc ...)

et super le code de labellisation en C ;-) . je vais surement m'en servir !


++

PS : special thanks to Xavier Philippeau ! ça fait déjà deux fois que tu m'aide! cf:le pdf sur les filtres et maintenant le code de labellisation en C!

[Anis99]

Bns;
donnez moi un exemple comment utilisé cette class (java)?
cordialment

[pseudocode]

Envoyé par Anis99

Bns;
donnez moi un exemple comment utilisé cette class (java)?
cordialment

Comme je l'ai dit au post #4, il n'y a qu'une seule méthode publique pour cette classe (et un seul constructeur). Ca ne laisse pas trop de doute sur son utilisation.

[Anis99]

Envoyé par pseudocode

Comme je l'ai dit au post #4, il n'y a qu'une seule méthode publique pour cette classe (et un seul constructeur). Ca ne laisse pas trop de doute sur son utilisation.

ok mais mon probleme est que mon image est sur un bufferedimage
exemple

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Segmentation {
	public static void main(String[] args) {
		try{
		BufferedImage img = ImageIO.read(new File("01.jpg")); 
				
		BufferedImage image_en_eniveau_gris = niveau_de_gris(img);
		BufferedImage image_binary = binary(img, auto_Threshold(img));
		
		ImageIO.write(image_en_eniveau_gris, "bmp",new File("01_en_Niveau_de_gris.jpg"));
		ImageIO.write(image_binary, "bmp",new File("01_binary.jpg"));
		
			}catch (Exception e)
			   {	
			   System.out.println("ERREUR!==> "+e.getMessage()+" \n");
			   }
			}
}

dite moi comment je vais appliqué votre class CCLabeling a cette classe

[pseudocode]

Envoyé par Anis99

ok mais mon probleme est que mon image est sur un bufferedimage.

dite moi comment je vais appliqué votre class CCLabeling a cette classe

Il faut convertir le bufferedimage en un tableau int[][]. Chaque case du tableau doit contenir une valeur de pixel (intensité, niveau de gris, composante, ...).

exemple:

Code java :

1
2
3
4
5
6
7
8
9
10
11
public static int[][] BufferedImageToArray(BufferedImage bi) {
	int W = bi.getWidth(), H=bi.getHeight();
	int[][] arr = new int[W][H];
	for(int y=0;y<H;y++)
		for(int x=0;x<W;x++) {
			int rgb = bi.getRGB(x, y); // codage rgb du pixel
			int value = (rgb>>8)&0xFF; // on prend la composante VERTE
			arr[x][y] = value;
		}
	return arr;
}

[Anis99]

Bonsoir,
je vous demande de m'orienter pour que je puisse extraire les composante connexe apres avoir fais un etiquetage.

[pseudocode]

Envoyé par Anis99

Bonsoir,
je vous demande de m'orienter pour que je puisse extraire les composante connexe apres avoir fais un etiquetage.

la méthode renvoie un tableau d'entier (int[][]). Chaque case du tableau correspond a un pixel de l'image. La valeur de la case indique le numero de la composante connexe a laquelle appartient le pixel.

Si on veut tous les pixels de la première composante, on parcourt tous le tableau pour trouver les cases qui ont la valeur 1. Les coordonnées de la case sont les coordonnées du pixel.

[Anis99]

Envoyé par pseudocode

la méthode renvoie un tableau d'entier (int[][]). Chaque case du tableau correspond a un pixel de l'image. La valeur de la case indique le numero de la composante connexe a laquelle appartient le pixel.

Si on veut tous les pixels de la première composante, on parcourt tous le tableau pour trouver les cases qui ont la valeur 1. Les coordonnées de la case sont les coordonnées du pixel.

Bonsoir,
je ne sais pas si j'ai fais tout le necessaire pour implementer un code java pour l'extraction des composantes connexes! mais j'ai pas pu
alors la je vous demande de m'aider d'avantage car je n'arrive pas a implementé le code pour extraire les composantes connexes.