郭光毅,王新生,李朋泽,邹 信,徐 亮
(1.湖北大学 资源环境学院,湖北 武汉 430062)
平面图形形状的特征点提取是形状表达与度量的重要研究方向之一。近年来,众多国内外学者就特征点提取这一问题展开了广泛而深入的研究[1-5]。现有的特征点提取方法主要分为2大类:角点检测法和多边形逼近法。
角点检测从形状理论的观点出发,一般分为2步:①定义一定的准则用以逼近各个边界轮廓点的曲率;②检测轮廓点曲率的极值,从而得到特征点。角点检测法认为物体形状的主要信息集中在方向变化最快的地方,即曲率的极值点[1]。该方法的优点在于不需要重复计算,缺点则是对形状边界轮廓上的细微变化(噪声)极其敏感,轻微的噪声或者边界轮廓的细微扰动都会对曲率逼近造成干扰,从而产生伪特征点。因此,使用角点检测方法对于简单多边形的特征点提取来说快速精确,但对于复杂多边形的特征点提取则无法获得理想效果。
多边形逼近则是从估计理论的观点出发,在一定的准则下求取数字曲线的最佳近似多边形,然后将近似多边形的顶点作为曲线上的特征点[2]。多边形逼近方法虽然避免了复杂的数学计算,可以快速地获得逼近多边形,进而得到特征点,但是由于多边形逼近追求的是一种全局下的最优[2],因此提取的特征点不一定是局部轮廓下的曲率极值点。
本文提出一种基于Delaunay三角网的特征点提取方法,可以用于各类多边形特征点的快速、准确提取。
在形状建模中,多边形的边界表达为点的序列,即C={pi= (xi,yi)|i=1,2,3,…,n},也就是用点集来逼近图形边界线。由于边界点集构建的Delaunay三角网可以保留多边形的边界结构信息,因此Delaunay三角网可以用来提取多边形边界上的特征点。
Delaunay三角网具有如下性质:
①三角网外围边界构建的多边形为点集的凸壳。
②任意三角形的外接圆内不包含其他点(这个性质是Delaunay三角网的定义也称为空外接圆规则)。
③三角形最大程度地保持了均衡,避免狭长形三角形的出现(最大最小角规则)。如果将三角网中的每个三角形的最小角进行升序排列,则Delaunay三角网排列得到的数值最大。从这个意义上讲,Delaunay三角网是“最接近于规则化”的三角网。
④性质②和③保证了Delaunay三角网是最接近等角或等边的三角网。Delaunay三角网具有良好的特性,由于其最大程度地保持了均衡,避免狭长形三角形的出现,是给定区域点集的最佳三角剖分[6]。
多边形的特征点在其局部存在凹凸性,也就是说,可将特征点分为凸特征点和凹特征点,进而又可将多边形的轮廓划分为不同性质的边,两个凸特征点之间的边称为凸边,凸点和凹点之间的边称为凹边,如图1所示,三角形符号表示的点是凸特征点,正方形符号表示的点是凹特征点,③、⑥边为凸边,①、②、④、⑤边则为凹边。
本文提到的Delaunay三角网是使用多边形的边界轮廓点集来构建的,它构成了该多边形形状的剖分结构,其基本单元称为三角形元。对图形剖分的三角形集合,根据每个三角形元的邻接三角形元的个数,可以将三角形分为3类:I类三角形只有1个邻接三角形;II类三角形存在2个邻接三角形;III类三角形存在3个邻接三角形(图2中深色三角形分别代表3类三角形)。根据Delaunay三角网构建规则和性质可知,I类三角形的2个顶点处于两条不同凹凸性的边上,第3个顶点处于不同凹凸性的边的交点处;II类三角形的3个顶点分别处在2条不同凹凸性的边上;III类三角形的3个顶点分别处在3条不同凹凸性的边上。
图1 图形的凹凸特征点和边
图2 三类三角形
基于Delaunay三角网的多边形特征点提取方法为:
1)使用多边形边界轮廓点集来构建 Delaunay三角网(见图3a、b)。
2)用多边形边界轮廓线将构建的Delaunay三角网进行分割,分成多边形内部Delaunay三角网与多边形外部Delaunay三角网,图3c中黑色虚线为多边形轮廓线,内外部Delaunay三角网使用不同符号填充。
3)分别提取多边形内部Delaunay三角网与多边形外部Delaunay三角网中I类三角形的顶点(不与其他三角形共用的顶点),内部Delaunay三角网I类三角形的顶点构成了多边形的凸特征点(图3d),外部Delaunay三角网I类三角形的顶点构成了多边形的凹特征点(图3e)。
4)由于使用原始多边形轮廓线对Delaunay三角网进行裁剪,会使得外部Delaunay三角网出现破碎,从而产出一些伪I类三角形(图4)。因此需要判断这些I类三角形的顶点是否在Delaunay三角网的凸包上,如果在,则不是凹特征点;反之,为凹特征点。
将本文提出的特征点提取方法应用于简单多边形、复杂多边形(含岛屿、自由曲线)、自然图形进行验证。图3展示了本方法的流程,图5分别展示了其内外部Delaunay三角网和提取特征点结果。本方法在提取特征点的同时将特征点的凹凸性准确地区分出来(图3f、图5)。从试验效果来看,本文提出的特征点提取方法是实用的、有效的和可行的。
图3 基于Delaunay三角网的多边形特征点提取方法
图4 伪I类三角形
图5 多边形图形的特征点提取
研究提出了基于Delaunay三角网的多边形特征点提取方法,通过对多组不同类型图形的实例验证,该方法不仅适用于各类多边形,并且对自然图形也具有良好普适性。本方法能够快速有效地提取出多边形的特征点,提取的特征点具有良好的准确性,并且能在提取的过程中判断特征点的凹凸性。
[1]刘晶.叶片数字化检测中的模型配准技术及应用研究[D].西安:西北工业大学,2006
[2]文贡坚,王润生.数字曲线上特征点检测[J].计算机学报,1998,21(6):520-526
[3]Marji M,Siy P.Polygonal representation of digital planar curves through dominant point detection-a nonparametric algorithm[J].Pattern Recognition , 2004 ,37:2 113-2 130
[4]Rannou F,Gregor J.Equilateral polygon approximation of closed contours[J].Pattern Recognition, 1996,29(7):1 105-1 115
[5]张文景,徐晓鸣,丁国骏,等.一种基于曲率提取轮廓特征点的方法[J].上海交通大学学报,1999,33(5): 592-595
[6]孙晓峰,李英成,王淼,等.一种改进的约束Delaunay三角网构建算法及其在快速立体解译平台中的应用[J].遥感信息,2012(1):9-12
[7]王新生,何津,叶小雷,等.图的谱方法的空间目标形状表达研究[J].武汉大学学报:信息科学版,2012(11): 25-28,42
[8]李精忠,艾廷华.以等高线为特征约束的Delaunay TIN的构建[J].地理空间信息,2011,9(5): 26-31
[9]邢海妮,顾庆华,李莉莉.以等高线为特征约束的Delaunay TIN的构建[J].地理空间信息,2009,7(6): 73-75
[10]艾廷华,郭仁忠.基于约束Delaunay结构的道中轴线提取及网络模型建立[J].测绘学报,2000,29(4):348-354