基于Delaunay三角網(wǎng)的多邊形特征點(diǎn)提取方法

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

（1.湖北大學(xué) 資源環(huán)境學(xué)院，湖北 武漢 430062）

平面圖形形狀的特征點(diǎn)提取是形狀表達(dá)與度量的重要研究方向之一。近年來，眾多國內(nèi)外學(xué)者就特征點(diǎn)提取這一問題展開了廣泛而深入的研究[1-5]?，F(xiàn)有的特征點(diǎn)提取方法主要分為2大類：角點(diǎn)檢測法和多邊形逼近法。

角點(diǎn)檢測從形狀理論的觀點(diǎn)出發(fā)，一般分為2步：①定義一定的準(zhǔn)則用以逼近各個(gè)邊界輪廓點(diǎn)的曲率；②檢測輪廓點(diǎn)曲率的極值，從而得到特征點(diǎn)。角點(diǎn)檢測法認(rèn)為物體形狀的主要信息集中在方向變化最快的地方，即曲率的極值點(diǎn)[1]。該方法的優(yōu)點(diǎn)在于不需要重復(fù)計(jì)算，缺點(diǎn)則是對(duì)形狀邊界輪廓上的細(xì)微變化（噪聲）極其敏感，輕微的噪聲或者邊界輪廓的細(xì)微擾動(dòng)都會(huì)對(duì)曲率逼近造成干擾，從而產(chǎn)生偽特征點(diǎn)。因此，使用角點(diǎn)檢測方法對(duì)于簡單多邊形的特征點(diǎn)提取來說快速精確，但對(duì)于復(fù)雜多邊形的特征點(diǎn)提取則無法獲得理想效果。

多邊形逼近則是從估計(jì)理論的觀點(diǎn)出發(fā)，在一定的準(zhǔn)則下求取數(shù)字曲線的最佳近似多邊形，然后將近似多邊形的頂點(diǎn)作為曲線上的特征點(diǎn)[2]。多邊形逼近方法雖然避免了復(fù)雜的數(shù)學(xué)計(jì)算，可以快速地獲得逼近多邊形，進(jìn)而得到特征點(diǎn)，但是由于多邊形逼近追求的是一種全局下的最優(yōu)[2]，因此提取的特征點(diǎn)不一定是局部輪廓下的曲率極值點(diǎn)。

本文提出一種基于Delaunay三角網(wǎng)的特征點(diǎn)提取方法，可以用于各類多邊形特征點(diǎn)的快速、準(zhǔn)確提取。

1 方法描述

在形狀建模中，多邊形的邊界表達(dá)為點(diǎn)的序列，即C={pi= (xi，yi)|i=1，2，3，…，n}，也就是用點(diǎn)集來逼近圖形邊界線。由于邊界點(diǎn)集構(gòu)建的Delaunay三角網(wǎng)可以保留多邊形的邊界結(jié)構(gòu)信息，因此Delaunay三角網(wǎng)可以用來提取多邊形邊界上的特征點(diǎn)。

1.1 Delaunay三角網(wǎng)

Delaunay三角網(wǎng)具有如下性質(zhì)：

①三角網(wǎng)外圍邊界構(gòu)建的多邊形為點(diǎn)集的凸殼。

②任意三角形的外接圓內(nèi)不包含其他點(diǎn)（這個(gè)性質(zhì)是Delaunay三角網(wǎng)的定義也稱為空外接圓規(guī)則）。

③三角形最大程度地保持了均衡，避免狹長形三角形的出現(xiàn)（最大最小角規(guī)則）。如果將三角網(wǎng)中的每個(gè)三角形的最小角進(jìn)行升序排列，則Delaunay三角網(wǎng)排列得到的數(shù)值最大。從這個(gè)意義上講，Delaunay三角網(wǎng)是“最接近于規(guī)則化”的三角網(wǎng)。

④性質(zhì)②和③保證了Delaunay三角網(wǎng)是最接近等角或等邊的三角網(wǎng)。Delaunay三角網(wǎng)具有良好的特性，由于其最大程度地保持了均衡，避免狹長形三角形的出現(xiàn)，是給定區(qū)域點(diǎn)集的最佳三角剖分[6]。

1.2 特征點(diǎn)提取原理

多邊形的特征點(diǎn)在其局部存在凹凸性，也就是說，可將特征點(diǎn)分為凸特征點(diǎn)和凹特征點(diǎn)，進(jìn)而又可將多邊形的輪廓?jiǎng)澐譃椴煌再|(zhì)的邊，兩個(gè)凸特征點(diǎn)之間的邊稱為凸邊，凸點(diǎn)和凹點(diǎn)之間的邊稱為凹邊，如圖1所示，三角形符號(hào)表示的點(diǎn)是凸特征點(diǎn)，正方形符號(hào)表示的點(diǎn)是凹特征點(diǎn)，③、⑥邊為凸邊，①、②、④、⑤邊則為凹邊。

