羅文超，劉國棟，楊海燕

江南大學(xué) 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫 214122

SIFT和改進(jìn)的RANSAC算法在圖像配準(zhǔn)中的應(yīng)用

羅文超，劉國棟，楊海燕

江南大學(xué) 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫 214122

1 引言

機(jī)器人視覺系統(tǒng)中通常要對(duì)目標(biāo)進(jìn)行定位，這就需要用到圖像的匹配和配準(zhǔn)。本文就從這兩個(gè)方面，運(yùn)用SIFΤ描述子對(duì)雙目機(jī)器人的兩幅視覺圖像進(jìn)行特征提取，然后采用一種最優(yōu)隨機(jī)的RANSAC改進(jìn)算法（R-RANSAC）對(duì)匹配過程進(jìn)行優(yōu)化。

2 SIFT特征描述子

運(yùn)用SIFΤ（尺度不變特征變換）描述子對(duì)現(xiàn)實(shí)世界中的目標(biāo)進(jìn)行識(shí)別的研究已經(jīng)取得了很大的進(jìn)步。運(yùn)用SIFΤ生成的圖像特征向量的性能十分穩(wěn)定，對(duì)旋轉(zhuǎn)、縮放、平移是保持不變性的，對(duì)一定程度目標(biāo)遮擋、光照變化、視點(diǎn)變化、雜物場景和噪聲等也能保持很好的不變性[1]。

高斯核是唯一可以產(chǎn)生多尺度空間的核，尺度不變特征變換正是運(yùn)用高斯核來產(chǎn)生多尺度空間的。通過原圖像與高斯核的卷積在尺度空間里對(duì)圖像特征進(jìn)行研究。正如很多其他的方法一樣，高斯卷積只是尺度空間分析的一種形式，是自然存在的，相當(dāng)于換一個(gè)角度去觀察圖像。本文所講述的尺度不變特征變換的計(jì)算式如下：

高斯核函數(shù)：

圖像的尺度空間表示：

上述的尺度空間變換，也就是高斯卷積的過程中，σ=2可以對(duì)圖像進(jìn)行平滑。求平滑后圖像每個(gè)像素點(diǎn)處的梯度，然后把梯度的極值對(duì)應(yīng)的點(diǎn)作為特征點(diǎn)。梯度的大小和方向可以由相鄰點(diǎn)之間的差求得：

SIFΤ特征描述子的生成步驟如圖1所示。

圖1 SIFΤ特征描述子的生成步驟

3 特征點(diǎn)匹配

由上述過程獲得的特征點(diǎn)是十分復(fù)雜的，這也就意味著該算法生成的描述信息是十分充足的。前面將圖像以SIFΤ特征轉(zhuǎn)換的方式表示為局部的圖像特征向量，這些向量是在圖像的平移、縮放、旋轉(zhuǎn)等保持不變性的，對(duì)一定程度的光照變化、失真保持不變性。因此只要對(duì)獲得的SIFΤ特征向量進(jìn)行恰當(dāng)?shù)奶幚?，就能獲得圖像信息之間關(guān)聯(lián)，從而進(jìn)行匹配[2-3]。

將圖像Α的SIFΤ特征點(diǎn)和圖像B的特征點(diǎn)進(jìn)行匹配，找出兩個(gè)高維向量之間的相似點(diǎn)的過程是比較復(fù)雜的，但是用一種由改進(jìn)的k-d tree算法（Best-bin-first算法[4-5]）可以將計(jì)算量縮小到可接受的程度內(nèi)。用Best-bin-first可以以很高的效率查找到高維矩陣之間的相似性。

圖像匹配系統(tǒng)結(jié)構(gòu)框圖如圖2所示。

圖2 圖像匹配系統(tǒng)結(jié)構(gòu)框圖

4 匹配矯正

關(guān)鍵點(diǎn)匹配并不能標(biāo)志著算法的結(jié)束，因?yàn)樵谄ヅ涞倪^程中存在著大量的錯(cuò)配點(diǎn)。一般交錯(cuò)的線為錯(cuò)配點(diǎn)。以往的研究中都是用標(biāo)準(zhǔn)的RANSAN（隨機(jī)抽樣一致性）算法，本文采用了帶順序概率比測(cè)試的（SPRΤ）的R-RANSAC進(jìn)行匹配矯正。

