謝 昕，徐 殷，熊煥東，李 波，胡鋒平

（華東交通大學(xué)1.信息工程學(xué)院；2.土木建筑學(xué)院，江西 南昌330013）

基于壓縮感知的SIFT圖像匹配算法的研究

謝 昕1，徐 殷1，熊煥東1，李 波1，胡鋒平2

（華東交通大學(xué)1.信息工程學(xué)院；2.土木建筑學(xué)院，江西 南昌330013）

針對尺度不變特征變換（SIFT）算法的計算量大、速度慢等缺點，提出了一種融合壓縮感知的圖像匹配算法。首先對目標(biāo)圖像和待匹配圖像進行預(yù)處理，利用壓縮感知技術(shù)進行圖像壓縮，結(jié)合SIFT算法提取圖像的特征點，通過自適應(yīng)閾值序貫相似性檢測（SSDA）匹配算法進行圖像快速匹配搜索，從而找到最佳匹配位置。

尺度不變特征變換；壓縮感知；序貫相似性檢測算法；自適應(yīng)閾值

隨著計算機技術(shù)的快速發(fā)展，圖像匹配[1]逐漸成為計算機機器視覺的一個重要研究方向，目前廣泛應(yīng)用在數(shù)字圖像安全、空間探測、醫(yī)學(xué)圖像分析、虛擬現(xiàn)實技術(shù)、遙感圖像處理、無線傳感器網(wǎng)絡(luò)和機器視覺等領(lǐng)域。

近年來，國內(nèi)外許多研究學(xué)者相繼提出了多種圖像匹配算法。1988年Harris C提出了Harris角點圖像匹配算法[2]，該算法圖像配準(zhǔn)精度較高且計算量小，并且對圖像的旋轉(zhuǎn)沒有限制，但對于圖像邊緣信息少的匹配效果不太理想。2004年Lowe David G提出了SIFT（scale invariant feature transform）特征點匹配算法[3]，該算法具有旋轉(zhuǎn)、縮放以及仿射不變性等特點，雖然能夠保持一定程度上的穩(wěn)定性，但存在誤匹配現(xiàn)象。上述兩種方法只能完成一些特定條件下的圖像匹配且匹配的效率不高，對于在復(fù)雜環(huán)境下的圖像匹配還有待進一步提高。

2003年俞輝等人提出了基于輪廓特征的圖像匹配算法，利用輪廓特征有效解決了圖像旋轉(zhuǎn)的問題[4]，同時也改善了光照的影響，但該算法中輪廓特征的提取易受噪聲的干擾，不適于有噪聲影響和輪廓不明顯的圖像。2005年王立新等人設(shè)計了一種快速高效的圖像匹配算法[5]，使用序貫相似性檢測（sequential similarity detection algorithm，SSDA）算法設(shè)置閾值進行圖像匹配，該算法的匹配效率較高且易于實現(xiàn)，但該算法閾值的適當(dāng)選取存在較大困難，且對圖像的明暗度、尺度旋轉(zhuǎn)等變化較為敏感。2011年曾巒等人采用了改進的SIFT特征提取和匹配算法[6]，通過采用SIFT描述向量之間的歐式距離最小值與次小值的比值作為閾值，對圖像先進行粗匹配，再利用匹配結(jié)果對主方向角度差直方圖去除偽匹配，有效解決了圖像匹配閾值的選擇問題且算法穩(wěn)定、可靠，但該匹配算法耗時太長，對大圖像的處理效果也不太理想。

針對上述問題，本文引入壓縮感知[7]進行空間變換信號描述，在保證信號足夠重構(gòu)的前提下，對數(shù)據(jù)進行壓縮，利用SIFT算法提取圖像的特征點，結(jié)合自適應(yīng)閾值序貫相似性檢測[8－9]匹配算法進行圖像快速匹配，從而找到最佳匹配位置。

1 壓縮感知概述

文獻[10-11]指出，設(shè)X是RN空間（RN空間的任何信號都可以用N×1維的基向量的線性組合表示）一維的可壓縮信號。信號X∈RN通過正交基所描述的變化系數(shù)向量可以表示為

其中：Ψ為正交變換基組成的N×N變換域矩陣；Θ是Ψ的等價或逼近的稀疏表示。

設(shè)計一個平穩(wěn)的、與變換基不相關(guān)的觀測矩陣Φ，其大小為M×N（M?N）維，對Θ進行觀測得到觀測向量Y=ΦΘ或Y=ΦΨTΘ。該過程也可以描述為信號X通過矩陣ACS（ACS＝ΦΨT）進行自適應(yīng)觀測

