视频编解码芯片设计原理----05 整像素运动估计

本系列主要介绍视频编解码芯片的设计，以HEVC视频编码标准为基础，简要介绍编解码芯片的整体硬件架构设计以及各核心模块的算法优化与硬件流水线设计。

本文首先将介绍整像素运动估计的基础知识，分析HEVC标准中IME的搜索策略。接着，分析IME算法优化在搜索模式和参考窗设计等方面的突破口，提出了微代码可配置的IME算法和对应的IME硬件设计。最后根据不同的应用场景提出了三种配置模式，并展示了优化后的IME架构测试结果。

概述

视频序列图像在时间上存在很强的相关性，即相邻帧的图像差别不大。帧间预测即消除视频序列在时间上的冗余，从而达到压缩视频的作用。运动补偿（Motion Compensation, MC）是一种描述相邻帧差别的方法。通过运动补偿，编码器可以通过编码两帧之间的差别，消除帧间的冗余信息。运动估计ME（Motion Estimation）是指搜索出每个块在邻近帧中最匹配块位置的方法。两者之间空间位置的相对偏移量被称为运动矢量（Motion Vector, MV）。

图1

在HEVC运动补偿的过程中，运动估计是其中计算复杂度最高、且耗时最长的模块。整像素运动估计IME即预测过程仅涉及整像素的运动估计，其计算得到的最佳整像素MV将送至后续的分像素运动估计阶段做进一步亚像素MV搜索。

预测单元

在HEVC标准中，“当前像素块”被称之为预测单元（Prediction Unit, PU）。当最大编码单元（Largest Coding Unit, LCU）的大小是64×64时，帧间PU的大小可以从64 × 64变化到4×4（本文中，“PU”指的都是“帧间PU”。）每一个PU都会被指定一个与之尽量相似的匹配块，该匹配块来自于已经编码了的图像帧，是编码端和解码端都能够获得的重建信息。下图给出了HEVC中的各种PU。

图2

运动估计

在HEVC标准中，“已经编码了的图像帧”被称之为“参考帧”。由于时间上相邻的参考帧更可能存在相似的图像块，因此，这些相邻帧一般是参考帧的主要来源。在选定参考帧之后，编码器需要通过整数运动估计的手段在一定大小的搜索窗内找到与预测当前PU最佳匹配的块，然后把所有的最佳匹配块组合成一幅图像构成预测帧，那么预测帧将与当前帧相差最小。如下图所示。

所谓“最佳匹配”，有两方面的指标。

其一、该匹配块与当前块相对偏移MV的编码代价较小。由于参考帧是编码端和解码端共有的信息，所以，编码端只需要保留运动矢量就可以将PU所采用匹配块的信息传递到解码端。

其二，该匹配块与当前块差值的失真程度较小（和编码代价较小）。这一指标通常可以使用包括均方差（MSE）、平均绝对差（MAE）、绝对值差之和（SAD）在内的函数进行估计。

搜索窗和快速搜索

块匹配的搜索策略决定了运动估计收敛速度和匹配块的准确度，一般可以把搜索策略分为两类：全搜索和快速搜索。

全搜索也称为穷尽搜索，遍历搜索区域内的所有位置块，因此精确度最高，但耗费的运算资源也最多。

为了保证搜索的效率，整数运动估计不会在整个参考帧内进行，而是限定于某个搜索范围，这一范围被称之为“搜索窗”。在HEVC标准下，搜索窗的大小一般设置为[-64,64)，换言之，对于每一个PU都存在16384（=128×128）种可能的运动矢量。快速搜索策略在保证运动估计一定精度的前提下，通过减少搜索点，从而减少运算复杂度。因此可以根据一定的收敛模型（搜索模板），通过一步步缩小搜索范围逼近最佳匹配点，较为著名的快速搜索算法有菱形搜索，六边形搜索，十字搜索等等。

HM推荐算法

在HEVC 模型（HM）中，整像素运动估计单元采用了快速预测算法TZSearch，算法流程见下图3。

图3

算法优化

本文提出的IME架构不是针对某个特定的算法。相反的，该IME架构包括若干个搜索步骤，每步执行不同的搜索策略，这样可以组成各种搜索算法。在不同步骤中，这些参数可以被配置为不同的数值。具体来说，在每一步内，每个QLCU（Quarter LCU）内的所有PU采用同样的搜索配置，包括起始点，搜索窗的形状和降采样率。

搜索起始点

每个QLCU可以获取前一帧的最佳MV，并将其作为该QLCU下一步的搜索起始点。

参考窗形状

最基础的参考窗是六边形。但是，通过改变参考窗的长度，宽度以及各个角的度数，参考窗可以转变为各种形状，如下图4所示。

图4

降采样搜索

本文提出的IME设计将通过降采样来搜索64×64，64×32和32×64大小的PU的最佳MV，如下图5所示。

图5

64×64大小的PU及其参考块被1/4降采样到32×32大小，然后被送入32×32大小的SAD引擎。降采样后的32×32块的最佳的MV结果以及相应的代价会被视作该64×64大小PU的最佳的MV和代价。

基于微代码的整像素运动估计架构

通过微代码（Micro-code）配置，每段微代码的长度为44个比特。其中：16个比特用来表示搜索的起始点，25个比特用来表示参考窗的形状，3个比特用来表示搜索的采样率。微代码的格式如下图6所示：

