一種樹狀結構的點云數據混合索引方法

張大鵬 汪軍林

?

一種樹狀結構的點云數據混合索引方法

張大鵬 汪軍林

（河南師范大學新聯學院 河南鄭州 450000）

為了提高點云數據的索引效率，本文基于KD樹和八叉樹的索引模型，提出一種新的點云數據的索引的方法，實驗證明這種混合索引的方式能夠提高點云數據索引的效率。

樹狀結構；混合索引；點云數據

點云數據索引是點云數據處理中的一個重要的環節，對于大量的三維點云數據信息來說,合理的空間索引結構方式可以高效的實現海量三維點云數據信息的存儲和管理。空間索引結構方式的好壞直接影響地理信息系統和空間數據庫工作效率，空間索引的結構方式的研究和開發影響了整個空間數據庫和地理信息系統領域的進展[1]。目前，數據檢索問題的解決除了靠計算機提供商在硬件上生產高速處理器和大容量的存儲設備外，還需在算法結構上進行優化，對三維點云數據進行高效的組織和管理，研究和開發新的數據組織和索引結構方式來適應更加復雜的空間操作。

本文提出一種基于KD樹和八叉樹的混合索引模型，并通過一處礦山點云數據進行實驗，證明這種混合索引模型對點云數據的索引效率的改善。

1 KD樹空間索引模型

KD書是一種適合管理點云數據的索引方式[2]，KD樹主要應用于多維點數據和多屬性段數據的檢索。KD樹是一種從二叉類搜索結構推廣到多維檢索樹的結構方式，KD樹中的K為數據的維數。與二叉搜索樹狀結構所不同的是，KD樹的每個節點表示K維空間中的一個點，每一層都根據本層次的分辨器和相對應的對象得出分支決策。KD樹具體的劃分方式是，最頂層節點按照由分辨器所決定的一個維度對數據進行劃分，第二層的分辨器所決定的一個維度來劃分，由此下去在各個維之間不斷的進行劃分。直到該節點中的點數少于閾值，劃分結束。

KD樹每一個節點都是一個K維點的二叉樹結構。在KD樹中所有的非葉子節點都可以看成許多超平面將數據空間劃分為左右或上下兩個部分。在這個超平面中所有位于左節點的數據信息都屬于左子樹，所有位于右節點的數據信息都屬于右子樹。超平面的構建可以采取下面方式進行構建：每一個節點都與K維中垂直于超平面的一維有著直接關系。假設以Y軸進行劃分，所有指定的比Y值小的數值都位于左子樹當中，所有指定比Y值大的數值都位于右子樹當中。超平面就可以根據此值來確定，法矢是Y軸方向的單位矢量，圖1展現了三維數據空間中KD樹的剖分結構圖，首先紅色線段將數據空間劃分為兩個空間部分，而后綠色線段將分割后的兩個空間劃分為四個空間部分，最后藍色線段將這四個空間又分割為八個空間部分，形成最后8個子空間部分。

2 八叉樹空間分割

八叉樹是四插樹在三維空間上的擴展[3]，可以用來對三維點云數據進行組織并建立空間索引。每一個八叉樹節點都可以代表了一個空間長方體的體積，在具體操作實現的時候，讓立方體與坐標軸相互平行。每個八叉樹都有8個子節點，如果一個節點沒有孩子就意味無需對該節點進行進一步的分割。對三維點云數據進行組織的時候，需要定義一個立方體的停止規則。最小點云個數和遞歸的最大深度都可以作為分割停止的規則。如果一個葉子節點其中的點云個數小于某閾值或者超過了最大遞歸深度則停止遞歸。所有的三維點云數據都存放在葉子節點當中，通過深度和點云數目的限制可以得到一個平衡的八叉樹，在這個八叉樹中所有的葉子節點都處在同一層次上，且其它的節點都有8個子節點，對于那些空的節點不需要進行分割，所以只對那些包含有三維點云數據的空間創建節點。由于三維點云數據一般都是采集目標物體表面的數據。利用八叉樹的數據組織結構方法適合對大量三維點云數據進行存儲。圖2表示了八叉樹的結構方式。

3 混合索引的建立

八叉樹的結構是將點云數據所占據的空間的外包六面體按照格網的進行分割，將點云數據通過遞歸分割的方式進行層層的深入分割，點云數據最終都將歸屬于葉子節點，中間節點僅僅是作為檢索點云數據的通道，采用這種索引方式易于實現，可操作性強。當點云數據量比較大，分布不均勾時，這樣分配得到葉子節點的點云的數量會很大，在葉子節點中對點云數據進行檢索的效率會大大降低。為了提高點云數據檢索的效率，需要對葉子節點的點云數據進行重新組織。將葉子節點中的點云數據采用KD樹的方式進行組織，由于KD樹已進行點云鄰域的空間數據進行組織，所以會大大的提高檢索的效率，在進行點云數據的檢索時，先確定點云數據所在的葉子格網，然后再對該葉子節點進行KD樹的檢索，利用這種混合的方法可以避免單一結構帶來的弊端。

