Zhang快速并行细化算法
最近的研究涉及获取二值图像骨架（图象的中轴线），网上找到许多方法，Zhang快速并行细化算法是出现次数最多的算法，看了几篇博客，又下载了提出这个算法的文献，感觉这个方法很容易理解，编程也容易，其实最后也没花多少时间就成功了，VB6.0编写的程序，用到了函数库MatrixVB，这里分享一下心得。
1. 算法简介
图1 8邻域系统
图1表示以P1为中心的8邻域系统，P2~P9代表与P1相邻的8个像素点，1.1 细化步骤1
删除同时满足下列条件的边界点:
① 2≤N(P1)≤6; ② S(P1)=1; ③ P2×P4×P6=0; ④ P4×P6×P8=0;
其中：N(P1)是P1的非零邻点的个数,S(P1)是以P2，P3，…，P9，P2为序时这些点的值从0到1变化的次数。 1.2 细化步骤2
删除同时满足下列条件的边界点:
① 2≤N(P1)≤6; ② S(P1)=1; ③ P2×P4×P8=0; ④ P2×P6×P8=0;
以上两步操作构成一次迭代，直至没有点再满足标记条件，这时剩下的点组
成区域即为细化后骨架。
2. 程序及细化结果
用VB6.0编写的程序，用到了函数库MatrixVB（需要的话可以到网上去搜，很老的东西了）。 2.1 模块部分
这部分包括自定义数据类型（相当于C语言里的结构体），定义了一些函数。 Option Explicit
Type necessary_conditions '4个条件 N_P1 As Integer S_P1 As Integer
Mult_P2P4P6 As Integer Mult_P4P6P8 As Integer Mult_P2P4P8 As Integer Mult_P2P6P8 As Integer End Type Type position x As Integer y As Integer End Type
'************************************************************** '计算4个条件的值
'输入：P1点的坐标，待处理的二值图binary_image '输出：4个条件的值
'**************************************************************
Function obtain_necessary_conditions_value(x%, y%, binary_image) As necessary_conditions
Dim i%, cnt1%, cnt2%, neighbor8%(9) '--------------------条件1---------------------
If binary_image(x - 1, y) = 1 Then neighbor8(2) = 1 If binary_image(x - 1, y + 1) = 1 Then neighbor8(3) = 1 If binary_image(x, y + 1) = 1 Then neighbor8(4) = 1 If binary_image(x + 1, y + 1) = 1 Then neighbor8(5) = 1 If binary_image(x + 1, y) = 1 Then neighbor8(6) = 1 If binary_image(x + 1, y - 1) = 1 Then neighbor8(7) = 1 If binary_image(x, y - 1) = 1 Then neighbor8(8) = 1 If binary_image(x - 1, y - 1) = 1 Then neighbor8(9) = 1 cnt1 = 0 cnt2 = 0
'--------------------条件2--------------------- For i = 2 To 9
If neighbor8(i) = 1 Then cnt1 = cnt1 + 1 Next i
'--------------------条件3--------------------- For i = 2 To 9 - 1
If neighbor8(i) - neighbor8(i + 1) = -1 Then cnt2 = cnt2 + 1 Next i
If neighbor8(9) - neighbor8(2) = -1 Then cnt2 = cnt2 + 1 '--------------------条件4---------------------
obtain_necessary_conditions_value.N_P1 = cnt1 obtain_necessary_conditions_value.S_P1 = cnt2
obtain_necessary_conditions_value.Mult_P2P4P6 = neighbor8(2) * neighbor8(4) * neighbor8(6)
obtain_necessary_conditions_value.Mult_P2P4P8 = neighbor8(2) * neighbor8(4) * neighbor8(8)
obtain_necessary_conditions_value.Mult_P2P6P8 = neighbor8(2) * neighbor8(6) * neighbor8(8)
obtain_necessary_conditions_value.Mult_P4P6P8 = neighbor8(4) * neighbor8(6) * neighbor8(8) End Function
'****************************************************************** 'Zhang快速并行细化算法
'输入：待处理的二值图binary_image_buf '输出：细化后的二值图binary_image_buf
'***************************************************************** Function Zhang_thinning_method(binary_image_buf) Dim rows%, cols%, delete_cnt% Dim i%, j%, k%
Dim sign(5000) As position, n1%, n2%, n3%, n4%, n5%, n6% rows = UBound(binary_image_buf, 1) cols = UBound(binary_image_buf, 2)
For k = 1 To 800
'--------------------迭代的前半部分------------------------ For i = 1 To rows For j = 1 To cols
If binary_image_buf(i, j) = 1 Then n1 = obtain_necessary_conditions_value(i, j, binary_image_buf).N_P1 n2 = obtain_necessary_conditions_value(i, j, binary_image_buf).S_P1 n3 = obtain_necessary_conditions_value(i, j, binary_image_buf).Mult_P2P4P6 n4 = obtain_necessary_conditions_value(i, j, binary_image_buf).Mult_P4P6P8
If (n1 >= 2 And n1 <= 6) And n2 = 1 And n3 = 0 And n4 = 0 Then delete_cnt = delete_cnt + 1
sign(delete_cnt).x = i sign(delete_cnt).y = j End If End If Next j Next i
If delete_cnt = 0 Then GoTo finish For i = 1 To delete_cnt
binary_image_buf(sign(i).x, sign(i).y) = 0 Next i delete_cnt = 0
'-------------迭代的后半部分-------------------------------- For i = 1 To rows For j = 1 To cols
If binary_image_buf(i, j) = 1 Then n1 = obtain_necessary_conditions_value(i, j, binary_image_buf).N_P1 n2 = obtain_necessary_conditions_value(i, j, binary_image_buf).S_P1 n3 = obtain_necessary_conditions_value(i, j, binary_image_buf).Mult_P2P4P8 n4 = obtain_necessary_conditions_value(i, j, binary_image_buf).Mult_P2P6P8
If (n1 >= 2 And n1 <= 6) And n2 = 1 And n3 = 0 And n4 = 0 Then delete_cnt = delete_cnt + 1
sign(delete_cnt).x = i sign(delete_cnt).y = j End If End If Next j Next i
If delete_cnt = 0 Then GoTo finish For i = 1 To delete_cnt
binary_image_buf(sign(i).x, sign(i).y) = 0 Next i delete_cnt = 0 Next k finish:
End Function
2.2 窗体部分 Option Explicit
Private Sub Command1_Click()
Dim bin, x1, y1, x2, y2, cnt1%, cnt2% Dim binary_image_buf%(), rows%, cols% Dim i%, j%
Set x1 = zeros(5000, 1) Set y1 = zeros(5000, 1) Set x2 = zeros(5000, 1) Set y2 = zeros(5000, 1)
bin = vbload(App.Path& \’导入二值图 rows = Size(bin).r1(1) cols = Size(bin).r1(2)
ReDimbinary_image_buf(rows, cols), binary_3D_buf(rows, cols, 6) For i = 1 To rows For j = 1 To cols
binary_image_buf(i, j) = bin(i, j).r1(1) Next j Next i
Call Zhang_thinning_method(binary_image_buf)’调用Zhang快速并行细化算法 For i = 1 To rows For j = 1 To cols
If binary_image_buf(i, j) = 1 Then’找出骨架像素点的坐标 cnt1 = cnt1 + 1 x1(cnt1) = i
y1(cnt1) = cols + 1 - j End If
If bin(i, j).r1(1) = 1 Then’找出原二值图为1的点的坐标 cnt2 = cnt2 + 1 x2(cnt2) = i
y2(cnt2) = cols + 1 - j End If Next j Next i
x1 = x1(linspace(1, cnt1, cnt1)) y1 = y1(linspace(1, cnt1, cnt1)) x2 = x2(linspace(1, cnt2, cnt2)) y2 = y2(linspace(1, cnt2, cnt2))
plot x2, y2, \绘制原二值图 hold \
plot x1, y1, \绘制骨架 msetgca, \End Sub
3. 运行结果