AV1中可变块大小的OBMC(variable block-si

2019-05-03 本文已影响2人 smallest_one

1. 参考

[1] VARIABLE BLOCK-SIZE OVERLAPPED BLOCK MOTION COMPENSATION
[2] M. Flierl, T. Wiegand, and B. Girod, “Video codec incorporating block-based multihypothesis motion-compensated prediction,” Proc. SPIE 4067 Visual Communications and Image
Processing, May 2000
[3] H. Watanabe and S. Singhal, “Windowed motion compensation,” Proc. SPIE Conf. Visual Commun. Image, vol. 1605, pp.
582–589, 1991
[4] M. T. Orchard and G. J. Sullivan, “Overlapped block motion compensation: An estimation-theoretic approach,” IEEE
Transactions on Image Processing, vol. 3, no. 5, 1994
[5] J. Zhang, M. O. Ahmad, and M. N. S. Swamy, “Overlapped
variable size block motion compensation,” Proceedings of International Conference on Image Processing, vol. 3, pp. 642–
645, 1997.
[6] Y. Chen, T. Wang, Y. Tseng, W. Peng, and S. Lee, “A parametric window design for OBMC with variable block size motion
estimates,” IEEE International Workshop on Multimedia Signal Processing, pp. 1–5, 2009
[7] S. Park, S. H. Kim, C. Kim, and S. Lee, “Adaptive windowing technique for variable block-size motion compensation,”
Proc. SPIE 5308 Visual Communications and Image Processing, 2004
[8] T. B. Terryberry, “Adaptive motion compensation without
blocking artifacts,”
[9] G. Bjontegaard, “Improvements of the BD-PSNR model,”
VCEG-AI11 ITU-T SG16 Q.6 Document, July 2008.

2. 概述

本文是对[1]的一个学习。

针对基于块复制的算法在压缩真实视频时效率低下，[1]针对AV1编码提出了重叠块运动补偿算法(OBMC)。

通过为高级可变块大小的分块框架设计良好的重叠方案，分配给周围块的运动矢量将有助于预测当前块。
为了有效地结合所提出的工具，对编码器进行了优化，采用适当的早期终止来管理复杂度，并结合加权运动搜索来处理重叠预测中的非均匀加权失真。
此外，作为一个扩展，通过重新安排解码操作，使非因果重叠利用下方和右侧块的运动矢量。

3. OBMC介绍

背景

块匹配在自适应亚像素插值和运动矢量参考等特点的补充下，能够有效地处理均匀的平移运动。
但由于摄像机和物体的运动复杂，以及运动物体形状不规则、不能完全分割的特点，自然视频信号中帧间的时间关系往往被低估。
尽管许多计算机视觉算法可以很好地分析运动和分割，但在视频压缩场景中，传输精确模型的比特成本或用于模型估计的计算仍然阻碍了这些技术的应用。
为了克服基于块的单参考预测过于简化的问题，在不改变时间预测的基础上，提出了多假设运动补偿算法，将多运动补偿预测叠加在一起，如双向复合预测、两个以上参考的复合预测等。参考文献[2]和重叠块运动补偿（OBMC）[3，4]。
在H.263时代提出并实现的重叠块预测在很大程度上减少了预测误差。

思想

假设帧被划分成相同大小的块，并且每个块都分配了自己的运动矢量，OBMC通过在每个扩展运动补偿块的每个块中心应用在每个块中心的钟形遮罩并加上加权预测，在4个相邻块的中心之间创建平滑的组合预测。

挑战

可变块大小分块和混合内嵌编码带来的复杂性，该技术在最近的文献中并没有得到广泛的应用。

OBMC的发展

[5]使用可变块大小的帧实际上被划分为最小的块大小，以使标准OBMC适用于一般情况。
在其他工作中，每个像素位置不同预测器的滤波系数与原始预测单元到中心的距离成反比。在此基础上，[6]将当前的预测器与靠近左上角或左下角的一个最近的预测器相结合，实现了因果OBMC，[7]支持与4个边缘相邻的两条或更多的邻边的混合。
- 这种距离调制权值对SIMD优化不是很友好，因为距离和权值需要逐像素实时计算，而且通常权值分布不均匀。
在[8]中，OBMC是在Daala编解码器的分块框架中实现的，该框架被限制为使用递归权值计算进行工作。
值得一提的是，之前的大部分工作，特别是对于4-sided OBMC[3,4,5,7]，都将OBMC应用于整个帧，假设所有块都是内部编码的，因此限制了编解码器的灵活性。

新思路

[]首先回顾了因果OBMC技术，并提出了一种实用的基于两阶段一维滤波的加权机制，可以很容易地适应先进的划分框架。
在一个扩展实验中，为了最大限度地利用分配给未来块的运动向量进行重叠预测，重新设计了编码过程来解决非因果OBMC (NCOBMC)中的非因果参考问题。
这些工具被作为额外的选项添加到帧间预测中，与现有的其他工具在RDO循环中竞争，并辅以有效的早期终止以实现可管理的编码复杂性。
通过加权运动估计对重叠预测进行优化，其设计与OBMC中的滤波完全一致。

4. 可变块大小的OBMC

高级编解码器利用可变块大小分块来将各种编码工具放入适当大小的矩形区域。
最常用的方法是递归四叉树分解，这是一种通用的框架，可以直接在静态和较大的区域操作，以节省比特流开销，或者向下到小的角来匹配对象的形状。
然而，另一方面，这种灵活性引入了块周围区域可能的分块模式数量的显著增加，使得块之间的交互，比如通过2D掩码组合预测块，尤其是对于当前块和很多邻块的情况在codec中很难去定义和实现hard-code。
因此，在[1]的OBMC框架中，为了避免直接定义任意分区邻域的2-D掩蔽的复杂性，提出了一种渐进的一维重叠算法。它在水平方向和垂直方向上分别使用1-D滤波器进行操作，每个周围的预测器都在一个有限的区域内工作，该区域不会与其他预测器的预测器发生严重冲突。

4.1 用于可变块大小编码的因果OBMC

该算法首先将重叠预测初始化为基本预测，并将运动参数分配给当前块。
- 对于一个N × M的预测单元，令 $p_i(x, y)(0 ≤ x < M, 0 ≤ y < N)$ 表示当前块(i = 0)中像素的预测块，使用块i的参考和运动向量组合计算，因此初始化 $p_{obmc}(x, y)$ 为 $p_0(x, y)$ 。
- 注意，复合和单参考帧预测器都可以对OBMC做出贡献，因此 $p_{i}$ 可以是一个组合预测，平均AV1编解码器中的两个单参考预测。
接下来，预测重叠将在不断更新的上逐步执行，分两个阶段进行：第一个阶段是上方相邻的块，第二个阶段是左侧的块。
- 例如，在图1中，block 0为待预测单元，block 1-4为编码邻块。
  
  图1 重叠的区域

第一阶段

检查位于block 0顶部的block 1-3的预测器。其中，如果block i使用的是帧间预测，利用运动参数计算一个新的运动块 $p_i(x, y)$ 用于 $p_0$ 和 $p_i$ 在block 0中的重叠块：在block 0中的一个矩形区域，以block 0和block i的公共边为其边之一，与block 0的相对边在block 0的中线上。
例如，在图1(a)中，阴影区域是block 0中p0和p2像素点的重叠区域，预测器混合只在这个重叠区域进行。
一个k抽头的1维滤波器 $w_K(k)$ ，其形状为半凸起的余弦窗口(参见图2 (b)中的32抽头示例)，其公式如下：
$w_k(k) = \frac{1}{2}sin(\frac{\pi}{2K}(k+\frac{1}{2})) + \frac{1}{2}, k = 0, 1, ..., K -1\ (1)$

图2 基于1维升余弦的加权窗口
应用于重叠区域的每一列(见图2(a))，更新 $p_{obmc}(x, y)$ 为：
$w_{\frac{N}{2}}(y)p_{obmc}(x, y) + (1 - w_{\frac{N}{2}}(y))p_i(x,y)\ (2)$
该滤波器近似平均了公共边缘的预测，并逐渐减小了新的预测 $p_i$ 的影响，直到在当前块的中线处消失，因为传统的块匹配 $p_0$ 通常对中心像素效果最好。

第二阶段

利用左邻域的预测器。
同样，在第一阶段更新后的的顶部进行一维滤波：
- (1) 每个左邻域的重叠区域位于公共边缘的右侧，如图1(b)中p4的阴影区域。
- (2) 水平方向采用一维滤波器，即
  $p_{obmc}(x, y) := w_{\frac{N}{2}}(x)p_{obmc}(x, y) + (1 - w_{\frac{M}{2}(x)}p_i(x, y))$

注意：在第二阶段的新预测可以与第一阶段的重叠区域有相同的部分，如图1中的blcok 1和block 4，在这种情况下，这意味着新的预测将被处理为组合预测而不是原始的p0，所以当前块的左上1/4最终的预测将是三个预测的组合。

因此，与对上述预测器的依赖程度相比，基于(1)的一个固定的一维滤波器的两阶段会使最终预测结果略微偏向于左侧的预测器。

仍然决定使用这个简单的方案是因为实验性的修正方法没有获得一致的额外收益，包括避免两个重叠或切换到二维窗口如在[4]中结合四个预测器(只有在当前、左上、左边的块是相同大小的帧间预测时)。

在未来的工作中，将探索每个阶段甚至不同重叠维度的系数优化，以增强该框架的能力。

4.2 用于可变块大小编码的非因果OBMC

[1]同时也实现了非因果的重叠预测。

假设所有邻居的运动参数都是可访问的，这个扩展可以很容易地实现，方法类似于4.1节，在四个阶段中与邻居协作，每个阶段分别使用底部、右侧、顶部和左侧的预测器。

因此，需要解决的唯一问题是底部和右侧邻居参数的可访问性。在目前的编解码器中，在进行预测时，由于每个预测单元的参数解码、预测和重构都是背对背(back-to-back)的，因此无法获得分配给“未来”单元的参数。

因此，我们重新安排解码器的流程实现在“未来”位置获得对运动参数的访问，而不会显著损害吞吐量。

将帧分割成64×64块，如图3中粗体线所示，由预测块组成。在每个块中，将整个组的预测参数通信和最终的预测编码完全分离为两个阶段，即在进行预测和重构之前，将所有的参数一次性在一起解码。这使得在预测时可以“随机”访问同一组中的运动参数，因为相同块中的“未来”块的参数已经提前解码和缓冲。

图3 分组预测块以实现非因果OBMC

在[1]的实验中，对于位于相同块中的底部或右侧邻居的块，启用了非因果OBMC，而在块边界上，它退化为部分非因果(3-sided)或因果(2-sided)OBMC。

5. 编码器的优化

5.1 码流的语法

编码器有很多工具来增强时间块复制的基本概念，包括但不限于使用可切换插值滤波器的复合预测和亚像素运动，因此重叠块预测并不总是比现有方法提供实质性的优势。

在实现的两个实验编码器中，一个是因果OBMC，另一个是非因果OBMC，在非重叠预测的基础上，将所提出的算法集成为≥8×8的帧间预测块的第二个选择。

在码流中，在对运动参数进行编码之后，每个块指示一个二进制符号来调用OBMC。在解码器端，首先使用指定的运动参数计算非重叠的帧间预测，如果OBMC模式有信号，则应用第3节中的重叠算法。基于这个操作逻辑，在本节中，将讨论编码器如何有效地为每个预测单元分配一个良好的预测参数组合(参考帧、运动矢量、OBMC标志等)。

5.2 快速RDO的因果OBMC

理想情况下，为了找出每个块的最佳编码工具，应该对所有可能的预测选项组合进行全面测试。

特别是在这个实验中，这意味着非常昂贵的测试编码，需要对所有可能的参考帧和运动矢量组合进行非重叠和重叠预测。

在所提出的框架中，非重叠预测器的测试与baseline AV1编解码器的测试相同。

而对于OBMC预测器，没有寻找最优性，而是忽略了那些建立在低质量基础上的预测器，会导致非重叠预测块的luma RD代价高于当前测试运动参数中最佳总RD代价(对于luma和色度面)。通过执行这个提前终止，将额外的编码时间减少了一半以上，而在CIF测试视频上只降低了0.07%的编码增益。

5.3 因果OBMC的运动估计

对于因果重叠块预测，传统的块匹配方法不能很好地解决不同像素位置的非均匀加权误差问题

因此，当测试一个允许新的矢量被差分编码的运动矢量模式，执行一个特殊的基于加权失真度指标的运动估计。

新方法考虑了重叠预测的实际逐像素失真。首先，最终的重叠预测一般可以用二维滤波器将所有预测因子线性组合表示，即
$p_{obmc}(x, y) = \sum_{i}f_i(x, y)p_i(x, y)$
对于给定未压缩像素值s(x, y)，预测误差为
$d(x, y) = s(x, y) - \sum_{i}f_i(x, y)p_i(x, y)$

接下来，对当前块的运动估计之前已知的变量进行排序。其中包括源视频s(x, y)，从周围的预测器 $p_i(x, y)(i = 0)$ 计算的预测，以及最后的二维权重f(x, y)，因为它们只依赖于分块和邻居的帧间/帧内预测模式的选择。所以公式可以表示为
$d(x, y) = s(x, y) - \sum_{i \ne 0}f_i(x, y)p_i(x, y) - f_0(x, y)p_0(x, y)$

前两项的结果是我们的目标加权预测
$t(x, y) = s(x, y) - \sum_{i \ne 0}f_i(x, y)p_i(x, y)$

在[1]的实验中，无论考虑的率失真函数是SAD、SSE还是方差，OBMC的运动搜索都是基于加权像素差的
$d(x, y) = t(x, y) - f_0(x, y)p_0(x, y)$

使用 $t(x, y)$ 和 $f_0(x, y)$ 在测试候选预测器之前预先计算一次。虽然不能用简单的闭式表达式表示 $t(x, y)$ 和 $f_0(x, y)$ ，但是可以通过遍历第4.1节中描述的两阶段重叠过程来计算它们。

具体地说，在 $t(x, y)$ 中，假设 $p_0$ 为全零， $\sum_{i \ne 0}f_i(x, y)p_i(x, y)$ 等于 $p_{obmc}(x, y)$ ，同样， $f_0(x, y)$ 是假设 $p_i(i \ne 0)全为0和$ p_0$全为1的结果。

在实际中，只有当前的预测器使用一个参考帧时，才会启用因果OBMC，因为对两个向量的加权联合运动搜索结果是一个非常昂贵的增益-复杂性权衡。对于非因果OBMC，需要做更多的工作来解决未来块对当前块的运动矢量依赖关系。

5.4 非因果OBMC的two-pass RDO

在支持非因果OBMC的编解码器中，编码器必须同时确定运动参数和NCOBMC标志。

如果在每个块上只执行一次RDO，就不能确定这个额外的标志，因为在没有未来邻居运动参数的情况下，无法计算NCOBMC预测。

为此，提出了一种two-pass RDO。在第一个循环中，对于每个64x64块，假设OBMC是因果关系，即使用5.2节和5.3节描述的RDO，选择所有参数，包括分块和运动。

然后，在分块和运动参数固定的情况下，以相同的因果扫描顺序，第二遍RDO访问块中的每个预测单元，根据常规预测和NCOBMC预测的RD成本，最终确定NCOBMC标志。

注意，NCOBMC的实现还处于初级阶段，还有很大的改进空间。例如，NCOBMC可以使用除第一遍选择的运动外的其他候选运动进行测试。

6. 实验结果

提出的重叠预测算法已集成到AV1的参考编解码器中。

因果obmc模式将使用配置-enable-experimental -enable-motion var启用，或者如果添加第三个配置-enable-ncobmc编解码器将切换到合并非因果obmc。

编解码器在高延迟设置下运行(大多数帧是B帧)，关闭了大多数加速特性(-cpu-used =0)。

为了做一个全面的研究，[1]在大范围的目标比特率下对每个测试视频的150帧进行编码。

使用PSNR度量，比较了三个编解码器，包括

(1) AV1baseline本身。
(2) OBMC：添加了因果OBMC作为额外的编码工具。
(3) NCOBMC：启用了非因果OBMC(因果OBMC在第三个编解码器中被禁用)。

在三个测试集上

lowres低分辨率(40个分辨率为240p、SIF或CIF的剪辑)。
midres中等分辨率(30个分辨率为4cif、480p或832×480的视频)。
hdres高分辨率(19个分辨率为720p的视频、19个分辨率为1080p的视频和1个分辨率为xga的视频)的平均差异见表1中的BDRate[9]。由于负BDRate意味着更好的压缩效率，因此两种工具在不同分辨率下均能将比特率节省2.2-2.8%，而采用非因果重叠预测模式的编解码器虽然尚未完全优化，但其性能比采用因果OBMC的编解码器高0.3-0.4%左右。

Table 1 对于不同分辨率的测试集，与AV1 baseline相比，BDRate(%)

Table 2中还列出了所选单个序列上的BDRates，我们可以看到所建议的工具改进了所有视频的压缩比(也适用于测试集中的视频，但没有在这里列出)，尤其适用于具有较低或中等运动的视频，很难通过块匹配完全补偿。

Table 2 与AV1基线相比，单个视频的bdrate（%）试验

例如，《工厂》是一部有着各种旋转和扭曲物体的动画，《城市》是从不同的视角拍摄的，《篮球通行证》既有摄像机运动，也有跑步运动员。

即使对于看起来非常静态的视频，例如akiyo和bow，重叠预测在处理物体边缘的微小非平动运动方面也显示出优势。我们的调查也进一步深入到block水平，不同大小block选择的原因OBMC的频率如Table 3所示。

Table 3 因果OBMC使用百分比(%)(Avg1:基于计数;Avg2:基于面积)

有趣的是，与方块相比，非方块对OBMC有很强的偏好。一个合理的直觉是，编解码器最终得到的是那些通常用于处理离网(off-grid)或不规则对象边缘的分区，在这些情况下，统一的预测显然是不够的。对于方形块，CIF 视频更倾向于对较小块应用OBMC，而1080p 视频的统计量更趋于平稳，这可能是由于运动变化比较平缓的缘故。对于两种分辨率，如Table 3中Avg2所示，OBMC预测区域约占帧间的30%。

[1]还测试了在CIF和1080p视频下的OBMC编解码器的复杂度。与baseline编解码器所消耗的时间相比，额外的计算列在Table 4中，显示了较低的解码复杂度开销和可管理的编码复杂度。此外，值得一提的是，如果去掉加权运动搜索并重用块匹配找到的向量，我们将牺牲约0.4%的性能增益，以换取在CIF和1080p序列上分别减少5%和12%的额外编码时间。

Table 4. 与AV1基线相比，支持因果OBMC的编解码器的额外编码时间(%)

7. 总结

[1]介绍了AV1中采用的一种新颖实用的实现OBMC的框架。

该方法还包括一个高效的模式决策模块和一个匹配OBMC目标的运动搜索算法。
通过对译码流程的修改，初步实现了对非因果OBMC的扩展，取得了良好的效果。
该工具以合理的额外编码复杂度为代价，实现了一致的压缩改进。

未来的工作

包括用完全优化的一维滤波器替换现成的窗口。
设计RDO来实现非因果OBMC的真正潜力。