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

(1.長江水利委員會(huì)長江科學(xué)院，武漢 430010； 2.哈爾濱工業(yè)大學(xué)深圳研究生院，深圳 518055；3.深圳市房地產(chǎn)評(píng)估發(fā)展中心，深圳 518040； 4.城市空間信息工程北京市重點(diǎn)實(shí)驗(yàn)室，北京 100830； 5.武漢大學(xué)遙感信息工程學(xué)院，武漢 430029)

顧及建筑物屋頂結(jié)構(gòu)的改進(jìn)RANSAC點(diǎn)云分割算法

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

(1.長江水利委員會(huì)長江科學(xué)院，武漢 430010； 2.哈爾濱工業(yè)大學(xué)深圳研究生院，深圳 518055；3.深圳市房地產(chǎn)評(píng)估發(fā)展中心，深圳 518040； 4.城市空間信息工程北京市重點(diǎn)實(shí)驗(yàn)室，北京 100830； 5.武漢大學(xué)遙感信息工程學(xué)院，武漢 430029)

針對(duì)傳統(tǒng)RANSAC點(diǎn)云分割算法在處理多層次、多面片的復(fù)雜建筑物中的困難，提出一種改進(jìn)算法對(duì)建筑物點(diǎn)云進(jìn)行分割和幾何基元的提取。首先,結(jié)合基于坡度和高差的三角形區(qū)域生長方法，對(duì)復(fù)雜建筑物的不同結(jié)構(gòu)層次進(jìn)行分解，提高了隨機(jī)采樣時(shí)的有效模型命中率，并降低了錯(cuò)分現(xiàn)象； 然后，提出一種浮動(dòng)一致集閾值的RANSAC算法，通過自動(dòng)調(diào)整RANSAC算法中的關(guān)鍵參數(shù)，使算法能夠適應(yīng)不同尺度的幾何基元。實(shí)驗(yàn)證明了該算法在復(fù)雜建筑物點(diǎn)云數(shù)據(jù)分割效果和運(yùn)算效率上的有效性。

LiDAR； 區(qū)域生長； RANSAC； 建筑物； 點(diǎn)云分割

0 引言

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

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

雖然，RANSAC算法已是一種具有成熟性和優(yōu)越性的點(diǎn)云分割方法，但是對(duì)于結(jié)構(gòu)復(fù)雜的多層次、多面片建筑物，仍然存在一些不足。本文將在RANSAC基本原理的基礎(chǔ)上，針對(duì)復(fù)雜機(jī)載LiDAR點(diǎn)云數(shù)據(jù)分割的難點(diǎn)進(jìn)行分析，并提出一種改進(jìn)的RANSAC算法。

1 RANSAC算法分析

1.1 RANSAC算法原理

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

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

1.2 RANSAC算法缺陷

傳統(tǒng)的RANSAC算法用于復(fù)雜建筑物點(diǎn)云分割存在3個(gè)缺陷：

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

2)點(diǎn)云錯(cuò)分割。針對(duì)建筑物中最常見的平面幾何基元，RANSAC算法提取出的只是特征空間中數(shù)學(xué)意義上的平面參數(shù)，并非目標(biāo)空間中帶有邊界約束的真實(shí)面片。為此文獻(xiàn)[6]加入了法向量的約束，但是在多面片的復(fù)雜建筑物中仍會(huì)出現(xiàn)某2個(gè)不同的面片法向量相同，造成錯(cuò)分現(xiàn)象。

3)點(diǎn)云分割尺度。傳統(tǒng)RANSAC算法中一致集閾值PN_S固定不變，但復(fù)雜建筑物往往由大小不一的多面片構(gòu)成，采用固定不變的點(diǎn)數(shù)閾值會(huì)導(dǎo)致一個(gè)兩難問題： 若采用較大的PN_S，那么小于此尺度的面片腳點(diǎn)則因?yàn)檫_(dá)不到有效的一致集閾值條件而無法提?。?若采用較小的PN_S，那么大于此尺度的平面在迭代過程中由于過早滿足了有效一致集閾值條件，會(huì)造成較大平面的破碎。

2 RANSAC算法改進(jìn)

2.1 結(jié)合區(qū)域增長的分割策略

復(fù)雜建筑物屋頂通?？梢砸暈槎鄠€(gè)典型結(jié)構(gòu)基元(平面、人字形和四坡型等)的組合。在點(diǎn)云數(shù)據(jù)中，這些結(jié)構(gòu)基元相鄰處存在高差，內(nèi)部則存在連通性。利用這一特性能夠?qū)⑦@些結(jié)構(gòu)基元進(jìn)行分解，然后以每個(gè)結(jié)構(gòu)基元為約束分別在其內(nèi)部進(jìn)行平面提取，則可提高隨機(jī)采樣時(shí)得到正確平面最小點(diǎn)云集合的概率。同時(shí)，由于結(jié)構(gòu)基元之間獨(dú)立處理，也能降低錯(cuò)分效應(yīng)的影響。

本文采用不規(guī)則三角網(wǎng)(triangulated irregular net,TIN)中的三角形作為增長單元。令建筑物點(diǎn)云生成的TIN為Dt，高程突變?cè)斐蒁t中處于結(jié)構(gòu)基元連接處的三角形斜率較大。三角形斜率可以通過三角形法向量與水平面的夾角進(jìn)行定義。對(duì)Dt中所有三角形進(jìn)行遍歷，判斷其斜率是否超限，并對(duì)其進(jìn)行相應(yīng)的標(biāo)記。這個(gè)過程可以表述為

(1)

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

當(dāng)結(jié)構(gòu)基元之間的高差較大或飛機(jī)航高較低的情況下，結(jié)構(gòu)基元之間也會(huì)存在遮擋現(xiàn)象，造成被遮擋區(qū)域所生成的三角形坡度較小，還需要增加高差條件對(duì)其進(jìn)行約束。假設(shè)某個(gè)三角形Tri的3個(gè)頂點(diǎn)分別為p1，p2和p3，當(dāng)滿足式(2)時(shí)，可以認(rèn)為其位于獨(dú)立結(jié)構(gòu)基元之間，即

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

(2)

式中：ε是事先設(shè)定的某個(gè)高差閾值；zp1，zp2和zp3分別為3個(gè)頂點(diǎn)的高程值。

在對(duì)Dt中的所有三角形都進(jìn)行正確的標(biāo)記之后，即可以通過文獻(xiàn)[11]中提出的三角形區(qū)域生長算法將具有相同標(biāo)記的三角形進(jìn)行分組。

2.2 浮動(dòng)一致集閾值的RANSAC算法

針對(duì)1.2節(jié)中缺陷3，本文提出一種浮動(dòng)閾值的改進(jìn)RANSAC算法，通過自動(dòng)調(diào)整一致集閾值PN_S在某一個(gè)區(qū)間內(nèi)由大到小浮動(dòng)變化，實(shí)現(xiàn)多尺度面片的自動(dòng)提取。假設(shè)每一次閾值調(diào)整之后，算法都能夠正確提取該尺度下的所有幾何基元，運(yùn)行K次后達(dá)到最小一致集閾值的收斂條件，則有

PNmin=PNmax(Tfactor)K,

(3)

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

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

(4)

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

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

3 實(shí)驗(yàn)與分析

為了驗(yàn)證本文所提出的改進(jìn)RANSAC算法的效果，本文采用C++語言分別實(shí)現(xiàn)傳統(tǒng)RANSAC算法以及本文所提出的改進(jìn)算法，并以真實(shí)建筑物點(diǎn)云數(shù)據(jù)作為實(shí)驗(yàn)對(duì)象，對(duì)二者進(jìn)行對(duì)比。

3.1 復(fù)雜多平面建筑物點(diǎn)云分割

選取同一測(cè)區(qū)內(nèi)2棟復(fù)雜建筑物作為實(shí)驗(yàn)數(shù)據(jù)。平均點(diǎn)云密度約為2.5個(gè)/m2，航向點(diǎn)間距約為0.46 m，旁向點(diǎn)間距約為0.51 m。其中建筑物A包含10 837個(gè)激光腳點(diǎn)，建筑物B包含7 128個(gè)激光腳點(diǎn)。最小的面片約4.7 m×6.9 m，而最大的面片大小約為27.1 m×39.3 m，結(jié)構(gòu)尺度跨度較大。實(shí)驗(yàn)數(shù)據(jù)如圖2所示。

(a) 建筑物A點(diǎn)云數(shù)據(jù) (b) 建筑物A航空影像

(c) 建筑物B點(diǎn)云數(shù)據(jù) (d) 建筑物B航空影像

圖2實(shí)驗(yàn)點(diǎn)云數(shù)據(jù)及其航空影像

Fig.2Experimentpointclouddatasetsandcorrespondingaerialimages

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

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

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

圖3傳統(tǒng)RANSAC算法分割結(jié)果Fig.3ResultsofclassicRANSACalgorithm

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

本文提出的改進(jìn)RANSAC算法所采用的參數(shù)如表1所示。

表1 算法參數(shù)Tab.1 Parameters of the proposed algorithm

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

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

圖4改進(jìn)RANSAC算法分割結(jié)果

Fig.4SegmentationresultsofimprovedRANSACalgorithm

3.2 改進(jìn)RANSAC算法效率驗(yàn)證

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

表2 改進(jìn)RANSAC算法效率實(shí)驗(yàn)結(jié)果Tab.2 Efficiency experimental results of improved RANSAC algorithm

圖5傳統(tǒng)RANSAC算法與本文算法運(yùn)行效率對(duì)比

Fig.5EfficiencycomparationofclassicRANSACalgorithmwiththeproposedalgorithm

實(shí)驗(yàn)中1—5號(hào)建筑物均為多層次、多面片的復(fù)雜建筑物，6號(hào)建筑物在層次結(jié)構(gòu)上相對(duì)簡單， 7號(hào)建筑物不具有多層次結(jié)構(gòu)。1—5號(hào)建筑物的對(duì)比實(shí)驗(yàn)證明，改進(jìn)算法在復(fù)雜建筑物上具有明顯的效率改進(jìn)，其得益于結(jié)合區(qū)域增長的分割策略，提高了每次隨機(jī)采樣時(shí)有效模型命中效率。

同時(shí)，比較6和7這2組數(shù)據(jù)，發(fā)現(xiàn)建筑物7在運(yùn)算時(shí)間上改進(jìn)算法長于傳統(tǒng)RANSAC算法，說明改進(jìn)算法在建筑物7上并無優(yōu)勢(shì)。分析其原因，建筑物7為層次結(jié)構(gòu)單一的建筑物，層次分組操作后只會(huì)得到一個(gè)結(jié)構(gòu)分組，對(duì)后續(xù)的分割并無幫助，反而造成冗余計(jì)算，會(huì)耗費(fèi)更多的運(yùn)算時(shí)間。

4 結(jié)論

針對(duì)多層次、多面片的復(fù)雜建筑物，提出了一種顧及建筑物屋頂結(jié)構(gòu)的改進(jìn)RANSAC分割算法。得到如下結(jié)論：

1)對(duì)復(fù)雜建筑物的不同結(jié)構(gòu)層次進(jìn)行分解，提高了隨機(jī)采樣時(shí)有效模型命中率，同時(shí)能夠大大降低算法的錯(cuò)分割現(xiàn)象；

2)自動(dòng)調(diào)整RANSAC算法中的關(guān)鍵參數(shù)一致集閾值，能夠盡可能適應(yīng)各種大小的面片，從而改進(jìn)了傳統(tǒng)RANSAC算法的分割尺度問題。實(shí)驗(yàn)證明了改進(jìn)算法在復(fù)雜建筑物點(diǎn)云數(shù)據(jù)分割正確率和運(yùn)算效率上的有效性。

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

[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].測(cè)繪學(xué)報(bào),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] 黃先鋒.利用機(jī)載LIDAR數(shù)據(jù)重建3D建筑物模型的關(guān)鍵技術(shù)研究[D].武漢:武漢大學(xué),2006.

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

[5] 張小紅,耿江輝.用不變矩從機(jī)載激光掃描測(cè)高點(diǎn)云數(shù)據(jù)中重建規(guī)則房屋[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),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

李云帆,譚德寶,劉瑞，等.顧及建筑物屋頂結(jié)構(gòu)的改進(jìn)RANSAC點(diǎn)云分割算法[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

中央級(jí)公益性科研院所基本科研業(yè)務(wù)費(fèi)項(xiàng)目“車載激光雷達(dá)點(diǎn)云數(shù)據(jù)堤防地形三維重建研究”(編號(hào)： CKSF2014031/KJ)、城市空間信息工程北京市重點(diǎn)實(shí)驗(yàn)室經(jīng)費(fèi)資助項(xiàng)目(編號(hào)： 2015201)和國家自然科學(xué)基金項(xiàng)目(編號(hào)： 41771485)共同資助。

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

(責(zé)任編輯：陳理)