基于硬件实现的高效率视频编码整像素运动估计算法优化

聂宇鑫，施隆照，黄霖

(福州大学物理与信息工程学院，福建 福州 350108)

0 引言

随着短视频的兴起和5G技术的普及，人们对超高清视频的需求越来越高.因此高效视频编码标准(high efficiency video coding, H.265/HEVC)应运而生.H.265/HEVC与上一代H.264相比同样采取混合编码框架，包括变换、 量化、 熵编码、 帧内预测、 帧间预测和环路滤波等模块[1].不同之处在于编码单元能够进行自适应四叉树划分，同时提升了帧内预测的精确度.帧间模式也引入了先进的运动矢量预测技术(advanced motion vector predictor，AMVP)[2].因此，在相同视频质量的情况下，HEVC编码后的码流大小仅为H.264的一半.在HEVC编码过程中，帧间预测约占整个编码时间的70%[3].因此对帧间预测的优化是提升编码器性能的关键.

目前HEVC编码器常见的搜索算法主要有： 全搜索算法(Full-search)、 TZ-Search、 二维对数搜索法[4]、 三步搜索法[5]、 四步搜索法[6]等.不同的算法就是在寻找速度和性能之间的平衡点.文献[7]提出一种快速CU尺寸决策算法，通过3种基于运动均匀性、 率失真代价(RD-COST)和SKIP模式的早期终止方法来跳过对不必要CU尺寸的运动估计，但是对于运动剧烈的图像编码效率较低.

也有许多研究人员提出了一些硬件友好型的运动估计算法.文献[8]提出一种改进版菱形算法，对中心区域细选，外围区域粗选，同时采用SAD树同时记录下全部PU的代价数据.但是硬件资源开销较大.文献[9]对128 px×128 px的区域进行S型全搜索，对参考像素的存储使用移位寄存器的方式，搜索左右移动时丢弃一列像素，因此能在一个时钟内完成参考像素的切换，但是这种做法模块整体时钟周期过长.文献[10]将GOP中QP值最小一帧和前一帧同位置CTU深度合并，决定当前CTU计算的最大深度，将CTU的深度决策路径从4个深度缩减到3个深度，能够有效减少运算复杂度，但是性能损失并不理想.文献[11]提出一种可变搜索范围的快速算法，利用LCU的MV通过经验公式，估计出子块PU的搜索范围，能够有效减少运动估计过程中的搜索点数.但是对于一些特定序列效果并不理想.

本研究基于小菱形搜索算法，在硬件实现的架构上对算法做一定调整，利用流水线处理和并行处理的方式，对AMVP和IME模块进行流水处理，同时对PU和CU的处理顺序进行调整，解决因为AMVP和IME互相参考导致流水线停滞的问题.硬件电路对小尺寸PU并行处理，进一步减少整个模块周期数.

1 算法简述

1.1 小菱形搜索算法

一帧画面中，每个PU的运动矢量(MV)都与其相邻PU有着紧密相连的关系，因此HEVC引入AMVP算法，用于确定搜索起点，加快搜索过程.小菱形搜索算法搜索过程如图1所示，图中数字代表搜索的顺序，搜索起点由AMVP的结果确定.一次搜索需计算包括中心点在内的上下左右一共5个点所对应的SAD(像素差值的绝对值和)代价.一次搜索结束后，进行代价比较来判断是否需要迭代还是可以进行下一块PU的搜索.判断的条件是代价最小的点是否是中心点，如果不是则以代价最小的点作为中心点进行迭代搜索，直到代价最小的点为中心点或者达到最大迭代次数为止(本研究最大迭代次数设置为64次).小菱形搜索算法与视频编码标准代码HM16.7中TZ-Search搜索算法相比，BD-rate平均只增加0.5%，搜索的点数却平均减少了72.9%[12].因此小菱形搜索算法能够大幅度减少搜索数据量，提高硬件的处理速度.

表1 关闭非对称模式后性能对比

