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

1 改進(jìn)的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)為反射率.通過對(duì)式(1)進(jìn)行微分和二次微分處理可得

(2)

(3)

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

(4)

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

(5)

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

(6)

1.2 SURF特征點(diǎn)檢測(cè)

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

(7)

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

(8)

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

1.3 SURF改進(jìn)預(yù)處理

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

(9)

2 Delaunay三角剖分與匹配

2.1 Delaunay三角剖分

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

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

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

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

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

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

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

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

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

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

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

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

(10)

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

I=(Ia+Ib+Ic)/3

(11)

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

2.4 射影不變量精匹配

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

(12)

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

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

2.5 改進(jìn)匹配算法流程

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

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

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

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

3.1 算法魯棒性分析

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

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

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

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

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

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

3.2 計(jì)算代價(jià)分析

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

圖3 五種方法計(jì)算時(shí)間Fig.3 Calculation time of five algorithms

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

4 結(jié) 論

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