改进的基于深度卷积网的图像匹配算法①

雷 鸣, 刘传才



改进的基于深度卷积网的图像匹配算法①

雷 鸣, 刘传才

(南京理工大学计算机科学与工程学院, 南京 210094)

鉴于图像匹配中单一特征难以获得理想效果的问题, 提出一种改进的基于深度卷积网的图像匹配算法.首先对卷积层作展开, 利用BLAS(Basic Linear Algebra Subprograms)高效地计算矩阵乘法, 从而提高了算法运行速度; 然后通过基于POEM(Pattern of Oriented Edge Magnitudes)特征的匹配点筛选方法, 去除部分误匹配点, 增强了基础矩阵的鲁棒性. 实际图像的实验验证了改进算法的准确性和实时性, 对于重复纹理及旋转图像的匹配效果显著.

图像匹配; 梯度信息; 深度卷积网络; BLAS; POEM特征

图像匹配是图像分析和处理的重要内容, 是实现计算机视觉研究的重要环节. 在实际的应用中, 待匹配的图像常常存在视角、亮度、平移、噪声、旋转等差异, 这给图像的匹配带来了巨大挑战. 按照匹配模式分类, 通常分为基于图像区域匹配(又称为基于模板匹配)和基于图像特征匹配[1], 并以此拓展出多种算法, 目前基于局部特征的图像匹配算法应用度较高, 然而各类算法之间也都存在一定的缺陷.

在诸多基于局部特征的匹配算法中, SIFT[2](尺度不变特征变换)、SURF[3](加速稳健特征)、HOG(方向梯度直方图)都是应用比较广泛的局部特征描述子. SIFT和SURF这类描述子都具有旋转和光照不变性,可在图像中检测出关键点, 但是其描述子构成复杂度较高, 计算量较大. HOG[4]特征构成较为简单, 最初由Dalal在2005年的CVPR提出, 现已经被广泛用于图像匹配、人脸识别等技术, 并获得了极大成功. HOG描述子保持了几何和光学转化不变性, 但是在处理图像旋转和尺度变化上效果不佳. 针对该缺陷, Ngoc-Son Vu等人提出对HOG特征加入梯度幅值和边缘方向分布信息的POEM[5](基于方向的边缘振幅模式), 丰富了HOG的特征描述, 能够较好地解决具有旋转变化的图像匹配问题, 同时POEM计算简单, 存取空间较小, 计算效率比较出色. 随着深度卷积网络的提出, Jerome Revaud等人提出一种基于深度卷积网络的图像匹配算法[6](下简称DM), 对待测图像提取梯度信息, 放入深度卷积网络进行特征点相似度计算, 根据相似度得到稠密匹配对, 该算法正确率较高, 但是计算量较大, 并且在运算过程中没有很好利用中间层信息, 可能存在一些特征信息的丢失或偏移. 为了提高算法的鲁棒性和实时性, 针对算法中可能存在的误匹配和算法速度较慢的问题, 提出了一种改进的深度卷积网图像匹配算法, 提高了图像匹配准确率, 加快了算法运行速度.

1 梯度特征的提取

HOG全称为梯度方向直方图, 该技术将图像局部出现的方向梯度次数进行计数. 其依据的原理是局部物体外形能被光强梯度或边缘方向的分布所描述, 由于是对梯度信息的处理, 所以该算子能保持较好的几何和光学不变形, 因此本文采用HOG作为算法的输入特征. 具体提取步骤如下:

(1) 进行图像的预处理(去除图像压缩噪声).

(2) 采用Gamma校正法进行颜色空间的标准化(降低图像局部阴影和光照变化的影响).

(3) 计算图像每个像素的梯度, 梯度的计算公式:

(2)

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

(4) 计算每个像素的梯度方向直方图.

2 加速深度卷积匹配

在深度卷积网络结构中, 卷积层计算复杂度较高, 为了加快算法处理速度, 降低卷积计算的消耗时间, 本算法通过卷积技术对输入数据进行展开, 应用BLAS实施矩阵乘法, 得到加速的深度卷积网络结构(如图1所示), 并最终输出一个初始匹配点集, 下面结合算法结构对算法各环节作简单阐述:

2.1 自底向上获取区分度最大化的特征图

算法结构的各模块作用描述如下(以边长大小为4的卷积核作为输入进行举例):

2) 卷积: 对任意p∈{2,6,…W-2}×{2,6,…H-2}, 对与做卷积:

由于卷积层运算十分耗时, 因此很有必要对卷积层计算进行优化, 提高算法的运算速度. 针对本文计算输入数据卷积, 无法直接用矩阵乘法实现的问题, 本文基于卷积展开技术[7]对输入数据进行展开, 并使用BLAS矩阵运算库实现具体操作, 有效提高了运算速度.

3) 非线性校正: 卷积的结果通过一个非线性函数处理, 调整映射结果范围, 最大程度保留处理后的特征.

4) 降采样和池化: 本文中通过一个步长为2, 边长为3×3的最大池化操作实现池化和降采样. 最大池化有3个具体效果:

第一, 通过最大池化我们能使池化后的结果获得最大相似度, 即满足公式(4)的需求:

第二, 将底层的特征向上层传播, 特征具有平移不变性;

第三, 达到了降采样目的, 降低了输出特征维数.

图2 网格中心漂移

2.2 自顶向下获取待匹配图像之间的响应点集:

3 匹配点筛选

在第2节算法2步骤3获得的匹配点集中, 可能存在非匹配对因在卷积网络传播过程中发生偏移产生误配, 针对该问题, 本文通过计算匹配点POEM特征的相似度, 限定相似度筛选匹配点集, 再通过RANSAC算法进一步去除误匹配.

3.1 基于匹配点集POEM特征的提纯

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

图3 POEM特征提取过程

主要包括以下步骤:

1) 获取梯度幅值图和方向图;

2) 将梯度方向量化到个区间内, 图中=8;

3) 将第个方向的振幅图划分成m×m个单元, 将每个单元所有像素点振幅累加, 作为该单元中心点在这个方向振幅图的特征G(), 将所有个方向的振幅累加值串联起来, 形成的向量[G(),G(),…G()], 即为像素点的特征向量;

4) 在像素点上, 对于第个方向, POEM特征的计算公式为:

其中:q是的相邻像素点;n是编码所选相邻像素点的总个数;的定义即是如果>0,()=1,否则()=0. 像素点的POEM特征就是把个方向的POEM值连接起来:

5) 最后再比较以匹配点坐标为中心的m×m块内POEM特征直方图的相似度:

表示特征维数序号, 该值越大表示两张图片越相似, 我们设定设定一个阈值, 大于这个阈值的则认为匹配点对符合匹配要求, 否则剔除.

在提取深度卷积匹配算法的输入特征时, 已经对图像进行梯度提取并计算梯度大小和方向, 因此可以同时对输入图像的梯度图提取POEM特征, 尽管有很多非特征点被提取POEM特征, 但是多线程并行处理仍然有效降低了计算时间.

3.2 利用RANSAC进一步消除误匹配

RANSAC算法是目前最有效的模型参数估计算法之一, 被广泛用于图像误匹配的剔除, 其缺点是效率不高, 误匹配次数直接影响RANSAC采样次数. 由于通过深度卷积匹配以及POEM特征筛选所得到的匹配点集已经是一个精度较高的匹配结果了, 所以RANSAC能够迅速收敛并达到剔除错误匹配点的要求[9].

本文通过迭代随机抽取, 找到使匹配点所占比的比例最高的最小点集, 对最小点集和匹配点集一同作非线性优化, 得到最终的基本矩阵估计值, 记为W, 最后使用极限约束去除误匹配[10].

输入得到的匹配点集, 然后根据式(8)来剔除:

若满足式(8)则为匹配点, 否则剔除.

通过上述过程, 去除误匹配的同时最大程度保留正确匹配点, 得到最终的匹配点集合.

4 算法和实验

改进的基于深度卷积网的图像匹配算法IDCNIM (Improved Deep Convolution Network Based Image Matching Algorithm)对输入、卷积和匹配点的筛选模块做了三个方面的改进, 其算法流程如下:

算法3: 本文算法IDCNIM 输入: 两幅彩色图像I1、I2. 输出: 图像I1、I2的匹配对集合 ①提取图像I1、I2的灰度图, 并根据压缩格式, 进行高斯平滑处理; ②对图像I1、I2进行降噪和归一化处理; ③提取I1、I2的梯度图T1、T2(含梯度的大小和方向); ④计算T1、T2梯度方向直方图, 并放入IDCNIM网络中, 计算得到一个匹配点集, 记作A; ⑤计算图像I1、I2像素的POEM特征, 此步与第4 步并行进行; ⑥利用匹配点集的POEM特征计算匹配点对的相似度, 根据设定阈值得到匹配点对B; ⑦利用RANSAC算法, 由集合B得到基本矩阵W; ⑧利用W去除A中的误匹配, 得到最终结果.

4.1 匹配性能的验证

为了验证IDCNIM算法的匹配性能, 我们搭建了相应的实验环境: 在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)

为了确保实验的可靠, 限定找出来的匹配点个数并从中计算各算法产生误匹配的概率. 对于双向SIFT通过限定阈值控制匹配点个数, 对于本文中的方法以及深度卷积网络匹配DM, 随机选取匹配点对数, 将多次的计算结果取平均值(向上取整)作为算法的误匹配概率.

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的结果验证: 在图像出现模糊的情况下, IDCNIM和DM算法都取得了较好的效果. 在匹配精度上, 错误率稳定在1.6%和2.4%, 而双向SIFT算法的错误率会随着匹配对数的增加而出现增长, 这是由于阈值t随着匹配对数的增大而增大导致的结果, IDCNIM和DM算法能检测出的正确匹配对数的数量要多于双向SIFT匹配算法, 而IDCNIM由于进行了匹配点的进一步筛选, 有效剔除了部分错匹配点, 对比原算法鲁棒性更强.

针对图5(a)所示的测试图像, 图像存在重复纹理、旋转和尺度变化, 这幅测试图左半边图像是右半边图像旋转180度后局部放大的结果, 而右上角区域未在左半边图像中出现. 对比图5(b)、图5(c)和图5(d)可以观察到, 图5(c)、图5(d)的匹配点连接线在右上角区域出现的概率较低, 同时图5(c)比图5(d)出现的误匹配连接线更少. 表2的结果验证: IDCNIM算法在测试图5这一类变化的图像中匹配效果更佳, 随着匹配对数的增加, IDCNIM错误率稳定在7%左右, DM接近13%, 而双向SIFT随着匹配对数的增加而增加, 这是由于IDCNIM算法中POEM特征本身具有一定旋转不变性以及丰富的纹理特征, 因此在对匹配点筛选后, 有效去除了部分误匹配, 提高了算法的鲁棒性.

针对图6(a)所示的测试图像, 图像存在视角变化, 这幅测试图最右侧的树木以及天空未出现在左半边图像, 对比图6(b)和图6(c)、图6(d)可以观察到, 图6(c)、图6(d)的匹配点连接线在此区域出现的概率较低, 同时图6(c)比图6(d)出现的误匹配连接线更少. 表3结果验证: IDCNIM算法和DM算法处理视角变化的图像时也具有比较稳定的匹配表现, 随着数量的增加, IDCNIM算法和DM算法错误率趋于稳定, 分别接近于9%和12%, 而双向SIFT错误率逐渐增加, 说明IDCNIM算法和DM算法可以找出更多正确的匹配点对, 同时IDCNIM算法也在DM算法的基础上去除了部分错误的匹配点对, 增强了DM算法的鲁棒性.

表4 IDCNIM和DM算法运行时间对比

此外, 由表4可看出, IDCNIM通过卷积展开操作有效降低了卷积运算所需时间, 卷积层运算时间大幅缩短, 比原算法在卷积层运算节省时间接近55%. 尽管由于特征点筛选处理占用了算法的部分时间, 但是算法总体时间还是较DM有所缩短, 有效提高了算法的实时性.

5 结语

本文提出一种以图像梯度信息为特征, 通过加速的深度卷积网络计算各点的相似度, 最后通过各像素点的POEM特征相似度和RANSAC算法实现了匹配点集的筛选. 实验的结果也显示, 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 刘进锋.一种简洁高效的加速卷积神经网络的方法.计算机技术,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]