激光雷達(dá)點云數(shù)據(jù)截面提取計算方法研究

熊曉光， 王 毅

（1. 北京洛斯達(dá)科技發(fā)展有限公司，北京100120；2. 中國地質(zhì)大學(xué)（武漢），武漢430074）

作為一種主動對地觀測技術(shù)， 機(jī)載激光雷達(dá)(Light Detection And Ranging, LiDAR) 能夠快速獲取地面點三維坐標(biāo)，具有全天時、全天候、高精度、成本低等特點， 對地物間縫隙具有一定的穿透性，已成為空間信息獲取的主要手段之一，該技術(shù)已經(jīng)在地形測繪、環(huán)境監(jiān)測、三維城市建模、電力系統(tǒng)選線等領(lǐng)域得到廣泛應(yīng)用[1-10]. 三維可視化是近期研究熱點，其關(guān)鍵技術(shù)之一是三維物體的截面獲取與顯示， 可用于顯示電力線路與周邊地物的空間關(guān)系，如設(shè)計線路與走廊范圍內(nèi)植被的高差，為設(shè)計線路及桿塔高度提供依據(jù). 但激光雷達(dá)獲取的空間三維點云具有數(shù)據(jù)量大、拓?fù)潢P(guān)系復(fù)雜、數(shù)據(jù)密度不均勻等特點，直接利用點云數(shù)據(jù)實現(xiàn)地物三維信息精確提取還很困難. 現(xiàn)有的大多數(shù)Lidar 點云處理算法在實踐中用于質(zhì)量控制及手工操作的時間，在整個數(shù)據(jù)處理時間中占據(jù)了較大比例[11]. 國內(nèi)外一些學(xué)者開展了相關(guān)研究，點云重建方法主要為：曲面擬合[12]、分段性重建、基于物理的重建、基于神經(jīng)網(wǎng)絡(luò)的重建等[13]；其中，隱式曲面重建方法易于表示拓?fù)浣Y(jié)構(gòu)復(fù)雜的幾何形體、無需對點云參數(shù)化，能夠方便進(jìn)行布爾運(yùn)算[14]. 文中就如何從散亂點云數(shù)據(jù)中有效提取截面信息進(jìn)行研究，通過點云數(shù)據(jù)的顯示、索引、選擇，基于八叉樹快速生成不同方向、不同深度的斷面圖，能夠較好展示地形、地物的空間關(guān)系，可有效應(yīng)用于電力選線等工作.

1 場景管理

圖1 八叉樹示意圖

散亂點云本身包含的結(jié)構(gòu)信息較少，在進(jìn)行某些操作如選擇等，往往需要遍歷全部點，因此這些操作的運(yùn)算量會隨著點的個數(shù)呈線性甚至指數(shù)級增加， 當(dāng)點集的數(shù)據(jù)較大時， 交互時間會比較長.在計算機(jī)圖形學(xué)中，常用場景管理技術(shù)包括加快渲染和碰撞檢測等，其基本原理是通過預(yù)先計算空間物體的結(jié)構(gòu)信息，并在渲染和碰撞檢測時，利用結(jié)構(gòu)信息排除部分?jǐn)?shù)據(jù)，從而減小計算量. 常用的場景管理數(shù)據(jù)結(jié)構(gòu)包括BSP 樹 (Binary Space Partitioning tree)，k-d 樹(k-dimensional tree), 四叉樹(Quadtree)和八叉樹(Octree)等. 這些樹形結(jié)構(gòu)的優(yōu)點是，通常在判斷子節(jié)點前，已通過對父節(jié)點的判斷排除了大部分?jǐn)?shù)據(jù)，減小計算量.

數(shù)據(jù)結(jié)構(gòu)中， 四叉樹通常用于處理二維數(shù)據(jù)，它的根節(jié)點為包含全部點集的四邊形，在遞歸生成過程中， 每次將當(dāng)前節(jié)點的四邊形劃分為上左、上右、下左、下右四等分，繼續(xù)遞歸直到遇到終止條件為止. 常用的終止條件包括節(jié)點中點的個數(shù)小于閾值或樹的深度達(dá)到某一閾值等. 八叉樹是四叉樹在三維空間的擴(kuò)展，其每一個節(jié)點為一個平行六面體的包圍盒，每次劃分為八個子節(jié)點. 圖1 是網(wǎng)格及其八叉樹圖像示意圖，其中圖1（a）為Stanford Bunny 的網(wǎng)格圖像，圖1（b）為由該網(wǎng)格圖生成的八叉樹圖像. 由圖1 可見，八叉樹具有在原始點云稀疏的地方節(jié)點較少，在原始點云密集的部分節(jié)點較多的特性，該特性對于加速數(shù)據(jù)處理有重要意義[15].

