基于移动最小二乘法的视差图像拼接

楚东东 李海晟

(华东师范大学计算机科学与软件工程学院 上海 200062)



基于移动最小二乘法的视差图像拼接

楚东东 李海晟

(华东师范大学计算机科学与软件工程学院 上海 200062)

对于视差图像拼接，现有的工作大都采用单应性变换，这不足以得到好的拼接结果。提出一个新的视差图像拼接算法。首先检测图像的特征点并匹配，随后用随机采样一致算法RANSAC(Random Sample Consensus)和距离相似性筛选出正确的匹配点集；其次，以这些特征点结合移动最小二乘法构造一个全局仿射变换对准图像；最后，在图像的重叠区域以像素为顶点构建一个网络流，用最大流最小割算法寻找最优拼接曲线，并融合图像。由于提高了特征点匹配的正确性，对准模型的准确性明显好于以前的工作，图像拼接结果平滑真实，无扭曲、鬼影等现象。

图像拼接 特征点匹配 移动最小二乘法 拼接曲线

0 引 言

图像拼接是计算机图形学和图像处理领域的一个研究方向，受到很多研究者的广泛关注[1-6]。早期的工作解决了重叠区域比较多或者拍摄角度比较一致的图像拼接问题，主要用一个2D变换矩阵，如单应性矩阵，来对准两幅图像[1,6]。部分优秀的方法已集成到商业软件中，如Adobe Photoshop等。但是实际情况中，因手持相机的角度和方向容易变化，拍摄的相片间往往存在视差。对于这样的图像，用上述的2D矩阵来对准和拼接，容易导致几何结构断裂和鬼影等一系列问题。尽管使用一些图像处理方法，如图像分割[7-8]和图像融合等技术[9-10]，能够缓解一些这种人工痕迹现象，但这些图像处理技术只是部分提高图像拼接质量，没有从根本上解决视差图像间的拼接问题。传统方法拼接视差图像不理想的主要原因是一个2D单应性矩阵不能很好地对准有视差图像的重叠部分，因此近期的图像拼接工作集中在视差图像的对准模型方面。这些模型基本上是基于特征的变换方法，很好地提高了视差图像的拼接质量。但仍旧没有一种拼接方法能够完美地解决视差图像间的拼接问题，这仍是一个挑战性的课题。

提高特征点匹配的正确性是本文的主要工作，我们提出了距离相似性衡量方法，结合随机采样一致算法(RANSAC)[11]，有效地去除特征点之间的错误匹配。为了能使一幅图像的特征点准确地变换到另一幅图像对应的特征点，我们选用基于移动最小二乘法的变形方法。由此，本文提出了一个新的图像对准模型。对准了视差图像后，我们在变形图像和参考图像的重叠区域构建网络流模型，寻找一条合理的拼接线，两幅图像沿此曲线进行拼接。

1 相关工作

从20世纪80年代开始，研究图像拼接问题已有二十多年的历史，迄今为止积累了许多成果。完整地回顾拼接算法没有必要，也不在本文的范畴之内，读者可参阅Szeliski写的图像拼接教程[12]。这里我们对近期的视差图像的拼接工作做一个概要的回顾。

为了得到更好的图像对准结果，近年来不少研究者提出多种方法。Gao等[13]提出双单应性变换的思想，他们的方法针对于一种特别的场景，这种场景可以主要分为两个平面：地平面和远地面。很显然这种双单应性变换很难扩展到任意场景，因为不是所有的场景都可以分成两个平面，可能场景中只有一个主要的结构或者超过两个主要的平面。Zaragoza等[2]提出一种投影变换拼接技术，他们把移动直接线性变换和投影变换结合起来形成图像对准模型，这种方法在图像视差较小时可以得到很完美的拼接结果，但当图像视差较大时会出现鬼影等人工痕迹。最近，Zhang等[14]提出一种混合的图像对准模型，其中包括单应性变换和内容保持变换，此方法只要求图像存在一个局部区域可以完美的对准。这种方法在图像视差较大时也可以得到较好的拼接结果，标准的图割和多带融合技术同样应用于此方法。但在非重叠区域，图像的变形结果有时会出现失真的现象，因为作者强调局部的对准而非全局的图像对准。

2 视差图像拼接