其中：ACS稱為傳感因子；Y是一個M×1維的觀測集合，由于Y中包含了每個信號的特有信息，因此不同的信號所對應(yīng)的Y值也不同，對于信號是圖像的情況，可以將壓縮后的數(shù)據(jù)Y做為圖像的特征表示。

2 自適應(yīng)閾值序貫相似性檢測（SSDA）算法

SSDA算法是1972年由Bamea D I和Silverman H F等人提出的一種著名的圖像匹配算法。該算法能對不匹配的點進行快速丟棄，大大減少了匹配的計算量，從而使匹配速度得到很大提高，該算法容易實現(xiàn)且匹配速度快。

自適應(yīng)閾值SSDA算法是對傳統(tǒng)SSDA匹配算法的一種改進，其實現(xiàn)原理及步驟如下：

設(shè)目標(biāo)圖像S的大小為N×N，待匹配圖像T的大小為M×M，待匹配圖像疊放在目標(biāo)圖像上平移，待匹配圖像覆蓋下的那塊目標(biāo)圖像設(shè)為子圖Si,j，（i，j）為這塊子圖的左上角點在目標(biāo)圖像S中的坐標(biāo)，（m，n）為待匹配圖像上每個像素點的坐標(biāo)，則有：1≤i，j≤N-M+1，且0≤m，n≤M。

1）定義絕對誤差值ε

2）把目標(biāo)圖像S的左上角點作為起始點，開始計算待匹配圖像T與待匹配圖像覆蓋下的那塊目標(biāo)子圖像Si,j之間匹配的累計誤差，并將其值作為自適應(yīng)閾值的初始值t0，然后按照行列順序依次選擇進行匹配檢測。

3）從第二點開始，在目標(biāo)圖像區(qū)域內(nèi)每次以隨機不重復(fù)的順序選取像素點進行匹配，計算待匹配圖像與該位置子圖像中的對應(yīng)像素點的累積誤差，記為t。將t與t0進行比較，若t≥t0，則立即停止對該目標(biāo)模塊的計算，并將子圖像移動到下一個位置并進行計算t；若t＜t0，則用t更新閾值t0，并記錄下該目標(biāo)子圖像左上角像素點的坐標(biāo)位置，即

4）按照上述步驟依次搜索整個目標(biāo)圖像，得到誤差累加和最小的值，即為最小閾值。

3 SIFT算法流程[12-14]

SIFT算法利用金字塔和高斯核濾波差分在尺度空間中尋找極值點，并提取圖像的特征點進行局部特征匹配，主要流程如下：

3.1 特征點的檢測

根據(jù)Tony Lindeberg理論可知，高斯函數(shù)作為唯一的尺度空間內(nèi)核函數(shù)，通過一個尺度可變的高斯函數(shù)G（x，y,σ）與原始圖像I（x，y）來構(gòu)造一個圖像的尺度空間函數(shù)L（x，y,σ）

其中：*表示卷積運算；σ是圖像的尺度空間因子，其值越小表示圖像被平滑的越少，相應(yīng)的尺度越小。

為了在尺度空間中更有效地檢測出穩(wěn)定的特征點，可使用高斯函數(shù)D（x，y,σ）來進行尺度近似歸一化處理

其中：k為閾值。在高斯尺度空間中，通過高斯平滑和降采樣處理，每個像素點和同一層的8個相鄰點及上下相鄰層的各9個相鄰點共26個像素點進行比較，得到尺度空間和圖像空間的局部極值點，并記為局部特征點。

3.2 特征點的精確定位

可以通過Hessian矩陣來精確定位特征點的位置和尺度，Hessian矩陣為：，則該點的穩(wěn)定性E為

其中：r為控制特征值大小的參數(shù)。

3.3 特征點的方向

通過特征點鄰域像素的梯度方向分布來確定特征點的方向，特征點的梯度幅值m（x，y）和方向θ（x，y）計算公式如下

其中：L表示檢測的特征點的尺度，上述方法可以使SIFT特征點具有旋轉(zhuǎn)不變形。

3.4 特征點的描述

每個特征點都具有位置、方向、尺度3個信息，以特征點為中心均勻分成4×4個鄰域子塊，每個子塊形成一個像素點，每個像素點含有8個方向的信息向量，即每個特征點可以得到128個方向特征描述。因此這128個特征向量可以準(zhǔn)確地描述所有特征點。

4 SIFT算法的改進

