數據結構sift演算法

⑴ SIFT演算法中的圖像尺度

這個尺度應該可以理解為一個比例因子delta，用來控制X、Y方向上圖像的縮放比例，它與X、Y參數的一個連續函數表達L(x,y,delta)就構成了一個空間，稱為尺度空間，該空間是由原始圖像的I(x,y)表達與高斯函數G(x,y,delta)進行卷積後形成的對已經申請了專利的技術進行修改後進行商業應用算不算侵權這個界定很模糊的，就像當年DVD晶元的專利侵權賠償案一樣，我覺得如果你是小打小鬧小范圍內使用的話，不對專利所屬單位或個人造成利益威脅，人家是不會費勁來查你的，但是如果你的商業應用影響大到了一定程度，人家有可能就來找碴了，私以為，國內大部分軟體都達不到這個程度。另外，如果你修改的部分比較多，超過了30%的話（這個好像要得到專利局的認可才算數），你可以換個名稱申請一個專利試試

⑵ SIFT特徵的原理

SIFT特徵不只具有尺度不變性，即使改變圖像的旋轉角度，亮度或拍攝視角，仍然能夠得到好的檢測效果。

這是一個初始化操作，尺度空間理論目的是模擬圖像數據的多尺度特徵。高斯卷積核是實現尺度變換的唯一線性核，於是一副二維圖像的尺度空間定義為：

下圖所示不同σ下圖像尺度空間：

關於尺度空間的理解說明：2kσ中的2是必須的，尺度空間是連續的。在 Lowe的論文中 ，將第0層的初始尺度定為1.6（最模糊），圖片的初始尺度定為0.5（最清晰）. 在檢測極值點前對原始圖像的高斯平滑以致圖像丟失高頻信息，所以 Lowe 建議在建立尺度空間前首先對原始圖像長寬擴展一倍，以保留原始圖像信息，增加特徵點數量。尺度越大圖像越模糊。

圖像金字塔的建立：對於一幅圖像I,建立其在不同尺度(scale)的圖像，也成為子八度（octave），這是為了scale-invariant，也就是在任何尺度都能夠有對應的特徵點，第一個子八度的scale為原圖大小，後面每個octave為上一個octave降采樣的結果，即原圖的1/4（長寬分別減半），構成下一個子八度（高一層金字塔）。

注意：使用Difference of Gaussian圖像的極大極小值近似尋找特徵點計算簡單，是尺度歸一化的LoG運算元的近似

為了尋找尺度空間的極值點，每一個采樣點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。
一個點如果在DOG尺度空間本層以及上下兩層的26個領域中是最大或最小值時，就認為該點是圖像在該尺度下的一個特徵點,如圖所示。

整個高斯金字塔如下圖所示，其中每個Octave代表一個金字塔，同一個金字塔內圖像尺寸一樣，同一個金字塔內每張圖通過不同的高斯卷積核產生。

在極值比較的過程中，每一組圖像的首末兩層是無法進行極值比較的，為了滿足尺度變化的連續性，我們在每一組圖像的頂層繼續用高斯模糊生成了 3 幅圖像，高斯金字塔有每組S+3層圖像。DOG金字塔每組有S+2層圖像。

使用Laplacian of Gaussian能夠很好地找到找到圖像中的興趣點，但是需要大量的計算量，所以使用Difference of Gaussian圖像的極大極小值近似尋找特徵點.DOG運算元計算簡單，是尺度歸一化的LoG運算元的近似,有關DOG尋找特徵點的介紹及方法詳見 http://blog.csdn.net/abcjennifer/article/details/7639488 ，極值點檢測用的Non-Maximal Suppression。

這一步本質上要去掉DoG局部曲率非常不對稱的像素。（不理解）

通過擬和三維二次函數以精確確定關鍵點的 位置 和 尺度 （達到亞像素精度），同時去除低對比度的關鍵點和不穩定的邊緣響應點(因為DoG運算元會產生較強的邊緣響應)，以增強匹配穩定性、提高抗雜訊能力，在這里使用近似Harris Corner檢測器。
計算過程摘錄如下：（還沒有自行推導）
①空間尺度函數泰勒展開式如下：

的值在兩個特徵值相等的時候最小，隨著r的增大而增大，因此，為了檢測主曲率是否在某域值r下，只需檢測

if (α+β)/ αβ> (r+1)2
/r, throw it out. 在Lowe的文章中，取r＝10。

上一步中確定了每幅圖中的特徵點，為每個特徵點計算一個方向，依照這個方向做進一步的計算， 利用關鍵點鄰域像素的梯度方向分布特性為每個關鍵點指定方向參數，使運算元具備旋轉不變性。

梯度直方圖的范圍是0～360度，其中每10度一個柱，總共36個柱。隨著距 中心點越遠的領域其對直方圖的貢獻也響應減小。Lowe論文中還提到要使用高斯函數對直方圖進行平滑，減少突變的影響。這主要是因為SIFT演算法只考慮了尺度和旋轉不變形，沒有考慮仿射不變性。通過高斯平滑，可以使關鍵點附近的梯度幅值有較大權重，從而部分彌補沒考慮仿射不變形產生的特徵點不穩定。
通常離散的梯度直方圖要進行插值擬合處理，以求取更精確的方向角度值。

在實際計算時，我們在以關鍵點為中心的鄰域窗口內采樣，並用直方圖統計鄰域像素的梯度方向。梯度直方圖的范圍是0～360度，其中每45度一個柱，總共8個柱, 或者每10度一個柱，總共36個柱。Lowe論文中還提到要使用高斯函數對直方圖進行平滑，減少突變的影響。直方圖的峰值則代表了該關鍵點處鄰域梯度的主方向，即作為該關鍵點的方向。

