利用SIFT算法實現(xiàn)圖像自動拼接

利用SIFT算法實現(xiàn)

圖像自動拼接1999年BritishColumbia大學大衛(wèi).勞伊（DavidG.Lowe）教授總結了現(xiàn)有的基于不變量技術的特征檢測方法，并正式提出了一種基于尺度空間的、對圖像縮放、旋轉甚至仿射變換保持不變性的圖像局部特征描述算子－SIFT（尺度不變特征變換），這種算法在2004年被加以完善。SIFT提出的目的和意義DavidG.LoweComputerScienceDepartment

2366MainMall

UniversityofBritishColumbia

Vancouver,B.C.,V6T1Z4,CanadaE-mail:lowe@cs.ubc.ca

SIFT簡介SIFT算法實現(xiàn)細節(jié)

SIFT算法實現(xiàn)步驟簡述SIFT算法的實質可以歸為在不同尺度空間上查找特征點（關鍵點）的問題。2023/1/314所謂關鍵點，就是在不同尺度空間的圖像下檢測出的具有方向信息的局部極值點。根據(jù)歸納，我們可以看出特征點具有的三個特征：

尺度

方向

大小關鍵點檢測的相關概念1.哪些點是SIFT中要查找的關鍵點（特征點）？

這些點是一些十分突出的點不會因光照條件的改變而消失，比如角點、邊緣點、暗區(qū)域的亮點以及亮區(qū)域的暗點，既然兩幅圖像中有相同的景物，那么使用某種方法分別提取各自的穩(wěn)定點，這些點之間會有相互對應的匹配點。尺度空間理論最早在1962年提出，其主要思想是通過對原始圖像進行尺度變換，獲得圖像多尺度下的尺度空間表示序列，對這些序列進行尺度空間主輪廓的提取，并以該主輪廓作為一種特征向量，實現(xiàn)邊緣、角點檢測和不同分辨率上的特征提取等。尺度空間方法的基本思想是：在視覺信息(圖像信息)處理模型中引入一個被視為尺度的參數(shù)，通過連續(xù)變化尺度參數(shù)獲得不同尺度下的視覺處理信息，然后綜合這些信息以深入地挖掘圖像的本質特征。構建尺度空間的目的是檢測對于圖像的尺度變化具有不變性的位置，可以使用尺度的連續(xù)函數(shù)也就是尺度空間在所有可能的尺度中尋找穩(wěn)定的特征。尺度空間（scalespace

）關鍵點檢測的關鍵點檢測的相關概念

根據(jù)文獻《Scale-spacetheory:Abasictoolforanalysingstructuresatdifferentscales》我們可知，高斯核是唯一可以產(chǎn)生多尺度空間的核，一個圖像的尺度空間，L（x,y,σ),定義為原始圖像I(x,y)與一個可變尺度的2維高斯函數(shù)G(x,y,σ)卷積運算。關鍵點檢測高斯函數(shù)關鍵點檢測的相關概念當尺度因子σ逐漸增大時的一組高斯尺度空間。為了在尺度空間中有效的檢測穩(wěn)定關鍵點的位置，Lowe提出了高斯差分卷積DOG（DifferenceofGaussians）關鍵點檢測——DOG2023/1/319DoG（DifferenceofGaussian）函數(shù) 關鍵點檢測——DOG關鍵點檢測——DOG高斯差分函數(shù)DOG的優(yōu)點？1）計算效率高：由于L對于每個尺度空間都是需要計算的，而D只需在此基礎上做減法操作；2）高斯差分函數(shù)DoG（Difference-of-Gaussian）是尺度歸一化算子LoG（LaplacianofGaussian）的近似LOG算子與高斯核函數(shù)的關系通過推導可以看出，LOG算子與高斯核函數(shù)的差有直接關系，由此引入一種新的算子DOG（DifferenceofGaussians），即高斯差分算子。關鍵點檢測——DOG高斯金字塔的構建過程可分為兩步：（1）對圖像做高斯平滑；（2）對圖像做降采樣。

