多約束的平面點(diǎn)集形狀重構(gòu)方法

朱 杰，孫毅中

1. 南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023； 2. 江蘇省地理信息資源開(kāi)發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京 210023

多約束的平面點(diǎn)集形狀重構(gòu)方法

朱 杰1,2，孫毅中1,2

1. 南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023； 2. 江蘇省地理信息資源開(kāi)發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京 210023

針對(duì)平面點(diǎn)集空間分布的復(fù)雜性，本文提出了一種基于Delaunay三角網(wǎng)的平面點(diǎn)集形狀重構(gòu)方法。首先采用一種簡(jiǎn)單且實(shí)用的數(shù)據(jù)結(jié)構(gòu)以表達(dá)Delaunay三角網(wǎng)中嵌入的幾何信息和拓?fù)湫畔ⅲ缓笥赏庀騼?nèi)迭代過(guò)濾Delaunay三角網(wǎng)得到一個(gè)大概邊界，最后進(jìn)一步考慮邊界的凹凸信息和空洞現(xiàn)象，獲取最終的精細(xì)邊界。試驗(yàn)結(jié)果表明與其他典型的Delaunay三角網(wǎng)重構(gòu)方法相比，本文提出的算法能更好地適用于平面點(diǎn)集空間分布的復(fù)雜性，通過(guò)所構(gòu)建的數(shù)學(xué)模型實(shí)現(xiàn)了凸凹多邊形內(nèi)外邊界提取。

平面點(diǎn)集；形狀重構(gòu)；Delaunay三角網(wǎng)；多約束；GIS

平面點(diǎn)集形狀重構(gòu)在GIS相關(guān)應(yīng)用領(lǐng)域如地圖綜合[1-3]、建筑物輪廓線提取[4-6]、地理范圍確定[7-8]以及地理信息檢索(GIR)[9]中是一項(xiàng)重要而基礎(chǔ)的工作，旨在從一堆無(wú)序的點(diǎn)集(僅有坐標(biāo)信息)中提取出平面點(diǎn)集的分布范圍，近似地表達(dá)真實(shí)的輪廓信息。如何考慮點(diǎn)集空間分布的復(fù)雜性是許多平面點(diǎn)集形狀重構(gòu)方法面臨的主要問(wèn)題。通過(guò)對(duì)國(guó)內(nèi)外學(xué)者的研究分析，將這種復(fù)雜性歸納為以下4個(gè)方面：①點(diǎn)集的空間關(guān)系表達(dá)，包括幾何信息和拓?fù)湫畔?；②空間密度分布不均；③局部凹凸信息的精確描述；④內(nèi)部空洞問(wèn)題。此外，為更加精確地描述點(diǎn)集形狀輪廓信息，重構(gòu)過(guò)程中還需要顧及重構(gòu)結(jié)果的唯一性和規(guī)則性。

現(xiàn)有平面點(diǎn)集形狀重構(gòu)方法可以分為3類：①基于凸殼的方法；②基于Delaunay三角網(wǎng)的方法；③基于曲線重構(gòu)的方法。基于凸殼的方法[10-12]大都采用凸殼內(nèi)縮的策略獲取邊界的凹凸特征，在一定情況下能夠處理空間密度分布不均的情況，但由于該算法缺少點(diǎn)集的拓?fù)湫畔ⅲy以保證邊界的規(guī)則性，也無(wú)法識(shí)別空洞現(xiàn)象?；贒elaunay三角網(wǎng)的重構(gòu)過(guò)程可以分為兩步：①構(gòu)建Delaunay三角網(wǎng)；②基于圖形結(jié)構(gòu)特征提取一些幾何單元來(lái)近似地表達(dá)真實(shí)邊界情況。最早的這類重構(gòu)方法是Sculpture方法[13]和α-shapes方法[14]。Delaunay Sculpture是一種剝離三角網(wǎng)算法，由外向內(nèi)不斷刪除不規(guī)則的三角形直到產(chǎn)生一個(gè)符合條件的點(diǎn)集形狀。基于這種思想衍生了許多算法[15-18]，這些算法能夠提取任意形狀的點(diǎn)集，剝離規(guī)則也保證了最終邊界的規(guī)則性，但這些算法不夠穩(wěn)健，難以適應(yīng)復(fù)雜的凹部和空洞現(xiàn)象，如χ-shape算法[16]通過(guò)迭代判斷Delaunay三角網(wǎng)邊界邊長(zhǎng)，將滿足閾值的邊長(zhǎng)保留作為最終的邊界提取結(jié)果，這種全局參數(shù)對(duì)密度分布不均的樣本數(shù)據(jù)重構(gòu)效果不是很穩(wěn)定，該算法也沒(méi)有考慮空洞問(wèn)題；為克服全局度量受密度變化影響較大的缺陷，?RGG算法[18]采用了局部度量方式對(duì)三角網(wǎng)進(jìn)行過(guò)濾，避免了算法的參數(shù)化，針對(duì)三角網(wǎng)中特定的結(jié)構(gòu)特征能夠有效識(shí)別空洞現(xiàn)象，但該算法對(duì)含有規(guī)則的凹邊界和狹長(zhǎng)空洞是失效的。α-shapes算法類似Delaunay三角網(wǎng)，參數(shù)α控制了輪廓信息的含量,由于這個(gè)原因，需要不斷變化參數(shù)α值以得到理想的輪廓信息。但是，α-shapes不能準(zhǔn)確地表達(dá)點(diǎn)集密度分布不均的情況。為了顧及局部密度信息,后期出現(xiàn)了若干α-shapes改進(jìn)算法，如r-shape[19]、A-shapes[20]、LDA-α-complex[21]等，這些算法采用了局部度量和全局度量策略，能夠滿足平面點(diǎn)集分布不均、空洞等復(fù)雜情況，但是輸入?yún)?shù)過(guò)多?；谇€重構(gòu)的方法采用曲線擬合方法如泊松法[22]、最小二乘法[23]、徑向基函數(shù)法[24]估算點(diǎn)集的曲率，將滿足曲率閾值條件的點(diǎn)判定為邊界特征候選點(diǎn)，最后將這些邊界點(diǎn)連接即達(dá)到了邊界提取的目的。曲線重構(gòu)方法可以針對(duì)無(wú)規(guī)則的點(diǎn)云數(shù)據(jù)提取出精度較高的邊界點(diǎn)，但這種方法需要計(jì)算每一個(gè)數(shù)據(jù)點(diǎn)的曲率值，其計(jì)算過(guò)程非常復(fù)雜。

