基于多結(jié)構(gòu)快速生成算法的建筑物平面提取

謝 嬌，吳云東，陳水利

(集美大學(xué)理學(xué)院，福建 廈門 361021)

0 引言

在數(shù)字城市建設(shè)中，空間信息數(shù)據(jù)是其賴以實現(xiàn)的不可或缺的基礎(chǔ)支撐.而快速發(fā)展的三維激光掃描儀系統(tǒng)，也稱LIDAR(Light Detection And Ranging)系統(tǒng)，對于空間信息數(shù)據(jù)的采集具有速度快、精度高、密度高和處理成本低的優(yōu)點，故采用其獲取城市空間信息數(shù)據(jù)是有現(xiàn)實意義的.建筑物作為城市地區(qū)中最重要的組成元素，正確地重建其模型是數(shù)字城市課題中的關(guān)鍵技術(shù)，也是目前亟需解決的問題.然而直接對建筑物數(shù)據(jù)進行重建，不僅增加數(shù)據(jù)處理的復(fù)雜度，而且可能造成系統(tǒng)資源的巨大消耗.為了后續(xù)數(shù)據(jù)處理的方便，所以對點云數(shù)據(jù)進行相應(yīng)的分割處理[1-2].又由于平面是大多數(shù)建筑物表面的主要組成元素，故對建筑物進行平面分割或提取高精度的平面區(qū)域是建筑物重建的基礎(chǔ).

關(guān)于三維點云數(shù)據(jù)的平面提取或平面擬合問題，已有許多學(xué)者對其進行了研究，主要歸納為3種:基于隨機一致采樣 (Random Sample Consensus，RANSAC)[3-8]方法，基于霍夫變換方法[9-12]和基于區(qū)域生長[13-18]或聚類方法.在點云數(shù)據(jù)的平面分割上，基于區(qū)域生長的方法是在每點的法向量特征上實現(xiàn)的，然而每個點法向量的計算對噪聲點敏感，且運算量巨大;基于霍夫變換的方法是利用所有數(shù)據(jù)獲得所有可能的平面模型參數(shù)后再選擇最優(yōu)的參數(shù)，雖然能較準(zhǔn)確分割平面，但效率低.而RANSAC的平面檢測算法能夠很好地解決以上問題，因為它并不需要計算法向量，也不需要選取所有數(shù)據(jù)獲得模型，只是隨機的產(chǎn)生一些平面模型，且每個模型只由原始數(shù)據(jù)中三個點構(gòu)成，最優(yōu)模型就在這些模型中選擇.但是RANSAC算法的魯棒性只在單模型的條件下才能得到保障，也就是在多平面結(jié)構(gòu)的情況下它不能做出正確地檢測.這是因為在隨機采樣模型時每個點的獲得是獨立的，多平面結(jié)構(gòu)的數(shù)據(jù)集則需要采集很多模型才有可能包含正確的那個模型.

由Chin[19]等人提出的多結(jié)構(gòu)快速假設(shè)生成算法，在結(jié)構(gòu)采樣上與RANSAC及其改進的算法比較，具有更高的準(zhǔn)確率和更快的速度，特別在多結(jié)構(gòu)數(shù)據(jù)集中.本文擬利用該算法對點云數(shù)據(jù)進行建筑物的平面檢測.

1 多結(jié)構(gòu)快速假設(shè)生成算法

輸入點云數(shù)據(jù)后，隨機地選擇最小點集構(gòu)成一些模型并計算相應(yīng)的殘差距離.通過對殘差距離進行排序，計算任意兩點的相似度，最后通過相似度驅(qū)動條件內(nèi)點概率指導(dǎo)采樣新模型.其流程為:輸入點云數(shù)據(jù)—殘差排列信息—計算兩點相似度—基于條件內(nèi)點概率采樣—輸出所有模型.

1.1 殘差排序信息

