发布时间: 2019-01-16 摘要点击次数: 全文下载次数: DOI: 10.11834/jig.180343 2019 | Volume 24 | Number 1 图像处理和编码

1. 华东师范大学计算机科学技术系, 上海 200062;
2. 中国银行软件中心上海分中心, 上海 201201
 收稿日期: 2018-06-05; 修回日期: 2018-08-14 第一作者简介: 樊逸清, 1993年生, 女, 硕士研究生, 主要研究方向为图像处理、特征匹配。E-mail:51164500043@stu.ecnu.edu.cn;楚东东, 男, 硕士, 主要研究方向为图像拼接。E-mail:dozai@sina.cn. 中图法分类号: TP391 文献标识码: A 文章编号: 1006-8961(2019)01-0023-08

# 关键词

Parallax image stitching using line-constraint moving least squares
Fan Yiqing1, Li Haisheng1, Chu Dongdong2
1. Department of Computer Science and Technology, East China Normal University, Shanghai 200062, China;
2. Software Center Shanghai Branch, Bank of China, Shanghai 201201, China

# Abstract

Objective Image alignment is a key factor in assessing stitching performance. Image deformation is a critical step of the alignment model for parallax image stitching and directly determines the alignment quality. Accurately aligning all points in an overlapping region of parallax images is difficult. Thus, an alignment strategy that can produce visually satisfying stitching results must be developed. Recent state-of-the-art stitching methods practically combine homography with content-preserving warping. Either homography is first used to pre-align two images and is followed by content-preserving warping to refine alignment, or the mesh deformation is globally optimized by solving an energy function, which is a weighting linear combination of homography and content-preserving warping. Both approaches commonly use homography in the aligning phase and therefore easily produce perspective distortion. At the same time, these approaches possibly misalign the object edges of images with several dominant structural objects. To address these problems, this paper presented a novel stitching method that combines homography, deformation using moving least squares (MLS), and line constraint. The deformation method based on MLS has an interpolation property and can therefore accurately align matching feature points. However, this deformation method may distort structural regions; thus a line constraint item was added to the deformation model to preserve the structure. Method To attain a clear depiction, we considered a two-image stitching as an example. The two input images are called the target and reference images, respectively, and are denoted by $\mathit{\boldsymbol{T}}$ and $\mathit{\boldsymbol{R}}$. First, feature detection and matching estimation were conducted using SIFT and RANSAC, followed by distance similarity to check the matching accuracy of the feature points. The homography (denoted by $\mathit{\boldsymbol{H}}$) with the best geometric fit was selected. Then, $\mathit{\boldsymbol{H}}$ was applied to the target image $\mathit{\boldsymbol{T}}$, and the transformed image was denoted as ${\mathit{\boldsymbol{T}}_H}$. Afterward, the two group images ($\mathit{\boldsymbol{T}}$, $\mathit{\boldsymbol{R}}$) and (${\mathit{\boldsymbol{T}}_H}$, $\mathit{\boldsymbol{R}}$) were aligned using a line constraint MLS. To eliminate perspective distortion in the deformation image, affine transformation was used in MLS. However, a simple affine transformation was insufficient to handle the parallax. Thus, an additional pair of images (${\mathit{\boldsymbol{T}}_H}$, $\mathit{\boldsymbol{R}}$) was processed as a candidate stitching result for the pair of images ($\mathit{\boldsymbol{T}}$, $\mathit{\boldsymbol{R}}$). The test experiments revealed that many examples obtained a more natural stitching result when only affine transformation rather than the composite transformation of homography and affine transformation was applied, implying that the alignment between $\mathit{\boldsymbol{T}}$ and $\mathit{\boldsymbol{R}}$ was better than that between ${\mathit{\boldsymbol{T}}_H}$ and $\mathit{\boldsymbol{R}}$. Taking the deformation from the target image $\mathit{\boldsymbol{T}}$ to the reference image $\mathit{\boldsymbol{R}}$ as an example, the line constraint MLS was outlined as follows. First, the four corner points of $\mathit{\boldsymbol{T}}$ were deformed to the coordinate system of $\mathit{\boldsymbol{R}}$ by using matching feature points as control points based on MLS. Then, we deformed the remaining points on the four border lines (top, bottom, left, and right boundaries) of $\mathit{\boldsymbol{T}}$ by using line constraint MLS. Here, the line constraint was constructed by preserving the relative position of each point of a border line, based on which a deformation objective function was developed. Similarly, we handled the internal points of $\mathit{\boldsymbol{T}}$ by using vertical and horizontal grid lines as constraint conditions, and the vertical and horizontal grid lines are consisted of the constraint lines of their intersection point. Finally, the quality of each alignment was evaluated, and the best one was chosen to blend them. In the overlapping regions, the max-flow min-cut algorithm was used to find the best stitching seam-cut of two alignments and assess the alignment quality along the seam-cut. The assessment of the alignment quality mainly considered the color and structural differences between overlapping regions of two images, and the structure was reflected by a gradient. Then, feathering approach was utilized to blend the two images of the best alignment. Result To test our stitching algorithm, 23 pairs of pictures, which cover commonly seen natural and man-made scenes, were captured. In addition, we conducted several experiments on publicly published data provided by recent related works. The experimental results demonstrated that the alignment accuracy of our method exceeded 95%, and the ratio of perspective distortion was lower than 17%. Compared with recent state-of-the-art methods, our method's alignment accuracy was higher by 3%, and the ratio of perspective distortion was lower by 73%. Therefore, our method exhibits a better performance in handling image stitching with a large parallax, and the stitching result is authentic and natural. Conclusion This paper presented a hybrid transformation for aligning two images that combines line constraint with MLS. In addition, an alignment quality evaluation rule was introduced by computing the weighted differences of the points along the stitching seam-cut and the remaining points in the overlapping region. As the proposed method can balance alignment accuracy and structure preservation, it can address the misalignment issues easily caused by current stitching approaches for parallax images and effectively reduce stitching artifacts, such as ghosting and distortion.

