Discussion :

[pseudocode]

Voici une implémentation du calcul du squelette d'une image par la méthode décrite dans ce document pdf.

La méthode consiste a faire des erosions multiples jusqu'a atteindre le squelette. Ce squelette peut etre utilisé, par exemple, pour la reconnaissance de formes (OCR, ...)

(EDIT: version améliorée au post #4)


A gauche: l'image originale
A droite: le squelette obtenu.

Code java :

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
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
import ij.IJ;
import ij.ImagePlus;
import ij.gui.GenericDialog;
import ij.plugin.filter.PlugInFilter;
import ij.process.ByteProcessor;
import ij.process.ImageProcessor;
 
 
/**
 * Skeleton Filter
 * 
 * @author Xavier Philippeau (from work of Dr. Chai Quek)
 *
 */
public class Skeleton_ implements PlugInFilter {
 
	// neighbours order
	private int[] dx = new int[] {-1, 0, 1,1,1,0,-1,-1};
	private int[] dy = new int[] {-1,-1,-1,0,1,1, 1, 0};
 
	// Smoothing pattern
	private int[] pattern1={-1,1,0,1,0,0,0,0};
	private int[] pattern2={0,1,0,1,-1,0,0,0};
	private int[] pattern3={0,0,-1,1,0,1,0,0};
	private int[] pattern4={0,0,0,1,0,1,-1,0};
	private int[] pattern5={0,0,0,0,-1,1,0,1};
	private int[] pattern6={-1,0,0,0,0,1,0,1};
	private int[] pattern7={0,1,0,0,0,0,-1,1};
	private int[] pattern8={0,1,-1,0,0,0,0,1};
 
	// filter configuration
	private boolean blackbackground = true;
	private int threshold = 0;
 
	//	 About...
	private void showAbout() {
		IJ.showMessage("Skeleton...","Skeleton Filter by Pseudocode");
	}
 
	public int setup(String arg, ImagePlus imp) {
 
		// about...
		if (arg.equals("about")) {
			showAbout(); 
			return DONE;
		}
 
		// else...
		if (imp==null) return DONE;
 
		// Configuration dialog.
		GenericDialog gd = new GenericDialog("Parameters");
		gd.addChoice("Background color", new String[]{"Black","White"}, "Black");
		gd.addNumericField("Black/White threshold",128,0);
 
		while(true) {
			gd.showDialog();
			if ( gd.wasCanceled() )	return DONE;
 
			this.blackbackground  =  gd.getNextChoice().equals("Black")?true:false;
			this.threshold  =  (int)gd.getNextNumber();
 
			if (this.threshold<=0) continue;
			if (this.threshold>=255) continue;
			break;
		}
		gd.dispose();
 
		return PlugInFilter.DOES_8G;
	}
 
	public void run(ImageProcessor ip) {
 
		// ImageProcessor -> ByteProcessor conversion
		ByteProcessor bp = new ByteProcessor(ip.getWidth(),ip.getHeight());
		for (int y = 0; y < ip.getHeight(); y++) {
			for (int x = 0; x < ip.getWidth(); x++) {
				bp.set(x,y,ip.getPixel(x,y));
			}
		}
 
		// filter
		ByteProcessor newbp = filter( bp );
 
		// ByteProcessor -> ImageProcessor conversion
		ImageProcessor out = new ByteProcessor(ip.getWidth(),ip.getHeight());
		for (int y = 0; y < ip.getHeight(); y++) {
			for (int x = 0; x < ip.getWidth(); x++) {
				out.set(x,y,newbp.get(x,y));
			}
		}
		ImagePlus newImg = new ImagePlus("Skeleton", out);
		newImg.show();
 
	}
 
	// -------------------------------------------------------------------------
 
	// Binary value of the gray scale image (0..255) -> (0,1)
	private int ChannelValue(ByteProcessor c,int x,int y) {
		if (c.getPixel(x,y)<this.threshold) return 0;
		return 1;
	}
 
	// Neighbourhood
	private int neighbourhood(ByteProcessor c,int x,int y) {
		int neighbourhood=0;
 
		for(int i=0;i<8;i++)
			neighbourhood += ChannelValue(c,x+dx[i],y+dy[i]);
 
		return neighbourhood;
	}
 
	// Transitions Count
	private int transitions(ByteProcessor c,int x,int y) {
		int Trans=0;
 
		for(int i=0;i<8;i++) {
			int pc = ChannelValue(c,x+dx[i],y+dy[i]);
			int pn = ChannelValue(c,x+dx[(i+1)%8],y+dy[(i+1)%8]);
			if ((pc==0) && (pn==1)) Trans++;
		}
 
		return Trans;
	}
 
	// Match a pattern
	private boolean matchPattern(ByteProcessor c,int x,int y,int[] pattern) {
		for(int i=0;i<8;i++) {
			if (pattern[i]==-1) continue;
			int v = ChannelValue(c,x+dx[i],y+dy[i]);
			if (pattern[i]!=v) return false;
		}
		return true;
	}
 
    // Match one of the 8 patterns
	private boolean matchOneOfPatterns(ByteProcessor c,int x,int y) {
		if (matchPattern(c,x,y,pattern1)) return true;
		if (matchPattern(c,x,y,pattern2)) return true;
		if (matchPattern(c,x,y,pattern3)) return true;
		if (matchPattern(c,x,y,pattern4)) return true;
		if (matchPattern(c,x,y,pattern5)) return true;
		if (matchPattern(c,x,y,pattern6)) return true;
		if (matchPattern(c,x,y,pattern7)) return true;
		if (matchPattern(c,x,y,pattern8)) return true;
		return false;
	}
 
	private ByteProcessor thinning(ByteProcessor original) {
		int width = original.getWidth();
		int height = original.getHeight();
 
		// previous image buffer
		ByteProcessor c = new ByteProcessor(width,height);
		for(int y=0;y<height;y++)
			for(int x=0;x<width;x++)
				if (this.blackbackground)
					c.set(x,y,255*ChannelValue(original,x,y));
				else
					c.set(x,y,255-255*ChannelValue(original,x,y));
 
		// new image buffer
		ByteProcessor c2  = new ByteProcessor(width,height);
 
		// loop until idempotence
		for(int loop=0;;loop++) {
 
			int pixelchangecount=0;
 
			// copy previous image in new image
			for(int y=0;y<height;y++)
				for(int x=0;x<width;x++) 
					c2.set(x,y,c.get(x,y));
 
			// for each pixel
			for(int y=1;y<height-1;y++) {
 
				for(int x=1;x<width-1;x++) {
 
					// pixel value
					int v = ChannelValue(c,x,y);
 
					// pixel not set -> next
					if (v==0) continue;
 
					// is a boundary ?
					int previousNeighbourhood = neighbourhood(c,x,y);
					if (previousNeighbourhood==8) continue;
 
					// is an extremity ?
					int currentNeighbourhood = neighbourhood(c2,x,y);
					if (currentNeighbourhood<=1) continue;
					if (currentNeighbourhood>=6) continue;
 
					// is a connection ?
					int transitionsCount = transitions(c2,x,y);
 
					// Addition to the original algorithm:
					// Preservation of the "Y curve" near the edges 
					if (transitionsCount==1 && previousNeighbourhood<=3) continue;
 
					if (transitionsCount==1) {
						pixelchangecount++;
						c2.set(x,y,0);
						continue;
					}
 
					// is a deletable pixel ?
					boolean matchOne = matchOneOfPatterns(c2,x,y);
					if (matchOne) {
						pixelchangecount++;
						c2.set(x,y,0);
						continue;
					}
				}
			}
 
			// no change -> return result
			if (pixelchangecount==0) return c;
 
			// swap image buffers, then loop.
			ByteProcessor tmp = c;
			c=c2;
			c2=tmp;
		}
	}
 
	// Return the skeleton
	public ByteProcessor filter(ByteProcessor bp) {
		ByteProcessor skel = thinning(bp);
		return skel;
	}
}

[kruskal21]

Bonjour,
J’ai testé ce programme en c++ ca marche bien
La question c'est comment éliminer les petits segments ajoutés dans les extrémités pour avoir des caractères comme elles sont

Ensuite je vais détecter les segments à partir du squelette
Par exemples pour la lettre A comment détecter les segments (/, _ et \)

[pseudocode]

Non, on ne peut pas retirer les fourches en Y. Elles font partie du squelette et permettent de détecter les extrémités des formes.

Comme je l'ai indiqué sur ton thread dans le forum de discussion (vive le multi-post), si tu veux détecter des points d'intérêts sur le squelette il faut détecter les "croisements", les "inflexions" et les "extrémités" des lignes du squelette.

Pour cela, on peut analyser les 8 voisins de chaque pixel du squelette et compter le nombre de transitions 0->1 (voir la fonction transitions() dans le code ci-dessus)

Code :

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

1
2
3
4
5
6
7
-------
|a|b|c|
-------
|h|X|d|  voisins de X (sens horaire): a,b,c,d,e,f,g,h
------- 
|g|f|e| 
-------

- si le nombre de transitions est 1, alors on est a une extrémité.

Code :

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

1
2
3
4
5
6
7
-------
|0|1|0|
-------
|0|X|0|  voisins de X (sens horaire): 0,1,0,0,0,0,0,0
-------                                 ^
|0|0|0|  1 transition
-------

- si le nombre de transitions est >=3, alors on est a un croisement.

Code :

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

1
2
3
4
5
6
7
-------
|0|1|0|
-------
|0|X|1|  voisins de X (sens horaire): 0,1,0,1,0,0,1,0
-------                                 ^   ^     ^
|1|0|0|  3 transitions
-------

- si le nombre de transitions est 2, alors on est au milieu d'une continuité. il faut alors regarder la position des pixels de transition pour connaître l'angle d'inflexion.

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
-------
|1|0|0|
-------
|0|X|0|  voisins de X (sens horaire): 1,0,0,0,0,1,0,0
-------                               ^         ^
|0|1|0|  2 transitions
-------
 
positions des transitions: 1 et 6
Écart entre les positions: 6-1 = 5
Correspondance en angle:
 
Écart | Angle
--------------
 1,7  |  45°
 2,6  |  90° (angle droit)
 3,5  |  135°
  4   |  180° (angle plat)

Pour faire une vectorisation (= transformer le squelette en segments), tu recherches uniquement les "extrémités" et les "croisements" et tu les relies entre eux en passant par les "inflexions".

NB: Si tu ne veux pas des fourches en Y, ne relie pas de segment aux "extrémités"


Image haut: squelette
Image milieu: squelette + points d'intérêts (blanc=extrémité, rouge=croisement, vert=inflexion)
Image bas: segments reliant les points d'intérêts

[pseudocode]

Voici une version légèrerment modifiée de l'algorithme:
- consommation mémoire réduite en modifiant directement le tableau passé en parametre (in-place)
- approximation plus précise (conservation des orientations dans les structures en H ou en X)

Code java :

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
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
 
/**
 * Skeleton (v2)
 * 
 * Original algorithm : Dr. Chai Quek
 * Modified algorithm : Xavier Philippeau 
 * 
 * @author Xavier Philippeau (based on work of Dr. Chai Quek)
 * 
 */
public class Skeleton {
 
	// Smoothing pattern
	private byte[] pattern1={-1,1,0,1,0,0,0,0};
	private byte[] pattern2={0,1,0,1,-1,0,0,0};
	private byte[] pattern3={0,0,-1,1,0,1,0,0};
	private byte[] pattern4={0,0,0,1,0,1,-1,0};
	private byte[] pattern5={0,0,0,0,-1,1,0,1};
	private byte[] pattern6={-1,0,0,0,0,1,0,1};
	private byte[] pattern7={0,1,0,0,0,0,-1,1};
	private byte[] pattern8={0,1,-1,0,0,0,0,1};
 
	// Neighbourhood
	private int neighbourhood(byte[][] c,int x,int y) {
		int neighbourhood=0;
		if (c[x-1][y-1]==1) neighbourhood++;
		if (c[x-1][y  ]==1) neighbourhood++;
		if (c[x-1][y+1]==1) neighbourhood++;
		if (c[x  ][y+1]==1) neighbourhood++;
		if (c[x+1][y+1]==1) neighbourhood++;
		if (c[x+1][y  ]==1) neighbourhood++;
		if (c[x+1][y-1]==1) neighbourhood++;
		if (c[x  ][y-1]==1) neighbourhood++;
		return neighbourhood;
	}
 
	// Transitions Count
	private int transitions(byte[][] c,int x,int y) {
		int transitions=0;
		if (c[x-1][y-1]==0 && c[x-1][y  ]==1) transitions++;
		if (c[x-1][y  ]==0 && c[x-1][y+1]==1) transitions++;
		if (c[x-1][y+1]==0 && c[x  ][y+1]==1) transitions++;
		if (c[x  ][y+1]==0 && c[x+1][y+1]==1) transitions++;
		if (c[x+1][y+1]==0 && c[x+1][y  ]==1) transitions++;
		if (c[x+1][y  ]==0 && c[x+1][y-1]==1) transitions++;
		if (c[x+1][y-1]==0 && c[x  ][y-1]==1) transitions++;
		if (c[x  ][y-1]==0 && c[x-1][y-1]==1) transitions++;
		return transitions;
	}
 
	// Match a pattern
	private boolean matchPattern(byte[][] c,int x,int y,byte[] pattern) {
		if (pattern[0]!=-1 && pattern[0]!=c[x-1][y-1]) return false;
		if (pattern[1]!=-1 && pattern[1]!=c[x-1][y  ]) return false;
		if (pattern[2]!=-1 && pattern[2]!=c[x-1][y+1]) return false;
		if (pattern[3]!=-1 && pattern[3]!=c[x  ][y+1]) return false;
		if (pattern[4]!=-1 && pattern[4]!=c[x+1][y+1]) return false;
		if (pattern[5]!=-1 && pattern[5]!=c[x+1][y  ]) return false;
		if (pattern[6]!=-1 && pattern[6]!=c[x+1][y-1]) return false;
		if (pattern[7]!=-1 && pattern[7]!=c[x  ][y-1]) return false;
		return true;
	}
 
	// Match one of the 8 patterns
	private boolean matchOneOfPatterns(byte[][] c,int x,int y) {
		if (matchPattern(c,x,y,pattern1)) return true;
		if (matchPattern(c,x,y,pattern2)) return true;
		if (matchPattern(c,x,y,pattern3)) return true;
		if (matchPattern(c,x,y,pattern4)) return true;
		if (matchPattern(c,x,y,pattern5)) return true;
		if (matchPattern(c,x,y,pattern6)) return true;
		if (matchPattern(c,x,y,pattern7)) return true;
		if (matchPattern(c,x,y,pattern8)) return true;
		return false;
	}
 
 
	/**
         * Skeletonize the image using succesive thinning.
         * 
         * @param image  the image in an array[x][y] of values "0" or "1" 
         * @param width of the image = 1st dimension of the array
         * @param height of the image = 2nd dimension of the array
         */
	public void thinning(byte[][] image,int width,int height) {
 
		// 3 columns back-buffer (original values)
		byte[][] buffer = new byte[3][height];
 
		// initialize the back-buffer
		for(int y=0;y<height;y++) {
			buffer[0][y]=0;
			buffer[1][y]=image[0][y];
			buffer[2][y]=image[1][y];
		}
 
		// loop until idempotence
		for(int loop=0;;loop++) {
 
			boolean changed=false;
 
			// for each columns
			for(int x=1;x<(width-1);x++) {
 
				// shift the back-buffer + set the last column
				byte[] swp0 = buffer[0]; buffer[0]=buffer[1]; buffer[1]=buffer[2]; buffer[2]=swp0;
				for(int y=0;y<height;y++) buffer[2][y]=image[x+1][y];
 
				// for each pixel
				for(int y=1;y<(height-1);y++) {
 
					// pixel value
					int v = image[x][y];
 
					// pixel not set -> next
					if (v==0) continue;
 
					// is a boundary/extremity ?
					int currentNeighbourhood = neighbourhood(buffer,1,y);
					if (currentNeighbourhood<=1) continue;
					if (currentNeighbourhood>=6) continue;
 
					// is a connection ?
					int transitionsCount = transitions(image,x,y);
					if (transitionsCount==1 && currentNeighbourhood<=3) continue;
 
					// no -> remove this pixel
					if (transitionsCount==1) {
						changed=true;
						image[x][y]=0;
						continue;
					}
 
					// can we delete this pixel ?
					boolean matchOne = matchOneOfPatterns(image,x,y);
 
					// yes -> remove this pixel
					if (matchOne) {
						changed=true;
						image[x][y]=0;
						continue;
					}
				}
			}
 
			// no change -> return result
			if (!changed) return;
		}
	}
}

NB: Cette implémentation n'est pas un filtre ImageJ. Exemple d'utilisation:

Code java :

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

1
2
3
4
5
6
7
8
 
// tableau constitué uniquement de "0" ou de "1", avec un border-extend de 1 pixel
byte[][] bytearray = ... ;
 
// appel du filtre
new Skeleton().thinning(bytearray, width, height);
 
// le tableau bytearray contient maintenant le squelette

[Booster_8]

Salut à tous!

je voudrais savoir est ce que je pourrais avoir le premier algorithme de pseudocode mais juste à l'aide le la bibliothèque OpenCV car la en imageJ je ne comprend rien !!

[pseudocode]

Salut à tous!

je voudrais savoir est ce que je pourrais avoir le premier algorithme de pseudocode mais juste à l'aide le la bibliothèque OpenCV car la en imageJ je ne comprend rien !!

Je te conseille de prendre le code du post #4 et de le traduire en C++/OpenCV. Ou de demander a quelqu'un de le traduire pour toi.

[Beranger]

Voici une version légèrerment modifiée de l'algorithme:
- consommation mémoire réduite en modifiant directement le tableau passé en parametre (in-place)
- approximation plus précise (conservation des orientations dans les structures en H ou en X)

Code java :

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
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
 
/**
 * Skeleton (v2)
 * 
 * Original algorithm : Dr. Chai Quek
 * Modified algorithm : Xavier Philippeau 
 * 
 * @author Xavier Philippeau (based on work of Dr. Chai Quek)
 * 
 */
public class Skeleton {
 
	// Smoothing pattern
	private byte[] pattern1={-1,1,0,1,0,0,0,0};
	private byte[] pattern2={0,1,0,1,-1,0,0,0};
	private byte[] pattern3={0,0,-1,1,0,1,0,0};
	private byte[] pattern4={0,0,0,1,0,1,-1,0};
	private byte[] pattern5={0,0,0,0,-1,1,0,1};
	private byte[] pattern6={-1,0,0,0,0,1,0,1};
	private byte[] pattern7={0,1,0,0,0,0,-1,1};
	private byte[] pattern8={0,1,-1,0,0,0,0,1};
 
	// Neighbourhood
	private int neighbourhood(byte[][] c,int x,int y) {
		int neighbourhood=0;
		if (c[x-1][y-1]==1) neighbourhood++;
		if (c[x-1][y  ]==1) neighbourhood++;
		if (c[x-1][y+1]==1) neighbourhood++;
		if (c[x  ][y+1]==1) neighbourhood++;
		if (c[x+1][y+1]==1) neighbourhood++;
		if (c[x+1][y  ]==1) neighbourhood++;
		if (c[x+1][y-1]==1) neighbourhood++;
		if (c[x  ][y-1]==1) neighbourhood++;
		return neighbourhood;
	}
 
	// Transitions Count
	private int transitions(byte[][] c,int x,int y) {
		int transitions=0;
		if (c[x-1][y-1]==0 && c[x-1][y  ]==1) transitions++;
		if (c[x-1][y  ]==0 && c[x-1][y+1]==1) transitions++;
		if (c[x-1][y+1]==0 && c[x  ][y+1]==1) transitions++;
		if (c[x  ][y+1]==0 && c[x+1][y+1]==1) transitions++;
		if (c[x+1][y+1]==0 && c[x+1][y  ]==1) transitions++;
		if (c[x+1][y  ]==0 && c[x+1][y-1]==1) transitions++;
		if (c[x+1][y-1]==0 && c[x  ][y-1]==1) transitions++;
		if (c[x  ][y-1]==0 && c[x-1][y-1]==1) transitions++;
		return transitions;
	}
 
	// Match a pattern
	private boolean matchPattern(byte[][] c,int x,int y,byte[] pattern) {
		if (pattern[0]!=-1 && pattern[0]!=c[x-1][y-1]) return false;
		if (pattern[1]!=-1 && pattern[1]!=c[x-1][y  ]) return false;
		if (pattern[2]!=-1 && pattern[2]!=c[x-1][y+1]) return false;
		if (pattern[3]!=-1 && pattern[3]!=c[x  ][y+1]) return false;
		if (pattern[4]!=-1 && pattern[4]!=c[x+1][y+1]) return false;
		if (pattern[5]!=-1 && pattern[5]!=c[x+1][y  ]) return false;
		if (pattern[6]!=-1 && pattern[6]!=c[x+1][y-1]) return false;
		if (pattern[7]!=-1 && pattern[7]!=c[x  ][y-1]) return false;
		return true;
	}
 
	// Match one of the 8 patterns
	private boolean matchOneOfPatterns(byte[][] c,int x,int y) {
		if (matchPattern(c,x,y,pattern1)) return true;
		if (matchPattern(c,x,y,pattern2)) return true;
		if (matchPattern(c,x,y,pattern3)) return true;
		if (matchPattern(c,x,y,pattern4)) return true;
		if (matchPattern(c,x,y,pattern5)) return true;
		if (matchPattern(c,x,y,pattern6)) return true;
		if (matchPattern(c,x,y,pattern7)) return true;
		if (matchPattern(c,x,y,pattern8)) return true;
		return false;
	}
 
 
	/**
         * Skeletonize the image using succesive thinning.
         * 
         * @param image  the image in an array[x][y] of values "0" or "1" 
         * @param width of the image = 1st dimension of the array
         * @param height of the image = 2nd dimension of the array
         */
	public void thinning(byte[][] image,int width,int height) {
 
		// 3 columns back-buffer (original values)
		byte[][] buffer = new byte[3][height];
 
		// initialize the back-buffer
		for(int y=0;y<height;y++) {
			buffer[0][y]=0;
			buffer[1][y]=image[0][y];
			buffer[2][y]=image[1][y];
		}
 
		// loop until idempotence
		for(int loop=0;;loop++) {
 
			boolean changed=false;
 
			// for each columns
			for(int x=1;x<(width-1);x++) {
 
				// shift the back-buffer + set the last column
				byte[] swp0 = buffer[0]; buffer[0]=buffer[1]; buffer[1]=buffer[2]; buffer[2]=swp0;
				for(int y=0;y<height;y++) buffer[2][y]=image[x+1][y];
 
				// for each pixel
				for(int y=1;y<(height-1);y++) {
 
					// pixel value
					int v = image[x][y];
 
					// pixel not set -> next
					if (v==0) continue;
 
					// is a boundary/extremity ?
					int currentNeighbourhood = neighbourhood(buffer,1,y);
					if (currentNeighbourhood<=1) continue;
					if (currentNeighbourhood>=6) continue;
 
					// is a connection ?
					int transitionsCount = transitions(image,x,y);
					if (transitionsCount==1 && currentNeighbourhood<=3) continue;
 
					// no -> remove this pixel
					if (transitionsCount==1) {
						changed=true;
						image[x][y]=0;
						continue;
					}
 
					// can we delete this pixel ?
					boolean matchOne = matchOneOfPatterns(image,x,y);
 
					// yes -> remove this pixel
					if (matchOne) {
						changed=true;
						image[x][y]=0;
						continue;
					}
				}
			}
 
			// no change -> return result
			if (!changed) return;
		}
	}
}

NB: Cette implémentation n'est pas un filtre ImageJ. Exemple d'utilisation:

Code java :

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

1
2
3
4
5
6
7
8
 
// tableau constitué uniquement de "0" ou de "1", avec un border-extend de 1 pixel
byte[][] bytearray = ... ;
 
// appel du filtre
new Skeleton().thinning(bytearray, width, height);
 
// le tableau bytearray contient maintenant le squelette

Bonjour,

Connaissez-vous une méthode qui transforme une image binarisée en tableau de byte (format attendu par votre méthode)?
Je n'ai pas trouvé ce type de fonctionnalité au sein de la bibliothèque imageJ.

Merci de votre aide.

[pseudocode]

Bonjour,

Connaissez-vous une méthode qui transforme une image binarisée en tableau de byte (format attendu par votre méthode)?
Je n'ai pas trouvé ce type de fonctionnalité au sein de la bibliothèque imageJ.

Merci de votre aide.

Heu... non, je ne connais pas de méthode qui fait cela directement. Mais si vous avez un "ImageProcessor", il suffit de créer un tableau et de le remplir. Un truc du genre:

Code java :

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

1
2
3
4
5
6
7
ImageProcessor ip = ... 
 
int w = ip.getWidth(), h=ip.getHeight();
byte[][] bytearray = new byte[w][h];
for (int y = 0; y < h; y++)
	for (int x = 0; x < w; x++)
		if ( ip.getPixel(x,y) > SEUIL ) bytearray[x][y]=1;

[behichi]

Bonjour,
J’ai testé ce programme en c++ ca marche bien
La question c'est comment éliminer les petits segments ajoutés dans les extrémités pour avoir des caractères comme elles sont

Ensuite je vais détecter les segments à partir du squelette
Par exemples pour la lettre A comment détecter les segments (/, _ et \)

Bonjour,

Je voudrais bien s'il vous plait que vous m'envoyez ce code en C++

Et merci d'avance.

[Invité]

Bonjour,

Merci beaucoup pour ce plugin qui fonctionne très bien, et pour le lien vers l'algo de Chai Quek. Cette implémentation pourrait peut-être être postée sur le site des plugins d'ImageJ ? ( http://imagejdocu.tudor.lu/doku.php?id=plugin:start )

En plus ancien, j'ai noté l'existence d'autres algorithmes de squelettisation.

• l'algorithme de Philippe Marthon, utilisé pour de la reconnaissance de caractères (il produit des érosions avec peu de barbules [non réversible]). Chercher "marthon squelette" dans un moteur de recherche, par exemple, pour plus d'informations.
  
• l'algorithme de Zhang Suen. Ce dernier est déjà installé dans Fiji (Fiji Is Just ImageJ), dans le menu "Process / Binary / Skeletonize". Sur l'image test de ce fil, il produit un résultat avec moins de "fourches" (comme Marthon). C'est une squelettisation non réversible, mais peut-être plus propice à la reconnaissance de caractères...

[khoeds]

Vous n'avez pas un code matlab qui fait la même chose en 3D??

[pseudocode]

Vous n'avez pas un code matlab qui fait la même chose en 3D??

Non. Et je ne suis pas bien sur qu'on puisse facilement étendre cet algorithme a la 3D, spécialement le comptage du nombre de transitions.

[mickeynad]

Voici une implémentation du calcul du squelette d'une image par la méthode décrite dans ce document pdf.

La méthode consiste a faire des erosions multiples jusqu'a atteindre le squelette. Ce squelette peut etre utilisé, par exemple, pour la reconnaissance de formes (OCR, ...)


A gauche: l'image originale
A droite: le squelette obtenu.

Code java :

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
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
import ij.IJ;
import ij.ImagePlus;
import ij.gui.GenericDialog;
import ij.plugin.filter.PlugInFilter;
import ij.process.ByteProcessor;
import ij.process.ImageProcessor;
 
 
/**
 * Skeleton Filter
 * 
 * @author Xavier Philippeau (from work of Dr. Chai Quek)
 *
 */
public class Skeleton_ implements PlugInFilter {
 
	// neighbours order
	private int[] dx = new int[] {-1, 0, 1,1,1,0,-1,-1};
	private int[] dy = new int[] {-1,-1,-1,0,1,1, 1, 0};
 
	// Smoothing pattern
	private int[] pattern1={-1,1,0,1,0,0,0,0};
	private int[] pattern2={0,1,0,1,-1,0,0,0};
	private int[] pattern3={0,0,-1,1,0,1,0,0};
	private int[] pattern4={0,0,0,1,0,1,-1,0};
	private int[] pattern5={0,0,0,0,-1,1,0,1};
	private int[] pattern6={-1,0,0,0,0,1,0,1};
	private int[] pattern7={0,1,0,0,0,0,-1,1};
	private int[] pattern8={0,1,-1,0,0,0,0,1};
 
	// filter configuration
	private boolean blackbackground = true;
	private int threshold = 0;
 
	//	 About...
	private void showAbout() {
		IJ.showMessage("Skeleton...","Skeleton Filter by Pseudocode");
	}
 
	public int setup(String arg, ImagePlus imp) {
 
		// about...
		if (arg.equals("about")) {
			showAbout(); 
			return DONE;
		}
 
		// else...
		if (imp==null) return DONE;
 
		// Configuration dialog.
		GenericDialog gd = new GenericDialog("Parameters");
		gd.addChoice("Background color", new String[]{"Black","White"}, "Black");
		gd.addNumericField("Black/White threshold",128,0);
 
		while(true) {
			gd.showDialog();
			if ( gd.wasCanceled() )	return DONE;
 
			this.blackbackground  =  gd.getNextChoice().equals("Black")?true:false;
			this.threshold  =  (int)gd.getNextNumber();
 
			if (this.threshold<=0) continue;
			if (this.threshold>=255) continue;
			break;
		}
		gd.dispose();
 
		return PlugInFilter.DOES_8G;
	}
 
	public void run(ImageProcessor ip) {
 
		// ImageProcessor -> ByteProcessor conversion
		ByteProcessor bp = new ByteProcessor(ip.getWidth(),ip.getHeight());
		for (int y = 0; y < ip.getHeight(); y++) {
			for (int x = 0; x < ip.getWidth(); x++) {
				bp.set(x,y,ip.getPixel(x,y));
			}
		}
 
		// filter
		ByteProcessor newbp = filter( bp );
 
		// ByteProcessor -> ImageProcessor conversion
		ImageProcessor out = new ByteProcessor(ip.getWidth(),ip.getHeight());
		for (int y = 0; y < ip.getHeight(); y++) {
			for (int x = 0; x < ip.getWidth(); x++) {
				out.set(x,y,newbp.get(x,y));
			}
		}
		ImagePlus newImg = new ImagePlus("Skeleton", out);
		newImg.show();
 
	}
 
	// -------------------------------------------------------------------------
 
	// Binary value of the gray scale image (0..255) -> (0,1)
	private int ChannelValue(ByteProcessor c,int x,int y) {
		if (c.getPixel(x,y)<this.threshold) return 0;
		return 1;
	}
 
	// Neighbourhood
	private int neighbourhood(ByteProcessor c,int x,int y) {
		int neighbourhood=0;
 
		for(int i=0;i<8;i++)
			neighbourhood += ChannelValue(c,x+dx[i],y+dy[i]);
 
		return neighbourhood;
	}
 
	// Transitions Count
	private int transitions(ByteProcessor c,int x,int y) {
		int Trans=0;
 
		for(int i=0;i<8;i++) {
			int pc = ChannelValue(c,x+dx[i],y+dy[i]);
			int pn = ChannelValue(c,x+dx[(i+1)%8],y+dy[(i+1)%8]);
			if ((pc==0) && (pn==1)) Trans++;
		}
 
		return Trans;
	}
 
	// Match a pattern
	private boolean matchPattern(ByteProcessor c,int x,int y,int[] pattern) {
		for(int i=0;i<8;i++) {
			if (pattern[i]==-1) continue;
			int v = ChannelValue(c,x+dx[i],y+dy[i]);
			if (pattern[i]!=v) return false;
		}
		return true;
	}
 
    // Match one of the 8 patterns
	private boolean matchOneOfPatterns(ByteProcessor c,int x,int y) {
		if (matchPattern(c,x,y,pattern1)) return true;
		if (matchPattern(c,x,y,pattern2)) return true;
		if (matchPattern(c,x,y,pattern3)) return true;
		if (matchPattern(c,x,y,pattern4)) return true;
		if (matchPattern(c,x,y,pattern5)) return true;
		if (matchPattern(c,x,y,pattern6)) return true;
		if (matchPattern(c,x,y,pattern7)) return true;
		if (matchPattern(c,x,y,pattern8)) return true;
		return false;
	}
 
	private ByteProcessor thinning(ByteProcessor original) {
		int width = original.getWidth();
		int height = original.getHeight();
 
		// previous image buffer
		ByteProcessor c = new ByteProcessor(width,height);
		for(int y=0;y<height;y++)
			for(int x=0;x<width;x++)
				if (this.blackbackground)
					c.set(x,y,255*ChannelValue(original,x,y));
				else
					c.set(x,y,255-255*ChannelValue(original,x,y));
 
		// new image buffer
		ByteProcessor c2  = new ByteProcessor(width,height);
 
		// loop until idempotence
		for(int loop=0;;loop++) {
 
			int pixelchangecount=0;
 
			// copy previous image in new image
			for(int y=0;y<height;y++)
				for(int x=0;x<width;x++) 
					c2.set(x,y,c.get(x,y));
 
			// for each pixel
			for(int y=0;y<height;y++) {
 
				for(int x=0;x<width;x++) {
 
					// pixel value
					int v = ChannelValue(c,x,y);
 
					// pixel not set -> next
					if (v==0) continue;
 
					// is a boundary ?
					int previousNeighbourhood = neighbourhood(c,x,y);
					if (previousNeighbourhood==8) continue;
 
					// is an extremity ?
					int currentNeighbourhood = neighbourhood(c2,x,y);
					if (currentNeighbourhood<=1) continue;
					if (currentNeighbourhood>=6) continue;
 
					// is a connection ?
					int transitionsCount = transitions(c2,x,y);
 
					// Addition to the original algorithm:
					// Preservation of the "Y curve" near the edges 
					if (transitionsCount==1 && previousNeighbourhood<=3) continue;
 
					if (transitionsCount==1) {
						pixelchangecount++;
						c2.set(x,y,0);
						continue;
					}
 
					// is a deletable pixel ?
					boolean matchOne = matchOneOfPatterns(c2,x,y);
					if (matchOne) {
						pixelchangecount++;
						c2.set(x,y,0);
						continue;
					}
				}
			}
 
			// no change -> return result
			if (pixelchangecount==0) return c;
 
			// swap image buffers, then loop.
			ByteProcessor tmp = c;
			c=c2;
			c2=tmp;
		}
	}
 
	// Return the skeleton
	public ByteProcessor filter(ByteProcessor bp) {
		ByteProcessor skel = thinning(bp);
		return skel;
	}
}

Bonjour,

Alors j'ai essayé d'utiliser ce filtre sur imagej mais je n'obtiens pas du tout la même chose que toi. Pourtant, dans mon menu imagej, je suis allée à plugin puis new puis j'ai copié ton code que j'ai compilé sans aucune erreur. Ensuite, j'ai ouvert une image, j'ai sélectionné le texte d'intérêt, j'ai lancé le plugin et il me demande de rentrer des valeurs de black/white threshold. Tu mets quoi comme valeur?
Aussi comment tu fais pour avoir après les points d'intérêts?
Je travaille sur la reconnaissance de caractères sur un texte dans une image à l'aide de imagej et je pense que ce filtre pourra beaucoup m'aider.

Merci.

[pseudocode]

Alors j'ai essayé d'utiliser ce filtre sur imagej mais je n'obtiens pas du tout la même chose que toi. Pourtant, dans mon menu imagej, je suis allée à plugin puis new puis j'ai copié ton code que j'ai compilé sans aucune erreur. Ensuite, j'ai ouvert une image, j'ai sélectionné le texte d'intérêt, j'ai lancé le plugin et il me demande de rentrer des valeurs de black/white threshold. Tu mets quoi comme valeur?

L'image d'entrée est une image a 256 niveaux de gris. Le seuil (threshold) permet de binariser l'image (pixel<threshold)=>noir, et (pixel>=threshold)=>blanc.

cf. méthode ChannelValue()

Aussi comment tu fais pour avoir après les points d'intérêts?
Je travaille sur la reconnaissance de caractères sur un texte dans une image à l'aide de imagej et je pense que ce filtre pourra beaucoup m'aider.

Pour les points d'intérêts, j'ai proposé une approche basique au post #3

[wamajed]

j'ai téléchargé la librairie IJ et ca n'a pas marché avec moi ce programme
"Exception in thread "main" java.lang.IllegalArgumentException: Width (0) and height (0) must be > 0"
il n'arrive pas à lire l'image

[manuel-v]

Bonjour,
J'ai utilisé cette bibliothèque pour mon usage personnel. J'ai modifié son utilisation pour qu'il fonctionne uniquement avec des WritableRaster.

J'ai trouvé un petit bug.

Par moment on va chercher à des coordonnées de -1.
J'ai modifié ceci dans la fonction thinning :

Code :

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

1
2
3
4
5
 
// for each pixel
			for(int y=1;y<height-1;y++) {
 
				for(int x=1;x<width-1;x++) {

Si y ou x vaut 0, avec l'appel à la fonction
int previousNeighbourhood = neighbourhood(c,x,y);
on ira chercher par moment un pixel avec un coordonnée de -1.
C'est la même chose pour height et width.

Cette modification ne fonctionne plus avec une image qui touche le bord.
Pour que cela fonctionne quand même, j'ai agrandi mon image d'un pixel sur les quatres cotés.

Je ne sais pas si cette erreur est due au fait d'utiliser un WritableRaster, je ne m'y connais pas assez pour le dire.

[pseudocode]

Si y ou x vaut 0, avec l'appel à la fonction
int previousNeighbourhood = neighbourhood(c,x,y);
on ira chercher par moment un pixel avec un coordonnée de -1.
C'est la même chose pour height et width.

Cette modification ne fonctionne plus avec une image qui touche le bord.
Pour que cela fonctionne quand même, j'ai agrandi mon image d'un pixel sur les quatres cotés.

Je ne sais pas si cette erreur est due au fait d'utiliser un WritableRaster, je ne m'y connais pas assez pour le dire.

Effectivement c'est un bug. La boucle devrait etre

Code :

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

1
2
for(int y=1;y<height-1;y++) {
	for(int x=1;x<width-1;x++) {

D'ailleurs j'ai du m'en rendre compte car dans la version du post #4, j'avais fait la modif. J'ai du oublier de la reporter dans le code du post #1.

Merci.