三維點云數(shù)據(jù)的兩種結(jié)構(gòu)Kdtree和Octree

三維點云數(shù)據(jù)用于表征目標(biāo)表面的海量點集合，但是各個離散點之間并沒有拓?fù)潢P(guān)系，一般通過建立點云的空間索引來實現(xiàn)基于鄰域關(guān)系的快速查找。在三維點云數(shù)據(jù)中用的較為廣泛的兩種結(jié)構(gòu)分別是Kdtree和Octree。

目錄

什么是Kdtree

什么是Octree

對比總結(jié)

什么是Kdtree？

1. Kdtree的原理

Kdtree是一種劃分k維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)，在一個K維數(shù)據(jù)集合上構(gòu)建一棵Kdtree代表了對該K維數(shù)據(jù)集合構(gòu)成的K維空間的一個劃分，即樹中的每個結(jié)點就對應(yīng)了一個K維的超矩形區(qū)域。主要用于多維空間關(guān)鍵數(shù)據(jù)的搜索。

2. Kdtree的創(chuàng)建

Kdtree的創(chuàng)建就是按照某種順序?qū)o序化的點云進行有序化排列，方便進行快捷高效的檢索。算法流程如下：

（1） 在K維數(shù)據(jù)集合中選擇具有最大方差的維度，然后在該維度上選擇中值m為中心對該數(shù)據(jù)集合進行劃分，得到兩個子集合；同時創(chuàng)建一個樹結(jié)點node，用于存儲；

（2）對兩個子集合重復(fù)（1）步驟的過程，直至所有子集合都不能再劃分為止；如果某個子集合不能再劃分時，則將該子集合中的數(shù)據(jù)保存到葉子結(jié)點。

根據(jù)上述算法步驟，以二維數(shù)據(jù)創(chuàng)建Kdtree為例，輸入數(shù)據(jù)列表為{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}；劃分的二維分割圖如下：

首先統(tǒng)計X和Y方向上的方差，選取方差較大的X維度作為初始分割軸，對X軸上的數(shù)值{2，5，9，4，8，7}取中值X=7作為分割線，生成左子樹{(2,3)，(5,4)，(4,7)}，生成右子樹{(9,6)，(8,1)}，更新分割軸Y，分別在左右子樹中找到中位數(shù)（5,4）和（9,6），依次迭代如下圖：

3. Kdtree的搜索

Kdtree的搜索方法有以下兩種：

范圍搜索：給定搜索點和搜索距離的閾值，從數(shù)據(jù)集中找出所有與搜索點距離小于閾值的數(shù)據(jù)；

最近鄰搜索：給定查詢點和正整數(shù)K，從數(shù)據(jù)集中找到距離查詢點最近的K個數(shù)據(jù)，當(dāng)K=1時，就是最近鄰搜索。

以最近鄰搜索算法為例，其流程如下：

（1）將查詢數(shù)據(jù)Q從根結(jié)點開始，按照Q與各個結(jié)點的比較結(jié)果向下訪問Kdtree，直至達到葉子結(jié)點。
其中Q與結(jié)點的比較指的是將Q對應(yīng)于結(jié)點中的k維度上的值與中值m進行比較，若Q(k) < m，則訪問左子樹，否則訪問右子樹。達到葉子結(jié)點時，計算Q與葉子結(jié)點上保存的數(shù)據(jù)之間的距離，記錄下最小距離對應(yīng)的數(shù)據(jù)點，記為當(dāng)前最近鄰點和最小距離Distance。

（2）進行回溯操作，該操作是為了找到離Q更近的“最近鄰點”。即判斷未被訪問過的分支里是否還有離Q更近的點，它們之間的距離小于Distance。

如果Q與其父結(jié)點下的未被訪問過的分支之間的距離小于Distance，則認(rèn)為該分支中存在離P更近的數(shù)據(jù)，進入該結(jié)點，進行（1）步驟一樣的查找過程，如果找到更近的數(shù)據(jù)點，則更新為當(dāng)前的最近鄰點，并更新Distance。

如果Q與其父結(jié)點下的未被訪問過的分支之間的距離大于Distance，則說明該分支內(nèi)不存在與Q更近的點。

回溯的判斷過程是從下往上進行的，直到回溯到根結(jié)點時已經(jīng)不存在與P更近的分支為止。

4. Kdtree的注意事項

a.對子空間進行劃分時，怎樣確定在哪個維度上劃分？

輪流劃分法：如果這次選擇在第i維上進行數(shù)據(jù)劃分，那下一次就在第j(j≠i)維上進行劃分，例如：j = (i mod k) + 1。

但是這樣忽略了不同屬性數(shù)據(jù)之間的分散程度，有的屬性值比較分散，有的屬性值比較集中。當(dāng)數(shù)據(jù)的分布在某一個維度較為集中，出現(xiàn)下圖的現(xiàn)象，第一次劃分將數(shù)據(jù)分為左右兩個子集合，安裝輪流的交替原則，第二次劃分的軸并不能很好的分割數(shù)據(jù)：

