張曉宇，何文思，段紅燕，魏松濤

(蘭州理工大學(xué)機(jī)電工程學(xué)院，甘肅 蘭州 730050)

在機(jī)器視覺研究領(lǐng)域，圖像匹配一直是其中重要的組成部分。匹配算法根據(jù)其思想可以分為兩大類：基于區(qū)域匹配方法和基于特征匹配方法，其中基于特征的匹配方法有計(jì)算速度快、魯棒性好和對圖像變形不敏感等優(yōu)點(diǎn)，是常用的匹配方法。

SIFT(scale-invariant feature transform)[1]是最常用的特征點(diǎn)檢測算法，對圖片的平移、縮放、旋轉(zhuǎn)等具有不變特性，然而SIFT算法在計(jì)算特征點(diǎn)描述子的時(shí)候?qū)γ總€(gè)特征點(diǎn)都需要構(gòu)建128維特征向量，這樣就降低了運(yùn)算速度。Wang和Bay等[2-3]提出的SURF(speeded up robust features)算法，繼承了SIFT的不變性，并在提取圖像的特征點(diǎn)運(yùn)算速度上比SIFT快3倍左右[4]。然而SURF算法在求取特征點(diǎn)主方向時(shí)受到局部區(qū)域像素梯度方向的影響，在匹配過程中僅使用歐氏距離作為評判標(biāo)準(zhǔn)，使得匹配產(chǎn)生較大誤差。本文提出一種改進(jìn)SURF算法，先利用余弦相似度進(jìn)行二次匹配來去除偽特征點(diǎn)，再使用隨機(jī)抽樣一致算法(random sample consensus，RANSAC)進(jìn)一步降低誤匹配率。

1 SURF算法原理

SURF是一種具有高效性和高魯棒性的局部特征描述算法，其不僅對圖像旋轉(zhuǎn)、縮放具有極強(qiáng)的適應(yīng)性，而且圖像環(huán)境在光照變化、視角變化、仿射變換和噪聲的情況下也能保持一定程度的穩(wěn)定性[5]。SURF特征匹配算法可以分為3個(gè)步驟：特征點(diǎn)檢測、構(gòu)建特征描述子和特征點(diǎn)匹配[6]。

1.1 特征點(diǎn)檢測

特征點(diǎn)檢測可分為3步：尺度空間極值點(diǎn)檢測、精確定位極值點(diǎn)、選取特征點(diǎn)主方向。

1.1.1 尺度空間極值點(diǎn)檢測

(1)

由于圖像中的特征點(diǎn)需要具備尺度無關(guān)性，所以先對特征點(diǎn)進(jìn)行高斯濾波消除特征點(diǎn)的相關(guān)性，再進(jìn)行Hessian的計(jì)算。L(x，t)代表不同解析度下的圖像，計(jì)算公式如式(2)、(3)所示。

L(x,t)=G(t)·I(x,t)

(2)

(3)

式中：I(x,t)為圖像函數(shù)。

Herbert Bay提出用近似值代替L(x,t)以達(dá)到簡化計(jì)算的目的，同時(shí)引入權(quán)值帶消除誤差，權(quán)值大小會隨尺度變化而發(fā)生改變，則Hessian矩陣行列式為：

det(Happrox)=LxxLyy-(0.9Lxy)2

(4)

式中：det(Happrox)為像素點(diǎn)的Hessian矩陣行列式；Lxx,Lyy,Lxy為高斯濾波后圖像在各個(gè)方向的二階導(dǎo)數(shù)。

匹配圖像具有不同的空間尺度，圖像金字塔可以將模板圖像求解出多種尺度空間以適應(yīng)匹配要求。傳統(tǒng)的金字塔結(jié)構(gòu)各層待檢測圖片尺寸大小發(fā)生了變化，各子層在運(yùn)算過程中都需要用高斯函數(shù)進(jìn)行平滑處理，降低了運(yùn)算效率，如圖1所示。但在SURF算法中，各個(gè)octave層之間的待檢測圖片尺寸大小是相同的，只改變了濾波器大小。采用這種方法縮短了采樣過程所消耗的時(shí)間，處理速度得到較大提高。

圖1 金字塔結(jié)構(gòu)

1.1.2 精確定位極值點(diǎn)

將Hessian矩陣處理過的每個(gè)像素點(diǎn)與其三維領(lǐng)域的26個(gè)點(diǎn)進(jìn)行對比，如果是極值點(diǎn)則保留，反之剔除，再通過三維線性差值法獲得亞像素級的特征點(diǎn)，并刪除檢測特征點(diǎn)中小于一定閾值的點(diǎn)。

