何惠洋，韓 軍

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

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

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

1 SIFT算法原理

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

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

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

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

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

1.1 尺度空間極值檢測

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

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

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

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

圖2 SIFT 極值點檢測Fig.2 SIFT extreme point detection

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

1.2 剔除不合格關鍵點

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

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

其中

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

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

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

令α=γβ，可得

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

1.3 關鍵點方向分配

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

式中：L（x，y）為關鍵點的尺度空間值。

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

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

1.4 生成關鍵點描述子

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

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

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

2 k-d樹與RANSAC算法

2.1 k-d樹算法

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

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

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

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

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

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

2.2 RANSAC算法

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

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

步驟1從一個有N個數(shù)據(jù)的集合P 中隨機抽取模型求解要求最少的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次，對應最大c值的估計模型即為所求的模型，這c個數(shù)據(jù)即為內(nèi)點；

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

式中：w為該數(shù)據(jù)是數(shù)學模型內(nèi)點的概率；n為確定模型參數(shù)的最少點數(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所示，室外拍攝圖像色彩較為單一，匹配到的特征點較少，使用所研究的SIFT算法可使匹配效果更佳，特征點數(shù)據(jù)見表1。

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

將匹配到一起的特征點連線，再進行拼接，結(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)拍攝的圖像色彩較為豐富，故匹配到的特征點比室外圖像多，采用SIFT算法仍可獲得較好的拼接效果，特征點數(shù)據(jù)見表2。

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

表2 室內(nèi)試驗特征點數(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算法，并以此為基礎加入了中k-d樹匹配算法，匹配完成后再使用RANSAC算法去除誤匹配，經(jīng)過試驗分析，雖然SIFT算法的特征點提取較復雜，計算時間相對較長，但是SIFT算法檢測出的特征點具有尺度不變性，可以處理圖像間發(fā)生的平移、旋轉(zhuǎn)、仿射變換的匹配，再經(jīng)過RANSAC算法提高匹配精度，使該算法具有匹配能力強、精確度高的特征。