Zhang快速并行细化算法

1、Zhang快速并行细化算法最近的研究涉及获取二值图像骨架（图象的中轴线），网上找到许多方法，Zhang快速并行细化算法是出现次数最多的算法，看了几篇博客，又下载了提出这个算法的文献，感觉这个方法很容易理解，编程也容易，其实最后也没花多少时间就成功了，VB6.0编写的程序，用到了函数库MatrixVB，这里分享一下心得。1. 算法简介图1 8邻域系统图1表示以P1为中心的8邻域系统，P2P9代表与P1相邻的8个像素点，1.1 细化步骤1删除同时满足下列条件的边界点: 2N(P1)6; S(P1)=1; P2P4P6=0; P4P6P8=0;其中：N(P1)是P1的非零邻点的个数,S(P1)是以P

2、2，P3，P9，P2为序时这些点的值从0到1变化的次数。1.2 细化步骤2删除同时满足下列条件的边界点: 2N(P1)6; S(P1)=1; P2P4P8=0; P2P6P8=0;以上两步操作构成一次迭代，直至没有点再满足标记条件，这时剩下的点组成区域即为细化后骨架。2. 程序及细化结果用VB6.0编写的程序，用到了函数库MatrixVB（需要的话可以到网上去搜，很老的东西了）。2.1 模块部分这部分包括自定义数据类型（相当于C语言里的结构体），定义了一些函数。Option ExplicitType necessary_conditions 4个条件 N_P1 As Integer S_P1

3、As Integer Mult_P2P4P6 As Integer Mult_P4P6P8 As Integer Mult_P2P4P8 As Integer Mult_P2P6P8 As IntegerEnd TypeType position x As Integer y As IntegerEnd Type*计算4个条件的值输入：P1点的坐标，待处理的二值图binary_image输出：4个条件的值*Function obtain_necessary_conditions_value(x%, y%, binary_image) As necessary_conditionsDim i%,

4、 cnt1%, cnt2%, neighbor8%(9)-条件1-If binary_image(x - 1, y) = 1 Then neighbor8(2) = 1If binary_image(x - 1, y + 1) = 1 Then neighbor8(3) = 1If binary_image(x, y + 1) = 1 Then neighbor8(4) = 1If binary_image(x + 1, y + 1) = 1 Then neighbor8(5) = 1If binary_image(x + 1, y) = 1 Then neighbor8(6) = 1If b

5、inary_image(x + 1, y - 1) = 1 Then neighbor8(7) = 1If binary_image(x, y - 1) = 1 Then neighbor8(8) = 1If binary_image(x - 1, y - 1) = 1 Then neighbor8(9) = 1cnt1 = 0cnt2 = 0-条件2-For i = 2 To 9 If neighbor8(i) = 1 Then cnt1 = cnt1 + 1Next i-条件3-For i = 2 To 9 - 1 If neighbor8(i) - neighbor8(i + 1) =

6、-1 Then cnt2 = cnt2 + 1Next i If neighbor8(9) - neighbor8(2) = -1 Then cnt2 = cnt2 + 1-条件4-obtain_necessary_conditions_value.N_P1 = cnt1obtain_necessary_conditions_value.S_P1 = cnt2obtain_necessary_conditions_value.Mult_P2P4P6 = neighbor8(2) * neighbor8(4) * neighbor8(6)obtain_necessary_conditions_v

7、alue.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输出：细化后的

8、二值图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

9、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

10、_buf).Mult_P4P6P8 If (n1 = 2 And 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

11、 delete_cnt = 0Next kfinish:End Function2.2 窗体部分Option ExplicitPrivate 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 & bin4.txt)

12、导入二值图rows = Size(bin).r1(1)cols = Size(bin).r1(2)ReDim binary_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 jNext iCall 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 jNext ix1 = x1(linspace(1, cnt1, cnt1)