王世杰，艾明耀，馬 捷，嚴(yán) 俊

（1.河南省交通規(guī)劃勘察設(shè)計(jì)院有限責(zé)任公司，河南 鄭州 450052；2.武漢大學(xué) 遙感信息工程學(xué)院，湖北 武漢 430079）

基于KD樹的LiDAR點(diǎn)云索引方法及其在公路勘測中的應(yīng)用

王世杰1，艾明耀2，馬 捷1，嚴(yán) 俊2

（1.河南省交通規(guī)劃勘察設(shè)計(jì)院有限責(zé)任公司，河南 鄭州 450052；2.武漢大學(xué) 遙感信息工程學(xué)院，湖北 武漢 430079）

針對基于LiDAR點(diǎn)云公路勘測設(shè)計(jì)中高密度、海量、散亂點(diǎn)云的索引與管理難點(diǎn)，提出一種基于KD樹的LiDAR點(diǎn)云索引方法，對機(jī)載LiDAR點(diǎn)云進(jìn)行高效管理，在此基礎(chǔ)上快速生成縱橫斷面，實(shí)現(xiàn)基于LiDAR點(diǎn)云的公路勘測應(yīng)用。實(shí)驗(yàn)結(jié)果表明，該方法能夠支持高密度大數(shù)據(jù)量點(diǎn)云的一體化索引管理，能夠很好地支持基于LiDAR的公路勘測設(shè)計(jì)。

機(jī)載LiDAR；點(diǎn)云；KD樹；索引；公路勘測

隨著以3S技術(shù)為基礎(chǔ)，以現(xiàn)代高分辨率衛(wèi)星對地觀測，全球重力場模型及空間信息分析技術(shù)為核心的對地觀測技術(shù)的發(fā)展，全球定位系統(tǒng)、航測遙感、高分辨率衛(wèi)星在公路規(guī)劃、勘察與設(shè)計(jì)和信息化管理中得到廣泛應(yīng)用。由于實(shí)際公路勘測對高程和效率的高要求，GPS-RTK、高分辨率遙感技術(shù)和常規(guī)航測及低空航測精度難以滿足公路測量的要求和建立公路數(shù)據(jù)庫的任務(wù)[1]。國外，三維激光掃描系統(tǒng)已經(jīng)用于公路的勘測設(shè)計(jì)以及維護(hù)。國內(nèi)也引進(jìn)了LiDAR設(shè)備與技術(shù)，用于公路勘測選線、線路設(shè)計(jì)，但多采用成熟的LiDAR數(shù)據(jù)處理軟件得到DEM、DOM和DLG等產(chǎn)品，將這些數(shù)據(jù)產(chǎn)品導(dǎo)入設(shè)計(jì)軟件進(jìn)行公路的勘測和選線設(shè)計(jì)等[2-4]。因此，研究利用高密度LiDAR點(diǎn)云的公路勘測設(shè)計(jì)方法，對于提高公路勘測設(shè)計(jì)精準(zhǔn)度和效率、公路工程和信息化運(yùn)營管理有著極其重要的現(xiàn)實(shí)意義。

基于LiDAR點(diǎn)云的公路勘測設(shè)計(jì)需要解決將高密度、海量、散亂點(diǎn)云導(dǎo)入公路勘測設(shè)計(jì)平臺(tái)（AutoCAD、緯地CAD、EiCAD等）進(jìn)行三維可視化顯示，方便勘測設(shè)計(jì)人員直接操作點(diǎn)云數(shù)據(jù)，快速提取所需要的縱、橫斷面及對周邊三維地形的觀察。本文提出了一種基于KD樹的LiDAR點(diǎn)云索引方法，對機(jī)載LiDAR點(diǎn)云進(jìn)行高效管理，在此基礎(chǔ)上快速生成縱橫斷面，實(shí)現(xiàn)基于LiDAR點(diǎn)云的公路勘測應(yīng)用。實(shí)驗(yàn)表明，本文提出的方法能夠支持高密度大數(shù)據(jù)量點(diǎn)云的一體化索引管理，能夠很好地支持基于LiDAR的公路勘測設(shè)計(jì)。

1 機(jī)載LiDAR原理及數(shù)據(jù)特點(diǎn)

機(jī)載LiDAR集成激光測距儀、動(dòng)態(tài)差分GPS接收機(jī)（DGPS）、慣性導(dǎo)航系統(tǒng)（INS）、成像設(shè)備和同步控制裝置等[5,6]，通過激光測距與DGPS、IMU獲取的位置和姿態(tài)數(shù)據(jù)聯(lián)合解算，能夠直接快速地獲取地物表面的三維空間坐標(biāo)，生成數(shù)字高程模型，如圖1所示。

圖1 LiDAR原理示意圖

機(jī)載LiDAR作為直接的主動(dòng)測量方式，能夠獲取高密度、海量的三維點(diǎn)云。目前大部分的商業(yè)機(jī)載LiDAR系統(tǒng)都能達(dá)到每m2幾個(gè)數(shù)據(jù)點(diǎn)的密度。例如，F(xiàn)li-Map1系統(tǒng)可達(dá)9點(diǎn)/m2[6]，如果采用Fli-MAP1系統(tǒng)進(jìn)行公路勘測測量，每km2可以達(dá)到900萬個(gè)點(diǎn)，其以標(biāo)準(zhǔn)格式存儲(chǔ)可以達(dá)到200 M。在實(shí)際工程中機(jī)載激光雷達(dá)的飛行區(qū)域可以達(dá)到幾百甚至上千km2，如此海量的數(shù)據(jù)給數(shù)據(jù)的存儲(chǔ)、處理帶來了巨大挑戰(zhàn)，也直接影響到LiDAR在公路勘測、數(shù)字城市、水利電力勘測等領(lǐng)域中的應(yīng)用。

2 基于KD樹的LiDAR點(diǎn)云索引方法

對于海量、離散的機(jī)載LiDAR點(diǎn)云數(shù)據(jù)而言，選擇合適的空間索引方法以便有效地實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)、查詢和組織管理是非常重要的。合適的索引方法對執(zhí)行點(diǎn)云存貯、查詢、操作，實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的快速搜索、建模和重復(fù)應(yīng)用、計(jì)算以及入庫存檔有很大的幫助和便利。在目前的研究和應(yīng)用中，對LiDAR點(diǎn)云數(shù)據(jù)進(jìn)行空間索引建立的方法主要有規(guī)則格網(wǎng)、四叉樹、八叉樹等[7,8]。

KD樹[9,10]是k（k≥2）維的二叉索引樹，主要用于檢索多屬性的數(shù)據(jù)或多維點(diǎn)數(shù)據(jù)。它要么是一棵空樹，要么是一棵具有下列性質(zhì)的二叉樹：

1）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的第d維的值均小于它的根結(jié)點(diǎn)的第d維的值，其中d為根結(jié)點(diǎn)的分辨器值；

2）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的第d維的值均大于或等于它的根結(jié)點(diǎn)的第d維的值；

3）它的左右子樹也分別為KD樹。

與二叉索引樹不同的是，KD樹的每個(gè)結(jié)點(diǎn)表示k維空間的一個(gè)點(diǎn)，而且樹的每一層都根據(jù)這層的分辨器作出分枝決策。在本文中，KD樹的第i層的分辨器定義為：i mod k（樹的根結(jié)點(diǎn)所在的層為第0層，根結(jié)點(diǎn)孩子所在的層為第1層，依次遞增）[10,11]，取分辨器所在數(shù)據(jù)維的中值作為分割點(diǎn)。根據(jù)這一原則，三維點(diǎn)集構(gòu)建KD樹時(shí)，首先第0層的分辨器為X，根據(jù)所有X值的中值來決定根結(jié)點(diǎn)，左右子樹依據(jù)根結(jié)點(diǎn)X值進(jìn)行分割，所有X值小于根結(jié)點(diǎn)X值的點(diǎn)都分配于左子樹中，大于根結(jié)點(diǎn)X值的點(diǎn)分配于右子樹中；根結(jié)點(diǎn)的孩子結(jié)點(diǎn)則以Y值進(jìn)行類似的分割，得到第二層；根結(jié)點(diǎn)的孫結(jié)點(diǎn)則以Z值進(jìn)行類似的分割，是為第三層；根結(jié)點(diǎn)的曾孫結(jié)點(diǎn)則以X值進(jìn)行分割；一直進(jìn)行類似的分割直至葉結(jié)點(diǎn)，從而完成三維點(diǎn)集的KD樹。

