sift演算法提取特徵點

『壹』 sift演算法是什麼

Sift演算法是David Lowe於1999年提出的局部特徵描述子，並於2004年進行了更深入的發展和完善。Sift特徵匹配演算法可以處理兩幅圖像之間發生平移、旋轉、仿射變換情況下的匹配問題，具有很強的匹配能力。

這一演算法的靈感也十分的直觀，人眼觀測兩張圖片是否匹配時會注意到其中的典型區域（特徵點部分），如果我們能夠實現這一特徵點區域提取過程，再對所提取到的區域進行描述就可以實現特徵匹配了。

sift演算法的應用

SIFT演算法目前在軍事、工業和民用方面都得到了不同程度的應用，其應用已經滲透了很多領域，典型的應用如下：物體識別；機器人定位與導航；圖像拼接；三維建模；手勢識別；視頻跟蹤；筆記鑒定；指紋與人臉識別；犯罪現場特徵提取。

『貳』 圖像特徵之SIFT特徵匹配

SIFT具有尺度不變性和旋轉不變性。具體分為：

尺度規范化的Laplacian of Gaussian(LoG)運算元具有尺度不變性。在具體實現中，可用Difference of Gaussian(DoG)運算元近似LoG運算元，在構建的尺度空間中檢測穩定的特徵點。

因此尺度空間的構架包含：

sigma越大丟失的高頻越多

每個像素要和周圍的26個像素比較，確定它是當前尺度下，相鄰頻率信息的一個峰值。

為什麼要精確定位，因為我們這個不論是x、y、sigma方向上都是離散的，要在連續的變化上求得極值點。

DoG函數D(X)=D(x,y,σ)在尺度空間的的Taylor展開式為：

令D(X)導數為0，得到極值點的偏移量：

若X^=(x,y,σ)T在任意一個維度大於0.5，說明極值點精確位置距離另一個點更近，應該改變當前關鍵點的位置，定位到新點後執行相同操作，若迭代5次仍不收斂，則認為該檢測點不為關鍵點。精確關鍵點處函數值為：

|D(X^)|過小易受雜訊點的干擾而變得不穩定，若其小於某個閾值(例如0.03或者0.04/S)，則將該極值點刪除旅哪。

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

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

D 的主曲率和H的特徵值成正比，令α為較大特徵值，β為較小特徵值，且α/β=r，則

(r+1)2/r在兩個特徵值相等時最小，隨著r的增大而增大，r值越大，說明兩個特徵值的比值越大，正好對應邊緣的情況。因此，設定一個閾值rt，若滿足

則認為該關鍵點不是邊緣，否則予以剔除。

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

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

為了使特徵描述子具有旋轉不變性，需要利用關鍵點鄰域像素的梯度方向分布特性為每個關鍵點指定方向參數。對於在DoG金字塔中檢測出的關鍵點，在其所在高斯金字塔圖像的3σ鄰域窗口內計算每個像素的梯度幅值和方向，公式如下：

L為關鍵點所在尺度空間的灰度值，m(x,y)為梯度拆帆碼幅值，θ(x,y)為梯度方向。對窗口內的像素的模值m(x,y)按σ=1.5σoct、鄰域窗口為3σ=3×1.5σoct的高斯分布加權。

在完成關鍵點的梯度計算後，使用直方圖統計鄰域內像素的梯度和方向，梯度直方圖將梯度方向(0,360∘)分為36柱(bins)，如下圖所示，直方圖的峰值所在的方向代表了該關鍵點的主方向。

梯度方向直方圖的峰值代表了該特徵點處鄰域梯度的主方向，為了增強魯棒性，保留峰值大於主方向峰值80%的方向作為該關鍵點的輔方向，因此，在相同位置和尺度，將會有多個關鍵點被創建但方向不同，可以提高特徵點匹配的穩定性。

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

是用128維向量對每個關鍵點進行描述。

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

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

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

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

這樣兩幅圖的特徵坐標系都是以關鍵點的方向為准了，旋轉不變性。

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

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

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

對兩幅圖像中檢測到的特徵點，可採用特徵向量的歐式距離作為特徵點相似性的度量，取圖像1中某個關鍵點，並在圖像2中找到與其距離最近的兩個關鍵點，若最近距離與次近距離的比值小於某個閾值，則認為距離最近的這一對關鍵點為匹配點。降低比例閾值，SIFT匹配點數量會減少，但相對而言會更加穩定。閾值ratio的取值范圍一般為0.4~0.6。

