（计算机应用技术专业论文）基于加权块匹配的图像修复方法.pdf

华东师范人学硕士学位论文摘要 摘要 随着计算机技术的发展和数码设备的普及，图像的智能操作和编辑技术引起了 许多研究人员的兴趣，并逐渐发展成为一个研究热点。图像修复是指用图像中的已 知信息修复破损区域或者移除图像中的遮挡物，获得视觉上的满意效果，是图像操 作的一个重要内容。它在文物保护、影视特技制作、虚拟现实、多余物体剔除等方 面有着广泛的应用。 目前，修复算法主要有基于p o i s s o n 方程的内绘法和基于样本块的块匹配法。内 绘法模仿了热扩散过程，沿着等强度线方向平滑地复制目标区域周围的信息到目标 区域内。该方法得到的修复结果非常光滑，缺点是不能修复大范围的纹理区域，计 算量大。块匹配法是一种条件约束下的纹理合成方法，它按一定的填充顺序把已知 区域的信息块复制到未知区域。块匹配算法简单，运行效率高，成为近期的主流研 究方向。本文就块匹配算法展开研究，提出了新的基于梯度的优先级计算方法、加 权块匹配标准、局部搜索和用户干预相结合的最佳匹配块搜索策略。在此基础上， 给出了一个新的块匹配算法一基于加权块匹配的修复算法。实验结果表明，该修 复算法运行速度快，能够很好地修复纹理和结构图，取得视觉上满意的效果。 本文首先阐述了两种常见的图像修复算法：内绘算法和块匹配算法；其次介绍 了结构优先的修复技术，阐明了结构在图像修复中的重要性，以及不同的块大小和 搜索范围对图像的处理结果造成的不同程度的影响；最后讲述了加权块匹配修复算 法。 关键词：图像修复，优先级，加权块匹配，置信度，梯度 华东师范大学硕上学位论文 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n dt h ep o p u l a r i t yo fd i g i t a ld e v i c e s ，t h e i n t e l l i g e n tm a n i p u l a t i o na n de d i t i n gt e c h n i q u eo fi m a g e sh a sa t t r a c t e dm a n yr e s e a r c h e r s ， a n dh a sb e c o m ear e s e a r c hh o t s p o t i m a g er e s t o r a t i o ni st or e s t o r et h ed a m a g e da r e a so r r e m o v et h eo c c l u d i n go b j e c t s 谢t i lk n o w ni n f o r m a t i o n ，e v e n t u a l l ya c q u i r e sav i s u a l l y s a t i s f a c t o r yr e s u l la n di ti sa ni m p o r t a n tc o n t e n to fi m a g em a n i p u l a t i o n i m a g er e s t o r a t i o n h a sb e e nw i d e l yu s e di nt h ec o n s e r v a t i o no fc u l t u r a lr e l i c s ，f i l ms p e c i a le f f e c t s ，v i r t u a l r e a l i t y , r e m o v a lo fr e d u n d a n to b j e c t se t c s of a r , t h e r ea l et w om a i nr e s t o r a t i o na l g o r i t h m s ：i m a g ei n p a i n t i n gb a s e do nt h ep o i s s o n e q u a t i o na n de x e m p l a r - b a s e da l g o r i t h m t h ei m a g ei n p a i n t i n gt e c h n i q u e sf i l l h o l e si n i m a g e sb yp r o p a g a t i n gl i n e a rs t r u c t u r ei n t ot h et a r g e tr e g i o n , w h i c hi ss i m i l a rt od i f f u s i o n p r o c e d u r e t h i sm e t h o dc a na c q u i r es m o o t hr e s u l t s ，b u tf a i lt or e s t o r eaw i d er a n g eo f t e x t u r e r e g i o n s ，a n dt h ec o m p u t a t i o nc o s t i s h i g h e x e m p l a r - b a s e da l g o r i t h m i sa c o n s t r a i n e dt e x t u r es y n t h e s i sm e t h o d ，w h i c hp r o p a g a t et h ei n f o r m a t i o no fk n o w nr e g i o n i n t ot h eu n k n o w na r e a 、析t l lac e r t a i nf i l l i n go r d e r t h i sa l g o r i t h mi sp o p u l a rf o ri t s i n t u i t i v ei d e aa n de f f i c i e n c y t h i sp a p e rp r o p o s e san o v e lm e t h o df o rc o m p u t i n gp r i o r i t y b a s e do nt h eg r a d i e n t ，w e i g h t i n gp a t c hm a t c hc r i t e r i a ，i n t r o d u c e sas e a r c h i n gs t r a t e g yf o r t h eb e s tp a t c hm a t c ht h a tc o m b i n e sl o c a ls e a r c hw i t ht h eu s e ri n t e r v e n t i o n o nt h eb a s i so f t h e s ea l g o r i t h m s ，w ep r e s e n tan e wp a t c hm a t c h i n ga l g o r i t h m - - r e s t o r a t i o na l g o r i t h m b a s e do nt h ew e i g h t i n gp a t c hm a t h an u m b e ro fe x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a t o u r a l g o r i t h mr u n sf a s ta n dw e l lr e s t o r et h ei m a g e s 、析廿lt e x t u r e sa n ds t r u c t u r e s ，o b t a i n i n g v i s u a l l ys a t i s f a c t o r yr e s u l t s t h i sp a p e rf i r s t l yd e s c r i b e st w om a i ni m a g er e s t o r a t i o na l g o r i t h m s ：i m a g ei n p a i n t i n ga n d e x e m p l a r - b a s e da l g o r i t h m s e c o n d l y , w ei n t r o d u c ear e s t o r a t i o nt e c h n i q u et h a t f i l l s s t r u c t u r er e g i o n sa tap r i o ro r d e r , c l a r i f yt h ei m p o r t a n c eo ft h es t r u c t u r ei ni m a g e r e s t o r a t i o n ，a n dd i s c u s sr e s t o r a t i o nr e s u l t sc o m p l e t e db yv a r i o u ss i z ep a t c h e sa n ds e a r c h r e g i o n s f i n a l l y , w eg i v et h ew e i g h t i n gp a t c hm a t c h i n ga l g o r i t h m k e y w o r d ：i m a g er e s t o r a t i o n ；p r i o r i t y ；w e i g h t i n gp a t c hm a t c h ；c o n f i d e n c e ； g r a d i e n t 学位论文独锄性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取 得的研究成果。据我所知，除文中已经注明引用的内容外，本论文不包 含其他个人已经发表或撰写过的研究成果对本文的研究做出重要贡献 的个人和集体，均已在文中作了明确说明并表示谢意 作者签名：盘3 亘盈盏 一 日期： 学位论文授权使用声明 加o j ) 2 二 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版有权将学位论文用于非赢利目的的少量复制并允许论文进入 学校图书馆被查阅有权将学位论文的内容编入有关数据库进行检索 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用 本规定。 学位论文作者签名：j 丽哿 日期： 塑里i ：! 三：兰 导师签名：习奢数 日期边班垂 o r i g i n a l i t yn o t i c e i np r e s e n t i n gt h i st h e s i si np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o rt h em a s t e r sd e g r e e a te a s tc h i n an o r m a lu n i v e r s i t y , i 、v a n a n tt h a tt h i st h e s i si so r i g i n a la n da n yo ft h e t e c h n i q u e sp r e s e n t e di nt h et h e s i sh a v eb e e nf i g u r e do u tb ym e a n yo ft h er e f e r e n c e st o t h ec o p y r i g h t ，t r a d e m a r k ，p a t e n t ，s t a t u t o r yr i g h t ，o rp r o p r i e t yr i g h to fo t h e r sh a v eb e e n e x p l i c i t l ya c k n o w l e d g e da n di n c l u d e di nt h er e f e r e n c e ss e c t i o na tt h ee n do ft h i st h e s i s 跚g n a t u r e ：峥 c o p y r i g h tn o t i c e ih e r e i na g r e et h a tt h el i b r a r yo fe c n us h a l lm a k ei t sc o p i e sf r e e l ya v a i l a b l ef o r i n s p e c t i o n if u r t h e ra g r e et h a te x t e n s i v ec o p y i n go f t h et h e s i si sa l l o w a b l eo n l yf o r s c h o l a r l yp u r p o s e s ，i np a r t i c u l a r , s t o r i n gt h ec o n t e n to ft h i st h e s i si n t or e l e v a n td a t a b a s e s ， a sw e l la sc o m p i l i n ga n dp u b l i s h i n gt h et i t l ea n da b s t r a c to ft h i st h e s i s ，c o n s i s t e n t 谢廿1 ”f a i ru s e ”a sp r e s c r i b e di nt h ec o p y r i g h tl a wo ft h e p e o p l e sr e p u b l i co fc h i n a s i g n a t u r e = 鼙烨r fd a t e ：掣 l i 华东师范大学硕十学位论文引言 第一章引言 1 1 研究背景与意义 图像修复技术是指针对图像中遗失或者损坏的部分，利用未被损坏的图像信息， 按照一定的修复规则填充损坏部分，使得处理后的图像接近或达到原图的视觉效果。 该技术可以修复电影胶片上的线状划痕、褪色破损的照片、视频中丢帧等这些常见 的图像瑕疵。早在文艺复兴时期，人们就开始了修复画面的工作。对一些受损的中 世纪艺术品，艺术家通过观察画作的原始风格和寓意，用自己的主观创作填补那些 裂缝来使画面恢复原貌，这一工作称之为修补或修复( i n p a i m i n g ) 。另外，艺术家在 绘画过程中，经常要对画作进行润饰( r e t o u c h i n g ) 。从原理上看，修补和润饰有共 同之处，它们遵循以下基本规则：( 1 ) 图像修复是为了恢复图像的完整性，而如何 填补目标区域是由全局图像决定的；( 2 ) 目标区域周围的结构向目标区域内部延伸， 并通过延伸抵达目标区域边界留啪结构来绘制等强度线；( 3 ) 由等强度线定义目标 区域刃内不同的区域，并用不同的、与昆湘匹配的颜色填充它们；( 4 ) 填充小的细 节部分( 如蓝天上出现的一个小白点，可以将这个白点修复为跟它周围点一样的颜 色) ，即添加纹理。 随着计算机科学技术的发展，生活中产生了越来越多的数字图像和视频，因此 数字媒体的智能处理逐渐引起了人们的研究兴趣，成为计算机科学中的一个重要研 究领域，是目前的研究热点之一。半自动化或完全自动化恢复图像是图像智能处理 的一个方面，是当前计算机图形学和机器视觉中的一个研究热点。它的基本原理为： 从图像的己知区域中获得信息去填补未知部分，以获得视觉上满意的效果。实际上， 自动修复算法的基本依据是艺术家的修复规则，是对人工修复过程的模仿。图像修 复的智能方法被广泛应用到文物保护、影视特技制作、虚拟现实、多余物体剔除( 如 数字图片中的多余背景或前景，图像中需要保密隐藏的内容、视频图像中删除部分 人物、文字等) 等多个方面。 图像的人工修补效率很低。对于需要修复的图片或工艺品，人们必须在开始处 理之前花费大量的时间对它们进行研究，分析它们的色彩搭配、几何造型、对象组 成、纹理、结构等等，这一个过程会明显地融入人的主观意志，从而消磨或扭曲原 创作者的本来意图，而且人工处理的结果难免会留下修复痕迹，减弱了目标区域与 华东师范人学硕士学位论文引言 周围边界的协调性，让人产生不真实的感觉。尽管有一些传统的辅助软件如 p h o t o s h o p 和p a i n t ，以及一些方便实用的图像处理小工具如t u r b op h o t o 、光影魔术 手等等，它们能够方便快捷的对图片进行后期加工，并且得到较为满意的效果。但 是要取得良好的修复效果，用户同样需要花费大量的时间做细致的交互工作，而且 有时候处理后的图像会留下尖锐的边界、模糊纹理等明显的修复痕迹。而我们对图 形图像修复算法的研究，就是为了能够最大程度地提高匹配精度，避免图像的走样， 从而提高修复质量，并实现图像自动修复的功能。因此，图形图像修复算法的研究 不仅具有合理的理论意义，而且具有很大的实际价值。 在2 0 世纪后期就有人开始对由计算机自动完成图像修复的算法进行学习研究， 并改进已有算法的不足之处，不断提出新的修复方法，到现在已经积累了丰富的研 究成果，其中主要的方法有以下几种： 内绘法：b e r t a l m i o 1 模仿了热扩散过程【2 ，3 】沿着等强度线方向平滑地复制目 标区域周围的信息到目标区域内。由于扩散作用是通过逐点实现的，所以内绘法计 算量大、很不稳定。此外，该方法得到的修复结果因为缺少纹理而变得非常光滑， 特别是修复大范围的纹理区域时，将会形成一片模糊的区域。为了克服这个缺点， b e r t a l m i o 等人【4 】结合了内绘法和纹理合成方法，将图像分解成两部分：一部分代表 图像的结构，另一部分代表图像的纹理，并分别用内绘技术和纹理合成方法完成图 像的修复。但是这个改进的方法需要很大的计算量，使得图像修复速度较慢，因此 它只适用于修复小的破损区域。 整体变分方法和基于曲率的扩散模型：整体变分方法( t v ，t o t a l v a r i a t i o n a l ) 5 】 采用了欧拉一拉格朗日方程和各向异性的扩散，基于曲率的扩散模型( c d d ， c u r v a t u r e d r i v e n d i f f u s i o n ) 方法【6 】是整体变分法的一种扩展，在扩散过程中考虑了轮 廓的几何信息( 曲率) ，可以处理较大的区域，但边界处往往很模糊。 对图像进行滤波的方法【7 】能快速地修复破损区域，但该算法仅考虑了破损区域 边缘一周的图像颜色值，使其仅适用于破损区域为2 3 个象素宽度的情形。 纹理合成的方法【8 ，9 ，1 0 ，1 1 】：给定某个有限大的纹理样本，然后生成任意大 小的同种纹理，最后从源样本中往待修复区域传播纹理。样本纹理合成方法从基于 特征匹配的方法发展到基于m r f ( m a r k o vr a n d o mf i e l d ) 模型的方法，如基于点匹 配的方法和基于块匹配的方法。m r f 模型是香农在1 9 4 8 年提出的，由 个具有先 华东师范大学硕士学位论文引言 后顺序的已知字母决定下一个将要生成的字母的概率分布。它根据结果图中当前待 合成像素点的邻域，在样本图中搜索所有像素并得到和邻域匹配的像素点的集合， 然后从中随机选择一个作为当前待修复像素点的最佳匹配点，并将它合成到结果图 中。e f r o s 和l e u n g 9 提出了通过无参采样方法的纹理合成，对于当前待修复点p ， 在样本图中搜索与其具有相似邻域的待选像素点，形成关于p 的直方图，然后从待 选点中随机选择一个作为p 的匹配点，并且用邻域的尺寸控制修复结果的随机性。 l i a n g ，l i u ，x u ，g u oa n ds h u m 1 2 先将样本纹理重复映射得到初步的修复结果，然后 在结果图中随机选择纹理块，并通过混沌变换将它绘制在图中的随机位置上，这种 做法对随机性纹理的处理效果较好，而且速度很快。e f r o s 和f r e e m a n 1 3 按扫描线 顺序合成纹理块。它在输入图像中搜索和输出图像中当前修复位置的边界区的误差 小于给定阈值的纹理块，形成待选纹理块集合，从中随机选择一个作为匹配纹理块， 然后利用最佳分割路径将匹配纹理块贴到输出图像中。这种逐块合成纹理的方法大 大缩短了修复时间，不仅适用于随机性纹理，而且适用于结构性纹理，还能较好地 去除图像中的大块污斑，但由于算法运行时间是与图像大小成正比，而不是与目标 区域成正比，因此修复时间相对较长。另外，这种办法处理纯纹理的图像时可以得 到满意的结果，但在修复自然图片中的未知区域或者是那些具有线性结构和复杂纹 理的图片时，这种算法会将图像中的结构看成是二维的纹理，所以效果并不理想。 近来，有人提出了基于样本块的图像修复方法 1 4 ，1 5 ，1 6 ，1 7 ，1 8 ，1 9 1 。第一 个基于样本块的合成方法是由h a r r i s o n 1 5 提出的，他通过判断目标区域邻域中的纹 理差别来确定目标区域中像素的填充顺序。虽然从直觉上会认为这种办法是合理的， 但是它忽视了目标区域附近的噪音对图像结构的影响，通常这些噪音会将明显的结 构覆盖掉，从而影响修复效果。另外一种类似的技术是：通过目标区域的局部形状 决定填充顺序【1 9 】，但是这种方法不能清楚地复制线性结构。为了有效地将结构延伸 到目标区域，c r i m i n i s i 等人f 1 4 】提出了一种受等强度线驱动的基于样本块的图像修复 算法，它用样本块以向内的同心层顺序填充目标区域。其中，块填充顺序由置信度、 等强度线和目标区域边界的矢量之间的角度决定。由于填充过程中目标区域的边界 会发生变化，因此在一些情况下线性结构不能被持续的修复。 梯度分析方法和泊松方程在图像处理中被广泛的应用，诸如图像压缩 2 0 】，图像 编辑 2 1 ，2 2 ，以及摄影文物移除【2 3 】。j i a n b i n gs h e n 等人【2 4 】尝试在图像修复中使 华东师范大学硕士学位论文引言 用渐变映射，并提出了基于梯度的算法。他们将目标区域的修复分为两个阶段：首 先使用基于样本块的算法填充目标区域的渐变映射，其次通过求泊松方程来重建渐 变映射。这个技术的性能比其它现有的修复方法都比较好，但是其计算成本相对于 c r i m i n i s i 等人提出的算法 1 4 1 要高。 通过分析上述提到的图像修复方法的优缺点，本文对图像修复方法在处理图像 特征( 如颜色、纹理、结构等) 、待修复区域中各点的填充顺序、确定最佳匹配块的 搜索范围等方面做出了一些改进。 1 2 研究目的与内容 按照对图像现有信息的了解程度来分，图像修复方法大致可分为两种：一种方 法适用于缺乏图像先验知识的情况，此时可对图像进行整体判断，以图像的空间连 贯性和视觉为依据，在已知图像的其他完整区域中寻找与破损区域最接近的信息， 这是一种估计方法；另外一种方法是针对原始图像有足够的先验知识的情况，根据 已知图像的相对位置的可靠信息区处理损坏图像，能够获得更好的修复效果。 通过对现有算法的分析，我们清楚地看到图像修复的主要问题：一是修复质量 和算法运行时间的平衡问题，二是能否智能识别纹理和结构，从而真实还原图像。 本文拟改进基于样本块修复方法，以解决图像修复质量和算法时间复杂性的平衡问 题，达到纹理和结构的真实还原。 基于样本块的图像修复方法易理解，操作简单，只需要记录一些数据，如目标 区域的边界、当前待修复块、最佳匹配块的位置等等，但是对内存要求较高，程序 执行时需要进行大量的计算。因此，我们提出了局部搜索方法来解决这个问题，这 种方法不仅能够提高搜索效率，避免搜索无关区域，而且提高了匹配块的准确度。 另外，在比较模板块与候选块的相似度方面，我们引入了加权块匹配标准：模板块 中与块中心距离越近的点具有更大的权重，对匹配误差越敏感。基于以上这两种想 法，我们提出了基于加权块匹配的图像修复技术。 1 3 本文主要工作与组织结构 本文的主要工作有： l 、提出了基于梯度的优先级计算方法，它能保证以结构优先填补的方式修补图 像，可以较真实地还原纹理信息。与已有优先级计算方法相比，该方法不考虑未知 华东师范大学硕r 上学位论文引言 区域的边界，只关心结构信息，从而不会出现结构走样的修复结果。 2 、给出了局部搜索和用户干预相结合的最佳匹配块搜索策略，能在保证修复质 量的前提下有效地减少搜索时间，从而大幅度地提高修复效率。 3 、提出一个新的块匹配标准加权块匹配标准，它反映了像素之间的空间连 贯性，使得能找到视觉上满意的最佳匹配块。 本文的组织结构如下： 第一章：引言。阐述了本文的研究背景、研究的意义及研究目的与内容、主要 的研究工作和内容组织。 第二章：图像修复的主要方法。介绍了图像修复领域中已经使用的方法，以及 本文中使用的在图像识别中的一个重要的块匹配方法。 第三章：结构优先的修复技术。在基于梯度的填充顺序基础之上，提出了结构 优先的修复技术，并指出如何搜索最佳匹配块。 第四章：基于加权块匹配的修复技术。本章提出了加权块匹配的修复算法，并 提供了修复模型、算法及实现过程。 第五章：总结与展望。本章主要对本文进行总结，指出本文的研究成果以及今 后进一步有待研究的工作。 华东师范大学硕士学位论文图像修复的主要方法 第二章图像修复的主要方法 修复技术从中世纪时手工修复工艺品到偏微分方程方法的引入，再到纹理的合 成方法以及基于样本块的方法，图像修复技术已经有了很大的改进，这一章介绍目 前最常用的两种方法：内绘算法和块匹配算法。 2 i 内绘算法 在内绘法出现之前，人们通常使用纹理合成的方法实现图像的修复。该方法用 纯纹理去填充破损区域，能较好地去除图像中的大块污斑，但由于算法运行时间与 图像大小成正比，而不是与目标区域成正比，所以修复时间相对较长。此外，该方 法还需要用户指定将要使用哪些纹理、需要填充哪些位置，然而被填充区域的周围 可能不只是纹理，还可能有结构混合在一起，因此这样做降低了修复结果的可靠性。 经过对图像修复算法的不断探索研究，b e r t a l m i o 等人f 1 】提出了内绘算法。 在内绘算法中，用户只需要输入待修复图像并确定目标区域即可。如图2 1 a 所 示，用q 表示目标区域，融堤日标区域的边界，图像中除目标区域以外的所有区域 为源区域矽，它在修复过程中始终保持不变。 设l o ( i , j ) 是一个离散的二维灰度图。图像修复过程中将产生一系列的图像 j ( f ，_ ，) ，并且，( f ，歹，o ) = 厶( 歹) ，l i r a 。一i ( i ，_ ，刀) = 厶( f ，) ，其中，厶g ，) 是最终的修复结果。 内绘算法的执行过程可以表示为： j ”1 g ，) = j ，”( f ，d + 觚“以) ，v ( i , j ) eq ( 2 1 ) 其中，上标胛表示修复次数，( f ，_ ，) 是像素坐标。” _ ，) 表示第刀次修复时目标 区域肭的图像像素之，而，“1 gj | ) 是，4 g _ ，) 更新后的图像，随着，的增加，图像 将逐步得到改善。f 是改善率，r g ，) 表示图像，”g _ ，) 的更新，它的定义如下： “枷2 卜抄耥妒叫埘 q 2 其中朋”) 是被鼬“的信乩碗用来度且脯变化殆l 表示等强 度线的方向。历呜嵩的乘积表示而在雨上的投影，也就是l 沿方向的变化量， i n i 华东师范大学硕士学位论文 图像修复的主要方法 如公式( 2 6 ) ，我们用矿表示该乘积。对每一个给定的点( f ，_ ，) 都有一个离散的梯 度向量v 1 ”( f ，_ ，) ，它表示该点在空间上变化最大的方向。 其中，而瓴，) 定义如下： 万r ( f ，- ，) ：= ( r ( f + l ，- ，) 一r ( ，一1 ，d ，r ，+ 1 ) 一f “歹一1 ) ) ( 2 3 ) l ：q ，n = 1 0 q ，j 、) + 1 0 q ，j 、 面( ，n ) ( 一“( _ ，) ，i x “( f ，) ) i n ( i , j 川i + 厄瓦万可百万 朋丽卜黼 ( 2 4 ) ( 2 5 ) ( 2 6 ) 最后，计算图像梯度归一化后的值l v ，”( ) l 。其中，下标b 、分别表示向前误 差和向后误差，m 、m 分别表示在0 到导数范围内的最小值和最大值。 i v r ( i , ：) l ： 唑! ：! ：二! ! ：! 二! ! ：! ! 二! ! ：圣毗 0 ( 2 7 ) l ( ，】蝴”) 2 + ( 却”) 2 + ( ，曲w ”) 2 + ( j ，咖”) 2 ，w h e n f l 0 为了减少噪音对抵达蒯勺等强度线方向的预测造成影响，在预处理时，要对整 幅图像进行各向异性的扩散。特别地，下面是连续时间连续空间各向异性的扩散 公式的简单离散化： 祟( 训 f ) = ( 训) 坼，y f ) i v 以砌l ，v ( 训) 饼 ( 2 8 ) 其中，饼是在q 周围以为半径的扩大区域，k 是，的等强度线的欧几里得曲率， & ( 工，j ，) 是饼区域内的一个光滑函数，当瓴y ) 在q 内时其值为l ，在掰内时值为o 。 之后，图像修复进入算法的循环，即对目标区域力的边界a 肚的待修复像素执 行公式( 2 1 ) ( 2 7 ) ，这时口内的值会根据图像修复过程中所进行的操作而发生变 化，且q 一q 区域带的灰度值、等强度线方向被复制到q 内。同时，每隔几个循环， 图像就需要进行一次各向异性的扩散，这种扩散使得在修复过程中，曲线既不会丢 失其明显的特征也不会相互交叉，直到t ：0 ，即修复达到稳定状态时才停止执行扩 散。当目标区域的像素都被修复好时，退出循环，修复算法执行结束。 内绘算法得到的修复结果非常光滑，应用广泛，能够修复旧照片，损坏的胶卷， 华东师范人学硕学位论文 目像恬复的 要方法 移除冗余文字，以及移除大的物体等等但是该方法使得图像的修复区域变得很模 糊，特别是修复比较大的纹理区域时，结果更模糊。 2 2 块匹配算法 内绘法采用了扩散技术，通过逐点处理的方法实现了对目标区域的修复，因此 该方法计算量大，不能修复大范围的纹理区域。纹理合成方法是采用从源区域中往 待修复区域复制纹理的方法来实现图像修复的。这种方法能较好地去除图像中的大 块污斑，但由于算法运行时间是与图像大小成正比，而不是与目标区域成正比，因 此修复时间相对较长，并且在修复自然图片中的未知区域或者是那些具有线性结构 和复杂纹理的阻片时，效果并不理想。最近，有人提出了基于样本块的图像修复方 法 1 4 ，1 5 ，1 6 ，1 7 ，1 8 ，19 】，本文称为块匹配算法。第一个基于样本块的合成方法 是由n a n i s o n 1 5 黜的，假定要修复以p 为中心的方形模板块n ，ne n ，源区域 中的最佳匹配块e ，它与中已经被填充的部分最相似。如图2 l b 所示，如果虬 处于图像内的直线上，那么和它昂相似的块也处于类似的直线上，如图2 1 c ，野和 均是n 的最佳匹配块。图2l d 就是从最佳匹配块中拷贝信息到模板块中得到的图像。 园圆圈圈 圈2 1 块匹配示意图 如今，块匹配算法己经得到了广泛的应用，例如，在计算机识别过程中，常需 要将同一空间在不同时间和拍摄条件下获得的图像进行对准，或根据已知图像在另 一幅图像中搜索相同或相近的部分，这就需要用到匹配的知识。块匹配简单的讲就 是将图像看成是许多连续的样本块，我们用其中某一个固定的块或其它图像中的一 个已知块与这些块相比较，进而得到一个或多个与这个固定块信息最相近的样本块 f 2 5 。 图像匹配是图像处理领域中的个重要手段，它又被称为“模式匹配”或“模 板“配”。设模板t 6 t x n ) 在搜索图吖w x h ) 上平移，模板覆盖下的那块区域称为子 华东师范大学硕上学位论文图像修复的主要方法 图岛，f 、歹是这块子图的左上角像素点在s 中的坐标，叫做参考点，如图2 2 所示。 则搜索范围是： 1 i w - n + i 1 j h m + i ( 由被搜索图 子图s i 图2 2 被搜索图与模板 模板t 基于上述描述，则可以通过比较模板丁和子图s u 的相似性，来完成模板的匹配 过程。相似性关系函数为： 烈歹) ：m n s ( m ，功一7 ( 所，刀) 2 将上式展开可以得到： ( 2 9 ) d ( ，) ：m n 岛( 肌，疗) 2 2 m n 而( 肼，胛) r ( 历，) + m n 【7 ( 所，行) 1 2 ( 2 1 0 ) m = ln = l m = lh = lm = ln = l 这里第一项为模板覆盖下的子图的能量，第三项为模板的总能量，它们都与模 板匹配无关。第二项式模板和子图的互相关系，随着g 力改变而改变。当模板丁和 子图岛匹配时，该项有极大值，因此可以定义相关函数为： 归一化得：聊= 糯= 一 ( 2 1 1 ) 华东师范 学硕学位论立罔像修复的土要片眭 e s ( m ，n ) x t ( m , n ) ( 2 1 2 ) 酬卜鹰蒿啊 当模板和子图完全一样时，相关系数尉护1 ，否则，胄“力 d o 时就停止对该点所在块的计算，继 续对下一个块进行匹配。使用误差法进行匹配的速度较快，它与模板的尺寸有关， 且阈值的大小对匹配速度和修复质量也有影响。 本节所讲的块匹配算法，是在同一副图像的源区域中寻找与特定块最相近的匹 配块。我们在后续章节中会详细介绍。 2 3 小结 本章主要介绍了两种图像修复方法：内绘算法和块匹配方法。内绘算法的修复 结果中的目标区域会变得很模糊，特别是对比较大的纹理区域的修复。而基于样本 块的处理技术可以看作是一种带约束的纹理合成方法，该方法在计算效率和修复性 能上都取得了很大的进步。 华东师范大学硕上学位论文结构优先的修复技术 第三章结构优先的修复技术 在现实世界中，有各种各样的数码照片、手工画、胶卷、视频等等，它们有的 是纯纹理的图像，有的具有明显的结构，还有的是纹理和结构杂糅在一起。 结构和纹理是图像的两个重要特性，相对于结构，图像中纹理的梯度变化小对 比特征不明显，而结构更能明显地反应图像的的空间连贯性，比如，在修复结果中， 原本认定的强线性结构可能没有补起来，而是出现了一个大洞，或者是结构在某点 处出现断裂，它的两边出现了分层等等。这些结果中存在的瑕疵对用户来说很容易 就能识别出来，所以我们特别关注图像的结构，给予结构先被修复的优先权，并且 保证它们最终能被自然地连接起来而不出现赝像。本章介绍基于梯度的优先级计算 方法和最佳匹配块的搜索策略。在此基础上，给出一种新的结构优先的修复技术。 3 1 基于梯度的填充顺序 图像的内容特征，如颜色直方图、梯度、纹理、形状和对象组成等等，是图像 内在的本质特征，因而常被用来确定目标区域中块的填充顺序。 梯度值就是图像灰度值的显著变化的地方。这个数据可以用米体现图像中像素 的变化，变化越大就越有可能是结构，我们便优先修复这个地方，这样不仅能很好 的修复目标区域，还能将断开的线条连接起来，符合了视觉心理的连通性原则。 图像中有的点位于强线性结构上，有的结构特性比较弱，而且随着修复的进行， 目标区域内有些点还会成为线性结构上的点。所以，我们需要规定一个标准来区分 这些处于不同位置上的点，本文使用公式3 1 规定这些点被修复的优先级。计算方 法是：给定一个以p 为中心的块v - p , v p e 扣, 它的优先级尸( 功由足0 ) 和g ( 功的乘积 计算得到： p ( p ) = r ( p ) g ( p ) ( 3 1 ) 尺( 功是置信度项，g 是数据项，它们的定义如下： 脚，= 产川加挈g x 2 + g y 2 2 ， 其中，q 是以p 为中心的块上的任意一点，c ( g ) 是其置信度。所有源区域的点的 置信度都被初始化为i ，而将目标区域内所有点的置信度初始化为0 。可以把p 点的 华东师范大学硕上学位论文 结构优先的修复技术 置信度看作是它周围的有效信息的总和，这样做是为了首先填充那些包含更多已填 像素的块。块内包含源区域内的像素个数越多，其优先级越高，这将自动包含边界 线上某些区域，例如，目标区域中包含拐角的块就包含了更多源区域中的像素，它 们提供了更多可靠的匹配信息，所以将被优先填充。相反，那些包含源区域的像素 较少的块将被搁置，直到填入更多的像素时才会被考虑填充。另外，i 场i 是场的面 积，也就是块内所有像素点的个数。 数据项g p ) 中的g 譬( 力，g y ( p ) 表示p 点的梯度，q 妇) 和g y p ) 分别是x 和y 方向 的分量，用向前差分的办法计算得到。 吣加两1 非吾五m m ) i ( 3 3 ) 其中，点g 是物上不在目标区域内的点，并且点g 的置信度不为0 ，为g 点 沿x 轴正向的下一个点，该点的置信度也不为0 。( p i x ) 表示点p i x 的颜色信息。 g ，( 加高。；吾五脚叫g ) | ( 3 4 ) 其中，点刀为g 点在y 轴正向的下一个点，并且该点的置信度不为0 。a 的大 小等于i 场i 。 g ( 功项中的雅是一个归一化因数，也是一个反映每次修复过程中边界线8 o _ l z 等强度线强度的函数，本文诹值为2 5 5 。这个数据提高了那些等强度线向内的块的 优先级，优先修复线性结构。 在置信度和数据项之问有一个平衡点，数据项趋向于迅速将等强度线向内推进， 而置信度项则刚好压制这种向目标区域内的侵入，在计算边界线上所有块的优先级 尸时很好的把握了这个平衡。 图3 1 是一副真实的数码照片，原来的图中站立着一个人，他的身体遮挡了湖 边的栏杆和一小部分水面，为了恢复这个地方原来的面貌，我们从原始图像中选中 人物并将他剔除。图b ，c 是用我们的算法修复该图像的过程，很明显，在图b 中， 栏杆部分先被修复，目标区域正逐渐地往里收缩。如图c ，结构部分都修复完毕只剩 下纯纹理部分。处理结果如图d 所示，可以看出，栏杆部分很自然的衔接起来了， 背景中的草滩、湖面、天空等等也都恢复了原貌。 华东女口范大学硕学位论文结构优先的修复技术 cd 囝3l ，( 艚自然照片中的 物选中。( hc ) 晦复过程。( d ) 修复结果。 由于目标区域的填补顺序完全是由表示图像性质的函数，即优先级函数，规 定的，它使得修复算法是一个有机的合成过程，从而不会有破坏结构的隐患，同时 该修复过程没有复杂的块切割过程或者是模糊诱导的融合步骤，简化了人工找块的 过程。 3 2 最佳匹配块的搜索方法 基于块匹配的图像修复方法主要有两个步骤，第一步是在源区域中寻找与待修 复区域中正在被执行的区域最匹配的块。第二步是修复，即将最佳匹配块和当前被 执行块相对应的有效信息复制到待修复区域中。接卜来我们将讨论实掩这两个步骤 的具体细则。 黧。裂崩一。一躺 毕求师范太学硕学位论文 结构优先的恬丝技术 3 2 1 选择搜索区域 在输入图像中除了用户选择的目标区域之外的任何区域都是源区域，我们可 以将它看成是许多个连续的待匹配块，模板块将与这些块逐个进行匹配，最终确定 那个最相似的块为虽佳匹配块。虽然我们可以在整个源区域巾搜索最佳匹配块，而 且这样傲不会丢失某些地方的信息，得到的结果很准确，但这样会做许多无用功， 占用了大量内存，消耗很多时间。 在实验中，我们发现源区域中有些地方和目标区域周围信息相差很多，在空间 上不可能具有根好的连贯性，因此可以略去在这些区域的搜索。如图3 2 所示，原 始图像中有一个人出现在广阔的麦田里，我们想要从图像中移除这个人所以选择 她为目标区域。为了能够填充人物移除后留下的洞，首先需要寻找一个最佳匹配块。 图c 是在整个源区域中搜索最佳匹配块得到的结果。然而根据观察，和目标区域相 似且具有空间连贯性的块应该在目标区域附近就能找到，如图d ，修复结果是在目 标区域的邻域中搜索最佳匹配块而得到的。两个处理结果都很好地完成了填充工作， 但是邻域搜索只需要较少的计算量，在很大程度上提高了修复效率。 藜释 嚣国 c d 图3 2 ，( a ) 输 图像。( 砷选择源图像中的人为目标区域。( 0 在整个谭区域中搜索最佳匹配 块的修复结果。( 由在目标区域的领域中搜索最佳匹配块的修复结果。 根据以 分析，和在整个源区域中拽索最佳匹配块相比较，邻域搜索的疗法的 确加快了算法的修复速度，但邻域搜索方法并不能应用到所有的破损图像修复中。 例如图3 3 是副典型的既有结构又有纹理的图像，图a 是原始图像。如图b 所示， 毕糸师范大学碗i 学位皓文结构优先l i 勺修技术 假定图中某块地方被破损了，我们要把损坏的网片修复成原来的样子，选择破损区 域并标记为绿色区。图c 是在目标区域的领域中搜索最佳匹配块得到的结果，很明 显，修复的结果并不理想，有一条曲线出现了断裂。实际上，目标区域应该和图中 的某一块区域最相似，比如说图像左下角和目标区域周围的纹理、结构都比较接近， 于是我们尝试在该区域中搜索最佳匹配块，结果如图d 所示，目标区域的结构和纹 理都得到了理想的结果。 cd 图3 3 ，( a 精 图像。伯) 选择目标区域。( 0 在邻域中搜索最佳匹配块的修复结果曲线部 分出现了断裂。( m 在局部区域中搜索晟佳匹配块的修复结果。 上面两种情况都足在源区域的某个相似区域中搜索最佳匹配块的，于是我们提 出了人上干预的局部搜索方法。源区域中和目标区域巾最相似的区域对于人来说根 容易区分m 来但对计算机来蜕就得通过仔细计算才能得到，所