基于KD樹的海量圖像匹配技術(shù)

張小莉

摘 要： 針對海量圖像匹配的速度瓶頸問題，提出一種結(jié)合圖像SIFT特征和KD樹搜索的圖像匹配算法，并建立了適應(yīng)有限內(nèi)存環(huán)境的大型KD樹混合存儲模式。實驗結(jié)果表明，該方法能顯著提高圖像搜索速度和圖像庫的可擴展性，查準(zhǔn)率和查全率也明顯高于其他搜索方法。

關(guān)鍵詞： 圖像匹配； 特征提取； KD樹； 近似最近鄰搜索

中圖分類號：TP391.4 文獻標(biāo)志碼：A 文章編號：1006-8228（2014）07-40-03

Abstract： To deal with the performance bottleneck problem in massive pairwise image matching， an image matching algorithm based on KD-tree is proposed， with a hybrid approach to KD-tree construction under a memory constraint. The experimental results indicate that the proposed method increases image searching speed and the extensibility of image library greatly. It has better performance than other search methods， in terms of precision and recall of image matching.

Key words： image matching； feature extraction； KD-Tree； approximate nearest neighbor searching

0 引言

圖像匹配是圖像處理和計算機視覺領(lǐng)域的重要內(nèi)容，是圖像查詢、圖像拼接、運動恢復(fù)結(jié)構(gòu)等應(yīng)用的核心步驟，也是最耗時的一個步驟。對于海量圖像數(shù)據(jù)，匹配過程往往成為效率的最大瓶頸。本文提出一種結(jié)合圖像SIFT特征[1]和KD樹[2]搜索的圖像匹配方法，并針對海量圖像處理建立了一種大型KD樹混合存儲模式，基于該技術(shù)，圖像搜索的時間復(fù)雜度大大降低，在同樣的內(nèi)存限制下，可索引更多的數(shù)據(jù)，有效提升了圖像庫的可擴展性，查準(zhǔn)率和查全率也明顯高于其他搜索方法。

1 圖像特征提取

在基于特征的圖像匹配技術(shù)中，首要任務(wù)是自動提取穩(wěn)定可靠的圖像特征。2004年Lowe提出了尺度不變特征變換（SIFT，Scale Invariant Feature Transform）算法，先建立圖像的尺度空間表示，然后在尺度空間中搜索圖像的極值點，由極值點建立特征點的描述向量。SIFT算法提取的圖像特征是圖像的局部特征，其對圖像的旋轉(zhuǎn)、縮放保持不變性，對光照改變和攝像機角度變化具有部分的不變性。以下給出算法實現(xiàn)的主要過程。

步驟2 關(guān)鍵點定位。檢測到的極值點作為侯選點，對位置、尺度、彎曲度等做擬合，篩除所有低對比度和定位差邊緣附近的點，同時對尺度空間函數(shù)D（x，y，σ）做泰勒展開得到關(guān)鍵點，計算二階Hessian矩陣得出主曲率。

步驟3 設(shè)定主方向并建立描述向量。將以特征點為中心的16×16鄰域分成4×4的像素塊，建立梯度方向直方圖，每個直方圖包含8個特征，得到4×4×8=128維的特征描述向量。

實驗表明，計算圖像特征點的128維描述向量占用了SIFT算法80%以上的計算時間，為提高算法的實時性，采用PCA（主成分分析）降維技術(shù)加以改進，不使用梯度直方圖而用主成分分析法將梯度面片歸一化，將128維描述向量降低到36維，因而大大減少了計算量。

2 基于KD樹的特征匹配

利用SIFT特征，將查詢圖像的特征描述向量與圖像庫的所有特征進行比較，特征匹配數(shù)目最多的幾張圖像即為查詢結(jié)果。特征描述向量的匹配性采用歐氏距離度量，匹配過程相當(dāng)于在兩個特征集合中搜索距離最近的特征點的過程。常用的搜索過程有兩種：一種是線性掃描，將一個特征描述向量與數(shù)據(jù)庫中的所有向量逐一比較，這種方法實現(xiàn)簡單但效率較低，時間復(fù)雜度為0（N），N為數(shù)據(jù)庫中向量的數(shù)目；另一種是先建立數(shù)據(jù)索引，再對特征描述向量進行匹配。

2.1 KD樹的構(gòu)建

KD樹是K維二叉索引樹，是用于多維檢索的樹形數(shù)據(jù)結(jié)構(gòu)。它的每一層將空間分成兩個子空間，頂層結(jié)點按一維劃分，下一層結(jié)點按另一維劃分，以此類推，直至一個結(jié)點中的數(shù)據(jù)量少于設(shè)定的上限為止。KD樹的搜索時間復(fù)雜度為0（log2N），其具有如下性質(zhì)：