SIFT是一種檢測、描述、匹配圖像局部特徵點的演算法，通過在尺度空間中檢測極值點，提取位置、尺度、旋轉不變數，並抽象成特徵向量加以描述，最後用於圖像特徵點的匹配。SIFT特徵對灰度、對比度變換、旋轉、尺度縮放等保持不變性，對視角變化、仿射變化、雜訊也具有一定的魯棒性。但其實時性不高，對邊緣光滑的目標無法准確提取特徵點

旋轉不變性是計算關鍵點方向並旋轉得到的；尺度不變性是圖像下采樣獲得高斯金字塔得到的。

『叄』 SIFT演算法提取特徵點，怎樣得到正確的特徵點空間坐標，網上實現的程序里loc(i,1),loc(i,2)說是特徵點的坐標

為了更加准確，大衛勞氏推薦用了subpixel也就是子像素坐標，
但是這里的話你直接取整形就是了。
有warning能通了不就行了？

『肆』 sift特徵向量的維數

基於不變數技術的特徵檢測方法的基礎上，提出的一種基於尺度空間的、對圖像縮放、旋轉、仿射變換、光照變化保持穩定性的圖像局部特徵描述演算法-SIFT運算元。SIFT特徵點向量的生成由以下四步驟組成：1、在尺度空間中檢測極值點；2、去除低對比度的極值點和不穩定的邊緣極值點，得到特徵點；3、計算特徵點的方向參數；4、生成SIFT特徵點向量，向量維數一般為128維。運用SIFT演算法提取的SIFT特徵點向量具有如下優點：1、SIFT特徵是圖像的局部特徵，對旋轉、尺度縮放、亮度變化保持不變化性，對視角變化、仿射變換、噪音也保持一定程度的穩定性；2、獨特性好，信息量豐富，適用於在海量特徵資料庫中進行快速、准確的匹配；3、多量性，即使少數的幾個物體也可以產生大量SIFT特徵向量。現有的SIFT演算法具有一定的缺陷，對於圖像的檢測效率和檢測精度較差。
技術實現思路
有鑒於此，本專利技術實施例的目的在於提供一種基於改進SIFT的圖像特徵檢測方法及裝置，以解決上述技術問題。第一方面，本專利技術實施例提供了一種基於改進S...

【技術保護點】
1.一種基於改進SIFT的圖像特徵檢測方法，其特徵在於，包括：獲取待檢測圖像和對應的標准圖像；利用尺度不變特徵變換SIFT演算法對所述待檢測圖像和所述標准圖像進行圖像匹配，獲得多對匹配點；計算所述匹配點之間的鄰域直徑比和方向角度差；根據所述鄰域直徑比和所述方向角度差對所述匹配點進行剔除，獲得正確匹配點，以獲得所述待檢測圖像中的特徵。

『伍』 圖像特徵提取-SIFT

濾波一般指就是一個二維矩陣（卷積核），卷積就是用這個矩陣與原圖像進行卷積運算得到一個新的圖像。

尺度是一個視覺問題，不是數學問題，簡單的來講就是你在不同距離上觀察一個物體，產生的視覺感受是不同的。比如你站在不同距離觀察一片雪花，離的越遠你感受的形狀越接近於a->b->c->d的順序，就是越遠，你看到的越是一個大概的輪廓。

一幅圖像的SIFT特徵提取，分為4個步驟：

SIFT特徵點其實就是尺度空間中穩定的點/極值點，那麼，為了得到這些穩定點

對於一幅輸入圖像，為了進行sift特徵檢測、實現scale-invariant（任何尺度下都能夠有對應的特徵點），需要對該圖像的尺度空間進行分析，即建立高斯金字塔圖像、得到不同scale的圖像，這里的高斯金字塔與最原始的高斯金字塔稍微有點區別，因為它在構造尺度空間時，將這些不同尺度圖像分為了多個Octave、每個Octave又分為了多層。下圖給出了Sift中的高斯金字塔的結構圖；

構造完尺度空間（差分高斯金字塔）後，接下來的任務就是「在尺友友寬度中間中檢測出圖像中的穩定特徵點」：

對於DoG中每一個采樣點（每一個Octave中每一層），將其與它鄰域內所有像素點（8+18=26）進行比較，判斷其是否為局部極值點（極大或者極小），更加具體地：如下圖所示，中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應的9×2個點共26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點。 一個點如果在DOG尺度空間本層以及上下兩層的26個領域中是最大或最小值時，就認為該點是圖像在該尺度下的一個特徵點。但要注意：這種相鄰層之間的極值點的尋找是在同一Octave中的相鄰尺度之間進行尋找的，而不要跨組！

通過擬和「三維二次函數」可以精確確定關鍵點的位置和尺度（達到亞告猜像素精度），具體方法還未知，可以得到一系列的SIFT候選特徵點集合，但由於這些關好亮鍵點中有些具有較低的對比對，有些輸屬於不穩定的邊緣響應點(因為DoG運算元會產生較強的邊緣響應)，所以，為了增強匹配穩定性、提高抗雜訊能力，應該將這2類關鍵點去除，實現對候選SIFT特徵點集合的進一步凈化：

上面只是得到了每個關鍵點的方向，接下來，需要確定每個關鍵點的特徵向量，具體方式如下：

現有A、B兩幅圖像，分別利用上面的方法從各幅圖像中提取到了k1個sift特徵點和k2個特徵點及其對應的特徵描述子，即k1 * 128維和k2 * 128維的特徵，現在需要將兩圖中各個scale（所有scale）的描述子進行匹配。
接下來採用關鍵點特徵向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。

[1] SIFT特徵提取及匹配
[2] 圖像處理之特徵提取

『陸』 OpenCV-Python之——圖像SIFT特徵提取

在一定的范圍內，無論物體是大還是小，人眼都可以分辨出來。然而計算機要有相同的能力卻不是那麼的容易，在未知的場景中，計算機視覺並不能提供物體的尺度大小，其中的一種方法是把物體不同尺度下的圖像都提供給機器，讓機器能夠對物體在不同的尺度下有一個統一的認知。在建立統一認知的過程中，要考慮的就是在圖像在不同的尺度下都存在的特徵點。

在早期圖像的多尺度通常使用圖像金字塔表示形式。圖像金字塔是同一圖像在不同的解析度下得到的一組結果其生成過程一般包括兩個步驟：

多解析度的圖像金字塔雖然生成簡單，但其本質是降采樣，圖像的局部特徵則難以保持，也就是無法保持特徵的尺度不變性。

我們還可以通過圖像的模糊程度來模擬人在距離物體由遠到近時物體在視網膜上成像過程，距離物體越近其尺寸越大圖像也越模糊，這就是高斯尺度空間，使用不同的參數模糊圖像（解析度不變），是尺度空間的另一種表現形式。

構建尺度空間的目的是為了檢測出在不同的尺度下都存在的特徵點，而檢測特徵點較好的運算元是Δ^2G(高斯拉普拉斯，LoG)
使用LoG雖然能較好的檢測到圖像中的特徵點，但是其運算量過大，通常可使用DoG（差分高斯，Difference of Gaussina）來近似計算LoG。

從上式可以知道，將相鄰的兩個高斯空間的圖像相減就得到了DoG的響應圖像。為了得到DoG圖像，先要構建高斯尺度空間，而高斯的尺度空間可以在圖像金字塔降采樣的基礎上加上高斯濾波得到，也就是對圖像金字塔的每層圖像使用不同的參數σ進行高斯模糊，使每層金字塔有多張高斯模糊過的圖像。
如下圖，octave間是降采樣關系，且octave(i+1)的第一張（從下往上數）圖像是由octave(i)中德倒數第三張圖像降采樣得到。octave內的圖像大小一樣，只是高斯模糊使用的尺度參數不同。

對於一幅圖像，建立其在不同尺度scale下的圖像，也稱為octave，這是為了scale-invariant，也就是在任何尺度都能有對應的特徵點。下圖中右側的DoG就是我們構建的尺度空間。

為了尋找尺度空間的極值點，每一個采樣點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。如圖所示，中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應的9×2個點共26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點。 一個點如果在DOG尺度空間本層以及上下兩層的26個領域中是最大或最小值時，就認為該點是圖像在該尺度下的一個特徵點。下圖中將叉號點要比較的26個點都標為了綠色。

