論文推薦|朱傑：多約束的平面點集形狀重構方法

《測繪學報》

構建與學術的橋樑 拉近與權威的距離

測繪地理信息與導航高端論壇 ——《測繪學報》創刊60周年學術研討會通知（第一號）

朱傑1,2

, 孫毅中1,2

1. 南京師範大學虛擬地理環境教育部重點實驗室, 江蘇 南京 210023;
2. 江蘇省地理信息資源開發與利用協同創新中心, 江蘇 南京 210023

收稿日期：2016-03-30； 修回日期：2016-10-27

基金項目：國家自然科學基金（41671392）；公安部科技強警基礎工作專項（2015GABJC39）

第一作者簡介： 朱傑(1989-),男,博士生,研究方向為城市空間數據表達與挖掘。E-mail： [email protected]

E-mail:[email protected]

摘要：針對平面點集空間分佈的複雜性，本文提出了一種基於Delaunay三角網的平面點集形狀重構方法。首先採用一種簡單且實用的數據結構以表達Delaunay三角網中嵌入的幾何信息和拓撲信息，然後由外向內迭代過濾Delaunay三角網得到一個大概邊界，最後進一步考慮邊界的凹凸信息和空洞現象，獲取最終的精細邊界。試驗結果表明與其他典型的Delaunay三角網重構方法相比，本文提出的演算法能更好地適用於平面點集空間分佈的複雜性，通過所構建的數學模型實現了凸凹多邊形內外邊界提取。

關鍵詞： 平面點集 形狀重構 Delaunay三角網 多約束 GIS

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

ZHU Jie1,2

, SUN Yizhong1,2

Abstract: 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.

Key words: planar point set shape reconstruction Delaunay triangulation multi-constraints GIS

平面點集形狀重構在GIS相關應用領域如地圖綜合[

-

]、建築物輪廓線提取、地理範圍確定以及地理信息檢索(GIR)中是一項重要而基礎的工作，旨在從一堆無序的點集(僅有坐標信息)中提取出平面點集的分佈範圍，近似地表達真實的輪廓信息。如何考慮點集空間分佈的複雜性是許多平面點集形狀重構方法面臨的主要問題。通過對國內外學者的研究分析，將這種複雜性歸納為以下4個方面：①點集的空間關係表達，包括幾何信息和拓撲信息；②空間密度分佈不均；③局部凹凸信息的精確描述；④內部空洞問題。此外，為更加精確地描述點集形狀輪廓信息，重構過程中還需要顧及重構結果的唯一性和規則性。現有平面點集形狀重構方法可以分為3類：①基於凸殼的方法；②基於Delaunay三角網的方法；③基於曲線重構的方法。基於凸殼的方法[

-

]大都採用凸殼內縮的策略獲取邊界的凹凸特徵，在一定情況下能夠處理空間密度分佈不均的情況，但由於該演算法缺少點集的拓撲信息，難以保證邊界的規則性，也無法識別空洞現象。基於Delaunay三角網的重構過程可以分為兩步：①構建Delaunay三角網；②基於圖形結構特徵提取一些幾何單元來近似地表達真實邊界情況。最早的這類重構方法是Sculpture方法[

]和

-shapes方法[

]。Delaunay Sculpture是一種剝離三角網演算法，由外向內不斷刪除不規則的三角形直到產生一個符合條件的點集形狀。基於這種思想衍生了許多演算法[

-

]，這些演算法能夠提取任意形狀的點集，剝離規則也保證了最終邊界的規則性，但這些演算法不夠穩健，難以適應複雜的凹部和空洞現象，如

-shape演算法[

]通過迭代判斷Delaunay三角網邊界邊長，將滿足閾值的邊長保留作為最終的邊界提取結果，這種全局參數對密度分佈不均的樣本數據重構效果不是很穩定，該演算法也沒有考慮空洞問題；為克服全局度量受密度變化影響較大的缺陷，

演算法[

]採用了局部度量方式對三角網進行過濾，避免了演算法的參數化，針對三角網中特定的結構特徵能夠有效識別空洞現象，但該演算法對含有規則的凹邊界和狹長空洞是失效的。

