算法詳解及應(yīng)用

尺度不變特征變換匹配算法

ScaleInvariantFeatureTransform

（SIFT）宋丹109050569/28/20231SIFT簡介SIFT算法實(shí)現(xiàn)細(xì)節(jié)提綱SIFT算法的應(yīng)用領(lǐng)域SIFT算法的擴(kuò)展與改進(jìn)9/28/20232SIFT簡介傳統(tǒng)的特征提取方法

成像匹配的核心問題是將同一目標(biāo)在不同時間、不同分辨率、不同光照、不同位姿情況下所成的像相對應(yīng)。傳統(tǒng)的匹配算法往往是直接提取角點(diǎn)或邊緣，對環(huán)境的適應(yīng)能力較差，急需提出一種魯棒性強(qiáng)、能夠適應(yīng)不同光照、不同位姿等情況下能夠有效識別目標(biāo)的方法。9/28/202331999年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簡介9/28/20234SIFT簡介將一幅圖像映射（變換）為一個局部特征向量集；特征向量具有平移、縮放、旋轉(zhuǎn)不變性，同時對光照變化、仿射及投影變換也有一定不變性。OriginalimagecourtesyofDavidLowe9/28/20235SIFT簡介

SIFT算法特點(diǎn)

SIFT特征是圖像的局部特征，其對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。

獨(dú)特性(Distinctiveness)好，信息量豐富，適用于在海量特征數(shù)據(jù)庫中進(jìn)行快速、準(zhǔn)確的匹配。

多量性，即使少數(shù)的幾個物體也可以產(chǎn)生大量SIFT特征向量。經(jīng)過優(yōu)化的SIFT算法可滿足一定的速度需求。

可擴(kuò)展性，可以很方便的與其他形式的特征向量進(jìn)行聯(lián)合。

9/28/20236

目標(biāo)的自身狀態(tài)、場景所處的環(huán)境和成像器材的成像特性等因素影響圖像配準(zhǔn)/目標(biāo)識別跟蹤的性能。而SIFT算法在一定程度上可解決：

目標(biāo)的旋轉(zhuǎn)、縮放、平移（RST）圖像仿射/投影變換（視點(diǎn)viewpoint）光照影響（illumination）目標(biāo)遮擋（occlusion）雜物場景（clutter）噪聲

SIFT算法可以解決的問題SIFT簡介Back9/28/20237SIFT算法實(shí)現(xiàn)細(xì)節(jié)

SIFT算法實(shí)現(xiàn)步驟簡述SIFT算法的實(shí)質(zhì)可以歸為在不同尺度空間上查找特征點(diǎn)（關(guān)鍵點(diǎn)）的問題。

SIFT算法實(shí)現(xiàn)物體識別主要有三大工序，1、提取關(guān)鍵點(diǎn)；2、對關(guān)鍵點(diǎn)附加詳細(xì)的信息（局部特征）也就是所謂的描述器；3、通過兩方特征點(diǎn)（附帶上特征向量的關(guān)鍵點(diǎn)）的兩兩比較找出相互匹配的若干對特征點(diǎn)，也就建立了景物間的對應(yīng)關(guān)系。9/28/20238

關(guān)鍵點(diǎn)檢測

關(guān)鍵點(diǎn)描述關(guān)鍵點(diǎn)匹配消除錯配點(diǎn)SIFT算法實(shí)現(xiàn)細(xì)節(jié)

SIFT算法實(shí)現(xiàn)步驟9/28/20239所謂關(guān)鍵點(diǎn)，就是在不同尺度空間的圖像下檢測出的具有方向信息的局部極值點(diǎn)。根據(jù)歸納，我們可以看出特征點(diǎn)具有的三個特征：

