（计算机软件与理论专业论文）基于分组行进算法的数字图像修补技术研究.pdf

捅要 图像复原是当前计算机图形学、计算机视觉和图像处理领域的研究热点之 一。它在艺术品的修复、网络数据传输、计算机动画、影视特技、虚拟现实等方 面具有广泛的应用前景。 图像修补是图像复原研究中的一个重要内容，它的目的是根据图像现有的信 息来自动恢复丢失的信息。虽然图像修补基本思想十分简单，但是许多的图像修 补算法都十分复杂，而且难于实现。快速行进算法与水平集法( 1 e v e ls e t ) 相结合进 行曲线进化是一种高效曲线进化算法，算法的时间复杂度是o ( n l b n ) 。k i m 等提 出了另一种水平集的曲线进化算法分组行进算法，算法的时间复杂度是o ( j v ) 。 受其启发，本文将分组行进算法与图像修补算法理论相结合，提出了一种基于分 组行进算法的图像修补技术，完成的主要工作包括下面三个方面： 提出了一种基于分组行进算法的非纹理图像修补算法。该算法适合于修 补非纹理图像上面的线状区域。与其他算法相比，本文算法在大幅度缩 短修补时间的同时仍然能够保持较好的修补效果。 提出了一种基于分组行进算法的纹理图像修补算法。该算法适合于修补 包含纹理和结构信息的复杂图像，并且在物体移除方面取得了较好的效 果。对于包含纹理和结构信息的复杂图像，本文将基于样本的纹理合成 理论与分组行进算法理论相结合，提出一种基于分组行进算法的纹理图 像修补算法。实验表明，本文算法能够较好的传播图像的纹理信息和结 构信息。 引入分组行进算法对窄带( 待修补区域边缘) 进行水平集曲线演化，节 省了窄带演化的时问，提高了图像修补的效率。 为了验证算法的有效性，本文实验如下：非纹理图像线状区域修补、物体移 除和纹理图像修补，同时与其他算法的修补结果进行比较。通过比较，发现本文 算法在大幅度提高修补速度的同时，仍能保持较好的修补效果。 关键词：图像复原，图像修补，水平集，快速行进算法，分组行进算法，偏微 分方程 a b s t r a c t i m a g er e s t o r a t i o ni so n e o ft h ei m p o r t a n tr e s e a r c hh o t s p o t si nc o m p u t e r g r a p h i c s ， c o m p u t e rv i s i o na n di m a g ep r o c e s s i n g i th a sg r e a tp o t e n t i a li nm a n ya p p l i c a t i o n s , e s p e c i a l l yi nr e s t o r a t i o no fa r t , f a s td a t at r a n s f e r r i n go nt h ei n t e r a c t ，c o m p u t e r a u t o m a t i o n ，s p e c i a le f f e c t s , v i r t u a lr e a l i t ya n ds oo n i m a g ei n p a i n t i n gi sa ni m p o r t a n tr e s e a r c ht o p i ci nt h ea r e ao fi m a g er e s t o r a t i o n ； i t so b j e c t i v ei st or e s t o r et h el o s ti n f o r m a t i o na c c o r d i n gt oa r o u n di m a g ei n f o r m a t i o n a l t h o u g ht h ei n p a i n t i n gb a s i c s a r es t r a i g h t f o r w a r d ，m o s t i n p a i n t i n gt e c h n i q u e s p u b l i s h e di nt h el i t e r a t u r ea r ec o m p l e xt ou n d e r s t a n da n di m p l e m e n t f a s tm a r c h i n g m e t h o d ( f m m ) i sa ne f f i c i e n ta l g o r i t h mf o rl e v e lj e ta p p l i c a t i o n sw h o s et o t a l c o m p u t a t i o nc o s ti so ( n i b n ) k i mp r e s e n t e dam o r ee f f i c i e n ta l g o r i t h mc a l l e dg r o u p m a r c h i n gm e t h o d ( g m m ) w i t ht h ec o m p l e x i t yo fo ( 忉m o t i v a t e db yh i sw o r k , w e p r o p o s ean e wt e c h n i q u ef o ri m a g ei n p a i n t i n gb a s e do ng m m t h e w o r ki n c l u d e si m p o r t a n ta s p e c t sa sf o l l o w s ： ag m mb a s e dn o n t e x t u r ei n p a i n t i n gt e c h n i q u ei sp r e s e n t e d t h i st e c h n i q u e i se s p e c i a l l yu s e f u lf o ri n p a i n t i n gl i n e a rr e g i o n so nn o n - t e x t u r ei m a g e s c o m p a r e dt oo t h e rt e c h n i q u e s , t h et e c h n i q u ew ep r o p o s e di sm u c hf a s t e r w h i l ep r e s e r v i n ga l m o s tt h es a m ei n p a i n tr e s u l t ag m mb a s e dt e x t u r ei n p a i n t i n gt e c h n i q u ei sp r e s e n t e d t h i st e c h n i q u ei s g o o da ti n p a i n t i n gi m a g e sc o n t a i nb o t ht e x t u r ea n ds t r u c t u r ei n f o r m a t i o n , a n dc a na l s ob eu s e df o ro b j e c tr e m o v a l f o rt e x t u r ei m a g e si n p a i n t i n g , w e i n t r o d u c eg m mf o rn a r r o wb a n de v o l u t i o n i ts e e m st h a to u rt e c h n i q u e 啪 p r o p a g a t eo r i g i n a li m a g e ss t r u c t u r ea n d t e x t u r ei n f o m a t i o nv e r yw e l l w ei n t r o d u c eg m mf o rn a r t o wb a n de v o l u t i o n s i n c ei tt a k e sm u c hi e s $ t i m eo nn a l t o wb a n de v o l u t i o n , o u rt e c h n i q u ei sm o r ee f f i c i e n t t h r e ee x p e r i m e n t su s i n go u ra l g o r i t h ma r ei l l u s t r a t e d ，t h a ti s ，l i n e a rr e g i o n s i n p a i m i n go nn o n - t e x t u r ei m a g e s ，o b j e c tr e m o v a l ，a n dt e x t u r ei m a g ei n p a i n t i n g i t s e e m st h a to u rt e c h n i q u ei sm u c hf a s t e rt h a no t h e ri n p a i n tt e c h n i q u e sw h i l ep r e s e r v i n g a l m o s tt h es a m er e s u l t k e yw o r d ：i m a g er e s t o r e , i m a g ei n p a i n t i n g , l e v e ls e t , f a s tm a r c h i n g m e t h o d , g r o u pm a r c h i n gm e t h o d , p a r t i a ld i f f e r e n t i a le q u a t i o n 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果据我所知，除文中已经注明引用的内容外，本论文 不包含其他个人已经发表或撰写过的研究成果对本文的研究做出重 要贡献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名：至荛：避 日期：二：掣 学位论文授权使用声明 本人完全了解华东师范大学有关保留，使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅有权将学位论文的内容编入有关数据库进 行检索有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后适用本规定 学位论文作者签名：王岔，谢伤导师签名： 泐蠢 基于分组行进算法的数字图像修补技术研究 第1 章引言 1 1 研究背景 第1 章引言 据统计，人类获取的信息，大约6 0 来自视觉，2 0 来自听觉，另外2 0 来自触觉和其他感观途径。由此可见，视觉信息的是人类获取信息的重要途径， 而图像作为视觉信息获取和传播的主要载体，随着计算机技术的飞速发展，越来 越受到人们的重视。 图像处理在现代信息处理领域中变得越来越重要，医疗图像、遥感图像、视 频图像、特征识别、三维物体或场景的重建、质量检测、指纹分析等，都需要图 像处理技术的支持。二十世纪八十年代，图像处理的研究与发展使基于f o u r i e r 分析方法的信号处理学科发生了日新月异的变化。目前，主要出现三类的图像处 理理论：随机模型理论、小波理论和偏微分方程理论。随机模型理论主要是基于 马可夫场的随机理论，可以直接处理数字图像。小波理论来源于信号处理，并且 依赖分解技术。9 0 年代以后，基于偏微分方程的数字图像处理方法获得了较大 的发展。 图像修补是图像处理领域一个研究的热点之一。早在文艺复兴时期，人们就 开始修补中世纪的一些艺术品他们的目的就是想通过填补裂缝来使中世纪的一 些艺术作品得到翻新，这样的工作叫做“r e t o u c h i n g ( 润饰) ”或者叫做“i n p a i n t i n g ( 修补) ”。那时候的修补工作主要是由专业修补师手工完成，存在着费时、辛苦、 主观、一旦出错不易修改和工作不容易重复进行等缺点。 用计算机进行数字图像处理的目的有两个，一是产生更适合人类观察和识别 的图像，二是希望计算机能够自动识别和理解图像。而图像复原原则综合了这两 个方面，在研究过程中实际牵涉到很多项技术，而且需要理论与实践相结合；同 时，它又是一个涉及许多技术难题的课题，需要将各项技术进行筛选、调整和结 合，并且应用到课题中去。这也正说明了图像复原研究有着极为广阔的发展天地。 同国外的研究热潮相比，国内的图像复原方面尚处于起步阶段。本文通过对这一 课题的研究，对图像复原、图像修补关键技术进行深入的研究，为提出本文算法 打下了基础。 1 2 研究现状 图像修补就是将图像中的损坏区域以一定的方式修补起来，使之成为一幅完 基于分组行进算法的数字图像修补技术研究第1 章0 i 言 整的图像。在和数字图像修补相关的文献中，研究的问题主要有三： 1 1 视频序列恢复问题 和数字图像修补的一个相关领域，也是非常活跃的一个领域就是受损影片 ( 视频序列) 的恢复。在这里利用到的主要思想就是使用前面或者后面的连续帧 信息来修复受损的视频帧。一般，通用的处理视频序列恢复算法不能处理静态的 图片或者静止的场景，或者裂缝区域跨越了太多的连续帧的影片。 2 1 纹理合成问题 另外一个领域就是纹理合成。这种技术的主要思想就是首先选择一个纹理， 然后将它合成到需要填充的区域里面去。这是一项非常简单但却十分有效的技 术。纹理合成的不足是需要用户指定复制到修补区域的纹理。对于待修补区域包 含了多个不同纹理特征的图像，用户可能需要做大量的工作才能很好的修补。这 些工作可以包括分割以及在图像中寻找相应的替换块。虽然有一部分的搜索工作 可以自动完成，但是也需要设定一些临界参数。 3 ) 去除遮蔽物( d i s o c c l u s i o n ) l h l 题 在一些文献中，去除遮蔽物的工作被称为物体移除( o b j e c tr e m o v a l ) 。关于去 除遮蔽物问题是比较复杂的问题。这类工作也在一些文献里面大量的报道，但都 是一些基础的工作，而且大家都还没有深入的研究。大量解决去除遮蔽物问题的 算法主要是采用样本和纹理合成方法。 针对上述三个方面的主要问题，经过研究和实践，研究人员提出了大量的图 像修补算法。根据处理的图像类型的不同，可以将图像修补算法分为纹理图像修 补算法和非纹理图像修补算法。 非纹理图像修补算法主要有两种，即基于偏微分方程的修补算法和变分方 法： 1 ) 基于偏微分方程的图像修补方法，即微观方法。 这类方法通过分析像素点之间的关系，将损坏区域周围的信息延伸到待修补 区域里面。这类方法的模型主要有c a s e l i e s , m o r e la n ds o b e r t 的公理化方法【l j ， 连续延伸方法【2 1 ，扩散方法【3 】等。 变分方法。 变分方法9 0 年代以来发展较快的另一种图像修补方法，包括所有基于最佳 猜测原理1 4 ( b e s tg u e s s ) 的变分模型。从统计的观点来看，最佳猜测与贝叶斯框架 理论比较相似。这两种方法所采用的图像修补原理是简单和直观的：艺术家在进 行图像修复时需要考虑两方面的主要因素，一方面是图像剩余部分的信息( 数据 模型) ，另一方面是原图像属于什么类型的图像( 图像模型) 。在变分方法中，最佳 猜测通过优化能量泛函实现。这类模型主要有：总体变分模型f 5 6 1 ( t o t a lv a r i a t i o n ) ， 2 基于分组行进算法的数字图像修补技术研究 第1 章i 亩 函数化的弹性摸型 7 1 ，值和方向( v a l u ea n dd i r e c t i o n l 的联合模型 8 1 ，基于 m u m f o r d s h a h 的主动轮廓模型等。 以上两种方法只适用于非纹理图像的修补，而修补纹理图像不可避免的要利 用图像中包含的统计信息，所以一般的偏微分方程方法只能用于非纹理图像的修 补。 二维图像纹理合成算法可以归为两类：一种是采用m a r k o vr a n d o m f i e l d ( m r f ) 模型；另一种是基于特征匹配的方法。对于大多数纹理，m r f 模型 是一种很好的逼近模型，许多算法都是基于这一模型的，并取得了较好的效果。 另外一些算法把纹理当作一种特征集，通过在样本图中匹配特征的方法生成新的 纹理图像。h e e g e r 和b e r g e n l 9 】提出了把随机噪声分层的方法，对随机性纹理取得 了较好的效果，但对结构性纹理效果不理想；d eb o n e t 采用了类似的方法，对结 构纹理的合成驱动了较好的效果1 6 l ，但对结构不明显的纹理会造成人工痕迹。 最近，b e r t a l m i o 和v e s e 提出了一种将图像分解为纹理部分和结构部分i 姗， 并利用相应理论分尉对这两部分修补的方法，s u n gh ak a n g , t o n yc h a n 和 s t e f a n o s o a t t 0 1 1 1 荆用图像特征提取和匹配的方法，提出了一种修补图像中较大区 域的方法。但是，这个模型需要图像有明显的结构特征，以用于提取两个图像的 匹配点，而且还需要参照图像。 1 3 研究意义 图像是客观世界的再现，具有直观、信息丰富等特点，被认为是二十一世纪 信息的主要载体形式。图像修补是图像处理的一项重要课题，在图像处理许多领 域具有重要的意义。图像修补主要可以应用在如下几个方面： 1 ) 对陈旧或者破损的美术作品、照片或者影像等进行修复 由于保存条件，人为或者其他种种原因，经常有一些美术作品、照片或者影 像等资料遭到破坏，这其中包括具有珍贵历史价值的宝贵资料。对这些资料进行 恢复具有非常重要的意义( 图1 1 ) 。 2 ) 为特殊的目的移除图像中的目标。 在一些对外公布的资料中，经常由于一些军事的或者政治的原因，需要隐藏 其中的某个目标，以达到一定的目的( 图1 2 ) 。 3 1 为特殊的目的移除图像中的文字。 图像中过多的文字往往是观察者对图像本身的认识或进一步处理产生一定 的难度，通过使用图像修补技术移除图像中的文字，可以消除这种障碍( 图1 3 ) 。 3 基于分组行进算法的数字闰像修补技术研究 第1 章q l 官 ( a ) 原图片 ( a ) 原幽片 图1 1 对破损老照片进行修复 i b ) 修补后的图片 ( b ) 修补后的图片 围i 2 为特殊目的移除图片中的目标 ( a ) 原图片 ( b ) 修补后的图片 圉1 3 移除图像中多余的文字 1 4 本文的主要工作 本文针对数字图像修补技术展开研究，将传统的图像修补算法与分组行进算 4 摹于分组行进算法的数字图像修补技术研究第1 章0 l 言 法相结合，提出了一种基于分组行进算法的数字图像修补技术。本文的研究对象 是纹理的和非纹理的图像，研究包括三个方面的主要问题： 1 1 纹理和非纹理图像上面线状区域的修补问题。 纹理和非纹理图像上面较大丽积区域的修补( 大物体移除) 问题。 图像修补效率问题。 针对上述三个问题，本文将分组行进算法与图像修补方法相结合，提出了一 种基于分组行进算法的图像修补技术，完成的主要工作包括下面两个方面： 1 1 提出了一种基于分组行进算法的非纹理图像修补算法。该算法适合修补 非纹理图像上面的线状区域。修补非纹理图像上面线状区域的难题在于 传播源图像信息的同时避免造成模糊点。 提出了一种基于分组行进算法的纹理图像修补算法。该算法适合修补同 时包含纹理和结构信息的图像，同时也可以用于图像上面的物体移除。 移除物体的关键问题在于如何填充物体被移除后留下来的大块空白区 域。这就要求填充算法既要能够传播源图像的纹理和结构信息又要避免 填充以后的图像带有明显的人工痕迹。 对比其他图像修补算法，本文算法的优点在于： 1 1 引入分组行进算法对窄带( 待修补区域边缘) 进行水平集曲线演化，节 省了窄带演化的时间，提高了图像修补的效率。 对于非纹理图像，本文提出一种基于分组行进算法的非纹理图像修补算 法。在大幅度缩短修补时间的同时，仍能保持较好的修补效果。 3 ) 对于包含纹理和结构信息的图像本文将基于样本的纹理合成理论与分 组行进算法理论相结合，提出一种基于分组行进算法的纹理图像修补算 法。实验表明，本文算法能够较好的传播原图像的纹理信息和结构信息。 1 5 本文的章节结构 第一章介绍本文的研究背景、研究现状、研究意义、本文所做的主要工作以 及本文章节结构。首先，介绍目前国内外数字图像修补领域研究的主要问题。其 次，介绍目前已有的应用技术和他们的算法，并指出这些技术应用的局限性。最 后，介绍本文所做的主要工作和本文的章节结构。 第二章主要介绍数字图像复原和修补的主要技术。简单介绍目前国内外数字 图像复原和修补领域的主要技术，包括复杂纹理图像的修补技术以及非纹理图像 的修补技术。 第三章介绍水平集曲线演化方法。阐述了本文研究的理论基础：首先介绍曲 线演化运动，然后讨论使用水平集方法进行曲线演化，最后介绍一种高效的窄带 5 摹于分组行进算法的数字图像修补技术研究 第1 章g i 言 水平集曲线演化方法一快速水平集曲线演化算法的数学模型和算法实现的详细 步骤。 第四章介绍分组行进的水平集曲线演化算法。研究了快速水平集曲线演化的 改进算法一分组行进的水平集曲线演化。主要内容包括分组行进算法的基本思 想、数学模型和算法实现步骤。 第五章介绍基于分组行进算法的图像修补技术的设计与实现。首先，介绍本 文的算法原型；其次，介绍适合非纹理图像修补的经典算法，并提出基于分组行 进算法的非纹理图像修补算法的基本思想和实现步骤；最后，介绍适合纹理图像 修补的经典算法，并提出基于分组行进算法的纹理图像修补算法的基本思想和实 现步骤。 第六章介绍本文实验程序的设计和实现，以及展示本文所作的实验。首先， 介绍实验程序的设计与实现，包括待修补区域的预处理、主要数据结构及其关系、 以及执行步骤：然后，展示本文所做的实验，并与其他图像修补算法进行比较。 主要实验包括目标图片上面的线状区域修补、物体移除和纹理图像的修复。同时， 与其它算法处理的结果进行比较，展示本文算法的优劣。 第七章总结与展望。总结本文算法的优缺点，并提出改进方案思想以及将来 的发展方向。 6 蕞于分组行进算法的数字图像修补技术研究第2 章图像复原与图像修补 第2 章图像复原与图像修补 在对本文提出的基于分组行进算法的数字图像修补技术进行讨论之前，有必 要对目前国内外数字图像复原技术和数字图像修补技术的发展现状进行回顾，通 过这些总结可以使我们对国内外相关课题的发展现状有一个比较全面的了解，只 有在对这些算法的优缺点进行充分了解的前提下，我们才能在进一步的研究中扬 长避短，取得令人满意的成果。 2 1 图像及图像处理 什么是图像? 目前尚没有严格的定义，直观的讲图像是以二维强度的分布作 用于人的视觉，是3 d 世界在2 d 成像平面上的投影。 什么是图像处理? 2 0 0 2 年国际联合数学大会上，美国u c l a 大学科学家 t o n yf c h a n 认为：从机器视觉和感知科学的角度讲，图像处理是一种由2 d 图 像( 或者图像序列) 重建3 d 序列中的几何关系、拓扑结构、模式和动力学行为 的基本工具：图像处理可以抽象为一个输入一输出系统t ：q o - q ，t 是数字图 像处理器，包括图像去噪、反模糊、图像修补、图像压缩等等，输入q 0 为观测 到的图像或者图像序列，输出数据q 为包含所有可能的图像特征1 1 2 1 。 2 1 1 纹理及纹理图像 纹理是用来识别目标的重要方法，它是图像中一个重要又难于描述的特性。 到目前为止，还没有公认的纹理的定义。纹理以象素的临域空间分布为特征，因 此无法用点来定义。有些图像在局部区域内呈现不规则性，而在整体上表现出某 种规律性，习惯上，局部不规则而宏观有规律的特性称为纹理。以纹理特征为主 导的图像，称为纹理图像。 由于构成纹理的规律可能是规则的，也可能是随机的。纹理通常分为结构纹 理( 或称为规则纹理) 和随机纹理。规则纹理有可以识别的单元且有一定的排列 规则，现实世界中的纹理大多介于这两者之间( 图2 1 ) 。 纹理和图像是有区别的。对非纹理图像，任选两个方形区域，这两个区域差 别很大：而对纹理图像而言，任选两个方形区域，这两个区域在视觉上是相似的。 所以，可以把纹理图像看作是具有局部性和稳定性的随机过程实现。所谓的稳定 性是指：纹理中每个象素点都可以由其空间临域内的象素集合来表达，并且这种 7 蔫于分组行进算法的数字图像修补技术研究第2 章图像复原与图像修补 表达对每个象素都是一样的。所谓的纹理的局部性是指：窗口中的任一象素可以 由其周围临域内的象素预测到，而与图像中的剩余部分无关。 ( a ) 随机纹理( b ) 结构纹理( c ) 两者兼有的纹理 图2 1 纹理图像 总的来说，纹理图像的特点主要表现为： 1 1 某种局部特性在更大的区域内不断的重复； 2 ) 局部特性是由基本组成单元随机或按一定规则组成的； 整个区域是均匀的统一体。 2 2 图像复原 图像复原试图利用退化现象的某种先验知识来重建或复原被退化的图像。因 而复原技术就是把退化模型化，并且用相反的过程进行处理，以便复原出。原图像。 2 2 1 图像退化复原过程模型 一般来讲，数字图像复原属于工程学范畴，它主要研究如何从退化图像中复 原原始的图像。在该领域，人们曾经使用信号处理、天文学、和光学等理论进行 研究。其实，大量的图像复原算法是与数学理论紧密相连的，例如，估值理论、 线性代数理论和数值分析理论等。总之，数字图像复原技术就是建立模拟的图像 退化模型，然后沿着相反的方向来获得原始图片的估计值。 如图2 2 所示，图像退化过程可以被模型化为一个退化函数和一个加性噪声 项，处理一幅输入图像，弛) 口产生一幅退化图像g 仁力。给定g 伍纠和关于退化 函数日的一些知识已经外加噪声项, k x ，y ) ，图像复原的目的是获得关于原始图 像的近似估计，0 ，y ) 。通常我们希望这一估计尽可能地接近原始输入图像，并 且h 和叩知道得越多，所得到得f ( x ，y ) 就会越接近挖毫力。 如果系统日是一个线性、位置不变的过程，那么在空间域中给出的退化图 像可由下式表示l 玎】： g o ，y ) 一h ( x ，j ，) f ( x ，) ，) + 叩 ，) ，)( 2 1 ) 8 摹于分组行进算法的数字图像修补技术研究第2 章图像复原与图像修补 其中i l 似纠是退化函数的空间描述，“”表示卷积。 ，o ，y ) 日 g ( x ，y ) 介 u , k x ，y ) 图2 2 图像退化，复原模型 对于退化图像的复原，一般可以采用两种方法。一种方法适用于对于图像缺 乏先验知识的情况，此时可以对退化过程( 模拟和噪声) 建立模型，进行描述， 并进而找出一种去除或削弱其影响的方法。由于这种方法试图估计图像被一些特 性相对来说为己知的退化过程影响以前的情况，因而是一种估计的方法。 另一种方法，若对原始图像有足够的先验知识，则对原始图像建立一个数学 模型，并根据它对退化图像进行拟合会更有效。例如，加入已知图像中仅含有确 定大小的原型物体( 如星辰、颗粒、细胞等) ，这样，由于仅是原始图像很少的 几个参数( 数目、位置、幅度等) 未知，因此这是一个检测问题。 2 2 2 图像复原主要技术 在进行图像复原时，有很多方法可以选择。首先，问题既可以用连续数学， 也可以用离散数学进行处理。其次，处理既可以在空m 域，也可以在频域进行。 此外，当必须用数学方法处理时，既可以通过空间域的卷积，也可以通过频域的 相乘来实现。 下面我们回顾一下在实践中证明有效的并且十分重要的图像复原技术。 1 ) 正则化方法。 通过t i k o h o n o v 正则化方法构造合适的变分模型来进行图像复原，构造不同 的正则项来达到不同的目的。 劲基于统计的方法。 由于噪声具有一定的统计模型，通过对噪声模型的分析可以得到去除噪声的 目的，w i e n e r 滤波是一种常用的基于统计滤波的方法。 基于频谱分析的方法。 利用噪声往往在高频段的特点，通过频谱变换后，去掉高频信息从而达到去 除噪声的目的。这种方法的代表是利用f o u r i e r 分析来进行频谱分析。 4 ) 小波分析的方法。 这是目前被广泛采用的一种方法。通过构造具有特殊性质的小波基进行小波 9 基于分组行进算法的数字闺像修补技术研究 第2 章圈像复原与图像修补 分解，然后对小波系数进行处理从而达到去除噪声的目的。 5 ) 基于p d e 的方法。 例如，使用各向异性分解达到去除噪声的目的。 2 3 图像修补 2 3 1 图像修补的主要问题 在和数字图像修补技术有关的文献里面，我们发现主要有三个方面工作。第 一类涉及到影片( 视频序列) 的恢复，第二类是有关纹理综合的工作，第三类是 去除障碍物。 首先，和数字图像修补相关的一个领域，也是一个非常活跃的领域就是受损 影片( 视频序列) 的恢复。它的关键技术是利用受损视频帧的前后帧来修复受损 的视频帧。当然，这种方法不能用于处理静态的图像或者静止的场景。 其次，纹理综合领域。这种技术的基本思想就是首先选择一个纹理，然后采 用一定的方法将其合成到需要填充的区域里面去。这是一项比较简单的技术，却 能产生令人难以置信的效果。 最后一项工作是有关去除障碍物和线性连续的工作，这类工作也在一些文献 里面大量报道。图像中，目标区域的障碍物会增加图像分割的难度，在图像分割 前，需要进行去除障碍物。 研究人员现在| 下在用计算机技术，研究实现自动的图像修补。在这种实际应 用程序中，用户只简单地选择要恢复的区域，计算机就会自动完成剩下的修补工 作。这样，能够显著减少我们的处理时间和精力，它不仅能够填补空白区域，而 且还可以去除一些无关联的物体，去除置于图像上面的文字，徽标，转移一定背 景下的观众，或者给定背景下的人物。除此之外，还能够提高图像分辨率，修正 数字图像在传输过程中丢失的信息。 当然，不管是数字的方式还是手工的方式，修补技术都只是尽可能地去修补 图像丢失的信息。在大多数情况下，对于怎样去填充一个裂缝而产生一个令人满 意的结果，通常的解决方案又很多种。 2 3 2 关于局部图像修补 由于图像函数的复杂性，图像修补并不是简单的函数插值问题，也不仅仅是 一个边界值问题。对于自然图像，m 啪f o r d 【1 4 】提出通过图像分布或者是“可为传 基于分组行进算法的数字图像修补技术研究 第2 章图像复原与图像修补 感器检测出来的因素”来检测模型。对于多数纹理图像来说，虽然其函数常常包 含了非常丰富的统计信息，要远比一些普通的随机域的简单采样复杂的多。在经 典的傅立叶变换方法及广泛应用的线性小波分析中，图像被认为是r 空间中的。 在基于各向异性扩散的尺度空间理论中，图像是被认为在有界变差函数空间中 的。对于许多人认为的图片来说，分段平滑函数是极好的近似函数，并且较容易 实现。由于图像的非平稳性，图像修补技术面临着极大的挑战。因此，我们考虑 的只是局部的图像修补。局部性是图像修补中一个至关重要的概念。 “局部性”不仅表示我们所关心的这一类图像修补问题是局部的，而且我们 研究的修补方案也是局部的。 首先，从数值分析的观点来看，如果要完全重构缺损的图像信息，局部性是 必要条件。因为，根据香农采样定理：如果想正确恢复一有限带宽信号，采样的 间隔必须小于带宽的一半，就是说，采样的问隔必须足够小。从频域角度来看， 一幅图像的平滑区域对应低频信号成分，而边界等重要信息对应图像的高频成 分。如果一个待修补的区域太大，而图像又不是十分平滑的，因此通常会丢失许 多重要的“高频”信息。因此，所有的修补方案都只能处理可被处理的图像，而 不是智能化的从视觉上对原图进行近似。由于图像修补的质量基本上是用人眼判 断的，虽然并不保证它与原图完全相似，但是期望人眼对修补过的图像觉察不多 修补的痕迹，即修补后的图像在视觉意义上是自然的。 一个很好的例子是对人脸的修补。如果待修补区域是左眼或是右眼，修补后 丢失的区域被填充以周围的脸部色彩信息，那么任何一种修补方案都只能得出一 张可怕的脸。因此本文只讨论丢失区域比例较小的图像的修补方案。 其次，在图像修补中，局部性也同视觉分析中的两大问题紧密相关：局部推 断以及比例因素。在计算机视觉以及人类视觉的文献中可以找出相似的理论。 局部推断：局部性情况意味着修补模型并不依靠全局的特性或模式识别( 图 2 3 ) 。修补仅仅是基于局部的信息。对于非纹理图像，模式就是一种空间或色彩 的对称，比如镜面对称，平移不变性及周期性等等。例如，人脸就几乎是按照嘴 巴到鼻子这条中线镜面对称的。虽然从人类的视觉规则是这样的，但是由于它在 比例及特征方面丰富的统计数字，将这一模式以数字智能实现的话十分困难。 比例因素：在视觉分析及图像处理过程中，比例因素扮演了一个普通且十分 重要的角色，在图像修补中也一样。如图2 4 ，图( a ) 中，待修补区域的长度l 已经远大于它特有的特征，左边的“e ”与右边的“三”看起来并无关联，我们 因此认为它是由两个独立的字母“e 三”所组成。图( b ) 中，修补区域的比例 l 远小于l ，一次我们更有理由相信它是一个中间截断的“e ”。在这个例子中， 这个不唯一的结果并不是由全局模式引起的，而是对已有信息的连通方式的不同 1 1 基于分组行进算法的数字图像修补技术研究第2 章图像复原与图像修补 猜测产生的，这个控制的参数就是比例的概念。 蛰缸麓：搿罐臻。* 翅 图2 3 局部推断 jil至垂 o t _ 一 “ ，) 瑟霎 圈2 4 比例因素 2 3 3 非纹理图像局部修补的三原则 在经典的近似原理中，平滑修补允许我们严格的研究修补的精确性。在许多 应用中。这些模型并不实际。因为，一方面许多图像包括了边缘及纹理等非光滑 成分，这就决定了图像的函数模型应该是非平滑的；另一方面，图像常常含有噪 声。 显然，在手工修补过程中，人类的认知能够轻松地解决上述问题。因此，在 建模过程中，希望能够模拟手工修补的机制，建立更加可靠的低层修补模型。因 此，这些特性是建模还原为h e l m h o l t z 最佳猜测原理。在被遮断的区域中，物体 连通的方式只能基于我们所能看到的部分进行猜测。类似的，修复古画时，修补 者只能根据己存在的特征，从而对丢失部分做最佳猜测来填充色彩和物体。 所以，基于最佳猜测原理建立修复模型是很显然的。在确定性逼近中，最佳 猜测是通过最优化一些能量函数建立的。可靠的最佳猜测也不简单，因为必须处 理诸如模式识别和统计信息之类的复杂图像处理工作。 综上所述，简单的图像修补模型必须遵循三个原则嘲： 1 1 模型必须是局部的。 限制模型并不需要全局信息，修补区域的信息完全由修补区域的周围已有的 甚于分组行进算法的数字图像修补技术研究第2 章图像复原与图像修补 信息产生。对于需要先验知识、模式识别等才能修补的图像，本文所述算法并不 能保证总是正确修补。 2 ) 模型必须能够修补破损的狭窄的光滑边缘。 我们必须关心边缘修补，因为人眼对于边缘是十分敏感的。因此，边缘对于 物体的识别以及图像分割来说都是至关重要的。并且，在实际的例子中，图像中 的边缘的断丌或者连接是由很大的动态变化范围决定的。尽管如此，通常并不期 望完全恢复大片受损的边缘，原因就是前面所述的比例因素。 3 1 模型对噪声的鲁棒性。 要求模型对噪声具有鲁棒性是由于对于人类视觉来说，当噪声低于一个合理 的层次时，从存在噪声的图像中提取有用的特征信息并将其扩展到修补区域，这 是一件相对简单的事情。 2 3 4 图像修补的主要技术 长期以来，众多学者对图像修补的算法进行了大量的研究。由于待修补图像 和待修补区域的多样性，导致了针对不同的待修补图像和不同图像的待修补区域 的各种算法层出不穷，各种算法的适用范围和修补效果也各有千秋。 从算法设计时所考虑的适用范围出发，目前存在的修补算法大致有五类。 1 ) 适于序列数字影像的算法( 图2 5 ) 。 r 0 0 锄a l e n l l 5 噜人结合回归模型和马尔可夫随机场对连续影像进行修补。g r 觚c 1 1 6 1 等人介绍了一种多级三维中值滤波的算法，该算法已经考虑到了移动 物体位置上面的变化，从而避免了运动补偿的预处理。um a d d a l e n a i ”l 采用插值 算法对连续影像上的刮痕进行修补，该算法适合待修补区域较窄的影像。l j o y e u x i 墙】等人在去除刮痕的时候，首先采用简单的多项式进行插值，先修补待修 补区域的低频部分，然后采用基于傅立叶级数的插值技术，最后修补待修补区域 的高频部分，该算法适合待修补区域较宽的影像。 2 ) 适合于传输或者压缩过程中误码所造成的影响的算法( 图2 6 ) 。 s s h e m 锄i l l 9 l 是通过线性拟合的方法来 占算当前待修补块在传输过程中 丢失的系数；孙晓军等人【冽利用局域像元的整体相关性和图像纹理的连续性， 通过对已知像元进行迭代拟合，同时修复多点缺损数据。 3 ) 适用于纹理图像的算法( 图2 7 ) 。 李厚强等人1 2 l l 提出了一种基于分形和金字塔算法的纹理综合方法，该方法 适用于生成各向同性( 即无方向性随机纹理) ，但不能生成各向异性( 即有方向) 纹理。 s cz h u 等人阎利用纹理图像的特点，将纹理看作马尔可夫随机场，并结 基于分组行进算法的数字幽像修补技术研究第2 章图像复原与图像修补 合最大熵原则和吉布斯取样进行纹理综合。h e e g e r , b e r g e n 等人1 8 l 认为图像纹理 不能由一个“确定性的”算法产生，所以他们在图像产生的过程中添加了一个随 机因素，从一幅随机噪声图像合纹理采样出发进行纹理综合，该算法不适合纹理 采样中包含结构( 如积木块) 的纹理综合，因为添加噪声会破坏边缘。 舢适合边缘保持的算法。 结构修补的方法主要是通过待修补区域相邻区域的灰度信息和梯度方向或 光照线方向( 光照线是只图像上面的一条线或一个面，它构成对给定的光源来说 具有相等的照度或光强度的点的轨迹) 信息的扩散来达到结构修补的目的。在文 献嗍中，作者用相同的灰度值连接与闭合区边界相连的t 型区域。该算法最初是 为了图像分割，但是消除闭合区域与图像修补有着相似之处。许多学者根据这个 思想进行了将该算法应用于图像修补的尝试，并取得了令人满意的成果。m a s n o u 和m o r e l q 根据上述思想提出了一种变分公式，用连接光照线来达到修补的目的， 该算法要求简单的拓扑，不能保持修补区域边界的角度，并且用直线来连接相同 的同灰度值的象素。 5 ) 纹理综合与边缘保持结合的算法【图2 6 ) 。 s h a n a n t a n ud r a n e 等人1 2 3 】对图像修补技术应用于图像无线传输和图像压缩 进行了探讨，他们提出的算法首先将图像分成大小相等的若干子块，然后将各子 块分为纹理块和结构块，最后若丢失的块为纹理块则采用纹理修补的方法进行修 补，若丢失的为结构块则采用结构修补的方法进行修补。该算法一般来说比整幅 图像都采用单一技术进行修补效果要好。然而，实际上图像的任何一部分一般都 不会是纯纹理或纯结构的。为了解决这个问题，m a r c e l o b e r t a l m i o 等人1 2 4 j 提出了 在一幅图像上面同时采用纹理综合和结构修补。该方法同时结合了现有的三种算 法：图像纹理和结构分离、纹理综合、结构修补。首先将图像分解为纹理图像和 结构图像，然后用结构修补的方法对结构图像进行处理，用纹理综合的方法对纹 理图像进行处理，最后再将两个处理结果相加。该算法针对图像的不同特点利用 两种不同的算法取得了较满意的结果。 ( a ) 第n 1 帧( b ) 第n 帧 ( c ) 第n + l 帧 图2 5 数宇影像修补实例 1 4 基于分组行进算法的数：幽像修补技术研究第2 章图像复腻与图像修补 ( a ) 传输之前( b ) 传输之后( c ) 修补之后 图2 6 传输过程误码图像修补实例 ( | ) 厥图像( b ) 采j j 纹理合成算法修补之后 图2 7 纹理图像修补实例 基于分组行进算法的数字幽像修朴技术研究第3 章水平集曲线演化方法 第3 章水平集盐线演化方法 水平集方法( 1 e v e ls e tm e t h o d ) 是求解几何曲线演化( g e o m e t r i cc u r v e e v o l u t i o n ) 的一种新颖方法，它以隐含的方式来表达平面闭合曲线，避免了对闭 合曲线演化过程进行跟踪，将曲线演化转化成数值求解偏微分方程问题。 本章首先对曲线演化运动进行阐述，然后使用水平集方法进行曲线演化，最 后介绍一种高效的窄带水平集曲线演化方法一快速水平集曲线演化算法。 3 1 曲线演化 曲线演化是指曲线上各点以某种方式不断改变自身的空间位置。在变化过程 中，曲线可能扩张、收缩、分裂、合并，各点的改变方式和行为方式可以不同。 3 1 1 曲线演化运动 描述曲线几何特征的两个重要参数是单位法矢和曲率| | 。单位法矢描述 曲线的方向，而曲率七则描述曲线的弯曲程度。曲线演化理论就是仅利用曲线的 单位法矢和曲率等几何参数来研究曲线随时间的演变情况。 假设演化曲线为： c o ，f ) - 0 0 ，) y o ，f ) )( 3 1 ) 其中，s 矢任意参数化变量，t 是时间，则曲线沿其单位法矢方向的演化过 程可以用如下偏微分方程表示： 旦掣v ( c o , t ) ) x ( 3 2 ) 唧 其中，y 心仅圳是速度函数，它决定曲线上面每个点的演化速度。 研究中，最常用的曲线演化是曲率演化。曲率演化可以用如下热力学方程加 以描述： a c ( s , t ) 积- ( 3 3 ) 甜 其中，口为正值常数。可以证明，任意形状的简单闭合曲线，在上述偏微分 方程的驱动下，将逐渐变平滑，并最终收缩成一个圆点。 假设曲线演化过程充分光滑，经过一个充分小的时