基于感知Hash和极线约束的改进AKAZE算法

王宏志, 张金栋, 胡黄水, 谢沛松

(长春工业大学 计算机科学与工程学院, 长春 130012)

基于特征的图像匹配是图像匹配的主流方法之一, 目前已有许多经典算法. SIFT(scale invariant feature transform)算法[1]使用高斯核函数, 使特征点具有尺度不变性, 但计算量较大； SURF(speedup robust features)算法[2]是SIFT算法的加速版本, 使用Hesse矩阵用于尺度空间的构造； ORB算法通过FAST(feature from accelerated segment test)算法提取特征点, 通过BRIEF(binary robust independent elementary features)计算得到描述子[3], 提高了运算效率, 但特征点匹配准确率较低； KAZE算法是基于非线性的特征提取与匹配算法[4], 使用加性算子分裂算法(additive operator splitting, AOS)进行非线性扩散滤波, 使KAZE算法在模糊图像的同时还能保留边缘细节； AKAZE(accelerated-KAZE)算法[5]使用快速显示扩散(fast explicit diffusion, FED)算法代替KAZE中的AOS算法构造非线性尺度空间, 提升了计算效率, 并使用二进制描述符M-LDB(modified-local difference binary)描述特征点. 针对传统算法目前已提出了许多改进方法， 例如： 用贪婪搜索算法[6]或遗传算法[7]优化性能； 用改进下采样方法保留更多有区分性的点对[8]； 用四叉树划分图像辅助特征点的检测[9]； 用光谱维度进行图像空间性质的测量[10]； 用基于全局运动建模的双边函数算法进行特征点匹配[11]； 用自适应阈值[12]或自适应直方图均衡化的方法[13]提高特征点匹配准确率.

原始AKAZE算法虽然具有较好的鲁棒性, 但当图像发生变化时特征点匹配准确率较低. 为解决上述问题, 梁焕青等[14]使用颜色不变量的灰度级增加了图像的彩色信息, 但需要根据经验值确定灰度变换的参数； 李闯等[15]使用AKAZE检测特征点, 并使用RANSAC(random sample consensus)算法剔除误匹配点, 实现了对喀斯特地貌无人机影像的快速匹配; Liu等[16]将AKAZE特征与改进的SIFT描述子相结合, 提高了算法的匹配精度; 李丹等[17]提出了一种基于网格运动约束的遥感图像配准方法, 能快速且鲁棒性较强的进行特征点匹配； 陈海鹏等[18]使用基于密度的聚类算法去除错误匹配, 并通过仿射变换整幅图像对篡改区域进行定位； 邢长征等[19]提出了基于AKAZE的掩码描述符匹配算法, 使其可应用于对鲁棒性和匹配速度要求较高的匹配场景； 沈学利等[20]使用三元组LATCH(learned arrangements of three patch codes)描述符替代M-LDB描述符, 提高了特征点匹配的速度； Anuja等[21]使用AKAZE和FAST技术提取关键点, 在FAST关键点提取过程中, 采用自动对比度阈值进行非最大值抑制.

本文提出一种改进的AKAZE算法, 将特征点匹配分为两个阶段. 粗匹配阶段在使用快速近似最近邻算法筛选出匹配点对的基础上, 引入最近邻特征点和次近邻特征点的概念, 利用两者的距离比值进行特征点的筛选, 并使用感知Hash算法计算出特征点Hash值增加特征点的独特性, 将其用于粗匹配阶段特征点对的筛选, 同时使用感知Hash算法计算出两张图片的Hash值差异, 将其用于精匹配阶段阈值的选取； 精匹配阶段在使用RANSAC算法的基础上利用极线约束原理进一步筛选特征点对.

1 AKAZE算法

1.1 构造非线性尺度空间

AKAZE算法将非线性扩散滤波器用于尺度空间的构造, 非线性扩散滤波可用非线性偏微分方程表示, 表达式为

(1)

其中L为图像的亮度, div为散度,为梯度,c为传导函数,x和y为坐标,t为尺度参数.传导函数c可表示为

c(x,y,t)=g(Lσ(x,y,t)),

(2)

