基于感知哈希与尺度不变特征变换的快速拼接算法

要小涛, 王正勇, 石 伟, 卿粼波, 何小海

(1.四川大学电子信息学院， 成都 610065； 2.中国民航局第二研究所， 成都 610041)

1 引 言

图像拼接是指将具有互相重合部分的图像融合为一张更大视域图像的技术. 近年来, 这项技术在无人机勘测、卫星遥感、三维重建以及增强现实等诸多领域发挥着重大的作用[1-4].图像拼接技术一般分成特征点提取、特征点匹配和图像融合3个阶段. 在特征点匹配这一环节影响着图像拼接的速度并且决定着图像的拼接是否成功. 而图像融合决定着最后呈现的拼接效果. 现在使用最多的拼接算法是先通过ORB算法、SIFT算法或者SURF算法提取特征点, 然后使用k-d树算法进行特征点匹配, 再求出两幅图像的单应性矩阵并转换到同一坐标系下, 最后采用渐入渐出算法完成融合. 其中ORB使用的是FAST特征点与BRIEF特征描述符, 特征提取速度很快, 但BRIEF描述简单, 匹配率相对降低[5]; SIFT算法对矩阵变换不敏感, 噪点污染和光照强弱的变化不会影响其稳定性, 但算法耗时较大[6]; SURF 算法基于SIFT算法的思想, 改变计算方法减少了特征点提取时间, 但精度相对降低[7].

为了提升算法匹配的准确率及效率, 在特征点提取方面, 李玉峰等[8]采用基于区域分块的算法, 将图像按照4等份分成4个分块, 选择两幅图像分块相似度最大的一组作为相似区域提取特征点, 减少特征点数量, 加快匹配速度, 但是图像4等份存在所选区域相似部分不完整, 不具备代表性等问题. 厉丹等[9]采用相位相关法, 计算两幅图像的互功率谱提取两幅图像的位移从而定位相似区域, 但该方法对有尺度变化或角度变化的图像效果不佳, 且图像越大傅里叶变换耗时越多. 在特征点匹配方面, Bian等[10]在BF算法[11]匹配之后加入网格运动统计(GMS)算法剔除错误的匹配, 提高了匹配精度. Lowry等[12]提出LOGOS算法，利用特征局部尺度信息剔除错误的匹配, 同样提高了匹配精度. 在图像融合方面, Zaragoza等[13]提出局部单应性矩阵, 将图像网格化, 只对重叠部分进行处理, 拼接结果过渡平滑, 但是对特征点匹配的要求较高.

综上所述, 本文采用感知哈希算法[14], 通过比对匹配图像与待匹配图像的HASH指纹, 确定相似区域. 在特征点选取上为了保证特征点的精度而使用SIFT特征, 在图像匹配上则直接替换传统的k-d树算法[15], 利用SIFT特征点的主方向信息与相似区域的坐标信息, 过滤掉非匹配组, 缩短匹配时间. 区别于GMS算法在匹配完后过滤, 本文算法在匹配计算过程中实现过滤, 加速匹配过程的同时还提高了精度. 最后在图像融合上选择加权最佳拼接缝算法[16]消除突变, 完成拼接. 实验结果显示, 本文算法在速度、计算资源消耗、拼接效果上都明显优于传统的SIFT算法,并且在上百张岩石微观图像拼接的实际应用场景上, 有较好的表现.

2 相似区域提取

一张图像相当于一个二维信号, 含有多种不同的频率. 低频部分的亮度变化小, 包含了图像大多数的信息. 高频部分的亮度变化强烈, 表现的是图像的细节. 相似区域感兴趣部分是图像的低频部分, 对其进行编码生成哈希指纹. 感知哈希算法首先将原始图像进行缩放为32*32尺寸并转化为灰度图, 以减小计算量, 然后使用离散余弦变换(DCT)将信号转换到频域, DCT公式[14]如下.

(1)

(2)

(3)

其中,E是一维变换后的系数;F是二维变换后的系数；f是输入的信号；u和v是输入信号每一维点的个数；c是系数, 可以将矩阵转换为正交矩阵.

