编解码器优化 – Yuanqing's MMLab

编译反馈优化（PGO）

PGO(Profile-guided optimization)通常也叫做 FDO(Feedback-directed optimization)，它是一种编译优化技术，它的原理是编译器使用程序的运行时 profiling 信息，生成更高质量的代码，从而提高程序的性能。

传统的编译器优化通常借助于程序的静态分析结果以及启发式规则实现，而在被提供了运行时的 profiling 信息后，编译器可以对应用进行更好的优化。通常来说编译反馈优化能获得 10%-15% 的性能收益，对于特定特征的应用（例如使用编译反馈优化 Clang本身）收益高达 30%。

编译反馈优化通常包括以下手段：

Inlining，例如函数 A 频繁调用函数 B，B 函数相对小，则编译器会根据计算得出的 threshold 和 cost 选择是否将函数 B inline 到函数 A 中。
ICP（Indirect call promotion），如果间接调用（Call Register）非常频繁地调用同一个被调用函数，则编译器会插入针对目标地址的比较和跳转指令。使得该被调用函数后续有了 inlining 和更多被优化机会，同时增加了 icache 的命中率，减少了分支预测的失败率。
Register allocation，编译器能使用运行时数据做更好的寄存器分配。
Basic block optimization，编译器能根据基本块的执行次数进行优化，将频繁执行的基本块放置在接近的位置，从而优化 data locality，减少访存开销。
Size/speed optimization，编译器根据函数的运行时信息，对频繁执行的函数选择性能高于代码密度的优化策略。
Function layout，类似于 Basic block optimization，编译器根据 Caller/Callee 的信息，将更容易在一条执行路径上的函数放在相同的段中。
Condition branch optimization，编译器根据跳转信息，将更容易执行的分支放在比较指令之后，增加icache 命中率。
Memory intrinsics，编译器根据 intrinsics 的调用频率选择是否将其展开，也能根据 intrinsics 接收的参数优化 memcpy 等 intrinsics 的实现。

编译器需要 profiling 信息对应用进行优化，profile 的获取通常有两种方式：

Instrumentation-based（基于插桩）
Sample-based（基于采样）

Instrumentation

Instrumentation-based PGO 的流程分为三步骤：

编译器对程序源码插桩编译，生成插桩后的程序（instrumented program）。
运行插桩后的程序，生成 profile 文件。
编译器使用 profile 文件，再次对源码进行编译。

Instrumentation-based PGO 对代码插桩包括：

1. 插入计数器（counter）

对编译器 IR 计算 MST，计算频繁跳转的边，对不在 MST 上的边插入计数器，用于减少插桩代码对运行时性能的影响。
在函数入口插入计数器。

2. 插入探针（probes）

收集间接函数调用地址（indirect call addresses）。
收集部分函数的参数值。

Sampling

Sample-based PGO 的流程同样分为三步骤：

编译器对程序源码进行编译，生成带调试信息的程序（program with debug information）。
运行带调试信息的程序，使用 profiler（例如linux perf）采集运行时的性能数据。
编译器使用 profile 文件，再次对源码进行编译。

其中步骤2采集的数据为二进制级别采样数据（例如 linux perf 使用 perf record 命令收集得到 perf.data 文件）。二进制采样数据通常包含的是程序的 PC 值，我们需要使用工具，读取被采样程序的调试信息（例如使用 AutoFDO 等工具），将程序的原始二进制采样数据生成程序源码行号对应的采样数据，提供给编译器使用。

比较

对比 sampled-based PGO，Instrumentation-based PGO 的优点采集的性能数据较为准确，但繁琐的流程使其在业务上难以大规模落地，主要原因有以下几点：

应用二进制编译时间长，引入的额外编译流程影响了开发、版本发布的效率。
产品迭代速度快，代码更新频繁，热点信息与应用瓶颈变化快。而 instrumented-based PGO 无法使用旧版本收集的 profile 数据编译新版本，需要频繁地使用插桩后的最新版本收集性能数据。
插桩引入了额外的性能开销，这些性能开销会影响业务应用的性能特征，收集的 profile 不能准确地表示正常版本的性能特征，从而降低优化的效果，使得 instrumented-based PGO 的优点不再明显。

使用 Sample-based PGO 方案可以有效地解决以上问题：

无需引入额外的编译流程，为程序添加额外的调试信息不会明显地降低编译效率。
Sample-based PGO 对过时的 profile 有一定的容忍性，不会对优化效果产生较大影响。
采样引入的额外性能开销很小，可以忽略不计，不会对业务应用的性能特征造成影响。

H.264/AVC 中的 MB-Tree

翻译自 J. Garrett-Glaser, “A novel macroblock-tree algorithm for high-performance optimization of dependent video coding in h. 264/avc,” Tech. Rep., 2009.

x264 有一个复杂的前(lookahead)模块，旨在估计尚未被主编码器模块分析的帧的编码成本。它使用这些估计来做出各种决策，例如自适应 B 帧、显式加权预测以及带VBV的码率控制的比特分配。出于速度原因，它在帧的半分辨率版本上运行并仅计算 SATD 残差，不进行量化或重建。

Lookahead 的核心是 x264_slicetype_frame_cost 函数，该函数会被重复调用以计算给定 p0、p1 和 b 值的帧的成本。 p0 是要分析的帧的列表 0（过去）参考帧。 p1 是要分析的帧的列表 1 参考帧。 b 是要分析的帧。如果p1等于b，则该帧被推断为P帧。如果p0等于b，则该帧被推断为I帧。由于 x264_slicetype_frame_cost 可能会作为使用它的算法的一部分在相同的参数上重复调用，因此每个调用的结果都会被缓存以供将来使用。

