摘 要:为保证无线显示适配器对视频进行实时压缩编码，提出了一种基于全搜索块匹配算法的运动估计硬件结构，并在FPGA上实现。结构采用二维processsing element(PE)阵列，设计的搜索窗寄存器阵列可获得搜素范围数据最高的复用率，经过优化的PE单元结构减少了对硬件资源的需求。实验结果显示，系统运算速度快，PE利用率高，在工作主频35.6 MHz下，能实时完成1 280×720@30fps视频编码，可用于无线显示适配器的编码端。
关 键 词:运动估计;全搜索算法;硬件结构;现场可编程门阵列
0 引言
随着移动计算技术的不断发展，越来越多的人开始追求办公方式的移动性和便利性。无线显示适配器基于无线视频传输技术和视频编解码技术，实现了显示器与主机相分离，以无线方式传输主机显存数据到显示器。所传输的视频数据具有数据量大、实时性要求高的特点，而无线环境却具有带宽有限、误码率较高的缺陷。为适应无线信道的低带宽，必须使用高效率的压缩算法对视频数据进行压缩编码。
运动估计(ME)是各类视频编码算法普遍采用的一项关键技术，它是去除时间冗余最基础、最有效的方法，其优劣直接决定编码效率和重构视频质量。运动估计越准确，补偿的残差图像越小，编码效率越高，在相同码率下的解码视频就具有更好的图像质量。随着VLSI工艺的提高，FPGA的规模越来越大，并且新型FPGA内嵌DSP内核，并支持软硬件协同设计，成为视频编解码解决方案的通用平台。这种方案具有较高的性能和灵活性，更新方便，开发成本低，应用成熟。更重要的是，在FPGA上实现的方案可以对AISC设计提供很好的性能验证，优点是可以使软件的开发调试和AISC的开发调试并行进行，目前用FPGA来进行ASIC设计是最为流行的方式之一。本文主要研究一种全搜索块匹配运动估计算法的硬件结构，并在FPGA上综合实现。算法固定后，若大批量应用，可采用ASIC芯片实现，能进一步降低系统成本。
1 全搜索块匹配算法分析
由于块匹配运动估计(BMME)算法具有简单高效、开销少、硬件易于实现等优点而被大多数的编码标准采用。BMME的基本思想［1］是将视频序列的每一帧都划分为大小相同、无重叠的子块，并假定子块内的所有像素具有运动一致性，并且只做平移运动。在参考帧的匹配范围内按照一定的匹配准则搜索与之最接近的块(预测块)，该块与当前块的位移就是运动矢量(MV)，预测块与当前块之间的差值称为残差图像，每个原始图像宏块都可以用残差块和1个运动矢量表示。宏块的大小一般取为16×16，宏块不能太小，也不能太大，如果太小，很可能发生匹配到有相同像素值但与场景无关的块，并且块太小会增加运算量，同时也增加了所需传输的MV信息，增加码率;如果宏块太大，在1个块里存在不同的运动场景，则估计精度下降。搜索范围一般为S=(M+2d)(N+2d)，其中M、N是宏块的长和宽，d为垂直和水平方向上的最大位移，通常取d=8，宏块取为16×16，则S=32×32。在ME中，由于匹配准则对运动估计的精度影响不大，通常使用绝对误差和(SAD)，SAD准则不需要做乘法运算，实现简单、方便，其定义为
图1 运动估计示意图
全搜索算法(FSA)通过对匹配窗内所有可能的候选位置计算出SAD值，从中找出最小SAD，其对应的偏移量即为所求运动矢量。FSA计算量大，但简单可靠，找到的必为全局最优预测块，且数据流规整，控制简单，易于硬件高效实现，因此得到广泛研究。在多种支持FSA的运算结构中，脉动阵列(SA)结构最为典型和常用，SA结构是一种采用并行处理单元和流水线技术的计算网络。SA内的处理单元采用同步时钟和同步控制，并且具有模块化和结构整齐的特点，可充分利用硬件资源，采用并行结构及数据复用技术，极大节省了数据传输时间。SA主要有 AB1、AS1、AB2 和 AS2［2］1301－1302四种。AB1 和AS1是一维阵列，结构简单，使用硬件资源少，但是1次仅能搜索1行或1列，适用于极低码率的应用。AB2和AS2是二维阵列，相对于一维阵列，控制较复杂，占用硬件资源多，功耗大，需要更高的数据带宽，但处理速度明显快于一维阵列，因此，对于高码率的应用必须采用二维阵列。SA结构的数据复用技术利用全搜索算法对整个搜索区域的所有候选块都进行运算比较，搜索过程中采用反复的光栅扫描式的搜索方式，如图2所示。奇数行以从左向右顺序移动，而偶数行从右向左搜索，每到行的末尾，仅需向下移1行像素，循环往复直到所有候选块SAD计算完毕。搜索过程中每当进行下一个候选块SAD计算时，仅调入新的1列或1行像素的数据，重复的数据仅在结构内部作相应的移位操作即可，从而获得最高的数据利用率。
图2 光栅扫描搜索方式
快速运动估计算法只搜索几个搜索点，搜索点比较分散，数据的重用性很难保证，且控制复杂。综合考虑以上因素，本文利用FSA的数据流特点，并结合传统的AB2结构，设计了一种用于无线显示适配器编码端的高效运算结构。
2 硬件结构设计
硬件整体结构如图3所示，ME硬件结构主要由存储器模块、控制器模块、寄存器阵列模块、PE阵列模块、加法树模块和MV产生等模块构成。为了避免从外部视频存储系统频繁读取数据，本设计采用并联多块片内 RAM的方式实现128 bit位宽RAM作为高速缓冲区，分为当前块数据存储器和搜索窗数据存储器，其容量分别为16×16×8=2 kbit和32×32×8=8 kbit，本文采用2组这样的存储器构成乒乓结构，进一步提高ME的效率。
图3 整体结构设计
为实现反复的光栅扫描式的搜索方式，设计的基本搜索窗寄存器单元RegS如图4所示，它包含1个选择器和1个触发器，在sel信号的控制下实现8 bit的3选1多路开关，触发器用于保存选择的数据。如图5所示，搜索窗由256个RegS单元互联构成16 ×16 阵列，sel信号采用独热编码［3］:001，010，100，这3种状态分别控制搜索窗从左向右，从上到下，从右向左移动，用独热码虽然比采用Gray码多用了1个触发器，但所用组合电路可节省一些，因而电路的速度和可靠性有显著提高，而单元数并无显著增加。
图4 RegS基本单元
在计算SAD值的过程中(如图6a所示)，传统的PE单元先对减数C做取反加1操作，由于256个并行PE单元共用1个当前块数据，所以可以在当前块数据输入寄存器阵列前完成取反加1操作(如图6b所示)，只需16个取反加1逻辑单元，而按传统的PE结构则需要256个取反加1逻辑单元，极大地减少了PE阵列所需逻辑单元数。
图5 RegS阵列结构
图6 PE单元结构图
MV产生模块由SAD比较器和MV处理器构成。8级加法树得出的第1个候选块SAD后，接下来的每个时钟周期得出1个SAD，SAD比较器内部有1个最小SAD值寄存器和对应的坐标寄存器，最小SAD值寄存器初始值为65 535，MV坐标寄存器初始值为(－15，－15)，MV处理器则根据selmv信号实时更新当前SAD所对应的候选块坐标，当SAD小于最小值寄存器中的值时，更新MV坐标寄存器的值为当前候选块坐标，所有SAD值输入完毕后，得到最佳预测块的MV和SAD值。
控制器模块控制各部分协调工作，主要产生当前块和搜索窗的读取控制信号和地址信号，产生的sel信号用于控制搜索窗→、↓、←3个方向移动，产生的selmv信号用于控制MV产生模块获得每个候选块的坐标，产生的复位信号用于控制其他单元得到当前块最佳MV后复位，以准备进入下一个当前块的计算。
3 FPGA实现与实验结果分析
芯片选择 Xilinx Spartan 3E XC3S1600E，EDA开发软件采用Xilinx公司推出的ISE Design Suite 10.1设计套件，用Verilog HDL对以上硬件结构进行设计，综合工具选用XST，仿真工具为ISE Simulator，并用ISE自带的工具进行翻译、映射、布局布线。
功能仿真信号波形如图7所示。其中，周期设定为10 ns，仿真测试1个宏块在相应搜索范围内搜索的结果。本设计中搜索范围为32×32的正方形区域，左上角坐标为(－15，－15)，右下角坐标为(16，16)，每个候选块用其左上角坐标(i，j)表示，共需要匹配17×17=289个块;整个ME包括当前窗数据的输入，输入带宽为128 bit，16个时钟周期完成，搜索窗初始窗口数据的输入，输入带宽为128 bit，16个时钟周期完成，经PE阵列得到256个对应两点差的绝对值，之后经过8级加法树，8个时钟周期得到第1个SAD，之后在控制单元控制下每个时钟周期输入1行或1列数据到搜索窗寄存器阵列，可得到1个新的候选块。整个过程在8级流水线下工作，只需1个周期就能得到1个SAD，最后1个周期得到最佳MV。因此，处理每个宏块共需16+16+8+288+1=329个时钟周期。
表1所示为几种ME硬件结构的性能比较，其中文献［4］提出的是典型的一维结构，可实时处理1 280×720@30fps视频，编码芯片主频至少需442.4 MHz。可见，一维结构不宜于高码率视频的实时编码。与文献［2］1307－1308，文献［5 －7］相同二维结构相比，本文设计的结构数据重用率高，虽存储访问带宽略高，但运算速度快，可实时处理1 280×720@30fps视频，编码芯片主频只需35.6 MHz。
图7 ME功能仿真波形图
表1 几种ME硬件结构的比较
* 表示实时处理1280x720@30fps视频所需频率。
4 结束语
不同的ME结构会有不同的硬件开销、数据吞吐和运算速度，适用于不同的应用场合。针对特定应用，在结构性能满足要求时，无须再通过增加并行度来追求极高的运算速度。本文设计的全搜索运动估计硬件结构，采用级联多块片内RAM的方式实现存储位宽为128 bit的RAM，搜索窗寄存器阵列可实现左、右和下3个方向的移位操作，获得最高的数据复用率，优化的PE单元减少了硬件资源消耗，数据控制简单高效。实验结果显示，提出的结构运算速度快，PE单元利用率高，芯片主频为35.6 MHz，可实时处理1 280×20@30fps视频，其性能满足高码率视频的实时编码要求，可用于无线显示适配器编码端部分。
