surf演算法圖像拼接

1. surf演算法C語言編寫，要做嵌入式開發，不要C++和基於OPENCV的

surf借鑒了sift中簡化近似的思想，將DOH中的高斯二階微分模板進行了近似簡化，使得模板對圖像的濾波只需要進行幾個簡單的加減法運算，並且，這種運算與濾波模板的尺寸有關。實驗證明surf演算法較sift演算法在運算速度上要快3倍左右。
1積分圖像
surf演算法中要用到積分圖像的概念。藉助積分圖像，圖像與高斯二階微分模板的濾波轉化為對積分圖像的加減運算。積分圖像（IntegralImage）的概念是由viola和Jones提出來的，而將類似積分圖像用於盒子濾波是由Simard等人提出。
積分圖像中任意一點（i,j）的值為ii(i,j)為原圖像左上角到任意點（i,j）相應的對角線區域灰度值的總和即：
公式中，I(x`,y`)表示原圖像中點（i`,j`）的灰度值，ii（x,y）可以由下面兩公式迭代計算得到：
公式中，S（x,y）表示一列的積分，且S（i,-1）=0,ii(-1,j)=0.求積分圖像，只需對原圖像的所有像素素進行一遍掃描。下面的代碼為c++語言的實現
pOutImage[0][0]=pInImage[0][0];
for(intx=1,x<nWidth;i++)
{
pOutImage[x][0]=pInImage[x-1][0]+pInImage[x][0];
}
for(inty=1;y<nHeight;y++)
{
intnSum=0;
for(intx=0;x<nWidth;x++)
{
nSum=pInImage[x][y];
pOutImage[x][y]=pInImage[x][y-1]+nSum;
}
}
如圖表示，在求取窗口w內的像元灰度和時，不管窗口W的大小如何，均可利用積分圖像的4個對應點（i1,j1）（i2,j2）（i3,j3）（i4,j4）的值計算的到。也就是說，求取窗口W內的像元灰度和與窗口的尺寸是無關的。窗口W內的像元的灰度和為
Sum（W）=ii(i4,j4)-ii(i2,j2)-ii(i3,j3)+ii(i1,j1)
下面看以截圖，相信都可以看懂
關於矩形區域內像素點的求和應該是一種簡單重復性運算，採用這種思路總體上提高了效率。為什麼這么說呢？假設一幅圖片共有n個像素點，則計算n個位置的積分圖總共的加法運算有n-1次（注意：可不是次哦，要充分利用遞推思想），將這些結果保存在一個跟原圖對應的矩陣M中。當需要計算圖像中某個矩形區域內的所有像素之和是直接像查表一樣，調出A,B,C,D四點的積分圖值，簡單的加減法（注意只需要三次哦）即可得到結果。反之，如果採用naive的方式直接在原圖像中的某個矩形區域內求和，你想想，總共可能的矩形組合有多少？！！且對於一幅圖像n那是相當大啊，所以2^n
那可是天文數字，而且這裡面絕大部分的矩形有重疊，重疊意味著什麼？在算求和的時候有重復性的工作，其實我們是可以有效的利用已經計算過的信息的。這就是積分圖法的內在思想：它實際上是先計算n個互不重疊（專業點說是不相交）的矩形區域內的像素點求和，充分利用這些值（已有值）計算未知值，有點類似遞推的味道...這就完全避免了重復求和運算。
這樣就可以進行2種運算：
（1）任意矩形區域內像素積分。由圖像的積分圖可方便快速地計算圖像中任意矩形內所有像素灰度積分。如下圖2.3所示，點1的積分圖像ii1的值為(其中Sum為求和):
ii1=Sum（A）

同理，點2、點3、點4的積分圖像分別為：
ii2=Sum(A)+Sum(B);ii3=Sum(A)+Sum(C);ii4=Sum(A)+Sum(B)+Sum(C)+Sum(D);
矩形區域D內的所有像素灰度積分可由矩形端點的積分圖像值得到:
Sum(D)=ii1+ii4-(ii2+ii3)(1)
(2)特徵值計算
矩形特徵的特徵值是兩個不同的矩形區域像素和之差，由(1)式可以計算任意矩形特徵的特徵值，下面以圖2.1中特徵原型A為例說明特徵值的計算。

