发布时间: 2018-07-16 摘要点击次数: 全文下载次数: DOI: 10.11834/jig.170653 2018 | Volume 23 | Number 7 图像处理和编码

1. 上海交通大学图像通信与网络工程研究所, 上海 200240;
2. 上海市数字媒体处理与传输重点实验室, 上海 200240
 收稿日期: 2017-12-22; 修回日期: 2018-02-01 基金项目: 国家自然科学基金项目(61471234, 61527804);国家科技支撑计划项目(2015BAK05B03) 第一作者简介: 何川, 1993年生, 男, 上海交通大学信息与通信工程专业硕士研究生, 主要研究方向为多视点图像配准。E-mail:tribody@sjtu.edu.cn. 中图法分类号: TP301.6 文献标识码: A 文章编号: 1006-8961(2018)07-0973-11

# 关键词

Mesh-based image stitching algorithm with linear structure protection
He Chuan, Zhou Jun
1. Institute of Image Communication and Network Engineering, Shanghai Jiao Tong University, Shanghai 200240, China;
2. Key Laboratory of Digital Media Processing and Transform, Shanghai 200240, China
Supported by: National Science Foundation of China(61471234, 61527804);National Key Technology Research and Development Program of the Ministry of Science and Technology of China(2015BAK05B03)

# Abstract

Objective The image registration method based on mesh deformation can handle some parallax in the overlapping area of input images and can adapt to more complex scenarios where the scenery is not in the same plane.A new mesh-based image stitching with linear structure protection (MISwLP) is proposed.This algorithm applies constraints to the lines extracted from images to protect them from being distorted by the mesh deformation process, thus obtaining natural panoramas with reduced distortion. Method MISwLP is based on mesh deformation.Images are meshed with a set of vertices, and image deformation is guided by the indexed vertices.The algorithm can be implemented with four steps.The first step is called APAP (As-Projective-As-Possible Image Stitching with Moving DLT) pre-registration.The APAP algorithm is applied to align the images, and the feature matching pairs obtained by the APAP algorithm can be used to obtain all the vertex matching pairs in the overlapped area of the image matching pairs, which are called matching points.These matching points are distributed evenly and can be used to obtain good alignment capability for the mesh optimization model.The second step is called global similarity estimation.The relative 2D rotation angle and the relative scale between two images are estimated in this step.Then, a similarity transform between the two images can be constructed.In the third step, a mesh optimization model is established for the input vertices of the images.The mesh optimization process is implemented in two stages.In the first stage, the energy function includes three terms, namely, the alignment, local similarity, and global similarity terms, and the original vertices are used as the input for this function.It is solved by the least-squares conjugate gradient method.The first stage aims to align the images.Then, the outputs of the first stage are used as the input vertices of the second stage.In the second stage, a new term called line protection is added for further optimization.The lines are extracted by the LSD algorithm with a threshold or user-guided interface and then sampled across the grid.The line protection term constrains the sample points in a straight line.The optimization solution is computed with a sparse matrix effectively.At this time, the distorted lines in the first stage of this step are straightened.In the fourth step, a texture mapping method is applied by affine transforming the input grids into the output grids.All images are blended with a linear blending method. Result The performance of MISwLP is verified using images captured from different sceneries by handheld devices, such as mobile phones and digital cameras, and several open datasets.The scenes include urban and nature sceneries.MISwLP can handle more complicated image stitching tasks, in which the scenery consists of two planes, than image-stitching algorithms, which use only one global holography, such as AutoStitch.Furthermore, MISwLP produces a natural stitching result and reduced projective distortion.In addition, MISwLP outperforms several state-of-the-art methods, such as SPHP (Shape-Preserving Half-Projective Warps for Image Stitching), APAP, and NISwGSP (Natural Image Stitching with the Global Similarity Prior).These algorithms use similarity transform to protect the non-overlapping area from projective distortion.Consequently, inconsistency is introduced between the overlapped and non-overlapped areas.The human eyes can perceive the destruction of certain geometry structures of the transitional area.MISwLP handles this problem with a line protection term and provides a good result with only a few geometry distortions.The proposed method works especially well for urban sceneries that contain many linear structures.For sceneries with no evident geometry, a user-guided auxiliary method is provided for selecting lines to protect.MISwLP is based on the NISwGSP algorithm, but the experiments show that their time complexities are nearly the same. Conclusion The performance of the proposed method is superior to those of state-of-the-art image-stitching methods.MISwLP protects the linear structure in the image stitching process, thereby providing a good stitching result with no geometry and projective distortions.Therefore MISwLP has good application value.

# Key words

image stitching; mesh deformation; lines protection; energy function; optimization; least-squared conjugate gradient method; projective distortion

# 0 引言

1) 图像重叠区域必须尽量处于同一个平面, 画面整体最好处于同一个平面;

2) 每次拍摄时, 相机光心近乎重合。

Gao等人[4]率先提出了基于双平面假设的图像拼接算法, 即假设所获图像近似存在背景和地面两个基本平面, 通过分别计算两个平面的单应变换, 而更好的配准图像。Lin等人[5]使用平滑变化的仿射变换对齐图像, 能够接受一定的视差。Zaragoza等人[6]率先使用网格优化模型, 将图像划分为密集网格, 以网格中心到特征点的距离为权重, 为每个网格计算一个单应矩阵, 使用局部单应性对齐图像, 并给出了一套高效的计算方法Moving DLT。网格优化模型是一套非常灵活的图像优化框架, 基于网格变形的图像优化算法, 能够对图像做更精细化的调整。考虑到点特征匹配的不可靠性(比如周期重复纹理等造成的误匹配), Li和Joo等人[7-8]在提出了一种结合点特征和线特征的图像配准方法。Zhang等人[9]借鉴视频去抖方法的优化项, 并结合了缝合线搜索算法[10], 提高了大视差场景下的拼接性能[11]。Lin等人[12]提出使用缝合线引导的局部单应对齐方法(SEAGULL), 通过super pixel[13]聚类产生初始化的一组局部单应假设, 然后通过计算缝合线生成一系列的拼接候选结果, 通过评估缝合效果选择最终结果。在考虑使用更好地几何变换模型对齐图像的同时, 越来越多的算法开始关注保护原图片的拍摄视角, 减少投影失真, 从而获得观感更加自然的拼接效果。Chang等人[14]借鉴图像缩放中的形状保护方法, 使得非重叠区域到重叠区域, 由相似变换逐渐过渡到透视变换, 既保证了重叠区域的对齐性, 又保证了非重叠区域产生较少的投影失真。Lin等人[15]使用单应插值的方式控制单应渐进变换, 并提出了一种自动选择最小旋转角度的全局相似变换的方法, 减小图片之间的旋转角度, 能够进一步提高图片自然观感。Chen等人[16]使用APAP初始化网格, 并同时利用局部相似项和全局相似项约束网格变形, 同样减小了投影失真, 多图拼接效果提升较大。Li和Xiang等人[17-18]的工作同样强调了对非重叠区域的保护。

# 1 NISwGSP算法简介

NISwGSP算法采用网格优化模型。算法总体流程可分解为四大步骤:

1) APAP预配准;

2) 全局相似参数估计;

3) 网格优化;

4) 图像合成。

# 2 MISwLP算法

MISwLP算法流程如图 4所示, 第1步APAP预配准和第2步全局相似估计同NISwGSP算法一致, 得到网格顶点匹配对和全局相似变换。网格优化分为两个阶段, 第1阶段同原算法相同, 不考虑直线约束项, 第2阶段优化加入直线约束项, 得到最终的顶点集。

# 2.1 网格优化模型

 ${\mathit{\boldsymbol{S}}_\mathit{\boldsymbol{I}}} = \{ {\mathit{\boldsymbol{I}}_1}, {\mathit{\boldsymbol{I}}_2}, \ldots, {\mathit{\boldsymbol{I}}_N}\}$

 $\mathit{\boldsymbol{J}} = \{ ({\mathit{\boldsymbol{I}}_i}, {\mathit{\boldsymbol{I}}_j})|{\mathit{\boldsymbol{I}}_i}{\rm{match}}{\mathit{\boldsymbol{I}}_j}\} ;i, j \in {\rm{ }}\left\{ {1, \ldots, N} \right\}$

 $\mathit{\boldsymbol{W}}_k^{ij} = \left[{\begin{array}{*{20}{l}} \ldots &{w_1^{ij}}&0& \ldots &{w_2^{ij}}&0& \ldots &{w_3^{ij}}&0& \ldots &{w_4^{ij}}&0& \ldots \\ \ldots &0&{w_1^{ij}}& \ldots &0&{w_2^{ij}}& \ldots &0&{w_3^{ij}}& \ldots &0&{w_4^{ij}}& \ldots \end{array}} \right]$ (4)