綜上分析，基于Delaunay三角網(wǎng)的平面點(diǎn)集重構(gòu)方法原理較簡(jiǎn)單，其結(jié)構(gòu)能夠很好地彌補(bǔ)不規(guī)則點(diǎn)集的幾何信息和拓?fù)湫畔?，較其他方法相對(duì)系統(tǒng)和穩(wěn)健。針對(duì)該方法存在的問(wèn)題，本文基于Delaunay三角網(wǎng)提出了一種有效的平面點(diǎn)集重構(gòu)方法，首先采用一種局部度量方式對(duì)整個(gè)Delaunay三角網(wǎng)(凸殼)進(jìn)行過(guò)濾得到初始邊界，然后通過(guò)構(gòu)建有效的數(shù)學(xué)模型實(shí)現(xiàn)凸凹多邊形內(nèi)外邊界提取。

1 理論基礎(chǔ)

1.1 數(shù)據(jù)結(jié)構(gòu)

Delaunay三角網(wǎng)中包含了3種實(shí)體要素：點(diǎn)、邊和三角形，本文采用了一種簡(jiǎn)單且實(shí)用的數(shù)據(jù)結(jié)構(gòu)，即在Delaunay三角網(wǎng)中每個(gè)三角形記錄了其相應(yīng)的三條邊，每條邊存儲(chǔ)了兩個(gè)端點(diǎn)信息，包括每個(gè)端點(diǎn)的坐標(biāo)信息。此外，為了更有效地對(duì)邊界進(jìn)行操作，每條邊還記錄了鄰近三角形信息，每個(gè)點(diǎn)存儲(chǔ)了鄰域邊信息。采用以上數(shù)據(jù)組織方式來(lái)表達(dá)Delaunay三角網(wǎng)中3種要素之間的拓?fù)湫畔?duì)邊界搜索、提取以及拓?fù)錂z查有著重要的作用。

1.2 相關(guān)定義

a. 懸掛邊、鏈?zhǔn)竭叄核鼈儾粚儆谌魏我粋€(gè)三角形(圖1(a))。

b. 交叉點(diǎn)：每個(gè)邊界點(diǎn)由兩條邊界邊交匯而成，交叉點(diǎn)是兩條以上邊界邊的交點(diǎn)(圖1(a))。

圖1 邊界規(guī)則性示意圖Fig.1 Illustration of regular and non-regular boundary

(6) 空洞：從Delaunay三角網(wǎng)的結(jié)構(gòu)而言，空洞是一個(gè)封閉的凹部區(qū)域，即每個(gè)空洞由若干凹邊構(gòu)成而不存在可見(jiàn)邊界邊，從某種意義上而言，凹部和空洞具有相似的結(jié)構(gòu)特征。

2 算法過(guò)程

本文提出的算法是一種由外向內(nèi)有序過(guò)濾Delaunay三角網(wǎng)的過(guò)程。首先按照設(shè)定的數(shù)據(jù)結(jié)構(gòu)采用生長(zhǎng)法[26]對(duì)平面點(diǎn)集構(gòu)建Delaunay三角網(wǎng)，將點(diǎn)群圍在一個(gè)凸殼內(nèi)，找出初始邊界；然后根據(jù)一種有序的篩選策略對(duì)初始邊界向內(nèi)過(guò)濾，得到一個(gè)大概邊界，過(guò)濾的過(guò)程中要保證邊界的規(guī)則性；最后進(jìn)一步考慮邊界的凹凸信息和空洞現(xiàn)象，得到最終的準(zhǔn)確邊界。算法可分為兩部分：粗邊界提取和精細(xì)邊界生成。

2.1 粗邊界提取

Delaunay三角網(wǎng)提供了3個(gè)參數(shù)：周長(zhǎng)、角度和邊長(zhǎng)。周長(zhǎng)和邊長(zhǎng)閾值都屬于全局度量方式，容易受密度變化的影響，角度作為一種局部度量方式要優(yōu)于周長(zhǎng)和邊長(zhǎng)。根據(jù)格式塔鄰近性原則[27]可知平面點(diǎn)集的邊界由點(diǎn)群外圍且距離相近的點(diǎn)連接而成，換言之，在一個(gè)邊界三角形中，如果邊界邊所對(duì)應(yīng)的角度越大，則兩個(gè)邊界點(diǎn)之間的距離也就越大，兩個(gè)邊界點(diǎn)之間不符合鄰近性原則，應(yīng)當(dāng)刪除它們之間的連線(即邊界邊)。上述性質(zhì)能夠適應(yīng)空間實(shí)體密度的變化，為此本文采用角度作為重構(gòu)參數(shù)。給定一個(gè)平面點(diǎn)集，設(shè)邊界邊為Be,邊界三角形中邊界邊所對(duì)應(yīng)的角度表示為Angle(Be)，角度閾值為R，其粗邊界提取的具體流程如圖2所示。

