macroblocktree算法的简介，可参看：https://blog.csdn.net/zhoudegui88/article/details/80221765。
下面对该文章中提到的A novel macroblocktree algorithm for high-performance optimization of dependent video coding in H264/AVC做部分翻译。因水平有限，翻译只是为了方便本人自己理解，多有不妥之处，建议去看原文。
H264/AVC视频编码中一种对高性能优化的新的宏块树算法
摘要
一种对视频编码近似失真率优化的新的快速探索式的算法已经出现。以前解决该问题的算法在每帧内使用固定的量化器，且依赖慢到不切实际的方法，如对每一帧进行多次重复编码。这个新的macroblock-tree(宏块树)方法将PSNR提升将近1.2db, SSIM提升将近2.3db，超过现有的快速码率控制算法却只有很低的计算开销。macroblock-tree已经被应用题提交到H.264/AVC的开源编码器x264中。
1.介绍
省略
2.背景
省略
3.macroblock-tree预览
macroblock-tree算法的目的是估计每个宏块对将来帧的预测贡献的信息量。macroblock-tree会基于这个贡献信息量来设定该宏块的权重。为了完成这个目的，macroblock-tree从预测的反方向开始，从未来帧往回到当前待编码帧来取得传播的信息量。
为了完成这个任务，macroblock-tree需要知道多种信息，或他们的近似。首先，必须知道被分析的未来帧的帧类型。第二，必须知道这些帧的运动向量。第三，必须知道每一步有多少信息被传播，这个信息是基于帧间编码和帧内编码的代价计算的。x264 lookahead，接下来要讨论的，描述macroblock-tree是如何得到这个信息的。
4.x264 lookahead
X264有一个复杂的lookahead（预测）模型，它被设计为用来估计还未被编码的帧的编码代价（coding cost）.它通过这些估计值来完成一系列决定，例如自适应B帧的存放，显式的权重预测，缓冲受限的码率控制的位存放。由于性能问题，它只在一个二分之一像素版本的帧上操作和计算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来完成的。由于该帧是二分之一像素的，每个“宏块”是8x8大小，而不是16x16。x264_slicetype_mb_cost对每个参考帧（P帧是前向搜索，B帧是前向和后向搜索）执行一个运动搜索。运动搜索典型的是采用四分之一像素的精度的六边形运动搜索。
对于B帧，也检查一些双向模式：一种类似H.264/AVC的”temporal direct”，零运动向量，和一种使用从队列0和队列1的运动搜索中得出的运动向量。x264_slicetype_mb_cost也计算一个近似的帧内cost。所有这些costs被保存起来以便将来可能用到。这对于macroblock-tree很重要，因为它需要这些信息来计算。
这些分析的结果在Viterbi算法中主要用来决定自适应B帧存放的位置。Viterbi算法的输出不仅仅是下一帧的类型，同时也是接下来N个帧的类型的计划，N是lookahead的大小。这个计划是一个高效的队列：它随着一帧图像的在尾部输出和以特定的类型编码，一个新的图像从另一头输入，这个计划被重新计算和改变。这个计划的存在对于macroblock-tree是非常重要的：这意味着任何需要知道未来帧类型的算法都需要对他们有一个一个相当精确的评估，即使gop的结构不是常数。
因此，macroblock-tree需要知道接下来N个帧的类型，近似的运动向量和模式，和帧内/帧间模式的代价（SATD scores）。计算的代价几乎是0，因为编码器为了其他目的已经计算好了这些数据。虽然如此，相对于总的编码时间，lookahead的计算量是很低的。
5.macroblock-tree算法
为了执行上述信息传播(propagation information)的估计，macroblock-tree为每帧图像的每个宏块维持一个propagate_cost：一个数值估计，以SATD残差为单位，表示未来预测中依赖该宏块的信息量。在lookahead中的所有frames的propagate_cost被初始化为0。
在lookahead中， macroblock-tree是在一个minigop组中的最后（最远）的一帧开始处理的，首先处理B帧，然后是P帧。直到lookahead的第一帧。按这种方式，macroblock-tree由后往前工作：它从时间上往后“propagates”（传播）依赖关系(dependencies)。因此，当我们“传播”一个依赖性(dependency)，我们是用与真正的依赖性相反的方向来操作的：从一帧frame移动信息到它参考的那些frames。
对于每一帧，我们队所有宏块运行propagate步骤。macroblock-tree的propagate步骤如下：
1.对于当前宏块，我们加载下面的变量：
intra_cost:该宏块的帧内编码模式的SATD代价的估计；
inter_cost:该宏块帧间编码模式的SATD代价的估计，如果该值大于intra_cost，则把它设为intra_cost。
propagate_in:当前宏块的propagate_cost，对第一帧我们故意把它的propagate_cost设为0，因为没有其他帧需要从它身上获取信息。
2.我们计算从参考帧中的宏块传播到别的宏块的information的fraction，叫做propagate_fraction。它可以近似用公式1-intra_cost/inter_cost来表示。举个例子，如果一个宏块的inter cost是intra cost的80%，
我们就说该宏块的20%的information来自它的参考帧。这是一个非常粗糙的近似，但是快速而简单。
3.依赖于一个宏块的总的information数量等于intra_cost+propagate_in。这是当前宏块所有future dependencies的总和（到达lookahead的边界）和intra cost。我们对它乘以propagate_fraction, 结果近似等于propagate_amount, 应该向宏块的参考帧传播的信息的数量。
4.我们拆分用来预测当前宏块的参考帧中的宏块的propagate_amount。这个拆分是基于从每个宏块预测当前宏块的像素的数目为权重的。这个可以基于当前宏块的运动向量来计算。如果一个块有两个参考帧，如双向预测，propagate_amount被平等的分为两半，或者如果B真预测权重被使能，就会根据双向预测的权重。propagate_amount的适当的拆分比例会被加到每个用来预测的宏块的propate_cost中。注意，如果我们简单的忽略了插值滤波器的影响，每个帧中的至少有4个宏块都会被用来当前宏块的预测。
这些流程的结果是当前帧的参考帧的propagate_cost会基于当前帧的内容而增加。通过重复反向对lookahead的所有帧处理，我们近似求出每个宏块在接下来的frames中的贡献。
最终，最后的步骤是为我们希望的frame的宏块都得到一个量化偏移值。典型的就是接下来即将编码的frames。 macroblock-tree的结束步骤的操作的输入和propagate一样，但输出是H264的量化偏移值：
Macroblock QP Delta = -strength * log2((intra_cost + propagate_cost) / intra_cost)
其中strength是一个来自经验的一个确定系数。测试建议2是对所有视频都能有效优化的近似值。因为H264量化器每6个Qps提高一倍，
网友评论