视频DSP中运动估计的快速实现

liyf

  
         
    摘要：运动估计是运动补偿技术的核心部分。本文在比较了VDSP中几种运动估计算法（光流分析法、块匹配法和象素递归法）的基础上，详细介绍了硬件复杂度较低、易于实现的块匹配法的典型电路。结合这种设计思路，设计了出具有良好前景的VDSP专用芯片。
关键字：运动补偿；运动估计；光流分析法；块匹配法

1概述：
视频是时变图象序列，是时空信号，与静态图象相比不仅在空间上存在冗余，而且在时间上存在冗余。视频的压缩一方面可以利用图象本身的空间相关性，还可以利用时间上的相关性。视频编码需要将帧内编码和帧间编码混合起来达到高的压缩率。帧内编码即单幅图象本身的编码过程，通常采用DCT变换编码方法。帧间编码可分为无运动补偿的差分脉码调制（DPCM）和有运动补偿的差分脉码调制。帧内编码通常是以宏块为单位的DCT编码，帧间编码是在帧内编码的基础上进行的，在不同帧之间以对应的宏块为对象进行DPCM编码。所谓运动补偿是指对宏块在下一帧的位置做运动估计，将该运动估计用于确定下一帧对应宏块的位置，再进行DPCM编码，使编码考虑了图象的运动分量，即对运动做了补偿，提高编码效率。
可见，运动估计是序列图象编码和计算机视觉领域中的一项关键技术，是运动补偿技术的核心部分，在目前已成为国际标准的电视图象编码方法中，从H.261、 H.263到MPEG-1、MPEG-2和MPEG-4，都无一例外用到了"简单帧间预测+运动补偿"的技术框架。本文针对VDSP芯片的运动估计部分的实现方法进行讨论。
2 运动估计的几种方案的工作原理及其比较
2．1帧间补偿技术简介
在对运动估计进行分析之前，我们先对补偿预测技术给予简要的介绍，其通常分为以下几个步骤：
⑴首先把图象分割为静止的和运动的两部分；图象分割是运动补偿的基础，但实际上要把图象分割成不同运动的物体比较困难，通常采用两种较简单的的方法。一种是把图象分为矩形子块，适当选择块的大小，把子块分为动和不动两种，估计出运动子块的位移，进行预测传输；另一种方法是对每个象素的位移进行递归估计。相比较而言，通常象素递归较块匹配法精度高，对多运动画面的适应能力也强，但只能跟踪较小的位移，且实现复杂。块匹配法(BMA)虽然精度低于象素递归法，但由于其位移跟踪能力强（不低于6-7象素/帧）且硬件实现比较方便，是目前最常用的运动估计算法，活动图象编码国际建议H.261和MPEG都采用 BMA作运动估计。由硬件实现的运动估计多采用BMA来实现，在后面我们对其硬件实现给予详细说明。
⑵估计物体的位移值；在一定的范围内，以每一象素的亮度分量作为比较量，根据前后两帧内子块所有象素的亮度分量的差的绝对值的和确定一个二维的运动矢量。即寻找前后两帧相差最小的图象块。
⑶用位移估值（即运动矢量）进行运动补偿预测；以位移估计和象素块之间的方差等指标为基础，为每个子块选出一种压缩模式。这一过程分支判断较为复杂，如在 h.261标准中，以位移块差分这一指标为基础，为每个块选择一种压缩模式，压缩模式一般有帧内模式、带有零运动矢量的帧间模式、运动补偿帧间模式和带有循环滤波的运动补偿帧间模式几种，补偿后得到预测图象,这一部分的工作量较大，用中小规模的硬件电路难以完成，一般采用软件实现。
⑷预测信息编码；得到预测图象后，将预测图象和实际图象进行比较，对预测误差图象进行编码，这时由于误差图象的能量较小，容易得到比较大的压缩比。
可以看出，在对图象的分割作了必要的简化后，对子块的估计或者说运动估计（ME）问题就成了必须解决的关键技术，在目前市场上的实时图象处理压缩芯片中，利用软硬件结合解决运动估计问题成为芯片的重要组成部分，其中，采用何种算法以及软硬件的搭配方式都直接影响到芯片的总体性能。
2.2 运动估计的几种方案比较
目前比较流行的运动估计方法有光流分析法[1]、块匹配法[2]、象素递归法[3]、贝叶斯法[4]，通过关于运动估计的各种算法工作原理的分析讨论、性能比较，可以得到如下的结论：块匹配法由于其位移跟踪能力强（不低于6"7象素/帧），且简单和易于直接用硬件实现，是目前最常用的运动估计算法，活动图象编码国际建议H.261、H.263和MPEG都采用BMA作运动估计。由硬件实现的运动估计也多采用BMA来实现。
2.3 块匹配法的具体步骤及算法
将当前帧划分为M x N图象子块,在上一帧中开辟大小为(M+2WX) x (N+2WY) 的一块搜索区，利用M x N子块在该搜索区寻求最优匹配来得到运动矢量的估值。衡量匹配好坏的准则有归一化相关函数（NCCF）、均方误差(MSE)和帧间绝对差（MAD）以及最大匹配象素统计（MPC）等。采用四种准则所得的估值结果差别不大，因MAD便于计算和硬件实现，所以用的较多。
我们设计的VDSP芯片中就采用的是MAD块匹配法，有八个运动估计协处理器，它可以利用我们设计的VDSP中的并行矢量运算器同时处理64对象素的比较，并且通过一个连续的的比较过程可以找出最佳的匹配块。简单的讲，其实现过程如下，在一个CPU的时钟周期内，并行处理器从内存中取出15个8位的操作数通过交错算法或线型算法同寄存器中的象素的参数值完成64对象素的相减，在每行将其绝对值进行累加，多次累加后得到完整图象块的绝对值差，通过每行绝对值累加和的比较得到最佳匹配块，从而得到与此块相对应的运动矢量。
3 VDSP芯片运动估计的实现
视频压缩算法是压缩视频帧与帧之间的时间冗余和帧内的空间冗余。其中时间冗余是指两帧或多帧之间的相似性。如果图象的变化不大，即可得到大的压缩比，帧和帧之间的相关性的测量通常是采用象素亮度绝对值差的和来得到的。运动估计包括搜索在目标帧中与目标块（通常大小为16x16象素大小）最相近的块，运动估计器就是通过比较绝对值差的大小来获得最佳匹配块。
3.1 VDSP芯片的结构
我们设计的VDSP芯片是一种高速的图象处理DSP芯片，在100兆时钟下完成16X16的运动估计平均需要四个时钟周期。它具有高度并行的处理器结构以及巧妙的指令系统。在每个我们设计的VDSP芯片中，有一个标量处理器和八行四列的矢量处理器，每行的并行处理单元后有一个运动协处理器专用于运动估计。在长度为32位的指令中，包含标量操作部分和矢量操作部分，标量操作的重要用途之一就是为流水线的下一级的矢量运算提供内存操作数地址。结构简图如图1所示：




