[人工智能]【论文精读】Parallax-tolerant Image Stitching

图像拼接系列相关论文精读

1. Seam Carving for Content-Aware Image Resizing
2. As-Rigid-As-Possible Shape Manipulation
3. Adaptive As-Natural-As-Possible Image Stitching
4. Shape-Preserving Half-Projective Warps for Image Stitching
5. Seam-Driven Image Stitching

论文题目：允许视差的图像拼接
论文链接：Parallax-tolerant Image Stitching

关键词：大视差，种子特征点，CPW，接缝

摘要

视差处理是图像拼接领域一项有挑战性的任务。在输入图片的整个重叠区域不需要完美配准的情况下，本文提出了一个局部拼接方式来解决视差问题。在可以无缝融合的局部区域，只需用某一种方式配准。我们采用一种混合的配准模型，它结合单应性和内容保护扭曲，提供处理视差的灵活性，避免令人讨厌的局部扭曲失帧。我们提出一个高效的随机算法，它和内容保护扭曲结合，寻找单应矩阵，从而给予最优拼接。我们通过搜索一个似乎是真实的接缝并使用接缝成本作为衡量标准来预测一个单应矩阵使图片近乎真实拼接。这种接缝寻找方法仅通过考虑几何配准和图像内容粗略地以配准图片为标准衡量接缝是否接近真实。然后，使用最优单应矩阵预配准输入图片，进一步使用内容保护扭曲局部精细化配准。最后，使用标准接缝算法和多频融合算法将配准图结合在一起。我们的实验展示我们的方法可以高效拼接图片，解决大视差问题。

1.介绍

图像拼接使一个很好的研究课题。它的第一步就是配准输入图像。早期的方法是在两张图片之间，用一个2D变换，典型的如单应矩阵，使用它来配准。由于单应矩阵不能解决视差，这些方法要求输入图片应该在相同的视点采集，或者场景基本在同一平面。否则，就找不到单应矩阵来配准图像，会导致伪影(artifacts，先这么翻译吧，就是效果不好的产物)，如鬼影或者破坏了图片结构。虽然先进的图像混合技术，如接缝和融合，可以解决这些伪影，但它们不能解决未配准问题。

笔者注：所以本文方法又能解决大视差问题，又能解决拼接伪影，又能解决未配准问题。可能只是大视差条件下，效果才比较好？

最近的图像拼接方法使用空间变化扭曲算法配准图片。虽然空间变化扭曲比单应矩阵更好控制视差，但是它不能很好地解决大视差问题。图1展示一个有挑战性的例子，两张输入图片的视差很大。

注意图1（a）中的水平空间排序，车，树，烟囱。左图中烟囱在车和树的中间，右图中树在车和烟囱中间。
对于此例，一个图片恰好需要折叠起来才能和另一张图配准。这对于扭曲方法来说是个非常难的任务，因为扭曲方法不能折叠图片或者显著损失，正如图1（c）展示的那样。

本文中，我们突出一个容忍视差的图像拼接方法。我们的方法建立在“图像拼接不是必须完美的配准整个重叠区域”这种条件之上的。相反，我们只需要配准它们以这样的方式——
重叠区域存在一个局部空间可以配准图像。我们把这称为局部拼接，并提出一个高效方法去找到这样一个局部最优配准。我们的局部配准方式采用一个混合配准模型，使用单应矩阵和内容保护扭曲。单应矩阵可以保护全局图像结构，但是不能处理视差。和单应矩阵相比，内容保护扭曲可以更好地处理视差，但不能保护全局结构。而且，局部拼接也可以更好地配准大的局部公共区域。然而，当单应矩阵用于大视差图像配准时，局部区域大小和配准质量通常时两个矛盾的目标。我们通过使用单应矩阵粗略配准图像，用内容保护扭曲精细化配准，以此来解决这个问题。

我们提出一种高效随机搜索算法，首先粗略寻找局部配准的单应矩阵。在这里，我们通过从粗略配准图中寻找最优接缝，使用接缝成本来判定单应矩阵的得分，来预测单应矩阵对于局部拼接的好坏。我们使用图割算法寻找接缝，通过考虑几何配准和图像内容，仅从粗略配准图中评估近似真实的接缝。一旦我们找到最优单应矩阵，就使用它预拼接输入图片，然后使用内容保护扭曲优化配准。

本文主要的贡献时一个高效且鲁棒的拼接方法来处理大视差问题。我们的方法主要来自局部拼接，通过内容保护扭曲和接缝裁剪增强，探索图像内容和几何配准的关系，找到最优配准的局部区域。正如我们实验展示的，我们的方法可以拼接大视差的图像。