x264_slicetype_frame_cost 通过为帧中的每个宏块调用 x264_slicetype_mb_cost 进行操作。由于帧是半分辨率，因此每个“宏块”是 8×8 像素，而不是 16×16。 x264_slicetype_mb_cost 对每个参考帧执行运动搜索。该运动搜索通常是具有子像素细化的六边形运动搜索。

对于 B 帧，它还检查一些可能的双向模式：类似于 H.264/AVC 的“temporal direct”的模式、零运动矢量以及使用 list0 和 list1 运动搜索产生的运动矢量的模式。 x264_slicetype_mb_cost 还计算近似的intra cost。所有这些cost都被存储以供将来使用。这对于宏块树来说很重要，它需要这些信息来进行计算。

The Macroblock-tree algorithm

为了执行上述的信息传播估计，宏块树跟踪每个前瞻帧中每个宏块的传播成本：以 SATD 残差为单位的数值估计，表示未来残差在多大程度上取决于该宏块。对于前瞻中的所有帧，该值都初始化为零。

宏块树在前瞻中的最后一个minigop 中开始操作，首先对 B 帧进行操作，然后对 P 帧进行操作。然后，它向后移动到前瞻中的第一帧（要编码的下一帧）。通过这种方式，宏块树向后工作：它及时向后“传播”依赖关系。因此，当我们“传播”依赖关系时，我们是在与实际依赖关系本身相反的方向上进行操作：将信息从一个帧移动到其参考帧。

对于每一帧，我们对所有宏块运行传播步骤。宏块树的传播步骤如下：

对于当前宏块，我们加载以下变量:
- intra_cost：该宏块的帧内模式的估计 SATD 成本。
- inter_cost：该宏块的帧间模式的估计 SATD 成本。如果该值大于intra_cost，则应将其设置为intra_cost。
- propagate_in：当前宏块的propagate_cost。对于运行传播的第一个帧，故意将propagate_cost设置为零，因为尚未收集该帧的信息。
我们计算从该宏块传播到其参考帧中的宏块的信息分数，称为propagate_fraction。这可以通过公式 1 – intra_cost / inter_cost 来近似。例如，如果宏块的帧间成本是该宏块的帧内成本的 80%，则我们说该宏块中 20% 的信息源自其参考帧。这显然是一个非常粗略的近似，但是快速且简单。
依赖于该宏块的信息总量(total amount)等于(intra_cost+propagate_in)。这是所有未来依赖性（直到前瞻边缘）和当前宏块的内部成本的总和。我们将其乘以propagate_fraction，得到应该传播到该宏块的参考帧的近似信息量，propagate_amount。
我们在其参考帧中的宏块之间分割propagate_amount，用于预测当前块。基于每个宏块用于预测当前宏块的像素数量对分割进行加权。这可以基于当前宏块的运动矢量来计算。如果块有两个参考帧（如双向预测的情况），则将传入的值平均分配到两者之间，或者如果启用了加权 B 帧预测，则根据双向预测权重。然后将propagate_amount 的适当分割部分添加到用于预测的每个宏块的propagate_cost 中。请注意，如果为了简单起见我们忽略插值滤波器的影响，则每帧中最多有 4 个宏块可用于当前宏块的预测。

该过程的结果是当前帧的参考的propagate_cost值已基于当前帧的内容而增加。通过对前瞻中的所有帧以相反的顺序重复此操作，我们可以估算出前瞻中每个宏块对前瞻中其余帧的质量的贡献。

最后，将完成步骤应用于我们希望获取最终量化器增量的任何帧中的宏块。这通常是接下来要编码的几帧。宏块树的完成步骤使用与传播相同的输入进行操作，但输出 H.264 量化器增量：

\(Macroblock QP Delta = -strength * log2((intra\_cost + propagate\_cost) / intra\_cost)\)

其中strength是从实验中得出的任意因子。测试表明，对于大多数视频来说，2 是接近最佳的值。由于 H.264 量化器比例每 6 Qps 精度加倍，这意味着最佳量化器精度似乎与完成步骤中使用的结果值 (1 +propagate_cost/intra_cost) 的立方根大致成比例。

应该注意的是，该算法会导致 QP 增量完全为零的未引用帧，因为没有任何内容传播到它们：

\(Macroblock QP Delta = -strength * log2((intra\_cost + 0) / intra\_cost) = -strength * log2(1) = 0\)

这是有意为之的：根据宏块树的逻辑，所有未引用的宏块都具有相等（因此最小）的值。

Analysis

宏块树在比特分布方面具有许多一致的效果。其中之一是对 B 帧量化器的影响。正如简介中提到的，B 帧量化器通常是通过 P 帧量化器的偏移导出的。宏块树实际上相反：未引用的 B 帧量化器始终相同，而相邻的 P 帧量化器则不同。

其结果实际上是自适应 B 帧量化器偏移。在高速运动区域，B 帧的量化值往往不会比附近 P 帧的量化值高很多。在低运动区域，量化器差异要高得多：在某些情况下+4-6 QP 或更多。值得注意的是，在 x264 中，当宏块树打开时，常规 B 帧量化器偏移将被禁用，因为它们起到相同的作用。

人们可能会类似地假设宏块树可以替代关键帧量化器偏移。然而，测试表明情况并非如此：宏块树通常会降低整个场景的量化器，而不仅仅是场景中的第一帧。关键帧量化器偏移对于 PSNR 仍然有用，因此保留在 x264 中。关键帧量化器偏移的算法推导可能需要某种形式的前瞻量化。

