一种降低硬件HEVC帧间编码器存储器开销的方法

魏家聪，范益波，曾晓洋

(复旦大学 微电子学院，上海 201203)

近年来，随着超高清(Ultra High Definition, UHD)视频的普及，主流的视频分辨率逐渐从720p(1280×720)、1080p(1920×1080)等较低分辨率向4k(3840×2160)等更高分辨率靠拢.而高分辨率视频给视频的传输与存储带来了极大的压力，为了解决这一问题，在2013年，视频编码联合工作组(Joint Collaborative Team on Video Coding, JCT-VC)发布了高效率视频编码(High Efficiency Video Coding, HEVC)标准，这代编码标准相比于上一代高级视频编码(Advanced Video Coding, AVC)标准，综合编码效率提升了大约50%[1].

HEVC编码器通常需要支持较高分辨率的视频，因此目前HEVC整像素运动搜索模块的实现一般需要较大的搜索范围来满足高分辨率编码的需求.在高性能HEVC整像素运动搜索模块实现方面，文献[2]提出的方案使用了最高[-512，+511]的搜索范围，文献[3]提出的方案使用了最高[-3847.75，+3847.75]的搜索范围；而在硬件开销较小的HEVC整像素运动搜索模块实现方面，文献[4]提出的方案也需要[-64，+64]的搜索范围.对于硬件视频编码器来讲，由于从外部存储器中读取数据的时间代价较高，通常会将运动搜索所需要的像素点缓存在片上.在硬件开销限制较为严格的情况下，上述方案中较大的搜索范围会带来非常大的片上存储器开销.

针对上述问题，本文提出了一种以编码树单元为单位确定搜索起点的方法，这种方法使得低延时硬件编码器可以在使用较小搜索范围的情况下，得到较优的帧间预测结果，从而大幅降低片上存储器的开销.

1 HEVC整像素运动搜索的分析

1.1 整像素运动搜索的算法与研究现状

在HEVC帧间编码中，整像素运动搜索通常取当前编码块，在参考帧中相同位置附近，进行块匹配计算，并将参考帧中最佳匹配块与当前编码块的相对位置记为运动向量.运动搜索的过程如图1所示.考虑到块匹配的时间复杂度，在编码器当中，通常设有搜索范围的上限.另外，在搜索范围内，通常并不会搜索所有可能的搜索点，仅会搜索部分更有可能出现最佳匹配块的搜索点.

图1 HEVC中整像素运动搜索的例子Fig.1 Sample of motion search in HEVC

在早期，由于视频尺寸通常较小，故运动搜索通常使用全搜索算法，即在指定区域内，对区域内的所有搜索点进行搜索.随着视频尺寸越来越大，需要搜索的范围也变得越来越大.由于全搜索算法需要搜索的搜索点的数量与搜索区域的面积成正比，全搜索算法的搜索代价迅速扩大到难以接受的程度，故在整像素运动搜索的领域，大量简化搜索的方案被提出.

最早的快速搜索算法是文献[5]中所提出的3步搜索策略.这种方法假设搜索点的误差值是沿梯度下降的.在3步搜索中，首先在(0，0)点及其周围进行一次搜索，从这些点中找到1个最优点，在最优点的周围再进行一次搜索，之后在上一步中的最优点附近进行第3步搜索.这种方法认为： 搜索点的误差与当前搜索点和最优搜索点的距离呈正相关，每一步的最优点会沿着误差下降的梯度前进，并且可以找到一个局部最优.误差沿梯度下降的假设以及这种多步搜索的策略非常有效，多年来一直被业界追捧.文献[6]提出了一种对3步搜索进行优化的方法，这种方法认为在(0，0)点附近更可能存在最优点，并依据此种假设，调整了3步搜索需要搜索的搜索点；文献[7]在3步搜索算法的基础上，提出了一种4步搜索算法，相比3步搜索，在较大尺度上能够搜索到更好的结果；文献[8]提出了一种菱形搜索算法，这种搜索算法在每一步中，每个搜索点距离搜索中心点的距离相等，相比3步搜索以及4步搜索，搜索效率得到了进一步的提升；文献[9]提出了一种六边形的搜索方法，这种搜索方法相比菱形搜索算法，能够降低搜索的复杂度，同时仅略微降低编码效率；而在高效率视频编码测试模型(HEVC test Model, HM)参考编码软件中，使用的搜索方法是TZ-Search策略，这种方法一般基于菱形搜索或六边形搜索，可以灵活调整搜索步长以及搜索起始点，此搜索方法的搜索效率非常接近全搜索.