视差图像的拼接算法已有不少，它们的流程基本上相同，大致可以分成以下三个步骤：首先检测图像的SIFT特征点，并进行匹配[15]；由于匹配的结果通常包含一些错误的匹配点对，因此要对特征点进行筛选，剔除错误的匹配点对，通常使用RANSAC；其次，用得到的SIFT匹配点对来对准图像，一般运用图像变形的方法实现；最后，对初步对准的图像直接进行融合拼接或者寻找合理的分割线进行拼接融合。本文的工作采用这个拼接流程，在SIFT特征点的筛选方面，提出了距离相似性方法，进一步验证RANSAC算法初选后的匹配点的正确性；图像变形方面，我们使用移动最小二乘法把特征点精确地变到参考图上对应的点，提高对准精度；最后，用图割算法计算合理的拼接线。

2.1 特征点选择

SIFT是一种基于梯度的特征点，具有尺度、光照和旋转不变性。基于特征的图像对准模型大都使用SIFT特征点[1-2,13-14]。然而由于它是一种局部的特征点，不含图像的全局结构信息，所以匹配结果经常包含一些错误，尤其当图像中含有多个类似结构性强的物体，容易把一个物体上的SIFT点匹配到另一个相似的物体上，如图1所示。图中圆圈表示SIFT特征点，直线表示匹配结果，很明显这个结果包含了一些错误的特征点匹配。

图1 出现错误对应的SIFT匹配结果

在提取和初步匹配SIFT特征点后，我们用RANSAC算法来对SIFT的匹配结果进行第一步筛选，以去除一些错误的匹配。随机选取四组特征点对，由此构造一个单应性矩阵H，用H去检测图像中所有的对应特征点对(p,q)，如果‖Hp-q‖

由于单应性矩阵能保持点的相对位置关系，RANSAC方法去除了大多数的异常匹配。但由于RANSAC使用阈值选取特征点对，具有一定的容忍度，所以对较小的位置扭曲可能会漏检。为了去除这类错误的对应关系，我们分析了图像拼接的特性： 首先，两张图片的尺寸差异不会过分悬殊，因此特征点间的距离基本不变和位置相似；其次，错误匹配的特征点比较少，可认为错误匹配的特征点附近有正确的特征点对。基于以上观察，我们使用距离相似性方法进一步筛选特征点对，这个方法类似于Igarashi1等人提出的图形变形方法[16]。设(p,q)是一对匹配的特征点，p1和p2是与p距离最近的两个特征点，与它们对应的两个特征点分别是q1和q2。

我们可用向量p2-p1和它绕点p1逆时针旋转90度的向量(p2-p1)⊥构建的局部坐标系表示点p：

p=p1+u(p2-p1)+v(p2-p1)⊥

(1)

(p,q)被认为是一个正确的匹配，如果这三个特征点对间满足下面的公式：

‖q1+u(q2-q1)+v(q2-q1)⊥-q‖

(2)

其中s是一个阈值。图2直观地表示出这个判定机制。

图2 SIFT特征点匹配的不同情况

经过上述操作，尽管基本上移除了错误的特征点对，但匹配点对的数量仍然很大。为了提高图像变形的效率，需要进一步采样特征点对。这一步采样要求尽可能地均匀，使得用于变形的特征点对不要过分集中，为此我们引入一个距离阈值λ。先按匹配度大小排序，用贪婪法从大到小选择特征点，同时满足下面的均匀性条件：计算当前处理的特征点与已经入选的SIFT特征点集的距离，如果距离小于λ，则舍弃这个特征点，否则加入特征点集。图3给出了一个经过上述三步筛选的SIFT特征点匹配的结果。

图3 筛选出的SIFT特征点对集合

2.2 图像变形

Schaefer等人提出的基于移动最小二乘法的图像变形方法[17]以图像中点的集合或者线条集合作为控制集对图像实施变换，能够把特征点精确地变到对应的位置。因此我们把图像中的SIFT特征点对分别看作控制点和变形后的位置点，运用上述变形方法来对准图像。为了便于理解，下面简要地回顾该变形方法。

设pi和qi是对应的SIFT特征点，wi是一个权重表示特征点对当前处理的像素点的影响，lv是关于像素点v的一个仿射变换，可以分解成一个线性变换M和一个平移变换T，即：