虽然宏块树太复杂而无法实现封闭形式的通用解决方案，但可以从特殊情况输入的解决方案中得出一些见解：全零运动向量、无 B 帧、恒定的intra_cost和恒定的propagate_fraction。尽管这样的输入完全不切实际，但它提供了对宏块树作为propagate_cost函数进行缩放的方式的深入了解。

令 TREE[N] 为传播 N 帧后的propagate_cost。令 Y 为常量intra_cost，Z 为常量propagate_fraction，范围为0-1。

\(TREE[0] = 0\)
\(TREE[N] = (TREE[N-1] + Y)*Z\)

对于较大的 N，这可以简单地证明收敛于 Y * (Z/(1-Z))。因此，在这种情况下宏块树的量化器增量按如下比例缩放：

Perceptual considerations

由于宏块树在视频的帧内和帧间之间重新分配比特，因此它特别有可能产生积极和消极的感知后果。我们在视觉比较过程中注意到这些影响有两个主要类别：运动自适应量化和“pre-echo”。

视频的高运动部分的视觉质量下降是 qcompress 和其他类似算法的感知解释。因此，与qcompress不同，宏块树不会仅仅因为帧的其他部分在时域上复杂而降低帧的静态部分的质量。这对于静态背景和重叠图形的情况尤其重要。从这个意义上说，宏块树是一种注重编码效率的运动自适应量化算法。

“pre-echo”是宏块树设计的自然结果。宏块的质量取决于它在未来被引用的程度；如果该宏块很快就会被遮挡（如移动物体的情况）或完全被替换（如场景变化的情况），宏块树将降低其质量。

通常，这种“pre-echo”仅在遮挡/场景变化之前的几帧中可见，并且几乎完全被帧间预测隐藏。此外，场景变化会导致向后时间掩蔽效应，有助于隐藏此类伪影。这种向后的时间掩蔽效应持续几十毫秒，足以覆盖一两帧，并且被认为是由人类视觉系统的处理延迟引起的。这与我们自己对宏块树的非正式视觉测试一致，这也表明此类伪影在视觉上是不可见的。因此，保存在此类宏块中的比特可以自由地用于视频中的其他地方。

在一种特殊情况下，“pre-echo”是可见的：即强制关键帧。朴素的宏块树算法将关键帧视为全帧内帧，即使关键帧不是场景变化。这会导致关键帧之前的几帧质量降低，在关键帧实际上不是场景变化的情况下，这在视觉上可以明显感觉到质量的微小脉冲。

在 x264 中，为了宏块树的目的，通过将强制关键帧视为 P 帧来避免此问题。请注意，此优化仅在感知优化开启时在 x264 中执行。忽略这种感知优化可能会对 PSNR 和 SSIM 产生较小的积极影响。

视频编码器效率评价标准

1. PSNR

PSNR 定义为信号（原始图像）的最大可能功率与噪声功率之间的比率，在所考虑的场景中，噪声功率是通过有损压缩引入的。对于解码图像分量 Id ，参考原始图像分量 I 的均方误差 (MSE) 计算如下：

其中M和N是图像分量的宽度和高度，并且图像分量可以是亮度样本或Cb或Cr色度样本。 PSNR 值计算如下：

其中 B 是图像样本的位深度。这通常是针对每个帧单独计算的，然后对视频序列的帧进行平均。由于是对数变换，这相当于使用帧 MSE 的几何平均值，当帧上存在高波动时，应严格考虑其影响。

对于通常由三个颜色分量组成的视频序列，可以报告仅使用亮度分量值计算的亮度 PSNR 值 (PSNRY )，或者可以使用某些加权标准计算使用所有三个分量的加权 PSNR 值 (PSNRW ) 。采用 4:2:0 采样的内容的流行加权示例是：

一般来说PSNR大于45以上，人眼就比较难以察觉压缩后的图像与原始图像的差距。

2. Bjøntegaard Model

Bjøntegaard 模型已成为一种流行的工具，用于评估给定视频编解码器与参考编解码器在一定质量点或比特率范围内的编码效率。 Bjøntegaard delta (BD) 指标通常根据测试数据点的插值曲线计算为比特率差异或质量差异。

首先，定义两个编码器或编码器配置A和B。例如，A和B可以代表两个不同的编解码器、同一编解码器的两个不同编码器、或者打开和关闭某个单一编码工具的同一编码器。

然后，为A和B选择一组支持点。一般支持点由量化参数（QP）定义，用于确定速率和失真之间的权衡。通常，选择 i = 4 个支撑点。某些编码器使用恒定速率因子（CRF）。

然后，选择两个性能度量（PM），这两个度量通常是峰值信噪比（PSNR）和比特率R。使用编码器配置k∈{A，B}和由i索引的所选支持点集对输入视频进行编码。然后，将所得八个压缩视频的两个PM用于后续计算。PM值必须按单调顺序排列。

为确定两个 PM 之间的函数关系，需要决定在插值函数中将哪个 PM 用作因变量，哪个用作自变量。例如，在 RD 比较的情况下，生成函数 R(D) 或 D(R)。最常见的方法是将R(D)定义为自变量。为了通用性并表明可以使用其他 PM，我们在下面分别使用术语 Pind（例如，PSNR）和 Pdep（例如，比特率）作为自变量和因变量。

比特率（即因变量）的值可能有多个数量级，因此，比特率被转换为对数域：