虽然TZ-Search的搜索效率较好，但由于其设计是基于软件算法考虑，每步搜索中不同搜索点距离较远，难以实现相邻搜索点中参考像素的复用，带来了很大的读取硬件存储器的开销.为了解决在硬件上实现高效率整像素搜索的问题，很多在整像素搜索中优化存储器读取的方法被提出： 文献[10]提出了一种搜索方法，该方法在水平方向依次搜索水平距离为1的点，在每次搜索中仅需要读取一列像素，但缺点是不同搜索点之间的距离过近导致搜索范围难以扩大；文献[11]提出了一种单向搜索的算法，这种算法基于搜索误差沿梯度下降的假设，搜索时在上下左右4个方向中的3个方向(除去搜索前进方向的反方向)选取最佳方向前进，这种方法每次仅需读取一行或一列像素，但搜索方向受限较大.

而文献[4]提出了一种新的方法，这种方法使用了支持二维复用的存储器，可以快速沿垂直、水平、对角线3个方向进行搜索框的移动，利用这种特性，本方法中使用了改良的菱形TZ-Search搜索方法，如图2(见第196页)所示，这种搜索方法假设在(0，0)点附近更有可能出现最佳的搜索点，故在(0,0)点附近设置了更密集的菱形搜索图案.此方法相比HM中的TZ-Search，除了菱形搜索框更密集之外，每个菱形搜索框上的搜索点也更加密集，这使得此方法相较HM中的TZ-Search，编码效率更高.但这种方法以64×64的编码树单元为单位进行搜索，并且搜索范围为[-64，+64]，这导致需要在片上缓存至少(64+64+64)×(64+64+64)×8bits，即192×192×8bits的参考像素矩阵；除此之外，片上还需缓存原始图像像素(64×64×8)bits以及预测图像像素(64×64×8)bits，这又是相当大的一笔片上存储器开销.本文将在此方法的基础上进行改进，在保证运动整像素搜索准确性的前提下，实现降低存储器开销的目的.

图2 一种高效的硬件整像素运动搜索算法Fig.2 A high efficiency integral motion search algorithm for hardware

1.2 对HEVC运动向量的分析

在HEVC中，编码块的大小通常较小，在多数情况下，一个单独的编码块并不能完整包含整个运动物体；相反地，通常情况下运动物体会被分解为多个编码块，如图3(见第196页)所示.这意味着同一个运动物体中，相邻的编码块的运动向量应该是相近的.基于这种假设，HEVC中使用了先进运动向量预测(Advanced Motion Vector Prediction, AMVP)方式[12].AMVP使用的相邻的运动向量如图4所示，预测单元(Prediction Unit, PU)为HEVC存储运动向量的基本单位.在AMVP中，分为A和B 2个列表，其中列表A有2个候选运动向量，分别为左侧运动向量(A1)和左下运动向量(A0)，列表B有3个候选运动向量，分别为右上运动向量(B0)、上方运动向量(B1)、左上运动向量(B2).AMVP模式会在A、B列表中各选出1个候选运动向量.A列表中选出候选运动向量的方法是： 若A0运动向量存在，则选择A0；若A0不存在，A1存在，则选择A1；若均不存在，则列表A的候选运动向量为空.列表B的选择方式类似，顺序为B0→B1→B2.若A、B列表均为空，则运动向量的预测值为(0，0).

图3 运动物体编码块划分的例子Fig.3 An example of partitions for coding blocks in moving object

图4 AMVP中使用的邻近运动向量Fig.4 Neighboring motion vectors used in AMVP

AMVP方法原本是用作降低编码运动向量时的冗余信息，若此方法有效，实际运动向量不应偏离AMVP中预测得到的运动向量预测值较多.图5(a)中展示了在HM16.20当中，使用仅参考前一帧的低延迟模式，并且仅使用AMVP模式时，以8×8为单位，统计实际运动向量(Motion Vector, MV)长度的绝对值，与预测运动向量(Motion Vector Prediction, MVP)和实际运动向量作差得到的运动向量差(Motion Vector Difference, MVD)的长度绝对值之间的关系.图中所使用的Class A～F为JCT-VC推荐的不同分辨率的视频测试集[1].可以看到，在1920×1080以及2560×1600分辨率下，运动向量绝对长度的平均值已经超过50，而此时运动向量差的绝对长度仅略大于10.而在图5(b)中，展示了在1920×1080分辨率下，AMVP预测得到的运动向量在实际运动向量[-12，+12]范围内的比例.

图5 实际编码中运动向量的统计分布Fig.5 Statistical distribution of motion vectors in actual coding

