基于SIFT-BP的圖像配準(zhǔn)算法

高 華，曹 鋒，陳明星

(重慶交通大學(xué)，重慶 400074)

圖像配準(zhǔn)技術(shù)是圖像處理的重要分支，其目的是對不同時間、不同傳感器或者不同視角的2張或2張以上的圖像進(jìn)行匹配。該技術(shù)廣泛應(yīng)用于機(jī)器視覺、遙感圖像、醫(yī)學(xué)影像、三維重構(gòu)等。圖像的配準(zhǔn)一般采用基于區(qū)域或基于特征［1－3］?；趨^(qū)域的配準(zhǔn)方法要先比較區(qū)域內(nèi)的各個像素點(diǎn)，然后建立圖像之間的變換模型參數(shù)，因此其計算量大，配準(zhǔn)時間長。如果圖像存在縮放旋轉(zhuǎn)或扭曲，就會影響圖像配準(zhǔn)的精確性，進(jìn)而影響到后續(xù)工作的處理?；谔卣鞯膱D像配準(zhǔn)方法因其配準(zhǔn)速度快、精度高、魯棒性好而成為研究熱點(diǎn)。

基于特征的配準(zhǔn)算法主要有角點(diǎn)匹配算法、SIFT特征［4］提取算法、SURF特征提取算法等。角點(diǎn)提取雖具有旋轉(zhuǎn)不變性，但是對于尺度變化較大的圖像無法保持特征的不變性;SIFT特征是圖像的局部特征，不僅對旋轉(zhuǎn)、尺度縮放、亮度變化可以保持不變性，而且對視角變化、仿射變換、噪聲也具有一定程度的穩(wěn)定性［5］。

但是，傳統(tǒng)的SIFT算法僅考慮了特征點(diǎn)的描述子信息，完全忽略了特征點(diǎn)描述符之間的幾何信息。本文對參考圖像和映射圖像中離散的關(guān)鍵點(diǎn)應(yīng)用BP算法，將關(guān)鍵點(diǎn)的相似度融入到消息傳遞過程中，以迭代算法計算對應(yīng)關(guān)鍵點(diǎn)，不但利用了關(guān)鍵點(diǎn)的局部信息，而且保持了映射圖像中關(guān)鍵點(diǎn)間的空間約束。

1 SIFT特征檢測與匹配

1.1 特征檢測

SIFT算法特征點(diǎn)的檢測基于尺度空間理論。二維圖像的尺度空間定義為

其中:G(x，y，δ)是二維高斯函數(shù);δ為尺度空間因子;(x，y)表示圖像的像素位置。

為了在尺度空間檢測到有效的關(guān)鍵點(diǎn)，提出用不同的高斯差分核分別與圖像進(jìn)行卷積生成高斯差分尺度空間:

DoG算子計算簡單，是歸一化LoG算子的近似。

利用SIFT算法構(gòu)造DOG金字塔時通過相鄰尺度空間函數(shù)相減即可。在形成的尺度空間中的3×3×3的空域和尺度域結(jié)合的鄰域里進(jìn)行非最大值抑制。一個點(diǎn)如果在尺度空間本層以及上下26個鄰域中值是最大或最小時，才可認(rèn)為是特征點(diǎn)。通過擬合3維2次函數(shù)精確確定特征點(diǎn)的位置和尺度，同時去除對比度低的特征點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)。

1.2 特征點(diǎn)描述

1.2.1 確定特征點(diǎn)主方向

為了使關(guān)鍵點(diǎn)具備旋轉(zhuǎn)不變性，利用關(guān)鍵點(diǎn)鄰域像素的梯度方向的分布特性為每個關(guān)鍵點(diǎn)指定方向參數(shù):以特征點(diǎn)為中心，在鄰域窗口內(nèi)采樣，用梯度方向直方圖統(tǒng)計鄰域像素的梯度方向，峰值代表特征點(diǎn)處鄰域梯度的主方向，即為特征點(diǎn)的主方向，如果存在相當(dāng)于主峰值80%能量的峰值時，則作為特征點(diǎn)的輔方向。因此，一個特征點(diǎn)可能會有1個主方向和1個以上的輔方向，這可以增強(qiáng)匹配的魯棒性。

1.2.2 構(gòu)建描述子

首先將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的方向，以確保旋轉(zhuǎn)不變性，然后將以關(guān)鍵點(diǎn)為中心的8×8的窗口分成16個2×2的小塊，并計算各小塊內(nèi)8個方向的梯度方向直方圖再進(jìn)行累加，形成一個種子點(diǎn)，。每個種子點(diǎn)對應(yīng)8個方向的向量信息，則每個關(guān)鍵點(diǎn)就對應(yīng)16×8=128維的向量。