-shapes演算法類似Delaunay三角網，參數

控制了輪廓信息的含量,由於這個原因，需要不斷變化參數

值以得到理想的輪廓信息。但是，

-shapes不能準確地表達點集密度分佈不均的情況。為了顧及局部密度信息,後期出現了若干

-shapes改進演算法，如r-shape[

]、A-shapes[

]、LDA-

-complex[

]等，這些演算法採用了局部度量和全局度量策略，能夠滿足平面點集分佈不均、空洞等複雜情況，但是輸入參數過多。基於曲線重構的方法採用曲線擬合方法如泊松法[

]、最小二乘法[

]、徑向基函數法[

]估算點集的曲率，將滿足曲率閾值條件的點判定為邊界特徵候選點，最後將這些邊界點連接即達到了邊界提取的目的。曲線重構方法可以針對無規則的點雲數據提取出精度較高的邊界點，但這種方法需要計算每一個數據點的曲率值，其計算過程非常複雜。

綜上分析，基於Delaunay三角網的平面點集重構方法原理較簡單，其結構能夠很好地彌補不規則點集的幾何信息和拓撲信息，較其他方法相對系統和穩健。針對該方法存在的問題，本文基於Delaunay三角網提出了一種有效的平面點集重構方法，首先採用一種局部度量方式對整個Delaunay三角網(凸殼)進行過濾得到初始邊界，然後通過構建有效的數學模型實現凸凹多邊形內外邊界提取。

1 理論基礎1.1 數據結構

Delaunay三角網中包含了3種實體要素：點、邊和三角形，本文採用了一種簡單且實用的數據結構，即在Delaunay三角網中每個三角形記錄了其相應的三條邊，每條邊存儲了兩個端點信息，包括每個端點的坐標信息。此外，為了更有效地對邊界進行操作，每條邊還記錄了鄰近三角形信息，每個點存儲了鄰域邊信息。採用以上數據組織方式來表達Delaunay三角網中3種要素之間的拓撲信息對邊界搜索、提取以及拓撲檢查有著重要的作用。

1.2 相關定義

設平面點集為S，DTS為平面點集S所構建的Delaunay三角網，DTS中的三角形、邊、點分別表示為t、e、v。

(1) 邊界邊：如果DTS中一條邊e屬於邊界邊，則這條邊只屬於一個三角形，即e不是公共邊。基於Delaunay三角網的平面點集形狀重構方法最終結果是由一系列邊界邊構成。

(2) 邊界三角形：如果DTS中一個三角形屬於邊界三角形，則這個三角形至少包含一條邊界邊。

(3) 邊界點：如果DTS中一個點v屬於邊界點，則這個點必定在邊界邊上，其餘的點都是內點。

(4) 邊界規則性：在對DTS過濾過程中要保持邊界的規則性，必須排除以下幾種情況：

當一個邊界邊從DTS中刪除后，需要對新生成的邊界進行拓撲檢驗，如果邊界出現以上幾種情況，則邊界邊予以保留，其他情況下則可以刪除。

：給定一個覆蓋點集

的多邊形

，Conv(P)表示

的凸殼,

表示Conv(P)與

之間的開放區域，每個開放區域用一條封閉曲線

來表示，這些封閉曲線構成的區域稱之為凹部。在DTS中，凹部內的邊稱之為凹邊，每個凹部由一條可見邊界邊和若干凹邊構成。

(6) 空洞：從Delaunay三角網的結構而言，空洞是一個封閉的凹部區域，即每個空洞由若干凹邊構成而不存在可見邊界邊，從某種意義上而言，凹部和空洞具有相似的結構特徵。

2 演算法過程

本文提出的演算法是一種由外向內有序過濾Delaunay三角網的過程。首先按照設定的數據結構採用生長法[

]對平面點集構建Delaunay三角網，將點群圍在一個凸殼內，找出初始邊界；然後根據一種有序的篩選策略對初始邊界向內過濾，得到一個大概邊界，過濾的過程中要保證邊界的規則性；最後進一步考慮邊界的凹凸信息和空洞現象，得到最終的準確邊界。演算法可分為兩部分：粗邊界提取和精細邊界生成。

2.1 粗邊界提取

Delaunay三角網提供了3個參數：周長、角度和邊長。周長和邊長閾值都屬於全局度量方式，容易受密度變化的影響，角度作為一種局部度量方式要優於周長和邊長。根據格式塔鄰近性原則[

]可知平面點集的邊界由點群外圍且距離相近的點連接而成，換言之，在一個邊界三角形中，如果邊界邊所對應的角度越大，則兩個邊界點之間的距離也就越大，兩個邊界點之間不符合鄰近性原則，應當刪除它們之間的連線(即邊界邊)。上述性質能夠適應空間實體密度的變化，為此本文採用角度作為重構參數。給定一個平面點集，設邊界邊為Be,邊界三角形中邊界邊所對應的角度表示為Angle(Be)，角度閾值為

，其粗邊界提取的具體流程如

所示。

粗邊界提取過程採用了排序-過濾的策略，這是因為邊界處的幾何特徵與內部相比具有明顯的「不規則性」，排序的效果是為了過濾掉最不規則的元素，保證邊界提取結果的唯一性；另一方面粗邊界提取演算法雖然在一定程度上能夠反映形狀輪廓的凹凸信息，但是無法識別複雜的凹部和空洞現象，需要進一步施加約束條件，生成精細邊界。

2.2 精細邊界生成

粗邊界提取過程採用了基於角度的過濾策略對以下兩種結構是失效的。

(1) 含有規則三角形的凹部。如果凹部存在如圖 3(a)所示的規則三角形時，其作為邊界三角形邊界邊所對應的角度很小，為刪除此邊界邊必須降低閾值R，但閾值過小，邊界會過度收縮，難以得到理想的重構效果。如果無法刪除此邊界邊，勢必會阻礙凹部的進一步探測。

(2) 空洞。粗邊界提取是由外向內過濾邊界邊的內縮過程，由邊界邊的定義可知，空洞內的邊(圖 4(a))不屬於邊界邊，因此，空洞現象無法被識別。

在1.2節中指出凹部和空洞可以視為同一種結構，它們通常位於較周邊密度稀疏的區域，採用Voronoi圖來表示這種密度變化，從圖 3(b)和圖 4(b)中可以看出凹部和空洞區域密度較小，其周邊區域的密度相對較高。選用密度變化來定義這兩種結構的原因在於Delaunay三角網是一個帶有密度性質的空間鄰近性模型，不需要任何參數設置，參數信息完全包含在三角網中。從圖 3(a)和圖 4(a)中可以看出，位於這兩種結構的邊界點其鄰域內連線長短不一，梯度變化較大。基於此，採用一個相對參數來量化這種特徵，即通過判斷點的鬆散度來探測凹部和空洞，具體表達如下。

點的鬆散度：給定一個平面點集D，由點集生成的Delaunay三角網表示為DT。針對DT內任一點實體P，F(P)表示點實體P的鬆散度，表示為

(1)

(2)

(3)

式中，Local_Mean_Length(

)表示點

的鄰域內所有邊長的均值；Local_SD(

)表示點

鄰域內所有邊長的標準差；

表示點

直接鄰近對象的個數；

表示點

鄰域內的邊長。

F(P)值越小，說明該對象鄰域內邊長梯度變化小。真實輪廓內的點由於鄰域內邊長變化較小，其F(P)值較小，相反，空洞和凹部處的邊界點F(P)值較大(圖 3(c)和圖 4(c))。因此，針對DT內任一點實體P，凹部和空洞的鬆散度可以表達為

式中，Sets表示凹部和空洞的鬆散度集合；T表示鬆散度閾值。通過集合Sets可以找到空洞和凹部的邊界點，這些邊界點鄰域內連線長短不一，如何篩選這些邊長是關鍵問題。從空間聚類的角度出發，鬆散度較大的主要原因在於長邊的存在，為刪除這些不合理的長邊，本文採用了AUTOCLUST演算法[

]，其根據密度信息來探測長邊，具體表達如下。

長邊約束：給定一個平面點集D，由點集生成的Delaunay三角網表示為DT。針對DT內任一點實體P，Longedge表示與P連接的所有邊的長邊約束條件，表示為

(5)

(6)

式中，Local_Mean_Length(

)表示

鄰域內所有邊長的均值；Local_SD(

)表示點

鄰域內所有邊長的標準差；Global_SD表示DT內所有對象Local_SD(

)的平均值；

表示平面點集數目。

針對網內任一點實體P，若與其直接相連接的邊的長度大於Longedge，則刪除該邊。對於保留下來的短邊可以調用粗邊界提取進行約束。基於此，精細邊界提取的具體過程如下。

(1) 在粗邊界提取的結果基礎上，計算整個點集的鬆散度並獲取集合Sets。

(2) 將Sets分為兩部分：邊界點的鬆散度和內點鬆散度，如果點集同時存在凹部和空洞，凹部識別優先於空洞，即邊界點遍歷優先於內點。

精細邊界提取過程中顧及了兩個順序，一是優先順序，凹部和空洞識別的優先順序，鄰域內邊長和邊界邊的遍歷優先順序，優先順序能夠確保過濾掉最不規則的元素；另一個順序是遍歷順序，鬆散度遍歷和鄰域邊長遍歷都採用了降序排列，這確保了邊界提取的唯一性。

2.3 鬆散度閾值T的確定

值是識別凹部和空洞邊界的重要參數，為了保證閾值

能夠適應不同點集的需求，設計了一種自適應的閾值確定方法。由點的鬆散度內涵可知，邊界處點的鬆散度要大於真實輪廓內點的鬆散度，本文將閾值選擇看作是一種二類分割問題，通過目標函數對點集進行判別以尋找到邊界處與真實輪廓之間過渡的點。具體過程為首先計算整個點集的鬆散度

(

)並按照升序進行排列，記為集合

=

(

12

)；然後通過目標函數對集合

進行順序判別，如果出現不滿足目標函數的點，判別結束則此點的鬆散度即為閾值T。自適應閾值確定方法的目標函數表示為

式中，

表示

值；表示集合

的均值；

表示集合

的標準差；k是調節參數,

越大，則鬆散度閾值

越大，網內較多的邊將會被保留。目標函數通過探測過渡點將鬆散度劃分為兩部分，為達到二類分割的最佳效果即類內方差最小或類間方差最大，引入PBM指數來求解參數

。PBM指數作為一個相對評價指標能夠滿足緊密性與分離性的聚類準則，其具體表示為

(8)

(9)

式中，

表示簇的數量；

表示簇

中實體數量；

表示簇

的質心；

表示簇

的內部距離(簇內所有空間對象到其質心的距離之和)；

表示數據集分為

個簇的聚類內部距離；

表示空間簇間的分離度，其隨著

增大而增大，最大值為數據集中最遠兩個簇的質心距離。PBM指數越大，則表示得到的聚類結果越可靠。

結合粗邊界和精細邊界提取過程，分別對含有規則三角形的凹部和空洞機進行識別。首先調用粗邊界提取流程對含有凹部或者空洞的Delaunay三角網(參考圖 3(a)和4(a))進行過濾，其結果如圖 7(a)和圖 8(a)所示；在粗邊界提取的基礎上調用精細邊界提取流程，通過PBM指數確定鬆散度閾值T(參考圖 7(d)—(e)和圖 8(d)—(e))以此找到位於凹部或者空洞處的邊界點(圖 7(b)和圖 8(b))，篩選邊界點的鄰域邊從而得到最終的邊界(圖 7(c)和圖 8(c))。

3 試驗分析3.1 參數R的選擇

粗邊界和精細邊界的生成過程中，角度閾值

是邊界收斂的重要約束條件。平面點集存在兩種形式：一是含有空洞和凹部的點集，另一個是不含有以上兩種現象的點集。針對不含有空洞和凹部的點集，Delaunay三角網內的三角形近似等邊三角形，此類點集的凸殼邊界即為理想的邊界收斂結果。對於含有空洞和凹部的點集，需要深入討論角度閾值

