陳 虹，肖 越，肖成龍，宋 好

(遼寧工程技術(shù)大學(xué)軟件學(xué)院，遼寧葫蘆島125105)

(*通信作者電子郵箱1150996133@qq．com)

0 引言

近年來，隨著計(jì)算機(jī)視覺領(lǐng)域的飛速發(fā)展，圖像匹配技術(shù)逐漸引起各界的廣泛關(guān)注。目前已在多個(gè)領(lǐng)域得到大量研究及應(yīng)用，如工件識(shí)別［1］、醫(yī)學(xué)診斷［2］、計(jì)算機(jī)視覺［3］、自動(dòng)跟蹤定位［4－5］、人臉識(shí)別［6－7］、圖像三維重建［8］等。

圖像匹配指兩幅圖像間的映射關(guān)系，即具有相同中心事物不同視點(diǎn)的兩幅圖像，將彼此在空間中同一位置的點(diǎn)聯(lián)系起來的過程。在實(shí)際操作中，待匹配的圖像往往獲取自不同環(huán)境，在尺度、亮暗、視角、噪聲等方面存在差異，因此給圖像匹配技術(shù)帶來了難度。從方法上來說，目前主要的圖像匹配方式分為基于灰度匹配的方法、基于特征提取的匹配方法兩類?；诨叶绕ヅ涞姆椒?，例如序貫相似性檢測(cè)(Sequential Similarity Detection Algorithm，SSDA)、去均值歸一化互相關(guān)法NNPROD(average-removed normalized cross-correlation)等，基于灰度的匹配對(duì)圖像尺度、旋轉(zhuǎn)、亮暗、視角等變換較敏感。相比之下，基于特征提取的方法具有良好的尺度不變性。常見特征提取算法有尺度不變特征變換(Scale Invariant Feature Transform，SIFT)［9］、角點(diǎn)提取 Harris［10］、SURF(Speeded Up Robust Feature)［11－12］等。文獻(xiàn)［4］和文獻(xiàn)［12］通過對(duì)幾種代表性的局部特征進(jìn)行多項(xiàng)實(shí)驗(yàn)評(píng)估，結(jié)論顯示SIFT算法的魯棒性最佳。

文獻(xiàn)［13］將SIFT特征描述子結(jié)合全局信息，以達(dá)到降低誤匹配的目的，但計(jì)算量大，由于范圍固定的全局信息描述，導(dǎo)致計(jì)算結(jié)果受尺度變化影響較大。文獻(xiàn)［14］中提出通過差值運(yùn)算將128維特征向量轉(zhuǎn)化為128維二值特征描述子，達(dá)到降維和提升運(yùn)算速度的目的，但同時(shí)降低了匹配正確率。Zhou等［15］將SIFT中128維特征描述子轉(zhuǎn)化為256維緊湊的二值特征描述子，在匹配速度上稍有提升，但仍以降低匹配正確率為代價(jià)。以上文獻(xiàn)都在如何降低誤匹配、提升運(yùn)算速度等方面進(jìn)行了深入的探索，但不可避免地在提升運(yùn)算速度過程中降低了匹配正確率。另外，文獻(xiàn)［16］指出SIFT算法選用單一的歐氏距離比的測(cè)度方法，導(dǎo)致SIFT算法在原圖像和目標(biāo)圖像相似區(qū)域較多的情況下，會(huì)出現(xiàn)明顯的錯(cuò)配和亂配的情況。

針對(duì)以上問題，本文提出一種基于SIFT算子融合最大相異系數(shù)的圖像匹配算法。綜合考慮，由于算法復(fù)雜度高導(dǎo)致效率降低、特征描述子降維運(yùn)算導(dǎo)致的匹配正確率損失、圖像相似區(qū)域較多導(dǎo)致錯(cuò)配亂配等問題，將特征向量相似性程度測(cè)量運(yùn)算融合于SIFT圖像匹配中，在可以承受的時(shí)間范圍內(nèi)，盡可能提升匹配正確率，同時(shí)不會(huì)過多地增加算法復(fù)雜度，并解決相似區(qū)域易出現(xiàn)錯(cuò)配亂配問題。

1 相關(guān)工作

1．1 SIFT算法基本原理

尺度不變特征變換(SIFT)［9］是由哥倫比亞大學(xué)的Lowe提出的，用于提取圖像局部特征描述子，該算法對(duì)于圖像的平移、旋轉(zhuǎn)、仿射變換等情況均具有良好的穩(wěn)定性與匹配能力，其基本思想是在尺度空間中提取位置、尺度和旋轉(zhuǎn)無關(guān)量。具體做法是根據(jù)尺度空間概念構(gòu)建尺度空間，在尺度空間中尋找局部極值點(diǎn)，將局部極值點(diǎn)中的低響應(yīng)點(diǎn)與邊緣響應(yīng)點(diǎn)剔除，確定關(guān)鍵點(diǎn)的主方向，生成關(guān)鍵點(diǎn)的描述子，最后進(jìn)行特征點(diǎn)的匹配。