图6

VLSI实现

VLSI实现概述

在Fan[1]的工作中，Fan[1]根据特定算法设计了整像素运动估计引擎，最终的B-D rate损失非常小，但是硬件开销比较大，且搜索算法缺少灵活性。因此，本次设计优化了硬件设计架构，如下图7所示。

图7

优化后的硬件架构仍将使用Fan[1]中提出的4×4块压缩和解压缩逻辑，水平-垂直参考像素存储器和低功耗32×32大小SAD引擎。本节提出的硬件设计的主要工作如下：

(1) 寻址控制逻辑支持微代码可编程。

(2) 简化了参考像素更新逻辑，减少了该模块的硬件开销。

(3) 在转置逻辑中复用了参考像素阵列。

(4) 引入了像素截位，减少了H-VSRAM，寄存器阵列和SAD引擎的硬件开销。

水平垂直参考像素存储器

为了支持二维数据复用，本次设计采用了水平-垂直参考像素存储器（Horizontal-vertical Reference SRAM，H-V SRAMs）。该存储器由两个SRAM组成，即水平参考像素存储器（Horizontal Reference SRAM，H SRAM）和垂直参考像素存储器（VerticalReference SRAM，V SRAM），如图8所示。前者以行的方式存储参考像素，每一行像素存储在H SRAM的同一地址上；后者以列的方式存储参考像素，每一列像素存储在V SRAM的同一地址上。

图8

转置寄存器

在本文提出的硬件设计中，转置模块将复用参考像素阵列。这不仅可以减少硬件代价，还可以提供“双工”数据传输。为了简化转置过程的说明，下图9展示了一个4×4块的转置过程。

图9

像素截位

在Fan[1]的工作中，一个基于4×4块的压缩和解压缩方案被提了出来，用来减少片上参考像素存储器的面积。由于采用了这项技术，每个像素相当于被截位到7个比特，且引入的B-D rate损失非常小。

在本次设计中，测试了不同截位比特数对于最终编码B-D rate和硬件代价的影响，如下表1所示。

表1

根据上表1，在截位比特数为3，即每个像素用5个比特表示的时候，SAD树的硬件代价可以减少40.8%，但是B-D rate的损失仅为-0.01%。因此，本设计采用了3比特截位，这可以在减小硬件代价的同时保证图像的编码质量。

性能评估

为了对基于微代码可编程的IME架构进行测试，我们提出了3种搜索方案，3种方案均可以通过微代码配置出来，如下图10所示。

三种方案中，A方案的侧重点在于编码速度，C方案的侧重点是编码质量，B方案是两者的折衷。值得注意的是，在采用1/4降采样的时候，如果起始点为(0, 0)，那么搜索过程只能覆盖搜索范围内的奇数行、奇数列的候选点，因此，在C方案中，将(0, 0)，(0, 1)，(1, 0)和(1, 1)分别作为起始点搜索，这样可以覆盖搜索范围内的所有点。此外，C*方案采取了和C方案一致的搜索策略，不同点在于C*方案并没有使用像素截位。

图10

B-D rate的测试基于HM 16.9，测试的基准是encoder_lowdelay_P_main.cfg下的默认配置，且只有一帧参考帧。

将综合结果与业界的相关工作进行了比较，如下表所示。值得注意的是，SAD树的门数是指换算到16×16大小时的门数。

在编码效果方面，我们提出的IME架构在B方案和C方案时的B-D rate增益均为负值，远优于Ye[2]、Medhat[3]和Jou[4]的工作。虽然B-Drate效果不如Fan[1]的工作，但是在搜索起始点、参考窗形状和降采样率等参数上灵活性都比Fan[1]的工作要更好。

在编码速度方面，本节提出的方案A在处理单个LCU时仅需要2146个时钟周期，与Jou的工作[4]接近。但是，A方案的B-D rate增量仅为0.55%，远优于Jou[4]工作的4.04%。

在硬件面积方面，在同样换算到16×16大小的SAD树以后，本节提出的IME架构与Jou[4]工作中的SAD树的门数是差不多的。而在SRAM大小上，本节提出的IME架构是这几个工作里面最小的。

在灵活性上，我们提出的IME架构可以通过微代码配置成各种复杂度的运动估计算法，是远优于其他几个工作的。

图11

参考文献：

[1] Y. Fan, L. Huang, B. Hao and X. Zeng. AHardware-Oriented IME Algorithm for HEVC and its Hardware Implementation [J].IEEE Transactions on Circuits and Systems for Video Technology, 2018, 28(8):2048-2057.

[2] X. Ye, D. Ding and L. Yu. Ahardware-oriented IME algorithm and its implementation for HEVC [A]. IEEEVisual Communications and Image Processing Conference[C].IEEE, 2014: 7-10.

[3] A. Medhat, A. Shalaby, M. S. Sayed, M.Elsabrouty and F. Mehdipour. Fast center search algorithm with hardwareimplementation for motion estimation in HEVC encoder [A]. IEEE InternationalConference on Electronics (ICECS) [C]. IEEE, 2014: 155-158.

[4] S. Jou, S. Chang and T. Chang. FastMotion Estimation Algorithm and Design for Real Time QFHD High Efficiency VideoCoding [J]. IEEE Transactions on Circuits and Systems for Video Technology,2015, 25(9): 1533-1544.