張小莉

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

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

中圖分類(lèi)號(hào)：TP391.4 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

1 圖像特征提取

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

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

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

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

2 基于KD樹(shù)的特征匹配

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

2.1 KD樹(shù)的構(gòu)建

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

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

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

⑶ 它的左右子樹(shù)也分別是KD樹(shù)。

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

2.2 KD樹(shù)近似最近鄰搜索

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

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

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

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

3 大型KD樹(shù)混合存儲(chǔ)模式

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

3.1 基于硬盤(pán)的KD樹(shù)構(gòu)造

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

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

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

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

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

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

3.3 基于硬盤(pán)的近似最近鄰搜索

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 實(shí)驗(yàn)環(huán)境

本文的實(shí)驗(yàn)對(duì)象為一個(gè)有1萬(wàn)張圖像的圖像庫(kù)，每個(gè)圖像包含約1500個(gè)SIFT特征，每個(gè)特征是一個(gè)36維的向量，圖像庫(kù)共有1500萬(wàn)個(gè)特征，存儲(chǔ)該圖像庫(kù)特征描述向量的外部文件占用了1500萬(wàn)×144≈2GB硬盤(pán)空間。

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

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

4.2 實(shí)驗(yàn)結(jié)果

對(duì)實(shí)驗(yàn)圖像庫(kù)分別使用精確匹配和近似匹配，統(tǒng)計(jì)數(shù)據(jù)如表1所示?？梢钥吹浇破ヅ浍@得的匹配特征比精確匹配少了約90%，但近似匹配的速度快了約400倍，因?yàn)樗粰z索了精確匹配特征對(duì)的一小部分，約0.02%。在實(shí)際應(yīng)用中，近似匹配時(shí)相對(duì)稀少的匹配特征數(shù)量并不影響匹配效果，因?yàn)閮煞嬲嗨频膱D像往往有幾百個(gè)匹配的特征，而兩個(gè)不相似的圖像間最多只有幾個(gè)匹配的特征，所以即使失去了很多匹配特征，這種方法仍然能夠把相似和不相似的圖像配對(duì)區(qū)分開(kāi)。

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

[2] 杜振鵬，李德華.基于KD-Tree搜索和SURF特征的圖像匹配算法研究[J].計(jì)算機(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.