何惠洋，韓 軍

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

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

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

1 SIFT算法原理

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

SIFT算法的核心理論[3]是尺度空間理論，其步驟如下：①尺度空間極值檢測(cè)；②剔除不合格關(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 尺度空間極值檢測(cè)

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

DoG 尺度空間生成如圖1所示。由圖可見(jiàn)，DoG空間是通過(guò)在圖像高斯金塔的每個(gè)尺度上減去相鄰金字塔來(lái)獲得的。

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

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

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

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

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

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

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

其中

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

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

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

令α=γβ，可得

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

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

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

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

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

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

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

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

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

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

2 k-d樹(shù)與RANSAC算法

2.1 k-d樹(shù)算法

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

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

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

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

2.1.2 k-d樹(shù)最近鄰查找的算法

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

2.2 RANSAC算法

隨機(jī)抽樣一致性RANSAC（RANdom SAmple Consensus）算法是一種魯棒的變換估計(jì)算法，利用特征集合的內(nèi)在集合約束關(guān)系進(jìn)一步剔除錯(cuò)誤的配準(zhǔn)，提高配準(zhǔn)正確率，該算法的主要思想是先隨機(jī)選取2個(gè)點(diǎn)來(lái)確定一條直線，將這條直線一定距離范圍內(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ù)，存在可以計(jì)算出符合這些數(shù)據(jù)的模型參數(shù)的方法，估計(jì)模型參數(shù)的過(guò)程如下：

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

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

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

實(shí)際應(yīng)用中需要確定一個(gè)適當(dāng)?shù)牡螖?shù)k，迭代次數(shù)是保證模型估計(jì)需要的n個(gè)數(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 算法試驗(yàn)結(jié)果與分析

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

3.1 室外場(chǎng)景拼接試驗(yàn)

圖5 室外試驗(yàn)圖像Fig.5 Outdoor experimental images

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

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

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

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

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

3.2 室內(nèi)場(chǎng)景拼接試驗(yàn)

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

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

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

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

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

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

4 結(jié)語(yǔ)

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