一种基于截面序列的线形图骨架提取算法

一种基于截面序列的线形图骨架提取算法

1节点区畸变、节点位置与节点位置的连接近年来，线性图的识别技术一直是研究的重点。在识别之前，通常需要获取具有线条的骨架（也称为中心线），以减少后续处理的数据和模型特征的提取，通常需要获取具有线条提取的结构（也称为细节）。骨骼提取结果的质量直接影响识别的精度。我们认为，衡量骨骼提取质量的基准不仅包括骨架的精度，还包括结构与结构关系的准确性。然而，许多骨提取算法都存在一个缺点。节点严重变形（这里，通常称为节点的点、点、角点区和分支区的总称）。骨骼中包含许多多余的螺钉和线性骨，通常分为几个孤立的段。图1显示了传统改进算法的改进结果。如图所示。实验结果表明，基于这种结构，很难获得正确的识别结果。在分析线性图时，提取图中节点区域时，确定节点的精确位置。如果节点完成，整个图的结构关系就基本上固定（这个效果类似于人体关节）。在这两个节点之间提取骨架并不困难，所有框架都将获得接收到的节点信息。我们认为节点信息对于保存节点信息非常重要。因此，我们提出了一种高质量骨架提取算法，以注意保持节点信息。基本方法是通过间接方法提取每个节点，正确确定节点的结构关系，然后确定哪个线素嵌入该节点和框架的各个节点，并建立完整的骨架。2轮廓线上的控制板设计本算法适用于黑白二值图像.约定图像左上角像素点为坐标原点,X轴正方向水平指向左,Y轴正方向竖直指向下.设图像在X轴方向有Width个像素宽,在Y轴方向有Height个像素高,所以图中任一像素点可记为p(x,y),其中x∈{0,1,\:,Width-1},y∈{0,1,\:,Height-1}.不失一般性,我们假定背景为白色,背景像素点取值为“0”;有图像素点为黑色,取值为“1”——即当p(x,y)=0时,p为背景像素点;当p(x,y)=1时,p为有图像素点.定义1.设I为图像中所有像素点的集合.K是I的子集,K={p1,p2,\:,pi,\:,pn},pi=1(i=1,2,\:,n).如果K满足以下两个条件,则称K为I的一个连通体.(1)K中的任意两像素点是连通的.(2)不属于K的任一值为1的像素点与K中的任一像素点不是连通的.对于线状图,一个连通体是一条线素或多条线素相交的产物.定义2.设像素点p(x,y)=1,如果在p的4邻域内存在值为零的点,则称p为轮廓像素点.构造4邻域轮廓像素点判别子e4(x,y),其逻辑表达式如下:e4(x,y)=p(x,y)∩{¯p(x,y-1)∪¯p(x-1,y)∪¯p(x,y+1)∪¯p(x+1,y)}(1)e4(x,y)=p(x,y)∩{p(x,y−1)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯∪p(x−1,y)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯∪p(x,y+1)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯∪p(x+1,y)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯}(1)记p(-1,y)=0,p(x,-1)=0,p(Width,y)=0,p(x,Height)=0.当e4(x,y)=1时p(x,y)为轮廓像素点.一个连通体的所有轮廓像素点集合构成这个连通体的轮廓线,轮廓线可分为外轮廓和内轮廓.一个连通体仅有一条外轮廓,可以有零至多条内轮廓.所有轮廓线都是8邻域封闭的环.约定:设线状图中,共有N条轮廓线,每条轮廓线以值为1的像素点始终在右侧的方式进行跟踪,即对外轮廓顺时针跟踪,对内轮廓逆时针跟踪,得到N个有序轮廓像素点集合,即每条轮廓线由有序的轮廓像素点所描述.定义3.设第j条轮廓中有nj个轮廓像素点,则第j条轮廓可记为:Pj={pj(1),pj(2),\:,pj(nj)},(1≤j≤N),我们称pj(i+1)是pj(i)的后继,pj(i-1)是pj(i)的前趋,并分别记作pj(i+1)=succ(pj(i))和pj(i-1)=pred(pj(i)).定义4.轮廓线上一点处指向线素内部的法矢方向称为轮廓线在该点处的内法矢方向.定义5.设a为连通体K上的任一轮廓像素点,→vv⃗为a点处轮廓线的内法矢方向.以a为起点,沿方向→vv⃗经过4邻域直线路径遇到第一个背景像素点止,我们定义遇到背景像素点之前的最后一个值为“1”的点为a的对面像素点b,记作b=opp(a).注意:a的对面像素点是唯一的,但b可以是多个像素点的对面像素点,也可以不是任何像素点的对面像素点.定义6.设P为连通体K的全体轮廓像素点的集合,p,q∈P,p≠q,(p,q)是一个点对.如果(p,q)满足以下逻辑表达式,我们就称其为K在p和q点处的截面,记作C(p,q):(p=opp(q)∩D(opp(p),q)<Τh1)∪(q=opp(p)∩D(opp(q),p)<Τh1)=1(2)(p=opp(q)∩D(opp(p),q)<Th1)∪(q=opp(p)∩D(opp(q),p)<Th1)=1(2)其中:D(a,b)为像素点a与b之间的距离(不含a,b),单位为像素pixel;Th1为常数,通常取2.注意:一个轮廓像素点可以属于多个截面,此现象常发生在线素的高曲率区域.不难想象,对于线状图,若C(p,q)成立,则p,q连线与线素在p点处的走向近似正交.定义7.设C(=C(p,q))和C′(=C(p′,q′))是截面,如果p∈{p′,succ(p′)}且q∈{q′,pred(q′)}且C≠C′,则称C是C′的后继,记为C=next(C′),并称C′是C的前趋,记为C′=last(C).定义8.设L为一系列截面的有序集合,L=(C0,C1,\:,Ck-1)(k>0),如果任意一对截面Ci和Ci+1(i=0,1,\:,k-2)满足Ci+1=next(Ci)(Ci=last(Ci+1))且next(Ck-1)∈{ue001φ,C0}的关系,我们称L为截面序列,C0为L的头,Ck-1为L的尾,分别记为C0=head(L),Ck-1=tail(L).不难想象,如果某一连通体的某区域为截面序列,则该区域两侧的轮廓线可以看作是近似平行的(或等距的),那么在线状图中,这些截面序列集合称为线状区域,而由不属于线状区域的点所组成的区域,我们称为非线性区域,或称节点区.节点区通常位于线素的端点处、折点处、交点处、分支点处.3提取形态区域本算法的技术路线是:首先对二值化的线状图进行轮廓提取并跟踪;然后找出全部截面序列并提取线状区域;通过线状区域反求出非线状区域并分析其拓扑结构;最后依据非线状区域的拓扑结构对满足光滑性条件的截面序列进行归并,并提取完整骨架.3.1轮廓点的提取将定义轮廓点的逻辑表达式式(1)作交换如下:e4(x,y)={p(x,y)∩[¯p(x,y-1)[p(x,y−1)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯∪¯p(x,y+1)]}p(x,y+1)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯]}∪{p(x,y)∩[¯p(x-1,y)[p(x−1,y)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯∪¯p(x+1,y)]}=V(x,y)∪Η(x,y)(3)p(x+1,y)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯]}=V(x,y)∪H(x,y)(3)其中:V(x,y)是竖直方向的运算结果,H(x,y)为水平方向的运算结果.根据式(3),我们可将轮廓点提取分解为水平和垂直两次独立的操作来完成.图像按行描述如下:P=[h1,h2,\:,hn]T其中,hi表示第i行像素点,则竖直方向的操作可记为:Vi=hi∩(¯hi-1(hi−1¯¯¯¯¯¯∪¯hi+1)hi+1¯¯¯¯¯¯)可以看出,在竖直方向上,轮廓点的判断只与当前行、上一行、下一行的数据相关.类似的,水平方向上可通过像素行的左移和右移得到h-i和h+i,则水平方向上的操作可记为:Ηi=hi∩(¯h-i∪¯h+i)Hi=hi∩(h−i¯¯¯¯∪h+i¯¯¯¯)因此,第i行像素点的轮廓点提取结果为e4i=Vi∪Hi,而整图的轮廓点阵列为:Em.n=[e41,\:,e4i,\:,e4n]Τ=[V1∪Η1,\:,Vi∪Η2,\:,Vn∪Ηn]Τ(4)得到轮廓点阵列后,可依据相邻点定义对轮廓线进行跟踪,得到有序轮廓点列,跟踪过程中应始终遵循“值为1的点在右侧”的原则,轮廓线结果可用Freeman链码的形式描述.许多文献对跟踪算法均有描述,这里不再赘述.3.2截面序列集合的消除经过轮廓提取与跟踪,我们可得到若干条有序轮廓点组成的封闭轮廓线.线状区域提取过程如下:步骤1:依据定义5使用DDA算法,求得每一轮廓点的对面像素点.步骤2:依据定义6,求出所有可能的截面,构成线状图全部截面的集合F.步骤3:在截面集合F中,以任意截面为起点,找出满足定义7的前趋和后继,并继续找出前趋的前趋和后继的后继,依此类推,直至不再有前趋和后继,所找出的截面构成一个截面序列,将此截面序列中的截面从集合F中删除.依此方法,找出集合F中的所有可能的截面序列,构成截面序列集合G.注意,在寻找后继(或前趋)的过程中,一个截面C(p,q)可能有多个满足定义7的后继(或前趋),如图2所示共存在5种情况.在这5种情况中,我们取C′(p′,q′)为C(p,q)的后继(或前趋),并将图中其余截面从集合F中删除.步骤4:在截面序列集合G中,可能会出现如图3所示多个截面序列相交的现象.这种情况是非法的.我们计算每个截面序列中任一截面的宽度,记为截面序列的宽度.在两个相交的截面序列中,我们认为宽度最短的截面序列合法,并将所有非法截面序列从集合G中删除.步骤5:在本算法中,我们希望每个截面序列都尽可能的长,使节点区域尽可能小,这样有利于节点的精确定位和分析节点的拓扑结构,但在实际图像中,线状图的轮廓线通常并不“平坦”,常存在许多“噪声”(小的凸起或凹坑),如图4所示,这些“噪声”常使本可构成同一线状区域的截面序列分成若干小段.下面我们给出消除“噪声”、合并截面序列的判据.设集合G中的两截面序列Lm,Ln的头(或尾)分别为截面Cm(pm,qm),Cn(pn,qn),如图4.如果①D(pm,qm)≈D(pn,qn);②pm与pn连线近似平行于qm与qn连线;③pm,pn之间的轮廓点数与qm,qn之间的轮廓点数之差小于D(pm,pn)/2均成立,我们就将Lm与Ln合并为一个截面序列.将集合G中的可以合并的截面序列加以合并后,所得到的集合G即为线状区域集合.3.3节点区域的提取在轮廓点集中,不属于线状区域集合G的点即为组成非线状区域的点,但这些点是无序的,无组织的,我们称这些点为非线状区域点.节点区域提取就是要将这些非线状区域点以节点区域为单位组织起来,理清哪些非线性区域点属于哪个节点区域.设非线状区域点集合为W,从中任取一点a,以a为起点沿轮廓线顺时针(或逆时针)跟踪,直至遇到第一个截面序列L1中的一点p1,设p1与q1组成L1的端截面C1,那么从p1跳至q1,从q1开始,继续沿轮廓线顺时针(或逆时针)跟踪至下一个截面序列L2中的一点p2,依次类推,如图5所示,必能跟踪至某一截面序列Ln,当再以Ln中的qn继续跟踪时,将回到起点a,至此节点区域A提取完毕,由跟踪所经过的非线状区域点和截面序列端截面所围区域即为节点区域A.从集合W中删除组成节点区域A的非线状区域点后,可开始下一个节点区域的提取,直至将W中包含的所有节点区域提取完为止.定义9.我们把与节点区域S相连接的线状区域的个数称为节点S的度.(2)节点精确定位如图6所示,线状区域Lk1,Lk2,Lk3相交于节点区域S.理论上,节点区域S的精确位置应该是距离Lk1,Lk2,Lk3的轴线Vk1,Vk2,Vk3最近的点.为此,我们给出估计值F为:F=1nkn∑k=k1(Vk,Wk)|Vk∥Wk|(5)其中:n为节点区域S的度;Vk是Lk的轴线在靠近S处的切矢量;Wk是节点区域S中一点s与Lk端截面中点的连线矢量;(Vk,Wk)是Vk,Wk的内积;|Vk|,|Wk|是矢量Vk,Wk的模长.易知,在S中的点s越靠近Vk(k=k1,\:,kn)估计值F越大,所以使估计值F最大的点s(x,y)即为节点S的精确位置.(3)节点区域的聚合如图7(a)所示,某些线状区域是多余的,它将本可能成为一个节点的区域分成两部分.我们应对每个线状区域加以判断,看其是否属于多余,看节点是否可以聚合.我们规定,当两节点间距离D小于线状区域宽度W时,两节点应合并,如图7(a);否则,两节点不应合并,如图7(b).3.4同源线素的归并过程在线状图中,一个圆弧与直线相交,交点将圆弧分为两段线状区域a,b.这里我们称像a,b这样本应属于同一母线素的一组线状区域互为同源线素.为使所提取的骨架简洁、完整,我们需要对互为同源线素的一组线状区域加以归并,以利于对同源线素提取一根完整骨架.通过节点提取我们获得一些节点拓扑信息,如节点的度及哪些线状区域与此节点相连接等.进一步分析节点拓扑结构的过程实际上就是同源线素的归并过程.节点拓扑结构分析的目的就在于明确哪些线素相交于此和一条线素通过哪些交点.对于线状图,如果a,b互为同源线素,它们应具有以下性质:(1)a,b的线宽近似相等.(2)a,b在与节点相连处具有光滑连接性质,光滑性可由a,b在节点连接处的轴线切向夹角来决定,通常夹角小于某一阈值θ即可认为光滑.在程序中我们取经验值θ=10°(3)一个线状区域在一个节点处最多只有一个另外的线状区域与之构成同源线素.3.5线素的骨架提取每个线状图都是由若干线素构成,通过以上的线状区域和节点的提取及对同源线素的归并过程,现在线素的骨架提取变得很容易.每条线素由节点和互为同源线素的线状区域交替连接而成,线素两端均为节点,示意图见图8.对于线状区域,其中心线即为该段的骨架,每段之间以通过节点精确位置的折线连接,即可构成线素的完整骨架,骨架的两端点由端节点的精确位置决定.4算法的基本思想我们用C语言实现了本算法,其骨架提取效果可参见图9.从原始图像、骨架提取结果、传统细化算法细化结果的比较,我们可以看出基于节点的骨架提取算法明显优于细化算法,具有高质量、高精度、结果简洁,不失真的特点.两种算法的比较:(1)本算法骨架提取完整,包含信息丰富.每一条骨架都是一个完整的直线、圆弧,或是由直线与圆弧光滑连接所组成的复合线素.而传统细化算法得到的是多条线段,在后续识别之前仍需进行短线归并,但这些短线发生了严重的畸变,给归并造成了困难.用本算法得到骨架后,再进行直线、圆弧等基本线素的识别将变得容易且准确,另外本算法提取结果中,既包含了线素的精确位置信息、线宽信息,也包含了线素间的拓扑信息和节点的拓扑信息,是进行后续复杂关系识别的基础.(2)节点拓扑结构(如“T”型、“X”型或更复杂的相交关系)被正确地保留,节点位置精确.如图9(a)居中偏上有一个圆弧与两条直线近似相交的节点,但事实上并不是一个交点,而是两两相交,经本算法提取骨架(如图9(e)),正确地反映了原图本意,而细化结果则出现了明显的畸变.同时细化算法使用腐蚀的原理,无法控制节点位置;而本算法通过相邻线状区域的轴线,经严格地分析计算确定节点位置,所以具有高精度.(3)本算法不产生寄生短线.对于细化算法,在“T”字型、“X”字型或更复杂的相交情况下,都会出现寄生短线,将会给后续识别造成麻烦,见图9(f).而对于本算法,则不会出现这种情况.(4)本算法对噪声有较好的抑制作用.这里噪声指原图上就有的或扫描时产生的斑点或毛刺.使用细化算法时,部分噪声被强化,这就是为什么在