• 什么是Kdtree

• 什么是Octree

• 對比總結

1. Kdtree的原理

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

2. Kdtree的創(chuàng)建

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

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

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

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

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

3. Kdtree的搜索

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

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

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

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

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

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

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

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

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

4. Kdtree的注意事項

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

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

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

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

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

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

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

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

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

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

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

1. Octree的原理

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

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

2. Octree的創(chuàng)建

（1）設定最大遞歸深度 ? ?

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

（3）依序將單位元元素丟入能被包含且沒有子節(jié)點的立方體 ? ?

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

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

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

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

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

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

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

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

如果將Octree和Kdtree結合起來的應用，應用八叉樹進行大粒度的劃分和查找，而后使用Kdtree樹進行細分，效率會有一定的提升，但其搜索效率變化也與數據量的變化有一個線性關系。