基于KD樹的點(diǎn)云索引技術(shù)研究

王儒　胡萍　蔣俊豪

【摘 要】隨著計算機(jī)技術(shù)的進(jìn)步以及社會需求的不斷增加，激光雷達(dá)技術(shù)作為一種三維空間信息的實(shí)時獲取手段，正以日新月異的速度向前發(fā)展。激光雷達(dá)技術(shù)有效地拓寬了數(shù)據(jù)源范圍，改變了數(shù)據(jù)獲取模式，能夠快速獲取高分辨率數(shù)字表面模型。然而，點(diǎn)云數(shù)據(jù)的海量性一直是制約點(diǎn)云數(shù)據(jù)處理方法的重要因素，迫切需要尋找一種高效空間索引方法來管理海量點(diǎn)云數(shù)據(jù)。因此，研究點(diǎn)云數(shù)據(jù)的管理和處理方法，形成點(diǎn)云的數(shù)據(jù)處理理論顯得十分重要。本文利用kd-tree來管理點(diǎn)云數(shù)據(jù)的索引，實(shí)驗證明kd-tree能高效的管理海量點(diǎn)云數(shù)據(jù)。

【關(guān)鍵詞】點(diǎn)云；kd-tree；索引；激光雷達(dá)

0 引言

地球空間信息的快速獲取和智能化處理是當(dāng)前測繪領(lǐng)域的研究熱點(diǎn)，也是“數(shù)字地球”、“數(shù)字城市”急待解決的問題。21世紀(jì)測繪技術(shù)必將實(shí)現(xiàn)高精度化、高速化、高效率化和標(biāo)準(zhǔn)化，空間數(shù)據(jù)處理必將實(shí)現(xiàn)智能化[1]。激光雷達(dá)技術(shù)是近幾十年攝影測量與遙感領(lǐng)域最具有革命性的成就之一，是繼全球定位系統(tǒng)（GPS）發(fā)明以來在遙感測繪領(lǐng)域的又一座里程碑，同時，激光雷達(dá)也可自成體系，組成地面三維激光掃描儀[2]。激光雷達(dá)系統(tǒng)掃描獲得數(shù)以萬計的激光點(diǎn)，被形象地稱之為點(diǎn)云[3]。對于點(diǎn)云數(shù)據(jù)來講，高效的索引結(jié)構(gòu)還是其他數(shù)據(jù)處理的基礎(chǔ)，例如點(diǎn)云濾波、點(diǎn)云精簡都依存于某種索引結(jié)構(gòu)。

本文針對激光雷達(dá)系統(tǒng)所獲取的點(diǎn)云數(shù)據(jù)在管理與檢索，提出了基于kd-tree的點(diǎn)云管理方案。并利用三維激光點(diǎn)云數(shù)據(jù)進(jìn)行實(shí)驗，結(jié)果表明基于kd-tree的點(diǎn)云管理能高效的管理海量點(diǎn)云數(shù)據(jù)。

1 KD 樹基本原理

采用KD 樹結(jié)構(gòu)分割散亂點(diǎn)云，能明顯加快搜索速度，為k 領(lǐng)域的建立打下堅實(shí)基礎(chǔ)。KD 樹是K-dimension tree 的縮寫，是對數(shù)據(jù)點(diǎn)在k 維空間（如二維（ x，y），三維（ x，y，z），k維（x，y，z，…））中劃分的一種數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索：主要有范圍搜索和最近鄰搜索。

2 基于KD樹建立點(diǎn)云鄰域

點(diǎn)云數(shù)據(jù)為散亂數(shù)據(jù)點(diǎn)，即對于每個數(shù)據(jù)點(diǎn)只包含點(diǎn)的三維坐標(biāo)值，而沒有明確給出其對應(yīng)的幾何拓?fù)湫畔?，因此一般需要根?jù)空間點(diǎn)的鄰域關(guān)系估算點(diǎn)對應(yīng)的拓?fù)潢P(guān)系[5]，從而估算點(diǎn)對應(yīng)的幾何信息（如數(shù)據(jù)點(diǎn)單位法向量、微切平面、曲率大小和鄰接關(guān)系）。

通常，計算某點(diǎn)的k個最近鄰域的方法是求出候選點(diǎn)與其余n-1個點(diǎn)的歐氏距離，并按從小到大的順序排列，前面的k個點(diǎn)即為候選點(diǎn)的k最近鄰域。這種方法很直觀，然而對于海量的點(diǎn)云數(shù)據(jù)而言，采用這種方法相當(dāng)耗時，效率十分低下。本文通過對點(diǎn)云數(shù)據(jù)建立kd-tree索引，進(jìn)而利用kd-tree進(jìn)行點(diǎn)云鄰域搜索[6]，算法如下：

假設(shè)kd-tree的結(jié)點(diǎn)為i，每一個結(jié)點(diǎn)都對應(yīng)一個區(qū)域（根結(jié)點(diǎn)對應(yīng)整個點(diǎn)區(qū)域），那么結(jié)點(diǎn)i所對應(yīng)的區(qū)域為Reg（i）；R表示所要查找的區(qū)域范圍。范圍查詢的函數(shù)Search（i，R）的算法描述如下：

