特徵點檢測-SIFT

本文由知乎作者lowkeyway授權轉載，不得擅自二次轉載。

原文連結：https://zhuanlan.zhihu.com/p/90122194

在特徵點檢測的路上，註定要越走越遠。但也漸漸觸及到了傳統CV的核心，如果之前看到好多內容都是星星點點，那麼最近的內容就是組合這些散落的繁星，真正落實成能夠解決實際問題的美麗圖案。

為什麼要引入SIFT？

明確目的

不管是Harris還是Shi-Tomas，角點檢測檢測即便做得再優化，也總是有不可克服的缺點：

對尺度很敏感，不具有尺度不變性

需要設計角點匹配算法

咱們雖然從Harris一路過來，但是要理解這兩個缺點，還是有有一些潛在的共識。不管是Harris還是SIFT，再複雜的算法在理解之前一定要不斷提醒自己目的是什麼？

目的是尋找圖像中的特徵點！

所有的算法中做的努力都是為了更好的實踐這一目標。

什麼是特徵點？

那麼問題是，什麼是特徵點呢？簡單的說就是你感興趣的點。從人的視角邏輯：比如我們怎麼識別人跟人的區別？眼睛、鼻子、嘴巴就是良好的特徵點；我們如何識別良品和次品？物體的輪廓就是良好的特徵點；在傳統CV中，就是要讓計算機用它們自己的方式模擬識別宏觀上的特徵點。

如果讓計算機來做人臉識別，來做良品檢測，那麼首要的就是要讓計算機找到對應的特徵點，而且是顯著的具有良好特性的特徵點。什麼良好特性呢？比如局部不變性：

識別物體的縮放不應該影響物體的識別，大貓是貓，小貓也是貓！識別物體的旋轉不應該影響物體的識別，橫著的貓是貓，豎著的貓也是貓！

再識Harris

我們用這兩個「良好」去檢驗Harris，很容易得到Harris不具備尺度不變性（空間縮放后角點數量、相對位置會變化），但是具備旋轉不變性（旋轉後的角點還是角點，但是要識別兩張旋轉圖像之間的關係，需要獨立設定角點匹配算法）。

從原理上講就是圖片縮放前後的相關矩陣不相似，導致求解特徵點會不同。

（如果有讀者是算法專家，可以幫忙寫一篇數學推導，下面是我搜到的一篇文章）

https://blog.csdn.net/kxuehen/article/details/40313669

拯救尺度不變性

好了，有問題就會有人解決。

1999年Lowe提出了SIFT(Scale-invariant feature transform，尺度不變性特徵變換)特徵檢測算法，並於2004年對其完善總結。其應用範圍包含物體辨識、機器人地圖感知與導航、影像縫合、3D模型建立、手勢辨識、影像追蹤和動作比對。

在沒有誕生深度神經網絡的image net比賽中，SIFT一直都是霸榜的存在。在特徵點檢測的傳統CV算法中，SIFT也是No1的引用。

SIFT確立的特徵點不會因為視角的改變（尺度變化和旋轉變化）、光照的變化（亮度變化）、噪音的幹擾（噪聲幹擾）而消失，比如角點、邊緣點、暗區域的亮點以及亮區域的暗點。這樣如果兩幅圖像中有相同的景物，那麼這些穩定點就會在兩幅圖像的相同景物上同時出現，這樣就能實現匹配。

迫不及待了，SIFT怎麼做到的？

SIFT的實現

先提醒自己，我們的目的是什麼？尋找圖像中的特徵點，良好特徵點！

實現SIFT，可以分成如下幾個步驟。

構建高斯多尺度金字塔

為了解決尺度敏感問題，最正常的思路就是在多尺度下做運算。然後，要解決多尺度問題，首先就要搞清楚什麼是尺度空間？以及單尺度下該怎麼構建？

1、首先，要做的是要創建一個尺度空間。

有這個理解就夠了。Lowe告訴我們，在單尺度空間下要有6張圖片。（為什麼是6張的建議值，這裡先Mark一下，後面會提到），就像下圖：

單層空間中的五張圖片

這六張圖從左到右，分別是原圖（論文中的第一層實際上是把原圖的解析度提高了4倍 2M*2N）經過方差為  、  、  、  、  、  的高斯濾波後的圖片，即從左到右圖片應該越來越模糊。

