基于HEVC六边形运动估计算法的VLSI设计

闫博冉，何卫锋，毛志刚

(上海交通大学 微纳电子学系,上海 200240)

基于HEVC六边形运动估计算法的VLSI设计

闫博冉，何卫锋，毛志刚

(上海交通大学 微纳电子学系,上海 200240)

运动估计是HEVC中计算量最大、耗时最多的模块。为了加速编码过程，设计了适用于HEVC运动估计的六边形搜索算法的VLSI架构。该架构支持HEVC标准中的尺寸可变块设计，并且充分考虑六边形模板的数据复用特点，在PE阵列中使用流水线的组织策略，有效降低了片上缓存的访问次数。采用SMIC 65 nm工艺综合该电路，最高工作频率可达100 MHz，电路规模101 k门，能够满足高清视频(1 920×1 080,60帧/秒)的实时编码要求。

HEVC; 运动估计；六边形搜索；VLSI

与之前的视频编码标准相比，HEVC标准具有更高的编码效率。灵活的块分割结构是HEVC提升编码效率的重要技术之一。在HEVC中，最大编码单元(LCU)尺寸为64×64，LCU会根据四叉树结构继续划分成编码单元(CU)，CU的最小尺寸为8×8。与每个CU相关的有预测单元(PU)和变换单元(TU)[1-3]。

运动估计是HEVC编码中最关键的模块之一。参与运动估计的块是预测单元(PU)，与之前的编码标准中单一的预测单元尺寸相比，HEVC引入了共36种不同尺寸的预测单元，如图1所示，其中N=8,16或32，最大尺寸为64×64，最小为4×8和8×4， AMP为不对称划分。编码器可以根据视频的内容特性，对平滑的图像区域采用较大尺寸的块来进行预测，以此提高压缩率；对变化剧烈的图像区域采用较小的块来预测，以此来保证图像细节[4]。

图1 HEVC中预测单元的尺寸及划分模式

在支持可变块的快速运动估计算法的VLSI设计中，文献[10～15]分别采用了菱形搜索算法和三步搜索算法，六边形搜索算法的VLSI实现很少[6-8]。但是文献[5]指出六边形算法相对于其他快速算法，有以下3个显著优势：(1)找到最优匹配点需要的搜索步数更少；(2)六边形模板更接近于圆形，不会漏掉图像的某个运动方向；(3)模板步长较大，避免了陷入局部最优。基于上述考虑，本文采用六边形算法完成HEVC中运动估计的VLSI设计。

1 预测型六边形算法分析

六边形算法是一种基于块匹配的快速运动估计算法，使用绝对误差和(Sum of Absolute Difference, SAD)作为块匹配的判断准则。假设块的大小为M×N，Pi和Pi-1分别表示当前块和参考块的像素值，(x,y)表示运动向量(Motion Vector, MV)的分量，SAD的定义如下

(1)

其中，SAD值最小点即为当前块的最优匹配块。

在快速搜索算法中，一般以3个相邻块的MV的平均值作为当前块的起始搜索点[9]，但是除以3在硬件中实现过于复杂。本文增加了图2所示的左上方的MV4，除以4可以通过操作数右移2位实现。

图2 预测起始搜索点示意图

图3给出了预测型六边形算法的搜索示例，首先得到起始搜索点之后，以六边形模板去搜索最优匹配块，如果最优匹配块出现在六边形模板的中心处，则再搜索菱形的4个点，如图3中的第5步，此时得到SAD值最小块即为最终的匹配块，对应的MV为(-1,-3)。

图3 六边形搜索过程示意图

搜索算法确定之后，需要确定搜索范围。根据式(2)，参考帧片上缓存RAM的大小与搜索范围成平方关系，所以需要在保证运动估计质量的情况下，尽量减小搜索的范围。

参考帧RAM容量=(搜索范围×2+64)2

(2)

在HEVC的官方标准HM.15的仿真模型中，通过将搜索范围设为[-64,64]来统计运动较为剧烈的高清视频Basketball的MV的分布情况，结果95%的MV均分布在[-32,32]之内，80%的MV分布在[-16,16]之内，54%的MV分布在[-8,8]之内，其他测试视频得到的MV分布统计都是类似的。因此本文确定搜索范围为[-32,32]。

2 六边形算法的数据复用分析

图4中每个网格线的交点代表1个像素点，0号～6号代表六边形模板的搜索点，7号～10号代表菱形的搜索点。

图4 六边形搜索点编号

在对每一个不同大小的块进行六边形搜索的过程中，SAD值的计算都是独立的，所以根据所有块尺寸的最小长度为4，最小宽度为4，确定每次计算当前块中大小为4×4的块的SAD值，通过累加得到更大尺寸块的SAD值。由于不同搜索点之间有参考像素的重叠，从参考帧缓存中读出8行×8列像素即可得到4×4块的11个搜索点的SAD值。