离散余弦变换后将得到一个32*32的矩阵, 仅需要矩阵中的低频部分, 即位于左上方8*8大小的矩阵. 计算该矩阵内的均值, 将矩阵中每一个小于等于均值的点修改为“0”, 大于均值的修改为“1”. 将得到一个长度为64位的字符串, 即哈希指纹.

相似区域提取具体流程如下：输入匹配图像与待匹配图像, 将匹配图像从左到右平均分成4部分, 考虑到效率以及精度取第4部分生成匹配HASH指纹. 将待匹配图像以图像宽度的1/128作为步长截取图像(截取图像宽度与匹配图像截取宽度相同), 共获得96幅截取图像, 并生成待匹配HASH指纹, 如图1所示.

图1 相似区域提取示意图Fig.1 Similar area extraction diagram

计算匹配HASH指纹与待匹配HASH指纹的汉明距离, 汉明距离最小的即为最佳相似截取图像, 该图像到原图像坐标原点的距离再加上截取图像宽度即为两幅图像的大致相似区域, 图2和图3为相似区域提取的结果.

(a) 待匹配图像

(b) 提取的相似区域

(a) 待匹配图像图2 图像一相似区域提取结果Fig.2 Image 1 similar area extraction result

(b) 提取的相似区域图3 图像二相似区域提取结果Fig.3 Image 2 similar area extraction result

3 特征点提取与匹配

3.1 特征点提取

获取到图像的相似区域后再提取SIFT特征[6].SIFT特征提取步骤如下.

(1) 构造尺度空间：一副图像清晰程度可以用尺度来度量, 尺度越大则图像越模糊, 所展示的细节越少, 在各个尺度上提取特征点, 确保经过缩放的图像特征点的唯一性, 提高特征点的精度.

(2) 关键点搜索与定位：关键点是尺度空间里的局部极大值或极小值. 将每一个像素点与它所有的相邻点, 以及它的图像域和尺度域的相邻点值的大小进行比较. 如果该点的值最大或是最小, 即将该点作为一个关键点候选点. 然后以主曲率大小作为判断依据, 除去在边缘的关键点.

(3) 方向赋值：为了消除旋转变换对特征的影响, 对关键点周围邻域内的所有像素点求得其梯度的方向. 使用直方图统计的方法, 以每柱10°的间隔将360°分为36个柱面, 统计像素点梯度的方向在各区间的分布. 关键点的主方向是最高柱面所代表的方向. 为了提高鲁棒性, 并选择一些关键点的辅方向, 这些方向的峰值大于或等于最高值的80%.

(4) 特征点描述子：以关键点为中心, 将坐标轴旋转一定角度, 与主方向平行. 在关键点的周围邻域内, 计算它们的局部梯度, 用向量的形式表示, 并进行归一化, 最终生成一个128维的特征向量. 特征点描述子具有很好的独立性, 归一化除去了亮度变化造成的误差. 旋转到主方向保证了特征点对旋转变换抗性.

3.2 基于SIFT特征点主方向与位置信息的匹配算法

传统的k-d树算法只使用到了SIFT特征点的特征描述子, 没有充分利用特征点的主方向、位置坐标信息, 使得存在很多的误匹配, 且浪费了大量的时间. 因此本文提出基于SIFT特征点主方向与位置信息的匹配算法. 算法的核心思想是根据已匹配特征点的结果缩小匹配范围，减少不必要的匹配计算. 流程如图4所示.

图4 算法流程图Fig.4 Flowchart of algorithm

图4中的算法步骤如下：

(1) 输入匹配图像相似区域的匹配特征点集SIFT1和待匹配图像相似区域的待匹配特征点集SIFT2. 特征点集中的每一个特征点都包含主方向信息arc, 坐标信息x、y以及特征描述子信息.

(2) 初始化参数HS为图像的高度, 参数WS为原始图像的1/4截取部分宽度. 这两个参数作为两个特征点是否可能关联的判断依据.HS代表两幅图像在y轴方向的偏移,WS代表两幅图像在x轴方向的偏移. 这两个参数会在后续过程中收敛稳定.

(3) 计算特征点之间的主方向信息与位置信息的误差，公式如下.

Ex=||xi-xj|-WS|-30

(4)

Ey=||yi-yj|-HS|-20

(5)

Earc=|Siarc-Sjarc|-8

(6)

