kd-tree建樹算法改進

廖勇毅，丁怡心

（廣州民航職業技術學院計算機系，廣州 510403）

kd-tree（k-dimensional tree 的簡稱）是一種分割k 維數據空間的數據結構，主要應用于多維空間特征向量的快速搜索。但是kd-tree 的重要缺點是建樹速度非常慢，提出一種改進的建樹算法，可顯著提高建樹速度。

kd-tree；建樹優化

0 引言

kd-tree（k-dimensional 樹的簡稱），是一種分割k維數據空間的數據結構。主要應用于多維空間特征向量的搜索。kd-tree 是一種軸對齊的BSP 樹，其具有場景自適應劃分、低存儲消耗和快速遍歷等優勢，特別是對高維數據具有很好的自適應劃分效果，常用于在大規模的高維數據空間進行最近鄰查找（Nearest Neighbor）和近似最近鄰查找（Approximate Nearest Neighbor），例如圖像檢索和識別中的高維圖像特征向量的K近鄰查找與匹配。

1 kd-tree的數據結構

kd-tree 從空間角度看待存儲的數據，并采用樹形結構劃分和組織場景空間。當存儲二維數據時，存儲空間就是一個二維平面。根節點按照某一維索引中的某個值M1 把數據劃分成左右兩部分，所有在該維小于等于M1 的數據都放在L1 的左子樹，所有大于M1 的數據都放在的右子樹R1。接下來如果左子樹L1 或右子樹R1 擁有大于1 個節點，則用同樣的方法對它們進行劃分。

2 kd-tree建樹算法分析

kd-tree 建樹的基本思想是一直二分下去，直到所有子樹都只有一個節點為止。對于多維數據，首先需要選則一個維度來進行二分，然后需要在該維度上選擇一個分割點，再把在該維度上小于等于分割點的節點都放在左子樹，把在該維度上大于分割點的節點都放在右子樹，最后如果子樹擁有大于1 個節點，則用同樣的方法遞歸分割子樹。

舉一示例：假設有7 個二維數據點={（0，3），（2，2），（3，3），（4，2），（6，1），（7，2），（7，4）}，數據點位于二維空間中。為了能有效的找到最近鄰，kd-tree 采用分而治之的思想，即將整個空間劃分為幾個小部分。7 個二維數據點生成的kd-tree 如圖1 所示。

圖1 kd-tree建樹演示

3 建樹算法描述

（1）確定候選分割維度：對于所有描述子數據（特征矢量），統計它們在每個維上的數據方差。以SIFT特征點為例，描述子為128 維，可計算128 個方差。挑選出最大值，對應的維就是分割平面（對于多維數據就是超平面）。數據方差大表明沿該坐標軸方向上的數據分散得比較開，在這個方向上進行數據分割有較好的分辨率；

（2）從候選分割平面中選擇最優的分割位置，通常是取該維度上的中間點作為分割點；

（3）以分割點為中心把數據分成左子樹和右子樹；

（4）對于左、右子樹的數據集，按（1）、（2）、（3）步遞歸處理直到每個子樹只有一個節點。

4 選擇分割維度

研究kd-tree 是為了優化在一堆數據中高頻查找的速度，用樹的形式，也是為了盡快地縮小檢索范圍，所以這個“比對維”就很關鍵，通常來說，更為分散的維度，就更容易的將數據分開，是以通過求方差，用方差最大的維度來進行劃分，即最大方差法。用下面公式計數據在某一維度上的方差。

5 選擇分割點

確定了分割維度后，需要在該維度上選擇一個分割點，以此作為kd-tree 的根（root）。選擇分割點的原則有兩點：①保證樹的平衡；②保證葉子節點所占的空間大致相等。第一點是為了降低搜索樹的平均效率，一個極端不平衡的樹會讓搜索的時間復雜度變成O（N），而不是O（logN）。第二點則最大限度地提高了搜索的精度。

1987年，Omohundro 提出選擇分割維度中心點做為分割點的思想，這種思想能最大限度實現樹的平衡，但是分割的葉子節點空間不均勻，很多葉子節點在非常細小的空間，導致搜索精度受到影響。當需要進行精準搜索是，要經過多次搜索，使得搜索性能大大下降。

選擇最靠近分割維度空間中間位置的點作為分割點，是一種較好地折中平衡性和分割空間的思想，雖然樹的分布出現部分不平衡，但是分割的葉子空間基本相等，大大提高了搜索精度，通常一次搜索就可以精確匹配，提高搜索性能。

6 改進建樹算法

kd-tree 建樹的時間復雜度為O（N*N*M），其中N為特征點數量，M 為特征點維數。當候選特征點數量很大時建樹速度很慢，算法最耗費時間的部分是每次確定候選分割平面前統計每維上的數據方差。針對建樹速度慢的問題，提出對于所有描述子數據（特征矢量），取一定數量t 作為樣本，統計它們在每個維上的數據方差。于是，kd-tree 建樹的時間復雜度變為O（t*t*m），當t 的值選擇得當時，可大大提高建樹的效率，并且對kd-tree 搜索的準確性影響非常小。

在實際工程中可以選取間隔相等的t 個特征點做為樣本，例如：特征點數N=100000，確定統計樣本樹t=1000，則每隔100000/1000=100 個特征點選1 個作為樣本。

改進算法代碼實現：

輸入：①特征點數組；②特征點個數

輸出：選取維度

7 實驗對比

取100 萬個SIFT 特征點做實驗，用改進前的算法建樹，耗時361 分鐘。用改進后的算法建樹，取統計樣本數量t=4096，即當子樹特征點數量大于4096 時，t=4096，否則t=實際特征點個數，完成建樹耗時3 分鐘。

8 結語

針對kd-tree 搜索效率高，建樹效率低的特點，本文提出通過適當的取樣，來統計特征點在每個維度上的方差，可以大大提高kd-tree 的建樹效率。實驗表明，當特征點數量越大，效率提高越明顯，并且不影響搜索的精度。