sift演算法harris演算法

① sift演算法是什麼

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

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

sift演算法的應用

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

② 圖像角點特徵之Harris、SIFT、SURF、ORB

角點檢測(Corner Detection)是計算機視覺系統中用來獲得圖像特徵的一種方法，廣泛應用於運動檢測、圖像匹配、視頻跟蹤、三維建模和目標識別等領域中。也稱為特徵點檢測。 角點通常被定義為兩條邊的交點，更嚴格的說，角點的局部鄰域應該具有兩個不同區域的不同方向的邊界。而實際應用中，大多數所謂的角點檢測方法檢測的是擁有特定特徵的圖像點，而不僅僅是「角點」。這些特徵點在圖像中有具體的坐標，並具有某些數學特徵，如局部最大或最小灰度、某些梯度特徵等。

這些角點通常在圖像中是穩定存在的。角點的微小偏移就能反映出圖像幀的相對運動。

Harris角點檢測演算法就是對角點響應函數R進行閾值處理：R > threshold，即提取R的局部極大值。
特點：具有角度不變性

SIFT克服了Harris的不足，縮放也沒影響，具有尺度不變性。
特點：角度不變性，尺度不變性

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

更多

ORB（Oriented FASTand Rotated BRIEF）演算法是目前最快速穩定的特徵點檢測和提取演算法，許多圖像拼接和目標追蹤技術利用ORB特徵進行實現。
ORB採用FAST（features from accelerated segment test）演算法來檢測特徵點，採用BRIEF演算法來計算一個特徵點的描述子。
特點：角度不變性，尺度不變性，計算速度快（ORB是sift的100倍，是surf的10倍）

1、OpenCV版本

③ 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 准確。

④ 在圖像處理方面什麼是SIFT匹配

一、特徵點（角點）匹配
圖像匹配能夠應用的場合非常多，如目標跟蹤，檢測，識別，圖像拼接等，而角點匹配最核心的技術就要屬角點匹配了，所謂角點匹配是指尋找兩幅圖像之間的特徵像素點的對應關系，從而確定兩幅圖像的位置關系。
角點匹配可以分為以下四個步驟：
1、提取檢測子：在兩張待匹配的圖像中尋找那些最容易識別的像素點（角點），比如紋理豐富的物體邊緣點等。
2、提取描述子：對於檢測出的角點，用一些數學上的特徵對其進行描述，如梯度直方圖，局部隨機二值特徵等。檢測子和描述子的常用提取方法有：sift，harris，surf，fast，agast，brisk，freak，brisk，brief/orb等。
3、匹配：通過各個角點的描述子來判斷它們在兩張圖像中的對應關系，常用方法如 flann等。
4、消噪：去除錯誤匹配的外點，保留正確的匹配點。常用方法有KDTREE，BBF，Ransac，GTM等。
二、SIFT匹配方法的提出
為了排除因為圖像遮擋和背景混亂而產生的無匹配關系的關鍵點，SIFT的作者Lowe提出了比較最近鄰距離與次近鄰距離的SIFT匹配方式：取一幅圖像中的一個SIFT關鍵點，並找出其與另一幅圖像中歐式距離最近的前兩個關鍵點，在這兩個關鍵點中，如果最近的距離除以次近的距離得到的比率ratio少於某個閾值T，則接受這一對匹配點。因為對於錯誤匹配，由於特徵空間的高維性，相似的距離可能有大量其他的錯誤匹配，從而它的ratio值比較高。顯然降低這個比例閾值T，SIFT匹配點數目會減少，但更加穩定，反之亦然。
Lowe推薦ratio的閾值為0.8，但作者對大量任意存在尺度、旋轉和亮度變化的兩幅圖片進行匹配，結果表明ratio取值在0. 4~0. 6 之間最佳，小於0. 4的很少有匹配點，大於0. 6的則存在大量錯誤匹配點，所以建議ratio的取值原則如下:
ratio=0. 4：對於准確度要求高的匹配；
ratio=0. 6：對於匹配點數目要求比較多的匹配；
ratio=0. 5：一般情況下。
三、常見的SIFT匹配代碼
1、vlfeat中sift toolbox中的vl_ubcmatch.c使用的是普通的歐氏距離進行匹配（該SIFT代碼貢獻自Andrea
Vedaldi）。
2、Lowe的C++代碼中使用的是歐氏距離，但是在matlab代碼中為了加速計算，使用的是向量夾角來近似歐氏距離：先將128維SIFT特徵向量歸一化為單位向量（每個數除以平方和的平方根），然後點乘來得到向量夾角的餘弦值，最後利用反餘弦（acos函數）求取向量夾角。實驗證明Lowe的辦法正確率和耗時都很不錯。
同樣，也可以採用knnsearch函數求最近點和次近點：knnsearch採用euclidean距離時得到的結果與lowe採用的近似方法結果幾乎一致，正好印證了模擬歐氏距離的效果。
3、Rob Hess的OpenSIFT採用了KDTREE來對匹配進行優化。
4、CSDN大神v_JULY_v實現了KDTREE+BBF對SIFT匹配的優化和消除錯誤匹配：從K近鄰演算法、距離度量談到KD樹、SIFT+BBF演算法
- 結構之法 演算法之道 - 博客頻道 - CSDN.NET。
5、OpenCV中features2d實現的SIFT匹配有多種matcher：VectorDescriptorMatcher，BFMatcher（Brute-force descriptor matcher），FernDescriptorMatcher，OneWayDescriptorMatcher，FlannBasedMatcher 等等。目前只知道採用knnsearch，提供了多種距離度量方式，具體區別不懂。

⑤ 機器視覺演算法有哪些

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

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