（运筹学与控制论专业论文）基于四阶偏微分方程的分裂bregman图像复原方法.pdf

硕士学位论文 摘要 1 9 9 2 年，r u i n ，o s h e r 和f a t e m i 在他们开创性的论文中提出了著名的基于全变 差的r o f 图像复原模型从那时起，基于变分偏微分方程的图像复原方法开始了其 快速发展的历程由r o f 模型导出的e u l e r - l a g r a n g e 方程为一个二阶偏微分方程， 按照该方程得到的复原图像具有良好的性质，它可以在消除噪声的同时保持图像 的边缘但是r o f 模型存在“阶梯效应 的缺点并且计算也较为复杂，因此大量修 正或扩展模型以及快速计算方法被提出来克服这些不足 本论文主要研究如何结合具有良好性质的一种四阶变分偏微分方程模型一l l t 模型和一类快速优化算法一分裂b r e g m a n 迭代方法来进行图像复原工作，使得我 们在获得较好的图像复原效果的同时花费较少的计算代价全文由如下五章组成 第一章简要介绍了图像复原的基本知识和变分偏微分方程方法在图像复原领 域中的相关成果 第二章介绍了一些数学基础知识，它们是利用变分偏微分方程方法进行图像复 原任务的理论基础 第三章介绍了用于求解图像复原问题的b r e g r n a n 迭代方法与分裂b r e g m a n 迭 代方法，并给出了它们的收敛性，它们对本论文的工作具有很强的启发意义 在第四章中，我们将分裂b r e g m a n 迭代方法与u j 模型结合起来，提出了基于 四阶偏微分方程的分裂b r e g m a n 图像复原方法同时，我们还证明了所提出方法的 收敛性 在第五章中，我们详细推导了所提出方法的数值计算格式并进行了数值实验， 实验结果表明该方法非常快，解得的复原图像也具有良好视觉效果 关键词：图像复原；四阶偏微分方程；变分法；分裂b r e g m a n 迭代 i i 硕士学位论文 a b s t r a c t i n1 9 9 2 ，r u d i n ，o s h e ra n df a t e m ii nt h e i rp i o n e e r i n gp a p e r p u tf o r w a r daw e l l - k n o w nt o t a lv a r i a t i o n - b a s e di m a g er e s t o r a t i o nm o d e l w h i c hi sc a l l e dt h er o fm o d e l s i n c et h e n ，t h ev a r i a t i o n a lp a r t i a ld i f f e r e n t i a le q u a t i o n - b a s e di m a g er e s t o r a t i o nm e t h o d s b e g a nt h e i rr a p i dd e v e l o p m e n tp r o c e s s t h ee u l e r - l a g r a n g ee q u a t i o nd e r i v e df r o mt h e r o fm o d e li sas e c o n d - o r d e rp d e ，w h i c hc a nb eu t i l i z e dt oo b t a i nt h er e s t o r e di m a g e w i t hag o o d q u a l i t y ：i tc a nr e m o v en o i s ew h i l ep r e s e r v i n gt h ee d g e so fa ni m a g e h o w e v e r , t h er o fm o d e lh a sa l s os o m es h o r t c o m i n g ss u c ha s “s t a i r c a s ee f f e c t s ，a n dm o r e c o m p l i c a t e dc o m p u t a t i o n ，s oal o to fm o d i f i e do re x t e n d e dm o d e l sa n df a s tc a l c u l a t i o n m e t h o d sa r ep r o p o s e dt oo v e r c o m et h e s ed e f i c i e n c i e s i nt h i sd i s s e r t a t i o n ，w em a i n l ys t u d yh o wt oc o m b i n eac l a s so ff o u r t h o r d e rv a r i a - t i o n a lp a r t i a ld i f f e r e n t i a le q u a t i o nm o d e l sw i t hg o o dn a t u r e l l tm o d e la n dac l a s so f f a s to p t i m i z a t i o na l g o r i t h m s - - s p r i tb r e g n u mi t e r a t i v em e t h o dt or e c o v e ra n i m a g es ot h a t w eo b t a i nb e t t e ri m a g er e s t o r a t i o ne f f e c tb u tt a k el e s sc o m p u t a t i o n a lc o s lt h i st h e s i si s c o m p o s e do ft h ef o l l o w i n gf i v ec h a p t e r s i nt h ef i r s tc h a p t e r , t h eb a s i ck n o w l e d g eo fi m a g er e s t o r a t i o na n dt h ec o r r e l a t i v e a c h i e v e m e n t so nt h ev a r i a t i o n a lp d e - b a s e di m a g er e s t o r a t i o na r eb r i e f l y p r e s e n t e d t h es e c o n dc h a p t e ri sd e v o t e dt oi n t r o d u c i n gs o m eb a s i cm a t h e m a t i c a lk n o w l e d g e w h i c ha r et h e o r e t i c a lf o u n d a t i o no ft h ev a r i a t i o n a lp d e - b a s e di m a g er e s t o r a t i o n i nt h et h i r dc h a p t e r , w ei n t r o d u c eb r e g m a ni t e r a t i v em e t h o d sa n ds p l i tb r e g m a n i m r a t i v em e t h o d sa n dg i v et h e i rc o n v e r g e n c e ，w h i c hg r e a t l y i n s p i r eo u rw o r k s i nt h ef o u r t hc h a p t e r , b yc o m b i n i n gs p l i tb r e g m a ni t e r a t i v em e t h o da n dt h el u m o d e l ，w ep r o p o s eaf o u r t h - o r d e rv a r i a t i o n a lp d e - b a s e ds p l i tb r e g m a ni t e r a t i v em e t h o d f o ri m a g er e s t o r a t i o n a tt h es a m et i m e ，w ep r o v et h ec o n v e r g e n c eo ft h ep r o p o s e d m e t h o d i nt h ef i f t hc h a p t e r , t h en u m e r i c a lc o m p u t a t i o n a ls c h e m eo ft h ep r o p o s e dm e t h o di s d e d u c e di nd e t a i la n dt h en u m e r i c a le x p e r i m e n t sa r ei m p l e m e n t e d e x p e r i m e n t a lr e s l u t s s h o wt h a tt h ep r o p o s e dm e t h o di sf a s tw i t hg o o dv i s i o ne f f e c t k e yw o r d s ：i m a g er e s t o r a t i o n ；f o u r t h o r d e rp a r t i a ld i f f e r e n t i a le q u a t i o n s ；v a r i a t i o n a l m e t h o d s ；s p l i tb r e g m a ni t e r a t i o n i i i 硕士学位论文 第1 章绪论 1 1 数字图像处理简介 所谓数字图像处理，就是指借用数字计算机及其他有关数字技术，对数字图像 施加某种运算和处理，从而达到某种预想的目的图像处理是一门跨领域的学科， 它在自然科学，工程学和医学中均有着广泛而深刻的应用在计算机技术兴起之前， 图像处理的应用通常是视觉检测而在当今时代，随着数字化技术的高速发展，从 纳米技术、天文学、远程遥感、安全监视和娱乐产业到信号滤波、模式识别、医学 检测以及计算机辅助设计，数字图像处理技术已经覆盖了现代科技的诸多领域并给 人类社会带来了巨大的影响和冲击【1 1 典型的图像处理过程可以由下图表示： 图1 1 图像处理 这里，厂是观测到的图像，p 表示图像处理的方法，它可能包括各种随机性或确 定性的方法并可能具有线性或非线性的形式而跖二般是我们感兴趣的图像或图 像的某些特征，比如说纹理，边缘和轮廓 而从数学研究的角度看，数字图像处理通常由以下三个主要部分组成： 建立模型设计或寻找与u 和p 相对应的合适的数学模型，分析其基本原理 以构建模型结构并考虑模型的主要特征 分析模型分析用于描述u 和p 的模型是否合适，模型的解即输出图像h = p 是否存在且唯一，并考虑一个好的解应具有什么样的特征由于在很多时 候图像处理问题都可以归结为一个不适定问题，所以解的存在性，唯一性和稳 定性是模型分析中非常重要的因素 计算模型即如何有效地计算模型的解我们往往要考虑应采取什么样的数 值计算方法来保证解的收敛性和稳定性，同时也要考虑如何正确地来表述所求 出的结果 基于四阶偏微分方程的分裂b r e g m a n 图像复原方法 作为信号处理技术的一部分。传统的图像处理技术是建立在f o u r i e r 分析和谱 分析理论的基础上在过去几十年中，科研人员已经提出了许多关于图像处理的方 法和工具比如基于g i b b s m a r k o v 随机场理论和b a y e s i a n 理论的随机性方法 2 3 1 、 结合几何正则性的变分方法【4 洌、偏微分方程方法【1 ，6 】以及以小波为核心的调和分 析方法【7 ，羽等这些方法在外在形式上表现出了很大的差异，但他们却在本质上密 切相关每种方法都是从不同的某一特定的角度出发，并受到各自理论和应用背 景的限制而另一方面，在更深的层次下，它们有着共同的理论基础，这一特点也使 得研究人员可以结合这些不同领域的研究成果，从而发展出大量新的混合型方法 1 2 图像复原问题在数学上的表述 在图像的成像、记录和传输过程中，退化是常常遇到的问题在数学上，图像退 化的原因通常可分为两类一类是确定性的，它往往和图像获取的方式有关，比方 说图像成像时镜头焦距调整有误，成像对象和成像器材发生了相对移动或者由于类 似于大气湍流的现象而造成图像成像模糊另一类则是随机性的，它往往由噪声引 起，在信号传输的过程中，由于外部环境的干扰或传输介质固有的缺陷，图像几乎无 法避免受到噪声的“污染” 图像复原则是针对图像退化来说的，它可以看成是后者的逆过程图像复原的 工作在于研究图像退化的机理，建立退化过程的数学模型，而后采取措施使得图像 在退化过程中产生的失真得到修复虽然说图像复原是图像处理中最古老也是最基 础的工作，并且在研究和应用领域都已经取得了很大的成果，但它仍然是当前的一 个富有挑战性的问题，并且它对图像处理的其它方面有着极为重要的影响，所以图 像复原问题一直都是图像处理领域的一大研究热点f 9 】 典型的图像退化和复原过程可用下图表示： 圈一囹 圈 曰一圈 图1 2 图像的退化与复原 而在数学上。我们常常可以将图像复原问题做如下表述： 一2 一 仓圈 硕士学位论文 令拈：1 1 r 2 一r 为原始图像，为退化了的图像且与m 有相同的定义域和值 域则有 f = a u + 1 ， 图像复原问题就是在已知退化图像厂的情况下，由式( 1 1 ) 式来重构出原始图像h 这里4 为一线性算子，它一般为一个卷积算子，表示模糊过程；1 ，则表示加性噪声，为 一个随机变量，在大多数情况下，它服从g a u s s 分布，当然，在某些特定背景下，它也 有其它的分布情形比如在雷达成像图像中，噪声y 一般服从g a m m a 分布，而在x 射线断层扫描图像中它往往被认为服从p o i s s o n 分布在本文中，我们假设所有的 噪声在图像区域上都为g a u s s 型的独立同分布的随机变量特别地，当线性算子a 为恒等算子j 时，图像复原问题就成了一个纯去噪声的问题事实上，这也是图像复 原任务中最常见最基本的问题，在本文中，我们主要是针对这个问题来进行讨论 1 3 基于变分偏微分方程的图像复原方法 正如前面介绍的那样，图像处理领域的各种方法都可以结合起来应用而得到新 的处理手段，其中一类就是将变分法与偏微分方程理论结合起来并应用到图像复原 的任务当中在本文中，我们将其称为基于变分偏微分方程的图像复原方法 由于引入了变分法和偏微分方程，我们在图像复原任务中获得了一种强大的数 学工具变分法所涉及的凸优化理论与偏微分方程相关理论在数学上均有着深入的 系统研究，这些理论基础为进行图像复原的相关工作提供了极为有力的数学支撑 并且，由于偏微分方程能很好地反映自然世界中的物理现象，这种方法使得我们可 以很好的建立起符合客观实际的图像复原模型更重要的是，它具有高度的灵活性， 采用这种方法建立的模型可以很方便的进行推广。从而使我们可以从更加全面的视 角来分析图像复原任务的数学本质 基于变分偏微分方程的图像复原方法是一种确定性的方法，它通过引入能量函 数，将图像复原问题转化成泛函求极值问题，再由变分法的相关理论将其转化为求 解一个偏微分方程简单地说，它可以分为以下几个主要步骤【1 0 1 ： ( 1 ) 从实际问题的物理意义出发，建立相应的泛函极小值问题并寻找其约束条 件； ( 2 ) 通过泛函变分，利用变分法求得e u l e r - l a g r a n g e 方程，通常是一个偏微分方 程； ( 3 ) 在适当的边界条件下求e u l e r - l a g r a n g e 方程的数值解 基于变分偏微分方程的图像复原方法兴起于上世纪9 0 年代，r u d i n ，o s h e r 和 一3 一 基于四阶偏微分方程的分裂b r e g m a n 图像复原方法 f a t e m i 在他们开创性的论文中提出了著名的r o f 图像复原模型【l l 】 ， 珊) 上酬d x d y 盯i l u - 川；删a r 2 ， ( 1 2 ) 其等价的无约束形式为 1 2 1 埘疏上帆id x d y + 乏a 陋卅i ； ( 1 3 ) 这里，i v u ld x d y 表示函数“在区域q 上的全变差，其具体定义将在下一章中 介绍由于数字图像自身显示和保存上的特点，一般假设q 为r 2 空间中的矩形区 域，i q i 表示该区域的面积函数厂：q r 表示已知的被噪声“污染”后的图像，即 f = “+ 1 ，矿表示图像厂中噪声 ，的标准差i 1 表示空间r 2 中的e u c i l d e a n 范数， 对应于r o f 模型，有i v u l = i ( 魄，坳) i - 嵋+ 嵋b v ( o ) 表示定义在区域q 上的有 界变差函数全体所组成的空间 在文【il 】中，r u d i n 等提出了一种求解r o f 模型的梯度下降方法其主要思想 是从图像演化的角度出发，引入了一个“时间 辅助变量，从而将之前讨论的静态 图像“仇y ) 看作一个关于空间和时间的函数u ( x ，y ，力，并使得图像按照模型的要求 随时间进行演变 梯度下降方法存在着收敛速度慢和精度不高的缺点，从而严重限制了r o f 模 型的实际应用针对这些缺点，众多研究人员提出了许多新的数值算法，比如由 v o g e l 和o m a n 提出的时滞扩散固定点迭代方法f 1 3 1 ，由c h a r t ，g o l u b 和m u l l e t 提出 的结合牛顿法和本原对偶系统的c g m 方法【1 4 】，以及由c h a m b o l l e 提出的对偶算 法【1 5 】等 r o f 模型最大的优点在于它在去除噪声的同时可以很好地保持边缘，而边缘 往往被认为是图像中最重要的特征信息这一良好特点使得它的模型结构和构建思 想被推广到许多图像复原任务中，比如图像去模糊和图像修补问题等虽然，该模 型同时也存在着复原图像具有“阶梯效应”( s t a i r c a s ee f f e c t s ) 的缺点【1 6 1 ( 具体可见 第五章实验3 ) ，但是这并没有妨碍它成为近年来图像复原领域中最为成功的模型 之一目前，r o f 模型及其思想已经受到了大量研究人员的关注，众多学者均致力 于研究r o f 模型的性质并作出改进比如，为了克服r o f 模型中存在的“阶梯效 应，l y s a k e r , l u n d e r v o l d 和协在文【1 7 】中提出用二阶微分算子代替r o f 模型中 的梯度算子，以此发展出了u j 模型 m i l l fi v 2 u l d x d y + 卸h 一朋 ( 1 4 ) q z 其中。 i v 2 “i ：= l u x x l + i l ， ( 1 5 ) 4 硕士学位论文 一 或 一一一， i v 2 u l ：= “乏+ 吗+ 咄+ 略 ( 1 6 ) 实验表明，该模型在处理非块状的图像时可以很好的减弱r o f 模型带来的“阶梯 效应 ，同时也继承了其保持边缘的良好性质 m e y e r 等则在b v 空间的对偶空间g 空间上研究了r o f 模型的性质，并提出 了基于g 空间中的范数进行约束的优化模型【1 8 】 蜒i n f 上n v u i d x d y + 五“一，g ) ( 1 7 ) 这里 g = vi v = 船t + 弧，扎9 2 r ( r 2 ) ) ， 俐o = 础i n ，f 舰， l l 麻l l l - v - 弧+ 掘) ( 1 8 ) ( 1 9 ) 该模型能很好地检测到图像中存在的纹理特征 一些学者还结合应用了变分偏微分方程方法和其它类型的方法，如由李敏和冯 象初提出的结合小波自适应滤波方法和变分偏微分方法的双阶段混合型方法d 9 1 ， 这种方法很好的综合了这两个图像处理方向的各自优点 近年来，一种基于b r e g m a n 距离的迭代模型受到了广泛的关注并应用到图像 处理的各个领域【2 0 1 在此基础上，g o l d s t e i n 等提出了分裂b r e g m a n 迭代复原模型， 它可以用来快速求解包括r o f 模型和u j 模型在内的l 1 范数优化问题【2 1 1 ；y i n 等提出了线性化b r e g m a n 模型并将其应用到压缩传感这一新兴的图像处理领域中 f 2 2 - 2 4 1 ；b u r g e r 等则进行了研究和推广，并发展出了一种更广泛意义下的非线性逆尺 度空间方法 2 5 2 7 1 值得提出的是，由于r o f 模型在基于变分偏微分方程的图像复 原方法中的指导性意义，前面提及的计算r o f 模型的数值方法也可以直接或经修 改后应用到其它大量的图像复原模型中 2 8 - 3 1 1 相关的模型和计数值算方法我们将 在第三章中给出更详细的说明 1 4 本文的主要工作 近年来，基于变分偏微分方程的图像复原方法因r o f 模型的成功而倍受关 注，甚至可以说r o f 模型的出现直接推动了这一研究方向的发展但前面已经提 及r o f 模型的解存在“阶梯效应”的缺陷，而由其发展而来的l l t 模型可以有效 地克服这个不足l l t 模型的e u l e r - l a g r a n g e 方程为一个四阶的偏微分方程，由该 方程解得的复原图像比较平滑，可以在保持边缘的同时较好地处理图像的平坦区 域，从而显著减弱“阶梯效应，使得其视觉效果更加符合自然图像的特点但该模 一5 一 基于四阶偏微分方程的分裂b r e g m a n 图像复原方法 型存在计算较为复杂的问题，传统的梯度下降方法在求解由u 模型导出的四阶 e u l e r - l a g r a n g e 方程时将不可避免地遇到计算代价较大的问题 为了使复原图像具有较好的视觉效果的同时加快计算速度，在本文中我们将分 裂b r e g m a n 迭代方法与u j 模型结合起来，得到相应的能量泛函，再由变分法的知 识推导出它的e u l e r - l a g r a n g e 方程。这是一个可以快速求解的四阶偏微分方程我 们将从理论上严格证明所提出方法的收敛性，同时，我们还将详细研究和推导相应 的数值计算方法并进行数值试验来实际检测所提出方法的有效性实验结果表明 所提出方法在去噪效果，克服“阶梯效应 及快速性等方面比传统的梯度下降方法 都均有改进全文由如下五章组成： 第一章简要介绍了图像复原的基本知识和变分偏微分方程方法在图像复原领 域中的相关成果 第二章介绍了一些数学基础知识，它们是利用变分偏微分方程方法进行图像复 原任务的理论基础 第三章介绍了用于求解图像复原问题的b r e g m a n 迭代方法与分裂b r e g m a n 迭 代方法，并给出了它们的收敛性，它们对本论文的工作具有很强的启发意义 在第四章中，我们将分裂b r e g m a n 迭代方法与u 卫模型结合起来，提出了基于 四阶偏微分方程的分裂b r e g m a n 图像复原方法同时，我们还证明了所提出方法的 收敛性 在第五章中，我们详细推导了所提出方法的数值计算格式并进行了数值试验， 实验结果表明该方法非常快，解得的复原图像也具有良好视觉效果 一6 一 硕士学位论文 第2 章预备知识 本章介绍求解图像复原问题时常用到的数学基础知识，包括有界变差函数空 间、外点罚函数方法、变分法和e u l e r - l a g r a n g e 方程以及微分方程数值解法的相关 内容 2 1 有界变差函数空间 有界变差( b o u n d e dv a r i a t i o n ) 函数空间被认为是一种比较合理的描述非纹理 图像的函数空间，它允许图像函数存在边缘、纹理等重要而不连续的信息，同时在 数学上它也比较容易处理有界变差函数理论为很多图像处理模型提供了必要的 数学基础这里，我们首先介绍有界变差函数空间理论 定义2 1 1 令q 为r n 中的有界开子集，i g 为l 1 ( q ) 空间中的函数其全变差定 义为： i v ( “) = f nl d u l ：= s u p f n - u v c a d x = - ，忱，蛳) c 5 ( q ) n ，曲b l ( 2 1 ) 其中，v 一竺l 蕊0 为散度算子，d x 为l e s b e s g u e 测度，函数空间c 6 ( q ) n 为q 中具有 紧支集的连续可微函数，i b 1 表示向量值函数所有分量的l ”( q ) 模都不超 过1 需要指出的是，如果有y u c 1 ( q ) ，即“是定义在q 上的一阶连续可微函数， 由g r e e n 公式，可得f nu v w d x = 一f nv u u d x ，这里v u 表示两个n 维向量的 欧几里德内积所以上i d u l = 厶i v u ( x ) ld x 其中v u = ( 筹，老，器) ，这里的偏 导数是古典意义下的偏导数也就是说，如果u 的古典导数存在，那么函数“的全 变差可写成： t v ( 加上陬i d x ( 2 2 ) ， 在本文中。今后我们都用这一记号表示函数的全变差 定义2 1 2 有界变差函数空间被定义为? b v ( q ) = u l 1 ( q ) l t v ( “) 1 ( 2 3 ) 可以证明：有界变差函数空间b v ( q ) 在范数i l u l h v = i l u l l l t + t v ( u ) 下是一个 b a n a c h 空间，而全变差t v ( u ) 只是b v m ) 上的半范数 b v ( q ) 上有很多重要性质，在图像处理的基础领域，如图像复原和分割等，我 们一般比较关心如下三条性质： 一7 一 基于四阶偏微分方程的分裂b r e g m a n 图像复原方法 性质2 1 1 下半连续性：如果撕，b v ( q ) 且有h ，_ l i 则 。 l l ( a ) 。fl d u l l o u , j j + + o o ( 2 4 ) 性质2 1 2 紧性? 当p 满足1 p 0 ) ，b v ( q ) 可以连续地嵌入 ) ，此处，当n = i 时，定义p = + 瓯 性质2 1 3c o a r e a 公式? 如果比b v ( f 1 ) ，则t v ( u ) = c 日1 ( a q a ) 肌其中， 边界籼是使得“( 力= a 的水平集，嘞= 比( 曲 0 为一个较大的正数，则凡( 曲八曲现在我们任取一个递增的正罚参数 序列l ，且使得k 0 0 时，有触一对每一个心，求解如下的无约束问题： 这里， n f l n ( 2 8 ) ( 劝= 厂( 劝+ 巳。 = 删+ 判1 愀劝n o 曲 双枷 卧 ( 2 9 ) i e j 刚 j 设式( 2 9 ) 的解为，由如下定理，可得到原问题( 2 5 ) 的解【3 3 1 定理2 2 1 设函数f , g f ，h j ，f l , j ，连续且约束问题( 2 5 ) 的解存在设序列 由式( 2 9 ) 产生，其中罚参教序列恤七) 单调递增且趋于+ o o ，则 规 的任何极限 点都是问题( 2 5 ) 的解 2 3 变分法与e u l e r - l a g r a n g e 方程 通过之前的介绍，我们知道图像复原问题在数学上可以表述为一个泛函求极值 问题，这正是变分法所研究的对象这里用一个简单的例子说明如何利用变分法来 求解泛函的极值 考虑如下泛函的极小值问题： 一 嘧j ( 妁) = 上，) ，) ，) d x ，( 2 1 0 ) 其中函数y 6 , 2 陋，b 】且y ( a ) = ，y ( b ) = 始 假设y = y ( 曲是使得泛函，取到极值的曲线，夕是与该极值曲线接近的一条容 许曲线，它在端点处的取值与y 相同，即夕( 口) = ，夕( 6 ) = y b 我们定义微小的变量 夕一y 为变分毋，并且构造一个与极值曲线接近的曲线族： 夕( 五口) = ) ，( 曲 1 - 叻= y ( 曲+ 口 ( 曲一y ( x ) ) ，( 2 1 1 ) 其中口为一个小实数注意到该曲线族在端点处的取值均相同，这意味着在端点上， 曲线族中任意一条曲线的变分都为o 在这个曲线族上，可定义关于口的函数， m ( a ) = j ) = j ( ) ，+ 口毋) ，( 2 1 2 ) 且这个函数在口= 0 处取到极值，所以函数西( 口) 的导数在口= 0 处为o 一9 一 基于四阶偏微分方程的分裂b r e g m a n 图像复原方法 因为 。 产 ( 口) = j ( y + o r 6 y ) = jf ( x ，y + a 6 y ，) ，+ a ) d x ，( 2 1 3 ) 易得 ，q ， o = 西，( o ) = f ( f , 6 y + f y 6 y ) d x ， ( 2 1 4 ) 对上式第二项应用分部积分，有 r 聃淑+ 乃卿c - r 毋譬a x o 亿均 前面已经指出在端点上变分毋为0 ，所以有 r 毋一一些d x ) d x = 。 ( 2 1 6 ) 由于上式对任何$ 均成立，由变分预备定理可知【3 4 1 b 一素乃= 0 ( 2 1 7 ) 该方程被称为式( 2 1 0 ) 的e u l e r - l a g r a n g e 方程，它表示泛函取得极值时的必要条件， 也是变分法的核心 对于多变量和涉及到高阶偏导数的泛函求极值问题，我们可以用类似的方法来 求它们的e u l e r - l a g r a n g e 方程比如对于如下泛函 北c 删= 旺f 卜酗塞，考，象，为，象) 蛐 亿均 它的e u l e r - l a g r a n g e 方程为跚： 瓦o f 一熹( 篆) 一为( 篝) + 要( 差) + 为( 差) + 岳( 薏) = 。，c 2 舯， 且在边界施上，z ( x ，y ) 和赛为已知这里，n 为单位外法方向 需要指出的是，我们在上面提出的都是在固定边值条件下求得的e u l e r - l a g r a n g c 方程，即我们首先已经假定了边界上的函数值和某些外法方向的导数值是固定不变 的事实上，还有一种与固定边值条件相对应的自然边值条件，具体可以参看文【3 4 】 2 4 微分方程数值解法简介 通过上一节对变分法的介绍，我们知道图像复原问题的解可以由一个满足一定 边值条件的微分方程的解来描述，由于图像是一个二维函数，所以这个微分方程通 常都是一个偏微分方程而对于偏微分方程，虽然它的解的存在唯一性在很普通的 一1 0 一 硕士学位论文 条件下一般也可以得到证明，但是只有其中极小的一部分可以求出它们的解析表达 式因此，为了在广泛的领域上研究并应用这些偏微分方程，科研工作者不得不去 尝试一些解的近似表达形式随着计算机科学在过去半个多世纪里的飞速发展，数 字化技术为我们描述偏微分方程的近似解提供了强有力的手段，同时也开创了一个 具有强大应用能力的综合性学科 从思想上看，微分方程数值解法并不试图在整体上用通式来描述微分方程的 解，反而它专注于这个解在一些离散的单点处的取值以有限差分方法为例，它往往 通过寻找微分方程在这些离散点处所必需满足的条件来建立这些取值的联系，一般 而言，为一个关于这些取值的线性或非线性的方程组之后，利用高效数值计算方 法和计算机强大的数值计算能力来求解这个方程组，最终得到微分方程的解在这些 离散点处的精确或近似值可以看到，在解函数的定义域确定下来以后，当离散的点 取得越密集，我们就能得到关于这个解越多的数值信息，从而我们求得的数值解也 越逼近它的连续形式 一般来说，利用有限差分方法来数值求解微分方程由以下几个步骤组成： 网格剖分：实质上就是在解的定义域中选择一些离散的网格点，以便准备在这 些点上求出解的近似值由于数字图像自身的特点，在图像处理中，我们往往直 接利用它的像素所在的位置一般地，这些网格点被认为以均匀的间隔排列成 矩形 离散化：即在剖分后的网格上离散地表示待求解的微分方程在这些网格点上， 数值解的函数值可以用连续解在该点处的取值来表示。而数值解的导数值则利 用差分格式将其转化为数值解的函数值来表示比如，在一个均匀剖分的网格 上，每两个水平相邻的网格点距离为毗垂直相邻的两个网格点的距离为y 对于连续函数“亿y ) ，它在工= f ，y = j 处的网格点的函数值记为魄，则在该点 处，u 关于工的偏导数可以用如下几种差分格式来离散表示： 蚝( l j 3 = ( e “) 圹警， u x ( i ，1 3 = ( v ：“) u = 警， 啪力= ( v o “) 旷警 ( 2 2 0 ) ( 2 2 1 ) ( 2 2 2 ) 上述差分格式分别被称为函数“关于工的向前差分，向后差分和中心差分，e 可以被称为函数u 关于工的向前差分算子关于高阶导数的差分格式可以参见 表2 1 适定性分析：即分析离散化后的问题是否满足解的存在唯一性，同时，由于数值 一1 1 基于四阶偏微分方程的分裂b r e g m a n 图像复原方法 表2 1 导数的有限差分格式 导数有限差分格式 v ：( 蜥j )士( j 一) 骘( )士古( 比扛t 一魄j ) ( )击似( ) 一e ( 伪 v 刍( 训古( v x ( u i , j ) 一v ：( 训) v 妄x ( u i , j )古愕( u ) 一丐( ) ) 旦虹壶盟血) 二旦亟! 泣 解一般都是近似解，我们还需考虑在误差存在的情况下，数值解是否满足稳定 性要求 设计数值算法：离散化后，我们往往得到的是一个高阶的方程组，因此我们需要 设计高效可行的数值计算方法来求解这个方程组同时，我们还必须考虑所采 取的数值计算方法是否收敛，是否可以逼近原来的连续问题 编写计算机程序：最后，根据所采取的算法，编写程序并由计算机进行计算，得 到微分方程的数值解 一1 2 硕士学位论文 第3 章图像复原问题的b r e g m a n 迭代方法 b r e g m a n 迭代方法是近年来在r o f 模型的基础上发展起来的一种新的图像 复原方法它采取迭代的思想，在形式上相当于多次求解初值不同的r o f 模型，最 终得到一个精度更高，视觉效果更好的复原图像并能有效避免r o f 模型的解存在 “阶梯效应 的缺点；但另一方面，它需要进行多次迭代，因而计算量大大增加为 了克服这个缺点，借助于b r e g m a n 迭代方法的思想，g o l d s t e i n 和o s h e r 利用了变量 分离的技巧，提出了一种可以快速计算的分裂b r e g m a n 迭代方法本章主要介绍 b r e g m a n 方法和分裂b r e g m a n 方法在r o f 模型中的应用，在此之前，先简要回顾求 解r o f 模型的一些传统数值方法 3 1 求解r o f 模型的数值方法 在绪论中我们已经简要介绍了r o f 模型的结构，这里我们具体分析计算该模 型的数值方法 c h a m b o l l e 等在文【1 2 】中证明了r o f 模型( 1 2 ) 与下述无约束优化问题等价： 埘躲) l l v u ld x d y - i - 扣“一，i i i( 3 1 ) 其中，a 是l a g r a n g e 乘子，它起着平衡去噪效果和保持图像特征的作用过大的a 将 使得最终的复原图像十分接近退化图像厂，导致去除的噪声很小，结果仍然被噪声 过度“污染一而如果其取值过小，则将使最终的复原图像被过度的光滑，从而可能 丢失大量图像本身的特征信息 由变分法的知识，不难得到式( 3 1 ) 的一阶必要条件，即其e u l e r - l a g r a n g e 方程： v 叫“一d = - - ( 3 2 ) 该方程为一个二阶的非线性偏微分方程，即便是离散化后求其数值解，直接计 算也是相当复杂的，即使当图像的规模并不是太大时( 如分辨率为2 5 6 2 5 6 的图 像) ，也可能导致计算量极为巨大，因此我们需要一些特别的方法来求解它r u d i n 等在文【11 】中提出了利用有限差分格式和梯度下降流来计算该偏微分方程的数值 解然而，由于该方程本身具有的奇异性( 在如= 0 且u y = 0 处无意义) ，需要对其 进行光滑化处理，即考虑修正模型： “。m i nj ! ：i v “i 归d x d y + 扣一月睦 ( 3 - 3 ) 这里，i v u b = i v 圳2 + 卢，其中卢被称为正则化参数，一般设为一个很小的正实数与 一1 3 基于四阶偏微分方程的分裂b r e g m a n 图像复原方法 r o f 模型不同，该模型关于“有连续的偏导数，其一阶必要条件为： v ( 嵩) “”力- 0 ( 3 4 ) 在文【1 1 】中，r u d i n 等利用了演化的思想，引入了一个“时间 辅助变量，从而将 之前讨论的静态图像u ( x ，y ) 看作一个关于空间和时间的函数u ( x , y ，f ) ，并指出方程 ( 3 1 ) 的解函数应为按照下述随时问进行演化的方程的稳态解： 型a t “( 旦i v u ( x 揣, yt ) l a ) 叫出y ，力一八删( 3 蜘， ， 。、。、。一。7，、，7 7 、 。7 ， 在确定时间步长址和空间网格长度血并对对上述方程进行离散化处理后，他们 提出了一个显式的迭代格式： = 矿化篙) 一a ( 铲一力 6 ， 在这个迭代格式下，如果时间步长址被设定得足够小，目标函数值将一直下降，在 迭代足够多次之后，最终可以得到唯一的极小解 上述方法被称为梯度下降方法，从优化理论的角度看，它等价于对能量泛函 ( 3 1 ) 采取最速下降算法该方法的最大缺点在于它的收敛速度非常慢，主要原因 在于为保证算法的收敛性，需要满足c o u r a n t - f r i e d r i c h s 。l e w y ( c f l ) 条件a t c l v u b ( a x ) 2 ，这里c 为某个常数【1 1 】，a x 为空间网格长度可以看到，在图像的平坦 区域( 此时i v u i 0 ) ，c f l 条件中的右端项将非常小，因此时间步长f 将被限制 得很小，从而导致目标函数下降的速度非常慢此外，正则化参数卢的引入导致所 求得的解只是一个近似解当然，较大的卢可以放松c f l 条件，但这样也将不可避 免地使得解的精度显著下降 为了克服上述缺点，众多学者都在设计快速且稳定的计算方法方面做了大量研 究，其中很重要的一类方法利用了对偶的观点 这里首先简要描述r o f 模型的对偶问题和本原一对偶系统由全变差的定义 式( 2 1 1 ) 出发，可以得到关于r o f 本原问题( 3 1 ) 的对偶问题： 雠蹁 。= _ a 2 i t f l l 2 一i l l v o + ，| l l 7 ， 结合r o f 本原问题和对偶问题，可定义d u a l i t yg a p ： g ( 地) = f , v u i d x d y + = 上( 阶v ) a x 曲+ 到半小圯 8 ， 一1 4 硕士学位论文 不难证明，当g ( u ，曲= 0 时，本原变量h 和对偶变量都将使各自系统中的目标函 数取到极值 3 6 1 所以此时有： 掣i _ 孔 ( 3 9 ) iv u a 似一力= 0 式( 3 9 ) 被称为r o f 模型的本原一对偶系统 c h a n ，g o l u b 和m u l e t 在文【1 4 1 中提出了求解r o f 模型的c g m 方法，其主要 思想在于引入一个新的变量叫= i 岛，将其代入式( 3 4 ) 即得到： i v u b 川肛0 ( 3 1 0 ) iv u a 一力= 0 可以看到，式( 3 1 0 ) 实际上就是式( 3 9 ) 光滑化后的结果因此，c g m 方法同时也被 称为本原一对偶方法该方法的好处在于，相较于r o f 本原模型，它所涉及的本原 对偶系统更适合于利用牛顿法来作数值计算经验表明，c g m 方法往往能以超线性 的速度收敛，而之前提到的梯度下降方法最多只能达到线性收敛速度 在文【1 5 】中，c h a m b o l l e 则从对偶问题( 3 7 ) 出发并设计了如下的仅关于对偶 变量的迭代方法： + l = 再a + 而7 - h ( a ) ( 3 1 1 ) 。： 其中， 日( 山) = v ( v 一柳且l u i 1 ( 3 1 2 ) 由上述迭代格式计算出后，再由原变量u 和对偶变量u 的关系得到u 的值： l ，l = - ，v + f ( 3 1 3 ) 其中，丁是时间步长c h a m b o h e 指出，当f i 1 时算法具有全局收敛性实验表明，该 算法的收敛速度非常快，并且它无须像前两种方法那样引入正则化参数p ，避免了 只能得到一个近似解的缺点 除以上