基于點云空間分布特征的多級索引結(jié)構(gòu)

楊麗娟,崔鈺琳,楊紫騫,翟光杰,王 超

(1.中國科學(xué)院國家空間科學(xué)中心,北京 100190;2.中國科學(xué)院大學(xué),北京 100049)

1 引 言

點云數(shù)據(jù)是三維空間中離散分布的一組點,廣泛應(yīng)用于地形測量、文物保護(hù)、三維重建、城市規(guī)劃、智能駕駛、虛擬現(xiàn)實等領(lǐng)域[1-4]。點云空間分布離散無序,數(shù)據(jù)量巨大,為后續(xù)的數(shù)據(jù)處理帶來了挑戰(zhàn)。建立合理高效的空間索引機(jī)制,是實現(xiàn)數(shù)據(jù)高效檢索和快速調(diào)度的關(guān)鍵,是后續(xù)數(shù)據(jù)處理的前提[5]。傳統(tǒng)的單一索引模型難以對海量點云數(shù)據(jù)進(jìn)行高效組織管理,混合索引模型通常結(jié)合了兩種及以上不同索引的優(yōu)勢,是當(dāng)前研究的重點[6]。

文獻(xiàn)[7]提出了一種八叉樹和三維R樹集成的空間索引方法,顯著提升了空間利用率和空間查詢效率。文獻(xiàn)[8]提出了一種多級格網(wǎng)和KD樹相結(jié)合的混合空間索引,既提升了查詢效率,又解決了單一分辨率數(shù)據(jù)冗余的問題。文獻(xiàn)[9]將點云的方向信息引入傳統(tǒng)的模糊c-均值,并使用BSP樹對點云進(jìn)行逐點劃分,使索引能夠沿著點云的空間結(jié)構(gòu)擴(kuò)展,避免產(chǎn)生不必要的分區(qū)。文獻(xiàn)[10]提出了一種全局KD樹和局部八叉樹相結(jié)合的兩級混合索引結(jié)構(gòu),實現(xiàn)了樹結(jié)構(gòu)的均衡,并能以塊為單位對海量點云進(jìn)行快速檢索。文獻(xiàn)[11]提出了一種結(jié)合KD樹空間切分思想的類八叉樹索引結(jié)構(gòu),降低了內(nèi)存空間占用和鄰域搜索耗時。文獻(xiàn)[12]將快速劃分空間的八叉樹和高效查詢空間的三維R*樹相結(jié)合,構(gòu)建了一種名為3DOR*-tree的混合空間索引結(jié)構(gòu),實現(xiàn)了三維地質(zhì)四面體模型的有效訪問和高效查詢。文獻(xiàn)[13]針對地鐵隧道的點云數(shù)據(jù)特點,提出了一種格網(wǎng)和多分辨率八叉樹結(jié)合的索引模型,提升了空間分布不平衡但集中的線狀點云的索引構(gòu)建效率和質(zhì)量。

這些方法的空間劃分都是基于空間規(guī)律性和軸對齊包圍盒的,無法表達(dá)點云本身的空間結(jié)構(gòu)。因此,針對點云分布的不規(guī)則性和非均勻性,將方向包圍盒引入傳統(tǒng)的規(guī)則八叉樹結(jié)構(gòu),提出了一種方向八叉樹空間劃分方法。在全局索引中,采用方向八叉樹組織點云數(shù)據(jù)。通過對點云結(jié)構(gòu)進(jìn)行主成分分析,自適應(yīng)地計算包含一組點的每個節(jié)點的方向包圍盒。為提升索引模型的檢索能力,在局部索引中,增加KD樹來管理方向八叉樹的葉子節(jié)點。

2 方向八叉樹索引結(jié)構(gòu)

2.1 八叉樹結(jié)構(gòu)