在HM16.7平台上，CU非对称模式划分的占比仅为6.43%[13].利用HM16.7对关闭CU非对称划分模式后进行性能测试，得到的结果如表1所示.从表中可知，关闭非对称模式整体编码时间平均减少13.2%，BD-rate平均增长了0.687%.HM中并非全部PU都去执行非对称模式，只有对尺寸为32 px×32 px和16 px×16 px的CU才启动非对称模式[15]，并且不同的划分方式对应不同的非对称模式，2Npx×Npx的PU只做2Npx×nDpx和2Npx×nUpx两种非对称划分，Npx×2Npx的PU只做nLpx×2Npx和nRpx×2Npx两种非对称划分，2Npx×2Npx的PU需要做上述四种非对称划分.所以关闭非对称模式，复杂度只减少了13.2%，但对于硬件实现，只要有PU需要进行非对称处理，就要为其准备相应的硬件电路，但对于大多数PU无需做非对称模式，这样会造成硬件电路利用率低，硬件资源浪费； 其次，关闭非对称模式后，一个CU需要处理的PU数量从13个减少到5个，对于尺寸64 px ×64 px的CTU，经过四叉树划分可分为85个CU，因此处理一个CTU，遍历的PU数由1 105降低至425个，在性能损失较小的情况下可有效缩减处理时间.综上所述，运动估计模块只对CU进行对称划分.

文献[12]基于小菱形搜索算法做了硬件实现，对于PU的IME过程采用串行计算的方式，根据当前PU迭代判断的结果来判断下一个处理的是新的PU块还是当前PU块的迭代.这种处理方式逻辑清晰、 实现简单，但是硬件各模块由于等待迭代判断的结果导致模块内数据处理断断续续，硬件工作效率不高.同时文献[12]对CU采取按层搜索，每层按照Z扫描的方式顺序执行，CU内包含的5个PU也为顺序执行.由于相邻CU会互相参考IME的结果，这也会引起硬件处理的停滞.

对于高帧率、 高清晰度视频，要实现实时编码的功能，采用文献[12]的硬件处理架构是不可行的.文献[12]中处理的CTU尺寸为16 px×16 px，内部一共包括25个PU，整体数据量偏小.本研究要处理尺寸为64 px×64 px的CTU，其包含425个PU，因此如果采取上述方法不能达到理想的吞吐率目标.本研究基于小菱形搜索算法在PU和CU的处理方式上进行了优化，对CU、 PU的处理顺序进行调整，有效提高了硬件处理效率.

2 基于小菱形搜索的硬件架构设计

本研究提出的硬件框架结构如图2所示，对一个PU的处理主要分为AMVP处理和IME搜索两大过程.

两个过程中间用FIFO进行数据的缓存，达到两个过程并行计算的目的.AMVP处理主要包括候选列表的建立和代价计算比较模块.IME过程主要包括PU对应的原始像素和参考像素地址计算，SAD代价计算模块和迭代判断模块.

2.1 PU的处理顺序

从图2中可以看出，对于一个PU的处理首先要进行AMVP过程，然后利用AMVP的结果进行IME搜索，因此为了高效处理一个PU，将AMVP和IME过程修改为流水处理，同时PU的处理顺序也做了调整.对于一个CU包含三种划分方式下的5个PU，如图3所示.由于序号为3的PU块进行AMVP处理需要依赖序号为2的PU块的IME结果(序号4和序号5的PU块同理)，因此对于PU块的处理顺序做了如下调整.将CU下5个PU可以分为MV互相没有参考关系的3组，块1为一组，块2、 4为一组，块3、 5为一组.

将PU块的处理顺序调整为块2、 4、 1、 3、 5，由于块2和4之间的AMVP没有参考关系，因此在对块2进行IME处理的同时可以对块4进行AMVP处理.同理本研究的PU处理顺序在两个有参考关系的块中(例如块2、 3)插入了两个不相关的块，因此能够有效解决因为等待IME的结果导致AMVP处理停滞的现象，减少整个模块的时钟数.

2.2 CU的处理顺序

文献[12]的CU处理顺序为分层处理，每层按照Z扫描的顺序.这种处理方法导致下一个CU必须等待前一个CU处理结束后才能启动.CU计算结束后的处理过程包括不同划分方式的代价比较和更新IME到CTU_MV_TABLE_RAM中，这样会造成IME处理模块在CU切换时的停滞.因此利用不同层CU之间MV互不参考的规律，提出了一种新的CU处理顺序，如图4所示.图4中数字代表CU的处理顺序，将不同层或非相邻位置的CU插入两个相邻CU的处理过程中间.这种方式保证了相邻CU之间处理的流畅性，从后续的仿真波形可以看出，本研究提出的PU和CU处理顺序能够使IME中SAD模块达到全流水状态.