本文提到的Delaunay三角網(wǎng)是使用多邊形的邊界輪廓點(diǎn)集來構(gòu)建的，它構(gòu)成了該多邊形形狀的剖分結(jié)構(gòu)，其基本單元稱為三角形元。對(duì)圖形剖分的三角形集合，根據(jù)每個(gè)三角形元的鄰接三角形元的個(gè)數(shù)，可以將三角形分為3類：I類三角形只有1個(gè)鄰接三角形；II類三角形存在2個(gè)鄰接三角形；III類三角形存在3個(gè)鄰接三角形（圖2中深色三角形分別代表3類三角形）。根據(jù)Delaunay三角網(wǎng)構(gòu)建規(guī)則和性質(zhì)可知，I類三角形的2個(gè)頂點(diǎn)處于兩條不同凹凸性的邊上，第3個(gè)頂點(diǎn)處于不同凹凸性的邊的交點(diǎn)處；II類三角形的3個(gè)頂點(diǎn)分別處在2條不同凹凸性的邊上；III類三角形的3個(gè)頂點(diǎn)分別處在3條不同凹凸性的邊上。

圖1 圖形的凹凸特征點(diǎn)和邊

圖2 三類三角形

1.3 特征點(diǎn)提取方法

基于Delaunay三角網(wǎng)的多邊形特征點(diǎn)提取方法為：

1）使用多邊形邊界輪廓點(diǎn)集來構(gòu)建 Delaunay三角網(wǎng)（見圖3a、b）。

2）用多邊形邊界輪廓線將構(gòu)建的Delaunay三角網(wǎng)進(jìn)行分割，分成多邊形內(nèi)部Delaunay三角網(wǎng)與多邊形外部Delaunay三角網(wǎng)，圖3c中黑色虛線為多邊形輪廓線，內(nèi)外部Delaunay三角網(wǎng)使用不同符號(hào)填充。

3）分別提取多邊形內(nèi)部Delaunay三角網(wǎng)與多邊形外部Delaunay三角網(wǎng)中I類三角形的頂點(diǎn)（不與其他三角形共用的頂點(diǎn)），內(nèi)部Delaunay三角網(wǎng)I類三角形的頂點(diǎn)構(gòu)成了多邊形的凸特征點(diǎn)（圖3d），外部Delaunay三角網(wǎng)I類三角形的頂點(diǎn)構(gòu)成了多邊形的凹特征點(diǎn)（圖3e）。

4）由于使用原始多邊形輪廓線對(duì)Delaunay三角網(wǎng)進(jìn)行裁剪，會(huì)使得外部Delaunay三角網(wǎng)出現(xiàn)破碎，從而產(chǎn)出一些偽I類三角形（圖4）。因此需要判斷這些I類三角形的頂點(diǎn)是否在Delaunay三角網(wǎng)的凸包上，如果在，則不是凹特征點(diǎn)；反之，為凹特征點(diǎn)。

2 試驗(yàn)驗(yàn)證

將本文提出的特征點(diǎn)提取方法應(yīng)用于簡單多邊形、復(fù)雜多邊形（含島嶼、自由曲線）、自然圖形進(jìn)行驗(yàn)證。圖3展示了本方法的流程，圖5分別展示了其內(nèi)外部Delaunay三角網(wǎng)和提取特征點(diǎn)結(jié)果。本方法在提取特征點(diǎn)的同時(shí)將特征點(diǎn)的凹凸性準(zhǔn)確地區(qū)分出來（圖3f、圖5）。從試驗(yàn)效果來看，本文提出的特征點(diǎn)提取方法是實(shí)用的、有效的和可行的。

圖3 基于Delaunay三角網(wǎng)的多邊形特征點(diǎn)提取方法

圖4 偽I類三角形

圖5 多邊形圖形的特征點(diǎn)提取

3 結(jié) 語

研究提出了基于Delaunay三角網(wǎng)的多邊形特征點(diǎn)提取方法，通過對(duì)多組不同類型圖形的實(shí)例驗(yàn)證，該方法不僅適用于各類多邊形，并且對(duì)自然圖形也具有良好普適性。本方法能夠快速有效地提取出多邊形的特征點(diǎn)，提取的特征點(diǎn)具有良好的準(zhǔn)確性，并且能在提取的過程中判斷特征點(diǎn)的凹凸性。

[1]劉晶.葉片數(shù)字化檢測中的模型配準(zhǔn)技術(shù)及應(yīng)用研究[D].西安:西北工業(yè)大學(xué),2006

[2]文貢堅(jiān),王潤生.數(shù)字曲線上特征點(diǎn)檢測[J].計(jì)算機(jī)學(xué)報(bào),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]張文景,徐曉鳴,丁國駿,等.一種基于曲率提取輪廓特征點(diǎn)的方法[J].上海交通大學(xué)學(xué)報(bào),1999,33(5): 592-595

[6]孫曉峰,李英成,王淼,等.一種改進(jìn)的約束Delaunay三角網(wǎng)構(gòu)建算法及其在快速立體解譯平臺(tái)中的應(yīng)用[J].遙感信息,2012(1):9-12

[7]王新生,何津,葉小雷,等.圖的譜方法的空間目標(biāo)形狀表達(dá)研究[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2012(11): 25-28,42

[8]李精忠,艾廷華.以等高線為特征約束的Delaunay TIN的構(gòu)建[J].地理空間信息,2011,9(5): 26-31

[9]邢海妮,顧慶華,李莉莉.以等高線為特征約束的Delaunay TIN的構(gòu)建[J].地理空間信息,2009,7(6): 73-75

[10]艾廷華,郭仁忠.基于約束Delaunay結(jié)構(gòu)的道中軸線提取及網(wǎng)絡(luò)模型建立[J].測繪學(xué)報(bào),2000,29(4):348-354