一種基于線性KD樹的點(diǎn)云數(shù)據(jù)組織方法

陳茂霖，萬幼川，田思憶，秦家鑫，盧維欣

(1. 武漢大學(xué)遙感信息工程學(xué)院，湖北 武漢 430079； 2. 武漢市測繪研究院，湖北 武漢 430022)

A Method of Organizing Point Clouds Based on Linear KD Tree

CHEN Maolin，WAN Youchuan，TIAN Siyi，QIN Jiaxin，LU Weixin

?

一種基于線性KD樹的點(diǎn)云數(shù)據(jù)組織方法

陳茂霖1，萬幼川1，田思憶2，秦家鑫1，盧維欣1

(1. 武漢大學(xué)遙感信息工程學(xué)院，湖北 武漢 430079； 2. 武漢市測繪研究院，湖北 武漢 430022)

A Method of Organizing Point Clouds Based on Linear KD Tree

CHEN Maolin，WAN Youchuan，TIAN Siyi，QIN Jiaxin，LU Weixin

摘要：常規(guī)KD樹索引對大規(guī)模點(diǎn)云數(shù)據(jù)進(jìn)行組織和管理時，指針的存儲往往耗費(fèi)大量的內(nèi)存空間。本文結(jié)合線性索引的編碼思想，提出了一種線性KD樹索引的構(gòu)建和查找方法，存儲點(diǎn)云時可以充分利用內(nèi)存空間，通過自然數(shù)編碼表示結(jié)點(diǎn)間的關(guān)系，并給出了線性KD樹的構(gòu)建和鄰域查找方法。最后通過與開源最臨近搜索庫ANN庫進(jìn)行對比試驗(yàn)，證明本文的線性KD樹索引可以明顯減少點(diǎn)云組織時的內(nèi)存消耗，并與基于指針的ANN庫具有相近的臨近查找效率。

關(guān)鍵詞：點(diǎn)云索引；點(diǎn)云組織；鄰域查找；KD樹；線性索引

隨著激光掃描技術(shù)的發(fā)展，大規(guī)模的點(diǎn)云數(shù)據(jù)不斷產(chǎn)生，點(diǎn)云數(shù)據(jù)的組織和管理已經(jīng)成為后續(xù)處理和應(yīng)用中的瓶頸[1]。點(diǎn)云數(shù)據(jù)的后處理往往依賴于點(diǎn)云的索引技術(shù)[2]，一個高效的點(diǎn)云索引不僅可以提高點(diǎn)云的處理效率，還可以節(jié)省計(jì)算機(jī)的存儲空間。

KD樹索引是點(diǎn)云數(shù)據(jù)處理中常用的一種索引方式，由Bentley在1975年提出[3]，是二叉查找樹在多維空間的擴(kuò)展，在點(diǎn)云數(shù)據(jù)處理中具有廣泛的應(yīng)用。在KD樹被提出后，有大量的論文對KD樹索引的理論和應(yīng)用進(jìn)行了研究和改進(jìn)。Nene提出了KD樹在高維搜索中高效應(yīng)用的方法[4]；Greenspan通過改進(jìn)KD樹索引來提高ICP算法的效率[5]；Horn等通過GPU對KD樹索引進(jìn)行加速[6]；此外KD樹還被應(yīng)用在點(diǎn)云簡化[7]、去噪[8]等不同的應(yīng)用中。在多數(shù)研究中，其關(guān)注點(diǎn)主要集中在檢索效率、索引維度、索引應(yīng)用等方面，KD樹結(jié)點(diǎn)間的關(guān)系主要通過指針記錄，在上千萬甚至上億的點(diǎn)云數(shù)據(jù)量中，傳統(tǒng)KD樹索引中的指針維護(hù)往往要占據(jù)大量的內(nèi)存，造成內(nèi)存空間的浪費(fèi)甚至無法構(gòu)樹等問題。

本文將線性索引的編碼思想與KD樹索引結(jié)合，提出了一種線性KD樹索引的構(gòu)建方法。該方通過編碼的方式表示KD樹結(jié)點(diǎn)間的關(guān)系，避免了指針的使用，解決了傳統(tǒng)KD樹在存儲點(diǎn)云時需要維護(hù)大量指針而造成的內(nèi)存浪費(fèi)問題。同時，索引中的結(jié)點(diǎn)關(guān)系可以通過文件方式存儲，點(diǎn)云構(gòu)建索引并存儲為文件后，可以按照索引順序從文件中讀入而無須再次構(gòu)樹，進(jìn)而提高了點(diǎn)云讀入和處理的效率。