其中，Ex是x轴方向的误差;Ey是y轴方向的误差;Earc是主方向角度误差.Sarc是特征点的主方向. “8”、“20” 和“30”为经验值, 代表允许误差, 值越小匹配速度越快, 但相应的会损失匹配的精度. 当Ex,Ey和Earc中某一项的值大于0则说明两个特征点匹配的概率极小, 舍弃并进行下一个关键点的判断. 在满足条件的待匹配特征点中计算与匹配特征点欧式距离, 公式如下.

(7)

其中,mi,ni是特征点描述子的向量；D(m,n)是特征点描述子向量之间的的欧式距离.D(m,n)越小匹配度越高, 记距离最小的一对匹配点的距离为D1, 距离次小的一对匹配点的距离为D2, 若D1小于0.8倍的D2，则最小距离的一对匹配点即为匹配对.

(5) 每找到3个匹配对以后, 根据各匹配对权重和M, 更新HS与WS. 权重与D大小成反比.公式如下.

(8)

(9)

(10)

为了验证本文匹配算法本身的优越性, 选择在相同特征点数量下(保证匹配前初始条件的一致性, 为了显示效果设置为1 000个特征点), 对比k-d树算法[15]、GMS算法[10]、LOGOS算法[12]与本文匹配算法. 实验结果如图5、图6和表1所示.

(a) k-d树算法 (b) GMS算法

(c) LOGOS算法 (d)本文算法

(a) k-d树算法 (b) GMS算法图5 图像一匹配结果对比Fig.5 Image 1 match result comparison

(c) LOGOS算法 (d) 本文算法图6 图像二匹配结果对比Fig.6 Image 2 match result comparison

表1 实验数据对比

可以看到, k-d树算法存在大量的误匹配, 算法的时间对特征的维度敏感且存在回溯搜索的过程, 所以耗时稍长. GMS算法与LOGOS算法则过滤掉大量的误匹配, 结果更加精准, 但是GMS算法依赖于暴力匹配之后的结果, LOGOS算法需要进行特征聚类计算, 更加耗时. 而本文匹配算法直接在匹配过程中实现过滤, 减少了计算量与算法耗时. 速度提升数倍. 使用迭代方式更新判断的条件, 提高了算法的稳定性, 使得匹配准确率较k-d树算法有显著提升, 虽然不如GMS算法与LOGOS算法精确, 但是获得了更多的正确匹配对, 综合结果更优.

4 图像融合

使用RANSAC算法可以得到图像之间的单应性矩阵, 消除拍摄模式不同而造成旋转变换、位移变换以及投影变换的影响[17]. 单应性矩阵模型如下.

(11)

其中,x,y是匹配图像的横纵坐标，x′,y′是待匹配图像的横纵坐标. 根据上一节求出的匹配结果, 求出矩阵 , 通过单应性矩阵将两幅图像转换到同一坐标系下.

传统的渐入渐出融合算法, 在图像之间的重叠部分加入权值, 在重合部分过渡的时候, 权值从0至1, 消除重叠区域的突变达到融合的效果. 但是如果重叠部分有运动状态的物体, 会产生鬼影等现象, 拼接效果不佳. 因此本文使用加权最佳拼接缝图像融合算法[16], 通过动态规划的方式找到两幅图像的最佳拼接缝, 消除鬼影, 然后在最佳拼接缝处使用加权融合, 最终完成拼接.

两幅图像在拼接缝上的像素点色彩差异最小以及结构最相似, 这条拼接缝即为最佳拼接缝[18]. 公式如下.

Egeometry(x,y)=|Sx*I|+|Sy*I|

(12)

Ecolor(x,y)=|I1-I2|

(13)

(14)

E(x,y)=Ecolor(x,y)2+Egeometry(x,y)

(15)

其中,Sx与Sy是sobel梯度算子;I是图像;Egeometry是两幅图像结构上的差异值;Ecolor是两幅图像像素的色彩差异值.

然后以重叠部分第一行作为拼接缝的起点, 按照上述条件, 建立多条拼接缝, 找出误差最小的一条即为最佳拼接缝. 最后在最佳拼接缝处使用渐入渐出加权融合, 消除突变. 部分实验结果如图7和图8所示.