其中小写 p 表示对数域。执行此步骤是为了确保平均 BD 速率值不会偏向更高的比特率。请注意，某些实现使用自然对数而不是以 10 为底的对数。然而，从理论上讲，在对数计算中使用不同的基数会导致相同的 BD 值，因为不同的基数对应于插值中的简单线性因子，观察到的差异是由浮点运算引起的数值不准确引起的。

然后，对两种编码器配置 k 进行分段多项式曲线插值，其中使用自变量 Pind(k, i) 和因变量 pdep(k, i) 的位置作为支持点。所有 I -1 条插值曲线均由三阶多项式表示。由此产生的分段多项式曲线可以写为:

其中 φ 是表示自变量的辅助变量，参数 ak,i、bk,i、ck,i 和 dk,i 是通过两种编码器配置的插值导出的。常用的插值方法主要是三次样条插值（CSI）、分段三次 Hermite 多项式插值（PCHIP）和 Akima 插值。

然后，通过积分计算两个所得插值之间的差异。选择上限和下限作为自变量（例如 PSNR）的重叠部分。两组支撑点的边界由下式计算：

最后，两条插值曲线之间的平均相对差值，我们称之为 Bjøntegaard-Delta (BD) 或 ΔBD，由下式获得：

积分范围 ΔPind = Pind,high − Pind,low。它描述了使用编码器 k = A 相对于参考编码器 k = B 进行编码时在积分范围内的相对比特率差异。请注意，平均差（即积分）是在对数域中计算的，与计算非对数域中的平均差异相比，它强调小差异并减少大差异的影响。因此，BD 值可以解释为在对数域中平均的平均相对差值。

从数学上来说，BD 演算的定义在其大部分组成部分中都是清晰且独特的。唯一的不确定性是确定 ak,i、bk,i、ck,i 和 dk,i 的插值方法的选择。

SAO Implementation Aspects and Parameters Estimation

由于SAO需要样本级操作来将每个样本分类为编码器和解码器中的边带或类别，因此需要尽可能减少每个样本的操作数量，以降低总体计算复杂性。在编码器端，有许多SAO类型需要测试，以在合理的计算复杂性下实现更好的速率失真性能。本文将讨论一些有效的编码器算法。

关于SAO的介绍可以参考：样本自适应偏移 Sample Adaptive Offset (SAO) – 我受到了惊吓 (mmedia-t.cn)

Fast Edge Offset Sample Classification

可以通过使用以下函数和方程以更有效的方式实施EO样本分类：

其中，“c”是当前样本，“a”和“b”是两个相邻样本。作为进一步的加速，上一步骤中获得的数据可以在下一个样本的分类中重复使用。例如，假设EO类为0（即，一维水平图案），并且CTB中的样本按照光栅扫描顺序进行处理。当前样本的“sign3(c-a)”等于左侧相邻样本的“sign3(c-b)”。同样，当前样本的“sign3(c-b)”可以被右侧的相邻样本重用。在软件实现中，sign3(x)函数可以通过使用逐位操作或查找表来实现，以避免使用if-else操作，这在某些平台上可能是耗时的。

Fast Band Offset Sample Classification

样本范围在BO中平均分为32个波段。由于32等于2的5次幂，所以BO样本分类可以实现为使用每个样本的五个最高有效位作为分类结果。通过这种方式，BO的复杂性降低了，特别是在硬件中，只需要电线连接而不需要逻辑门来从样本值获得分类结果。为了减少软件解码运行时间，可以通过使用逐位操作或查找表来实现BO分类，以避免使用if-else操作。

Distortion Estimation for Encoder

速率失真优化过程需要多次计算原始和重建样本值之间的失真。一个简单的SAO实现将通过向de-blocking后的样本添加偏移，然后计算得到的样本和原始样本之间的失真。为了减少存储器访问和操作次数，可以如下实现快速失真估计方法。设k, s(k)和x(k)分别是样本位置、原始样本和重建样本，其中k属于C，CTB内属于特定SAO类型（即BO或EO）起始边带位置或EO类别以及特定边带或类别的样本集合。原始样本和重建样本之间的失真可以通过以下等式描述：

原始样本和SAO修改的样本之间的失真可以通过以下等式描述

其中h是样本集的偏移量。失真变化由以下方程定义：

其中N是集合中的样本数，E是原始样本和重建样本（SAO之前）之间的差值之和，如以下等式所定义：

请注意，样本分类和（7.28）可以在去块滤波后输入样本变得可用后立即计算。因此，N和E只计算一次并存储。然后，ΔJ定义如下：

其中λ是拉格朗日乘数，R表示估计的比特。

对于具有特定SAO类型（即BO或EO）、起始频带位置或EO类别以及特定频带或类别的给定CTB，测试接近E/N的几个h值（偏移），并选择使ΔJ最小化的偏移。在选择了所有边带或类别的偏移之后，将32个BO边带中的每个边带或五个EO类别中的每个的ΔJ相加，以获得整个CTB的速率失真成本的增量（变化）。使用零偏移和EO类别0的BO边带的失真可以通过（7.25）预先计算，并存储以供后续重复使用。当SAO降低整个CTB的成本（即，增量成本为负）时，该CTB启用SAO。类似地，通过快速失真估计可以找到最佳SAO类型和最佳起始位置或EO类。

Slice-Level On/Off Control

HM参考软件通用测试条件使用分级量化参数（QP）设置。作为示例，在随机接入条件下，GOP大小为8。根据帧在GOP中的位置，帧可以属于不同的层次结构级别。通常，帧仅从具有较小或相同层次结构的帧中预测。具有较高层次结构的帧可能会被赋予较高的QP。