方差統(tǒng)計法：統(tǒng)計樣本在每個維度上的數(shù)據(jù)方差，選出對應(yīng)方差最大值的那個維度。因為方差大說明在該坐標(biāo)軸上的數(shù)據(jù)點較為分散。

但是理論上空間均勻分布的點，在一個方向上分割之后，通過計算方差下一次分割就不會出現(xiàn)在這個方向上了，不過特殊情況如下：

方差優(yōu)化法：初始維度的劃分依據(jù)數(shù)據(jù)方差范圍最大的那一維作為分割維度，之后也是選中這個維度的中間節(jié)點作為軸點，然后進行分割，分割出來的結(jié)果如下圖所示：

b.在某個維度上劃分時，怎樣確保樹盡量平衡？

中位數(shù)法：找到該維度上數(shù)據(jù)的中位數(shù)，然后將數(shù)據(jù)點與中位數(shù)進行比較，得到兩個子集合的個數(shù)基本相同。

c.怎樣判斷未被訪問的分支里有離搜索數(shù)據(jù)更近的點？

從幾何空間上，通過判斷以搜索數(shù)據(jù)為中心和以記錄的當(dāng)前距離為半徑的超球面與樹分支代表的超矩形之間是否相交。如下圖所示：

星號為搜索數(shù)據(jù)，綠色的點為疑似最近點，以搜索點和疑似最近點構(gòu)成的圓與所在分割區(qū)域的矩形有交集，則需要回溯根節(jié)點中未被訪問的分支。

什么是Octree

1. Octree的原理

Octree是一種用于描述三維空間的樹狀數(shù)據(jù)結(jié)構(gòu)。八叉樹的每個節(jié)點表示一個正方體的體積元素，每個節(jié)點有八個子節(jié)點，將八個子節(jié)點所表示的體積元素加在一起就等于父節(jié)點的體積。能夠很好的壓縮點云節(jié)省存儲空間。

通過對三維空間的幾何實體進行體元剖分，每個體元具有相同的時間和空間復(fù)雜度，通過循環(huán)遞歸的劃分方法對大小為(2n?2n?2n)的三維空間的幾何對象進行剖分，從而構(gòu)成一個具有根節(jié)點的方向圖。在八叉樹結(jié)構(gòu)中如果被劃分的體元具有相同的屬性，則該體元構(gòu)成一個葉節(jié)點；否則繼續(xù)對該體元剖分成8個子立方體，依次遞剖分，對于(2n?2n?2n)大小的空間對象，最多剖分n 次，如下圖所示：

2. Octree的創(chuàng)建

（1）設(shè)定最大遞歸深度

（2）找出場景的最大尺寸，并以此尺寸建立第一個立方體

（3）依序?qū)挝辉貋G入能被包含且沒有子節(jié)點的立方體

（4）若沒有達到最大遞歸深度，就進行細(xì)分八等份，再將該立方體所裝的單位元元素全部分擔(dān)給八個子立方體

（5）若發(fā)現(xiàn)子立方體所分配到的單位元元素數(shù)量不為零且跟父立方體是一樣的，則該子立方體停止細(xì)分，因為根據(jù)空間分割理論，細(xì)分的空間所得到的分配必定較少，若是一樣數(shù)目，則再怎么切數(shù)目還是一樣，會造成無窮切割的情形。

（5）重復(fù)3，直到達到最大遞歸深度。

Octree的葉子節(jié)點代表了分辨率最高的情況。例如分辨率設(shè)成0.01m，那么每個葉子就是一個1cm見方的小方塊。如下圖所示：

當(dāng)分辨率較高時，方塊很??；分辨率較低時，方塊很大。以斯坦福課程中的兔子模型為例：

對比總結(jié)

由于三維點云的數(shù)據(jù)量較大，使用Kdtree和Octree進行檢索可以較少時間消耗，確保點云的關(guān)聯(lián)點尋找和配準(zhǔn)處于實時的狀態(tài)。

Kdtree在鄰域查找上比較有優(yōu)勢，但在大數(shù)據(jù)量的情況下，若劃分粒度較小時，建樹的開銷也較大，但比八叉樹靈活些。在小數(shù)據(jù)量的情況下，其搜索效率比較高，但在數(shù)據(jù)量增大的情況下，其效率會有一定的下降，一般是線性上升的規(guī)律。

Octree算法實現(xiàn)簡單，但大數(shù)據(jù)量點云數(shù)據(jù)下，其使用比較困難的是最小粒度（葉節(jié)點）的確定，粒度較大時，有的節(jié)點數(shù)據(jù)量可能仍比較大，后續(xù)查詢效率仍比較低，反之，粒度較小，八叉樹的深度增加，需要的內(nèi)存空間也比較大（每個非葉子節(jié)點需要八個指針），效率也降低。而等分的劃分依據(jù)，使得在數(shù)據(jù)重心有偏斜的情況下，受劃分深度限制，其效率不是太高。

如果將Octree和Kdtree結(jié)合起來的應(yīng)用，應(yīng)用八叉樹進行大粒度的劃分和查找，而后使用Kdtree樹進行細(xì)分，效率會有一定的提升，但其搜索效率變化也與數(shù)據(jù)量的變化有一個線性關(guān)系。