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

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

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

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

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

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

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

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

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

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

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

1 壓縮感知概述

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

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

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

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

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

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

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

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

1）定義絕對(duì)誤差值ε

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

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

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

3 SIFT算法流程[12-14]

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

3.1 特征點(diǎn)的檢測(cè)

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

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

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

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

3.2 特征點(diǎn)的精確定位

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

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

3.3 特征點(diǎn)的方向

通過(guò)特征點(diǎn)鄰域像素的梯度方向分布來(lái)確定特征點(diǎn)的方向，特征點(diǎn)的梯度幅值m（x，y）和方向θ（x，y）計(jì)算公式如下

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

3.4 特征點(diǎn)的描述

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

4 SIFT算法的改進(jìn)

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

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

算法描述：

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

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

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

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

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

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

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

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

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

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

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

圖4 提取的匹配點(diǎn)圖像Fig.4 Extraction of image matching point

圖5 特征點(diǎn)匹配圖像Fig.5 Feature points matching images

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

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

圖7 特征點(diǎn)匹配圖像Fig.7 Feature points matching images

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

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

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

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

6 結(jié)論和展望

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

[1]王軍，張明柱.圖像匹配算法的研究進(jìn)展[J].大氣與環(huán)境光學(xué)學(xué)報(bào)，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ì)與實(shí)驗(yàn)[J].石油大學(xué)學(xué)報(bào)：自然科學(xué)版，2003，27（2）：114-118.

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

[6]曾巒，王元?dú)J，譚久彬.改進(jìn)的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è)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與用，2014，50（20）：64-68.

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

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

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

[13]郝勇，戴芳，黎瑩.位平面和SIFT相結(jié)合的圖像匹配方法[J].計(jì)算機(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]王松林，項(xiàng)欣光.基于壓縮感知的多特征加權(quán)目標(biāo)跟蹤算法[J].計(jì)算機(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

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

謝昕（1969—），男，教授，研究方向?yàn)闄C(jī)器視覺(jué)和網(wǎng)絡(luò)與信息安全。