2.3 IME模块PU交替计算与流水线处理

IME处理简单来说包括3个步骤： ① 根据PU的信息计算对应的原始像素和参考像素地址； ② 按行输入的原始像素和参考像素经过裁剪后计算SAD代价； ③ 比较一次搜索过程中5个搜索点对应PU的代价，判断结束当前PU的IME过程或者进行迭代搜索.

由于迭代机制的存在，在迭代过程结束之前并不能确定下一个需要处理的过程是当前PU的迭代搜索还是下一个PU的搜索.因此，PU的串行处理会导致模块的处理时间增长，且各个子模块内部的数据流时断时续，时序示意图如图5所示.

为了解决这个问题，将PU的处理方式修改为三级流水线处理，并且为了压缩判断是否迭代而引起的时钟周期浪费，保证模块内部始终有数据进行计算，在两次迭代之间插入下一个PU的计算.如图6所示，在PU1的SAD计算过程中就对PU2的地址进行计算，当PU1的迭代处理结束时，如果需要迭代就将PU1的信息存入到迭代FIFO中，因此IME的数据有两个来源，一个是存有下一个PU信息的FIFO，一个是存储迭代PU信息的FIFO，且迭代FIFO的优先级更高，每次IME开始之前都会判断两个FIFO的数据存储情况，来判断从哪个FIFO中获取数据.

2.4 IME_SAD代价计算

遍历CU包含的5个PU进行IME处理后，要比较3种不同划分的代价来决定CU的最终划分方式，计算代价的公式为J=D+λR+cost.其中： 残差D在IME过程中用SAD表示；λ为拉格朗日因子与外部配置参数QP值有关，在本研究硬件中采用查表的方式获得；R是当前MV与MVP差值(MVD)的编码比特数； cost表示代价.

64 px×64 px的CTU一共包含425个PU，其中宽度为64 px的PU仅有3个，为了避免在处理小块PU时，对逻辑资源利用的不完全造成的资源浪费，选择每个时钟周期同时计算32个像素点运算器.对于宽度为64 px的PU块，分两次进行代价计算，因此在AMVP模块将宽度为64 px的PU信息和MVP连续存两次到AMVP和IME的缓存FIFO中.然而对于16 px×16 px与8 px×8 px的PU，将有一半以上的处理单元处于空闲状态，为了提高硬件资源的利用率，将32点运算器分为两个互相独立的运算器，每个运算器可以处理宽度为16 px的PU块，也可以合并起来处理32点的PU，所以对于宽度为16 px和宽度为8 px的CU，可以同时处理2Npx×2Npx和上方2Npx×Npx大小的PU块.

2.5 IME存储单元设计

要实现运算单元的并行度，首要任务是存储单元要能够及时提供需要的数据.首先说明一下存储单元的需求，原始像素RAM中按行暂存着一个CTU的原始像素数据，其宽度为(64×8)bit，深度为64.本研究的搜索框设定是CTU周围扩展32个像素点，同时考虑到进行分像素插值还需要向外扩展4个像素点，因此采用的搜索框大小是136 px×136 px.参考像素RAM宽度为(136×8)bit，深度为136.

IME地址计算模块根据当前处理PU块在CTU和搜索框中的坐标.根据y坐标作为地址输出给参考像素和原始像素RAM，输入到SAD的参考像素和原始像素分别为136 px和64 px，由x坐标值对按行输入的像素进行筛选.然后二者相减并进行绝对值计算，由PU宽度选择合适的SAD值进行相加，得到一个PU块最终SAD值.为了提高一个PU块的处理速度，硬件选择同时计算5个搜索点的SAD代价.由于5个搜索点之间的位置关系是确定的，因此对参考像素和原始像素进行一遍读取便可以计算5个点的代价，具体实现如图7所示.图中黑点表示需要同时搜索的5个搜索点，实线和虚线框表示每个搜索点对应的PU块.以搜索中心点左上角的像素点坐标作为首地址.第一个时钟周期，第一行参考像素和原始像素差值的绝对值和得到上方搜索点第一行的SAD代价.第二个时钟周期，第二行参考像素和打一拍的第一行原始像素差值的绝对值和能够得到中间3个搜索点第一行的SAD值，3个搜索点只需要对参考像素进行不同的筛选，同理第二行参考像素和原始像素差值的绝对值和得到上方搜索点第二行的SAD代价.按照上述计算方式，5个搜索点得到最后一行的代价仅相差两个时钟周期，且对参考像素和原始像素只进行一次读取，提高了数据交互的效率.