對此類點集邊界收斂的作用過程，為此，本文設計了幾組模擬試驗來評價參數

對重構結果的精度影響，以獲取合適的參數取值範圍為用戶在參數

選擇方面提供參考。模擬試驗採用既定的形狀和點集分佈類型，L2誤差范數

式中,O代表原始多邊形；S代表重構結果。L2誤差范數通過原始多邊形與重構結果的面積比例大小評價重構效果，L2誤差范數等於0，則表示重構結果與原始多邊形邊界完全吻合。

模擬實驗採用了5組形狀數據：雲南、內蒙古、F字(宋體)、K字(宋體)和A字(宋體)，5組形狀數據邊界具有明顯的不規則性，包含了大量的凹部和空洞；考慮到點集分佈類型(如隨機分佈)有可能使點集內部產生空洞現象，因此點集分佈類型選擇均勻分佈；每組形狀數據內部生成的點集數目確保能夠覆蓋到形狀邊界，模擬實驗採用的點集數目分別是70、100、130和160，代表了不同的點集密度。由角度參數的內涵可知閾值R的取值範圍在[0, 180](試驗取值間隔為10)，圖 11顯示了基於參數R每組形狀數據邊界收斂的L2誤差范數變化曲線，5組數據的邊界收斂過程大體相似這主要是因為空洞和凹部是等價的結構；另外，每組數據的邊界收斂過程並沒有隨點集密度變化而發生改變。當R取值180時粗邊界中Delaunay三角網沒有邊被刪除(如圖 9所示)，網內存在大量的「不規則」長邊，此時精細邊界中的鬆散度閾值T也較高(如圖 10所示)，只能刪除部分不規則長邊，無法徹底識別凹部或者空洞，邊界收斂效果不理想，表現為L2誤差范數值較高(如圖 11(b)所示)；當R取值0時，網內的邊本該全部刪除，但是由於受到邊界規則性的約束邊界邊不能存在懸挂邊、鏈式邊和交叉點，保留下來的邊界呈「鋸齒狀」，如圖 9和10所示，邊界收斂效果同樣不理想，L2誤差范數值較高，如圖 11(b)所示，因此要想獲得理想的邊界收斂效果R的取值範圍應該是0＜R＜180。在180到0這個區間內隨著參數R取值逐漸減少粗邊界不斷向內過濾，如圖 9所示，精細邊界中的鬆散度閾值T也相應變小，如圖 10所示，閾值R在一定區間內凹部或者空洞內的邊得以徹底識別並刪除，邊界收斂效果較理想，如圖 10中R取[60,110]的結果，表現為L2誤差范數值較低，如圖 11(b)所示。點集中的凹部或者空洞徹底識別後，Delaunay三角網內鬆散度差異會很小，二類分割的結果有可能是鬆散度同屬一類，那麼粗邊界結果與精細邊界結果是等價的，如圖 9和圖 10中R取[40,80]的結果，如果繼續降低閾值R向內過濾，邊界收斂效果會變差，表現為L2誤差范數值不斷提高，如圖 11(b)所示。

結合模擬試驗的邊界收斂過程和圖 11中不同點集密度邊界收斂的L2誤差范數變化過程可以得出，角度閾值R取值範圍在[80,120]內就含有空洞和凹部的點集而言可以取得理想的邊界收斂結果。

3.2 試驗結果對比

為了驗證本文方法的有效性與優勢性，將提出的方法與其他兩種基於Delaunay三角網的典型方法χ-shape和∂RGG演算法進行比較分析，試驗內容主要包含以下幾個方面：

3.2.1 非均勻分佈

圖 12分別顯示了在平面點集分佈不均情況下3種方法的邊界提取結果。χ-shape演算法由於採用邊長閾值作為度量參數，當點集分佈不均時邊界提取效果不是很穩定，會產生大塊的鋸齒現象；∂RGG演算法和本文方法都採用了局部度量參數(三角形外接圓心和角度)能夠獲取合理的重構結果；另外，平面點集形狀重構本質上屬於不確定性問題，即合理的重構結果並不唯一。雖然∂RGG是一種自動構建形狀輪廓的方法，不需要任何參數，但從不確定性角度而言，本文提出的方法能夠產生若干合理的重構結果，提供了更多的重構細節。

