SIFT特征匹配技術

SIFT特征匹配技術ScaleInvariantFeatureTransformSIFT算法提出及其改進SIFT算法由1999年提出，2004年完善總結。[1]DavidG.Lowe,"Objectrecognitionfromlocalscale-invariantfeatures,"InternationalConferenceonComputerVision,Corfu,Greece(September1999),pp.1150-1157.

[2]DavidG.Lowe,"Distinctiveimagefeaturesfromscale-invariantkeypoints,"InternationalJournalofComputerVision,60,2(2004),pp.91-110.后來Y.Ke將其描述子局部用PCA代替直方圖的方式，對其進行改進。[3]Y.KeandR.Sukthankar.PCA-SIFT:AMoreDistinctiveRepresentationforLocalImageDescriptors.ComputerVisionandPatternRecognition,2004

SIFT算法主要思想SIFT算法是一種提取局部特征的算法，在尺度空間尋找極值點，提取位置，尺度，旋轉(zhuǎn)不變量。SIFT算法的主要特點：a)SIFT特征是圖像的局部特征，其對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。

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

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

d)高速性，經(jīng)優(yōu)化的SIFT匹配算法甚至可以到達實時的要求。

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

圖像多尺度表示(x,y)代表圖像的像素位置，σ稱為尺度空間因子，其值越小那么表征該圖像被平滑的越少，相應的尺度也就越小。SIFT算法SIFT算法SIFT算法步驟:Sift特征匹配算法主要包括兩個階段，一個是Sift特征的生成，即從多幅圖像中提取對尺度縮放、旋轉(zhuǎn)、亮度變化無關的特征向量；第二階段是Sift特征向量的匹配。

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

1、構建尺度空間，檢測極值點，獲得尺度不變性；

2、特征點過濾并進行精確定位；3、為特征點分配方向值；4、生成特征描述子。

構建尺度空間設輸入圖像經(jīng)過s次卷積后可以得到高斯卷積函數(shù)為G(x,y,2σ)的輸出圖像,所有σ從到2σ的圖像構成一個octave,每個octave固定有s個平面。每一層Ip=G(x,y,kpσ)*I,p=1,2,…,s.而ks=2。根據(jù)高斯函數(shù)的性質(zhì)可得:構建尺度空間建立高斯金字塔為了得到在不同尺度空間下的穩(wěn)定特征點,將圖像I(x,y)與不同尺度因子下的高斯核G(x,y,σ)進行卷積操作,構成高斯金字塔。高斯金字塔有o階,一般選擇4階,每一階有s層尺度圖像,s一般選擇5層。建立高斯金字塔在高斯金字塔的構成中要注意,第1階的第1層是放大2倍的原始圖像,其目的是為了得到更多的特征點;在同一階中相鄰兩層的尺度因子比例系數(shù)是k,那么第1階第2層的尺度因子是kσ,然后其它層以此類推那么可;第2階的第1層由第一階的中間層尺度圖像進行子抽樣獲得,其尺度因子是k2σ,然后第2階的第2層的尺度因子是第1層的k倍即k3σ。第3階的第1層由第2階的中間層尺度圖像進行子抽樣獲得。其它階的構成以此類推。構建尺度空間需確定的參數(shù)σ－尺度空間坐標O－octave坐標S－sub-level坐標和O、S的關系，σ(O,S)=2o+s/S,o∈omin+[0,...,O-1],s∈[0,...,S-1]其中σ0是基準層尺度。o-octave坐標，s-sub-level坐標。注：octaves的索引可能是負的。第一組索引常常設為0或者-1,當設為-1的時候，圖像在計算高斯尺度空間前先擴大一倍。空間坐標x是組octave的函數(shù)，設是x0組的空間坐標，那么Scale-spaceDefinition: whereKeypointsaredetectedusingscale-spaceextremaindifference-of-GaussianfunctionDCloseapproximationtoscale-normalizedLaplacianofGaussian,RelationshipofDtoDiffusionequation:Approximate?G/?σ:giving,Therefore,WhenDhasscalesdifferingbyaconstantfactoritalreadyincorporatestheσ2scalenormalizationrequiredforscale-invariance建立DOG金字塔DOG金字塔通過高斯金字塔中相鄰尺度空間函數(shù)相減即可,如圖2所示。在圖中,DOG金字塔的第1層的尺度因子與高斯金字塔的第1層是一致的,其它階也一樣。