2.6 AMVP与IME的五级流水处理

根据前面的安排，IME模块的SAD计算过程可以实现不断流全流水，因此AMVP模块也要达到这个速率，才能匹配IME模块的处理速度.为此，AMVP模块应尽量提前将数据准备好，存在FIFO中等IME模块读取.流水线结构如图8所示，每个PU的处理需要经过五级处理，其中AMVP分为候选列表建立和代价比较两级，IME分为IME地址计算，SAD代价计算，代价比较和迭代判断三级.总体来看AMVP的处理时间小于IME的处理时间，因此本研究重新设计了PU的处理顺序，使相邻处理的两个PU不存在MV参考关系，AMVP模块无需等待IME的结果即可对下一块PU进行计算，然后将MVP等信息存储在FIFO中，IME模块结束后将得到的IMV更新到CTU_MV_TABLE中后判断缓存FIFO是否为空，如果FIFO中存在数据即可自启动下一块PU的IME处理.AMVP和IME内部每级流水之间也采用FIFO进行数据缓存.

3 硬件电路综合结果

硬件框架采用Verilog语言设计，在Linux系统下使用Synopsys VCS软件对RTL代码进行仿真和编译，利用Verdi软件对波形进行时序调整.首先用Matlab打印出硬件所需要的激励数据，包括参考像素、 原始像素、 上方和左侧CTU的参考MV.利用Testbench将激励数据从文本文件存入RAM中后发出起始信号，并且将硬件电路中IME的代价值和CU划分方式与Matlab中的数据进行比对来验证电路的正确性.之后利用QuartusII软件，选择Arria10AX115N3F40E2SG型号开发板，模块资源测试结果详见表2.

文献[9]对搜索区域采取全搜索的方式，采用移位存储器的方式存储数据，搜索点上下移动时丢弃一行像素，搜索点左右移动时每个移位寄存器移动一位，只需要一个时钟即可完成参考像素的切换，蛇形全搜索两点之间数据重复率很高.但全搜索计算复杂度很高，需要处理的数据量庞大，导致硬件资源开销较大，处理所需周期数较多.文献[14]采用分层搜索加并行处理的方式进行搜索，并行计算很大程度提高了处理速度，但是硬件资源开销较大.文献[16]首先进行一次粗选，通过粗选得到的步长决定第二次搜索的方式，很大程度上减少了搜索的点数，但是需要的存储资源和硬件资源较大.从表2可以看出，本研究主频略低于文献[9]和文献[14]，但在硬件资源开销上明显小于上述3篇论文，在吞吐率与硬件资源开支上取得较高的性价比.

表2 本研究与其他文献资源对比

表中的周期数为处理一个CTU所消耗的时钟数，本研究平均周期数为5 800个时钟周期，为了直观地看到所提方法的有效性，还测试了在不改变CU和PU处理顺序的条件下，处理一个64 px×64 px CTU平均消耗周期数为9 918个时钟周期.这是因为不改变PU/CU处理顺序导致相邻处理的两个PU/CU块之间有MV参考关系，需要等待上一个PU块IME计算结束后才能进行当前PU块的AMVP，并且需要等待AMVP模块处理结果.因此本研究的设计方案与正常顺序的做法相比，处理一个CTU平均减少了41.5%的时钟数.

4 结语

在视频编码中，帧间运动估计占据了编码的大部分时间.因此如果想进一步提高编码器的处理效率，就要在搜索方式或硬件实现方式上对运动估计进行优化.搜索框中代价最小的点一定存在，如何利用搜索算法快速定位到它，如何利用硬件设计高效计算每一个点的代价就是研究人员的最终目标.在硬件架构上对小菱形搜索算法进行优化，重新对CU和PU的处理顺序进行设计，采用PU交替处理和流水线的方式，尽量使IME模块达到全流水的目标.同时对小尺寸PU进行并行处理，进一步缩减了模块的周期数.通过QuartusII平台对RTL代码进行综合和编译，提出的硬件架构处理一个64 px×64 px的CTU平均消耗5 800个时钟周期，主频能够达到186 MHz，综合性能达到1080P@61 f·s-1.