【基于图切割的图像拼接技术】 基于sift算法的图像拼接技术

　　摘要：图像拼接作为基于图像绘制的一部分近年来成为研究的热点之一。本文对图像拼接技术进行研究，详细的分析了新的基于图切割的拼接方法。该方法在相位校正的基础上将图切割和泊松融合相结合实现拼接，图切割用于搜索全局最优的缝合线以去除鬼影，泊松融合用于曝光差异的处理。本文给出新的基于梯度方向直方图统计的权值计算方法，实现稳定的图切割。另外，本文还设计出重叠过渡的泊松融合方法，较好地完成图像合成。
　　关键词：图像拼接；图切割；泊松融合
　　中图分类号：TP302文献标识码：A文章编号：1009-3044(2007)18-31715-02
　　A NoveI Image Mosaic Method Based on Graph Cut
　　WANG Qi-hui
　　(Hangzhou Normal University,Hangzhou 310011,China)
　　Abstract:Image mosaic is one of the topics of image based rendering(IBR) these years.A noveI image mosaic method based on graPh cut.This method first calculates. Phase correlation and then reaches image mosaic by graph cut and poisson image fusion.Graph cut is used to find a globally optimized seam-line for deghosting while poisson image fusion is used to realize smooth mosaic without exposure difference.A new weight calculation method based on the statistics of guadient direction histogram is presented here in order to robustly realize graph cut.An edge transition poisson image fusion method is also proposed to reach exposure difference removal
　　Key words:image mosaic;multiresolutions pline mosaic;graph cut
　　
　　前人对图切割在图像编辑上的应用已做一些研究[Ag~l2a004，Lvein2004，Li2004，Roht2er0O4]，这些应用的特点都是如何定义合适的权系数以完成特定的应用需求，而所有的这些权系数都是直接利用色彩强度差或梯度强度差进行计算。在泊松融合方面的应用，Ag~ala等A[g~l2a004]提出的基于纽曼边界条件的泊松融合技术以实现片段间的合成，从而保持两个不同片段间的连续过渡。本文将图切割和泊松融合应用到图像拼接中，提出基于图切割的拼接方法。该方法在相位校正的基础上先利用图切割寻找一条最佳缝合线以消除鬼影，再利用泊松融合实现合成以消除曝光差异。为提高算法的稳定性，本文提出新的基于梯度方向直方图统计的权值计算方法，将梯度强度和方向相结合，克服前人只是基于强度得到的权值的不稳定性。本文还提出重叠过渡的泊松融合方法，通过将重叠区划分成两个片段然后分别执行泊松融合，实现平滑过渡。
　　
　　1 基于图切割的最佳缝合线搜索
　　
　　1.1 图切割与最大流问题简介
　　在计算机视觉里常常遇到标识(labeling)问题，比如如何对图像分段，如何确定象素的深度等。这样的标识问题，实际上也是最小化问题，即如何保证算法标识的结果和实际观察的数据之间能量差达到最小以保证标识的正确性：E(f)=Esmooth(f)+Edata(f)
　　其中，Esmooth(f)仍表示相邻两个象素间的光滑度，Edata(f)表示标识值与实际观察值
　　之差。标识问题中常常要研究如何进行两个标识的划分问题，比如用s和t两个标识对一幅3x3图像进行最佳的标识划分以到能量差最小。如下图1所示，解决这幅图像的两个标识划分问题需要建立如图所示的带权有向图，权值的大小在这里简化为边的粗细来表示，用两个分别叫源节点s和接收节点t的终点节点表示这两个标识。在这个图里有两种弧，一种是由源节点或接收节点发出的，叫t弧，权值为Edata(f)；另外一种是相邻象素间互相连接的弧，叫e弧，权值为Esmooth(f)。图的切割(cut)就是要将这个有向图切成两个部分S和T，s放在S里，t放在T里。最小切割就是要找到代价最小的一个切割，这也就是我们所说的图切割问题。如图1中右图的虚线就表示这样的一个切割。
　　对于图1所示的带权有向图(其中圆圈表示节点，直线表示有向边)，如果将其想象为图2所示的一个水管网络，那么图切割问题可以描述成如何求解在某一时刻从s到t能通过的最大流量的问题。 [Ford1962]中指出从s和t间的最大流在将这个有向图分成两个部分 (S和T)的边组成的最小切割上饱和，也即这个切割上的水流之和就是最大流。求解有向图的最小切割问题就是求解最大流的问题，已有很多算法对最大流问题进行研究[Boykov2004，Boykovl999]，本文的算法引自[Boykovl999]。
　　1.2最佳缝合线搜索
　　下图3显示如何对图像重叠区进行图切割的初始化。在图3(a)中，IM和IN表示两幅相邻图像，Iover表示重叠区。首先建立两幅图像间如图3(b)所示的带权有向图，这里假设重叠区的大小为3x3，IM和IN分别作源点(M)和接收点(N)。M和N分别向相邻的重叠区内的象素发出t弧，同时重叠区内的象素向四个邻域象素发出e弧。t弧权值大小为∞，这样可以保证切割线不穿过重叠区的边界，从而保证切割。e弧权值的定义方法是实现图切割算法的关键。
　　
　　图3 图切割拼接原理
　　前人的方法都是基于梯度强度或色彩强度进行e弧的权值计算。由于相邻图像存在曝光差异，因此基于色彩强度差是不稳定的。梯度强度差虽然在一定程度上强调几何结构上的相似的，但是由于噪声和配准误差的影响，仅仅梯度强度上的相似性也是不够的，还必须要考虑图像中纹理变化方向的相似性，即梯度方向上的相似性。为此可以对每个象素的邻域进行统计得到该象素的梯度方向直方图，然后将e弧权值的求解建立在相邻象素间的梯度方向直方图比较之上，这样得出的权值结合梯度强度和方向的影响，可以有效表达该象素点及其周围象素的特点。结合图4所示的两幅带蓝框标识的源图像，具体的。弧权值求解过程如下：
　　(l)初始化:对于图像上的每个点计算相邻区域的梯度方向直方图。梯度方向直方图统计是对周围半径；的圆形区域，以该象素点为中心采用高斯加权的方式统计邻域内所有象素点在各个梯度方向的强度之和。高斯加权一方面降低噪声的影响，另外一方面也强调离中心点近的象素的作用。
　　(2)峰值求精:梯度方向直方图峰值反映象素及其周围的主要分布特征，因此需要对其进行求精。求精的方法是首先对峰值方向的强度和其相邻三个方向的强度的进行抛物线拟合，然后用拟合得到的抛物线的峰值替代原峰值。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　
　　2 重叠过渡的泊松融合
　　
　　2.1泊松融合原理
　　如图5所示，R2上的封闭子集s是一个的图像定义域。?赘是s上的一个封闭子集，其边界是?鄣?赘，假设f是定义在?赘上未知的标量函数，f*是定义在?鄣?赘上已知的标量函数，那么求解f最简单的方法是用模插值来求解：
　　图5中的右图就是指导场v的一个示意，借助这个指导场，模插值的目标就是希望f具有和v一样的变化场。这样，上式的最小化就变成如下的相对于指导场的最小化：
　　具体到图像合成，取指导场为待合成图像区域的梯度场，然后利用上式就可以将被合成的图像无缝融合到待合成图像区域中。
　　2.2重叠过渡的拼接
　　图6如何利用泊松融合技术实现基于缝合线的图像拼接。为方便解释，我们将这种实现方法定义为重叠过渡的泊松融合方法。具体执行步聚如下：
　　(3)未知区域泊松融合求解。对每个未知区域按前面计算式进行求解就实现重叠区的融合过渡。
　　图6 重叠过渡的泊松融合
　　2.3高斯一赛德尔方程求解
　　未知区域的每个象素点得到的计算式组合到一起，可以写成UX=v的形式。由于系数U是对称、稀疏的正定矩阵，因此可以用超松驰的高斯一塞德尔迭代方法(SOR)求解，迭代过程如下式所示：
　　对于两个重叠区占到三分之一的640x480的图像来说，每个未知区域通常会有50000
　　左右的象素，这样就会得到一个U为50000x50000左右的超定方程组，显然直接用SOR法计算占用空间太大，计算速度慢。
　　但是因为每个象素最多4个近邻，所以上式的n个未知解中只存在4个未知数需要更新。假设图像坐标系原点在图像的左下角，逐行逐列编号，则这4个数分别为编号小的左邻和下邻以及编号大的右邻和上邻。因此，假定第i个象素的下邻和上邻的编号分别s和t，结合前面式，可以将上式(简化为：
　　这里表示第i象素的相邻象素的个数，即Np。上述简化计算明显加快计算速度，节约存储空间。
　　
　　3 结束语
　　
　　本文提出基于图切割的图像拼接方法，这个方法利用图切割查找出一条全局最佳缝合线，用泊松融合实现最终的合成。为提高图切割的稳定性，本文给出基于梯度方向直方图统计的权值计算方法，通过计算每个象素点邻域的梯度方向直方图，将象素点的梯度强度和方向结合一起进行权值计算，克服前人方法基于色彩强度或梯度强度的权值计算方法的不稳定性，达到了较好的图切割缝合线搜索。本文还设计重叠过渡的泊松融合方式，通过将重叠区划分成两个未知区域，分别定义实现平滑过渡过的边界值，实现曝光差异的处理。
　　
　　参考文献：
　　[1]梅春晖.基于预计算及采样的实时高真实感图像绘制技术研究,博士学位论文,浙江大学,2004.
　　[2]漆驰,刘强.等.摄像机序列的全景图拼接,计算机辅助设计与图形学学报,2001.
　　[3]阮宗才,梁栋.等.一种自动全景拼图的快速算法,计算机研究与发展,2001.
　　[4]王立峰,潘志庚.全景图像的拼合及优化算法,计算机应用研究,2006.
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文