八叉樹結(jié)構(gòu)通過對大小為2n×2n×2n的三維空間實體進(jìn)行循環(huán)遞歸的體元剖分,其中每個體元的時間和空間復(fù)雜度相同,從而構(gòu)成一個方向圖[14]。如果被剖分的體元屬性相同,則構(gòu)成一個八叉樹的葉節(jié)點；否則將該體元劃分為8個子立方體,并依次遞歸劃分。八叉樹劃分及結(jié)構(gòu)示意圖如圖1所示。

圖1 八叉樹結(jié)構(gòu)示意圖

傳統(tǒng)的八叉樹首先為點云數(shù)據(jù)建立軸向包圍盒,之后遞歸地將空間規(guī)則地劃分成八個均勻的子立方體,并將空間中的數(shù)據(jù)分配到相應(yīng)的子立方體中,可以實現(xiàn)對海量點云數(shù)據(jù)的高效管理。但是,易產(chǎn)生大量的空白節(jié)點,影響樹的平衡性[15]。

2.2 方向包圍盒

方向包圍盒是沿著物體的主成分方向生成的最小立方體包圍盒。因此,相較于軸向包圍盒,方向包圍盒可以根據(jù)物體的形狀特征盡可能緊密地逼近物體,緊密性更好,能顯著降低冗余空間。計算方向包圍盒主要是借助頂點坐標(biāo)的一階及二階統(tǒng)計特性來確定最佳方向,并尋找包圍盒在該方向上的最小尺寸[16]。

本文采用了一種利用三角網(wǎng)計算方向包圍盒的方法[17],具體步驟如下:

Step1:三角面片的平均向量如式(1)所示:

(1)

其中,n代表三角面片的總數(shù);pi、qi和ri分別表示的是第i個三角面片的三個頂點的坐標(biāo)向量。

Step2:協(xié)方差矩陣C計算如下:

(2)

Step3:計算協(xié)方差矩陣C的特征向量,確定方向包圍盒的方向和尺寸。對特征向量進(jìn)行單位化,將其作為一個基。由于矩陣C是對稱矩陣,因此特征向量基是正交的。沿基的每個軸向找到該軸向上的極值頂點,并由極值頂點確定方向包圍盒的尺寸[18]。將軸向作為方向包圍盒的方向。

2.3 方向八叉樹的思想與構(gòu)建

方向八叉樹是一種用來描述三維空間的樹狀結(jié)構(gòu)模型。方向八叉樹的每個非葉子節(jié)點代表對應(yīng)空間數(shù)據(jù)的方向包圍盒。每個節(jié)點空間可以均勻分割成8個子立方體,8個子立方體對應(yīng)的點集組成當(dāng)前節(jié)點的8個子節(jié)點。如果子節(jié)點滿足分割條件,則對其進(jìn)行遞歸劃分,直至滿足分割停止條件。

方向八叉樹的輸入是原始點云集P,組織構(gòu)建步驟為:

Step1:初始化分割閾值Toc。本次實驗中,Toc設(shè)為原始點集數(shù)量的0.2 %。

Step2:使用原始點云集P作為樹的根節(jié)點。

Step3:如果當(dāng)前節(jié)點中的點云數(shù)量大于Toc,計算節(jié)點的方向包圍盒。

Step4:根據(jù)包圍盒將空間分解成8個子立方體,并將每個子立方體對應(yīng)的點集作為當(dāng)前節(jié)點的8個子節(jié)點:

由包圍盒的中心位置,轉(zhuǎn)換節(jié)點中的點集坐標(biāo):

(3)

根據(jù)轉(zhuǎn)換后的坐標(biāo)點在每一軸上的正負(fù)性,將原始點分配到對應(yīng)的子節(jié)點中。

Step5:如果子節(jié)點所存儲的點云數(shù)量與父節(jié)點一樣且不為零,則停止當(dāng)前節(jié)點的細(xì)分。

Step6:迭代執(zhí)行步驟(3)至(5),直到節(jié)點中的點云數(shù)量均小于或等于Toc。

2.4 八叉樹與方向八叉樹的比較

