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();
}
} |
[java] Etiquettage de composantes connexes (union-find)
Répondre avec citation
Envoyé par Xav00007
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 ?
. Regarde sur le net s'il n'y a pas un tuto. J'explique en gros le principe
Partager