1.2.3 SIFT 特征向量的匹配

Lowe提出的SIFT算法采用歐式距離作為兩幅圖像間的相似性度量，即如果最近的距離除以次近的距離少于某個比例閾值，則認(rèn)可該匹配點(diǎn)是對的。

其中:D1(i)、D2(j)分別為參考圖和映射圖中的第i個和第j個特征向量;T為不依賴于圖像的常量。

1.3 改進(jìn)的SIFT匹配算法

盡管SIFT算法可以提取圖像獨(dú)特的特征，但是最近歐氏距離決定了它只是一種局部優(yōu)化的方法，完全忽略了不同的特征描述符之間的幾何信息。這造成的后果就是本應(yīng)映射在參考圖描述符附近的映射圖描述符距離可能很遠(yuǎn)。為此本研究作一個全局優(yōu)化匹配并且定義一個補(bǔ)償函數(shù)φ(m)，表示參考從一個關(guān)鍵點(diǎn)到另一個關(guān)鍵點(diǎn)的距離和映射圖對應(yīng)關(guān)鍵點(diǎn)之間的距離的差異總和，如式(4)所示。

其中:ID1是原始圖像的描述符集;m(·)是映射圖中相應(yīng)于參考圖的映射描述符指數(shù)。因此，可按式(6)～(8)解決全局優(yōu)化問題:

但是，式(6)不是凸函數(shù)并且?guī)в袕?fù)雜的指數(shù)，這樣，經(jīng)過式(3)計算后會丟棄一些關(guān)鍵點(diǎn)，但剩下的關(guān)鍵點(diǎn)的數(shù)量通常仍然會超過100。因此，一次徹底的搜索將需要100!步，顯然是難以計算的。此外，在這么早的階段應(yīng)用式(6)也可能會不必要地丟棄有用的信息，并且式(6)有可能在存在不滿足這個條件下的匹配的情況下出現(xiàn)錯誤。

為此，本文提出使用信任度擴(kuò)散算法(belief propagation)［7］解決式(6)出現(xiàn)的問題。BP算法廣泛地應(yīng)用于信號處理應(yīng)用中［8－9］，它的優(yōu)點(diǎn)就是目標(biāo)函數(shù)的凹凸性不受限制，其主要思想是消息的迭代傳輸。首先，將整個優(yōu)化問題分解成若干較簡單的局部問題。在每次迭代過程中，每個局部問題嘗試估計下一個將要進(jìn)行的優(yōu)化問題的最優(yōu)解。相鄰的2個局部優(yōu)化問題將交換信任度。每一個局部優(yōu)化問題的信任度將會納入下一次迭代計算信任度的過程中。當(dāng)進(jìn)行到一個固定的預(yù)定義的迭代數(shù)量或者所有的局部優(yōu)化問題在收斂在一個最有可能的解時，算法停止。

由于即使提出的目標(biāo)函數(shù)呈指數(shù)增長，優(yōu)化問題也不會發(fā)生改變，因此式(6)可改為

并且 CDes/CDist= ε。bDesi(mi)和 bDisti，j(mi，mj)可以分別近似看作映射圖中給定的第mi個關(guān)鍵點(diǎn)的描述符信息所匹配的參考圖中第i個關(guān)鍵點(diǎn)的信任度和第mj個關(guān)鍵點(diǎn)相匹配的第j個關(guān)鍵點(diǎn)的信息。

此時本文的優(yōu)化問題轉(zhuǎn)化為式(10)，但是，它并沒有使優(yōu)化問題變得更易于處理。因此，把優(yōu)化問題簡化一點(diǎn)，對于相互接近的關(guān)鍵點(diǎn)，使優(yōu)化函數(shù)只包含 bDisti，j，在鄰域(假設(shè) j∈N(i) ?ID1，并且，優(yōu)化問題可以近似使用最大積BP 算法［10］解決。此時，

如果網(wǎng)絡(luò)圖是一棵樹，最大積BP算法收斂到全局最優(yōu)。在一般情況下，該算法不是最理想的，但是在許多應(yīng)用中卻依然工作良好［9］。定義為關(guān)鍵點(diǎn)i的信任度，關(guān)鍵點(diǎn)j在第n次迭代的正確匹配為mj。在每次迭代過程中，消息從關(guān)鍵點(diǎn)i傳輸?shù)疥P(guān)鍵點(diǎn)j。改進(jìn)算法描述如下:

2)當(dāng) i∈ID1時，利用式(14)迭代更新消息

3)計算每個節(jié)點(diǎn)的信任度:

4)令n=n+1，轉(zhuǎn)至步驟2)。當(dāng)n達(dá)到最大迭代次數(shù)時，算法結(jié)束。

1.4 求解圖像間的投影變換關(guān)系

假設(shè)2幅圖像滿足以下投影變換關(guān)系

表示成向量形式為kXi=HX'i，單應(yīng)性矩陣H的自由度為8，因此需要4對匹配點(diǎn)就可計算出H。

2 實(shí)驗(yàn)分析

本文實(shí)驗(yàn)操作系統(tǒng)為Window XP，內(nèi)存為2G，編程環(huán)境是Visual 2008，OpenCV2.1。選取圖1作為待配準(zhǔn)的原始圖像，分別用Lowe的傳統(tǒng)SIFT配準(zhǔn)算法和本文的改進(jìn)算法對圖1進(jìn)行配準(zhǔn)，配準(zhǔn)結(jié)果如圖2所示。觀察可知，在傳統(tǒng)配準(zhǔn)算法中有一些匹配的錯誤，特別是原始圖像的關(guān)鍵點(diǎn)都相當(dāng)接近，然而原SIFT匹配算法基本上忽略了這些信息并且去匹配了遠(yuǎn)離該關(guān)鍵點(diǎn)的其他關(guān)鍵點(diǎn)中的一個，本文提出的BP算法卻試圖保持關(guān)鍵點(diǎn)的距離不變。在傳統(tǒng)算法中，上下圖像分別包含了306279個特征點(diǎn)，有效匹配點(diǎn)對數(shù)為65。使用改進(jìn)的匹配算法后，上下圖像分別提取了284252個特征點(diǎn)，有效匹配點(diǎn)對數(shù)為78?？梢娕c傳統(tǒng)算法相比，改進(jìn)的算法提高了提取特征點(diǎn)位置的精確度與匹配的準(zhǔn)確性。本文CDes被設(shè)置成40000，CDist設(shè)置為 550。

圖3 改進(jìn)算法配準(zhǔn)效果

3 結(jié)束語

本文實(shí)現(xiàn)了基于BP的SIFT特征點(diǎn)的改進(jìn)的圖像配準(zhǔn)算法。在圖像配準(zhǔn)的過程中，對于傳統(tǒng)SIFT算法忽略特征點(diǎn)的位置信息等，提出了利用信任度擴(kuò)散算法求解關(guān)鍵點(diǎn)之間的匹配關(guān)系，將關(guān)鍵點(diǎn)的相似度融入到消息傳遞過程中，以迭代的方法計算對應(yīng)點(diǎn)，最后利用投影變換矩陣對之進(jìn)行匹配。在配準(zhǔn)的過程中，改進(jìn)算法比傳統(tǒng)的方法有了顯著的改善，不但減少了誤匹配點(diǎn)，降低了誤匹配率，而且與原始算法相比，能夠找出更多的匹配點(diǎn)，增強(qiáng)了定位的魯棒性。

［1］趙向陽，杜利民.一種全自動穩(wěn)健的圖像拼接融合算法［J］.中國圖象圖形學(xué)報，2004，9(4):417 －422.

［2］關(guān)曉菊，周激流，何坤.基于方向能量的灰度圖像邊緣檢測［J］.激光雜志，2010，31(2):14 －16.

［3］范永輝，王剛，曲文娟.基于小波域分類隱馬爾可夫樹模型的圖像融合算法研究［J］.激光雜志，2009，30(5):32－34.

［4］Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91 －110.

［5］YANG HENG，WANG QING.A novel local feature descriptor for image matching［Z］//IEEE International Conference on Multimedia and Expo.［S.l.］:［s.n.］，2008:1405－1408.

［6］Fischler M A，Bolles R C.Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image A-nalysis and Automated Cartography［J］.Communications of ACM，1981，24(6):381 －395.

［7］Pearl J.Probabilistic reasoning in intelligent systems:networks of plausible inference［M］.San Francisco:Morgan Kau Fmann Publishers Inc，1988.

［8］Kschischang F，F(xiàn)rey B，Loeliger H.Factor graphs and the sum-product algorithm［J］.IEEE Trans Inform Theory，2001，47:498 －519.

［9］Sun J，Zheng N N，Shum H Y.Stereo matching using belief propagation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(7):787 －800.

［10］MacKay D.Information Theory，Inference，and Learning Algorithms［M］.Cambridge:［s.n.］，2003.