改進的高維搜索算法在圖像匹配中的應用

王佩文

（四川大學計算機學院，成都 610065）

改進的高維搜索算法在圖像匹配中的應用

王佩文

（四川大學計算機學院，成都 610065）

針對現有的高維數搜索算法在進行圖像匹配中存在大量錯配點對的問題，提出一種基于KD-Tree的改進算法（PCAKD-Forest）。該方法將數據集分解成等量的N個子數據集，針對每個子數據集單獨建樹。建樹時，使用PCA算法，根據各維數之間的協方差，求出它們的主成分奉獻率，再按主成分奉獻率進行維數優先級排序。將N棵樹形成的KDForest應用于圖像特征點匹配。實驗結果表明，改進后的算法在保證實時性的同時，顯著地提高匹配精度。

搜索算法；分區；圖像匹配；精度

0 引言

高維數搜索在很多計算機視覺應用中是一個非常重要的組成部分。高維搜索技術發展至今，已經擁有很多經典的算法，例如等距索引、Opt-Tree、C-Tree、hBTree，等等。在眾多的高維搜索算法當中，K維搜索樹因其良好的實時性在圖像匹配中被廣泛地應用。但是，隨著樣本數據集當中特征點數量的增多，K維搜索樹算法一般只能匹配到較近的點，而無法匹配到最近點，同時還有一些錯配點。針對以上不足，本文提出一種基于K維搜索樹的PCA-KD-Forest算法，該算法形成多棵有序K維搜索樹。實驗表明，該算法顯著地提高了匹配精度，同時保持了良好的實時性。

1 K維搜索樹及圖像匹配算法簡介

K維搜索樹——即KD-Tree（KD樹），是一種高維索引樹形數據結構，常用于大規模的高維數據空間進行最近鄰查找和近似最近鄰查找，例如圖像檢索和識別中的高維圖像特征向量的K近鄰查找與匹配。下面分析KD-Tree的基本原理。

1.1 K維搜索樹的構造

構建KD-Tree時，在樹的第一層（根），先選定一個最大方差維度，因為數據在該維度上分散得比較開，更容易在這個維度上將數據劃分開。然后計算該維度上數據的中值，以此作為劃分閾值，此時數據被一個垂直于該維度的超平面分割成兩半。然后每半數據用相同的方法遞歸分割來創建一棵完全平衡的二叉樹。

1.2 最近鄰查找

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

（2）進行回溯（Backtracking）操作，該操作是為了找到離Q更近的“最近鄰點”。即判斷未被訪問過的分支里是否還有離Q更近的點，它們之間的距離小于D。如果Q與其父結點下的未被訪問過的分支之間的距離小于D，則認為該分支中存在離P更近的數據，進入該結點，進行步驟（1）一樣的查找過程，如果找到更近的數據點，則更新為當前的“最近鄰點”P，并更新D。如果Q與其父結點下的未被訪問過的分支之間的距離大于D，則說明該分支內不存在與Q更近的點。回溯的判斷過程是從下往上進行的，直到回溯到根結點時已經不存在與P更近的分支為止。

1.3 圖像特征匹配算法

Sift算法是經典的圖像特征點匹配算法，由128維的數據作為描述子，將兩個高維數據的歐氏距離作為匹配準則。Sift算法包括以下五個步驟：

①建立尺度空間極值。尺度空間函數等于可變尺度的高斯函數G（x，y，σ）與輸入圖像I（x，y）的卷積，公式如下：

其中：

通過建立高斯金字塔來求取特征點的位置，高斯金字塔是通過對輸入圖像進行降采樣形成的圖像組。為了有效獲取穩定的特征點位置，采用差分高斯金字塔DOG，即：

②去除不可靠的特征點。

③特征點方向分配。每個特征點都被分配一個或多個方向基于梯度直方圖。

式（4）和式（5）分別為（x，y）處梯度的模值和方向計算公式。每個特征點被指定一個主方向和一個輔方向，這樣，每個特征點都包含位置、尺度以及方向三個信息。

④生成特征描述符。局部圖像梯度是在每個特征點區域已經選擇好的尺度下檢測的。特征描述符是由特征點周圍的16×16像素領域內計算的，將領域分成4×4的子塊，然后對每個子像素塊計算8個方向的梯度方向直方圖。這樣每個特征點的特征向量是128維（4× 4×8）。

⑤匹配。求參考圖像中的每個特征點在測試圖像中特征點集中最近與次近的特征點；若最近與次近的比率小于某個給定閾值，則認為正確匹配，否則不匹配；這里的最近與次近定義為特征點的描述符向量的歐氏距離。

2 PCA-KD-Forest算法

