图像拼接技术已应用于各个领域:全景图像生成、大面积地图绘制、医学图像合成以及虚拟现实场景构建^[1]。图像拼接技术的核心思路是建立输入图像间的投影关系，然后将输入图像投影到一个公共画布上，并通过融合算法生成一张视角更广的图像^[2]。随着日常生活中图像拼接技术需求的增加，一些专注于图像拼接的商业软件也得到普及，例如Auto-Stitching，微软ICE等。这些软件要求输入图像尽可能满足图像拼接的理想条件，即图像中场景只包含一个主平面，且图像本身只存在旋转差异^[3]。然而，当非专业摄影师拍摄时，不能满足固定相机于一点的要求，拍摄过程中会发生走动或移动相机到空间中另一点再拍摄的情况。由此，捕获的图像会存在一定视差。在配准大视差图像时，由于3维场景之间的复杂的交互作用，2维图像很难实现准确的对齐^[4]。若仅使用一个全局的单应性矩阵对其投影，可能会导致严重的误配准，进而产生鬼影现象。

近年来，研究人员在大视差图像配准方面做了大量的工作。Gao和Kim^[5]提出将图像分割成两个主平面，即地平面和远背景平面，并使用双单应性变换的方法投影其对应区域。该方法对于符合其分割条件的图像有较好的效果，但是对于其他图像或是更大视差的图像，配准精度不足。Zaragoza和Chin^[3]提出尽可能投影(APAP)的配准方法。

他们将图像分成C₁×C₂个单元(100×100)，利用移动直接线性变化法(moving DLT)求解每个单元的单应性矩阵，并逐个投影所有单元。该方法采用局部投影结合全局投影的方式有效地提高了配准精度。之后，他们在原来实验的基础上引入捆绑调整的方法，矫正多幅图像拼接的投影失真^[6]。Chang等人^[7]提出了保持形状的半投影变换(SPHP)方法。SPHP在重叠区域采用投影变换在非重叠区域采用相似变换，有效地解决了非重叠区域的投影失真问题。而对于大视差图像的配准仍需要结合APAP算法。Lin等人^[4]提出了自适应的尽可能自然投影(AANAP)方法。AANAP算法结合了投影变换、相似变换和仿射变换，能够有效处理拼接过程中的投影失真，使拼接后的图像更加符合视觉审美。实质上，AANAP在配准方面也采用了APAP算法的思路，即利用Moving DLT方法计算局部投影和全局投影。Chen和Chuang等人^[8]提出了一种优先相似变换的拼接方法，该方法在多幅图像拼接时，能够有效地处理全局失真。由此可见，在拼接大视差图像方面APAP算法仍是目前配准精度最高的拼接方法之一。然而，APAP算法复杂度高，计算量大且APAP的图像单元划分过小，累积的投影失真会导致图像扭曲变形。此外，该方法需要调节多个取值范围大却无规律的参数。

显然，无论是将图像分割成地平面和背景平面^[5]，还是分割成数万个大小均等的单元^[3]，都不符合大视差图像包含显性子平面的真实情况。于是，本文提出一种更接近真实情况的显性子平面自动配准算法用于拼接大视差图像。该算法可通过拼接误差与聚类算法大致确定图像中所含子平面的数目及位置，然后利用局部投影实现高精度配准拼接。

假设1 倘若图像中某一块连续区域的像素点集属于同一平面，那么该像素点集所提供的特征点必定存在于这一平面。

假设2  对于已匹配的特征点：内点密集，外点稀疏^[9]。

基于上述的描述和假设，本文提出一个关于图像中所含子平面的假设：

假设3  如果图像中包含多个子平面，那么这些子平面所在区域的特征点必定相近且密集。

为验证该假设3，本文对整幅图像分别使用全部特征点推导出的全局单应性矩阵和由聚类算法得到的局部密集特征点推导出的局部单应性矩阵进行投影拼接，其结果如图 1所示。

由于在求解全局单应性矩阵的过程中，使用了图 1(a)的所有特征点，图像的每个区域都对投影参数有所贡献，即全局单应性矩阵成为一种折中结果，这就导致图像中的几个主要区域均未实现配准，如图 1(b)所示。当仅使用图像某一特定区域的特征点求解投影参数时，如重叠区域左上角或右下角区域，所得拼接结果在对应区域均实现了高精度配准，如图 1(c) (d)所示。其中，红色矩形框内为未对齐区域，绿色矩形框内为对齐区域。

以上结果表明：由某一局部区域的密集特征点导出的局部投影变换相较于全局投影变换使得该区域配准更加准确。这一区域可以称为图像的一个显性子平面。显然，局部区域的划定成为影响局部配准精度高低的关键。根据上述所提假设，本文提出使用基于距离的聚类方法对特征点进行分组，并利用特征点分组情况对图像进行区域划分，进而得到显性子平面在图像中的大概位置。

