（计算机科学与技术专业论文）基于关键帧的视频对象变形技术.pdf

浙江大学硕士学位论文 摘要 本文提出了一种全新的处理视频对象变形的系统。该系统的目的是尽可能的减少 用户的交互，同时提供较高的灵活性和较精确的控制力。它具有基于关键帧的用 户界面。用户仅仅只需要在一些关键帧上将视频对象的形状编辑到目标形状，我 们的算法能自动的将此编辑结果光滑的传播到其余帧上，并生成一段新的视频对 象的视频。该算法能较好的保持视频对象在其原视频中的形状和时问上的相关 性。我们用了各种例子来证明系统的潜在应用力。 关键词关键帧，视频对象，变形。 撕旺大学硬士学位论文 a b s h a c t t h i sp a p e rp 胤 啪a v e ld e f o 皿撕s y s t c mf b f 、r i d o 坳e c t s t ks y s t 鼬i s d e s i 弘e dt o l j _ l l i m i 聆m ea m o 岫to fu s 盯i “c 盯a c t i ，w “l ep r o v i d i n gf l e x i b ka n d p r e c i u s 盯c 咖1 nh 勰ak e y 托帅e 妇du s 盯i 咖f 缸e t h eu s 目o i l l y 玳静d st o m a n i p m a t e 也ev i d e oo b j e c ta ts e v e m lk e y l h m e s 0 u ra l g o r i t h m 、i l l 锄o o t l l l y p r o p a g a t et h ee d i t i n gr c s u hf 如mt l l ek e y f r a m e st ot h er e m a i n i i l gf h m e s 蛐d a 眦o m a t i c a l l yg e n 删et h ci 地w 、，i d e oo b j e c t t h ea l g o r i m mi sa b l et op 坞s e e 龇 删c 慨e 雠i l 够t l i es 1 1 a p e o f l l i ev i d c o 州e c ti l ll b e 喇 v i d c l i p s w 毫d e m m l s 眦m ep c i t e 以a lo fa 皤s y 赋锄谢t l lav a r i e t yo fe x a m p l e s k e y w o r d s v i d c oo 巧c c t ，d c f o n n a t i o i i k e y 丘锄- b 笛c d 浙江大学硕士学位论文图目录 图目录 图1 1 利用两张不同背景进行抠图的例子( a ) 在已知的蓝色背景上进行拍 摄。( b ) 在已知的黑色背景进行拍摄。( c ) 提取出的物体。( d ) 组合到 新的背景中2 图1 2v i d e 00 b i e c tc u t 锄dp 嬲t e 系统流程图3 图1 3n 1 中关键帧编辑作用3 图1 4 对复杂图像对象的抠图4 图1 5 3 1 中对玩具模型的变形编辑4 图1 6 用三维动作数据驱动二维图像变形5 图1 7 视频卡通风格转化技术6 图1 8f 1 1 中卡通风格化示例6 图1 9 通过拖拽控制点对二维图形进行变形编辑7 图1 1 0 基于动态最小二乘的二维图形变形。( a ) 为原始图像。( b ) ( c ) ( d ) 为变形 后图像。其中( b ) 采用仿射变换。( c ) 采用相似变换。( d ) 采用刚性变换。7 图1 1 1 基于非线性最小二乘的二维图形变形8 图1 1 2 视频对象变形技术概览1 0 图2 1 对视频对象的提取。左为包含视频对象的原视频。左中为前景图。右 中为a l d l l a m a s k 图。右为视频对象与新背景的融合一1 2 图2 2 视频对象轮廓跟踪示例1 3 图2 3 轮廓跟踪示例。如大象前腿和企鹅左脚处所示，对于非编辑兴趣区域， 轮廓跟踪不必非常精细1 4 图2 4b e z i e r 曲线离散化。左图为跟踪得到的b e z i e r 曲线。右图为采样后得 到的线段序列1 5 图2 52 d 图形的生成。左图为多边形的指定，右图为2 d 图的生成1 5 图2 6 内部网格的生成1 6 图2 7 左为网格覆盖下的图形。中为初步生成的内部图。右为进行5 次光滑 操作后的2 d 图。1 6 图2 82 d 图的传播1 7 图2 9 控制柄编辑的传播。实体线所示为编辑后的结果。虚线为初始形状及 其在时问轴上的运行轨迹2 l 图2 1 0 非线性2 d 图形变形算法和我们基于降维法算法的比较2 4 图2 1 l 求解控制柄编辑结果传播后的结果2 5 图2 1 2 通过三角化2 d 图进行新视频物体的绘制2 5 图2 1 3 对带自遮挡物体处理的示例2 6 图2 1 4 纹理填充及重采样。左为原始图形，中为编辑后的图形。右为绘制 时采用的纹理2 7 图2 1 5 额外的修边处理的效果。左为未采用额外修边处理的结果。右为采 i i 浙江大学硕一p 学位论文 图目录 用了的结果。可以看出，未采用时手臂轮廓锋利，过渡不自然。处理后 结果令人满意2 8 图3 1 烛火。上行为原始视屏的部分帧。下行为编辑结果2 9 图3 2 茶壶。第一行为原始视频。第二行为提取后的视频对象。第三行为生 成的2 d 图。倒数第二行为对关键帧的编辑( 这个例子就是第一帧) 。最后 一行为最终结果3 0 图3 3 大象。上行为原始视频的部分帧。下行为编辑结果3 l 图3 4 鱼。上行为原始视频的部分帧。下行为编辑结果3 2 图3 5 角色行走的编辑。( a ) 原视频中的两帧。( b ) 编辑结果3 3 i 浙江大学硕士学位论文 第l 章绪论 第l 章绪论 1 1 课题背景 通常意义上，视频编辑的过程为将视频的部分片段进行修改或重排列，以产 生新的视频。很久以来，视频编辑被广泛应用于电影工业界，被视作为产生高质 量视频的必要后续处理过程。 视频编辑也是计算机图像领域研究的热点。 4 ，1 0 ，1 4 ，1 9 开发出一系列的交 互式系统，能让用户将视频对象从其原始视频片断中剪切，提取出来。于是，视 频编辑就可以比较容易的在对象层面进行处理了。其中一个典型的例子就是视频 对象的剪切与复制，即将一个视频对象从其原始视频中剪切出来，然后无缝的集 成到另外一个场景中以达到新的特殊效果。 最近，在对视频对象的编辑方面也有了一定的研究进展。这包括对视频对象 的风格和动作进行编辑。非真实感绘制( n p r ) 技术被推广到了视频上，用来以卡 通风格绘制视频对象 1 ，2 1 。对于动作编辑来说，l i ue ta 1 1 5 提出了一种采 用动作放大技术来使得视频对象的微小移动变为可见，而j u ee ta 1 2 0 则提出 用卡通过滤器来让视频对象的动作变得更夸张，以达到伸展和挤压的效果。 但是直到目前为止，具我们所知，仍然没有一种交互系统能让用户直接编辑 视频对象的形状。因此，对该项课题进行深入的研究是具有一定的开创性，且非 常具有实际应用意义的。 1 2 相关工作 现在已有许多与视频对象和2 d 图形变形的研究成果。本文的工作受到了大 量的前人工作的启发。它们包括，视频对象提取，动画编辑及2 d 图形编辑。在 此，我们仅仅对与我们的视频对象变形系统直接相关的工作进行一番回顾。 1 2 1 视频对象提取 视频对象剪切的最普通的算法当属蓝屏修边技术。很多年以前，该技术就已 被广泛的应用于电影和视频工业界，但其一直受到专利法的保护。直到1 9 9 5 年， p e t r ov l a h o s 的该项专利公开后， 1 8 便于第二年发表了一篇对其进行改进的文 浙江大学硕士学位论文 第1 章绪论 章。其主要思想是，从一幅图中提取出的图像对象可以用两幅图像来表示：带 a l p h a 通道的图像对象的前景图像和背景颜色图像。通过将前景图像和背景图像 根据a l p h a 通道线性混合起来，即可得到组合后的图像。他们通过在两个不同的 背景上( 置，垦1 对同一物体d 进行拍照，来计算出 幺物体的前景色和相应的a l p h a 通道值( 如图1 1 所示) 但是，这种方法受到工作室环境的限制，而且无法对 运动中的物体进行两次拍摄。而将自然场景中的视频对象剪切出来则是一个更具 挑战性的任务。 图1 1 利用两张不同背景进行抠图的例子( a ) 在已知的蓝色背景上进行拍摄。( b ) 在已知的 黑色背景进行拍摄。( c ) 提取出的物体。( d ) 组合到新的背景中。 同时，对静态图像进行区域划分的图像分割技术，比如m e a ns h i f t 和g r a p h c u t ，也被成功推广到自然场景下的视频对象剪切中。在 1 4 ，1 9 中，视频将首 先用图像分割法进行分割，然后采用3 dg r a p hc u t 技术，对视频每一帧中每个 像素点标记其从属于前景或背景。因为g r a p hc u t 是建立在被分割后的图像区域 上的，因此它可以对图像进行像素级的后续处理，从而得到高质量的修边结果。 文 1 9 的系统流程如图1 2 所示。 浙江大学硕士学位论文第l 章绪论 图i 2v i d o b j t c t l | m dp a s t e 系统流程图 另一方面，边界跟踪技术也可以用于将视频对象从自然场景中提取出来。 6 ，1 1 提出主动轮廓线模型( 又称s n a k e 算法) ，它定义为一条在曲线内力和图像 势能场的共同作用下进行形变的参数曲线，它满足能量最小化原则，最终收敛到 目标边缘。然而该算法也存在一定的问题，如对初始轮廓的位置敏感、势场中存 在局部最小、s n a k e 不能收敛至目标边缘的凹陷、对模型参数敏感等。 最近，a g a r w a l ae ta 1 1 提出将空间一时间的优化和用户知道结合起来处 理“r o t o s c o p i n g ”。他们通过对空间时间上的优化，来同时计算视频对象的外形 的动作。这种方法很好的结合了程序的自动跟踪和用户的指导作用。用户可以在 程序优化的过程中随时对生成的结果进行改进，然后继续优化。如图1 3 所示， 第一行显示的是直接用s n a k e 算法进行跟踪的结果。很明显从第2 3 帧开始出现 了不准确的情况，到第4 0 帧则算法完全失效了。而 1 则允许用户在此结果上编 辑第4 0 帧，同时将其设为关键帧，然后系统将会整体进行优化，生成比较理想 的跟踪结果( 第二行所示) 。 图1 3 【l 】中关键帧编辑作用 浙江大学硕士学位论文 第1 章绪论 但是基于跟踪曲线的r o t o s c o p i n g 仍有其不足之处，由于曲线的表达能力有 限，它无法跟踪非常复杂的边界区域( 如图1 4 ) ，同时也无法在边界而上得到像 素级的高质量修边结果。针对这个问题，c h u a n ge ta 1 4 则提出了一种跟踪 t r i 岫p 而不是边界的方法，以生成更高质量的视频修边结果。该方法基于 b a y e s i a nm a t t i n g ，并采用光流技术来指导关键帧之问的t r i 眦p 流动，同时通 过借用相邻帧的背景色来改进t r i i i l a p 。 图1 4 对复杂图像对象的抠图 鉴于我们的系统在跟踪方便并不要求非常高的精确性，而 1 的r o t o s c o p i n g 方法具有良好的交互性及鲁棒性，因此我们的系统在跟踪部分将采用此方法。 1 2 2 图像和视频对象编辑 在图像和视频的对象层上直接进行编辑，用户可以很直观、快速的得到理想 的有意义的结果。因此，这种方法受到了广泛的欢迎。b a r r e t te ta 1 3 提出 了一种基于对象的图像编辑系统，它允许用户对图像中的静态对象进行动画制 作。如图1 5 所示，( a ) 为原始图像，( b ) 为用户指定的各个的图像对象( 手臂， 鼻子，眼睛，嘴巴等) ，( c ) 为编辑后的结果。用户可以直接操作各个图像对象来 直接对图像进行编辑。当图像对象形变后，在原图像上留下的空洞用类似与纹理 合成的方法进行填补。 图1 5 【3 】中对玩具模型的变形编辑 4 浙江大学硕士学位论文 第l 章绪论 最近 7 更提出用3 d 动作数据来驱动图像中的2 d 角色，以直接生成动画。 卡内基梅隆大学的图形实验室在其网站上提供大量的3 dm 0 c a p 数据下载，供研 究人员使用。3 d m o c a p 数据由一系列的人类骨架模型的姿势组成。每个姿势都包 含了各个骨头和连接处在三维空间中的相对位置和朝向。首先系统会重建摄像机 模型，然后用户需选择一种合适的模型初始姿势，再将人类模型的各个连接处与 图像上的对应的像素点对应起来，即可完成3 d 数据和2 d 图像的绑定。之后，系 统会自动计算摄像机投影矩阵，并用3 d 数据库中最匹配的姿势来驱动2 d 图像进 行形变。如图1 6 所示，左图显示了2 d 图像和3 d 动作数据的绑定。中右即为用 3 d 动作数据驱动2 d 图像变形后生成的动画结果。 图1 6 用三维动作数据驱动二维图像变形 与图像对象相比，视频对象较其多了一个时间维度。这直接导致了更复杂的 数据信息，并在技术上带来了新的挑战。视频卡通风格转化技术( v i d e o t o o n i n g ) 2 1 将n p r 推广到了视频对象上。非真实感图形绘制( n p r ) 也是近年来 计算机图形学领域的一个热点。 2 1 运用均值平移( m e a n s h i f t ) 分割技术和均值 平移引导插值技术，来对空间时间相关性的问题进行求解。具体做法为，首先用 均值平移视频分割技术来确定带体积的视频对象集合。然后用户可以在关键帧上 将小的分割片断进行合并，组合成大的有语义的区域。之后，系统会采用均值平 移引导的插值技术，将用户的设定插值到其余帧中。接下来，系统会自动对有语 义的区域和表面进行重建和光滑化。最后，这些带体积的区域将按每帧切片，然 后按照用户指定的风格绘制出来，最终形成具有卡通风格的视频。如图1 7 ，左 为原始视频图像，中右为卡通风格化后的视频图像。 浙江大学硕上学位论文第l 章绪论 图1 7 视频 通风格转化技术 a g a 肼a l ae ta 1 1 也提出了一种n p r 的系统来处理视频对象( 图1 8 ) 。他 们将跟踪获得的轮廓曲线作为平台，由用户用刷子在一些关键帧上随意的进行绘 制。而这些绘制的信息将被自动与r o t o c u r v e s 相关联，并被插值到其余帧中。 图1 8 【l 】中 通风格化示例 l i ue ta 1 则 1 5 展示了一种动作放大的技术，以使视频物体的微小移动 变为可见。他们称之为动作层( m o t i o n1 a y e r ) 。为了提取动作层，他们首先将一 些特征点聚集成相互关联的动作，然后进行图像分割，将像素点标记为不同的动 作层。就在不久前，j u ee ta 1 2 0 提出了一个采用卡通动画过滤器来让视频对 象的动作变得更为夸张，以达到伸展和挤压的效果。 而我们的视频对象变形系统则提供了一种更常规的方法，以方便用户操作视 频对象。 1 2 3 带特征保持的2 d 图形变形 最近，2 d 图形变形算法的也取得了较大的进展。其研究的重点在以下两个方 面：1 用少量的操作生成视觉上令人满意的结果。2 提供一种实时交互式的用户 界面，让用户能立即得到其编辑的结果。 i g r a s h ie ta 1 9 开发出了一种交互式系统，使得用户可以通过操纵几个 控制点( 图1 9 ) 来对二维三角化的图形进行变形编辑。为了达到尽可能刚性的 6 浙江大学硕上学位论文 第1 章绪论 形变 2 ，该方法以每个三角形的形变达到最小作为目标。而解此非线性系统是 比较困难的，为此，他们提出了一种分两部线性化的算法：第一步计算旋转，第 二步计算缩放比例。但是，由于其线性的本质所带来的局限，在某些情况下会产 生并不自然的变形结果。 图1 9 通过拖拽控制点对二维图形进行变形编辑 另一方面，基于动态最小二乘的算法 1 7 并不需要三角化的网格作为图形表 示，因此可以运用到任意的图像上。他们的主要思想是，将形变视为一种从原始 图像到变形后的图像的一种映射函数f 。将此函数作用到原始图像上的每个点， 既可以产生变形后的图像。现考虑原图像上的控制点集合p ，然后用户拖拽到新 的位置q 。那么合适的f 必须满足：i f ( p i ) = q i ，i i f 的结果必须光滑，i i i q i = p i = f ( v ) = v 。 图1 1 0 基于动态最小二乘的二维图形变形。( a ) 为原始图像。( b ) ( c ) ( d ) 为变形后图像。其中( ” 采用仿射变换。( c ) 采用相似变换。( d ) 采用刚性变换。 w e n ge ta 1 2 2 提出的二维图形变形算法是用非线性的最小平方优化方法 来求解变形结果。它试图保持原2 d 图形的两个几何属性：图形边界曲线上的拉 普拉斯坐标，和图形内部的局部面积。该系统能够以实时的速度产生物理上看似 真实的变形结果。因此，我们将此变形方法运用在我们系统内的关键帧编辑中。 7 浙江大学硕上学位论文第1 章绪论 嘲1 1 l 基丁- 1 f 线性最小二乘的二维图形变形 最近，也有一种研究趋势是将静态3 d 网格的编辑方法推广到对网格动画的 编辑上 1 2 。2 3 。我们的工作也受到了此趋势的启发，我们的工作是试图将静态 图像的编辑方法推广到对视频对象的编辑上。如前一章所述，这给我们带来了一 些技术上的挑战。 1 3 技术目标及挑战 在本文中，我们提出了一种新的视频对象变形系统。它具有以下特点： 基于关键帧的编辑：我们的系统提供基于关键帧的用户界面。用户只需在一 系列的关键帧中，如传统的图像变形操作一样，通过操作控制柄对视频对象 进行变形。我们的系统能够将编辑结果从关键帧光滑的扩散到其余的帧中， 然后在每一帧中采用二维图形变形算法对物体形状进行变形，从而产生一个 全新的视频对象。 时间一致性保持：我们的算法能够很好的保持视频物体在其原始视频中的时 间一致性。 形状特征保持：我们的算法能够在生成令人满意的变形结果的同时，保持其 原有的形状特征。 为了开发此系统，我们需要解决以下问题： 首先，我们需要一个视频对象几何外形的表达方式。和静止图片不同的是， 视频对象其本质是动态的。它的形状会随着时间改变而改变。我们首先利用最近 的交互式视频物体剪切工具 1 4 ，1 9 来将视频物体从其原始视频中提取出来。然 后采用基于关键帧的轮廓跟踪技术 1 ，用b e z i e r 曲线来确定每帧中视频对象轮 廓的位置。我们便用这些边界曲线所围的区域来表示原视频对象的形状。 然后，为了保持视频对象时间上的一致性，关键帧的变形编辑结果必须被光 滑的传播到其余帧中，从而使得视频对象在整个视频中的形变是连贯的。在每个 s 浙江大学硕士学位论文 第l 章绪论 关键帧中，用户通过拖拽控制柄来对视频对象进行编辑。我们采用基于最小二乘 的控制柄传播算法来将控制柄光滑的传播到其余帧中。然后，运用二维图形变形 算法对每帧图像进行变形。该控制柄传播算法能很好的保持时问上的一致性。因 为它力图达到最小化的能量方程表达了控制柄在原视频中的时间上的运行轨迹。 最后，虽然在交互式二维图形变形中，非线性二维图形变形算法 2 2 已能产 生不错的结果较好的保持细节特征及物理上看似真实。但当将其直接应用于 采用扩散算法更新后的控制柄的约束时，我们仍发现了其稳定性存在一定的问题 ( 图2 1 0 ) 。这是因为其变形求解器求出的结果并非全局最优的，而由于控制柄在 其余帧上较大的突变，其可能求出一个并不好的局部最优解。这不同与交互式编 辑中，用户用鼠标进行光滑的拖拽。 受到子空间( s u b s p a c e ) 方法 2 2 的启示，我们提出一个将形变能量映射到由 b e z i e r 曲线控制点所组成的子空间上的一种降维方法。在子空间上进行能量优化 能极大的提高非线性变形过程的稳定性和收敛性。从而产生更为理想的变形结 果。 1 4 技术概览 我们的视频对象变形系统共包含5 个步骤( 见图1 1 2 ) ，具体描述如下： 1 视频对象提取：给出一段输入视频，我们首先采用基于图像分割的视频对象 提取技术【1 4 ，1 9 】，将视频中的前景物体与背景分离出来。于是我们得到了一 个仅仅包含前景物体的图像序列，图像文件中利用a l p h a 通道来标识每个像素 的o p a c 酊。同时，基于关键帧的r o t o s c o p i n g 技术也能进行视频对象提取处理， 我们将用此技术来区分视频对象不同的特征部位，亦即提取视频对象的特征 区域。 2 视频对象参数化：在对视频对象进行变形编辑时，为了使用户的编辑结果在 每一帧上都能作用到视频对象相同的特征部位，我们需要对视频对象各特征 部位的轮廓进行跟踪标记。在这一步中，我们采用基于关键桢的r o t o s c o p i n g 技术 1 来跟踪前景图像f i 中视频对象的轮廓。之后，我们将得到的b e z i e r 跟踪曲线迸一步组织成一些多边形，并在多边形内部插入一些顶点以组成一 个连通的2 d 图( 第4 1 节中将详细描述) 。最后，我们得到了一个2 d 图形序 列： s i ，i = 1 ，n ) 。 3 关键帧编辑：将视频对象形状参数化之后，用户可以选择该段视频中的任意 一帧来进行2 d 形状编辑。而被编辑过的那一帧将变为关键帧。在编辑过程 9 浙江大学硕上学位论文第l 章绪论 中，用户仅仅只需要设定一些变形控制柄，然后移动这些控制柄移动到新的 地方即可。2 d 形状变形算法将自动的将形状进行变形。 4 控制柄编辑结果的传播：有了用户在关键帧上编辑过的控制柄的结果，控制 柄编辑结果扩散算法将采用最小二乘能量函数来计算出每一帧中的控制柄编 辑结果的目标位置。 5 新视频的产生：在这一步中，我们将对每一帧运用2 d 形状变形算法进行计算。 得到的2 d 形状变形结果将满足控制柄新的的目标位置。用原始前景图像做纹 理，我们便可以绘制新的2 d 图形以获得编辑过后的前景图像。此时，这已是 一个新的视频对象了，它将可以被组合到任意新的背景视频中而得到一段新 的视频。 iv 妇婚删耐铷啪t 啊 v i 出。确e c t s h a p e 9 e r 垃j 。n d e 亿m 诒 p r 蹲跨越黼 q qqc 3c )o 图1 1 2 视频对象变形技术概览 跟踪在计算机视觉中是一个非常具有挑战性的任务，因为通常视频中的动作 i o 浙江大学硕士学位论文第l 章绪论 都是非常复杂的。在本系统中，我们通过跟踪前景图片来减小跟踪的困难度。最 后，我们的系统也支持带有自遮挡的视频对象的变形。为此，我们允许将一个视 频对象建立为多个多边形图形的组合。每个多边形可以遮挡其余任意多边形。第 2 章将对此进行详细描述。 我们将在实验结果章节中证明，我们的系统简单易用。而且能够处理拓扑非 常复杂的视频对象。 1 5 本章小结 本章将与我们的视频对象变形系统直接相关的工作进行一番回顾。它们包括 视频对象提取，轮廓跟踪，图像和视频对象编辑，二维图形变形等。这些研究成 果对我们的研究工作起了极大的指导和帮助作用。本章同时对我们的视频对象变 形系统进行了一个总体上简要的描述。它共包含5 个步骤：视频对象提取，视频 对象图形参数化，关键帧的变形，控制柄编辑结果的传播及新视频的产生。该方 法在尽可能的减少用户的交互的同时，能提供较高的灵活性和较精确的控制力。 本文以下部分如此安排：第二章将详细介绍我们整个视频对象变形系统的所 有算法细节。实验结果在第三章中给出。最后，我们将在第四章中总结和讨论未 来工作。 浙江大学硕上学位论文 第2 章基于关键帧的视频对象变形系统 第2 章基于关键帧的视频对象变形技术 2 1 视频对象的提取及轮廓跟踪 1 视频对象的提取 目前，市面上出售的和网络上容易获得的视频资源都是前景和背景混合形式 的。能够直接进行使用的视频对象的资源很少。如果想要对绝大多数的视频中的 视频物体进行编辑，则需要对原视频片段进行预处理，即将视频对象从其所属视 频中剪切，提取出来。这一部分的工作，被称之为视频对象的提取。 正如我们在相关工作中所提到，视频对象的剪切与提取是计算机图像中的一 个非常热门的研究领域。目前已研究并开发出不少较为成熟的方法。在这里我们 采用的是类似 1 4 的方法来完成这一步。其方法是基于关键帧的：我们首先在一 些关键帧上运用工具对视频对象的前景和背景进行划分。然后，他们的算法能自 动根据关键帧中的结果，对其余每一帧进行前景和背景的划分，同时提供工具让 用户对不满意的地方进行修改。这里需要指出的是，现在在单帧上对视频对象剪 切和提取的工具已非常成熟。l a z y s n a p p i n g 和p h o t o s h o p 中的套索技术都已能让 初学者快速的会学使用并生成出理想的结果。 图2 1 显示我们对视频对象进行剪切和提取后的结果。在绘制时，根据每个 像素的a l p h a 标记，将前景图的颜色和新的背景图的颜色进行混合，产生的新的 图像便是将该视频对象放入新的背景中的结果。 图2 1 对视频对象的提取。左为包含视频对象的原视频。左中为前景图。右中为a l p h am 私k 图。右为视频对象与新背景的融合。 2 轮廓跟踪 有了视频对象之后，我们便可以不受其原背景干扰的对其进行编辑操作了。 但是，对于同一个视频对象而言，其在不同帧中的几何形状和位黄通常是不同的。 浙江大学硕士学位论文第2 章基于关键帧的视频对象变形系统 而对视频对象关键帧进行的变形编辑，我们将通过控制柄传播算法自动计算出的 其余帧应有的变形编辑结果。而对于这些编辑结果，我们则期望其与关键帧上的 编辑具有相同的含义。因此，我们需要将不同帧中，视频对象具有相同特征关系 的部位统一对应起来。 在这里，我们采用同样基于关键帧的r o t o s c o p i n g 技术来跟踪前景图像中视 频对象的轮廓和特征部位。我们首先在一些关键帧上人工绘制一系列的b e z i e r 曲线，用来标识期望编辑的区域的边界。然后，i 幺跟踪算法将在剩余帧中计算出 b e z i e r 曲线的最优位置，同时较好的跟踪到特征区域的边界。该系统也提供易用 的工具，方便用户修改系统自动生成的不理想的局部结果。图2 2 给出一个跟踪 的示例。 图2 2 视频对象轮廓跟踪示例 由于现实生活中，视频对象的动作都是极其复杂的。因此完成高质量的跟踪 比较困难。由于我们已经提取出了视频对象的前景图，因此可以大大降低跟踪的 困难度。其具体表现在两个方面： 1 我们可以采取在蓝屏背景上跟踪视频对象，这样跟踪算法将不会被复杂的背 景所影响，对视频对象边界轮廓的跟踪成功率和精确度将得到极大提高。 2 用户只需精确的跟踪期望编辑区域，而其他部分大致跟踪即可。因为有a l p h a 标记的存在，用户不必担心在绘制时，视频对象的边界上会带有不相关的背 景信息。但至少需保证生成的2 d 图形完全覆盖原视频对象( 如图2 3 ) 浙江大学硕士学位论文第2 章基于关键帧的视频对象变形系统 图2 1 3 轮廓跟踪示例。如大象前腿和企鹅左脚处所示，对于1 f 编辑兴趣区域，轮廓跟踪不必 非常精细。 2 2 视频对象的图形表示 正如之前所描述，轮廓跟踪算法得到的结果是每一帧中b e z i e r 曲线所在的 位置。而b e z i e r 曲线是无法直接用来对图形进行变形编辑的。为了满足2 d 图形 的变形要求，我们仍需将此视频对象对应的b e z i e r 曲线构造成为2 d 图形表示。 在构造2 d 图形时，必须注意以下两点： 幻在每一帧中，该2 d 图都应保持其原视频对象的特征的一一对应。 b 1 在每一帧中，该2 d 图都应具有相同的拓扑结构。 如果让用户来在每一帧中指定和构造对应的2 d 图形，其过程将是十分繁冗 复杂的。我们的做法是，让用户在第一帧中对视频对象构造一个2 d 图，我们的 算法将自动将此2 d 图传播到其余帧中，并同时满足上述两个要求。 本节将详细描述如何根据由轮廓跟踪算法得到的一系列的b e z i e r 曲线，来构 造出相应的视频对象的2 d 图表示。该过程主要分为以下几步： 1 b e z i e r 曲线参数化 如图2 4 所示，由轮廓跟踪算法得到的行走茶壶的边界是由一系列的b e z i e r 曲线表示的。在本文中，我们采用三次b e z i e r 曲线表示法： g o ) = 异( 1 一f r + 3 只，( 1 一r ) 。+ 3 b ，2 ( 1 一，) + b f 3 ， ( 2 1 ) 其中p 表示控制点，f o ，1 1 为标量参数。 然后，我们对每条b e z i e r 曲线进行离散化。使其成为一些互相连接的线段 序列。在采样时，采用统一的步长，并包含曲线收尾两端。在离散化之后，我们 便得到了一个由一系列的线段组成的2 d 图形。 1 4 浙江大学硕上学位论文第2 章基于关键帧的视频对象变形系统 图2 4b e z i e r 曲线离散化。左图为跟踪得到的b e z i e r 曲线。右图为采样后得到的线段序列。 2 多边形的指定 为了定义图形的内部区域，用户需要指定视频对象各个部分对应的多边形各 由哪些线段所组成。如 图 所示，我们将表示茶壶的那些线段组织成4 个多边形， 它们分别对应茶壶的嘴( 紫色) ，身体( 绿色) ，壶腿( 浅红) 和茶壶柄( 棕色) 至此，我们得到了一个由一些多边形所表示的2 d 图形。 3 2 d 图的生成 在这一步中，我们的系统会自动在各个多边形中插入一些内部点，使其组成 一个连通的2 d 图。这样，我们就能够用2 d 图形变形算法对其进行变形编辑了。 图2 52 d 图形的生成。左图为多边形的指定，右图为2 d 图的生成。 下面我们将详细介绍如何在多边形内部插入顶点，并使其组成连通图。生成 2 d 图主要分为以下几个步骤： ( 1 ) 在多边形所包含的区域中分布一系列的网格点，使整个图形处于网格覆 盖范围，如图2 7 左； ( 2 ) 删除处于多边形外部的网格点，并将网格点与多边形边界上相近的点连 接起来： a ) 首先沿着每条网格线找到这条网格线与多边形的交点p 。处于两交点间 浙江大学硕士学位论文第2 章基于关键帧的视频对象变形系统 的线段上的网格点即为多边形的内部点。将所有相邻的内部点按原邻 接关系连接起来，即生成了多边形内部的网格。 b ) 同时对多边形轮廓上包含p 的线段l ，将l 的两端点分别与较近的合适 的内部点连接。这样就得到了初始的2 d 图。 船 图2 6 内部网格的生成。 ( 3 ) 最后，将生成的2 d 图光滑化： a ) 记所有内部边的平均长度为a v e l ，给图内的每个顶点标记一个权值 g = ( 1 _ m i n l a v e l ) ，其中m i n l 为与该顶点相连接边的最小的边长。 b ) 将所有的顶点按其权值排序。将最大权值得顶点提出，更新其坐标为 相邻所有点的中心，同时更新权值。 c ) 重复b ) 操作直至所有权值接近l 止。 图2 7 左为网格覆盖下的图形。中为初步生成的内部图。右为进行5 次光滑操作后的2 d 图。 形式上，我们用( 矿，占o ) 来表示这个2 d 图。其中，矿表示图中n 个定点的集 合，表示图中所有边的集合。y o 由两部分组成：一，包含图形边界上的m 个 顶点；和彬，包含图形内部的n - 珊含顶点。根据中值坐标定理，对每个多边形， 彬可以直接的用碟来表示： 哆= 螺哆， ( 2 2 ) 其中，m 是中值坐标的矩阵。 6 雾雾 浙江大学硕士学位论文第2 章摹于关键帧的视频对象变形系统 4 2 d 图的传播 传播算法相对比较简单。由于跟踪得到的b e z i e r 曲线在每一帧中的是一一 对应的，因此根据第一帧中生成多边形( 即嵋) 时所使用的参数，我们可以采用 同样的参数自动的生成其余帧中的多边形。此时，我们得到了与曙对应的吃。 对于内部点而言，我们直接原样复制第一帧中内部点和边界的拓扑信息。对内部 点的位置，同样采用第一帧中使用的中值坐标肘。来计算： 圪= 肼。圪， ( 2 3 ) 通过以上步骤，视频对象的形状已经表示为一系列的2 d 图了 y o ，e o ，i = 1 ，n 这些2 d 图在拓扑结构上是一致的。它们的区别在与各个顶点在每一帧 中的位置不同。现在，我可以采用类似与 2 2 的算法，来对此2 d 图进行变形操 作了。图2 8 为经过传播后的部分帧的2 d 图，注意它们是拓扑同构的。 2 3 关键帧的变形 图2 82 d 图的传播 如前所述，对于关键帧的变形编辑，我们采用类似【2 2 】中的变形算法。这里 简要介绍如下： 2 3 1 约束介绍 1 局部特征保持 为了保持2 d 图中的局部细节特征，这里通过保持原始顶点的拉普拉斯坐标来 实现。与三维情况类似，2 d 中每个顶点v f 的的拉普拉斯坐标点可以表示为e 和它 邻接点的平均值的向量差： 瞑= 上( v i ) = q 一( v f 一。+ _ ) 2 ， ( 2 4 ) 其中，叶一。和h + 。表示在曲线中与顶点v 相邻接的顶点；被称为曲线的拉普拉斯 1 7 浙江大学硕士学位论文第2 章基于关键帧的视频对象变形系统 算子。为了，在变形过程中保持拉酱拉斯坐标，需要将f 列能量方程最小化： 怜( v f ) 一硝， ( 2 5 ) 叶0 其等价的矩阵形式是： 0 厶巧一万( ) n ( 2 6 ) 其中匕表示原多边形中顶点的坐标值。工，为一个小所矩阵，称为拉普拉斯矩阵。 艿为拉普拉斯坐标向量。为了简化描述，在三中插入零元素，将矩阵扩展为m 栉 的矩阵三，上述可重写为； 0 矿一艿( y ) 2 ( 2 7 ) 2 中值坐标( m e 柚v a l u ec 0 0 r d i n a t e ) 对k 中的每个顶点h ，这里通过中值坐标来其与邻接点的相对位置关系。为 此，先计算中值坐标： m ，j2 ( 2 8 ) 其中，q 是向量哆一和+ 一v j 的夹角。将所有的m ，按其总和归一化之后，即 得到该点相对与其邻接点的中值坐标。根据中值的属性，有： h 一m 匕= o ，f 0 。v ( 2 9 ) ，j e 占 其矩阵形式为， t k = o ， ( 2 l o ) 其中收是一个0 一m ) ( h 一所) 的矩阵同样在矩阵中插入零元素，将肘。扩展为 ( 胛一肼) ”的矩阵肼。于是，可以采取最小化以下能量方程来在变形过程中保持 中值坐标： 0 n ( 2 1 1 ) 3 边长约束 注意到由于中值坐标不受到缩放影响，因此其不足以保持多边形的局部面 积。所以这里还要加一个保持边长的约束。关于边长的能量方程如下： 。孙) 一p ( 圳l 亿蚴 伪一 堑 避刊哟百 q 一 叫一 浙江大学硕士学位论文第2 章基于关键帧的视频对象变形系统 其中e ( q ，_ ) = 笋( v j 一_ ) ；o 是变形后边( i ，歹) 的长度，t 是变形前的长度 u 其矩阵表达形式如下： 0 月y f ( 矿虮 ( 2 1 3 ) 其中日是一个i 乓卜一的矩阵 2 3 2 采用非线性最小二乘优化的变形算法 综合上一节的内容，总的变形能量方程如下所示： l 仁矿一万( y ) 1 1 2 + 0 f 矿0 2 + 0 日y p ( y ) 1 1 2 + i i c y u i j 2 ， ( 2 1 4 ) 其中，y 是2 d 图中点的位置，忙y 一艿( y ) 旷是保持拉普拉斯坐标的能量式， 0 1 1 2 + l | 士一p ( 矿) 1 1 2 对应于局部面积的保持，i l c 矿一( ，1 1 2 则表示控制柄中点的位置 约束。c 是一个l s l x n 的矩阵，且【，是一个s 元的向量，表示用户控制点的目标 位置。上述能量式可以简化成如下公式： 吨n l 阻矿一6 ( 矿) 1 1 2 ( 2 1 5 ) 其中： 4 = 三 肼 日 c ，6 ( n = 万( n 0 p ( 功 u 因为彳仅仅依赖于原始2 d 图，而6 仅由当前顶点的坐标值y 决定。因此这是 一个非线性的二乘问题。下面将介绍如何使用一个迭代的高斯牛顿方法 2 2 来直 接解此问题。重写公式( 2 1 5 ) ， i 卿1 4 矿“1 6 ( 矿) ， ( 2 1 6 ) 其中，是第k 次迭代后的顶点坐标，y “1 是我们希望在第k + 1 次迭代中求出的 顶点位置坐标。6 ( 矿1 在当前迭代步骤中是已知的，因此我们可以通过求解一个 线性系统来求解等式( 2 1 6 ) ， 矿“= ( 4 7 _ ) 一彳7 6 ( 矿) = g 6 ( ) ( 2 1 7 ) 其中，g = f 彳1 - l 。因为4 仅仅依赖于原始2 d 图，而g 可以在变形前预处理 1 9 浙江大学硕士学位论文第2 章基于关键帧的视频对象变形系统 好，并在整个变形过程中保持不变。因此，每次迭代只需一个回代。6 可以由最 近一次迭代得到的求的。p ( 矿) 用下列公式计算： r p ( 矿，t ) 2 南( t t ) 巾r ( “) 乓 像埘 艿( ) 的计算比较复杂，需要先为每个顶点计算一个变换矩阵彳： 艿( t ) = 才占) ( 2 1 9 ) 其中艿( 口) 是曲线变形前的拉普拉斯坐标。现在将口和t 看作旋转中心，转换矩 阵彳可以通过最小化下面的能量方程来求得： ，i k ( 口一砰) 一( 嘭一霄) f ( z z o ) u 】e ” ” 令对矩阵砰中的各项导数为零，可以得到： 私( ，毛( t 时) ( 口一口) 【。，毛( 口一口) ( 口一口) 7 j( o 知耳k ( ，) e 昂， ( 2 2 1 ) 至此，给出了利用非线性最小二乘法计算二维图形变形结果的算法全部细节。 同时【2 2 】也提出了可以通过向能量方程中加硬性约束束保持全局面积。这里 就不详细介绍了，具体方法请参阅其论文。 2 4 控制柄编辑的传播 如技术概览中所讲，我们只需用户在一些关键帧上对2 d 图进行变形编辑。 之后，我们的算法会将此变形的编辑操作自动的传播到其余的帧中。本节将详细 描述该传播算法。 ， 在关键帧编辑操作中，用户选择一些点作为变形的控制柄，然后拖拽这些控 制柄到新的位置。这些新的位置将会作为位置约束来驱动2 d 图的形变算法。因 此，为了使得每一帧的2 d 图都能进行相应的合适的形变，我们需要一个控制柄 编辑的传播算法，将关键帧中用户对控制柄的编辑结果光滑的传播到其余帧中。 为了在传播过程中，保持控制柄在原2 d 图序列中时间上的相关性，我们将控制 柄的传播转换为类似与最小二乘优化的问题。 一个控制柄可能包含一个或多个相关的顶点。我们对每个控制柄定义一个唯 一的局部标架，使得该控制柄中所有的顶点都服从相同的刚性形变。这样可以避 浙江大学硕上学位论文第2 章基于关键帧的视频对象变形系统 免控制柄的形状在变形过程中发生严重的扭曲。 形式上，我们将第k 帧中用户指定的控制柄i 表示为： 研= 群，p ， ti ，= o ，q 一1 ) ) 。其中 1 ：i _ ，= o ，q 一1 ) 表示控制柄中点的集合， 一和p 的列定义了局部标架的中心和坐标轴。0 可以是控制柄的几何中心，而 初始坐标轴可以为任意的，因为我们仅仅只考虑初始坐标轴和改变后的坐标轴之 间的旋转量。 这里需要指出的是，一旦用户在一些关键帧上指定了一些控制柄，我们可以 根据这些控制柄所包含的顶点的索引，很容易的得到其余帧上相应的控制柄。因 为每一帧中的2 d 图都具有相同的拓扑结构。 每一帧中相应的控制柄的中心0 在时间域上形成了一条曲线，同时局部标架 f 与每个中心相关联。 图2 9 控制柄编辑的传播。实体线所示为编辑后的结果。虚线为初始形状及其在时间轴上的 运行轨迹。 每个控制柄的时间相关性可以表示为，每个中心在其相邻帧的局部标架下的 旋转不变坐标。详细描述为，对每个中心矿，我们可以计算其在原动画序列中的 旋转不变坐标： 0 一一= 只矿“， ( 2 2 2 ) 其中表示与t 相邻的控制柄的序号，l l 2 ，钟“表示r 的旋转不变坐标。 显而易见，西“是0 在其相邻控制柄的局部标架下的坐标。 正是因为矿“表达了原视频中控制柄的时问相关性，因此在控制柄传播过程 浙江大学硕士学位论文第2 章基于关键帧的视频对象变形系统 中，我们想保持一不变。于是，我们为控制柄的传播建立了一个二次的能量方 程： l 阿一爿一t 。影“ ( 2 2 3 )