顧及建筑物屋頂結構的改進RANSAC點云分割算法

李云帆， 譚德寶， 劉 瑞, 鄔建偉

(1.長江水利委員會長江科學院，武漢 430010； 2.哈爾濱工業大學深圳研究生院，深圳 518055；3.深圳市房地產評估發展中心，深圳 518040； 4.城市空間信息工程北京市重點實驗室，北京 100830； 5.武漢大學遙感信息工程學院，武漢 430029)

顧及建筑物屋頂結構的改進RANSAC點云分割算法

李云帆1， 譚德寶1， 劉 瑞2,3, 鄔建偉4，5

(1.長江水利委員會長江科學院，武漢 430010； 2.哈爾濱工業大學深圳研究生院，深圳 518055；3.深圳市房地產評估發展中心，深圳 518040； 4.城市空間信息工程北京市重點實驗室，北京 100830； 5.武漢大學遙感信息工程學院，武漢 430029)

針對傳統RANSAC點云分割算法在處理多層次、多面片的復雜建筑物中的困難，提出一種改進算法對建筑物點云進行分割和幾何基元的提取。首先,結合基于坡度和高差的三角形區域生長方法，對復雜建筑物的不同結構層次進行分解，提高了隨機采樣時的有效模型命中率，并降低了錯分現象； 然后，提出一種浮動一致集閾值的RANSAC算法，通過自動調整RANSAC算法中的關鍵參數，使算法能夠適應不同尺度的幾何基元。實驗證明了該算法在復雜建筑物點云數據分割效果和運算效率上的有效性。

LiDAR； 區域生長； RANSAC； 建筑物； 點云分割

0 引言

在機載LiDAR點云處理領域，分割始終是主要的研究方向之一[1-5]，其目的在于將大量數據進行一定層次的組織，以便于從中提取出有用信息，是點云目標識別的重要前提[6]。但是，目前點云分割算法研究還遠未達到滿足現實需求的水平，即使只是針對相對簡單的平面特征，仍需要大量人工處理[6-7]。同時，現代城市的發展建造了大量具有多層次、多面片的復雜結構建筑物，點云分割問題更為復雜，尋找一種魯棒、高效的建筑物點云分割方法是目前的研究熱點。

近年來提出了大量點云分割算法，大致被分為3類： ①基于區域增長的分割算法[8-14]，該算法依據點坐標、法向量和表面粗糙度等屬性制定生長規則，但是仍沒有通用的規則適用于所有場景[10]； ②基于特征聚類的分割算法[2, 10, 15-16]，該算法提供了一種更靈活的一致性模式識別方法，但是從大量的散亂三維點云中進行特征估計和聚類分析非常耗時，同時也具有較大的噪聲敏感性； ③基于模型擬合的分割算法，該算法用不同的幾何形狀基元通過互異的數學模型進行描述，將分割過程轉變為各種數學模型的擬合過程，如三維Hough變換[17]和RANSAC[18]算法。這2種算法均可以用于自動處理點云數據，在建筑物的三維建模領域應用廣泛，文獻[19]對二者在效率和噪聲敏感性等方面進行了詳細的比較分析，指出RANSAC算法較Hough變換更適宜于點云分割。

雖然，RANSAC算法已是一種具有成熟性和優越性的點云分割方法，但是對于結構復雜的多層次、多面片建筑物，仍然存在一些不足。本文將在RANSAC基本原理的基礎上，針對復雜機載LiDAR點云數據分割的難點進行分析，并提出一種改進的RANSAC算法。

1 RANSAC算法分析

1.1 RANSAC算法原理

根據RANSAC算法的基本原理[18]，在一次運算周期中只能提取出一個模型，并需要多次迭代，當一次運算周期結束，將屬于最佳模型的一致集從原始的樣本集中移除，依次迭代，直到從剩余的樣本集中找出其余的模型，并設定一個剩余點數比例閾值作為迭代結束的條件。RANSAC算法包括3個關鍵閾值參數[18]，分別為擬合精度閾值、隨機采樣次數和有效一致集的大小閾值(簡稱為一致集閾值)。其中一致集閾值決定了通過隨機采樣得到的模型是否有效，為了確保得到正確的模型，一般要求一致集足夠大，對于多尺度目標的檢測成功率具有決定性的影響。通常情況下，上述參數均依據經驗值設置，其自適應性問題也是目前的研究方向之一[6]。

通過對RANSAC算法的復雜度進行分析，表明RANSAC算法的效率由以下2個關鍵因素決定[20]： ①定義一個有效模型所需的最小樣本集大小； ②評估每一個隨機采樣得到的幾何基元的有效性所耗費的時間。RANSAC算法運行時，若要提升其效率，則必須降低候選幾何基元的數量s，同時提高能夠成功檢測出最佳形狀候選人的概率P(n)。這正是本文對RANSAC進行改進的依據。

1.2 RANSAC算法缺陷

傳統的RANSAC算法用于復雜建筑物點云分割存在3個缺陷：

1)算法效率。由RANSAC算法原理可知對于數據量較大的復雜建筑物數據，如果籠統地對整體點云數據進行提取，那么具體到某一次搜索過程中，s的大小增加，相應的P(n)降低，算法耗時較長。文獻[20]采用了基于八叉樹的局部采樣策略，在建筑物不同結構層次的邊界處仍然存在八叉樹的一個結點中同時包含了2個幾何基元點云的現象，這同樣會造成算法效率的降低。

2)點云錯分割。針對建筑物中最常見的平面幾何基元，RANSAC算法提取出的只是特征空間中數學意義上的平面參數，并非目標空間中帶有邊界約束的真實面片。為此文獻[6]加入了法向量的約束，但是在多面片的復雜建筑物中仍會出現某2個不同的面片法向量相同，造成錯分現象。

3)點云分割尺度。傳統RANSAC算法中一致集閾值PN_S固定不變，但復雜建筑物往往由大小不一的多面片構成，采用固定不變的點數閾值會導致一個兩難問題： 若采用較大的PN_S，那么小于此尺度的面片腳點則因為達不到有效的一致集閾值條件而無法提取； 若采用較小的PN_S，那么大于此尺度的平面在迭代過程中由于過早滿足了有效一致集閾值條件，會造成較大平面的破碎。

2 RANSAC算法改進

2.1 結合區域增長的分割策略

復雜建筑物屋頂通常可以視為多個典型結構基元(平面、人字形和四坡型等)的組合。在點云數據中，這些結構基元相鄰處存在高差，內部則存在連通性。利用這一特性能夠將這些結構基元進行分解，然后以每個結構基元為約束分別在其內部進行平面提取，則可提高隨機采樣時得到正確平面最小點云集合的概率。同時，由于結構基元之間獨立處理，也能降低錯分效應的影響。

本文采用不規則三角網(triangulated irregular net,TIN)中的三角形作為增長單元。令建筑物點云生成的TIN為Dt，高程突變造成Dt中處于結構基元連接處的三角形斜率較大。三角形斜率可以通過三角形法向量與水平面的夾角進行定義。對Dt中所有三角形進行遍歷，判斷其斜率是否超限，并對其進行相應的標記。這個過程可以表述為

(1)

式中：Trij∈Dt；slope()為計算三角形斜率的函數；Slopemax為斜率閾值。

當結構基元之間的高差較大或飛機航高較低的情況下，結構基元之間也會存在遮擋現象，造成被遮擋區域所生成的三角形坡度較小，還需要增加高差條件對其進行約束。假設某個三角形Tri的3個頂點分別為p1，p2和p3，當滿足式(2)時，可以認為其位于獨立結構基元之間，即

max(zp1,zp2,zp3)-min(zp1,zp2,zp3)>ε,

(2)

式中：ε是事先設定的某個高差閾值；zp1，zp2和zp3分別為3個頂點的高程值。

在對Dt中的所有三角形都進行正確的標記之后，即可以通過文獻[11]中提出的三角形區域生長算法將具有相同標記的三角形進行分組。

2.2 浮動一致集閾值的RANSAC算法

針對1.2節中缺陷3，本文提出一種浮動閾值的改進RANSAC算法，通過自動調整一致集閾值PN_S在某一個區間內由大到小浮動變化，實現多尺度面片的自動提取。假設每一次閾值調整之后，算法都能夠正確提取該尺度下的所有幾何基元，運行K次后達到最小一致集閾值的收斂條件，則有

PNmin=PNmax(Tfactor)K,

(3)

式中：PNmax和PNmin分別為平面包含點數的最大值和最小值，則PN_S∈[PNmin，PNmax]；Tfactor為閾值PN_S的收縮因子，Tfactor∈(0,1)。在迭代開始時PN_S0=PNmax，以較嚴格的一致集閾值準則檢測較大的平面； 經過數次迭代后，算法無法得到有效一致集，說明以PN_S0為一致集條件的平面已檢測完畢，則以PN_S1=PN_S0Tfactor為新的閾值，對剩下的樣本集繼續進行搜索，以檢測較小尺度的平面； 以此類推，在第i次迭代中，PN_Si=PN_Si-1Tfactor； 達到收斂條件時迭代結束。

故可以得到最大迭代次數(MaxIteration)計算方法為

(4)

其中加入一個正整數n，用來保證迭代效果的完整性，實驗證明通常情況下n取1即可。改進后的算法流程如圖1。

圖1 浮動一致集閾值的RANSAC點云分割算法流程Fig.1 Flowchat of point cloud segmentation base on floating consensus threshold RANSAC algorithm

3 實驗與分析

為了驗證本文所提出的改進RANSAC算法的效果，本文采用C++語言分別實現傳統RANSAC算法以及本文所提出的改進算法，并以真實建筑物點云數據作為實驗對象，對二者進行對比。

3.1 復雜多平面建筑物點云分割

選取同一測區內2棟復雜建筑物作為實驗數據。平均點云密度約為2.5個/m2，航向點間距約為0.46 m，旁向點間距約為0.51 m。其中建筑物A包含10 837個激光腳點，建筑物B包含7 128個激光腳點。最小的面片約4.7 m×6.9 m，而最大的面片大小約為27.1 m×39.3 m，結構尺度跨度較大。實驗數據如圖2所示。

(a) 建筑物A點云數據 (b) 建筑物A航空影像

(c) 建筑物B點云數據 (d) 建筑物B航空影像

圖2實驗點云數據及其航空影像

Fig.2Experimentpointclouddatasetsandcorrespondingaerialimages

基于傳統RANSAC分割算法[6]，2個建筑物的分割結果如圖3所示。為了便于比較，分別使用接近最大面片的點云數目和略小于最小面片的點云數目2組不同的一致集閾值(PN_S)。

(a) 建筑物APN_S=550 (b) 建筑物APN_S=81

(c) 建筑物BPN_S=460 (d) 建筑物BPN_S=70

圖3傳統RANSAC算法分割結果Fig.3ResultsofclassicRANSACalgorithm

從圖3中可以看出，由于采用較大的一致集閾值可以完整提取較大平面，如圖3 (a) 1—3、圖3 (c) 1—3，但較小的平面未能有效提取，黑色為未成功提取的腳點，如圖3 (a) 4—7、圖3 (c) 4—6； 采用較小的一致集閾值能夠成功提取較小的平面，如圖3 (b) 1—2、圖3 (d) 1—2，但較大的平面出現了破碎，如圖3 (b) 5—6、圖3 (d) 3—4。實驗表明了傳統RANSAC算法的點云分割錯誤隨分割尺度的變化規律： 閾值變大則欠分割情況增多； 閾值變小則過分割情況增多。另外，圖3 (b)中3，4和7同時說明了對復雜建筑物數據整體進行平面提取會產生較嚴重的共面判斷錯誤。

本文提出的改進RANSAC算法所采用的參數如表1所示。

表1 算法參數Tab.1 Parameters of the proposed algorithm

改進RANSAC算法分割結果見圖4。通過對比圖3與圖4可以看出，本文改進算法得到的分割結果很好地解決了復雜建筑物中多尺度面片提取的問題，保證了平面的完整性，同時大大減少了共面判斷錯誤的發生。

(a) 建筑物A (b) 建筑物B

圖4改進RANSAC算法分割結果

Fig.4SegmentationresultsofimprovedRANSACalgorithm

3.2 改進RANSAC算法效率驗證

為了驗證本文算法在效率上的改善效果，利用多組數據，在采用相同關鍵參數的前提下與傳統RANSAC算法進行比較。由于2種算法均需要計算腳點法向量，實驗中將事先計算的法向量作為輸入數據，其運算時間不計入統計。同時，由于RANSAC算法在采樣上的隨機性，本文將2種算法各運行10次并取其平均值作為最終結果。本文實驗環境為Intel Core2 Duo T9300(2.5 GHz)/2 048 M內存/Windows XP(32 bit)，實驗結果如表2所示。

表2 改進RANSAC算法效率實驗結果Tab.2 Efficiency experimental results of improved RANSAC algorithm

圖5傳統RANSAC算法與本文算法運行效率對比

Fig.5EfficiencycomparationofclassicRANSACalgorithmwiththeproposedalgorithm

實驗中1—5號建筑物均為多層次、多面片的復雜建筑物，6號建筑物在層次結構上相對簡單， 7號建筑物不具有多層次結構。1—5號建筑物的對比實驗證明，改進算法在復雜建筑物上具有明顯的效率改進，其得益于結合區域增長的分割策略，提高了每次隨機采樣時有效模型命中效率。

同時，比較6和7這2組數據，發現建筑物7在運算時間上改進算法長于傳統RANSAC算法，說明改進算法在建筑物7上并無優勢。分析其原因，建筑物7為層次結構單一的建筑物，層次分組操作后只會得到一個結構分組，對后續的分割并無幫助，反而造成冗余計算，會耗費更多的運算時間。

4 結論

針對多層次、多面片的復雜建筑物，提出了一種顧及建筑物屋頂結構的改進RANSAC分割算法。得到如下結論：

1)對復雜建筑物的不同結構層次進行分解，提高了隨機采樣時有效模型命中率，同時能夠大大降低算法的錯分割現象；

2)自動調整RANSAC算法中的關鍵參數一致集閾值，能夠盡可能適應各種大小的面片，從而改進了傳統RANSAC算法的分割尺度問題。實驗證明了改進算法在復雜建筑物點云數據分割正確率和運算效率上的有效性。

本文提出的改進算法同樣也存在不足： ①僅考慮了一致集閾值的向下調整，而且收縮因子依靠經驗值確定，主要原因在于事先缺乏對于建筑物面片大小的尺度分析； ②對于簡單結構的建筑物，改進算法在運算效率上并無改善，需要研究如何對建筑物結構復雜程度進行快速判斷，從而平衡建筑物結構分組與分割之間的計算資源； ③受制于RANSAC算法本身的原理，對于自由曲面建筑物的處理仍然需要進一步研究。

[1] Sapkota P P.Segmentation of Coloured Point Cloud Data[D].Endchede,The Netherlands:International Institute for Geo-Information Science and Earth Observation,2008:67.

[2] Filin S,Pfeifer N.Segmentation of airborne laser scanning data using a slope adaptive neighborhood[J].ISPRS Journal of Photogrammetry and Remote Sensing,2006,60(2):71-80.

[3] 程 亮,龔健雅.LiDAR輔助下利用超高分辨率影像提取建筑物輪廓方法[J].測繪學報,2008,37(3):391-393.

Cheng L,Gong J Y.Building boundary extraction using very high resolution images and LiDAR[J].Acta Geodaetica et Cartographica Sinica,2008,37(3):391-393.

[4] 黃先鋒.利用機載LIDAR數據重建3D建筑物模型的關鍵技術研究[D].武漢:武漢大學,2006.

Huang X F.Research on 3D Building Model Extraction from Airborne LIDAR Data[D].Wuhan:Wuhan University,2006.

[5] 張小紅,耿江輝.用不變矩從機載激光掃描測高點云數據中重建規則房屋[J].武漢大學學報(信息科學版),2006,31(2):168-171.

Zhang X H,Geng J H.Building reconstruction from airborne laser altimetry points cloud data set based on invariant moments[J].Geomatics and Information Science of Wuhan University,2006,31(2):168-171.

[6] Awwad T M,Zhu Q,Du Z Q,et al.An improved segmentation approach for planar surfaces from unstructured 3D point clouds[J].The Photogrammetric Record,2010,25(129):5-23.

[7] Boulaassal H,Landes T,Grussenmeyer P,et al.Automatic segmentation of building facades using terrestrial laser data[C]//ISPRS workshop on laser scanning and silvilaser.Espoo,Finland:ISPRS,2007:65-70.

[8] Besl P J,Jain R C.Segmentation through variable-order surface fitting[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1988,10(2):167-192.

[9] Vosselman G,Gorte B G H,Sithole G,et al.Recognising structure in laser scanner point clouds[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Sciences,2004,46(8):33-38.

[10] Biosca J,Lerma J L.Unsupervised robust planar segmentation of terrestrial laser scanner point clouds based on fuzzy clustering methods[J].ISPRS Journal of Photogrammetry and Remote Sensing,2008,63(1):84-98.

[11] Gorte B.Segmentation of TIN-structured surface models[C]//Proceedings Joint International Symposium on Geospatial Theory Processing and Application.Ottawa,Canada:ISPRS,2002:465-469.

[12] Tóvári D,Pfeifer N.Segmentation based robust interpolation-a new approach to laser data filtering[C]//ISPRS WG III/3,III/4,V/3 Workshop “Laser scanning 2005”.Enschede,the Netherlands:ISPRS,2005:79-84.

[13] Rabbani T,Van den Heuvel F,Vosselman G.Segmentation of point clouds using smoothness constraint[C]//ISPRS Commission V Symposium “Image Engineering and Vision Metrology”.Dresden,German:ISPRS,2006:248-253.

[14] Pu S,Vosselman G.Automatic extraction of building features from terrestrial laser scanning[C]//ISPRS Commission V Symposium “Image Engineering and Vision Metrology”,Dresden,German:ISPRS,2006:25-27.

[15] Filin S.Surface clustering from airborne laser scanning data[C]//ISPRS Commission III Symposium “Photogrammetric Computer Vision”.Graz,Austria:ISPRS,2002:119-124.

[16] Hofmann A D,Maas H G,Streilein A.Derivation of roof types by cluster analysis in parameter spaces of airborne laserscanner point clouds[C]//IAPRS International Archives of Photogrammetry and Remote Sensing and Spatial Information Sciences.Dresden,Germany:IAPRS,2003,34:112-117.

[17] Hough P V C.Method and Means for Recognizing Complex Patterns:U.S.,Patent 3.069.654[P].1962-12-18.

[18] Fischler M A,Bolles R C.Random sample consensus:A paradigm for model fitting with applications to image analysis and automated cartography[J].Communications of the ACM,1981,24(6):381-395.

[19] Tarsha-Kurdi F,Landes T,Grussenmeyer P.Hough-transform and extended ransac algorithms for automatic detection of 3D building roof planes from lidar data[C]//ISPRS Workshop on Laser Scanning and SilviLaser.Espoo,Finland:ISPRS,2007:407-412.

[20] Schnabel R,Wahl R,Klein R.Efficient RANSAC for point-cloud shape detection[J].Computer Graphics Forum,2007,26(2):214-226.

AnimprovedRANSACalgorithmforbuildingpointcloudssegmentationinconsiderationofroofstructure

LI Yunfan1， TAN Debao1， LIU Rui2,3， WU Jianwei4,5

(1.YangtzeRiverScientificResearchInstitute,Wuhan430010,China; 2.ShenzhenGraduateSchool，HarbinInstituteofTechnology，Shenzhen518055,China； 3.CenterforAssessmentandDevelopmentofRealEstate,Shenzhen518040,China; 4.BeijingKeyLaboratoryofUrbanSpatialInformationEngineering,Beijing100830,China; 5.SchoolofRemoteSensingandInformationEngineering,WuhanUniversity,Wuhan430029,China)

An improved RANSAC algorithm was proposed for point cloud segmentation and geometric primitives extraction of buildings with multiple facets and complex roof structures, including two innovations. Firstly, the “split-segment” strategy combined with regional growth concept is proposed to improve the segment result and efficiency of classic RANSAC algorithm; Secondly, an improved RANSAC algorithm with variant consensus set threshold is presented. By automatically adjusting the consensus set threshold value, geometric primitives with scale difference are likely to meet the validity test, thus avoiding the over-segmentation and under- segmentation problems of classic RANSAC algorithm with fixed consensus set threshold.

LiDAR; regional growing; RANSAC; building; point clouds segmentation

10.6046/gtzyyg.2017.04.04

李云帆,譚德寶,劉瑞，等.顧及建筑物屋頂結構的改進RANSAC點云分割算法[J].國土資源遙感,2017,29(4)：20-25.(Li Y F,Tan D B,Liu R,et al.An improved RANSAC algorithm for building point clouds segmentation in consideration of roof structure[J].Remote Sensing for Land and Resources,2017,29(4)：20-25.)

TP 79

A

1001-070X(2017)04-0020-06

2016-05-18；

2016-08-22

中央級公益性科研院所基本科研業務費項目“車載激光雷達點云數據堤防地形三維重建研究”(編號： CKSF2014031/KJ)、城市空間信息工程北京市重點實驗室經費資助項目(編號： 2015201)和國家自然科學基金項目(編號： 41771485)共同資助。

李云帆(1984-),男,博士,主要從事機載、車載激光雷達數據處理方向的研究。Email： liyunfan0828@gmail.com。

(責任編輯：陳理)