从上面的2组统计中可以看出，若可以在AMVP预测得到的运动向量周围展开搜索，仅需[-12，+12]的搜索范围便可以在大多数情况下搜索到一个非常好的运动向量，远远小于文献[4]中所需的[-64，+64]的搜索范围.但这个方法在硬件编码器中是不现实的，原因如下：

第一，AMVP中的预测运动向量需要得到准确的邻近运动向量，而这是不切实际的；这是因为在进行整数运动搜索时，相邻块通常尚未决定最终的运动向量以及划分，以及整数运动搜索通常在分像素运动搜索之前进行，这意味着在整数运动预测阶段，预测器不能够拿到准确的邻近运动向量，从而导致当前编码块不能得到准确的运动向量预测值.

第二，在硬件编码器中，为了充分利用硬件的并行优势，通常会以较大的块为基本单位，对其中的小块进行并行的搜索，如文献[4]提出的方法是以64×64为单位进行整像素运动搜索；而由于访问主存储器抓取参考帧像素的代价是非常高昂的，硬件编码器通常是以同样的较大块为单位抓取参考帧像素，而非为每一个小编码块单独抓取所需的参考像素.由于每个编码块的预测运动向量均不尽相同，故难以在编码开始之前便确定需要抓取的参考像素的范围.

基于以上两点考虑，直接使用AMVP的预测运动向量作为搜索起点的做法是不现实的.在第2章中，将提出一种新的利用相邻运动向量确定搜索起点的方法，来降低整数运动搜索中需要搜索的范围，并降低硬件整数运动搜索模块中所需的存储器开销.

2 以编码树单元为单位的搜索起点优化

在1.2节中提到，若能够利用相邻的运动向量信息来确定当前编码块的搜索起点，可以大大降低所需的运动搜索范围.在本章中，2.1节将提出一种利用当前帧邻近运动向量优化搜索起点的方法；2.2节中会将这种方法扩展至时域来进一步增加搜索起点的准确性.

2.1 基于空域相邻运动向量确定搜索起点的方法

图6 编码树单元的编码顺序Fig.6 Encoding order of coding tree units

在1.2节中曾提到，硬件编码器中通常以较大的块为单位抓取参考帧中的参考像素，一般来说，以编码树单元为基本单位抓取参考像素是一个较好的选择，这是因为在图像中编码树单元是按照简单的光栅顺序进行扫描，而编码树单元内的编码块是按照更为复杂的z扫描方式进行扫描，以编码树单元为单位抓取参考像素可以降低复杂度.

由于图像中运动物体通常是连续的，距离当前编码块较近的运动信息，通常与当前编码块中的运动信息相近，而距离较远的块通常难以保证运动信息的相似性.故在确定当前编码树单元的搜索起点时，应增加近距离运动信息的权重，并降低距离较远运动信息的权重.

另外，如图6所示，对于当前编码树单元来说，左边和上边以及右上方的单元的编码已经结束，可以用作参考，而其他方向上的编码尚未开始，故不能用作参考.

图7 空域中使用的相邻参考块Fig.7 Neighboring reference blocks used in spatial

结合以上几点，图7(见第198页)中展示了一种利用相邻编码块中的运动信息来为当前编码树单元确定运动搜索起点的方法.在图中可以看到，相邻的参考块分为2类: 第1类是近距离参考块，这部分参考块包括上方和左方已编码的参考块，第2类是远距离参考块，包括左上方和右上方已编码的参考块，参考块以8×8为单位，表示当前位置运动向量，若该8×8块中包含2个运动向量，则当前参考块中的运动向量的水平和垂直分量分别表示为2个运动向量的算术平均值.在此方法中，为了简化计算，将每个区域至当前块的距离简化为当前区域中心至编码树单元中心的距离，假设编码树单元每一边至中心的距离为1.00，则近距离参考块区域至编码树单元中心的距离为1.00，远距离参考块区域距离编码树单元中心的距离设为1.75，则近距离和远距离参考块的权重可分别记为1.75和1.00.另外，若某参考块不包含任何运动信息，则该块的运动向量记为不存在.

空域中搜索起始点在水平和垂直2个方向可分别表示为式(1)和(2)：

(1)

(2)

其中：MVSpatial,x和MVSpatial,y分别为搜索起始点在水平和垂直2个方向上的分量；MVNear,x和MVNear,y分别表示近距离参考块在水平和垂直2个方向上的分量；MVFar,x和MVFar,y分别表示远距离参考块在水平和垂直2个方向上的分量；NNear和NFar分别表示近距离和远距离上所有的包含有效运动信息的参考块的数量.

