SIFT算法~薛純

1、尺度不變特征變換匹配算法（SIFT算法）薛純Scale Invariant Feature TransformSIFT2022/6/2021. SIFT簡介2. SIFT算法實(shí)現(xiàn)細(xì)節(jié)3. SIFT算法的應(yīng)用領(lǐng)域Scale Invariant Feature TransformSIFT2022/6/203l 傳統(tǒng)的特征提取方法傳統(tǒng)的特征提取方法傳統(tǒng)的匹配算法往往是直接提取角點(diǎn)或邊緣，對環(huán)境的傳統(tǒng)的匹配算法往往是直接提取角點(diǎn)或邊緣，對環(huán)境的適應(yīng)能力較差適應(yīng)能力較差Scale Invariant Feature TransformSIFT2022/6/204 19991999年大衛(wèi)年大衛(wèi). .勞伊教

2、授提出勞伊教授提出SIFTSIFT（尺度不變特征變（尺度不變特征變換）算法，這種算法在換）算法，這種算法在20042004年被加以完善。年被加以完善。l SIFT提出提出David G. LoweUniversity of British ColumbiaScale Invariant Feature TransformSIFT2022/6/205l SIFT算法特點(diǎn)算法特點(diǎn)穩(wěn)定性。穩(wěn)定性。 快速性快速性準(zhǔn)確性準(zhǔn)確性 多量性多量性 可擴(kuò)展性可擴(kuò)展性Scale Invariant Feature TransformSIFT2022/6/206 l SIFTSIFT算法實(shí)現(xiàn)步驟簡述算法實(shí)現(xiàn)步驟簡述

3、SIFTSIFT算法的實(shí)質(zhì)可以歸為在不同尺度空間上查找特征點(diǎn)（關(guān)鍵點(diǎn)）的問題。算法的實(shí)質(zhì)可以歸為在不同尺度空間上查找特征點(diǎn)（關(guān)鍵點(diǎn)）的問題。Scale Invariant Feature TransformSIFT2022/6/207l SIFTSIFT算法實(shí)現(xiàn)步驟算法實(shí)現(xiàn)步驟（1 1） 關(guān)鍵點(diǎn)的檢測；關(guān)鍵點(diǎn)的檢測；（2 2） 關(guān)鍵點(diǎn)的方向；關(guān)鍵點(diǎn)的方向；（3 3）關(guān)鍵點(diǎn)的精確定位）關(guān)鍵點(diǎn)的精確定位（4 4） 關(guān)鍵點(diǎn)描述子的生成關(guān)鍵點(diǎn)描述子的生成 Scale Invariant Feature TransformSIFT2022/6/208關(guān)鍵點(diǎn)具有的三個(gè)特征：關(guān)鍵點(diǎn)具有的三個(gè)特征：尺度尺度

4、方向方向 大小大小哪些點(diǎn)是哪些點(diǎn)是SIFTSIFT中要查找的關(guān)鍵點(diǎn)（特征點(diǎn)）？中要查找的關(guān)鍵點(diǎn)（特征點(diǎn)）？ 這些點(diǎn)是一些十分突出的點(diǎn)不會(huì)因光照條件的改變而消失的穩(wěn)定點(diǎn)這些點(diǎn)是一些十分突出的點(diǎn)不會(huì)因光照條件的改變而消失的穩(wěn)定點(diǎn)Scale Invariant Feature TransformSIFT2022/6/209關(guān)鍵點(diǎn)檢測的相關(guān)概念尺度空間（scale space ）：物體都是通過一定的尺度來反映的。不同尺度的觀察而得到不同的變化。尺度越大圖像越模糊sift算法采用了高斯函數(shù)來建立尺度空間一個(gè)圖像的尺度空間L（x,y, ) ,定義為原始圖像I(x,y)與上述的一個(gè)可變尺度的2維高斯函數(shù)G(

5、x,y, ) 卷積運(yùn)算隨著的變化，建立起不同的尺度空間，或稱之為建立起圖像的高斯金字塔Scale Invariant Feature TransformSIFT2022/6/2010關(guān)鍵點(diǎn)檢測 高斯模糊 建立不同尺度空間，構(gòu)造高斯金字塔 DOG高斯差分金字塔 找其極值點(diǎn)得關(guān)鍵點(diǎn)Scale Invariant Feature TransformSIFT2022/6/2011 高斯模糊高斯模糊 原理：可以理解成每一個(gè)像素都取周邊像素的平均值 Scale Invariant Feature TransformSIFT2022/6/2012高斯模糊1：分配權(quán)重：正態(tài)分布2：高斯函數(shù)：正態(tài)分布的密度函數(shù)