# Key words

image alignment; parallax image; line constraint; moving least squares; image stitching; max-flow min-cut

# 0 引言

1) 整体2D变换。文献[8-10]是基于SIFT特征的拼接工作，而曹世翔等人[11]则是利用边缘特征点进行配准，以减少计算复杂性。Brown等人[8]应用一个最佳单应变换进行图像配准。Gao等人[9]提出了双单应变换的配准模型，能够处理远平面和背景平面占优的图像。基于单应变换的拼接缝评估[10]首先计算多个候选单应变换，然后评估每个单应变换对应的配准质量，选择最好的那个单应变换作为配准模型。这些方法可以很好地处理相机中心固定拍摄的或场景近似平面的图像，但是不能胜任一般视差图像的配准。

2) 空间变化的变形。Lin等人[12]提出了逐点变化的连续仿射变换的图像配准模型。由于仅使用仿射变换，对于透视感强的图像的配准不够理想。Zaragoza等人[13]提出了运动直接线性变换来配准图像，该方法与运动最小二乘法的变形方法[14]类似，只是用单应变换代替仿射变换。与整体2D变换相比，这类方法灵活度大，能够产生更好的配准结果，但是容易产生透视和几何扭曲现象。

3) 上述两种变换的组合方法。一般先使用单应变换预配准图像，然后应用内容或特征保持的变形微调匹配特征点之间的配准。2014年Zhang等人[15]把单应变换和内容保持的变形结合起来，提出了一种混合配准模型。随后，2016年Lin等人[16]提出了另一种组合方法：先把特征点分成若干组，利用每一组特征点或者它们组合而成的特征点组生成若干局部单应变换初步配准图像，然后应用特征加权和结构保持的变形迭代地修正每个局部配准，评估每个配准的拼接缝合的质量，选取最优的拼接。这两种方法均用变形前后特征点在网格内的相对位置保持不变这一约束对预配准进行局部修正，尽可能地配准匹配特征点附近的区域。这种组合方法的拼接性能整体上优于以往的方法，但是对单应变换预配准时产生的特征点的配准误差消除有限，仍有可能产生局部错位现象。

