基于SIFT算法的圖像拼接技術(shù)研究

何惠洋，韓 軍

（西安工業(yè)大學(xué) 光電工程學(xué)院，西安710021）

圖像拼接是指將兩幅或者兩幅以上的具有比較明顯重疊區(qū)域的圖像，拼接成一幅寬視野、無縫的質(zhì)量較高的高分辨率圖像，目前，圖像拼接技術(shù)被廣泛應(yīng)用于計算機(jī)視覺、醫(yī)療診斷、軍事探測、車輛輔助駕駛等諸多的領(lǐng)域。

圖像拼接的步驟有圖像配準(zhǔn)、圖像融合，其中以圖像配準(zhǔn)為最重要的步驟，圖像配準(zhǔn)算法的好壞直接決定了圖像拼接的質(zhì)量和效率，經(jīng)過對幾種具有代表性的圖像配準(zhǔn)算法進(jìn)行性能評估，發(fā)現(xiàn)SIFT算法是目前圖像處理領(lǐng)域最有效的圖像配準(zhǔn)算法[1]。然而，SIFT算法在細(xì)節(jié)比較豐富的圖像區(qū)域會提取到過多的特征點(diǎn)即無用特征點(diǎn)，導(dǎo)致在匹配時產(chǎn)生較多的誤匹配，針對這一問題，在研究SIFT算法的基礎(chǔ)上，加入RANSAC算法對特征點(diǎn)進(jìn)行篩選，在不影響算法魯棒性的前提下提高匹配正確率，從而整體優(yōu)化圖像配準(zhǔn)的效果。

1 SIFT算法原理

SIFT算法[2]是一種局部特征提取方法，最早是由哥倫比亞大學(xué)的David Lowe 提出，并在2004年得到完善，大量研究證明，其在特征提取階段相比于同類型的其他算法性能更加優(yōu)良，在目前的圖像處理領(lǐng)域應(yīng)用十分廣泛。

SIFT算法的核心理論[3]是尺度空間理論，其步驟如下：①尺度空間極值檢測；②剔除不合格關(guān)鍵點(diǎn)；③關(guān)鍵點(diǎn)方向分配；④生成關(guān)鍵點(diǎn)描述子。

首先，定義二維高斯函數(shù)為

由高斯函數(shù)推出尺度空間為

式中：σ為尺度空間因子；I（x，y）為圖像在某一點(diǎn)的像素值；L（x，y，σ）定義為有著尺度變換的高斯函數(shù)和圖像的卷積。

1.1 尺度空間極值檢測

為了在尺度空間檢測出穩(wěn)定的關(guān)鍵點(diǎn)，SIFT算法使用高斯差分尺度空間DoG（difference of Gaussians）算子，即

DoG 尺度空間生成如圖1所示。由圖可見，DoG空間是通過在圖像高斯金塔的每個尺度上減去相鄰金字塔來獲得的。

圖1 DoG 尺度空間生成Fig.1 DoG scale space generation

SIFT 極值點(diǎn)檢測如圖2所示，為找到極值點(diǎn)，需要將每個采樣點(diǎn)的中間點(diǎn)與其本層同一尺度以及相鄰上下兩層尺度共26個點(diǎn)進(jìn)行比較，如果該點(diǎn)為最大值或最小值，就認(rèn)為該點(diǎn)是圖像在該尺度上的一個極值點(diǎn)，作為待選特征點(diǎn)。

圖2 SIFT 極值點(diǎn)檢測Fig.2 SIFT extreme point detection

值得注意的是，在尋找極值點(diǎn)的過程中，每一組圖像的首末兩層無法進(jìn)行極值比較，為滿足尺度變化的連續(xù)性，人為地在每一組圖像的首尾兩層用高斯模糊生成2 幅圖像，從而保證不會在首位兩層漏選某些有用的極值點(diǎn)。

1.2 剔除不合格關(guān)鍵點(diǎn)

對所檢測得到的極值點(diǎn)執(zhí)行差分處理，確定極值點(diǎn)的位置和尺度，同時需要剔除不合格的關(guān)鍵點(diǎn)，如低對比度極值點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)。

用插值處理來剔除低對比度的極值點(diǎn)，DoG 函數(shù)在尺度空間的Taylor 展開式為

其中

式中：X為樣本的像素點(diǎn)，對式（4）求導(dǎo)并令導(dǎo)數(shù)為0，可獲得插值后極值像素點(diǎn)偏移量X^，通過對偏移量進(jìn)行控制可篩選掉低對比度的極值點(diǎn)。

當(dāng)需要消除邊緣相應(yīng)區(qū)域內(nèi)不穩(wěn)定的極值點(diǎn)時，可以對2×2的Hessian 矩陣H 求導(dǎo)，得出主曲率：

假設(shè)，特征值α 較大且特征值β 較小，并且H特征值與D的主曲率成比例，則

令α=γβ，可得

利用式（9）可以檢測主曲率是否低于某個閾值γ，從而進(jìn)行極值點(diǎn)篩選。

1.3 關(guān)鍵點(diǎn)方向分配