# 2.3 局部相似项约束${E_{ls}}(\mathit{\boldsymbol{\hat V}})$

 $\begin{array}{l} {E_{ls}}(\mathit{\boldsymbol{\hat V}}) = {\sum\limits_{I = 1}^N {\sum\limits_{{\mathit{\boldsymbol{e}}_j}^i \in {\mathit{\boldsymbol{E}}_i}} {\left\| {{\mathit{\boldsymbol{e}}_j}^i\prime- \mathit{\boldsymbol{S}}_j^i{\mathit{\boldsymbol{e}}_j}^i} \right\|} } ^2}\\ {\mathit{\boldsymbol{e}}_j}^i\prime = \mathit{\tilde v}_k^i- {{\mathit{\tilde v}}^i}_j, \mathit{\boldsymbol{e}}_j^i = v_k^i- v_j^i\\ \mathit{\boldsymbol{S}}_j^i = \left[{\begin{array}{*{20}{c}} {c({\mathit{\boldsymbol{e}}_j}^i)}&{s({\mathit{\boldsymbol{e}}_j}^i)}\\ {-s({\mathit{\boldsymbol{e}}_j}^i)}&{c({\mathit{\boldsymbol{e}}_j}^i)} \end{array}} \right] \end{array}$ (5)

# 2.4 全局相似项约束${E_{gs}}(\mathit{\boldsymbol{\hat V}})$

 ${E_{gs}}\left( {\mathit{\boldsymbol{\hat V}}} \right) = \\ \sum\limits_{i = 1}^N {\sum\limits_{{\mathit{\boldsymbol{e}}_j}^i \in {\mathit{\boldsymbol{E}}_i}} {w({\mathit{\boldsymbol{e}}_j}^i)} \left[ \begin{array}{l} {(c({\mathit{\boldsymbol{e}}_j}^i) - {s_i}{\rm{cos}}{\theta _i})^2} + \\ {\rm{ }}{(s({\mathit{\boldsymbol{e}}_j}^i) - {s_i}{\rm{sin}}{\theta _i})^2} \end{array} \right]}$ (6)

# 3.2 算法时间复杂度分析

Table 1 Algorithm runtime comparison

 数据集(图片数量) NISwGSP/s MISwLP/s Park(2) 11.492 8 13.493 1 Building(3) 22.459 8 25.869 2 Lake(4) 22.695 3 31.869 2 Garden(5) 77.756 9 89.018 8 Eitan office(6) 19.904 8 24.378 2 SantaMaria-all(8) 255.704 7 269.782 6 Playroom-all(10) 49.532 2 62.013 3 PalazzoPubblico2(11) 243.734 4 267.987 0 SienaCathedralLibrary(14) 804.434 4 838.648 7 Grail(17) 55.350 2 73.436 5 Times Square(20) 202.776 0 231.821 5 Church(32) 287.297 3 338.513 0 Atrium(34) 415.666 9 466.522 2

# 3.3 算法效果对比

NISwGSP在对齐和多图拼接的场景下优于其他算法, 通过结合直线结构保护, 能得到较好的拼接结果。和APAP算法以及SPHP等算法相比, MISwLP更是具有明显的优势, 图 10图 11展示了在笔者自己采集的照片上, NISwGSP算法和本文MISwLP算法的拼接效果比较。

# 参考文献