Imagespacetoscalespacek4σk3σk2σkσσDOG空間的極值檢測在上面建立的DOG尺度空間金字塔中,為了檢測到DOG空間的最大值和最小值,DOG尺度空間中中間層(最底層和最頂層除外)的每個像素點需要跟同一層的相鄰8個像素點以及它上一層和下一層的9個相鄰像素點總共26個相鄰像素點進行比較,以確保在尺度空間和二維圖像空間都檢測到局部極值。標記為叉號的像素假設比相鄰26個像素的DOG值都大或都小,那么該點將作為一個局部極值點,記下它的位置和對應尺度。LocalextremadetectionFindmaximaandminimainscalespace

精確定位特征點位置由于DOG值對噪聲和邊緣較敏感,因此,在上面DOG尺度空間中檢測到局部極值點還要經(jīng)過進一步的檢驗才能精確定位為特征點。下面對局部極值點進行三維二次函數(shù)擬和以精確確定特征點的位置和尺度,尺度空間函數(shù)D(x,y,σ)在局部極值點處的泰勒展開式如公式(4)所示。精確的極值位置公式(4)中的一階和二階導數(shù)是通過附近區(qū)域的差分來近似求出的,列出其中的幾個,其它的二階導數(shù)以此類推。通過對公式(4)求導,并令其為0,得出精確的極值位置,如公式(5)所示:去除低比照度的特征點在上面精確確定的特征點中,同時要去除低比照度的特征點和不穩(wěn)定的邊緣響應點,以增強匹配穩(wěn)定性、提高抗噪聲能力。去除低比照度的特征點:把公式(5)代到公式(4)中,只要前兩項,得到公式(6):通過式(6)計算出D(Xmax),假設|D(Xmax)|≥0.03,那么該特征點就保存下來,否那么就丟棄。去除不穩(wěn)定的邊緣響應點海森矩陣如公式(7)所示,其中的偏導數(shù)是上面確定的特征點處的偏導數(shù),它也是通過附近區(qū)域的差分來近似估計的。去除不穩(wěn)定的邊緣響應點通過2×2的海森矩陣H來計算主曲率,由于D的主曲率與H矩陣的特征值成比例,不具體求特征值,求其比例ratio。設α是最大幅值特征,β是次小的，r=α/β，那么ratio如公式(8)所示。通過公式(8)求出ratio,常取r=10,假設ratio≤(r+1)2/r,那么保存該特征點,否那么就丟棄。確定特征點主方向利用特征點鄰域像素的梯度方向分布特性為每個特征點指定方向參數(shù),使算子具備旋轉(zhuǎn)不變性。公式(9)為(x,y)處的梯度值和方向。L所用的尺度為每個特征點各自所在的尺度,(x,y)要確定是哪一階的哪一層。

