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

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

2366MainMall

UniversityofBritishColumbia

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

SIFT簡介第2頁，課件共32頁，創(chuàng)作于2023年2月SIFT算法實(shí)現(xiàn)細(xì)節(jié)

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

尺度

方向

大小關(guān)鍵點(diǎn)檢測(cè)的相關(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ì)有相互對(duì)應(yīng)的匹配點(diǎn)。7/9/20234第4頁，課件共32頁，創(chuàng)作于2023年2月尺度空間理論最早在1962年提出，其主要思想是通過對(duì)原始圖像進(jìn)行尺度變換，獲得圖像多尺度下的尺度空間表示序列，對(duì)這些序列進(jìn)行尺度空間主輪廓的提取，并以該主輪廓作為一種特征向量，實(shí)現(xiàn)邊緣、角點(diǎn)檢測(cè)和不同分辨率上的特征提取等。尺度空間方法的基本思想是：在視覺信息(圖像信息)處理模型中引入一個(gè)被視為尺度的參數(shù)，通過連續(xù)變化尺度參數(shù)獲得不同尺度下的視覺處理信息，然后綜合這些信息以深入地挖掘圖像的本質(zhì)特征。構(gòu)建尺度空間的目的是檢測(cè)對(duì)于圖像的尺度變化具有不變性的位置，可以使用尺度的連續(xù)函數(shù)也就是尺度空間在所有可能的尺度中尋找穩(wěn)定的特征。尺度空間（scalespace

）關(guān)鍵點(diǎn)檢測(cè)的關(guān)鍵點(diǎn)檢測(cè)的相關(guān)概念第5頁，課件共32頁，創(chuàng)作于2023年2月

根據(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)檢測(cè)高斯函數(shù)關(guān)鍵點(diǎn)檢測(cè)的相關(guān)概念第6頁，課件共32頁，創(chuàng)作于2023年2月當(dāng)尺度因子σ逐漸增大時(shí)的一組高斯尺度空間。第7頁，課件共32頁，創(chuàng)作于2023年2月為了在尺度空間中有效的檢測(cè)穩(wěn)定關(guān)鍵點(diǎn)的位置，Lowe提出了高斯差分卷積DOG（DifferenceofGaussians）關(guān)鍵點(diǎn)檢測(cè)——DOG第8頁，課件共32頁，創(chuàng)作于2023年2月DoG（DifferenceofGaussian）函數(shù) 關(guān)鍵點(diǎn)檢測(cè)——DOG7/9/20239第9頁，課件共32頁，創(chuàng)作于2023年2月關(guān)鍵點(diǎn)檢測(cè)——DOG第10頁，課件共32頁，創(chuàng)作于2023年2月高斯差分函數(shù)DOG的優(yōu)點(diǎn)？1）計(jì)算效率高：由于L對(duì)于每個(gè)尺度空間都是需要計(jì)算的，而D只需在此基礎(chǔ)上做減法操作；2）高斯差分函數(shù)DoG（Difference-of-Gaussian）是尺度歸一化算子LoG（LaplacianofGaussian）的近似第11頁，課件共32頁，創(chuàng)作于2023年2月LOG算子與高斯核函數(shù)的關(guān)系通過推導(dǎo)可以看出，LOG算子與高斯核函數(shù)的差有直接關(guān)系，由此引入一種新的算子DOG（DifferenceofGaussians），即高斯差分算子。關(guān)鍵點(diǎn)檢測(cè)——DOG第12頁，課件共32頁，創(chuàng)作于2023年2月高斯金字塔的構(gòu)建過程可分為兩步：（1）對(duì)圖像做高斯平滑；（2）對(duì)圖像做降采樣。

為了讓尺度體現(xiàn)其連續(xù)性，在簡單下采樣的基礎(chǔ)上加上了高斯濾波。一幅圖像可以產(chǎn)生幾組（octave）圖像，一組圖像包括幾層（interval）圖像。關(guān)鍵點(diǎn)檢測(cè)高斯金字塔第13頁，課件共32頁，創(chuàng)作于2023年2月DoG高斯差分金字塔 對(duì)應(yīng)DOG算子，我們要構(gòu)建DOG金字塔左側(cè)的每一階的尺度空間是由初始圖像重復(fù)與高斯函數(shù)卷積生成的一組高斯尺度空間圖像，右側(cè)是相鄰兩個(gè)高斯圖像經(jīng)差分得到的一組高斯差分尺度空間。每一階的第一個(gè)圖像是由高斯圖像經(jīng)因子為2的亞采樣得到的關(guān)鍵點(diǎn)檢測(cè)——DOG第14頁，課件共32頁，創(chuàng)作于2023年2月為了檢測(cè)D(x,y,σ)的局部極大值和極小值，每個(gè)采樣點(diǎn)都要和它同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對(duì)應(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)的檢測(cè)第15頁，課件共32頁，創(chuàng)作于2023年2月上一步被選擇的點(diǎn)稱為候選點(diǎn)，但是如果要進(jìn)行下一步確定關(guān)鍵點(diǎn)的位置、尺度、主曲率，還需剔除那些低對(duì)比度（對(duì)噪聲很敏感）的點(diǎn)和處于邊緣的點(diǎn)。1）濾除低對(duì)比度的點(diǎn)2）去除邊緣響應(yīng)DoG算子在邊緣處有很強(qiáng)的響應(yīng)，由于邊緣的位置很難確定，故而對(duì)噪聲的影響很敏感。一個(gè)DOG空間極值點(diǎn)的主曲率的大小跟其所在的位置有關(guān)，它在與邊緣相互垂直處較小，而在邊緣處較大，所以可以根據(jù)這一特點(diǎn)來去除位于邊緣的極值點(diǎn)。局部極值點(diǎn)的檢測(cè)第16頁，課件共32頁，創(chuàng)作于2023年2月

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

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

