VIDEO INPAINTING OF COMPLEX SCENES
VIDEO INPAINTING OF COMPLEX SCENES
Alasdair Newson† ‡, Andr´es Almansa ‡, Matthieu Fradet †, Yann Gousseau ‡, and Patrick P´erez †
摘要:
提出patch-based的全局优化自动视频修复算法,能够处理各种各样视频中自然出现的情况,比如重构动态纹理、运动目标、运动背景,并且计算时间与最好的算法相比少了一个数量级,在高清视频中也取得了一个好的质量效果。该算法除了手动输入视频修复标注外不需要进行分割或者其他操作,可以处理更广泛的多种情况。
1、简介
先进的图像和视频编辑技术越来越多的应用在图像处理和计算机视觉领域中。一个普遍困难的任务是图像视频‘inpainting’,说白了,就是用其他内容替换需要修复的内容,并且视觉上能够接受。在图像修复中,已经进行广泛研究,并且已有商业产品。然而由于视频的时间维度必然会增加修复的时间复杂度,因此在视频修复中的研究还远远不及图像修复。获得高质量的视频修复同样重要,如电影恢复,影视的后期处理,个人应用等。
1.1 前期工作
视频修复算法有基于目标和基于块两类,object-based算法一般将视频分割为移动目标前景和静止或者简单运动的背景。背景修复一般用图像修复方法,而移动的目标尽量平滑的复制到occlusion(损坏区域),然而这类方法有限制性假设,比如严格的周期性。Patch-based方法为将小的视频patch填充到损坏区域,这些块提供了局部纹理,结构和运动的可行的编码方法。
块方法首先被提出并成功的应用在图像修复上,其核心思想为以greedy fashion方式将块复制粘贴到损坏区域,而保证不了解的全局一致性。随后该方法进一步改进,但一个事实是,得到一个好的修复效果前提是将图像很好的分割成移动目标前景和背景。缺少全局一致性是个劣势,尤其是修复移动目标。
另外一种块方法的主要观点为将修复看成是一种标签问题:每一个损坏中的像素跟非损坏区域中的像素相关,最后像素的标签为一个离散的优化过程。该方法的搜索空间跟时间复杂度都很大。
还有一种思想是启发式的迭代求解一个全局优化问题,这样可以保证全局一致性,类似于非局部去噪。
本文参考了non-local patch-based方法。在视频修复中,高维度问题使得此类方法相当慢,尤其是邻域搜索方法,往往要几天时间。本文结合前期的工作,给出一个灵活有潜能的non-local patch-based方法。
1.2 本文的概要跟贡献
- 加速邻域搜索方法,将扩展的Patch-match算法应用在时空域情况
- 提出块距离的纹理特征以正确的修复视频纹理
- 对于明显的运动进行仿射估计来处理移动背景问题
- 仔细的描述了初始化方法
- 给出多分辨率组合实现细节
2、框架跟符号
本文算法为交替求解全局块优化函数,分两步进行:第一步为搜索损坏区域块的最近邻域块;第二步为根据最近邻域块信息重构。
符号
代价函数:
其中
用以下两步对公式(2.1)进行优化:
Matching 已知
Reconstruction 已知偏移
3、本文提出的算法
3.1 Approximate Nearest Neighbour (ANN) search
改进的patchmatch算法由三部分组成:初始化;传导(propagation);随机搜索。
第一次迭代时,随机初始化偏移映射
传导步骤为激励偏移
随机搜索为在
其中
算法1:
3.2 Video reconstruction
我们启发于加权均值的方法,每个像素用以下方式进行重构:
其中,
公式(3.2)为无权均值,当解收敛时,我们只是简单的用贡献块中最好的块修复损坏区域,这相当于将参数
3.3 Video texture pyramid(没太懂)
通过块距离确定正确的视频块很重要,在图像和视频纹理丰富的地方,找到的相似块往往有歧义。为了解决该问题,本文提出纹理特征金字塔方法,将纹理特征金字塔加入到块距离公式中,以便确定正确的块。
定义二维纹理特征
其中
特征金字塔是对输入视频u的纹理特征进行二次采样,根据下面的公式可以看出,每一层二次采样获得的信息都会包含金字塔最高层的分辨率。
需要的纹理信息不会存在于金字塔底层,由于平均分布在邻域
类似于公式(3.2),同样的重构方法来修复纹理特征:
总之,可以将特征看成是纹理描述器来避免我们的算法选择错误的区域进行修复。
3.4 Inpainting with mobile background
对于移动背景的修复,大部分算法是将前景与背景分割,并且在修复时是简单的将对齐后的图像内容复制过去,这就要求图像的重新排列要非常精确,具有很大的局限性。为了避免此问题,我们提出变化的patch-based框架同时进行前景与背景的修复,而不需要将二者分割。
基于块方法的基本假设是块内容是冗余和重复的,而对于增加了时间维度的视频,则意味着一序列的图像块应该是重复的。当视频随机运动时,情况并不是这样。虽然在图像序列中出现某一需要的内容,但是无法保证时空域的块会重复同样的运动。为了解决这一问题,选择一张参考帧,依次对图像帧对进行运动估计,本文参考帧为一序列图像帧的中间帧,然后用插值方法重新排列帧图像[32],显然损坏区域也重新排列,随后进行视频修复。当修复完成后,再对运动估计进行逆变换将解复制到损坏区域。
算法2:
3.5 Initialisation of the solution
视频修复时采用”剥洋葱”的修复方法,由外到内。每次只修复损坏区域的一层。
算法3:
接下来介绍多分辨率金字塔的实现,算法的参数设置,这里不赘述了。最后给出整体的修复算法。
算法4: