HEVC中分像素插值算法的动态可重构实现

惠 超，蒋 林，朱 筠，王 萍，崔馨月

(1.西安邮电大学 电子工程学院，陕西 西安 710121； 2.西安科技大学 集成电路实验室，陕西 西安 710054)

0 引 言

在基于块匹配的视频编解码算法中，分数运动估计算法在编码端占据了约1/4的复杂度[1,2]，在解码端占据了约1/2的复杂度，是视频编解码器中计算密集度最高的任务之一。

国内外学者进行了大量降低亚像素插值模块复杂程度的研究，Hong等[3]提出了一种可配置滤波器的电路结构，虽然提高了硬件资源利用率，但却增加了计算的复杂度。Liu等[4]和Wang等[5]对所有的帧间编码块通过自适应插值滤波器来获取亚像素预测像素块，降低了码流所需滤波器系数和解码计算复杂度，但在面积和性能上都达不到人们的期望值。Luo等[6]提出一种基于Wallace树优化的HEVC分像素插值滤波算法的实现方案，相比于传统方法不仅减少了硬件面积，而且提高了模块可工作的最高频率，但只是针对8×8大小的编码块，难以满足视频编码质量多标准的要求。Kalali等[7]提出了两个近似的HEVC分数插值滤波器，通过修改插值滤波器系数来进行分数滤波，能耗降低了67.1%，但是以损耗峰值信噪比和增加比特率为代价。这些方法虽然都能满足算法实现的需求，但其结构固定，不能根据处理速度自适应地改变硬件实现的规模。

综上所述，基于多核体系结构视频编码算法的动态可重构是解决不同大小预测块灵活切换，提高插值计算效率与计算速度的有效途径。本文使用可重构视频阵列处理器设计分像素插值算法块重构映射方案，根据不同大小的编码块，灵活配置处理元逻辑功能和处理元之间的互连方式，结合数据复用和并行处理的思想进行算法验证。实验结果表明，本文提出的方案无论在数据复用率还是资源占用量上都有较大改善。

1 分像素插值算法分析

在帧间编码中，运动矢量不一定总是像素的整数倍。与H.264/AVC不同，HEVC中亮度分数样点的内插分两种情况处理，对1/2像素位置插值使用一个8抽头滤波器，对1/4像素位置插值使用一个7抽头滤波器，由于没有中间的舍入操作，并且使用了更长的滤波器可大幅度提高内插精度，抽头系数见表1。

表1 亮度分数样点插值滤波器抽头系数

图1所示的亮度分数样点插值中，大写字母表示整数像素所在的位置，小写字母表示分数像素所在位置。以A0,0附近的亚像素点为例，a0,0、b0,0、c0,0分别为1/4精度、1/2精度、3/4精度的水平亚像素插值点，它们可由水平方向上的整像素点计算得出；d0,0、h0,0、n0,0分别为1/4精度、1/2精度、3/4精度的垂直亚像素插值点，它们可由垂直方向上的整像素点计算得出，虚线框内的中间9个点e0,0、f0,0、g0,0、i0,0、j0,0、k0,0、p0,0、q0,0和r0,0可由内插出来的垂直邻近的像素a0,j、b0,j、c0,j滤波得到。若以A0,0为基准像素点进行1/2插值，h′0,0和h0,0分别为垂直方向的上亚像素插值点和下亚像插值素点，h′0,0的插值系数跟式(1)是一致的，不同之处是向上取垂直方向上的4个像素点，向下取垂直方向上的3个像素点

h0,0={4(A0,-2+A0,3)-(A0,-3+A0,4)- 11(A0,-1-A0,2)-40(A0,0+A0,1)}≫6

(1)

b0,0={4(A-2,0+A3,0)-(A-3,0+A4,0)-

11(A-1,0+A2,0)-40(A0,0+A1,0)}≫6

(2)

图1 分数位置像素插值

同理b0,0和b′0,0分别为水平方向的右亚像素插值点和左亚像插值素点，b′0,0的插值系数跟式(2)是一致的，不同之处是向左取水平方向上的4个像素点，向右取水平方向上的3个像素点。同理，1/4内插点a0,0和3/4内插点c0,0， 可利用水平方向的7个整数点，采用7抽头滤波器内插得到；1/4内插点d0,0和3/4内插点n0,0， 可利用垂直方向的7个整数点，采用7抽头滤波器内插得到。对于1/4精度的插值，平均每一个整数像素将伴随着15个插值生成的像素。

2 分像素插值算法的动态可重构实现

2.1 可重构视频阵列处理器结构