除了生成樹外，遍歷也是八叉樹常見的操作之一. 在點云處理中，計算當(dāng)前節(jié)點包圍盒中所包含的全部節(jié)點即是通過遍歷實現(xiàn). 取節(jié)點node 包圍盒中的全部點集放入容器vec 的步驟如圖2.

2 點云的快速選擇

圖2 遞歸遍歷實現(xiàn)方式

點云的選擇是常用的交互操作之一，對于某些數(shù)據(jù)， 經(jīng)常需要手動選擇部分感興趣區(qū)域進(jìn)行處理，或者是手動選擇并刪除某些噪聲點. 一般使用在屏幕上畫多邊形的方式對點云進(jìn)行框選. 為了選中多邊形中的點云，需要獲取當(dāng)前的模型視圖及投影矩陣，對當(dāng)前全部點使用模型視圖投影變換得到每個點對應(yīng)的屏幕坐標(biāo)，再計算判斷該屏幕坐標(biāo)是否位于多邊形內(nèi)部. 判斷二維空間中點與多邊形的關(guān)系可以通過依次判斷點與多邊形每條邊的關(guān)系得出.

由于上述過程需要對全部點進(jìn)行判斷，因此隨著點云個數(shù)的增加，運(yùn)算速度會明顯變慢. 而八叉樹用于交互式選擇操作的優(yōu)勢在于對節(jié)點進(jìn)行遞歸調(diào)用時，可以在到達(dá)葉子節(jié)點之前排除大部分的點集. 八叉樹節(jié)點的包圍盒在應(yīng)用模型視圖變換及投影變換后得到的多邊形與屏幕上用于框選的多邊形有四種可能的關(guān)系，依次是：

1）包圍盒投影與框選多邊形相離；

2）包圍盒投影與框選多邊形相交；

3）包圍盒投影被包含在框選多邊形中；

4）框選多邊形被包含在包圍盒投影中.

在遞歸判斷中，依次判斷當(dāng)前包圍盒投影后與框選多邊形的關(guān)系，如果為①，則忽略該節(jié)點及其子節(jié)點； 如果為②或④并且該節(jié)點為葉子節(jié)點，則取出其中的全部點云并依次判斷與框選多邊形的關(guān)系，否則繼續(xù)依次判斷該節(jié)點的子節(jié)點；如果為③，則調(diào)用本文上一節(jié)提到的遍歷算法取出其中的全部點云，并設(shè)置為選中狀態(tài)[16].

以圖3 所示的四叉樹及框選多邊形為例，假設(shè)點集均勻分布，則在對根節(jié)點的四個子節(jié)點的判斷過程中，即可排除3/4 的數(shù)據(jù). 更特殊的情況，當(dāng)框選多邊形與根節(jié)點包圍盒相離時，該方法僅需要判斷根節(jié)點包圍盒與框選多邊形的投影關(guān)系， 然而，如果沒有采用任何數(shù)據(jù)結(jié)構(gòu)管理點云，那么將不得不對全部點云遍歷一遍.

圖3 四叉樹中框選點云示意圖

3 基于八叉樹的近似橫截面生成

在諸如電力布線、 鐵道路線規(guī)劃等應(yīng)用中，經(jīng)常需要獲取三維地形任意方向的橫截面信息. 對于機(jī)載激光雷達(dá)點云數(shù)據(jù)， 由于點云的離散特征，通常無法獲取精確的截面坐標(biāo). 為了解決該問題，本文提出一種基于八叉樹的替代方案，實現(xiàn)了近似橫截面的快速生成.

前文提到， 八叉樹在點云密集的部分節(jié)點較多，在點云稀疏的部分節(jié)點較少. 同時，八叉樹還有另外一個特征，即點云密集的部分樹的葉子深度較深，在稀疏的部分樹的葉子深度較淺，即八叉樹中較深的葉子節(jié)點可近似代替三維點云，如圖1 所示.綜合考慮上述特征，可以取八叉樹中大于某一深度值的節(jié)點的包圍盒與平面的交點作為點云位于該平面的近似橫截面，該算法的基本過程如下[17]：

Step 1：設(shè)置節(jié)點深度閾值hmin；