图1我们设计的VDSP芯片结构简图
3.2 运动估计协处理器结构
在协处理器中主要分为扩展寄存器、绝对值累加树和最佳匹配选择器，下面我们对其结构和功能分别给予介绍。
3.2.1
(1) PixelDist：在v_PixelDist_xxx指令时，存放图象块比较的中间结果，将每次得到的结果的绝对值累加和与上次的结果叠加后再放入到这个寄存器中;
(2) PixelBest：在v_PixelBest_xxx指令时，将PixelBest原先的值与PixelDist和当前累加树之和进行比较，将结果小的值放在这个寄存器中;
(3) MatchCount：每次v_PixelBest_xxx指令时，将此寄存器累加一，作为图象块的标识;
(4) BestMatchCount：在v_PixelBest_xxx指令时，此累加器保存绝对值差最小的图象块的标识。
3.2.2 绝对值累加树
我们设计的VDSP计算象素块差的方式有四字节和八字节方式两种。四字节方式是计算四个8位象素的绝对差，而八字节方式是计算八个八位象素的绝对差。在一个周期中，四个象素或八个象素的绝对差可以被计算出来并且被累加到象素绝对差的寄存器当中。其数据流图如图2所示。
计算象素块差的第一步是计算象素对的差，这是通过矢量处理器的ALU完成的。在四字节方式下，一次计算四个8位的象素对的差并将差寄存在寄存器中。而在八字节方式下，一次计算八个8位的象素对的差并将其寄存在寄存器中。为了保持精度，寄存器中的存储方式为9位。
第二步是计算出差的绝对值。这是通过第一步所得的差的符号位来完成的。如图2所示，S0，S1到S7代表符号位。如果差为负值（符号位为1），则将各个位取反（通过符号位与各位取异或得到）之后，再在求和树中加符号位（实际上综合整个树，对负数进行相加运算的是其补码）。如果差为正，不需要任何的变换。
第三步是求绝对值的和，如图2所示，在这一步中，运用了一个求和树来完成求和的工作。在四字节方式下，八个差中有四个为零，不对结果产生影响。在树结构中，每一阶段操作数的数量减半，第一阶段，求和的操作数被减为四个。第二阶段，求和的操作数被减为两个。第三阶段，得到了一个初步结果。在每一个阶段中，为保持精度，必须将附加的一位加到结果当中。可以看到，在第三步的七个求和节点上，将第一步得到的符号位分别加到结果当中，这正是负数取补码的要求，理论上说，符号位在哪个节点无关，但必须注意将所有符号位全部加上
第四步也就是绝对值累加和的最后一步，从而计算出一个区域或块中所有象素的差。在这最后一个节点上，同时也完成了将第三步所剩的最后的一个符号位进行累加的功能。符号位全部累加到和中，且每个符号位只能累加一次。