一、線性KD樹索引的構(gòu)建

在數(shù)字圖像處理和地理信息系統(tǒng)等領(lǐng)域，人們一般采用線性四叉樹取代常規(guī)四叉樹方法[9]，通過一定的編碼方式對數(shù)據(jù)進(jìn)行劃分，比普通四叉樹大大節(jié)省了存儲空間,且蘊(yùn)含有層次特性[10]。受線性索引思想的啟發(fā)，本文將線性索引編碼的方式應(yīng)用于KD樹結(jié)點(diǎn)關(guān)系構(gòu)建過程中，使用自然數(shù)編碼的方式表示KD樹中相鄰結(jié)點(diǎn)間的關(guān)系，從而減少了索引的內(nèi)存空間占用。

1. 線性KD樹的編碼規(guī)則

本文提出的線性KD樹將根節(jié)點(diǎn)Pr的編碼I(P)標(biāo)記為1，同時放在結(jié)點(diǎn)序列的第1個位置，Pr的兩個子結(jié)點(diǎn)的編碼分別為2和3，分別放在結(jié)點(diǎn)序列的第2和第3個位置。對于一個數(shù)量為M的節(jié)點(diǎn)序列，線性KD樹的編碼規(guī)則如下：

1) 根結(jié)點(diǎn)Pr的編碼為1。

2) 對于KD樹中不為根結(jié)點(diǎn)的任意結(jié)點(diǎn)Pi，令其編碼為I(Pi)，則其兩個子結(jié)點(diǎn)的編碼分別為2×I(Pi)和2×I(Pi)+1，其父節(jié)點(diǎn)的編碼為[(I(Pi)/2),]為向下取整，結(jié)點(diǎn)Pi在結(jié)點(diǎn)序列的第I(Pi)個位置。若2×I(Pi)>M，則該結(jié)點(diǎn)沒有子結(jié)點(diǎn)，為葉子結(jié)點(diǎn)。

圖1所示為常規(guī)KD樹與線性KD樹結(jié)點(diǎn)關(guān)系的對比。常規(guī)KD樹利用大量指針來表示結(jié)點(diǎn)之間的關(guān)系，存儲空間的利用率低；而線性KD樹通過結(jié)點(diǎn)在序列中的位置編碼，描述了結(jié)點(diǎn)之間的關(guān)系，節(jié)省了大量的內(nèi)存空間。同時，由于編碼與結(jié)點(diǎn)在內(nèi)存序列中的位置相對應(yīng)，每個結(jié)點(diǎn)中不需要存儲其對應(yīng)的編碼值，進(jìn)一步提高了存儲空間的利用效率。

圖1　常規(guī)KD樹與線性KD樹的組織方式對比

2. 線性KD樹的構(gòu)建方法

本文提出的線性KD樹不僅可以通過散亂的點(diǎn)云序列進(jìn)行構(gòu)建，對于按照編碼順序存儲的點(diǎn)云文件，還可以在順序讀取點(diǎn)云時直接從文件中生成KD樹索引，提高了點(diǎn)云數(shù)據(jù)的組織和管理效率。

(1) 散亂點(diǎn)云序列的構(gòu)樹方法

面向散亂點(diǎn)云序列的線性KD樹構(gòu)建方法基于快速排序算法中的劃分交換思想[11]，通過不斷交換和迭代來尋找每層的根結(jié)點(diǎn)，最終構(gòu)建出完整的KD樹。

令Q(1，M)表示大小為M的無序點(diǎn)云序列，Q(i,j)表示整體點(diǎn)云序列中從i到j(luò)的一段子序列，q[i][k]表示整體點(diǎn)云序列中第i個結(jié)點(diǎn)的第k個坐標(biāo)值，k取值為0、1和2時分別對應(yīng)x、y和z坐標(biāo)，QI(i,j)則表示平衡后的有序多點(diǎn)云序列。具體構(gòu)建方法如下：

1) 空間分辨器的選擇。在KD樹的每一層，選擇對應(yīng)空間中最長的坐標(biāo)軸對應(yīng)的坐標(biāo)作為KD樹在該層的分辨器(discriminator)。這樣可以最大限度上保證空間的均衡劃分。

2) 劃分交換。在KD樹當(dāng)前層次對應(yīng)的結(jié)點(diǎn)序列Q(i,j)中，取中間點(diǎn)作為當(dāng)前層次的根結(jié)點(diǎn)，令其序號為median，并根據(jù)其父節(jié)點(diǎn)的編碼計(jì)算當(dāng)前結(jié)點(diǎn)的編碼index。令d為當(dāng)前最長數(shù)據(jù)軸所對應(yīng)的分辨器，取i和j分別為start和end。執(zhí)行劃分交換算法：