Step 2：將根節(jié)點設(shè)置為當(dāng)前節(jié)點；

Step 3：判斷當(dāng)前節(jié)點是否與給定的平面相交，如果不相交則跳至Step 4，如果相交則判斷該節(jié)點是否為葉子節(jié)點，如果不為葉子節(jié)點，則依次對其子節(jié)點設(shè)置為當(dāng)前節(jié)點，并返回Step 3，如果為葉子節(jié)點并且該節(jié)點的深度大于或等于hmin， 則將交點存入橫截面點云，否則跳至Step 4；

Step 4：結(jié)束生成.

由上述過程可知，該算法同樣基于八叉樹的遞歸遍歷， 但是由于在對節(jié)點的遞歸訪問過程中，僅有少數(shù)的父節(jié)點與平面相交，因此可以在判斷子節(jié)點之前排除大部分的父節(jié)點，從而對程序起到明顯的加速作用.

任意近似斷面的截取操作通過用戶在2D 屏幕上畫線進(jìn)行交互，在獲取屏幕上所畫線段的屏幕坐標(biāo)后，任取直線上的兩點計算其視口坐標(biāo)，再反投影得到這兩點的三維空間坐標(biāo)；同時，還可以計算出當(dāng)前視線的方向向量， 該向量平行于待求的平面，將其與平面上的兩點連線叉乘即可獲得平面法向，從而進(jìn)一步得到平面的方程. 其中，當(dāng)前視線的方向向量可以通過對視口坐標(biāo)（x, y, 0）與（x, y, 1）反投影得到， x 和y 可以為任意值. 三維空間中八叉樹節(jié)點包圍盒與平面相交的交點可以通過依次對包圍盒中的邊與平面計算交點得到.

4 實驗結(jié)果

本節(jié)將分別介紹點云顯示、基于八叉樹的點云選取、點云近似橫截面生成、頂點拾取和測量功能的實驗結(jié)果.

激光雷達(dá)點云一次掃描得到的數(shù)據(jù)可達(dá)到數(shù)百萬甚至千萬，本文的可視化實驗方式采用圖形處理單元GPU(Graphic Process Unit)進(jìn)行硬件加速，使點云顯示和交互操作時控制幀率在可接受范圍內(nèi)， 調(diào)用OpenGL 接口和GPU 硬件驅(qū)動層上封裝的C++ API，實現(xiàn)點云渲染和拾取等交互操作.

圖4 給原始點云添加了偽彩色，偽彩色的顏色表有一定的重合， 圖中黃色代表海拔較高的區(qū)域，紅色代表海拔較低的區(qū)域，從圖中可以看出，以海拔高度作為索引，使用顏色表對點云的顏色進(jìn)行設(shè)置后，由于不同高度的點云顏色不同，因此可以較容易區(qū)分出點云的高度和邊緣，從而進(jìn)一步區(qū)分出建筑物和植被的形狀以及地形的起伏.

圖4 按高程對點云賦予偽彩結(jié)果

圖5 顯示了基于八叉樹的任意多邊形的點云選擇結(jié)果，對于任意多邊形，都能快速搜索到其中包含的點云，圖5（a）為簡單凸多邊形選擇，圖5（b）為凹多邊形選擇，圖5（c）為蝶形多邊形選擇的結(jié)果.

圖5 基于八叉樹的點云框選結(jié)果

圖6 為使用基于八叉樹的近似橫截面生成結(jié)果. 圖6（a）和圖6（c）為從不同角度觀察時橫截面與原始點云疊加顯示的結(jié)果， 灰色斜線為橫截面，橫截面的寬度為2.5m，圖6（c）中的橫截面與圖6（a）相同. 圖6（b）為從圖6（a）中的同一角度觀察，橫截面的顯示結(jié)果， 由于觀察角度與橫截面平行，因此橫截面在圖6（b）中退化為一條直線. 圖6（d）為從圖6（c）中同一位置觀察，僅顯示橫截面的結(jié)果，由圖6（d）可以看出，盡管這里使用的是近似算法， 得到的橫截面仍然可以較好地反映地形的變化，甚至可以顯示出電力塔及植被的垂直結(jié)構(gòu). 基于八叉樹索引結(jié)構(gòu)進(jìn)行截面計算的效率與點云數(shù)量有關(guān)，當(dāng)點云數(shù)量時，效率提高程度不顯著；反之亦然. 在點云數(shù)量為500 萬的情況下，基于八叉樹索引方法計算效率提高10 倍以上.