• [1] Brown M, Lowe D G. Automatic panoramic image stitching using invariant features[J]. International Journal of Computer Vision, 2007, 74(1): 59–73. [DOI:10.1007/s11263-006-0002-3]
• [3] Igarashi T, Igarashi Y. Implementing as-rigid-as-possible shape manipulation and surface flattening[J]. Journal of Graphics, Gpu, and Game Tools, 2009, 14(1): 17–30. [DOI:10.1080/2151237x.2009.10129273]
• [4] Gao J H, Kim S J, Brown M S. Constructing image panoramas using dual-homography warping[C]//Proceedings of 2011 IEEE Conference on Computer Vision and Pattern Recognition. Springs, Colorado, USA: IEEE, 2011: 49-56. [DOI:10.1109/cvpr.2011.5995433]
• [5] Lin W Y, Liu S Y, Matsushita Y, et al. Smoothly varying affine stitching[C]//Proceedings of 2011 IEEE Conference on Computer Vision and Pattern Recognition. Colorado Springs, USA: IEEE, 2011: 345-352. [DOI:10.1109/cvpr.2011.5995314]
• [6] Zaragoza J, Chin T J, Brown M S, et al. As-projective-as-possible image stitching with moving DLT[C]//Proceedings of 2013 IEEE Conference on Computer Vision and Pattern Recognition. Portland, OR, USA: IEEE, 2013: 2339-2346. [DOI:10.1109/CVPR.2013.303]
• [7] Li S W, Yuan L, Sun J, et al. Dual-feature warping-based motion model estimation[C]//Proceedings of 2015 IEEE International Conference on Computer Vision. Santiago, Chile: IEEE, 2015: 4283-4291. [DOI:10.1109/iccv.2015.487]
• [8] Joo K, Kim N, Oh T H, et al. Line meets as-projective-as-possible image stitching with moving DLT[C]//Proceedings of 2015 IEEE International Conference on Image Processing. Québec City, Canada: IEEE, 2015: 1175-1179. [DOI:10.1109/icip.2015.7350985]
• [9] Liu F, Gleicher M, Jin H L, et al. Content-preserving warps for 3D video stabilization[C]//Proceedings of 2009 ACM SIGGRAPH. New Orleans, Louisiana, USA: ACM, 2009: #44. [DOI:10.1145/1576246.1531350]
• [10] Gao J H, Li Y, Chin T J, et al. Seam-driven image stitching[C]//Proceedings of 2013 EUROGRAPHICS. Girona, Spain: EUROGRAPHICS, 2013. [DOI:10.2312/conf/eg2013/short/045-048]
• [11] Zhang F, Liu F. Parallax-tolerant image stitching[C]//Proceedings of 2014 IEEE Conference on Computer Vision and Pattern Recognition. Columbus, OH, USA: IEEE, 2014: 3262-3269. [DOI:10.1109/cvpr.2014.423]
• [12] Lin K M, Jiang N J, Cheong L F, et al. SEAGULL: seam-guided local alignment for parallax-tolerant image stitching[C]//Proceedings of the 14th European Conference on Computer Vision-ECCV 2016. Amsterdam, The Netherlands: Springer, 2016: 370-385. [DOI:10.1007/978-3-319-46487-9_23]
• [13] Achanta R, Shaji A, Smith K, et al. SLIC superpixels compared to state-of-the-art superpixel methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(11): 2274–2282. [DOI:10.1109/tpami.2012.120]
• [14] Chang C H, Sato Y, Chuang Y Y. Shape-preserving half-projective warps for image stitching[C]//Proceedings of 2014 IEEE Conference on Computer Vision and Pattern Recognition. Columbus, Ohio, USA: IEEE, 2014: 3254-3261. [DOI:10.1109/cvpr.2014.422]
• [15] Lin C C, Pankanti S U, Ramamurthy K N, et al. Adaptive as-natural-as-possible image stitching[C]//Proceedings of 2015 IEEE Conference on Computer Vision and Pattern Recognition. Boston, Massachusetts, USA: IEEE, 2015: 1155-1163. [DOI:10.1109/CVPR.2015.7298719]
• [16] Chen Y S, Chuang Y Y. Natural image stitching with the global similarity prior[C]//Proceedings of the 14th European Conference on European Conference on Computer Vision. Amsterdam, Netherlands: Springer, 2016: 186-201. [DOI:10.1007/978-3-319-46454-1_12]
• [17] Li N, Xu Y F, Wang C. Quasi-homography warps in image stitching[J]. IEEE Transactions on Multimedia, 2017. [DOI:10.1109/tmm.2017.2771566]
• [18] Xiang T Z, Xia G S, Bai X, et al. Image stitching by line-guided local warping with global similarity constraint[J]. arXiv: 1702. 07935, 2017.
• [19] Yao D, Zhou J, Xue Z. Homography matrix genetic consensus estimation algorithm[C]//Proceedings of 2010 International Conference on Audio Language and Image Processing. Shanghai, China: IEEE, 2010: 1139-1143. [DOI:10.1109/icalip.2010.5685084]