如下提供Slice级开/关判定算法。对于层次结构级别0的帧，Slice header中始终启用SAO。给定具有非零层次级别N的当前帧，先前帧被定义为解码顺序中具有层次级别（N-1）的上一个图片。如果在前一张图片中超过75%的CTB中禁用SAO，HM参考编码器将在当前图片的所有切片标头中禁用SAO，并跳过SAO编码过程。这种编码器技术不仅可以减少要解析的语法数量，还可以提高0.5%的BD速率。请注意，亮度和色度SAO可以在Slice header中单独启用或禁用。

SAO Parameters Estimation and Interaction with Deblocking

在HM参考编码器中，估计每个CTU的SAO参数。由于SAO被应用于去块滤波器的输出，所以在去块样本可用之前，不能精确地确定SAO参数。然而，当前编码树块（CTB）中的右列和底行的解块样本可能不可用，因为右侧的CTU和当前CTU下方的CTU可能尚未被重建（在单通道编码器中）。这一限制可以通过两个选项中的一个来克服。第一个选项估计可用CTB样本上的SAO参数，即除了三个底行亮度样本、一个底行Cb和Cr样本、最右侧四列亮度样本、最右边两列Cb和Cr样本之外的CTB样本。当使用64×64 CTU大小时，所提出的方法不会引起显著的编码效率损失。然而，对于较小的CTU大小，SAO参数估计中未使用的样本百分比较高，这可能导致显著的编码效率损失。在这种情况下，第二选项在SAO参数估计期间使用去块之前的样本，而不是不可用的去块样本，这可以减少较小CTU大小的编码效率损失。

率失真优化量化 (Rate-Distortion Optimized Quantization RDOQ)

率失真优化量化 (RDOQ) 是一种编码优化技术，可以对其进行修改，而不会影响比特流是否符合标准。

在视频编码器操作中，量化步骤是唯一负责通过量化和减少变换系数的数量来减少有损数据的步骤。因此，量化变换系数的计算对压缩效率具有显著影响。利用标量量化的编码器所提供的压缩效率（在速率失真方面）可以通过选择更复杂的量化变换系数的计算方式来显著提高（它不是标准化的，可以以任何方式执行）。

在视频压缩技术的发展过程中，已经开发了许多旨在改进量化系数计算的方法。由于其效率，RDOQ被选为HEVC测试模型开发中两种可能的量化方法之一。

改进的量化器可以考虑量化误差和传输变换系数所需的位数，并确定量化变换系数的最佳集合。可以对每个变换系数块（即HEVC中的变换单元（TU））执行优化，并且通过最小化拉格朗日函数来计算最优成本。

该方法的一般思想是找到与最低RD成本相对应的量化变换系数的最佳集合。理论上，确定量化系数的最佳集合需要通过评估所有可能的组合进行穷举搜索。由于编码器的极端计算复杂性，穷举方法是不切实际的。因此，引入了快速次优方法。此外，在[1] “速率失真优化量化（RDOQ）”这一名称已被提出，并被广泛采用。

RDOQ的目的是找到表示编码块中的残差数据的量化变换系数的最佳或次最佳集合。RDOQ计算编码块中的图像失真（由变换系数的量化引入）和编码相应量化变换系数所需的比特数。基于这两个值，编码器通过计算RD成本来选择更好的系数值。

率失真优化量化过程

RDOQ的主要思想是确定TB中的第i个系数（表示为\(c_i\)）的最优量化水平，或者在两个候选量化水平之间[上限舍入水平（表示为\(l_{i,ceil}\)）和下限舍入水平（称为\(l_{i,floor}\)）]，或者特别地，在三个候选之间，或者通过在 \(l_{i,ceil}=2\)的情况下额外考虑 0，\(l_{i,ceil}\)和\(l_{i,floor}\)的值计算如下：

其中QStep是对应于量化参数（QP）的量化步长。RDOQ过程需要所有候选量化级别的RD代价，其中产生最小RD代价的量化级别被选为最优级别。每个候选级别的RD代价导出为:

其中\(D(c_i,r_{li})\)是系数\( c_i \)被量化为\( l_i \)时的量化误差，\( r_{li} \)是其重构（即反量化），\(R(l_i)\) 是量化级别 \(l_i\) 的熵编码产生的码率。 λ是对应于QP的拉格朗日乘数。

注意，(2)中的量化误差\(D(c_i,r_{li})\)可以表示为

其中 \(l_{i,float} \)是由 \(|c_i|/QStep \)计算的量化中的实际浮点数。现在， \(R(li) \)被计算为：

如(4)中，\(R(li) \)需要 \(R_{li}^{Sig}\)、 \(R_{li}^{1}\)、 \(R_{li}^{2}\)、 \(R_{li}^{Rem}\)，分别为与量化级别相关的4个语法元素(SE)的各自速率[3]，即coeff_sig_flag、coeff_abs_lev_greater1_flag、coeff_abs_lev_greater2_flag、coeff_abs_remaining 。这四个 SE 的含义如表 I 所示。

请注意，在 HEVC 中，coeff_sig_ falg、coeff_abs_lev_greater1_falg和 coeff_abs_lev_greater2_ falg的 bin 是上下文编码的，而 coeff_abs_remaining 的 bin 是旁路编码的 [4]。为了估计 SE 的个体速率，需要执行实际的熵编码和上下文更新过程。然而，在 HEVC 参考软件中，速率 \(R_{li}^{Sig}\)、 \(R_{li}^{1}\)、 \(R_{li}^{2}\)是根据级别重要性、位置和上下文从预定义的查找表中估计的；通过使用 Golomb–Rice 代码和 Exp-Golomb 代码对低复杂度估计进行二值化 coeff_abs_remaining（表示为 Rem）来估计速率 \(R_{li}^{Rem}\)。 Rem 的值计算如下，其中 absLevel 是量化级别的绝对值：

