雙閾值A(chǔ)lpha Shapes算法提取點(diǎn)云建筑物輪廓研究

李云帆，譚德寶，高 廣，劉 瑞

(1.長江科學(xué)院 空間信息技術(shù)應(yīng)用研究所，武漢 430010; 2.深圳飛馬機(jī)器人科技有限公司，廣東 深圳 518000；3.哈爾濱工業(yè)大學(xué) 深圳研究生院，廣東 深圳 518055;4.深圳市房地產(chǎn)評估發(fā)展中心，廣東 深圳 518040)

?

雙閾值A(chǔ)lpha Shapes算法提取點(diǎn)云建筑物輪廓研究

李云帆1，譚德寶1，高 廣2，劉 瑞3,4

(1.長江科學(xué)院 空間信息技術(shù)應(yīng)用研究所，武漢 430010; 2.深圳飛馬機(jī)器人科技有限公司，廣東 深圳 518000；3.哈爾濱工業(yè)大學(xué) 深圳研究生院，廣東 深圳 518055;4.深圳市房地產(chǎn)評估發(fā)展中心，廣東 深圳 518040)

針對單一閾值的Alpha Shapes算法在提取點(diǎn)云建筑物輪廓時(shí)存在的輪廓精度和完整性難以兼顧的問題，提出一種雙閾值的Alpha Shapes算法，利用簡單環(huán)的概念設(shè)計(jì)輪廓搜索算法，獲得既有較好完整性又有較高幾何精度的建筑物輪廓線；然后，利用一種最小二乘的輪廓線化簡算法對提取出的初始輪廓進(jìn)行化簡，與經(jīng)典的Douglas Peucker算法相比，在存在噪聲的情況下，該方法化簡后的輪廓線更接近實(shí)際的輪廓線。

LiDAR；建筑物輪廓提?。籖ANSAC；Alpha Shapes算法

1 研究背景

建筑物的輪廓信息是建筑物提取與三維模型重建的重要基礎(chǔ)，已廣泛應(yīng)用于城市基礎(chǔ)信息庫更新、目標(biāo)識別、災(zāi)害預(yù)估、變化檢測、房地產(chǎn)等領(lǐng)域[1]。目前，基于機(jī)載LiDAR數(shù)據(jù)追蹤建筑物平面輪廓的一般方法是將點(diǎn)云內(nèi)插成深度影像，然后利用圖像分割算法對深度影像進(jìn)行分割，最后用掃描線法、鄰域搜索法等方法實(shí)現(xiàn)建筑物邊界的追蹤[2-5]。這些方法存在的問題是所追蹤到的邊緣是離散點(diǎn)集的粗略邊界，精度較低。也有一些學(xué)者研究了直接從離散點(diǎn)集提取其輪廓的方法，如黃先鋒等[6]提出一種基于平面離散點(diǎn)的邊緣追蹤算法，該算法將邊長比作為約束條件，降低了算法參數(shù)對點(diǎn)密度的依賴性，從而提高算法對細(xì)長特征或分布不均勻的點(diǎn)集邊緣提取的適應(yīng)性，但是約束條件的閾值設(shè)置不當(dāng)易造成邊緣過渡收縮的現(xiàn)象；Alpha Shapes算法最早由Edelsbrunner等[7]提出，后來許多學(xué)者對其進(jìn)行改進(jìn)并應(yīng)用于機(jī)載LiDAR數(shù)據(jù)處理領(lǐng)域，該算法理論完善、效率高，還能夠處理較復(fù)雜的建筑物輪廓提取問題，主要缺點(diǎn)是不適用于分布不均勻的數(shù)據(jù)，同時(shí)算法參數(shù)的選擇也較困難。

從點(diǎn)云中提取建筑輪廓可歸結(jié)為恢復(fù)離散點(diǎn)集的原始形狀，而Alpha Shapes算法[7]是一種有效的方法。Alpha Shapes算法是一種確定性算法，有著嚴(yán)格的數(shù)學(xué)定義，對于任意一個(gè)有限點(diǎn)集S，Alpha Shapes算法得到點(diǎn)集形狀?S是確定的，另外，用戶還可以通過調(diào)整算法的唯一參數(shù)α來控制點(diǎn)集形狀?S的精細(xì)程度。鑒于Alpha Shapes算法的優(yōu)良性能，國內(nèi)外不少學(xué)者提出利用Alpha Shapes算法直接從機(jī)載LiDAR數(shù)據(jù)提取建筑物輪廓線[8-10]。但是，在實(shí)際應(yīng)用中，仍存在一些問題需要解決：①Alpha Shapes算法主要適用于密度相對均勻的點(diǎn)集數(shù)據(jù)，這是由算法的本質(zhì)決定的，因?yàn)辄c(diǎn)集形狀的精細(xì)程度完全由參數(shù)α控制，單一參數(shù)的Alpha Shapes算法無法適應(yīng)密度差異較大的點(diǎn)集數(shù)據(jù)；②Alpha Shapes算法在處理凹型點(diǎn)集時(shí)處理效果不太好，如果α值較大的話，凹拐角容易被鈍化掉，如果α值較小的話，又容易得到破碎的點(diǎn)集形狀，沈蔚等[9]指出，應(yīng)該將α值設(shè)置為1～2倍的平均點(diǎn)間距，此時(shí)得到的點(diǎn)集形狀相對完整又不會太破碎。

針對上述問題，本文提出一種雙閾值的Alpha Shapes算法，用來完整地提取建筑輪廓;然后，采用基于最小二乘的輪廓線對提取出來的初始輪廓線進(jìn)行化簡。

2 基于雙閾值A(chǔ)lpha Shapes算法的輪廓線提取

2.1 雙閾值α-shape的獲取

令DT(S)為點(diǎn)集S的Delaunay三角網(wǎng)，?S1，?S2分別為參數(shù)設(shè)置為α1和α2時(shí)Alpha Shapes算法得到的α-shape，文獻(xiàn)[7]已證明任意閾值下的α-shape均為DT(S)的子集，即?S1?DT(S)，?S2?DT(S)，因此α-shape的獲取過程為：首先采用逐點(diǎn)插入算法構(gòu)建點(diǎn)集S的Delaunay三角網(wǎng)DT(S)(詳見文獻(xiàn)[11])，然后依次對DT(S)中的每條邊進(jìn)行Alpha Shapes測試，如圖1所示，pq為DT(S)中的一條邊，圓C為過pq且半徑為α的圓(圓心坐標(biāo)見式(1)和式(2))，如果沒有其他頂點(diǎn)在圓C內(nèi)，則邊pq屬于α-shape。

(1)

(2)

圖1 Alpha Shapes測試原理Fig.1 Principle of Alpha Shapes test

2.2 基于廣度優(yōu)先搜索的簡單環(huán)查詢算法

基于廣度優(yōu)先的搜索算法可以用來進(jìn)行無向圖頂點(diǎn)遍歷，本文提出一種搜索策略，可以顯著提高搜索效率。

首先引入2個(gè)關(guān)鍵概念：簡單路徑和簡單環(huán)。簡單路徑指一個(gè)無向圖內(nèi)，從某個(gè)起點(diǎn)出發(fā)，經(jīng)過不重復(fù)的端點(diǎn)到達(dá)另外一個(gè)端點(diǎn)的過程中所形成的路徑；簡單環(huán)指一個(gè)無向圖內(nèi)，從某個(gè)起點(diǎn)出發(fā)，經(jīng)過一條簡單路徑回到起點(diǎn)所形成的路徑。

令G為?S1和?S2中的邊所構(gòu)建的無向圖，建立無向圖G的鄰接表L，假設(shè)p為無向圖G中的任一頂點(diǎn)，from[p]表示從某一起點(diǎn)出發(fā)，在到達(dá)終點(diǎn)p之前所經(jīng)過的最后一個(gè)頂點(diǎn)；dist[p]表示從某一起點(diǎn)出發(fā)到達(dá)終點(diǎn)p所經(jīng)過的簡單路徑的長度。利用dist[p]可以僅搜索一定長度閾值內(nèi)(如20 m)的簡單環(huán)，從而顯著提高算法的搜索效率。以下為算法具體步驟。

步驟(1)：按順序從無向圖G中選取一個(gè)頂點(diǎn)p，令p為起點(diǎn)，經(jīng)過p的簡單環(huán)為Loop，將所有from值設(shè)置為null，將起點(diǎn)p的dist值設(shè)置為0，其他頂點(diǎn)的dist值設(shè)置為無窮大，根據(jù)鄰接表L創(chuàng)建無向圖G的鄰接矩陣M，將p壓入搜索隊(duì)列Q中。

步驟(2)：從搜索隊(duì)列Q中取出最早壓入的頂點(diǎn)q，轉(zhuǎn)步驟(3)。

步驟(3)：根據(jù)鄰接表L依次判斷q的鄰接點(diǎn)qi。①查詢鄰接矩陣M，如果q與qi不相連，則判斷一下鄰接點(diǎn)；②在鄰接矩陣M中，將q與qi鄰接關(guān)系去除，避免該路徑被多次經(jīng)過；③判斷鄰接點(diǎn)qi是否已經(jīng)加入過隊(duì)列，如果qi沒有加入過隊(duì)列(即dist[qi]為無窮大)，轉(zhuǎn)④，否則轉(zhuǎn)⑤；④更新from[qi]為q，dist[qi]為dist[q]+d(q,qi)，如果dist[qi]<閾值條件，則將qi加入到搜索隊(duì)列Q中，返回步驟(3)繼續(xù)判斷下一個(gè)鄰接點(diǎn)；⑤判斷路徑p-q-qi-p是否為簡單環(huán)，如果是簡單環(huán)且該環(huán)的長度比Loop短，則將Loop更新為該環(huán)。

步驟(4)：如果搜索隊(duì)列Q不為空，記錄Loop并轉(zhuǎn)步驟(2)，否則轉(zhuǎn)步驟(1)。

2.3 對應(yīng)路徑篩選

篩選過程僅考慮由簡單路徑l1和l2構(gòu)成的簡單環(huán)，其中l(wèi)1和l2分別屬于?S1和?S2。篩選過程分以下3種情況進(jìn)行討論：

(1) 如圖2(a)所示，如果l1的長度是l2的5倍以上，則丟棄l1，保留l2。

(2) 如圖2(b)所示，如果l2的兩個(gè)鄰邊接近垂直，且l1上所有端點(diǎn)到l2任一鄰邊的距離均較小，則丟棄l2，保留l1。

(3) 如圖2(c)所示，如果l2與l2兩個(gè)鄰邊接近平行，且l1上的端點(diǎn)到l2的距離小于一定的閾值(如0.5倍的平均點(diǎn)間距)，則丟棄l1，保留l2。

圖2 對應(yīng)路徑篩選的3種情況

2.4 閉合輪廓線獲取

由第2.1—2.3節(jié)步驟獲得的中間結(jié)果是一些離散的邊，而最終所需的建筑物輪廓線是按順序連接的閉合多邊形。該過程可以采用基于深度優(yōu)先的搜索算法，算法詳細(xì)流程與步驟(2)類似，主要有2點(diǎn)不同：基于深度優(yōu)先的搜索算法使用堆棧，而基于廣度優(yōu)先的搜索算法使用隊(duì)列；基于深度優(yōu)先的搜索算法的目標(biāo)是長度大于閾值的環(huán)，而基于廣度優(yōu)先的搜索算法的目標(biāo)是長度小于閾值的環(huán)。

圖3 提取的某棟建筑物輪廓Fig.3 Results of extracting building contour

3 基于最小二乘的輪廓線化簡

利用雙閾值的Alpha Shapes算法得到的建筑物閉合輪廓非常粗糙，一般需要先對其進(jìn)行化簡處理。Douglas Peucker算法是一種經(jīng)典的矢量壓縮算法，被眾多GIS系統(tǒng)所采用。針對建筑物輪廓線化簡問題，Douglas Peucker算法存在易受噪聲點(diǎn)干擾的問題。

本文提出一種基于最小二乘法的輪廓線化簡算法，該算法需要2個(gè)參數(shù)，即距離閾值dmax和長度閾值L，算法的詳細(xì)步驟如下所示。

(2) 令集合U的兩端點(diǎn)為P和Q，分別以P和Q為起點(diǎn)向兩側(cè)增長，增長過程中將會遇到新的頂點(diǎn)，如果新的頂點(diǎn)到直線L的距離

(3) 如果步驟(2)中有新的頂點(diǎn)加入到集合U中，則對集合U進(jìn)行最小二乘擬合，得到新的直線L，轉(zhuǎn)步驟(2)；否則轉(zhuǎn)步驟(4)。

(4) 判斷集合U的長度，如果U的長度大于閾值L，則保留集合的兩端點(diǎn)，丟棄中間頂點(diǎn)。

(5) 如果還有連續(xù)的3個(gè)頂點(diǎn)集都沒有判斷過，轉(zhuǎn)步驟(1)；否則判斷長度閾值L的大小，如果L大于2～3倍的平均點(diǎn)間距，縮小長度閾值至0.8L，轉(zhuǎn)步驟(1)。

4 實(shí)驗(yàn)結(jié)果

選取一棟建筑物點(diǎn)云為實(shí)驗(yàn)數(shù)據(jù)(如圖3(a))，該數(shù)據(jù)已經(jīng)過了分類處理，一共包含9 170個(gè)建筑物激光腳點(diǎn)，平均點(diǎn)間距約為0.75m。雙閾值A(chǔ)lphaShapes算法采用的α值為0.5m和1.5m。圖3(b)為α值為0.5m時(shí)AlphaShapes算法得到的建筑物輪廓，由于機(jī)載LiDAR數(shù)據(jù)不太均勻，在有些地方處點(diǎn)間距>1m(2倍的α值)，如圖3(b)的上方較多虛假的輪廓線被提取出來，但是在凹拐角處的建筑物輪廓線比較精確地描述了建筑物的原始形態(tài)；圖3(c)為α值為1.5m時(shí)AlphaShapes算法得到的建筑物輪廓線，該輪廓線整體比較完整，但是存在比較明顯的凹拐角被鈍化的問題，在圖中用圓形標(biāo)注出了一個(gè)凹拐角被鈍化的示例；圖3(d)是對圖3(b)和圖3(c)的提取結(jié)果構(gòu)建無向圖后，利用廣度優(yōu)先搜索算法得到的簡單環(huán)，可以發(fā)現(xiàn)存在問題的虛假輪廓和凹拐角基本都被包含在提取出的簡單環(huán)中，通過對簡單環(huán)的篩選，得到如圖3(e)所示的建筑物輪廓，該輪廓既有較好的完整性，又能夠較精確地描述建筑物的原始形態(tài)；最后對圖3(e)中提取的輪廓線施用基于最小二乘法的化簡算法，得到化簡后的建筑物輪廓線。

5 結(jié) 語

從建筑物點(diǎn)云中提取輪廓線是車載、機(jī)載激光雷達(dá)數(shù)據(jù)處理中的一個(gè)熱門研究方向。本文提出一種新的建筑物輪廓線提取和化簡方法，該方法主要有2個(gè)優(yōu)點(diǎn)：

(1) 針對單一閾值的AlphaShapes算法存在輪廓精度和完整性難以兼顧的問題，提出一種雙閾值的AlphaShapes算法，利用簡單環(huán)的概念設(shè)計(jì)輪廓搜索算法，可以獲得既有較好完整性又有較高幾何精度的建筑物輪廓線。

(2) 采用一種基于最小二乘的輪廓線化簡算法，與經(jīng)典的DouglasPeucker算法相比，在存在噪聲的情況下，該算法化簡后的輪廓線更接近實(shí)際的輪廓線。

采用真實(shí)的機(jī)載點(diǎn)云數(shù)據(jù)設(shè)計(jì)實(shí)驗(yàn)，證明了本文方法的有效性。但是該方法仍然存在不足之處，譬如AlphaShapes算法的雙閾值的取值自適應(yīng)性不高，對點(diǎn)云數(shù)據(jù)本身特征利用不足，這也是下一步的研究方向。

[1]SAMPATHA,SHANJ.BuildingBoundaryTracingandRegularizationfromAirborneLiDarPointClouds[J].PhotogrammetricEngineeringandRemoteSensing, 2007, 73(7): 805.

[2]錢 韜. 從DSM數(shù)據(jù)中自動提取建筑物的方法研究[J]. 測繪與空間地理信息, 2008, 31(6): 137-140.

[3] 楊 洋，張永生，馬一薇，等. 基于LiDAR數(shù)據(jù)的建筑物輪廓提取[J]. 測繪科學(xué), 2010, 35(3): 203-205.

[4] 王大瑩，程新文，潘慧波，等. 基于最佳閾值形態(tài)學(xué)方法對機(jī)載LiDAR數(shù)據(jù)進(jìn)行邊緣提取[J]. 測繪工程, 2009, 18(2): 34-37.

[5] 馬 文，岳建平，曹 爽. 基于影像分割技術(shù)的LiDAR數(shù)據(jù)建筑物邊緣提取[J]. 地理與地理信息科學(xué), 2010, 26(4): 57-59.

[6] 黃先鋒，程曉光，張 帆，等. 基于邊長比約束的離散點(diǎn)準(zhǔn)確邊界追蹤算法[J]. 武漢大學(xué)學(xué)報(bào): 信息科學(xué)版, 2009, 34(6): 688-691.

[7]EDELSBRUNNERH,KIRKPATRICKD,SEIDELR.OntheShapeofaSetofPointsinthePlane[J].IEEETransactionsonInformationTheory, 1983, 29(4): 551-559.

[8] 李云帆. 機(jī)載LiDAR數(shù)據(jù)聯(lián)合航空影像的城市建筑物三維重建研究[D]. 武漢：武漢大學(xué), 2012.

[9] 沈 蔚，李 京，陳云浩，等. 基于LiDAR數(shù)據(jù)的建筑輪廓線提取及規(guī)則化算法研究[J]. 遙感學(xué)報(bào), 2008, 12(5): 692-698.

[10]JOCHEMA,H?FLEB,RUTZINGERM, et al.AutomaticRoofPlaneDetectionandAnalysisinAirborneLiDarPointCloudsforSolarPotentialAssessment[J].Sensors, 2009, 9(7): 5241-5262.

[11]DEBERGM,VANKREVELDM,OVERMARSM, et al.ComputationalGeometry[M].US:Springer, 2000.

(編輯：王 慰)

Extraction of Building Contour from Point Clouds Using DualThreshold Alpha Shapes Algorithm

LI Yun-fan1，TAN De-bao1，GAO Guang2，LIU Rui3,4

(1.Spatial Information Technology Application Department, Yangtze River Scientific Research Institute,Wuhan 430010, China; 2.Shenzhen Feima Robotics Co., Ltd., Shenzhen 518000, China;3.Shenzhen Graduate School, Harbin Institute of Technology，Shenzhen 518055, China；4.Center for Assessment and Development of Real Estate Shenzhen, Shenzhen 518040, China)

To balance the contour accuracy and completeness of single threshold Alpha Shapes in extracting point cloud building contours, we present a dual-threshold Alpha Shapes algorithm using a simple ring design concept contour search algorithm to obtain both a good integrity and a relatively high geometric precision of the building’s contour. Furthermore, the initial contour is simplified based on least squares algorithm. In the presence of noise, the simplified contour lines of the present algorithm are closer to the actual contours compared with the classic Douglas Peucker algorithm.

LiDAR; building boundaries extraction; RANSAC; Alpha Shapes algorithm

2016-08-10

中央級公益性科研院所基本科研業(yè)務(wù)費(fèi)項(xiàng)目(CKSF2014031/KJ)；云南省水利重大科技項(xiàng)目(CKSK2015852/KJ)

李云帆(1984-)，男，湖北恩施人，工程師，博士，主要從事機(jī)載、車載激光雷達(dá)點(diǎn)云數(shù)據(jù)處理方向研究，(電話)13429843035(電子信箱)yun_di@sina.com。

10.11988/ckyyb.20160811

2016,33(11):1-4

P237

A

1001-5485(2016)11-0001-04