'基于泊松方程的图像处理ImageprocessingbasedonPoissonequation数学科学学院计算与应用数学系方轶智PB10001063刘利刚教授二〇一四年五月
中国科学技术大学UniversityofScienceandTechnologyofChina本科毕业论文ADissertationfortheBachelor’sDegree基于泊松方程的图像处理ImageprocessingbasedonPoissonequation姓名方轶智B.S.CandidateYizhiFang导师刘利刚教授SupervisorProf.LigangLiu二〇一四年五月May,2014
学士学位论文题目基于泊松方程的图像处理院系数学科学学院计算与应用数学系姓名方轶智学号PB10001063导师刘利刚教授二〇一四年五月
UniversityofScienceandTechnologyofChinaADissertationfortheBachelor’sDegreeImageprocessingbasedonPoissonequationB.S.CandidateYizhiFangSupervisorProf.LigangLiuHefei,Anhui230026,ChinaMay,2014
中国科学技术大学本科毕业论文致谢首先感谢导师刘利刚教授给我学习的机会,多次亲临指导和给我论文写作的思路及修改建议,并且在我迷茫时开导我,使我明白了,只要对一件事有真正的渴望,就不会受到其他琐事的干扰,环境是不能限制住一个人的行动的,因为行动是由思想驱动的。感谢陆炎同学对我的程序的认真检查,并提出修改意见,并且在我遇到困难的时候,帮助我耐心分析并给予思路的点拨。更要感谢这次毕业设计,让我改变了生活的态度,学到了很多非常实用的编程知识,这将会在我的人生道路上受用无穷。i
中国科学技术大学本科毕业论文目录致谢i摘要iiiAbstractiv第一章绪论11.1背景..................................11.2图像处理的研究现状.........................21.3本文主要的工作............................3第二章偏微分方程及其性质42.1偏微分方程简介............................42.2二阶偏微分方程............................42.2.1波动方程...........................52.2.2热传导方程..........................52.2.3位势方程...........................62.3泊松方程...............................6第三章泊松方程及其应用83.1泊松图像编辑方法..........................83.2图像融合的基本实现.........................93.2.1原理..............................93.2.2离散实现...........................103.3在不同梯度下的应用效果......................11第四章总结与收获15参考文献16ii
中国科学技术大学本科毕业论文摘要从图像获取的角度来说,图像可以分为拍摄获取的和绘制获取的,拍摄比较依赖环境的选取,绘制比较依赖创作者的艺术水平。因此仅仅靠拍摄和绘制的手段来获取理想的图像的成本过高,时间过长。随着计算机图形学技术的飞速发展,图像融合技术可以克服大部分以上缺点,图像融合技术是一种非常高效的生成新图像的方法,已经在电视,电影等可视化媒体中广泛地应用,这同时也能应用于小范围的图像修复。图像融合是图像处理研究中的一项重要内容,它的目的是在原有的几幅图像中,截取其中的一小部分融合到背景图像中,且无明显的边界,不改变背景图的其他特征,给人一种非常自然的效果。这是传统的剪切工具无法做到的。主要的难点是边界自然过度和整体的光照一致。本文在介绍Perez等发表的泊松图像编辑方法的基本框架之后[1],并按照这种方法实现图像的无缝融合和混合融合效果,这里主要使用的数学方法为泊松方程,在边界条件和内部梯度确定后有唯一解,并采用两种不同的梯度进行测试。为了让大家对该技术有一个大概了解,本文首先对图像处理的背景,图像融合的分类和研究现状做了简要说明,并在第二章中简略介绍了偏微分方程的概念,分类,以及定解条件,重点是二阶线性偏微分方程及其在物理中的应用,最后包括泊松方程的简介和应用举例。最后用几个例子说明在两种不同梯度下,与传统克隆工具相比的不同效果和它们的应用,以及图像的小范围修复效果。关键字:图像融合,偏微分方程,泊松方程,无缝融合,混合融合,梯度iii
中国科学技术大学本科毕业论文AbstractImagescanbedividedintotwoparts:gettingbyshootingandgettingbydrawing.Shootingneedsagoodenvironmentanddrawingneedsthecreatorhasahighlevelofart.Gettingimagesasyouwantbyshootingordrawingwhichcostsistoohighandtakestoomuchtime.TheTechnologyofimagefusionhasbeenwidelyusedforTVandmovies,itisaveryefficientwaytocreatenewimages,anditalsocanbeusedforimageinpainting.Imagefusionisanimportantresearchtopicintheareaofimagepro-cessing,itsobjectiveistocutpartsofsomesourseimagesandpastethemtothedestinationdomaininaverynaturalway,withoutapparentboundaryandchangingotherfeatures.Theproblemsarehowtomakethetransitionofboundarynaturalandconsistentwiththeoverallillumination.ThispaperdetailsthepoissonimageeditingpublishedbyPerez,andIwilldoasthewayofthepaperraisedtocompletetheimageseamlessfusion.ThemathematicaltoolattheheartoftheapproachisthePoissonpartialdifferentialequationwithDirichletboundaryconditions,andcom-putethesolutionsbydifferentgradients.AttemptingtomakeanoverviewofImagefusion,atfirstthispaperwillintroducethebackgrandofthistechnology,itslevelsandcontrast,anditsresearchinrecentyears;ThesecondsectionwillintroducethebasicconceptsandclassificationofPDE,thentalkaboutThesecondorderlinearpartialdifferentialequationsandtheirapplicationinphysics,especiallythepoissonequation.Atlast,Iwillshowseveralinstancesindifferentgradientstoexplaintheirapplicatins.Keywords:Imagefusion,PDE,poissonequation,seamlessfusion,mixingfusion,gra-dientiv
中国科学技术大学本科毕业论文第一章绪论1.1背景随着信息时代的到来,我们的生活已经被各式各样的信息所包围,而可视媒体信息占了其中的极大的比例。科学统计和研究表明,75%的人们从外界获得的信息都是视频,图形和图像信息,这些信息都靠视觉系统接收的,而其中的图像信息是可视媒体的一个重要组成部分。图像的种类很多,属性很多,从图像获取的途径来看图像可分为绘制和拍摄两种,在计算机图像处理中,所用的图像的区分也是以上两种,即拍摄类图像和绘制类图像。在计算机图形学中,图像采集,图像分析,图像理解,图像融合以及图像处理等相关处理的对象往往是通过实景拍摄和人工创作获取的图像。拍摄类图像顾名思义是通过实景拍摄获取的,这类图像的特点是:由于摄像机和照相机的使用,在降低了对创作者的要求同时提高了对拍摄时机和拍摄环境的要求,即拍摄对象必须切实存在于拍摄的环境中,且拍摄者对结果的控制能力较低;绘制类图像则要求创作者对图像各方面特点的驾驭能力强且必须有不错的艺术手法,所以图像的成本比较高,耗时长。因此,一副高质量的图像的获取,比想象中的要困难的多。21世纪以来,随着计算机图形学的飞速发展,数字图像处理技术得到了极大的提高,使得对不同图像的无缝融合成为我们获得新图像的重要方法。该方法在重复使用现有图像的基础上,极大地提高了获取图像的效率。无缝图像编辑的要求是将一个或多个来自不同的图像的部分无缝融入到另一个背景图像中,得到一幅新的没有明显人工痕迹的图像。这一技术在电视,电影的制作过程中有着不可替代的应用,例如有些场景是无法通过拍摄实景获得的,就需要使用计算机来合成达到作者想要的效果,或是有些场景需要异地拍摄,成本高昂,就可以采用他人的作品或之前的作品进行再加工,可以极大地降低成本。1
中国科学技术大学本科毕业论文09年我国第一部文化产业专项规划《文化产业振兴规划》提出重点推进:文化创意,影视制作,广告,数字内容和动漫等文化产业。而图像无缝融合正好为这些产业的发展提供了有效的技术基础。1.2图像处理的研究现状图像处理的研究主要集中在图像的修复补缝[2]和图像的无缝融合。其中融合技术应用更广。图像修复技术是根据图像现有的信息经过计算以达到恢复丢失信息的目的。图像修复技术现在主要分为两类:一类是修复小尺寸缺损的图像修补技术。由Bertalmio等引入图像处理中[3],根据破损区域的边缘部分信息对内部进行插值,主要数学方法为使用的热扩散方程来插值内部信息,而基于热扩散方程的颜料扩散方法还被应用于水墨风格的中国画中[4]。另一类是填充图像中大块丢失信息的补全技术,这种技术包含两种方法:一种是基于变分法的图像分解修复技术;另一种为基于快的纹理合成技术,即用纹理块去匹配图像块。两种方法的核心思想都是把图像分成小块后再处理。图像融合由低到高分为三个层次:数据级融合,特征级融合和决策级融合。数据级融合[5]也称像素级融合,是指直接对传感器采集来得数据进行处理而获得融合图像的过程,它是高层次图像融合的基础,也是目前图像融合研究的重点之一。这种融合的优点是保持尽可能多得现场原始数据,提供其它融合层次所不能提供的细微信息。特征级融合是在像素级基础上,使用参数模板,统计分析,模式相关等方法进行几何关联,目标识别,特征提取的融合方法,用于排除虚假特征,以利于系统判决。该层融合的优点在于实现了客观的信息压缩,便于实时处理,其融合结果能够最大限度地给出决策分析所需的特征信息。研究方法主要从类聚分析法,贝叶斯估计,RBF等展开。决策级融合关联各传感器的提供的判决,以增加识别的置信度。决策及融合主要基于认知模型,需要采用大型数据库和专家判决系统来模拟人的分析,推理,识别,判决过程,以增加决策的智能化和可靠性。该层融合的优点在于:通信及传输要求低,容错率高,数据要求低,分析能力强。主要研究方法为贝叶斯估计,RBF2
中国科学技术大学本科毕业论文神经网络法,模糊类聚法及专家系统。三个层次层层递进,而其中最为常用的是数据级融合,本文使用的也是数据级的,因为从像素层面获得的信息更加精确[6],各种细微的特点更不易丢失。图像融合过程其实并不复杂:首先从源图中取得需要融合的部分,把它放入目标图中,进行计算处理后重新显示在相应的位置。最初的技术框架是由Perez等发表的泊松图像编辑方法,这种方法根据泊松方程实现了无缝融合,且用户可以根据自己的需求选择自己要融合的部分。在此之后许多研究者对此经行了优化:Jia等使用修正边缘的迭代优化中能量的定义来实现对源物体边缘的改进[7],这种方式可以更好地改善边界的阴影效果,使目标更具真实感,他们使用的是最短路径算法。Tao等定义了新的边界梯度而且控制边界整合过程,从而改进了梯度域的融合算法[8]。而近几年对融合的源图的实时控制成为了其中研究的热点。其中基于均值坐标[9]和基于GPU的拉普拉斯求解法[10]来对泊松方程的图像融合算法进行加速,前者使用的是基于MVC坐标的方法而不是去解一个大型的线性系统,快速易于操作使用,内存占用小,能够进行大区域的实时克隆,甚至视频流的互动;后者首先提供了一种稳健的光栅化技术转化连续的边界值来分解区域,接着定义了一个可变的模板规模扩散的解决方案来解决极小曲面问题。但是使用过多的源图或过多次的选取会使图像多少产生一些不真实的感觉,于是,Sunkavalli等在2010年提出多尺度图像协调方法在融合过程中迁移对比度,纹理,噪音等特征,避免了图像伪影,解决了图像不真实的问题[11]。1.3本文主要的工作本文主要完成的工作是:在C++环境下,按照由Perez等发表的泊松图像编辑方法基本实现图像融合,并比较在两种不同梯度下,不同融合的效果。3
中国科学技术大学本科毕业论文第二章偏微分方程及其性质2.1偏微分方程简介偏微分方程[12]指的是含有未知函数及其偏导数的方程,它所描述的是自变量,未知函数和偏导数之间的关系,满足方程的未知函数即为该偏微分方程的解。其中方程中所含偏导数的最高阶数称为该偏微分方程的阶数,因此偏微分方程可以按阶数分为一阶,二阶……M阶等。也可以按照线性的定义(若偏微分方程所有部分——未知函数及其偏导数都是线性的,则称为线性偏微分方程)分为线性和非线性。如果对于未知函数最高阶偏导数是线性的方程,则称它为拟线性的。主要应用的对象时一阶,二阶的线性或拟线性偏微分方程,按照所给的定解条件(Cauchy条件和边界条件)来解决实际应用问题。起始条件和边界条件根据它们的特性可以分为三类:第一类:DirichletCondition第二类:Neumanncondition第三类:Robbinscondition2.2二阶偏微分方程二阶偏微分方程的一般形式(以两个自变量为例):Auxx+2Buxy+Cuyy+F(x,y,u,ux,uy)=0(2-1)其中A,B,C为定义在Ω上的连续函数,且A,B,C不同时为0。不失一般性,设A>0.于是上式的特征型为:(())BξDξ2Q(ξ)=Aξ2+2Bξξ+Cξ2=A2+ξ2−2(2-2)1122A1A24
中国科学技术大学本科毕业论文得到判别式:D=B2−AC。根据判别式D可分为:椭圆方程,双曲线方程和抛物线方程。1.D<0:椭圆方程;2.D>0:双曲线方程;3.D=0:抛物线方程。还有特殊的混合型方程,例如Tricomi方程,它是椭圆双曲线方程。以下是三个经典的偏微分方程[13]。2.2.1波动方程波动方程是典型的双曲线方程,其一般形式为:2utt−a∆u=f(2-3)其中f=f(x,t)为已知的实值函数,∆为关于x的Laplace算子。u(x,t)表示质点x在时刻t时沿某固定方向的位移。f取0值时,一维情况下,方程描述的是无外力时的弦的自由振动,因此又叫弦振动方程;二维情况下,方程描述的是薄膜的自由横振动。有外力时,方程为非齐次,即f不为0.2.2.2热传导方程热传导方程是偏微分方程发展史上最早的方程之一,它是抛物线型方程的典型代表。N维热传导的形式是:2ut−a∆u=f,x∈t,Ω>0(2-4)其中a>0是常数。设有一个由均匀且各向同性的介质组成的物体占有三维空间有界区域Ω,并设体内无热源。令u(x,t)为物体在点x于t时的温度,J(x,t)为点(x,t)的热流速度,则在Ω的任一具有光滑边界的有界子域G,在单位时间内流出G的热量是:wJVdsˆ(2-5)∂G由热学定律知:由温度高处流向温度低出的热流速度正比于温度函数的梯度,即J=−kDxu,其中k>0为戒指的热传导系数。体积微元dx的温度升高正比于流入dx内的热量,于是再点(x,t)单位时间内流入微元dx的热量是cutdx,其中c>0是介质单位体积内的热容量。5
中国科学技术大学本科毕业论文所以得到:ww−cutdx=−uvkDˆxdS(2-6)G∂G即:w(cut−k∆u)dx(2-7)G由此便得三维热传导方程:2ut−a∆u=f,x∈t,Ω>0(2-8)其中a2=k/c.2.2.3位势方程位势方程是椭圆型方程的典型代表−∆u=f(2-9)当f(x)恒为0时,成为调和方程,否则称为Poisson方程。具体形式为:∑n∂2u−∆u=−(2-10)∂x2i=1i调和方程描述的是平衡状态,例如描述薄膜微小横振动,如果薄膜处于平衡状态,则位移函数u(x,t)与时间t无关,于是utt=0,方程变为-u=0,同样热传导方程中,若温度u(x,t)处于稳定状态,即不随时间变化,ut=0,从而方程变为-u=0.2.3泊松方程泊松方程是一种特殊的位势方程,当位势方程右边的部分不为零时,即为泊松方程。在静电学[14]很容易遇到泊松方程。对于给定的f找出是一个很实际的问题,因为我们经常遇到给定电荷密度然后找出电场的问题。在国际单位制(SI)中:2ρ∇Φ=−(2-11)ϵ06
中国科学技术大学本科毕业论文此Φ代表电势(单位为伏特),ρ是电荷体密度(单位为库仑/立方米),而ϵ是真空电容率(单位为法拉/米)。如果空间中有某区域没有带电粒子,则ρ=0此方程就变成拉普拉斯方程:2∇Φ=0(2-12)如果有一个三维球对称的高斯分布电荷密度ρ(r):2 rQe22ρr=√3(2-13)2πσ3此处,Q代表总电荷此泊松方程的解Φ(r)则为erfQrrΦ=(√)(2-14)(4πrϵ0)2σerf(x)代表的是误差函数.注意:如果r远大于,erf(x)趋近于1,而电场QΦ(r)趋近点电荷电场;正如我们所预期的。4πrϵ07
中国科学技术大学本科毕业论文第三章泊松方程及其应用3.1泊松图像编辑方法图像编辑包括全局变化和局部变化,我们关心的是我们所选中的局部区域如何几乎无缝且无影响地嵌入到目标图像中。传统的工具来完成局部的剪切,是通过克隆工具直接取代那部分区域的内容,因此选择的片区域的改变会导致明显的边缝,这些边缝只能被选择用的边界部分遮挡,没有较为平稳的过度,而且这也增加了边界选取的难度。所以为了达到我们想要的理想效果,就迫切地需要一种可以消除边缝的且不改变图像其他特征的方法,而且选择区域的方法非常简单。这种无缝编辑和克隆方法的核心是数学工具——泊松方程,需满足在所选区域未知函数的拉普拉斯条件,和它的Dirichlet边界条件:未知函数的边界值与目标图像中所选区域的边界值相同。在这两个条件下方程的解是唯一的。首先,非常著名的心理学家LandandMcCann在1971年提出[15]通过拉普拉斯算子的限制可以减缓渐变的梯度,当把一幅图像叠到另一幅图像上几乎注意不到有什么影响。然后,在目标图像中的选中区域上的标量函数可以被它的边界值和内部的拉普拉斯条件唯一确定。即泊松方程有唯一解,这需要一个合理的算法。所以,在给定了边界条件和内部的拉普拉斯条件后,泊松方程可以完成无缝地填满目标图像中的选中区域。即在RGB三个颜色通道中独立计算得到的值返回到图像的选中区域上,RGB对应红绿蓝三原色,每一幅图像都可以由这三个通道组成。解泊松方程有一个很自然的插值相当于一个最小梯度问题,确定内部区域的梯度,梯度确定选中区域在源图中的引导向量场。在这种方式下,选择一个合理的梯度是解决问题的关键所在。以下将采用多种引导向量场来测试。其中主要给出无缝克隆和混合克隆测试的例子。8
中国科学技术大学本科毕业论文3.2图像融合的基本实现3.2.1原理首先各个参数定义如下图所示:图3.1区域示意图V引导插值:1)S是目标图像区域,Ω是S的一个闭子集,边界为∂Ω;2)f*是S/Ω的一个已知函数,g为源图上的已知函数,f为Ω上的未知函数;3)V是定义在Ω上的向量场,由g的梯度来确定。最简单的用f*来插值f的方法相当于解一个最小值问题:z2min|∇f|(3-1)Ω其中f=f*在∂Ω上,∇为梯度算子。∆f=0overΩ(3-2)∆为拉普拉斯算子,f=f*在∂Ω上为Dirichlet边界条件,对于图像编辑的应用,这个方法产生了一种模糊的插值,其中一种克服这种情况的方法是用一个更为复杂的微分方程,即Bertalmio等在图像修复技术中提出的——使用引导向量场。引导向量场V应用到最小值问题中为:z2min|∇f−v|(3-3)Ω9
中国科学技术大学本科毕业论文其中f=f*在∂Ω上∆f=divv(3-4)在RGB三个颜色通道上分别使用以上方程来求解。3.2.2离散实现以上方程因为内部梯度和边界条件已经确定,可以通过很多方法来解。由于图像像素是离散的,很自然的想到使用像素网格来确定区域。不是一般性,继续使用同样的记号:S在这里可以包含图像的所有像素点或比Ω大一些的区域内的所有像素点。Np定义为与像素点p相邻的上下左右四个像素点的集合,
记为一对像素点,其中q属于Np。Ω的边界∂Ω=p∈SΩ:Np∩Ω̸=0.fp为f在p点处的函数值,在这里函数值为像素点的RGB三个通道的值。以下得到上述问题的离散形式:∑2min(fp−fq−vpq)(3-5)
Ω!=0∑∑∑|Np|fp−fq=(fq)+vpq(3-6)q2NpΩq2Np∂Ωq2Np然后根据以上方程,以所有未知点的RGB值作为未知向量建立方程组,进行矩阵求解。10
中国科学技术大学本科毕业论文3.3在不同梯度下的应用效果对于无缝克隆部分,实现的是用以下方程确定的向量场:Vpq=gp−gq,对所有Ω上的p都成立。把熊融入到背景图中的效果为:(a)选中游泳的熊(b)传统复制粘贴(c)无缝融合效果图3.2无缝融合效果11
中国科学技术大学本科毕业论文这种方法也可以进行对图像的修补:(a)选中特征类似的部分(b)修补效果1(c)修补效果2图3.3修补效果对比12
中国科学技术大学本科毕业论文对于混合克隆部分,使用的是:Vpq=fp−fq当|gp−gq|<|fp−fq|时,否则Vpq=gp−gq,(a)原图蜡笔画(b)用第一种梯度实现(c)用第二种梯度实现图3.4混合融合效果13
中国科学技术大学本科毕业论文也可以应用于风景图像的编辑(a)彩虹(b)背景图(c)混合融合图3.5彩虹融合效果14
中国科学技术大学本科毕业论文第四章总结与收获本文主要的工作为通过C++环境下编程实现Perez等发表的泊松图像编辑方法,并简要介绍了图像处理研究,以及偏微分方程。图像融合是如今对图像再加工的一种非常有效的方式,相对于绘制类图像不需要艺术手法,相对于拍摄类图像没有环境的要求,在生成新图像的方式中无疑是一种捷径。图像融合分为三个层次:数据级融合,特征级融合和决策级融合。其中数据级从像素出发精确度最高,也是最为常用的方法。偏微分方程的应用源于物理学中。其中二阶线性三大经典方程有:波动方程,热传导方程,位势方程。通过初始条件和边界条件可以求得唯一解。泊松方程是非齐次的位势方程,在电磁学中有广泛的应用。在这里它应用于图像的无缝编辑。泊松图像编辑在泊松方程离散化后,根据确定的边界条件还内部的梯度后建立线性方程组求得唯一解,RGB三个像素通道需要分别求值,返回到图像上显示出来。接着总结一下图像融合的效果。和传统的复制工具相比,两种梯度都能很好地消除明显的边界。在第一种梯度下,图像能更好的保持源图的特征;在第二种梯度下,图像能更多地保持背景图的特征。所以,可以根据需求使用不同的梯度,来达到理想的效果。除此之外,无缝融合在图像局部修复方面也有不错的应用价值。最后通过毕业设计,不仅学到了新的知识,练习了编程,对图像融合技术也有了更加深刻的理解,为我下阶段的学习打好了基础。15
中国科学技术大学本科毕业论文参考文献[1]MichelGangnetPatrickPerezandAndrewBlake.Poissonimageediting.SIGGRAPHAsia,2003.[2]张红英,彭启琮.数字图像修复技术综述.中国图像图形学报,2007年1月.[3]CasellesV-andBallesterCBertalmioM.,SapiroG.Imageinpainting.InProceedingsofACMSIGGRAPH2000,2000.[4]马燕.水墨风格融合图像的计算机模拟.硕士论文,2013.[5]郭雷.图像融合.电子工业出版社,书号:ISBN978-7-121-05885-1,北京,2008.[6]王春华.图像融合研究综述[j].科技创新导报,2011年13期.[7]TangC.-KShumH.-YJiaJ,SunJ.Dragand-droppasting[j].SIGGRAPHAsia,2006.[8]ParisSTaoM.W,JohnsonM.K.Error-tolerantimagecompositing[j].InProceedingsofthe11thEuropeanconferenceonComputervision:PartI,2010.[9]LipmanY-Cohen-orD-LischinskiDFarbmanZ,HofferG.Coordinatesforinstansimagecloning.ACMTrans.Graph.28,3,2009.[10]WonkaPJeschkeS,ClineD.Agpulaplaciansolverfordiffusioncurvesandpoissonimageediting[j].ACMTrans.Graph.28,2009.16
中国科学技术大学本科毕业论文[11]MatusikW-PfisterHSunkavalliK,JohnsonM.K.Multi-scaleimageharmo-nization[j].ACMTrans.Graph.29,4,2010.[12]陈祖墀.偏微分方程第三版.高等教育出版社,书号:ISBN978-7-04-023587-6,合肥,2008.[13]季孝达,薛兴恒,陆英,宋立功.数学物理方程.科学出版社,书号:ISBN978-7-03-025823-6,合肥,2009.[14]胡友秋,程福臻,叶邦角.电磁学与电动力学(上册).科学出版社,书号:ISBN978-7-03-021753-0,合肥,2008.[15]McCannJLandE.Lightnessandretinextheory.J.Opt.Soc.Amer.61,1971.17'