为了减少处理单元的个数，本文采用流水线的设计方法，每个周期读入参考块像素共8行×1列，这样经过4个周期后可以得到0号位置的SAD值，第5个周期得到1号、2号和7号位置的SAD值，以此类推。当计算到当前4×4块位于6号位置的SAD值时，此时处理单元(PE)中的参考块恰好是右侧相邻4×4的块的0号位置的参考块，所以为了进一步增加数据的复用率，同时不打乱PE阵列的流水线结构，PE阵列中会寄存当前块中的2个左右相邻的4×4块，在第8个周期时，会同时计算第1个4×4块在6号位置的SAD值和第2个4×4块在0号位置的SAD值。从第9个周期开始，计算下一个4×4块的SAD值。直至当前块中所有处于同一行的4×4块的SAD值计算完成，然后开始计算下一行的4×4块的SAD值。

下面以8×8块的一次六边形搜索为例，说明SAD值的计算过程。如图5所示，8×8的块可以分解为(0,0)，(1,0)，(0,1)，(1,1)共4个4×4的块，整个8×8块的参考像素个数为12×12。表1列出了整个8×8块在1次六边形搜索中的完整数据流。

图5 8×8块在1次六边形搜索中所需要的参考像素

表1 8×8块在1次六边形搜索的完整数据流

通过上述流水线式的数据组织方式，可以不断将新的1列参考帧像素读入PE阵列中，每个周期都会得到新搜索点的SAD值，避免为了新的搜索点再次去缓存中读取之前已经读过的数据。

3 六边形运动估计算法的VLSI设计

本文提出的电路结构如图6所示，其中片外存储器提供视频信息的读取接口。

图6 运动估计整体VLSI结构示意图

该电路结构与文献[7]中的结构相比，没有采用并行的7个处理单元，而是采用同一个PE阵列流水线式完成所有搜索点的SAD值计算，有效降低了电路面积。另外，文献[7]中的电路结构在每次新一轮六边形搜索时，都会读取片外存储器，这大幅增加了访存的功耗，由于不同搜索点之间的参考帧像素是有重叠的，这样会造成重复性访问片外的同一数据，尤其是针对当前帧中同一位置的不同尺寸块均需要进行六边形搜索的情况，片外访存的次数是难以接受的，因此本文的参考帧缓存采取将所需要的参考帧像素全部缓存到片上，减少对片外存储器的访问次数。

3.1 当前帧和参考帧缓存

最大块尺寸为64×64，因此当前帧缓存为4KB。PE阵列要求当前帧像素可以在一个周期内更新4行×4列，设计当前帧缓存器由4个独立的单口RAM构成，存储策略为：第1个RAM存第1行、第5行、…、第61行，第2个RAM存第2行、第6行、…、第62行，以此类推，第4个RAM存第4行、第8行、…、第64行，如此可以读出连续的4行像素。

根据搜索范围为[-32,32]，得到所有参考像素共32+64+32=128行，缓存共16 kB。PE阵列的数据更新是每个周期读8行×1列的参考像素，因此参考帧缓存器由8个独立的单口RAM构成，存储策略为：第1个RAM存第1行、第9行、…、第121行，第2个RAM存第2行、第10行、…、第122行，以此类推，第8个RAM存第8行、第16行、…、第128行，如此可以读出任意的连续8行。

3.2 PE阵列结构

PE阵列大小为8×4，每个周期更新8行×1列的参考帧像素，即为图7中PE0～PE7的参考像素，后续PE的参考像素来自前一级的PE。利用加法树结构，对PE中得到的像素差值进行累加，依次得到1×4、 2×4的SAD值，然后组合得到搜索模板中0号～6号和7号～10号的4×4块的SAD值。SAD值存储在指定的寄存器中，由控制器状态机标识其更新、累加或保持原值。

图7 PE阵列及SAD值运算示意图

3.3 控制器设计

如图8所示，主控制器接收到外部的帧开始信号，然后电路将当前块像素写入当前帧缓存，将参考像素写入参考帧缓存。当参考帧像素写入完成后，电路开始对当前块不同尺寸的划分块逐个进行六边形搜索，找到每个块在参考帧中的最优匹配块，并记录最优匹配块的运动向量MV和SAD值。

图8 状态机切换示意图

假设当前块的高为H，宽为W，根据第3部分的数据流分析，当前块进行1次六边形搜索需要的周期数为(W+4)×(H/4)，电路在搜索点的转换过程中, 利用计数器统计当前的周期数，控制每个4×4块的SAD值的计算和累加，同时根据当前块的地址和MV，产生参考帧缓存的读地址。

4 性能分析

本文的电路结构与文献[6～8]的不同之处主要体现在3个方面：(1)可支持HEVC标准中灵活的块分割结构；(2)充分考虑六边形模板的数据复用特点，没有采用文献[6～7]中的7个并行处理单元的数据流组织方式，而是采用了1个处理单元，通过流水线依次得到7个参考点的结果，提高了参考帧像素的复用率，使得PE阵列的大小从112降低到32；(3)增加了起始点预测功能，使得搜索的第一步就比较接近最优匹配点，有效降低了搜索步数。

实现上述VLSI结构后，利用Snopsys Design Complier工具，SMIC 65 nm工艺库进行综合，结果如表2所示。

表2 电路综合结果