圖2 粗邊界提取流程Fig.2 Rough boundary extraction flow chart

粗邊界提取過(guò)程采用了排序-過(guò)濾的策略，這是因?yàn)檫吔缣幍膸缀翁卣髋c內(nèi)部相比具有明顯的“不規(guī)則性”，排序的效果是為了過(guò)濾掉最不規(guī)則的元素，保證邊界提取結(jié)果的唯一性；另一方面粗邊界提取算法雖然在一定程度上能夠反映形狀輪廓的凹凸信息，但是無(wú)法識(shí)別復(fù)雜的凹部和空洞現(xiàn)象，需要進(jìn)一步施加約束條件，生成精細(xì)邊界。

2.2 精細(xì)邊界生成

粗邊界提取過(guò)程采用了基于角度的過(guò)濾策略對(duì)以下兩種結(jié)構(gòu)是失效的。

(1) 含有規(guī)則三角形的凹部。如果凹部存在如圖3(a)所示的規(guī)則三角形時(shí)，其作為邊界三角形邊界邊所對(duì)應(yīng)的角度很小，為刪除此邊界邊必須降低閾值R，但閾值過(guò)小，邊界會(huì)過(guò)度收縮，難以得到理想的重構(gòu)效果。如果無(wú)法刪除此邊界邊，勢(shì)必會(huì)阻礙凹部的進(jìn)一步探測(cè)。

(2) 空洞。粗邊界提取是由外向內(nèi)過(guò)濾邊界邊的內(nèi)縮過(guò)程，由邊界邊的定義可知，空洞內(nèi)的邊(圖4(a))不屬于邊界邊，因此，空洞現(xiàn)象無(wú)法被識(shí)別。

圖3 含有規(guī)則三角形的凹部Fig.3 An example of cavity with regular triangle

圖4 空洞現(xiàn)象Fig.4 An example of a hole

在1.2節(jié)中指出凹部和空洞可以視為同一種結(jié)構(gòu)，它們通常位于較周邊密度稀疏的區(qū)域，采用Voronoi圖來(lái)表示這種密度變化，從圖3(b)和圖4(b)中可以看出凹部和空洞區(qū)域密度較小，其周邊區(qū)域的密度相對(duì)較高。選用密度變化來(lái)定義這兩種結(jié)構(gòu)的原因在于Delaunay三角網(wǎng)是一個(gè)帶有密度性質(zhì)的空間鄰近性模型，不需要任何參數(shù)設(shè)置，參數(shù)信息完全包含在三角網(wǎng)中。從圖3(a)和圖4(a)中可以看出，位于這兩種結(jié)構(gòu)的邊界點(diǎn)其鄰域內(nèi)連線長(zhǎng)短不一，梯度變化較大?；诖?，采用一個(gè)相對(duì)參數(shù)來(lái)量化這種特征，即通過(guò)判斷點(diǎn)的松散度來(lái)探測(cè)凹部和空洞，具體表達(dá)如下。

點(diǎn)的松散度：給定一個(gè)平面點(diǎn)集D，由點(diǎn)集生成的Delaunay三角網(wǎng)表示為DT。針對(duì)DT內(nèi)任一點(diǎn)實(shí)體P，F(xiàn)(P)表示點(diǎn)實(shí)體P的松散度，表示為

F(P)=Local_SD(P)/Local_Mean_Length(P)

(1)

(2)

Local_SD(P)=

(3)

F(P)值越小，說(shuō)明該對(duì)象鄰域內(nèi)邊長(zhǎng)梯度變化小。真實(shí)輪廓內(nèi)的點(diǎn)由于鄰域內(nèi)邊長(zhǎng)變化較小，其F(P)值較小，相反，空洞和凹部處的邊界點(diǎn)F(P)值較大(圖3(c)和圖4(c))。因此，針對(duì)DT內(nèi)任一點(diǎn)實(shí)體P，凹部和空洞的松散度可以表達(dá)為

(4)

式中，Sets表示凹部和空洞的松散度集合；T表示松散度閾值。通過(guò)集合Sets可以找到空洞和凹部的邊界點(diǎn)，這些邊界點(diǎn)鄰域內(nèi)連線長(zhǎng)短不一，如何篩選這些邊長(zhǎng)是關(guān)鍵問(wèn)題。從空間聚類的角度出發(fā)，松散度較大的主要原因在于長(zhǎng)邊的存在，為刪除這些不合理的長(zhǎng)邊，本文采用了AUTOCLUST算法[28]，其根據(jù)密度信息來(lái)探測(cè)長(zhǎng)邊，具體表達(dá)如下。

長(zhǎng)邊約束：給定一個(gè)平面點(diǎn)集D，由點(diǎn)集生成的Delaunay三角網(wǎng)表示為DT。針對(duì)DT內(nèi)任一點(diǎn)實(shí)體P，Longedge表示與P連接的所有邊的長(zhǎng)邊約束條件，表示為

Longedge=Local_Mean_Length(P)+Global_SD

(5)

(6)

式中，Local_Mean_Length(P)表示P鄰域內(nèi)所有邊長(zhǎng)的均值；Local_SD(Pi)表示點(diǎn)Pi鄰域內(nèi)所有邊長(zhǎng)的標(biāo)準(zhǔn)差；Global_SD表示DT內(nèi)所有對(duì)象Local_SD(Pi)的平均值；N表示平面點(diǎn)集數(shù)目。

