改進SURF和Delaunay三角網(wǎng)在圖像匹配中應(yīng)用*

毛克樂

(新鄉(xiāng)學(xué)院 現(xiàn)代教育技術(shù)中心， 河南 新鄉(xiāng) 453003)

隨著現(xiàn)代科學(xué)技術(shù)的飛速發(fā)展，圖像匹配技術(shù)在當(dāng)代信息處理領(lǐng)域中顯得愈來愈重要.圖像匹配主要針對多個不同傳感器或者不同時段等對同一場景拍攝下來的兩幅圖像，尋找圖像間的共有區(qū)域以確定圖像間的平移旋轉(zhuǎn)關(guān)系，然后進行配準(zhǔn)/匹配的過程.魯棒性、精確性和穩(wěn)定性是衡量圖像匹配算法性能的重要技術(shù)指標(biāo)，如何提高圖像配準(zhǔn)的精度和效率一直都是圖像配準(zhǔn)技術(shù)研究的核心問題.

2006年，Bay等[1]在SIFT(scale invariant feature transform)基礎(chǔ)上提出SURF(speeded up robust feature)算法提取圖像特征點.該算法不僅匹配速度快而且具有更高的穩(wěn)定性和可移植性，相比局部特征的SIFT算法，其速度要快3倍左右[2]，因此，是目前主流匹配方法之一.但是SURF算法在匹配時僅考慮特征向量間的歐氏距離，丟棄了大量數(shù)據(jù)本體的結(jié)構(gòu)信息，當(dāng)圖像噪聲大、相關(guān)信息模糊時，錯誤匹配點數(shù)明顯增大.針對這個問題，文獻[3]提出M估計法對匹配矩陣進行預(yù)估計，但是M估計嚴(yán)重依賴由線性最小二乘估計獲得的初始矩陣，精度和穩(wěn)定性都比較差.文獻[4]提出一種利用Kd樹先把樣本空間劃分后再進行最近鄰查詢法，但是這種方法在構(gòu)建Kd樹索引結(jié)構(gòu)時，計算代價比較高.文獻[5]提出在SURF算法基礎(chǔ)上引入顏色信息來改善SURF算法，在特征點提取時引入圖像顏色信息和圖像全局信息來對特征點進行描述，彌補了SURF的不足，但是匹配效果仍然不理想.文獻[6]提出在SURF的基礎(chǔ)上采用RANSAC對匹配點對進一步提純，RANSAC是一種通過對觀測數(shù)據(jù)進行全局魯棒性參數(shù)估計的方法，但是該方法需要反復(fù)迭代，以獲取最優(yōu)代價函數(shù)模型，因此，計算代價大且結(jié)果可能并非最優(yōu).文獻[7]提出一種利用子塊的三角特征與對角特征的SURF機制和Delaunay三角剖分法的圖像匹配方法，雖然該方法具有良好的魯棒性，但是特征點稀疏導(dǎo)致匹配效果并不理想.文獻[8]提出一種引入顏色不變模型的SURF和Delaunay三角剖分法的圖像匹配法，雖然該方法有效保留了圖像顏色信息，增加了特征點數(shù)量，但是卻忽略了因引入顏色不變模型所帶來的特征點過于密集、錯誤匹配點對增大的影響，大大降低了后續(xù)Delaunay三角剖分的匹配精度與效率.本文提出一種改進的基于SURF和Delaunay三角網(wǎng)格的匹配方法.首先引入顏色不變模型對兩幅圖像進行預(yù)處理，保留圖像顏色信息以彌補SURF特征點檢測不足的影響；其次通過SURF算法提取圖像特征點集，并利用鄰近特征點之間的關(guān)系初步剔除錯誤匹配對，解決特征點過于密集問題；然后對兩幅圖像分別進行Delaunay三角剖分獲得兩幅圖像的Delaunay三角網(wǎng)，通過相似性判斷，根據(jù)經(jīng)驗值選擇相似度大于0.75的三角形對作為候選配準(zhǔn)三角形對；接著通過射影不變量分析剔除錯誤匹配對；最后通過空間變換處理實現(xiàn)兩幅圖像的最終精確匹配.本文方法有效克服了文獻[7-8]的缺陷，具有較強的魯棒性和匹配精度.

1 改進的SURF算法

1.1 顏色不變量模型

Bannert等[9]在Kubelka-Munk理論基礎(chǔ)上提出顏色不變量模型.Kubelka-Munk理論的光度發(fā)射模型為

E(λ，x)=μ(x)(ρf(x)+(1-ρf(x))2R∞(λ，x))

(1)

式中：x為圖像的二維平面位置；μ(x)為位置函數(shù)；λ為波長；ρf(x)為在x處的Fresnel反射系數(shù)；E(λ，x)為光譜反射的成像結(jié)果；R∞(λ，x)為反射率.通過對式(1)進行微分和二次微分處理可得

(2)

(3)

根據(jù)式(2)、(3)可以得到一系列顏色不變量的描述子，即

(4)

式中：Hi為光譜強度為i時的顏色不變量；mx為位置x處時縱坐標(biāo)上的特征點數(shù)；n和m為選取的橫縱坐標(biāo)特征點數(shù).

(5)

本文選擇的顏色不變量描述特征為：Eλy、Eλx、Eλλx、Eλλy、Eλ、Eλλ，根據(jù)式(6)可以求得顏色不變量為

(6)

1.2 SURF特征點檢測

SURF是一種非常優(yōu)秀的局部特征點檢測和描述算法，對圖像的幾何變換、光照等具有很好的不變特性.將上文計算得到的顏色不變量H作為輸入，采用箱式濾波器[10]取代二階高斯微分.通過不斷增大箱式濾波器的窗口大小構(gòu)建不同的圖像尺度空間，并采用積分圖[10]提高計算速度.取空間圖像中任意一個點X(x，y)，尺度為σ，Hessian矩陣H(X，σ)定義為

(7)

det(H)=DxxDyy-(0.9Dxy)2

(8)

差分圖像中得到Hessian矩陣行列式的響應(yīng)圖像后，需要設(shè)置一個閾值，當(dāng)式(8)大于這個值時，對該點對應(yīng)的3×3×3三維空間鄰域內(nèi)的所有點作非極大值抑制處理，將大于臨近26個響應(yīng)值的點作為備選特征點，然后在圖像空間和尺度空間采用線性插值法得到穩(wěn)定特征點的精確位置值.

1.3 SURF改進預(yù)處理

考慮到由于引入顏色不變量模型，雖然保留顏色信息成分，但是同時會導(dǎo)致引入更多的冗余和錯誤匹配對并且會明顯增大后續(xù)Delaunay部分的計算代價.因此，在執(zhí)行Delaunay三角剖分之前先利用鄰近特征點之間的關(guān)系，對SURF檢測到的預(yù)匹配點對進行預(yù)處理，剔除部分冗余和錯誤匹配對，剩下的數(shù)據(jù)作為Delaunay三角剖分的輸入.具體剔除原理為：設(shè)(Pi，Qi)和(P′i，Q′i)是兩幅圖像上的正確匹配點對，則Pi和P′i的距離d(Pi，P′i)應(yīng)該與Qi和Q′i的距離d(Qi，Q′i)相似.根據(jù)這一關(guān)系提出以下評價函數(shù)，即

(9)

2 Delaunay三角剖分與匹配

2.1 Delaunay三角剖分

Delaunay三角剖分在代數(shù)拓?fù)鋵W(xué)中是一種采用拓?fù)浣Y(jié)構(gòu)精確衡量離散點集之間幾何關(guān)系的一種基本方法[11].本文采用SURF算法優(yōu)化后獲取的點集作為給定的離散點集，剖分得到Delaunay三角網(wǎng)格結(jié)構(gòu)，并且該結(jié)構(gòu)具有不重疊性和唯一性.Delaunay三角剖分滿足最小角最大準(zhǔn)則和空外接圓準(zhǔn)則.本文主要由逐點插入法構(gòu)建Delaunay三角網(wǎng)格，同時采用局部優(yōu)化提升網(wǎng)格質(zhì)量、三角形相似函數(shù)對三角網(wǎng)格判斷和射影不變量處理三部分引入到Delaunay三角剖分中.

2.2 構(gòu)建Delaunay三角網(wǎng)格

逐點插入法是Lawson提出的用于構(gòu)建Delaunay的基本方法[12]，具體步驟如下所示：

1) 創(chuàng)建一個涵蓋所有離散點的超大三角形作為初始三角網(wǎng)；

2) 在離散點集中隨機選取一個點，然后在初始三角網(wǎng)中插入該點；

