雷 鳴, 劉傳才

?

改進的基于深度卷積網(wǎng)的圖像匹配算法①

雷 鳴, 劉傳才

(南京理工大學計算機科學與工程學院, 南京 210094)

鑒于圖像匹配中單一特征難以獲得理想效果的問題, 提出一種改進的基于深度卷積網(wǎng)的圖像匹配算法.首先對卷積層作展開, 利用BLAS(Basic Linear Algebra Subprograms)高效地計算矩陣乘法, 從而提高了算法運行速度; 然后通過基于POEM(Pattern of Oriented Edge Magnitudes)特征的匹配點篩選方法, 去除部分誤匹配點, 增強了基礎矩陣的魯棒性. 實際圖像的實驗驗證了改進算法的準確性和實時性, 對于重復紋理及旋轉圖像的匹配效果顯著.

圖像匹配; 梯度信息; 深度卷積網(wǎng)絡; BLAS; POEM特征

圖像匹配是圖像分析和處理的重要內容, 是實現(xiàn)計算機視覺研究的重要環(huán)節(jié). 在實際的應用中, 待匹配的圖像常常存在視角、亮度、平移、噪聲、旋轉等差異, 這給圖像的匹配帶來了巨大挑戰(zhàn). 按照匹配模式分類, 通常分為基于圖像區(qū)域匹配(又稱為基于模板匹配)和基于圖像特征匹配[1], 并以此拓展出多種算法, 目前基于局部特征的圖像匹配算法應用度較高, 然而各類算法之間也都存在一定的缺陷.

在諸多基于局部特征的匹配算法中, SIFT[2](尺度不變特征變換)、SURF[3](加速穩(wěn)健特征)、HOG(方向梯度直方圖)都是應用比較廣泛的局部特征描述子. SIFT和SURF這類描述子都具有旋轉和光照不變性,可在圖像中檢測出關鍵點, 但是其描述子構成復雜度較高, 計算量較大. HOG[4]特征構成較為簡單, 最初由Dalal在2005年的CVPR提出, 現(xiàn)已經(jīng)被廣泛用于圖像匹配、人臉識別等技術, 并獲得了極大成功. HOG描述子保持了幾何和光學轉化不變性, 但是在處理圖像旋轉和尺度變化上效果不佳. 針對該缺陷, Ngoc-Son Vu等人提出對HOG特征加入梯度幅值和邊緣方向分布信息的POEM[5](基于方向的邊緣振幅模式), 豐富了HOG的特征描述, 能夠較好地解決具有旋轉變化的圖像匹配問題, 同時POEM計算簡單, 存取空間較小, 計算效率比較出色. 隨著深度卷積網(wǎng)絡的提出, Jerome Revaud等人提出一種基于深度卷積網(wǎng)絡的圖像匹配算法[6](下簡稱DM), 對待測圖像提取梯度信息, 放入深度卷積網(wǎng)絡進行特征點相似度計算, 根據(jù)相似度得到稠密匹配對, 該算法正確率較高, 但是計算量較大, 并且在運算過程中沒有很好利用中間層信息, 可能存在一些特征信息的丟失或偏移. 為了提高算法的魯棒性和實時性, 針對算法中可能存在的誤匹配和算法速度較慢的問題, 提出了一種改進的深度卷積網(wǎng)圖像匹配算法, 提高了圖像匹配準確率, 加快了算法運行速度.

1 梯度特征的提取

HOG全稱為梯度方向直方圖, 該技術將圖像局部出現(xiàn)的方向梯度次數(shù)進行計數(shù). 其依據(jù)的原理是局部物體外形能被光強梯度或邊緣方向的分布所描述, 由于是對梯度信息的處理, 所以該算子能保持較好的幾何和光學不變形, 因此本文采用HOG作為算法的輸入特征. 具體提取步驟如下:

(1) 進行圖像的預處理(去除圖像壓縮噪聲).

(2) 采用Gamma校正法進行顏色空間的標準化(降低圖像局部陰影和光照變化的影響).

(3) 計算圖像每個像素的梯度, 梯度的計算公式:

(2)

式(1)和(2)中,dd分別表示方向和方向的一階差分值, 式(1)表示像素的梯度幅值, 式(2)表示像素的梯度方向.

(4) 計算每個像素的梯度方向直方圖.

2 加速深度卷積匹配

在深度卷積網(wǎng)絡結構中, 卷積層計算復雜度較高, 為了加快算法處理速度, 降低卷積計算的消耗時間, 本算法通過卷積技術對輸入數(shù)據(jù)進行展開, 應用BLAS實施矩陣乘法, 得到加速的深度卷積網(wǎng)絡結構(如圖1所示), 并最終輸出一個初始匹配點集, 下面結合算法結構對算法各環(huán)節(jié)作簡單闡述:

2.1 自底向上獲取區(qū)分度最大化的特征圖

算法結構的各模塊作用描述如下(以邊長大小為4的卷積核作為輸入進行舉例):

2) 卷積: 對任意p∈{2,6,…W-2}×{2,6,…H-2}, 對與做卷積:

由于卷積層運算十分耗時, 因此很有必要對卷積層計算進行優(yōu)化, 提高算法的運算速度. 針對本文計算輸入數(shù)據(jù)卷積, 無法直接用矩陣乘法實現(xiàn)的問題, 本文基于卷積展開技術[7]對輸入數(shù)據(jù)進行展開, 并使用BLAS矩陣運算庫實現(xiàn)具體操作, 有效提高了運算速度.

3) 非線性校正: 卷積的結果通過一個非線性函數(shù)處理, 調整映射結果范圍, 最大程度保留處理后的特征.

4) 降采樣和池化: 本文中通過一個步長為2, 邊長為3×3的最大池化操作實現(xiàn)池化和降采樣. 最大池化有3個具體效果:

第一, 通過最大池化我們能使池化后的結果獲得最大相似度, 即滿足公式(4)的需求:

第二, 將底層的特征向上層傳播, 特征具有平移不變性;

第三, 達到了降采樣目的, 降低了輸出特征維數(shù).

圖2 網(wǎng)格中心漂移

2.2 自頂向下獲取待匹配圖像之間的響應點集:

3 匹配點篩選

在第2節(jié)算法2步驟3獲得的匹配點集中, 可能存在非匹配對因在卷積網(wǎng)絡傳播過程中發(fā)生偏移產(chǎn)生誤配, 針對該問題, 本文通過計算匹配點POEM特征的相似度, 限定相似度篩選匹配點集, 再通過RANSAC算法進一步去除誤匹配.

3.1 基于匹配點集POEM特征的提純

一幅圖像的POEM特征提取過程[8]如圖3所示.

圖3 POEM特征提取過程

主要包括以下步驟:

1) 獲取梯度幅值圖和方向圖;

2) 將梯度方向量化到個區(qū)間內, 圖中=8;

3) 將第個方向的振幅圖劃分成m×m個單元, 將每個單元所有像素點振幅累加, 作為該單元中心點在這個方向振幅圖的特征G(), 將所有個方向的振幅累加值串聯(lián)起來, 形成的向量[G(),G(),…G()], 即為像素點的特征向量;

4) 在像素點上, 對于第個方向, POEM特征的計算公式為:

其中:q是的相鄰像素點;n是編碼所選相鄰像素點的總個數(shù);的定義即是如果>0,()=1,否則()=0. 像素點的POEM特征就是把個方向的POEM值連接起來:

5) 最后再比較以匹配點坐標為中心的m×m塊內POEM特征直方圖的相似度:

表示特征維數(shù)序號, 該值越大表示兩張圖片越相似, 我們設定設定一個閾值, 大于這個閾值的則認為匹配點對符合匹配要求, 否則剔除.

在提取深度卷積匹配算法的輸入特征時, 已經(jīng)對圖像進行梯度提取并計算梯度大小和方向, 因此可以同時對輸入圖像的梯度圖提取POEM特征, 盡管有很多非特征點被提取POEM特征, 但是多線程并行處理仍然有效降低了計算時間.

3.2 利用RANSAC進一步消除誤匹配

RANSAC算法是目前最有效的模型參數(shù)估計算法之一, 被廣泛用于圖像誤匹配的剔除, 其缺點是效率不高, 誤匹配次數(shù)直接影響RANSAC采樣次數(shù). 由于通過深度卷積匹配以及POEM特征篩選所得到的匹配點集已經(jīng)是一個精度較高的匹配結果了, 所以RANSAC能夠迅速收斂并達到剔除錯誤匹配點的要求[9].

本文通過迭代隨機抽取, 找到使匹配點所占比的比例最高的最小點集, 對最小點集和匹配點集一同作非線性優(yōu)化, 得到最終的基本矩陣估計值, 記為W, 最后使用極限約束去除誤匹配[10].

輸入得到的匹配點集, 然后根據(jù)式(8)來剔除:

若滿足式(8)則為匹配點, 否則剔除.

通過上述過程, 去除誤匹配的同時最大程度保留正確匹配點, 得到最終的匹配點集合.

4 算法和實驗

改進的基于深度卷積網(wǎng)的圖像匹配算法IDCNIM (Improved Deep Convolution Network Based Image Matching Algorithm)對輸入、卷積和匹配點的篩選模塊做了三個方面的改進, 其算法流程如下:

算法3: 本文算法IDCNIM 輸入: 兩幅彩色圖像I1、I2. 輸出: 圖像I1、I2的匹配對集合 ①提取圖像I1、I2的灰度圖, 并根據(jù)壓縮格式, 進行高斯平滑處理; ②對圖像I1、I2進行降噪和歸一化處理; ③提取I1、I2的梯度圖T1、T2(含梯度的大小和方向); ④計算T1、T2梯度方向直方圖, 并放入IDCNIM網(wǎng)絡中, 計算得到一個匹配點集, 記作A; ⑤計算圖像I1、I2像素的POEM特征, 此步與第4 步并行進行; ⑥利用匹配點集的POEM特征計算匹配點對的相似度, 根據(jù)設定閾值得到匹配點對B; ⑦利用RANSAC算法, 由集合B得到基本矩陣W; ⑧利用W去除A中的誤匹配, 得到最終結果.

4.1 匹配性能的驗證

為了驗證IDCNIM算法的匹配性能, 我們搭建了相應的實驗環(huán)境: 在Ubuntu 14.04LTS下, 安裝了Eclipse for C++和OpenCV2.4.9, CPU(Intel Core i7-3610QM(8核))的主頻為2.30GHz, 內存為8G.

為了驗證所提算法的有效性, 對IDCNIM算法、深度匹配算法DM[6]、雙向SIFT算法[12]作實驗對比, 并采用recall和1-precision來評價實驗[11]. recall和1-precision分別定義為:

(10)

為了確保實驗的可靠, 限定找出來的匹配點個數(shù)并從中計算各算法產(chǎn)生誤匹配的概率. 對于雙向SIFT通過限定閾值控制匹配點個數(shù), 對于本文中的方法以及深度卷積網(wǎng)絡匹配DM, 隨機選取匹配點對數(shù), 將多次的計算結果取平均值(向上取整)作為算法的誤匹配概率.

4.2 實驗結果分析

匹配實驗效果圖如圖4至圖6.

圖4 存在模糊的測試圖像以及3種方法的匹配結果. (a)測試圖; (b)雙向SIFT算法得到的匹配結果; (c)本文算法得到的匹配結果; (d)DM算法得到的匹配結果.

圖5 存在重復紋理、尺度和旋轉變化的測試圖像. (a)測試圖; (b)雙向SIFT算法得到的匹配結果; (c)本文算法得到的匹配結果; (d)DM算法得到的匹配結果.

圖6 存在視角變換的測試圖像以及3種算法的匹配結果. (a)測試圖; (b)雙向SIFT算法得到的匹配結果; (c)本文算法得到的匹配結果; (d)DM算法得到的匹配結果.

表1 測試圖4匹配結果

表2 測試圖5匹配結果

表3 測試圖6匹配結果

針對圖4(a)所示的測試圖像存在模糊變化, 不存在明顯的位移或者視角的變化, 對比圖4(b)和圖4(c)、圖4(d)可以觀察到, 圖4(c)、圖4(d)的匹配點連接線幾乎都是平行的, 而圖4(b)存在交叉連接線, 是明顯的錯誤匹配, 同時圖4(c)比圖4(b)的連接線明顯減少, 這是匹配點篩選后的結果, 表1的結果驗證: 在圖像出現(xiàn)模糊的情況下, IDCNIM和DM算法都取得了較好的效果. 在匹配精度上, 錯誤率穩(wěn)定在1.6%和2.4%, 而雙向SIFT算法的錯誤率會隨著匹配對數(shù)的增加而出現(xiàn)增長, 這是由于閾值t隨著匹配對數(shù)的增大而增大導致的結果, IDCNIM和DM算法能檢測出的正確匹配對數(shù)的數(shù)量要多于雙向SIFT匹配算法, 而IDCNIM由于進行了匹配點的進一步篩選, 有效剔除了部分錯匹配點, 對比原算法魯棒性更強.

針對圖5(a)所示的測試圖像, 圖像存在重復紋理、旋轉和尺度變化, 這幅測試圖左半邊圖像是右半邊圖像旋轉180度后局部放大的結果, 而右上角區(qū)域未在左半邊圖像中出現(xiàn). 對比圖5(b)、圖5(c)和圖5(d)可以觀察到, 圖5(c)、圖5(d)的匹配點連接線在右上角區(qū)域出現(xiàn)的概率較低, 同時圖5(c)比圖5(d)出現(xiàn)的誤匹配連接線更少. 表2的結果驗證: IDCNIM算法在測試圖5這一類變化的圖像中匹配效果更佳, 隨著匹配對數(shù)的增加, IDCNIM錯誤率穩(wěn)定在7%左右, DM接近13%, 而雙向SIFT隨著匹配對數(shù)的增加而增加, 這是由于IDCNIM算法中POEM特征本身具有一定旋轉不變性以及豐富的紋理特征, 因此在對匹配點篩選后, 有效去除了部分誤匹配, 提高了算法的魯棒性.

