一、Sift算法簡介

　　Sift算法是David Lowe于1999年提出的局部特征描述子，并于2004年進行了更深入的發(fā)展和完善。Sift特征匹配算法可以處理兩幅圖像之間發(fā)生平移、旋轉(zhuǎn)、仿射變換情況下的匹配問題，具有很強的匹配能力。總體來說，Sift算子具有以下特性：

　　（1）Sift特征是圖像的局部特征，對平移、旋轉(zhuǎn)、尺度縮放、亮度變化、遮擋和噪聲等具有良好的不變性，對視覺變化、仿射變換也保持一定程度的穩(wěn)定性。

　　（2）獨特性好，信息量豐富，適用于在海量特征數(shù)據(jù)庫中進行快速、準確的匹配。

　　（3）多量性，即使少數(shù)的幾個物體也可以產(chǎn)生大量Sift特征向量。

　　（4）速度相對較快，經(jīng)優(yōu)化的Sift匹配算法甚至可以達到實時的要求。

　　（5）可擴展性強，可以很方便的與其他形式的特征向量進行聯(lián)合。

　　其Sift算法的三大工序為：

　　（1）提取關鍵點；

　　（2）對關鍵點附加詳細的信息（局部特征）也就是所謂的描述器；

　　（3）通過兩方特征點（附帶上特征向量的關鍵點）的兩兩比較找出相互匹配的若干對特征點，也就建立了景物間的對應關系。提取關鍵點和對關鍵點附加詳細的信息（局部特征）也就是所謂的描述器可以稱做是Sift特征的生成，即從多幅圖像中提取對尺度縮放、旋轉(zhuǎn)、亮度變化無關的特征向量。

　　Sift特征的生成一般包括以下幾個步驟：

　　（1）構(gòu)建尺度空間，檢測極值點，獲得尺度不變性；

　　（2）特征點過濾并進行精確定位；

　　（3）為特征點分配方向值；

　　（4）計算變換參數(shù)

　　當兩幅圖像的Sift特征向量生成以后，下一步就可以采用關鍵點特征向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。取圖1的某個關鍵點，通過遍 歷找到圖像2中的距離最近的兩個關鍵點。在這兩個關鍵點中，如果次近距離除以最近距離小于某個闕值，則判定為一對匹配點。

　　二、Surf算法原理

　　（1）構(gòu)建Hessian矩陣

　　Hessian矩陣是Surf算法的核心，為了方便運算，假設函數(shù)f（z，y），Hessian矩陣H是由函數(shù)，偏導數(shù)組成：

　　H矩陣判別式為：

　　判別式的值是H矩陣的特征值，可以利用判定結(jié)果的符號將所有點分類，根據(jù)判別式取值正負，來判別該點是或不是極值點。在SURF算法中，用圖像像素l（x，y）代替函數(shù)值f（x，y），選用二階標準高斯函數(shù)作為濾波器，通過特定核間的卷積計算二階偏導數(shù)，這樣便能計算出H矩陣的三個矩陣元素L。、L。、k，從而計算出H矩陣：

　　L。（X，￡）是一幅圖像在不同解析度下的表示，可以利用高斯核G（￡）與圖像函數(shù)，（X）在點X一（z，y）的卷積來實現(xiàn)，核函數(shù)G（￡）具體表示如式（5），g（￡）為高斯函數(shù)，t為高斯方差，L。與L。同理。通過這種方法可以為圖像中每個像素計算出其H行列式的決定值，并用這個值來判別特征點。為方便應用，Herbert Bay提出用近似值現(xiàn)代替L。為平衡準確值與近似值間的誤差引入權(quán)值叫，權(quán)值硼隨尺度變化，則H矩陣判別式可表示為：

　　（2）構(gòu)建尺度空間