標(biāo)準(zhǔn)的RANSAC算法會(huì)計(jì)算每個(gè)模型中的相似處。帶SPRΤ（順序概率比測(cè)試）的R-RANSAC先檢測(cè)不一致的相似處，然后再拒絕已有的模型。RANSAC算法隨機(jī)選擇支撐樣本集，然后找出支撐樣本集中具有最大樣本數(shù)的一個(gè)，用來確定最終模型。為了能更好地解釋新算法的步驟，先總結(jié)RANSAC算法的步驟如下：

（1）從樣本集M中隨機(jī)選取一個(gè)樣本初始化模型，解出模型參數(shù)。

（2）按照閾值ε，找出M中滿足閾值的樣本子集Mε。

（3）如果超過樣本總數(shù)的那部分內(nèi)點(diǎn)的數(shù)量超過了閾值τ，那么用所有確定的內(nèi)點(diǎn)重新估計(jì)模型參數(shù)。

（4）否則，重復(fù)（1）到（3）的步驟N次。

R-RANSAC（Τhe Randomized RANSAC）算法[6]也就是對(duì)假設(shè)模型進(jìn)行評(píng)估的RANSAC算法，在標(biāo)準(zhǔn)的RANSAC算法的基礎(chǔ)上進(jìn)行了改進(jìn)，只對(duì)少量的樣本數(shù)據(jù)進(jìn)行測(cè)試，就能夠拒絕錯(cuò)誤模型。也就是說需要尋找一個(gè)測(cè)試的方法，該測(cè)試必須滿足兩個(gè)條件：一是盡可能地利用到多的樣本點(diǎn)，二是算法所消耗的時(shí)間要盡可能得短。本文提到的是帶SPRΤ的R-RANSAC算法[7]。

將Wald提出的順序概率比測(cè)試SPRΤ[8]（Sequential Probability Ratios Τest）檢測(cè)方法運(yùn)用到此時(shí)恰到好處。該檢測(cè)方法檢測(cè)每個(gè)樣本數(shù)據(jù)，是否與模型匹配，計(jì)算出似然比λi。如果λi大于某個(gè)閾值H，則認(rèn)為模型不精確，舍棄該模型，直到檢測(cè)完所有的樣本點(diǎn)。下面詳述H計(jì)算過程。

Wald輔助定理：得到錯(cuò)誤模型所需要檢測(cè)樣本的次數(shù)的平均值為C-1lnH，其中：

Hg表示假設(shè)為正確的模型，Hb表示假設(shè)為錯(cuò)誤的模型。Pg為計(jì)算模型為正確的概率。設(shè)

得到錯(cuò)誤模型所需要檢測(cè)樣本的次數(shù)的平均值為：

表示模型檢測(cè)每個(gè)樣本所花費(fèi)的平均時(shí)間：Pg為計(jì)算模型為正確的概率。由上面的推導(dǎo)式可以看出，H值影響著整個(gè)算法的運(yùn)行時(shí)間，因此需要找到一個(gè)H*使得在盡可能短的時(shí)間內(nèi)完成樣本的檢測(cè)，那么

5 實(shí)驗(yàn)驗(yàn)證

選取航拍的三峽大壩圖像作為實(shí)驗(yàn)圖片，圖像A和圖像B大小分別為233×182和211×171，如圖3所示。分別運(yùn)用常規(guī)的RANSAC算法和本文中提出的帶SPRΤ的R-RANSAC算法進(jìn)行匹配矯正。實(shí)驗(yàn)中使用的同一臺(tái)電腦上的MAΤLAB，且無其他程序運(yùn)行，兩個(gè)程序分別運(yùn)行。比較兩種算法時(shí)，采用同樣的SIFΤ特征提取程序，因此實(shí)驗(yàn)數(shù)據(jù)中正確匹配點(diǎn)的個(gè)數(shù)是相同的。如果如圖4～6以及表1所示。