針對圖6(a)所示的測試圖像, 圖像存在視角變化, 這幅測試圖最右側的樹木以及天空未出現(xiàn)在左半邊圖像, 對比圖6(b)和圖6(c)、圖6(d)可以觀察到, 圖6(c)、圖6(d)的匹配點連接線在此區(qū)域出現(xiàn)的概率較低, 同時圖6(c)比圖6(d)出現(xiàn)的誤匹配連接線更少. 表3結果驗證: IDCNIM算法和DM算法處理視角變化的圖像時也具有比較穩(wěn)定的匹配表現(xiàn), 隨著數(shù)量的增加, IDCNIM算法和DM算法錯誤率趨于穩(wěn)定, 分別接近于9%和12%, 而雙向SIFT錯誤率逐漸增加, 說明IDCNIM算法和DM算法可以找出更多正確的匹配點對, 同時IDCNIM算法也在DM算法的基礎上去除了部分錯誤的匹配點對, 增強了DM算法的魯棒性.

表4 IDCNIM和DM算法運行時間對比

此外, 由表4可看出, IDCNIM通過卷積展開操作有效降低了卷積運算所需時間, 卷積層運算時間大幅縮短, 比原算法在卷積層運算節(jié)省時間接近55%. 盡管由于特征點篩選處理占用了算法的部分時間, 但是算法總體時間還是較DM有所縮短, 有效提高了算法的實時性.

5 結語

本文提出一種以圖像梯度信息為特征, 通過加速的深度卷積網(wǎng)絡計算各點的相似度, 最后通過各像素點的POEM特征相似度和RANSAC算法實現(xiàn)了匹配點集的篩選. 實驗的結果也顯示, IDCNIM算法的匹配精度和運行速度較原算法都有所提高. 下一步的研究考慮對卷積過程中非最頂層的特征進行融合, 進一步提升匹配精度.

1 Verma P, Shaligram V. A survey: Image matching. International Journal of Digital Application & Contemporary Research, 2015, 4(1): 631–635.

2 Lowe D. Distinctive image feature from scale-invariant keypoints. International Journal of Computer Vision, 2004, 60(2): 91–110.

3 Bay H, Ess A, Tuytelaars T, et al. Speeded-up robust features (SURF). Computer Vision & Image Understanding, 2008, 110(3): 346–359.

4 Dalal N, Triggs B. Histograms of oriented gradients for human detection. IEEE Conference on Computer Vision & Pattern Recognition, 2005, 1(12): 886–893.

5 Ngoc-Son V, Alice C. Enhanced patterns of oriented edge magnitudes for face recognition and image matching. IEEE Trans. on Image Processing, 2012, 21(3): 1352–1365.

6 Revaud J, Weinzaepfel P, Harchaoui Z, et al. Deep convolutional matching. Computer Vision & Pattern Recognition, 2015: 1164–1172.

7 劉進鋒.一種簡潔高效的加速卷積神經(jīng)網(wǎng)絡的方法.計算機技術,2014,14(33):240–243.

8 張祥德,朱和貴,李倩穎,等.基于MBC和POEM特征的人臉識別方法.東北大學學報,2015,36(11):1526–1529.

9 Cao Y, Feng Y, Yang Y, et al. Application of plane estimation algorithm based on RANSAC in volume measurement of object on road surface. Chinese Journal of Sensors & Actuators, 2012, 25(3): 413–416.

10 單小軍,唐娉.圖像匹配中誤匹配點的檢測技術綜述.計算機應用研究,2015,9(9):2561–2565.

11 Davis J, Goadrich M. The relationship between precision- recall and ROC curves. Proc. of the 23rd International Conference on Machine Learning. ACM. 2010, 6. 233–240.

12 李剛,曾榮盛,韓建濤,等.基于雙向SIFT的未標定圖像的立體匹配.全國信號和智能信息處理與應用學術會議, 2010,46(9S):253–257.

Improved Image Matching Algorithm Based on Deep Convolution Network

LEI Ming, LIU Chuan-Cai

(School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China)

In view of the difficulty of obtaining the ideal effect by the single feature in image matching, an improved image matching algorithm based on deep convolution network is proposed. First of all, the algorithm expands the convolution layers, and efficiently computes the matrix multiplication by using the BLAS (Basic Linear Algebra Subprograms) libraries. The algorithm can accelerate the running speed. Then, a screening method of matching points based on the POEM (Pattern of Oriented Edge Magnitudes) feature similarity of feature points is used as well. The method can remove some wrong matching points, make the estimated fundamental matrix more robust and improve the repeating texture and rotational image. The accuracy and instantaneity of the algorithm are proved by the experimental results.

image matching; gradient information; deep convolution network; BLAS; POEM feature

國家自然科學基金(61373063)

2016-04-12;收到修改稿時間:2016-05-30

[10.15888/j.cnki.csa.005548]