針對(duì)網(wǎng)內(nèi)任一點(diǎn)實(shí)體P，若與其直接相連接的邊的長(zhǎng)度大于Longedge，則刪除該邊。對(duì)于保留下來(lái)的短邊可以調(diào)用粗邊界提取進(jìn)行約束?；诖?，精細(xì)邊界提取的具體過(guò)程如下。

(1) 在粗邊界提取的結(jié)果基礎(chǔ)上，計(jì)算整個(gè)點(diǎn)集的松散度并獲取集合Sets。

(2) 將Sets分為兩部分：邊界點(diǎn)的松散度和內(nèi)點(diǎn)松散度，如果點(diǎn)集同時(shí)存在凹部和空洞，凹部識(shí)別優(yōu)先于空洞，即邊界點(diǎn)遍歷優(yōu)先于內(nèi)點(diǎn)。

精細(xì)邊界的提取過(guò)程如圖5和圖6所示。

圖5 凹部識(shí)別流程Fig.5 Concave recognition flow chart

圖6 空洞識(shí)別流程Fig.6 Hole recognition flow chart

精細(xì)邊界提取過(guò)程中顧及了兩個(gè)順序，一是優(yōu)先級(jí)，凹部和空洞識(shí)別的優(yōu)先級(jí)，鄰域內(nèi)邊長(zhǎng)和邊界邊的遍歷優(yōu)先級(jí)，優(yōu)先級(jí)能夠確保過(guò)濾掉最不規(guī)則的元素；另一個(gè)順序是遍歷順序，松散度遍歷和鄰域邊長(zhǎng)遍歷都采用了降序排列，這確保了邊界提取的唯一性。

2.3 松散度閾值T的確定

(7)

目標(biāo)函數(shù)通過(guò)探測(cè)過(guò)渡點(diǎn)將松散度劃分為兩部分，為達(dá)到二類分割的最佳效果即類內(nèi)方差最小或類間方差最大，引入PBM[29]指數(shù)來(lái)求解參數(shù)k。PBM指數(shù)作為一個(gè)相對(duì)評(píng)價(jià)指標(biāo)能夠滿足緊密性與分離性的聚類準(zhǔn)則，其具體表示為

(8)

(9)

式中，Nc表示簇的數(shù)量；Ni表示簇Ci中實(shí)體數(shù)量；vi表示簇i的質(zhì)心；Ei表示簇Ci的內(nèi)部距離(簇內(nèi)所有空間對(duì)象到其質(zhì)心的距離之和)；E1表示數(shù)據(jù)集只分為一類的聚類內(nèi)部距離；ENc表示數(shù)據(jù)集分為Nc個(gè)簇的聚類內(nèi)部距離；DNc表示空間簇間的分離度，其隨著Nc增大而增大，最大值為數(shù)據(jù)集中最遠(yuǎn)兩個(gè)簇的質(zhì)心距離。PBM指數(shù)越大，則表示得到的聚類結(jié)果越可靠。

結(jié)合粗邊界和精細(xì)邊界提取過(guò)程，分別對(duì)含有規(guī)則三角形的凹部和空洞機(jī)進(jìn)行識(shí)別。首先調(diào)用粗邊界提取流程對(duì)含有凹部或者空洞的Delaunay三角網(wǎng)(參考圖3(a)和4(a))進(jìn)行過(guò)濾，其結(jié)果如圖7(a)和圖8(a)所示；在粗邊界提取的基礎(chǔ)上調(diào)用精細(xì)邊界提取流程，通過(guò)PBM指數(shù)確定松散度閾值T(參考圖7(d)—(e)和圖8(d)—(e))以此找到位于凹部或者空洞處的邊界點(diǎn)(圖7(b)和圖8(b))，篩選邊界點(diǎn)的鄰域邊從而得到最終的邊界(圖7(c)和圖8(c))。

圖7 含有規(guī)則三角形的凹部識(shí)別過(guò)程Fig.7 Different stages of the proposed algorithm for cavity detection

圖8 空洞的識(shí)別過(guò)程Fig.8 Different stages of the proposed algorithm for hole detection

3 試驗(yàn)分析

3.1 參數(shù)R的選擇

粗邊界和精細(xì)邊界的生成過(guò)程中，角度閾值R是邊界收斂的重要約束條件。平面點(diǎn)集存在兩種形式：一是含有空洞和凹部的點(diǎn)集，另一個(gè)是不含有以上兩種現(xiàn)象的點(diǎn)集。針對(duì)不含有空洞和凹部的點(diǎn)集，Delaunay三角網(wǎng)內(nèi)的三角形近似等邊三角形，此類點(diǎn)集的凸殼邊界即為理想的邊界收斂結(jié)果。對(duì)于含有空洞和凹部的點(diǎn)集，需要深入討論角度閾值R對(duì)此類點(diǎn)集邊界收斂的作用過(guò)程，為此，本文設(shè)計(jì)了幾組模擬試驗(yàn)來(lái)評(píng)價(jià)參數(shù)R對(duì)重構(gòu)結(jié)果的精度影響，以獲取合適的參數(shù)取值范圍為用戶在參數(shù)R選擇方面提供參考。模擬試驗(yàn)采用既定的形狀和點(diǎn)集分布類型，L2誤差范數(shù)[16]作為重構(gòu)結(jié)果的精度評(píng)價(jià)方法，其具體表達(dá)為

(10)