图2 运动估计协处理器结构
3.2.3 最佳匹配选择器
最佳匹配也就是通过计算得到的与目标象素块最相似的象素块。为了加快整个图象处理速度，这一寻找最相似象素块的部分是通过运动估计协处理器的一部分专用硬件来实现的，从而运动估计器在寻找最相似象素块时可以得到最快的处理速度。其处理流程图如图3所示。




图3 最佳匹配选择器处理流程图
最佳匹配的寻找过程是一系列累加和比较的过程，将块内（这个块通常为16x16大小）的所有象素点的差值全部累加起来，再利用PixelDist和PixelBest寄存器和一个比较器就能完成最佳匹配的选取。
对PixelDist和PixelBest寄存器的的初始化是通过对PixelDistAll和PixelBestAll两个虚拟扩展寄存器来完成的，一旦有对其的写入操作，则将八个运动估计协处理器中的PixelDist清零，相应的将PixelBest寄存器置为最大值。一般来讲，在初始化后，就开始一次运动估计的过程，应该指出的是在这之前应将所要比较的两幅图象之一调入到PAU阵列中的寄存器中，另一幅图象的数据则是在比较的过程中通过并行单元与数据CACHE的交叉网络实时调入的。比较是在PixelDist与本次累加树之和同PixelBest这两个寄存器之间进行的。如果PixelBest 中的值为小，则不进行任何的操作；如果PixelDist中的值小，则将PixelDist的值写入PixelBest中，相应的将MatchCount 的值写入BestMatchCount寄存器中。
MatchCount寄存器中的值为进一步递增的值，其目的是为识别最佳匹配块而设置的，其值不能超过4095，否则将产生溢出。
3.3 运动估计相应软件过程简介
第一步: 图象数据的调入：利用v_load 指令将要比较的两幅图象之一的数据写入到PAU阵列的窗口寄存器中;
第二步: 寄存器初始化：利用对虚拟标量寄存器PixelDistAll和PixelBestAll的写入完成;
第三步: 图象块绝对值差累加：利用连续的v_PixelDist_xxx指令完成，注意运算过程中从内存中实时调入另一幅图象的数据;
第四步: 图象块累加和比较：利用v_PixelBest_xxx指令完成，得到8个最小值和其标识;
第五步: 将得到的八个最小值读入到标量寄存器中，再次比较得到真正的最小值及其标识， 这个标识经过换算即为要求的运动矢量;
（至此完成了一个图象块运动矢量的求解）
第六步: 根据所有图象块的运动矢量可以得到预测图象;
第七步: 预测图象与实际图象得到差值图象;
第八步: 将差值图象和运动矢量进行压缩传送;
第九步:在接收端利用差值图象和运动矢量以及参考图象将当前图象还原。
4 结束语
文中介绍了我们设计的VDSP视频并行处理芯片中专用运动估计部分的实现方案，并对其硬件实现给出了具体分析，其实现方法为专用运动估计芯片和通用视频 DSP芯片的设计提供了实用的电路，我们设计的VDSP中并行处理与运动估计相结合，可以完成静态、动态图象压缩以及小波变换和图象编解码功能，已在电视电话会议系统中得到广泛应用。就其运动估计部分而言，电路比较典型，易于实现，结合这种设计思路设计出新的专用芯片具有比较好的前景。
         
          [/td]
        [/tr]