由于三維點集的劃分較為復(fù)雜,為了清晰明了地展示思路,如圖2所示,分別使用四叉樹和方向四叉樹對二維點集的空間劃分來示意比較。樹的分割閾值設(shè)置為3。圖2(a)、圖2(b)分別表示四叉樹的空間劃分和劃分后形成的樹結(jié)構(gòu),圖2(c)、圖2(d)分別表示方向四叉樹的空間劃分和劃分后形成的樹結(jié)構(gòu)。非空節(jié)點率定義為所有節(jié)點中非空節(jié)點的占比。四叉樹產(chǎn)生了25個節(jié)點(18個葉節(jié)點,3個空節(jié)點),非空節(jié)點率是88 %；方向四叉樹產(chǎn)生了 21個節(jié)點(16個葉節(jié)點,1個空節(jié)點),非空節(jié)點率是95 %。

圖2 二維點集的空間劃分比較

可以看出,與四叉樹相比,方向四叉樹在節(jié)點總數(shù)、葉節(jié)點數(shù)、空節(jié)點數(shù)和非空節(jié)點率上都有更好的結(jié)果,有助于減少節(jié)點數(shù)量和冗余節(jié)點。

3 多級索引結(jié)構(gòu)

3.1 KD樹結(jié)構(gòu)

KD樹是一種對多維歐氏空間進(jìn)行劃分而構(gòu)造的二叉樹。每個非葉節(jié)點代表一次空間劃分。每次劃分時,選擇其中某一維度進(jìn)行比較,并使用一個合適的數(shù)據(jù)點作為劃分標(biāo)準(zhǔn),將當(dāng)前空間劃分成兩個子空間[19]?？蓪⒋怪庇趧澐志S度且經(jīng)過劃分?jǐn)?shù)據(jù)點的平面視作一個超平面。節(jié)點的左子樹代表超平面左邊的點,右子樹代表超平面右邊的點。

為了使KD樹具有更好的平衡性,每次劃分應(yīng)盡量使數(shù)據(jù)點集均勻分割成兩部分。通常,與其他維度相比,數(shù)據(jù)點集在劃分維度上應(yīng)分布盡量分散[20]。因此,可選擇所有數(shù)據(jù)點方差最大的維度作為劃分維度,并取劃分維度上的中位數(shù)對應(yīng)的點作為劃分?jǐn)?shù)據(jù)點。以劃分?jǐn)?shù)據(jù)點在劃分維度上的值為標(biāo)準(zhǔn),將其余數(shù)據(jù)點分配到左、右子樹上。如果當(dāng)前數(shù)據(jù)點在劃分維度上對應(yīng)的值小于標(biāo)準(zhǔn)值,則將其劃分到當(dāng)前節(jié)點的左子樹,反之,則劃分到當(dāng)前節(jié)點的右子樹。如圖3所示,KD樹將二維及三維空間分割成多個子空間。

圖3 KD樹分割

3.2 多級索引結(jié)構(gòu)的思想

KD樹能實現(xiàn)點云的快速查找,但由于建樹期間占用內(nèi)存過大,難以對海量點云進(jìn)行構(gòu)建。而方向八叉樹構(gòu)建簡單、快速,查詢效率受限于分割閾值。因此,可結(jié)合二者優(yōu)勢,基于方向八叉樹和KD樹建立混合索引結(jié)構(gòu)。在上層采用方向八叉樹對點云進(jìn)行全局劃分,在下層使用KD樹對局部點云信息進(jìn)行組織,遞歸劃分方向八叉樹葉節(jié)點,直至KD樹葉節(jié)點內(nèi)的點數(shù)不超過提前設(shè)置的閾值。劃分后的空間信息存儲在方向八叉樹葉節(jié)點中,如圖4所示,形成全局方向八叉樹和局部KD樹的多層混合索引結(jié)構(gòu)。

圖4 多級索引結(jié)構(gòu)

3.3 多級索引結(jié)構(gòu)的構(gòu)建

建立基于三維點云空間分布特征的多級索引結(jié)構(gòu)的具體步驟如下:

Step1:使用初始點云P構(gòu)建一個方向八叉樹。

Step2:為每一個葉子節(jié)點Qi構(gòu)建KD樹,具體操作如下:

①葉子節(jié)點的點集作為KD樹的根節(jié)點。

②如果當(dāng)前節(jié)點中的點數(shù)大于Tkd,當(dāng)前節(jié)點繼續(xù)細(xì)分。其中,Tkd=N/2m,N表示點云數(shù)據(jù)集的大小,m表示KD樹遞歸分解層數(shù)。

③根據(jù)點集空間的軸向包圍盒,計算點集在各個維度上的方差:

(4)

(5)

(6)

選擇具有最大方差的維度,來確定分割維度:

sd=max(sx,sy,sz)

(7)

以空間中分割維度上的中值點作為分割點,根據(jù)分割維度,將空間劃分成兩個子空間,子空間中的點集作為當(dāng)前節(jié)點的子節(jié)點。

④迭代執(zhí)行②至③,直至節(jié)點中的點數(shù)均小于或等于Tkd。葉子節(jié)點中的點集以及每個節(jié)點點集的包圍盒,即為劃分結(jié)果。

索引構(gòu)建的流程如圖5所示。

圖5 多級索引構(gòu)建流程

4 實驗結(jié)果與分析

為驗證所提方向八叉樹在節(jié)點冗余方面的提升,本文使用經(jīng)典八叉樹與方向八叉樹進(jìn)行對比實驗。同時,為驗證本文基于三維點云空間分布特征的多級索引的結(jié)構(gòu)有效性,將KD樹、八叉樹、四叉樹—KD樹與基于三維點云空間分布特征的多級索引進(jìn)行比較。比較指標(biāo)包括構(gòu)建索引消耗時間、鄰域搜索時間。最后,通過實驗探索方向八叉樹分割閾值對多級索引結(jié)構(gòu)構(gòu)建時間以及構(gòu)建內(nèi)存的影響。

4.1 實驗數(shù)據(jù)與環(huán)境

根據(jù)空間分布特征和數(shù)據(jù)量,本文選擇了三種類型的點云數(shù)據(jù)進(jìn)行實驗。第一類數(shù)據(jù)是The Stanford 3D Scanning Repository中的典型點云數(shù)據(jù);第二類數(shù)據(jù)是RGB-D Object Dataset中的常見室內(nèi)環(huán)境點云數(shù)據(jù);第三類數(shù)據(jù)是大型自然場景的海量三維點云數(shù)據(jù)。數(shù)據(jù)點的數(shù)量級分布是103～108。實驗環(huán)境是Intel(R)Core(TM)i5-7200U CPU @2.50 GHz,12 GB內(nèi)存。

4.2 方向八叉樹與八叉樹節(jié)點實驗

表1顯示了八叉樹與方向八叉樹的節(jié)點對比,對比項包括節(jié)點總數(shù)、空節(jié)點數(shù)和非空節(jié)點率。在所有數(shù)量級的點云數(shù)據(jù)上,與八叉樹相比,方向八叉樹生成的總節(jié)點數(shù)和空節(jié)點數(shù)均更少。同時,方向八叉樹結(jié)構(gòu)的非空節(jié)點率有較為顯著的提升。八叉樹的非空節(jié)點率集中分布在83 %～90 %,而方向八叉樹的非空節(jié)點率集中在88 %～96 %范圍內(nèi),空間利用率提高了5 %。

表1 各方法針對不同點云數(shù)據(jù)的節(jié)點比較

4.3 索引構(gòu)建時間實驗

四種索引的構(gòu)建時間對比如表2所示。其中,KD樹建樹耗時最長,遠(yuǎn)大于其他三種方法,且隨著點云數(shù)量級的增加,差異逐漸擴(kuò)大。當(dāng)點云數(shù)量達(dá)到100萬時,KD樹建樹耗時比其他方法多65～91 s。當(dāng)點云數(shù)量超過1000萬時,KD樹會由于內(nèi)存不足而無法完成建樹。四種方法中,八叉樹索引構(gòu)建速度最快。由于引入了方向信息,基于三維點云空間分布特征的多級索引建樹時間增加,但明顯快于四叉樹—KD樹混合索引,與八叉樹相差不大。