3) 把該點與初始三角網(wǎng)的三個頂點連接，生成三個小三角形；

4) 利用Lawson的LOP優(yōu)化算法，對所有三角形逐個更新[13-14]；

5) 重復(fù)步驟2)～3)，直到插入所有離散點；

6) 刪除包含有初始三角網(wǎng)定點的三角形.

2.3 Delaunay三角形相似函數(shù)判斷

Delaunay三角網(wǎng)格中任意兩個對應(yīng)的三角形相似性可以根據(jù)三角形模糊相似度方法進行判斷[15].

在兩幅圖像上的Delaunay三角網(wǎng)格中隨機取一對相似三角形分別記為△ABC和△A′B′C′，且兩個三角形的三個定點分別依次對應(yīng).取A角值為a，A′角值為a′，則對應(yīng)相似度為

(10)

通過式(10)分別求取該相似三角形對的另外兩對頂點的相似度值Ib、Ic，則這對三角形的相似度為

I=(Ia+Ib+Ic)/3

(11)

通過式(10)、(11)分別計算兩幅圖像中Delaunay網(wǎng)格所有三角形的相似函數(shù)，同時把得到的相似度值寫入一個M×N(M、N分別為兩個Delaunay三角網(wǎng)格中三角形的個數(shù))的相似度矩陣中，并找出相似度大于0.75的三角形對.

2.4 射影不變量精匹配

根據(jù)Delaunay三角網(wǎng)格結(jié)構(gòu)的不重疊性和唯一性可知，在Delaunay三角網(wǎng)格中每個共線相鄰三角形最多有3個，如圖1所示.通過這些不變量剔除SURF預(yù)處理后剩下的錯誤匹配對.選取尺寸為232×223像素的玫瑰花，以點對A和A′為例，若它們滿足式(12)則表示為正確匹配點對，否則為錯誤匹配點對.處理結(jié)果如表1所示.

(12)

圖1 三角形及其對應(yīng)三角形Fig.1 Triangles and their counterparts

表1 三角網(wǎng)格處理結(jié)果Tab.1 Result of triangular meshing process

2.5 改進匹配算法流程

針對傳統(tǒng)SURF算法顏色信息丟失問題引入顏色不變模型，同時利用鄰近特征點之間的關(guān)系克服因顏色不變量模型而導(dǎo)致的錯誤匹配對增加問題，最后利用Delaunay三角剖分法作精確匹配處理，詳細(xì)流程如圖2所示.

3 實驗和結(jié)果分析

本文實驗硬件環(huán)境為Intel i3 CPU，6 GB內(nèi)存，實驗軟件環(huán)境為Win10操作系統(tǒng)下Visual-Studio2015+OpenCV2.4.9編程工具，實驗數(shù)據(jù)為232×223像素的玫瑰花.

圖2 匹配算法流程Fig.2 Flow chart of matching algorithm

3.1 算法魯棒性分析

本文首先通過對測試圖像進行椒鹽噪聲+旋轉(zhuǎn)+尺度變換處理以測試圖像匹配算法的魯棒性能.依次利用文獻[7-8，16-17]以及本文算法進行圖像匹配測試.不同算法的匹配效果如表2所示.從表2中可以看出，本文算法具有更好的魯棒性和匹配效果.

首先分析只加入噪聲處理的五種方法匹配對比效果.表2中，從利用文獻[7]匹配算法處理加入椒鹽噪聲的圖片可以明顯看出存在錯誤匹配對，并且特征點稀疏匹配效果不理想，正確匹配率約為89.5%；文獻[8]匹配算法的匹配結(jié)果看不出明顯的錯誤匹配點對，且檢測的特征點多，分布也比較均勻，匹配結(jié)果符合文獻[8]所述，既保留了圖像的顏色不變量信息，又有效提高了匹配效果，正確匹配率為94.1%，但是其計算代價明顯增加.文獻[16]匹配算法從匹配效果上可以看出特征點數(shù)較文獻[8]明顯減少，正確匹配率達到95.1%，效果良好；文獻[17]的匹配特征點數(shù)最少，匹配效率較文獻[16]有一定提升.從本文算法匹配效果可以看出，匹配效果良好，無明顯錯誤匹配對，正確匹配率為96.2%，略高于文獻[17]，特征點數(shù)介于文獻[16]和文獻[17]之間，分布也比較均勻.表2中的綠色圓點為本文算法相比文獻[8]所剔除的點，既保留了圖像顏色不變量信息，又有效避免了文獻[8]的計算代價缺陷.因此本文算法魯棒性更強.