6、叫做“高斯函數(shù)” 它的一維形式：計(jì)算平均值的時(shí)候，中心點(diǎn)就是原 點(diǎn)，所以等于0 二維形式：Scale Invariant Feature TransformSIFT2022/6/2013高斯模糊 3： 2221rrexp22G權(quán)重矩陣22r= xyr是模糊半徑，是模糊半徑，高斯函數(shù)高斯函數(shù)如果只計(jì)算這9個(gè)點(diǎn)的加權(quán)平均，還必須讓它們的權(quán)重之和等于1 。=1.5Scale Invariant Feature TransformSIFT2022/6/2014計(jì)算高斯模糊1：假設(shè)現(xiàn)有9個(gè)像素點(diǎn)，灰度值（0-255）如下 2：每個(gè)點(diǎn)乘以自己的權(quán)重值： 3：將這9個(gè)值加起來，就是中心點(diǎn)的高斯模糊的值。 S

7、cale Invariant Feature TransformSIFT2022/6/2015 高斯金子塔的構(gòu)建過程可高斯金子塔的構(gòu)建過程可分為兩步：分為兩步：（1 1）對圖像做高斯平滑；）對圖像做高斯平滑；（2 2）對圖像做降采樣。）對圖像做降采樣。 高斯金字塔里有兩個(gè)概念高斯金字塔里有兩個(gè)概念組（組（OctaveOctave）和層（）和層（LevelLevel或或IntervalInterval），每組里有若），每組里有若干層干層！ 高斯金字塔高斯金字塔Scale Invariant Feature TransformSIFT2022/6/201612Sk 高斯金字塔的構(gòu)成高斯金字塔的構(gòu)成

8、1：第一組的第一層為原圖像 2：圖像做一次高斯模糊參數(shù)取1.6 得第二層3：將k作為新的平滑因子來平滑第二層得到第三層4：得到L層他們分別對應(yīng)的平滑參數(shù)為：0，k，k2.。S每組層數(shù)（一般為35）1212( ,)inkkk尺度空間的所有取值：Scale Invariant Feature TransformSIFT2022/6/2017DoGDoG（Difference of GaussianDifference of Gaussian）函數(shù)）函數(shù), , ,*,L x yG x yI x y, , , ,*, , ,D x yG x y kG x yI x yL x y kL x yDoGDo

9、G在計(jì)算上只需相鄰尺度高斯平滑后圖像相減，因此簡化了計(jì)算！在計(jì)算上只需相鄰尺度高斯平滑后圖像相減，因此簡化了計(jì)算！Scale Invariant Feature TransformSIFT2022/6/2018DoGDoG高斯差分金字塔高斯差分金字塔對應(yīng)對應(yīng)DOGDOG算子，我們要構(gòu)建算子，我們要構(gòu)建DOGDOG金字塔金字塔我們可以通過高斯差分圖我們可以通過高斯差分圖像看出圖像上的像素值變像看出圖像上的像素值變化情況。（如果沒有變化，化情況。（如果沒有變化，也就沒有特征。特征必須也就沒有特征。特征必須是變化盡可能多的點(diǎn)。）是變化盡可能多的點(diǎn)。）DOGDOG圖像描繪的是目標(biāo)的圖像描繪的是目標(biāo)的輪