SIFT圖像匹配算法主要包括3個(gè)步驟:

步驟1 特征點(diǎn)檢測(cè)。特征點(diǎn)檢測(cè)分為尺度空間極值檢測(cè)、關(guān)鍵點(diǎn)定位、關(guān)鍵點(diǎn)方向分配三步。

尺度空間極值檢測(cè) 不同尺度空間下的空間表示L(x，y，σ)，可由二維圖像 I(x，y) 與高斯核 G(x，y，σ) 的卷積得到，σ為空間尺度因子。

利用高斯差分(Difference of Gaussian，DoG)近似高斯拉普拉斯(Laplace of Gaussian，LoG)在構(gòu)造的尺度空間中搜索穩(wěn)定的關(guān)鍵點(diǎn):

由此得到高斯金字塔，通過相鄰尺度圖像相減生成DoG金字塔并形成尺度空間。尺度空間中，如果一個(gè)點(diǎn)同周圍8個(gè)點(diǎn)以及相鄰上下層中2×9=18個(gè)點(diǎn)共26個(gè)點(diǎn)進(jìn)行比較，該點(diǎn)均為最大或最小，該點(diǎn)即為局部極值點(diǎn)。

關(guān)鍵點(diǎn)定位 由于DoG值對(duì)噪聲和邊緣響應(yīng)較敏感，因此DoG尺度空間中檢測(cè)到的極值點(diǎn)中包含較多低響應(yīng)點(diǎn)，關(guān)鍵點(diǎn)需要進(jìn)一步精確定位。利用Hessian矩陣計(jì)算主曲率設(shè)置閾值的方法，剔除邊緣響應(yīng)點(diǎn)。

關(guān)鍵點(diǎn)方向分配 根據(jù)關(guān)鍵點(diǎn)附近鄰域的梯度方向分布信息，為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)，梯度值的m(x，y)和θ(x，y)的計(jì)算如式(4)和式(5)所示:

其中:L為關(guān)鍵點(diǎn)所在的尺度空間值，m(x，y)是梯度的模值，θ(x，y) 表示點(diǎn) (x，y) 處的方向值。

步驟2 特征點(diǎn)生成。實(shí)際計(jì)算過程中，以每個(gè)關(guān)鍵點(diǎn)為中心取16×16像素窗口，并在每個(gè)窗口中取4×4像素種子點(diǎn)來描述，每個(gè)種子點(diǎn)方向由8個(gè)方向梯度累加，故單個(gè)關(guān)鍵點(diǎn)就形成了128維的描述特征向量。

步驟3 特征點(diǎn)匹配。生成SIFT特征描述符向量后，采用最近鄰(Nearest Neighbor，NN)算法［9］進(jìn)行特征點(diǎn)匹配，當(dāng)查詢樣本與目標(biāo)樣本最近鄰特征點(diǎn)歐氏距離與次近鄰特征點(diǎn)歐氏距離比值小于某一閾值時(shí)，認(rèn)為該特征點(diǎn)對(duì)匹配成功，否則匹配失敗。根據(jù)Lowe的實(shí)驗(yàn)，閾值設(shè)定為0．8。

1．2 研究現(xiàn)狀

針對(duì)傳統(tǒng)SIFT算法的改進(jìn)研究已進(jìn)行了多年，改進(jìn)算法層出不窮。主要改進(jìn)方法包括以下幾方面:融合其他經(jīng)典圖像匹配算法優(yōu)勢(shì)的改進(jìn)、融合多方法的SIFT特征降維改進(jìn)、基于特征點(diǎn)匹配方式的改進(jìn)、增加精確匹配篩選等。文獻(xiàn)［17］中提出將角點(diǎn)檢測(cè)(Harris)的閾值準(zhǔn)則與SIFT特征提取過程融合，對(duì)基于SIFT提取的尺度不變特征進(jìn)行再次篩選，從而得到穩(wěn)定性佳、可區(qū)分性強(qiáng)的特征點(diǎn);傅衛(wèi)平等［1］利用多分辨率小波變換(multiscale wavelet transform)，構(gòu)建低頻信息參與匹配，將特征向量降維到32維，并利用積分圖像進(jìn)行精確匹配篩選;文獻(xiàn)［18］采用分級(jí)放射狀分區(qū)的方法，同樣達(dá)到降維目的，并提出運(yùn)用馬氏距離(Mahalanobis distance)雙向匹配方法取代原SIFT算法中歐氏距離匹配方法。本文分析當(dāng)前研究現(xiàn)狀得出，基于原SIFT匹配效果并不理想，增加精確匹配篩選是必要的，并利用在特征點(diǎn)匹配階段融合有效方法，對(duì)特征點(diǎn)匹配方法進(jìn)行改進(jìn)，能夠達(dá)到提升特征點(diǎn)匹配效率、有效降低誤匹配的目的。

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

