夏 杰，李奇安，李 悅，單海歐

（遼寧石油化工大學(xué) 信息與控制工程學(xué)院，遼寧 撫順 113001）

圖像匹配就是運(yùn)用算法將不同條件下攝取的兩幅或多幅圖像在空間上進(jìn)行相互匹配。目前圖像匹配已經(jīng)廣泛地運(yùn)用于社會(huì)多種領(lǐng)域，比如空間物體三維重建、模式識(shí)別以及目標(biāo)物運(yùn)動(dòng)分析等。

傳統(tǒng)的圖像匹配算法計(jì)算量較大，在圖像目標(biāo)發(fā)生旋轉(zhuǎn)、縮放、光照等參數(shù)發(fā)生變化時(shí)適應(yīng)力不強(qiáng)。近年來(lái)，在計(jì)算機(jī)視覺領(lǐng)域中，基于局部不變量描述符的算法在圖像匹配方面取得了令人矚目的進(jìn)展。

David G.Lowe教授提出一種基于尺度空間的、對(duì)圖像縮放、旋轉(zhuǎn)甚至仿射變換保持不變性的圖像局部特征描述算子——SIFT算法[1]。

SIFT算法可以很好地解決旋轉(zhuǎn)和縮放在圖像匹配過(guò)程中的影響，但在實(shí)時(shí)性上存在不足。許多研究人員對(duì)該算法進(jìn)行了改進(jìn)，例如，Yan Ke的 PCA-SIFT方法[2]；Mikolajczy的GLOH算法[3]；劉立等人用圓形窗口的12維向量作為特征描述子的方法[4]；劉健等人采用對(duì)數(shù)極坐標(biāo)變換、信息熵原理提取SIFT特征和不變矩特征，構(gòu)造新型特征描述符進(jìn)行匹配的方法[5]；王曉華等人以街區(qū)距離和棋盤距離的線性組合代替歐式距離作為特征描述符之間的相似性度量的方法[6]。改進(jìn)的算法很多，大多是改進(jìn)特征向量的計(jì)算方法，提高算法速度的方法，但效果不太理想。筆者針對(duì)SIFT算法的不足，提出了以街區(qū)距離代替歐式距離的新方法來(lái)提高SIFT特征匹配效率。

1 SIFT算法簡(jiǎn)介

SIFT算法分為4步，即檢測(cè)尺度空間中的極值點(diǎn)，精確定位檢測(cè)到的極值點(diǎn)位置，為極值點(diǎn)分配方向，生成描述極值點(diǎn)的SIFT特征向量。

1.1 檢測(cè)尺度空間極值點(diǎn)

一幅二維輸入圖像 I（x，y）和尺度可變高斯函數(shù) G（x，y，σ）卷積可得到該輸入圖像的尺度空間 L（x，y，σ）如式（1）。

其中，（x，y）是每個(gè)像素在輸入圖像中的空間坐標(biāo)，符號(hào)*表示卷積，σ是高斯正態(tài)分布的方差，也是尺度空間因子，σ越小，圖像被平滑的越少，尺度也就越小。

不同尺度空間的差分生成高斯差分尺度空間（DOG scale-space），即 D（x，y，σ），DOG 空間可以有效的在尺度空間內(nèi)檢測(cè)到穩(wěn)定的關(guān)鍵點(diǎn)。尺度空間域上的圖像特征點(diǎn)由常數(shù)乘性尺度因子k的相鄰尺度高斯差分與圖像卷積生成：

DOG空間檢測(cè)極值時(shí)，將關(guān)鍵點(diǎn)在同尺度周圍的鄰域8個(gè)像素和上下相鄰對(duì)應(yīng)尺度位置的周圍鄰域9×2個(gè)像素總共26個(gè)像素相互比較。

1.2 精確定位極值點(diǎn)

DOG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng)，對(duì)DOG算子進(jìn)行檢驗(yàn)后，精確定位為特征點(diǎn)。剔除對(duì)噪聲很敏感的點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)后，剩余的特征點(diǎn)匹配能力和抗噪聲能力都比較強(qiáng)。低對(duì)比度的點(diǎn)用擬合三維二次函數(shù)濾除，得到亞像素精度關(guān)鍵點(diǎn)的位置和尺度。

1.3 極值點(diǎn)方向分配

關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性為圖像中的任一關(guān)鍵點(diǎn)確定方向，使算子具備旋轉(zhuǎn)不變性。

像素點(diǎn)的梯度表示為：

式（4）、（5）分別是像素（x，y）處梯度的模值和方向，L 為每個(gè)極值點(diǎn)各自所在的尺度。

1.4 生成SIFT特征向量

任一尺度內(nèi)，以關(guān)鍵點(diǎn)為中心的鄰域內(nèi)進(jìn)行像素采樣，計(jì)算出像素梯度方向的直方圖，轉(zhuǎn)換為128維的特征向量。實(shí)際操作是，以關(guān)鍵點(diǎn)為中心取一個(gè)正方形塊，平均分為8×8的小格，計(jì)算每4×4的小塊上8個(gè)方向的直方圖，產(chǎn)生128個(gè)數(shù)據(jù)，即128維的SIFT特征向量。SIFT特征向量長(zhǎng)度歸一化，可以去除尺度變化、旋轉(zhuǎn)等幾何變形和光照因素的影響。

2 對(duì)特征匹配算法的改進(jìn)

原SIFT算法在特征向量的計(jì)算過(guò)程中，采用主方向旋轉(zhuǎn)并統(tǒng)計(jì)梯度直方圖的方式，生成128維特征向量。圖像特征匹配時(shí)計(jì)算量相當(dāng)龐大，占算法全部時(shí)間的50%左右，直接影響SIFT算法的實(shí)時(shí)性。文中改進(jìn)算法的主要思想是減少特征向量的計(jì)算量，提高特征匹配速度。

原SIFT算法匹配圖像時(shí)，需要一幅圖像中的特征點(diǎn)和另外一幅圖像中的所有特征點(diǎn)進(jìn)行匹配，每一個(gè)特征點(diǎn)有128維數(shù)據(jù)，計(jì)算量之大可想而知。改進(jìn)的SIFT算法是在特征向量匹配中，通過(guò)街區(qū)距離代替歐式距離，通過(guò)極限幾何約束消除多的錯(cuò)誤匹配點(diǎn)對(duì)，減少匹配時(shí)間，提高算法的匹配效率，盡可能地提高SIFT的實(shí)時(shí)性。

原SIFT算法特征向量提取時(shí)，采用歐氏距離函數(shù)作為特征的相似性度量，歐氏距離是兩個(gè)像素之間的直線距離，在二維情況下定義為：

而街區(qū)距離是二維圖像中相應(yīng)情形的推廣距離，即

其中（x1，y1），（x2，y2）分別是兩個(gè)像素的二維坐標(biāo)，比較公式（6）和（7）可看出，L1比 L0計(jì)算量少。用線性組合后的 L1代替L0，可以降低圖像匹配過(guò)程的計(jì)算量，同時(shí)減少計(jì)算的偏差。 定義一個(gè)參數(shù) α，以 αL1代替 L0，即 L0=αL1。 很明顯，L0要進(jìn)行128次乘法和一次開平方的運(yùn)算；而L1只需要一次乘法運(yùn)算。如果圖像中生成128維的SIFT特征點(diǎn)有k個(gè)，則每個(gè)特征點(diǎn)都減少了127 k次計(jì)算。算法改進(jìn)后，圖像匹配的匹配點(diǎn)對(duì)就是兩點(diǎn)間距離最短的特征向量。此方法明顯縮短了運(yùn)算時(shí)間，提高了算法的效率。

3 仿真實(shí)驗(yàn)及結(jié)果分析