# 1 线约束运动最小二乘法

1) 两幅源图像分别称为目标图像和参考图像，记为$\mathit{\boldsymbol{T}}$$\mathit{\boldsymbol{R}} 2) 每幅图像均匀分割成m(行)×n(列)个网格，{\mathit{\boldsymbol{v}}_{kj}}(k=0, 1, …, m; j=0, 1, …, n)是网格顶点，{\mathit{\boldsymbol{\tilde v}}_{kj}}$${\mathit{\boldsymbol{v}}_{kj}}$变换后的顶点。$\mathit{\boldsymbol{T}}$的特征点集记为{${\mathit{\boldsymbol{p}}_i}$}，$\mathit{\boldsymbol{R}}$中与之匹配的点集记为{${\mathit{\boldsymbol{q}}_i}$}，即点${\mathit{\boldsymbol{p}}_i}$的对应点是${\mathit{\boldsymbol{q}}_i}$，其中$i$是特征点的索引。

1) 对于图像$\mathit{\boldsymbol{T}}$的四个角点${\mathit{\boldsymbol{v}}_{kj}}$ ($k=0, m; j=0, n$)，构造一个仿射变换${F_v}(\mathit{\boldsymbol{p}}){\rm{ }} = \mathit{\boldsymbol{p}}{\mathit{\boldsymbol{M}}_v} + {\mathit{\boldsymbol{T}}_v}$，其中$\mathit{\boldsymbol{p}}$${\mathit{\boldsymbol{T}}_v}是行向量，{\mathit{\boldsymbol{M}}_v}是2×2的矩阵，把它们变换到\mathit{\boldsymbol{R}}图像坐标系中。{F_v}通过如下的优化问题求解，即  {\rm{arg}}\;\mathop {{\rm{min}}}\limits_{{F_v}} \sum\limits_i {{w_i}} {\left| {{F_v}({\mathit{\boldsymbol{p}}_i})-{\mathit{\boldsymbol{q}}_i}} \right|^2} (1) 式中，{w_i} = 1/{\left| {{\mathit{\boldsymbol{p}}_i}-\mathit{\boldsymbol{v}}} \right|^2}。这是个经典的二次优化问题，其解为  \begin{array}{l} {\mathit{\boldsymbol{M}}_v} = {({\sum\limits_i {({\mathit{\boldsymbol{p}}_i}-{\mathit{\boldsymbol{p}}_*})} ^{\rm{T}}}{w_i}({\mathit{\boldsymbol{p}}_i}-{\mathit{\boldsymbol{p}}_*}))^{-1}}\cdot\\ \;\;\;\;\;\;\;\;\;\;\sum\limits_i {{{({\mathit{\boldsymbol{p}}_i} - {\mathit{\boldsymbol{p}}_*})}^{\rm{T}}}} {w_i}({\mathit{\boldsymbol{q}}_i} - {\mathit{\boldsymbol{q}}_*})\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\mathit{\boldsymbol{T}}_v} = {\mathit{\boldsymbol{q}}_*} - {\mathit{\boldsymbol{p}}_*}{\mathit{\boldsymbol{M}}_v} \end{array} 式中, {\mathit{\boldsymbol{p}}_*}$${\mathit{\boldsymbol{q}}_*}$为加权中心

 ${\mathit{\boldsymbol{p}}_*} = \frac{{\sum\limits_i {{w_i}{\mathit{\boldsymbol{p}}_i}} }}{{\sum\limits_i {{w_i}} }}, \;{\mathit{\boldsymbol{q}}_*} = \frac{{\sum\limits_i {{w_i}{\mathit{\boldsymbol{q}}_i}} }}{{\sum\limits_i {{w_i}} }}$

