（计算机应用技术专业论文）基于数字蒙太奇的图像编辑方法研究.pdf

基于数字蒙太奇的图像编辑方法研究 浙珏大学2 0 4 2 1 2 3 0 蕺芬 第一章绪论 1 1引言 在虚拟现实技术广泛应用的今天，需要重现的三维场景逐渐复杂和庞大，传统 的以三维几何信息为基础的图形绘制技术越来越不能满足人们对真实性和实时性的 要求。基于图像的绘制技术应运丽生。数字蒙太奇技术作为图像处理技术和基于图 像的绘制技术中的一种，近年来得到了广泛深入的研究。目前，已有很多的图像处 理应用领域用到了蒙太奇技术，如照片处理、宏强影、全景拼图、背景重建、运动 物体的频闪观测可视化等等。这些图像处理技术在动漫原型设计、媒体设计制作、 旅游风景宣传画绘制和人脸整形手术效果预览等领域中得到了极为广泛的应用。同 时基于数字蒙太奇的图像编辑技术还可以广泛地应用于科学研究、宏摄影和医疗业 中，例如科学家用显微镜看标本的时候往往只可以看到很有限的景深，不能同时看 清楚整个标本。利用景深扩展就能够聚焦到整个三维标本，立体地显示物体。又例 如用选择合成的方法可以在脸部整形手术之前预览可能出现的整形效果等等。 综上所述，基于数字蒙太奇的图像编辑技术具有巨大的应用开发价值。但是数 字蒙太奇还是一门新兴的技术，并不是十分完善。它的研究前景还很广，而且目前 国内与之相关的研究并不多见。因此，有必要对数字蒙太奇技术进行进一步的深入 研究。本文提出了一种基于数字蒙太奇的图像编辑系统的技术架构，着重介绍了本 构架解决蒙太奇两个技术挑战的实现细节，并把它们应用于交互式和非交互式两种 图像编辑方式。 在本章的其余部分，先简单介绍了基于图像的绘制技术，然后介绍了数字蒙太 奇的定义及其研究背景和现状，最后给出了本文的章节结构 1 2 基于图像的绘制 基于图像的绘制( i b r ) ，就是从初始的一组取自真实场景的图像开始，经过一 定的计算处理，合成新的图像。基于图像的绘制技术是传统图形学和计算机视觉的 有机组合。它利用了图形学中用几何信息生成新图像和计算机视觉中恢复粗略场景 基于数字蘩太奇的图像编辑方法研究 浙江大学2 0 4 2 1 2 3 0 戴芬 1 3 数字蒙太奇的研究背景 蒙太奇的历史可以追溯到摄影术开始的时候。早在十九世纪中叶，一些艺术家 ( 例如0 s c a rr e j l a n d e r 和h e n r yp e a c hr o b i n s o n ) 就开始利用合并多幅照片的方 法来表达更好的细节。后来，又有很多艺术家( 例如s c o t tm u t t e ra n dj e r r y u e l s m a n n ) 利用这种方法来获得超现实结果。无论是现实还是超现实，这些艺术家 都面临着同样的难题，那就是：怎样才能更有效地拼接合并多幅照片，使这些照片 看起来更加自然、完整。 数字蒙太奇则是伴随着计算机图形图像处理的发展而产生的一个新的应用领 域。它是一种新的基于图像的绘制技术。它是指对于同一场景的不同照片，通过拼 接、融合形成一幅新的更好表达摄影师对场景理解的照片的架构技术。 1 3 。l 国内外已有的算法 ( 1 ) 1 9 8 5 年，毕业于美国伊利诺伊大学的o 酣e n 博士利用拉普拉斯金字塔算法 进行了照片融合 o g d e n 8 5 。 ( 2 ) 1 9 9 3 年，p e t e rj b u r t 博士与r a y m o n djk o l c z y n s k i 博士利用逐像素的 特征启发式方法进行了照片融合 b u r t 9 3 。 以上两种早期的成果都显示了扩展动态范围和景深的可能性，也表明了在不同 的光照下产生融合效果合成图像的可行性。但是这些早期的作品都不能很好的表达 细节，同时也不能提供对结果的交互控制。 ( 3 ) 1 9 9 4 年，s i l i c o ng r a p h i c s 公司的研究员p a u lh a e b e r l i 简化了逐像素的 特征启发式方法，并演示了用简化方法做的扩展景深效果图 h a e b e r li 9 4 。但是由 于缺乏空问规范化( s p a t i a lr e g u l a r i z a t i o n ) ，会产生很多噪音。他还演示了用 一个物体的不同的光照图获得的简单的重光照( r e l i g h t i n g ) 效果图。 ( 4 ) 2 0 0 1 年，底省理工大学的w e i s s 博士运用基本梯度区域融合技术创建了“本 征图像” w e i s s 0 1 。 基于数字蒙太奇的图像编辑方法研究 浙江大学2 0 4 2 1 2 3 0 戴芬 ( 5 ) 2 0 0 2 年，毕业于希伯来大学的研究生，计算机图形学实验室的成员r a a n a n f a t t a l 将梯度区域融合技术运用于“高动态范围压缩” f a t t a l 0 2 。 ( 6 ) 2 0 0 3 年，左治亚理工大学的v i v e kk w a t r a 博士将最近几年应用范围较广的 图像分割技术运用于图像合成 b o y k o v o l a ，k w a t r a 0 3 。 ( 7 ) 2 0 0 4 年，华盛顿大学的a s e e ma g a w a l a 博士等提出了一系列先进的数字蒙 太奇的处理方法 a g a r w a l a 0 4 ，如基于泊松图像编辑法的梯度区域融合技术等，并 把这些技术推广到一些新的应用领域，譬如希伯来大学计算机视觉实验室的a n a t l e v i n 研究员的全景马赛克缝合 l e v i n 0 4 ，剑桥大学肛r l 实验室的高级研究员 r a m e s hr a s k a r 博士的超现实重光照模拟等等 r a s k a r 0 4 。 上述都是国外的一些研究现状，国内目前在这方面的研究很少。 1 3 2 国内外具有数字蒙太奇处理效果的软件 a d o b ep h 。t o s h o p ： p h o t o s h 。p 具有简单的蒙太奇图像编辑效果，它有两个工具， 画笔工具 b r u s ht 0 0 1 、层遮罩 l a y e r sm a s k s 。用户选定一组想要放到一起的经 过增强的图片，置于同一张画布( 图像文件) 里，然后选用画笔工具 b r u s ht 0 0 1 ( 采用比较大的笔刷) ，并选择层遮罩。最后用画笔工具在要融合的区域涂抹，便 可产生蒙太奇效果。由此可见p h 。t o s h o p 处理蒙太奇需要很多的人工交互，例如在扩 展景深的应用中，我们只需给出源图像，系统会自动选择最好的象素点和接缝点， 但p h o t o s h o p 需要人工的选择边界，很不方便，而且得到的结果也不精确。 f i r e w o r k sm ) 【：f i r e w o r k s l x 亦可产生简单的蒙太奇效果。它需要类似于 p h o t o s h o p 的三种技术：修饰( r e t o u c h i n g ) ，遮罩( m a s k i n g ) ，淡入( f a d i n g ) 。 智能剪刀( i n t e l l i g e n ts c i s s o r s ) ：不需要人工交互，可以自动生成图像， 但不能同时处理多幅源图像 m o r t e n s e n 9 5 。 4 基于数字蒙太奇的图像编辑方法研究靳江大学2 0 4 2 1 2 3 0 藏芬 1 4 本文的研究内容和组织结构 本文的工作就是基于目前一种新的基于图像绘制技术：基于数字蒙太奇的图像 编辑技术而展开。研究了该技术的两个主要技术难点，并对于交互式和非交互式两 种图像编辑方式中的应用进行了探索和实践。本文后面的几章介绍了以下几项工作： 第二章的开始介绍了数字蒙太奇技术的几个基本术语：然后详细讲解了它的两 个理论基础，也就是本文用来解决本系统中两个难点的技术：图分割的能量最小化 技术和p o i s s o n 方程的基本理论：在本章的最后列出了数字蒙太奇的几种常见的应 用。 第三章介绍了我们设计实现的数字蒙太奇图像编辑系统，对于系统的架构，功 能，用户界面和操作流程等做出了详细的介绍。 第四章详细讲述了系统中交互式数字蒙太奇的图像编辑的实现方法，首先对用 户交互的基本概念和实现方法进行了简单的介绍，然后探讨了如何把图分割的能量 最小化和p o i s s o n 方程应用于解决交互式蒙太奇的图像编辑方式，即：交互式的圈分 割最优化和基于p o i s s o n 方程的梯度域融合。在这一章的最后，我们给出了交互式数 字蒙太奇的应用：选择合成和人像合成。以及相应的试验结果。 第五章介绍了如何实现非交互式数字蒙太奇的图像编辑。与交互式不同的是， 在非交互式蒙太奇方法中，我们首先要探讨的是如何进行图像校准，而且非交互式 数字蒙太奇方法和交互式在图分割最优化和基于p o i s s o n 方程的梯度域融合上也有 一些不同，主要是它的多目标梯度域融合要在整个合成空间上解。在5 2 和5 3 节中 将有详细讲述，本章的最后同样给出了非交互式数字蒙太奇的应用和试验结果：扩 展景深，运动物体的频闪可视化等等。 第六章是对论文的总结和对数字蒙太奇技术的展望。 基于数字蒙太奇的图像编辑方法研究 浙江大学2 0 4 2 1 2 3 0 戴芬 4 ) 最小或最大可能性( m i n i m u mo rm a x i l u m1 i k e l i h 0 0 d ) ：这个像素带 中出现次数最多或最少的像素( 服从特定的柱状量化方程) 5 ) 橡皮( e r a s e r ) ：和当前合成图像差别最大的颜色。 6 ) 最小或最大差异( m i n i m u mo rm a x i m u md i f f e r e n c e ) ：与某一特定源 图像在p 处的颜色最相近或差别最大的颜色。 7 ) 指定图像( d e s i g n a t e di m a g e ) ：源图像序列中指定的某一特定图像。 接缝目标( s e a mo b j e c t i v e ) ：在蒙太奇效果处理中另一个需要指定的属性。用来 表示两个图像区域接缝的吻合程度。在一幅图像中只能有一个接缝标准，因此接 缝目标只能全局的运用，不同于图像目标既可以全局的运用，也可以运用于局部 区域。目前可实现的接缝目标有： 1 ) 颜色( c 0 1 0 r s ) ：接缝处颜色匹配 2 ) 颜色剃度( c o l o r s g r a d i e n t ) ：接缝处颜色和颜色梯度都匹配。 3 ) 颜色边缘( c 0 1 0 r s e d g e s ) ：接缝处颜色匹配但是保留边界处的颜色差异。 2 2 数字蒙太奇的理论基础 数字蒙太奇方法有两个主要的技术挑战：一是为合成照片的不同部分选择好的 接缝，使其更好的拼接，拼接赝像( a r t i f a c t s ) 最少；二是通过融合各个图像区域 的方法减少剩余的拼接赝像。 为了解决以上两个问题，一般采用以下 x 基于数字蒙太奇的图像编辑方法研究 浙江大学2 0 4 2 1 2 3 0 戴芬 多局部最小值，而且可能的标记法空间具有数以千计的维数。于是人们便试图设 计各种快速能量最小化算法图。模拟退火算法就是其中一种，它在计算机视觉中被 普及，并且由于它能优化任意能量函数而被广泛使用。然而，优化任意能量函数需 要指数时间复杂度，因而速度很慢，而且由于模拟退火的每一步骤都改变了单一的 像素值，在实际应用中是无效的。 为了增强能量函数的通用性。我们允许d 。为任意值，且将平滑项定义为如下形 式： 互。= ( ，) ( 2 2 ) p ，甜“ 其中n 是相邻像素对集。在特别的情况下，这样的能量能够被精确地最小化。如 果可能的标记数目为= 2 ，那么通过计算某图上的最小惩罚值分割可以在多项式时 间复杂度内找到精确的解 g r e i 9 8 9 。如果l 是一个有限的一维集且交互势能为 p ，( ，) = i 一那么通过图分割能够精确地找到最小值 b o y k 0 v 9 8 ，i s h i k a w a 。 2 z 1 2 图分割的快速近似能量最小化方法 b o y k o v 设计的算法 b o y k o v 0 1 a 是对于任意有限的标记集l 在两类普通的交互势 能v ( 半度量和度量) 上快速近似地最小化能量占( ，) 的。半度量和度量是这样定义 的：如果对于任意标记对口，卢，满足矿，) = 矿( 卢，口) o 并且矿心，国= o 口= ， 则v 在标记空间l 中被称为半度量。如果v 还对于任意l 中的a ，声，y 满足三角不等 式矿( d ，芦) 矿( a ，r ) + 矿( n 芦) ，则v 被称为度量。半度量和度量都包含非连续保留交互 势能的重要实例。非连续保留交互势能都属于半度量和度量的范畴。例如上限距离厶 y 心，卢) = m i n ( k ，忙一印和p 。t t s 交互惩罚因子y = d ( ) 都是度量。 b o y k o v 描述的图分割算法主要是计算一种( 即便允许较大变动时) 局部最小值 的标记法。他提出了两种计算局部最小量的图分割算法。一种是口扩张：对于一种 标记a ，此变动将任意一部分像素集的标记赋为。；另一种是a 一口交换，对于一 对标记a ，此变动将任意一部分标记为a 的像素集与任意一部分标记为卢的像素 基于数字蒙太奇的图像编辑方法研究浙江大学2 0 4 2 1 2 3 0 戴芬 集之间相互交换标记。这两种算法都将最终生成能量最小的标记。a 扩张只能用于 度量一。 情况，而a 一声交换能用于任何半度量_ 。 。 两种算法描述如下： 、s t d n w i t h 册口岫i 打r y l 曲e h n g ， 2 f c c ：= o 3 f o re h p o r l 口b e b 恼，趴 l 3 、f i n d f = a 工g h 曲e u j 、a m 狮g ，j w “m no n ea 一马刚叩o j f 32 矿量( ，) ( e ( ，x f ，；，口耐s c c j ：= l 4 骖s c e = 1g o t 0 2 5 ，r e m ，竹厂 图2 一l 交换算法流程图 、s t - tw n hd nc b t 打n r yt o b e l i n g ， 2 s 台f5 c c p s s ：= 0 3 而r8 口幽如6 p z 口三 3 1 丹耐厂= a r g m i n 三( 厂) 硎。裙厂w 确抑研e 口一e x p 册s 而”d ，厂 3 2 矿e ( ，) e ( 厂) ，j 鲥厂= = 厂口，耐j 诎c e 船：= 1 4 、薛s w c e s s = 、9 0 t 0 2 5 r e m m ， 图2 2 扩张算法流程图 2 2 1 2 1 分类与变动空间 任何一种标记法f 可以独特地表示为图像像素的一种分类p = f 只1 ，e ，其中 # = p e p = ，) 是一个标记赋为l 的图像像素的子集。由于标记法f 与分类p 之间有明 显的一一对应关系，我们可以交换地使用这些概念。 给予一对标记口，卢，从一个分类p ( 标记法f ) 到一新分类p ，( 标记法厂) 的 称作口一声交换的变动是指：对于任何，a ，声的标记，鼻= 鼻。这意味着p 与一之 间的唯一差异是：某些原本在p 中标记为口的像素现在在p ，中标记为口，而某些原 本在p 中标记为口的像素现在在p 中标记为口。 给予一个标记a ，从一个分类p ( 标记法。到新分类p ( 标记法，) 的变动 叫作口一扩张，当且仅当对于任何标记f a ，只c 巧且0 c 鼻。换句话说，a 一扩张允 基于数字荣太奇的图像编辑方法研究 浙江大学2 0 4 2 1 2 3 0 戴芬 许任何一部分图像像素集的标记变换为a 。 注意到给予单一像素标记a 的变动既是一次a 一卢交换，也是一次a 扩张。 2 2 1 2 2 算法及其性质 在图2 一l ，2 2 所示的两种能量最小化算法中b o y k o v 把步骤3 卜3 2 的一次执行叫 做一次迭代，把步骤2 4 的一次执行叫做一次循环。每次循环中，算法以某种固定或 随机的顺序对于每个标记( 扩张变动算法) 或每对标记( 交换变动算法) 执行一次 迭代。如果在任意一次迭代中可以找到一严格意义上更好的标记法，那么这次循环 是成功的。遇到第一次不成功的循环之后，算法结束，因为不可能有更进一步的改 进了。很明显，交换变动算法的一次循环进行蚶次迭代，扩张变动算法的一次循环 进行吲次迭代。 算法的一些重要性质：首先算法循环次数是有限的。通常情况下，算法在o ( 1 p f ) 次循环内终止结束。其次算法终止生成标记法的能量是一个对应于交换变动或扩张 变动的局部最小值。 2 2 1 2 3 图分割 上述两种算法的主要部分在于3 1 步骤，图分割被用来有效地寻找夕。令g = ( 矿，s ) 为一带两个特别顶点( 称为端点) 的带权图。一条分割c c e 指的是使得两端点在 引导图g ( c ) = ( 矿，s c ) 中被分离的一个边的集合。另外。没有任何c 的真子集将g ( c ) 的两端点分离。分割c 的惩罚值( 用蚓表示) ，等于它边的权重值之和。 最小分割问题就是要寻找惩罚值最小的分割。 步骤3 1 对于大小为硎p i ) 的图使用单一的最小值分割。每次迭代之后，图被动态 地更新。此最小值分割的细节对于交换变动和扩张变动算法来说不完全一样，本文 主要介绍了交换变动，扩张变动请参看 b o y k o v 0 1 a 。 2 2 1 - 2 4 寻找最优的交换变动 基于数字蒙太奇的图像编辑方法研究 浙江大学2 0 4 2 1 2 3 0 戴芬 图2 3 一个图实例g 。，对于源图像序列的抽象a 源图像序列的像素集为乞= 只u 0 ，其中只e 为像素集的一个分割，只= 协斟，b = q ，i f j 给予一输入标记法f ( 分类尸) 和标记对a 、卢，我们想要在瑚一次a 一声交换中 找到对于所有标记来说，可以最小化瑚一个新标记法尹。这是图2 3 上部分算法的 关键步骤。b o y k o v 的技术是基于计算一个对应于图= ( ，) 的最小值分割的标记 法。此图的结构是由当前的分类p 和标记a 、口动态决定的。 图的结构由图2 3 展示。为了便于理解，此图仅仅显示了1 维图像的情况。图分割 的理论认为对于任何图像，的结构可表示如下：项点集包括两终点“和和 岛= 只u 只；每个像素pe 岛通过和笮边分别与两终点a 和卢相连，我们将这些边 叫做卜l i n k ( 终点连接) ；每对相邻的像素点 n g c 厶( f p ，9 ) e j v ) 通过边e ( 我 们称之为n n k ( 相邻连接) ) 相连；边集由u 日 ，) 卜n “和。雠 ( l i n k ) 组成。赋予边的权重如图2 4 ： e d g ew e i g h t f o r 谬d p ( n ) + 臻，k ，q ) ( n ，矗) p 月 口p n t # d p ( 口) + ：恐k n 时( 口，厶) p p ，棚 8 鼽q u n 砷( n ) 9 ) 佃，q e ，；q p 。p 图2 4 1 2 基于数字蒙太奇的图像编辑方法研究浙江大学2 0 4 2 1 2 3 0 戴芬 引理2 ( 由性质1 和方程式2 3 得到) ：对于任意切割研口任意p l i n k 边e i c “卜，f ) ( 2 4 ) 定理1 ( 由引理1 和2 及性质1 得到) ：一条在上的分割卿啪一次a 一卢交换后 得到的标记法之间有一一对应关系。此外，岛上的分割珀惩罚值是蚓= e ( ，。) 加上 一个常量值。 因此，由b o y k o v 理论得出：确最优的a 一声交换结果是夕= ，。，其中劲在g 。上 的最小值分割。 2 2 1 3 最大流最小割的算法 在寻求最小值切割问题的过程中，为了避免冗余且缓慢的组合计算方法，快速地 计算最小能量，我们使用了最大流最小割的算法 b o y k o v 0 4 。它基于经典的最大流 图论算法，在计算机视觉领域有着广泛应用。简单地说，可以通过寻求源端点s 至 目标端点t 的最大流的方法来解决最小a 口切割问题。 我们可以将图的边视为最大流通量等于边权重值的“有向管道”，最大流就是指 自源端点s 至目标端点 传输的“最大水流量”。f o r d 和f u l k e r s o n 的理论 f o r d 6 2 阐明：s 至f 的最大流使得图中的一些边达到饱和，将图结点分为对应于一条最小 切割的两个不相交的部分 最n 。因此，最大流和最小割问题是等价的。事实上， 最大流值与最小割的总惩罚值是相等的。所以我们可以通过求最大流来解决最小割 问题。 图2 - 6 最大流最小割算法图，左边是一个3 3 的图实例，边的粗细代便权重值的大小，箭头 方向指示水流管道方向，右图是左图的一个最小值切割 此算法和d i n i c 算法 d i n i c 7 0 相似，它通过建立查找树来寻找增广路径，不同 1 4 基于数字蒙太奇的图像编辑方法研究 浙江大学2 0 4 2 1 2 3 0 戴芬 之处在于它将重用而不是重新构造这棵树。b o y k o v 的试验结果表明在典型视觉问题 中，此算法很大程度上优于早期视觉的能量最小化算法。 2 2 1 _ 3 1 算法概述 我们保存一棵以a 作为根结点的搜索树舅其中自父结点到子结点的边都是非饱 和的。不在s 中的点称为“自由”结点。所有自由结点的集合用，表示。搜索树5 中的结点可分为“主动”和“被动”两类。主动结点可以增长，也就是说它们可以 从自由结点集中获得新的子结点。被动结点不具有通过非饱和边相连的自由邻结点。 因此，被动结点不能增长。 算法迭代地重复以下三个步骤： “生长”阶段：搜索树不断增长，直到找到卢。 “增广”阶段：已寻找到的路径被增广，搜索树被分割为森林。 “回收”阶段：森林被重新转换为一棵树。 在生长阶段，搜索树在增广，主动结点从自由结点集中获得新的子结点。新获得 的结点也成为搜索树s 的主动成员。只要指定主动结点的所有邻结点被遍历过，此 主动结点就变为被动。当遇到卢时生长阶段就结束了，这样就找到了从。到卢的一 条路径。 增广阶段对生长阶段寻找到的路径进行增广。因为我们顺着可能的最大流量推 动，因而路径中的一些边就饱和了。因此树中的一些结点变成了“孤儿”，也就是说， 连接这些结点和它们父结点的边不再有效( 它们饱和了) 。事实上，增广阶段把搜索 树j 拆分成一个森林。原点仍然是森林中某棵树的根结点，孤结点成为其它树的根 结点。 回收阶段的目标是恢复为个以a 为根结点的搜索树结构。在这个阶段我们试图 为每一个孤结点寻找一个新的有效的父结点。如果没有这样的父结点，我们就把这 个孤结点从j 中移除，使它成为自由结点。我们亦将它以前的子结点声明为孤结点。 当没有孤结点留下时，这个阶段就结束了，于是搜索树s 就被修复了。因为s 中的 一些孤结点变为自由结点，所以回收阶段导致集合s 的收缩。 回收阶段完成以后，算法返回生长阶段。当搜索树不能再生长，且口没有被找到( 所 基于数字蒙太奇的图像编辑方法研究 浙江大学2 0 4 2 1 2 3 0 戴芬 有的主动结点检查他们的邻结点，并且变为被动) 时，算法结束。 2 2 1 3 2 执行细节 假定给予我们一个有向图g = s ) 。对于增广路径算法，我们将保存流，和剩余 图g ， 6 ，对于每一结点p ，我们将它的父结点存储为删脚。森林的根结点 ( 。和孤结点) 以及所有的自由结点都没有父结点，即剧舾w ( 西= 曲。我们也将 所有的主动结点标记为丑所有孤结点记为口。算法的总体结构如下： 加l ，北“协：s = 一= 口) ，丁= y 一 日) ，d = o w h i k 打e g r d wst o 再n dd nn r 鲁h e m e n t 妇gp t hp 扣。m 口 o 母 玎p = 0t e r m i i e d m g m e 卅d n d 。p t 唧h _ l s e n d w h i k 生长，增广，回收阶段的细节描述分别如下： 1 ) 生长阶段：在这个阶段，主动结点从自由结点集中获得新的子结点。 玎t sr e n f np = p a t h w 如彳a p i c k d c 舡v en o d e p a 如re v e wm n - s 曲l r m e de d g et b 前 矿ge ra 谢g i 。f 船舶砌撕p 珊a a o 打v pn o 出： s ：= s u g ，一：= 一u 叮) ，p 4 r e r ( g ) ：= p 矿g = f 胛m 聊尸= p 7 况f e 耐如r r e m o v ep 声o l na e d w f 把 瑁m m p = o 2 ) 增广阶段：这个阶段的输入是一条从a 到卢的路径只此阶段开始时孤结点集是 空的。但是由于p 中至少有一条边变为饱和，此阶段结束时会存在一些孤结点。 扣n d t 沁b o m e 聊c kc a p o c i 秽o n p 婶d a t e t h e ”s t 出矗昏r 印hb yp 懈h n g f m r 帆g hp 扣re d c e 罐弘( p ，g ) 加| d 聃甜6 e c 册蛾，j 。f 甜口招d f 删r e r q ) ：= g a d dq t o o e n d 如r 基于数字蒙太奇的图像编辑方法研究浙江大学2 0 4 2 1 2 3 0 戴芬 3 ) 回收阶段：此阶段中，对孤结点集口中的所有结点进行处理，直到口变为空集。 被处理的孤结点试图在j 中找到新的父结点。如果找到了新的父结点，此结点就继 续留在集合s 中，否则便将其从s 中移出至自由结点集l 并且它的所有子结点都 被添加入孤结点集执 w 以0 o p i c knn o d ep o r e m o v ep o m 0 p r o c e s sp p 耐w 池 操作“口w c e s s p ”包括如下几个步骤：首先，试图为点p 寻找一个新的父结点。 对于每一条非饱和边( op ) ，我们判断g 是否为一个有效的父结点。口应该遵循两 个条件： ( 1 ) g 应该在了中。 ( 2 ) 口应该“起源”于口点。 之所以要检测“口是否“起源”于“点”是因为5 中的有些结点是起源于孤结点 的。 如果找到新父结点函那么p 就留在s 中。p 在占中的主动( 被动) 状态仍然没 有改变。如果p 在s 中没有找到有效的父结点，就执行如下三个操作： ( 1 ) p 从5 ( 和栅中移除，成为，中的一个自由结点。 ( 2 ) 对于p 的所有子结点口，我们设置翩膨m ( 动= 中，并将它们添加入孤结点集 以 ( 3 ) p 的所有“潜在”父结点( g 点在f 中，由此边( 叮，p ) 不饱和) 被加入主动 结点集彳 有必要执行最后一步操作来确保s 中没有被动结点通过非饱和边与自由邻结点 相连。只有主动结点才允许拥有这样的自由邻结点。 2 2 2p o i s s o n 方程及其解法 2 2 2 1p o i s s o n 方程及相关概念 图像编辑主要关注两个问题：颜色亮度修正、滤波、变形等全局变化或选择区 基于数字蒙太奇的图像编辑方法研究 浙江大学2 0 4 2 1 2 3 0 戴芬 域的局部变化。而我们感兴趣的是将手工选择范围的源图像区域无缝地导入目标区 域，从而实现无可见接缝的局部变化。传统的用于解决这些问题的工具包括图像滤 波器( 用于解决局限于选择区域的细微变化) ，以及交互式剪切与粘帖结合的复制工 具( 用于完全的替换) 。然而，利用这些经典的工具时，在选择区域内的变化会产生 可见接缝，即使通过羽化选择区域边缘的方式也只能部分地隐藏。 pe r e z 提出了一种范型方法，此方法所用的核心数学工具是带d i r i c h l e t 边界 条件的p o i s s o n 偏微分方程，d i r i c h l e t 边界条件指定了在影响域内未知函数的 l a p l a c i a n 算子，以及在区域边界上的未知函数值的l a p l a c i a n 算子。使用带 d i r j c h l e t 边界条件的p o i s s o n 方程的理由有两点： 首先，被l a p l a c i a n 算子抑制的缓慢的亮度梯度，能够以几乎不明显的效果被添 加至图层上。 其次，一个标量函数在有界域是由它在边界的值和内部的l a p l a c i a n 算子唯一确 定的。p o i s s o n 方程拥有唯一解。 因此，给予精心设计在某域和其边界条件的未知函数上的l 即1 a c i a n 算子的方 法，就能够数值化地解p o i s s o n 方程来实现其域的无缝填补。p o i s s o n 方程的求解 过程是一种最小化问题：它计算在给定边界条件下厶范式梯度与某指定的向量场( 引 导向量场) 最接近的函数；因此，重建函数时一方面要符合边界条件，同时也要尽 可能严格地遵循引导场的空间变化。 pe r e z 提出了许多引导向量场的计算方法。这些方法在使用方便和性能两方面 都对传统复制工具作出了很大改进。利用这些引导向量场能很好地实现梯度域融合。 同时通过适宜地混合源图像与目标图像的梯度，可以在选择区域清晰地添加透明物 体。此外，这种方法也可以在简单用户交互的情况下自动地添加包含空洞的复杂轮 廓物体。具体实例详见 pe r e z 0 3 。 p o i s s o n 方程和边界条件 p 。i s s 。n 的基本表达式：警+ 等= 妒( t y ) ( 2 5 ) 有三类给定方法的边界条件，分别是： d i r i c h l e t 条件：给出“+ 西上的值( 如图2 7 所示) 图2 7 基于数字蒙太奇的图像编辑方法研究浙江大学2 0 4 2 1 2 3 0 戴芬 图2 - 】4 时延马赛克拼图。第一排是一组描绘一幢楼房坍塌的视频序列的若干帧的图像集。 描绘时间从左向右流，从右向左流的效果( 左中，右中) 。时间还可以被掐绘成从下到上 从上到下( 左下，右下) 。 背景重建( c l e a n p 1 8 t ep r o d u c t i o n ) ：消除一幅图像中的瞬间物体，获得一个 背景清晰的视图，也叫做“c l e a np l a t e ”。如图2 1 5 图2 一1 5 背景重建 基于数字蕺太奇的图像编辑方法研究浙江大学2 0 4 2 1 2 3 0 戴芬 第三章基于数字蒙太奇的图像编辑系统 我们设计了一个数字蒙太奇的图像编辑系统，这个系统涵盖了上章所述几种方 法，实现了背景校准，自动选择区域，交互选择区域，梯度融合等功能，具有比较 全面完整的蒙太奇处理效果。此编辑系统可广泛应用于各种图片的合成处理，包括 选择合成，扩展景深，重光照，运动物体的频闪观测可视化，全景拼图，时延马赛 克拼图，背景重建等。这些操作可广泛应用于动漫原型设计，媒体设计制作，旅游 风景宣传画绘制和人脸整形手术效果预览等领域。也能在旅游业、动漫业和医疗业 中褥到广泛的应用。 3 1 系统架构 我们的数字蒙太奇系统是从一系列源图像开始的，又叫作图像栈。为了达到最 好的结果，源图像通常应该以某种方式相关联。例如，它们可能都具有相同的景像 但是拍摄于不同的光照或者相机位置之下。或者它们可能描述的都是一个变换的场 景，但是相机位置是锁定的并且相机参数是固定的。这些条件的限制就对相机的摆 放提出了一定的要求。当需要一架静止的相机时，最简单的方法是使用个三脚架。 当然如果源图像不能满足这个要求，我们的系统也具有图像校准的功能。 针对蒙太奇图像编辑的特点，设计系统整体框架如图3 1 所示： 图3 一i 数字蒙太奇系统框架 基于数字絮太奇的图像编辑方法研究浙扛大学2 0 4 2 1 2 3 0 戴芬 如上图所示，对于数字蒙太奇系统，首先要求能够由给出的输入图像序列，根 据图像本身的特征和用户的需求进行一定的预处理。然后根据预处理的结果和一定 的图像目标自动生成标记，合成图像。并能通过梯度域融合技术对结果进行优化。 最后是对生成的结果保存。 经过细分后，我们的数字蒙太奇系统的组成应该如图3 2 所示： 图3 2 数字蒙太奇系统组成 预处理可以分为两种，一种是对用户交互处理，包括画笔的采集和种子的生成； 另一种是图像的校准，包括对图像的平移处理稷旋转处理。 标记的生成主要是根据用户的需要或者图像的特征，根据相应的图像目标，在 图像目标的基础上利用图分割最优化实现自动标记生成。从而合成图像。图像目标 也可以分为全局的图像目标，用于非交互式蒙太奇方法，以及局部图像目标，用于 交互式蒙太奇方法。 梯度域融合主要分为实现基本梯度域融合和多标记的梯度域融合两种情况。 3 2 用户界面和操作流程 我们的应用界面( 图3 3 ) 利用了两个主要窗口：一个源窗口，在其中用户能滚 动浏览源图像；和一个合成窗口，在其中用户能看见当前的结果并与之交互。如果 基于数字蒙太奇的图像编辑方珐研究 浙江大学2 0 4 2 1 2 3 0 戴芬 导入了图像库( 即人像合成模块中用到的人像库) ，则还会拥有第三个库窗口，在其 中用户可以浏览并选择库中的图像用于合成。用户可以选择画笔在源窗口中直接进 行交互操作( 对于交互式的情况来说) ，也可以选择菜单项或图标按钮的相应功能， 利用第四章和第五章将描述的各种各样的自动算法对当前图像进行操作处理，从而 生成新的结果。新生成的中间结果也能随时被添加至源图像集内，这样它们也能在 源窗口里被观看并且选择。在我们的系统中，用户经过反复的改进处理创建一幅新 的合成图像。与合成图像相关的标记法的概念在第二章中已有介绍，具体到我们的 应用来说就是一个对于合成图像中的每个象素指定源图的数组。 图3 3 我们的蒙太奇系统界面 对于交互式和非交互式数字蒙太奇来说，操作流程不完全相同，我们通过下面 两个操作流程图分别介绍。具体实现方法和试验结果将分别在第四章和第五章详细 讲述。 基于数字蕺太奇的图像编辑方法研究 浙江大学2 0 4 2 1 2 3 0 戴芬 图3 - 4 交互式数字蒙太奇系统界面和操作流程 图3 4 描述的交互式数字蒙太奇的操作流程。它是一个循环操作的过程。加载 了源图像之后，我们就进入了这个循环操作的过程，循环的第一步是用户利用相应 的系统画笔( 目标背景) 提供简单的交互信息( 如图3 4 所示) ，图中不同颜色的 画笔分别表示用户选择的目标特征点和背景特征点，同时用户还可以绘制一个多边 形来限制系统计算范围。第二步是系统根据用户提供的简单交互信息进行自动快速 的区域选择，选择的结果被自动粘帖至目标图像，我们还可以对选择的区域进行移 动和缩放，将适合的大小放至图像中合适的位置。第三步是系统利用梯度域融合功 能优化结果。交互式数字蒙太奇操作的三介步骤可以循环遥代地进行，直到生成用 户满意的结果为止。 对于人像合成的情况，还可以导入人像库，先在源图像中确定需要替换部位， 然后选择库中合适的替换，经过预处理的相应脸部区域就会被自动地缩放为合适的 大小，糙帖至目标图像中预先确定的位置并融合。此环节可以和区域选择合成环节 交替使用。运用图像库使得大大提高了合成操作的效率。用户还可以用一定的方式 对库中的图像进行检索和更新。 基于数字蒙太奇的图像编辑方法研究 浙江大学2 0 4 2 1 2 3 0 戴芬 人像合成将一系列人像的各个脸部部位拼接并融合，形成一幅新的人像。 见4 4 2 人像库读出库中的人脸部位区域，将其调整大小拼接入 合成图像并融合。 将新图像添加入库删除库中的图像。 对库图像按一定方式检索 非交互扩展景深将一系列源图像的最清晰区域拼接并融合，形成一幅清晰的全 n 貌。见5 4 1 频闪可视化背景重建将系列源图像中出现凡率最多的区域拼接并融 合，形成一幅背景图。见5 t 4 2 频闪合成将一系列中与背景图颜色差别最大的区域拼接并 融合，形成一幅频闪合成图。见5 ，4 2 净图版将一系列源图像的最平缓的区域拼接并融合，形成一幅平滑干 净的图。见5 4 3 下面根据具体实现方法和应用领域的不同，分别讲述了交互式和非交互式数字 蒙太奇的实现方法以及相应的试验结果。 3 0 基于数字蒙太奇豹图像编辑方法研究 浙扛大学2 0 4 2 1 2 3 0 戴芬 单地说，将图g 的边视为最大流通量等于边权重值的“有向水流管道”，最大流就 是指自源端点s 至目标端点r 传输的“最大水流量”【s e d g e w i c k 叭，a h u j a 9 3 。s 至 f 的最大流将使得图中的一些边达到饱和，除去这些饱和的边，便可以将剩余图中 的结点分离为两个不相交的部分，得到的分离结果对应于一条最小切割的分离结果。 4 3 基于p o is s o n 方程的梯度域融合 在一些应用中由于源图像和目标图像有一定的差别，用图像分割的方法也很难找 到很好的接缝，这就会出现拼接赝像( a r t i f a c t s ) 。这时就要用梯度域融合技术进 行处理。 从源图像复制过来的区域颜色不能很好的匹配目标图像的颜色，因此这里的梯度 域融合是这样进行操作的：将复制过来的图像区域视为颜色梯度来源而不是颜色来 源。此颜色梯度被用来形成一个矢量场，然后利用目标图像中此区域周围的颜色值， 将其带入p o i s s o n 方程，用引导插值法求解，从而计算出一幅梯度与此矢量场最匹 配的颜色合成图像。如此便允许我们抚平相邻图像区域的颜色差异。 具体实现过程 梯度域融合的目的是要使得交互图分割能量最小化算法选择的区域边界与外界 边缘颜色相一致，并使得区域内部的颜色梯度尽可能接近选择区域的原先梯度函 我们可以通过离散化并求解带d i r i c h l e t 边界条件的p o i s s o n 方程来实现梯度域融 合。我们在第二章讲述此类p o i s s o n 方程的解法时提到它是计算在给定边界条件下 厶范式梯度与某指定的向量场( 引导向量场) 最近的函数 引导场v 的最佳选择是直接从源图像获取的梯度场。用g 表示此图像，则是在 v = v g 的引导下作插值，于是( 2 9 ) 现在变为： ，= 厶go r q ，w 确，k = 厂i 。( 4 1 4 ) 如同对于数值实现一样，连续的规范转译为：对于所有( p ，g ) ，k = 邑一岛，代入 ( 2 1 2 ) 得： 对于所有p e n ，i | 一一= f + ( g ，一g f ) ( 4 1 5 ) p ”，t l一以嘣1， 把方程( 4 1 5 ) 写为更好理解的形式就是： 基于数字蒙太奇的图像编辑方法研究浙江大学2 0 4 2 1 2 3 0 藏莽 i 一一= ( g ，一毋) ( 4 1 6 ) g ， 2口虬d f 叶 4 ，1 6 方程的左边表示f 梯度的离散解，右边表示引导梯度v 的离散解。此方程 表示：f 的解满足如下条件：一、f 在区域边界a q 上的值等于厂；二、f 的梯度值 等于引导向量场的梯度。结合到我们的情况就是从源图像拷贝致目标图像的选择区 域的颜色值一方面要满足边缘颜色值和目标图像一致，另一方面又保持原有图像的 梯度。因为梯度是一个图像特征( 图像的颜色梯度表示象素的变化情况，我们对一 幅图像求梯度，会发现此图像虽然丢失了颜色，但图像特征仍然存在) 。 通过上面的解释，我们知道了由方程4 1 5 获得的梯度融合工具既保证了源边界 和目标边界的相互依从，又没有破还源图像的特征。因此我们需要通过对方程4 1 5 的求解来最终达到我们的梯度域融合目的。 在方程4 ，1 5 中和表示需计算的内部颜色，是两个未知值；f j 表示p 的相 邻节点的个数， 表示边缘颜色值，( g ，一墨) 表示源图像梯度，这些都是己 t酣-m)叫。 知值。联立所有p e q 的情况，如果把n 离散为m 个点，就可以得到m 个联立方程。 而在这m 个联立方程中只有m 个未知数( 因为p 和q 都表示。内部点，而。内部只 有m 个点，因此p ，q 有大量重复) 。因此方程4 1 5 可解。 由于边界勰形状任意，所以我们必须使用较好的迭代法才能得到解。本文使用 的是连续超松弛的g a u s s s e i d e l 迭代法。详见 金0 2 。 如此设计的基于交互式的p o i s s o n 方程的梯度域融合方法确保了选择 同的图像特征，这样 便达到了局部区域融合的效果。它可以被用来隐藏不合需要的图像特征或在图像中 插入新元素，但与传统的复制相比有更好的韧性和简易性。 44应用及试验结果本节 介绍交互式数字蒙太奇方法的应用：选择合成和人像合成以及相应的试验结果。4 4 1 选择合成 基于数字荣太奇的图像编辑方法研究浙江大学2 0 4 2 1 2 3 0 戴芬 在拍摄集体照的时候，摄影师往往拍摄多幅照片，最后选择最佳的结果。但由于 人物较多，每个人在各幅照片中的表现各不一样很难找到一幅每个人都满意的照 片，这时我们就可以用到本章所介绍的交互式数字蒙太奇的方法，选择每幅源图像 的最佳片断，形成一幅大家都满意的合成照片 同样数字蒙太奇还可以用于卡通画的制作。传统的卡通画都是用人工绘制，而我 们将利用蒙太奇技术从现实世界的图像中获取动漫原型：例如利用照片处理中的选 择合成技术获取一张夸张的动漫人物形象；从而改变原来大众的、单一的动画制作 手段。具体实现过程是：首先用户利用画笔在源图像的最终想获取的部分中简单绘 制具有代表性的象素点；然后在运用了上节所述的k 均值聚类法生成种子的基础上 利用交互式图分割最优化技术，合成一幅用户期望的卡通效果图，最后利用梯度融 合技术优化生成结果。下图分别显示了两幅选择合成效果图：集体照片的选择合成 结果，以及马和天鹅的合成卡通图片。 图4 4 集体照片选择合成示例