熊曉光， 王 毅

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

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

1 場(chǎng)景管理

圖1 八叉樹示意圖

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

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

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

2 點(diǎn)云的快速選擇

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

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

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

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

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

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

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

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

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

圖3 四叉樹中框選點(diǎn)云示意圖

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

圖4 按高程對(duì)點(diǎn)云賦予偽彩結(jié)果

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

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

圖6 為使用基于八叉樹的近似橫截面生成結(jié)果. 圖6（a）和圖6（c）為從不同角度觀察時(shí)橫截面與原始點(diǎn)云疊加顯示的結(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)行截面計(jì)算的效率與點(diǎn)云數(shù)量有關(guān)，當(dāng)點(diǎn)云數(shù)量時(shí)，效率提高程度不顯著；反之亦然. 在點(diǎn)云數(shù)量為500 萬(wàn)的情況下，基于八叉樹索引方法計(jì)算效率提高10 倍以上.

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

5 總 結(jié)

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

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

圖7 基于八叉樹的頂點(diǎn)拾取與距離測(cè)量

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

[2] 張 煜，竇延娟，張曉東. 機(jī)載激光雷達(dá)數(shù)據(jù)采集及數(shù)據(jù)處理[J].長(zhǎng)江科學(xué)院院報(bào)，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]. 測(cè)繪工程，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á)和遙感影像融合的地物探測(cè)方法研究[J]. 首都師范大學(xué)學(xué)報(bào):自然科學(xué)版，2009，30(4)：6-11.

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

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

[10] 王 蕊，李俊山，劉玲霞，等. 基于幾何特征的點(diǎn)云配準(zhǔn)算法[J].江西理工大學(xué)學(xué)報(bào)，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ì)算機(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.