SIFT特征匹配算法.doc

SIFT特征匹配算法尺度不變特征變換（Scale Invariant Feature Transform，SIFT）是David G Lowe 在1999年提出的基于不變量描述子的匹配算法，SIFT 具有以下特征：（1）SIFT特征是圖像的局部特征，對(duì)平移、旋轉(zhuǎn)、尺度縮放、亮度變化、遮擋和噪聲等具有良好的不變性，對(duì)視覺(jué)變化、 仿射變換也保持一定程度的穩(wěn)定性；（2）獨(dú)特性好，信息量豐富，適用于在海量特征數(shù)據(jù)庫(kù)中進(jìn)行快速、準(zhǔn)確的匹配；（3）多量性，即使少數(shù)的幾個(gè)物體也可以產(chǎn)生大量SIFT特征向量；（4）速度相對(duì)較快，經(jīng)優(yōu)化的SIFT匹配算法甚至可以達(dá)到實(shí)時(shí)的要求。SIFT特征匹配算法主要包括兩個(gè)階段，一個(gè)是SIFT特征向量的生成，第二階段是SIFT特征向量的匹配。1 SIFT特征向量的生成1.1 構(gòu)建尺度空間，檢測(cè)極值點(diǎn)由于Koendetink證明了高斯核是實(shí)現(xiàn)尺度變換的唯一變換核，所以對(duì)圖像在不同尺度下提取圖像特征，從而達(dá)到了尺度不變性。首先建立高斯金字塔，然后再建立DOG（Difference Of Gaussian）金字塔，最后在DOG金字塔的基礎(chǔ)上進(jìn)行極值檢測(cè)。（1）建立高斯金字塔根據(jù)二維高斯濾波函數(shù)，對(duì)圖像進(jìn)行高斯濾波： （1）一幅圖像I(x,y)，在不同尺度空間下的表示可以由圖像與高斯核卷積得到 Gaussian 圖像： （2）其中：（x,y）為圖像I 上的點(diǎn)，L 表示尺度空間，為尺度空間因子。大尺度對(duì)應(yīng)于圖像的概貌特征，小尺度對(duì)應(yīng)于圖像的細(xì)節(jié)特征。值越小表示圖像被平滑得越大，即分辨率越高。根據(jù)尺度函數(shù)來(lái)建立高斯金字塔，高斯金字塔的第一階的第一層是原始圖像。高斯金字塔有o階、s層，在同一階上的兩個(gè)相鄰層之間的尺度比例為k，例如第1階第2層的尺度因子為，則第1階第3層的尺度因子為k，并且每一階圖像是前一階圖像大小的 1/2。 如圖1 左邊的高斯金字塔。圖1 由高斯金字塔建立DOG金字塔關(guān)于尺度空間的理解說(shuō)明：如圖2所示，尺度空間是連續(xù)的。在Lowe的論文中，將第0層的初始尺度定為1.6，圖片的初始尺度定為0.5. 在檢測(cè)極值點(diǎn)前對(duì)原始圖像的高斯 平滑以致圖像丟失高頻信息，所以Lowe建議在建立尺度空間前首先對(duì)原始圖像長(zhǎng)寬擴(kuò)展一倍，以保留原始圖像信息，增加特征點(diǎn)數(shù)量。尺度越大圖像越模糊。圖2 空間尺度變化（2）建立 DOG 高斯金字塔在高斯金字塔的基礎(chǔ)上，利用同一階上的兩個(gè)相鄰的兩層的尺度空間函數(shù)之差得到 DOG高斯金字塔的一層。DOG的表達(dá)式定義為： （3）由此圖 1 可以看出如何由高斯金字塔得到 DOG金字塔。（3）檢測(cè)極值點(diǎn)為了檢測(cè)到DOG空間的局部極值點(diǎn)，每一個(gè)采樣點(diǎn)要和它所有的相鄰點(diǎn)比較。如圖3所示，中間的檢測(cè)點(diǎn)需要與它同層的8個(gè)，上層和下層各9個(gè)像素點(diǎn)進(jìn)行比較，以確保在尺度空間和二維圖像控件都檢測(cè)到極值點(diǎn)。如果該檢測(cè)點(diǎn)為最大值或者最小值，則該點(diǎn)為圖像在該尺度下的一個(gè)候選關(guān)鍵點(diǎn)。圖3 檢測(cè)極值點(diǎn)在極值比較的過(guò)程中，每一組圖像的首末兩層是無(wú)法進(jìn)行極值比較的，為了滿足尺度 變化的連續(xù)性，我們?cè)诿恳唤M圖像的頂層繼續(xù)用高斯模糊生成了3 幅圖像，高斯金字 塔有每組S+3層圖像。DOG金字塔每組有S+2層圖像.1.2特征點(diǎn)過(guò)濾及精確定位關(guān)鍵點(diǎn)的選取要經(jīng)過(guò)兩步：它必須去除低對(duì)比度和對(duì)噪聲敏感的候選關(guān)鍵點(diǎn)；去除邊緣點(diǎn)。（1）去除低對(duì)比度的點(diǎn)對(duì)局部極值點(diǎn)進(jìn)行三維二次函數(shù)擬合以精確確定特征點(diǎn)的位置和尺度，尺度空間函數(shù)的泰勒展開(kāi)式如公式（4）所示： （4）令上式對(duì)x的偏導(dǎo)數(shù)等于0，可得極限點(diǎn)位置 （5）把公式（5）代入公式（4）中，可得： （6）若，該特征點(diǎn)就保留下來(lái)，否則丟棄。（2）去除邊緣點(diǎn)一個(gè)定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率由海森矩陣求出： （7）D的主曲率和H的特征值成正比，令為最大特征值，為最小特征值，則 （8） （9）令=，則： （10）如果，曲率小于(r+1)2/r，保留該特征點(diǎn)，否則丟棄。1.3為關(guān)鍵點(diǎn)分配方向值利用特征點(diǎn)領(lǐng)域像素的梯度方向分布特征來(lái)定關(guān)鍵點(diǎn)的方向，公式如下： （11） （12）m(x,y)表示(x,y)處梯度的模值，(x,y)表示方向，L是關(guān)鍵點(diǎn)所在的空間尺度函數(shù)。用梯度直方圖來(lái)統(tǒng)計(jì)鄰域像素的梯度方向，如圖4所示，梯度直方圖的橫軸代表了鄰域像素的梯度方向的大小，縱軸代表了鄰域像素梯度值的大小。梯度直方圖的橫軸的取值范圍是0360，每10為一個(gè)單位。總共有36個(gè)單位。梯度方向的直方圖的主峰值則代表了該關(guān)鍵點(diǎn)的主方向，如果有相當(dāng)于主峰值的80%大小的其他峰值，則為該關(guān)鍵點(diǎn)的輔方向?？梢钥闯鲫P(guān)鍵點(diǎn)的方向就由一個(gè)主峰值方向和多個(gè)次峰值的方向決定。這樣可以減少圖像旋轉(zhuǎn)對(duì)特征關(guān)鍵點(diǎn)的影響。圖4 方向參數(shù)的確定1.4生成特征向量描述子為了進(jìn)一步描述關(guān)鍵點(diǎn)的信息，則確定關(guān)鍵點(diǎn)的鄰域范圍的大小很重要。 如圖5所示：每個(gè)小方格代表的是關(guān)鍵的鄰域像素，小方格內(nèi)的的箭頭代表了該鄰域像素的梯度方向，箭頭的大小代表了梯度大小。圖5(b)中的左上角的小方塊由圖5(a)中的左上角的四個(gè)小方格組成。即：（b）圖中的每個(gè)小方塊的方向是對(duì)于（a）圖中的方格方向的累積值。 圖5顯示的是（a）圖是88的鄰域范圍，（b）圖顯示的是 22 的種子點(diǎn)（每個(gè)方格代表一個(gè)種子）。 為了增強(qiáng)抗噪能力和匹配的穩(wěn)健性，通常把鄰域的取值范圍設(shè)成1616，那么就會(huì)產(chǎn)生 44 的種子點(diǎn)。 這樣每個(gè)關(guān)鍵點(diǎn)的信息量就包含在了448=128維特征向量里。圖5 特征向量描述子的生成2 SIFT特征向量的匹配對(duì)SIFT特征向量進(jìn)行匹配是根據(jù)相似性度量來(lái)進(jìn)行的，常用的匹配方法有：歐式距離和馬氏距離等。采用歐氏距離對(duì)SIFT的特征向量進(jìn)行匹配。獲取SIFT特征向量后, 采用優(yōu)先k-d樹(shù)進(jìn)行優(yōu)先搜索來(lái)查找每個(gè)特征點(diǎn)的近似最近鄰特征點(diǎn)。在這兩個(gè)特征點(diǎn)中，如果最近的距離除以次近的距離少于某個(gè)比例閾值，則接受