10、廓。輪廓。Scale Invariant Feature TransformSIFT2022/6/2019由高斯金字塔到DOGScale Invariant Feature TransformSIFT2022/6/2020 中間的檢測點(diǎn)和它同尺度的中間的檢測點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對應(yīng)的個(gè)相鄰點(diǎn)和上下相鄰尺度對應(yīng)的92個(gè)點(diǎn)共個(gè)點(diǎn)共26個(gè)點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測到極個(gè)點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測到極值點(diǎn)。值點(diǎn)。 l DoG的局部極值點(diǎn)的局部極值點(diǎn) 關(guān)鍵點(diǎn)是由關(guān)鍵點(diǎn)是由DOGDOG空間的局部極值點(diǎn)組成的?？臻g的局部極值點(diǎn)組成的。Scale Inva

11、riant Feature TransformSIFT2022/6/2021為了滿足尺度變化的連續(xù)性，為了滿足尺度變化的連續(xù)性，我們在每一組圖像的頂層繼續(xù)我們在每一組圖像的頂層繼續(xù)用高斯模糊生成了用高斯模糊生成了3幅圖像，幅圖像，高斯金字塔有每組高斯金字塔有每組S+3層圖像。層圖像。DOG金字塔每組有金字塔每組有S+2層圖像層圖像 右圖為不同尺度不同層間右圖為不同尺度不同層間極值檢測示意圖。極值檢測示意圖。Scale Invariant Feature TransformSIFT2022/6/2022l 關(guān)鍵點(diǎn)精確定位關(guān)鍵點(diǎn)精確定位1 1：利用：利用DoGDoG函數(shù)在尺度空間的函數(shù)在尺度空間的

12、TaylorTaylor展開式：展開式：2212TTDDD XDXXXXX 2:2:求導(dǎo)，并令其為求導(dǎo)，并令其為0 0，得極值點(diǎn)。，得極值點(diǎn)。3:3:保留絕對值大于等于保留絕對值大于等于0.030.03的特征點(diǎn)的特征點(diǎn)212()TDDXXX 12TDD XDXX可去除低對比度的點(diǎn)可去除低對比度的點(diǎn)Scale Invariant Feature TransformSIFT2022/6/2023l 去除邊緣響應(yīng)去除邊緣響應(yīng)利用利用HessianHessian矩陣判斷關(guān)鍵點(diǎn)是否位于邊緣矩陣判斷關(guān)鍵點(diǎn)是否位于邊緣xxxyxyyyDDHDDxxD表示表示DOGDOG金字塔中某一尺度的圖像金字塔中某一尺度

13、的圖像x x方向求導(dǎo)兩次方向求導(dǎo)兩次DoG函數(shù)峰值點(diǎn)在橫跨邊緣的方向有較大的主曲率，函數(shù)峰值點(diǎn)在橫跨邊緣的方向有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。而在垂直邊緣的方向有較小的主曲率。D的主曲率和的主曲率和H的特征值成正比的特征值成正比高斯函數(shù)在邊緣易產(chǎn)生噪聲高斯函數(shù)在邊緣易產(chǎn)生噪聲Scale Invariant Feature TransformSIFT2022/6/2024221Tr HrDet Hr 在兩特征值相等時(shí)達(dá)最小，隨在兩特征值相等時(shí)達(dá)最小，隨r的增長而增長。的增長而增長。Lowe論文中建議論文中建議r取取10。21rrr2221Tr HrDet Hr D的主曲率和的主

14、曲率和H的特征值成正比，為了避免直接的計(jì)算這些特征值，而只的特征值成正比，為了避免直接的計(jì)算這些特征值，而只是考慮它們的之間的比率。令為是考慮它們的之間的比率。令為 最大特征值最大特征值 ， 為最小的特征值，則為最小的特征值，則xxyyTr HDDxxyyxyxyDet HDDDD時(shí)將關(guān)鍵點(diǎn)保留，反之剔除時(shí)將關(guān)鍵點(diǎn)保留，反之剔除xxxyxyyyDDHDDl 去除邊緣響應(yīng)去除邊緣響應(yīng)Scale Invariant Feature TransformSIFT2022/6/2025關(guān)鍵點(diǎn)檢測關(guān)鍵點(diǎn)檢測（a）233x189像素的原始圖像像素的原始圖像（b）DOG算法得到的算法得到的832個(gè)極個(gè)極值點(diǎn)值

