SIFT算法

????????SIFT（Scale Invariant Feature Transform），尺度不變特征變換。具有旋轉(zhuǎn)不變性、尺度不變性、亮度變化保持不變性，是一種非常穩(wěn)定的局部特征。在目標(biāo)檢測和特征提取方向占據(jù)著重要的地位。

? ? ? ? SIFT算法所查找到的關(guān)鍵點是一些很突出，不因光照、仿射變換和噪聲等因素而變化的點，比如角點、邊緣點、暗區(qū)亮點或亮區(qū)暗點等。

SIFT算法步驟

? ? ? ? 1. 尺度空間極值檢測：在各個尺度的圖像上搜索極值位置。通過高斯差分函數(shù)識別潛在的對于尺度和旋轉(zhuǎn)不變的關(guān)鍵點。

? ? ? ? 2. 確定關(guān)鍵點位置：在每個潛在的位置上，通過一個擬合的精細(xì)模型確定位置和尺度。關(guān)鍵點的選擇依據(jù)于其穩(wěn)定程度。

? ? ? ? 3. 確定關(guān)鍵點方向：基于局部圖像的梯度方向，給每個關(guān)鍵點位置分配了一個或多個方向。所有后面對圖像數(shù)據(jù)的操作都相對于關(guān)鍵點的方向、尺度和位置進行變換，從而保證此類變換的不變性。

? ? ? ? 4. 關(guān)鍵點描述：在每個關(guān)鍵點周圍鄰域內(nèi)，在給定尺度上測量圖像局部的梯度，這些梯度作為關(guān)鍵點的描述符，允許比較大的局部形狀的變化或光照變化。

尺度空間極值檢測

? ? ? ? 當(dāng)我們近距離和遠(yuǎn)距離看一個物體時，模糊程度是不一樣的，從近距離到遠(yuǎn)距離圖像細(xì)節(jié)越來越模糊。在SIFT中，圖像的尺度的意思也是類似的，注意這里的尺度空間指的不是圖像的大小，而是圖像的模糊程度。

????????從頻域的角度看，圖像的模糊程度代表的頻域信息的低頻成分和高頻成分。?模糊圖像代表信息大部分都集中低頻，僅含少量的高頻信息。圖像清晰代表信息成分豐富，高低頻的信息都有。

????????高斯核是唯一可以產(chǎn)生多尺度空間的核函數(shù)。這一點在T Lindeber的文獻《Scale-space theory: a basic tool for analyzing structures at different scales》中被證明。

? ? ? ? 圖像的尺度空間定義為原始圖像(x,y)與一個可變尺度的二維高斯函數(shù)的卷積運算，即：

????????

? ? ? ? 其中：

????????是尺度空間因子，它決定了圖像的模糊程度。當(dāng)較大時，尺度較大，圖像模糊，顯示的是概況為主。較小時，尺度較小，顯示的是更多細(xì)節(jié)。

? ? ? ? 到這里，相信大家對尺度空間的概念應(yīng)該有了一定認(rèn)識。如果還不清楚，我這里舉一個不太恰當(dāng)?shù)睦樱?/p>

? ? ? ? 假設(shè)有兩個人A和B站在同一窗戶旁邊看向遠(yuǎn)處的一顆樹。A是馬賽人，視力極其牛逼；B是一個300度的近視眼。A和B所看到的樹的圖像就屬于不同尺度空間。在這里就可以理解為近視度數(shù)。

? ? ? ? 在計算高斯函數(shù)離散近似時，距離之外的像素所起的作用幾乎為0，因此可以忽略掉這些像素，一般在實際應(yīng)用時，高斯卷積核只要計算就可以了。?

? ? ? ? 在SIFT做尺度空間極值檢測時，需要構(gòu)建高斯金字塔，高斯金字塔的細(xì)節(jié)，請在“參考”中的鏈接"高斯金字塔"中去查看。得到高斯金字塔后，我們就得到了不同大小的圖片組（octave），每個octave由多個不同尺度的圖像組成。

原圖地址：高斯金字塔_小鹿煥煥的博客-CSDN博客