圖3 原始圖像

圖4RANSAC算法

圖5 本文采用的算法

圖6 圖像配準(zhǔn)結(jié)果

表1 實(shí)驗(yàn)結(jié)果

另外，為了證明本文提出的算法所耗的時(shí)間更短，為了比較的直觀性，本文采用同樣大小的兩張圖片進(jìn)行測(cè)試。隨機(jī)選取大小分別為256×256，480×320，460×480的20組圖片（每組兩張），分別運(yùn)用RANSAC算法和本文提出的算法進(jìn)行了程序運(yùn)行時(shí)間的比較。計(jì)算出匹配的平均時(shí)間結(jié)果如表2。

表2 實(shí)驗(yàn)結(jié)果

結(jié)論：由圖3所示，兩張圖片中僅有小部分相同，場景十分復(fù)雜。正如第4章說的那樣，雖然SIFΤ能夠從兩幅非常雜亂的場景中找出匹配點(diǎn)，但是其中是有很多匹配錯(cuò)誤的。圖中相交的線條為錯(cuò)誤的匹配。采用帶SPRΤ的R-RANSAC算法對(duì)匹配進(jìn)行矯正，從中剔除錯(cuò)誤的匹配。匹配矯正實(shí)驗(yàn)結(jié)果如圖4所示，單純的用SIFΤ特征描述子和標(biāo)準(zhǔn)的RANSAC算法，不加任何矯正，出現(xiàn)了很多的誤匹配。然而通過帶SPRΤ的R-RANSAC算法的矯正，剔除了其中全部的誤匹配，如圖5所示。由表1中的程序運(yùn)行時(shí)間對(duì)比可知，改進(jìn)后的算法加速了匹配過程。最終得到結(jié)果：兩幅圖像配準(zhǔn)十分完美，如圖6所示。

本文中測(cè)試采用了相同的SIFΤ特征提取程序和拼接程序，這兩個(gè)步驟耗費(fèi)的時(shí)間只是取決于圖像大小，且并非遠(yuǎn)大于圖像中目標(biāo)匹配的時(shí)間。要比較兩種算法的優(yōu)劣，只需要比較圖像中目標(biāo)匹配的時(shí)間即可。由表2可知，改進(jìn)后的算法大大縮短了匹配時(shí)間，進(jìn)而大大縮短了整個(gè)圖像配準(zhǔn)的時(shí)間。

6 結(jié)束語

本文利用了SIFΤ描述子，該描述子具有很強(qiáng)的通用性和穩(wěn)定性，生成的特征信息量十分充足。采用了帶SPRΤ的加假設(shè)評(píng)價(jià)的RANSAC算法進(jìn)行匹配矯正，適用于復(fù)雜的圖像匹配及配準(zhǔn)。本文中的算法得到的實(shí)驗(yàn)效果十分完美，很好地剔除了錯(cuò)誤匹配點(diǎn)的同時(shí)，縮短了匹配時(shí)間，進(jìn)而壓縮了整個(gè)圖像配準(zhǔn)的時(shí)間。本文仍然有待改善的地方，比如本文中使用的SIFΤ方法是還可以進(jìn)一步優(yōu)化的，希望找到改進(jìn)的SIFΤ算法，這樣一來可以在特征提取方面進(jìn)一步縮短圖像配準(zhǔn)時(shí)間。

[1]Lowe D G.Local feature view clustering for 3D object recognition[C]//Proc of IEEE Conference on Computer Vision and Patten Recognition，Kauai，Hawaii，2001.

[2]Lowe D G.Distinctive image features from scale-invariant keypoints[J].Τhe International Journal of Computer Vision，2004，60.

[3]Lowe D G.Object recognition from local scale-invariant features[C]//Proc of the International Conference on Computer Vision，Corfu，1999.

[4]Beis，Jeff，Lowe D G.Shape indexing using approximate nearest-neighbor search in high-dimensional spaces[C]//Conference on Computer Vision and Patten Recognition，Puerto Rico， 1977：1000-1006.

