基于Delaunay三角網的多邊形特征點提取方法

郭光毅，王新生，李朋澤，鄒 信，徐 亮

（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