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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) 劃分交換。在KD樹當(dāng)前層次對應(yīng)的結(jié)點序列Q(i,j)中，取中間點作為當(dāng)前層次的根結(jié)點，令其序號為median，并根據(jù)其父節(jié)點的編碼計算當(dāng)前結(jié)點的編碼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é)點

end if

start++

end--

end while

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

3) 遞歸構(gòu)樹。在每一層的劃分交換算法基礎(chǔ)上，通過遞歸的方法，為KD樹的每一層尋找對應(yīng)結(jié)點，計算編碼值，并為下一層的劃分交換算法提供所屬點云序列，最終構(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é)點序列，通過一個結(jié)點的編碼可以在序列中快速查找其對應(yīng)的父節(jié)點和子結(jié)點。

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

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

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

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

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

3. 線性KD樹的鄰域搜索

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

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

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

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

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

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

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

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

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

二、試驗與分析

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

圖6　點云試驗數(shù)據(jù)

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

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

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

圖7　鄰域查找時間對比

三、結(jié)束語

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

參考文獻：

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

[2]賴祖龍, 萬幼川,申邵洪,等.基于Hilbert排列碼與R樹的海量LIDAR點云索引[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樹散亂點云數(shù)據(jù)的Guass平均曲率精簡算法[J]. 測繪通報, 2013(S1): 44-46.

[8]張毅, 劉旭敏, 隋穎, 等.基于K-近鄰點云去噪算法的研究與改進[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樹的點云數(shù)據(jù)組織方法[J].測繪通報，2016(1)：23-27.DOI:10.13474/j.cnki.11-2246.2016.0006.

作者簡介：陳茂霖(1991—)，男，博士生，主要研究方向為地面激光數(shù)據(jù)處理。E-mail:maolinchen@qq.com

基金項目：國家863計劃(2013AA122104)；高等學(xué)校博士學(xué)科點專項科研基金(20130141130003)

收稿日期：2014-11-17

中圖分類號：P237

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

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