K維搜索樹算法在進行高維空間特征點匹配時，隨著樣本點的增多，準確率會快速下降，一般只能匹配到相近的點，而無法匹配到最近的點，甚至會出現很多錯配點。而且樣本點的維數越高，越容易在之前的維數對特征點進行錯分，導致錯配率升高。PCA-KD-Forest算法針對以上不足，提高搜索準確性，提高匹配精度，它是在K維搜索樹的基礎上加以改進的，其步驟如下：

①首先利用Sift算法提取參考圖像與測試圖像的特征點，設參考圖像與測試圖像提取的特征點個數分別為Nr與Nt，設參考圖像的特征點集合為Sr=｛Xr（0），Xr（1），…，Xr（Nr－1）}，測試圖像的特征點集合為St=｛Xt（0），Xt（1），…，Xt（Nt－1）｝；

②將參考圖像特征點集Sr劃分為F個分區，每個分區單獨建樹，經實驗表明，當F=9時，既能保持原有算法實時性，又能提高匹配精度；

④計算相關矩陣R=r（i，j），如式（6）：

⑤由|R-λiI|=0，求得特征值和特征向量，其中λi表示主成分的方差貢獻；

⑥計算主成分貢獻率如式（7）：

⑦按照Ci，得到數組E[n]，它根據主成分貢獻率從大到小存儲特征點的維數；

⑧按照E[n]中維數的順序，構造K維搜索樹，由F棵K維搜索樹形成有序的KD-Forest；

⑨將測試圖像中的特征點，依次在有序KD-Forest中的每棵K維搜索樹中進行搜索，用歐氏距離計算，得到F個相近點，比較這F個相近點，取其中距離最小的點作為最近點，此時算法終止。

3 實驗及結果分析

為了驗證本文提出的PCA-KD-Forest算法的有效性，使用不同內容的圖像集，對本文方法與K維搜索樹方法做比較。用于本文實驗的多組不同圖像來自文獻[2]中給出的被使用最廣泛的圖像集，每組圖像包含6幀內容一致的圖像，在這多組圖像中分別包含了視角變化、圖像旋轉和尺度縮放以及光線改變。實驗環境使用的操作系統為Windows 7，CPU為1.70 GHz，內存為4G，程序運行環境為Visual Studio 2008。

從圖像集中選一組針對不同角度旋轉和尺度縮放的圖像來進行匹配正確率對比，圖1為用于實驗的其中兩幀圖像，圖1（a）為參考圖像，圖1（b）為測試圖像；圖2為兩種算法的匹配結果。

圖1 用作實驗的兩幀圖像

圖2 兩種算法的匹配結果

用于實驗的多幀圖像的尺寸均為原始尺寸，表1為匹配結果數據。

表1 兩種算法的匹配數據

上述實驗結果表明，PCA-KD-Forest算法相比K維搜索數算法，在精度方面有著顯著的提高。

4 結語

本文分析了K維搜索樹算法的原理及其存在的缺點，提出了PCA-KD-Forest算法。該算法旨在提高高維數搜索算法的精度，同時保證實時性，因此PCA-KDForest算法具有良好的實際應用價值。

[1] 熊云艷，毛宜軍，閔華清.有序的KD-Tree在圖像特征匹配上的應用[J].化學自動化儀表，2010，37（10）：84～87

[2] Mikolajczyk K，Tuytelaars T，Schmid C，etc.A Comparison of Affine Region Detectors[J].International Journal of Computer Vision，2005，65（1/2）：43

[3] You Jia，Jingdong Wang，Gang Zeng，Hongbin Zha.Optimizing KD-Trees for Scalable Visual Descriptor Indexing[J].Computer Vision and Pattern Recognition（CVPR），2010：3392～3399

[4] Qian Zhang*，Ning Shan，Feng Chen Qian，Ya Lin Ye.A New Method of Expressing Point Model Based on KD-Tree for Plane Area [J].Advanced Materials Research，2013：658～661

Application of the Improved High-Dimensional Search Algorithm in Image Matching

WANG Pei-wen
（College of Computer Science，Sichuan University，Chengdu 610065）

Since the matching result with traditional high-dimensional search algorithm has many false matching points,proposes an improved highdimensional search algorithm（PCA-KD-Forest）based on KD-Tree.Decomposes the data set into N subsets with the same amount.For each subset,creates a KD-Tree.Uses principal components analysis and calculates the rate of contributions of the main components.According to the covariance between dimensions,the dimensions are sorted by the rate of contributions.Then all KD-trees constitute a KDForest.Applies the improved KD-Forest to match the Sift characteristic point.The experiment demonstrates that the matching accuracy is improved greatly in the premise of real time property.

Search Algorithm;Partition;Image Matching;Accuracy

1007-1423（2015）04-0015-04

10.3969/j.issn.1007-1423.2015.04.004