SIFT算法進(jìn)行相似區(qū)域較多的圖像匹配時(shí)，某些點(diǎn)的鄰域信息非常相近，便會(huì)出現(xiàn)很明顯的錯(cuò)配和亂配現(xiàn)象。為保證圖像匹配的準(zhǔn)確性，需通過有效手段剔除誤配點(diǎn)對(duì)。文獻(xiàn)［19］中提到一般向量的相似性函數(shù)測(cè)度方法，故提出在歐氏距離比約束基礎(chǔ)上，增加向量相似性約束提升匹配率。

2．1 最大相異系數(shù)

原SIFT算法中采用與樣本圖像最近鄰特征點(diǎn)歐氏距離與次近鄰特征點(diǎn)歐氏距離比值小于0．8來提取匹配點(diǎn)，但并未考慮特征向量間的相關(guān)性，單一的向量分量可能會(huì)影響結(jié)果的準(zhǔn)確性。

衡量?jī)蓚€(gè)向量間的相似性方法有距離測(cè)度法和相似性函數(shù)法［19］。歐氏距離是最常見的距離測(cè)度法，通過衡量向量空間距離來表示向量間相似程度，距離越近向量越相似;相似性函數(shù)法通過函數(shù)的方法來表征向量間的相似程度，最大相異系數(shù)是相似性函數(shù)法中的一種，適用于比較未知向量與已知向量間的相似性。故在距離測(cè)度基礎(chǔ)上，增加空間向量相似性約束，通過自適應(yīng)估計(jì)每組匹配圖像的最大相異系數(shù)，高于最優(yōu)取值的匹配視作誤匹配，以此降低誤匹配個(gè)數(shù)。

具體做法:在對(duì)應(yīng)目標(biāo)圖像與查詢圖像間的某組特征描述符向量歐氏距離比小于0．8基礎(chǔ)上，進(jìn)一步計(jì)算兩描述符向量的最大相異系數(shù)Zy［19］，最大相異系數(shù) Zy取值范圍［0，∞)，Zy取值越小兩向量越接近，Zy=0兩向量完全相同。最大相異系數(shù)法通過加權(quán)平均過程，突出了差異較大元素對(duì)判決的影響力，而差異較小的元素則并不在判決中起到實(shí)質(zhì)作用。x和y分別代表未知待比較向量與已知確定向量，如式(6)計(jì)算兩向量的相對(duì)誤差向量λ，將向量λ中各分量進(jìn)行從大到小排列重組為:λ ={λi＞ λj，i≤j}，取出λ的前k個(gè)值得到ξ ={λ1，λ2，λ3，…，λk};最后，對(duì)ξ 向量進(jìn)行加權(quán)平均得到最大相異系數(shù)Zy。

通過分析式(7)，計(jì)算128維特征描述符向量的最大相異系數(shù)需要確定符合計(jì)算要求的k值。既要保證選定的k值計(jì)算出的數(shù)值穩(wěn)定，又要保證k值對(duì)應(yīng)的最大相異系數(shù)足夠小，故選用繪制k-Zy圖像來分析最優(yōu)k值選取問題。根據(jù)Zy數(shù)值越小向量越接近原則，從圖中得出Zy數(shù)值最小值穩(wěn)定在k=125處，如圖1所示。通過分析k-Zy關(guān)系圖像發(fā)現(xiàn)，Zy在k=126處出現(xiàn)明顯躍升，k=125處取到曲線最小值。

圖1 最大相異系數(shù)隨k變化Fig．1 Change of Zywith k

2．2 最優(yōu)最大相異系數(shù)自適應(yīng)估計(jì)

待匹配的每組圖像各不相同，形成的向量集也就不同。由此提出對(duì)于每組匹配圖像進(jìn)行最優(yōu)最大相異系數(shù)自適應(yīng)估計(jì)，利用最優(yōu)Zy約束初篩匹配點(diǎn)集，進(jìn)一步剔除誤匹配點(diǎn)。