lv(x)=xM+T

(3)

我们寻找最优的M和T，使得下述函数值最小：

(4)

其中wi如式(5)所示：

(5)

式(4)的优化求解可以转化成一个最小二乘法问题，能够精确求得显式解如下：

(6)

(7)

(8)

对图像中的每个像素点应用仿射变换，再结合一种双线性插值技术就可以得到最终的图像变形结果。图4给出了一张图像的变形结果。

图4 原始图像和图像最终变形结果

2.3 拼接曲线

图割技术被广泛应用在计算机视觉的多个领域，包括图像拼接，视频合成[7]和数字蒙太奇图片的制作[8]等。在图像对准后，基于缝隙的拼接方法大多采用图割技术寻找变形图片和参考图片的最优拼接缝。我们参考Boykov等[18]提出的图割技术，以两幅图像的重叠区域上的像素为顶点，四邻域为连接关系，各边的容量由像素的对应关系确定，构建一个网络流D(V,E,C)。寻∀e={p,q}∈E，e的容量c(e)具体定义如下：

c(p,q)=D(p)+D(q)

(9)

D(v)=|I1(v)-I2(v)|

(10)

其中p和q是两个相邻的像素，I(v)是v点的颜色强度，c(p,q)表示定义在p和q像素点上的平滑惩罚值。对于D(V,E,C)，应用最大流/最小割算法，我们得到网络流的一个最小割，与此对应的图像上的分割线就是图像重叠区域的拼接缝。图5显示了一个具体的拼接缝结果。在最终的拼接图像中，在拼接缝左边的像素点将会采用变形图片；落在右边的像素点则采用参考图片。同样图像融合技术被用来消除微小的对准误差和图像间的曝光差异，在实验中，仅分别对图像的拼接缝隙周围像素的三个通道采取加权平均的方法来实现融合。

图5 对重叠区域运用图割之后的拼接结果

3 实验结果和讨论

利用Visual Studio和OpenCV，我们在Windows平台实现了上述方法。通过测试，算法中用到的各个参数的合理取值如下：d=10，s=12，λ=图像的宽高之积的平方根与20的比值。为了评估本文的方法，我们拍摄了一组内容多样的有视差的照片，涵盖人物、建筑、树、河流等自然景象，我们的方法能够理想地拼接大部分的照片，图6给出了这组照片的一个测试结果。

图6 强结构性图像的拼接

