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

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

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

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

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

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

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

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

隨著計算機技術的快速發展，圖像匹配[1]逐漸成為計算機機器視覺的一個重要研究方向，目前廣泛應用在數字圖像安全、空間探測、醫學圖像分析、虛擬現實技術、遙感圖像處理、無線傳感器網絡和機器視覺等領域。

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

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

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

1 壓縮感知概述

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

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

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

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

2 自適應閾值序貫相似性檢測（SSDA）算法

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

自適應閾值SSDA算法是對傳統SSDA匹配算法的一種改進，其實現原理及步驟如下：

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

1）定義絕對誤差值ε

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

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

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

3 SIFT算法流程[12-14]

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

3.1 特征點的檢測

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

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

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

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

3.2 特征點的精確定位

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

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

3.3 特征點的方向

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

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

3.4 特征點的描述

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

4 SIFT算法的改進

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

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

算法描述：

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

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

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

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

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

4）確定最小閾值。通過自適應閾值SSDA匹配算法確定最小閾值t，其實現如圖2所示。

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

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

5 算法仿真及結果分析

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

圖3 目標圖像和待匹配圖像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

本文還對目標圖像進行逆時針旋轉30°與待匹配圖像進行匹配，圖7為特征點匹配圖像，圖8為匹配效果圖。

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

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

本文與以下幾種經典的匹配算法從特征點檢測數量、匹配點數量、算法時間和準確率上來衡量這幾種算法的優越性，如表1所示。

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

從表1發現，本文算法從特征點的數量和匹配點的數量上都少于傳統的SIFT算法，耗時與準確度上也優于其他幾種經典的匹配算法，這說明本文算法的匹配精度更高、匹配速度更快。

6 結論和展望

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

[1]王軍，張明柱.圖像匹配算法的研究進展[J].大氣與環境光學學報，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]俞輝，侯在克，何旭莉.一種基于輪廓特征的圖像拼接算法設計與實驗[J].石油大學學報：自然科學版，2003，27（2）：114-118.

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

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

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

[8]王麗丹，華順剛，劉紅衛.自適應閾值SSDA圖像匹配拼接算法的研究[J].光學技術應用，2006，21（3）：54-58.

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

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

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

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

[13]郝勇，戴芳，黎瑩.位平面和SIFT相結合的圖像匹配方法[J].計算機工程與應用，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]王松林，項欣光.基于壓縮感知的多特征加權目標跟蹤算法[J].計算機應用研究，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

(責任編輯 姜紅貴)

2015-05-04

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

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