式中，O代表原始多邊形；S代表重構(gòu)結(jié)果。L2誤差范數(shù)通過(guò)原始多邊形與重構(gòu)結(jié)果的面積比例大小評(píng)價(jià)重構(gòu)效果，L2誤差范數(shù)等于0，則表示重構(gòu)結(jié)果與原始多邊形邊界完全吻合。

如果只看老師的評(píng)語(yǔ)，肯定是扁平片面的。通過(guò)創(chuàng)新的他評(píng)形式，看到了很多人生活中學(xué)習(xí)上為人上的更全面更真實(shí)的一面，看到了很多人在為人處世上的成長(zhǎng)改變，看到了他們的朋友圈人緣，看到了他們的真心真意。

模擬實(shí)驗(yàn)采用了5組形狀數(shù)據(jù)：云南、內(nèi)蒙古、F字(宋體)、K字(宋體)和A字(宋體)，5組形狀數(shù)據(jù)邊界具有明顯的不規(guī)則性，包含了大量的凹部和空洞；考慮到點(diǎn)集分布類型(如隨機(jī)分布)有可能使點(diǎn)集內(nèi)部產(chǎn)生空洞現(xiàn)象，因此點(diǎn)集分布類型選擇均勻分布；每組形狀數(shù)據(jù)內(nèi)部生成的點(diǎn)集數(shù)目確保能夠覆蓋到形狀邊界，模擬實(shí)驗(yàn)采用的點(diǎn)集數(shù)目分別是70、100、130和160，代表了不同的點(diǎn)集密度。由角度參數(shù)的內(nèi)涵可知閾值R的取值范圍在[0,180](試驗(yàn)取值間隔為10)，圖11顯示了基于參數(shù)R每組形狀數(shù)據(jù)邊界收斂的L2誤差范數(shù)變化曲線，5組數(shù)據(jù)的邊界收斂過(guò)程大體相似這主要是因?yàn)榭斩春桶疾渴堑葍r(jià)的結(jié)構(gòu)；另外，每組數(shù)據(jù)的邊界收斂過(guò)程并沒(méi)有隨點(diǎn)集密度變化而發(fā)生改變。當(dāng)R取值180時(shí)粗邊界中Delaunay三角網(wǎng)沒(méi)有邊被刪除(如圖9所示)，網(wǎng)內(nèi)存在大量的“不規(guī)則”長(zhǎng)邊，此時(shí)精細(xì)邊界中的松散度閾值T也較高(如圖10所示)，只能刪除部分不規(guī)則長(zhǎng)邊，無(wú)法徹底識(shí)別凹部或者空洞，邊界收斂效果不理想，表現(xiàn)為L(zhǎng)2誤差范數(shù)值較高(如圖11(b)所示)；當(dāng)R取值0時(shí)，網(wǎng)內(nèi)的邊本該全部刪除，但是由于受到邊界規(guī)則性的約束邊界邊不能存在懸掛邊、鏈?zhǔn)竭吅徒徊纥c(diǎn)，保留下來(lái)的邊界呈“鋸齒狀”，如圖9和10所示，邊界收斂效果同樣不理想，L2誤差范數(shù)值較高，如圖11(b)所示，因此要想獲得理想的邊界收斂效果R的取值范圍應(yīng)該是0

圖9 粗邊界提取過(guò)程Fig.9 Rough boundary extraction process

圖10 精細(xì)邊界提取過(guò)程Fig.10 Refined boundary extraction process

圖11 邊界收斂的精度變化Fig.11 Precision variation of boundary convergence

結(jié)合模擬試驗(yàn)的邊界收斂過(guò)程和圖11中不同點(diǎn)集密度邊界收斂的L2誤差范數(shù)變化過(guò)程可以得出，角度閾值R取值范圍在[80,120]內(nèi)就含有空洞和凹部的點(diǎn)集而言可以取得理想的邊界收斂結(jié)果。

3.2 試驗(yàn)結(jié)果對(duì)比

為了驗(yàn)證本文方法的有效性與優(yōu)勢(shì)性，將提出的方法與其他兩種基于Delaunay三角網(wǎng)的典型方法χ-shape和?RGG算法進(jìn)行比較分析，試驗(yàn)內(nèi)容主要包含以下幾個(gè)方面：

3.2.1 非均勻分布

圖12分別顯示了在平面點(diǎn)集分布不均情況下3種方法的邊界提取結(jié)果。χ-shape算法由于采用邊長(zhǎng)閾值作為度量參數(shù)，當(dāng)點(diǎn)集分布不均時(shí)邊界提取效果不是很穩(wěn)定，會(huì)產(chǎn)生大塊的鋸齒現(xiàn)象；?RGG算法和本文方法都采用了局部度量參數(shù)(三角形外接圓心和角度)能夠獲取合理的重構(gòu)結(jié)果；另外，平面點(diǎn)集形狀重構(gòu)本質(zhì)上屬于不確定性問(wèn)題，即合理的重構(gòu)結(jié)果并不唯一。雖然?RGG是一種自動(dòng)構(gòu)建形狀輪廓的方法，不需要任何參數(shù)，但從不確定性角度而言，本文提出的方法能夠產(chǎn)生若干合理的重構(gòu)結(jié)果，提供了更多的重構(gòu)細(xì)節(jié)。

3.2.2 含有規(guī)則三角形的凹部

3.2.3 空洞現(xiàn)象

