基于LiDAR點(diǎn)云法向量穩(wěn)健估計(jì)的室內(nèi)平面圖自動生成方法

湛逸飛，楊必勝

(武漢大學(xué) 測繪遙感信息工程國家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430079)

0 引 言

“室內(nèi)地圖”是根據(jù)位置服務(wù)的需求，遵循特定的數(shù)學(xué)法則，通過圖形符號、三維模型、全景圖像、數(shù)據(jù)圖表等形式，抽象概括表達(dá)室內(nèi)空間和對象的分布狀況及其屬性特征的信息載體與工具[1]。近年來，隨著數(shù)字地圖技術(shù)和移動互聯(lián)網(wǎng)技術(shù)的發(fā)展，室內(nèi)地圖已成為定位、導(dǎo)航不可或缺的基礎(chǔ)支撐圖[2]。移動互聯(lián)網(wǎng)時(shí)代給室內(nèi)地圖帶來更大的應(yīng)用空間及可想象空間，消費(fèi)經(jīng)濟(jì)的極大繁榮、電子商務(wù)的快速發(fā)展、社交工具基于位置的功能進(jìn)化等給予室內(nèi)地圖越來越多的商業(yè)價(jià)值[3]，被視為室外地圖的“最后一公里”。被廣泛應(yīng)用于室內(nèi)定位、室內(nèi)導(dǎo)航級室內(nèi)外一體化導(dǎo)航、o2o電子商務(wù)等方面[4]。基于平面圖數(shù)字化的室內(nèi)地圖制作已遠(yuǎn)遠(yuǎn)不能滿足現(xiàn)有需求[5]。近年來，隨著便攜式LiDAR技術(shù)的興起，基于LiDAR技術(shù)，如背包式、手推車[6-8]等數(shù)據(jù)采集為室內(nèi)地圖的制作帶來了新的數(shù)據(jù)來源，同時(shí)也帶來了新的挑戰(zhàn)。由于室內(nèi)點(diǎn)云具有噪聲大，場景復(fù)雜等特點(diǎn)，如何準(zhǔn)確估算點(diǎn)云的法向量實(shí)現(xiàn)點(diǎn)云的高質(zhì)量分割成為研究的熱點(diǎn)和難點(diǎn)。Jean-Francois Lalonde,2005；Unnikrishnan R,2010提出了球形自適應(yīng)鄰域方法[9]，實(shí)現(xiàn)了在局部鄰域內(nèi)保證擬合平面的法向量誤差最小。楊必勝等人提出了另一種自適應(yīng)鄰域方法[10-13]。它既參照了“維數(shù)特征”方法也融入了局部強(qiáng)度信息，兼顧了幾何特征和強(qiáng)度信息的最優(yōu)，極大地提高了混合區(qū)域內(nèi)對不同地物的幾何特征計(jì)算精度。Abdul Nurunnabi另辟蹊徑，它利用RobustPCA方法克服了傳統(tǒng)的PCA方法對噪點(diǎn)過于敏感的弊端[14]。在固定的鄰域內(nèi)，通過RobustPCA先計(jì)算出局部幾何特征，再以區(qū)域生長方法對點(diǎn)云進(jìn)行分割。

本文提出了一種基于LiDAR點(diǎn)云數(shù)據(jù)的室內(nèi)平面圖自動生成方法，其關(guān)鍵技術(shù)點(diǎn)在于：使用了穩(wěn)健的點(diǎn)云法向量估計(jì)方法，從室內(nèi)LiDAR點(diǎn)云數(shù)據(jù)中提取墻面點(diǎn)云。經(jīng)過一系列優(yōu)化處理后，生成XoY平面上的矢量邊界，經(jīng)過修整后完成室內(nèi)平面圖的構(gòu)建。相對于傳統(tǒng)的矢量化方法，本方法具有更精確、成圖快、自動化程度高等優(yōu)點(diǎn)。

1 基于LiDAR點(diǎn)云的室內(nèi)平面圖自動生成