尺度方向大小關(guān)鍵點(diǎn)檢測的相關(guān)概念1.哪些點(diǎn)是SIFT中要查找的關(guān)鍵點(diǎn)（特征點(diǎn)）？這些點(diǎn)是一些十分突出的點(diǎn)不會因光照條件的改變而消失，比如角點(diǎn)、邊緣點(diǎn)、暗區(qū)域的亮點(diǎn)以及亮區(qū)域的暗點(diǎn)，既然兩幅圖像中有相同的景物，那么使用某種方法分別提取各自的穩(wěn)定點(diǎn)，這些點(diǎn)之間會有相互對應(yīng)的匹配點(diǎn)。9/28/202310我們要精確表示的物體都是通過一定的尺度來反映的?，F(xiàn)實(shí)世界的物體也總是通過不同尺度的觀察而得到不同的變化。尺度空間理論最早在1962年提出，其主要思想是通過對原始圖像進(jìn)行尺度變換，獲得圖像多尺度下的尺度空間表示序列，對這些序列進(jìn)行尺度空間主輪廓的提取，并以該主輪廓作為一種特征向量，實(shí)現(xiàn)邊緣、角點(diǎn)檢測和不同分辨率上的特征提取等。尺度空間中各尺度圖像的模糊程度逐漸變大，能夠模擬人在距離目標(biāo)由近到遠(yuǎn)時目標(biāo)在視網(wǎng)膜上的形成過程。尺度越大圖像越模糊。2.什么是尺度空間（scalespace

）？關(guān)鍵點(diǎn)檢測的關(guān)鍵點(diǎn)檢測的相關(guān)概念9/28/202311根據(jù)文獻(xiàn)《Scale-spacetheory:Abasictoolforanalysingstructuresatdifferentscales》我們可知，高斯核是唯一可以產(chǎn)生多尺度空間的核，一個圖像的尺度空間，L（x,y,σ),定義為原始圖像I(x,y)與一個可變尺度的2維高斯函數(shù)G(x,y,σ)卷積運(yùn)算。關(guān)鍵點(diǎn)檢測高斯函數(shù)尺度是自然存在的，不是人為創(chuàng)造的！高斯卷積只是表現(xiàn)尺度空間的一種形式…關(guān)鍵點(diǎn)檢測的相關(guān)概念9/28/2023123.高斯模糊

高斯模糊是在AdobePhotoshop等圖像處理軟件中廣泛使用的處理效果，通常用它來減小圖像噪聲以及降低細(xì)節(jié)層次。這種模糊技術(shù)生成的圖像的視覺效果是好像經(jīng)過一個半透明的屏幕觀察圖像。

關(guān)鍵點(diǎn)檢測關(guān)鍵點(diǎn)檢測的相關(guān)概念9/28/202313關(guān)鍵點(diǎn)檢測r為模糊半徑，在減小圖像尺寸的場合經(jīng)常使用高斯模糊。在進(jìn)行欠采樣的時，通常在采樣之前對圖像進(jìn)行低通濾波處理。這樣就可以保證在采樣圖像中不會出現(xiàn)虛假的高頻信息。

關(guān)鍵點(diǎn)檢測的相關(guān)概念9/28/202314在實(shí)際應(yīng)用中，在計(jì)算高斯函數(shù)的離散近似時，在大概3σ距離之外的像素都可以看作不起作用，這些像素的計(jì)算也就可以忽略。通常，圖像處理程序只需要計(jì)算關(guān)鍵點(diǎn)檢測高斯模板大小的選擇0.000000670.000022920.000191170.000387710.000191170.000022920.000000670.000022920.000786330.006559650.013303730.006559650.000786330.000022920.000191170.006559650.054721570.110981640.054721570.006559650.000191170.000387710.013303730.110981640.225083520.110981640.013303730.000387710.000191170.006559650.054721570.110981640.054721570.006559650.000191170.000022920.000786330.006559650.013303730.006559650.000786330.000022920.000000670.000022920.000191170.000387710.000191170.000022920.00000067高斯模板關(guān)鍵點(diǎn)檢測的相關(guān)概念9/28/202315高斯模糊具有圓對稱性。高斯模糊具有線性可分的性質(zhì)，也可以在二維圖像上對兩個獨(dú)立的一維空間分別進(jìn)行計(jì)算。這樣可以大大減少了運(yùn)算的次數(shù)。對一幅圖像進(jìn)行多次連續(xù)高斯模糊的效果與一次更大的高斯模糊可以產(chǎn)生同樣的效果，大的高斯模糊的半徑是所用多個高斯模糊半徑平方和的平方根。例如，使用半徑分別為6和8的兩次高斯模糊變換得到的效果等同于一次半徑為10的高斯模糊效果，根據(jù)這個關(guān)系，使用多個連續(xù)較小的高斯模糊處理不會比單個高斯較大處理時間要少。高斯模糊的性質(zhì)關(guān)鍵點(diǎn)檢測關(guān)鍵點(diǎn)檢測的相關(guān)概念9/28/202316高斯金子塔的構(gòu)建過程可分為兩步：（1）對圖像做高斯平滑；（2）對圖像做降采樣。