为了满足分像素插值算法灵活切换的需求，使用可重构视频阵列处理器来对算法进行映射。可重构视频阵列处理器不仅具有通用处理器的灵活性而且兼备专用集成电路的高效性，具有高性能、低功耗的优点，适合用于加速计算密集型任务，分像素运动估计亮度分量插值算法作为典型的计算密集型任务非常适合在可重构视频阵列处理器上实现。

此处理器由可重构视频阵列结构和输入存储器(data input memory，DIM)、输出存储器(data output memory，DOM)组成，可重构视频阵列结构包含主机接口、全局控制器和处理单元阵列(processing element，PE)。全局控制器是可重构机制的关键部分，用于实现对阵列计算资源的控制与管理，为了确保每一条指令同时到达处理元阵列，在主机接口和底层PE阵列之间形成一个H-Tree型层次化网络，通过H-Tree型传输网络给PE下发不同的配置信息实现算法的灵活切换，全局控制器也可以根据H-Tree型网络反馈的信息对每个处理元的执行状态进行检测和信息采集[8,9]；PE阵列是整个系统的核心计算部分，它包括主控单元、功能运算单元、配置缓存和指令寄存器，相邻处理元通过东、南、西、北4个方向的邻接互连共享寄存器进行数据交互[10]。图2所示的PE阵列包括4个处理元簇(processing element group，PEG)，不同处理元簇通过路由器进行通信，每个PEG中包含4×4个PE，每个PE中又包含指令、数据存储器。将多个子任务的配置信息存储在可重构阵列结构中的数据存储中，通过软件编程控制正在执行任务中数据的写入和读出，同时对任务执行数据进行统计。当数据处理完成后，通过检测数据存储中标志位地址信息，向处理元下发重构信息，将PC(program counter)跳转至对应代码的标志位从而达到任务的自主切换。

图2 视频阵列处理器结构

图3 分像素插值算法框架

2.2 分像素插值算法的并行化设计

图3为分像素插值算法硬件实现框架，该算法位于帧间环路中，处于整数运动估计算法之后，在接收到整数运动估计传来的运动矢量后开始提取参考像素并进行亚像素插值计算。在该算法中，四叉树划分的深度越小，待插值像素数目就越多，插值计算量也越大。如果同一时间只针对一种亚像素位置进行处理，虽然提高了编码精度，但同时也增加了算法处理时间，进而影响整个HEVC的编码效率，这是得不偿失的。

由于不同像素点间的插值计算并无数据相关性，在不同处理单元中同时进行插值操作是提高插值效率与计算速度的有效途径。此外，视频算法中的数据处理大部分以N×N矩形块进行，这种H-Tree型体系结构相比其它通用结构更能满足HEVC算法设计需求，能更有效的对视频算法进行并行化和可重构设计。此算法共用到PEG03和PEG04两个处理元簇，每个处理元簇包含PE00到PE33共16个处理元。以8×8大小的编码块为例，图4为4条路径并行的分像素插值算法映射，具体操作步骤如下：

步骤1 原始像素和参考像素加载。PEG03中的PE30接到整数运动估计传来的双握手信号‘555’和‘999’后，通过邻接互连寄存器，接收到3个数值，两个运动矢量，一个整数运动估计的绝对差值和(sum of absolute diffe-rence，SAD)。

随后对当前编码块是否需要做插值运算进行判断，如若进行亚像素插值，给PEG03中的PE00、PEG04中的PE33分别下发握手信号‘222’和‘111’。PEG03中的PE00在接到握手信号222后，按8×8的块开始从数据输入存储(data input memory，DIM)取原始像素值，并下发给PEG03中PE01、PE11、PE21和PE31的0-63号地址。与此同时，PEG04中的PE33按16×24的块大小取参考像素值，在并下发给与数据输出存储(data output memory，DOM)相连的PE03、PE13、PE23的117-500号地址准备进行插值计算。按16×24的块大小取参考像素值，在取数和计算过程中充分考虑1/2和1/4像素点中可复用的数据，相比于不利用数据复用的情况，从外部存储器读取数据量减少了74.7%。

步骤2 分像素插值计算。不同PE在收到由DIM中取入的原始像素和由DOM中取入的参考像素后，开始进行1/2精度或者1/4精度插值计算。待参考像素下发完成后，PEG04中的PE03、PE13、PE23、PE33按1/2水平和垂直插值公式进行计算，对64个像素值进行1/2插值，并将插值结果保存到对应的数据存储中。1/2插值计算完成后，4条路径在同一时刻依次进行3/4插值、1/4插值和倾斜方向的亚像素点插值计算。最后将插值结果下发到PEG03进行残差值的比较。值得注意的是，为了保证像素在计算中具有较高亚像素精度，所有像素在插值时都右移了6位，待进入后续帧间预测环节中，其像素值将被还原。