找到所有特徵點後， 要去除低對比度和不穩定的邊緣效應的點 ，留下具有代表性的關鍵點（比如，正方形旋轉後變為菱形，如果用邊緣做識別，4條邊就完全不一樣，就會錯誤；如果用角點識別，則穩定一些）。去除這些點的好處是增強匹配的抗噪能力和穩定性。最後，對離散的點做曲線擬合，得到精確的關鍵點的位置和尺度信息。

近來不斷有人改進，其中最著名的有 SURF（計算量小，運算速度快，提取的特徵點幾乎與SIFT相同）和 CSIFT（彩色尺度特徵不變變換，顧名思義，可以解決基於彩色圖像的SIFT問題）。

其中sift.detectAndCompute()函數返回kp，des。

上圖dog的shape為(481, 500, 3)，提取的特徵向量des的shape為(501, 128)，501個128維的特徵點。

該方法可以在特徵點處繪制一個小圓圈。

https://blog.csdn.net/happyer88/article/details/45817305
https://www.jianshu.com/p/d94e558ebe26
https://www.cnblogs.com/wangguchangqing/p/4853263.html

『柒』 SIFT特徵

參考了幾位大佬的博文：

參考1

參考2

SIFT特徵也叫做尺度不變特徵，SIFT特徵最後是把輸入的圖像表現成為以128維的特徵向量集合，SIFT特徵具有 旋轉，縮放，平移，光照 不變形，SIFT特徵檢測的步驟：

1. 尺度空間的極值檢測：高斯金字塔->DOG->極值檢測

2. 關鍵點的准確定位：二階泰勒展開+邊緣點過濾

3. 關鍵點主方向確定

4. 生成特徵向量

目的：我們的目的是要找到一些特徵，這些特徵具有尺度不變形，也就是說一張圖在不同的尺寸下面，我們仍然可以找到這些特徵

方法：我們可以通過對圖像連續的尺度變化，生成圖像的尺度空間，具體的做法就是對圖像進行多次的高斯模糊，為什麼用高斯核呢，因為高斯核：是唯一可以產生多尺度的核，那麼在這里，我們其實也可以直接通過計算圖像的二階導數，可以在不同尺度下找到比較穩定的極值點（圖像的高斯拉普拉斯運算元LOG），但是LOG的計算復雜，我們可以通過計算高斯差分（DOG）的方法來近似LOG，下面是證明過程

高斯函數：