　　圖像的尺度空間是這幅圖像在不同解析度下的表示，由式（4）知，一幅圖像j（X）在不同解析度下的表示可以利用高斯核G（￡）的卷積來實現(xiàn)，圖像的尺度大小一般用高斯標準差來表示［6］。在計算視覺領域，尺度空間被象征性的表述為一個圖像金字塔，其中，輸入圖像函數(shù)反復與高斯函數(shù)的核卷積并反復對其進行二次抽樣，這種方法主要用于Sift算法的實現(xiàn)，但每層圖像依賴于前一層圖像，并且圖像需要重設尺寸，因此，這種計算方法運算量較大，而SURF算法申請增加圖像核的尺寸，這也是SIFT算法與SURF算法在使用金字塔原理方面的不同。算法允許尺度空間多層圖像同時被處理，不需對圖像進行二次抽樣，從而提高算法性能。圖1（a）是傳統(tǒng)方式建立一個如圖所示的金字塔結(jié)構(gòu)，圖像的寸是變化的，并且運（1） 算會反復使用高斯函數(shù)對子層進行平滑處理，圖1（b）說明Surf算法使原始圖像保持不變而只改變?yōu)V波器大小。

　　（3）精確定位特征點

　　所有小于預設極值的取值都被丟棄，增加極值使檢測到的特征點數(shù)量減少，最終只有幾個特征最強點會被檢測出來。檢測過程中使用與該尺度層圖像解析度相對應大小的濾波器進行檢測，以3×3的濾波器為例，該尺度層圖像中9個像素點之一圖2檢測特征點與自身尺度層中其余8個點和在其之上及之下的兩個尺度層9個點進行比較，共26個點，圖2中標記‘x’的像素點的特征值若大于周圍像素則可確定該點為該區(qū)域的特征點。

　　（4）主方向確定

　　為保證旋轉(zhuǎn)不變性［8I，首先以特征點為中心，計算半徑為6s（S為特征點所在的尺度值）的鄰域內(nèi)的點在z、y方向的Haar小波（Haar小波邊長取4s）響應，并給這些響應值賦高斯權(quán)重系數(shù)，使得靠近特征點的響應貢獻大，而遠離特征點的響應貢獻小，其次將60。范圍內(nèi)的響應相加以形成新的矢量，遍歷整個圓形區(qū)域，選擇最長矢量的方向為該特征點的主方向。這樣，通過特征點逐個進行計算，得到每一個特征點的主方向。

　　（5）特征點描述子生成

　　首先將坐標軸旋轉(zhuǎn)為關鍵點的方向，以確保旋轉(zhuǎn)不變性。

　　接下來以關鍵點為中心取8×8的窗口。圖左部分的中央黑點為當前關鍵點的位置，每個小格代表關鍵點鄰域所在尺度空間的一個像素，利用公式求得每個像素的梯度幅值與梯度方向，箭頭方向代表該像素的梯度方向，箭頭長度代表梯度模值，然后用高斯窗口對其進行加權(quán)運算，每個像素對應一個向量，長度為，為該像素點的高斯權(quán)值，方向為， 圖中藍色的圈代表高斯加權(quán)的范圍（越靠近關鍵點的像素梯度方向信息貢獻越大）。然后在每4×4的小塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，即可形成一個種子點，如圖右部分示。此圖中一個關鍵點由2×2共4個種子點組成，每個種子點有8個方向向量信息。這種鄰域方向性信息聯(lián)合的思想增強了算法抗噪聲的能力，同時對于含有定位誤差的特征匹配也提供了較好的容錯性。

　　3、原理結(jié)束語

　　Sift/Surf采用Henssian矩陣獲取圖像局部最值還是十分穩(wěn)定的，但是在求主方向階段太過于依賴局部區(qū)域像素的梯度方向，有可能使得找到的主 方向不準確，后面的特征向量提取以及匹配都嚴重依賴于主方向，即使不大偏差角度也可以造成后面特征匹配的放大誤差，從而匹配不成功；另外圖像金字塔的層取 得不足夠緊密也會使得尺度有誤差，后面的特征向量提取同樣依賴相應的尺度，發(fā)明者在這個問題上的折中解決方法是取適量的層然后進行插值。Sift是一種只 利用到灰度性質(zhì)的算法，忽略了色彩信息，后面又出現(xiàn)了幾種據(jù)說比Surf更穩(wěn)定的描述器其中一些利用到了色彩信息，讓我們拭目以待吧。

　　三、sift算法的應用

　　SIFT算法目前在軍事、工業(yè)和民用方面都得到了不同程度的應用，其應用已經(jīng)滲透了很多領域，典型的應用如下：

　　1、物體識別

　　2、機器人定位與導航

　　3、圖像拼接

　　4、三維建模

　　5、手勢識別

　　6、視頻跟蹤

　　7、筆記鑒定

　　8、指紋與人臉識別

　　9、犯罪現(xiàn)場特征提取