? ? ? ? 要找到尺度空間下的極值，可以使用LoG（高斯拉普拉斯方法）來求得，這在邊緣檢測筆記中有提到，其本質(zhì)就是使用圖像的二階導(dǎo)數(shù)來計算。但LoG的計算量較大，在SIFT算法原始論文中，提到了使用高斯差分函數(shù)來做歸一化拉普拉斯算子的近似，通過兩個相鄰高斯尺度空間圖像直接相減即可：

?

? ? ? ? D(DoG)函數(shù)和LoG之間的關(guān)系：

?? ? ? ? 具體證明可以參考下面的鏈接：

DoG和LoG算子 - 知乎DoG(Difference of Gaussian)算子和LoG(Laplacian of Gaussian)算子是常用的極值點檢測(Blob Detection)兩種方法，高斯卷積是為了進行尺度變換，那么LapLacian呢。 因此這里首先引入LapLacian算子。 圖像邊緣檢測…https://zhuanlan.zhihu.com/p/49447503? ? ? ? 通過DoG算子，我們可以得到高斯差分金字塔，具體計算很簡單，對每一個octave中相鄰兩個尺度的圖像做減法即可：

? ? ? ? ?可以看到，DoG金字塔每個Octave的層數(shù)是原始高斯金字塔層數(shù) - 1。

? ? ? ? 接下來，通過DoG金字塔來查找不同尺度空間中的局部最大值或最小值。如下圖：

? ? ? ? ?對于某個像素點（圖中以X標(biāo)記）來說，它需要與自己相鄰的8個鄰域，以及尺度空間中相鄰的上下兩層的18個臨近點（2x9）做比較。如果該點的值在所有這些點中是最大或最小的，則該點可能是一個關(guān)鍵點，這個點會作為候選點。

? ? ? ? 局部最大值的搜索過程從每組的第二層開始，以第二層為當(dāng)前層，對當(dāng)前層的DoG圖像中的每一個點都和26個（當(dāng)前層8個+上下臨近層各9個）臨近點進行比較。搜索得到的極值點包含的信息既有位置坐標(biāo)（DoG圖像坐標(biāo)），也有尺度空間信息（第幾層）。當(dāng)?shù)诙铀阉魍瓿珊螅缘谌龑訛楫?dāng)前層重復(fù)局部最大值搜索過程。當(dāng)S = 3時，表示每組里面要搜索3層，因此DoG里需要有S+2層，最初構(gòu)建的高斯金字塔就需要有S+3層。

確定關(guān)鍵點位置（精確定位關(guān)鍵點）

? ? ? ? 前一步我們找到的候選極值點，是在離散空間上的候選極值點，這樣檢測出的極值點，和真實極值點位置有一定差異，為了更精確地定位到真正的極值點，SIFT算法中使用了尺度空間函數(shù)的三元二階泰勒展開來定位。

? ? ? ? 假設(shè)我們檢測到的極值點為，則該點對應(yīng)的泰勒展開為：

????????

? ? ? ? 我們用向量替換?，它表示曲線上某個點相對于候選極值點的一個偏移量，用表示向量。則會得到：

????????

? ? ? ? 這里的就是我們說的尺度空間函數(shù)的近似多項式形式,因此我們可以簡單認(rèn)為和是一樣的，后續(xù)推導(dǎo)會繼續(xù)使用這個符號。

????????我們知道，二階泰勒展開的目的是為了得到一個多項式來近似出原函數(shù)。得到這個展開式后，要求真實的極值點，其實就是求這個函數(shù)一階導(dǎo)數(shù)為0的位置。

? ? ? ? ?首先，求出這個函數(shù)的一階導(dǎo)數(shù)：

????????最右邊的這種形式的矩陣是一個二次型，對其求導(dǎo)可得

? ? ? ? 由于二次型矩陣的系數(shù)矩陣的轉(zhuǎn)置和其本身相等，因此

? ? ? ? 綜上，?可得函數(shù)的一階導(dǎo)為：

????????

? ? ? ? 讓導(dǎo)數(shù)為零，求解：

????????

