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、框架跟符号
本文算法为交替求解全局块优化函数，分两步进行：第一步为搜索损坏区域块的最近邻域块；第二步为根据最近邻域块信息重构。
** 符号**
u :Ω→R^3表示彩色视频内容，Ω为时空域；定义上的某点p = (x, y, t) ∈Ω，则u(p) ∈ R^3为该位置的视频彩色值；H表示损坏区域的数据集，D为正常区域的数据集，Ω= H∪D ，H∩D =∅；N_p表示p点的邻居；以为中心点的视频块定义为3×N 的向量W^p_u =(u(q1)…u(qN)), 其中N个像素属于, q1…qN的顺序事先定义好；
\bar D = {p ∈ D : N_p ⊂ D} 表示正常区域的数据集，且其邻居也在正常区域；\bar H = ∪_{p∈H}N_p表示损坏区域的扩充；d(.,.) 定义为两个视频块的距离，用\phi:Ω→ R^3表示两个块的偏移映射，其中两个块分别位于损坏区域和完好区域，即任取域中的某点，找到\bar D域中最相似的点q，二者对应关系为q = p+\phi(p)。
代价函数：
其中 
用以下两步对公式（2.1）进行优化：
Matching 已知u，对于域中的视频块W_p，利用最近邻域法（nn）在中寻找最佳匹配，找到最近偏移\phi(p)；
Reconstruction 已知偏移\phi，对于像素p∈H，计算新的值u(p)。
3、本文提出的算法
3.1 Approximate Nearest Neighbour (ANN) search
改进的patchmatch算法由三部分组成：初始化；传导(propagation)；随机搜索。
第一次迭代时，随机初始化偏移映射，随后的每次迭代中以上一次的值作为初始化，来取代随机初始化。
传导步骤为激励偏移将好的ANN传播出去。这一步，所有video volume中的位置被扫描。看例子更明白些，中心点p = (x, y, t)的视频块，搜索到最佳匹配W_p+\phi(p)，另外还要考虑W_p+\phi(x−1,y,t), W_p+\phi(x,y−1,t) 和W_p+\phi(x,y,t−1)。如果三个块中有一个到的距离小于到的距离，则偏移替换为新的更优的值。在下一次传导步骤的迭代中，扫描顺序变为W_p+\phi(x+1,y,t), W_p+\phi(x,y+1,t) 和W_p+\phi(x,y,t+1)。
随机搜索为在p+\phi(p)周围，先是以一个大的半径ANN搜索块的优值，然后再逐渐缩小搜索半径，直到第k次迭代时搜索位置为
其中r_{max}为的最大搜索半径，δ_k为三维向量，与立方体[-1,1]x[-1,1]x[-1,1]具有一致分布，ρ∈(0,1)位搜索窗的减小因子，设置为0.5。随机搜索可避免算法陷入到局部最优。
算法1：
3.2 Video reconstruction
我们启发于加权均值的方法，每个像素用以下方式进行重构：
其中，
公式(3.2)为无权均值，当解收敛时，我们只是简单的用贡献块中最好的块修复损坏区域，这相当于将参数σ_p设置为0，即s_p^q约等于1最后的重构公式为：
3.3 Video texture pyramid（没太懂）
通过块距离确定正确的视频块很重要，在图像和视频纹理丰富的地方，找到的相似块往往有歧义。为了解决该问题，本文提出纹理特征金字塔方法，将纹理特征金字塔加入到块距离公式中，以便确定正确的块。
定义二维纹理特征T=(T_x,T_y)，像素p∈Ω的纹理特征为：
其中I_x(q)( I_y(q))为点在x(y)方向的偏导，的纹理特征为导数的绝对值，在其邻居域ν的平均。将纹理特征加入到块距离公式中则为：
特征金字塔是对输入视频u的纹理特征进行二次采样，根据下面的公式可以看出，每一层二次采样获得的信息都会包含金字塔最高层的分辨率。
需要的纹理信息不会存在于金字塔底层，由于平均分布在邻域中，在二次采样时也不会被滤波掉。在本文中邻居域ν默认是固定的，与金字塔最底层相对应，大小为2L−1。然而，更一般的设置，v的大小与金字塔层数无关。基于偏移映射算法，纹理特征如何进行重构并不是一个难题，因为在定义损坏区域像素时已经呈现了一些特点，如颜色、纹理特征或者其他。
类似于公式(3.2)，同样的重构方法来修复纹理特征：
总之，可以将特征看成是纹理描述器来避免我们的算法选择错误的区域进行修复。
3.4 Inpainting with mobile background
对于移动背景的修复，大部分算法是将前景与背景分割，并且在修复时是简单的将对齐后的图像内容复制过去，这就要求图像的重新排列要非常精确，具有很大的局限性。为了避免此问题，我们提出变化的patch-based框架同时进行前景与背景的修复，而不需要将二者分割。
基于块方法的基本假设是块内容是冗余和重复的，而对于增加了时间维度的视频，则意味着一序列的图像块应该是重复的。当视频随机运动时，情况并不是这样。虽然在图像序列中出现某一需要的内容，但是无法保证时空域的块会重复同样的运动。为了解决这一问题，选择一张参考帧，依次对图像帧对进行运动估计，本文参考帧为一序列图像帧的中间帧，然后用插值方法重新排列帧图像[32]，显然损坏区域也重新排列，随后进行视频修复。当修复完成后，再对运动估计进行逆变换将解复制到损坏区域。
算法2：
3.5 Initialisation of the solution
视频修复时采用”剥洋葱”的修复方法，由外到内。每次只修复损坏区域的一层。H′⊂ H为当前待修复区域， ∂H′⊂ H′为待修复区域的当前层；定义邻居N_p′= {q∈ N_p, q \notin H′}。两个块W_p、W_p+\phi(p)的距离如公式(3.6)。如何选择邻居块用来进行重构，我们的实现中，用ANN搜索中心点在损坏区域外的块，重构公式为(3.2)。
算法3：
接下来介绍多分辨率金字塔的实现，算法的参数设置，这里不赘述了。最后给出整体的修复算法。
算法4：
4、实验结果