為了檢驗(yàn)實(shí)驗(yàn)結(jié)果的正確性，需要引入匹配正確率的概念。利用隨機(jī)抽樣一致性算法(Random Sample Consensus，RANSAC)計(jì)算出圖像匹配過程中的“內(nèi)點(diǎn)”和“外點(diǎn)”，從而得出正確的匹配率。通過RANSAC算法優(yōu)化得到正確的匹配點(diǎn)數(shù)目記作N1，誤匹配點(diǎn)數(shù)目記作N2，匹配正確率P計(jì)算公式如式(8)［20］所示:

在執(zhí)行RANSAC優(yōu)化算法之前，先根據(jù)Lowe推薦的0．8歐氏距離比篩選根據(jù)最近鄰距離算法(NN)［9］得到的匹配點(diǎn)集，獲取初篩匹配點(diǎn)集 Si，并在 Zy∈［0．2，1．0］范圍內(nèi)自適應(yīng)估計(jì)最優(yōu)最大相異系數(shù)Zb，從Si匹配點(diǎn)集中選取滿足特征點(diǎn)間最大相異系數(shù)值Zy＜Zb條件的匹配，如滿足便記作符合最優(yōu)匹配條件，具體做法如下:

步驟 1 取 Zy∈［0．2，1．0］，以0．01 為步長(zhǎng)，嘗試根據(jù)每個(gè)Zy來篩選Si中所有匹配點(diǎn)，并獲取篩選后匹配點(diǎn)集Sf，Sf滿足其中每組特征描述符向量的最大相異系數(shù)均小于等于Zy。

步驟2 對(duì)獲取的Sf執(zhí)行RANSAC優(yōu)化算法，根據(jù)優(yōu)化結(jié)果得到正確匹配點(diǎn)數(shù)目N1，計(jì)算匹配正確率P。

步驟3 將 Zy∈［0．2，1．0］，以0．01為步長(zhǎng)的80 個(gè)取值全部整合，繪制Zy-P，Zy-N1，Zy-Ms(N1×P)關(guān)系圖像如圖2所示(為在同一坐標(biāo)系中顯示，將P×500顯示)，由圖2整合曲線圖可知，隨Zy取值的不斷變化，Ms的取值逐步增大。

圖2 Zy-Ms圖像Fig．2 Diagram of Zy-Ms

步驟4 利用三分法分析Zy-Ms折線圖，獲得最優(yōu)Zy取值Zb，設(shè)置相鄰Ms計(jì)算差值小于1×10－5時(shí)，停止進(jìn)一步精確取值操作。Ms取得穩(wěn)定最大值對(duì)應(yīng)的Zy值，作為最大相異系數(shù)最優(yōu)值。

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

3．1 實(shí)驗(yàn)用圖

實(shí)驗(yàn)平臺(tái)為 Windows 7操作系統(tǒng)、CPU 2．50 GHz、內(nèi)存4 GB的PC機(jī)，編譯環(huán)境為 python2．7．5，并加入了開源庫(kù)OpenCV。本實(shí)驗(yàn)采用Daniel Scharstein和Richard Szeliski立體匹配實(shí)驗(yàn)所用的圖像［21］，選用 venus、sawtooth、map、poster四組圖像。

其中每組圖像均來自于一段三維立體動(dòng)圖，圖像在亮暗、視角、尺度等方面均存在變化，由于保持中心事物不變，導(dǎo)致目標(biāo)圖像與查詢圖像存在大量相似區(qū)域?；谝陨咸匦?，選用該立體匹配圖像組能有效檢驗(yàn)算法在相似區(qū)域較多情況下的匹配能力。本次實(shí)驗(yàn)從每組立體圖像中選取兩張圖像，一張作為目標(biāo)圖像img_train，一張作為查詢圖像img_query，在查詢圖像中尋找對(duì)應(yīng)目標(biāo)圖像的匹配，如圖3所示。

3．2 最佳最大相異系數(shù)求解實(shí)驗(yàn)

針對(duì)2．2節(jié)介紹的最優(yōu)最大相異系數(shù)求解方法，本文對(duì)venus、sawtooth、bull、poster四組圖像分別進(jìn)行實(shí)驗(yàn)，求出符合每組圖像的最大相異系數(shù)最優(yōu)取值。匹配過程從查詢圖像到目標(biāo)圖像，在進(jìn)行RANSAC算法優(yōu)化時(shí)，理論上至少含有7個(gè)點(diǎn)才可計(jì)算基礎(chǔ)矩陣，Zy取值應(yīng)保證RANSAC優(yōu)化算法基礎(chǔ)矩陣的計(jì)算生成，由此本實(shí)驗(yàn)過程中設(shè)定備選Zy最小值為 0．2，最大值為 1．0。

