一种自适应四叉树分块的图像拼接算法
王元炜;郁梅;姜浩;邵华
【摘 要】Image stitching is a hot topic in computer graphics rearch, and the reprentative As-Projective-As-Possible (APAP) stitching algorithm gments image into uniform blocks to achieve local image warping, which does not take into full account the differences between varying image regions. In order to achieve the tradeoff between the accuracy and the efficiency of image stitching, an image warping algorithm bad on the feature points distribution is propod, which us quadtree to gment image into blocks to achieve local image warping for image stitching. Firstly, the maximum depth of the quadtree is t, and the matching threshold of each image block is estimated according to the number of image matching points. Then, the maximum depth and the matching point threshold is ud to adaptively gment the image into blocks by quadtree. Finally, homography matrices of different image blocks are estimated by Moving Direct Linear Transformation algorithm to complete the stitching. The experimental results show that the
propod algorithm notably improve the accuracy of image stitching, and the speed is much faster than the APAP algorithm, and the quality of the stitched image is ameliorated accordingly.%图像拼接技术是计算机图形学的研究热点, 具有代表性的As-Projective-As-Possible (APAP)算法采用均匀分块法来实现图像拼接的局部映射, 没有充分考虑图像不同区域之间的差异性.为了兼顾图像拼接的精度和效率, 提出了一种基于特征点分布的图像映射算法, 利用四叉树对图像分块来实现图像拼接的局部映射. 首先, 设定四叉树的最大深度, 并根据图像匹配点的总数估计出每个图像块的匹配点阈值; 然后, 利用最大深度和匹配点阈值对图像做自适应四叉树分块; 最后, 对不同的图像块使用移动线性变换估计出单应性矩阵, 依据估计的结果完成图像拼接.实验结果表明, 提出的算法提高了图像拼接的精度, 其速度远大于APAP算法, 并且提升了拼接图像的质量.
【期刊名称】《宁波大学学报（理工版）》
【年(卷),期】内电路2018(031)004
【总页数】7页(P52-58)
周公解梦梦见【关键词】图像拼接;图像映射;投影变换;四叉树
【作 者】梅花三弄歌词王元炜;郁梅;姜浩;邵华
【作者单位】宁波大学 信息科学与工程学院, 浙江 宁波 315211;宁波大学 信息科学与工程学院, 浙江 宁波 315211;南京大学 计算机软件新技术国家重点实验室, 江苏 南京 210023;宁波大学 信息科学与工程学院, 浙江 宁波 315211;宁波大学 信息科学与工程学院, 浙江 宁波 315211
【正文语种】中 文
【中图分类】TN911.73节目的英语
图像拼接是把一组图像拼接成一幅大视场图像的处理过程, 在全景成像、场景理解、摄影测量以及遥感成像等领域得到有效应用[1]. 图像拼接过程通常包含了预处理、配准、映射和融合等步骤[2]. 图像映射是根据图像配准的结果, 利用变换矩阵估计图像间的空间映射关系, 从而实现图像的无缝拼接. 按照变换矩阵的作用区域, 图像映射分为全局映射和局部映射两种映射模型. 全局映射指的是整幅图像使用同一个变换矩阵的方法. Brown等[3]提出了AutoStitch算法, 该算法只使用一个单应性矩阵来完成图像的拼接. 全局映射算法要求图像
的重叠区域近似在同一个平面上, 并且拍摄图像时的相机光心近似重合, 只适合拼接视差很小或没有视差的图像.
为了克服全局映射模型的缺陷, 人们提出了局部映射模型, 局部映射是对图像的不同区域使用不同变换矩阵的方法. Gao等[4]提出了DHW (Dual-Homography Warping)算法, 将图像划分为背景区域和前景区域, 用2个单应性矩阵分别对应于前景区域和背景区域, 提高了图像拼接算法的精度. Lin等[5]提出了SVA (Smoothly Varying Affine)算法, 用多个仿射变换矩阵实现图像的分块映射, 拼接精度进一步提高. Zaragoza等[6]提出了APAP算法, 将图像划分成均匀密集的网格块, 使用移动线性变换(Moving Direct Linear Transformation, MDLT)来估计每个网格块的单应性矩阵. APAP算法能够精确地进行拼接, 可以较好地拼接视差较大的图像.
APAP算法的精度和效率问题也非常值得研究. 本文针对APAP算法的均匀分块引起的时间复杂度过高的问题展开研究, 提出了改进算法. 实验表明, 在保证精度的同时, 本文提出的不均匀分块的图像拼接算法要比APAP算法的效率高得多.
针对APAP算法的分块过多导致速度过慢的问题, 提出一种自适应四叉树分块的图像拼接算
法, 该算法主要包含图像配准、基于匹配点分布的目标图像四叉树分块、目标图像映射和插值、图像融合等步骤.
图像配准包含特征点提取和特征点匹配2个步骤. 特征提取算法种类繁多, 已有的特征提取算法不少于50种[7], 其中SIFT算法[8]和MSER算法表现出极好的性能[9]. SIFT算法具有鲁棒性好, 缩放、旋转、平移不变性以及特征点丰富等特点. 在特征点提取后, 需要进行特征点匹配, 这一过程容易产生误配点, 可以通过随机抽样一致性算法[10]来剔除错误的匹配点对, 该算法鲁棒性好, 在提高精度的同时减少了匹配点对的损失.
在图像映射的过程中, 为了提高精度, APAP算法将图像分割成密集且均匀的矩形块(默认分成100×100个块), 对每个矩形块分别进行单应性矩阵估计, 而单应性矩阵估计复杂且耗时, 这在很大程度上影响了图像拼接的效率. 其改进思路就是尽可能地保留精度的同时减少图像的分块.
单应性矩阵的估计是根据特征匹配点对来进行的. 当匹配点数量多的时候, 为了提高精度, 有必要对图像密集分块; 反之, 当图像的匹配点很少的时候, 即使密集分块也不能提高精度. 此外, 匹配点密集的区域一般纹理复杂、细节信息丰富, 匹配点稀疏的区域一般纹理简单、
正月是几月细节信息较少, 应该对特征点密集的区域做精确的单应性估计, 而对特征点稀疏的区域做较粗略的估计. 因此, 图像分块可以依据匹配点的密度来确定, 在匹配点密度大的区域密集分块, 密度小的区域稀疏分块.
采用四叉树能够实现上述的图像分块思想, 为此, 本文所提出算法描述如下: 首先设定一个四叉树的最大深度De限制四叉树的最大划分深度; 然后设定每个分块内部的匹配点阈值Th, 如果当前块内部的匹配点大于阈值Th, 就对当前块进行四叉树划分, 否则就不再划分, 认为当前块已经划分完成; 根据这个划分规则对图像进行四叉树递归划分, 直到所有图像块内部的匹配点数量小于阈值Th或者该分块对应的四叉树深度达到De时停止划分, 完成图像的分块操作, 算法流程如图1所示. 一幅已知图像的分块是由Th和De确定的, 对匹配点分布比较密集的区域, 由于每个图像块内部的匹配点不超过Th, 该区域的分块就会比较密集; 而在某些匹配点过于密集的图像区域, 仅仅靠Th来自适应划分图像, 又会导致该区域的分块过密, 因此引入参数De来限制图像的最大划分深度, 防止图像的某些区域分块过密.
若采用一棵深度是De的四叉树对图像进行分块, 则这棵树最多可划分的图像块数S为: 人事档案
De只影响极少数的小图像块, 所以De的取值只要在一定范围即可, 一般De取8~10都能很好
满足要求. 每个分块的匹配点阈值Th可以根据匹配点数量来设置, 当匹配点数量很多的时候, 阈值Th应该适当取较大值, 反之当匹配点数量很少的时候, 阈值Th应该取较小值. 研究表明, 对于匹配点数在几百到几千之间的普通图像来说, Th可以设置为1~20, 具体可由实验确定.
快客便利店加盟图像的空间几何坐标变换是建立一幅图像坐标(x,y)与另一幅图像坐标间的变换关系[11]. 常用的变换有相似变换、仿射变换和投影变换. 为了提高精度, 这里选用投影变换来完成图像映射. 对目标图像每一个分块使用一个投影变换矩阵, 将目标图像映射到参考图像平面上去, 以便于后续的图像融合.
假设坐标和坐标分别是参考图像和目标图像的一对匹配点, 这两个点之间的单应性关系可表示为:
式中, 和分别为和对应的齐次坐标, 是的单应性矩阵, 表示向量按比例相等. 将单应性矩阵表示成式(3)的形式后, 非齐次坐标下的匹配点和之间的对应关系表示成:
式中,,,,是坐标和坐标 的坐标分量.
将式(2)变形成, 计算得到:
式中,
在估计单应性矩阵的时候, 可以尽可能利用更多的匹配点信息来减少误差. 式(5)中等式右边的系数矩阵中只有2行是独立的, 选择前2行组成独立系数矩阵, 将所有的匹配点考虑进来, 就可以组成一个的系数矩阵, 根据最小二乘法的思想, 对的求解可以表示成:
式中,是经过归一化后的单位向量; 表示匹配点的总对数;表示第i对匹配点对应的独立系数矩阵. 可以通过奇异值分解来完成对的计算, 的最小奇异值所对应的右奇异向量就是所求的结果. 将向量的各个元素按照式(3)的排列顺序就得到了单应性矩阵的估计值.
实现目标图像局部映射的时候, 可以将目标图像划分成多个图像块, 对每个图像块利用上述估计方法来计算该图像块对应的单应性矩阵. 但是, 研究表明, 单独对每个图像块求取单应性矩阵将会使拼接图像的整体视觉效果变得很差.
为了兼顾图像映射的精度和拼接图像的整体视觉效果, 采用MDLT算法[12]来实现图像映射. MDLT算法的思想类似于移动最小二乘法(Moving Least-Squares, MLS)[13], 将整幅图像的所有匹配点都考虑进来, 根据当前图像块的位置, 对图像的所有匹配点分配相应权重, 从而
乳房炎症哪些症状
完成该图像块的单应性矩阵估计. 匹配点权重是由匹配点到图像块中心点之间的距离决定的, 距离越小权重越大, Zaragoza等[12]提出的MDLT算法选用高斯函数来计算权重, 其计算方法如下:
式中, 表示第对匹配点在当前图像块的权重; 表示当前图像块的中心坐标; 表示目标图像的第对匹配点坐标; 为尺度因子; 为最小权重值, 用以防止某些远离当前图像块的匹配点权重过小.
Lin等[14]提出了另外一种计算权重的方法, 使用学生t-分布函数来代替高斯分布函数, 因为学生t-分布函数比高斯分布函数更加平滑, 可以省略掉最小权重值, 从而具有更好的鲁棒性. 计算式[14]如下:
式中, 是自由度. 与高斯函数类似, 应该在上式中加入尺度因子:
学生t-分布函数与高斯分布函数非常相近, 实际实验中, 两种计算方法所得到的实验结果相差不大, 但是高斯分布函数的计算速度要比学生t-分布函数的计算速度快很多, 这里仍然采用高斯函数来计算权重.
图像映射分为正向映射和反向映射, 为了防止映射后的图像出现空洞, 实际经常采用反向映射的方法[11]. 在图像反向映射的过程中, 利用单应性矩阵计算出的图像位置可能不是整数, 必须利用其周围整数像素位置通过插值技术得到. 常用的插值算法有最邻近插值法、双线性插值法和双三次插值法, 这里使用最邻近插值法.
目标图像完成投影变换后, 与参考图像近似在同一个平面上, 但与参考图像之间仍然存在明暗差异、拼接缝、鬼影等问题, 这就需要图像融合技术. 本文主要研究的是图像拼接中的图像映射问题, 为了便于跟APAP等算法做比较分析, 这里直接采用简单的直接平均法[15]做图像的融合.
