基于以SURF改进AKAZE的图像匹配算法
2019-04-09赵柏山郑丽娟
赵柏山,郑丽娟,陈 瑜
(1.沈阳工业大学信息科学与工程学院,沈阳110870;2.中国石油长庆油田分公司第四采油厂,银川750006)
1 引 言
图像匹配是指通过一定的匹配算法在两幅或多幅图像之间识别同名点的过程,主要可分为基于图像灰度信息与基于图像特征信息匹配两类。其中,基于特征的图像匹配技术,以其具有鲁棒性高、计算量小的优势取得快速的发展[1]。D. G. Lowe 于2004 年提出了尺度不变特征匹配算法(SIFT)[2],该算法对图像的旋转、尺度变化等都是鲁棒不变的,缺点是实时性差。H. Bay 等人于2006 年提出了加速鲁棒特征算法(SURF)[3],它依赖于图像的高斯尺度空间分析,同时基于Hessian 矩阵[4]的行列式进行特征点检测,利用积分图像、Haar 小波响应提高检测速度,采用Haar 小波变换增加鲁棒性。SURF 特征不受旋转和尺度的影响。与SIFT 相比,SURF 的主要优点是计算成本低,但是在目前各种匹配算法当中,其匹配速度比利用二进制描述符进行匹配的速度慢[5]。Alcantarilla 等人于2012 年提出了利用非线性扩散滤波和非线性尺度空间的KAZE 特征[6]。KAZE 特征对旋转、尺度、有限仿射变换具有不变性,不足之处是计算成本高。Alcantarilla 等人于2013 年提出了加速的KAZE(AKAZE)算法[7],该算法也是基于非线性扩散滤波的,但其使用FED 数学框架,从而动态地加快了非线性尺度空间的计算速度, 并且利用改进的局部差分二进制(M-LDB)[8]描述符,使其速度较KAZE 有很大提高,尽管如此,仍提高得不够理想。故此提出一种改进方法,选择将SURF 特征点检测与AKAZE 特征点描述相结合,并利用汉明距离对图像进行粗匹配,利用RANSAC 算法[9]剔除误匹配点,使得算法在匹配速度及一些变换图像的鲁棒性方面[10-11]有进一步的提高。
2 AKAZE算法原理
2.1 特征点检测
AKAZE 算法以各向异性的非线性滤波来构造尺度空间,非线性扩散滤波通常采用偏微分方程进行求解。经典非线性扩散方程如下:
式中,div 和∇ 分别为散度与梯度,L 为图像的亮度,c(x,y,t)为传导函数。时间t 是尺度参数,数值越大表示图像形式越简单。
1) 构建非线性尺度空间
AKAZE 算法构建非线性尺度空间策略与经典SIFT 算法类似,其组数为o,每组的层数为S。通过以下公式将组数索引和层数索引映射到对应的尺度σ(像素)上[12]:
式中:M 是滤波图像的总数。由于非线性扩散滤波作用于时间序列上,需将以像素为单位的尺度参数σi映射到以时间为单位的尺度参数ti,公式如下:
接着利用FED 算法求解式(1),即可得到非线性尺度图像,其式如下:
式中,I 为单位矩阵,A(Li)为图像Li的传导矩阵,τ 为时间步长,n 为显式扩散步数。
2) 定位特征点
寻找不同尺度归一化后Hessian 矩阵的行列式的局部极大值点,把采样点的响应值与同尺度的8个邻域点及相邻尺度的2×9 个邻域点比较判断是否为最大值,然后将二维二次函数拟合到3×3 像素邻域内Hessian 响应的行列式上,得到亚像素级精度的关键点的二维位置,如下式:
式中,σi,norm=σi/2σi,为对应图像组中归一化尺度因子,Lxx和Lyy分别为二阶横向和纵向微分,Lxy为二阶交叉微分。
3) 判断特征点主方向
与SURF 算法相似,在梯度图像上以特征点为中心,在半径为6σ 范围内,取特征点邻域的一阶微分值Lx和Ly并对其进行高斯加权,接着用π/3 的扇形绕原点旋转并计算该扇形向量和,主方向即为扇形向量和中的最长矢量方向。
2.2 特征点描述与匹配
二进制描述符(如BRIEF、ORB 和BRISK)最近得到了广泛的应用,因为它们可以实现高效的计算和匹配。然而,这些二进制描述符利用过度简化的信息,即用于二进制测试的图像块内的像素子集的原始强度,因此辨别能力不高。AKAZE 算法利用一种局部差分二进制描述符(M-LDB),该描述符遵循和BRIEF 相同的原理,但在区域平均值之间使用二进制测试而不是单个像素,以获得额外的鲁棒性。
以任意给出的某图像为例,LDB 将图像分成n×n 个相等大小的网格单元并从每个网格单元中提取平均强度和一阶梯度,如图1(a)所示,用于计算直立的描述符;而M-LDB 描述符根据特征点主方向,将LDB 所划分的网格单元做相应旋转使其旋转到主方向上,如图1(b)所示,然后计算每个网格的平均强度和梯度,各公式如下:
式中,m 为网格i 的总数,Iavg(i)为各网格单元的平均强度,dx(i)和dy(i)分别为网格i 区域的x 和y 方向的梯度。然后,LDB 分别比较成对网格单元之间的平均强度和梯度,根据比较结果,相应地设为0 或者1。其公式如下:
利用M-LDB 算子生成结果的是由0 和1 组成的二进制描述符,最终使用两幅图片特征点二进制描述符的汉明距离进行暴力匹配,生成匹配结果。
图1 围绕一个特征点的二进制测试网格划分
3 改进的AKAZE算法
AKAZE 算法虽然利用了二进制描述符,但由于特征点检测部分是用非线性滤波来构造尺度空间,因此匹配速度较慢。为提高匹配速度,现将SURF 特征点检测与AKAZE 算法的M-LDB 描述符相结合,来实现图像特征匹配。
3.1 基于Hessian矩阵的特征点检测
利用Hessian 矩阵检测特征点的方法是去计算图像所有像素的Hessian 矩阵的行列式,极值点处就是图像特征点所在的位置。
设图像I 中有某点X=(x,y),则在该点处,尺度为σ 的Hessian 矩阵为:
式中,Lxx=(X,σ)是高斯滤波后的图像点X 在x 方向上的二阶导数,Lyy=(X,σ)和Lxy=(X,σ)具有相似的含义。在构造Hessian 矩阵时应先进行高斯滤波,再计算二阶导数。SURF 算法使用盒式滤波器来代替高斯函数,大大提高了运算速度。近似处理的效果如图2 所示。
图2 对高斯函数的近似处理
其中,图2(a)、(b)、(c)分别为沿x 方向、y 方向、xy方向的高斯二阶微分算子, 即Lxx模板、Lyy模板、Lxy模板;图2(d)、(e)、(f)分别为盒式滤波器Dxx模板、Dyy模板、Dxy模板。在盒式滤波器中,白色部分的权值为1,灰色部分的权值为0,Dxx和Dyy中黑色部分的权值为-2,Dxy中黑色部分的权值为-1。Dxx,Dyy和Dxy可通过积分图像求得。可用以下公式来近似计算Hessian 矩阵的行列式:
式中,ω 为权值,被用来平衡因子近似所带来的偏差,其值为0.9。据此即可利用公式(12)得到每个像素点的Hessian 矩阵的行列式值的近似值。
为了使检测到的特征点具有尺度不变性,通过改变盒式滤波器模板的大小,对图像进行滤波,以产生多幅不同尺度的图片;并通过公式(12)计算出不同尺度图像下所有像素的Hessian 矩阵的行列式值。具体步骤为:首先取阈值,保留那些行列式值高的像素;然后将要检测的像素与其邻域的26 个像素点的行列式值做比较,去掉不是最大值的点;最后利用插值法来确定特征点的位置。
为获得旋转不变性,SURF 算法通过统计特征点邻域内的Haar 小波特征确定其主方向。首先以特征点为中心,计算特征点邻域(如半径为6s 的圆,s为该点所在尺度)内的点在x,y 方向的Haar 小波响应[13],用它即可以检测出x 方向和y 方向上的梯度。Haar 小波边长取4s,这样每个扇形都得到了一个值。然后用60°扇形以一定间隔进行旋转,将60°范围内的响应相加以形成新的矢量,历遍整个圆形区域,选择最长矢量的方向为该特征点的主方向,如图3 所示。
图3 梯度坐标系内求方向
3.2 特征描述与匹配
在计算描述符之前,首先将不同尺度图像以特征点为中心分成n×n 的小块,并将图像旋转到主方向上,接着利用2.2 节所描述的AKAZE 特征描述方法来得到描述符,然后使用二进制描述符的汉明距离进行暴力匹配,得出匹配结果。在得出匹配结果之后,使用RANSAC 算法剔除误匹配点,得到准确率较高的匹配图像。
4 实验与分析
4.1 实验设计
使用牛津数据集中的不同模糊程度图像(blurbikes)、不同程度的JPEG 压缩图像(JPEG ubc)、不同光照强度图像(light.Leuven)、不同视角下的图像(viewpoint.graf),每种图像变换的程度由从小到大的6 张图片组成,通过第一张图片与其后的5张图片匹配得出匹配结果,把它们定义为第1~5组,对比它们的匹配时间与正确率。其中匹配时间是通过取30 次匹配时间的平均值得出的,匹配正确率是取30 次匹配正确率的平均值得出的。
实验中,所用的电脑为Windows 10 系统,处理器为Intel(R)Core(TM)i5-3210M, 64 位操作系统,内存为4.00GB,并使用Visual Stdio 2015 进行实验。
4.2 各变化条件下图像
匹配结果及分析
不同模糊程度的图像的匹配时间与匹配正确率的对比情况如表1、表2 所示。
表1 不同模糊图像匹配时间
表2 不同模糊图像匹配正确率
从表1,表2 可以看出,在不同程度的图像模糊条件下,在匹配速度方面,本算法比SURF 的匹配速度平均快了近3 倍,比AKAZE 算法快了近8 倍;在匹配准确率方面,本文算法的正确率明显比SURF算法高,比AKAZE 算法相比也有小幅度提高。
不同JPEG 压缩图像的匹配时间与匹配正确率对比情况如表3、表4 所示。
表3 不同JPEG压缩图像匹配时间
表4 不同JPEG压缩图像匹配正确率
从表3、表4 可以看出,在不同程度的图像压缩条件下,在匹配速度方面,本算法比SURF 的匹配速度平均快了2 倍多,比AKAZE 算法快了近7 倍;在匹配准确率方面,本算法比SURF 算和AKAZE 算法都要更高。
不同光照强度图像的匹配时间与匹配正确率对比情况如表5、表6 所示。
表5 不光照强度图像匹配时间
表6 不光照强度图像匹配正确率
从表5、表6 可以看出,在不同光照强度的图像匹配中,在匹配速度方面,本算法比SURF 的匹配速度平均快了近3 倍,比AKAZE 算法快了7 倍多;在匹配正确率方面,本算法在光照强度变化较小时,比SURF 算法和AKAZE 算法都高,但是在光照强度变化较大时,正确率还有待提高。
不同视角图像的匹配时间与匹配正确率对比情况如表7、表8 所示。
表7 不同视角图像匹配时间
表8 不同视角图像匹配正确率
从表7、表8 可以看出,在图像的视角变化中,在匹配速度方面,本算法比SURF 的匹配速度平均快了2 倍多,比AKAZE 算法快了6 倍多;在匹配正确率方面,本文算法比SURF 算和AKAZE 算法都有明显提高。
5 结束语
在提出的算法改进中,将SURF 算法与AKAZE算法相结合,在SURF 特征点检测部分采用盒式滤波器以代替高斯函数进行滤波,提高了特征点检测速度;而AKAZE 的特征点描述部分采用二进制描述符,匹配时使用汉明距离,速度也很快。由此可见,两者结合后,算法的匹配速度比SURF 算法和AKAZE 算法提高很多。在不同模糊程度、不同JPEG压缩、不同视角下的图像匹配中,改进后的算法的匹配精度也比SURF 算法与AKAZE 算法更高。目前还存在着在不同光照强度下匹配精度较另外两种算法为差的问题,对此如何解决,也将成为后续研究的重点。