①首先i=root，即表示從根結(jié)點(diǎn)開始搜索；

②如果i是葉子結(jié)點(diǎn)，那么返回該葉子結(jié)點(diǎn)中處于R中的點(diǎn)；

③如果R包含Reg（i），那么返回v的所有子樹結(jié)點(diǎn)；

④否則，如果Reg（lefi（i））和R相交，那么search（left （i），R）；如果Reg（right（i））和R相交，那么seareh（righr（i），尺）。

KD 樹是把整個空間劃分為特定的幾個部分，然后在特定空間的部分內(nèi)可以進(jìn)行相關(guān)搜索操作。搜索的核心在于找到實(shí)例點(diǎn)的鄰居，關(guān)于搜索主要有兩種搜索模式[7]：范圍搜索和最近鄰搜索。

2.1 范圍搜索

范圍搜索就是利用與實(shí)例點(diǎn)的空間距離作為判定標(biāo)準(zhǔn)，來尋找滿足條件的點(diǎn)作為鄰近點(diǎn)，因為特征空間中兩個實(shí)例點(diǎn)的距離和反應(yīng)出兩個實(shí)例點(diǎn)之間的相似性程度。K近鄰模型的特征空間一般是n維實(shí)數(shù)向量空間，使用的距離一般使用歐式距離。三維激光掃描儀掃描得到的墻角點(diǎn)云比較復(fù)雜，利用kd-tree索引管理技術(shù)可以方便的搜索出任意點(diǎn)的鄰近點(diǎn)，從而快速建立起點(diǎn)云的拓?fù)潢P(guān)系，在搜索中我們可以采取基于點(diǎn)數(shù)以及基于距離（即范圍）來快速搜索鄰近點(diǎn)。如圖2（a）所示。

2.2 最近鄰搜索

最鄰近搜索就是給定查詢點(diǎn)及正整數(shù)K，從數(shù)據(jù)集中找到距離查詢點(diǎn)最近的K個數(shù)據(jù)點(diǎn)。與范圍搜索不同，K值只要大于1就一定可以找出對應(yīng)的鄰近點(diǎn)，而范圍搜索如果設(shè)置的距離閾值可能會使得點(diǎn)云中比較稀的點(diǎn)沒有滿足條件的鄰近點(diǎn)。如圖2（b）所示。

3 實(shí)例分析

現(xiàn)采用kd-tree建立散亂點(diǎn)云的索引技術(shù)，并快速建立散亂點(diǎn)云的拓?fù)潢P(guān)系。利用三維激光掃描儀可掃描得到的球標(biāo)靶點(diǎn)云，通過對該點(diǎn)云建立kd-tree索引，可以快速獲得該點(diǎn)云的拓?fù)潢P(guān)系。如圖3所示為利用最鄰近8點(diǎn)搜索得到的點(diǎn)云拓?fù)渚W(wǎng)結(jié)構(gòu)，原始點(diǎn)云的點(diǎn)數(shù)為35743，利用kd-trees索引來建立其拓?fù)潢P(guān)系所用的時間是3.8s。利用此方法獲得點(diǎn)云的拓?fù)潢P(guān)系相比利用貪婪三角化獲得拓?fù)潢P(guān)系更加高效。

最鄰近8點(diǎn)搜索

4 總結(jié)

激光雷達(dá)技術(shù)在快速、精確獲取空間目標(biāo)的幾何數(shù)據(jù)方面已取得了突破性進(jìn)展，與此同時也給海量雷達(dá)數(shù)據(jù)的處理效率帶來了挑戰(zhàn)。本文針對激光雷達(dá)系統(tǒng)所獲取的點(diǎn)云數(shù)據(jù)在管理與檢索，提出了基于kd-tree的點(diǎn)云管理方案。利用三維激光點(diǎn)云數(shù)據(jù)進(jìn)行實(shí)驗并利用編程實(shí)現(xiàn)，結(jié)果表明通過對散亂點(diǎn)云建立kd-tree索引可以快速建立建立點(diǎn)云拓?fù)潢P(guān)系，從而方便了對點(diǎn)云的后處理。

【參考文獻(xiàn)】

[1]張毅.地面三維激光掃描點(diǎn)云數(shù)據(jù)處理方法研究[D].武漢：武漢大學(xué)，2008.

[2]減克.地面激光雷達(dá)應(yīng)用處理關(guān)鍵技術(shù)研究[D].北京：首都師范大學(xué)，2007.

[3]劉經(jīng)南，張小紅.激光掃描測高技術(shù)的發(fā)展與現(xiàn)狀[J].武漢大學(xué)學(xué)報·信息科學(xué)版，2003，28（2）：132-137.

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

[5]PIEGL L A. TILLER W. Algorithm for Finding All K Nearest Neighbors[J]. Computer-Aided Design，2002，34（2）：167-172.

[6]劉立強(qiáng).散亂點(diǎn)云數(shù)據(jù)處理相關(guān)算法的研究[D].西北大學(xué)，2010.

[7]劉艷豐.基于 kd-tree 的點(diǎn)云數(shù)據(jù)空間管理理論與方法[D].長沙：中南大學(xué)， 2009.

[責(zé)任編輯：曹明明]