算法規定（第一層）：

如果要用公式精確表示這裡的一張圖：

其中

 是二維高斯模糊的算子。

 是原圖

 表示卷積，即做了高斯模糊

 表示處理後的照片

2、然後，做這一層的DoG

高斯模糊咱們之前有聊過（而且不止一次），問題是，我們的現在要做的是特徵值檢測，做不同程度的高斯模糊有什麼用呢？

同一張圖片不同期望的高斯的插值

看，不同期望的高斯模糊後的圖片差值，是不是就有了一個物體的輪廓？輪廓是什麼？哈哈，最原始的特徵出現了！！！

用數學公式表示：

它就形象的被稱為difference of gaussian（DOG）

我們知道，一個空間尺度上有6張圖片。每相鄰的兩張圖片之差就會產生一張DoG， 所以總共可以產生5幅DoG:

相鄰兩張照片相減，得到一個DOG。

3、最後， 構建金字塔空間

如果說我們構造不同高斯模糊圖片是為了獲得帶有特徵值的DoG圖片，那麼下一步就該不忘初心，想一想怎麼解決尺度不變性。

Binggo！對，就是拿金字塔把特徵值拓展到多解析度上。

S=3， 展示3層金字塔，解析度是按照行列各1/2遞減

相同解析度的照片組成一個尺度空間，每個尺度空間由6張遞增高斯模糊處理的照片構成；

根據金字塔原理，把尺度空間拓展到3個，稱為高斯金字塔的組數。

這裡需要解釋幾個名詞和關鍵變量：

高斯金字塔的組數（Octave）：即尺度空間的個數。

S（Scale？）：表示一個尺度空間（也就是金字塔的一組）挑選出來做特徵值搜索的圖片個數（也即層數）。

係數 

高斯模糊的期望序列  ，  表示是高斯金字塔的第幾組。

多尺度空間構建好後，就可以得到DoG的多尺度空間：

番外篇：這些圖片有沒有讓你想起了想起了拉普拉斯金字塔？

檢測尺度空間的極值點

我們拿到了一組多空間下的帶有特徵值Dog金字塔，但是輪廓信息並不是我們的最終目的，我們想要的是特徵點，那下一步怎麼辦呢？Lowe說由輪廓的線變成點，那就找極值點吧。

1、 首先，我們要找到金字塔中一組的極值點。

怎麼找呢？暴力解決！一幅DoG圖像，從左到右，從上到下依次輪詢每個點，讓目標點跟它周圍的8鄰域的8個點比較，除此之外，我們每一層不是還生成了5幅DoG圖像嗎？同時也讓目標點跟它相鄰Scale的DoG圖像做三維的空間比較。

如下圖，這樣一個目標點就會同周邊26個點比較。

如果一個點經過如此比較後，確實是這26個點中的極大或極小值，就認為該點是圖像在該尺寸下的極值點。

S=3的一個空間尺度下的極值查找

可以想像，如果一個空間有6張圖，那麼產生5張DoG，到這裡就只有3張可供選擇的特徵點了（以內頂層和底層無法湊夠26個點），這也是S=3的由來！

2、然後，把它拓展到多尺度空間

其實，拓展這件事情很好做，只要在不同的尺度空間（金字塔的不同組）做一遍相同的事情就OK了，這也是保證多尺度不變性的關鍵。

但是，有一個隱藏的坑：怎麼保證最終得到的特徵點滿足尺度空間的連續性？

答案就在構建金字塔的時候一個尺度空間並不是拿原圖直接做解析度縮放，然後再依次做高斯模糊的，而是取上一張的倒數第3張圖像隔行採樣後作為下一組的第一張圖像！

6張圖片要減去倒數第一張變成了5張DoG，5張DoG裡面倒數第一張又不能參與特徵值的提取，是不是本尺度空間的關鍵信息點都是倒數第三張？如果為了保證下一個尺度空間的特徵值連續，是不是應該以該圖作為基準點做縮放？

我們知道對於尺度空間第o組，第s層的圖像，它的尺度為  ，其中，  ，那麼我們從第0組開始，看它各層的尺度。

第0組： 

第1組： 

