改進SURF和Delaunay三角網在圖像匹配中應用*

毛克樂

(新鄉學院 現代教育技術中心， 河南 新鄉 453003)

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

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

1 改進的SURF算法

1.1 顏色不變量模型

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

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

(1)

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

(2)

(3)

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

(4)

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

(5)

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

(6)

1.2 SURF特征點檢測

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

(7)

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

(8)

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

1.3 SURF改進預處理

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

(9)

2 Delaunay三角剖分與匹配

2.1 Delaunay三角剖分

Delaunay三角剖分在代數拓撲學中是一種采用拓撲結構精確衡量離散點集之間幾何關系的一種基本方法[11].本文采用SURF算法優化后獲取的點集作為給定的離散點集，剖分得到Delaunay三角網格結構，并且該結構具有不重疊性和唯一性.Delaunay三角剖分滿足最小角最大準則和空外接圓準則.本文主要由逐點插入法構建Delaunay三角網格，同時采用局部優化提升網格質量、三角形相似函數對三角網格判斷和射影不變量處理三部分引入到Delaunay三角剖分中.

2.2 構建Delaunay三角網格

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

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

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

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

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

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

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

2.3 Delaunay三角形相似函數判斷

Delaunay三角網格中任意兩個對應的三角形相似性可以根據三角形模糊相似度方法進行判斷[15].

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

(10)

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

I=(Ia+Ib+Ic)/3

(11)

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

2.4 射影不變量精匹配

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

(12)

圖1 三角形及其對應三角形Fig.1 Triangles and their counterparts

表1 三角網格處理結果Tab.1 Result of triangular meshing process

2.5 改進匹配算法流程

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

3 實驗和結果分析

本文實驗硬件環境為Intel i3 CPU，6 GB內存，實驗軟件環境為Win10操作系統下Visual-Studio2015+OpenCV2.4.9編程工具，實驗數據為232×223像素的玫瑰花.

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

3.1 算法魯棒性分析

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

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

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

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

表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像素的圖片并分別進行噪聲和旋轉處理構成10組測試數據，測試結果如圖3所示.可以看出文獻[8]因為引入圖像顏色不變量模型導致SURF特征點檢測數過于密集，對于后期Delaunay三角網構建非常困難進而導致計算代價增加.文獻[7]因為沒有考慮圖像顏色不變量信息，因而特征點檢測數量稀疏，計算代價最小，所以時間最快.文獻[16]和文獻[17]均保留了傳統SIFT算法的優點，但文獻[16]沒有考慮SIFT計算代價高這一缺點.本文方法在考慮顏色不變量信息的同時利用鄰近特征點之間的關系解決文獻[8]缺陷，同時既保留了圖像顏色不變量信息，又降低了算法計算代價.由圖3可以看出，本文算法時間與文獻[7]相當.五種方法匹配正確率均值如圖4所示，從整體上看，本文算法匹配正確率最佳，文獻[8，17]效果較本文算法略差，文獻[7，16]效果最差.

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

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

4 結 論

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