其中g为传导核函数,Lσ为图像经过高斯平滑后的梯度图像.传导核函数g可表示为

(3)

其中参数λ用于控制扩散程度.对于偏微分方程的求解, AKAZE并未使用KAZE算法中的AOS算法, 而使用了FED算法确保算法的实时性, 并以此构造出O组非线性尺度空间, 其中每组有S层.用FED算法求解式(1)得到图像的非线性尺度空间表达式为

Li+1=(I+τA(Li))Li,i=0,1,…,n-1,

(4)

其中I为单位矩阵,τ为时间步长,A(Li)为图像Li在维度i的传导矩阵,n为显式扩散步数.

1.2 检测特征点

AKAZE算法首先对每层尺度空间中的像素点进行Hesse矩阵计算, 然后将该像素点的响应值与同层以及上下相邻层的3×3区域内26个像素点进行比较, 若该像素点在与这26个像素点的比较中均为最大, 则该点即为特征点.Hesse矩阵的计算公式为

(5)

其中σ为尺度参数,Lxx和Lyy分别为二阶横向微分和二阶纵向微分,Lxy为二阶交叉微分.

1.3 确定特征点主方向

AKAZE算法以特征点为中心, 以尺度参数的6倍为半径确定圆形区域, 将特征点邻域的一阶微分值Lx和Ly进行高斯赋权运算, 并以角度为60°的扇形窗口旋转, 计算该窗口内的向量和, 向量和最大的方向即为特征点的主方向.

1.4 计算特征描述符

AKAZE算法使用M-LDB描述符. M-LDB描述符主要针对LDB(local difference binary)描述符进行了旋转与缩放性能的改进, 该描述符未使用所有的划分网格像素, 而是通过网格像素采样完成尺度自适应, 这样离散采样获得的描述符是由0和1构成的二值描述符, 可提高算法的实时性能.

1.5 特征点匹配

AKAZE算法中特征点的描述符为二值描述符, 因此一般通过计算特征点描述符间的Hamming距离判断特征点之间的匹配程度进行特征点的匹配. 而在实际使用中常会在上述特征点匹配完成后使用随机抽样一致算法等消除误匹配点, 从而进一步完成特征点的匹配.

2 改进的AKAZE算法

2.1 基于最近邻次近邻比值和感知Hash特征点的粗匹配

2.1.1 最近邻次近邻比值

AKAZE算法通过计算描述符的Hamming距离进行特征点的暴力匹配易导致大量误匹配, 本文将特征点的匹配分为粗匹配和精匹配两个阶段对AKAZE算法进行改进. 粗匹配阶段中, 在使用快速近似最近邻算法筛选出匹配点对的基础上, 通过最近邻次近邻的比值进行匹配点对的筛选, 并使用感知Hash算法计算特征点的Hash值增加特征点的独特性, 进一步剔除错误的匹配点对.

最近邻次近邻比值是指使用快速近似最近邻算法在待匹配图像中找出与基准图像特征点Hamming距离最近和次近的两个特征点, 并将分别计算出的最近距离与次近距离的比值与设定的阈值比较, 如果比值结果大于设定的阈值, 则将该特征点对剔除, 本文阈值设定为0.75.

2.1.2 感知Hash

感知Hash算法(perceptual Hash algorithm)可对图像生成一个“指纹”, 通过比较两张图像之间的指纹对图像的相似度进行判断. 感知Hash算法步骤如下.

1) 缩小尺寸: 将图片缩小到8×8大小, 共64个像素, 其目的是快速去除图像高频和细节, 只保留图像基础的结构.

2) 色彩简化: 将缩小后的图片转化为灰度图像.

3) 计算离散余弦变换(DCT): 离散余弦变换就是将图片分解频率聚集和梯形状, 表示为

(6)

其中F(u,v)为DCT变换后的系数矩阵,f(i,j)为原始信号,c(u)和c(v)为补偿系数,N为原始信号的个数,u和v是系数矩阵F(u,v)的坐标.

4) 计算Hash值: 计算步骤3)中64个值的平均值, 并将每个值与平均值进行比较, 如果小于平均值则该值为0, 大于等于平均值则该值为1, 从而获得由0和1组成的64位Hash值, 即该图像的指纹.

