算法詳解及應用

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

ScaleInvariantFeatureTransform

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

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

SIFT算法特點

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

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

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

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

9/28/20236

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

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

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

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

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

關鍵點檢測

關鍵點描述關鍵點匹配消除錯配點SIFT算法實現(xiàn)細節(jié)

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

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

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

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

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

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

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

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

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

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

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

DoG的局部極值點

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

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

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

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

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

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

求解得9/28/202332DoG局部極值檢測去除邊緣響應

僅僅去除低對比度的極值點對于極值點的對于特征點穩(wěn)定性是遠遠不夠的。DoG函數(shù)在圖像邊緣有較強的邊緣響應，因此我們還需要排除邊緣響應。DoG函數(shù)的（欠佳的）峰值點在橫跨邊緣的方向有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率可以通過計算在該點位置尺度的2×2的Hessian矩陣得到，導數(shù)由采樣點相鄰差來估計：表示DOG金字塔中某一尺度的圖像x方向求導兩次9/28/202333

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

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

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

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

80%能量的峰值時，則將這個方向認為是該關鍵點的輔方向。

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

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

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

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

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

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

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