首先對待匹配圖像和目標(biāo)圖像進行預(yù)處理，利用壓縮感知技術(shù)快速的得到兩幅圖像的局部特征，然后利用SIFT算法進行特征點提取，結(jié)合自適應(yīng)閾值SSDA算法進行圖像匹配,從而找到最佳匹配位置。改進后的算法流程如圖1所示。

圖1 改進后的圖像匹配算法流程圖Fig.1 The improved image matching algorithm flow

算法描述：

1）預(yù)處理操作。由于在獲取圖像過程中可能會受到噪聲等因素干擾，為了避免這些因素對本算法的影響，本文對讀入的目標(biāo)圖像T和待匹配圖像S進行預(yù)處理操作，比如去噪、二值化處理等。

2）壓縮感知獲取圖像局部特征。通過對預(yù)處理后的圖像進行小波變換，得到稀疏的小波變換系數(shù)矩陣，通過設(shè)計合適的稀疏隨機觀測矩陣對P其進行觀測，從而可以得到數(shù)據(jù)量遠小于原信號或圖像維數(shù)N的M個觀測值（M?N）。根據(jù)文獻[15]采用的稀疏隨機觀測矩陣P定義如下

其中：s通過隨機概率在2～4之間[16]。因此，利用壓縮感知可以快速準(zhǔn)確獲取圖像特征并對圖像進行壓縮。

3）SIFT算法提取特征點。利用SIFT算法分別對2幅圖像進行特征點描述，然后進行特征點提取及匹配。特征點匹配以2個特征點描述符之間的歐式距離作為相似度準(zhǔn)則。假設(shè)特征點對和的特征描述符分別為da和db，則其歐式距離定義為

采用K-D樹（二叉樹的一種，K維數(shù)據(jù)結(jié)構(gòu)）進行優(yōu)先搜索，查找出目標(biāo)子圖像與待匹配圖像中特征點p歐式距離最近和次近的2個相連特征點p'和p",然后計算p和p'，p和p"兩組描述符之間歐式距離的比值r。

4）確定最小閾值。通過自適應(yīng)閾值SSDA匹配算法確定最小閾值t，其實現(xiàn)如圖2所示。

圖2 確定最小閾值流程圖Fig.2 The flow of minimum threshold

5）圖像匹配。將r與閾值t進行比較,如果r≤t，則匹配成功，即找到最佳匹配位置；否則讓待匹配圖像在目標(biāo)圖像上進行行列平移一個位置，直到搜索完目標(biāo)圖像為止。

5 算法仿真及結(jié)果分析

為了驗證算法的可行性時，本文選取了經(jīng)典的lena圖像作為目標(biāo)圖像，lena圖像中的一小部分圖像作為待匹配圖像，如圖3所示，2幅圖像的大小分別為512×512和64×64。圖4為2幅匹配圖像通過本文算法所提取的匹配點圖像，圖5為特征點匹配圖像，圖6為最后的匹配效果圖像。

圖3 目標(biāo)圖像和待匹配圖像Fig.3 Original image

圖4 提取的匹配點圖像Fig.4 Extraction of image matching point

圖5 特征點匹配圖像Fig.5 Feature points matching images

圖6 匹配效果圖Fig.6 Effect image after matching

本文還對目標(biāo)圖像進行逆時針旋轉(zhuǎn)30°與待匹配圖像進行匹配，圖7為特征點匹配圖像，圖8為匹配效果圖。

圖7 特征點匹配圖像Fig.7 Feature points matching images

圖8 匹配效果圖Fig.8.Effect image after matching

本文與以下幾種經(jīng)典的匹配算法從特征點檢測數(shù)量、匹配點數(shù)量、算法時間和準(zhǔn)確率上來衡量這幾種算法的優(yōu)越性，如表1所示。

表1 幾種匹配算法的比較Tab.1 The comparison of several kinds of matching algorithm

從表1發(fā)現(xiàn)，本文算法從特征點的數(shù)量和匹配點的數(shù)量上都少于傳統(tǒng)的SIFT算法，耗時與準(zhǔn)確度上也優(yōu)于其他幾種經(jīng)典的匹配算法，這說明本文算法的匹配精度更高、匹配速度更快。

6 結(jié)論和展望

本文在傳統(tǒng)的SIFT算法的基礎(chǔ)上，提出了一種新的基于壓縮感知圖像匹配算法。不僅大大減少了與圖像匹配無關(guān)的特征點，使特征點匹配更精確，又能讓圖像匹配速度更快。通過仿真實驗結(jié)果表明，本文算法在匹配準(zhǔn)度與匹配時間上都得到比較滿意的效果，能夠滿足機器視覺系統(tǒng)的實時處理要求。但是對于彩色圖像的匹配不太穩(wěn)定，還需要進一步的研究。

