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

尹麗花 陳勇 楊玉平

摘 要 針對(duì)經(jīng)典SIFT算法因特征描述符維數(shù)過高而導(dǎo)致匹配效率降低的問題，本文提出了一種簡化的SIFT特征匹配算法，首先對(duì)算子進(jìn)行降維，以提高速度，然后用雙向匹配消除錯(cuò)配以保證算法的準(zhǔn)確性，實(shí)驗(yàn)取得了較好的結(jié)果，驗(yàn)證了方法的可行性。

關(guān)鍵詞 SIFT 尺度空間 圖像匹配 特征描述符

中圖分類號(hào)：TP39文獻(xiàn)標(biāo)識(shí)碼：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 引言

圖像匹配是同一場(chǎng)景在兩個(gè)不同視點(diǎn)下的圖像之間的對(duì)應(yīng)關(guān)系，是虛擬現(xiàn)實(shí)、計(jì)算機(jī)視覺等研究領(lǐng)域的一個(gè)熱點(diǎn)，也是計(jì)算機(jī)視覺應(yīng)用，如深度恢復(fù)、攝像機(jī)標(biāo)定、運(yùn)動(dòng)分析以及三維重構(gòu)等研究的基本問題。①總結(jié)起來，圖像匹配算法大致分為：基于面積的方法、②基于比值的方法③等，但這些算法有著共同的缺點(diǎn)。本文提出一種簡化的SIFT算法，通過減少特征描述符的維數(shù)來降低計(jì)算的復(fù)雜度，并采用雙向匹配增強(qiáng)匹配的精度。

1 SIFT算法研究

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

1.1 尺度空間的形成。

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

() =()* ()（1）

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

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

1.2 空間極值點(diǎn)的檢測(cè)

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

1.3 特征點(diǎn)方向分配

為使算子具備旋轉(zhuǎn)不變性，統(tǒng)計(jì)特征點(diǎn)鄰域像素的梯度方向直方圖，以確定每個(gè)特征點(diǎn)的方向參數(shù)。

1.4 特征點(diǎn)描述器的生成

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

1.5 特征匹配

SIFT算法選用歐式距離作為特征點(diǎn)的相似性度量函數(shù)，設(shè)定一個(gè)閾值，當(dāng)距離小于這個(gè)閾值時(shí)就接受這一對(duì)匹配點(diǎn)。

2 簡化的SIFT算法研究

2.1 簡化算法的匹配步驟

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

2.1.1 初步特征點(diǎn)的檢測(cè)（方法同原算法）

2.1.2 形成特征向量

（1）以初步檢測(cè)到的特征點(diǎn)為中心采用圓形窗體來確定需要統(tǒng)計(jì)的領(lǐng)域范圍，選取圓形窗口半徑為4.5s，在該窗體內(nèi)統(tǒng)計(jì)12個(gè)梯度方向。

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

（3）

（3）為保證算子的旋轉(zhuǎn)不變性，查找最大的梯度方向統(tǒng)計(jì)量。向左循環(huán)移動(dòng)整個(gè)向量序列，直至梯度方向統(tǒng)計(jì)量最大的元素移動(dòng)到序列的第一個(gè)元素。

2.1.3 特征匹配

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

2.2 維數(shù)設(shè)定

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

匹配效率 = （4）

3 仿真實(shí)驗(yàn)及結(jié)果

為了驗(yàn)證算法，在CPU為Intel Corei3 2.20GHz，內(nèi)存為2G的PC機(jī)上采用Matlab7.8軟件平臺(tái)進(jìn)行實(shí)驗(yàn)。為了證明算法對(duì)物體旋轉(zhuǎn)、遮擋和光照的魯棒性，在設(shè)計(jì)場(chǎng)景的時(shí)候?qū)⑽矬w任意擺放，在不同的光照條件下進(jìn)行實(shí)驗(yàn)，部分效果及結(jié)果如圖表所示，其中圖1(a)為SIFT算法匹配圖像，圖1(b)為簡化SIFT算法匹配圖像，表1為兩種算法匹配對(duì)比結(jié)果。

4 結(jié)論

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

注釋

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

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

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