雷 鳴, 劉傳才

?

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

雷 鳴, 劉傳才

(南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院, 南京 210094)

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

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

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

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

1 梯度特征的提取

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

(1) 進(jìn)行圖像的預(yù)處理(去除圖像壓縮噪聲).

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

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

(2)

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

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

2 加速深度卷積匹配

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

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

算法結(jié)構(gòu)的各模塊作用描述如下(以邊長(zhǎng)大小為4的卷積核作為輸入進(jìn)行舉例):

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

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

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

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

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

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

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

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

2.2 自頂向下獲取待匹配圖像之間的響應(yīng)點(diǎn)集:

3 匹配點(diǎn)篩選

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

3.1 基于匹配點(diǎn)集POEM特征的提純

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

圖3 POEM特征提取過(guò)程

主要包括以下步驟:

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

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

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

4) 在像素點(diǎn)上, 對(duì)于第個(gè)方向, POEM特征的計(jì)算公式為:

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

5) 最后再比較以匹配點(diǎn)坐標(biāo)為中心的m×m塊內(nèi)POEM特征直方圖的相似度:

表示特征維數(shù)序號(hào), 該值越大表示兩張圖片越相似, 我們?cè)O(shè)定設(shè)定一個(gè)閾值, 大于這個(gè)閾值的則認(rèn)為匹配點(diǎn)對(duì)符合匹配要求, 否則剔除.

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

3.2 利用RANSAC進(jìn)一步消除誤匹配

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

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

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

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

通過(guò)上述過(guò)程, 去除誤匹配的同時(shí)最大程度保留正確匹配點(diǎn), 得到最終的匹配點(diǎn)集合.

4 算法和實(shí)驗(yàn)

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

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

4.1 匹配性能的驗(yàn)證

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

為了驗(yàn)證所提算法的有效性, 對(duì)IDCNIM算法、深度匹配算法DM[6]、雙向SIFT算法[12]作實(shí)驗(yàn)對(duì)比, 并采用recall和1-precision來(lái)評(píng)價(jià)實(shí)驗(yàn)[11]. recall和1-precision分別定義為:

(10)

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

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

匹配實(shí)驗(yàn)效果圖如圖4至圖6.

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

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

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

表1 測(cè)試圖4匹配結(jié)果

表2 測(cè)試圖5匹配結(jié)果

表3 測(cè)試圖6匹配結(jié)果

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

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

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

表4 IDCNIM和DM算法運(yùn)行時(shí)間對(duì)比

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

5 結(jié)語(yǔ)

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

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ìn)鋒.一種簡(jiǎn)潔高效的加速卷積神經(jīng)網(wǎng)絡(luò)的方法.計(jì)算機(jī)技術(shù),2014,14(33):240–243.

8 張祥德,朱和貴,李倩穎,等.基于MBC和POEM特征的人臉識(shí)別方法.東北大學(xué)學(xué)報(bào),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 單小軍,唐娉.圖像匹配中誤匹配點(diǎn)的檢測(cè)技術(shù)綜述.計(jì)算機(jī)應(yīng)用研究,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的未標(biāo)定圖像的立體匹配.全國(guó)信號(hào)和智能信息處理與應(yīng)用學(xué)術(shù)會(huì)議, 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

國(guó)家自然科學(xué)基金(61373063)

2016-04-12;收到修改稿時(shí)間:2016-05-30

[10.15888/j.cnki.csa.005548]