4 算法實現

基于八叉樹與KD樹的混合索引進行三維點云數據索引的構建，具體的構建算法如下：

1．根據所輸入的三維點云數據集合，計算其最小外包圍盒，設定改進八叉樹葉子節點的大小和分割的深度deep。

2．通過上一步所得到的參數，對八叉樹進行遞歸分割并存儲相關節點的信息。

3．對于分割完成的八叉樹的葉子節點，用KD樹方法進行二次剖分，節點分別存儲索引信息和節點的坐標，并將KD樹指針的地址保存在八叉樹的葉子節點之中。

4．對三維點云數據進行檢索時，首先定位到其所在八叉樹的葉子節點當中，然后在進行與該葉子節點唯一確定的KD樹當中進行二次檢索。需要注意的是，在進行點云鄰域搜索時，若該葉子節點點的個數不滿足條件數，那么需要在其鄰域的8個節點中進行搜索。

利用復合嵌套的組織索引結構，可以平衡各個節點中的點云數據量，在對點云數據進行檢索時可以取得較好的查詢效率。

5 實驗分析

本實驗數據是TrimbleGX200激光掃描系統采集的一座礦山。為了更便利區分不同索引方式的效率，選取同一目標物，對點云數據分別抽取25%、50%、75%后得到1178902 、785935、369280個點的數據，抽稀后得到的點云如圖3所示。

（a）100%的點云數據 （b）75%的點云數據

（c）50%的點云數據 （d）25%的點云數據

圖1 礦山三維掃描點云抽稀結果

分別利用改進的八叉樹、KD樹以改進八叉樹與KD樹的混合索引方式對其進行組織。運行環境為XP系統，用于數據處理實驗的計算機CPU型號為Pentium (R)Dual-Core E5200 2.5GHz雙核。其構建時間統計如表3.2。根據表3.2中的數據繪制圖3.17。

表1 不同索引方式的構建時間

圖2 三種組織索引方式的耗時過程線

對同一礦山點云數據，按照25%、50%、75%抽取后的點云數據進行實驗比較，通過對KD樹、改進八叉樹以及改進八叉樹與KD混合索引方式的實驗驗證及分析發現，雖然改進八叉樹能夠在計算機內存消耗方面得到較大的改善，但是在對點云數據進行檢索時，最小分割粒度（葉節點大小）影響了其檢索的效率，葉節點越大，其包含的點的數目就越多，由于點數據在葉子當中是以線性的方式進行存儲的，所以對點數據的定位和查詢時間很長。若分割的粒度太小，那么八叉樹的深度就會增加。KD樹重建了點云數據之間的鄰域關系，所以在查詢效率上得到了較大的改善，構建KD樹的鄰域關系需要消耗大量的時間，所以對所有點云數據都進行KD樹的構建，顯然是不現實的。利用改進八叉樹與KD樹的混合索引的結構方式，在不失點云數據整個空間結構的情況下，對葉節點的點進行KD樹鄰域的構建，可以在處理時間方面取得不錯的效果。實驗證明混合索引方式的在時間的消耗上花費更少。

6 結語

本文在KD樹和八叉樹的基礎之上，利用混合索引的方式進行點云數據的索引。

1）本文驗證了混合索引方式在點云索引過程中的效率,為點云索引提供了一種思路。

2）本文為點云數據索引提供了一個新的思考方向。如何針對不同類型的點云數據使用更加有效的索引方式可以進一步研究。

[1] Levoy M.The digital Michelangelo project.In:3DIM99,1999.2-11.

[2]劉艷豐. 基于kd-tree的點云數據空間管理理論與方法[D].長沙：中南大學，2009.

[3]惠文華，郭新城.3維GIS中的八叉樹空間索引研究.測繪通報，2003（1）：25~27.

[4]路明月，何永健.三維海量點云數據的組織與索引方法.地球信息科學，2008，10(2)：190-194

[5]許鵬.海量三維點云數據的組織與可視化研究[D].南京：南京師范大學，2013.

G322

B

1007-6344（2017）03-0338-01

張大鵬， 1988年7月 ， 男，漢，河南 衛輝，碩士研究生，助教，研究方向為三維激光掃描技術。

汪軍林，1989年3月，男，漢，河南 項城，碩士研究生，助教，研究方向為精密工程測量