用圖像的局部區(qū)域特征來計算每個點(diǎn)的方向，從而使特征描述向量具有方向上旋轉(zhuǎn)不變的特性。所計算的梯度m（x，y）和方向θ（x，y）為

式中：L（x，y）為關(guān)鍵點(diǎn)的尺度空間值。

實際計算時，在以關(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)進(jìn)行采樣，并用直方圖來統(tǒng)計鄰域像素的梯度方向。梯度直方圖的范圍為0～360°，其中可以每10°一個柱，共36個柱；也可以每45°一個柱，共8個柱，實際計算一般多使用8個柱來統(tǒng)計，直方圖的峰值表示該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向，當(dāng)存在另一個峰值達(dá)到主峰值80%的能量時，則將這個方向認(rèn)為是該關(guān)鍵點(diǎn)的輔方向，因此，一個關(guān)鍵點(diǎn)的方向并不是固定的，它可能會被指定具有多個方向，這樣增強(qiáng)了匹配算法的魯棒性[4]。

至此，圖像的特征點(diǎn)已檢索完畢，每個特征點(diǎn)具有3個信息，即尺度信息、位置信息和方向信息。

1.4 生成關(guān)鍵點(diǎn)描述子

首先將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的方向，以確保旋轉(zhuǎn)不變性，然后以關(guān)鍵點(diǎn)為中心取一個8×8的窗口。生成特征子描述如圖3所示，圖3a的中央黑點(diǎn)為當(dāng)前關(guān)鍵點(diǎn)的位置，每個小格代表關(guān)鍵點(diǎn)鄰域所在尺度空間的一個像素，箭頭方向為該像素的梯度方向，箭頭長度代表該像素的梯度模值，在每4×4的小塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，即可形成一個種子點(diǎn)（如圖3b所示），圖3b 中，一個關(guān)鍵點(diǎn)由2×2 共4個種子點(diǎn)組成，每一個種子點(diǎn)都有8個方向的向量信息，可產(chǎn)生2×2×8 共32個數(shù)據(jù)，即產(chǎn)生一個32維的SIFT 特征向量對特征點(diǎn)進(jìn)行描述。

圖3 生成特征子描述Fig.3 Generate feature sub-description

在實際計算過程中，為增強(qiáng)匹配的穩(wěn)健性，Lowe 建議對每個關(guān)鍵點(diǎn)使用4×4 共16個種子點(diǎn)來描述，這樣，對于一個關(guān)鍵點(diǎn)就可以產(chǎn)生4×4×8共128個數(shù)據(jù)，即最終形成一個128維的SIFT 特征向量。

2 k-d樹與RANSAC算法

2.1 k-d樹算法

在SIFT算法中利用k-維樹k-d（dimensional）樹進(jìn)行搜索匹配特征點(diǎn)，k-d樹算法由2部分組成，一是建立k-d樹數(shù)據(jù)結(jié)構(gòu)，二是在k-d樹這種數(shù)據(jù)結(jié)構(gòu)上進(jìn)行數(shù)據(jù)查找的算法。

2.1.1 構(gòu)建k-d樹

k-d樹是一個二叉樹的數(shù)據(jù)結(jié)構(gòu)。k-d樹上每一個節(jié)點(diǎn)代表著一個空間范圍，通過分割平面將整個空間分割成左右2個子空間，1）確定分割域，對于所有描述子數(shù)據(jù)（特征向量），統(tǒng)計它們在每個維上的數(shù)據(jù)方差，選取出最大值，而對應(yīng)的維數(shù)k 即為分割域的值；2）確定節(jié)點(diǎn)數(shù)據(jù)域，數(shù)據(jù)點(diǎn)集按照前面的分割域的值進(jìn)行排序，位于中間的那個數(shù)據(jù)點(diǎn)即為節(jié)點(diǎn)數(shù)據(jù)；3）確定左子空間和右子空間，分割平面（k等于節(jié)點(diǎn)數(shù)據(jù)值）將整個空間分割成2個子空間，k-d樹的構(gòu)建是一個遞歸的過程，對左子空間和右子空間內(nèi)的數(shù)據(jù)重復(fù)根節(jié)點(diǎn)的過程就可以得到下一級子節(jié)點(diǎn)，如此反復(fù)到空間只包含一個數(shù)據(jù)點(diǎn)，構(gòu)建k-d樹的流程如圖4所示。

圖4 k-d樹構(gòu)建流程Fig.4 k-d tree construction flow chart

2.1.2 k-d樹最近鄰查找的算法

首先，通過二叉樹搜索（比較待查詢節(jié)點(diǎn)和k-d樹節(jié)點(diǎn)最大方差維數(shù)的值，小于時進(jìn)入左子樹分支，大于等于時則進(jìn)入右子樹分支直到葉子結(jié)點(diǎn)），進(jìn)行二叉樹查找后可以得到最近鄰的相似點(diǎn)，即在二叉樹的葉子節(jié)點(diǎn)，然后，這個葉子節(jié)點(diǎn)返回到父節(jié)點(diǎn)查找是否有距離查詢節(jié)點(diǎn)更近的節(jié)點(diǎn)，如果沒有則說明該子節(jié)點(diǎn)就是最近鄰點(diǎn)，否則需要跳到其他子結(jié)點(diǎn)空間中去搜索（將其他子結(jié)點(diǎn)加入到搜索路徑），重復(fù)該過程直至搜索路徑為空。