笔者注：用一个例子解释了两张图片的大视差，强调本方法不注重配准，而注重单应，改良了选择单应矩阵的方式，结合单应和内容保护扭曲。本节的内容与摘要差不多。

2.相关工作

略。后面补上，主要看本文算法。

3.容忍视差的图像拼接

我们的方法使用常用图像拼接流程。具体地，首先配准输入图像，然后使用接缝裁剪算法找到接缝去切割配准图像，最后应用多频段融合算法生成最终拼接图。我们的贡献时一个新颖的图像配准方法，它可以以一种最优的图像拼接方式配准图像。

我们观察到不需要在整个图像重叠区域完美配准图像。事实上，对于大视差图像，非常难完美配准。我们的目标是在一个局部区域配准图像，这个局部区域可以找到一个接缝去分割它们。我们应用随机算法搜索最佳拼接。具体，首先选择SIFT特征点，并匹配它们。然后随机算则一个种子特征点，并把它和它的相邻特征点看成一组，这是为了评估配准，因为我们的目标就是让局部区域有紧密的特征分布。我们评估这样配准的拼接质量。如果这样配准对拼接足够好，就停止；否则重复配准估计和质量估计。以下我们先讨论这个算法的关键部分，然后提出算法描述细节。

3.1 配准模型选择

第一个问题就是选择什么配准模型。有两个主流选项：全局2D变化，如单应矩阵，和空间变化扭曲，如内容保护扭曲。大多数方式使用全局2D变换配准两张图。全局2D变换有一个显著的优势，它全局扭曲图像，避免令人不满的局部扭曲损失。例如，单应矩阵可以保护直线和相似变换进而保护目标形状不变。但是它们对于操作视差是刚性的。对于图像拼接，虽然我们讨论不需要整个重叠区域配准，但是也要尽可能更好更大的配准公共区域。然而，对于大视差的图像，2D变换，如单应矩阵，通常仅配准一个小的局部区域。相反，内容保护扭曲更灵活，更好配准，但通常会有局部损失。
我么的解决方案是结合两种配准方式，在更大的重叠区域有最小的损失。给定一个种子特征点，我么的方法增加聚合种子点的邻居点，为了适配2D变换（单应矩阵失效）。这里，我们使用一个稍微更大的阈值，为了聚合尽可能多的特征点，虽然这会使单应矩阵不能适配这些特征对应点。减少单应矩阵的适配性可以通过之后应用的内容保护扭曲补偿，因为内容保护扭曲可以很好地用于局部扭曲优化，没有显著性损失。

3.2 配准质量评估

一个简单的评估拼接质量的方式就是上面提到的混合配准，首先使用单应矩阵扭曲图片，并且应用内容保护扭曲。然后，我们可以比较扭曲图片，参照图用于测试这两张图配准的有多好。然而，这种方式不能可靠地预测是否能找到重叠区域内一个很好的接缝。而且，这种方式不会考虑拼接图内容的影响。对于拼接，当图像区域比如蓝天不需要完美配准时，主要的图像特征，例如边缘，应该很好地配准。最后，在随机算法中，无论什么时候我们评估拼接质量，这种方式很慢，因为它需要内容保护扭曲。

我们解决了上述问题。首先，我们评估拼接质量基于图像边缘而不是直接基于整个图像。然后，我们仅评估单应矩阵如何支撑拼接。这样简化是合理的，因为内容感知扭曲是非常有效的，如果仅小范围调整全局扭曲。但它也带来了一个挑战：我们方法中的单应矩阵的设计是松散的，不能精确配准两张图像。然后我们需要预测从粗略配准图中如何配准能达到无缝拼接。通过寻找粗略配准图中的近乎真实的接缝，使用接缝成本给配准打分，我们解决了这个挑战。

具体相关算法这里开始