可以看到, 传统的渐入渐出加权算法在细节上表现不佳, 对RANSAC算法求得的单应性矩阵精度要求很高, 稍有偏差就会出现鬼影现象, 如图8(c)所示. 使用最佳拼接缝方法有效地避免了在整个重叠区域进行加权运算, 消除了鬼影. 但在拼接缝处, 由于匹配图像与待匹配图像之间亮度差异等原因, 造成拼接缝处左右亮度不均, 过渡生硬, 如图7(b)所示. 所以在拼接缝处使用加权运算, 消除拼接缝处的突变, 完成自然过渡.

(a) 待拼接图像

(b) 最佳拼接缝

(c) 传统算法拼接结果及细节

(d) 加权最佳拼接缝拼接结果及细节图7 图像一拼接结果对比Fig.7 Image 1 stitching result comparison

(a) 待拼接图像

(b) 最佳拼接缝

(c) 传统算法拼接结果及细节

(d) 加权最佳拼接缝拼接结果及细节图8 图像二拼接结果对比Fig.8 Image 2 stitching result comparison

5 实验数据分析及工程应用

本文算法运行在64位win 10操作系统, Intel (r) Core (tm)i5-4590 CPU @ 3.30 GHz CPU, 12 G内存, 编译环境为VS 2015.

为验证本文算法可行性, 对图2和图3从提取特征点数、匹配结果以及算法时间上对比算法1(SIFT+k-d树算法+渐入渐出)、算法2(ORB +GMS[11]算法+渐入渐出)和算法3(SIFT +LOGOS[12]算法+渐入渐出). 实验结果如表2所示.

表2 实验数据对比

从表2数据中可以看到, 传统算法从大量的特征点中获取到有限的正确匹配数, 耗时长且匹配准确率低, 大量的错误匹配影响后续计算单应性矩阵. GMS算法与LOGOS算法匹配准确率很高, 但是由于GMS提取的特征点结构简单, 使得检测到过多的特征点, 并且GMS算法需要先使用BF算法暴力匹配, 导致匹配用时过长. 而LOGOS算法需要先训练BOW字典集, 更加耗时. 而本文算法先是提取了相似区域, 在相似区域上提取特征点, 减少特征点的总数目与特征点匹配时间. 并在匹配算法上进一步地剔除不相关特征点, 从有限的特征点数量上获得大量的正确匹配数, 匹配正确率接近GMS算法与LOGOS算法, 并且在特征提取和特征匹配上耗时最短, 虽然最后的加权最佳拼接缝的融合时间较长, 但是总时间相对更短, 并实现了更好的拼接效果. 综合效率、精度以及效果, 本文的算法更具优越性.

此外, 在实际工程应用中, 例如多幅岩石微观薄片图像的拼接, 由于显微镜下的微观图像只能展示局部特征, 实际应用中往往需要将多幅微观图像拼接为一张完整的图像来观察全局的特征, 这涉及到几十张甚至几百张图像的拼接, 以此来验证本文算法. 图9是单幅岩石微观薄片图像, 尺寸为2 448×2 048, 图10是600张岩石微观薄片图像的拼接结果, 尺寸为44 104×45 504, 共25行24列, 从实验结果来看证明了本文算法的有效性. 仅在相似区域提取有效特征点, 可以减少硬件内存资源的浪费, 基于位置与主方向信息的匹配方法可以加快匹配速度, 使得在有限的硬件计算资源条件下实现多幅图像的快速拼接成为可能.

图9 单幅岩石微观薄片图像Fig.9 Single rock micro slice image

图10 600张岩石微观薄片图像的拼接结果

6 结 论

由于SIFT算法提取特征点计算复杂, k-d树算法进行特征匹配时回溯次数过多且存在大量的误匹配. 针对这一现象本文提出一种基于感知哈希与尺度不变特征变换的快速拼接算法. 感知哈希算法通过HASH指纹对比, 快速识别出两幅图像的相似区域. 匹配算法上利用SIFT特征点主方向与位置信息过滤掉不必要的特征点匹配并实现粗过滤. 融合算法采用加权最佳拼接缝算法消除鬼影. 实验结果显示, 本文算法在保证匹配精度的前提下, 耗时更短, 拼接效果更好, 并且在实际应用场景下得到了验证. 但是匹配算法对于旋转过大的图像效果会有降低, 需进一步优化.