本次仿真利用MATLAB7.0編程，運(yùn)行在配置為Pentium（R） Dual－Core CPU E5700 3.0 GHz、2.00 GB RAM、操作系統(tǒng)為Microsoft Windows7的微機(jī)平臺(tái)上。文中選取內(nèi)容和背景比較復(fù)雜的圖像 a（圖 1）和b（圖2），經(jīng)過(guò)多次反復(fù)實(shí)驗(yàn)，測(cè)算出錯(cuò)誤匹配對(duì)、算法時(shí)間和匹配率。匹配的過(guò)程中，對(duì)算法中的值不斷的調(diào)試，經(jīng)過(guò)大量的測(cè)試，最合適的值在0.600～1.500之間。實(shí)驗(yàn)結(jié)果如下，圖1和圖2為原始圖像a和b，在拍攝時(shí)進(jìn)行了相機(jī)平移、轉(zhuǎn)動(dòng)和變焦操作；分別對(duì)原始圖像a和原始圖像b檢測(cè)SIFT特征，圖像a有1 147個(gè)特征點(diǎn)，圖像b有1 032個(gè)特征點(diǎn)；圖3是原SIFT算法匹配的結(jié)果，圖4是改進(jìn)SIFT算法的結(jié)果。圖像匹配的匹配率是SIFT特征對(duì)減去錯(cuò)誤匹配對(duì)后的值除以SIFT特征對(duì)的百分比，比較數(shù)據(jù)如表1所示。

表1 圖像匹配比較數(shù)據(jù)Tab.1 Comparative data of image matching

圖1 原始圖像aFig.1 Original image a

圖2 原始圖像bFig.2 Original image b

圖3 原SIFT算法匹配的結(jié)果Fig.3 Results of the original SIFT algorithm matching

圖4 改進(jìn)SIFT算法匹配的結(jié)果Fig.4 Results of the improved SIFT algorithm matching

對(duì)比后可明顯看出改進(jìn)算法在匹配率上比原SIFT算法高，匹配時(shí)間減少，雖然總的匹配特征對(duì)要少，但對(duì)匹配的結(jié)果影響不大。匹配率增大的同時(shí)，匹配的精度略有提高，圖像的尺度、光照、視角以及噪聲所導(dǎo)致的干擾也隨之降低。本文提出的改進(jìn)圖像匹配特征向量的計(jì)算方法，減少了運(yùn)算時(shí)間，提高了圖像匹配算法的實(shí)時(shí)性。

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

本文研究原SIFT算法后，在特征向量匹配過(guò)程中，用街區(qū)距離代替歐式距離實(shí)現(xiàn)圖像的匹配。實(shí)驗(yàn)結(jié)果達(dá)到了預(yù)定目標(biāo)，在滿足匹配率的同時(shí)，減少了匹配時(shí)間，提高了圖像特征匹配的實(shí)時(shí)性。SIFT算法的可擴(kuò)展性很強(qiáng)，可以輕松地與其他特征檢測(cè)方法相結(jié)合，在今后的研究中，希望可以使用PCA-SIFT、CSIFT、SURF、ASIFT 等算法來(lái)實(shí)現(xiàn)圖像匹配。

[1]Lowe D.Distinctive image features from scale-invariant key points[J].International Journal of Computer Vision，2004，60（2）:91-110.

[2]Ke Y，Sukthankar R.Pca-Sift:a more distinctive representation for local image descriptors [C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition，Washington，2004.

[3]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors，pattern analysis and Machine Intelligence[J].IEEE Transactions，2005，27（10）:1615-1630.

[4]劉立，彭復(fù)員，趙坤.采用簡(jiǎn)化SIFT算法實(shí)現(xiàn)快速圖像匹配[J].紅外與激光工程，2008，37（1）:181-184.LIU Li，PENG Fu-yuan，ZHAO Kun.Simplified SIFT algorithm for fast image matching[J].Infrared and Laser Engineering.2008，37（1）:181-184.

[5]劉健，張國(guó)華，黃琳琳.基于改進(jìn)SIFT的圖像配準(zhǔn)算法[J].北京航空航天大學(xué)學(xué)報(bào)，2010，36（9）:1121-1124.LIU Jian，ZHANG Guo-hua，HUANG Lin-lin.Image registration approach based on improved SIFT[J].Journal of Beijing University of Aeronautics and Astronautics，2010，36 （9）:1121-1124.

[6]王曉華，傅衛(wèi)平，梁元月.提高SIFT特征匹配效率的方法研究[J].機(jī)械科學(xué)與技術(shù)，2009，28（9）:1252-1254.WANG Xiao-hua，F(xiàn)U Wei-ping，LIANG Yuan-yue.A Method for Improving SIFT Feature Matching Efficiency[J].Mechanical Science and Technology for Aerospace Engineering，2009，28（9）:1252-1254.