表2 各方法索引構(gòu)建時間對比(單位:s)

4.4 鄰域搜索耗時實驗

鄰域搜索耗時是指搜索指定的每一個點的最鄰近點所消耗的平均時間。本文方法與其他三種方法相應(yīng)指標(biāo)對比如表3所示。通過對比可知,八叉樹搜索耗時最長,查詢效率遠(yuǎn)低于KD樹。與單一索引結(jié)構(gòu)的查詢效率相比,混合結(jié)構(gòu)的索引方式的查詢效率有著明顯優(yōu)勢。本文方法和四叉樹—KD樹結(jié)構(gòu)查詢效率均在KD樹基礎(chǔ)上有所提升,相比于八叉樹結(jié)構(gòu)提升了1～2個數(shù)量級。與四叉樹—KD樹混合索引結(jié)構(gòu)相比,本文方法鄰域搜索速度更快,具有更好的查詢性能。

表3 各方法鄰域搜索時間對比(單位:ms)

4.5 方向八叉樹分割閾值實驗

不同數(shù)量級的點云數(shù)據(jù)構(gòu)建混合索引所消耗的時間、空間與方向八叉樹分割閾值的關(guān)系如圖6、圖7所示。索引構(gòu)建時間及內(nèi)存占用主要與點云數(shù)據(jù)量相關(guān),不同方向八叉樹分割閾值對同一點云的構(gòu)建影響較小。同時,點云數(shù)據(jù)量越大,方向八叉樹分割閾值產(chǎn)生的影響越大。對于數(shù)據(jù)量較大的點云,當(dāng)上層方向八叉樹分割閾值逐漸增大時,構(gòu)建索引所消耗的時間和空間先有明顯的下降,之后下降幅度逐漸減弱,最后趨于平緩。因此,對海量點云的索引構(gòu)建而言,選擇合適的方向八叉樹分割閾值能節(jié)省大量時間及空間占用,具有重要意義。

圖6 不同方向八叉樹閾值下構(gòu)建索引時間

圖7 不同方向八叉樹閾值下構(gòu)建索引占用內(nèi)存

5 總 結(jié)

本文針對海量不規(guī)則點云管理困難,時空消耗大的問題,根據(jù)點云分布特征,將空間分布特征引入八叉樹,提出了一種新的空間劃分方法——方向八叉樹,來適應(yīng)點云數(shù)據(jù)的非均勻空間分布。在此基礎(chǔ)上分析了方向八叉樹和KD樹的優(yōu)缺點,并設(shè)計了方向八叉樹與KD樹結(jié)合的雙層點云管理模型,進(jìn)一步提高索引查詢效率,對點云數(shù)據(jù)進(jìn)行合理管理。實驗表明,方向八叉樹結(jié)構(gòu)相比于傳統(tǒng)八叉樹,空間利用率提高了5 %左右。且本文提出的基于空間分布特征的多級索引結(jié)構(gòu),構(gòu)建索引耗時接近于八叉樹,相比于KD樹、四叉樹—KD樹混合索引提高了25 %；與其他三種索引結(jié)構(gòu)相比,鄰域搜索效率提高了18 %,充分驗證了本文方法的有效性。

但本文提出的索引方法仍有很多可改進(jìn)之處。例如,對海量點云數(shù)據(jù)而言,上層方向八叉樹分割閾值對索引構(gòu)建時間、空間有較大影響,但目前難以通過簡單、自動的方法確定最優(yōu)的分割閾值；方向八叉樹與八叉樹的樹結(jié)構(gòu)高度相差不大,如何更加充分的利用點云數(shù)據(jù)分布特征來構(gòu)建索引,使樹具有更好的平衡性,是未來的研究目標(biāo)。