圖14分別顯示了3種方法對(duì)空洞現(xiàn)象的處理結(jié)果。χ-shape算法無(wú)法識(shí)別空洞；?RGG算法針對(duì)三角網(wǎng)的結(jié)構(gòu)可以對(duì)空洞現(xiàn)象構(gòu)造邊界，但它無(wú)法識(shí)別狹長(zhǎng)的空洞現(xiàn)象；本文方法能夠識(shí)別多樣的空洞現(xiàn)象，包括狹長(zhǎng)空洞(圖14)和球狀空洞(圖8)。

3.2.4 噪聲和非連通區(qū)域

3種方法的重構(gòu)結(jié)果都包含了平面點(diǎn)集中所有點(diǎn)包括噪聲，若要解決噪聲問(wèn)題可以采用空間聚類的方法如AMOEA算法[30]對(duì)平面點(diǎn)集進(jìn)行預(yù)處理，剔除噪聲；在一些實(shí)例中，有些點(diǎn)集是非連通區(qū)域如“i”或者“=”,考慮到邊界的規(guī)則性，三種方法同樣不能生成非連通區(qū)域。

圖12 針對(duì)點(diǎn)集分布不均χ-shape(綠色)、?RGG(藍(lán)色)和本文方法(白色)邊界提取結(jié)果的定性比較Fig.12 Qualitative comparison of χ-shape (in green)) and ?RGG(in cyan)) with the proposed algorithm (in black boundary) for non-uniform point set

圖13 針對(duì)含有規(guī)則三角形的凹部χ-shape(綠色)、?RGG(藍(lán)色)和本文方法(白色)邊界提取結(jié)果的定性比較Fig.13 Qualitative comparison of χ-shape (in green)) and ?RGG(in cyan)) with the proposed algorithm (in black boundary) for Cavities with regular triangles

3.3 應(yīng)用實(shí)例

本節(jié)將引入兩個(gè)應(yīng)用實(shí)例來(lái)驗(yàn)證本文方法的實(shí)用性，以發(fā)現(xiàn)平面點(diǎn)集重構(gòu)方法在不同領(lǐng)域內(nèi)的應(yīng)用潛力。城市輪廓是城市空間形態(tài)分析中一個(gè)重要的組成部分，本文基于POI數(shù)據(jù)利用提出的方法提取城市輪廓線。圖15(a)顯示了洛陽(yáng)市地名地址POI數(shù)據(jù)(灰色部分)，由于城市輪廓線表達(dá)的是一個(gè)城市的大概分布范圍，因此這里采用粗邊界提取方法和凹部識(shí)別算法，不需要構(gòu)造城市內(nèi)部的邊界。圖15(a)給出了洛陽(yáng)市城市輪廓提取結(jié)果(黑色曲線)，將提取的城市輪廓線與洛陽(yáng)市遙感影像圖(圖15(b))疊加比較，結(jié)果如圖15(c)所示，紅色曲線代表洛陽(yáng)市遙感影像邊界線，黑色曲線代表輪廓提取結(jié)果，二者邊界線有很高的吻合度。

圖15 洛陽(yáng)城市輪廓提取結(jié)果及對(duì)比Fig.15 The urban contour of Luoyang generated by our algorithm and comparison result

另一個(gè)實(shí)例是基于LIDAR數(shù)據(jù)的建筑輪廓線提取，數(shù)據(jù)來(lái)源于文獻(xiàn)[31]給出的馬來(lái)西亞吉隆坡城市中心區(qū)各類不同幾何形狀的建筑，基于本文方法提取的各種形狀建筑輪廓線結(jié)果(如圖16所示)與文獻(xiàn)[31]的提取結(jié)果相似，這表明提出的方法可適用于凸凹多邊形內(nèi)外邊界提取。

圖16 各種形狀建筑輪廓線提取結(jié)果Fig.16 The extracting results of different building boundary with our algorithm

4 結(jié) 論

本文提出了一種多約束的平面點(diǎn)集形狀重構(gòu)方法，相比已有方法，該方法能夠更好地適應(yīng)平面點(diǎn)集空間分布的復(fù)雜性。通過(guò)模擬試驗(yàn)和應(yīng)用實(shí)例可以發(fā)現(xiàn)：①本文方法可以適應(yīng)空間密度分布不均、凹凸信息精確描述、內(nèi)部空洞等復(fù)雜情況下的平面點(diǎn)集形狀重構(gòu)；②需要的輸入?yún)?shù)只有一個(gè)且在試驗(yàn)部分中給出了指導(dǎo)信息，方便用戶實(shí)際使用；③重構(gòu)過(guò)程中對(duì)平面點(diǎn)集中存在的凹部和空洞給出了一種有效的數(shù)學(xué)描述以及識(shí)別方法，具有較強(qiáng)的理論保證。進(jìn)一步改進(jìn)的方面有：實(shí)驗(yàn)分析中缺少對(duì)算法自身的定量分析包括點(diǎn)集密度變化和點(diǎn)集分布類型的適應(yīng)性分析；在應(yīng)用領(lǐng)域中還局限在二維平面中，后期進(jìn)一步考慮拓展到三維空間中。

[1] 艾廷華, 劉耀林. 保持空間分布特征的群點(diǎn)化簡(jiǎn)方法[J]. 測(cè)繪學(xué)報(bào), 2002, 31(2): 175-181. AI Tinghua, LIU Yaolin. A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 175-181.

[2] GALTON A,DUCKHAM M.What is the Region Occupied by a Set of Points?[M]∥RAUBAL M, MILLER H J, FRANK A U, et al. Geographic Information Science. Berlin Heidelberg: Springer, 2006: 81-98.