本文提出的基于LiDAR點(diǎn)云的室內(nèi)平面圖自動生成方法整體結(jié)構(gòu)流程如下圖1所示。分為冗余點(diǎn)離群點(diǎn)剔除、墻面提取、平面矢量化，矢量線段修整等幾個(gè)步驟。其中，基于RobustPCA的法向量穩(wěn)健估計(jì)確保了室內(nèi)墻面點(diǎn)云法向量計(jì)算的魯棒性，是后續(xù)工作的基礎(chǔ)，為本方法的關(guān)鍵技術(shù)點(diǎn)。

圖1 基于室內(nèi)LiDAR點(diǎn)云自動生成室內(nèi)平面圖流程圖Fig.1 Flowchart of automatic generation of indoor plan based on LiDAR point cloud

由于Lidar點(diǎn)云中存在大量的噪聲和冗余，本文方法首先剔除噪點(diǎn)、大量的地面點(diǎn)及天花板點(diǎn)。通過計(jì)算點(diǎn)到其最近點(diǎn)歐氏距離來判定，若該點(diǎn)到其最近點(diǎn)歐式距離大于某閾值，即判定為噪聲點(diǎn)。然后通過格網(wǎng)剖分統(tǒng)計(jì)Z值直方圖，從而區(qū)分地面點(diǎn)和天花板點(diǎn)。經(jīng)過上述步驟后，剩余點(diǎn)中的絕大多數(shù)則被認(rèn)為是墻面點(diǎn)。為實(shí)現(xiàn)墻面的邊界，開發(fā)了基于穩(wěn)健主成分分析（RobustPCA）的點(diǎn)云法向量估計(jì)方法。

1.1 基于RobustPCA的法向量穩(wěn)健估計(jì)

主成分分析（PCA）的顯著性功能已被用于研究特征面和分割與重建[15]。室內(nèi)LiDAR點(diǎn)云由于玻璃幕墻反射以及數(shù)據(jù)采集中平臺誤差等問題會有大量的噪聲點(diǎn)云存在。而傳統(tǒng)的PCA對噪聲十分敏感，具有較大的不確定性，無法滿足室內(nèi)LiDAR點(diǎn)云的法向量準(zhǔn)確計(jì)算。本文基于RobustPCA計(jì)算室內(nèi)LiDAR點(diǎn)云穩(wěn)健的表面特征，從而為墻面邊界的穩(wěn)健提取奠定基礎(chǔ)。

RobustPCA的關(guān)鍵步驟如下：

1）確定初始點(diǎn)集。使用KD-tree獲取離目標(biāo)點(diǎn)距離最近的N個(gè)點(diǎn)，計(jì)初始點(diǎn)集為H。在本文中設(shè)N為20。若H中點(diǎn)數(shù)小于3，視該點(diǎn)為噪聲點(diǎn)予以刪除。

2）根據(jù)公式（1）計(jì)算迭代次數(shù)It：

式中，Pr=0.99，h=1/3，ε=0.5為經(jīng)驗(yàn)值。ε的實(shí)際意義為點(diǎn)云的可置信度，代表最小的非噪聲點(diǎn)云占總體點(diǎn)云的百分比。

3）隨機(jī)從H中選取3個(gè)點(diǎn)組成子點(diǎn)集h，用PCA方法擬合一個(gè)三點(diǎn)平面方程。利用公式（2）計(jì)算H中所有點(diǎn)對應(yīng)該平面的OD值，并進(jìn)行排序。

式中，Pi為H中各個(gè)點(diǎn)，P￣為中心點(diǎn)，n→為h對應(yīng)的平面法向量。

4）取OD值較小的前hfree個(gè)點(diǎn)，用PCA擬合一個(gè)平面，計(jì)算最小特征值λ0，其中，

5）重復(fù)3）4）過程It次，取λ0最小的平面P，求H中所有點(diǎn)對應(yīng)于P的OD值，并計(jì)算所有OD值的中間絕對偏差MAD：

式中，a=1.482 6。

然后計(jì)算出H中所有點(diǎn)的Rz值：