圖7 展示了基于八叉樹的頂點拾取與距離測量結(jié)果. 圖7（a）中電力塔的右上角紅色頂點標(biāo)記出了拾取的頂點，圖7（b）展示了距離測量功能，量測的對象為中間鐵塔兩頂端間的距離， 紅色頂點和藍(lán)色線段標(biāo)記出了此次測量操作，測量出的距離為11m.

5 總 結(jié)

激光雷達(dá)點云的數(shù)據(jù)處理是目前地形測繪、電力設(shè)計、數(shù)字城市等領(lǐng)域的研究熱點，本文針對點云數(shù)據(jù)量大、結(jié)構(gòu)關(guān)系復(fù)雜的特點，基于OpenGL，并通過建立三維點云的索引關(guān)系，減少了交互中的計算量，提高了點云交互的效率，適用于大量三維數(shù)據(jù)的處理. 隨著GPU 的發(fā)展，越來越多的通用計算將在GPU 上完成，因此，下一步將研究如何利用GPU 進(jìn)一步加速計算.

圖6 基于八叉樹近似橫截面生成結(jié)果

圖7 基于八叉樹的頂點拾取與距離測量

[1] 馬洪超，姚春靜. 徠卡機(jī)載激光雷達(dá)的數(shù)據(jù)獲取與處理[J]. 測繪通報，2008，10：70-71.

[2] 張 煜，竇延娟，張曉東. 機(jī)載激光雷達(dá)數(shù)據(jù)采集及數(shù)據(jù)處理[J].長江科學(xué)院院報，2010， 27(1)：13-21.

[3] 詹慶明，梁玉斌. 激光雷達(dá)數(shù)據(jù)處理、信息提取與應(yīng)用[J]. 地理信息世界，2011，4(2)：38-39.

[4] 陳松堯， 程新文. 機(jī)載LIDAR 系統(tǒng)原理及應(yīng)用綜述[J]. 測繪工程，2007，16(1)：27-31.

[5] 王俊剛，李新科. 機(jī)載激光雷達(dá)技術(shù)在電網(wǎng)工程建設(shè)中的應(yīng)用[J].廣東電力，2009，22(9)：46-49.

[6] 周淑芳，李增元，范文義，等. 基于機(jī)載激光雷達(dá)數(shù)據(jù)的DEM 獲取及應(yīng)用[J]. 遙感技術(shù)與應(yīng)用，2007，22(3)：356-360.

[7] 武繼廣. 基于機(jī)載激光雷達(dá)和遙感影像融合的地物探測方法研究[J]. 首都師范大學(xué)學(xué)報:自然科學(xué)版，2009，30(4)：6-11.

[8] 鞏淑楠，陳云，徐敏. 機(jī)載雷達(dá)數(shù)據(jù)處理方法的研究與應(yīng)用[J].測繪與空間地理信息，2010，33(5)：165-167.

[9] 隋立春，宋會傳，馬遠(yuǎn)新，等. 航空激光雷達(dá)數(shù)據(jù)處理原理及其應(yīng)用前景[J]. 測繪科學(xué)技術(shù)學(xué)報，2007，24(3)：850-851.

[10] 王 蕊，李俊山，劉玲霞，等. 基于幾何特征的點云配準(zhǔn)算法[J].江西理工大學(xué)學(xué)報，2009，30(5)：768-773.

[11] 賴旭東. 機(jī)載激光雷達(dá)基礎(chǔ)原理與應(yīng)用[M]. 北京: 電子工業(yè)出版社, 2010.

[12] Hoppe H, DeRose T, Duchamp T, et al. Surface reconstruction from unorganized points[M]. ACM, 1992.

[13] Pratt V. Direct least-squares fitting of algebraic surfaces[C]//ACM SIGGRAPH Computer Graphics. ACM, 1987, 21(4): 145-152.

[14] Carcenac M,Acan A.Modeling an isosurface with a neural network[C]//Computer Graphics and Applications, 2000. Proceedings. The Eighth Pacific Conference on.IEEE,2000:165-174.

[15] Donald Hearn. 計算機(jī)圖形學(xué)[M]. 蔡士杰，譯. 北京：電子工業(yè)出版社，2007.

[16] Samet H. Neighbor finding in images represented by octrees[J].Computer Vision, Graphics, and Image Processing, 1989, 46(3):367-386.

[17] De Berg M, Cheong O, Van Kreveld M. Computational geometry:algorithms and applications[M]. Springer, 2008.