我們只分析2組便可以看出，第1組的第0層圖像恰好與第0組的倒數第三幅圖像一致，尺度都為  ，所以我們不需要再根據原圖來重新卷積生成每組的第0張圖像，只需採用上一層的倒數第3張來降採樣即可。

另一個角度考慮，如果我們把它們的中間三項取出來拼在一起，則尺度為：  正好連續！！這一效果帶來的直接的好處是在尺度空間的極值點確定過程中，我們不會漏掉任何一個尺度上的極值點，而是能夠綜合考慮量化的尺度因子。

做完這兩個步驟後，應該就可以在原圖上畫出來極值點坐標了示意圖了：

精確定位極值點

嗯，不錯。極值點檢索完畢後是不是大功告成了？Lowe說還不夠完美。原因是我們求得的極值點的搜索是在離散空間中進行的，檢測到的極值點並不是真正意義上的極值點。比如上圖中紅色的叉標記圖像中的像素，但是真正的極值點是綠色的位於像素間的點

1、 首先，我們要明確為什麼要對定位後的極值點再做精確定位。

下圖顯示了一維信號離散空間得到的極值點與連續空間的極值點之間的差別。利用已知的離散空間點插值到連續空間極值點的方法叫子像元插值。

離散點並不能代表是真正意義上的極大極小值

2、 其次，再探討一下如何精確。

利用已知的離散空間點插值得到的連續空間極值點的方法叫做子像素插值（Sub-pixel Interpolation）為了提高關鍵點的穩定性，需要對尺度空間DoG函數進行曲線擬合。利用DoG函數在尺度空間的Taylor展開式(擬合函數)為：

其中  ，求導並讓方程等於零，可以得到極值點的偏移量為：

通過對x求偏導並將結果置為零，我們可以簡單地計算出方程的極值，從而得到子像素特徵點的位置，這些子像素點可以增加匹配和算法穩定性的機率。

