图像处理之Zhang Suen细化算法

ゝ一纸荒年。 2022-07-14 04:55 360阅读 0赞

转载自：[http://blog.csdn.net/jia20003/article/details/52142992][http_blog.csdn.net_jia20003_article_details_52142992]

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

**一：算法介绍**

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的像素位置与举例如下：

![20160807160046220][]

其中 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][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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);

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

a. Step One

**\[java\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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; 
31. 
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"); 
37. 
38. **int** con3 = p2\*p4\*p6; 
39. **int** con4 = p4\*p6\*p8; 
40. 
41. **if**((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) \{ 
42.  flagmap\[offset+col\] = 1; 
43.  stop = **false**; 
44.  \} 
45. 
46.  \} 
47.  \} 
48. **return** stop; 
49. \}

b. Step Two

**\[java\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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; 
31. 
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"); 
37. 
38. **int** con3 = p2\*p4\*p8; 
39. **int** con4 = p2\*p6\*p8; 
40. 
41. **if**((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) \{ 
42.  flagmap\[offset+col\] = 1; 
43.  stop = **false**; 
44.  \} 
45. 
46.  \} 
47.  \} 
48. **return** stop; 
49. \}

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

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

**三：运行效果**

![20160807160207570][]

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

**\[java\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **import** java.awt.image.BufferedImage; 
2.  **import** java.util.Arrays; 
3.  
4.  **public****class** ZhangSuenThinFilter **extends** BinaryFilter \{ 
5.  **private****int** fcolor; 
6.  **public** ZhangSuenThinFilter() \{ 
7.   fcolor = 0; 
8.   \} 
9.  
10. **public****int** getFcolor() \{ 
11. **return** fcolor; 
12.  \} 
13. 
14. 
15. **public****void** setFcolor(**int** fcolor) \{ 
16. **this**.fcolor = fcolor; 
17.  \} 
18. 
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); 
28. 
29. 
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.  \} 
45. 
46. // 结果
47.  BufferedImage bi = **new** BufferedImage(width, height, BufferedImage.TYPE\_INT\_ARGB); 
48.  setRGB(bi, 0, 0, width, height, pixels); 
49. **return** bi; 
50.  \} 
51. 
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.  \} 
59. 
60.  \} 
61. 
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; 
92. 
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"); 
98. 
99. **int** con3 = p2\*p4\*p6; 
100. **int** con4 = p4\*p6\*p8; 
101. 
102. **if**((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) \{ 
103.  flagmap\[offset+col\] = 1; 
104.  stop = **false**; 
105.  \} 
106. 
107.  \} 
108.  \} 
109. **return** stop; 
110.  \} 
111. 
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; 
142. 
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"); 
148. 
149. **int** con3 = p2\*p4\*p8; 
150. **int** con4 = p2\*p6\*p8; 
151. 
152. **if**((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) \{ 
153.  flagmap\[offset+col\] = 1; 
154.  stop = **false**; 
155.  \} 
156. 
157.  \} 
158.  \} 
159. **return** stop; 
160.  \} 
161. 
162. \}

[http_blog.csdn.net_jia20003_article_details_52142992]: http://blog.csdn.net/jia20003/article/details/52142992://
[Link 1]: http://lib.csdn.net/base/datastructure
[20160807160046220]: /images/20220714/f9a242477e104d95adffa359e8aad1e2.png
[view plain]: http://blog.csdn.net/jia20003/article/details/52142992#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/1814343
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/1814343/fork
[20160807160207570]: /images/20220714/891b9bb1f0bd4717a9c66a9fb7d688b3.png