利用SIFT算法實(shí)現(xiàn)圖像自動(dòng)拼接

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

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

2366MainMall

UniversityofBritishColumbia

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

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

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

尺度

方向

大小關(guān)鍵點(diǎn)檢測的相關(guān)概念1.哪些點(diǎn)是SIFT中要查找的關(guān)鍵點(diǎn)（特征點(diǎn)）？

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

）關(guān)鍵點(diǎn)檢測的關(guān)鍵點(diǎn)檢測的相關(guān)概念

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

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

關(guān)鍵點(diǎn)精確定位

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

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

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

在計(jì)算過程中，分別對圖像的行、列及尺度三個(gè)量進(jìn)行了修正，其修正結(jié)果如下：為修正值在Lowe的程序中，對坐標(biāo)進(jìn)行了五次修正。將修正后的結(jié)果代入式

求解得

去除邊緣響應(yīng)

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

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

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

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

*

8的鄰域窗口，圖中左圖即為關(guān)鍵點(diǎn)的鄰域窗口，每個(gè)小格代表關(guān)鍵點(diǎn)鄰域窗口中的一個(gè)像素，箭頭的長度為像素的模值，箭頭的方向?yàn)橄袼氐姆较?，這個(gè)方向就是旋轉(zhuǎn)后的像素方向；3）將8

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

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

模板圖中關(guān)鍵點(diǎn)描述子：實(shí)時(shí)圖中關(guān)鍵點(diǎn)描述子：

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

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

RANSAC（RandomSampleConsensus，隨機(jī)抽樣一致

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

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

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

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

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