全网最详细SIFT算法原理实现
文章目錄
- 一、SIFT算法
- 1.1什么是SIFT算法？
- 1.2SIFT算法特點
- 二、SIFT算法實質
- 2.1SIFT算法實現特征匹配主要有以下三個流程：
- 三、SIFT算法原理
- 3.1圖像金字塔
- 3.2創建圖像高斯金字塔
- 3.3高斯金字塔創建總圖
- 四、尺度空間
- 五、高斯差分金字塔
- 5.1極值點(Key points)的精確定位
- 5.2確定關鍵點（極值點）方向
- 5.3關鍵點描述
- 5.4關鍵點匹配
- 六、sift代碼
- 七、總結
一、SIFT算法
1.1什么是SIFT算法？
尺度不變特征轉換(SIFT, Scale Invariant Feature Transform)是圖像處理領域中的一種局部特征描述算法. 該方法于1999年由加拿大教授David G.Lowe提出，申請了專利，其專利屬于英屬哥倫比亞大學. SIFT專利在2020年3月17日之后到期，現在只需更新cv版本即可免費使用.
SIFT算法不僅只有尺度不變性，當旋轉圖像，改變圖像亮度，移動拍攝位置時，仍可得到較好的檢測效果.
其實，在我們生活中，SIFT算法還是有所應用的，比如，我們手機上的全景拍攝，當我們拿著手機旋轉拍攝時，就可以得到一幅全景圖，大家想過沒有，手機攝像頭的視角是確定的，為什么通過旋轉拍攝時，角度就變大了呢？其實角度并沒有變化，只是我們在旋轉拍攝時，拍攝了很多的圖像，這些圖像相鄰之間有重疊部分，把這些圖像合在一起，去除重疊部分，就可以得到一幅全景圖啦.
1.2SIFT算法特點
- 具有較好的穩定性和不變形，能夠適當旋轉、尺度縮放、亮度的變化，能在一定程度上不受視角變化、仿射變換、噪聲的干擾。
- 區分性好，能夠在海量特征數據庫中進行快速準確的區分信息進行匹配
- 多屬性，就算只有單個物體，也能產生大量特征向量
- 高速性，能夠快速的進行特征向量匹配
- 可擴展性，能夠與其它形式的特征向量進行聯合
二、SIFT算法實質
在不同的尺度空間上查找關鍵點，并計算出關鍵點的方向。
2.1SIFT算法實現特征匹配主要有以下三個流程：
三、SIFT算法原理
3.1圖像金字塔
圖像金字塔是一種以多分辨率來解釋圖像的結構，通過對原始圖像進行多尺度像素采樣的方式，生成N個不同分辨率的圖像。把具有最高級別分辨率的圖像放在底部，以金字塔形狀排列，往上是一系列像素（尺寸）逐漸降低的圖像，一直到金字塔的頂部只包含一個像素點的圖像，這就構成了傳統意義上的圖像金字塔。
獲得圖像金字塔一般包括二個步驟：
利用低通濾波器平滑圖像
對平滑圖像進行抽樣（采樣）
有兩種采樣方式——上采樣（分辨率逐級升高）和下采樣（分辨率逐級降低）
上采樣：
下采樣：
3.2創建圖像高斯金字塔
什么是圖像高斯金字塔？
在說高斯金字塔之前，我們先來說一下人的眼睛，我們人眼對世界的感知有兩種特性：一是近大遠小：同一物體，近處看時感覺比較大，遠處看時感覺比較小；二是"模糊"：更準確說應該是"粗細"，我們看近處，可以看到物體的細節(人會覺得比較清楚)，比如一片樹葉，近看可以看到該樹葉的紋理，遠處看只能看到該片的大概輪廓(人會覺得比較模糊). 從頻率的角度出發，圖像的細節(比如紋理，輪廓等)代表圖像的高頻成分，圖像較平滑區域表示圖像的低頻成分.
圖像高斯金字塔實際上是一種圖像的尺度空間(分線性和非線性空間，此處僅討論線性空間)，尺度的概念用來模擬觀察者距離物體的遠近程度，在模擬物體遠近的同時，還得考慮物體的粗細程序.
綜上，圖像的尺度空間是模擬人眼看到物體的遠近程度以及模糊程度.
圖像高斯金字塔就考慮了這兩個方面：① 圖像的遠近程度；② 圖像的模糊程度(理解為粗細更好).
那該怎么模擬圖像的遠近程度呢？
采樣法(上采樣，下采樣)
比如一幅圖像，對于每一行，隔一個像素點取一個像素點，那么最后得到的圖像就是原圖像的行和列各1/2. 這屬于下采樣的一種.
那該怎么模擬圖像的粗細程序呢？
采用高斯核對圖像進行平滑處理，因為高斯卷積核是實現尺度變換的唯一線性核.
上面，我們從一個感性的角度去理解高斯金字塔的形成過程，現在我們來理性分析高斯金字塔的創建過程。
高斯金字塔式在Sift算子中提出來的概念，首先高斯金字塔并不是一個金字塔，而是有很多組（Octave）金字塔構成，并且每組金字塔都包含若干層（Interval）。
高斯金字塔構建過程：
先將原圖像擴大一倍之后作為高斯金字塔的第1組第1層，將第1組第1層圖像經高斯卷積（其實就是高斯平滑或稱高斯濾波）之后作為第1組金字塔的第2層，高斯卷積函數為：
對于參數σ，在Sift算子中取的是固定值1.6。
將σ乘以一個比例系數k,等到一個新的平滑因子σ=k*σ，用它來平滑第1組第2層圖像，結果圖像作為第3層。
如此這般重復，最后得到L層圖像，在同一組中，每一層圖像的尺寸都是一樣的，只是平滑系數不一樣。它們對應的平滑系數分別為：0，σ，kσ，k2σ,k3σ……k^(L-2)σ。
將第1組倒數第三層圖像作比例因子為2的降采樣，得到的圖像作為第2組的第1層，然后對第2組的第1層圖像做平滑因子為σ的高斯平滑，得到第2組的第2層，就像步驟2中一樣，如此得到第2組的L層圖像，同組內它們的尺寸是一樣的，對應的平滑系數分別為：0，σ，kσ，k2σ,k3σ……k^(L-2)σ。但是在尺寸方面第2組是第1組圖像的一半。
這樣反復執行，就可以得到一共O組，每組L層，共計O*L個圖像，這些圖像一起就構成了高斯金字塔，結構如下：
在同一組內，不同層圖像的尺寸是一樣的，后一層圖像的高斯平滑因子σ是前一層圖像平滑因子的k倍；
在不同組內，后一組第一個圖像是前一組倒數第三個圖像的二分之一采樣，圖像大小是前一組的一半；
高斯金字塔圖像效果如下，分別是第1組的4層和第2組的4層：
3.3高斯金字塔創建總圖
其中
式(1)中，M 為原始圖像的行高；N 為原始圖像的列寬；O 為圖像高斯金字塔的組數.
式(2)中，n 為待提取圖像特征的圖像數；S 為圖像高斯金字塔每組的層數.
為了方便計算，從0開始記錄組數或層數
(3)中，o 為組索引序號，r 為層索引序號，σ (o, r ) 為對應的圖像的高斯模糊系數.
σ0σ_0σ0?為高斯模糊初始值，David G.Lowe 教授剛開始設置為1.6，考慮相機實際已對圖像進行σ=0.5的模糊處理，故實際：
通過式(3)，可以計算對應圖像金字塔中的高斯模糊系數，如下：
第0組，第0層：
第0組，第1層：
第0組，第2層：
…
…
第1組，第0層：
第1組，第1層：
第1組，第2層：
…
…
第2組，第0層：
第2組，第1層：
第2組，第2層：
…
…
由上述計算，我們知道
① 每一組內，相鄰層之間的高斯模糊系統相差 21/n2^{1/n}21/n；
② 第0組第0層，第1組第第0層，第2組第0層，…，的高斯模糊系數分別為σ0,2σ0,4σ0,...σ_0,2σ_0,4σ_0,...σ0?,2σ0?,4σ0?,... ;
③ 下一組的第0層為上一組倒數第3層降采樣所得，無須進行高斯模糊操作.
總的過程，如圖2所示：
四、尺度空間
圖像的尺度空間解決的問題是如何對圖像在所有尺度下描述的問題。
在高斯金字塔中一共生成O組L層不同尺度的圖像，這兩個量合起來（O，L）就構成了高斯金字塔的尺度空間，也就是說以高斯金字塔的組O作為二維坐標系的一個坐標，不同層L作為另一個坐標，則給定的一組坐標（O,L）就可以唯一確定高斯金字塔中的一幅圖像。
尺度空間的形象表述：
上圖中尺度空間中k前的系數n表示的是第一組圖像尺寸是當前組圖像尺寸的n倍
五、高斯差分金字塔
創建好圖像高斯金字塔后，每一組內的相鄰層相減可以得到高斯差分金字塔(DoG, Difference of Gaussian)，是后期檢測圖像極值點的前提，如圖2所示：
DOG金字塔的第1組第1層是由高斯金字塔的第1組第2層減第1組第1層得到的。以此類推，逐組逐層生成每一個差分圖像，所有差分圖像構成差分金字塔。概括為DOG金字塔的第o組第l層圖像是有高斯金字塔的第o組第l+1層減第o組第l層得到的。
每一組在層數上，DOG金字塔比高斯金字塔少一層。后續Sift特征點的提取都是在DOG金字塔上進行的。
DOG金字塔的顯示效果如下：
下邊對這些DOG圖像進行歸一化，可有很明顯的看到差分圖像所蘊含的特征，并且有一些特征是在不同模糊程度、不同尺度下都存在的，這些特征正是Sift所要提取的“穩定”特征：
5.1極值點(Key points)的精確定位
閾值化
其中，T = 0.04，可人為設定其值；n為待提取特征的圖像數；abs(val)為圖像的像素值. 設定像素閾值，為了去除一些噪點或其它一些不穩定像素點.
在高斯差分金字塔中尋找極值點
特征點是由DOG空間的局部極值點組成的。為了尋找DoG函數的極值點，每一個像素點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。
如下圖所示：在高斯差分金字塔中尋找極值點，除了考慮x，y方向的點，還要考慮σ 方向的點，所以判斷一個像素點是否為極值點，要與周圍的26個點進行比較.
注：
① 如果高斯差分金字塔每組有3層，則只能在中間1層圖像尋 找極值點，
兩端的圖像不連續，沒有極值點.
② 如果高斯差分金字塔每組有5層，則只能在中間3層圖像尋找極值點.
依此類推…
當我們檢測到極值點之后，會發現一個問題，高斯差分金字塔是離散的(因為尺度空間和像素點都是離散的)，所以找到的極值點不太準確的，很大可能在真正極值點附近，如圖4所示，為了找到更高亞像素位置精度的極值點，需利用泰勒展開式.
更正極值點位置
在檢測到的極值點處，作三元二階泰勒展開：
f(x)對x進行求導：
令導數為零
帶入f(x),可得
注：
上述求解的結束標志：達到一定的迭代次數.
求解亞像素精度極值點時，當所得解超出離散極值點一定范圍舍去，
因為泰勒展開只是在離散點附近能夠較好的擬合原函數.
舍去低對比度的點
若|f(x)|<T/n,則舍去點X
去除邊緣效應
本質上要去掉DoG局部曲率非常不對稱的像素. 一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率通過一個2×2的海森矩陣(Hessian Matrix)H求出，D的主曲率和H的特征值成正比，令α 為較大特征值，β 為較小的特征值.
注：最終得到像素點坐標(x,y)可以不是整數,σ可以不是在高斯金字塔的某一層上.
5.2確定關鍵點（極值點）方向
1、通過尺度不變性求極值點，需要利用圖像的局部特征為給每一個關鍵點分配一個基準方向，使描述子對圖像旋轉具有不變性。對于在DOG金字塔中檢測出的關鍵點，采集其所在高斯金字塔圖像3σ鄰域窗口內像素的梯度和方向分布特征。梯度的模值和方向如下：
2、本算法采用梯度直方圖統計法，統計以關鍵點為原點，一定區域內的圖像像素點確定關鍵點方向。在完成關鍵點的梯度計算后，使用直方圖統計鄰域內像素的梯度和方向。梯度直方圖將0~360度的方向范圍分為36個柱，其中每柱10度。如下圖所示，直方圖的峰值方向代表了關鍵點的主方向，方向直方圖的峰值則代表了該特征點處鄰域梯度的方向，以直方圖中最大值作為該關鍵點的主方向。為了增強匹配的魯棒性，只保留峰值大于主方向峰值80％的方向作為該關鍵點的輔方向。
統計以特征點為圓心，以該特征點所在的高斯圖像的尺度的1.5倍為半徑的圓內的所有的像素的梯度方向及其梯度幅值，并做1.5σ的高斯濾波(高斯加權，離圓心也就是關鍵點近的幅值所占權重較高).
5.3關鍵點描述
上述過程，只是找到關鍵點并確定了其方向，但SIFT算法核心用途在于圖像的匹配，我們需要對關鍵點進行數學層面的特征描述，也就是構建關鍵點描述符.
1、確定計算描述子所需的圖像區域
描述子梯度方向直方圖由關鍵點所在尺度的高斯圖像計算產生. 圖像區域的半徑通過下式(17)計算：
d=4，代表劃分4x4個子塊
2、將坐標移到關鍵點方向
關鍵點所在的半徑區域，移至關鍵點方向，如下圖所示
3、生成關鍵點描述符
將區域劃分為4x4的子塊，對每一個子塊進行8個方向的直方圖統計操作，獲得每個方向的梯度幅值，總共可以組成128維描述向量。
對于每一個關鍵點，都擁有位置、尺度以及方向三個信息。為每個關鍵點建立一個描述符，用一組向量將這個關鍵點描述出來，使其不隨各種變化而改變，比如光照變化、視角變化等等。這個描述子不但包括關鍵點，也包含關鍵點周圍對其有貢獻的像素點，并且描述符應該有較高的獨特性，以便于提高特征點正確匹配的概率。
實驗表明：描述子采用4x4x8=128維向量表示，效果最優
5.4關鍵點匹配
1、分別對模板圖（參考圖，reference image）和實時圖（觀測圖，observation image）建立關鍵點描述子集合。目標的識別是通過兩點集內關鍵點描述子的比對來完成。具有128維的關鍵點描述子的相似性度量采用歐式距離。
2、匹配可采取窮舉法完成，但所花費的時間太多。所以一般采用kd樹的數據結構來完成搜索。搜索的內容是以目標圖像的關鍵點為基準，搜索與目標圖像的特征點最鄰近的原圖像特征點和次鄰近的原圖像特征點。
Kd樹如下如所示，是個平衡二叉樹
六、sift代碼
import cv2 import numpy as np import matplotlib.pyplot as plt#1、讀取圖像 img=cv2.imread('cat.jpg') cat=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)#2、sift關鍵點檢測 #sift實例化對象 sift=cv2.xfeatures2d.SIFT_create()# 2.2關鍵點檢測：kp關鍵點信息包括方向，尺度，位置信息，des是關鍵點的描述符 kp,des=sift.detectAndCompute(cat,None)# 2.3在圖像上繪制關鍵點的檢測結果 cv2.drawKeypoints(img,kp,img,flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)#3圖像顯示 plt.figure(figsize=(8,6),dpi=100) plt.imshow(img[:,:,::-1]),plt.title('sift') plt.xticks([]),plt.yticks([]) plt.show()七、總結
SIFT特征具有穩定性和不變性，在圖像處理和計算機視覺領域有著很重要的作用，其本身也是非常復雜的，由于接觸SIFT不是很久，對其中的相關知識了解還很不足，經多方查閱參考，寫得此文，內容還不夠詳盡，望多多見諒。以下是SIFT算法的粗略總結。
1、DoG尺度空間的極值檢測。
2、刪除不穩定的極值點。
3、確定特征點的主方向
4、生成特征點的描述子進行關鍵點匹配。
參考文章
https://blog.csdn.net/qq_37374643/article/details/88606351
https://zhuanlan.zhihu.com/p/343522892?ivk_sa=1024320u
總結
以上是生活随笔為你收集整理的全网最详细SIFT算法原理实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： gvim for php,转 ： Gvi
- 下一篇： 树莓派Raspberry pi 4B 运