当画面中不同部分的运动反差较大时，若当前搜索范围较小，则须经过多个编码树单元的搜索范围叠加之后，才能将搜索起点从前一运动物体迁移至另外一个运动物体上.而在文献[1]中的数据显示，将编码树单元的大小从64×64降低至32×32之后，在相同的图像质量下，娱乐场景和交互场景中的码率仅分别平均增加2.2%与3.7%；另外，将编码树单元的大小降低为32×32之后，由于使用的相邻运动信息距离当前编码树单元中心更近，运动搜索起始点的准确性将会上升.并且，在编码树单元的尺寸缩减至32×32之后，参考像素缓存、当前帧像素缓存、预测像素缓存的大小都可以得到不同程度地降低.

图8中展示了在Basketball Drive(1920×1080)序列中，使用以编码树为单位确定搜索起点的方法之后，在使用[-12，+12]的搜索范围时，图像左上角256×256区域的运动向量相比最佳运动向量的偏差.这里假设HM16.20中的TZ-Search计算得到的运动向量为最佳的运动向量.图8中展示的数据为运动向量误差的绝对长度，以编码树单元为单位进行统计.由于在1帧的左上角没有任何可以参考的相邻运动信息，这导致左上角的编码树单元只能从(0，0)位置开始搜索.在图8(b)中可以看到，误差降低的速度要远远快于图8(a) 中64×64的编码树单元.这说明在以编码树单元为基本单位确定搜索起点时，使用32×32的编码树单元可以有效抑制运动突变导致的运动搜索误差.

图8 不同编码树单元尺寸下运动向量的误差Fig.8 Error of motion vectors in different size of coding tree unit

2.2 基于时域相邻运动向量确定搜索起点的方法

除了在空域之外，在时域中也有物体运动信息的相似性.在参考帧中，相同位置的编码块的运动信息很可能是相似的，这是由于在时域上相邻的2帧一般是连贯的，在相同位置下，很可能是同一个运动物体，而同一个运动物体在较短时间内，运动信息不太可能发生突变.另外，由于2.1节中提出的基于空域相邻运动向量确定搜索起点的方法仅能使用当前编码树单元之外的运动信息，而前一帧中相同位置的运动信息可以作为当前帧相邻运动信息的补充.除此之外，在当前图像的上边界和左边界的块，特别是左上角的块，由于缺少部分或者全部的相邻运动信息，导致搜索起始点出现偏差，利用时域上相同位置编码树单元中的运动信息可以缓解这种偏差.

图9 预测搜索起始点使用的时域相邻块Fig.9 Temporal neighboring blocks used in search starting point prediction

在图9中，展示了确定时域搜索起始点所使用的相邻运动信息.在当前帧的整像素运动搜索开始之前，首先以4×4为单位，计算前一帧中相同位置的编码树单元的平均运动向量，该运动向量即为时域上相同位置的运动向量预测值.若某块不存在运动信息，则将该块记为无效.式(3)和(4)中展示了时域搜索起始点的计算方法：

(3)

(4)

式中：MVTemporal,x和MVTemporal,y分别为搜索起点预测值在水平和垂直方向的分量；NTemporal为相同位置的编码树单元中所有有效的运动信息参考块；而MVframe-1,x和MVframe-1,y分别为该编码树单元中每个有效运动信息参考块的水平及垂直运动向量分量.

2.3 时域空域联合预测搜索起始点的方法

在前2节中，分别提出了使用空域以及时域来预测搜索起始点的方法.由于在同一帧中，不同位置的编码树单元能够使用的运动信息不同，这里将当前帧中不同位置的编码树单元分为3类，分别确定其搜索起点：

(1) 左上角的编码树单元

由于该位置的编码树单元是每帧当中首先被编码的编码树单元，故在空域中没有任何可以用来参考的运动信息.此块仅使用时域中相邻的运动信息，如式(5)和(6)所示：

(5)

(6)

式中：MVTemporal,(0,0)为前一帧中相同位置的时域搜索起始点预测值，权重为1.0；MVTemporal,(0,1)为前一帧中当前位置右侧的时域搜索起始点预测值，权重为0.5；MVTemporal,(1,0)为前一帧中当前位置下方的时域搜索起始点预测值，权重为0.5.这样便可在左上角编码树预测块没有任何可以使用的相邻运动信息的情况下，提供搜索起点预测值.

(2) 顶部及左侧第1列编码树单元(除左上角编码树单元)

这部分编码树单元中，顶部第1列编码树单元在空域中，仅有左侧以及左上方的运动信息可以使用，左侧第1列仅有上方以及右上方的运动信息可以使用，故在此种情况下，应降低当前帧中运动信息的权重，如式(7)和(8)中所示：