PointPartition(start, end)

while(start

if(q[start][d]q[median][d])

swap(q[start], q[end]) ∥交換結(jié)點(diǎn)

end if

start++

end--

end while

在劃分交換算法執(zhí)行完畢后，令QI[index]=Q[median]，記錄當(dāng)前層次下的根結(jié)點(diǎn)，并可以對劃分后的兩個區(qū)間繼續(xù)執(zhí)行劃分交換。

3) 遞歸構(gòu)樹。在每一層的劃分交換算法基礎(chǔ)上，通過遞歸的方法，為KD樹的每一層尋找對應(yīng)結(jié)點(diǎn)，計(jì)算編碼值，并為下一層的劃分交換算法提供所屬點(diǎn)云序列，最終構(gòu)成一個完整的KD樹，如圖2所示。具體算法如下：

PointSort (start, end, index)

median=PointPartition (start, end)

QI[index]=Q[median]

if(start

start=start

end=median-1

index=2*index

PointSort (start, end, index) ∥遞歸調(diào)用

end if

if(end>median)

start=median+1

end=end

index=2*index+1

PointSort (start, end, index) ∥遞歸調(diào)用

end if

圖2　線性KD樹的編碼和構(gòu)建過程

在迭代算法結(jié)束之后，QI(1，M)便構(gòu)成了線性KD樹的結(jié)點(diǎn)序列，通過一個結(jié)點(diǎn)的編碼可以在序列中快速查找其對應(yīng)的父節(jié)點(diǎn)和子結(jié)點(diǎn)。

(2) 基于點(diǎn)云文件的構(gòu)樹方法

由于線性KD樹每個結(jié)點(diǎn)的編碼與其在內(nèi)存序列中的位置保持一致，因此線性KD樹中的結(jié)點(diǎn)按照編碼順序保存為點(diǎn)云文件后，按照存儲順序再次讀入時無須執(zhí)行構(gòu)樹算法便可以直接構(gòu)建索引，明顯增加了點(diǎn)云的組織和管理效率，其存儲格式見表1。

表1　線性KD樹的文件存儲格式

綜合以上兩種方法，本文提出的線性KD樹索引可以基于無序點(diǎn)云序列及編碼后的點(diǎn)云文件兩種方式靈活構(gòu)建，如圖3所示，提高了點(diǎn)云數(shù)據(jù)的組織和管理效率。

圖3　線性KD樹的構(gòu)建方式

3. 線性KD樹的鄰域搜索

多維空間中的臨近搜索一般根據(jù)搜索半徑ε將查找范圍限制在一個由多維面構(gòu)成的空間中。如三維空間的查找是限制在一個邊長為2ε的正方體中，然后尋找距離中心點(diǎn)小于ε的點(diǎn)，如圖4所示。

圖4　三維空間中的臨近查找

本文中的線性KD樹也基于這種思想進(jìn)行鄰域查找，令r為鄰域半徑，進(jìn)行搜索的中心點(diǎn)為PCenter，則鄰域搜索方法如下：

1) 確定搜索起點(diǎn)的結(jié)點(diǎn)編碼index，一般取index為1。

2) 若當(dāng)前待搜索結(jié)點(diǎn)QI[index]為葉子結(jié)點(diǎn)，進(jìn)入步驟4)；若QI[index]不為葉子結(jié)點(diǎn)，則進(jìn)入步驟3)。

3) 計(jì)算QI[index]對應(yīng)的分辨器d，進(jìn)而計(jì)算PCenter到當(dāng)前分割平面的距離dist。若dist大于搜索半徑r，表明分割平面兩側(cè)的空間中都可能存在鄰域中的點(diǎn)，取當(dāng)前待搜索的結(jié)點(diǎn)編碼分別為2×index和2×index+1，分別執(zhí)行步驟2)；若dist小于搜索半徑r，表明鄰域中的點(diǎn)只存在于分割平面的一側(cè)，通過比較PCenter[d]與QI[index][d] 確定待搜索結(jié)點(diǎn)的編碼，PCenter[d]小于QI[index][d]時，待搜索結(jié)點(diǎn)的編碼取為2×index，否則取為2×index+1，執(zhí)行步驟2)。

4) 若QI[index]與中心點(diǎn)PCenter的距離小于r，將當(dāng)前搜索結(jié)點(diǎn)QI[index]加入鄰域集合，并將集合按照與中心點(diǎn)PCenter的距離從小到大進(jìn)行排序。在沒有可搜索結(jié)點(diǎn)后，結(jié)束整個鄰域搜索算法。