若子像素點與近似特徵點間的偏移量大於0.5，則按照偏移近似特徵點的方向相應改變（移動）特徵點，然後再把該點當做近似特徵點，重複該操作（(Lowe算法裡最多迭代5次），直到子像素點與近似特徵點間的偏移量小於等於0.5。

得到最終候選點的精確位置與尺度  ，將其代入公式求得  ，求其絕對值得  。如果其絕對值低於閾值的將被刪除。

3、 刪除邊緣效應

為了得到穩定的特徵點，只是刪除DoG響應值低的點是不夠的。由於DoG對圖像中的邊緣有比較強的響應值，而一旦特徵點落在圖像的邊緣上，這些點就是不穩定的點。一方面圖像邊緣上的點是很難定位的，具有定位歧義性；另一方面這樣的點很容易受到噪聲的幹擾而變得不穩定。

一個平坦的DoG響應峰值往往在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。而主曲率可以通過2×2的Hessian矩陣H求出：

上式中，  值可以通過求取鄰近點像素的差分得到。  的特徵值與  的主曲率成正比例。我們可以避免求取具體的特徵值，因為我們只關心特徵值的比例。令  為最大的特徵值，  為最小的特徵值，那麼，我們通過  矩陣直跡計算它們的和，通過  矩陣的行列式計算它們的乘積：

如果  為最大特徵值與最小特徵值之間的比例，那麼  ，這樣便有

上式的結果只與兩個特徵值的比例有關，而與具體特徵值無關。當兩個特徵值相等時，  的值最小，隨著  的增加，  的值也增加。所以要想檢查主曲率的比例小於某一閾值  ，只要檢查下式是否成立：

Lowe在論文中給出的  。也就是說對於主曲率比值大於10的特徵點將被刪除。

這一堆東西真是晦澀，不過他的物理所用就是濾除大部分邊緣，去找真正的關鍵信息。

角點？不全是，角點關注的是兩個特徵值的大小，這裡關注的是兩個特徵值的比值。主要是去除DoG局部曲率非常不對稱的像素。

選取特徵點方向

好了，到這一步，我們已經完成了特徵點的篩選，並且通過高斯金字塔的設計實現了尺度不變性。接下來，就該去搞定旋轉不變性了。

這裡的旋轉不變性跟咱們角點自帶的旋轉不變性有一些不同。Harris的角點不變性靠的是旋轉後，該是角點的地方還是角點，所以對於整張圖對應的所有角點這個尺度看，它是具備旋轉不變性的。但是SIFT中，我們希望給每個特徵點賦值一個方向，這樣，對於單個特徵點來說，不管是如何縮放、旋轉，這個方向作為它的一個屬性都不會變。

了解了我們的目的，下一步就是要實現它，給每個特徵點附加一個方向屬性。

1、 首先，要明確什麼是特徵點的方向？

還記得Harris怎麼判斷角點、邊緣、團點的嗎？對，對某一方向求偏導。同理，特徵店的方向也可以通過選取特徵點周邊圖像，求梯度方向和大小。

求得的最顯著的梯度大小付給該特徵點，就稱為了該特徵點的方向！

2、 然後，想辦法求特徵點的方向。

採集其所在高斯金字塔圖像3σ鄰域窗口內像素的梯度和方向分布特徵。梯度的模值和方向如下：

L為關鍵點所在的尺度空間值，按Lowe的建議，梯度的模值m(x,y)按  的高斯分布加成，按尺度採樣的3σ原則，鄰域窗口半徑為 

在完成關鍵點的梯度計算後，使用直方圖統計鄰域內像素的梯度和方向。梯度直方圖將0~360度的方向範圍分為36個柱(bins)，其中每柱10度。如圖所示，直方圖的峰值方向代表了關鍵點的主方向，(為簡化，圖中只畫了八個方向的直方圖)。

直方圖的峰值則代表了該關鍵點處鄰域梯度的主方向，即作為該關鍵點的方向；其他的達到最大值80%的方向可作為輔助方向。

為了增強匹配的魯棒性，只保留峰值大於主方向峰值80％的方向作為該關鍵點的輔方向。因此，對於同一梯度值的多個峰值的關鍵點位置，在相同位置和尺度將會有多個關鍵點被創建但方向不同。僅有15％的關鍵點被賦予多個方向，但可以明顯的提高關鍵點匹配的穩定性。實際編程實現中，就是把該關鍵點複製成多份關鍵點，並將方向值分別賦給這些複製後的關鍵點，並且，離散的梯度方向直方圖要進行插值擬合處理，來求得更精確的方向角度值，

至此，將檢測出的含有位置、尺度和方向的關鍵點即是該圖像的SIFT特徵點。

生成關鍵點描述子

完美...了嗎？

金字塔保證特徵點的空間不變性， 嚴格刪選保證了特徵點的準確性， 方向信息保證了特徵點的旋轉不變性。我們如何把所有信息作為屬性附加給關鍵點呢？

1、 首先，要了解為什麼要給關鍵點增加描述子

通過上面的步驟，對於每一個關鍵點，擁有三個信息：位置、尺度以及方向。接下來就是為每個關鍵點建立一個描述符，用一組向量將這個關鍵點描述出來，使其不隨各種變化而改變，比如光照變化、視角變化等等。這個描述子不但包括關鍵點，也包含關鍵點周圍對其有貢獻的像素點，並且描述符應該有較高的獨特性，以便於提高特徵點正確匹配的概率。

2、 然後，考慮如何增加

SIFT描述子是關鍵點鄰域高斯圖像梯度統計結果的一種表示。通過對關鍵點周圍圖像區域分塊，計算塊內梯度直方圖，生成具有獨特性的向量，這個向量是該區域圖像信息的一種抽象，具有唯一性。

表示步驟如下：

特徵描述子與特徵點所在的尺度有關，因此，對梯度的求取應在特徵點對應的高斯圖像上進行。將關鍵點附近的鄰域劃分為d*d(Lowe建議d=4)個子區域，每個子區域做為一個種子點，每個種子點有8個方向。每個子區域的大小與關鍵點方向分配時相同。

以關鍵點為中心，4*4格為一個種子點，每個種子點8個方向。

每一個小格都代表了特徵點鄰域所在的尺度空間的一個像素 ，箭頭方向代表了像素梯度方向，箭頭長度代表該像素的幅值。然後在4×4的窗口內計算8個方向的梯度方向直方圖。繪製每個梯度方向的累加可形成一個種子點。

其中a，b為關鍵點在高斯金字塔圖像中的位置坐標。

如上統計的4*4*8=128個梯度信息即為該關鍵點的特徵向量。特徵向量形成後，為了去除光照變化的影響，需要對它們進行歸一化處理，對於圖像灰度值整體漂移，圖像各點的梯度是鄰域像素相減得到，所以也能去除。

描述子向量門限。非線性光照，相機飽和度變化對造成某些方向的梯度值過大，而對方向的影響微弱。因此設置門限值(向量歸一化後，一般取0.2)截斷較大的梯度值。然後，再進行一次歸一化處理，提高特徵的鑑別性。

按特徵點的尺度對特徵描述向量進行排序。

這群科學家，真讓人頭大。對於工程狗，其實就一張圖：

在每個4*4的1/16象限中，通過加權梯度值加到直方圖8個方向區間中的一個，計算出一個梯度方向直方圖。這樣就可以對每個feature形成一個4*4*8=128維的描述子，每一維都可以表示4*4個格子中一個的scale/orientation. 將這個向量歸一化之後，就進一步去除了光照的影響。

SIFT有什麼用？

我們了解過如何用SIFT生成特徵點，有了這些特徵點後，我們就可以做匹配了！

如何匹配？

1、 首先還是要對圖片生成特徵點

一張圖經過SIFT算法後，會得到多個特徵點，每個特徵點有128維的描述子屬性。那麼，匹配特徵點都簡單多啦！

生成了A、B兩幅圖的描述子，（分別是k1*128維和k2*128維），就將兩圖中各個scale（所有scale）的描述子進行匹配，匹配上128維即可表示兩個特徵點match上了。

2、 然後考慮怎麼匹配

當兩幅圖像的SIFT特徵向量生成後，下一步我們採用關鍵點特徵向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。取圖像1中的某個關鍵點，並找出其與圖像2中歐式距離最近的前兩個關鍵點，在這兩個關鍵點中，如果最近的距離除以次近的距離少於某個比例閾值，則接受這一對匹配點。降低這個比例閾值，SIFT匹配點數目會減少，但更加穩定。

寫代碼的時候才想起來，SIFT是在xfeatures2d模塊裡面的，而我們現在還在用官方編譯好的opencv_world410d.dll， 而且還有專利問題沒有解決。這些都需要我們自己編譯OpenCV的原始碼以及三方擴展庫。配置自己的環境。做了一篇環境配置的教程，分享一下：

https://zhuanlan.zhihu.com/p/90810839

C++

#include <opencv2/opencv.hpp>
#include <opencv2/xfeatures2d.hpp>
#include <iostream>

using namespace cv;
using namespace cv::xfeatures2d;
using namespace std;

int main(int argc, char** argv) {

Mat cat = imread("cat.png");
Mat smallCat = imread("smallCat.png");
imshow("cat image", cat);
imshow("smallCat image", smallCat);

auto detector = SIFT::create();
vector<KeyPoint> keypoints_cat, keypoints_smallCat;
Mat descriptor_cat, descriptor_smallCat;
detector->detectAndCompute(cat, Mat(), keypoints_cat, descriptor_cat);
detector->detectAndCompute(smallCat, Mat(), keypoints_smallCat, descriptor_smallCat);

Ptr<FlannBasedMatcher> matcher = FlannBasedMatcher::create();
vector<DMatch> matches;
matcher->match(descriptor_cat, descriptor_smallCat, matches);
Mat dst;
drawMatches(cat, keypoints_cat, smallCat, keypoints_smallCat, matches, dst);
imshow("match-demo", dst);
waitKey(0);
return 0;
}

catsmallCat輸出

參考：

https://blog.csdn.net/u010440456/article/details/81483145

https://www.cnblogs.com/ronny/p/4028776.html

本文僅用做學術分享，如有侵犯版權，請聯繫作者，會自行刪文。

歡迎加入我們公眾號讀者群一起和同行交流，目前有3D視覺、CV&深度學習、SLAM、三維重建、點雲後處理、自動駕駛、CV入門、醫療影像、缺陷檢測、行人重識別、目標跟蹤、視覺產品落地、視覺競賽、車牌識別等微信群，請掃描下面微信號加群，備註：」研究方向+學校/公司+暱稱「，例如：」3D視覺 + 上海交大 + 靜靜「。請按照格式備註，否則不予通過。添加成功後會根據研究方向邀請進去相關微信群。原創投稿也請聯繫。