將Rz值大于2.5的視為噪點(diǎn)，不參與計(jì)算，得到穩(wěn)健的點(diǎn)集子集Hr。若Hr中點(diǎn)數(shù)小于3，視為噪聲予以刪除。

6）用PCA方法計(jì)算Hr，得到目標(biāo)點(diǎn)穩(wěn)健的表面法向量及曲率k。其中為最小特征值λ0對應(yīng)的特征向量，曲率k為：

1.2 面片分割及墻面面片選取

為提取墻面面片，本文基于區(qū)域生成方法，并利用點(diǎn)的法向量、歐氏距離以及到原始平面的距離作為比較條件，確定搜索點(diǎn)是否與種子點(diǎn)進(jìn)行聚類，直到無法找到合適的鄰近點(diǎn)為止[16-18]。具體流程如下：

1）根據(jù)計(jì)算出的點(diǎn)法向量計(jì)算出點(diǎn)的曲率k，并以曲率k進(jìn)行排序，k值最小點(diǎn)被確定為種子點(diǎn)。

2）取出初始種子點(diǎn)，使用KDtree以r為半徑獲取其周圍所有候選點(diǎn)，本文中r取1.5 m。對于每個(gè)候選點(diǎn)，若其同時(shí)滿足3個(gè)條件：

①當(dāng)前點(diǎn)未被分割；

②當(dāng)前點(diǎn)曲率小于閾值Kt；

③當(dāng)前點(diǎn)法向量與初始種子點(diǎn)法向量夾角小于閾值St且當(dāng)前點(diǎn)與初始種子點(diǎn)所在平面的距離小于閾值Ht；

則將Pi加入當(dāng)前點(diǎn)容器將與種子隊(duì)列。

其中，根據(jù)多次實(shí)驗(yàn)結(jié)果，在本文中設(shè)定Kt取0.05，St取8°，Ht取0.1 m。

3）執(zhí)行2）直到所有點(diǎn)被分割，即完成了區(qū)域生長。

對聚類的點(diǎn)群根據(jù)表1中的參數(shù)進(jìn)行篩選，得到所需要的墻面點(diǎn)云。利用公式（6）計(jì)算每個(gè)墻面點(diǎn)云的法向量，從而擬合出每個(gè)墻面的數(shù)學(xué)方程。

表1 墻面點(diǎn)云篩選閾值Tab.1 Threshold of selection of wall point cloud

1.3 墻面邊界提取

根據(jù)分割出每個(gè)墻面的數(shù)學(xué)方程Ax+By+Cz+D=0，將其投影到XOY平面，從而獲取其與XOY平面的交線AX+BY+D=0。根據(jù)墻面面片點(diǎn)云外包矩形中距離較大的一對對角點(diǎn)計(jì)算其到直線Ax+By+D=0的垂足，從而獲得墻面的初始邊界：

求出所有的墻面邊界后，對提取出的墻面邊界利用下面步驟進(jìn)行優(yōu)化。首先，選取最長線段的方向?yàn)橹鞣较?，將方向與主方向近似的邊界修正為與主方向一致，將方向與主方向垂直的邊界修正為與主方向垂直。最后通過如下步驟實(shí)現(xiàn)邊界的連接：

1)計(jì)算出所有線段的長度Li，并以線段長度Li進(jìn)行排序，線段長度最長的線段被確定為種子線段。

2)取出初始種子線段，線段容器內(nèi)的其他線段為候選線段。對于每條候選線段，其同時(shí)滿足：

①當(dāng)前線段未被合并；

②前線段方向與種子線段夾角小于閾值A(chǔ)t；

③當(dāng)前線段與種子線段的距離小于閾值Dt；

則將Li加入當(dāng)前線段容器將與種子隊(duì)列。

其中，根據(jù)多次實(shí)驗(yàn)結(jié)果，At在本文中設(shè)定為10°，Dt設(shè)定為0.2 m。

然后，在合并后的墻面線段基礎(chǔ)上，進(jìn)行閉合多邊形搜索。具體的方法是：

把線段按長短排序，優(yōu)先選取較長線段為種子線段。