為了讓尺度體現(xiàn)其連續(xù)性，在簡單下采樣的基礎上加上了高斯濾波。一幅圖像可以產(chǎn)生幾組（octave）圖像，一組圖像包括幾層（interval）圖像。關鍵點檢測高斯金字塔DoG高斯差分金字塔 對應DOG算子，我們要構建DOG金字塔左側的每一階的尺度空間是由初始圖像重復與高斯函數(shù)卷積生成的一組高斯尺度空間圖像，右側是相鄰兩個高斯圖像經(jīng)差分得到的一組高斯差分尺度空間。每一階的第一個圖像是由高斯圖像經(jīng)因子為2的亞采樣得到的關鍵點檢測——DOG為了檢測D(x,y,σ)的局部極大值和極小值，每個采樣點都要和它同尺度的8個相鄰點和上下相鄰尺度對應的9×2個點相比較。只有當它比所有相鄰點都大或者都小的時候這個點才被選擇。這個檢查的花費是相當?shù)牡?，因為大部分的采樣點在頭一些檢查中就被淘汰了。局部極值點的檢測上一步被選擇的點稱為候選點，但是如果要進行下一步確定關鍵點的位置、尺度、主曲率，還需剔除那些低對比度（對噪聲很敏感）的點和處于邊緣的點。1）濾除低對比度的點2）去除邊緣響應DoG算子在邊緣處有很強的響應，由于邊緣的位置很難確定，故而對噪聲的影響很敏感。一個DOG空間極值點的主曲率的大小跟其所在的位置有關，它在與邊緣相互垂直處較小，而在邊緣處較大，所以可以根據(jù)這一特點來去除位于邊緣的極值點。局部極值點的檢測

關鍵點精確定位

為了提高關鍵點的穩(wěn)定性，需要對尺度空間DoG函數(shù)進行曲線擬合。利用DoG函數(shù)在尺度空間的Taylor展開式：其極值點

由于DoG值對噪聲和邊緣較敏感,因此,在上面DoG尺度空間中檢測到局部極值點還要經(jīng)過進一步的檢驗才能精確定位為特征點。

上式去除那些對比度較低的不穩(wěn)定極值點。Lowe的試驗顯示，所有取值小于0.04的極值點均可拋棄（像素灰度值范圍[0，1]）。

在計算過程中，分別對圖像的行、列及尺度三個量進行了修正，其修正結果如下：為修正值在Lowe的程序中，對坐標進行了五次修正。將修正后的結果代入式

求解得

去除邊緣響應

僅僅去除低對比度的極值點對于極值點的對于特征點穩(wěn)定性是遠遠不夠的。DoG函數(shù)在圖像邊緣有較強的邊緣響應，因此我們還需要排除邊緣響應。

DoG函數(shù)的（欠佳的）峰值點在橫跨邊緣的方向有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率可以通過計算在該點位置尺度的2×2的Hessian矩陣得到，導數(shù)由采樣點相鄰差來估計：表示DOG金字塔中某一尺度的圖像x方向求導兩次

在兩特征值相等時達最小，隨r的增長而增長。Lowe論文中建議r取10。

D的主曲率和H的特征值成正比，為了避免直接的計算這些特征值，而只是考慮它們的之間的比率。令為最大特征值，為最小的特征值，則時將關鍵點保留，反之剔除在以特征點為中心的鄰域內(nèi)采樣，該特征點處的梯度方向利用梯度方向直方圖來計算。直方圖把360度的范圍平均劃分成36等份來統(tǒng)計，找到梯度方向直方圖的峰值，這個峰值就是特征點的主方向。如果存在一個能量相當于主峰值80%的峰值，則將它作為特征點的輔方向。特征點可能不存在輔方向也可能存在一個或多個輔方向，這樣也增強了算法的魯棒性。為了能夠確保生成的SIFT特征描述符具有旋轉不變性，需要利用特征點鄰域像素的梯度特性為每個特征點指定一個主方向。確定特征點主方向生成特征點描述子特征點描述子的生成過程具體如下：1）以關鍵點為圓心將關鍵點鄰域旋轉θ°（調(diào)整至0°），其中θ為關鍵點的方向，從而保證了旋轉的不變性；2）在旋轉后的圖像中，以關鍵的中心取8

*

8的鄰域窗口，圖中左圖即為關鍵點的鄰域窗口，每個小格代表關鍵點鄰域窗口中的一個像素，箭頭的長度為像素的模值，箭頭的方向為像素的方向，這個方向就是旋轉后的像素方向；3）將8

*8的矩形窗口均勻分為16個4*4個子區(qū)域，見圖中右圖，采用高斯模糊的方法，高斯模糊的方法有利于增加與關鍵點較近鄰域的權重值，并降低與關鍵點較遠鄰域的權重值，然后計算每個區(qū)域中8個方向（0°、45°、90°、135°、180°、225°、270°、315°）的梯度累加值，累加每個方向的值就生成了一個種子點4）每一個特征點具有4個種子點，每個種子點有8個方向，形成了一個32維的SIFT特征描述符2023/1/3123關鍵點匹配