為了讓尺度體現(xiàn)其連續(xù)性，在簡單下采樣的基礎(chǔ)上加上了高斯濾波。一幅圖像可以產(chǎn)生幾組（octave）圖像，一組圖像包括幾層（interval）圖像。4.高斯金字塔關(guān)鍵點(diǎn)檢測關(guān)鍵點(diǎn)檢測的相關(guān)概念9/28/202317高斯圖像金字塔共o組、s層，則有：關(guān)鍵點(diǎn)檢測的相關(guān)概念σ——尺度空間坐標(biāo)；s——sub-level層坐標(biāo)；σ0——初始尺度；S——每組層數(shù)（一般為3~5）。9/28/202318高斯金字塔的初始尺度當(dāng)圖像通過相機(jī)拍攝時，相機(jī)的鏡頭已經(jīng)對圖像進(jìn)行了一次初始的模糊，所以根據(jù)高斯模糊的性質(zhì)：M、N分別為圖像的行數(shù)和列數(shù)——第0層尺度——被相機(jī)鏡頭模糊后的尺度高斯金字塔的組數(shù)關(guān)鍵點(diǎn)檢測的相關(guān)概念9/28/202319高斯金字塔的組內(nèi)尺度與組間尺度組內(nèi)尺度是指同一組（octave）內(nèi)的尺度關(guān)系，組內(nèi)相鄰層尺度化簡為：組間尺度是指不同組直接的尺度關(guān)系，相鄰組的尺度可化為：由此可見，相鄰兩組的同一層尺度為2倍的關(guān)系關(guān)鍵點(diǎn)檢測的相關(guān)概念9/28/202320最后可將組內(nèi)和組間尺度歸為：i——金字塔組數(shù)n——每一組的層數(shù)關(guān)鍵點(diǎn)檢測的相關(guān)概念9/28/202321關(guān)鍵點(diǎn)檢測的相關(guān)概念上一組圖像的底層是由前一組圖像的倒數(shù)第二層圖像隔點(diǎn)采樣生成的。這樣可以保持尺度的連續(xù)性。9/28/202322

關(guān)鍵點(diǎn)檢測——DOG通過研究Lowe教授的論文發(fā)現(xiàn)，所有特征點(diǎn)的檢測都是基于了尺度不變的特性，特征點(diǎn)的檢測占據(jù)了論文的大部分的篇章，具有十分重要的意義！Lindeberg在文獻(xiàn)《Scale-spacetheory:Abasictoolforanalysingstructuresatdifferentscales》指出尺度規(guī)范化的LoG算子具有真正的尺度不變性。LoG算子即（LaplacionofGaussian）,可以由高斯函數(shù)梯度算子GOG構(gòu)建尺度規(guī)范化的GoG算子尺度規(guī)范化的LoG算子9/28/202323LOG算子與高斯核函數(shù)的關(guān)系通過推導(dǎo)可以看出，LOG算子與高斯核函數(shù)的差有直接關(guān)系，由此引入一種新的算子DOG（DifferenceofGaussians），即高斯差分算子。關(guān)鍵點(diǎn)檢測——DOG9/28/202324DoG（DifferenceofGaussian）函數(shù) DoG在計(jì)算上只需相鄰尺度高斯平滑后圖像相減，因此簡化了計(jì)算！關(guān)鍵點(diǎn)檢測——DOG9/28/202325DoG高斯差分金字塔 對應(yīng)DOG算子，我們要構(gòu)建DOG金字塔我們可以通過高斯差分圖像看出圖像上的像素值變化情況。（如果沒有變化，也就沒有特征。特征必須是變化盡可能多的點(diǎn)。）DOG圖像描繪的是目標(biāo)的輪廓。關(guān)鍵點(diǎn)檢測——DOG9/28/202326關(guān)鍵點(diǎn)檢測——DOG9/28/202327