本文使用感知Hash算法增加特征点的独特性, 相当于对M-LDB描述符增加了一个Hash值的新维度, 可有效减少原始算法中两个特征点在不同区域, 但根据Hamming距离仍然判断为匹配点对的情况. 本文以特征点为中心, 截取其8×8的邻域图像并计算Hash值, 在最近邻次近邻比值的基础上对匹配点对的Hash值进行计算, 如果小于设定的阈值, 则保留匹配点对, 如果大于设定的阈值, 则将该特征点对剔除. 在对整幅图片进行对比时, 阈值一般设定为5, 但对于本文所选取的特征点邻域并不存在缩小图片尺寸的步骤, 阈值如果仍设定为5会消除掉过多正确的匹配点对, 因此本文将该阈值设定为15.

2.2 基于RANSAC和极线约束的特征点精匹配

RANSAC算法虽然能鲁棒地估计模型参数, 但其本质存在着随机性和假设性, 因此只有一定的概率得到可信的模型. 针对上述问题, 本文在特征点的精匹配阶段, 在使用RANSAC算法的基础上利用极限约束进一步筛选匹配点对.

极线约束原理如图1所示, 其中C1和C2分别为两个相机的投影中心, 点P1和P2分别是点P在两个相机上的投影, 点C1,C2和P组成的平面称为极平面, 极平面和左右两张图像分别产生交线l1和l2, 这两条线称为极线, 极线和投影中心产生交点e1和e2, 这两个点称为极点. 由图1可见, 特征点对中右图的特征点应该在根据左图特征点计算出的极线上, 因此可通过极线约束原理创建基本矩阵F, 并通过基本矩阵F判断是否剔除特征点对.基本矩阵F是一个3×3的矩阵, 一般取右下角元素为1, 因此F包含了8个未知量, 本文采用8点法进行求解, 过程如下.

图1 极线约束原理Fig.1 Principle of epipolar constraint

设点P1和P2的坐标分别为(x1,y1,1)T和(x2,y2,1)T, 可得：

(x2x1,x2y1,x2,y2x1,y2y1,y2,x1,y1,1)f=0,

(7)

其中f为F的元素组成并按优先顺序排列的矢量, 表达式为

f=(F11,F12,F13,F21,F22,F23,F31,F32,F33),

(8)

式中Fij表示F的第i行、 第j列元素, 选取8组特征点对, 令x和y的第一个下标表示组数, 第二个下标表示坐标, 可得

(9)

由式(9)可计算出极线方程以及基础矩阵F.此时可判断匹配点对是否满足下式：

(10)

式中p0和p1为匹配点对坐标.若匹配点对满足式(10)则保留, 不满足则剔除.在实际应用中, 将正确匹配点对代入式(10)也不会完全为0, 因此本文根据两张图像Hash值的Hamming距离进行阈值的设定, 当特征点对代入后的值大于设定的阈值时, 剔除匹配点对.阈值设定为

(11)

式中η为两张图像Hash值的Hamming距离.

3 实验结果与分析

实验环境为虚拟机环境. 电脑操作系统为Windows 10, CPU为i7-4790四核处理器, 频率为3.60 GHz, 内存为8 GB, DDR3架构, 频率为1 600 MHz. 虚拟机操作系统为ubuntu 18.04, 处理器数量设为两个, 每个处理器有两个内核, 内存设为4 GB.

为验证本文改进后算法的有效性, 采用Mikolajcayk标准图像数据集中的ubc(压缩)、 bikes(模糊)、 boat(旋转缩放)、 leuven(光线亮度)4组图像进行实验, 对比算法1～算法4分别为AKAZE算法、 KAZE算法、 SIFT算法、 ORB算法. 由于在实际情况下计算出特征点对后会进行误匹配点对的剔除, 因此本文的对比算法均使用RANSAC算法进行了误匹配点对的剔除.

在图像发生压缩和模糊的情况下各算法的对比结果如图2和表1所示. 表1中压缩1～5, 模糊1～5表示数据集中的第一张图与后续第几张图进行实验.

图2 图像发生压缩和模糊情况下不同算法准确率的折线对比结果Fig.2 Broken line comparison results of accuracy of different algorithms in the case of image compression and blur

