謝 嬌，吳云東，陳水利

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

0 引言

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

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

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

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

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

1.1 殘差排序信息

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

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

1.2 計(jì)算兩點(diǎn)的相似度

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

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

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

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

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

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

為了提高算法的效率，提出在生成b個(gè)新模型之后再對(duì)殘差向量進(jìn)行一次更新，這是因?yàn)閱蝹€(gè)新模型不會(huì)給內(nèi)點(diǎn)概率帶來多少信息.

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

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

3 實(shí)驗(yàn)結(jié)果和分析

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

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

[2]趙煦.基于地面激光掃描點(diǎn)云數(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]周春霖，朱合華，李曉軍.隨機(jī)抽樣一致性平面擬合及其應(yīng)用研究[J].計(jì)算機(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]戴楠，李傳榮，蘇國中，等.激光點(diǎn)云提取建筑物平面目標(biāo)算法研究[J].微計(jì)算機(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].計(jì)算機(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.