從整體上看，線性KD樹中的鄰域查找利用上下層結(jié)點(diǎn)編碼間的關(guān)系進(jìn)行遞歸查找，其查找順序與結(jié)點(diǎn)編碼保持一致，由于將查找范圍限制在一個邊長為2r的正方體空間內(nèi)，因此實(shí)際遍歷結(jié)點(diǎn)遠(yuǎn)少于KD樹中的結(jié)點(diǎn)數(shù)目。圖5所示為一個線性KD樹的遍歷查找過程，黑色結(jié)點(diǎn)為中心點(diǎn)，1、3、6、13的深灰色結(jié)點(diǎn)為落在鄰域中的結(jié)點(diǎn)，2和7為遍歷但沒有落在鄰域中的結(jié)點(diǎn)，白色結(jié)點(diǎn)是落在正方體空間之外而未遍歷的結(jié)點(diǎn)，實(shí)際遍歷結(jié)點(diǎn)只占總結(jié)點(diǎn)數(shù)目的一半，大大提高了鄰域搜索的效率。

圖5　線性KD樹臨近查找的過程

二、試驗(yàn)與分析

為了驗(yàn)證線性KD樹(linear KD-Tree,LKD)在點(diǎn)云管理、查找等方面的性能，本文將線性KD樹索引同最臨近搜索開源庫ANN庫[12](approximate nearestn neighbor searching)在不同的三維點(diǎn)云數(shù)據(jù)中進(jìn)行了對比試驗(yàn)。試驗(yàn)數(shù)據(jù)如圖6所示，其中圖6(a)為機(jī)載點(diǎn)云數(shù)據(jù)，包含1 424 805個點(diǎn);圖6(b)為新疆某地野外的地面激光點(diǎn)云數(shù)據(jù)，包含6 079 124個點(diǎn)；圖6(c)為天津民園雕塑點(diǎn)云數(shù)據(jù)，包含9 092 351個點(diǎn);圖6(d)為武漢東湖石刻點(diǎn)云數(shù)據(jù)，包含16 354 184個點(diǎn)。試驗(yàn)使用的計(jì)算機(jī)配置為Core(TM) i5-4460處理器，8 GB內(nèi)存。

圖6　點(diǎn)云試驗(yàn)數(shù)據(jù)

表2為兩種索引在不同試驗(yàn)數(shù)據(jù)下的構(gòu)建效率與內(nèi)存占用情況的試驗(yàn)結(jié)果。試驗(yàn)結(jié)果表明，由于避免了指針的使用，線性KD樹對內(nèi)存的消耗僅為ANN庫的1/3，顯著降低了點(diǎn)云存儲對計(jì)算機(jī)內(nèi)存的占用。同時，由于在構(gòu)樹過程中，ANN庫需要動態(tài)開辟大量超出實(shí)際存儲量的臨時內(nèi)存，在對數(shù)據(jù)量為1600萬的點(diǎn)云進(jìn)行構(gòu)樹時，產(chǎn)生了內(nèi)存不足的問題而導(dǎo)致構(gòu)建失敗；而線性KD樹的構(gòu)建過程主要在點(diǎn)云序列內(nèi)部進(jìn)行劃分交換，對于計(jì)算機(jī)內(nèi)存的利用更加合理，可以處理數(shù)據(jù)量更大的點(diǎn)云數(shù)據(jù)。此外，從索引構(gòu)建的試驗(yàn)結(jié)果來看，本文提出的線性KD樹索引構(gòu)建效率約為ANN庫的2.5倍，且對于上千萬的點(diǎn)云可以在10 s之內(nèi)完成構(gòu)建，具有較好的索引構(gòu)建效率。

表2　線性KD樹與ANN庫的對比

為了測試線性KD樹的鄰域查找效率，使用線性KD樹和ANN庫對圖6(c)中的點(diǎn)云數(shù)據(jù)進(jìn)行試驗(yàn)，分別計(jì)算兩種索引在不同鄰域半徑下對點(diǎn)云中所有點(diǎn)進(jìn)行鄰域近查找所需的總時間和每個點(diǎn)進(jìn)行鄰域查找所需的平均時間，試驗(yàn)結(jié)果如圖7所示。其中，試驗(yàn)點(diǎn)云數(shù)據(jù)的密度為4~6 mm，圖7(a)為不同半徑下對所有點(diǎn)執(zhí)行一遍最臨近查找所需要的總時間；圖7(b)為不同半徑下對每個點(diǎn)進(jìn)行查找所需的平均時間，所有的數(shù)據(jù)均使用5次相同操作的平均數(shù)據(jù)。從試驗(yàn)結(jié)果可知，本文提出的線性KD樹索引在三維空間中的鄰域查找效率與基于指針的ANN庫十分接近，在千萬級的點(diǎn)云數(shù)據(jù)中，每個點(diǎn)所需的平均查找時間保持在10-5s的數(shù)量級上，可以實(shí)現(xiàn)高效的點(diǎn)云鄰域查找。