如圖2.4所示，該特徵原型的特徵值定義為:

Sum（A）-Sum（B）

根據（1）式則有：Sum(A)=ii4+ii1-(ii2+ii3);Sum(B)=ii6+ii3-(ii4+ii5);

所以此類特徵原型的特徵值為:

(ii4-ii3)-(ii2-ii1)+(ii4-ii3)-(ii6-ii5)

另示：運用積分圖可以快速計算給定的矩形之所有象素值之和Sum(r)。假設r=(x,y,w,h),那麼此矩形內部所有元素之和等價於下面積分圖中下面這個式子:

Sum(r)=ii(x+w,y+h)+ii(x-1,y-1)-ii(x+w,y-1)-ii(x-1,y+h)

由此可見，矩形特徵特徵值計算只與此特徵端點的積分圖有關，而與圖像坐標值無關。對於同一類型的矩形特徵，不管特徵的尺度和位置如何，特徵值的計算所耗費的時間都是常量，而且都只是簡單的加減運算。其它類型的特徵值計算方法類似。

2. 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

3. Surf的SURF演算法

加速穩健特徵(Speeded Up Robust Features, SURF)是一個穩健的圖像識別和描述演算法，首先於2006年發表在歐洲計算機視覺國際會議(Europeon Conference on Computer Vision，ECCV)。該演算法可被用於計算機視覺任務，如物件識別和3D重構。他部分的靈感來自於SIFT演算法。SURF標準的版本比SIFT要快數倍，並且其作者聲稱在不同圖像變換方面比SIFT更加穩健。SURF 基於近似的2D 離散小波變換響應和並且有效地利用了積分圖。
該演算法由Herbert Bay於2006年首次發表於ECCV，2008年正式發表在Computer vision and image understanding期刊上，論文被引9000餘次。 Hessian矩陣是SURF演算法的核心，為了方便運算，假設函數f(x,y)，Hessian矩陣H是由函數的二階偏導數組成：

4. 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 准確。

5. 機器視覺演算法有哪些

機器視覺演算法基本步驟；
1、圖像數據解碼
2、圖像特徵提取
3、識別圖像中目標。
機器視覺是人工智慧正在快速發展的一個分支。
簡單說來，機器視覺就是用機器代替人眼來做測量和判斷。
機器視覺系統是通過機器視覺產品(即圖像攝取裝置，分CMOS和CCD兩種)將被攝取目標轉換成圖像信號，傳送給專用的圖像處理系統，得到被攝目標的形態信息，根據像素分布和亮度、顏色等信息，轉變成數字化信號;圖像系統對這些信號進行各種運算來抽取目標的特徵，進而根據判別的結果來控制現場的設備動作。

現在做視覺檢測的公司比較多，國內國外都有，許多視覺算是很好的。
能提供完整的機器視覺軟體解決方案，也可以為客戶提供演算法級的定製，覆蓋所有的工業應用領域，適用范圍比較廣。機器視覺的應用會越來越多，因為計算的水平越來越高，可以處理更復雜的視覺演算法；其實好多的東西，包括現在流行的GPS，最早都是外國的公司在做，程序都是中國人在做外包；
光機電的應用我個人覺得已經很成熟了，不會再有新東西。

6. opencv 用python 使用surf演算法計算出了最後的結果，繪出了圖像，之後怎麼找出目標位置

這個用不著SURF。只需要聚色彩就可以了。芬達主要由橙色與黑色組成。只需要按橙色與黑色設計兩個向量指標，立刻就可以看出來，只有芬達同時符合這兩個峰值。

你顯然沒有做過數據處理的經驗。這個東西。甚至用不著opencv的核心功能。只需要用它的圖像採集然後處理一下圖像就可以了。

當然芬達是一個對象。你還需要將對象與背景分享出來。這個時候，可以使用一些類似人臉識別的演算法。

但是換作是我自己。顯然不會這樣做。我只需要計算顏色距離相似度。把相似的顏色自動分成區域。然後計算區域的重心與離散度。就可以輕松分離出哪些區域是背景，哪些是對象。