kd-tree建樹算法改進(jìn)

廖勇毅，丁怡心

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

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

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ù)空間進(jìn)行最近鄰查找（Nearest Neighbor）和近似最近鄰查找（Approximate Nearest Neighbor），例如圖像檢索和識別中的高維圖像特征向量的K近鄰查找與匹配。

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

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

2 kd-tree建樹算法分析

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

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

圖1 kd-tree建樹演示

3 建樹算法描述

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

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

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

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

4 選擇分割維度

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

5 選擇分割點(diǎn)

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

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

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

6 改進(jìn)建樹算法

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

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

改進(jìn)算法代碼實(shí)現(xiàn)：

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

輸出：選取維度

7 實(shí)驗(yàn)對比

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

8 結(jié)語

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