⑴ 若它的左子樹不為空，則左子樹上所有結(jié)點第d維的值均小于它的根結(jié)點第d維的值；

⑵ 若它的右子樹不為空，則右子樹上所有結(jié)點第d維的值均大于等于它的根結(jié)點第d維的值；

⑶ 它的左右子樹也分別是KD樹。

計算圖像庫中所有SIFT特征描述向量在每個維度上的數(shù)據(jù)方差，共得到36個方差，KD樹的維度分區(qū)沿著數(shù)據(jù)項方差最大的方向，該方向上數(shù)據(jù)最分散，進行空間分割會有較好的分辨率，有利于提高發(fā)現(xiàn)最近鄰的可能性。

2.2 KD樹近似最近鄰搜索

KD樹對于給定的多維目標(biāo)點，進行快速二分查找得到其近似最近鄰點，搜索過程如下：

⑴ 根據(jù)輸入的k維數(shù)據(jù)點建立KD樹；

⑵ 利用優(yōu)先隊列，用目標(biāo)點搜索比較整個KD樹，找到m個最近鄰的點，從其根結(jié)點掃描到葉結(jié)點，錯過的結(jié)點放入優(yōu)先隊列，再從隊列中取出當(dāng)前維度上距離最小的點，重復(fù)掃描到葉子結(jié)點，直到隊列為空或掃描次數(shù)達(dá)到設(shè)定上限；

⑶ 分別計算最近鄰點和次近鄰點到目標(biāo)點的歐氏距離，若最近距離除以次近距離的比值小于設(shè)定的比例閾值，則選擇該最近鄰點作為搜索結(jié)果，若沒有找到，則返回空。

3 大型KD樹混合存儲模式

傳統(tǒng)的KD樹要求將所有的數(shù)據(jù)項都加載到內(nèi)存，這將限制海量圖像數(shù)據(jù)匹配的應(yīng)用規(guī)模，為此，本文提出了一種大型KD樹混合結(jié)構(gòu)，來解決有限內(nèi)存環(huán)境下的圖像匹配問題。我們將所有圖像的SIFT特征描述向量及對應(yīng)的圖像ID信息保存為一個外部文件F，后續(xù)過程將針對文件F來實施基于硬盤的KD樹構(gòu)造和最近鄰搜索。

3.1 基于硬盤的KD樹構(gòu)造

外部文件F中存有N個36維數(shù)據(jù)項，需構(gòu)造一棵KD樹來索引這些數(shù)據(jù)項，構(gòu)造過程中數(shù)據(jù)項被加載到內(nèi)存執(zhí)行，目的是根據(jù)數(shù)據(jù)項計算并選擇分區(qū)方向軸，且計算這些數(shù)據(jù)項在分區(qū)軸上投影的中值點。假設(shè)有限內(nèi)存環(huán)境下最多只有m個數(shù)據(jù)項可被加載到內(nèi)存，則改進后的大型KD樹混合結(jié)構(gòu)如圖1所示。

圖1假設(shè)m=N/4，即在構(gòu)造KD樹時，任何時候最多只有N/4的數(shù)據(jù)項可被加載到內(nèi)存。在樹的最上面兩層（黑色結(jié)點），每個結(jié)點分支下索引的數(shù)據(jù)項數(shù)量超過了m，因此這些結(jié)點在硬盤上構(gòu)造；第三層以下（白色結(jié)點），每個結(jié)點分支下的索引數(shù)據(jù)項數(shù)量不到m，可在內(nèi)存中構(gòu)造。由于KD樹是一種平衡二叉樹，可以推知第0層（根結(jié)點）到第log2（N/M）-1層中每個結(jié)點索引的數(shù)據(jù)項都超過m，所以對這些結(jié)點使用基于硬盤的方法來構(gòu)造。具體來講，構(gòu)造第0到第log2（N/M）-1層時，隨機抽樣硬盤上的m個數(shù)據(jù)項即一個數(shù)據(jù)子集，加載到內(nèi)存后進行近似分區(qū)軸操作，分區(qū)軸選擇采樣數(shù)據(jù)項具有最大差異的坐標(biāo)軸。計算數(shù)據(jù)項投影并選擇中間值時，為保持KD樹的平衡，當(dāng)前結(jié)點下所有數(shù)據(jù)項應(yīng)被平分，外部文件F中所有相關(guān)數(shù)據(jù)項都要被計算，但內(nèi)存中只存放計算出的數(shù)據(jù)項投影，因此不會超出容量限制。當(dāng)遞歸構(gòu)造到達(dá)log2（N/M）層時，KD樹轉(zhuǎn)入內(nèi)存構(gòu)造過程，所有相關(guān)數(shù)據(jù)項都可被加載到內(nèi)存中構(gòu)造當(dāng)前結(jié)點的整個子樹。遞歸過程采用深度優(yōu)先的方式，一個結(jié)點的整個子樹構(gòu)造后，分配給這些數(shù)據(jù)項的內(nèi)存被立即釋放。KD樹葉結(jié)點的內(nèi)容不是特征向量數(shù)據(jù)，而是指向硬盤上數(shù)據(jù)項的一個指針。