由于DoG值對(duì)噪聲和邊緣較敏感,因此,在上面DoG尺度空間中檢測(cè)到局部極值點(diǎn)還要經(jīng)過進(jìn)一步的檢驗(yàn)才能精確定位為特征點(diǎn)。第17頁，課件共32頁，創(chuàng)作于2023年2月

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

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

求解得第18頁，課件共32頁，創(chuàng)作于2023年2月

去除邊緣響應(yīng)

僅僅去除低對(duì)比度的極值點(diǎn)對(duì)于極值點(diǎn)的對(duì)于特征點(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)兩次第19頁，課件共32頁，創(chuàng)作于2023年2月

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

D的主曲率和H的特征值成正比，為了避免直接的計(jì)算這些特征值，而只是考慮它們的之間的比率。令為最大特征值，為最小的特征值，則時(shí)將關(guān)鍵點(diǎn)保留，反之剔除第20頁，課件共32頁，創(chuàng)作于2023年2月在以特征點(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)主方向第21頁，課件共32頁，創(chuàng)作于2023年2月生成特征點(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特征描述符第22頁，課件共32頁，創(chuàng)作于2023年2月關(guān)鍵點(diǎn)匹配

分別對(duì)模板圖（參考圖，referenceimage）和實(shí)時(shí)圖（觀測(cè)圖，observationimage）建立關(guān)鍵點(diǎn)描述子集合。目標(biāo)的識(shí)別是通過兩點(diǎn)集內(nèi)關(guān)鍵點(diǎn)描述子的比對(duì)來完成。具有128維的關(guān)鍵點(diǎn)描述子的相似性度量采用歐式距離。7/9/202323第23頁，課件共32頁，創(chuàng)作于2023年2月關(guān)鍵點(diǎn)匹配原圖像目標(biāo)圖像窮舉匹配2023/7/924第24頁，課件共32頁，創(chuàng)作于2023年2月

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

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

要得到配對(duì)的關(guān)鍵點(diǎn)描述子，需滿足：關(guān)鍵點(diǎn)匹配7/9/202325第25頁，課件共32頁，創(chuàng)作于2023年2月關(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è)平衡二叉樹7/9/202326第26頁，課件共32頁，創(chuàng)作于2023年2月關(guān)鍵點(diǎn)匹配并不能標(biāo)志著算法的結(jié)束，因?yàn)樵谄ヅ涞倪^程中存在著大量的錯(cuò)配點(diǎn)。消除錯(cuò)配點(diǎn)圖中交叉的綠線為錯(cuò)配點(diǎn)7/9/202327第27頁，課件共32頁，創(chuàng)作于2023年2月消除錯(cuò)配點(diǎn)

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

）是一種魯棒性的參數(shù)估計(jì)方法。RANSAC簡介RANSAC實(shí)質(zhì)上就是一個(gè)反復(fù)測(cè)試、不斷迭代的過程。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ù)。7/9/202328第28頁，課件共32頁，創(chuàng)作于2023年2月消除錯(cuò)配點(diǎn)RANSAC事例如何估計(jì)最佳直線？重復(fù)進(jìn)行，擬合最優(yōu)直線隨機(jī)取兩樣本點(diǎn)擬合直線擬合直線：Back7/9/202329第29頁，課件共32頁，創(chuàng)作于2023年2月SIFT算子的性能評(píng)價(jià)：(1)SIFT算子提取的圖像局部的特征，對(duì)亮度變化、尺度縮放以及旋轉(zhuǎn)保持不變性，而且對(duì)物體噪聲、仿射變換、視角變化保持穩(wěn)定性。(2)描述符獨(dú)特性好，信息量豐富，適用于海量特征數(shù)據(jù)的匹配，與Harris算子匹配方式相比準(zhǔn)確率較高。(3)由于SIF