廖勇毅，丁怡心

（廣州民航職業(yè)技術(shù)學院計算機系，廣州 510403）

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

kd-tree；建樹優(yōu)化

0 引言

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

1 kd-tree的數(shù)據(jù)結(jié)構(gòu)

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

2 kd-tree建樹算法分析

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

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

圖1 kd-tree建樹演示

3 建樹算法描述

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

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

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

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

4 選擇分割維度

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

5 選擇分割點

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

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

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

6 改進建樹算法

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

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

改進算法代碼實現(xiàn)：

輸入：①特征點數(shù)組；②特征點個數(shù)

輸出：選取維度

7 實驗對比

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

8 結(jié)語

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