2) 对于$\mathit{\boldsymbol{T}}$的上、下和左、右4条边界线上的顶点，同样用仿射变换${F_v}$变形到参考图像坐标系中，但求解${F_v}$的能量函数有所不同，增加了保持结构的约束项

 $\begin{array}{l} {\rm{arg}}\;\mathop {{\rm{min}}}\limits_{{F_v}} \sum\limits_i {{w_i}} {\left| {{F_v}({\mathit{\boldsymbol{p}}_i})-{\mathit{\boldsymbol{q}}_i}} \right|^2} + \\ {w_{\rm{l}}}{\left| {{F_v}\left( v \right)-u{{\mathit{\boldsymbol{\tilde v}}}_{\rm{s}}}-\left( {1 - u} \right){{\mathit{\boldsymbol{\tilde v}}}_{\rm{e}}}} \right|^2} \end{array}$ (2)

 $\begin{array}{l} {\rm{arg}}\;\mathop {{\rm{min}}}\limits_{{F_v}} \sum\limits_i {{w_i}} {\left| {{F_v}({\mathit{\boldsymbol{p}}_i})-{\mathit{\boldsymbol{q}}_i}} \right|^2} + \\ {w_{{\rm{hl}}}}{\left| {{F_v}\left( \mathit{\boldsymbol{v}} \right)-u{{\mathit{\boldsymbol{\tilde v}}}_{{\rm{hs}}}}-\left( {1 - u} \right){{\mathit{\boldsymbol{\tilde v}}}_{{\rm{he}}}}} \right|^2} + \\ {w_{{\rm{vl}}}}{\left| {{F_v}\left( \mathit{\boldsymbol{v}} \right) - \lambda {{\mathit{\boldsymbol{\tilde v}}}_{{\rm{vs}}}} - \left( {1 - \lambda } \right){{\mathit{\boldsymbol{\tilde v}}}_{{\rm{ve}}}}} \right|^2} \end{array}$ (3)

 $E = \alpha \frac{{\sum\limits_{v \in \mathit{\boldsymbol{ \boldsymbol{\varOmega} }}} {D\left( \mathit{\boldsymbol{v}} \right)} }}{{\left| \mathit{\boldsymbol{ \boldsymbol{\varOmega} }} \right|}} + \left( {1-\alpha } \right)\frac{{\sum\limits_{v \in \mathit{\boldsymbol{ \boldsymbol{\overline \varOmega} }} } {D\left( \mathit{\boldsymbol{v}} \right)} }}{{\mathit{\boldsymbol{ \boldsymbol{\overline \varOmega} }} }}$ (5)

# 3 局部配准下结构保持的拼接算法

1) 检测目标和参考图像$\mathit{\boldsymbol{T}}$$\mathit{\boldsymbol{R}}的SIFT特征点，用RANSAC算法筛选准确的匹配特征点对，随后，用距离相似性[17]进一步去除错误的匹配点对； 2) 用筛选出来的所有匹配特征点计算一个最佳单应矩阵\mathit{\boldsymbol{H}}, 用\mathit{\boldsymbol{H}}$$\mathit{\boldsymbol{T}}$进行单应变换，变换后的图像记为${\mathit{\boldsymbol{T}}_H}$

3) 以$\mathit{\boldsymbol{T}}$$\mathit{\boldsymbol{R}}以及{\mathit{\boldsymbol{T}}_H}$$\mathit{\boldsymbol{R}}$的匹配特征点对作为控制点和变换后的对应位置，应用线约束运动最小二乘法变形$\mathit{\boldsymbol{T}}$${\mathit{\boldsymbol{T}}_H}，分别记为{\mathit{\boldsymbol{T}}^W}$${\mathit{\boldsymbol{T}}_H}^W$

4) 在${\mathit{\boldsymbol{T}}^W}$$\mathit{\boldsymbol{R}}以及{\mathit{\boldsymbol{T}}_H}^W$$\mathit{\boldsymbol{R}}$的重叠区域分别构建网络流模型，寻找最佳拼接缝，并用第2节的方法进行评估，选取配准最好的那组图像进行融合拼接。