表 II 显示了 coeff_abs_remaining 的二值化。 coeff_abs_remaining 二值化后,\(R_{li}^{Rem}\) 计算如下：

其中\({Length}^{prefix}\)和\({Length}^{suffix}\)分别是二值化后前缀和后缀的长度。由于HEVC变换系数左移15以表示整数域中速率的分数部分，并且还使用缩放系数估计失真，因此对\(R_{li}^{Rem}\) 左移15。

The RDOQ in HEVC

RDOQ已包含在HEVC参考软件（HM）中，并在HEVC开发和性能期间广泛使用。本节介绍了适用于HEVC的RDOQ算法。

HM中RDOQ的自适应与HEVC残差编码技术密切相关。在HEVC中，变换单元的大小可以从4×4到32×32像素不等，并且只允许方形单元。变换和扫描后，系数被划分为包含16个变换系数的系数组（CG）（图3）。HEVC变换系数编码的详细描述见[2]。

编码器中的RDOQ操作可分为三个阶段：变换系数的量化、系数组（CG）的消除和最后一个非零系数的选择。

A. 变换系数的量化

在该阶段中，编码器分别对每个变换系数执行计算。在第一步中，编码器通过使用无死区的均匀量化器量化变换系数的幅度来计算值Level。在下一步中，编码器考虑分析的量化系数的两个附加幅度：1级和0级。对于每一个提到的系数幅度，编码器计算用所选幅度编码系数的RD成本，并选择RD成本最低的一个。

值得一提的是，当与等于Level的系数幅度值进行比较时，将幅度设置为0值。与设置较低幅度值（级别1）相比，允许更显著的比特率降低。然而，通过将幅度设置为0来消除所选变换系数可能会导致显著失真。

B. 消除系数组

在该阶段中，编码器对每个变换系数组（CG）执行计算。编码器计算消除整个CG的RD成本。整个CG的消除是通过将CG中的所有系数量化为零来执行的。编码器计算所分析CG的消除的RD成本，如果消除允许降低成本，则消除所选择的CG。

整个CG的消除可以导致显著的比特率降低（不需要为CG内的每个系数发送sig_coeff_flag），同时向重建图像引入显著的失真。

C. 最后一个非零系数的选择

RDOQ的最后阶段是在步骤A和B之后针对TU中的所有剩余CG执行的。RDOQ算法分析系数以找到最佳的（短期RD成本）最后非零系数位置。包括此步骤是因为编码器必须编码比特流中最后一个非零系数的（x，y）坐标。

D. RD cost 的计算

在RDOQ操作期间，编码器必须计算所考虑的每一组变换系数或系数组的成本。可以通过考虑编码所选系数CG或TU所需的比特数（B）、引入的失真（D）以及通过拉格朗日乘数对两个值进行加权来计算该成本（RD_cost）:

\(RD\_cost = D+\lambda \cdot B\)

在不同的实现中，编码器可以使用引入的失真的精确或估计值以及编码所选变换系数、系数组或变换单元所需的比特数。使用估计值会导致最佳系数集选择中的一些错误，并导致压缩性能下降。然而，速率和失真的估计可以加快编码器的操作。

Reference

[1] M. Karczewicz, Y. Ye, I. Chong, “Rate Distortion Optimized Quantization”, ITU-T SG 16/Q 6 VCEG, document: VCEG-AH21, Jan. 2008.
[2] J. Sole, R. Joshi, N. Ngyuen, T. Ji, M. Karczewicz, G. Clare, F. Henry, A. Duenas, “Transform Coefficient Coding in HEVC”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 22, no. 12, pp. 1765-1777, Dec. 2012.
[3]J. Sole et al., “Transform coefficient coding in HEVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 22, no. 12, pp. 1765–1777, Dec. 2012.
[4]V. Sze and M. Budagavi, “High throughput CABAC entropy coding in HEVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 22, no. 12, pp. 1778–1791, Dec. 2012.

视频编码器多次运行不一致问题及解决方案

以为我自己的经验来说，编码器开发和优化过程中的不一致主要包括：CABAC 状态不一致、编解码不一致、debug/release 不一致、多次运行不一致。本文主要总结编码器多次运行不一致问题及解决方案。

多次运行不一致一般来说经常出现在多线程中。可能的原因是某些状态没有初始化，导致在多线程的时候每次运行拿到的值不一样；也可能是一个线程用到了另外一个还没有执行完的线程，导致拿到了空的或者错误的值。

多线程/单线程不一致

通常设置多线程时会保证单线程和多线程的结果时一致的，有时候更改某些代码后会出现多线程和单线程的结果不一致，如果多线程运行每次出现的结果是一样的，只是和单线程的结果不一样，那这是比较好解决的一个问题。

首先对多线程和单线程分别进行编码，尽量关闭deblock和sao。然后把多线程和单线程的码流使用码流分析仪打开，或者用VTM打开dtrace的宏解码再用YUView打开。这个目的是为了找到第一个出现不一致的块，同时可以确定两个不同的块选择的模式，找到第一个不同的块后后面就好办了，就不停的打log，来确定最初问题出现的地方，修掉就可以了。

多线程多次运行不一致

多线程多次运行不一致比较难的一点是难以复现，很难出现重复的编码结果，这就会导致我们无法方便定位问题的原因。所以需要通过几种方法来将不一致的可能情况给缩小，让不一致的结果尽量在一个结果上出现频率较高。我们先使用单线程编码一遍来得到一个anchor的编码结果。然后可以尝试以下办法：

