特徵提取的演算法sift

㈠ java opencv 怎樣確定sift 匹配結果

這幾天繼續在看Lowe大神的SIFT神作，看的眼花手腳抽筋。也是醉了！！！！實在看不下去，來點干貨。我們知道opencv下自帶SIFT特徵檢測以及MATCH匹配的庫，這些庫完全可以讓我們進行傻瓜似的操作。但實際用起來的時候還不是那麼簡單。下文將對一個典型的基於OPENCV的SIFT特徵點提取以及匹配的常式進行分析，並由此分析詳細的對OPENCV中SIFT演算法的使用進行一個介紹。

OPENCV下SIFT特徵點提取與匹配的大致流程如下：

讀取圖片-》特徵點檢測（位置，角度，層）-》特徵點描述的提取（16*8維的特徵向量）-》匹配-》顯示

其中，特徵點提取主要有兩個步驟，見上行黃子部分。下面做具體分析。

1、使用opencv內置的庫讀取兩幅圖片

2、生成一個SiftFeatureDetector的對象，這個對象顧名思義就是SIFT特徵的探測器，用它來探測衣服圖片中SIFT點的特徵，存到一個KeyPoint類型的vector中。這里有必要說keypoint的數據結構，涉及內容較多，具體分析查看opencv中keypoint數據結構分析，裡面講的自認為講的還算詳細（表打我……）。簡而言之最重要的一點在於：

keypoint只是保存了opencv的sift庫檢測到的特徵點的一些基本信息，但sift所提取出來的特徵向量其實不是在這個裡面，特徵向量通過SiftDescriptorExtractor 提取，結果放在一個Mat的數據結構中。這個數據結構才真正保存了該特徵點所對應的特徵向量。具體見後文對SiftDescriptorExtractor 所生成的對象的詳解。

就因為這點沒有理解明白耽誤了一上午的時間。哭死！

3、對圖像所有KEYPOINT提取其特徵向量：

得到keypoint只是達到了關鍵點的位置，方向等信息，並無該特徵點的特徵向量，要想提取得到特徵向量就還要進行SiftDescriptorExtractor 的工作，建立了SiftDescriptorExtractor 對象後，通過該對象，對之前SIFT產生的特徵點進行遍歷，找到該特徵點所對應的128維特徵向量。具體方法參見opencv中SiftDescriptorExtractor所做的SIFT特徵向量提取工作簡單分析。通過這一步後，所有keypoint關鍵點的特徵向量被保存到了一個MAT的數據結構中，作為特徵。

4、對兩幅圖的特徵向量進行匹配，得到匹配值。

兩幅圖片的特徵向量被提取出來後，我們就可以使用BruteForceMatcher對象對兩幅圖片的descriptor進行匹配，得到匹配的結果到matches中，這其中具體的匹配方法暫沒細看，過段時間補上。

至此，SIFT從特徵點的探測到最後的匹配都已經完成，雖然匹配部分不甚了解，只掃對於如何使用OPENCV進行sift特徵的提取有了一定的理解。接下來可以開始進行下一步的工作了。

附:使用OPENCV下SIFT庫做圖像匹配的常式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// opencv_empty_proj.cpp : 定義控制台應用程序的入口點。
//

#include "stdafx.h"
#include opencv.hpp>
#include features2d/features2d.hpp>
#includenonfree/nonfree.hpp>
#includelegacy/legacy.hpp>
#include
using namespace std;
using namespace cv;

int _tmain(int argc, _TCHAR* argv[])
{
const char* imagename = "img.jpg";

//從文件中讀入圖像
Mat img = imread(imagename);
Mat img2=imread("img2.jpg");

//如果讀入圖像失敗
if(img.empty())
{
fprintf(stderr, "Can not load image %s\n", imagename);
return -1;
}
if(img2.empty())
{
fprintf(stderr, "Can not load image %s\n", imagename);
return -1;
}
//顯示圖像
imshow("image before", img);
imshow("image2 before",img2);

//sift特徵檢測
SiftFeatureDetector siftdtc;
vectorkp1,kp2;

siftdtc.detect(img,kp1);
Mat outimg1;
drawKeypoints(img,kp1,outimg1);
imshow("image1 keypoints",outimg1);
KeyPoint kp;

vector::iterator itvc;
for(itvc=kp1.begin();itvc!=kp1.end();itvc++)
{
cout<<"angle:"<angle<<"\t"<class_id<<"\t"<octave<<"\t"<pt<<"\t"<response<<endl;
}

siftdtc.detect(img2,kp2);
Mat outimg2;
drawKeypoints(img2,kp2,outimg2);
imshow("image2 keypoints",outimg2);

SiftDescriptorExtractor extractor;
Mat descriptor1,descriptor2;
BruteForceMatcher<L2> matcher;
vector matches;
Mat img_matches;
extractor.compute(img,kp1,descriptor1);
extractor.compute(img2,kp2,descriptor2);

imshow("desc",descriptor1);
cout<<endl<<descriptor1<<endl;
matcher.match(descriptor1,descriptor2,matches);

drawMatches(img,kp1,img2,kp2,matches,img_matches);
imshow("matches",img_matches);

//此函數等待按鍵，按鍵盤任意鍵就返回
waitKey();
return 0;
}

㈡ 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演算法是什麼

Sift演算法是David Lowe於1999年提出的局部特徵描述子，並於2004年進行了更深入的發展和完善。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

㈥ sift演算法得到的特徵點如何用坐標描述

在我寫的關於sift演算法的前倆篇文章里頭，已經對sift演算法有了初步的介紹：九、圖像特徵提取與匹配之SIFT演算法，而後在：九（續）、sift演算法的編譯與實現里，我也簡單記錄下了如何利用opencv，gsl等庫編譯運行sift程序。
但據一朋友表示，是否能用c語言實現sift演算法，同時，盡量不用到opencv，gsl等第三方庫之類的東西。而且，Rob Hess維護的sift 庫，也不好懂，有的人根本搞不懂是怎麼一回事。
那麼本文，就教你如何利用c語言一步一步實現sift演算法，同時，你也就能真正明白sift演算法到底是怎麼一回事了。