在實際計算過程中,在以特征點為中心的鄰域窗口內(nèi)采樣,并用梯度方向直方圖統(tǒng)計鄰域像素的梯度方向。梯度直方圖的范圍是0～360°,其中每10°一個柱,總共36個柱。梯度方向直方圖的峰值那么代表了該特征點處鄰域梯度的主方向,即作為該特征點的方向。在梯度方向直方圖中,當存在另一個相當于主峰值80%能量的峰值時,那么將這個方向認為是該特征點的輔方向。一個特征點可能會被指定具有多個方向(一個主方向,一個以上輔方向),這可以增強匹配的魯棒性。通過上面的3步,圖像的特征點已檢測完畢,每個特征點有3個信息:位置、對應尺度、方向。生成SIFT特征向量首先將坐標軸旋轉(zhuǎn)為特征點的方向,以確保旋轉(zhuǎn)不變性。接下來以特征點為中心取8×8的窗口(特征點所在的行和列不取)。在圖4(a)中,中央黑點為當前特征點的位置,每個小格代表特征點鄰域所在尺度空間的一個像素,箭頭方向代表該像素的梯度方向,箭頭長度代表梯度模值,圖中圈內(nèi)代表高斯加權的范圍(越靠近特征點的像素,梯度方向信息奉獻越大)。然后在每4×4的圖像小塊上計算8個方向的梯度方向直方圖,繪制每個梯度方向的累加值,形成一個種子點,如圖4(b)所示。此圖中一個特征點由2×2共4個種子點組成,每個種子點有8個方向向量信息,可產(chǎn)生2×2×8共32個數(shù)據(jù),形成32維的SIFT特征向量即特征點描述器,所需的圖像數(shù)據(jù)塊為8×8。這種鄰域方向性信息聯(lián)合的思想增強了算法抗噪聲的能力,同時對于含有定位誤差的特征匹配也提供了較好的容錯性。生成SIFT特征向量實際計算過程中,為了增強匹配的穩(wěn)健性,建議對每個特征點使用4×4共16個種子點來描述,每個種子點有8個方向向量信息,這樣對于一個特征點就可以產(chǎn)生4×4×8共128個數(shù)據(jù),最終形成128維的SIFT特征向量,所需的圖像數(shù)據(jù)塊為16×16。此時SIFT特征向量已經(jīng)去除了尺度變化、旋轉(zhuǎn)等幾何變形因素的影響,再繼續(xù)將特征向量的長度歸一化,那么可以進一步去除光照變化的影響。SIFT特征向量的匹配首先,進行相似性度量。一般采用各種距離函數(shù)作為特征的相似性度量,如歐氏距離、馬氏距離等。通過相似性度量得到圖像間的潛在匹配。本文中采用歐氏距離作為兩幅圖像間的相似性度量。取圖像1中的某個關鍵點，并找出其與圖像2中歐式距離最近的前兩個關鍵點，在這兩個關鍵點中，如果最近的距離除以次近的距離少于某個比例閾值，那么接受這一對匹配點。降低這個比例閾值，SIFT匹配點數(shù)目會減少，但更加穩(wěn)定。采用優(yōu)先k-d樹近似BBF搜索算法進行優(yōu)先搜索來查找每個特征點的2個近似最近鄰特征點。其次,消除錯配。通過相似性度量得到潛在匹配對,其中不可防止會產(chǎn)生一些錯誤匹配,因此需要根據(jù)幾何限制和其它附加約束消除錯誤匹配,提高魯棒性。常用的去外點方法是RANSAC隨機抽樣一致性算法,常用的幾何約束是極線約束關系。。隨機抽樣一致性算法(RANSAC)是一種魯棒的變換估計算法,利用特征集合的內(nèi)在幾何約束關系進一步剔除錯誤的匹配。RANSAC算法的主要思想:首先隨機地選擇兩個點,這兩個點確定了一條直線,在這條直線一定距離范圍內(nèi)的點稱為這條直線的支撐。隨機選擇重復數(shù)次,具有最大支撐特征集的直線被確認為是樣本點集的擬和。在擬和的誤差距離范圍內(nèi)的點稱為內(nèi)點,反之那么為外點。RANSAC算法由于共線的匹配特征點在透視變換參數(shù)計算的過程中易出現(xiàn)奇異情況,導致圖像拼接錯誤。一種改進的RANSAC算法:根據(jù)RANSAC算法的思想,隨機地選擇3個特征點確定一個圓線進行擬和。這樣做可以降低匹配特征點共線的風險,同時在一定程度