一种方法是尽量关闭编码工具，现尝试把编码工具关闭之后是否还有不一致的情况。如果没有了，就去定位具体是哪个编码工具导致的。如果还有不一致，那就看出现不一致的结果复现的概率大不大，如果一个结果出现的概率比较大，这样就可以方便定位了。

定位方法和多线程/单线程不一致的方法一样，就不断的打log来找到问题所在的地方，但是要保证多线程编码的结果是一样的，比如多线程编出来码率是34.56kb的结果概率比较大，那只有在这个结果下的log才有意义，其他结果是没有意义的。

如果不一致的结果仍然难以复现，第二种方法就是尽量减少编码帧数。比如5帧10帧这种，先看看是不是可以稳定浮现。如果不行，可以随便将一个不一致的结果和anchor对比，找到编码顺序第一个不一样的帧的poc值，在编码时就编这么多帧，然后不断的缩小帧数，直到可以一种编码结果可以多次出现，然后按照上面的方法定位即可。

目前我遇到的问题基本上可以用这两个方法解决，这是我自己的解决方案，可能还有其它更好的方案。

VTM 快速CTC测试方案

以下内容总结自JVET-T2010、JVET-T0003、JVET-B0036

VTM作为VVC的参考软件，集成了许多编码工具。尽管这些编码工具大大提升了VTM的编码效率，然而编码时间却急速上升。在JVET-T0003中给出了VTM-10.0的性能，相对于HM16.20，AI配置下，码率节省26.85%，编码时间上升2630%；RA配置下，码率节省40.06%，编码时间增加859%。

我们在进行CTC测试时，尽管有足够多的计算资源（例如多核CPU），当我们采用最小的并行工作方式（每个序列、每个QP、每个配置编一次），每个job的编码时间是不一样的，整个测试时间是取决于编码时间最长的那个序列，这样我们需要花超过一周的时间来进行通测，所以一个快速的测试方案是必须的。

JVET-B0036分别为AI和RA配置提出了快速测试方案，并纳入VTM通用测试条件（JVET-2010）中。下面对JVET-B0036做简要的介绍。

1 Parallel encoding for RA configuration

通常，对测试序列的前 1 或 2 秒内的帧进行编码被认为是 RA 配置的快速模拟方法。但是编码结果可能与编码全长序列的结果有很大不同。一方面，不同帧数的预测结构可能不同，这对压缩性能有重要影响；另一方面，全长序列不同部分的运动特性可能会有很大差异。由于存在一些针对特定运动特性的帧间预测编码工具，因此最终的编码结果容易受到影响。通过考虑这些因素，RA配置的简化模拟方法不能改变预测结构，或减少帧数。

现有RA配置中的预测结构示例如图1所示，其中与每个帧相关联的数字代表编码顺序。为了启用随机访问，I 帧被定期插入。两个连续的 I 帧之间的预测结构是相同的。除了第一个 I 帧被编码为 IDR 帧外，所有 I 帧都被编码为非 IDR I 帧（“开放 GOP”）。对于非IDR I帧，虽然有一些编码顺序在其后面的前导图片，但这些前导图片将不会被后续图片引用。以图1中的第5~12帧为例，第6~8帧为第5帧的Leading picture，在解码过程中需要参考第5帧。但是第9~12帧在解码过程中不会参考第6~8帧。这意味着，如果我们根据帧内周期将整个序列划分为一些片段，如图 1 所示，则它们之间没有帧间预测依赖性。这样整个顺序编码过程就可以分为许多子过程，可以并行执行，充分利用计算资源。

考虑到上述分析，在本方案中，根据intra period，将整个顺序编码过程分为几个随机访问段（RAS），每个RAS以一个RAP帧开始和结束（最后一个段除外，可能是以B帧结束，因为帧数可能小于一个intra周期）。这里注意RAP帧必须是Intra帧。以序列Nebuta为例，RA配置的intra period为64，则poc为0~64的帧为第一RAS，64~128的帧为第二RAS，以此类推。由于两个连续的 RAS 之间没有帧间预测相关性，这样，这些 RAS 可以并行编码。

在所有RAS的编码过程完成后，利用每个RAS的编码日志文件（属于同一个整个序列编码过程）提取整个序列编码过程的编码结果。这里请注意，有些帧将被编码两次（作为 RAS 的结束，也是后续 RAS 的开始，如 Nebuta 的第 64 帧）。但它们只会被带入提取过程一次。由于每个 RAS 的第一个 I 帧中都会存在 VPS、SPS 和 PPS 编码位，为了避免重复统计，除了第一个 RAS 之外，只有作为每个 RAS 结尾的那些 I 帧才会被纳入提取过程，因为开始和结束都将被考虑在内。最后，可以通过提出的并行模拟方法获得原始RD数据。

