一種基于線性KD樹的點云數據組織方法

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

(1. 武漢大學遙感信息工程學院，湖北 武漢 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樹的點云數據組織方法

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

(1. 武漢大學遙感信息工程學院，湖北 武漢 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樹索引對大規模點云數據進行組織和管理時，指針的存儲往往耗費大量的內存空間。本文結合線性索引的編碼思想，提出了一種線性KD樹索引的構建和查找方法，存儲點云時可以充分利用內存空間，通過自然數編碼表示結點間的關系，并給出了線性KD樹的構建和鄰域查找方法。最后通過與開源最臨近搜索庫ANN庫進行對比試驗，證明本文的線性KD樹索引可以明顯減少點云組織時的內存消耗，并與基于指針的ANN庫具有相近的臨近查找效率。

關鍵詞：點云索引；點云組織；鄰域查找；KD樹；線性索引

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

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

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

一、線性KD樹索引的構建

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

1. 線性KD樹的編碼規則

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

1) 根結點Pr的編碼為1。

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

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

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

2. 線性KD樹的構建方法

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

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

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

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

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

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

PointPartition(start, end)

while(start

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

swap(q[start], q[end]) ∥交換結點

end if

start++

end--

end while

在劃分交換算法執行完畢后，令QI[index]=Q[median]，記錄當前層次下的根結點，并可以對劃分后的兩個區間繼續執行劃分交換。

3) 遞歸構樹。在每一層的劃分交換算法基礎上，通過遞歸的方法，為KD樹的每一層尋找對應結點，計算編碼值，并為下一層的劃分交換算法提供所屬點云序列，最終構成一個完整的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) ∥遞歸調用

end if

if(end>median)

start=median+1

end=end

index=2*index+1

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

end if

圖2　線性KD樹的編碼和構建過程

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

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

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

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

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

圖3　線性KD樹的構建方式

3. 線性KD樹的鄰域搜索

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

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

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

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

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

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

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

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

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

二、試驗與分析

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

圖6　點云試驗數據

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

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

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

圖7　鄰域查找時間對比

三、結束語

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

參考文獻：

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

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

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

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

[10]肖樂斌, 龔建華, 謝傳節. 線性四叉樹和線性八叉樹鄰域尋找的一種新算法[J].測繪學報,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樹的點云數據組織方法[J].測繪通報，2016(1)：23-27.DOI:10.13474/j.cnki.11-2246.2016.0006.

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

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

收稿日期：2014-11-17

中圖分類號：P237

文獻標識碼：B

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