# 4 实验结果和讨论

Table 1 Alignment accuracy on the picture libraries

 方法 配准精度 自拍图库 文献[15]图库 Photoshop 0.826 — PTIS — 0.943 SEAGULL — 0.943 本文 0.956 0.971 注：“—”表示无测试结果。

# 参考文献

• [1] Szeliski R. Image alignment and stitching:a tutorial[J]. Foundations and Trends in Computer Graphics and Vision, 2006, 2(1): 1–104. [DOI:10.1561/0600000009]
• [2] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91–110. [DOI:10.1023/b:visi.0000029664.99615.94]
• [3] Fischler M A, Bolles R C. Random sample consensus:a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381–395. [DOI:10.1145/358669.358692]
• [4] Brown M, Szeliski R, Winder S. Multi-image matching using multi-scale oriented patches[C]//Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego, CA: IEEE, 2005: 510-517.[DOI: 10.1109/cvpr.2005.235]
• [5] McLauchlan P F, Jaenicke A. Image mosaicing using sequential bundle adjustment[J]. Image and Vision Computing, 2002, 20(9-10): 751–759. [DOI:10.1016/s0262-8856(02)00064-1]
• [6] Pérez P, Gangnet M, Blake A. Poisson image editing[J]. ACM Transactions on Graphics, 2003, 22(3): 313–318. [DOI:10.1145/882262.882269]
• [7] Gu Y, Zhou Y, Ren G, et al. Image stitching by combining optimal seam and multi-resolution fusion[J]. Journal of Image and Graphics, 2017, 22(6): 842–851. [谷雨, 周阳, 任刚, 等. 结合最佳缝合线和多分辨率融合的图像拼接[J]. 中国图象图形学报, 2017, 22(6): 842–851. ] [DOI:10.11834/jig.160638]
• [8] 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]
• [9] Gao J H, Kim S J, Brown M S. Constructing image panoramas using dual-homography warping[C]//Proceedings of CVPR 2011. Colorado Springs, CO, USA, USA: IEEE, 2011: 49-56.[DOI: 10.1109/cvpr.2011.5995433]
• [10] Gao J H, Li Y, Chin T J, et al. Seam-driven image stitching[C]//Proceedings of EuroGraphics. The Eurographics Association, 2013: 45-48.[DOI: 10.2312/conf/EG2013/short/045-048]
• [11] Cao S X, Jiang J, Zhang G J, et al. Multi-scale image mosaic using features from edge[J]. Journal of Computer Research and Development, 2011, 48(9): 1788–1793. [曹世翔, 江洁, 张广军, 等. 边缘特征点的多分辨率图像拼接[J]. 计算机研究与发展, 2011, 48(9): 1788–1793. ]
• [12] Lin W Y, Liu S Y, Matsushita Y, et al. Smoothly varying affine stitching[C]//Proceedings of CVPR 2011. Colorado Springs, CO, USA, USA: IEEE, 2011: 345-352.[DOI: 10.1109/cvpr.2011.5995314]
• [13] 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]
• [14] Schaefer S, McPhail T, Warren J. Image deformation using moving least squares[J]. ACM Transactions on Graphics, 2006, 25(3): 533–540. [DOI:10.1145/1141911.1141920]
• [15] 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]
• [16] Lin K M, Jiang N J, Cheong L F, et al. SEAGULL: Seam-guided local alignment for parallax-tolerant image stitching[C]//Leibe B, Matas J, Sebe N, et al. Computer Vision-ECCV 2016. ECCV 2016. Cham: Springer, 2016: 370-385.[DOI: 10.1007/978-3-319-46487-9_23]
• [17] Chu D D, Li H S. Parallax image stitching based on moving least square method[J]. Computer Applications and Software, 2017, 34(8): 231–235. [楚东东, 李海晟. 基于移动最小二乘法的视差图像拼接[J]. 计算机应用与软件, 2017, 34(8): 231–235. ] [DOI:10.3969/j.issn.1000-386x.2017.08.041]