（信号与信息处理专业论文）基于图像检索的图像修复研究与平台实现.pdf

中文摘要 摘要：图像修复是指重建损坏的图像或去除图像中不需要的对象的过程。我们需 要采取最适当的方式修补其原始状态的图形，同时确保修补结果达到最佳的艺术 效果或者说视觉效果。目前有一些比较流行的修复方法，如基于偏微分方程的修 复理论或基于纹理合成的修复理论，它们分别在细节修复和规则纹理修复案例中 有良好的表现。但在受损区域过大或完全丢失了一个语义片段的情况下，那些传 统方法常常难以胜任。相比较从待修复图像自身获取信息进行修补，使用从其他 图像内容中引入新的信息来修复破损图像的修补方式可能更有帮助。随着图像检 索技术的不断提高，我们希望能够充分利用其带给我们的便利。通过基于内容的 图像检索结果技术，结合颜色与语义信息，检索得到与待修复图像最相似的补丁 图像，使用这个补丁图像中的有效信息融入待修复图像的破损区域，我们可以得 到一个更好的图像修复效果，并在此过程中实现更多的视觉效果特效。本论文对 该算法进行了详尽的研究实现，并在检索相似图像环节中针对性地实现一些改进， 最后在该算法的基础上搭建了一个易操作的图像修复平台。论文中展示的实验结 果表明该算法的高效率和良好质量。同时，由于程序计算的随机性，这一算法还 可以获得一系列意想不到的结果，显示出其具有创新性的潜力。 关键词：图像修复；大区域破损；图像检索；基于内容的图像检索；图切割；泊 松编辑；特效处理 分类号：t p 3 9 1 4 1 j e 立交适态堂亟堂僮迨塞 垦曼! 壁g ：i ： a bs t r a c t a b s t r a c t ：i m a g ei n p a i n t i n gr e f e r st ot h ep r o c e s so fr e c o n s t r u c t i n gt h ed a m a g e d i m a g eo r r e m o v a lo fu n w a n t e do b je c t si nt h ei m a g e w en e e dt ot a k et h em o s t a p p r o p r i a t ew a y o fi n p a i n t i n gt h ei m a g et oi t so r i g i n a ls t a t e ，w h i l ee n s u r i n gt h a tt h e r e s u l ta c h i e v e st h eb e s ta r t i s t i ce f f e c t t h e r ea r es o m em e t h o d sc o m m o n l yu s e d ，s u c ha s m e t h o db a s e do nt h et h e o r yo fp d eo rb a s e do nt e x t u r es y n t h e s i s t h e s em e t h o d s p e r f o r m e dw e l li nd e t a i lr e c o n s t r u c t i o na n dr e g u l a rt e x t u r es y n t h e s i sc a s e sr e s p e c t i v e l y b u ti nc a s e st h a tt h ed a m a g e dr e g i o ni st o ol a r g eo ras e m a n t i cf r a g m e n ti sc o m p l e t e l y m i s s e d ，t h o s eo l dm e t h o d sc a n n o td oag o o dj o b r a t h e rt h a ni n p a i n t i n gw i t h i nt h e o r i g i n a li m a g ed a t a ，aw a y o fi n p a i n t i n gu s i n gi m a g ec o n t e n tf r o mo t h e rp i c t u r e sw i l ld o h e l p a sl o n ga st h ei m p r o v e m e n to fr e s e a r c hi ni m a g er e t r i e v a l ，w eh o p et o t a k e a d v a n t a g eo ft h eg o o dr e s u l t sb yc o n t e n t - b a s e di m a g er e t r i e v a lw i t hp a r t i c u l a rc r i t e r i a s u c ha sc o l o r sa n ds e m a n t i c s w i t ht h ei m a g ep a t c h e sf r o mt h ei m a g er e t r i e v a lr e s u l t s a n da p p r o p r i a t ei m a g ef u s i o nt e c h n o l o g y ( g r a p hc u t sa n dp o i s s o nf u s i o ni nt h i sa r t i c l e ) ， w ec a nd oab e t t e ri n p a i n t i n ga n da c h i e v et h er e s u l tm o r ei nl i n ew i t ht h ev i s u a le f f e c t s t h i sd i s s e r t a t i o ne l a b o r a t e st h ea l g o r i t h mi nd e t a i la n dt h ei m p r o v e m e n ta i ma tt h e r e t r i e v a lf o ri m a g ep a t c h e si n c l u d i n gt h ea d d i t i o no fr e l e v a n c ef e e d b a c k ，a n df i n a l l y s h o w sa ni m a g er e t r i e v a lp l a t f o r mw ep r o d u c e db a s e do nt h i sa l g o r i t h mw h i c hi s d e s i g n e de a s yt oo p e r a t e as e r i e so fe x p e r i m e n tr e s u l t ss h o wt h eh i g he f f i c i e n c ya n d q u a l i t yo ft h ea l g o r i t h m a n dt h eu n e x p e c t e dr e s u l td u et ot h er a n d o mc o m p u t a t i o n s h o w si t sc r e a t i v ea c c o m p l i s h m e n tw h i c hm a k e st h i sa l g o r i t h ma b l et ob ea p p l i e dt ot h e i m a g es p e c i a le f f e c tp r o c e s s i n g k e y w o r d s ：i n p a i n t i n g ；l a r g er e g i o nd a m a g e di m a g e s ；i m a g er e t r i e v a l ；c b i r ； g r a p hc u t s ；p o i s s o ne d i t i n g ；s p e c i a le f f e c t s c i a s s n o ：t p 3 9 1 4 1 致谢 本论文的工作是在我的导师苗振江教授的悉心指导下完成的，苗振江教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。两年来苗振江老师悉 心指导我们完成了实验室的科研工作，对于我的科研工作和论文都提出了许多的 宝贵意见，在学习上和生活上都给予了我很大的关心和帮助，在此向苗振江老师 表示衷心的谢意。 在实验室工作及撰写论文期间，郭荣伟、于晏平同学对我论文中的图像修复、 检索及融合等研究工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人、朋友，他们的理解和支持使我能够在学校专心完成我的学 、l k 。 1 引言 图像是人类获取信息的一个重要来源，研究表明，在人类获得的信息中有近 七成来自于人眼获得的图像信息，而对于图像信息的描述通常可以使用信号处理 领域的技术。图像修复，指的是对图像上缺失信息的区域重新填充相关信息的过 程，其目的在于利用图像中现有的内容来自动填补缺失的信息，同时要使观察者 不易察觉到图像已被修复或曾经缺损。图像修复已经成为图像处理研究中一个重 要的研究方向【i j 。 ( a ) 受损的照片( b ) 修复后的照片 图1 1 数字图像修复示例 f i g u r e1 1a ne x a m p l eo fd i g i t a li n p a i n t i n g 现如今，人们生产生活的各个领域都可以看到数字图像修复技术的广泛应用， 比如医学图像修复，文物字画的修补，还有电影胶片上划痕、污迹的消除，去除 场景早多余的目标，旧照片折痕的修复等等，有时利用图像修复技术还可以得到 一些特殊的艺术效果。因此，对图像修复技术的深入研究意义非常重大。 1 1 研究背景与意义 图像修复技术在文物保护、影视特技制作、虚拟现实、多余物体剔除( 如删 除视频图像中部分文字、人物等) 等方面表现出了重大的应用价值，已成为当前 计算机图形学和计算机视觉中的一个研究热点。 图像修复技术并不仅是一项现代科学技术，它起源于欧洲文艺复兴时期，当 时为了将被损坏的中世纪美术作品修整恢复，使得艺术作品的美好得到重现，人 们着手从事一系列艺术作品破损修复的工作，比如修复图像划痕等。在当时的技 术条件下，人们基本上都是手工完成修复，结果的好坏完全取决于修复者的艺术 经验与技术的熟练程度，其难度与工作量都相当大，同时还要承担微小失误导致 珍贵艺术作品报废的巨大风险。因此从事艺术作品修复工作的通常是富有经验的 艺术馆藏人员。传统的图像修复技术主要用于修复艺术品，需要专业的艺术家了 解画家的绘画风格、运用画笔的技巧后重绘，过程十分繁琐与耗时。这一工作就 称之为“i n p a i n t i n g ”( 修复，润饰) 或称“r e t o u c h i n g ”。 可能引起数字图像上的局部信息缺损的因素有很多，比如：对存在划痕或 破损的照片等进行数字扫描后得到的图像；移除了某些特定的物体或文字从而 留下的空白区域的数字图像；因压缩、传输和解压缩过程出现问题而造成信息 丢失导致缺损的数字图像等。这时，我们就要对这些受损图像进行填补及修复， 以保证图像信息的完整。 目前有一些图像处理软件也可以进行图像修复操作，但是仍需要一定的人机 交互操作，步骤也比较繁杂，需要操作人员具有一定的经验，应用并不广泛。因 此人们迫切期望有一种修复技术，能够自动、快速、轻松地修复图像。近些年， 国内外发表了许多图像修复方面的论文，提出了很多效果很好的修复方法和算法， 力图借助计算机的力量做到高效、高质量的图像自动修复工作。 1 2 研究现状 目前比较流行的图像修复技术有两大类【2 】。一类是擅长小尺度缺损修复的图像 修复技术基于偏微分方程( 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 ，p d e ) 的修复算法，可以 称之为i n p a i n t i n g ，它最早是由b e r t a l m i o 、s a p i r o 、c a s e l l e s 和b e l l e s t e r 引入到图像 处理中。这一算法中，待修复区域的边缘信息得到充分利用，从粗略到精细地对 等照度线方向进行估计，并结合传播机制使有效信息在待修补的区域内得以扩散， 从而较好地完成修复。这一技术主要是利用热扩散方程来实现背景区域中的有效 信息想待修补区域进行传播。b s c b 模型是这一类技术的典型方法，它使用了三界 偏微分方程来模拟平滑传输的过程，另外还有利用偏微分方程模拟c d d 的 c h a n s h e n 模型等。另外还有一种是基于几何图像模型的变分修补技术，这一算法 则是模仿了人类手工修复图像的过程。该类算法认为能否完成修复图像的任务主 要依赖的因素有两个：其一，如何观察并读懂图片的现存部分，也就是用数学语 言所讲的如何建立图像的数据模型；其二，原始图片属于哪类图像，也就是数学 语言所讲的如何获得图像的先验模型。总而言之就是要建立图像的先验模型和数 据模型，借此转化图像修复问题为一个泛函求极值的问题。以此为基础的较成熟 的模型有t v ( t o t a lv a r i a t i o n ) 模型、e u l e re l a s t i c a 模型、m u m f o r d s h a h 模型等。偏微 分方程与变分法根据变分原理可以相互推导，因此这一类的方法我们可以统称为 基于变分p d e 的图像修复算法。 2 e塞盆迪厶堂亟上：羔位迨塞 互i矗 ( a ) 待修耍幽像( b ) b s c b 模型修复结果 幽1 2 基j i 偏微分方程的图像修复示例 f i g u r e1 - 2a ne x a m p l eo fi n p a i n t i n gb a s e do np d e 另外一类是擅长填充图像中大区域丢失的图像补全技术，可以称之为 c o m p l e t i o n 。这类技术的实现方法主要包括这几种：一种方法主要是基于图像分解， 即将图像分解为结构和纹理两个部分，使用上述i n p a i n t i n g 算法来修补其中的结构 部分，再使用纹理合成的方法填充其中的纹理部分。b e r t a l m i o 等人提i t 一, t5 1 ，在全 变分最小化方法的帮助下提取图像的结构部分，然后对噪声或纹理部分建模，这 样图像的结构和纹理两个部分被分解出来，结构部分就以b s c b 模型修复，纹理 部分则用纹理合成的技术来填充，再综合得到修补的这两部分结果，就得到了最 终的图像修补结果。另一种方法是利用基于块的纹理合成技术7 1 ，其主要思想是， 以待修补区域的边界上某一像素点为中心，根据图像的纹理特征选取合适大小的 区域块，然后在待修补区域的周围寻找与之最相似的纹理匹配块来许代该纹理块。 这一方法擅长修复大块丢失信息的图像，近几年来得到了相当的研究，也取得了 彳i 少成果。 ( a ) 原图像( b ) 标定待修复区域的幽像( c ) c r i m i n i s i 算法修复结果 图1 3 基1 ：纹理合成的图像修复示例 f i g u r e1 3a ne x a m p l eo fi n p a i m i n gb a s e do nt e x t u r es y n t h e s i s 上述西种方法，现在已出现较多的研究论文及成果，可称之为传统的图像修 复算法。在研究的过程中发现，在一些缺损区域较大的破损图片修复工作早，借 助原图像中的信息来进行破损区域的填补、修复往往难以达到满意的效果，因此， 新的图像修复思路应运而生。2 0 0 7 年，j a m e sh a y s 提出了一种利用其他图像上的 d e 塞 窒迪厶 堂亟：生耋兰i 立途塞曼直 信息，并融合了g r a p hc u t s 和p o i s s o nb l e n d i n g 的图像修复算法，和图像修复领域 丌辟了一个新的方向。本文也将重点针对这种方法进行研究实现。 1 3 图像修复的视觉心理学与难点分析 人眼接收图像信息时，通常依据对图像的整体理解及高层语义来识别，这种 对图像的认知同时也依赖于长期积累的经验。比如一张遮住半边的人脸图像，我 们仍旧可以根据经验【f 1 的人脸对称性猜出被遮住的另一边。由此可知，己知物体 先验的颜色、形状等信息对人的推断过程是很重要的。另一个影响我们对图像理 解的因素就是视觉心理学，比如我们可能比较习惯于完整的、闭合的图形，而不 习惯于断裂的图形，这可以称之为视觉的完形特征，都是我们在实现自动图像修 复算法时应该考虑的。总而言之，图像修复任务的实现需充分考虑到人类的视觉 系统和心脑认知机制。 在目前的视觉心理学的研究巾，暂时还没有比较成熟的理论可以作为图像修 复任务的指导理论，所以我们在研究中也只是考虑一些较简单的公认的视觉原理。 “看”就一个字却并非如其文字表述一样简单【8 】。看的行为是一个建构过程， 大脑在这个过程中并行地来响应图像的各种不同的“特征”，同时以自身经验作为 指导，将这些特征组合起来生成一个富有含义的整体。举一个例子来说，看到图 1 4 我们毫不费力的就可以看出这幅图像的含义，一张从室外拍摄的几名正在注视 窗外的人物面孔的照片。窗棱问每个人的模样分成了几部分，但是，你并没有把 它看成是多个不同人脸的分离的片断。你的大脑将它们组合在一起，解释为一个 单一物体被面前的窗棂部分遮挡的一张面孔。人类的视觉系统就是这样的处 理着我们的眼睛接收到的信息，视觉一f l , 理学被认为是“一个各部分之问相互影响 的有机整体，而整体大于各部分之和。” 图1 - 4 “看”一幅图的示例 f i g u r e1 - 4a ne x a m p l eo f “l o o k 4 k o f f k a 等人曾提出图形完形理论，意思就是说，知觉的组成遵循一定规律， 它不是简单的相加图形各部分，而是将相互关联的各个部分有机地组成，最终图 形以其整体被视觉感知。”比如我们在平时的视觉感知过程中，对于那些比较靠近 而远离其他对象的事物、那些共同特征明显如颜色风格相近的对象，我们都倾向 于将其组合在一起识别，还有几段连续却不连接但走向一致的线段我们也总是倾 向将其看作是一条连续直线被什么东西遮住而显示的部分。从视觉心理角度讲， 图像修复就是一个模拟视觉认知过程。 然而，要让图像修复过程符合视觉心理学，这一任务还是十分艰难的。若想 模拟人类感知这一高级行为，需要的技术包括模式识别、人工智能以及先验知识 与统计学习的积累。同时要遵循艺术研究者提出来的一些方法论，让数字图像处 理模拟人眼对图像的感知理解这一主动过程。包括注重艺术品的完整性，从整体 角度着眼如何填补；以破损区域周围的结构信息延伸至待修复区域：保证修复区 域与原图像颜色风格协调；加入纹理渲染来描绘细节信息。 b e r t a l m i o 等人在图像修复的研究中努力遵循上述一些原则，但在基于p d e 的 修复理论实现过程中他们发现，考虑整体效果的原则操作起来还是有困难的，且 借助p d e 也较难实现纹理的渲染。故在他们的理论中，主要从信息扩散和风格协 调两点出发，设计实现了第一个较有效的自动图形修复算法。按照这一方向研究 的算法通常适用于纹理简单的局部图像修复。后来的研究者们沿着这一方向提出 了进一步的修复模型建立原则，以局部性降低修复问题的复杂性并基于此开展底 层视觉修复的研究： ( 1 ) 局部性。修复的图像结果只与修复区域临近的信息相关，所以只能由已知 邻近的信息来推测待修复区域的信息。 ( 2 ) 可以连接断裂。人眼对边缘十分敏感，在物体识别和图像分割中边缘是一 个重要的信息，因此图像修复要考虑图像的边缘问题。 ( 3 ) 对噪声具有鲁棒性。将噪声一定程度地降低，人类视觉便可以从含有噪声 的图像中将纯净的图像提取出来，然后将其结构延伸至待修复区域中。 严格地来说，目前的图像复原研究都是用半自动的方法来修复图像，算法不 能自动获得照片的破损区域位置，所以都需要操作者按自己的需求指出。此外， 由于不能实现估计照片的损坏程度，还找不到一个统一的模型可以描述锁着这些 种类的破损，这也是一个自动算法实现上的困难。 所以目前看来，针对不同程度的破损需要使用不同类别的修复算法来分别针 对地处理，才可以真正将其修复至更好的状态。至于做到完美的图像修复，困难 还是比较大的，需要探寻一个更成熟的算法模型来实现。不过图像信息在当今人 们信息获取中的重要性，使得越来越多的人投入到图像处理领域的研究中来，随 0 。0 0 8 8 5 6 ( 9 0 3 3xfy 茎0 ，0 0 8 8 5 6 ( 3 2 ) 3 = s 0 0 ( f ( x ) 一f y ) b = 2 0 0 ( f ( y 一f ( z ) ) f ， 、一l 。 f ：0 0 0 8 8 5 6 其中，1 w 1 7 7 8 7 1 6 1 1 6 ，t 茎0 0 0 8 8 5 6 图3 - 9r g b 到l a b 颜色空间转换示例 f i g u r e3 - 9a nc o n v e r s i o nf r o mr g bt ol a b 至于颜色量化方式，考虑到颜色直方图无法有效地表达颜色分布的空问信息， 我们选择使用颜色集。颜色直方图、颜色矩等方法通常用于两幅图像问全局或局 部之间的颜色比较、匹配等，而颜色集的方法致力于实现基于颜色实现对大规模 图像的检索。山s m i t h 汞ic h a n g 提出的颜色集( c o l o rs e t s ) ，可作为对颜色直方图 的一种近似，较好的支持了大规模图像库中的快速查找，更符合本课题的要求。 在这一方法中，首先将r g b 模型转化成视觉均衡的颜色空问( 如h s v 空问) ，将 图像根据其颜色信息进行图像分割成若干r e g i o n ，并将其量化分为若干b i n 。每个 r e g i o n 进行颜色空间量化建立颜色索引，进而建立二进制图像颜色索引表。比较图 像颜色集的距离和色彩区域的窄问关系来进行图像匹配。颜色集由二进制向量表 曼塞窑垣厶堂亟堂i 互迨塞幽丝捡筮理途当簋这坌i 丘 达，因此构造二：分查找树的方法呵以提升检索的速度，这将大大利于人规模的图 像库中的检索。 根据上述知识，我们设计了一个实验，对r g b 、h s v 、l a b 三种t 颜色空l 、日j 上 的图像检索结果进行对比，最终选定一个最佳颜色空间。 r g b 颜色空问 原图 h s v 颜色窄问 l a b 颜色空问 图3 1 0r g b 、h s v 、l a b 颜色空间检索结果 f i g u r e3 10r e t r i e v a lr e s u l t su s i n gd i f f e r e n tc o l o rs p a c e s 在上述实验中，使用了包含4 0 0 幅户外风景照片的实验数据库，在其中检索 与输入图像色彩风格最相似的图像。其中，使用欧式距离函数 d ：y f t 王确2 ) 二 、 ( 3 3 ) 来计算两个图像特征的相似度。可以看到h s v 颜色空间如预想的表现出了较好的 检索效果，当然，这个结果一定程度上受到了图像库数量及图像颜色风格种类较 少的限制。最终，我们选定使用h s v 颜色空f n j 。 3 3 2 基于语义特征的算法实现 为了成功的完成图像修复，我们需要在数据库中找到不仅无缝、纹理恰当而 且语义有效的图像区域。我们不希望用车顶去修复山坡，或是在局部看似像湖一 样的城市人行道上出现鸭子在游泳。为了避免这样的情况，我们首先要寻找尽量 与待修复图像语义相等的场景。场景匹配是应用时我们的修复方法中最重要的元 素。如果没有它，我们的查找将不具备计算的可行性，而我们的图像修复结果也 将很难做到语义有效。有效的场景匹配，结合我们的庞大数据库，才使得我们在 完成图像修复工作时，不用像以前的照片综合系统一样收集明确的语义约束。 根据上一节的分析，我们选取了表征图像全局特征的g i s t 信息作为语义描述 符来完善图像检索过程。g i s t 信息是一组高维向量，而且随着样本数据集规模的扩 大，计算复杂度也将随之增大。如果直接对其进行匹配计算很容易陷入“维数灾 难”的问题。同时，原始的特征信息中有可能混杂一些“噪声”成分，需要将其 滤除掉。另外，一些特征信息在原始的输入空间中缺乏很强的鉴别能力，可能需 要经过某种函数映射到一个新的特征空问，其表征能力将大大加强。针对以上问 题，下面将分析并选择适当的特征变换及降维方法。 o t i v a & t o r r a l b a 在图像语义提取的研究中引入了场景全局特征1 7 】，通过图像的 一组统计属性或质量来描述图像的语义类别，对场景实现在自定义的粗糙度、险 峻度等5 个属性轴上的排序，试图在感官属性概念的帮助下从全局情况和场景结 构层面解释场景的语义。这一模型尽量避免了图像分割或对单个对象进行处理， 以一种低维的场景描述完成整个过程，我们称之为空域包络。 这种自定义的属性特征包括：自然度，开放度，粗糙度，展开度以及崎岖度。 每一种特征描述了该场景的某个空间属性，也对应空域包络中的一个维度，综合 所有特征便可以表示整个场景主要的空域结构。于是一个多维的空间产生，每一 维均定义了场景所要投影的图像特征空间，语义类别相似的场景在该空间的投影 也会十分相近，这便成为划分语义类别的依据。o l i v a 提出通过谱和粗略的定位信 息估计这些特征维。使用不同的回归技术可以估算基于图像特征的空问属性，例 如在一个简单的线性回归的情况下，通过场景图像的全局频谱特征v 计算得到场， 景属性s 的公式为： n a ；= v r d = 叶盔= 舭( 六，) 2 d s t ( f x ，l ) d f x l i = 1 ( 3 - 4 ) 监 d s t ( l ，) = d ，一帆，) 具中， i = 1 ( 3 - 5 ) 线性的操作提供了一个简单的估算过程写作，给人一种简单的解释系统的行 为。例如上式告诉我们空间属性可以通过图像幅度频谱和模板d s t 之间的点来估 算，判别谱模板d s t 描述了每个普分量的贡献值。 使用频谱直方图特征w 同样也可以对其进行估算： = w r d ：n lw i d i ：舭( z ，y ，六，) z w d s t ( x , y , 六，l ) d f x d l ( 3 - 6 ) i = lx y n t 其中，w d s t ( x ，y ，六，) = d ，( x ，y ，六，) ( 3 - 7 ) w d s t 即加窗的d s t ，它介绍了不同空间位置上的频谱成分如何贡献于空域 包络。w d s t 的值表征了频谱分量和空间属性s 之问的关系。 3 4相关反馈 基于内容的图像检索算法得到的检索结果完全依赖于计算机的计算，虽然是 海量图像的查找更加便捷，但其查找的准确率并不稳定，并不能做到完全符合用 户期待，毕竟计算机的运算与人类感知之间的鸿沟是目前技术很难跨越的。于是 我们考虑在检索过程中加入相关反馈技术，这样人为的干涉计算机的检索算法， 使得自动检索过程能够得到修正，使得结果更能贴近用户的期待。在基于文本的 图像检索技术盛行时，相关反馈技术即被提出用于检索【1 8 】。它在检索的过程中加 入人机交互，让用户对检索结果进行评价或排序，用户的满意程度信息被反馈给 计算机用于修正程序的查询条件，最终达到提升检索效果的目的。相关反馈技术 努力联系起了计算机与用户，各取所长服务于检索结果，希望以此填补语义与图 像特征之问的鸿沟。 在信息检索领域，相关反馈是一种指导性学习的技术。基于内容的图像检索 中的相关反馈具体过程为：系统根据输入图片自动提取的特征及图像数据库中的 图像特征，依相似度进行排序，与输入图片特征空问中相似程度越高的数据库图 像，排序越优先。用户在展示出来的排序中选择一组满意的正反馈图片和一组不 符合检索要求的负反馈图片，提交给检索系统。系统根据反馈信息来优化相似度 匹配算法并重新计算并排序。如何有效地利用交互信息，并通过优化检索算法来 提高检索的准确度成为相关反馈中最重要的问题。近年来涌现出了许多相关反馈 算法，其基本策略可以大致分为两种：改变相似度中的权重；改变检索向量，使 其向理想的方向转移。 权重调整算法，在图像检索中应用比较广泛，主要代表系统有m i n dr e a d e r 、 p i c t o s e e k 。这种算法是对图像的不同特征赋予不同的权重，通过反馈信息中用户 确定的相关或不相关的图像对查询矢量作调整：对相关的特征加大权重，不相关 的特征则减弱权重，这样会使查询矢量更加接近肯定实例的聚类而远离否定实例。 当某些查询可以用颜色、纹理等底层特征的组合来表示的时候，这一算法十分奏 效，但当用户只是关注图像中的某个对象，特征组合难以在表示查询请求时发挥 作用，则得不到理想的检索结果。 查询向量转移算法，获得反馈信息后，使图像库中相似的图像与输入更靠近 不相似的则远离。f 反馈信息加上负反馈信息的补充，将查询向量进一步优化， 结合权重调整算法和向量转移算法，可以建立一个反馈信息学习模型。检索过程 中用户与系统相互作用，用户的高等语言信息融入检索算法，使反馈后的检索效 果更佳 19 1 。 根据上述分析，我们使用了基于权重调整的相关反馈方法，采用r o c c h i o 公式 和b a y e s 方法作为策略实现反馈算法，具体流程如下图所示。 图3 1 1 相关反馈流程图 f i g u r e3 - 11r e l e v a n c ef e e d b a c k 加入了相关反馈的检索策略步骤如下： ( 1 ) 比较第一轮检索的图像和原始图像的特征向量，初始化的权重。 ( 2 ) 比较检索到的图像和原始图像的一系列相似措施。 ( 3 ) 用户标志出相关或不相关的检索图像。 ( 4 ) 计算新的查询条件，这是更多的调整。 ( 5 ) 更新每个功能的相似性度量的权重。 ( 6 ) 启动新一轮检索。 原来，这一步在提高图像检索的结果是有效的。从而搜索最相似的场景，我 们选择作为我们的形象补丁的前几名。 3 5实验结果与分析 对给定一个待修复的输入图像，首先计算其除待修复区域在外的g i s t 描述符。 然后计算出待修复图像的g i s t 描述符与数据库中每个g i s t 描述符之间的距离。然 后对h s v 颜色空间中进行颜色的距离计算。对这些距离相结合并加权，例如g i s t ：止! 窒迪厶堂亟上堂位途塞幽堡捡筮理途! i 簋i 叁坌近 描述符冰2 + 颜色距离术1 ，得到图像之问的最终距离。选择距离最小的图像来进行图 像的修复。 黼进盏 3 6本章小结 图3 1 2 一个图像检索结果示例 f i g u r e3 12h n a g er e t r i e v a lr e s u l t 本章针对基_ f 内容的图像检索技术展丌了讨论与研究。作为我们的图像修复 方案的基础，在这一环节中我们需要搜索得到一系列合适的补丁图像。因此，选 择了使用图像的h s v 颜色特征和全局场景语义特征来进行图像检索。这样基于综 合图像特征的检索方案使得检索的结果既满足了风格与待修复图像相似，又避免 了与原图像语义相去甚远导致的不和谐的拼接结果。为了进一步提高检索结果与 用户期待的契合程度，我们在检索过程中加入了相关反馈技术，用户反馈信息的 介入使得检索算法自身进行修f ，提高了补丁图像的满意度也就是提高了修复图 像的满意程度。实验结果证明，这样的改进显示出良好的效果。 4 基于图像检索的图像修复理论 根据第三章所述方案获得了一系列检索结果图像以后，我们需要进行一些更 精细的计算来得到用于填补缺损的补丁图像，并且将其无缝的融入带修补图像。 4 1引言 在高兴的得到了与待修复图像十分相似且语义相符的检索结果图像以后，我 们可以直接将其按照蒙版标记的区域剪切下有用部分，然后放入已经挖好了一个 洞的带修补图像。但是这样的简单拼接的结果可想而知，虽然不排除有个别补丁 与带修补区域十分匹配与吻合的情况，但大多数情况下，这样的拼接效果十分粗 鲁，得到的最终图像人工处理痕迹明显，难以被用户接受。 现代图像融合技术的帮助使我们摆脱了这种暴力拼接的方法。数字图像融合 技术对不同的图像最大限度的提取各自的图像信息，然后绘制成一幅具有综合信 息的新的图像，在目前具有广泛应用。这一技术在本质上，就是由一组图像获得 一幅图像，而这一新图像包含有更多有用信息。如将目标对象放入期待的背景图 像中，让图像吸收了新的内容而又看起来舒适和谐。早期有一些简单的图像融合 技术，但结果让人们很容易分辨出图像的拼接痕迹，效果不佳。 图像融合的优势是可以消除冗余信息，并添加有用的信息，总结其目标为： 从原图像中提取有用的信息 避免引入阻碍图像处理的冗余信息 保证算法在解决原图像对齐等问题时的可行性及鲁棒性 常见的图像融合算法有采用图像金字塔算法的融合和采用小波变换算法的融 合。这两种方法本质上是相似的，即转换图像的分辨率，以多层次的形象，综合 不同分辨率下的边缘信息，生成最终的融合图像。由于不同的方法产生的图像金 字塔可分为以下几种：低通滤波器的金字塔，拉普拉斯金字塔，梯度金字塔。 本文选取了除此以外的一种技术，基于泊松方程的梯度域融合方法。近几年 出现的几篇很棒的泊松图像编辑领域的论文，展示了梯度域图像处理在几个不同 方向的应用比如数字蒙太奇，泊松编辑，图像拖拽，高动态压缩，图像修补，梯 度域绘画，泊松抠图等。将图像转换为梯度域，然后建立泊松方程进行求解，这 一过程中，最终得到一幅细节更丰富的全新图像，这就是我们的目标。 在融合操作之前仍有一个重要的环节，就是从检索结果图片中取得精确的补 ： e 丞窑适厶：羔亟堂位迨塞堇幽遂捡塞的幽篮丝复理论 图像区域，也就是说要通过计算来丽出补丁与带修补图像的接缝，而不是简单 地依靠蒙版的f i i 硬线条米作为图像融合两部分的接缝。因此，我们采用了在计算 机视觉领域广泛使月j 的图分割能最最小化理论，利用最大流最小割的算法计算能 量最小的分割，以此为图像选择最佳的拼接映射，得到最佳接缝。 4 2 计算最佳接缝 为了融合的图像没有人j ：的痕迹，达到尽量好的效果，我们首先进行图像切 割，以找到具有最小梯度值的边界来进行泊松融合。 本文使用g r a p hc u t s 算法来快速找到最佳的接缝，其过程可山图4 1 所示。在 这一步中，用图像切割的方法来优化蒙面的边界，以减少在泊松融合过程中的人 工痕迹。这个过程中，我们需要对补丁图像和原始图像在蒙版外的图像的重叠的 区域内找到一个接缝，使两幅图像问梯度值的像素的欧氏距离和接缝到蒙板区域 的距离是最小的。在本论文耳! 我们用b o y k o v 的图像切割最优化技术来实现。 几 i 矧4 - 1 最佳接缝的计算过f 。t f i g u r e4 1g e tt h eb e s tp a t ho ff u s i o n 4 2 1图分割的能量最小化理论 本文使用了基于图分割的能量最小化技术为图片的不同部分选择更好的拼 接，因此本节介绍了图分割和能量最小化的几个理论基础。 一、图分割理论 割( c u t ) 是图论中的概念。在图论中【2 0 】，用g = 表示一个有向图，其中 v 为节点集，可代表图像中的像素点，e 为连接这些节点的带权有向边集。端点是 节点集v 中的一类特殊的点，如二元图像分割中的源端点s 和终端点t ，在图像处 理技术中则对应图像的前景和背景两部分，如图4 2 所示的( a ) 例。割的定义是对 网络中顶点的一个划分，把网络中的所有顶点划分成两个顶点集合s 和t ，其中源 点s e s ，终点t t ，即记为一个c u t ( s ，t ) 。如( b ) 图所示，选取一个合适的割c 令 它为e 的一个子集，使得图g = 被分为两个互不连通的子图，而源点s 与终点t 分属于不同的子图，各自连接s 与t 的两部分组合成分割结果，这个过程 即称为图像分害4 j ( g r a p hc u t ) 。 ( a ) a g r a p hg( b ) a c u to ng 图4 - 2 一个图像分割的例子 f i g u r e4 2a ne x a m p l eo fag r a p hc u t 如何判断一个图割c 的优劣，有不同的算法可以依据。如果一个割c 截断的 所有相连的边的权值和达到最小，则称这个割为最小割( m i n c u t ) 口1 1 。 二、最大流最d , 害- i j ( m a x f l o w m i n c u t ) 我们可以将图的边视为有向的管道，其最大流通量也就等于边的权值，则我 们将源点s 向终点t 传输的最大流通量成为最大流( m a x f l o w ) 。s 到t 的最大流让图 中的一部分边饱和，图中的节点被分为两个不连通的部分 s ，t ) ，即构成一个最小 割，这便是f o r d 提出的最大流最小割定理。因此，我们可以通过计算最大流来获 取最小割。 若我们把源点s 看作流通管道的入口，终点t 看作管道的出口，每一个边的权 值看作管道中各端点之间的管道流通量，则最小割的问题还可以这样来理解：从 入口流向出口的流量有一个速度，如果入口流量速度的增大不会再使出口的速度 增大，则中间的一部分管道流量已经达到饱和，而这些管道实际上就对应要被切 1 气 割的边，这个流量便是所谓的最大流。 图4 3 最大流最小割搜索树示例 f i g u r e4 - 3a ne x a m p l eo fs e a r c ht r e e 根据这种最大流最小割等价转换的思想，可以用如图4 3 示例表示算法思路。 图中s 树和t 树互不重叠，树根分别是源点s 和终点t 。s 树中所有所有连接父节 点到子节点的边都是不饱和的，相应的t 树中所有连接子节点到父节点的边都不 饱和。中间的空白节点是自由的，不属于s 树或t 树，即 sc v ，s s ，tcv ，t t ，sr 、t g ( 4 2 ) s 树和t 树中的节点可以是活动的或非活动的。活动节点表示了搜索树的边界 节点，而非活动节点表示内部节点。活动节点可以通过生长，沿着非饱和边从自 由节点中吸纳新的子节点。而非活动节点由于被同一棵树的节点所包围，所以不 能生长。活动节点可能在生长过程中碰到另一棵树的节点，那么一条增广路径就 形成了。 算法迭代地重复如下三个步骤： 、 “生长”阶段：搜索树s t 生长，直到两棵树相遇，并形成一条从s 到t 的路 径； “增广”阶段：增广路径生成，搜索树可能变为森林； “回收”阶段：树s 和t 被重新划分。 4 2 2 基于g r a p hc u t s 的方法 g r a p hc u t s 方法把分割问题转化成最优化问题，以最大流算法为基础能够对一 类具有某种特定形式的能量函数快速有效的求解全局最优解，因此在近些年受到 越来越多的关注。 基于g r a p hc u t s 的合成算法2 2 1 ，主要是使用图分割的方法对拼接重叠区块计 算最小误差边界，来决定用哪个补丁来填充重叠区域各位置上的像素。为了使用 图分割技术，我们将重叠区块位置视为一个图，在相邻的像素点之间建立起边， 由边所连接的两个像素的颜色差决定这条边的权值。得到图模型后我们便可以依 据最大流最小割定理，在图中找到一个最小割，此割决定的路径即可将两个重叠 块以最小的误差拼接起来。这样计算接缝不需要限制重叠块的形状，任意均可， 因此时拼接合成更灵活。所以在我们进行补丁图像与带修复图像的融合过程中， 第一步先使用g r a p hc u t s 算法来查找最佳的接缝。 在g r a p hc u t s 算法的实现过程中，为了度量已融合和待融合区域之间的像素 我们需要引入一种匹配方法，最简单的度量方法就是直接计算接缝两边的一对像 素的颜色差。设s 、t 为两相邻的像素点，a 、b 则代表已融合的和待融合的两个区 域，像素在相应区域内的颜色只用a ( ) 和b o 来表示，则定义匹配度量函数m 如下： m ( s , t , a , b ，= 嵩囊黯糕溉 件3 ， 式中，g ：( s ) 是区域a 沿着切线d 方向的梯度值。这个匹配度量就是我们使用 g r a p hc u t s 来解决接缝查找问题的关键。用形象的方式来表现g r a p hc u t s 算法计算 最小割寻找接缝的过程如图4 4 所示，也就是我们上面阐述的最大流最小割理论。 其中( b ) 图中的折线c u t 即代表最小割。 一吟 图4 - 4g r a p h c u t s 算法 f i g u r e4 - 4g r a p hc u t sa l g o r i t h m 仅依靠上述算法仍不足以实现效果良好的g r a p hc u t s 合成。假设在输出位置 已经填充了一些补丁像素，但在已经有多个补丁重叠的位置我们希望打上新的补 丁，在旧的补丁之间的边界会出现一条可能的新接缝，我们需要重新计算。 我们以图4 5 所示来阐述新接缝的计算问题。为解决这个问题，构建图时，所 有的旧补丁用节点a 表示，b 为新补丁，而a 。用来表示a 中的某一特定像素。对 于老像素之间的每个接缝，我们在图中一组像素点之间引入一个接缝节点。以一 条到b 的弧线来连接每个接缝节点，而弧成本就等于创建这个接缝时的计算得到 的匹配值，也就是4 3 式计算得到的m 值。比如( b ) 图中像素1 和像素4 之间的旧 接缝，我们在其位置上插入一个接缝节点s l ，连接s l 与新补丁b ，这个弧线则以 旧的匹配值m ( 1 4 ，a i ，a 4 ) 来赋值。如果接缝节点和新补丁b 之问的弧线是一个割， 就代表输出图像中仍保留这个旧接缝，如果不是则使用新像素来覆盖。就如( b ) 图 中的o l dc u t 将被n e wc u t 替代。 罐l 辩锵 ( a )( b ) 图4 5 搜索新接缝线替代旧接缝线 f i g u r e4 - 5s e a r c hf o ran e wc u t