基于Delaunay三角网的骨架提取算法研究_图文

1、第28卷第4期2006年8月舰 船 科 学 技 术SH I P SC I E NCE AND TEC HNOLOGY Vo.l 28,No .4Aug .,2006文章编号:1672-7649(200604-0106-03基于Delaunay 三角网的骨架提取算法研究倪 健1,董 强2(1.河北工程大学,河北邯郸056038;2.中国船舶重工集团公司第七一八研究所,河北邯郸056027摘 要: 对目标图像提取其骨架,在目标检测、图像编码等计算机视觉、图像处理与模式识别领域有着广泛的应用。本文提出了一种基于D elaunay 三角网的骨架提取改进算法,给出了实验效果。关键词: 图像处理;Dela

2、unay 三角网;骨架;中图分类号: TP391 文献标识码: AThe research of skeletonization algorith m based on D elaunay triangulationN I Jian 1,DONG Q iang2(1.H ebeiUn i v ersity of Eng i n eer i n g ,H andan 056038,Ch i n a ;2.The 718Research Institute of CSI C ,H andan 056027,ChinaAbst ract : The ske leton o f ob ject i m

3、 age is ex tracted have been app lied to co m puter v ision ,i m age processi n g and patter n recogn iti o n inc l u cling ob j e ct detection ,i m age code et a1.Th is paper presents a ne w ske l eton ization algo rithm based on de launay triangulati o n ,an experi m ent is g iven to de m onstrate

4、 t h e effecti v eness of t h e a l g orit h m here .K ey w ords : i m age processi n g ;De launay triangu lation ;ske leton收稿日期:2006-06-21基金项目:邯郸市科技攻关项目(200510301-30 引 言骨架是图像几何形态的一种重要的拓扑描述,由一些表明物体大致形状的细线组成。利用骨架表示原始图像,可以在保持图像重要拓扑特征的前提下,减少图像中的冗余信息。因此,骨架提取算法被广泛应用于生物形状描述、模式识别、视觉检测以及图像压缩编码等领域。骨架一般应具有以下性

5、质1:(1骨架宽度应为一个像素;(2骨架要尽可能穿过物体的 中部 ;(3骨架应保持物体的拓扑架构。近年来人们提出了很多骨架化算法,本文根据Delaunay 三角网思想改进了骨架线提取算法,即采用较为简单的三角形切割方法得到运动人体骨架线,有效地区分了轮廓内部和外部,压缩了信息,更利于后期处理。1 基于数学形态学的骨架提取方法数学形态学以图像的形态特征为研究对象,它的主要内容是设计一整套概念、变换和算法,用来描述图像的基本特征和基本结构,也就是描述图像中的元素与元素、部分与部分间的关系。数学形态学的数学基础和所用语言是集合论,它把图像看成是点的集合。数学形态学的长处在于能定量地描述几何结构,应用

6、数学形态学可以简化图像的数据,但仍保持他们的基本形状特征2。生成图像中一个物体骨架的一种方法可通过沿某方向反复删除物体内、外轮廓线上的像素来完成。这里假定处理的图像为二值图像,称轮廓线上的点为 边缘点 ,在下面的讨论中假设背景为黑色(0,前景(人体为白色(1,物体表现为图像平面上第一个8连通区域。被处理点及其相邻像素构成一个3!3第4期倪 健,等:基于Delaunay 三角网的骨架提取算法研究的区域。若一个位置的值为1则称其为白色,否则称黑点。若从一个位置出发到达另一位置所经过的路径均为白点,则称2个位置是连通的。骨架抽取的算法思想虽然较为简单,即反复地沿着某一方向删除物体的内、外轮廓上的边缘

7、点,直到满足骨架性质为止,但实现起来却有许多细节要特别注意。算法的任何不完备都将直接导致抽取的失败。2 通过De launay 三角网得出骨架多边形骨架线提取的关键在于探测多边形内部到边界线上的等距离点集,在几何特征上属于空间邻近关系的探测问题,而计算几何中的De launay 三角网是一种较成熟的支持模型3,具有其他算法模型无可比拟的优势。2.1 多边形内部约束Delaunay 三角网构架4计算几何研究的Delaunay 三角网从数学理论出发,严格符合Delaunay 三角网的性质定义。当应用到实际领域时,需针对其特殊性对算法进行改进。当多边形目标以群点角色直接构建三角网时,在多边形覆盖区域

8、以边界离散点为运算对象建立约束Delaunay 三角网,约束条件为三角形不能穿越多边形的边界。对多边形内部的三角形,根据邻接三角形的数目,进一步细分为三类:类三角形是三角网中的边界节点,其3个顶点中有一个顶点作为骨架线的端点;#类三角形是三角网中的跨接三角形,是骨架线的骨干结构,描述了骨架线的延展方向;类三角形作为骨架分支的交汇处,是向3方向伸展的出发点。2.2 三角网条件序贯遍历及骨架线树结构的建立对于骨架线的提取,可仿照栅格结构中的扩张算子来设计三角网结构中的扩张算子。由于De launay 三角网在几何特征上具有最邻近连接的特点,三角形的边可以看作是多边形边界上的一点到其他边界点的邻近跨

9、接,三角形跨接边的中点可以认为是多边形在该局部区域的片断中心。将邻接的1批三角形跨接边的中点顺序连接起来,便可以反映多边形在一维特征上的延展趋势,即骨架线。其具体的算法思想如下:首先,建立2个集合,即遍历三角形集TR I和分支三角形集BRANC H ,分别用来顺序记录遍历的所有三角形和顺序记录遍历的所有分支三角形(即类三角形。由任意一个类三角形出发,将这个三角形放入BRANC H 集合中,同时沿三角形三边方向进入邻接的三角形5。 (1如果当前考察的三角形是#类三角形,则继续行进的方向就是惟一的,只需将该三角形放入TR I集合中;(2如果当前考察的三角形是类三角形,则继续行进的方向就有2个,这样

10、的分支三角形既要放入TR I集合中,同时也要放入BRANC H 栈结构中,然后继续遍历;(3如果当前考察的三角形是类三角形,那么表示这个三角网的一个分支已经遍历完成,将该三角形放入TRI集合中。重复上述过程,考察BRANCH 栈是否为空,如果栈非空,则取出栈顶的三角形,直至BRANCH 栈中元素为空,三角网遍历结束,得到三角网中所有三角形元素之间的二叉树结构。图1(a表达了三角网内的遍历过程;图1(b为记录对应的二叉树结构。二叉树的叶子节点对应着多边形骨架线的一个端点,其他节点对应着多边形骨架线的分支节点,节点之间的层次关系则描述了骨架线的主干与分支间的嵌套结构。图1 记录三角网遍历过程的二叉

11、树结构2.3 主骨架线的提取上述方法得到的骨架线是二叉树结构,而主骨架线是沿着主延伸方向的线性结构。为此,还需要对按照上述方法提取的骨架线做出取舍,以提取惟一确定的主骨架线。图2描述了骨架线某个分支处的情况。从图2(a可以看到,多边形的骨架线在 P 1P 2P 3处产生分叉,是典型的二叉树结构。根据Gesta lt 连续性原则,为了保持人们视觉上的连续性和完整性,较为粗壮的R 分支应作为主延展方向。这样,L 分支被裁减,得到图2(b中惟一确定的多边形延展方向。基于上述的分析,对主骨架线的提取方法如下。在骨架线分支处,以分支部分的面积作为选取标准,舍弃面积较小的分支,保留面积较大的分支,直至终止

12、于多边形的2个节点,得到主骨架线。对于图1%107%舰 船 科 学 技 术第28 卷图2 消减分支示意图(a中的多边形而言,主骨架线上的节点依次为L& A&B&C&H(即被虚线圈住的部分,得到的多边形主骨架线即为图1(b中加粗的线段。从图1可以看到,得到的主骨架线可以反映出该多边形的形态特征和主延伸方向。多边形的形状分析是属于空间认知的问题,也是一个不确定性问题。这里选取图2中R分支的依据是因为R分支更加粗壮,即R分支的面积比L分支的面积要大。换言之,是将分支部分的面积作为选取标准。这是因为在视觉认知中,吸引注意力的是图形的主体。选取标准要根据具体需求来确定,并不是惟一的。同时,如果各部分面积

13、势均力敌,也会难以做出确定的选择,这说明,主骨架线只能针对线性结构延展十分明显的多边形,对于像圆形、五角星形等均匀分布的多边形,谈论主骨架线是没有意义的。3 本文采用的骨架线提取方法由于De launay三角形方法无法区分轮廓内部还是外部,因此本文在此思想的基础上采用了一种按逆时针遍历轮廓,找到最小的夹角,取对应两边的中线点,切割三角形,删除这个夹角点,继续递归,直到多边形为三角形为止的方法。对于中线点的连接,是采用记录被切割的三角形,在回复骨架时按照递归的方法寻找邻边三角形。其中,依据点与三角形内角和为360来判断某点是否在被切割三角形内。 用本文提出的骨架线算法,可得到各关键帧的骨架,其效

14、果如图3所示。说明本算法简单、高效,具有 很强的实用性和优越性。图3 提取骨架线效果4 结 语数学形态学在国外已被实际应用于机器视觉、模式识别、图像处理等领域。目前国内也有不少学者研究了基于经典形态学的骨架提取算法,获得了较好的结果。本文研究的骨架提取算法,是经典数学形态学骨架提取方法的拓广和改进,因此有着广泛的应用前景。参考文献:1 严涛.基于图像的树木造型方法的研究D.中国科学院软件研究所,2000.2 BLO C H I.M a itre Fuzzy m athe m atical m orpholog i es:acomparati ve studyJ.P attem R ecogn iti on,1995,28(9: