利用LMedS算法提取規(guī)則建筑物頂部面片

陳向陽，向云飛

(1. 南通職業(yè)大學(xué)建筑工程學(xué)院，江蘇 南通 226007； 2. 河海大學(xué)， 江蘇 南京 211100)

對(duì)城市進(jìn)行實(shí)景三維建模是數(shù)字城市構(gòu)建中一項(xiàng)重要的內(nèi)容，這引起了人們足夠的關(guān)注，城市的實(shí)景三維模型能夠方便城市的規(guī)劃、空間分析、信息查詢及統(tǒng)計(jì)等[1]。近些年迅速發(fā)展的機(jī)載LiDAR技術(shù)，融合各種高新技術(shù)于一體，能快速、大面積地獲取城市地物高精度的三維點(diǎn)云。機(jī)載LiDAR測(cè)量技術(shù)的迅速發(fā)展，可以很好地助力城市實(shí)景三維模型的高效構(gòu)建[2-3]。對(duì)于每個(gè)城市來說，城市建筑物是最為突出的實(shí)體。因此，對(duì)城市建筑實(shí)景三維模型的構(gòu)建顯得十分重要。對(duì)于城市建筑物來說，頂部面片的激光腳點(diǎn)包含了建筑物很多信息，同時(shí)，可以通過頂部面片提取建筑物輪廓線進(jìn)行建筑物三維建模[4]。大部分城市建筑物頂部以平面為主，RANSAC算法作為一種穩(wěn)健性非常好的模型參數(shù)估計(jì)方法，可以利用RANSAC平面模型從離散點(diǎn)云中提取建筑物頂部面片[5]。在RANSAC算法估計(jì)模型參數(shù)時(shí)，多次迭代計(jì)算，將Med偏差最小所對(duì)應(yīng)的模型的估計(jì)參數(shù)作為最終估計(jì)參數(shù)，即LMedS算法。LMedS算法相對(duì)于RANSAC算法，克服了RANSAC算法每次迭代閾值較難設(shè)定和迭代次數(shù)不確定等問題，且提取建筑物頂部面片的效果較好。

1 RANSAC算法與LMedS算法

1.1 RANSAC算法

RANSAC(random sample consensus)，是一種穩(wěn)健性非常好的模型參數(shù)估計(jì)方法。RANSAC首先從點(diǎn)云數(shù)據(jù)中選取一定數(shù)量的樣本點(diǎn)，并利用所選取的點(diǎn)進(jìn)行模型參數(shù)的初步估計(jì)。之后，迭代計(jì)算點(diǎn)云數(shù)據(jù)中其他點(diǎn)與該模型的偏差，設(shè)置一定的閾值，從而來判定該點(diǎn)是否屬于模型內(nèi)的點(diǎn)。重復(fù)以上過程，直至模型內(nèi)包含點(diǎn)的數(shù)目最多，則此模型的估計(jì)參數(shù)作為最終的模型估計(jì)參數(shù)[6-7]。圖1為RANSAC算法從二維數(shù)據(jù)集中估計(jì)直線模型，其中，(a)表示包含局內(nèi)點(diǎn)和局外點(diǎn)的數(shù)據(jù)集，(b)中淺灰色點(diǎn)為局外點(diǎn)，深灰色點(diǎn)為局內(nèi)點(diǎn)，灰色線為估計(jì)的直線模型。

圖1 RANSAC算法估計(jì)直線模型

從理論上來說，RANSAC算法能夠剔除局外點(diǎn)的影響，進(jìn)而得到最優(yōu)的模型估計(jì)參數(shù)。然而，RANSAC算法有兩個(gè)缺陷：一是每次的計(jì)算要先設(shè)置一定的閾值來區(qū)分局內(nèi)點(diǎn)與局外點(diǎn)；二是該算法的迭代計(jì)算的次數(shù)并不能事先知曉，由程序運(yùn)行的實(shí)際情況來決定。因此，并不適用于抽象模型的參數(shù)估計(jì)。與此同時(shí)，當(dāng)點(diǎn)云數(shù)據(jù)中包含多個(gè)模型時(shí)，RANSAC算法則不能精確地對(duì)模型進(jìn)行擬合。

1.2 LMedS算法

LMedS算法同樣也是一種穩(wěn)健性比較好的模型參數(shù)估計(jì)方法。LMedS算法與RANSAC算法模型估計(jì)的原理類似。然而，不同于 RANSAC算法的是，在每次迭代計(jì)算的過程中，LMedS算法僅僅記錄偏差值相對(duì)居中的Med偏差，并以此作為計(jì)算的模型估計(jì)參數(shù)[8]。因此，每次計(jì)算LMedS算法并不需要事先設(shè)置一定的閾值，從而很好地克服了RANSAC算法的第一個(gè)缺陷。之后，重復(fù)之前的計(jì)算，從中選取Med偏差最小作為最終的模型估計(jì)參數(shù)。迭代計(jì)算的次數(shù)可由選取樣本點(diǎn)的個(gè)數(shù)、預(yù)期的模型估計(jì)誤差等所來決定，從而克服了RANSAC算法的第二個(gè)缺陷。

綜上所述，可以利用LMedS算法來代替RANSAC算法來進(jìn)行模型的參數(shù)估計(jì)，進(jìn)而用來提取建筑物頂部面片。值得一提的是，LMedS算法并不適用于大于樣本點(diǎn)中outliers所占的比例達(dá)到或超過50%。

1.3 兩種算法平面模型提取效果對(duì)比

測(cè)試數(shù)據(jù)來自三維掃描儀對(duì)一些實(shí)物進(jìn)行掃描所獲取的點(diǎn)云數(shù)據(jù)，點(diǎn)云數(shù)據(jù)中平面模型的點(diǎn)云占較大的一部分，適合進(jìn)行兩種算法提取平面模型對(duì)比試驗(yàn)。該點(diǎn)云數(shù)據(jù)是利用三維掃描儀對(duì)實(shí)物茶杯進(jìn)行掃描，其中的平面模型有桌面和墻面，點(diǎn)云數(shù)據(jù)中有307 200個(gè)點(diǎn)，如圖2所示。

圖2 測(cè)試數(shù)據(jù)

經(jīng)過下采樣后，點(diǎn)云數(shù)據(jù)中點(diǎn)的個(gè)數(shù)為32 921個(gè)，在VS平臺(tái)中用C++語言對(duì)兩種算法進(jìn)行實(shí)現(xiàn)，并利用RANSAC算法和LMedS算法分別對(duì)樣本數(shù)據(jù)進(jìn)行平面模型的提取，提取的平面模型有桌面、墻面。統(tǒng)計(jì)兩種算法提取的平面模型中包含的點(diǎn)的數(shù)目，作為提取平面模型優(yōu)劣程度的量化指標(biāo)。Plan1和Plan2為從樣本數(shù)據(jù)中提取出的兩個(gè)平面模型，Plan1為桌面的平面模型，Plan2為墻面的平面模型。利用RANSAC算法提取的Plan1和Plan2包含的點(diǎn)個(gè)數(shù)分別為14 908和13 394個(gè)，而LMedS算法提取兩個(gè)平面包含的點(diǎn)的個(gè)數(shù)分別為14 978 和13 411個(gè)。

由上可知，相對(duì)于RANSAC算法，利用LMedS算法對(duì)兩個(gè)樣本數(shù)據(jù)提取的平面模型包含局內(nèi)點(diǎn)的個(gè)數(shù)較多，提取的平面模型的效果相對(duì)較好。從程序運(yùn)行的時(shí)間來看，LMedS算法程序運(yùn)行的時(shí)間比RANSAC算法程序運(yùn)行的時(shí)間短。綜上，LMedS算法對(duì)平面模型的提取效果較好，同時(shí)克服了RANSAC算法的缺點(diǎn)，可以利用LMedS算法對(duì)城市建筑物頂部面片進(jìn)行提取。

2 LMedS算法提取建筑物頂部面片流程

城市中的大部分建筑物頂部理論上是平面，但是由于一些附屬物及周圍樹木的存在，在利用機(jī)載LiDAR獲取城市點(diǎn)云數(shù)據(jù)時(shí)，相對(duì)于房屋頂部平面來說，就會(huì)產(chǎn)生許多“噪聲點(diǎn)”[9]。針對(duì)常用擬合方法在點(diǎn)云數(shù)據(jù)存在噪聲點(diǎn)時(shí)出現(xiàn)的擬合不穩(wěn)定的情況，可以用RANSAC算法從包含“噪聲點(diǎn)”的點(diǎn)云數(shù)據(jù)中估計(jì)出建筑物頂部平面模型，進(jìn)而提取出建筑物頂部面片[10]。在提取過程中，考慮從迭代的N次中選取Med偏差最小的模型參數(shù)為模型參數(shù)估計(jì)值(即LMedS算法)，克服了RANSAC算法每次迭代閾值較難設(shè)定和迭代次數(shù)不確定的問題。具體提取步驟如下：

(1) 利用直通濾波器對(duì)點(diǎn)云數(shù)據(jù)的Z軸維度實(shí)行一個(gè)簡(jiǎn)單的濾波，去掉在Z軸指定范圍內(nèi)的點(diǎn)。通過直通濾波器的過濾，可以初步將點(diǎn)云數(shù)據(jù)中的地面點(diǎn)和近地面點(diǎn)去除。

(2) 為了提高工作效率，利用VoxelGrid濾波器對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行重采樣。VoxelGrid濾波器的工作原理是：對(duì)點(diǎn)云數(shù)據(jù)建立一定的三維柵格，在每個(gè)柵格中，用所有點(diǎn)的重心點(diǎn)替代所有的點(diǎn)，完成三維點(diǎn)云數(shù)據(jù)的重采樣。經(jīng)過VoxelGrid濾波器重采樣的點(diǎn)云數(shù)據(jù)，保持點(diǎn)云的形狀特征，并減少點(diǎn)的數(shù)量，大大提高了建筑物頂部面片的效率。

(3) 將經(jīng)過重采樣的點(diǎn)云數(shù)據(jù)設(shè)為集合P，將P作為程序輸入數(shù)據(jù)，對(duì)P中的點(diǎn)執(zhí)行以下操作：

a. 從P中選取樣本子集，利用最小方差估計(jì)平面模型參數(shù)，計(jì)算其對(duì)應(yīng)的平面ax+by+cz=d。

b. 將P中去除樣本子集的所有點(diǎn)Pi，計(jì)算Pi與平面模型ax+by+cz=d的距離di

c. 計(jì)算距離的標(biāo)準(zhǔn)偏差σ

d. 迭代N次，選取Med值最小平面模型參數(shù)作為最終的平面模型參數(shù)。

(4) 由于城市建筑物頂部位于不同的高度，通過步驟(3)可以擬合出包含建筑物頂部面片的多個(gè)平面模型。在每個(gè)估計(jì)的平面模型中，不僅包含建筑物頂部的激光腳點(diǎn)，也會(huì)存在少量離散的激光腳點(diǎn)，這些激光腳點(diǎn)多為與建筑物頂面高度相近的較高植被點(diǎn)和其他建筑物側(cè)面上的激光腳點(diǎn)。對(duì)每個(gè)平面模型，可以利用歐氏聚類算法，設(shè)定包含點(diǎn)個(gè)數(shù)的閾值，多次重復(fù)計(jì)算，去除平面模型外少量的離散點(diǎn)，對(duì)建筑物頂部面片的提取結(jié)果進(jìn)行優(yōu)化。最終，將所有的平面模型進(jìn)行疊加，即可得到城市大部分建筑頂部面片。

3 試驗(yàn)與結(jié)果分析

3.1 試驗(yàn)數(shù)據(jù)介紹

以城區(qū)某塊建筑物較多區(qū)域的點(diǎn)云數(shù)據(jù)，作為本次試驗(yàn)數(shù)據(jù)。該點(diǎn)云數(shù)據(jù)總共包含點(diǎn)的個(gè)數(shù)為263 375個(gè)，平均點(diǎn)云密度為10個(gè)/m2。該區(qū)域點(diǎn)云的最大高程為977.5 m,最小高程為876.4 m。建筑物頂部大部分為平面，可以利用本文算法對(duì)該區(qū)域的建筑物進(jìn)行頂部面片的提取。圖3所示為該塊點(diǎn)云數(shù)據(jù)經(jīng)分類后的建筑物點(diǎn)云。

圖3 試驗(yàn)區(qū)的點(diǎn)云數(shù)據(jù)

3.2 面片提取試驗(yàn)

將本次試驗(yàn)的數(shù)據(jù)點(diǎn)云導(dǎo)入CloudCompare軟件中，根據(jù)軟件色標(biāo)可知地面點(diǎn)和近地面點(diǎn)的高程集中在876～889 m。因此，可以用直通濾波器將點(diǎn)云數(shù)據(jù)在Z軸維度進(jìn)行簡(jiǎn)單的濾波，設(shè)置濾波的范圍設(shè)定為876～889 m，即可將大部分地面點(diǎn)和近地面點(diǎn)剔除。通過直通濾波器可以快速高效地濾除地面點(diǎn)和近地面點(diǎn)，為之后頂部面片提取提供便利。經(jīng)過簡(jiǎn)單的濾波處理后，點(diǎn)云數(shù)據(jù)點(diǎn)的數(shù)目降為100 384個(gè)，濾波后的點(diǎn)云數(shù)據(jù)如圖4所示。

圖4 簡(jiǎn)單濾波后的試驗(yàn)區(qū)點(diǎn)云數(shù)據(jù)

利用C++語言對(duì)LMedS算法進(jìn)行了實(shí)現(xiàn)，將經(jīng)上述步驟處理過后的數(shù)據(jù)導(dǎo)入程序，檢測(cè)包含屋頂平面的平面模型。在每個(gè)估計(jì)的平面模型中，不僅包含不同高度的建筑物頂面的激光腳點(diǎn)，也會(huì)存在少量離散的激光腳點(diǎn)，這些激光腳點(diǎn)多為與建筑物頂面高度相近的較高植被點(diǎn)和其他建筑物側(cè)面上的激光腳點(diǎn)。同樣利用歐氏聚類算法，設(shè)定聚類的點(diǎn)距離閾值為0.7 m、每個(gè)類別包含點(diǎn)的最小數(shù)目為400個(gè)，重復(fù)計(jì)算，去除少量離群點(diǎn)，對(duì)建筑物頂部面片提取結(jié)果進(jìn)行優(yōu)化。圖5為試驗(yàn)區(qū)域提取的建筑物頂部面片。

圖5 試驗(yàn)區(qū)建筑物頂部面片

3.3 試驗(yàn)分析

對(duì)比試驗(yàn)區(qū)的影像圖可知，利用LMedS算法能夠成功地提取出試驗(yàn)區(qū)域的建筑物頂部的面片，并剔除其他物體的點(diǎn)云，克服了在有 “噪聲點(diǎn)”存在的情況下，出現(xiàn)擬合不穩(wěn)定的問題。利用LMedS算法進(jìn)行建筑物頂部面片的提取，相對(duì)于RANSAC算法來說，其克服了閾值難設(shè)定和迭代次數(shù)不確定的問題。用該方法進(jìn)行建筑物頂部面片的提取，自動(dòng)化程度較高。

同時(shí)，LMedS算法是依靠建筑物頂部的點(diǎn)云數(shù)據(jù)來提取建筑物頂部的面片，提取的結(jié)果會(huì)受該區(qū)域點(diǎn)云數(shù)據(jù)質(zhì)量的影響。當(dāng)建筑物頂部數(shù)據(jù)有部分缺失時(shí)，提取的建筑物頂部面片會(huì)出現(xiàn)空洞的情況。利用LMedS算法提取建筑物頂部面片，只適合于規(guī)則的頂部為平面的建筑物，并不適用于復(fù)雜的建筑物，具有一定的局限性，建筑物頂部的細(xì)節(jié)部分還需進(jìn)一步處理。

4 結(jié) 語

利用機(jī)載LiDAR技術(shù)來獲取城市區(qū)域地物的三維點(diǎn)位坐標(biāo)時(shí)，建筑物頂部相對(duì)于其他部分會(huì)有比較多的激光腳點(diǎn)，對(duì)建筑物描述更為詳盡。大部分城市以規(guī)則建筑物為主，建筑物頂部多以平面為主，可以利用本文方法將建筑物頂部面片提取出來[11]。在城市建筑物動(dòng)態(tài)監(jiān)測(cè)方面，可以比較不同時(shí)期建筑物頂部信息，來監(jiān)測(cè)城市房屋的動(dòng)態(tài)變化[12]。因此，有必要對(duì)規(guī)則建筑物頂部的面片的提取方法進(jìn)行研究。

RANSAC算法作為一種穩(wěn)健性非常好的參數(shù)估計(jì)方法，可以從包含“噪聲點(diǎn)”的點(diǎn)中提取出擬合模型內(nèi)的點(diǎn)，可以利用其平面擬合模型來提取建筑物頂部面片。在利用該算法進(jìn)行提取時(shí)，將最小中值作為考量因素(即LMedS算法)，克服了RANSAC算法閾值設(shè)定難和迭代次數(shù)不確定的問題。通過試驗(yàn)證明，利用LMedS算法能夠成功地提取出建筑物頂部面片，具有良好的效果。

參考文獻(xiàn)：

[1] 高山,陳思.城市三維建模技術(shù)與標(biāo)準(zhǔn)研究[J].測(cè)繪通報(bào),2013(3):95-97.

[2] 鄧非,徐國(guó)杰.LiDAR數(shù)據(jù)與航空影像結(jié)合的建筑物重建[J].測(cè)繪地理信息,2010,35(1):35-37.

[3] 劉經(jīng)南,張小紅.利用激光強(qiáng)度信息分類激光掃描測(cè)高數(shù)據(jù)[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2005,30(3):189-192.

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

[5] 魏英姿,劉曉莉.基于隨機(jī)抽取一致性的穩(wěn)健點(diǎn)云平面擬合[J].北京工業(yè)大學(xué)學(xué)報(bào),2014,40(3):400-403.

[6] 胡偉，盧小平，李珵，等.基于改進(jìn)RANSAC算法的屋頂激光點(diǎn)云面片分割方法[J].測(cè)繪通報(bào)，2012(11)：31-34.

[7] HIDALGO-PANIAGUA A，VEGA-RODRIGUEZ M A,PAVN N,et al.A Comparative Study of Parallel RANSAC Implementations in 3D Space[J].Intemational Journal of Parallel Programming，2015，43(5):703-720.

[8] TORR P H S，ZISSERMAN A.MLESAC:A New Robust Estimator with Application to Estimating Image Geometry[J].Computer Vision and Understanding，2000,78(1):138-156.

[9] 姜如波.基于三維激光掃描技術(shù)的建筑物模型重建[J].測(cè)繪通報(bào),2013(S1):80-83.

[10] 王植,李慧盈,吳立新，等.基于RANSAC模型的機(jī)載LiDAR數(shù)據(jù)中建筑輪廓提取算法[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,33(2):271-275.

[11] 李澤剛.基于機(jī)載LiDAR數(shù)據(jù)與影像處理技術(shù)的建筑物提取研究[D].南昌：東華理工大學(xué),2015.

[12] 趙家樂.基于LiDAR與航空影像的建筑物提取及三維重建研究[D].青島：山東科技大學(xué),2015.