如果两个连续的RAS的编码过程是完全独立的，那么并行RAS编码得到的RD数据应该等于整个顺序编码过程（原始）的RD数据。但实际上，在当前的编码参考软件中，有一些工具带来了依赖性。第一个是“CABAC_INIT_PRESENT_FLAG”，它指定“cabac_init_flag”是否出现在slice header中，“cabac_init_flag”表示当前slice的上下文初始化表项，在现在的编码软件中，前一个slice的slice类型会影响当前slice的表项选择。第二个是“VCEG_AZ07_INIT_PREVFRAME”，它是“VCEG_AZ07_ECABAC”的子宏[4]。如果“VCEG_AZ07_INIT_PREVFRAME”打开，则“可以通过从先前编码的图片复制状态来初始化slice间上下文模型的初始概率状态”。第三个是“COM16_C806_ALF_TEMPPRED_NUM”，它是ALF_HM3_REFACTOR的一个子宏，这个宏表示候选ALF参数集的长度，如果这个宏大于0，可以从参数集中选择当前切片的ALF参数，导出来自先前编码的切片。这3个因素带来的不等是因为RAS的起始I帧后面的slice（例如图1中的frame9或frame17）的前一个slice类型已经改变，在原始方法中，前一个slice类型是inter，但是提出的方法是 Intra。此外，通过我们的测试，如果“SAO”的长度太短，则会将比特率不匹配（仅比特率）带入最后一个 RAS 的第二帧。那是因为“slice级 SAO 开/关决定是由hierarchy level>0层的前一帧决定的。对于具有hierarchy level = N 的当前帧，前一帧被定义为解码顺序中具有hierarchy level = (N-1) 的最后一帧。”。因此，如果最后一个 RAS 很短，则hierarchy level不连续，例如只有 0、2、3。因此，最后一个RAS中hierarchy level = 2的帧的SAO开/关决定将由前一个RAS中hierarchy level = 1的帧决定。

即使存在这些因素，来自 RAS 并行的最终 RD 数据仍然非常接近来自原始整个顺序编码过程的 RD 数据。JEM1.0 与 HM16.6 在不同仿真方法下的性能在表 1~表 3 中给出。由于我们的集群无法提供关于编码时间和解码时间的公平比较，所以下面的“EncT”和“DecT”是不准确的，下同。

从表1~表3可以看出，原始方法的总体结果为-20.01%，而提出方法的结果为-20.00%，而前2个intra period内的结果为-19.37%。因此所提方法的编码结果与原始结果非常接近。

由于序列是按照intra period划分的，近似等于帧率，所以新的RA配置仿真时间仅为原来的1/T（T为序列持续时间，单位为秒）

2 AI simulation using snapshot of full-length sequence

与RA配置不同，AI配置的编码结果不会受预测结构或运动特性的影响，而是受镜头场景的影响。一般来说，对于现有的测试序列，拍摄场景相对稳定。即使在一些测试序列中有一些场景变化，它也很慢。所以，如果将整个场景变化缓慢的测试序列切割成一些均匀的小部分，对于每个部分，仍然可以认为是一个场景稳定的小序列。对于稳定的部分，任何帧的编码结果都可以很好地代表其他帧，因此不需要对所有帧进行编码。

在这个提议中，对于每个序列，选择每个intra period的第一帧（在 RA 配置中）以形成一个新的小得多的序列，如图 3 所示。对选择方法的更直接的解释是为每个序列选择 RA 配置中的 RAP 图片。以序列Nebuta为例，RA配置中其帧内周期为64，poc等于0、64、128、192、256的帧，总共只有5帧，将被选出形成一个新的序列进行AI模拟，比较原始完整序列的 300 帧。

即使每个序列的帧数显着减少，全长序列的编码性能仍然可以得到很好的体现。为了证实这一点，下面给出了 JEM1.0 与 HM16.6 的 3 种不同测试方法的性能。

从表4~表6，对比前1秒的编码结果（Y：-13.80%），snapshot的编码结果（Y：-13.91%）似乎更接近全长序列（Y：-13.99%），特别是对于ClassF。

对于每个序列，由于新的较小序列仅由每个帧内周期的第一帧组成，因此新的AI配置模拟时间仅为原始配置的1/IP（IP是RA配置的帧内周期）。

在VTM中的AI配置可以通过设置TemporalSubsampleRatio来直接实现这个方案。

CABAC状态不一致解决方案

以为我自己的经验来说，编码器开发和优化过程中的不一致主要包括：CABAC 状态不一致、编解码不一致、debug/release 不一致、多次运行不一致、多线程/单线程不一致。本文主要总结在编码器中遇到这些不一致时常见的原因和解决方案。

编码器在做RDO时，会选择cost最低的模式作为最优模式，其中

\(cost = D + \lambda R\)

我们在RDO的过程中要准确的估计当前模式产生的码率，为了得到准确的码率，需要保持CABAC状态的更新和最后编码CTU时CABAC的状态一致，因此在最后编码完CTU时可以进行CABAC的状态的检查，以判断估计过程的CABAC和真实的CABAC状态是否一致，如果不一致可以通过ASSERT()来触发断言，这样在Debug模式下就可以发现是否存在不一致，如果出现不一致，那么RDO选择的结果可能会出现错误。

在做RDO时，一般会把初始的CABAC状态先备份一份，然后在check每个候选的时候，拷贝出初始的CABAC状态，保证在check每个候选的时候，CABAC的初始状态是一致的，如果忘记拷贝，使用的时上个候选更新过的CABAC状态，就会出现不一致的情况。

同时也要保存最优候选的CABAC状态，如果没有保存也会出现不一致。

在估计码率时需要对某些flag进行bits估计，估计的过程会更新对应ctxIdx的CABAC状态，如果少估计了或者多估计了一次或者多次，也会导致CABAC状态的不一致。

解决方案：

当出现不一致时，在Debug模式下会触发ASSERT，这个时候可以看到当前出错误的CTU index，以及不一致的CABAC状态的ctxIdx（一般可以关闭WPP和SAO，这样比较好定位是哪个CTU index）。这样我们可以在check每个cu模式之前打印state[ctxIdx]的值，再打印出encode每个cu时state[ctxIdx]的值，找到第一个不一致的cu，然后再Debug确定具体哪个地方改变了state[ctxIdx]的值。