层次聚类算法是通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树，具有先聚类后分组的特点^[10]。在搜索最优分组数目时，相比于k-means算法无需重复聚类，能节省大量计算，有利于实现自动配准。

计算两个组合数据点间距离的方法有3种，分别为Single Linkage，Complete Linkage和Average Linkage。其中，Average Linkage的计算方法是计算两个组合数据点中的每个数据点与其他所有数据点的距离，将所有距离的均值作为两个组合数据点间的距离，其结果比前两种方法更合理^[10]。因此，本文使用Average Linkage层次聚类算法对图像的特征点聚类。

在使用层次聚类算法前，先使用RANSAC算法去除异常特征点。之后对剩余的特征点建立层次聚类树。由于特征点较多，如图 2仅展示30个特征点的距离关系。然后，自上而下依次剪枝，计算拼接误差，择优而选。计算方式在2.2节给出。

由于本文算法以特征点分布为依据进而确定显性子平面位置。对于重叠区域中不含特征点的区域，依据所提假设，本文使用就近原则处理其所含像素点，将其归于距离最近的一类，即以各类中心为中心，对整个重叠区域再聚类。

本文所用重叠区域，不同于真正意义上的重叠区域，而是以所有特征点中的横坐标最大值为界，纵向将图像划分成两部分，即重叠区域和非重叠区域。

划分出重叠区域后，初始化一块和重叠区域尺寸相同的黑色画布，并将所有特征点映射到对应位置，如图 3(a)所示。根据1.2节的减枝结果，找到每一类的4个方向上的极值点，从而得到对应于每一类的矩形框，记其左上角顶点为$\left( {{\mathit{\boldsymbol{X}}_{\rm{L}}}\mathit{\boldsymbol{, }}{\mathit{\boldsymbol{Y}}_{\rm{L}}}} \right)$；右下角顶点为$\left( {{\mathit{\boldsymbol{X}}_{\rm{R}}}\mathit{\boldsymbol{, }}{\mathit{\boldsymbol{Y}}_{\rm{R}}}} \right)$；中心为$\mathit{\boldsymbol{O}}\left( {\mathit{\boldsymbol{X}}_{{\rm{center}}}^{(i)}, \mathit{\boldsymbol{Y}}_{{\rm{center}}}^{(i)}} \right)$。则

$ \mathit{\boldsymbol{X}}_{{\rm{center}}}^{(i)} = \frac{1}{2}{\rm{ }}(\mathit{\boldsymbol{X}}_{\rm{L}}^{(i)} + {\rm{ }}\mathit{\boldsymbol{X}}_{\rm{R}}^{(i)}) $

(1)

$ \mathit{\boldsymbol{Y}}_{{\rm{center}}}^{(i)} = \frac{1}{2}{\rm{ }}({\rm{ }}\mathit{\boldsymbol{Y}}_{\rm{L}}^{(i)} + {\rm{ }}\mathit{\boldsymbol{Y}}_{\rm{R}}^{(i)}) $

(2)

式中，$i = 1, 2, \ldots, K$。

以$\mathit{\boldsymbol{O}}\left( {\mathit{\boldsymbol{X}}_{{\rm{center}}}^{(i)}, \mathit{\boldsymbol{Y}}_{{\rm{center}}}^{(i)}} \right)$为聚类中心，以欧氏距离为相似度测量，对整个重叠区域的像素点$({p_1}, {p_2}, \ldots, {p_n})$再聚类，即

$ \mathit{\boldsymbol{P }} = \{ {\rm{ }}{\mathit{\boldsymbol{P}}_1}, {\rm{ }}{\mathit{\boldsymbol{P}}_2}, \ldots, {\rm{ }}{\mathit{\boldsymbol{P}}_K}\} $

(3)

式中，$\mathit{\boldsymbol{P }}$为聚类结果；${\mathit{\boldsymbol{P}}_i}$单个类的特征点集，满足条件

$ {\rm{arg}}\;{\rm{min}}\sum\limits_{i = 1}^K {\sum\limits_{{p_j} \in {\mathit{\boldsymbol{P}}_i}} {\parallel {p_j} - \mathit{\boldsymbol{O}}\left( {\mathit{\boldsymbol{X}}_{{\rm{center}}}^{(i)}, \mathit{\boldsymbol{Y}}_{{\rm{center}}}^{(i)}} \right){\parallel ^2}} } $

(4)

式中，${p_j}$为重叠区域像素点。

二次聚类的结果如图 3(b)所示，其中，不同的颜色的区域代表所得的不同的显性子平面，根据聚类边界便可分割出显性子平面。