圖2 KD樹構(gòu)建示意圖（K=2）[10]

圖2是一個(gè)二維KD樹的實(shí)例，結(jié)點(diǎn)的二維坐標(biāo)為A（7, 2），B（5, 4），C（9, 6），D（2, 3），E（4, 7），F(xiàn)（8, 1）。根結(jié)點(diǎn)A點(diǎn)分辨器的值為0（X軸），其的左子樹的所有數(shù)據(jù)點(diǎn)B、D、E的X維的值都比A的X的值7小，右子樹的所有數(shù)據(jù)點(diǎn)C、F的X的值都大于7。結(jié)點(diǎn)B的分辨器的值為l（Y軸），則其左子樹的數(shù)據(jù)點(diǎn)D的Y維的值比B的Y維值4小，右子樹的數(shù)據(jù)點(diǎn)E的Y維值大于4。

為了測試索引的性能，分別取100萬、200萬、300萬點(diǎn)云數(shù)據(jù)對KD樹索引效率進(jìn)行實(shí)驗(yàn)，本文實(shí)驗(yàn)中采用的計(jì)算機(jī)硬件環(huán)境為CPU Intel E5300 2.60 GHz、內(nèi)存2 GB，系統(tǒng)環(huán)境為Windows XP SP3 32位操作系統(tǒng)。

從圖3可以看出，最鄰近查詢所耗費(fèi)時(shí)間與所查詢的點(diǎn)個(gè)數(shù)成正相關(guān)的關(guān)系，所查詢的點(diǎn)越多，所耗費(fèi)的時(shí)間越多。同時(shí)，建立索引的點(diǎn)云數(shù)目越大，最鄰近查詢所耗費(fèi)的時(shí)間也越多。

圖3 最鄰近查詢的時(shí)間消耗

3 基于KD樹索引的高密度LiDAR點(diǎn)云公路斷面設(shè)計(jì)

3.1 縱斷面設(shè)計(jì)

假定公路主線已經(jīng)給定，基于LiDAR點(diǎn)云數(shù)據(jù)獲取該公路縱斷面的算法為：

1）從公路主線起點(diǎn)開始，每隔1 m獲取公路主線上的點(diǎn)Vi（X，Y）。

2）基于LiDAR點(diǎn)云數(shù)據(jù)，利用KD樹索引，查找以Vi（X，Y）點(diǎn)為圓心，以5 m為半徑的圓內(nèi)的點(diǎn)，取其距離加權(quán)高程值作為Vi點(diǎn)的高程H，得到縱斷面數(shù)據(jù)的第i個(gè)點(diǎn)Vi（X，Y，Z）。

3）重復(fù)前兩步，直至達(dá)到公路主線的終點(diǎn)。

4）將點(diǎn)V1，V2，…，Vi，…，Vn（假設(shè)最終在公路主線上取到n個(gè)點(diǎn)）依次連接，即可得到該公路的縱斷面數(shù)據(jù)。

圖4為按照以上步驟所獲取的公路縱斷面。其中，左側(cè)窗口影像中的紅色線條即為目標(biāo)公路主線，右側(cè)窗口中是該公路的縱斷面，橫坐標(biāo)為沿公路主線與公路起點(diǎn)之間的距離，縱坐標(biāo)為在公路上取到的點(diǎn)的高程值。

圖4 縱斷面

3.2 橫斷面設(shè)計(jì)

在KD樹索引下，基于LiDAR點(diǎn)云數(shù)據(jù)獲取公路主線橫斷面算法步驟如下：

1）沿公路主線，從公路起點(diǎn)開始，每隔L m（本文設(shè)為5 m）取公路上的點(diǎn)，最終得到點(diǎn)W1，W2，…，Wi，…，Wn。

2）過點(diǎn)Wi作垂直于該點(diǎn)所在公路直線段的垂線段V，設(shè)定垂線段長度為S m（本文設(shè)為20 m），且點(diǎn)Wi為垂線段的中點(diǎn)。從線段V一端開始，每隔S m（本文設(shè)為1 m）取點(diǎn)，得到點(diǎn)P1，P2，…，Pn?；贚iDAR點(diǎn)云數(shù)據(jù)以及KD樹索引，獲取以Pi點(diǎn)為圓心，R為半徑的圓內(nèi)所有的點(diǎn)，求其高程的距離加權(quán)平均值作為Pi的高程。重復(fù)這一計(jì)算過程，最終獲取該垂線段V上所有點(diǎn)P1,P2,…,Pn的高程值H1，H2，…，Hn，以及橫斷面數(shù)據(jù)的坐標(biāo)（v1，H1），（v2，H2），…， （vn，Hn），其中v1是P2到垂線段起點(diǎn)的距離，Hi為該點(diǎn)的高程值。將點(diǎn)P1，P2，…，Pn依次連接，即可得到點(diǎn)Wi處公路的橫斷面。

3）重復(fù)前一步，直到生成所有點(diǎn)W1，W2，…，Wi，…，Wn的橫斷面數(shù)據(jù)，并將各個(gè)點(diǎn)的橫斷面數(shù)據(jù)依次由下而上進(jìn)行排列，可得到該公路的橫斷面數(shù)據(jù)。

圖5為按照以上步驟所獲取的公路橫斷面。其中，左側(cè)窗口影像中的紅色線條標(biāo)示的即為目標(biāo)公路主線，右側(cè)窗口中是該公路的橫斷面，橫坐標(biāo)代表與公路正交的垂線段，縱坐標(biāo)代表在公路上取到的用來生成橫斷面的正交點(diǎn)離開公路起點(diǎn)的距離。

圖5 橫斷面

4 結(jié) 語

本文給出了基于KD樹索引的高密度LiDAR點(diǎn)云公路勘測方法，利用LiDAR點(diǎn)云建立KD樹索引，快速查詢并計(jì)算得到公路設(shè)計(jì)中需要的縱橫斷面。利用LiDAR點(diǎn)云直接構(gòu)建公路勘測設(shè)計(jì)中的縱橫斷面，省去了生成DOM和DEM的步驟，避免了因數(shù)據(jù)處理產(chǎn)生的精度損失，提高了公路勘測設(shè)計(jì)的效率。

[1] 富志鵬.基于LiDAR的高速公路測設(shè)技術(shù)應(yīng)用研究[D].西安:長安大學(xué), 2011

[2] 蘭增榮,胡友健,隆華平,等. LiDAR技術(shù)在公路勘測中的應(yīng)用[J].工程地球物理學(xué)報(bào),2009,6(1): 99-104

[3] 李海亮,陳楚江,余紹淮,等.基于密集激光雷達(dá)數(shù)據(jù)的公路設(shè)計(jì)地表信息生成方法[J].中外公路,2011,31(4):330-332

[4] 王玲玲.機(jī)載激光雷達(dá)技術(shù)在山區(qū)高速公路勘測設(shè)計(jì)中的應(yīng)用[J].公路交通科技:應(yīng)用技術(shù)版,2010(7):115-117

[5] 李清泉,李必軍,陳靜.激光雷達(dá)測量技術(shù)及其應(yīng)用研究[J].武漢測繪科技大學(xué)學(xué)報(bào),2000,25(5):387-392

[6] 張小紅.機(jī)載激光雷達(dá)測量技術(shù)理論與方法[M].武漢:武漢大學(xué)出版社,2007

[7] 路明月,何永健.三維海量點(diǎn)云數(shù)據(jù)的組織與索引方法[J].地球信息科學(xué),2008,10(2):190-194

[8] Bertino E,Ooi B C.The Indispensability of Dispensable Indexes[J].IEEE Transactions on Knowledge and Data Engineering,1999,1(11):17-26

[9] Friedman J H, Louis B J, Ari F R.An Algorithm for Finding Best Matches in Logarithmic Expected Time[J].ACM Transactions on Mathematical Software,1977,3(3):209-226

[10] Wikipedia.Quadtree[EB/OL].http://en.wikipedia.org/wiki/ K-d_tree,2012-05-01

[11] Bentley J L.Multidimensional Binary Search Trees used for Associative Searching[J].Communications of the ACM,1975,18(9):509-517

P237.3

B

1672-4623（2015）01-0140-03

10.3969/j.issn.1672-4623.2015.01.046

王世杰，正高職高級(jí)工程師，主要研究方向?yàn)楣房睖y與設(shè)計(jì)。

2014-01-15。