在檢測極值點(diǎn)前對原始圖像的高斯平滑以致圖像丟失高頻信息，所以Lowe建議在建立尺度空間前首先對原始圖像長寬擴(kuò)展一倍，以保留原始圖像信息，增加特征點(diǎn)數(shù)量。在Lowe的論文中，將第0層的初始尺度定為1.6，圖片的初始尺度定為0.5，則圖像金字塔第0層的實(shí)際尺度為

當(dāng)對圖像長寬擴(kuò)展一倍時，便構(gòu)建了-1層，該層尺度為關(guān)鍵點(diǎn)檢測——DOGP.S.:圖像插值時，選用的插值函數(shù)可以是多種多樣的。9/28/202328

中間的檢測點(diǎn)和它同尺度的8個相鄰點(diǎn)和上下相鄰尺度對應(yīng)的9×2個點(diǎn)共26個點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測到極值點(diǎn)。

DoG的局部極值點(diǎn)

關(guān)鍵點(diǎn)是由DOG空間的局部極值點(diǎn)組成的。為了尋找DoG函數(shù)的極值點(diǎn)，每一個像素點(diǎn)要和它所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度域的相鄰點(diǎn)大或者小。DoG局部極值檢測9/28/202329

在極值比較的過程中，每一組圖像的首末兩層是無法進(jìn)行極值比較的，為了滿足尺度變化的連續(xù)性，我們在每一組圖像的頂層繼續(xù)用高斯模糊生成了3幅圖像，高斯金字塔有每組S+3層圖像。DOG金字塔每組有S+2層圖像右圖為不同尺度不同層間極值檢測示意圖。P.S.:我們只犧牲了-1組的第0層和第N組的最高層DoG局部極值檢測9/28/202330DoG局部極值檢測關(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)。9/28/202331DoG局部極值檢測

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

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

求解得9/28/202332DoG局部極值檢測去除邊緣響應(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)兩次9/28/202333

在兩特征值相等時達(dá)最小，隨r的增長而增長。Lowe論文中建議r取10。DoG局部極值檢測

D的主曲率和H的特征值成正比，為了避免直接的計(jì)算這些特征值，而只是考慮它們的之間的比率。令為最大特征值，為最小的特征值，則時將關(guān)鍵點(diǎn)保留，反之剔除9/28/202334關(guān)鍵點(diǎn)方向分配

通過尺度不變性求極值點(diǎn)，可以使其具有縮放不變的性質(zhì)，利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性，我們可以為每個關(guān)鍵點(diǎn)指定方向參數(shù)方向，從而使描述子對圖像旋轉(zhuǎn)具有不變性。像素點(diǎn)的梯度表示梯度幅值：梯度方向：我們通過求每個極值點(diǎn)的梯度來為極值點(diǎn)賦予方向。9/28/202335關(guān)鍵點(diǎn)方向分配方向直方圖的生成

