基于PDE与纹理合成的马赛克修复研究——毕业论文

浙江传媒学院本科毕业设计 基于PDE与纹理合成的马赛克修复研究毕业设计(论文) 论文题目 基于PDE与纹理合成的 马赛克修复研究Research of Mosaic InpaintingBased on PDE and Texture Synthesis 基于PDE与纹理合成的马赛克修复研究摘要:随着视频技术的飞速发展与数码电子产品的日益普及，高质量图像及其序列的采集与处理已成为一个非常活跃的研究领域。而去马赛克是其中一项必不可少的关键性技术。视频修复是图像修复的推广，图像修复的目的是根据图像现有的信息来自动恢复丢失的信息。图像修复问题主要关心图像中与视觉效果密切相关的结构和纹理两类信息。对应于这两类信息，基于偏微分方程的修复方法和基于纹理合成的方法各自取得了一定的发展。然而这两种方法存在各自的优缺点，且具有一定的互补性，为了获得更好的修复效果，考虑将二者结合起来综合分析。BSCB算法采取的是全局式搜索方式，搜索匹配块的过程比较费时，本文研究的是马赛克缺陷视频的修复，视频序列数据的庞大使得修复计算的高效性变得愈发困难。因而，本文的主要工作是在BSCB模型算法的基础上做出了相应的改进。最后，论文对所提出的算法进行了大量的实验仿真，实验结果证明了算法的有效性。关键词：图像修复；去马赛克；偏微分方程；纹理合成RESEARCH OF MOSAIC INPAINTING BASED ON PDE AND TEXTURE SYNTHESISAbstract: With the rapid development of video technology and the popularization of digital products, the collection and disposal of image and its sequence which is of high quality, become as an active field，in which demosaic is a necessary key technique.Video inpainting is an extension of image inpainting. The objective of image inpainting is to restore the lost information according to around image information, Image inpainting mainly concerns with structural and textural information, which is closely connected with the visual effect of the imageCorresponded with the two sorts of information, the inpainting methods based on PDE and on texture synthesis developed to a certain extent respectivelyHowever, there are both relative merits and complementarity in these two methods. Therefore, these two methods are considered to be put together in order to achieve better repairing result.BSCB algorithm is based on globally searching the source patch, which leads to a time consuming process of searching matching patches. Whats more, this paper mostly concentrates on the restoring of mosaic video, the enormous image sequences make efficiently inpainting much more difficult. Hence, my work is to put forward improved algorithm based on previous research of BSCB algorithm to improve the performance of the image restored.At last, based on the theoretical analysis, lots of numeric experiments are performed, and the experimental results verify the improvements of the proposed algorithm.Key words：image inpainting; demosaic; partial differential equation; texture synthesis目 录1 绪论11.1 研究背景11.2 国内外现状11.3 研究的目的与意义22传统手工修复和数字图像修复的对比32.1 手工修复32.2 数字图像修复43马赛克缺陷视频修复的概要研究53.1 马赛克缺陷视频产生原因63.2 马赛克故障图像特点总结63.3 马赛克缺陷视频帧修复原理63.4 马赛克缺陷视频修复设计思路84 马赛克缺陷视频修复的详细设计84.1马赛克修复算法原理及其步骤84.1.1 BSCB模型94.1.2 算法的改进104.1.3 本文算法流程134.2 算法的核心部分144.2.1 优先权的设定144.2.2 最佳匹配块的选择144.2.3 纹理合成过程164.3 马赛克缺陷视频修复处理流程175 马赛克缺陷视频修复的实验与测试185.1 马赛克缺陷视频修复的实现185.1.1 实现平台185.1.2 运行环境185.1.3 视频序列的获取和合成195.2 马赛克修复测试195.3 马赛克缺陷帧的修复195.4 算法比较205.4.1 修复效果比较205.4.1 用时比较216 总结和展望216.1 总结216.2 展望22致 谢24参考文献251 绪论1.1 研究背景 随着视频技术的飞速发展与数码电子产品的日益普及，高质量图像及其序列的采集与处理已成为一个非常活跃的研究领域，通过利用图像分割、图像识别、图像修复等技术来对视频帧信息进行处理使其成为高质量的视频已成为热门应用领域之一。人类自身生存和活动在一个多维的宇宙空间当中，人类认识世界最为直接的方式就是通过视觉获得图像，视觉为我们提供了60的信息来源1，“百闻不如一见”、“一图值千字”，可以毫不夸张的说，21世纪是信息获取处理及其应用世纪，更是视频图像处理和应用的世纪。以往视频资料的存储介质一般为胶片、光盘、磁带等，而胶片上化学物质随着时间在空气中的退化反应以及以前胶片保存技术的落后，很多影片无法良好地保存，或者损坏或者丢失或者老化。根据美国国会图书馆的一个调查，美国80的无声电影已经无法修复；另一个报告指出：90的1930年以前拍摄的无声电影和50的1950年以前拍摄的无声电影已经完全损坏。国内这方面的统计不得而知，但是我国电影胶片的保存手段和意识相比国外更加落后2。因此可以推断，我国有很多的旧电影存在严重的质量损伤情况。而电视台最重要的媒体实体就是历年保持的视音频节目和素材资料，这些资产具有很高的价值，甚至超过设备等固定的有形资产。因而如何修复这些电影资料并对其进行数字化存储已经成为迫在眉睫的任务3。同时，由于以前的电影制作设备本身的一些欠缺以及电影胶片在拷贝、播放和存放过程中不可避免地受到一些损伤，现保存下来的影片出现了诸如马赛克、抓痕、闪屏、花屏、静帧等问题，视觉效果上大打折扣。如不及时对这些影片进行翻新修复工作，这些保存下来的影片也将不复存在。因此，将这些保存下来的影片及时进行翻新修复是一项很紧急的任务。而Demosaic(去马赛克)则是其中一项必不可少的关键性技术。1.2 国内外现状图像修复有着悠久的历史，最早可以追溯到欧洲文艺复兴时期，为了恢复遭受破坏的美术作品，艺术家们利用人的感知力和想象力对作品的裂痕等受损区域进行修补,使其恢复和保持图像的完整性。近年来，研究者将艺术品修复的概念引入数字图像和视频的处理过程，提出了数字图像视频修复的概念4。数字图像修复inpainting一词最初是由Bertalmio引入到图像修复领域的，自从Bertalmio最早期的工作以后，数字图像修复技术就得到了广泛的应用。近些年，国内外发表的图像修复方面的论文提出了很多卓有成效的修复模型和方法。其中具有代表性的一类是用于小尺度缺损目标修复的图像修复技术，其核心思想是一种基于偏微分方程(PDE)的算法，另一类是基于纹理合成的模型和方法。基于偏微分方程的修复模型就是将图像修复过程转化为一系列的偏微分方程或能量泛函模型，从而通过数值迭代和智能优化的方法来处理图像。该类算法对裂缝、污点、划痕、文字覆盖等小尺度破损区域的修复取得了良好的效果。然而，对于大尺度的破损待修复区域，修复结果则会产生明显的模糊现象。对于待修复区域及其周围的纹理相当丰富时,也得不到很好的效果。基于纹理合成的图像修复在可用候选区域寻找“相似的”区域，拷贝至对应待修复区域，重建图像细节信息，但是受限于线形结构，当不同的特征区域相遇时通常不连续。图像修复问题主要关心图像中与视觉效果密切相关的结构和纹理两类信息。如果说图像的结构相当于图像的骨骼，那么图像的纹理就相当于图像的血肉，图像的完整性除了骨骼的完整还必须包含血肉的完整。对应于这两类信息，基于偏微分方程的修复方法和基于纹理合成的方法各自取得了一定的发展。具体地讲，基于偏微分方程的方法由于不适用于刻画纹理信息无法修复纹理，而基于纹理合成的修复方法在结构信息方面具有弱势，容易造成人工边界。两种方法存在各自的优缺点，且具有一定的互补性，为了获得更好的修复效果，考虑将二者结合起来综合分析。这样的修复结果比单纯采用结构修复方法或纹理修复方法效果要好，这也是当今国内外数字图像修复技术的发展趋势5。如图1.1所示。图像修复非纹理图像修复纹理图像修复偏微分方程模型纹理合成修复模型面向过程的微观仿真修复面向对象的宏观变分模型特征匹配结合PDE和纹理合成修复模型图1.1 数字图像修复技术发展方向1.3 研究的目的与意义为了恢复视频信息的“合理”和“完整”性以便观察者识别和理解，需要对这些受损的视频帧进行填充修复。对视频帧的图像修复就是对图像上信息缺损区域进行信息填充的过程，其目的就是为了对有信息缺损的图像进行恢复,并且要使观察者无法察觉到图像曾经缺损或已被修复。本课题根据视频帧中马赛克出现的位置，采用图像处理和修复算法对已损坏的帧进行修复。当对视频中每一帧的缺陷都进行修复后，修复后的旧电影播放的视觉效果就如同电影初次播放时的视觉效果。虽然目前有一些功能强大的图像处理软件，例如Photoshop，也可以对残缺的数字图像进行修补，但是需要有经验的专业技术人员进行复杂的手工处理，无法达到计算机自动处理的目的，而且处理效率低下，需要较长时间才能完成一幅图像的处理。另外对于视频图像修补这样的大数据量操作，人工处理更是不现实。因此，现在图像修补技术的研究旨在寻找更智能化、修复效果更好的算法，只需要用户简单地选择需要修复的区域，计算机就那根据图像的特征信息自动地完成修补图像的工作，显著减少处理时间，提高工作效率，完成一些人力难于完成的任务。综上可见，研究自动图像修复技术具有十分重要的实践和理论意义。该技术的研究不仅可以直接作用于人们的日常生活和工作，提高视频修复的工作效率，还可以推动智能图像处理技术的发展，使数字图像处理技术得到更广泛的应用。论文在论述安排上主要分为以下几个部分：第一章 简要介绍缺陷视频修复的研究背景和国内外现状以及本课题的主要研究目的和意义。第二章 简要介绍传统手工修复和数字图像修复的原理，并进行了概要的比较和总结。第三章 概要介绍马赛克缺陷视频修复的概要研究，包括马赛克图像特征表现，马赛克缺陷视频产生原因，马赛克缺陷视频帧修复原理以及马赛克缺陷视频的总体设计思路。第四章 详细介绍马赛克缺陷视频修复的设计方法，包括视频修复算法的原理、处理流程以及每一步的实现方法。第五章 进行实验测试，分析数据。第六章 总结全文，指出自己所做工作以及设计和论文需要进一步改进的地方。2传统手工修复和数字图像修复的对比2.1 手工修复视觉心理学的分析得出的结论表明，人类视觉在认知图像的受损区域时，会对图像受损区域有自动填充的功能，且随着区域的增大而减弱。同时，人类视觉感知的修复过程还具有如下三个特点6：(1) 亮度填充要比纹理填充迅速；(2) 填充取决于邻域复杂性以及密度，越规则越易受辨识；(3) 填充结果尽量与邻域保持一致。修补技术是一项古老的艺术，开始出现是在欧洲文艺复兴时期。当时，人们为了恢复美术作品中丢失或被损坏的部分并同时保持作品的整体效果，对中世纪的美术品进行修复，这些工作被称为“retouching（润饰）”或者“inpainting（修补）”7。技术经验丰富的艺术馆人员在修复艺术品时，首先判断原图的主体线条走向，连接待修复区域内的主要线条，然后在此基础上填充相应的背景色，完成结构信息的恢复，最后在根据邻域信息添加必要的细节，也就是纹理，使得修复结果显得自然协调更符合原图的风貌，得到最终的修复结果，可见，手工修复的过程符合上述人类视觉感知的过程。2.2 数字图像修复相比古代的人工修复技术，采用计算机进行数字图像修复具有一些优点：（1）采用计算机处理，自动完成修复过程，大大减少了人工修复的劳动强度，为图像修复提供了更加方便快捷的途径；（2）避免了原件被损坏的风险。由于数字图像的可复制性及处理流程的可逆转性特点，不会损坏原来的图像； （3）可以反复实验，直到满意为止。数字图像修复技术可以在不改变原图像的基础上尝试不同的修复方法。在经典的近似原理中，平滑修复允许我们严格的研究修复的精确性。在许多应用中，这些模型并不实际，因为：（1）许多图像包括了边缘及纹理等非光滑的成分，这就决定了图像的函数模型应该是非平滑的。（2）图像中常常含有噪音。显然在手工修复过程中，人类的认知能够很轻松地解决上述的问题，因此在建模的过程中，期望能够模仿手工修复的机制，建立更加可靠的低层的修复模型。因此，这些特性使建模还原为Helmholtz最佳猜测原理。在被马赛克覆盖的区域中，物体连通的方式只能基于我们所能看到的部分进行猜测。类似的，修复古画时，修复者只能根据已存在的特征从而对丢失部分做出最佳猜测来填充色彩和物体。文献总结了基于视觉感知的图像修复规律8：（1）图像修复模型是局部性的。因为我们建立的模型不需要知道图像的全局信息，待修复区域的信息完全由待修复区域周围的已知信息决定。然而，当待修复区域是一张人的肖像画，缺损区域为人的两只耳朵，这时我们只有根据先验知识进行修复，而不能根据一般的理论进行修复。根据理论修复的结果肯定是没有耳朵。（2）图像修复模型应该能够修复窄的被截断的光滑的边缘。人眼对灰度值的变化相对来说不是十分敏感，而对于边缘却非常敏感。所以边缘对于图像配准和图像切割都很重要。模型必须能把断裂的边缘光滑地连上。（3）图像修复模型应该对噪声具有鲁棒性。如果噪声低于某一门限，眼睛应能从含噪声图像中提取有用的信息，根据相似性原理，使用其领域的信息进行推断，并能把有用的信息扩散到待修复区域。这也就是认知规律中的相似性和简洁原理。（4）结构优先性。结构线条在视觉感知过程中的起着重要作用，它代表着图像整体上的趋势和走向，所以，修复时首先修复结构信息以保证图像整体一致性是很自然的基本原则。则如果先进行纹理填充，则有可能会出现虽然细节相似，但边缘连续性不好，从而使图像整体有一定偏差。（5）纹理一致性。纹理其实并不被大脑所重视，如果不仔细观察，则只是被看成是相似的物体，而不会主动分辨其中的细节。因此，对于纹理修复，只要没有出现不同于当前纹理的新信息，大脑就不容易察觉。因而可以得出，图像修复问题首先是结构信息的修复，在结构信息达到较好修复效果的基础上，再尽可能地保持纹理的相似性。这同时解释了为什么图像补全问题，即大规模的图像破损填充问题，要采用结构和纹理分步或分开处理的手段才能取得更好的视觉效果。然而，由于实际处理的图像复杂程度高，类型广泛，目前为止，还没有一种可以充分满足上述所有规律并对任何破损都具有较好的修复效果的“包治百病”的算法模型。3马赛克缺陷视频修复的概要研究 视频修复（Video inpainting）是图像修复在时间上的严拓，与图像修复有着密切的相关性。在视频领域的定义中，帧是影像动画中最小单位的单幅画面。我们可以将一段视频看作是一组图像的组合。在不同的应用中帧频是不同的，如PAL制式电视系统中帧频是每秒25帧，NTSC制式电视系统中每秒是30帧，对于电影而言帧频为每秒24帧。视频解压缩后，视频中帧的排列就是原始视频序列中一幅幅图片的组合，此时我们可以将它们看作是一张张图片，对视频的处理就转化成对图像的处理。因而，视频修复是图像修复的推广。从数学角度来看，图像修复即要根据待修复区域周围的信息将图像已知区域的信息填充到待修复区域中，并保证修复后整个画面色调和纹理的连续性和一致性。同样的，视频可以看作一系列图像帧沿时间轴的演化，因而，可以将视频看成是三维空间的一个视频体。二维图像的修复模型可以推广到视频的修复模型。如果采用像素扩展的方法将一幅正常的点阵视频帧图像不断地放大几次，图像的某些地方就会出现许多不连续的细小图像色块，这些图像色块的出现，在计算机图形和图像处理中称为图像的马赛克现象。马赛克的特征就是块状出现，同一画面中大小相差不大，块内部色彩相对均匀，而块相互之间色彩会有突变。视频马赛克现象的出现会直接影响对于视频内容的理解和分析。马赛克现象一般出现在如下几种情况：1、磁带因断磁或老化等原因，上载到硬盘中的磁带内容会出现马赛克等现象；2、播放质量较差的视频，如果播放画面过大，同样有马赛克现象出现；3、有时由于节目需要，比如要隐藏人物的有关信息，也会在特定部位人为地添加马赛克。3.1 马赛克缺陷视频产生原因 MPEG对视频数据规定了层次结构，共分为六层。最高层是视频序列（VS），其次是图像组（GOP）、图像（Picture）、像条（Slice）、宏块（MB），最低层是像块（Block）。除宏块和像块层之外，其他4层数据都具有特定的起始码，这些起始码对解码的同步起着重要的作用，也就是说，一旦传输误码或其他原因导致收发失步，通过重新寻找起始码，可以实现重新同步。宏块和像块没有同步头，所以宏块条是MPEG视频图像中的最小的同步单位。MPEG采用的这种分层结构使得当码流出现错误时，其影响被限制在了相应的级别中。宏块条内的错误，被限制在条内，也即最多影响到一个宏块条。MPEG-2是基于块的压缩编码方法，因此被损坏的图像的畸变区域总是块或条。马赛克现象是由于数字电视传输码流中误码率升高和数据包丢失而造成的，是传输码流中“块”或“宏块”图像信息丢失在屏幕上的外部表现，表示数字视频信号在网络中传输时已出现某种质量问题。宏块条内的错误就是因为各种原因造成的码流的误码或数据的丢失，误码或数据的丢失对视频图像的影响可能从三个方面产生9：（1）通过预测编码方式将错误传播给依赖于错误块进行解码的图像。（2）误码影响解码器的解码进程，导致解码停止。（3）误码导致解码出的数据错误，致使显示图像不正确。 3.2 马赛克故障图像特点总结依据3.1节马赛克故障图像产生的原因及其过程可见马赛克图像的特点如下：（1）由误码直接影响的畸变区域、误码导致解码器解码停止的畸变区域以及由DC系数的差分脉冲调制编码导致的畸变区域的位置在宏块条行上，也就是16行的整数倍区域内。且畸变区域在同一水平行内，从被腐蚀的宏块或块起，至被腐蚀的宏块条结束止。畸变区域为规则的条或块状。（2）畸变区域内部可能是黑色(如解码器停止造成的)或是与周围区域的连续性被破坏的带畸变的画面(如DC系数偏大或偏小，运动向量错误)。（3）由于误码位置的不同，会造成畸变区域的起始形状的区别。（4）由于帧间预测造成的畸变区域的扩散，随着预测的不断推进，畸变区域也进行扩散，但是畸变区域的条或块状特征会越来越不明显。（5）在数字电视的马赛克检测中，其目的是发现演播等故障，其产生的误码均为突发性误码，其误码的数量往往较大，所以一般情况下其产生的畸变区域也具有较大的范围。3.3 马赛克缺陷视频帧修复原理视频帧修复，就是利用使获得的图像产生退化的先验知识，建立退化图像数学模型，然后沿着图像退化的逆过程加以重建和复原，以获得“清晰和干净”的图像。图像修复的一般模型是：函数表示原始图像，这是未知的，是我们想找到的。其中表示图像域。用函数表示描述与相同场景的观测图像，它是退化的，已知的，我们称其为数据，是加性噪声。一般假设其服从正态分布： (3.1)其中是影响图像失真的因子，表示原始图像，是己知的图像。图像修复问题就是从已知图像得到恢复图像10。数字图像修复技术是从人的视觉心理角度出发，根据被遮物体的边缘信息，按照一定的方向进行延伸扩展、边界连接，填充被遮蔽的部分，达到视觉上的连通，模拟出人工修复的效果。由于因为大多数物体都是不透明的，一般情况人们靠经验来猜测被遮挡了的物体。同时，世界通常也被认为是由一种有序的、完整的方式组成，而不是乱糟糟的、独立分散的个体。因此，图像修复的建模过程一般依赖Helmholtz最佳猜测原理。Helmholtz基本原理指出11：在给定传感数据的情况下，我们所感觉到的一切是基于现实世界的状态而做出的最佳猜测。另外，一个实用的图像修复模型应该能够从含有噪声的图像中提取出干净的图像，并且从剩余的图像信息中猜测出最佳的丢失信息，因而依据最佳猜测原理建立的图像修复模型是自然的。最佳猜测原理是用统计的方法研究问题，它和贝叶斯理论对现实世界的分析类似。在决定性方法论中，最佳猜测原理通过最优化能量泛函实现12。因此它的困难点在于提出感觉上有意义的能量泛函。图像恢复就是利用受到污染的图像恢复干净的图像,根据最佳猜测原理，就是求Bayesian最大后验概率，即求使最大的，根据贝叶斯公式可以将问题转化13。由贝叶斯公式：，是个常数 (3.2)且若图像给定，则是固定的常数，可以得到：，是个常数 (3.3)从上式我们看到，的估计依赖于两点，即观测到的图像与的联系和基于最佳猜测而建立的图像先验概率。具体说来，基于贝叶斯框架的图像恢复模型分两部分：l、先验模型：真实的图像应该满足什么样的性质。2、数据模型：观测到的图像是怎样从理想图像获得的，即观测图像和理想图像的联系。3.4 马赛克缺陷视频修复设计思路图像修复算法有如下步骤：（1）人工选定需要修复的区域，并通过在受损区域涂上颜色等方式以便算法识别；（2）由待修复区域外边界向区域内部不断扩散纹理信息，亦即用待修复区域边界外面的已知图像信息来填充未知区域内空白块的像素点。通过了解视频基本结构，提取含有马赛克缺陷的视频帧，以手动的方式借助相应视频处理技术及媒体编辑软件对视频的马赛克缺陷区域进行定位，再根据当前帧受损区域与其外边界的区域自相似性来完成马赛克消除后的空白块。用像素亮度梯度表示亮度变化方向，二次微分表示像素变化的速率，通过解基于马赛克附近区域像素的偏微分方程，获取修复最大适应概率，再通过纹理合成技术填补马赛克消除后所残留的空白块。为了提高处理速度和修复质量，可以通过降维并迭代求精等方式来优化处理空间，从而减少解搜索范围。在对每一马赛克缺陷视频帧完成修复后，再合成为视频序列，从而实现对视频马赛克缺陷的修复。总体设计流程如图3.1所示。建立二值矩阵标识视频帧待修复区域与保留区域通过Laplace锐化算子对边缘平滑处理并计算待修复区域的边缘梯度和等照度值对待修复区域进行窗口块分割，并计算每个窗口块的置信度根据窗口块置信度次序，逐窗口块修复。每个窗口块的修复通过视频帧游走的方式检查，选取方差最小的匹配块，直至完成待修复区域的修复图3.1 总体设计流程图4 马赛克缺陷视频修复的详细设计4.1马赛克修复算法原理及其步骤本文马赛克缺陷修复算法依据BSCB(BertalmioSapiroCasellesBallester)的算法模型，主要针对视频序列数据庞大以致修复耗时的问题对算法做出了相应的改进从而实现对马赛克缺陷视频的修复。4.1.1 BSCB模型在详细介绍这项技术之前，先来分析下这方面专家是如何去修复的。对于这种工作，明尼阿波利斯文学艺术学院的讨论使我们更清晰图像修复不同于艺术和专业工作，它是一种非常主观的过程。这里不存在解决问题的特定方式，而是遵循以下基本的方法论14：（1）保持修复后图像的完整性，图像的整体性决定了如何修复破损区域，而修复的目的就是要恢复图像的完整性。（2）修复区域周围区域的结构必须延伸到修复区域中，通过对到达修复区域边界的延长画出轮廓。（3）修复后区域中不同的区域是由等照度线来划分的，各区域的颜色要和边缘外部的颜色保持一致。（4）细节部分即纹理必须添加。从这些被专业人员应用的基本图像修补规则中可以很快学到很多知识经验。BSCB算法同时并且反复地执行了上述的准则（2）和（3），通过延伸边界区域的等照度线进入待修复区域以实现图像修复。BSCB模型是各向异性扩散，使得等照度线延长时保持了它与边界的交角，因此修复效果更接近人的视觉感受。所谓等照度线就是灰度值在同一等级上的一系列点所组成的线，直观来讲，就是被照面上相同亮度的点组成的曲线。图像中两种最基本的要素即像素点的灰度和梯度（或边缘）信息。各像点的灰度是构成一幅图像的基础，而梯度则是构成图像边缘轮廓的要素，图像最重要的结构特征是边缘，所谓边缘是指其周围像素灰度有阶跃变化或屋顶变化的那些像素的集合，它存在于目标与背景、目标与目标、区域与区域、基元与基元之间。因此，它是图像分割所依赖的最重要的特征，也是纹理特征的重要信息源和形状特征的基础。在一幅具有丰富自然纹理结构的背景包围着一位蹦极者的图像中，如4.1(a)所示。背景和人物内部各像点分别具有各自不同的灰度值，而这些像点的梯度值为零，在背景和人物之间的边界区域内的像点，其梯度值不为零，如图4.1(b)所示。一般像素的梯度方向，是像素值在空域上变化最大的方向，而其垂直方向即为等照度线的方向。在BSCB算法模型中，图像的修复信息沿等照度线的方向进行扩散。像素的梯度值和梯度方向很好地反映了图像中微小的细节反差和纹理特征变化，4.1(c)可以清晰地看到放大后的部分边界区域的梯度方向，该图给出了各像点与其领域像点的空间关系，对图像的纹理能很好地描绘，对于具有方向性的纹理亦可从梯度的方向上反映出来。 (a) 原图 (b) 待修复区域边界 (c) 部分区域边界的的全图梯度方向 梯度方向 图4.1 边界的梯度(a)为蹦极者原图， (b)为全图修复区域边界的梯度方向，为了清晰的展示梯度方向情况，将(b)中用黑色方框标记区域的梯度在(c)中放大显示。BSCB算法的具体描述如下：表示要修复的区域，是它的边界。如图4.2所示。直观地说，BSCB模型是：延长达到的等照度线，并保留达到时的“角度”。从向内，继续依此进行，同时逐步地弯曲延长的线段，以防止它们相互交叉。在等照度线上所有的点均满足，到达边界上的点的等照度线与边界的夹角的方向就是与边界的方向，因此期望信息沿等照度线的方向传递。图4.2 传递的方向可以定义为和梯度垂直的方向4.1.2 算法的改进自然图像一般都具有多种纹理区域，修补目标块应与图像中某种纹理区域相似而与其它纹理区域差距较大，而基于BSCB模型的算法不对图像纹理信息进行区分，一视同仁地采用全搜索策略在全局范围内“盲目”搜索并进行修补，运算速度较慢，不仅有可能导致错误的匹配块的出现继而产生恶性繁衍而且会影响算法的整体性能。本文研究的是马赛克缺陷视频的修复，视频序列数据的庞大使得修复计算的高效性变得愈发困难。因而，本文从以下几个方面对算法进行了改进。（1）二阶导数二阶导数表示待修复边界梯度值的变化量，如果变化量较小时，说明该像素与领近像素的相关性较大，宏观统计来说，即待修复区域与领域差异性很小，所以采用待修复区域邻近的纹理信息进行替代填充，以缩小匹配块的游走范围，避免穷尽搜索，从而达到减少搜索范围的目的，提高了匹配搜索效率。匹配块的变化速度计算流程： 计算窗口块中各像素一阶导数，获得匹配块各像素的变化情况； 并根据各像素权重（距离边缘远近不同则权重不同）统计获得匹配块变化值； 对各匹配窗的变化值求导，获得各匹配块的变化速度；（2）置信度 置信度反映了待修复块中正确接收像素所占的百分比，比值越高表示该待修复块中已知像素越多。利用纹理的相关性原理，待修复块的置信度越高，说明它与附近区域的纹理相关性越强，因而可减少匹配窗的游走范围来提高匹配搜索效率。对匹配窗的游走处理流程如图4.3所示。对匹配窗变化较慢的区域缩小游走范围，同样，对匹配窗变化较快的区域增大游走范围对待修复的匹配窗计算其二阶导数，以获取修复处理过程中各窗口块的变化速度根据w1, w2计算待修复区域中每个匹配窗的游走范围设定匹配窗变化与匹配窗处理置信度对游走范围处理的权重，分别为w1,w2(w1+w2=1)。对置信度高的匹配窗减少游走范围，同样对置信度低的匹配窗增大游走范围对受损区域的每个匹配块计算其置信度图4.3 匹配窗游走处理流程（3）匹配窗大小的选择 匹配窗的尺寸决定了输出的纹理能否较好的保持输入纹理的局部纹理特征。如果尺寸过小，则接近于基于像素点的合成，对于纹理的局部统计特性描述较弱；反之，则容易产生视觉上的拼贴效应。对于不同类型的纹理块，匹配窗的尺寸也不同。对于光滑的、大尺度的纹理须采用较大复制块以充分捕捉纹理单元的特征；对于复杂的、小尺度的纹理则采用较小的复制块。因而，本文是通过对度量纹理块的特征包容性来考察所选的匹配窗的尺寸是否合适。纹理块的特征包容性是指复制块所包含的纹理特征与样本纹理所包含的纹理特征之间的差距。它们之间的差距越小，合成的纹理对样本的全局特征保持的就越好。本文采用归一化灰度直方图来度量纹理块的特征包容性，从而对匹配窗的大小进行选择，如图4.4所示。a(1)为样本纹理块，b(1)为9*9大小纹理块，c(1)为 16*16大小纹理块，d(1)为24*24大小纹理块，a(2)为a(1)的RGB分量直方图，b(2)为b(1)的RGB分量直方图，c(2)为c(1)的RGB分量直方图，d(2)为d(1)的RGB分量直方图。发现当纹理块大小为24*24时RGB分量直方图与纹理块最相似，并采用以上的度量值方法对样本纹理中可能尺寸计算其欧式距离，发现针对该图像采用匹配窗大小为24*24时对纹理的全局特征有比较好的反映。其算法的处理流程如图4.5所示。 a(1) 样本图 b(1) 9*9纹理块 c(1) 16*16纹理块 d(1) 24*24纹理块a(2) 样本纹理的RGB分量直方图 b(2) 纹理块大小为9*9 c(2) 纹理块大小为16*16 d(2) 纹理块大小为24*24RGB分量直方图 RGB分量直方图 RGB分量直方图图4.4 纹理块RGB分量直方图变换窗口块大小，如前一步骤重新计算最佳匹配度，并计算整体修复区域匹配误差对视频帧进行随机区域分割，并计算修复区域内中的块分别与保留区域中的块的最佳匹配度通过匹配误差选取窗口块大小4.5匹配窗大小选择处理流程4.1.3 本文算法流程 马赛克视频缺陷修复的算法步骤如图4.6所示。提取待修复视频帧标识视频帧中马赛克区域，并计算掩模分析视频帧并根据特征直方图计算窗口块大小设定窗口块匹配特征（纹理）计算整个视频帧的等照度线对掩模边缘区域进行Laplace锐化处理(实现修复后的边缘平滑)计算边缘平滑处理后待修复区域边缘梯度 沿着待修复区域边缘，根据窗口块中的等照度线、待修复区域边缘梯度和窗口块中保留像素比例通过求解PDE计算每个窗口块的置信度通过窗口块二阶导数计算各窗口块的变化速度 根据窗口块变化速度和置信度计算窗口块的游走范围 选取置信度最大的窗口块根据游走范围进行纹理匹配，并使用方差最小的匹配块进行修复传播等照度线和置信度整个待修复区域是否修复完毕将所有处理完成视频帧进行合成否是4.6 算法流程图4.2 算法的核心部分 4.2.1 优先权的设定修复的过程依赖于目标像素周围的确定源区域，像素的领域不同，其周围的可参考信息也是不同的，边缘像素的处理顺序在很大程度上影响着最终的修复效果，设计一个好的边界像素处理顺序可以提高图像的修复质量。一般应同时考虑图像的结构区域和纹理区域，实现二者的良好平衡，主要遵循以下三个原则：（1）边缘结构附近的待修复块具有较高的修复优先权；（2）置信度高（包含已知像素多）的匹配窗具有较高的优先权；（3）在同等情况下，原则（1）与原则（2）相比，应优先得到满足。其中原则（1）保证图像中的边缘结构具有较高的修复优先权，原则（2）保证匹配窗中包含已知像素多的块具有较高的修复权，包含已知像素越多，修复的准确性越高。原则（3）保证图像的结构区域具有最高的修复优先权，因为结构部分往往包含大量的图像边缘信息，对修复质量起决定作用。因而，优先权的计算直接决定了修复顺序，进而影响破损区域图像的修复效果。从上述三点原则可以知道，优先权的大小取决于两个因素：一个是匹配窗的边界梯度G，它表示匹配窗中所含结构信息的强弱，保证破损图像的结构区域优先得到修复；另一部分是匹配窗的置信度C，它表示匹配窗含已知像素的多少，保证优先修复含已知像素较多的匹配窗，匹配窗内的已知信息越多，修复的结果也越准确。边界梯度G和置信度C相互制约，共同构成优先权。修复块的优先权P采用式4.1计算15。P=G*C （4.1）在完成一个块的修复后，这个块的未知像素区域得到填充，原先的未知区域变为图像的已知区域，置信度值需要被更新，刚刚被填充的像素区域置信度置为1。处理过程中不断重建图像受损区域，产生新的边缘区域，更新权值和优先级，同时从中挑选对应时刻具有最大权值的匹配窗进行修补，直到图像修复完毕。总之，优先权P是图像的特征函数，反映了匹配窗的置信度和边界梯度（结构强弱）的综合特征。用它来决定图像的修复顺序，能使图像的修复全过程有组织地进行，符合视觉连通原理，避免了修复过程中出现的结构撕裂和模糊等现象16。4.2.2 最佳匹配块的选择 通过4.1.2节对算法做出的改进，即对匹配窗大小的选择以及确定了匹配窗的游走范围后，如何找到最佳的匹配块是很关键的，如果匹配规则选择的不合理，寻找到的块填充待修复区域后就不能得到很好的修复效果。对于输入的方形匹配窗（包括已知像素信息和待修复块，详见图4.2.2）和输出最佳匹配块中两个相同形状的领域或边界N1和N2 ，它们的相似性（或误差）可以用两者之间的欧氏距离来度量，即： (4.2)其中函数、分别表示纹理的红、绿、蓝三种颜色的特征分量。上述的匹配计算方法，是基于输入输出纹理之间的RGB颜色误差来度量的。匹配窗与匹配块之间的相似性度量依据待匹配窗中已知像素点与匹配块中相应像素的像素值距离来决定。在进行块匹配的过程中，一般需要搜索样图中所有领域或纹理块，然后计算其与输出纹理中待合成纹理块之间的相似误差。如果样图中纹理块的边界误差满足给定的阈值，则将其设定为候选纹理块，然后对所有候选纹理块与匹配窗纹理块的误差值进行比较，选取误差值最小的候选纹理块设定为匹配窗的最佳匹配块。如图4.7所示，通过比较可以看出，匹配窗(a1)的RGB直方图(a2)与最佳匹配块(b1)的RGB直方图(b2)的差异性最小，也即实现了最佳匹配。 (a1) 匹配窗 (a2) 匹配窗RGB直方图 (b1) 最佳匹配块 (b2) 最佳匹配块RGB直方图 (c1) 其余候选块 (c2) 其余候选块RGB直方图4.7 最佳匹配块的选择4.2.3 纹理合成过程设图像中有一任意形状的待填充区域，从受损区域边界开始向内部逐区域匹配填充。设定一定大小的方形匹配窗，大小应能基本覆盖纹理结构，比如9*9,16*16等，匹配窗内包括已知像素值和待修复的任意形状区域，然后在匹配窗的游走范围(详见4.1.2节)内寻找和匹配窗相似的窗口，根据设定的相似条件，寻找到最佳匹配窗，“拷贝”最佳匹配窗内的纹理信息至待修复块。这样从边缘的待修复块开始，逐步向内进行填充修复，最终填满整个受损区域。如图4.8所示。算法的处理流程如图4.9所示。待选匹配窗待修复块最佳匹配窗填充区域4.8 纹理合成过程通过优先权的计算确定优先匹配窗从初始像素开始扫描匹配窗，计算其与待选纹理块中像素点的欧氏距离比较相似度，将误差最小的最佳匹配块中的纹理信息拷贝至待修复块游走是否结束结束否是4.9 纹理合成算法流程图4.3 马赛克缺陷视频修复处理流程马赛克缺陷视频修复整体流程设计步骤如下：（1）提取需要修复的视频帧；（2）显示提取的视频帧、修复区域掩模（3）显示边缘梯度；（4）基于PDE和纹理合成方法对马赛克区域进行修复；（5）修复后图片保存及视频合成处理。 具体处理流程如图4.10所示。缺陷视频帧提取标识修复区域（若修复区域具有一致性则只需指定RGB）显示待修复视频帧及修复区域掩模对掩模区域进行Laplace锐化处理，并显示边缘梯度分割窗口块并计算窗口块置信度根据置信度和窗口块变化计算窗口块游走范围 将处理好的视频帧保存为图片，并加入合成视频中继续处理下一帧分析窗口块直方图并显示，以选取合适的窗口块大小图4.10 马赛克缺陷视频处理流程5 马赛克缺陷视频修复的实验与测试5.1 马赛克缺陷视频修复的实现5.1.1 实现平台本实验采用MATLAB7.9.0实现，MATLAB是由美国Math Works公司于1982年推出的一套高性能的数值计算和可视化软件，它集数值分析、矩阵运算、信号处理和图形显示于一体，拥有界面简洁、友好的用户环境。经过多年的逐步发展与不断完善，现已成为国际公认的最优秀和最可靠准确的科学计算与教学应用软件之一，是近些年来国内外广泛流行的一种可视化科学计算标准软件。MATLAB拥有强大的图形功能以及世界一流水平的数值计算函数库，它的数字图像是以矩阵形式表示的，这意味着MATLAB强大的矩阵运算能力用于图像处理非常有利，矩阵运算的语法对MATLAB中的数字图像同样适用。因此本次实验选MATLAB实现视马赛克视频缺陷的修复。5.1.2 运行环境（1）操作系统：Windows 7（2）CPU：Intel（R）Core (TM) Duo 1.66G（3）内存：1.80G（4）显卡：GeForce4MX44（5）硬盘：120G5.1.3 视频序列的获取和合成视频格式可以分为适合本地播放的本地影像视频和适合在网络中播放的网络流媒体影像视频两大类。常见的视频格式有：MPEG、AVI、MOV、ASF、WMV、n AVI、3GP、QuickTime、REAL VIDEO、MKV、DIVX、FLV等，而这众多的视频中有效的在Matlab中读入视频帧需要适当的视频编码方式，而并非所有的视频文件格式都满足。故视频格式的转换是对于视频帧在Matlab环境中能够被正常读入的必要环节。在Matlab函数库中，可以直接调用mmread()函数来实现对于马赛克缺陷视频帧的读取。在此，我们将获取并裁剪后的缺陷视频文件进行转换，使之成为恰当的mp4格式以便读取，从而实现将视频文件转换为图片序列，再将每帧转成jpg格式图片，以便接下来进行的数字图像修复以及修复后视频序列的合成。5.2 马赛克修复测试 本次实验通过图像处理软件将一幅图像的部分区域添加上马赛克来测试算法修复的可行性。如图5.1(a)所示，为添加了马赛克的图像，再用绿色填充此区域，如图5.1(b)所示。最后由程序对其进行修复，修复后的结果如图5.1(c)所示。 (a) 添加马赛克图片 (b) 待修复区域的标识 (c) 修复结果图5.1 区域添加马赛克进行的修复测试5.3 马赛克缺陷帧的修复 实验样本采用视频缺陷检测软件检测出的马赛克缺陷视频帧，如图5.2(a)所示。5.2(b)为对马赛克缺陷区域进行的标识，图5.2(c)为通过算法进行修复后的视频帧。由修复结果图可看出，算法较好