1.1.3 選取特征點(diǎn)主方向

在特征點(diǎn)區(qū)域內(nèi)統(tǒng)計(jì)其haar小波特征，以60°扇形為單位，統(tǒng)計(jì)扇形區(qū)域內(nèi)所有特征點(diǎn)的水平和垂直haar小波特征總和，然后60°扇形以一定間隔進(jìn)行旋轉(zhuǎn)，旋轉(zhuǎn)一周后以小波特征最大的扇形方向作為該特征點(diǎn)的主方向，過程示意圖如圖2所示。

圖2 特征點(diǎn)主方向求取過程

1.2 生成特征描述子

在特征點(diǎn)周圍選取一個(gè)正方形框，邊長為20s(s為該特征點(diǎn)的尺度)，方向?yàn)樘卣鼽c(diǎn)的主方向，然后把該框分成16個(gè)子區(qū)域，每個(gè)子區(qū)域統(tǒng)計(jì)25個(gè)像素的水平和垂直方向的haar小波特征，從而形成四維向量V=[∑dx∑|dx| ∑dy∑|dy|]，歸一化后形成16×4共64維SURF描述算子[8]。其中dx為水平方向haar小波特征；dy為垂直方向haar小波特征；|dx|為水平方向haar小波特征的絕對值；|dy|為垂直方向haar小波特征的絕對值。

1.3 特征點(diǎn)匹配

特征點(diǎn)匹配就是把兩幅圖像中特征點(diǎn)一一對應(yīng)，然后計(jì)算第一幅圖像的每一個(gè)特征描述子向量與第二幅圖像的特征描述子向量的歐氏距離，計(jì)算所得的最小值即認(rèn)為是那個(gè)特征的最佳匹配。

2 匹配算法的改進(jìn)

SURF算法匹配過程中，如果匹配圖像局部點(diǎn)領(lǐng)域信息相近和圖像視角不同，會引起兩個(gè)不同特征點(diǎn)描述符的匹配程度超過同一點(diǎn)的特征描述符匹配程度。因此在匹配的兩幅圖像中如果出現(xiàn)形狀相似區(qū)域，就會產(chǎn)生大量誤匹配。由于歐氏距離沒有考慮各特征描述子向量之間的相關(guān)性，本文進(jìn)行二次匹配，對誤匹配對進(jìn)行消除。

2.1 向量空間余弦相似度匹配

判斷兩個(gè)向量相似程度的準(zhǔn)則一般有兩種：距離測度法和相似性函數(shù)法。距離測度法是根據(jù)向量空間上存在的距離來判斷向量間的差異程度。相似性函數(shù)是用函數(shù)值的大小來表明兩向量間的差異程度。本文在歐式距離測度的基礎(chǔ)上再用余弦相似度作為約束，通過設(shè)定相似性函數(shù)的閾值來去除多余的匹配點(diǎn)對。

余弦相似度測度，即計(jì)算特征點(diǎn)間的相似程度，將向量根據(jù)坐標(biāo)值繪制到向量空間中，求得它們的夾角，并計(jì)算出夾角所對應(yīng)的余弦值，此余弦值就可以用來表征兩個(gè)特征點(diǎn)向量的相似性。余弦值越大，說明兩特征點(diǎn)向量之間的夾角越小，匹配相似度越大。

具體方法：先使用歐氏距離選取初步特征點(diǎn)對，然后再使用余弦相似度函數(shù)進(jìn)一步篩選，如果兩個(gè)向量的余弦值大于閾值K則保留，反之刪除。K可以根據(jù)實(shí)驗(yàn)得到，對于2個(gè)向量a和b，余弦相似度S(a,b)表達(dá)式為:

(5)

使用余弦相似度對產(chǎn)生縮放和旋轉(zhuǎn)、亮度對比度改變、模糊、視角變化的4類圖像進(jìn)行測試，選擇平均閾值K=0.975，測試結(jié)果見表1。

表1 測試結(jié)果

2.2 改進(jìn)的RANSAC算法

RANSAC算法設(shè)立一個(gè)閾值把測量數(shù)據(jù)分為內(nèi)點(diǎn)和外點(diǎn)，其中內(nèi)點(diǎn)數(shù)據(jù)比較準(zhǔn)確，因此利用內(nèi)點(diǎn)數(shù)據(jù)進(jìn)行參數(shù)估計(jì)，以便刪除不準(zhǔn)確的數(shù)據(jù)。此算法需要事先確定3個(gè)量[9]：隨機(jī)采樣次數(shù)、誤差容忍度(內(nèi)外點(diǎn)距離閾值)和一致集的大小(內(nèi)點(diǎn)總數(shù))。