上述KD樹的混合構(gòu)造方式會導(dǎo)致頂層分區(qū)軸的選擇可能不是最優(yōu)的，但經(jīng)過試驗證明，這種近似的影響很小。在區(qū)間{N，0.9N，…，0.1N}變換m的值，由此產(chǎn)生的大型KD樹結(jié)構(gòu)相同，直到m減少到0.01N時，構(gòu)造結(jié)果才出現(xiàn)不同。這是因為：首先，基于硬盤的過程只用于構(gòu)建KD樹的上層，即使m小到N/16，近似也只發(fā)生在最上面4層的15個結(jié)點；其次36維特征向量是分布在一個低維特征空間上的，維度之間的差異性本來就比較大，因此特征向量在KD樹的上層空間差異足夠明顯，足以抵消近似分區(qū)的影響。

3.2 大型KD樹的實現(xiàn)

KD樹是平衡二叉樹，因此可用數(shù)組來表示：樹中的結(jié)點以深度優(yōu)先的方式存儲在一個有2N個元素的數(shù)組中，其中N是被KD樹索引的數(shù)據(jù)項的數(shù)量；結(jié)點i的兩個子結(jié)點位于數(shù)組中2i和2i+1的位置。樹的每個內(nèi)結(jié)點上保存分區(qū)軸編號（1個字節(jié)，存儲整數(shù)1到36）和截斷值（4字節(jié)浮點數(shù)）。每個葉結(jié)點上保存指向特征描述向量的索引（每個索引4字節(jié)）。內(nèi)結(jié)點的數(shù)量和葉結(jié)點的數(shù)量都小于等于N，KD樹總共用約（1+4）N個字節(jié)存儲內(nèi)結(jié)點和4N個字節(jié)存儲葉結(jié)點，共占用約9N字節(jié)的內(nèi)存。被KD樹索引指向的特征描述向量大小為144N個字節(jié)（每個SIFT特征描述向量有36個浮點數(shù)）。通過將特征描述向量駐留在硬盤上，KD樹的內(nèi)存消耗從（144+9）N減少到9N。

在1GB內(nèi)存環(huán)境中，一個傳統(tǒng)KD樹要求所有的描述向量駐留在內(nèi)存中，只能索引約700萬描述向量（不到5000張常規(guī)尺寸的圖像），而本文的大型KD樹可以索引超過1億個描述向量（約8萬張圖像），系統(tǒng)的可擴展性顯著提高。

3.3 基于硬盤的近似最近鄰搜索

傳統(tǒng)的最近鄰搜索將數(shù)據(jù)庫所有特征描述向量駐留于內(nèi)存，以便快速地隨機存取（每次耗時10-4ms）并計算距離。大型KD樹索引的特征向量存放于硬盤，如果仍按隨機訪問的方式來存取數(shù)據(jù)（每次耗時10ms），最近鄰搜索的效率會很低。假設(shè)每個查詢特征向量最近鄰搜索s個數(shù)據(jù)庫特征后停止，當(dāng)s=200時，處理該查詢隊列會在I/O上花費2秒，當(dāng)處理1張有1500個特征點的圖像時，查詢隊列的存取時間將達(dá)到50分鐘，這甚至比依次精確比對圖像庫的速度還要慢。

改進后的硬盤最近鄰搜索將單個的硬盤隨機訪問優(yōu)化為批量順序訪問硬盤[3]（如圖2所示）。每次批量處理Q個查詢圖像，每個查詢圖像的每個特征點從大型KD樹獲取200個候選匹配特征。在此過程中不執(zhí)行候選特征匹配的距離測試，而是先放入內(nèi)存中緩沖，因而沒有觸發(fā)隨機硬盤訪問。當(dāng)搜索完所有Q個查詢圖像的候選匹配特征后，對指向硬盤上特征向量的索引進行統(tǒng)一排序，并按硬盤順序掃描來對其訪問。