分別對模板圖（參考圖，referenceimage）和實時圖（觀測圖，observationimage）建立關鍵點描述子集合。目標的識別是通過兩點集內(nèi)關鍵點描述子的比對來完成。具有128維的關鍵點描述子的相似性度量采用歐式距離。2023/1/3124關鍵點匹配原圖像目標圖像窮舉匹配2023/1/3125

模板圖中關鍵點描述子：實時圖中關鍵點描述子：

任意兩描述子相似性度量：

要得到配對的關鍵點描述子，需滿足：關鍵點匹配2023/1/3126關鍵點的匹配可以采用窮舉法來完成，但是這樣耗費的時間太多，一般都采用一種叫kd樹的數(shù)據(jù)結構來完成搜索。搜索的內(nèi)容是以目標圖像的關鍵點為基準，搜索與目標圖像的特征點最鄰近的原圖像特征點和次鄰近的原圖像特征點。關鍵點匹配Kd樹是一個平衡二叉樹2023/1/3127關鍵點匹配并不能標志著算法的結束，因為在匹配的過程中存在著大量的錯配點。消除錯配點圖中交叉的綠線為錯配點2023/1/3128消除錯配點

RANSAC（RandomSampleConsensus，隨機抽樣一致

）是一種魯棒性的參數(shù)估計方法。RANSAC簡介RANSAC實質上就是一個反復測試、不斷迭代的過程。RANSAC的基本思想：

首先根據(jù)具體問題設計出某個目標函數(shù)，然后通過反復提取最小點集估計該函數(shù)中參數(shù)的初始值，利用這些初始值把所有的數(shù)據(jù)分為“內(nèi)點”（inlier）和“外點“（outlier），最后用所有的內(nèi)點重新計算和估計函數(shù)的參數(shù)。2023/1/3129消除錯配點RANSAC事例如何估計最佳直線？重復進行，擬合最優(yōu)直線隨機取兩樣本點擬合直線擬合直線：BackSIFT算子的性能評價：(1)SIFT算子提取的圖像局部的特征，對亮度變化、尺度縮放以及旋轉保持不變性，而且對物體噪聲、仿射變換、視角變化保持穩(wěn)定性。(2)描述符獨特性好，信息量豐富，適用于海量特征數(shù)據(jù)的匹配，與Harris算子匹配方式相比準確率較高。(3)由于SIFT算子構造過程復雜，而且提取的特征數(shù)據(jù)較大，因此其實時性較差。(4)SIFT算子在特征分布均勻的情況下精度差、匹配準確率低。(5)由于SIFT算子描述子的多方向性，在匹配時容易產(chǎn)生重復的匹配點。SIFT算法的擴展與改進

SIFT在圖像的不變特征提取方面擁有無與倫比的優(yōu)勢，但其并不是完美的，仍然存在著實時性不高、有時特征點較少、對邊緣模糊的目標無法準確提取特征點等缺陷。自從1999年，SIFT算法問世以來，人們從未停止對它的優(yōu)化和改進。SURF特征的提取SURF算法就是一種加速的SIFT算法，它利用了盒子濾波、積分圖像以及Haar小波實現(xiàn)了算法的加速。在SURF特征檢測尺度空間極值時利用盒子濾波近似SIFT算法中的二階高斯函數(shù)，并利用了積分圖像進行卷積，這就是SURF算法和SIFT算法的本質區(qū)別。積分圖像和盒子濾波的使用是SURF比SIFT算法速度快的主要原因。SIFT算法構建尺度空間金子塔時，通過上一層的圖像不斷的下采樣來調(diào)整下一層圖像的大小。SURF算法與同一尺寸圖像進行處理，可以并行計算，提高了時間效率。確定特征點主方向

SURF算法為了提高其魯棒性利用了Haar小波，Haar小波是一種簡單的濾波器可以用來計算水平和垂直方向上的梯度。

SIFTSURF特征點檢測用不同尺度的圖片與高斯函數(shù)做卷積用不同大小的盒子濾波器與原始圖像做卷積，易于并行方向特征點鄰接矩形區(qū)域內(nèi)，利用梯度直方圖計算特征點鄰接圓域內(nèi)，計算x、y方向上的Haar小波響應描述符生成20*20(單位為pixel)區(qū)域劃分為4*4(或2*2)的子區(qū)域，每個子域計算8bin直方圖20*20(單位為sigma)區(qū)域劃分為4*4子域，每個子域計算