TV模型图像去噪的算法分析.pdf

论文作者签名： 指导教师签名： 论文评阅人1 ： 评阅人2 ： 评阅人3 ： 评阅人4 ： 评阅人5 ： 答辩委员会主席： 委员l ： 委员2 ： 委员3 ： 委员4 ： 委员5 ： 答辩日期： a u t h o r ss i g n a t u r e ： 一 o s u p e r v i s o r 7 ss i g n a t u r e ： t h e s i sr e v i e w e r1 ： t h e s i sr e v i e w e r2 ： t h e s i sr e v i e w e r3 ： t h e s i sr e v i e w e r4 t h e s i sr e v i e w e r5 ： c h a i r ： ( c o m m i t t e eo fo r a ld e f e n c e ) c o m m i t t e e m a nl ： c o m m i t t e e m a n2 ： c o m m i t t e e m a n3 ： c o m m i t t e e m a n4 c o m m i t t e e m a n5 ： d a t eo fo r a ld e f e n c e ： 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝鎏盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解逝望盘堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝婆盘堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期：年月日签字日期：年月日 浙江大学硕士学位论文摘要 摘要 图像去噪是图像领域中的经典的问题。现实生活中拍摄仪器所获取的图像可 能包含不同来源的噪声，会影响图像的质量，当我们需要对图像进一步处理时， 比如图像分割等等，为了保证后续的图像处理结果更可靠，我们需要对图像进行 去噪处理。我们进行图像去噪时，要保留图像的边缘纹理等重要信息，同时要去 除图像中的噪声。t v 模型不但能去除图像中原有的噪声，而且能有效地保留图像 的结构信息，是图像处理中的经典模型。 本文主要讨论了t v 模型图像去噪的算法分析。t v 模型能保留图像的结构， 针对t v 模型有很多经典的算法如p d h g ，a m a ，a d m m 等算法，我们深入分析学习了 这些经典的算法并阐述了算法之间的关系，利用n e s t e r o v 算法加速方法实现了 对算法的加速，并给出了p d h g 算法的改进以及实现。 关键词：凸优化，t v ，图像去噪，p d h g 浙江大学硕士学位论文 a b s t r a c t i m a g ed e n o i s i n gi sac l a s s i cp r o b l e mi ni m a g ep r o c e s s i n g w h e nw og e t a ni m a g e b yat r a d i t i o n a lw a y , t h ei m a g em a y c o n t a i nn o i s e sf r o md i f f e r e n ts o u r c e s n o i s ew i l l a f f e c tt h eq u a l i t yo fi m a g e ，a n di to f t e nh a sg r e a ti n f l u e n c eo nt h es u b s e q u e n ti m a g e a n a l y s i s ，s u c ha si a m g es e g m e n t a t i o n i no r d e rt og e tar e l a i a b l er e s u l t ，w o n e e dt o r e m o v et h en o i s ea sm u c ha sp o s s i b l ea n dm a i n t a i nt h ed e t a i ls t r u c t u r ei n f o r m a t i o n s u c ha se d g e sa n dt e x t u r e t vm o d e lc a ns u p p r e s st h en o i s ei ni m a g ea n dp r e s e r v et h e s t r u c t u r eo fi m a g e ，t vm o d e li sac l a s s i cm o d e li ni m a g ed e n o i s i n g w eg e n e r a l i z et h ea l g o r i t h m sf o rt vi m a g ed e n o i s i n gm o d e l t vm o d e lc a n p r e s e r v et h ei m a g es t r u c t u r ea n dt h e r ea r em a n ya l g o r i t h m sf o rt vm o d e l ，s u c ha s p d h g ，a m a ，a d m ma n d s oo n ，w es t u d yt h e s ea l g o r i t h m sa n dr e l a t et h e i r c o n n e c t i o n s t h ep r o p o s e da c c e l e r a t i o ni so ft h ef o r mf i r s tp r o p o s e db yn e s t e r o v w e a l s op r e s e n ts o m en u m e r i c a lc o m p a r i s i o n so fp d h ga n dt h em o d i f i e dv e r s i o no f p d h c t k e yw o r d s ： c o n v e xo p t i m i z a t i o n ，t o t a lv a r i a t i o n ，i m a g ed e n o i s i n g ，p d h g 浙江大学硕士学位论文目录 目录 摘要i a b s t r a c t i i 第1 章绪论1 1 1 引言1 1 2 图像噪声类型1 1 3 图像去噪的研究现状3 1 4 本文工作及内容安排6 第2 章图像去噪( t v ) 模型及相关概念8 2 1 相关概念一8 2 2t v 模型1 0 2 3t v 模型合理性证明11 第3 章t v 模型的算法分析1 4 3 1 原问题与对偶问题1 4 3 2 算法分析16 3 3 算法之间关系2 0 3 4 算法加速方法2 3 第4 章数值实验一2 8 4 1 图像去噪效果的评价2 8 4 2 数值实验2 9 第5 章总结与展望3 7 参考文献3 8 致i 射4 0 浙江大学硕士学位论文第1 章绪论 1 1 引言 第1 章绪论 曾经有外国学者做过统计，人类所获得的信息由8 0 以上来自眼睛摄取的图 像。图像在工业，农业，生物医学，科研国防安全等领域扮演着重要的角色。然 而图像在形成，传输，存储的过程中都可能会产生失真，例如由于对象的运动， 成像系统的缺陷，记录设备固有的噪声和外部干扰等等，造成图像质量退化。现 实生活中的许多问题需要高清图像，例如医学图像，雷达成像，我们需要对这些 退化的图像进行处理，以得到清晰完整的图像，这就涉及到了图像的去噪去模糊。 图像去噪是其它图像处理任务的基础，例如图像的恢复，图像分割，配准等问题。 图像去噪的主要目的是去除图像存在的噪声，同时又要保留图像的细节结构，譬 如边缘和纹理。然而，这是一个比较困难的任务，因为大部分图像去噪模型虽然 能去除图像的噪声，但是它们却使图像变得不清晰，很多细节结构丢掉。因此图 像去噪才成为吸引众多专家学者一直关注的研究课题，也陆续出现了许多相关的 算法。 在大多数的图像去噪模型中，我们希望从原来的模糊图像或带有噪声的图像 中得到一幅分片常值或有稀疏梯度的图像。因为它能保留图像的边缘及纹理，没 有那么高的光滑性要求。然而目标函数的不可微使得目标全变差极小问题的计算 面临挑战，因此产生了许多有趣而且有效的算法。 1 2 图像噪声类型 由于图像的拍摄仪器，传输媒介以及图像量化过程中辐射源的不同，图像信 息会受到不同的干扰，形成不同的噪声类型。例如超声图像中经常出现斑点噪声， 而核磁共振图像中经常出现瑞利噪声。设一幅清晰的灰度图像为函数“：q r ， 令厂：q 专r 是带有噪声的图像，刁：q 专r 为图像的噪声。其中q r 2 为图像定 浙江大学硕士学位论文第1 章绪论 义的区域。一般图像处理中常见的噪声类型有如下几种： ( 1 ) 加性噪声：f = u + r l ( 2 ) 乘性噪声：= u r l ( 3 ) 量化噪声：是数字图像的主要噪声来源，其大小显示出原始图像与数字图像的 差异。 ( 4 ) 椒盐噪声：即黑图像上出现白点，白图像上出现黑点 根据噪声分布的统计特性，噪声的类型主要分为以下几种： ( 1 ) 高斯噪声 高斯噪声是图像处理中最常见的噪声类型，我们一般认为大多数噪声都符合 高斯分布，且该噪声的数学模型比较简单易于分析与研究。设随机变量彳满足高 斯分布，则其概率密度函数为 朐，= 去唧 一譬 ( 2 ) 瑞利噪声 么满足瑞利分布，则其概率密度函数为 p r 。、li 2 ( r - a ) e x p 卜( r - 。b ) 21 ，7 7 口 p ( 巧) ：i (e x p 【- 6 ，7 7 口 t o ，刀 o 为平衡正则项与保真项 o x l 的参数，在数值实验时需要预先确定旯的值。正则项保证了解u 具有一定的光滑 性和某些区域的非连续性，同时保证了上式极小问题是良态的：保真项保证解甜与 初值厂的偏差不会太大，即所恢复的图像与原始图像的差距不是很大，保留了原 始图像的主要特征。该模型在日1 ( q ) 空间中存在唯解，而且解满足 e u l e r - l a g r a n g e 方程 浙江大学硕士学位论文第l 章绪论 一z f 一旯( 厂一甜) = 0 由于拉普拉斯算子作用在一幅图像上和高斯卷积的效果相同，使得图像变得 光滑，但同时磨光了图像的边缘等重要特征，因此该模型不利于保留图像的边缘 信息。从数学角度分析，s o b o l e v 空间对图像的光滑性要求比较高，不允许图像 边缘存在不连续性，它仅适合描述图像光滑的区域。 有界变差( b v ) 函数空间将图像的梯度看成一种测度而非函数，允许甜存在不连 续性，即允许图像存在边缘纹理等重要的不连续特征，因此b v 空间更适合图像 去噪。 因此全变差是b v 空间的半范数，它允许图像边缘的不连续性。因此大多数 图像，包含医学图像处理都是在b v 空问中求解。 r u d i no s h e r 和f a t e m i n 在1 9 9 2 年提出了下列具有全变差作为正则项的变分模型 为： 瑚m 啦i n ) l i d , i + 害( 掰一出 ( 1 2 ) 其中兄 0 为拉格朗e t 乘子，此模型称为t v 模型或r o f 模型。它的解存在且唯 一，对应的欧拉一拉格朗日方程为 砌叫加) = o 然后用最快下降流求解，得 丝a t = 咖f ，t 旦l v , i 、j + 兄( 厂一甜) 如果再加上合适的边值条件便可以解出u 。 ，r v 模型不但能去除图像中原有的加性噪声，而且能有效地保留图像的边缘 信息，这对进一步的图像处理，特别是医学图像的分割非常有用。但是它有一个 显著的缺点就是容易产生阶梯效应，即图像中光滑区域产生了虚假的边界，这对 进一步的图像分割及其不利。出现阶梯效应的原因是图像灰度水平的梯度变化不 正确，因为梯度模值的大小能区别图像的光滑区域和边缘。在图像的光滑区域， 4 浙江大学硕士学位论文 第l 章绪论 梯度的模值比较小，接近于零；在图像的边缘附近，梯度的模值比较大。从而出 现虚假边界时，图像的梯度变化是不正确的。要使图像比较光滑，高阶偏微分方 程方法是一个比较好的去噪方法。但该方法的平滑作用太强，使得图像的边缘不 能很好地保留下来，而且图像变得很模糊，高阶偏微分方程在数值计算时也容易 产生不稳定性。l y a s k e r , o s h e r 和t a i 为了解决图像去噪时高阶偏微分方程的数值 不稳定性而提出了l o t 模型。l o t 模型为一个两步方法：第一步平滑噪声图像 的单位法向量场或梯度场；第二步构造一个曲面( 即图像) ，使其向量场与第一 步得到的向量场相匹配。 第一平滑被观察图像的单位法向量场 常l v 刀陋+ 詈n 一1 2 出 其中栌尚2 ( 南，高) 表示灰度水平集的单位法向量玩通过这个步骤衔。 一个逼近于真实图像u 的梯度场，为第一i 步的处理打下基础。 第二找到一个解甜，使得它的梯度场与第一步所得的梯度场相匹配，并且需 要保证它与原观察图像的噪声图像相差不大，因此有下列极小化期望模型： m 。i n e ( ”) = ( 1 v 甜l v 甜珂) 出+ 导( 材一) 2 出 这里第一项意味着极小解u 的单位梯度场与第一步所得的向量场相匹配，即 丽v u = 门，两边与甩作内积，即得v u - - i v 甜i ：第二项意味着理想的图像与原噪声 图像的结构相差不大。然而l o t 模型需要计算具有约束条件的向量优化问题，用 传统的梯度下降流方法求解，计算速度会非常慢而且非常耗时。我们再介绍一个 l o t 模型的一个改进模型，它不但能克服l o t 模型的一些缺点，还会使计算速 度大幅度提高。 首先，在第一步中用极坐标表示单位法向量，力= ( c o s o ，s i n 0 ) ，通过极小化0 来代替n 。从而解两个变量的极小化问题就转化为求解一个变量的极小化问题， 浙江大学硕士学位论文 第1 章绪论 加速了计算，在第二步中引入一个边缘探测函数，使得在噪声类型未知的情况下 依然能保持图像的边缘纹理。 改进的l o t 模型为 ( 1 l 口珊，l i v a l + 詈( 秒一e 0 ) 2 d x ( 2 ) m 。i nf a g ( x ) ( 1 v “f - v 甜疗) a x + 口t l 甜一陋 g ( x ) 为边缘探测函数，g ( x ) 2 i 拇或者g ( x ) = e x p ( 一k v g 木u 2 ) l + k i q 木甜r 这里g ( x ) = 荔e x p ( 一专) 是二维高斯核函数，七是一个尺度因子。这两个函 数所产生的尺度空间是不同的的：第一个有利于检测高对比度的边缘；第二个有 利于检测宽一点的边缘。 t v 模型在图像去噪中起着里程碑的作用，很多模型的改进都是以t v 模型为 基础的，而且产生了许多求解t v 模型的算法如a d m ma m ap d h g 等经典算法， 许多专家学者也对这些算法上的改进。n e s t e r o v e 提出了一种算法加速方法，一阶 算法也能达n - 阶的收敛速率。 1 4 本文工作及内容安排 本文主要对图像去噪的经典模型( t v 模型) 及求解这个模型的算法进行系统 地学习与研究。并在实验上给出了改进的p d h g 算法去噪效果。 本文的结构如下： 第一部分：绪论。介绍了图像噪声的基本类型，去噪的模型及不同模型的优缺 点，并对本文的内容安排进行了说明。 第二部分：图像去噪模型( t v 模型) 。用统计学的最大似然估计方法证明了 ( t v ) 模型的合理性。 第三部分：介绍了处理原问题的方法，( 尸) ( d ) ( s 昂) ( s p o ) 详尽介绍了处理 t v 问题的一些经典的算法，以及这些算法之间的关系，接着介绍了n e s t e r o v e 加 6 浙江大学硕士学位论文 第1 章绪论 速算法的方法。并对p d h g 算法做了改进 第四部分：给出了p d h g 算法处理t 、，模型的去噪效果，并给出了改进后的 算法处理t v 模型的去噪效果， 第五部分：总结与展望。对本文的工作进行了总结，并讲述了图像去噪的改 进以及对未来工作的展望。 浙江大学硕士学位论文 第2 章图像去噪( t v ) 模型及相关概念 2 1 相关概念 第2 章图像去噪( t 模型及相关概念 定义2 1 1 ( 0 范数) ： 设x 是r ”中的向量，p 【1 ，叫，那么我们定义x 的0 范数为 当p 【- ，o 。，时，p 【1 ，o o ) i i x 犯= ( 善k i p ) j 当p 3 o 。时，l i x l l p2 ，爨h p ：o 时u x l l p = i ( f ：薯o ) l ，即向量x 中非零元素的个数。p ：o 时l l x l l p 已不再符合 范数的定义，但是我们依然用范数这个称呼。 定义2 1 2 设q 为r 2 的一个有界开子集，z f _ ( q ) ，若u 的分布导数可以用q 上 的r a n d o n 测度表示，即 u d i v o d x = 一d u 触，v 秒( 幺，砬) ，d u = ( d l 甜，砬甜) 成立，则称甜是q 上的有界变差函数，并定义 l 眈i = s u p 巳u d i v o d x ：p ( q ，睦) q ( q ) ，i o l p 1 其中舢：导+ 要 特别的，当扰c 1 ( q ) ，u 为q 上的一阶连续可微函数，有格林公式得 u d i v o d x = 一v 甜0 因此，可以推得 例= l l v z ，陋 因此我们可以得知：若甜是可微的，那么全变差就等于u 梯度的刀范数。 定义2 1 3 设x 是一个巴拿赫空间，e ：x 专r ，e 是凸的，那么e ( “) ：0 的解甜 坚大学硕士学位论文第2 章图像去噪( t v ) 模型及相关概念 是极小问题卿e ( v ) 的解。称 e ( 甜) = 0 为欧拉- 拉格朗日( e u l e r - l a g r a n g e ，e l ) 方程。 曰y ( q ) = “( q ) ：l d z f i o - 2 ( 1 一五) i x - y l i ，z e 0 ，1 】 定义2 1 9 设f ( x ) ：r ”专r ，f 的预解算子为： 如( z ) ：= ( n o f ) - z = a r g m ，i n f ( x ) + 劫x z 畦 当f ( x ) i x l l ， 0 时，有 9 浙江大学硕士学位论文 第2 章图像去噪( t v ) 模型及相关概念 如( z ) ：= s h r i n k ( z ，) s h r i n k ( z ，) 的第f 个元素为 肭讹廊5 白m a ) 【朴删洲乙) 2 2t v 模型 在生活中，灰度图像对应着一个矩阵，矩阵的位置对应着图像的像素点，矩 阵中的元素值对应着图像该像素点的灰度值，因此需要对模型离散化，离散化后 的( t v ) 模型为： m i n i m i z e g ( a u ) + 日 ) 其中u r ”，u 为图像按列拉成的列向量。a r “”为差分算子，都是凸函数 g ：r ”专( 一o o ， ，h ：r ”专( 一o 。， 都是凸函数，e h t - g 并u h 所取的范数不同，我 们主要考虑如下的模型。 l 1 一a t vg ( u ) = l l u 一州，g ( a u ) = i i a u l l 。 l 2 一a t v h ( 材) 2 忱一州i ，g ( a u ) = 忡“i | l 川一椰脚冲i i 们g ( 删= i l u l l 扩淞蒯： 也一删即) _ | 卜州：，g i l u l l 形爿毁8 ： 设x 为n xn 的矩阵，z 为x 的列向量拉成的向量，则 五，= h ( ，一1 ) f ，j = l ，2 ，n 为一阶差分矩阵。 d = 0 11 11 l o 浙江大学硕士学位论文第2 章图像去噪( t v ) 模型及相关概念 则a 为一个2 n 2 n 2 的矩阵 彳= 瞄- i 。d 混合积的性质为 ( a o b ) ( c p d ) = ( 彳c ) 圆( 肋) ( 彳召) 丁= a r o 召r ( 彳 b ) 。= a _ 1o b 1 则么丁= ，。7 。r 。厶 ，彳“= ( i n 。d ) u d 甜= f 徊7 ：l l u 1 2 一1 g n l n 2 2 3t v 模型合理性证明 形模型不但能抑制图像的噪声而且能保留图像的纹理，边缘等细节，是图 像去噪中最常用的的模型，接下来我们将证明该模型的合理性。 设厂= 尸 ) ，其中p 表示一种概率分布，我们的目标是求尸( 衫力的极大后验概率。 根据贝叶斯定理： 删门= 掣铲 方程两边同时求对数可得： l n p ( u f ) = i n p ( f u ) + i n p ( u ) l n p ( f ) 极大后验估计可以计算可得 u 。= a r gm a x i n ( f u ) + i n 尸( 掰) ) 1，ll_ 一 毪；讲 一； 一 浙江大学硕士学位论文 第2 章图像去噪( t v ) 模型及相关概念 1 炭设服从局斯分布，u 为均值每个分量的万程方差盯，条件概翠p ( f u ) 的 密度函数为： p ( f 炉后e x p ( 一丢喜华) 其中k 为归一化常数 1 1 1 尸( f 甜) 一万l 善m ( z 一) 2 伯尼 = 一去卜州i i + c= 一一材一，i 十i 2 仃” 。”2 回顾一下g i b b s 先验假设 1 尸( 甜) = 二e x p ( 一兄u ( 甜) ) z 其中z 为归一化常数，名是一个正则化参数，u ：r ”专r 为能量函数。 由此可得 旷a r g m 。i n 去卜州：+ 拟纠 在压缩传感信号处理中，我们一般选择u ( 甜) = 。，我们希望所得到的的解甜越 稀疏越好o ，m i n l l u l l 0 u2t 由于乇范数的非凸性，我们用范数来近似代替 营 i i l i 唰1 1 u = ， 此时工= a r g m i n 去卜州一。) r o f 一模型 此时选择u ( u = l l u l l r 矿 舻a r g m i n 去卜州一丁矿) 1 2 浙江大学硕士学位论文 第2 章图像去噪( t v ) 模型及相关概念 设f = p o i s s o n ( u + y ) 贝, l jp ( f u ) = 兀( + 乃) ze x p - ( u , + 乃) 卜h l ( z ! ) 两边同时求对数可得 h e ( f z f ) = 仙( 蚱+ 形) 一( + 乃) 一1 1 1 ( 岛! ) = ( h 1 ( “+ 7 ) ，厂) 一( z f + y ，1 ) + c o n s t m i n ( u ，1 ) 一( 坂“+ y ) ，f + ：t l l , , l l ：甜衅) 当噪声为椒盐噪声时 p ( u i = o ) 3 考，p ( u j = 2 5 5 ) = 考，p ( = z ) = 1 一詈，o 0 f o rk = 0 ，1 ，2 d o ( 3 2 2 口) 胁= 哪嚣( p , a u k ) 一刳p 一仇幢 ( 3 2 2 b ) r a r g m i n h ( 甜) + a r p k + l , u ) + 石1 卜墟 e n df o r 一一一 以上两种方式是等价的。 如果+ p d h g 算法中r 和口分别为，这是p d h g 算法的两个特殊的情况1 4 1 ，分 别对应着p f b s 11 1 算法求解( p ) 和( d ) p f b s 迭代分裂方法可以用来求解两个凸函数和的最优锯，应用p f b s 算法解( d ) 问题为 p m = a r g m p 吖i n g ( 舻扫p 七一他+ 1 ) 哐 其中“川甜+ ( - a r p i ) ， 由于+ l o h + ( 一彳r 仇) 营一么r p k o h ( u + 1 ) ，也等价为 。a r g m 硝i n h ( 甜) + a r 仇，秘) 因此p f b s 可以重新表示为 应用p f b s 算法解( d ) 问题 初始条件：仇，f 0 f o rk = 0 ，l ，2 d o ( 3 2 3 口) = a r g r r f i n h ( ”) + a 7 见，“) ( 3 2 3 b ) m = a r g m 删i n g ( 力+ ( p , - a u k + 1 ) + 期p 啊眨 e n df o r 1 7 研江大学坝士字位论文 第3 章t v 模型的算法分析 尽管算法的迭代顺序与p d h g 正好相反，但是由于初始条件是任意的，它依然是 p d h g 算法当o u - - - o o 时的特殊情况。 如果g ( v ) = m ，n + 。的迭代式可以认为是在凸集上的正交投影 p k + 1 - a r g m 库i 旷n g ( p ) + ( p ，一彳+ 扫p n 哐 2 a r g m i g n u p 一( 见+ r a u k + ，) 1 1 ： 即办+ 1 = 兀洲席g j ( 仇+ r a u 川) 因此应用p f b s 解( d ) 问题可以认为是梯度投影算法。 a m a l 2 0 1 解( 珥) 问题是一种交替迭代方法，首先迭代l a g r a n g i a n 方程0 ( 甜，1 ，p ) 的 甜，然后迭代增广l a g r a n g i a n 方程l p + 吾忙”一v 哐的1 ，最后迭代l a g m 舀a i l 乘子 刀o a m a 解( 踞) 初始条件：p or 0 f o rk = 0 ，1 ，2 d o ( 3 2 4 口) k + l = a r g 哑n h ( 甜) + ( 爿7 p k ，甜) ( 3 2 4 b ) 唯+ ra r g m 。i n g ( v ) 一( 见，v ) + i l l a u , - v 眨 ( 3 2 4 c ) p k + l = p k + r ( a u 一咋+ 1 ) e n d f o r a m a 解( 踢) 问题 f o rk = 0 ，1 ，2 d o ( 3 2 5 口) p “1 = a r g m p 。i ng + ( p ) + ( 一么z ，p ) 浙江大学硕士学位论文 第3 章t v 模型的算法分析 ( 3 2 5 b ) y 。+ 1 = = a r g m y 。r i n h ( y ) 一( z ，y ) + 詈l y + 彳，p 。+ 1 l i ： ( 3 2 5 c ) z ，+ 1 = z ，+ a ( - a r p + 1 一y + 1 ) e n d f o r a d m m t 硒j 算法是a m a 算法的一个改进，在第一步迭代式中加入了一个二次 惩罚项。a d m m 算法第一次被g l o w i n s k i 和m a r o c c o 提出，收敛结果被g a b a y , g l o w i n s k il e ，t a l l e ce c k s t e i n 和b e r t s e k a s 研究过。而且在厶正则化问题中这种技 术是我们熟知的分裂b r e g m a n 方法，在处理r o f 模型的厶正则化模型中a d m m 算法的收敛速率非常快，它将有约束的优化问题转成了无约束的优化问题。而且 a d m m 算法引进变量p ，p 是一个可以调节的值。在没有达到收敛之前，图片已 变得非常光滑，这是其它算法无法达到的。a d m m 收敛速率非常快，一般在十 步之后你就基本上无法比较图片的变化，而且当p 专，这也是一个病态问题。 a d m m 解( 哗) 问题 初始值：1 ，o 尺”，p o r ”，f 0 f o r k = 0 ，1 ，d o ( 3 2 6 口) z ，“l = a r g m i z n h ( 甜) + ( p ，一么甜) + 三i i a u - v k 哐 ( 3 2 6 b ) v t + j = a r g m i m n g ( v ) + p k , v ) + 吾l i 彳甜“l v 眨 ( 3 2 6 c ) p “1 = p + r ( a u “1 一f k + 1 ) e n df o r 我们利用a d m m 算法来求解( s ) 问题 初始条件：p o 尺”，y o r m , f 0 f o r k = 0 ，1 ，2 d o 浙江大学硕士学位论文 第3 章t v 模型的算法分析 ( 3 2 7 口) p k + i = a r g r a 胙i f n g ( p ) 一a u k , p ) + 三0 少“l + 么r p 8 ： ( 3 2 7 b ) y t + j = a r g m y 。胪i n h ( y ) + u k , - y ) + 三0 y + 彳7 p 哐 ( 3 2 7 c ) ”七+ 1 = “七+ r ( - y 。+ 1 - a ，p 。+ 1 ) e n d f o r 对于原问题的求解，我们也可以用增广的l a g r a n g i a n 方法，引入辅助变量v m i n g ( v ) + 日 ) 满足1 ，= a u ”v 增广l a g r a n g i a n 方程为： l p ( u , v , p ) = g ( v ) + h ( 甜) + ( p ，b ”一v ) + 譬o b 一v 哐 然后再用上述算法( 如a d m m ，a m a ) 来迭代( 甜，1 ，p ) 3 3 算法之间关系 算法p d h g 的( 3 2 1 ) 形式可以理解为运用交替方向算法求解( 啤) 或( - 踢) 问题。这种解释被证明是a m a 算法的松弛形式。我们可以通过对目标问题的拉 格朗日函数的迭代步骤中向( 3 2 4 口) 迭代步骤中加入去陋一眶或者在( 3 2 5 口) 迭代步骤中加入石1i l p 一致蛭。这样算法p d h g 的( 3 2 1 ) 的形式与松弛的a m a 算 法是等价的。 尽管将p f h g 算法等同于松弛的a m a ，但并不能直接给出p d h g 算法的收 敛性证明。但是我们可以得出p d h g 算法与a d m m 算法存在紧密的联系。它也 为我们提供了p d h g 算法收敛性的理论推理方法。如果我们并非在运用a m a 解 踞和踞算法迭代的第一步加入项去肛一哐和去怕一n 眶，而是加入增广 l a g r a n g i 锄惩罚项吾怕z ，一吒蛙和等怕7 1 p + 少睁我们就可以分别得到运用a d m m 浙江大学硕士学位论文第3 章t v 模型的算法分析 算法解衅和( 踢) 问题。 运用a d m m 算法解( 碑) 问题等价于运用d o u g l a s r a c h f o r ds p l i a i n gf 8 1 算法解( 尸) 问题。同样的运用a d m m 算法解( s p o ) 问题等价于运用d o u g l a s r a c h f o r ds p l i a i n g 算法解( d ) 问题。【1 8 1 接下来我们将会对p d h g 算法做一下小的改动得到新的算法p d h g m p 和 p d h g m u ，这两种算法可以解释为运用s p l i ti n e x a c t 方法求解( s 昂) 和( - ) 问题。 p d h g m p 算法为算法( 3 2 1 b ) + ，的迭代步骤中将p k + l 替换为2 p k + 。一p k 。 p d h g m u 算法为在( 3 2 1 a ) p k + l 迭代步骤中将替换为2 u k - u k l 。 运用s p l i ti n e x a c tu z a w a 算法求解( ) 问题可以认为是对a d m m 算法的修改。 在目标函数第一个迭代步中在惩罚项等忡r p + 儿哐中加入 三 为了确保h 州7 为正定的，当 0 ，f 0 f o rk = 0 ，1 ，2 d o ( 3 3 1 口) p k + l - a r g m p i n g + ( 小- a u , , p ) + 勺p 啊+ 刚( 彳7 1 n + 儿) 眨 ( 3 3 1 b ) y t = a r g m y i n h + ( y ) 一( 甜t ，y ) + 詈l l y + 彳7 p t + 。哐 ( 3 3 1 c ) + l = + a ( - a r p 一儿+ 1 ) 当。似丽1 时，算法收敛。 浙江大学硕士学位论文 第3 章t v 模型的算法分析 定理3 3 一2 1 1 设钞o 。0 0 0 ，f 0 f o rk = l ，2 ，3 d o p k + l = a r g m p i n g ( p ) + ( p , - a ( 2 u k - u k _ ! ) ) + 劫p 一仇畦 ，一r g m 。i n 4 ( 咖( 彳7 m ，z ，) + 去卜眭 同样地，运用s p l i ti n e x a c tu z a w a 求解( 晖) 问题可以通过运用a d m m 算法求解 ( 皿) 问题的+ 。的迭代步骤中加入去 。相似的我们在 浙江大学硕士学位论文 第3 章t v 模型的算法分析 p d h g 算法( 3 2 1 b ) 中用2 仇+ l n 替换n + l 得到算法p d h g m p 。 3 4 算法加速方法 接下来我们来考虑简单的无约束优化问题 m i n 砌也磐 f ( x ) 其中f ( x ) ：r 专r 为凸函数且导函数是李普希茨连续的。对于这种类型的问题， 接下来我们将考虑标准的一阶方法。首先，我们来研究梯度下降方法来求解上述 问题的最优解。 梯度下降法 初始条件：，r 0 f o rk = 0 ，1 ，2 d o 坼+ 1 = 矗一r v f ( x ) e n df o r 只要f 0 f o r k - - 0 ，1 ，2 d o 磁+ = 以明( 一们| g ( ) ) e n df o r 浙江大学硕士学位论文 第3 章t v 模型的算法分析 f b s 有很好的收敛性质，只要f 丽2 ，算法就收敛1 1 1 。 n e m i r o v s k y 和y u d i n 对一阶算法的收敛性做了详细而深入的研究，对于目标函数 有连续的利普希茨导数这类数学模型，梯度下降算法的收敛速率为o ( ，即 f ( x k ) 一， o 。 y u r i in e s t e r o v 第一次将他所提的加速方法用到梯度下降算法中，在该模型中，目 标函数是强凸的。加速后，一阶算法的收敛速率为o ( 寺 n e s t e r o v e 优化梯度下降算法【3 2 1 初始条件：2 1 ，2 m 彤，r l ( 二v f ) f o rk = l ，2 ，3 d o x k = y k w f ( y k ) ：半 儿+ 。：+ ( o r k - 1 ) ( x k - x k _ , ) ( - g k + i e n df n r 由于这种优化算法的提出，很多一阶优化算法都可以用这种方法来加速， n e s t e r 0 v e 证明了对于不可微的一类问题，这种加速方法也可以达到o ( 吉) 的收敛 速率。接下来我们将这种加速方法应用到f b s ，a m a ，a d m m 。 算法f i s t a m2 而以2 1 ，r 丽1 2 4 浙江大学硕士学位论文 第3 章t v 模型的算法分析 t b rk 。1 ，2 ，3 d o 瓦= ( 儿一刃h ( ) ) ：堂兰 几+ 。：+ 竺 兰( 黾一矗一。) “i + l e n df i n r 当把这种方法应用到a m aa d m m 算法的时候，要求h 和g 都是强凸函数。 这是因为强凸函数的一个重要性质是它的共轭函数导数是利普希茨连续的。即 o h + ( x ) = v h ( y ) ) ，当强凸函数的模数为时，则 l ( v h ) = 盯 ， l ( v h + ) 为v 日+ 的利普希茨常数，即 i v h ( x ) - v h + ( y ) i - l ( v h + ) 忙一y l i 快速a m a 舁纭 初始条件：- 1 ，p - 1 2 r ”，r 0 = a r g m 。i 胪n h c 材，+ i p “k , - a u 、i + 三l - a u + t 眶 2 。胪h ( 材) + + 言4唯l l ： v ；= a r g n a r g 哩n 6 ( v ) + p “k ，v + 三。一么“。+ v i i i v ；2 v ) + ，v ) + 主l i 一么“t + vi p k = p k + r ( 一a u k + 咋) 可e k 0t h e n + 12 1 + v + l2 唯+ 2 一1 p k n = p k 七 e l s e ( k 一一1 ) 口i 一1 吼+ 1 ( p k p h ) 口“12 1 ，1 ，i + 12v k ，p i + l2p k e n di f e n d f o r 算法中当每次迭代毛 o 时，将执行e l s e 语句。其中乓可以从以下的表达式中选 择： 霹= 霹= m a x ( n 矾北，忆| 1 2 - - m a x ( ：，i i 气l l ：) “ 1 1 2 2 l i p s - p k l l 2 - p ( a 7 a ) r 3卜t 眶 2 6 浙江大学硕士学位论文 第3 章t v 模型的算法分析 如果选择4 = 霹，条件语句中将不再执行e l s e 语句。我们对目标函数加某 、 些条件，将能证明出收敛速率为o i 七i fj 如果选择巨= 群等价于对余差算子加了一个单调条件，即当最大的余差下降 时，将执行e l s e 语句。这种乓的选择主要用于求解无约束凸优化问题。 如果选择巨= 群，这种类型巨收敛性的证明已有深入而广泛的理论研究， 但是它在实际的应用中并不广泛。 浙江大学硕士学位论文第4 章数值实验 第4 章数值实验 4 1 图像去噪效果的评价 1 3 1 主观评价准则 我们可以通过观察原始图像与去噪后图像效果的比较和主观理解两方面来 评价图像去噪效果，这是主观评价法。主观评价法可以分为两个方面：绝对评价 和相对评价。直接评判图像去噪的效果属于