我们首先对输入的图片下采样，为了提升速度和允许小的未配准。然后对输入图片使用Canny边缘检测算法，计算边缘映射。边缘映射对于允许小的未对准是低通滤波器。我们计算扭曲边缘映射和参照图的边缘映射直接的不同，获得这个不同映射$E_d$。
（笔者注：文章看到这里发现$E_d$应该就是衡量图像像素的能量了，只是这篇文章的方法是通过canny算子来计算能量。说明边缘检测的算子都可以用来衡量能量这个概念，结合系列里其他基于seam的方法，能量的概念有很多公式可以用，这样就提供了很多思路。）
在$E_d$中，为了获得无缝拼接结果，近乎真实的接缝应该避免经过数值高的像素。我们用图割接缝搜索算法去找到近乎真实的接缝。(笔者注：seam carving 中就是找最小能量线，用的动态规划，阅读源码之后发现初始的算子选择可以有很多，不同的算子选择计算的速度和效果各不相同。)简单地说，就是把重叠区域的每个像素点看作一个图中节点。我们定义两个相邻节点$s$和$t$的边缘成本为：
$$e(s,t)=f_c(s)\mid E_d(s)\mid +f_c(t)\mid E_d(t)\mid \text{\hspace{1em}(1)}$$
$f_c(s)$是配准置信函数，用于衡量边缘成本，进一步解释单应矩阵仅可以粗略配准两张图和内容保护扭曲将用于优化配准。具体地，如果局部区域有SIFT特征点，配准很可能改善通过内容保护扭曲。因此，仅来自于使用单应矩阵的未配准就不那么重要了。根据SIFT分布计算$f_c(s)$降低未配准的重要性：
$$f_c(s)=\frac{1}{{\sum }_{P_i}g(||P_s?P_i||)+\delta }\text{\hspace{1em}(2)}$$
$P_i$是SIFT特征点的位置，$P_s$是像素s的位置。g是高斯函数，用于传递SIFT特征点对于它相邻点的影响。$\delta$是一个常数，默认值是0.01。

基于公式（1）中定义的边缘成本，接缝寻找问题作为一个图割问题解决。一旦我们获得接缝，我们使用接缝的成本给配准质量打分。

3.2.1 单应放映

虽然一些单应矩阵可以完成无缝拼接，但有时也有很严重的图像扭曲，并导致视觉效果不好。我们发现这一的单应矩阵，并且在评估它们的配准质量之前就丢弃它们。我们衡量透视扭曲，通过对图片$I$应用单应矩阵$H$，计算$H$是怎样偏离最佳适配相似变换的。$C_i$是输入图像$I$的四个角点之一，$\overline{C_i}$是$H$变换的对应点。我们用下面公式找到最佳适配相似变换$\widehat{H_s}$:
$$\widehat{H_s}=\underset{H_s}{\mathrm{argmin}}\sum _{C_i}||H_s{C}_i?\overline{C_i}|{|}^2,where{H}_s=\left[\begin{array}{ccc}a& ?b& c\\ b& a& d\end{array}\right]\text{\hspace{1em}(3)}$$
一旦我们获取$\widehat{H_s}$，我们求$H$和$\widehat{H_s}$的角点变换的距离和，进而求得透视损失。如果这个和比阈值大（默认0.01），就丢弃这个单应矩阵。

3.3 配准算法总结

我们现在描述随机算法去评估拼接较好的配准。

1. 对于输入图像，选择和匹配SIFT特征点，计算边缘映射。
2. 随机选择一个种子特征点，一个接一个聚合空间最近邻的相邻点，直到选择的特征集合不能被单应矩阵适配，其中单应矩阵有一个提前定义好的阈值。（笔者注：没有说用RASCAN,读代码看看有什么区别。）对于每个特征点得到一个惩罚值，为了识别它在迭代过程中被选择了多少次。当一个特征点被选择，惩罚值+1。在每一轮，为了选择一个有效的种子，之前被选择过的特征点不应该被选择为种子，并且它的惩罚分数是低于所有特征点的平均惩罚值。
3. 用3.2中描述的算法评估步骤2得出的最佳单应矩阵的配准质量。如果单应矩阵达到预先定义好的质量阈值，转步骤4。否则，如果平均惩罚值比较低，转步骤2；否则在循环过程中选择最好的单应矩阵并转步骤4
4. 应用最佳单应矩阵去预配准图像，通过选择的用于细化配准的特征点引导内容保护扭曲，就像3.3.1中描述的那样。
   
   图2展示了我们的方法流程。对于给定的输入图片（a)，我们的方法首先找到最优局部单应矩阵和特征点子集，特征点子集是通过这个单应矩阵得到的松散点，展示在图（b）。我们用蓝色的圈标记选择的特征点对。注意，单应矩阵不能精确配准这些特征点。我们然后使用内容感知扭曲优化配准。正如图（c）展示的那样，选择的特征点对很好的配准了。我们的方法最终把配准图拼接在了一起，如图（d）。
   （笔者注：小吐槽一下，图2这个例子举的并不是很好，很像是为了秀算法，因为这两张图除了视差以外近似一致，实际上没有拼接的必要，并没有明显扩大场景。。。通常谁会想把这样两张图拼在一起。。。）

3.3.1 内容保护扭曲CPW