根據(jù)改進(jìn)算法，計(jì)算篩選后特征點(diǎn)集的匹配點(diǎn)數(shù)、正確匹配點(diǎn)數(shù)、匹配正確率，并與原SIFT算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明單次匹配平均時(shí)間在1．236 s左右，保證高準(zhǔn)確率的前提下匹配用時(shí)可以接受，匹配率方面提升10個(gè)百分點(diǎn)左右。實(shí)驗(yàn)結(jié)果如表1所示，篩選后總體點(diǎn)數(shù)下降，獲取RANSAC優(yōu)化后提取的正確匹配點(diǎn)數(shù)卻上升。證明最大相異系數(shù)對(duì)特征向量相似性篩選，在除去誤匹配方面確實(shí)起到了一定作用。

圖3 實(shí)驗(yàn)用圖Fig．3 Image in experiment

表1 四組圖像的最優(yōu)Zy求值結(jié)果Tab．1 Optimal Zyof four sets of images

3．3 相關(guān)算法比對(duì)分析

本文算法(算法1)思路來自計(jì)算向量間最大相異系數(shù)，衡量向量間的相似性程度，確定特征點(diǎn)是否匹配。文獻(xiàn)［16］(算法2)中提出了一種歐氏距離測(cè)度與余弦相似度相結(jié)合的匹配提取算法，將特征方向的一致性作為圖像匹配約束;文獻(xiàn)［20］(算法3)中提出通過自適應(yīng)獲取最優(yōu)歐氏距離比閾值，并通過雙向匹配剔除誤匹配點(diǎn)。以上所提兩種算法，其根本思路均是基于對(duì)SIFT特征描述子的操作，算法2將余弦相似度融合SIFT算子，從空間上約束特征點(diǎn)匹配;算法3通過對(duì)SIFT特征描述子的處理，獲取最大匹配點(diǎn)數(shù)，并通過擬合曲線的交點(diǎn)得到最優(yōu)ratio取值。相比其他經(jīng)典算法，上述兩種算法從算法設(shè)計(jì)角度看，與算法1出發(fā)點(diǎn)是相同的，更具有可比性。將上述算法，從匹配正確率、匹配點(diǎn)數(shù)、正確匹配點(diǎn)數(shù)、算法耗時(shí)幾方面進(jìn)行綜合比較。算法比對(duì)結(jié)果如表2所示。從表2分析可知，本文算法較其余兩種算法，在匹配正確率方面表現(xiàn)良好，針對(duì)不同組測(cè)試圖像均能提取較多正確匹配。但從venus組圖像數(shù)據(jù)看，算法3匹配正確率較低，但提取出更多正確匹配點(diǎn)數(shù)。在算法耗時(shí)上，算法2耗時(shí)最少，本文算法耗時(shí)較算法2稍有增多，但明顯少于算法3。

表2 算法性能比對(duì)結(jié)果Tab．2 Comparison results of algorithms performance

綜合分析，本文算法較好地提升了匹配正確率，獲取了更多的正確匹配點(diǎn)數(shù)，同時(shí)算法耗時(shí)適中，有效改進(jìn)了相似區(qū)域較多情況下的錯(cuò)配亂配問題，降低了誤匹配率。缺點(diǎn)是在剔除誤匹配的過程中，針對(duì)不同圖像也有不同程度上正確匹配點(diǎn)數(shù)的損失。經(jīng)過對(duì)比分析，本文算法整體表現(xiàn)良好，實(shí)驗(yàn)結(jié)果基本滿足最初算法設(shè)計(jì)目的。

如圖4所示，對(duì)比優(yōu)化前后的匹配圖像，大部分雜亂的誤匹配已被優(yōu)化算法成功剔除。

圖4 優(yōu)化前后匹配圖像對(duì)比Fig．4 Matched image comparison before and after optimization

4 結(jié)語

本文在基于SIFT特征算子的基礎(chǔ)上，提出融合最大相異系數(shù)的自適應(yīng)匹配算法。在單一的歐氏距離比基礎(chǔ)上，添加向量相似性約束，將未知向量與已知向量比較過程中相似度測(cè)量考慮在內(nèi)，對(duì)于相似區(qū)域較多容易出現(xiàn)錯(cuò)配或亂配的情況進(jìn)行了相應(yīng)優(yōu)化。本文所述方法可獲得較多的匹配點(diǎn)，并提升了正確匹配率。在實(shí)時(shí)性要求不高的系統(tǒng)中，利用本文方法可以保證良好的匹配正確率，剔除誤匹配點(diǎn)。