图像处理之Zhang Suen细化算法

转载自：http://blog.csdn.net/jia20003/article/details/52142992

在二值图像处理特别是OCR识别与匹配中，都要通过对字符进行细化以便获得图像的骨架，通过zhang-suen细化算法获得图像，作为图像的特征之一，常用来作为识别或者模式匹配。

一：算法介绍

Zhang-Suen细化算法通常是一个迭代算法，整个迭代过程分为两步：

Step One：循环所有前景像素点，对符合如下条件的像素点标记为删除：

1. 2 <= N(p1) <=6

2. S(P1) = 1

3. P2 * P4 * P6 = 0

4. P4 * P6 * P8 = 0

其中N(p1)表示跟P1相邻的8个像素点中，为前景像素点的个数

S(P1)表示从P2 ～ P9 ～ P2像素中出现0～1的累计次数，其中0表示背景，1表示前景

完整的P1 ～P9的像素位置与举例如下：

其中 N(p1) = 4, S(P1) = 3, P2*P4*P6=0*0*0=0, P4*P6*P8=0*0*1=0, 不符合条件，无需标记为删除。

Step Two：跟Step One很类似，条件1、2完全一致，只是条件3、4稍微不同，满足如下条件的像素P1则标记为删除，条件如下：

1. 2 <= N(p1) <=6

2. S(P1) = 1

3. P2 * P4 * P8 = 0

4. P2 * P6 * P8 = 0

循环上述两步骤，直到两步中都没有像素被标记为删除为止，输出的结果即为二值图像细化后的骨架。

二：代码实现步骤

1. 二值化输入图像，初始化图像像素对应的标记映射数组

[java] view plain copy

1. BufferedImage binaryImage = super.process(image);
2. int width = binaryImage.getWidth();
3. int height = binaryImage.getHeight();
4. int[] pixels = new**int*[width\height];
5. int[] flagmap = new**int*[width\height];
6. getRGB(binaryImage, 0, 0, width, height, pixels);

7. Arrays.fill(flagmap, 0);

8. 迭代细化算法(Zhang-Suen)

a. Step One

[java] view plain copy