[1]王軍，張明柱.圖像匹配算法的研究進展[J].大氣與環(huán)境光學(xué)學(xué)報，2007，2(1)：11-15.

[2]HARRIS C，STEPHENS M.A combined corner and edge detector[C]//Proc of Alvey Conf Vision.England:Manchester University Press，1988：189-192.

[3]LOWE D G.Distinctive image features from scale invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[4]俞輝，侯在克，何旭莉.一種基于輪廓特征的圖像拼接算法設(shè)計與實驗[J].石油大學(xué)學(xué)報：自然科學(xué)版，2003，27（2）：114-118.

[5]王立新，劉彤宇，李陽.SSDA匹配算法的研究及實現(xiàn)[J].光電技術(shù)應(yīng)用，2005，20（3）：53-55.

[6]曾巒，王元欽，譚久彬.改進的SIFT特征提取和匹配算法[J].光學(xué)精密工程，2011，19（6）：391-1396.

[7]DONOHO D L.Compressed sensing[J].Information Theory，2006，52（4）：1289-1306.

[8]王麗丹，華順剛，劉紅衛(wèi).自適應(yīng)閾值SSDA圖像匹配拼接算法的研究[J].光學(xué)技術(shù)應(yīng)用，2006，21（3）：54-58.

[9]張維琪，樊斐.自適應(yīng)SSDA圖像處理匹配并行算法設(shè)計與實現(xiàn)[J].計算機工程與用，2014，50（20）：64-68.

[10]石光明，劉丹華，高大化.壓縮感知理論及研究進展[J].電子學(xué)報，2009，37（5）：1070-1081.

[11]郭厚焜，吳峰，黃萍.基于壓縮感知和字典學(xué)習(xí)的背景差分法[J].華東交通大學(xué)學(xué)報，2012，29（1）：43-47.

[12]白廷柱，侯喜報.基于SIFT算子的圖像匹配算法研究[J].北京理工大學(xué)報，2013，33（6）：622-628.

[13]郝勇，戴芳，黎瑩.位平面和SIFT相結(jié)合的圖像匹配方法[J].計算機工程與應(yīng)用，2013，49（8）：191-194.

[14]QIU WENTAO，ZHAO JIAN，LIU JIE.Image matching combine SIFT with regional SSDA[J].International Conference on Control Engineering and Communication Technology,2012,78：177-179.

[15]ZHANG K H，ZHANG L，YANG M H.Real-time compressive tracking[C]//European Conference on Computer Vision，2012：89-99.

[16]王松林，項欣光.基于壓縮感知的多特征加權(quán)目標(biāo)跟蹤算法[J].計算機應(yīng)用研究，2014，3(3)：929-932.

Research on SIFT Image Matching Algorithm Based on Compressed Sensing

Xie Xin1，Xu Yin1，Xiong Huandong1，Li Bo1，Hu Fengping2
(1.School of Information Engineering，East China Jiaotong University，Nanchang 330013，China；2.School of Civil Engineering and Architecture East China Jiaotong University，Nanchang 330013，China)

Aiming at the disadvantages of massive calculation and slow speed of traditional scale invariant feature transform(SIFT)algorithm,this paper proposes an improved image matching method which combines compressed sensing(CS)algorithm.Firstly,target images and images to be matched are preprocessed and compressed by using compressed sensing technology.Then,image feature points are extracted in combination with SIFT algorithm. Finally,sequential similarity detection algorithm (SSDA)with adaptive threshold is used for fast search of image matching to find an optimal matching position,and a matching image is obtained.Experimental results demonstrate that the method realizes fast image matching,efficiently overcomes the shortcomings of heavy computation and low efficiency in the process of extracting image features,and guarantees the matching accuracy and efficiency,which meets the real-time requirements in machine vision system.

scale invariant feature transform;compressed sensing;sequential similarity detection algorithm; adaptive threshold value

TP391.9

A

1005-0523（2015）06-0115-07

(責(zé)任編輯 姜紅貴)

2015-05-04

國家自然科學(xué)基金項目（61272197）；江西省自然科學(xué)基金（20132BAB201027,20142BAB207007）；江西省科技廳工業(yè)支撐計劃（20151BBE50055）；贛鄱英才555工程領(lǐng)軍人才培養(yǎng)計劃（S2013-57）；江西省研究生創(chuàng)新專項基金項目（YC2015S254）

謝昕（1969—），男，教授，研究方向為機器視覺和網(wǎng)絡(luò)與信息安全。