試驗中，筆者根據(jù)經(jīng)驗設(shè)置Q=100，共有100×1500×200=3000萬個候選匹配特征，順序掃描外部文件F大約需要50秒。一個特征描述向量的平均硬盤訪問時間從單個隨機訪問時的10 ms，下降為50秒/3000萬≈2×10-3ms。相應(yīng)地，查詢一張圖像的I/O處理時間從50分鐘顯著下降為0.5秒。增大Q的值將進一步減少特征描述向量的平均訪問時間，但也同時增加了用于KD樹遍歷和數(shù)值計算的內(nèi)存消耗，查詢處理的瓶頸從硬盤轉(zhuǎn)移到內(nèi)存，因此Q的值不宜無限增加。

對所有候選匹配特征進行距離測試后，可獲得查詢圖像隊列Q和數(shù)據(jù)庫圖像的一組魯棒特征匹配，最終通過匹配特征的數(shù)量來確定兩幅圖像的相似性。

4 實驗結(jié)果與分析

為評估大型KD樹的圖像匹配性能，本文比較了大型KD樹與廣泛采用的詞匯樹方法[4]在圖像匹配時的查準(zhǔn)率和查全率，證明了大型KD樹的優(yōu)越性能。

4.1 實驗環(huán)境

本文的實驗對象為一個有1萬張圖像的圖像庫，每個圖像包含約1500個SIFT特征，每個特征是一個36維的向量，圖像庫共有1500萬個特征，存儲該圖像庫特征描述向量的外部文件占用了1500萬×144≈2GB硬盤空間。

⑴ 大型KD樹的近似圖像匹配。近似圖像匹配過程參照第3節(jié)的方法，構(gòu)造大型KD樹時，假設(shè)內(nèi)存限制m=0.1N，其中N是圖像庫特征描述向量的數(shù)量。在最近鄰居搜索中，設(shè)置s=200（每次查詢訪問的數(shù)據(jù)庫特征數(shù)量）和Q=100（一批處理的查詢圖像數(shù)量）。匹配結(jié)果由兩個圖像間匹配的特征數(shù)量決定。

⑵ 基于詞匯樹的近似圖像匹配。作為對比，本文同時使用廣泛應(yīng)用的詞匯樹方法進行近似圖像匹配。把所有圖像的SIFT特征描述向量進行分層聚類后構(gòu)造成一個分支系數(shù)為10、深度為6的詞匯樹，從而獲得一個有106=100萬個視覺單詞的字典。查詢特征描述向量通過遍歷詞匯樹量化成視覺單詞，每個圖像被轉(zhuǎn)換為一組視覺單詞，生成一個100萬維的稀疏特征向量。最后，以兩幅圖像詞匯特征向量之間的曼哈頓距離來判斷圖像相似度，距離越遠(yuǎn)，相似度越小。在計算距離時，特征向量里的每一維特征描述子都用對應(yīng)視覺單詞的熵加以權(quán)重。

4.2 實驗結(jié)果

對實驗圖像庫分別使用精確匹配和近似匹配，統(tǒng)計數(shù)據(jù)如表1所示。可以看到近似匹配獲得的匹配特征比精確匹配少了約90%，但近似匹配的速度快了約400倍，因為它只檢索了精確匹配特征對的一小部分，約0.02%。在實際應(yīng)用中，近似匹配時相對稀少的匹配特征數(shù)量并不影響匹配效果，因為兩幅真正相似的圖像往往有幾百個匹配的特征，而兩個不相似的圖像間最多只有幾個匹配的特征，所以即使失去了很多匹配特征，這種方法仍然能夠把相似和不相似的圖像配對區(qū)分開。

5 結(jié)束語

針對海量圖像匹配的效率瓶頸，本文提出大型KD樹混合存儲模式及其近似最近鄰搜索方法，有效地減少了圖像特征匹配的計算量，提高了圖像匹配的速度和圖像庫的可擴展性。除SIFT特征外，該技術(shù)同樣適用于其他圖像特征的匹配，甚至適用于其他類型的海量多維信息匹配應(yīng)用。這一技術(shù)方法具有廣泛的應(yīng)用價值。

參考文獻：

[1] 李宏榮，李曉明.基于SIFT，PCA-SIFT和SURF特征檢測方法的研究[J].太原師范學(xué)院學(xué)報（自然科學(xué)版），2012.

[2] 杜振鵬，李德華.基于KD-Tree搜索和SURF特征的圖像匹配算法研究[J].計算機與數(shù)字工程，2012.

[3] Ke Yan， Sukthankar R， Huston L. An efficient parts-basednear-duplicate and sub-image retrieval system[C].New York：MULTIMEDIA '04 Proceedings of the 12th annual ACM international conference on Multimedia，2004.

[4] Nister D， Stewenius H. Scalable recognition with a vocabulary tree[C].New York：IEEE Conference on Computer Vision and Pattern Recognition，2006.