1. private**boolean step1Scan(int[] input, int[] flagmap, int width, int** height) {
2. boolean stop = true;
3. int bc = 255 - fcolor;
4. int p1=0, p2=0, p3=0;
5. int p4=0, p5=0, p6=0;
6. int p7=0, p8=0, p9=0;
7. int offset = 0;
8. for(int row=1; row<height-1; row++) {
9. offset = row*width;
10. for(int col=1; col<width-1; col++) {
11. p1 = (input[offset+col]>>16)&0xff;
12. if(p1 == bc) continue;
13. p2 = (input[offset-width+col]>>16)&0xff;
14. p3 = (input[offset-width+col+1]>>16)&0xff;
15. p4 = (input[offset+col+1]>>16)&0xff;
16. p5 = (input[offset+width+col+1]>>16)&0xff;
17. p6 = (input[offset+width+col]>>16)&0xff;
18. p7 = (input[offset+width+col-1]>>16)&0xff;
19. p8 = (input[offset+col-1]>>16)&0xff;
20. p9 = (input[offset-width+col-1]>>16)&0xff;
21. // match 1 - 前景像素 0 - 背景像素
22. p1 = (p1 == fcolor) ? 1 : 0;
23. p2 = (p2 == fcolor) ? 1 : 0;
24. p3 = (p3 == fcolor) ? 1 : 0;
25. p4 = (p4 == fcolor) ? 1 : 0;
26. p5 = (p5 == fcolor) ? 1 : 0;
27. p6 = (p6 == fcolor) ? 1 : 0;
28. p7 = (p7 == fcolor) ? 1 : 0;
29. p8 = (p8 == fcolor) ? 1 : 0;
30. p9 = (p9 == fcolor) ? 1 : 0;
32. int con1 = p2+p3+p4+p5+p6+p7+p8+p9;
33. String sequence = “” + String.valueOf(p2) + String.valueOf(p3) + String.valueOf(p4) + String.valueOf(p5) +
34. String.valueOf(p6) + String.valueOf(p7) + String.valueOf(p8) + String.valueOf(p9) + String.valueOf(p2);
35. int index1 = sequence.indexOf(“01”);
36. int index2 = sequence.lastIndexOf(“01”);
38. int con3 = p2*p4*p6;
39. int con4 = p4*p6*p8;
41. if((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) {
42. flagmap[offset+col] = 1;
43. stop = false;
44. }
46. }
47. }
48. return stop;
49. }

b. Step Two

[java] view plain copy

1. private**boolean step2Scan(int[] input, int[] flagmap, int width, int** height) {
2. boolean stop = true;
3. int bc = 255 - fcolor;
4. int p1=0, p2=0, p3=0;
5. int p4=0, p5=0, p6=0;
6. int p7=0, p8=0, p9=0;
7. int offset = 0;
8. for(int row=1; row<height-1; row++) {
9. offset = row*width;
10. for(int col=1; col<width-1; col++) {
11. p1 = (input[offset+col]>>16)&0xff;
12. if(p1 == bc) continue;
13. p2 = (input[offset-width+col]>>16)&0xff;
14. p3 = (input[offset-width+col+1]>>16)&0xff;
15. p4 = (input[offset+col+1]>>16)&0xff;
16. p5 = (input[offset+width+col+1]>>16)&0xff;
17. p6 = (input[offset+width+col]>>16)&0xff;
18. p7 = (input[offset+width+col-1]>>16)&0xff;
19. p8 = (input[offset+col-1]>>16)&0xff;
20. p9 = (input[offset-width+col-1]>>16)&0xff;
21. // match 1 - 前景像素 0 - 背景像素
22. p1 = (p1 == fcolor) ? 1 : 0;
23. p2 = (p2 == fcolor) ? 1 : 0;
24. p3 = (p3 == fcolor) ? 1 : 0;
25. p4 = (p4 == fcolor) ? 1 : 0;
26. p5 = (p5 == fcolor) ? 1 : 0;
27. p6 = (p6 == fcolor) ? 1 : 0;
28. p7 = (p7 == fcolor) ? 1 : 0;
29. p8 = (p8 == fcolor) ? 1 : 0;
30. p9 = (p9 == fcolor) ? 1 : 0;
32. int con1 = p2+p3+p4+p5+p6+p7+p8+p9;
33. String sequence = “” + String.valueOf(p2) + String.valueOf(p3) + String.valueOf(p4) + String.valueOf(p5) +
34. String.valueOf(p6) + String.valueOf(p7) + String.valueOf(p8) + String.valueOf(p9) + String.valueOf(p2);
35. int index1 = sequence.indexOf(“01”);
36. int index2 = sequence.lastIndexOf(“01”);
38. int con3 = p2*p4*p8;
39. int con4 = p2*p6*p8;
41. if((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) {
42. flagmap[offset+col] = 1;
43. stop = false;
44. }
46. }
47. }
48. return stop;
49. }

c. 检查如果上述两部没有任何像素被标记，则停止迭代，否则继续执行a, b

1. 返回细化后的图像，并显示

三：运行效果

四：完整的Zhang-suen算法代码实现：

[java] view plain copy

1. import java.awt.image.BufferedImage;
2. import java.util.Arrays;
4. public**class ZhangSuenThinFilter extends** BinaryFilter {
5. private**int** fcolor;
6. public ZhangSuenThinFilter() {
7. fcolor = 0;
8. }
10. public**int** getFcolor() {
11. return fcolor;
12. }
15. public**void setFcolor(int** fcolor) {
16. this.fcolor = fcolor;
17. }
19. @Override
20. public BufferedImage process(BufferedImage image) {
21. BufferedImage binaryImage = super.process(image);
22. int width = binaryImage.getWidth();
23. int height = binaryImage.getHeight();
24. int[] pixels = new**int*[width\height];
25. int[] flagmap = new**int*[width\height];
26. getRGB(binaryImage, 0, 0, width, height, pixels);
27. Arrays.fill(flagmap, 0);
30. // 距离变化
31. boolean stop = false;
32. while(!stop) {
33. // step one
34. boolean s1 = step1Scan(pixels, flagmap, width, height);
35. deletewithFlag(pixels, flagmap);
36. Arrays.fill(flagmap, 0);
37. // step two
38. boolean s2 = step2Scan(pixels, flagmap, width, height);
39. deletewithFlag(pixels, flagmap);
40. Arrays.fill(flagmap, 0);
41. if(s1 && s2) {
42. stop = true;
43. }
44. }
46. // 结果
47. BufferedImage bi = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);
48. setRGB(bi, 0, 0, width, height, pixels);
49. return bi;
50. }
52. private**void deletewithFlag(int[] pixels, int**[] flagmap) {
53. int bc = 255 - fcolor;
54. for(int i=0; i<pixels.length; i++) {
55. if(flagmap[i] == 1) {
56. pixels[i] = (0xff << 24) | ((bc&0xff) << 16) | ((bc&0xff) << 8) | (bc&0xff);
57. }
58. }
60. }
62. private**boolean step1Scan(int[] input, int[] flagmap, int width, int** height) {
63. boolean stop = true;
64. int bc = 255 - fcolor;
65. int p1=0, p2=0, p3=0;
66. int p4=0, p5=0, p6=0;
67. int p7=0, p8=0, p9=0;
68. int offset = 0;
69. for(int row=1; row<height-1; row++) {
70. offset = row*width;
71. for(int col=1; col<width-1; col++) {
72. p1 = (input[offset+col]>>16)&0xff;
73. if(p1 == bc) continue;
74. p2 = (input[offset-width+col]>>16)&0xff;
75. p3 = (input[offset-width+col+1]>>16)&0xff;
76. p4 = (input[offset+col+1]>>16)&0xff;
77. p5 = (input[offset+width+col+1]>>16)&0xff;
78. p6 = (input[offset+width+col]>>16)&0xff;
79. p7 = (input[offset+width+col-1]>>16)&0xff;
80. p8 = (input[offset+col-1]>>16)&0xff;
81. p9 = (input[offset-width+col-1]>>16)&0xff;
82. // match 1 - 前景像素 0 - 背景像素
83. p1 = (p1 == fcolor) ? 1 : 0;
84. p2 = (p2 == fcolor) ? 1 : 0;
85. p3 = (p3 == fcolor) ? 1 : 0;
86. p4 = (p4 == fcolor) ? 1 : 0;
87. p5 = (p5 == fcolor) ? 1 : 0;
88. p6 = (p6 == fcolor) ? 1 : 0;
89. p7 = (p7 == fcolor) ? 1 : 0;
90. p8 = (p8 == fcolor) ? 1 : 0;
91. p9 = (p9 == fcolor) ? 1 : 0;
93. int con1 = p2+p3+p4+p5+p6+p7+p8+p9;
94. String sequence = “” + String.valueOf(p2) + String.valueOf(p3) + String.valueOf(p4) + String.valueOf(p5) +
95. String.valueOf(p6) + String.valueOf(p7) + String.valueOf(p8) + String.valueOf(p9) + String.valueOf(p2);
96. int index1 = sequence.indexOf(“01”);
97. int index2 = sequence.lastIndexOf(“01”);
99. int con3 = p2*p4*p6;
100. int con4 = p4*p6*p8;
102. if((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) {
103. flagmap[offset+col] = 1;
104. stop = false;
105. }
107. }
108. }
109. return stop;
110. }
112. private**boolean step2Scan(int[] input, int[] flagmap, int width, int** height) {
113. boolean stop = true;
114. int bc = 255 - fcolor;
115. int p1=0, p2=0, p3=0;
116. int p4=0, p5=0, p6=0;
117. int p7=0, p8=0, p9=0;
118. int offset = 0;
119. for(int row=1; row<height-1; row++) {
120. offset = row*width;
121. for(int col=1; col<width-1; col++) {
122. p1 = (input[offset+col]>>16)&0xff;
123. if(p1 == bc) continue;
124. p2 = (input[offset-width+col]>>16)&0xff;
125. p3 = (input[offset-width+col+1]>>16)&0xff;
126. p4 = (input[offset+col+1]>>16)&0xff;
127. p5 = (input[offset+width+col+1]>>16)&0xff;
128. p6 = (input[offset+width+col]>>16)&0xff;
129. p7 = (input[offset+width+col-1]>>16)&0xff;
130. p8 = (input[offset+col-1]>>16)&0xff;
131. p9 = (input[offset-width+col-1]>>16)&0xff;
132. // match 1 - 前景像素 0 - 背景像素
133. p1 = (p1 == fcolor) ? 1 : 0;
134. p2 = (p2 == fcolor) ? 1 : 0;
135. p3 = (p3 == fcolor) ? 1 : 0;
136. p4 = (p4 == fcolor) ? 1 : 0;
137. p5 = (p5 == fcolor) ? 1 : 0;
138. p6 = (p6 == fcolor) ? 1 : 0;
139. p7 = (p7 == fcolor) ? 1 : 0;
140. p8 = (p8 == fcolor) ? 1 : 0;
141. p9 = (p9 == fcolor) ? 1 : 0;
143. int con1 = p2+p3+p4+p5+p6+p7+p8+p9;
144. String sequence = “” + String.valueOf(p2) + String.valueOf(p3) + String.valueOf(p4) + String.valueOf(p5) +
145. String.valueOf(p6) + String.valueOf(p7) + String.valueOf(p8) + String.valueOf(p9) + String.valueOf(p2);
146. int index1 = sequence.indexOf(“01”);
147. int index2 = sequence.lastIndexOf(“01”);
149. int con3 = p2*p4*p8;
150. int con4 = p2*p6*p8;
152. if((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) {
153. flagmap[offset+col] = 1;
154. stop = false;
155. }
157. }
158. }
159. return stop;
160. }
162. }