一種簡化的SIFT特征匹配算法研究

尹麗花 陳勇 楊玉平

摘 要 針對經典SIFT算法因特征描述符維數過高而導致匹配效率降低的問題，本文提出了一種簡化的SIFT特征匹配算法，首先對算子進行降維，以提高速度，然后用雙向匹配消除錯配以保證算法的準確性，實驗取得了較好的結果，驗證了方法的可行性。

關鍵詞 SIFT 尺度空間 圖像匹配 特征描述符

中圖分類號：TP39文獻標識碼：A

Research on the Simplified SIFT Feature Matching Algorithm

YIN Lihua[1], CHEN Yong[1], YANG Yuping[2]

([1] Chongqing Normal University, Chongqing 401331;

[2] Chongqing College of Electronic Engineering, Chongqing 401331)

Abstract For SIFT algorithm, for the matching problem of the classic descriptors for feature dimension is too high and lead to reduced efficiency, this paper presents a simplified SIFT feature matching algorithm, the first of the operator dimensionality reduction to improve the speed, then use two-way matching to eliminate errors together with the algorithm to ensure the accuracy of experiments and achieved good results, verify the feasibility of the method.

Key wordsSIFT; scale space; image matching; feature descriptors

0 引言

圖像匹配是同一場景在兩個不同視點下的圖像之間的對應關系，是虛擬現實、計算機視覺等研究領域的一個熱點，也是計算機視覺應用，如深度恢復、攝像機標定、運動分析以及三維重構等研究的基本問題。①總結起來，圖像匹配算法大致分為：基于面積的方法、②基于比值的方法③等，但這些算法有著共同的缺點。本文提出一種簡化的SIFT算法，通過減少特征描述符的維數來降低計算的復雜度，并采用雙向匹配增強匹配的精度。

1 SIFT算法研究

SIFT( scale invariant feature transform，即尺度不變特征變換)算法是David G．Lowe于1999年提出，2004年進行了總結和完善的特征匹配算法，SIFT特征匹配算法共分為如下五個步驟：

1.1 尺度空間的形成。

Koendetink等人證明了高斯卷積核是實現尺度變換的惟一線性核，因此，一幅二維圖像的尺度空間可定義為：

() =()* ()（1）

式中：L為尺度空間，()為空間坐標， 則為尺度因子。 的值越小表示圖像越清晰，越大則表示圖像越模糊。為了提高尺度空間中被檢測關鍵點的穩定性，采用了高斯差分尺度空間()。定義為兩相鄰尺度的高斯核差分，公式如下：

() = [ () ()]* () =() -()（2）

1.2 空間極值點的檢測

在中，為確保在尺度空間及二維圖像空間都能檢測到極值點，每一個像素點(最頂層和最底層像素點除外)要和其上下兩層各9個及同層8個相鄰點進行比較。并通過擬和三維二次函數來精確確定特征點的尺度和位置，同時去除對比度低的特征點和不穩定的邊緣特征點，以增強圖像匹配的穩定性、提高抗噪聲能力。

1.3 特征點方向分配

為使算子具備旋轉不變性，統計特征點鄰域像素的梯度方向直方圖，以確定每個特征點的方向參數。

1.4 特征點描述器的生成

為了增強算子的抗噪能力，每個特征點選用16個種子點來描述，而每個種子點又有8個方向的向量信息，因此，每個特征點就能形成16?共128維的SIFT特征向量。

1.5 特征匹配

SIFT算法選用歐式距離作為特征點的相似性度量函數，設定一個閾值，當距離小于這個閾值時就接受這一對匹配點。

2 簡化的SIFT算法研究

2.1 簡化算法的匹配步驟

經典算法中，第三步的計算時間在整個算法中占了70%多，大大地降低了算法的速度，影響了實時性。為了改善這一狀況，將第二、三步合并，并在對特征點進行描述時，把原來的128維向量降為現在的12維向量。匹配步驟如下：

2.1.1 初步特征點的檢測（方法同原算法）

2.1.2 形成特征向量

（1）以初步檢測到的特征點為中心采用圓形窗體來確定需要統計的領域范圍，選取圓形窗口半徑為4.5s，在該窗體內統計12個梯度方向。

（2）歸一化這12個梯度方向，以保證算子的光照不變性。用表示特征向量，即 = ，歸一化后得到：

（3）

（3）為保證算子的旋轉不變性，查找最大的梯度方向統計量。向左循環移動整個向量序列，直至梯度方向統計量最大的元素移動到序列的第一個元素。

2.1.3 特征匹配

為保證算法的精度，采用雙向匹配。即第一次匹配完后，記錄下成功匹配的坐標對，然后交換匹配對的坐標位置，再匹配一次，如果這兩次匹配得到的坐標對是一樣的，就接受這一對匹配點。

2.2 維數設定

簡化算法中最重要的一步就是圓形窗口中維數n的設定，實驗結果表明，當＜12時，匹配效率隨著維數的增加呈指數級增加；反之，當＞12時，匹配效率卻隨著維數的增加反而下降。由此可得，當 =12時，匹配效率最高， =12即為所需確定的維數。對于匹配效率，定義為：

匹配效率 = （4）

3 仿真實驗及結果

為了驗證算法，在CPU為Intel Corei3 2.20GHz，內存為2G的PC機上采用Matlab7.8軟件平臺進行實驗。為了證明算法對物體旋轉、遮擋和光照的魯棒性，在設計場景的時候將物體任意擺放，在不同的光照條件下進行實驗，部分效果及結果如圖表所示，其中圖1(a)為SIFT算法匹配圖像，圖1(b)為簡化SIFT算法匹配圖像，表1為兩種算法匹配對比結果。

4 結論

總之，本文研究了經典SIFT算法，并分析了算法的優勢及其局限性，從匹配速度上加以了改進。首先利用圓形窗口本身的旋轉不變特性對算法進行降維，從原來的128維降為12維;其次采用雙向匹配提高匹配的精度，去除可能存在的不明顯誤匹配。將匹配結果同原SIFT算法進行了比較，試驗結果表明本文改進算法比原SIFT算法在速度上有了很大的提高，同時在一定程度上也保證了精度。

注釋

① 孔曉東,屈磊,桂國富等.基于極約束和邊緣點檢測的圖像密集匹配[J].計算機工程,2004(20):178-179.

② 甘進,王曉丹.基于特征點的快速匹配算法[J].電子與控制,2009.16(2):64-66.

③ 鐘力,胡小鋒.重疊圖像拼接算法[J].中國圖象圖形學報,1998.3(3):365-369.