15、點(diǎn)（c）精確定位后，精確定位后，729個(gè)關(guān)鍵點(diǎn)個(gè)關(guān)鍵點(diǎn) （d）去除邊緣響應(yīng)后，）去除邊緣響應(yīng)后，536個(gè)關(guān)鍵個(gè)關(guān)鍵點(diǎn)點(diǎn)Scale Invariant Feature TransformSIFT2022/6/2026 ,IIgradI x yxy22,1,1,1,1m x yL xyL xyL x yL x y1,1,1,tan1,1,L x yL x yx yL xyL xyl 像素點(diǎn)的梯度表示像素點(diǎn)的梯度表示梯度幅值：梯度方向：我們通過求每個(gè)極值點(diǎn)的梯度來為極值點(diǎn)賦予方向使其我們通過求每個(gè)極值點(diǎn)的梯度來為極值點(diǎn)賦予方向使其具備旋轉(zhuǎn)不變性。具備旋轉(zhuǎn)不變性。 Scale Invariant Fe

16、ature TransformSIFT2022/6/2027以關(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計(jì)鄰域像素的梯度方向梯度直方圖的范圍是0360度其中每45度一個(gè)柱，總共8個(gè)柱或者每10度一個(gè)柱，總共36個(gè)柱 方向直方圖的生成方向直方圖的生成Scale Invariant Feature TransformSIFT2022/6/2028 關(guān)鍵點(diǎn)主方向：關(guān)鍵點(diǎn)主方向：直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向即作為該關(guān)鍵點(diǎn)的方向 關(guān)鍵點(diǎn)輔方向：關(guān)鍵點(diǎn)輔方向：當(dāng)存在另一個(gè)相當(dāng)于主峰值當(dāng)存在另一個(gè)相當(dāng)于主峰值 80%能量

17、的峰值能量的峰值 選定倆個(gè)方向的原因：選定倆個(gè)方向的原因： 這可以增強(qiáng)匹配的魯棒性這可以增強(qiáng)匹配的魯棒性，穩(wěn)定性，穩(wěn)定性。 關(guān)鍵點(diǎn)的主方向與輔方向關(guān)鍵點(diǎn)的主方向與輔方向Scale Invariant Feature TransformSIFT2022/6/2029l 描述的目的描述的目的l 描述的思路描述的思路 通過對關(guān)鍵點(diǎn)周圍圖像區(qū)域分塊，計(jì)算塊內(nèi)梯度直方圖，生通過對關(guān)鍵點(diǎn)周圍圖像區(qū)域分塊，計(jì)算塊內(nèi)梯度直方圖，生成具有獨(dú)特性的向量，成具有獨(dú)特性的向量，描述關(guān)鍵點(diǎn)和關(guān)鍵點(diǎn)周圍對其有貢獻(xiàn)的像素點(diǎn)。描述關(guān)鍵點(diǎn)和關(guān)鍵點(diǎn)周圍對其有貢獻(xiàn)的像素點(diǎn)。Scale Invariant Feature Trans

18、formSIFT2022/6/2030將坐標(biāo)移至關(guān)鍵點(diǎn)主方向?qū)⒆鴺?biāo)移至關(guān)鍵點(diǎn)主方向那么旋轉(zhuǎn)角度后新坐標(biāo)為：那么旋轉(zhuǎn)角度后新坐標(biāo)為： cossinsincosxxyy Scale Invariant Feature TransformSIFT2022/6/2031將這個(gè)向量歸一化之后，就進(jìn)一步去除了光照的影響。 1：選?。哼x取16*16鄰域，然后將這個(gè)大區(qū)域分為鄰域，然后將這個(gè)大區(qū)域分為16個(gè)個(gè)4*4區(qū)域區(qū)域:2：分別對每個(gè)：分別對每個(gè)4*4區(qū)域區(qū)域8方向分布最后，共有方向分布最后，共有16*8=128維向量來表征維向量來表征這個(gè)特征點(diǎn)。這個(gè)特征點(diǎn)。 Scale Invariant Feature TransformSIFT2022/6/203212128,iiiiRr rr12128,iiiiSsss12821,iiijijjd