3.2.2 含有規則三角形的凹部

圖 13分別顯示了3種方法對含有規則三角形的凹部處理結果。當凹部內點集分佈均勻時(圖 13(a))，∂RGG演算法採用的局部度量方式只考慮到了狹長的邊界三角形，無法探測角度較小的三角形，因此凹部探測不徹底；本文方法和χ-shape演算法都能夠準確地識別這一類凹部。當凹部內點集分佈不均時(圖 13(b))，與χ-shape演算法相比，本文針對凹部給出了合理的數學定義以及識別方法，具有較強的理論保證，從而能夠獲取準確的重構結果。

3.2.3 空洞現象

圖 14分別顯示了3種方法對空洞現象的處理結果。χ-shape演算法無法識別空洞；∂RGG演算法針對三角網的結構可以對空洞現象構造邊界，但它無法識別狹長的空洞現象；本文方法能夠識別多樣的空洞現象，包括狹長空洞(圖 14)和球狀空洞(圖 8)。

3.2.4 雜訊和非連通區域

3種方法的重構結果都包含了平面點集中所有點包括雜訊，若要解決雜訊問題可以採用空間聚類的方法如AMOEA演算法[

]對平面點集進行預處理，剔除雜訊；在一些實例中，有些點集是非連通區域如「i」或者「=」,考慮到邊界的規則性，三種方法同樣不能生成非連通區域。

3.3 應用實例

本節將引入兩個應用實例來驗證本文方法的實用性，以發現平面點集重構方法在不同領域內的應用潛力。城市輪廓是城市空間形態分析中一個重要的組成部分，本文基於POI數據利用提出的方法提取城市輪廓線。圖 15(a)顯示了洛陽市地名地址POI數據(灰色部分)，由於城市輪廓線表達的是一個城市的大概分佈範圍，因此這裡採用粗邊界提取方法和凹部識別演算法，不需要構造城市內部的邊界。圖 15(a)給出了洛陽市城市輪廓提取結果(黑色曲線)，將提取的城市輪廓線與洛陽市遙感影像圖(圖 15(b))疊加比較，結果如圖 15(c)所示，紅色曲線代表洛陽市遙感影像邊界線，黑色曲線代表輪廓提取結果，二者邊界線有很高的吻合度。

另一個實例是基於LIDAR數據的建築輪廓線提取，數據來源於文獻[31]給出的馬來西亞吉隆坡城市中心區各類不同幾何形狀的建築，基於本文方法提取的各種形狀建築輪廓線結果(如圖 16所示)與文獻[31]的提取結果相似，這表明提出的方法可適用於凸凹多邊形內外邊界提取。

4 結 論

本文提出了一種多約束的平面點集形狀重構方法，相比已有方法，該方法能夠更好地適應平面點集空間分佈的複雜性。通過模擬試驗和應用實例可以發現：①本文方法可以適應空間密度分佈不均、凹凸信息精確描述、內部空洞等複雜情況下的平面點集形狀重構；②需要的輸入參數只有一個且在試驗部分中給出了指導信息，方便用戶實際使用；③重構過程中對平面點集中存在的凹部和空洞給出了一種有效的數學描述以及識別方法，具有較強的理論保證。進一步改進的方面有：實驗分析中缺少對演算法自身的定量分析包括點集密度變化和點集分佈類型的適應性分析；在應用領域中還局限在二維平面中，後期進一步考慮拓展到三維空間中。

【引文格式】朱傑，孫毅中。 多約束的平面點集形狀重構方法[J]. 測繪學報，2017，46(2)：253-264. DOI: 10.11947/j.AGCS.2017.20160122

權威 | 專業 | 學術 | 前沿

微信投稿郵箱 | [email protected]

歡迎加入《測繪學報》作者QQ群： 297834524