下面是我们的方法与两个当下流行的图像拼接软件Auto-Stitch和Microsoft ICE以及近期的拼接算法[14]的比较。实验采用Zhang等[14]所建立的一个图片库(http://graphics.cs.pdx.edu/project/stitch)，这个图片库有35组场景图片，我们测试了所有的图片，总体性能与文献[14]的算法相当。这里给出了在结构性占优的图片和自然景物图片上的四种方法的拼接结果。图7是含有桥梁、脚手架等结构性强的图片的拼接。Auto-Stitch是基于文献[1]中的图像拼接思想进行开发的软件，这种方法采用一个简单的二维变换来对准图片，当图像间视差较大时，将会带来严重的对准误差如图7(b)所示，Auto-Stitch的结果出现重影。ICE在Auto-Stitch的基础上应用了拼接缝技术[8]。这种图像后处理技术可以帮助掩盖图像的对准偏差以及拼接缝隙。但是和Auto-Stitch一样由于对准模型的局限性，ICE拼接的效果同样不理想，如图7(c)所示出现较大对准偏差。视差容忍的拼接方法混合了全局单应性变换及局部内容保持变换，可以很好地应对图像间的视差，因此可以得到看起来真实无缝隙的拼接结果如图7(d)。但在图像的非重叠区域，该方法的外插结果有时会导致图像内的显著物体形状变形从而带来失真。我们的实验结果如图7(e)。

(a) 输入图像

(b) Auto-Stitch

(c) ICE

(d) 视差容忍图像拼接

(e) 我们的拼接结果图7 强结构性图像的拼接比较

4 结 语

本文提出了一种新的视差图像拼接方法,结合RANSAC及距离相似性对SIFT特征点进行筛选，并利用移动最小二乘思想和仿射变换构成图像对准模型。它能精确对准筛选出的SIFT特征点对以此来平衡图像间的视差及图像的对准偏差。在图像对准完成后，使用图割和图像融合技术进一步平滑拼接结果。实验结果表明，此方法能够可靠地完成视差图像的拼接，利用图像融合技术，可以基本消除由对准偏差、曝光差异等因素带来的人工痕迹，从而得到无缝且感官上真实的拼接结果。

[1] Brown M, Lowe D G. Automatic panoramic image stitching using invariant features[J].International Journal of Computer Vision, 2007, 74(1):59-73.

[2] Zaragoza J, Chin T J, Brown M S, et al. As projective-as-possible image stitching with moving DLT [C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. California, USA, 2013:2339-2346.

[3] Shum H Y, Szeliski R. Construction of panoramic mosaics with global & local alignment[J].International Journal of Computer Vision, 2000, 36(2):101-130.

[4] Lin W Y, Liu S, Matsushita Y, et al. Smoothly varying affine stitching[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. New Jersey, USA, 2011:345-352.

[5] Eden A, Uyttendaele M, Szeliski R. Seamless image stitching of scenes with large motions and exposure differences[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. U.C. Berkeley, USA, 2006:2498-2505.

[6] Szeliski R, Shum H Y. Creating full view panoramic image mosaics and environment maps[C]//Computer Graphics Proceedings. New York, USA, 1997:251-258.

[7] Kwatra V, Schodl A, Essa I, et al. Graphcut textures: image and video synthesis using graph cuts[J].ACM Transactions on Graphics, 2003, 22(3):277-286.

[8] Agarwala A, Dontcheva M, Agarwala M, et al. 2004. Interactive digital photomontage[J].ACM Transactions on Graphic, 2004, 23(3):294-302.

[9] Burt P J, Adelson E H. A multiresolution spline with application to image mosaics[J].ACM Transactions on Graphics, 1983, 2(4):217-236.

[10] Perez P, Gangnet M, Blake A. Poisson image editing [J]. ACM Transactions on Graphics, 2003, 22(3):313-318.

[11] 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.

[12] Szeliski R. Image alignment and stitching: a tutorial[J].Foundations and Trends in Computer Graphics and Vision, 2006, 2(1):1-104.

[13] Gao J, Kim S J, Brown M S. Constructing image panoramas using dual-homography warping[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. New Jersey, USA, 2011:49-56.

[14] Zhang F, Liu F. Parallax-tolerant image stitching[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Ohio, USA, 2014:3262-3269.

[15] Lowe D G. Distinctive image features from scale-invariant key points[J].International Journal of Computer Vision, 2004, 60(2):91-110.

[16] Igarashi T, Moscovich T, Hughes J F. As-rigid-as-possible shape manipulation[J].ACM Transactions on Graphics, 2005, 24(3):1134-1141.

[17] Schaefer S, McPhail T, Warren J. Image deformation using moving least squares[J].ACM Transactions on Graphics, 2006, 25(3):533-540.

[18] Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001,23(11):1222-1239.

PARALLAXIMAGESTITCHINGBASEDONMOVINGLEASTSQUAREMETHOD

Chu Dongdong Li Haisheng
(SchoolofComputerScienceandSoftwareEngineering,EastChinaNormalUniversity,Shanghai200062,China)

Parallax image stitching usually utilizes the feature-based transformation. Existing works focused on the image transformation model, especially a homography, but this is inadequate to obtain better alignment. This paper presents a new stitching method. Firstly, detect and match features in images, then RANSAC and distance similarity are used to investigate the accuracy of matching features. Then, based on these matching point pairs, moving least squares is used to construct a global affine transformation to align two images and get the overlapped region of them. Finally, constructing a network flow whose vertices are the pixels on the overlapped region, and max-flow/min-cut algorithm is adopted to search for a best seam, then stitch and blend images according to this seam. As our method effectively strengthens the matching reliability between SIFT points, the alignment accuracy of two images is better than previous method. Image stitching result is smooth and authentic, no distortion, ghosting or other artifact.

Image stitching Feature matching Moving least square method Stitching curve

2016-08-22。楚东东，硕士生，主研领域：计算机视觉和图像处理。李海晟，副教授。

TP751.1

A

10.3969/j.issn.1000-386x.2017.08.041