注：等效逻辑门数=总面积/单元库中NAND2门的面积

与文献[7]相比，本文的电路面积有所增加，但是在性能方面，本文面向的是当下最新的HEVC标准，既可以支持更多尺寸的划分块，又可以支持更大的搜索范围，并且在数据复用率方面优于文献[7]。

5 结束语

本文设计了适用于HEVC运动估计的六边形搜索算法的VLSI架构。该架构流水线的数据组织策略可以增加参考帧数据的复用率，缺点是需要将参考帧数据全部缓存到片上，今后可以利用计算机体系结构中多级Cache的思想，只缓存最有可能用到的参考像素，从而减小片上缓存的大小。本文也为后续图像编码的进一步研究提供了参考。

[1] 万帅,杨付正.新一代高效视频编码H.265/HEVC[M].北京:电子工业出版社,2014.

[2] Sullivan G J,Ohm J R,Han W J,et al.Overview of the high efficiency video coding (HEVC) standard[J]. IEEE Transactions on Circuits and Systems for Video Technology,2012,22(12):1649-1668.

[3] Ohm J R,Sullivan G J,Schwarz H,et al.Comparison of the coding efficiency of video coding standards—including high efficiency video coding (HEVC)[J].IEEE Transactions on Circuits and Systems for Video Technology,2012,22(12):1669-1684.

[4] Li X,Wang R,Wang W,et al.Fast motion estimation methods for HEVC[C].Beijing:2014 IEEE International Symposium on Broadband Multimedia Systems and Broadcasting,IEEE,2014.

[5] Zhu C,Lin X,Chau L P.Hexagon-based search pattern for fast block motion estimation[J].IEEE Transactions on Circuits and Systems for Video Technology,2002,12(5):349-355.

[6] 王巍,林涛,谢玉亭,等.H.264运动估计改进六边形算法及FPGA设计[J].微电子学,2013(5):694-697.

[7] 商迪,王明江,郑海东,等.六边形运动估计算法的 VLSI实现[J].微电子学与计算机,2009,26(4):50-53.

[8] Muzammil M,Ali I,Sharif M,et al.An efficient FPGA architecture for hardware realization of hexagonal based motion estimation algorithm[C]. Shanghai:IEEE International Conference on Consumer Electronics-Taiwan (ICCE-TW),IEEE,2015.

[9] 李子印,朱善安.基于运动矢量预测的六边形块运动估计搜索算法[J].信号处理,2006,22(2):193-197.

[10] Ndili O,Ogunfunmi T.Algorithm and architecture co-design of hardware-oriented,modified diamond search for fast motion estimation in H.264/AVC[J]. IEEE Transactions on Circuits and Systems for Video Technology,2011,21(9):1214-1227.

[11] Tseng C F,Lai Y T,Lee M J.A VLSI architecture for three-step search with variable block size motion vector[C].Nanjing:The 1st IEEE Global Conference on Consumer Electronics IEEE,2012.

[12] Mukherjee R,Sheth K,Dhar A S,et al.High performance vlsi architecture for three-step search algorithm[J].Circuits,Systems and Signal Processing, 2015,34(5):1595-1612.

[13] Muzammil M,Raja G,Ali I.Field programmable gate array (FPGA) architecture of diamond search motion estimation algorithm for real-time video applications[J].Ned University Journal of Research, 2015(9):355-360.

[14] Porto M S,Sanchez G,Noble D,et al.An efficient ME architecture for high definition videos using the new MPDS algorithm[C].Nanjing:Proceedings of the 24th Symposium on Integrated Circuits and Systems Design,ACM,2011.

[15] Shah N N,Dalal U D.Hardware efficient double diamond search block matching algorithm for fast video motion estimation[J].Journal of Signal Processing Systems,2016,82(1):115-135.

A VLSI Architecture of Hexagonal Search Motion Estimation for HEVC

YAN Boran，HE Weifeng，MAO Zhigang

(Department of Microelectronics and Nanoscience，Shanghai Jiao Tong University，Shanghai 200240,China)

Motion Estimation is the most time consuming module in HEVC with high computational complexity. In order to speed up the encoding process, a VLSI architecture of hexagon-based motion estimation search for HEVC is proposed. This architecture can support variable-sized blocks in the HEVC standard and fully considerers the data multiplexing of hexagon search. The PE array uses the pipeline organization strategy to significantly reduce the on-chip cache access times. Using SMIC 65 nm technology, the proposed architecture is synthesized at the maximum operating frequency of 100 MHz with 101 thousand gates. Simulation result shows that the architecture is able to process 1 920 × 1080 p video at 60 f/s.

HEVC; motion estimation; hexagon-based search; VLSI

2016- 11- 25

闫博冉(1991-)，女，硕士研究生。研究方向：HEVC视频编码中的运动估计算法及其VLSI设计。何卫锋(1976-)，男，副研究员。研究方向：SoC设计与系统集成。毛志刚(1962-)，男，教授。研究方向：系统级芯片设计。

10.16180/j.cnki.issn1007-7820.2017.09.035

TN919.81

A

1007-7820(2017)09-130-05