表1 图像发生压缩和模糊情况下不同算法准确率的对比结果

由图2和表1可见, 本文算法在图像发生压缩的情况下平均准确率为96.79%, AKAZE,KAZE,SIFT,ORB算法的平均准确率分别为89.8%,77.458%,82.162%,74.368%, 与未改进的AKAZE算法相比, 本文算法平均准确率提高了6.99%; 与最接近的SIFT算法相比, 本文算法平均准确率提高了14.628%. 而在图像发生模糊的情况下, 本文算法平均准确率为92.242%, AKAZE,KAZE,SIFT,ORB算法的平均准确率分别为78.93%,69.032%,70.934%,48.866%, 与未改进的AKAZE算法相比, 本文算法平均准确率提高了13.312%, 与最接近的SIFT算法相比, 本文算法平均准确率提高了21.308%.

在图像发生旋转缩放和光线亮度改变情况下不同算法的对比结果如图3和表2、 表3所示. 表2和表3中旋转缩放1～5和光线亮度1～5表示数据集中的第一张图与后续第几张图进行实验. 由表2和表3可见, 本文算法在图像发生旋转缩放的情况下平均准确率为87.31%, AKAZE,KAZE,SIFT,ORB算法的平均准确率分别为72.605%,66.91%,82.167 5%,73.62%, 与未改进的AKAZE算法相比, 本文算法平均准确率提高了14.705%, 与最接近的SIFT算法相比, 本文算法平均准确率提高了5.143%. 而在图像发生光线亮度改变的情况下, 本文算法平均准确率为97.442%, AKAZE,KAZE,SIFT,ORB算法的平均准确率分别为80.87%,76.034%,89.002%,67.908%, 与未改进的AKAZE算法相比, 本文算法平均准确率提高了16.572%, 与最接近的SIFT算法相比, 本文算法平均准确率提高了8.44%.

图3 图像发生旋转缩放和光线亮度改变情况下不同算法准确率的折线对比结果Fig.3 Broken line comparison results of accuracy of different algorithms when images are rotated and scaled and brightness of light changes

表2 图像发生旋转缩放改变情况下不同算法准确率的对比结果

表3 图像发生光线亮度改变情况下不同算法准确率的对比结果

本文算法、 AKAZE算法、 KAZE算法、 SIFT算法、 ORB算法的特征点匹配平均用时分别为0.279 2,0.272 6,0.910 8,0.562 8,0.103 7 s. 表明由于本文算法在粗匹配阶段已经进行过一次匹配点对的筛选, 在图像发生变化时可先行有效地削减特征点对的数量, 而在精匹配阶段本文算法选择顺序执行而不是并行执行极线约束和RANSAC算法, 因此在面对图像发生变化的图片匹配时, 在速度上与原始算法相比仅慢2.4%, 并未产生明显差距.

选取4种图像变化效果中的模糊和旋转缩放绘制特征点匹配如图4所示. 图4中左侧为模糊数据集中第一张图像与第四张图像的特征点匹配, 右侧为旋转缩放数据集中第一张图像与第三张图像的特征点匹配. 从上到下依次为原始AKAZE算法、 经过RANSAC算法剔除误匹配点对的AKAZE算法以及本文算法. 由图4可见, 本文算法可有效匹配各特征点.

图4 特征点匹配Fig.4 Feature point matching

综上所述, 本文针对AKAZE算法在图像发生变化时, 特征点匹配精度较低的问题, 提出了一种基于感知Hash和极线约束的改进AKAZE算法, 并使用Mikolajcayk标准图像数据集中的ubc(压缩)、 bikes(模糊)、 boat(旋转缩放)、 leuven(光线亮度)4组图像, 与经过RANSAC算法进行误匹配点对剔除后的AKAZE算法、 KAZE算法、 SIFT算法、 ORB算法进行了对比. 实验结果表明, 改进后的AKAZE算法在保证算法效率的前提下, 特征点匹配准确率比原算法平均提高了12.9%, 比KAZE算法平均提高了21.09%, 比SIFT算法平均提高了12.38%, 比ORB算法平均提高了27.26%.