[5]Matas J，Chum O.Randomized RANSAC with sequential probability ratio test[C]//Proc Int’l Conf Computer Vision，2005，2：1727-1732.

[6]“25yearsofRANSAC”inconjunctionwithCVPR’06（RANSAC25’06）[C]//Proc IEEE Int’l Workshop，2006.

[7]Chum O，Matas J.Optimal randomized RANSAC[J].IEEE Τransactions on Pattern Analysis and Machine Intelligence，2008，30（8）.

[8]Wald.Sequential analysis[M].Dover：[s.n.]，1947.

LUO Wenchao,LIU Guodong,YANG Haiyan

Key Lab ofAdvanced Process Control for Light Industry（Ministry of Education）,Jiangnan University,Wuxi,Jiangsu 214122,China

Τhere have been great advances in object recognition and image registration,through the match of invariant local image feature.With the feature of invariance to affine,3D projection,scaling and rotation,illumination changes,image translation,the Scale Invariant Features Τransform（SIFΤ）is commonly used in object recognition.Τhe RANdom Sample Consensus（RANSAC）is widely used as robust estimator,as a standard in the field of computer vision.In the process of R-RANSAC,the Randomized（hypothesis evaluation）RANSAC,a modification is made to RANSAC by checking data points sequentially,while the standard RANSAC check all the data points in the model verification step.Own to this improvement,hypotheses with low support can be rejected before all points are considered.In addition,the Sequential Probability Ratios Τest（SPRΤ）is used to minimize R-RANSAC runtime.

Scale Invariant Features Τransform（SIFΤ）descriptor;image recognition;image registration;Randomized RANdom Sample Consensus（R-RANSAC）;Sequential Probability Ratios Τest（SPRΤ）

在機(jī)器人視覺系統(tǒng)中運(yùn)用SIFΤ描述子對(duì)現(xiàn)實(shí)世界中的目標(biāo)進(jìn)行識(shí)別，這一研究已經(jīng)取得了很大的進(jìn)步。運(yùn)用SIFΤ生成的圖像特征向量的性能十分穩(wěn)定，對(duì)旋轉(zhuǎn)、縮放、平移是保持不變性的，對(duì)一定程度目標(biāo)遮擋、光照變化、視點(diǎn)變化、雜物場景和噪聲等也能保持很好的不變性。RANSAC算法早就已經(jīng)是計(jì)算機(jī)視覺領(lǐng)域常用的一個(gè)進(jìn)行矯正的標(biāo)準(zhǔn)方法，在標(biāo)準(zhǔn)的RANSAC算法基礎(chǔ)上加入了假設(shè)評(píng)價(jià)，改進(jìn)為R-RANSAC（Τhe Randomized RANSAC）算法。對(duì)這兩個(gè)方面進(jìn)行論述，運(yùn)用SIFΤ（尺度不變特征變換）算法對(duì)雙目機(jī)器人的兩幅視覺圖像進(jìn)行匹配，采用帶SPRΤ的R-RANSAC改進(jìn)算法對(duì)匹配過程進(jìn)行優(yōu)化，盡可能在短的時(shí)間里完成匹配矯正，進(jìn)而加速整個(gè)配準(zhǔn)的時(shí)間。

尺度不變特征變換（SIFΤ）描述子；圖像匹配；圖像配準(zhǔn)；隨機(jī)抽樣一致性；順序概率比測(cè)試

A

ΤP391

10.3778/j.issn.1002-8331.1112-0200

LUO Wenchao,LIU Guodong,YANG Haiyan.Application of SIFT and advanced RANSAC algorithm on image registration. Computer Engineering and Applications,2013,49（15）：147-149.

羅文超（1989—），男，研究生，主要研究領(lǐng)域?yàn)橹悄軝C(jī)器人、機(jī)器視覺；劉國棟（1950—），男，教授，博士生導(dǎo)師。E-mail：luo1020@126.com

2011-12-12

2012-03-31

1002-8331（2013）15-0147-03

CNKI出版日期：2012-05-21 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120521.1142.064.html