設(shè)點集P={p1，p2，…，pN}作為輸入點集，N為點的個數(shù)，在隨機選擇輸入點集的最小子集n擬合出M個模型之后，就能對每個點計算其相對于M個模型的殘差距離:ri，j=Hj(pi)，i=1，…，N;j=1，…，M，其中Hj表示第j個模型作用在點上的函數(shù).計算每個點在M個模型下構(gòu)成的殘差向量為:Ri= [ri，1，ri，2，…，ri，M]，i=1，…，N，然后對每個點的殘差向量進行升序排序:

其中，fi(1)，fi(2)，…，fi(M)是1，2，…，M 的一個排序.

1.2 計算兩點的相似度

利用殘差排序定義兩點pi，pl的相似度函數(shù):

其中1≤h≤M，并且兩點的相似度函數(shù)值Φ(pi，pl)∈[0，1].

1.3 基于條件內(nèi)點概率的采樣

通過相似度函數(shù)驅(qū)動最小子集的條件采樣，生成有效的新模型，有利于模型的魯棒擬合.假設(shè)已經(jīng)隨機產(chǎn)生了M個模型，且生成一個模型的最小子集為n，通過條件內(nèi)點概率函數(shù)指導(dǎo)采樣下一個模型. 該模型表示為:E={pe1，pe2，…，pen}? P，{e1，e2，…，en}? {1，2，…，N}，其中第一個點 e1是從數(shù)據(jù)中隨機選擇的，即:e1～U(1，N)，然后利用第一個點的信息e1，構(gòu)建第一個條件內(nèi)點概率分布P1(i)指導(dǎo)采樣第二個點e2:

其中α1為歸一化參數(shù).以此類推，利用前k個點的信息采樣第(k+1)個點，對此需要構(gòu)建第k個條件內(nèi)點概率分布Pk(i)，

最后，一個新模型生成后，加入到原始的M個模型中，組成新的模型集.隨之需要改變條件內(nèi)點概率分布，因為每個點殘差向量的改變，也就是在最后一列添加其對于新模型的殘差距離，即:相應(yīng)的參數(shù) h隨之改變，即:hnew=「0．1(M+1).

為了提高算法的效率，提出在生成b個新模型之后再對殘差向量進行一次更新，這是因為單個新模型不會給內(nèi)點概率帶來多少信息.

2 點云數(shù)據(jù)的平面提取

實驗數(shù)據(jù)為只有x，y，z三維信息的點云數(shù)據(jù)，總個數(shù)為N.由于立體空間中不共線的三點構(gòu)成面，故最小子集n設(shè)為3.通過隨機選擇得到M個原始模型之后，利用多結(jié)構(gòu)快速假設(shè)生成算法獲得更多的模型，再從這些模型中選擇含內(nèi)點最多的模型，并將包含在該模型中的點從原始數(shù)據(jù)中提取和刪除，循環(huán)上述操作直到原始數(shù)據(jù)中剩余的點小于0.3N.在判斷點是否屬于平面模型時，本文采用點到模型的殘差距離即點到平面模型的距離.又因為激光掃描儀在掃描點云數(shù)據(jù)時由于精度問題，造成點云不夠絕對準(zhǔn)確，故需要給定閾值T，統(tǒng)一設(shè)定為0.05，具體的步驟為:1)輸入點云數(shù)據(jù)，記入點云的個數(shù)N;2)在T時間內(nèi)利用多結(jié)構(gòu)快速假設(shè)生成算法，生成平面模型集;3)統(tǒng)計模型內(nèi)點個數(shù)，選擇內(nèi)點個數(shù)最多的模型，并從原始數(shù)據(jù)中提取與刪除該模型中的點;4)判斷原始數(shù)據(jù)中剩余的點是否小于0.3N，若否，回到2)，若是，結(jié)束.

3 實驗結(jié)果和分析

為了評估該算法的有效性，本文的測試數(shù)據(jù)采用Trimble公司FX型三維激光掃描儀采集的點云數(shù)據(jù).點云數(shù)據(jù)是方形建筑物的一部分，包含單個平面和多個復(fù)雜平面的數(shù)據(jù).實驗平臺:2.8GHz處理器，內(nèi)存4G的windows 7的操縱系統(tǒng).

為了能看出數(shù)據(jù)的結(jié)構(gòu)，已經(jīng)通過人工標(biāo)定出共面的點，即同平面的點用同種顏色顯示，其中白色的點為未加入考慮的點.圖1主要是由單個平面構(gòu)成的原始數(shù)據(jù)，其中面上的點即紅色點個數(shù)為11559個，白色點個數(shù)為1128個.圖2是由兩個面構(gòu)成的原始數(shù)據(jù)，其中紅色點和黃色點的個數(shù)分別為2675和2461個.圖3是平面結(jié)構(gòu)復(fù)雜的原始數(shù)據(jù)，其中紅紫色、綠色、紅色、黃色、藍色和白色含有點個數(shù)分別為3181、2259、4313、2198、814和1729個，由于藍色點太少，本文將不對它進行提取.

圖1 單個平面的原始數(shù)據(jù)Fig.1 Original data of single plane

圖2 兩個平面的原始數(shù)據(jù)Fig.2 Original data of two planes

圖3 多個平面的原始數(shù)據(jù)Fig.3 Original data of multiple planes

把本文提出的算法與傳統(tǒng)的RANSAC算法[3]作比較，測試數(shù)據(jù)為上述的3個原始數(shù)據(jù).在以后的圖像中，RandomSample代表RANSAC算法測試的結(jié)果，MultigsSample代表本文提出的算法測試的結(jié)果，且黑色為未考慮結(jié)構(gòu)的點，其他顏色代表平面.實驗對比結(jié)果見圖4，量化結(jié)果如表1所示.在提取建筑物平面模型時，存在兩種誤差:第一種稱為α型誤差，指的是將非本平面的點錯誤地檢測為本平面點;第二種稱為β型誤差，指的是本平面的點錯誤地檢測為非本平面點.從圖4中發(fā)現(xiàn)，應(yīng)用本文提出的算法和RANSAC算法都能較好地檢測出平面結(jié)構(gòu)，很難區(qū)分哪個更好.結(jié)合表1和原始數(shù)據(jù)，發(fā)現(xiàn)檢測的平面是存在誤差的，其中每個檢測平面存在的誤差類型只是兩種誤差中的一種.對此，針對多平面數(shù)據(jù)，采用累加不同平面誤差來統(tǒng)計數(shù)據(jù)的整體誤差，結(jié)果見表2.不難發(fā)現(xiàn)，與RANSAC算法相比，本文算法的總誤差更小，故本文算法更有效.

表1 RANSAC和Multigs檢測平面的誤差比較Tab.1 Error comparision of detecting plane by RANSAC and Mutigs

表2 RANSAC和Multigs檢測平面的量化結(jié)果比較Tab.2 Quantitive comparision of detecting plane by RANSAC and Mutigs，cross means having no point

對效率的比較有兩種方法，一是產(chǎn)生同樣的效果時比較它們消耗的時間，另一是在相同時間內(nèi)比較它們產(chǎn)生的效果.本研究選擇后者，測試數(shù)據(jù)為圖1—圖3，測試時間為1 s，實驗結(jié)果見圖5.與原始圖像相比較，圖5a紅點中夾雜著黑點，而圖5b在視覺上看不出區(qū)別;圖5c中含有紅綠黃三色點，與原始圖像中的兩個平面不符，且其綠點中夾雜的黑色點比圖5d中夾雜的點多;圖5e中構(gòu)建的平面結(jié)構(gòu)不準(zhǔn)確;圖5f在視覺上與圖3相比區(qū)別不大，故不難發(fā)現(xiàn)本文的算法比RANSAC算法效率高.

4 結(jié)論

本文提出了一種通過指導(dǎo)采樣，從三維激光點云數(shù)據(jù)中檢測與提取平面的新方法.與RANSAC算法相比，本文的方法不是完全的隨機選擇模型，而是采用條件內(nèi)點概率的信息來指導(dǎo)采樣模型，加快有效模型的生成.實驗表明，本文的方法在點云數(shù)據(jù)的平面檢測上具有有效性，且比RANSAC更具效率，尤其在多結(jié)構(gòu)復(fù)雜模型的數(shù)據(jù)中.

雖然屬于同個平面上的點可以準(zhǔn)確提取，但是建筑物的重建需要通過線條來表示，故未來的研究方向是如何獲取點云的輪廓線.

圖4 RANSAC和Multigs檢測平面的結(jié)果比較Fig.4 Camparision of detecting plane by RANSAC and Multigs

圖5 RANSAC和Multigs在時間為1 s時檢測平面的結(jié)果比較Fig.5 Comparision of detecting plane in one second by RANSAC and Multigs

[1]魏征.車載LiDAR點云中建筑物的自動識別與立面幾何重建[D].武漢:武漢大學(xué)，2012.

[2]趙煦.基于地面激光掃描點云數(shù)據(jù)的三維重建方法研究[D].武漢:武漢大學(xué)，2010.

[3]FISCHLER M A，BOLLES R C.RANSAC:A paradigm for model fitting with applications to image analysis and automated cartography[J].Comm Of the ACM，1981，24(6):381-395.

[4]AMERI B，F(xiàn)RITSCH D.Automatic 3D building reconstruction using plane-roof structures[M].Washington DC:ASPRS，2000.

[5]BRENNER C.Towards fully automatic generation of city models[J].International Archives of Photogrammetry and Remote Sensing，2000，33(B3/1;PART 3):84-92.

[6]周春霖，朱合華，李曉軍.隨機抽樣一致性平面擬合及其應(yīng)用研究[J].計算機工程與應(yīng)用，2011，47(7):177-179.

[7]BAUER J，KARNER K，SCHINDLER K，et al.Segmentation of building models from dense 3D point-clouds[C/OL]//Proc.27th Workshop of the Austrian Association for Pattern Recognition. [2013-12-12]http://scholar.googleusercontent.com/scholar?q=cache:h_7VdvfVjvUJ:scholar.google.com/++Segmentation+of+building+models+from+dense+3D+point-clouds＆hl=zh_CN＆as_sdt=0，5html.

[8]BOULAASSAL H，LANDES T，GRUSSENMEYER P，et al.Automatic segmentation of building facades using terrestrial laser data [J].International Archives of Photogrammetry，Remote Sensing and Spatial Information Systems，2007:65-70.

[9]HOUGH P V C.Method and means for recognizing complex patterns:U.S.Patent 3，069，654 [P].1962-12-18.

[10]戴楠，李傳榮，蘇國中，等.激光點云提取建筑物平面目標(biāo)算法研究[J].微計算機信息，2010(7):205-207.

[11]DéCORET X，DURAND F，SILLION F X，et al.Billboard clouds for extreme model simplification[J].ACM Transactions on Graphics(TOG)，2003，22(3):689-696.

[12]HULIK R，SPANEL M，SMRZ P，et al.Continuous plane detection in point-cloud data based on 3D hough transform[J].Journal of Visual Communication and Image Representation，2014，25(1):86-97.

[13]章毓晉.圖像工程 (中):圖像分析 [M].北京:清華大學(xué)出版社，2005:102-103.

[14]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.

[15]BIOSCA J M，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.

[16]PETERNELL M，STEINER T.Reconstruction of piecewise planar objects from point clouds[J].Computer-Aided Design，2004，36(4):333-342.

[17]VERMA V，KUMAR R，HSU S.3D building detection and modeling from aerial lidar data[C]//IEEE Computer Society，Computer Vision and Pattern Recognition.New York:Andrew Fitzgibbon，2006:2213-2220.

[18]李云帆，馬洪超.從LiDAR數(shù)據(jù)中提取建筑物平面目標(biāo)的新方法[J].計算機工程與應(yīng)用，2011，47(10):5-7.

[19]CHIN T J，YU J，SUTER D.Accelerated hypothesis generation for multistructure data via preference analysis [J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2012，34(4):625-638.