各种各样的内容保护扭曲方法应用广泛，例如视频防抖和图像与视频重标定。虽然内容保护扭曲不能总是单独用于配准图像的整个重叠区域，它却很适合小的局部调整。因此，我们使用它去进一步配准从最优单应矩阵到参照图的预扭曲结果，正如图2（b）和（c）展示的那样。
用$I,\overline{I},\hat{I}$分别表示输入图片，预扭曲图片，和最终扭曲结果。输入图片$I$分成m×n个网格。$I,\overline{I},\hat{I}$中的顶点记为$V_i,{\overline{V}}_i,{\hat{V}}_i$。然后，图像扭曲问题就变成了网格扭曲问题，未知量是${\hat{V}}_i$。${\overline{V}}_i$是来自预扭曲图中的已知量。网格扭曲问题定义为一个优化问题，目的是配准$\overline{I}$和参照图，避免显著的损失。下面我们详细描述这些量的关系。

局部配准

$I,\overline{I}$的特征点在参照图中应该可以匹配它们的对应位置，以至于它们可以很好的配准。虽然特征点$P_j$通常上不是和任意一个网格顶点一致，但我们可以找到包含它的网格。然后表示${\overline{P}}_j$为$\overline{I}$中$P_j$的对应点，用一个四个网格顶点的与对应点的线性组合。线性组合系数用逆双线性差值计算。这些系数用于结合输出图像$\hat{I}$的顶点，从而计算${\hat{P}}_j$。我们可以定义配准能量：
$$E_p=\sum _{j=1}^n||\sum {\alpha }_{j,k}\widehat{V_{j,k}}?P_j|{|}^2,\text{\hspace{1em}(4)}$$
n是选择的特征点点集大小，来自配准优化步骤3.3。${\alpha }_{j,k}$是双线性组合系数，$\widehat{V_{j,k}}$是网格顶点，包含${\hat{P}}_j$,$P_j$是参考图的对应特征点。

全局配准

上述的配准仅限制在有被选择的特征点的重叠区域内扭曲。对于其他的区域，内容保护扭曲通常会使它们变形。当预扭曲结果$\overline{I}$已经提供一个好的近似值时，我们的方法会尽可能地促使无特征点的区域去接近预扭曲的结果。因此，定义下面的全局配准：
$$E_g=\sum _i{\tau }_i||\widehat{V_i}?\overline{V_i}|{|}^2,\text{\hspace{1em}(5)}$$

$\widehat{V_i},\overline{V_i}$分别是内容保护扭曲和预扭曲结果中的对应顶点 。${\tau }_i$是一个二值。如果$V_i$没有相邻特征点，就把它置为1；否则置为0。这样使用它提供了局部配准灵活性。

平滑

扭曲过程中进一步最小化局部损失，我们让预扭曲结果中的网格做一个相似变换。我们使用论文【11】中的二次能量编码相似变换限制。具体地，考虑三角形$△{\overline{V}}_1{\overline{V}}_2{\overline{V}}_3$。顶点${\overline{V}}_1$可以通过其他两个顶点表示：
$${\overline{V}}_1={\overline{V}}_2+u({\overline{V}}_3?{\overline{V}}_2)+vR({\overline{V}}_3?{\overline{V}}_2),R=\left[\begin{array}{cc}0& 1\\ ?1& 0\end{array}\right],\text{\hspace{1em}(6)}$$

（笔者注：看到这发现是 As-Rigid-As-Possible Shape Manipulation这篇文章里的知识，正好复习一下。）
$u,v$是顶点${\overline{V}}_1$在局部坐标系中被${\overline{V}}_2,{\overline{V}}_3$定义的坐标。如果这个三角形经过一个相似变换，它在局部坐标系中的坐标不会改变。（笔者注：也就是保持刚性不变）因此，相似变换被定义为：
$$E_s({\hat{V}}_i)=w_s\mid \mid {\overline{V}}_1?({\overline{V}}_2+u({\overline{V}}_3?{\overline{V}}_2)+vR({\overline{V}}_3?{\overline{V}}_2))\mid {\mid }^2,\text{\hspace{1em}(7)}$$
$u,v$用公式（6）计算。所有顶点的$E_s({\hat{V}}_i)$求和，获得全部平滑能量$E_s$。这里$w_s$测量三角形的显著值用【14】中相同的方法。我们使用显著权重将更多的损失散播到更少的显著区域，和其他显著区域相比。

最优

结合上面的三个能量得到下面的求下面最小能量问题。
$$E=E_p+\alpha E_g+\beta E_s,\text{\hspace{1em}(8)}$$
其中，$\alpha ,\beta$是每个能量的权重，默认值为0.01和0.001。上面的最小化问题是二次方程，用标准稀疏线性矩阵求解得到。一旦我们得到输出的网格，我们使用纹理映射呈现最终的结果。
（笔者注：纹理映射（texture mapping）又是一个大坑，好像unity3D里的材质球就是这个原理。也是附录中论文里的方法）