步骤3 SAD绝对差值和计算。在同一时间计算不同编码块的SAD值，不仅可以最大化资源配置利用率，而且还能缩短算法运行周期。PEG03中的PE01、PE11、PE21和PE31在收到原始像素与插值像素后，进行SAD计算，并将SAD结果下发到PE20与整数运动估计传来的SAD值进行比较，若整数运动估计的SAD值更小，将对应的运动矢量、相应的整数标签‘1212’保存到PE10的506、507、508号地址；若插值后编码块的SAD值更小，则将插值后的像素值通过PE10的邻接互连寄存器输出传给帧间运动补偿算法。

图4 分像素插值算法并行映射

2.3 分像素插值算法的动态可重构实现

HEVC中，一帧图像被分割为多个互补重叠的编码单元，这些编码单元按照四叉树的方式递归划分为多个子单元，子单元编码块大小为64×64、32×32、16×16和8×8。HEVC标准规定编码单元的规模不能小于8×8，编码平坦的区域用大尺寸块表示，编码复杂的区域用小尺寸块表示。一个大小为64×64的最大编码单元(largest coding unit，LCU)总共有85种划分方式，面对如此众多的划分情况，调整算法模式以适用于不同规模的划分成为提高视频编码效率的关键。

如图5所示为HM中随机挑选的3种测试序列四叉树划分结果，经过对比分析得出8×8大小的编码块被选择的平均概率为66%，16×16大小的编码块被选择的平均概率为25%，其余大小编码块被选择的平均概率仅为9%，因此本文主要对8×8和16×16大小的编码块进行重构切换。

图5 不同测试序列四叉树划分占比情况

图6 块重构指令存放

块重构是指不同块大小的分像素插值算法的重构实现，以满足针对四叉树划分和计算时间的不同需求选择不同的编码规模。如图6所示为分像素插值算法块重构指令存放。首先对编码块大小为8×8与16×16的代码进行分区，随后HPN向阵列下发执行何种块大小的状态，并将PC值指向对应代码的标志位处。图中PC1为执行8×8代码时的标志位，PC2为执行16×16代码时的标志位。当执行重构指令时，从存储块中读取出任务的配置信息，同时修改程序计数器，将配置信息的首地址写入其中。PE根据配置信息，执行相应操作，实现8×8与16×16的块切换。具体操作步骤如下：

步骤1 首先将标准视频测试序列转换为处理器可操作的二进制灰度值，将灰度值以文本格式存入片外存储器DIM中。其次对每个PE独立的指令存储器进行分区处理，例如可以分成两段，上半段可以设置为编码块大小为8×8的CU进行插值计算的指令存储区，将核心运算代码初始化到0-254号地址中；下半段可以设置为编码块大小为16×16的CU进行插值计算的指令存储区，将核心运算代码初始化到255-511号地址中，最后将PC标志位‘0’和‘255’存储到PEG04中PE33的510号和511号地址中。

步骤2 由于8×8大小的编码块被选择的平均概率高过50%，本文默认执行8×8大小编码块的分像素插值算法，如若编码区域过于平坦，没有过多的细节信息，需要使用大小为16×16的编码块进行计算，则全局控制器通过HPN网络下发块重构配置信息，执行初始化于指令存储后半段中块大小为16×16的分像素插值算法。

步骤3 插值计算结束后需要进行最优预测块的选取，支持可变块HEVC分像素插值算法需要根据原始像素与参考像素对插值后的编码块进行SAD比较。SAD计算同样采取上述方法，将不同规模编码块对应的SAD算法分段存储于指令存储器中，根据插值计算时CU的大小，全局控制器通过HPN网络将PC跳转至与当前编码规模相匹配的SAD算法的起始位置。PEG03中PE10的509号地址在接到握手信号‘666’时，说明分像素插值和SAD比较都已执行完成，PE10开始向02簇执行数据下发过程，通过双握手‘888’、‘555’与02簇的PE13进行传数。

3 实验结果与分析

为了验证本文所提出动态可重构分像素插值算法的可行性，使用基于BEECube公司BEE4开发平台搭建的视频阵列处理器原型系统进行验证和测试。实验所涉及的可重构视频阵列处理器用Verilog HDL语言描述，算法验证测试环境和所使用的工具见表2。以标准测试序列akiyo.qicf作为测试序列在Questasim 10.1d工具下进行功能仿真验证，采用90 nm CMOS技术工艺进行综合。首先将此重构方案的指令和数据初始化到对应的指令存储器和数据存储器中，通过MATLAB端下发一帧测试序列来进行仿真和验证。

表2 算法验证测试环境和所使用工具

3.1 数据复用率与算法插值计算速度分析