LOG(高斯拉普拉斯運算元LoG(Laplacian of Gaussian):

再看DOG：

 --(1)

同時：

--(2)

令(1)=(2)，可得：

以上可以證明，我們可以用DOG來近似LOG

其中Octave成為組，組數一般取4，但實際上跟輸入圖像的大小(M*N)有關

每一個組中的層數s，一般為3～5，模型的初始參數 ，高斯金字塔的形成過程是這樣的：

1. 由原始的輸入圖像開始進行高斯模糊，生成第0組的隔層圖像  ,其逗指中

2. 第1組的的第0層圖像由第0組的倒數第三層圖像下采樣得到，第0層的倒數第三層圖像：

所以第1組的第0層圖像尺度為： ,於是我們可以得到規律，第o組的第r層圖像相對於輸入的圖像的尺度可以用用下面的計算公式得到：

3. 之後就可以根據高斯金字塔，計算DOG，也就是根據高斯金字塔連續的兩層相減得到，若高斯金字塔中的一組有s+2 層，那麼DOG對應的組就有s+2層

4. 最後計算尺度空間的極值點，對於每個點，對比其周圍的8個點以及上下兩層的共18個點，如果是最大值/最小值，則被選定為極值點

上一部找到的極值點是在離散空間找到的，離散空間的極值點並不一定是真真的連續空間的極值點，對此我們可以對尺度空間的DOG函數函數進行曲線擬合，從而找到極值點的更准確的定位，同時我們還需要對邊緣位置進行處理提高關鍵點的穩定性。

利用已知的離散空間點插值得到的連續空間極值點的方法叫做子像素插值，利用尺度空間DOG函數山臘配進行曲線擬合，然後對其函數利用泰勒展開式，求得一個偏移量，從而實現對行（x），列（y）以及尺度（sigma）進行修正，一般認為，偏移量小於0.5則調整完畢.

之後我們還要對邊緣點進行過濾，SIFT認為邊緣點容易受到噪音的影響，因此需要剔除，對於邊緣點的檢測是通過曲率來判讀的，邊緣點在橫跨邊緣的地方曲率較大，而在垂直邊緣的方向有較小的曲率，候選特徵點的曲率與2*2的海森矩陣的特徵值成正比,可以通過以下的公式進行篩選：

其中Tr表示海森矩陣對角線元素之和，Det表示海森矩陣的行列式，Tgamma表示一個閥值，默認取10，如果上式成立，那我們就可以剔除該候選關鍵點

上面找到的關鍵點保證了尺度不變形，為了實現旋轉不變形，我們需要給特徵點的方向進行賦值，利用特徵點周圍的像素點的梯度分布，統計生成一個梯度直方圖從而方便來確定特徵點的主方向，我們上面已經找到了特徵點的尺度，那也就可以得到特徵點所在的尺度圖像：

對於一個特徵點，我們要去計算以該特徵點為中心， 為半徑的區域內的像素點的梯度向量的幅度和方向：

之後統計一個梯度直方圖，我們以10度為一個bin，共分了36個bin，每個采樣點按照其梯度方向加權統計到直方圖中，權重為幅度m和貢獻因子的乘積，貢獻因子是采樣點到關鍵點的距離的反比。

當直方圖確定以後，任何大於峰值80%的的方向，可以看作是該特徵點的輔助方向，以此來提高匹配的穩定性。 最後我們可以用方向的峰值和左右兩個幅值擬合二次曲線，來更准確的定位峰值的位置。

通過之前的步驟，我們已經得到了特徵點的尺度，位置已局州經方向信息，這一步我們需要用一個特徵向量來表示它。我們可以通過三步來生成特徵向量：

我們以關鍵點為中心，取一個16*16的window，對於裡面的每一個像素點，我們都要計算其幅度和角度，然後我們以4*4作為一個種子點，把裡面的像素點的梯度進行統計並生成一個梯度直方圖，對於每一個梯度直方圖，我們以45度作為一個bin在360度的范圍內共有8個方向區間，於是，對每個關鍵點，我們取4*4共16個種子點來描述，每個描述子由8個方向的梯度信息，所以對於每個特徵點，我們生成了一個4*4*8=128維的向量

最後我們對生成的特徵向量進行歸一化處理，該處理可以去除光照的影響

通過SIFT提取的特徵有著旋轉平移不變形，尺度不變形，光照不變形，其中：

1. 旋轉不變形是因為在生成特徵向量之前，我們需要將坐標軸做一個映射使其旋轉到主方向，因此有了一定的旋轉不變形

2. 平移不變形是因為SIFT在計算特徵向量的時候，提取關鍵點周圍的區域的樣本點，所以如果該特徵點移動到任何處於該區域內的位置都可以被提取出來，這就有點像CNN中的pooling

3. 尺度不變形是首先因為我們通過DOG擬合LOG，而LOG又經前人的證明可以在不同尺度下檢測到圖像的特徵，其次通過DOG我們可以擬合出來不同的尺度的情況，在這種情況下求出來的關鍵點，自然是具有尺度不變形的

4.光照不變形是因為我們對最後的特徵向量進行了歸一化

1. SIFT高度依賴局部區域像素的梯度，有可能這個區域取得不合適，導致我們找的主方向不準確，從而導致計算出來的特徵向量誤差很大，從而不能成功匹配

2. 另外我們在進行SIFT特徵選取之前，可以看一下圖像的像素值分布，如果像素值分布過於集中，那麼SIFT的表現也不會很好，對此我們可以做一些圖像均衡化的處理

『捌』 圖像處理中sift特徵可以用來進行訓練嗎

按理來說，任何特徵都可以用於訓練的。但是sift提取的是一個點，一個點進行訓練，好像沒啥意租槐義。一般來說，友型基都是用sift提取特徵點，然後通過其他的匹配演算法找到另一幅對好謹應點(比如：立體匹配)，然後重建三維等。

『玖』 HartSift: 一種基於GPU的高准確性和實時SIFT

尺度不變特徵變換 (SIFT) 是最流行和最強大的特徵提取演算法之一，因為它對尺度、旋轉和光照保持不變。它已被廣泛應用於視頻跟蹤、圖像拼接、同時定位和映射（SLAM）、運動結構（SFM）等領域。然而，高計算復雜度限制了其在實時系統中的進一步應用。這些系統必須在准確性和性能之間進行權衡以實現實時特徵提取。他們採用其他更快但精度較低的演算法，如 SURF 和 PCA-SIFT。為了解決這個問題，本文提出了一種使用 CUDA 的 GPU 加速 SIFT，命名為 HartSift，充分利用單機CPU和GPU的計算資源，實現高精度、實時的特徵提取。實驗表明，在 NIVDIA GTX TITAN Black GPU 上，HartSift 可以根據圖像的大小在 3.14-10.57ms (94.61-318.47fps) 內處理圖像。此外，HartSift 分別比 OpenCV-SIFT（CPU 版本）和 SiftGPU（GPU 版本）快 59.34-75.96 倍和 4.01-6.49 倍。同時，HartSift 的性能和 CudaSIFT（迄今為止最快的 GPU 版本）的性能幾乎相同，而 HartSift 的准確度遠高於 CudaSIFT。

SIFT演算法可以提取大量顯著特徵，這些特徵在縮放、旋轉、光照和3D視點保持不變，還提供了跨越雜訊和仿射失真的穩健匹配。但SIFT的高計算復雜度限制了其在大規模數據和實時系統中的進一步應用。而復雜度較低的演算法，如SURF、PCA-SIFT的准確性又不太高。因此，在主流計算平台上實現高精度、實時的SIFT是一個重要而有意義的研究課題。

而SIFT演算法具有很好的並行性，可以正確移植到GPU上。因此，在配備GPU的異構計算系統上實現高性能的SIFT具有重要的實用價值。

SIFT 演算法包含三個階段，包括高斯差分（DoG）金字塔的構建、精確的關鍵點定位和 128 維描述符生成。由於每個階段都有自己的並行特性，因此必須使用不同的並行粒度和優化來實現高性能。尤其是後兩個階段，負載不平衡不利於GPU優化，會導致性能下降。

本文的主要貢獻和創新可以概括如下：

有許多工作嘗試在GPU上使用SIFT演算法。

然而，為了實現高性能，他們省略了 SIFT 演算法的一些重要步驟，例如將輸入圖像加倍、保持尺度變化的連續性和擬合二次函數以定位準確的關鍵點信息。作者的實驗表明，這些遺漏會導致 SIFT 丟失很多關鍵點和准確性。

Lowe將輸入圖像尺寸加倍作為高斯金字塔 的最底層，每個尺度 通過高斯卷積產生：

高斯金字塔確定之後，利用相同Octave的層級相減，得到差分金字塔：

其中 ，在本文中， .

檢測尺度空間極值

將DoG金字塔每個像素與相鄰像素比較，同層8個，上下層9個，若像素是局部最大值或局部最小值，將其視為關鍵點候選。

去除無效關鍵點

去除較低對比度和不穩定邊緣響應的候選關鍵點，通過將3D二次函數擬合到附近數據執行子像素插值，以獲取精確的位置、比例和主曲率比。

方向分配

將候選關鍵點周圍的梯度累積到36 bins的直方圖中，根據每層的尺度計算搜索半徑。每個緊鄰像素由一個高斯加權窗口加權，梯度方向累計到36 bins的方向直方圖中。峰值為主要梯度方向，同時超過峰值80%的局部峰值bin也被視為關鍵點方向。

對關鍵點周圍像素計算梯度直方圖，搜索半徑比上一步驟大得多，同樣用一個高斯加權函數用於為每個鄰居的梯度值分配權重。

根據梯度方向將最終的梯度值累積到一個 360-bin 的圓形方向直方圖。最後，直方圖將被歸一化、平滑並轉換為 128D 描述符。

構建金字塔應該保持順序，以保證尺度空間變化連續性。Acharya和Bjorkman為加快這一過程，犧牲准確性打破構建順序。考慮到不能使准確性降低，構建順序在HartSift中保留。

分離卷積核

對於 大小的卷積核處理 大小的圖像需要進行 次運算，如果將2D卷積核拆解為兩個1D的卷積核，計算量減少至 . 通過使用共享內存和向量化方法，更容易實現合並全局內存訪問並減少一維卷積的冗餘訪問。

Uber 內核

Uber內核將多個不同任務放到一個物理內核中，在一個內核中並行處理任務，而不需要在內核之間切換。差分金字塔第 層由高斯金字塔第 和第 層決定。將高斯差分金字塔和高斯卷積核封裝在單個核中，可以充分挖掘並行性。

線程不需要重復讀取高斯金字塔第 層的值，這是由於第 層的值計算完後，結果會放在寄存器內而不是全局內存中。藉助Uber內核的優勢，我們可以節省 的空間和 的內核運行時間

異構並行

HartSift 採用異構並行方法來加速這一階段。CPU 和 GPU 將並行協作，構建 DoG 金字塔。

由於GPU處理小圖像沒有優勢，作者將 以下的圖像放到CPU處理，大圖像放到GPU處理。用戶也可以自行設置分離點，確保CPU和GPU負載平衡。

存在兩個問題：

負載均衡

Warp是GPU最小並行執行單元，即以鎖步方式執行的 32 個線程的集合。若負載不均衡，則warp執行時間取決於最後一個線程完成的時間，warp負載不均衡會導致GPU效率降低。

由於候選關鍵點分布的隨機性，幾乎所有經線都包含不同數量的空閑線程。如果這些warp繼續處理以下部分，就會出現兩個級別的負載不平衡.

在去除無效的候選關鍵點部分時，線程將進行亞像素插值以獲得准確的候選關鍵點信息，從而去除具有低對比度或不穩定邊緣響應的關鍵點候選。換句話說，一些線程會比其他線程更早返回一次。負載不平衡會變得更加嚴重。

為了突破性能瓶頸，HartSift 引入了重新平衡工作負載和多粒度並行優化。

重新平衡工作負載

當檢測到負載不平衡時，HartSift 將通過啟動具有適當粒度的新內核並分派每個具有 32 個活動線程的新經線來重新平衡工作負載。

此外，啟動三個內核分別處理這三個部分，不僅可以重新平衡工作量，還可以根據不同部分的並行特性提供多粒度的並行。

多粒度並行

重新平衡工作負載優化保證每個內核中的線程和經線被完全載入，多粒度並行優化保證工作負載將平均分配到線程和經線。此外，不同內核的並行粒度取決於工作負載的特性。

HartSift通過將一個線程映射到一個或多個像素，採用與關鍵點候選檢測部分和無效關鍵點去除部分並行的線程粒度。然而，線程粒度並行會導致方向分配部分的負載不平衡，因為不同關鍵點的相鄰區域半徑不同。線程粒度並行會為單個線程分配過多的工作，這在某些情況下限制了硬體資源的利用率。所以在這部分應用混合粒度並行：扭曲粒度構建直方圖，線程粒度找出並將主導方向分配給相應的關鍵點。

基於扭曲的直方圖演算法

作者針對每個關鍵點提出了一種基於扭曲粒度和原子操作的高性能直方圖演算法，以充分利用局部性。

該階段關鍵點的鄰域半徑遠大於前一階段。需要為每個關鍵點累積數千個鄰居到一個 360-bin 直方圖。如果採用前一階段的基於原子扭曲的直方圖演算法，會對這一階段的性能產生不同的影響。

HartSift引入了一種atomic-free的直方圖演算法，進一步提升了這一階段的性能。

該演算法包含三個步驟：

為了消除線程間的負載不平衡，實現全局合並訪問，HartSift 使用一個warp 來處理一個keypoint 的所有鄰居。當線程計算出它們的方向 bin 時，它們需要根據bin變數的值將梯度值累加到局部直方圖。考慮到有如此多的鄰居並且一個經線的一些線程可能具有相同的 bin，演算法1引入了一種無原子的多鍵約簡方法來累積每個經線的部分和。這種方法可以利用warp級shuffle和vote指令完全消除原子操作和本地同步。它根據bin對經紗的線程進行分組並指定每組具有最低車道的線程作為隊長線程。隊長線程將保存他們自己的 bin 的部分總和，並將它們並行地累積到駐留在共享內存中的本地直方圖，而不會發生 bank 沖突和同步。在遍歷所有鄰居後，HartSift 將最終的局部直方圖復制到駐留在全局內存中的全局直方圖。

本文提出了一種GPU上的並行SIFT，命名為Hart-Sift，它可以在單機內同時使用CPU和GPU來實現高精度和實時的特徵提取。HartSift根據每個階段的不同特點，通過適當採用不同的優化策略來提升性能，例如負載均衡、基於warp的直方圖演算法和不同尺度樣本的atomic-free直方圖演算法等。在NVIDIA GTX TITAN Black GPU上，HartSift可以在3.14 ~ 10.57ms（94.61 ~ 318.47fps）內提取高精度特徵，輕松滿足高精度和實時性的苛刻要求。另外，與OpenCV-SIFT和SiftGPU相比，HartSift獲得了59.34 ~ 75.96倍和4.01 ~ 6.49倍加速分別。同時，HartSift 和 CudaSIFT 的性能幾乎相同，但 HartSift 遠比 CudaSIFT 准確。

『拾』 OpenCV+Python特徵提取演算法與圖像描述符之SIFT / SURF / ORB

演算法效果比較博文

用於表示和量化圖像的數字列表，簡單理解成將圖片轉化為一個數字列表世灶表示。特徵向量中用來描述圖片的各種屬性的向量稱為特徵矢量。

參考
是一種演算法和方法，輸入1個圖像，返回多個特徵向量（主要用來處理圖像的局部，往往會把多個特徵向量組成一個一維的向量）。主要用於圖像匹配（視覺檢測），匹配圖像中的物品。

SIFT論文
原理
opencv官網解釋
實質是在不同的尺度空間上查找關鍵點(特徵點)，並計算出關鍵點的方向。SIFT所查找到的關鍵點是一些十分突出，不會因光照，仿射變換和噪音等因素而變化的點，如角點、邊緣點、暗區的亮點及亮區的暗點等。

尺度不變特徵轉換(Scale-invariant feature transform或SIFT)是一種電腦視覺的演算法用來偵測與描述影像中的局部性特徵，它在空間尺度中尋找極值點，並提取出其位置、尺度、旋轉不變數。
其應用范圍包含物體辨識、機器人地圖感知與導航、影像縫合、3D模型建立、手勢辨識、影像追蹤和動作比對。

對現實中物體的描述一定要在一個十分重要的前提下進行，這個前提就是對自然界建模時的尺度。當用一個機器視覺系統分析未知場景時，計算機沒有辦法預先知道圖像中物體的尺度，因此我們需要同時考慮圖像在多尺度下的描述，獲知感興趣物體的最佳尺度。圖像的尺度空間表達指的是圖像的所有尺度下的描述。

KeyPoint數據結構解析

SURF論文
原理
opencv官網解釋
SURF是SIFT的加速版，它善於處理具有模糊和旋轉的圖像，但是不善於處理視角變化和光照變化。在SIFT中使用DoG對LoG進行近似，而在SURF中使用盒子濾波器對LoG進行近似，這樣就可以使用積分圖像了（計算圖像中某個窗口內所有像素和時，計算量的大小與窗口大小無關）。總之，SURF最大的特點在於採用了Haar特徵以及積分圖改團像的概念，大大加快了程序的運行效率。

因為專利原因，OpenCV3.3開核返橘始不再免費開放SIFT\SURF，需要免費的請使用ORB演算法

ORB演算法綜合了FAST角點檢測演算法和BRIEFF描述符。

演算法原理
opencv官方文檔
FAST只是一種特徵點檢測演算法，並不涉及特徵點的特徵描述。

論文
opencv官方文檔
中文版
Brief是Binary Robust Independent Elementary Features的縮寫。這個特徵描述子是由EPFL的Calonder在ECCV2010上提出的。主要思路就是在特徵點附近隨機選取若干點對，將這些點對的灰度值的大小，組合成一個二進制串，並將這個二進制串作為該特徵點的特徵描述子。文章同樣提到，在此之前，需要選取合適的gaussian kernel對圖像做平滑處理。

1：不具備旋轉不變性。
2：對雜訊敏感
3：不具備尺度不變性。

ORB論文
OpenCV官方文檔

ORB採用了FAST作為特徵點檢測運算元，特徵點的主方向是通過矩（moment）計算而來解決了BRIEF不具備旋轉不變性的問題。
ORB還做了這樣的改進，不再使用pixel-pair，而是使用9×9的patch-pair，也就是說，對比patch的像素值之和，解決了BRIEF對雜訊敏感的問題。
關於計算速度：
ORB是sift的100倍，是surf的10倍。

對圖片數據、特徵分布的一種統計
對數據空間(bin)進行量化

Kmeans

邊緣：尺度問題->不同的標准差 捕捉到不同尺度的邊緣
斑點 Blob：二階高斯導數濾波LoG

關鍵點(keypoint)：不同視角圖片之間的映射，圖片配准、拼接、運動跟蹤、物體識別、機器人導航、3D重建

SIFT\SURF