郭光毅，王新生，李朋泽，邹 信，徐 亮

（1.湖北大学 资源环境学院，湖北 武汉 430062）

平面图形形状的特征点提取是形状表达与度量的重要研究方向之一。近年来，众多国内外学者就特征点提取这一问题展开了广泛而深入的研究[1-5]。现有的特征点提取方法主要分为2大类：角点检测法和多边形逼近法。

角点检测从形状理论的观点出发，一般分为2步：①定义一定的准则用以逼近各个边界轮廓点的曲率；②检测轮廓点曲率的极值，从而得到特征点。角点检测法认为物体形状的主要信息集中在方向变化最快的地方，即曲率的极值点[1]。该方法的优点在于不需要重复计算，缺点则是对形状边界轮廓上的细微变化（噪声）极其敏感，轻微的噪声或者边界轮廓的细微扰动都会对曲率逼近造成干扰，从而产生伪特征点。因此，使用角点检测方法对于简单多边形的特征点提取来说快速精确，但对于复杂多边形的特征点提取则无法获得理想效果。

多边形逼近则是从估计理论的观点出发，在一定的准则下求取数字曲线的最佳近似多边形，然后将近似多边形的顶点作为曲线上的特征点[2]。多边形逼近方法虽然避免了复杂的数学计算，可以快速地获得逼近多边形，进而得到特征点，但是由于多边形逼近追求的是一种全局下的最优[2]，因此提取的特征点不一定是局部轮廓下的曲率极值点。

本文提出一种基于Delaunay三角网的特征点提取方法，可以用于各类多边形特征点的快速、准确提取。

1 方法描述

在形状建模中，多边形的边界表达为点的序列，即C={pi= (xi，yi)|i=1，2，3，…，n}，也就是用点集来逼近图形边界线。由于边界点集构建的Delaunay三角网可以保留多边形的边界结构信息，因此Delaunay三角网可以用来提取多边形边界上的特征点。

1.1 Delaunay三角网

Delaunay三角网具有如下性质：

①三角网外围边界构建的多边形为点集的凸壳。

②任意三角形的外接圆内不包含其他点（这个性质是Delaunay三角网的定义也称为空外接圆规则）。

③三角形最大程度地保持了均衡，避免狭长形三角形的出现（最大最小角规则）。如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网排列得到的数值最大。从这个意义上讲，Delaunay三角网是“最接近于规则化”的三角网。

④性质②和③保证了Delaunay三角网是最接近等角或等边的三角网。Delaunay三角网具有良好的特性，由于其最大程度地保持了均衡，避免狭长形三角形的出现，是给定区域点集的最佳三角剖分[6]。

1.2 特征点提取原理

多边形的特征点在其局部存在凹凸性，也就是说，可将特征点分为凸特征点和凹特征点，进而又可将多边形的轮廓划分为不同性质的边，两个凸特征点之间的边称为凸边，凸点和凹点之间的边称为凹边，如图1所示，三角形符号表示的点是凸特征点，正方形符号表示的点是凹特征点，③、⑥边为凸边，①、②、④、⑤边则为凹边。

本文提到的Delaunay三角网是使用多边形的边界轮廓点集来构建的，它构成了该多边形形状的剖分结构，其基本单元称为三角形元。对图形剖分的三角形集合，根据每个三角形元的邻接三角形元的个数，可以将三角形分为3类：I类三角形只有1个邻接三角形；II类三角形存在2个邻接三角形；III类三角形存在3个邻接三角形（图2中深色三角形分别代表3类三角形）。根据Delaunay三角网构建规则和性质可知，I类三角形的2个顶点处于两条不同凹凸性的边上，第3个顶点处于不同凹凸性的边的交点处；II类三角形的3个顶点分别处在2条不同凹凸性的边上；III类三角形的3个顶点分别处在3条不同凹凸性的边上。

图1 图形的凹凸特征点和边

图2 三类三角形

1.3 特征点提取方法

基于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三角网的凸包上，如果在，则不是凹特征点；反之，为凹特征点。

2 试验验证

将本文提出的特征点提取方法应用于简单多边形、复杂多边形（含岛屿、自由曲线）、自然图形进行验证。图3展示了本方法的流程，图5分别展示了其内外部Delaunay三角网和提取特征点结果。本方法在提取特征点的同时将特征点的凹凸性准确地区分出来（图3f、图5）。从试验效果来看，本文提出的特征点提取方法是实用的、有效的和可行的。

图3 基于Delaunay三角网的多边形特征点提取方法

图4 伪I类三角形

图5 多边形图形的特征点提取

3 结 语

研究提出了基于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