接著分析五種算法對加入椒鹽噪聲并旋轉(zhuǎn)處理的圖片處理效果.單從圖像匹配結(jié)果上看，五種方法都不存在明顯的錯誤匹配，但是由于文獻[7]方法忽略了圖像顏色不變量信息，導(dǎo)致其特征點數(shù)依然很稀少，文獻[8]檢測到的特征點數(shù)非常豐富且分布均勻，而本文方法所檢測到的特征點數(shù)依然位于兩者之間，效果較兩者都比較好.文獻[16-17]匹配效果和本文相當(dāng).

最后分析五種算法對加入椒鹽噪聲+旋轉(zhuǎn)+尺度變換處理的圖片匹配效果.由表2可以看出，文獻[7-8，16]三種方法匹配效果都存在比較明顯的錯誤匹配對.文獻[17]采用基于梯度角度的直方圖局部特征描述子，雖然有效克服了旋轉(zhuǎn)與尺度變換的影響，但是以犧牲有效特征點為代價，在圖像噪聲大的環(huán)境下效果很差.本文方法在有效剔除錯誤匹配對的同時保留了絕大多數(shù)有效特征點，效果表現(xiàn)良好.表2中五種方法匹配正確率分別如表3所示.正確匹配率隨著加入干擾的復(fù)雜度逐漸降低，雖然對于只加入椒鹽噪聲及椒鹽噪聲+旋轉(zhuǎn)的兩組圖片匹配點對數(shù)變化不大，但是椒鹽噪聲+旋轉(zhuǎn)+尺度變換后，檢測的匹配點對數(shù)明顯減少.因此，干擾越復(fù)雜，匹配點對數(shù)越少，正確匹配點對數(shù)也相應(yīng)變少.

表2 五種算法匹配對比Tab.2 Matching comparison of five algorithms

表3 五種方法針對不同圖像的匹配精度Tab.3 Matching accuracy of different images obtained by five algorithms

3.2 計算代價分析

為了衡量三種算法的計算代價，本文從百度圖庫下載10幅分辨率為232×223像素的圖片并分別進行噪聲和旋轉(zhuǎn)處理構(gòu)成10組測試數(shù)據(jù)，測試結(jié)果如圖3所示.可以看出文獻[8]因為引入圖像顏色不變量模型導(dǎo)致SURF特征點檢測數(shù)過于密集，對于后期Delaunay三角網(wǎng)構(gòu)建非常困難進而導(dǎo)致計算代價增加.文獻[7]因為沒有考慮圖像顏色不變量信息，因而特征點檢測數(shù)量稀疏，計算代價最小，所以時間最快.文獻[16]和文獻[17]均保留了傳統(tǒng)SIFT算法的優(yōu)點，但文獻[16]沒有考慮SIFT計算代價高這一缺點.本文方法在考慮顏色不變量信息的同時利用鄰近特征點之間的關(guān)系解決文獻[8]缺陷，同時既保留了圖像顏色不變量信息，又降低了算法計算代價.由圖3可以看出，本文算法時間與文獻[7]相當(dāng).五種方法匹配正確率均值如圖4所示，從整體上看，本文算法匹配正確率最佳，文獻[8，17]效果較本文算法略差，文獻[7，16]效果最差.

圖3 五種方法計算時間Fig.3 Calculation time of five algorithms

圖4 五種方法匹配正確率Fig.4 Correct matching rate of five algorithms

4 結(jié) 論

本文針對基于SURF+Delaunay三角剖分圖像匹配算法忽略圖像顏色不變量信息以及由于引入顏色不變量模型后特征點過于密集而導(dǎo)致后期Delaunay三角剖分處理困難問題，提出在SURF算法和Delaunay三角剖分算法之間加入利用鄰近特征點之間的關(guān)系解決特征點過于密集問題的方法.兼顧匹配效率與匹配精度，在實際應(yīng)用中具有良好的應(yīng)用效果.后期將進一步研究在原有基礎(chǔ)上加入分區(qū)域處理，探究相鄰區(qū)域之間的臨近特征點關(guān)系.