PE00连接片外输入存储DIM，按8×8或16×16的编码单元取原始像素值；PE33连接片外输出存储DOM，根据分像素插值原理需求按24×16或48×32的块大小取参考像素值。对于一帧1920×1080的图像来说，如果都按8×8的块进行编码，总共有32 400块，不采用数据复用的情况下，每个编码块需从DOM中读取256个参考像素值，总共需要读取32 400×256=8 294 400个参考像素值，但是利用数据复用的情况下，除了第一个块取256个像素值，剩余的第一行和第一列每个块只需要从DOM中取128个参考像素值，最后余下的块仅仅需要从DOM中取64个参考像素值，总共需要读取256+128×374+64×32 026=2 097 792个参考像素值。相比于不利用数据复用的情况，从外部存储器读取数据量减少了74.7%。(图7中A、B、C和D这4块都是大小为16×16的参考像素块，以A参考块为基准，B参考块是与A同行相邻的一个参考块，C参考块是与A同列相邻的一个参考块，可以看出，A和B相交的部分为同行相邻的参考块中数据复用的部分，A和C相交的部分为同列相邻的参考块中数据复用的部分，A、B、C和D相交的部分为4个参考块中数据复用的部分。)

图7 CU为8×8时数据复用简化

在进行亚像素插值时，对同一个整数像素点来说，其上、下、左、右会用到大量相同的参考像素值，插值计算时数据复用结构如图8所示。例如图1中h′0,0需要用到地址为4，20，36，52，68，84，100，116号的参考像素值，h0,0需要用到地址为20，36，52，68，84，100，116，132号的参考像素值，8个参考像素值中有7个是不变的，若充分利用数据复用，垂直方向的下亚像素点所用到像素值只需要更新一个新值，插值计算部分读取数据量减少了43.8%。同理可得16×16的编码块在取数据和插值计算部分的数据复用率分别为74.4%和42.7%。

图8 插值计算时数据复用结构

图9(a)为两种编码块在像素加载与SAD值计算阶段耗时统计，以DIM取原始像素为例，在采取数据复用后，16×16大小的编码块比8×8大小编码块相对耗时减少约7.5%。图9(b)为分像素插值算法在串行和并行两种情况下处理不同大小的编码块所需的时间对比，对于8×8的编码块来说，采用4路并行的处理方式进行插值计算比不同精度运动矢量串行计算的速度提升68.2%，加速比为3.14；对于16×16的编码块来说，采用4路并行的处理方式比串行计算速度提升74.7%，加速比为3.96。

图9 不同CU大小下时间对比

3.2 性能分析

表3是对部分性能的统计，根据实验结果显示在90 NM工艺下硬件实现时最大工作频率可达357 MHZ，资源占用量为24 830个逻辑门。本文HEVC分像素插值算法将每个子任务划分到阵列处理器上进行映射，在前一个编码块插值任务进行完后即可开始下一个编码块的计算，16个PE规模的阵列结构。

表3 性能分析

可同时处理1-4组子任务，最大并行度为4。为了更好地说明本算法的优势，将算法对应的硬件设计综合情况与其它同类型文献进行对比。由表3实验数据得出，在相同的90 nm工艺下，与文献[7]相比，虽然硬件消耗有所增加，但是最高频率增加了19%，与文献[11]相比，硬件消耗减少18.5%，最高频率增加53.2%，与32 nm工艺的文献[6]相比，虽然最高频率还有待提高，但是硬件消耗减少24.7%，吞吐率增加了10.3%。由此可见，本设计可在硬件面积更小的情况下达到更高的工作频率，这一点在与对照组的对比过程中尤为明显。此外本设计用加法器和移位操作代替乘法器进行运算，使得计算速度更快，运算时钟周期数更小。在并行方式的选择上比文献[6,7,11]更加灵活，支持1-4路组并行的处理方式，可以根据应用处理速度需求的不同进行选择。在支持重构方面，相比于文献[6,7,11]可以快速实现不同规模、不同块大小算法之间的灵活切换，以应对不同图像序列的划分需求。

4 结束语

针对HEVC分像素插值算法计算量大、冗余度高、灵活性不足的问题，结合视频阵列处理器的特点和现已存在的分像素插值算法特点，提出一种动态可重构且具有高数据复用率的分像素插值算法实现方法，并将算法映射到可重构视频阵列处理器上。通过实验得出此方法可有效解决分像素插值算法资源利用率不高、不同编码块之间难以灵活切换的问题。在90 nm工艺下硬件最大工作频率可达357 MHz，资源占用量为24 830个逻辑门，参考像素的读取数量减少了43.8%，且硬件资源消耗减少18.5%。此算法在高清视频编码和传输中有很强的实用性。此外，在未来研究中将进一步提高资源利用率与数据复用率，做到时间和空间上可重构。