Zhang快速并行细化算法

Zhang快速并行细化算法最近的研究涉及获取二值图像骨架（图象的中轴线），网上找到许多方法，Zhang快速并行细化算法是出现次数最多的算法，看了几篇博客，又下载了提出这个算法的文献，感觉这个方法很容易理解，编程也容易，其实最后也没花多少时间就成功了，VB6.0编写的程序，用到了函数库MatrixVB，这里分享一下心得。1.算法简介图18邻域系统图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语言里的结构体），定义了一些函数。OptionExplicitTypenecessary_conditions'4个条件N_P1AsIntegerS_P1AsIntegerMult_P2P4P6AsIntegerMult_P4P6P8AsIntegerMult_P2P4P8AsIntegerMult_P2P6P8AsIntegerEndTypeTypepositionxAsIntegeryAsIntegerEndType'**************************************************************'计算4个条件的值'输入：P1点的坐标，待处理的二值图binary_image'输出：4个条件的值'**************************************************************Functionobtain_necessary_conditions_value(x%,y%,binary_image)Asnecessary_conditionsDimi%,cnt1%,cnt2%,neighbor8%(9)'--------------------条件1---------------------Ifbinary_image(x-1,y)=1Thenneighbor8(2)=1Ifbinary_image(x-1,y+1)=1Thenneighbor8(3)=1Ifbinary_image(x,y+1)=1Thenneighbor8(4)=1Ifbinary_image(x+1,y+1)=1Thenneighbor8(5)=1Ifbinary_image(x+1,y)=1Thenneighbor8(6)=1Ifbinary_image(x+1,y-1)=1Thenneighbor8(7)=1Ifbinary_image(x,y-1)=1Thenneighbor8(8)=1Ifbinary_image(x-1,y-1)=1Thenneighbor8(9)=1cnt1=0cnt2=0'--------------------条件2---------------------Fori=2To9Ifneighbor8(i)=1Thencnt1=cnt1+1Nexti'--------------------条件3---------------------Fori=2To9-1Ifneighbor8(i)-neighbor8(i+1)=-1Thencnt2=cnt2+1NextiIfneighbor8(9)-neighbor8(2)=-1Thencnt2=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_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)EndFunction'******************************************************************'Zhang快速并行细化算法'输入：待处理的二值图binary_image_buf'输出：细化后的二值图binary_image_buf'*****************************************************************FunctionZhang_thinning_method(binary_image_buf)Dimrows%,cols%,delete_cnt%Dimi%,j%,k%Dimsign(5000)Asposition,n1%,n2%,n3%,n4%,n5%,n6%rows=UBound(binary_image_buf,1)cols=UBound(binary_image_buf,2)Fork=1To800'--------------------迭代的前半部分------------------------Fori=1TorowsForj=1TocolsIfbinary_image_buf(i,j)=1Thenn1=obtain_necessary_conditions_value(i,j,binary_image_buf).N_P1n2=obtain_necessary_conditions_value(i,j,binary_image_buf).S_P1n3=obtain_necessary_conditions_value(i,j,binary_image_buf).Mult_P2P4P6n4=obtain_necessary_conditions_value(i,j,binary_image_buf).Mult_P4P6P8If(n1=2Andn1=6)Andn2=1Andn3=0Andn4=0Thendelete_cnt=delete_cnt+1sign(delete_cnt).x=isign(delete_cnt).y=jEndIfEndIfNextjNextiIfdelete_cnt=0ThenGoTofinishFori=1Todelete_cntbinary_image_buf(sign(i).x,sign(i).y)=0Nextidelete_cnt=0'-------------迭代的后半部分--------------------------------Fori=1TorowsForj=1TocolsIfbinary_image_buf(i,j)=1Thenn1=obtain_necessary_conditions_value(i,j,binary_image_buf).N_P1n2=obtain_necessary_conditions_value(i,j,binary_image_buf).S_P1n3=obtain_necessary_conditions_value(i,j,binary_image_buf).Mult_P2P4P8n4=obtain_necessary_conditions_value(i,j,binary_image_buf).Mult_P2P6P8If(n1=2Andn1=6)Andn2=1Andn3=0Andn4=0Thendelete_cnt=delete_cnt+1sign(delete_cnt).x=isign(delete_cnt).y=jEndIfEndIfNextjNextiIfdelete_cnt=0ThenGoTofinishFori=1Todelete_cntbinary_image_buf(sign(i).x,sign(i).y)=0Nextidelete_cnt=0Nextkfinish:EndFunction2.2窗体部分OptionExplicitPrivateSubCommand1_Click()Dimbin,x1,y1,x2,y2,cnt1%,cnt2%Dimbinary_image_buf%(),rows%,cols%Dimi%,j%Setx1=zeros(5000,1)Sety1=zeros(5000,1)Setx2=zeros(5000,1)Sety2=zeros(5000,1)bin=vbload(App.Path&\bin4.txt)’导入二值图rows=Size(bin).r1(1)cols=Size(bin).r1(2)ReDimbinary_image_buf(rows,cols),binary_3D_buf(rows,cols,6)Fori=1TorowsForj=1Tocolsbinary_image_buf(i,j)=bin(i,j).r1(1)NextjNextiCallZhang_thinning_method(binary_image_buf)’调用Zhang快速并行细化算法Fori=1TorowsForj=1TocolsIfbinary_image_buf(i,j)=1Then’找出骨架像素点的坐标cnt1=cnt1+1x1(cnt1)=iy1(cnt1)=cols+1-jEndIfIfbin(i,j).r1(1)=1Then’找出原二值图为1的点的坐标cnt2=cnt2+1x2(cnt2)=iy2(cnt2)=cols+1-jEndIfNextjNextix1=x1(linspace(1,cnt1,cnt1))y1=y1(linspace(1,cnt1,cnt1))x2=x2(linspace(1,cnt2,cnt2))y2=y2(linspace(1,cnt2,cnt2))plotx2,y2,k.,markersize,1’绘制原二值图holdonplotx1,y1,r*,markersize,1’绘制骨架msetgca,color,wEndSub3.运行结果