MVx=0.3MVSpatial,x+0.7MVTemporal,x，

(7)

MVy=0.3MVSpatial,y+0.7MVTemporal,y.

(8)

(3) 其余位置的编码树单元

在其余位置中，所有的空域相邻运动信息均存在，故可以提升空域相邻运动信息的权重；另外，由于当前帧中运动信息的相似性通常大于相邻帧中的相似性，故应适当降低时域相邻运动信息的权重，如式(9)和(10)中所示：

MVx=0.8MVSpatial,x+0.2MVTemporal,x，

(9)

MVy=0.8MVSpatial,y+0.2MVTemporal,y.

(10)

3 实验结果及分析

3.1 编码效率的分析

本节中将对2.3节中提出的搜索起点确定方法的编码效率进行分析.本文所使用的测试方法为JCT-VC中推荐的Bjøntegaard-Delta Bit-Rate，即BDBR方法[13]，来确定在同样的图像质量下，图像比特率的变化百分比.本文在BDBR中所使用的PSNR(Peak Signal-to-Noise Ratio)为JCT-VC推荐的计算方法，如式(11)中所示.

(11)

表1 本文方法的编码效率

其中，PSNRY指亮度分量的PSNR，PSNRU和PSNRV分别指U和V 2个色度分量的PSNR.这样做的原因： 一方面是由于人眼对亮度更敏感；另一方面是由于U、V 2分量的像素数均只有亮度分量的1/2，此外，在HEVC中，U、V分量的预测精度要高于亮度分量，故需要进一步降低这2个分量的权重值.

在表1中展示了本文方法与HM 16.20默认搜索方法的BDBR，本文方法中使用32×32的编码树单元，搜索范围为[-12，+12]，HM的设置为低延迟模式，且仅参考前一帧，其余均为默认设置.从表中可以看到，本文提出的方法在搜索范围仅有[-12，+12]的情况下，相比HM中[-64，+64]的搜索范围，编码效率平均仅下降1.6%，即在相同客观图像质量下，视频的码率上升1.6%.值得注意的是，在高分辨率，且运动较为剧烈的视频中，特别是People On Street、Kimono和Basketball Drive这3个视频序列，本文提出的方法会导致较大的编码效率下降，这是由于每个编码树单元的搜索范围仅有[-12，+12]，在不同运动物体的边界，容易使编码块不能迅速响应运动的变化，在这种场景下，本方法在今后可以被进一步优化.

3.2 电路的综合结果以及存储器开销的分析

本文所提出的方法主要目标有两个： 第一是降低片上像素缓存存储器的开销；第二是在第一点的基础上，将编码效率维持在一个较为合理的水平.在3.1节的分析中可以看到，本文提出的方法仅牺牲1.6%的编码效率，这表明此方法顺利完成了第二个目标.在表2中展示了本文方法与文献[4]中编码特性及像素存储器综合结果的对比.值得指出的是，表格中的BDBR增量均是与HM16.20默认搜索方法相比较得出的结果.

表2 本文方法的电路的综合结果与对比

由表2可以看到，相比文献[4]中的设计，本文提出的方法将参考像素的存储器开销从189.3千门降至了16.1千门，相当于将参考像素存储器的大小降低了91.5%.另外，由于编码树单元的尺寸从64×64降至了32×32，故原始像素和预测像素的存储器开销均降低了75%.本方法中，参考像素、原始像素、预测像素的开销总计降低了84.9%.从电路综合的结果可以看出，本方法很好的完成了降低整像素搜索中存储器开销的目标.

另外，由于本方法将文献[4]设计中的[-64，+64]搜索窗范围缩减至[-12，+12]，并且不需要搜索边长为64的搜索块，这使得在粗搜阶段需要搜索的搜索点大大降低，粗搜所需的周期数也从6180周期降低至了365周期.从这点来看，本文提出的方法在今后可以充分利用节约出的周期数进行更加精细的精搜来提升编码效率.

4 结 语

在高分辨率视频中，通常需要更大的搜索范围来保证帧间预测的效率，这导致在硬件视频编码器中，整像素搜索单元的参考像素存储器开销越来越大.实际上，由于相邻预测块的运动信息相似性，大量起点较远的搜索点实际上并不需要进行搜索.因此本文提出了一种适用于HEVC硬件编码器确定整像素搜索起点的方法，这种方法利用空域以及时域邻近的运动信息来确定当前编码树单元的搜索起始点，在编码效率仅下降1.6%的条件下，将参考像素所需的存储器大幅缩减至参考设计的8.5%.