圖7　鄰域查找時間對比

三、結(jié)束語

隨著生產(chǎn)中獲取的點(diǎn)云數(shù)據(jù)規(guī)模不斷增大，如何合理利用計(jì)算機(jī)內(nèi)存對點(diǎn)云進(jìn)行組織成為一個不容忽視的問題。本文通過引入線性索引的編碼思想改進(jìn)傳統(tǒng)基于指針的KD樹索引，提出了線性KD樹索引的構(gòu)建和鄰域查找方法；通過試驗(yàn)證明線性KD樹索引的內(nèi)存占用約為基于指針的開源ANN庫的1/3，并且具有與ANN庫幾乎相同的查找效率，對于點(diǎn)云數(shù)據(jù)的組織和空間查找提供了高效的索引基礎(chǔ)。本文主要針對三維空間中的點(diǎn)云進(jìn)行了KD樹索引構(gòu)建和查找方法的設(shè)計(jì)，對于高維度數(shù)據(jù)中的索引高效構(gòu)建和查找方法還有待進(jìn)一步的研究。

參考文獻(xiàn)：

[1]楊建思. 一種四叉樹與KD樹結(jié)合的海量機(jī)載LiDAR數(shù)據(jù)組織管理方法[J].武漢大學(xué)學(xué)報(信息科學(xué)版)， 2014，39(8)：918-922.

[2]賴祖龍, 萬幼川,申邵洪,等.基于Hilbert排列碼與R樹的海量LIDAR點(diǎn)云索引[J].測繪科學(xué), 2009, 34(6): 128-130.

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

[4]NENE S A, NAYAR S K. A Simple Algorithm for Nearest Neighbor Search in High Dimensions[J]. IEEE Pattern Analysis and Machine Intelligence, 1997, 19(9): 989-1003.

[5]GREENSPAN M, YURICK M. Approximate KD Tree Search for Efficient ICP[C]∥Proceedings of Fourth International Conference on 3-D Digital Imaging and Modeling. [S.l.]: IEEE, 2003: 442-448.

[6]HORN D R, SUGERMAN J, HOUSTON M, et al. Interactive KD Tree GPU Raytracing[C]∥Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games.[S.l.]: ACM, 2007: 167-174.

[7]蔡志敏, 王晏民, 黃明.基于KD樹散亂點(diǎn)云數(shù)據(jù)的Guass平均曲率精簡算法[J]. 測繪通報, 2013(S1): 44-46.

[8]張毅, 劉旭敏, 隋穎, 等.基于K-近鄰點(diǎn)云去噪算法的研究與改進(jìn)[J].計(jì)算機(jī)應(yīng)用, 2009, 29(4): 1011-1014.

[9]龔健雅.一種基于自然數(shù)的線性四叉樹編碼[J].測繪學(xué)報, 1992, 21(2): 90-99.

[10]肖樂斌, 龔建華, 謝傳節(jié). 線性四叉樹和線性八叉樹鄰域?qū)ふ业囊环N新算法[J].測繪學(xué)報,1998,27(3):195-203.

[11]HOARE C A R.Quicksort[J]. The Computer Journal, 1962, 5(1): 10-16.

[12]ARYA S, MOUNT D M, NETANYAHU N S, et al. An Optimal Algorithm for Approximate Nearest Neighbor Searching Fixed Dimensions[J].Journal of the ACM (JACM), 1998, 45(6): 891-923.

引文格式： 陳茂霖，萬幼川，田思憶，等. 一種基于線性KD樹的點(diǎn)云數(shù)據(jù)組織方法[J].測繪通報，2016(1)：23-27.DOI:10.13474/j.cnki.11-2246.2016.0006.

作者簡介：陳茂霖(1991—)，男，博士生，主要研究方向?yàn)榈孛婕す鈹?shù)據(jù)處理。E-mail:maolinchen@qq.com

基金項(xiàng)目：國家863計(jì)劃(2013AA122104)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20130141130003)

收稿日期：2014-11-17

中圖分類號：P237

文獻(xiàn)標(biāo)識碼：B

文章編號：0494-0911(2016)01-0023-05