基于點云空間分布特征的多級索引結構

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

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

1 引 言

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

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

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

2 方向八叉樹索引結構

2.1 八叉樹結構

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

圖1 八叉樹結構示意圖

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

2.2 方向包圍盒

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

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

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

(1)

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

Step2:協方差矩陣C計算如下:

(2)

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

2.3 方向八叉樹的思想與構建

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

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

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

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

Step3:如果當前節點中的點云數量大于Toc,計算節點的方向包圍盒。

Step4:根據包圍盒將空間分解成8個子立方體,并將每個子立方體對應的點集作為當前節點的8個子節點:

由包圍盒的中心位置,轉換節點中的點集坐標:

(3)

根據轉換后的坐標點在每一軸上的正負性,將原始點分配到對應的子節點中。

Step5:如果子節點所存儲的點云數量與父節點一樣且不為零,則停止當前節點的細分。

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

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

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

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

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

3 多級索引結構

3.1 KD樹結構

KD樹是一種對多維歐氏空間進行劃分而構造的二叉樹。每個非葉節點代表一次空間劃分。每次劃分時,選擇其中某一維度進行比較,并使用一個合適的數據點作為劃分標準,將當前空間劃分成兩個子空間[19]?？蓪⒋怪庇趧澐志S度且經過劃分數據點的平面視作一個超平面。節點的左子樹代表超平面左邊的點,右子樹代表超平面右邊的點。

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

圖3 KD樹分割

3.2 多級索引結構的思想

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

圖4 多級索引結構

3.3 多級索引結構的構建

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

Step1:使用初始點云P構建一個方向八叉樹。

Step2:為每一個葉子節點Qi構建KD樹,具體操作如下:

①葉子節點的點集作為KD樹的根節點。

②如果當前節點中的點數大于Tkd,當前節點繼續細分。其中,Tkd=N/2m,N表示點云數據集的大小,m表示KD樹遞歸分解層數。

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

(4)

(5)

(6)

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

sd=max(sx,sy,sz)

(7)

以空間中分割維度上的中值點作為分割點,根據分割維度,將空間劃分成兩個子空間,子空間中的點集作為當前節點的子節點。

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

索引構建的流程如圖5所示。

圖5 多級索引構建流程

4 實驗結果與分析

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

4.1 實驗數據與環境

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

4.2 方向八叉樹與八叉樹節點實驗

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

表1 各方法針對不同點云數據的節點比較

4.3 索引構建時間實驗

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

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

4.4 鄰域搜索耗時實驗

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

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

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

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

圖6 不同方向八叉樹閾值下構建索引時間

圖7 不同方向八叉樹閾值下構建索引占用內存

5 總 結

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

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