4.实验

我们用了一系列大视差图片做实验。也和一些主流的方法做了比较,包括PS,自动拼接,APAP,SEAM.对于APAP,我们使用作者源码.虽然代码仅配准图像,我们添加了与我们相同的相同的接缝剪裁和多频段融合算法.本文仅展示一些有代表性的拼接结果,部分裁剪不正.请在项目网站上参考更多的结果,没有裁剪过的,更中性的结果.

图3(a)是两张输入的大视差图片.

1. PS拼接失败.
2. 自动拼接使用全局2D变换,没有配准两张图,(b)中圈里显示,在红绿灯处有鬼影.
3. seam没有通过单应矩阵找到有代表性的局部平面,图?显示也是红绿灯有重影.
4. APAP产生了一个值得注意的结果,如图(d),APAP试图去配准整个重叠区域,它破坏了图片的结构,如图中红框的柱子.
5. 我们的方法最好,图(e),接缝用红线画出来.
   
   图4展示了另一个有挑战的例子.两张输入图片有大视差,没有全局变换可以配准它们的整个重叠区域.图4(b),自动拼接有鬼影,融合可以缓解未对齐,但它也能造成像红圈中那样的模糊情况.PS和SEAM在红色建筑物中都有重影.图4?(d).图(e)中APAP扭曲了直线.我们的方法很好.

4.1 讨论

我们的方法只需要部分配准,适配松散的单应矩阵,正如3.2中描述的那样.因此,我们的方法有时使用更严格的全局变换,和从单应矩阵中移除透视损失相比.图5(a)展示了我们的方法对于有着显著透视损失的初始配准拼接结果.一旦我们用相似变换代替单应矩阵对于初始配准,拼接结果就会有更少的损失,正如图5(b)中展示的.
我们也测试了如何选择单应矩阵,不同于通过计算我们的单应矩阵和最佳适配间的变换图像角点间的位置距离的最好适配方式.在我们的项目网站中,超过75%的例子平均角点位置距离大于36像素(每个图片宽1000像素).中间距离大约60像素.这证明了我们的方法使用不同的单应矩阵好于最佳适配.

我们的方法不仅在大视差图片上效果好,也在APAP中提供的数据集上效果很好.于此同时,我们找到了一些失败的例子展示在项目网站上.一个就是输入图片有大视差和充满了显著结构.对于拼接,图像必须能配准,以至于至少存在一个局部公共区域,这个区域能找到最佳拼接缝.在大视差的图片中,通常不再是一个能配准的局部区域.我么的方法探索了不显著的区域不需要被很好的配准,并把这考虑到搜索最好局部配准.但如果图片有大视差并充满了显著性结构,我么的方法有时不能起作用因为没有不显著的区域存在.

关键步骤:最优局部单应矩阵评估和CPW
实验设备:desktop machine Intel i7 CPU和 8GB内存配准两张宽度为1000像素的图,花费20~40秒.
其他步骤都是用的现成的拼接算法.

5.结论

本文提出了一个允许视差的图像拼接方法.我们发现,有显著时差的图片不能在整个重叠区域很好的配准,比如没有伪影.并且这些图片实际上不需要在整个拼接区域完美配准.然后我们提出了一个局部优化拼接的方式.设计了一个高效算法评估什么样的结果是无缝的配准结果.我们的实验在这个具有挑战性的拼接任务上展示了我们算法的高效.

总结

1. 单应矩阵和CPW结合,主要折腾单应矩阵,不是选最好的,而是选最适合的.最适合的不一定是最好的.
2. 找特征点通过种子点,这是个创新.
3. 初期的配准用相似变换代替单应矩阵会减少损失.
4. 大视差图片和APAP数据集效果不错,但是不能又是大视差又是全部显著结构,重叠区域得有不显著的结构才行.局限性有点高.
5. 不要求整个重叠区域完美配准.
6. 针对重影和直线扭曲,结合两种方法达到了不错的效果.

附录

参考文献中的论文[10]是纹理映射,[11]是3.3.1中提到的CPW,就是下面这篇文章，感兴趣的同学可有看一下Content-preserving warps for 3D video stabilization
[12]是介绍图割算法的

实验中提到的算法:
[3]是自动图像拼接
[9]是SEAM
[27]是APAP

本文项目相关链接,具体的例子都可以在其中找到:
http://graphics.cs.pdx.edu/project/stitch