? ? ? ? 將代回到泰勒展開式中，有:

????????

? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ?

????????定位極值點的過程，本質(zhì)是通過擬合出的曲線來求極值點位置并不斷迭代：

? ? ? ? 迭代的意思是找到一個更精確的極值點位置后，再以它為基礎(chǔ)，去擬合出一條曲線定位這條曲線上的極值點。因此需要注意兩個問題：迭代次數(shù)要加以限制（多次計算后都沒有收斂，三個分量都沒有小于0.5）；如果求出的極值點位置超出了一定范圍（比如0.5表示點的位置太遠(yuǎn)，因為泰勒展開式在特定點位置附近能較好地擬合出曲線，太遠(yuǎn)了就不準(zhǔn)確了）。

? ? ? ? 舍去低對比度的點：

? ? ? ? 前面通過泰勒展開得到了比較粗的關(guān)鍵點位置，此時的關(guān)鍵點可能會包含一些低對比度的像素噪聲。通過對比極值點的灰度值和一個閾值(一般是0.03左右，論文里假定像素值的范圍是[0,1]）來決定是否要舍去極值點。小于閾值算法認(rèn)為該點是一個噪聲，會舍去。

? ? ? ? 去除邊緣響應(yīng)：

? ? ? ? DoG在邊緣上會有很強的響應(yīng)，沿著邊緣上的點如果不做處理也會被判斷為關(guān)鍵點。為了去除邊緣響應(yīng)，需要引入黑森（海森）矩陣來做處理。

????????

? ? ? ?引入黑森矩陣H的目的是因為H描述了曲線的局部曲率，黑森矩陣的特征值標(biāo)定了函數(shù)在相應(yīng)特征向量方向上變化的快慢程度。如果函數(shù)在該點的不同方向上的曲率變化差不多，則其為角點。黑森矩陣的特征值和局部曲率是成正比的?(可以類比一下Harris角點檢測算法，如果檢測出邊，則其M矩陣的特征值中是某一個大，某一個??；如果檢測到角點，則兩個特征值都大)。

? ? ? ? SIFT算法中，也沒有直接去求H矩陣的特征值，而是通過矩陣的跡和行列式的比值來間接得知兩者的關(guān)系:

????????

????????

? ? ? ? 其中和為兩個特征值，并且。表示為兩個特征值的最大的一個，且為的r倍。

? ? ? ? 當(dāng)Det(H)小于0時，去掉點X，因此此時兩個特征值異號，變化不均勻，為邊緣。

? ? ? ? 當(dāng)和同號并且，那么r大于1，通過跡的平方和行列式比值來做檢測：

????????

? ? ? ? 從這個表達式可以看出，只有兩個特征值幾乎相等時，這個表達式值最小，表達式的值隨著r變大而變大。函數(shù)是一個單調(diào)遞增的函數(shù)，最小值為4：

?????????因此，在SIFT算法中，會設(shè)定一個閾值r（論文中取的是10），然后判斷下面這個不等式是否成立：

????????

? ? ? ? 如果不滿足此條件，則表示該點不符合要求，會被丟棄。

關(guān)鍵點檢測過程概覽總結(jié)

? ? ? ? (a) 原始233x189圖像；

????????(b) DoG函數(shù)極值檢測出的最初832個關(guān)鍵點位置；

? ? ? ? (c) 使用閾值去掉低對比度的點后剩下729個關(guān)鍵點；

? ? ? ? (d) 去除邊緣響應(yīng)后，最終剩下536個關(guān)鍵點。

確定關(guān)鍵點的方向

????????為了讓關(guān)鍵點具有旋轉(zhuǎn)不變性，SIFT算法會將特征點區(qū)域統(tǒng)一旋轉(zhuǎn)到特定方向，這一方向即為特征點區(qū)域的主方向。如何確定這個方向呢？

????????對于每個關(guān)鍵點，SIFT統(tǒng)計以該點所在的高斯尺度圖像中，以該點為圓心、半徑為3*1.5（此半徑并未從我看到的論文中查到，參考的是網(wǎng)絡(luò)中的資料，請注意）的圓內(nèi)，所有的像素的梯度方向及其梯度幅值。每個點的梯度和幅值計算方法如下：

????????

? ? ? ? 從前面精確定位關(guān)鍵點的小節(jié)我們知道，關(guān)鍵點的尺度（亞像素級）大概率和原始高斯金字塔中的特定尺度不是同一個值。這里說所的高斯圖像的尺度，是通過找到和亞像素級的關(guān)鍵點尺度值最接近的那一層高斯圖像。（注意：此時計算梯度和幅值是在高斯金字塔中的圖像中進行，并非DoG金字塔中的圖像）。

? ? ? ? 將計算得到的信息用直方圖表示（論文中以每10度為一個范圍，也就是有36個方向，下面的圖為示意圖，沒有畫出36個方向）：

? ? ? ? 直方圖的每一個bin（柱）為10度，在圓內(nèi)梯度方向在這個角度的像素都找出來，然后將他們的幅值相加作為這個bin（柱）的高度。需要注意的是，離圓心越遠(yuǎn)的像素對幅值的貢獻程度就越小，實際計算幅值相加時，并非簡單地加和，而是會通過高斯函數(shù)加權(quán)而來，高斯函數(shù)的方差為1.5。

? ? ? ? 直方圖峰值所對應(yīng)的方向為主方向，任何大于峰值80%的方向為特征點的輔方向。這里得到的方向角度值是一個范圍，要更精確地知道具體的角度，可以通過擬合直方圖中主方向和輔方向的拋物線來獲取。

????????現(xiàn)在，我們就得到了關(guān)鍵點的三個關(guān)鍵信息：位置、尺度和方向。?

關(guān)鍵點特征描述符

? ? ? ? 接下來，我們要對關(guān)鍵點建立特征描述符，描述符不僅包含了關(guān)鍵點的信息，也包含了關(guān)鍵點周圍對其有貢獻的像素點信息。主要思路是將關(guān)鍵點周圍的像素區(qū)域進行分塊，計算塊內(nèi)的梯度直方圖，然后得到特征向量。

? ? ? ? 描述符和特征點所在的尺度是相關(guān)的，因此描述符是在關(guān)鍵點對應(yīng)的高斯尺度圖像上進行生成的。以關(guān)鍵點為中心，將其附近鄰域劃分為d*d個子區(qū)域（d一般為4）,每個區(qū)域是一個正方形。統(tǒng)計每個正方形區(qū)域內(nèi)的梯度信息。對于要統(tǒng)計的關(guān)鍵點的區(qū)域，為了保證旋轉(zhuǎn)不變性，需要先將圖像的x軸旋轉(zhuǎn)到關(guān)鍵點的主方向上。

? ? ? ? ?然后，在每個子塊內(nèi)，統(tǒng)計像素在8個方向上的梯度值，統(tǒng)計梯度值的時候一般會進行高斯加權(quán)。

?? ? ? ? ? d一般為4，表示有16個子塊，每個子塊會得到8個值（8個方向），將這8個梯度信息記錄下來就得到了關(guān)鍵點的特征描述符。因此，一個特征描述符的維度是：4*4*8 = 128。

參考資料

? ? ? ? 高斯金字塔

高斯金字塔_小鹿煥煥的博客-CSDN博客1、為什么要構(gòu)建高斯金字塔高斯金字塔模仿的是圖像的不同的尺度，尺度應(yīng)該怎樣理解？對于一副圖像，你近距離觀察圖像，與你在一米之外觀察，看到的圖像效果是不同的，前者比較清晰，后者比較模糊，前者比較大，后者比較小，通過前者能看到圖像的一些細(xì)節(jié)信息，通過后者能看到圖像的一些輪廓的信息，這就是圖像的尺度，圖像的尺度是自然存在的，并不是人為創(chuàng)造的。好了，到這里我們明白了，其實以前對一幅圖像的處理還是比較單調(diào)的，因為我們的關(guān)注點只落在二維空間，并沒有考慮到“圖像的縱深”這樣一個概念，如果將這些內(nèi)容考慮進去我們是不是會_高斯金字塔https://blog.csdn.net/qq_44771627/article/details/123840316? ? ? ? SIFT算法原始論文

https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdfhttps://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf

圖像算法：Difference of Gaussian(DOG) 高斯函數(shù)差分_高斯差分_SSS_369的博客-CSDN博客概念Difference of Gaussian(DOG)是高斯函數(shù)的差分。它是可以通過將圖像與高斯函數(shù)進行卷積得到一幅圖像的低通濾波結(jié)果，即去噪過程，這里的Gaussian和高斯低通濾波器的高斯一樣，是一個函數(shù)，即為正態(tài)分布函數(shù)。同時，它對高斯拉普拉斯LoG的近似，在某一尺度上的特征檢測可以通過對兩個相鄰高斯尺度空間的圖像相減，得到DoG的響應(yīng)值圖像?；纠碚撌紫?，高斯函數(shù)..._高斯差分https://blog.csdn.net/sss_369/article/details/84674639SIFT算法詳解_夜半罟霖的博客-CSDN博客大綱引言一、高斯金字塔二、高斯差分金字塔三、特征點處理1.閾值化2.非極大值抑制3. 二階泰勒修正待續(xù)引言?SIFT算法是為了解決圖片的匹配問題，想要從圖像中提取一種對圖像的大小和旋轉(zhuǎn)變化保持魯棒的特征，從而實現(xiàn)匹配。這一算法的靈感也十分的直觀：人眼觀測兩張圖片是否匹配時會注意到其中的典型區(qū)域（特征點部分），如果我們能夠?qū)崿F(xiàn)這一特征點區(qū)域提取過程，再對所提取到的區(qū)域進行描述就可以實現(xiàn)特征匹配了。于是問題就演變成了以下幾個子問題：應(yīng)該選取什么樣的點作為特征點呢？：人眼對圖像中的高頻區(qū)域更加的敏感，由此_sift算法https://blog.csdn.net/Dr_maker/article/details/121442210

? ????????關(guān)于二次型矩陣和其求導(dǎo)的相關(guān)內(nèi)容，可參考這里：

二次型 - AcWing高數(shù)https://www.acwing.com/blog/content/35231/

二次型求導(dǎo)的推導(dǎo)過程? - 知乎直接給你看我們上課的PPT吧下圖中的a對應(yīng)xT，b對應(yīng)Ax，過程就是直接套下面這個公式， 最后一步，求導(dǎo)要…https://www.zhihu.com/question/22455493/answer/131136246?utm_id=0

極值點的精確定位_嗶哩嗶哩_bilibili極值點的精確定位是6.SIFT(尺度不變特征變換)的第2集視頻，該合集共計5集，視頻收藏或關(guān)注UP主，及時了解更多相關(guān)視頻內(nèi)容。https://www.bilibili.com/video/BV1Qb411W7cK/?p=2&vd_source=474bff49614e62744eb84e9f8340d91a

? ? ? ? 多元函數(shù)的泰勒展開

多元函數(shù)的泰勒展開 - 知乎類比一元函數(shù)的泰勒公式 f(x) = f(x_k)+(x-x_k)f'(x_k)+\frac{1}{2!}(x-x_k)^2f''(x_k)+\cdot\cdot\cdot+\frac{1}{n!}(x-x_k)^nf^{(n)}(x_k)+o^n 根據(jù)多元函數(shù)求偏導(dǎo)的法則，我們可以推出多元函數(shù)的泰…https://zhuanlan.zhihu.com/p/490766872

? ? ? ?黑森矩陣

https://www.cnblogs.com/zywnnblog/p/16605038.htmlhttps://www.cnblogs.com/zywnnblog/p/16605038.html? ? ? ? 有限差分方法

????????有限差分方法（圖像處理必學(xué)）知識點講解(論文資料) - 豆丁網(wǎng)有限差分方法（圖像處理必學(xué)）知識點講解(論文資料)https://www.docin.com/p-1288918830.html文章來源地址http://www.zghlxwxcb.cn/news/detail-578933.html

到了這里，關(guān)于關(guān)鍵點檢測SIFT算法筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！