一種樹狀結(jié)構(gòu)的點(diǎn)云數(shù)據(jù)混合索引方法

張大鵬 汪軍林

?

一種樹狀結(jié)構(gòu)的點(diǎn)云數(shù)據(jù)混合索引方法

張大鵬 汪軍林

（河南師范大學(xué)新聯(lián)學(xué)院 河南鄭州 450000）

為了提高點(diǎn)云數(shù)據(jù)的索引效率，本文基于KD樹和八叉樹的索引模型，提出一種新的點(diǎn)云數(shù)據(jù)的索引的方法，實(shí)驗(yàn)證明這種混合索引的方式能夠提高點(diǎn)云數(shù)據(jù)索引的效率。

樹狀結(jié)構(gòu)；混合索引；點(diǎn)云數(shù)據(jù)

點(diǎn)云數(shù)據(jù)索引是點(diǎn)云數(shù)據(jù)處理中的一個(gè)重要的環(huán)節(jié)，對(duì)于大量的三維點(diǎn)云數(shù)據(jù)信息來說,合理的空間索引結(jié)構(gòu)方式可以高效的實(shí)現(xiàn)海量三維點(diǎn)云數(shù)據(jù)信息的存儲(chǔ)和管理?？臻g索引結(jié)構(gòu)方式的好壞直接影響地理信息系統(tǒng)和空間數(shù)據(jù)庫工作效率，空間索引的結(jié)構(gòu)方式的研究和開發(fā)影響了整個(gè)空間數(shù)據(jù)庫和地理信息系統(tǒng)領(lǐng)域的進(jìn)展[1]。目前，數(shù)據(jù)檢索問題的解決除了靠計(jì)算機(jī)提供商在硬件上生產(chǎn)高速處理器和大容量的存儲(chǔ)設(shè)備外，還需在算法結(jié)構(gòu)上進(jìn)行優(yōu)化，對(duì)三維點(diǎn)云數(shù)據(jù)進(jìn)行高效的組織和管理，研究和開發(fā)新的數(shù)據(jù)組織和索引結(jié)構(gòu)方式來適應(yīng)更加復(fù)雜的空間操作。

本文提出一種基于KD樹和八叉樹的混合索引模型，并通過一處礦山點(diǎn)云數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，證明這種混合索引模型對(duì)點(diǎn)云數(shù)據(jù)的索引效率的改善。

1 KD樹空間索引模型

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

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

2 八叉樹空間分割

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

3 混合索引的建立

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

4 算法實(shí)現(xiàn)

基于八叉樹與KD樹的混合索引進(jìn)行三維點(diǎn)云數(shù)據(jù)索引的構(gòu)建，具體的構(gòu)建算法如下：

1．根據(jù)所輸入的三維點(diǎn)云數(shù)據(jù)集合，計(jì)算其最小外包圍盒，設(shè)定改進(jìn)八叉樹葉子節(jié)點(diǎn)的大小和分割的深度deep。

2．通過上一步所得到的參數(shù)，對(duì)八叉樹進(jìn)行遞歸分割并存儲(chǔ)相關(guān)節(jié)點(diǎn)的信息。

3．對(duì)于分割完成的八叉樹的葉子節(jié)點(diǎn)，用KD樹方法進(jìn)行二次剖分，節(jié)點(diǎn)分別存儲(chǔ)索引信息和節(jié)點(diǎn)的坐標(biāo)，并將KD樹指針的地址保存在八叉樹的葉子節(jié)點(diǎn)之中。

4．對(duì)三維點(diǎn)云數(shù)據(jù)進(jìn)行檢索時(shí)，首先定位到其所在八叉樹的葉子節(jié)點(diǎn)當(dāng)中，然后在進(jìn)行與該葉子節(jié)點(diǎn)唯一確定的KD樹當(dāng)中進(jìn)行二次檢索。需要注意的是，在進(jìn)行點(diǎn)云鄰域搜索時(shí)，若該葉子節(jié)點(diǎn)點(diǎn)的個(gè)數(shù)不滿足條件數(shù)，那么需要在其鄰域的8個(gè)節(jié)點(diǎn)中進(jìn)行搜索。

利用復(fù)合嵌套的組織索引結(jié)構(gòu)，可以平衡各個(gè)節(jié)點(diǎn)中的點(diǎn)云數(shù)據(jù)量，在對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行檢索時(shí)可以取得較好的查詢效率。

5 實(shí)驗(yàn)分析

本實(shí)驗(yàn)數(shù)據(jù)是TrimbleGX200激光掃描系統(tǒng)采集的一座礦山。為了更便利區(qū)分不同索引方式的效率，選取同一目標(biāo)物，對(duì)點(diǎn)云數(shù)據(jù)分別抽取25%、50%、75%后得到1178902 、785935、369280個(gè)點(diǎn)的數(shù)據(jù)，抽稀后得到的點(diǎn)云如圖3所示。

（a）100%的點(diǎn)云數(shù)據(jù) （b）75%的點(diǎn)云數(shù)據(jù)

（c）50%的點(diǎn)云數(shù)據(jù) （d）25%的點(diǎn)云數(shù)據(jù)

圖1 礦山三維掃描點(diǎn)云抽稀結(jié)果

分別利用改進(jìn)的八叉樹、KD樹以改進(jìn)八叉樹與KD樹的混合索引方式對(duì)其進(jìn)行組織。運(yùn)行環(huán)境為XP系統(tǒng)，用于數(shù)據(jù)處理實(shí)驗(yàn)的計(jì)算機(jī)CPU型號(hào)為Pentium (R)Dual-Core E5200 2.5GHz雙核。其構(gòu)建時(shí)間統(tǒng)計(jì)如表3.2。根據(jù)表3.2中的數(shù)據(jù)繪制圖3.17。

表1 不同索引方式的構(gòu)建時(shí)間

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

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

6 結(jié)語

本文在KD樹和八叉樹的基礎(chǔ)之上，利用混合索引的方式進(jìn)行點(diǎn)云數(shù)據(jù)的索引。

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

2）本文為點(diǎn)云數(shù)據(jù)索引提供了一個(gè)新的思考方向。如何針對(duì)不同類型的點(diǎn)云數(shù)據(jù)使用更加有效的索引方式可以進(jìn)一步研究。

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

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

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

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

[5]許鵬.海量三維點(diǎn)云數(shù)據(jù)的組織與可視化研究[D].南京：南京師范大學(xué)，2013.

G322

B

1007-6344（2017）03-0338-01

張大鵬， 1988年7月 ， 男，漢，河南 衛(wèi)輝，碩士研究生，助教，研究方向?yàn)槿S激光掃描技術(shù)。

汪軍林，1989年3月，男，漢，河南 項(xiàng)城，碩士研究生，助教，研究方向?yàn)榫芄こ虦y(cè)量