確定關(guān)鍵點(diǎn)的方向采用梯度直方圖統(tǒng)計(jì)法，統(tǒng)計(jì)以關(guān)鍵點(diǎn)為原點(diǎn)，一定區(qū)域內(nèi)的圖像像素點(diǎn)對關(guān)鍵點(diǎn)方向生成所作的貢獻(xiàn)。9/28/2023361.直方圖以每10度方向?yàn)橐粋€柱，共36個柱，柱所代表的方向?yàn)橄袼攸c(diǎn)梯度方向，柱的長短代表了梯度幅值。2.根據(jù)Lowe的建議，直方圖統(tǒng)計(jì)半徑采用3*1.5*σ。3.在直方圖統(tǒng)計(jì)時，每相鄰三個像素點(diǎn)采用高斯加權(quán)，根據(jù)Lowe的建議，模板采用[0.25,0.5,0.25]，并連續(xù)加權(quán)兩次。關(guān)鍵點(diǎn)方向分配關(guān)于方向直方圖的幾點(diǎn)說明9/28/202337關(guān)鍵點(diǎn)方向分配關(guān)鍵點(diǎn)主方向：極值點(diǎn)周圍區(qū)域梯度直方圖的主峰值,也是特征點(diǎn)方向關(guān)鍵點(diǎn)輔方向：在梯度方向直方圖中，當(dāng)存在另一個相當(dāng)于主峰值

80%能量的峰值時，則將這個方向認(rèn)為是該關(guān)鍵點(diǎn)的輔方向。

這可以增強(qiáng)匹配的魯棒性，Lowe的論文指出大概有15%關(guān)鍵點(diǎn)具有多方向，但這些點(diǎn)對匹配的穩(wěn)定性至為關(guān)鍵。

關(guān)鍵點(diǎn)的主方向與輔方向9/28/202338關(guān)鍵點(diǎn)方向分配確定計(jì)算關(guān)鍵點(diǎn)直方圖的高斯函數(shù)權(quán)重函數(shù)參數(shù)；生成含有36柱的方向直方圖，梯度直方圖范圍0~360度，其中每10度一個柱。由半徑為圖像區(qū)域生成；對方向直方圖進(jìn)行兩次平滑；求取關(guān)鍵點(diǎn)方向（可能是多個方向）；對方向直方圖的Taylor展開式進(jìn)行二次曲線擬合，精確關(guān)鍵點(diǎn)方向；方向分配實(shí)現(xiàn)步驟

圖像的關(guān)鍵點(diǎn)已檢測完畢，每個關(guān)鍵點(diǎn)有三個信息：位置、尺度、方向；同時也就使關(guān)鍵點(diǎn)具備平移、縮放、和旋轉(zhuǎn)不變性。Back9/28/202339關(guān)鍵點(diǎn)描述描述的目的描述的思路

通過對關(guān)鍵點(diǎn)周圍圖像區(qū)域分塊，計(jì)算塊內(nèi)梯度直方圖，生成具有獨(dú)特性的向量，這個向量是該區(qū)域圖像信息的一種抽象，具有唯一性。

描述的目的是在關(guān)鍵點(diǎn)計(jì)算后，用一組向量將這個關(guān)鍵點(diǎn)描述出來，這個描述子不但包括關(guān)鍵點(diǎn)，也包括關(guān)鍵點(diǎn)周圍對其有貢獻(xiàn)的像素點(diǎn)。用來作為目標(biāo)匹配的依據(jù)，也可使關(guān)鍵點(diǎn)具有更多的不變特性，如光照變化、3D視點(diǎn)變化等。9/28/202340關(guān)鍵點(diǎn)描述

下圖是一個SIFT描述子事例。其中描述子由2×2×8維向量表征，也即是2×2個8方向的方向直方圖組成。左圖的種子點(diǎn)由8×8單元組成。每一個小格都代表了特征點(diǎn)鄰域所在的尺度空間的一個像素，箭頭方向代表了像素梯度方向，箭頭長度代表該像素的幅值。然后在4×4的窗口內(nèi)計(jì)算8個方向的梯度方向直方圖。繪制每個梯度方向的累加可形成一個種子點(diǎn)，如右圖所示：一個特征點(diǎn)由4個種子點(diǎn)的信息所組成。9/28/202341關(guān)鍵點(diǎn)描述

Lowe實(shí)驗(yàn)結(jié)果表明：描述子采用4×4×8＝128維向量表征，綜合效果最優(yōu)（不變性與