在經(jīng)典的RANSAC算法中，計(jì)算最佳模型參數(shù)是遍歷所有可能的組合，并以誤差最小的一組作為最佳參數(shù)，往往導(dǎo)致計(jì)算量大、運(yùn)行時(shí)間長。本文采用PROSAC(the progressive sample consensus)將余弦相似度匹配的結(jié)果作為排序的依據(jù)，在采樣時(shí)根據(jù)匹配結(jié)果由高到低進(jìn)行排序，如此最有可能導(dǎo)致最佳參數(shù)的采樣會較早出現(xiàn)，從而減少隨機(jī)采樣次數(shù)、提高運(yùn)算效率。

3 實(shí)驗(yàn)結(jié)果與分析

用于實(shí)驗(yàn)的硬件為聯(lián)想ThinkPad E420，其CPU主頻為2.2GHz，內(nèi)存4GB；程序在Visual Studio 2010開發(fā)環(huán)境下編寫。測試用圖為經(jīng)典測試圖像，以正確匹配率作為評價(jià)標(biāo)準(zhǔn)[11]。

(6)

式中：precision為正確率；falsematches為錯(cuò)誤匹配；correctmatches為正確匹配。

使用原SURF算法和改進(jìn)SURF算法分別處理測試圖像，如圖3～6所示，其中(a)為使用SURF算法匹配效果圖，(b)為改進(jìn)SURF匹配效果圖。圖3為旋轉(zhuǎn)45°、尺度增加2倍，圖4為經(jīng)過模糊變化，圖5為亮度有較大改變，圖6為相機(jī)視角發(fā)生變化的。表2是實(shí)驗(yàn)數(shù)據(jù)。

圖3 匹配旋轉(zhuǎn)和縮小圖像

圖4 匹配模糊變化圖像

圖5 匹配亮度變化圖片

圖6 匹配視角變化的圖片

圖像處理方式算法左圖特征點(diǎn)數(shù)量右圖特征點(diǎn)數(shù)量匹配點(diǎn)數(shù)量正確匹配點(diǎn)數(shù)量正確率/%時(shí)間/s旋轉(zhuǎn)和縮放SURF61441061437360.751.13改進(jìn)SURF448224313096.771.31模糊SURF1681011689657.141.02改進(jìn)SURF131621919100.001.24亮度SURF127881277861.411.14改進(jìn)SURF105664242100.001.36視角SURF32732232720863.611.21改進(jìn)SURF225230171694.111.32

從表2可知，改進(jìn)SURF算法與原SURF算法相比，改進(jìn)算法在不同條件下的圖像匹配正確率都有顯著提高，誤匹配率平均降低37%，匹配時(shí)間比SURF算法增加0.1～0.2s。使用余弦相似度進(jìn)行二次匹配，需要選取的特征點(diǎn)平均減少20%～30%，說明本文算法穩(wěn)定可靠，對圖像產(chǎn)生旋轉(zhuǎn)、縮放、模糊、亮度和視角變化等情況都有較強(qiáng)的適應(yīng)性。

使用SURF和本文算法對隨機(jī)拍攝的一幅照片進(jìn)行匹配，余弦相似度閾值K=0.975，人工對匹配結(jié)果進(jìn)行校驗(yàn)，發(fā)現(xiàn)誤匹配對為0對，匹配正確率為100.00%，所用時(shí)間比SURF多0.12s，在可接受的范圍之內(nèi)，如圖7所示。

圖7 匹配實(shí)驗(yàn)圖片

4 結(jié)束語

本文在用SURF算法提取特征點(diǎn)的基礎(chǔ)上結(jié)合余弦相似度進(jìn)行進(jìn)一步提取，很好地解決了SURF算法匹配中沒有考慮特征點(diǎn)空間位置關(guān)系從而導(dǎo)致誤匹配率高的問題。本文提出的方法可以在保證正確率的基礎(chǔ)上對圖像的旋轉(zhuǎn)、縮放、模糊、亮度變化和視角變化具有較強(qiáng)的魯棒性，匹配正確率較高。但是由于旋轉(zhuǎn)和視角變化易使相近特征點(diǎn)方向一致，導(dǎo)致余弦相似度進(jìn)行二次匹配對誤匹配點(diǎn)去除不完全，還需要做進(jìn)一步的研究。