[3] 李佳田,康順,羅富麗.利用層次Voronoi圖進(jìn)行點(diǎn)群綜合[J]. 測(cè)繪學(xué)報(bào), 2014, 43(12): 1300-1306. DOI: 10.13485/j.cnki.11-2089.2014.0166. LI Jiatian, KANG Shun, LUO Fuli. Point Group Generalization Method Based on Hierarchical Voronoi Diagram[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(12): 1300-1306. DOI: 10.13485/j.cnki.11-2089.2014.0166.

[4] ZHU Chao, ZHANG Xiaopeng, HU Baogang, et al. Reconstruction of Tree Crown Shape from Scanned Data[M]∥PAN Zhigeng, ZHANG Xiaopeng, RHALIBI A E, et al. Technologies for E-learning and Digital Entertainment. Berlin Heidelberg: Springer, 2008: 745-756.

[5] 孫穎, 張新長(zhǎng), 康停軍, 等. 改進(jìn)GAC模型在點(diǎn)云和影像自動(dòng)提取建筑物邊界中的應(yīng)用[J]. 測(cè)繪學(xué)報(bào), 2013, 42(3): 337-343, 350. SUN Ying, ZHANG Xinchang, KANG Tingjun, et al. Improved GAC Model for Automatic Building Extraction from LiDAR Point Clouds and Aerial Image[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(3): 337-343, 350.

[6] 孫穎, 張新長(zhǎng), 羅國(guó)瑋. 從機(jī)載激光雷達(dá)點(diǎn)云提取建筑物屋頂邊界的活動(dòng)輪廓模型改進(jìn)方法[J]. 測(cè)繪學(xué)報(bào), 2014, 43(6): 620-626, 636. DOI: 10.13485/j.cnki.11-2089.2014.0106. SUN Ying, ZHANG Xinchang, LUO Guowei. Improved Active Contour Model for Building Roof Boundary Extraction from LiDAR Point Cloud[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(6): 620-626, 636. DOI: 10.13485/j.cnki.11-2089.2014.0106.

[7] KISILEVICH S, MANSMANN F, BAK P, et al. Where Would You Go on Your Next Vacation? A Framework for Visual Exploration of Attractive Places[C]∥Proceedings of 2010 Second International Conference on Advanced Geographic Information Systems, Applications, and Services(GEOPROCESSING). St. Maarten: IEEE, 2010: 21-26.

[8] HU Yingjie,GAO Song, JANOWICZ K, et al. Extracting and Understanding Urban Areas of Interest Using Geotagged Photos[J]. Computers, Environment and Urban Systems, 2015, 54: 240-254.

[9] LIU Yu, YUAN Yihong, XIAO Danqing, et al. A Point-set-based Approximation for Areal Objects: A Case Study of Representing Localities[J]. Computers, Environment and Urban Systems, 2010, 34(1): 28-39.

[10] SAMPATH A,SHAN Jie. Building Boundary Tracing and Regularization from Airborne LiDAR Point Clouds[J]. Photogrammetric Engineering & Remote Sensing, 2007, 73(7): 805-812.

[11] 程效軍, 何桂珍. 適用于多值曲面修復(fù)的空洞邊界提取方法及應(yīng)用[J]. 測(cè)繪學(xué)報(bào), 2012, 41(6): 831-837. CHENG Xiaojun, HE Guizhen. The Method and Application of Hole Boundary Extraction for Multi-valued Surface Repair[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6): 831-837.

[12] 李雯靜, 李少寧, 邱佳, 等. 凸殼內(nèi)縮法進(jìn)行多密度離散點(diǎn)群邊界檢測(cè)[J]. 測(cè)繪科學(xué), 2014, 39(9): 126-129. LI Wenjing, LI Shaoning, QIU Jia, et al. Boundary Detection of Multi-density Point Cluster Using Convex Hull Retracted Method[J]. Science of Surveying and Mapping, 2014, 39(9): 126-129.

[13] BOISSONNAT J D. Geometric Structures for Three-dimensional Shape Representation[J]. ACM Transactions on Graphics (TOG), 1984, 3(4): 266-286.

[14] EDELSBRUNNER H, KIRKPATRICK D, SEIDEL R. On the Shape of a Set of Points in the Plane[J]. IEEE Transactions on Information Theory, 1983, 29(4): 551-559.

[15] KOLINGEROVI, ?ALIK B. Reconstructing Domain Boundaries Within A Given Set of Points, Using Delaunay Triangulation[J]. Computers & Geosciences, 2006, 32(9): 1310-1319.

[16] DUCKHAM M,KULIK L,WORBOYS M, et al. Efficient Generation of Simple Polygons for Characterizing the Shape of a Set of Points in the Plane[J]. Pattern Recognition, 2008, 41(10): 3224-3236.

[17] 黃先鋒, 程曉光, 張帆, 等. 基于邊長(zhǎng)比約束的離散點(diǎn)準(zhǔn)確邊界追蹤算法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2009, 34(6): 688-691. HUANG Xianfeng, CHENG Xiaoguang, ZHANG Fan, et al. Boundary Tracing from Irregular Points Based on Ratio of Edge Length[J]. Geomatics and Information Science of Wuhan University, 2009, 34(6): 688-691.

[18] PEETHAMBARAN J, MUTHUGANAPATHY R. A Non-parametric Approach to Shape Reconstruction from Planar Point Sets Through Delaunay Filtering[J]. Computer-Aided Design, 2015, 62: 164-175.

[19] CHAUDHURI A R, CHAUDHURI B B, PARUI S K. A Novel Approach to Computation of the Shape of A Dot Pattern and Extraction of Its Perceptual Border[J]. Computer Vision and Image Understanding, 1997, 68(3): 257-275.

[20] MELKEMI M, DJEBALI M. Computing the Shape of A Planar Points Set[J]. Pattern Recognition, 2000, 33(9): 1423-1436.

[21] CHEVALLIER N, MAILLOT Y. Boundary of a Non-uniform Point Cloud for Reconstruction: Extended Abstract[C]∥Proceedings of the 27th Annual ACM Symposium on Computational Geometry. New York: ACM, 2011: 510-518.

[22] KAZHDAN M, HOPPE H. Screened Poisson Surface Reconstruction[J]. ACM Transactions on Graphics (TOG), 2013, 32(3): 29.

[23] 顧天奇, 張雷, 冀世軍, 等. 封閉離散點(diǎn)的曲線擬合方法[J]. 吉林大學(xué)學(xué)報(bào)(工學(xué)版), 2015, 45(2): 437-441. GU Tianqi, ZHANG Lei, JI Shijun, et al. Curve Fitting Method for Closed Discrete Points[J]. Journal of Jilin University(Engineering and Technology Edition), 2015, 45(2): 437-441.

[24] MERRY B, GAIN J, MARAIS P. Moving Least-squares Reconstruction of Large Models with GPUs[J]. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(2): 249-261.

[25] MISTRY S,NIRANJAN U N, GOPI M. Puzzhull: Cavity and Protrusion Hierarchy to Fit Conformal Polygons[J]. Computer-Aided Design, 2014, 46: 233-238.

[26] 武曉波, 王世新, 肖春生. Delaunay三角網(wǎng)的生成算法研究[J]. 測(cè)繪學(xué)報(bào), 1999, 28(1): 28-35. WU Xiaobo, WANG Shixin, XIAO Chunsheng. A New Study of Delaunay Triangulation Creation[J]. Acta Geodaetica et Cartographica Sinica, 1999, 28(1): 28-35.

[27] 艾廷華, 郭仁忠. 基于格式塔識(shí)別原則挖掘空間分布模式[J]. 測(cè)繪學(xué)報(bào), 2007, 36(3): 302-308. AI Tinghua, GUO Renzhong. Polygon Cluster Pattern Mining Based on Gestalt Principles[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 302-308.

[28] ESTIVILL-CASTRO V,LEE I.Argument Free Clustering for Large Spatial Point-data Sets Via Boundary Extraction from Delaunay Diagram[J]. Computers, Environment and Urban Systems, 2002, 26(4): 315-334.

[29] PAKHIRA M K, BANDYOPADHYAY S, MAULIK U. Validity Index for Crisp and Fuzzy Clusters[J]. Pattern Recognition, 2004, 37(3): 487-501.

[30] ESTIVILL-CASTRO V,LEE I. Multi-level Clustering and Its Visualization for Exploratory Spatial Analysis[J]. GeoInformatica, 2002, 6(2): 123-152.

[31] 沈蔚, 李京, 陳云浩, 等. 基于LiDAR數(shù)據(jù)的建筑輪廓線提取及規(guī)則化算法研究[J]. 遙感學(xué)報(bào), 2008, 12(5): 692-698. SHEN Wei, LI Jing, CHEN Yunhao, et al. Algorithms Study of Building Boundary Extraction and Normalization Based on LIDAR Data[J]. Journal of Remote Sensing, 2008, 12(5): 692-698.

(責(zé)任編輯：陳品馨)

An Efficient Approach to Shape Reconstruction from Planar Point Set Based on Multi-constraints

ZHU Jie1,2，SUN Yizhong1,2

1. Key Laboratory of Virtual Geographic Environment of Ministry of Education, Nanjing Normal University, Nanjing 210023,China; 2. Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023, China

An efficient algorithm to boundary representation from a planar point set in order to adapt the complexity of spatial distribution was presented in this paper. At first, an appropriate and practical data structure was designed to express geometric information and topological information, which provides an easy access to links embedded in DT serving as a basis for the filtering procedures; then the algorithm generates rough boundary based on an iterative removal of Delaunay triangulation. Furthermore, a mathematic formulation for cavities and holes was given and a statistical method to detect them was designed. Finally, a series of experiments including both simulated and real data sets to validate the effectiveness and practicability of our algorithm was conducted.

planar point set; shape reconstruction; Delaunay triangulation; multi-constraints; GIS

The National Natural Science Foundation of China (No.41671392); Special Program for basic research of Sci-tech Police of Ministry of Public Security (No.2015GABJC39)

ZHU Jie(1989—), male, PhD candidate, majors in city spatial data representation and mining.

SUN Yizhong

朱杰，孫毅中.多約束的平面點(diǎn)集形狀重構(gòu)方法[J].測(cè)繪學(xué)報(bào)，2017,46(2)：253-264.

10.11947/j.AGCS.2017.20160122. ZHU Jie，SUN Yizhong.An Efficient Approach to Shape Reconstruction from Planar Point Set Based on Multi-constraints[J]. Acta Geodaetica et Cartographica Sinica,2017,46(2):253-264. DOI:10.11947/j.AGCS.2017.20160122.

P208

A

1001-1595(2017)02-0253-12

國(guó)家自然科學(xué)基金(41671392)；公安部科技強(qiáng)警基礎(chǔ)工作專項(xiàng)(2015GABJC39)

2016-03-30

朱杰(1989—)，男，博士生，研究方向?yàn)槌鞘锌臻g數(shù)據(jù)表達(dá)與挖掘。

E-mail： Chu_Je@163.com

孫毅中

E-mail： sunyizhong_cz@163.com

修回日期： 2016-10-27