2.2 RANSAC算法

隨機(jī)抽樣一致性RANSAC（RANdom SAmple Consensus）算法是一種魯棒的變換估計算法，利用特征集合的內(nèi)在集合約束關(guān)系進(jìn)一步剔除錯誤的配準(zhǔn)，提高配準(zhǔn)正確率，該算法的主要思想是先隨機(jī)選取2個點(diǎn)來確定一條直線，將這條直線一定距離范圍內(nèi)的點(diǎn)稱為這條直線的支撐，隨機(jī)選擇重復(fù)多次，具有最大支撐特征集的直線被確認(rèn)為是樣本點(diǎn)集的擬合，在擬合的誤差距離范圍內(nèi)的點(diǎn)稱為內(nèi)點(diǎn)，反之則為外點(diǎn)，將外點(diǎn)剔除掉，增強(qiáng)圖像配準(zhǔn)算法的穩(wěn)健型，利用這種方法能減少誤匹配的點(diǎn)，使配準(zhǔn)效果更佳，提高了正確率。

RANSAC算法假設(shè)給定一組數(shù)據(jù)，存在可以計算出符合這些數(shù)據(jù)的模型參數(shù)的方法，估計模型參數(shù)的過程如下：

步驟1從一個有N個數(shù)據(jù)的集合P 中隨機(jī)抽取模型求解要求最少的n個數(shù)據(jù)，根據(jù)這些抽取的n個數(shù)據(jù)計算出一個估計模型M；

步驟2然后對其余的N-n個數(shù)據(jù)，計算它們與估計模型M 之間的距離，保存這個集合中在估計模型M的誤差允許范圍內(nèi)的數(shù)據(jù)個數(shù)c；

步驟3步驟1和步驟2 不斷迭代k次，對應(yīng)最大c值的估計模型即為所求的模型，這c個數(shù)據(jù)即為內(nèi)點(diǎn)；

實際應(yīng)用中需要確定一個適當(dāng)?shù)牡螖?shù)k，迭代次數(shù)是保證模型估計需要的n個數(shù)據(jù)都是內(nèi)點(diǎn)的概率p所需要的迭代次數(shù)，迭代次數(shù)k 需要滿足的條件為

式中：w為該數(shù)據(jù)是數(shù)學(xué)模型內(nèi)點(diǎn)的概率；n為確定模型參數(shù)的最少點(diǎn)數(shù)。

3 算法試驗結(jié)果與分析

在此，試驗硬件環(huán)境為酷睿i5 處理器，4 GB內(nèi)存的PC，采用32位Windows 10 操作系統(tǒng)，編譯環(huán)境為VS 2010和OpenCV 2.4.9。

3.1 室外場景拼接試驗

圖5 室外試驗圖像Fig.5 Outdoor experimental images

該組試驗圖像為室外拍攝，如圖5所示，室外拍攝圖像色彩較為單一，匹配到的特征點(diǎn)較少，使用所研究的SIFT算法可使匹配效果更佳，特征點(diǎn)數(shù)據(jù)見表1。

表1 室外試驗特征點(diǎn)數(shù)據(jù)Tab.1 Outdoor experimental feature point data

將匹配到一起的特征點(diǎn)連線，再進(jìn)行拼接，結(jié)果見圖6，圖7。

圖6 匹配兩幅圖像Fig.6 Matching two image

圖7 室外試驗結(jié)果圖Fig.7 Outdoor experimental result

3.2 室內(nèi)場景拼接試驗

該組試驗圖像為室內(nèi)拍攝，如圖8所示，室內(nèi)拍攝的圖像色彩較為豐富，故匹配到的特征點(diǎn)比室外圖像多，采用SIFT算法仍可獲得較好的拼接效果，特征點(diǎn)數(shù)據(jù)見表2。

圖8 室內(nèi)試驗圖像Fig.8 Indoor experiment images

表2 室內(nèi)試驗特征點(diǎn)數(shù)據(jù)Tab.2 Indoor experimental feature point data

最終試驗結(jié)果見圖9，圖10。

圖9 匹配兩幅圖像Fig.9 Matching two image

圖10 室內(nèi)試驗結(jié)果圖Fig.10 Indoor experimental result

4 結(jié)語

本文主要研究了圖像拼接過程中的SIFT算法，并以此為基礎(chǔ)加入了中k-d樹匹配算法，匹配完成后再使用RANSAC算法去除誤匹配，經(jīng)過試驗分析，雖然SIFT算法的特征點(diǎn)提取較復(fù)雜，計算時間相對較長，但是SIFT算法檢測出的特征點(diǎn)具有尺度不變性，可以處理圖像間發(fā)生的平移、旋轉(zhuǎn)、仿射變換的匹配，再經(jīng)過RANSAC算法提高匹配精度，使該算法具有匹配能力強(qiáng)、精確度高的特征。