完成显性子平面分割后，分别计算各个平面的投影关系。

$c = {\left[{x\;\;\;\;y} \right]^{\rm{T}}}$和$\mathit{\boldsymbol{c'}} = {\left[{x'\;\;\;\;y'} \right]^{\rm{T}}}$为对应子平面${\mathit{\boldsymbol{\omega }}_{\left( i \right)}}$和${{\mathit{\boldsymbol{\omega '}}}_{\left( i \right)}}$中已匹配的特征点。令$\mathit{\boldsymbol{\tilde c}} = {\left[{{\mathit{\boldsymbol{c}}^{\rm{T}}}\;\;\;\;1} \right]^{\rm{T}}}$且$\mathit{\boldsymbol{\tilde c'}} = {\left[{{{\mathit{\boldsymbol{c'}}}^{\rm{T}}}\;\;\;\;1} \right]^{\rm{T}}}$，则$\mathit{\boldsymbol{\tilde c}}$与$\mathit{\boldsymbol{\tilde c'}} $满足以下投影变换关系，即

$ \mathit{\boldsymbol{\tilde c'}} = {\mathit{\boldsymbol{H}}_{\left( i \right)}}\mathit{\boldsymbol{\tilde c, }}\;\;\;\;i = 1, 2, \ldots, K $

(5)

式中，${\mathit{\boldsymbol{H}}_{\left( i \right)}}$是显性子平面对应的单应性矩阵。

由于非重叠区域没有已匹配的特征点，无法直接计算其投影变换，本文采用就近原则，把重叠区域的投影矩阵推广到相邻的非重叠区域。相比于全局投影，基于就近原则的局部投影能够有效避免重叠区域与非重叠区域交界处的投影错位。

图像拼接的整体过程如图 4所示，红色虚线框内为本文算法。

由于特征点的数量对子平面分割有着重要的影响，所以本文选用SIFT(scale-invariant feature transform)算法^[11]提取特征点。相比于SURF (speed-up robust features)^[12]等其他特征，SIFT特征具有特征点丰富且分布广泛的优点^[13]。之后，先使用KNN (k-Nearest Neighbor algorithm)算法对特征点进行粗匹配，再使用RANSAC(random sample consensus)算法^[14]去除匹配异常点。再通过层次聚类算法，对特征点聚类，并求得聚类中心。规划出目标图像的重叠区域后，依据聚类中心对整个重叠区域进行再聚类。根据聚类结果将重叠区域分割成K个单元，用每个单元中所含特征点求得该单元的投影参数。迭代求解拼接误差$error$，当初出现满足$error < \varepsilon $ (其中$\varepsilon$为可允许的最小误差值)的分组数时，保留该分组数并采用就近原则分配非重叠区域的投影参数，最终得到拼接结果。在整个拼接过程中，始终保持参考图像不变，只分割目标图像的显性子平面。

受APAP算法启发，最初本文希望误差函数具有收敛性，即当分组数尽可能大时，拼接效果越好。APAP算法所用的配准精度指标$RMSE$具备此特性。然而，$RMSE$作为标准衡量的是特征点的配准精度，并不一定能表征最终拼接质量的好坏。

由于误配准所引发的鬼影、重影等问题均发生在重叠区域，本文直接将重叠区域整体配准情况作为衡量拼接质量的标准，即

$ error = \frac{{\sum\limits_{i \in \mathit{\boldsymbol{\omega }}} {\parallel \mathit{\boldsymbol{\omega }}{_{(i)}} - {\rm{ }}{{\mathit{\boldsymbol{\omega '}}}_{(i)}}\parallel {^2}} }}{{\sum\limits_{i \in \mathit{\boldsymbol{\omega }}} {\parallel \mathit{\boldsymbol{\omega }}{_{(i)}}\parallel {^2}} }} $

(6)

不同图像的$error$和K的关系如图 5所示。事实上，由于特征点数量有限，分组数也不可能实现无限增大。随着分组数的增加，平均到每个组的特征点数目逐渐减少，受外点影响，所计算的投影矩阵误差也就越大。经过多次实验，最大分组数目适合取值${K_{\max }}$=8~12。尽管$error$不具备收敛性，但在${K_{\max }}$具有一个较小下限的情况下，局部最优成为全局最优。当$error < \varepsilon $的条件难以满足时，可以采用并行计算的方法寻找最优解。

为了有效地辨别重叠区域的配准精度，本文使用加权融合法合成新的图像。设使${I_1}$、${I_2}$为待融合的图像，则融合后的图像$I$满足：

$ \mathit{\boldsymbol{I}}\left( {i, j} \right) = \left\{ \begin{array}{l} {\mathit{\boldsymbol{I}}_1}\left( {i, j} \right) + {\mathit{\boldsymbol{I}}_2}\left( {i, j} \right)\\ {\mathit{\boldsymbol{I}}_1}\left( {i, j} \right) = 0{\rm{ }}或{\mathit{\boldsymbol{I}}_2}\left( {i, j} \right) = 0\\ 0.5 \times {\mathit{\boldsymbol{I}}_1}\left( {i, j} \right) + 0.5 \times {\rm{ }}{\mathit{\boldsymbol{I}}_2}\left( {i, j} \right)\\ {\mathit{\boldsymbol{I}}_1}\left( {i, j} \right) \ne 0{\rm{ }}且{\mathit{\boldsymbol{I}}_2}\left( {i, j} \right) \ne 0 \end{array} \right. $

(7)

式中，${i, j}$是图像的坐标索引。

相比于其他融合算法通过遮挡或者避开错位区域等策略处理误配准^[15]，加权融合法能够更直接地展示出真实的配准情况，如图 6所示。图 6(a)为BaseLine(全局投影变换)方法结果，红色矩形框内的误配准的情况清晰可见。

由于投影变换过程中，默认使用双线性插值法^[16]对边缘处像素空缺区域进行像素填充，导致加权融合法会在图像的边缘处出现暗淡的斑点，如图 6(b)所示。本文采用最近邻插值法^[17]取代双线性插值法对图像投影后的边缘区域进行插值。最近邻插值法跟据相邻像素值确定填充像素值，不会因空缺区域的像素初始值为零而导致新像素值的减小，其结果如图 6(c)所示。

将本文算法与其他4种方法做对比实验，其中包括Auto-Stitching^[18]、微软ICE^[19]两种商业软件，及Baseline和APAP^[20]两种目前常用方法。

图 7、图 8展示了不同方法的拼接结果。图中右侧的两列图像为左侧图像的局部放大。绿色框中的区域为正确配准的区域；红色框中的区域为错误配准的区域；蓝色框中的区域为非重叠区域由累积误差造成的失真。在处理大视差图像时，Auto-Stitc-hing和微软ICE两款软件对于纹理细节配准精度较差，例如temple数据集的地砖处(图 7 (a) (b))和railtracks数据集的铁轨处(图 8 (a) (b))。BaseLine作为图像拼接的一般性方法，无法有效处理大视差图像。APAP算法作为目前配准精度最高的算法之一，在不同数据集上均表现出较好的效果。但在一些细节处仍有误配准出现，如图 7 (d)所示。而本文算法在重叠区域都实现了高精度配准，如图 7(e)、图 8(e)所示。

在客观评价方面，采用APAP算法所用的均方根误差作为配准标准衡量各算法的客观指标，计算公式为

$ RMSE\left( f \right) = \sqrt {\frac{1}{N}\sum\limits_{i = 1}^N ||{{\rm{ }}f(\mathit{\boldsymbol{x}}{_i}) - {\rm{ }}\mathit{\boldsymbol{x'}}{_i}||^2} } $

(8)

式中，$f$为两幅图像之间的变换关系，$\left\{ {\mathit{\boldsymbol{x}}{_i}, \mathit{\boldsymbol{x'}}{_i}} \right\}_{i = 1}^N$为已匹配的特征点对。

由于商业软件无法计算其$RMSE$，所以本文仅统计几种常用算法的$RMSE$值，不同图像的$RMSE$均为十次计算的平均值，详见表 1。本文算法的$RMSE$值明显小于BaseLine方法，且非常接近APAP算法。

在参数设置方面，为获得最佳拼接结果APAP算法需要调节两个大范围参数，分别是Moving DLT的正则化参数(0.001 5~0.1)和其带宽(8 ~12)。对于未知图像，该算法使用极为不便。而BaseLine和本文算法均为自动配准算法，无需设置参数。

针对大视差图像拼接的配准问题，提出一种显性子平面自动配准算法。通过对特征点聚类实现子平面分割及配准，进而拼接具有大视差的图像。相比于传统全局投影方法，配准精度平均提高55 %左右；相比于当前配准精度最高的方法之一的APAP算法，二者配准精度接近，但无需调节复杂参数，可实现自动配准；相比于Auto-Stitching和微软ICE两种商业软件，能够更好地消除大视差图像由于误配准引起的鬼影错位等问题，适合应用于图像拼接中大视差图像的配准。

由于本文采用平面逼近以及非重叠区域采用就近原则分配投影矩阵，在图像的非重叠区域可能会产生一定的由投影变换带来的累积失真，对多幅图像拼接产生影响。之后的工作，本文将结合一些优秀的图像变换方法^{[4, 11]}，以解决非重叠区域投影失真等问题，并将本文算法应用到全景图像拼接中。