直方圖中的峰值就是主方向，其他的達到最大值80%的方向可作為輔助方向

Identify peak and assign orientation and sum of magnitude to key point.
** The user may choose a threshold to exclude key points based on their** assigned sum of magnitudes.

直方圖峰值代表該關鍵點處鄰域內圖像梯度的主方向，也就是該 關鍵點的主方向 。在梯度方向直方圖中，當存在另一個相當於主峰值 80%能量的峰值時，則將這個方向認為是該 關鍵點的輔方向 。所以一個關鍵點可能檢測得到多個方向，這可以增強匹配的魯棒性。Lowe的論文指出大概有15%關鍵點具有多方向，但這些點對匹配的穩定性至為關鍵。
獲得圖像關鍵點主方向後，每個關鍵點有三個信息(x,y,σ,θ)：位置、尺度、方向。由此我們可以確定一個SIFT特徵區域。通常使用一個帶箭頭的圓或直接使用箭頭表示SIFT區域的三個值：中心表示特徵點位置，半徑表示關鍵點尺度（r=2.5σ）,箭頭表示主方向。具有多個方向的關鍵點可以復製成多份，然後將方向值分別賦給復制後的關鍵點。如下圖：

通過對關鍵點周圍圖像區域分塊，計算塊內梯度直方圖，生成具有獨特性的向量，這個向量是該區域圖像信息的一種抽象，具有唯一性。

首先將坐標軸旋轉為關鍵點的方向，以確保旋轉不變性。以關鍵點為中心取8×8的窗口。

Figure.16*16的圖中其中1/4的特徵點梯度方向及scale，右圖為其加權到8個主方向後的效果。
圖左部分的中央為當前關鍵點的位置，每個小格代表關鍵點鄰域所在尺度空間的一個像素，利用公式求得每個像素的梯度幅值與梯度方向，箭頭方向代表該像素的梯度方向，箭頭長度代表梯度模值，然後用高斯窗口對其進行加權運算。

圖中藍色的圈代表高斯加權的范圍（越靠近關鍵點的像素梯度方向信息貢獻越大）。然後在每4×4的小塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，即可形成一個種子點，如圖右部分示。此圖中一個關鍵點由2×2共4個種子點組成，每個種子點有8個方向向量信息。這種鄰域方向性信息聯合的思想增強了演算法抗雜訊的能力，同時對於含有定位誤差的特徵匹配也提供了較好的容錯性。

計算keypoint周圍的16*16的window中每一個像素的梯度，而且使用高斯下降函數降低遠離中心的權重。

在每個4 4的1/16象限中，通過加權梯度值加到直方圖8個方向區間中的一個，計算出一個梯度方向直方圖。
這樣就可以對每個feature形成一個4 4 8=128維的描述子，每一維都可以表示4 4個格子中一個的scale/orientation. 將這個向量歸一化之後，就進一步去除了光照的影響。

生成了A、B兩幅圖的描述子，（分別是k1 128維和k2 128維），就將兩圖中各個scale（所有scale）的描述子進行匹配，匹配上128維即可表示兩個特徵點match上了。

實際計算過程中，為了增強匹配的穩健性，Lowe建議對每個關鍵點使用4×4共16個種子點來描述，這樣對於一個關鍵點就可以產生128個數據，即最終形成128維的SIFT特徵向量。此時SIFT特徵向量已經去除了尺度變化、旋轉等幾何變形因素的影響，再繼續將特徵向量的長度歸一化，則可以進一步去除光照變化的影響。 當兩幅圖像的SIFT特徵向量生成後，下一步我們採用關鍵點特徵向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。取圖像1中的某個關鍵點，並找出其與圖像2中歐式距離最近的前兩個關鍵點，在這兩個關鍵點中，如果最近的距離除以次近的距離少於某個比例閾值，則接受這一對匹配點。降低這個比例閾值，SIFT匹配點數目會減少，但更加穩定。為了排除因為圖像遮擋和背景混亂而產生的無匹配關系的關鍵點,Lowe提出了比較最近鄰距離與次近鄰距離的方法,距離比率ratio小於某個閾值的認為是正確匹配。因為對於錯誤匹配,由於特徵空間的高維性,相似的距離可能有大量其他的錯誤匹配,從而它的ratio值比較高。Lowe推薦ratio的閾值為0.8。但作者對大量任意存在尺度、旋轉和亮度變化的兩幅圖片進行匹配，結果表明ratio取值在0. 4~0. 6之間最佳，小於0. 4的很少有匹配點，大於0. 6的則存在大量錯誤匹配點。(如果這個地方你要改進，最好給出一個匹配率和ration之間的關系圖，這樣才有說服力)作者建議ratio的取值原則如下:
ratio=0. 4對於准確度要求高的匹配；ratio=0. 6對於匹配點數目要求比較多的匹配； ratio=0. 5一般情況下。也可按如下原則:當最近鄰距離<200時ratio=0. 6，反之ratio=0. 4。ratio的取值策略能排分錯誤匹配點。

當兩幅圖像的SIFT特徵向量生成後，下一步我們採用關鍵點特徵向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。取圖像1中的某個關鍵點，並找出其與圖像2中歐式距離最近的前兩個關鍵點，在這兩個關鍵點中，如果最近的距離除以次近的距離少於某個比例閾值，則接受這一對匹配點。降低這個比例閾值，SIFT匹配點數目會減少，但更加穩定。

⑶ sift演算法是什麼

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

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

sift演算法的應用

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