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

羅文超，劉國棟，楊海燕

江南大學(xué) 輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122

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

羅文超，劉國棟，楊海燕

江南大學(xué) 輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122

1 引言

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

2 SIFT特征描述子

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

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

高斯核函數(shù)：

圖像的尺度空間表示：

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

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

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

3 特征點匹配

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

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

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

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

4 匹配矯正

關(guān)鍵點匹配并不能標志著算法的結(jié)束，因為在匹配的過程中存在著大量的錯配點。一般交錯的線為錯配點。以往的研究中都是用標準的RANSAN（隨機抽樣一致性）算法，本文采用了帶順序概率比測試的（SPRΤ）的R-RANSAC進行匹配矯正。

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

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

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

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

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

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

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

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

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

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

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

5 實驗驗證

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

圖3 原始圖像

圖4RANSAC算法

圖5 本文采用的算法

圖6 圖像配準結(jié)果

表1 實驗結(jié)果

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

表2 實驗結(jié)果

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

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

6 結(jié)束語

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

[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Τ）

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

尺度不變特征變換（SIFΤ）描述子；圖像匹配；圖像配準；隨機抽樣一致性；順序概率比測試

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)域為智能機器人、機器視覺；劉國棟（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