以種子線段的一個(gè)端點(diǎn)為起點(diǎn)，搜索離該點(diǎn)最近的其他線段的端點(diǎn)，若小于閾值Dt，則將兩線段連為折線。

以被連接線段的另一端點(diǎn)為起點(diǎn)搜索下一線段。重復(fù)②③過程，直到無法找到下一線段或找到初始線段。

若搜索停止且未搜索到初始線段的另一端點(diǎn)，則舍棄本次搜索。

若搜索到初始線段的另一端點(diǎn)，則發(fā)現(xiàn)閉合多邊形，停止搜索。

2 試驗(yàn)與分析

本文所用的室內(nèi)LiDAR點(diǎn)云采集背包搭載了Velodyne的HDL-32E的激光雷達(dá)傳感器，以及NovAtel的SPAN-CPT作為慣性測量單元（Inertia Measurement Unit，IMU），兩者之間剛性連接并已測兩者間相對姿態(tài)。

本文利用兩個(gè)不同類型、大小的室內(nèi)LiDAR點(diǎn)云為試驗(yàn)數(shù)據(jù)在Intel Core i7-4710MQ 2.50Ghz處理器與16G內(nèi)存的計(jì)算機(jī)對本文提出的方法進(jìn)行驗(yàn)證。

2.1 試驗(yàn)數(shù)據(jù)

兩份試驗(yàn)數(shù)據(jù)的基本情況見表2：

表2 試驗(yàn)數(shù)據(jù)說明Tab.2 Declaration of experiments data

分別對應(yīng)圖2(a)，圖2(b)。其中，數(shù)據(jù)1的場景為寫字樓，其特點(diǎn)是室內(nèi)窗戶較多，玻璃鏡面反射導(dǎo)致產(chǎn)生較多噪聲點(diǎn)。數(shù)據(jù)2的場景為商場，其特點(diǎn)為場景面積大，墻體長。

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

利用本文的方法提取的室內(nèi)平面圖如圖2(c)和2(d)所示。黑色線段為提取出的墻面線段，紅色線條為墻面線段首尾閉合形成的封閉多邊形。

圖2 試驗(yàn)數(shù)據(jù)與試驗(yàn)結(jié)果Fig.2 Experiments data and indoor plan results

統(tǒng)計(jì)結(jié)果表明：場景1中提取結(jié)構(gòu)線137條，準(zhǔn)確率為90.51%，召回率為94.48%，搜索到閉合多邊形5個(gè)。誤提取得墻面主要為較大桌子的立面，漏提的部分主要是被窗戶分隔開的小墻面。場景2中提取結(jié)構(gòu)線175條，準(zhǔn)確率為88.24%，召回率為97.59%，搜索到閉合多邊形13個(gè)。誤提取墻面主要為柜臺立面；漏提部分主要是弧形墻面。實(shí)驗(yàn)結(jié)果同時(shí)表明：墻面提取整體準(zhǔn)確率達(dá)到了88.06%，而且能夠提取跨度幾十米的墻面，并具有較好的抗噪性，證實(shí)了本文方法的穩(wěn)健性，見表3。

表3 試驗(yàn)結(jié)果與處理時(shí)間Tab.3 Experiments results and processing time

3 結(jié)束語

本文提出了一種基于LiDAR點(diǎn)云的室內(nèi)平面圖自動生成方法，該方法通過一種穩(wěn)健法向量估計(jì)方法實(shí)現(xiàn)墻面點(diǎn)云法向量的準(zhǔn)確估計(jì)，從而為室內(nèi)墻面邊界的準(zhǔn)確提取奠定了基礎(chǔ)。實(shí)際的試驗(yàn)結(jié)果表明：本文的方法能夠有效地從室內(nèi)掃描點(diǎn)云中穩(wěn)健提取墻面的邊界線，具有快速、準(zhǔn)確等特點(diǎn)，為室內(nèi)地圖的制作提供了不可或缺的基礎(chǔ)信息，鑒于室內(nèi)定位及導(dǎo)航對室內(nèi)地圖的精細(xì)化要求，自動化地提取樓梯、門等附屬設(shè)施將是本文下一步工作的重點(diǎn)。