一种基于子搜索格雷码核的快速视频块运动估计算法*

王　冠，罗　珅，葛　迦

(1.中国电子科技集团公司第二十八研究所，南京210007; 2.东南大学影像科学与技术实验室，南京210096)



一种基于子搜索格雷码核的快速视频块运动估计算法*

王冠1*，罗珅1，葛迦2

(1.中国电子科技集团公司第二十八研究所，南京210007; 2.东南大学影像科学与技术实验室，南京210096)

摘要:快速视频块运动估计是视频编码中的一个重要问题。在格雷码核(GCK)算法的基础上，提出一种改进的子搜索格雷码核(Sub-GCK)算法。理论上的计算复杂度分析表明:提出的子搜索格雷码核算法的运算量大约为原始格雷码核算法的22.1%。实验比较了子搜索格雷码核算法、原始格雷码核算法和其他几种常见的运动估计算法的编码性能，结果显示:新算法在保证编码质量的前提下，有效降低了运动估计时间，时间约为原始格雷码核算法的41.9%。

关键词:视频编码;运动估计;子搜索格雷码核;计算复杂度;运行时间

项目来源:江苏省自然科学基金项目(BK2012329) ;国家自然科学基金项目(61201344，11301074)

随着通信和网络技术的快速发展，人们的通信方式已经从信件、语音发展为可视电话等交互式视频信息模式。据统计通过视觉途径获得的信息量占人类感官获得信息量的60%［1］以上。视频信息被认为是多媒体信息中最重要的信息［2－6］。

H. 264的编码过程包括预测及运动估计、变换及量化、熵编码等。其中，基于块匹配的运动估计过程是所有编码过程中最费时和复杂的步骤，在H. 264中占50%以上的运算量［7］。所以，优化运动估计算法将大大减少编码复杂度和编码时间，降低对编码器硬件的要求。对运动估计算法的研究不仅在视频压缩的研究方面具有重要的理论意义，并且在商业和工业等领域也有着很高的实际应用价值。

基于块匹配的运动估计算法的优劣主要体现在3个方面:搜索速度、压缩码率以及图像质量，这些效果又主要由3个因素决定:匹配准则、初始搜索点和搜索策略。

(1)运动估计的匹配准则

运动估计匹配准则的实质是一类误差衡量函数，用以度量两个图像块的相似度。实际中常用的匹配准则包括:最小绝对误差和SAD (Sum of Absolute Difference)和投影绝对误差和SPAD(Sum of Projection Absolute Difference)［8］等。

(2)运动估计的初始搜索点

初始搜索点的预测是基于当前块和相邻帧匹配块在时间和空间上的相关性，使用相邻块的运动矢量对当前块的最佳起始搜索位置进行预测。大量实验证明，使用预测点作为起始搜索点，能够加快运动估计过程。

(3)运动估计的搜索策略

运动估计的搜索策略主要从搜索路径方面入手，通过减少搜索点数来达到降低运动估计计算复杂度的目的。国内外研究人员已经对此进行了许多研究，提出了一系列的搜索策略，主要包括:全搜索算法FS(Full Search)，三步搜索算法TSS(Three Step Search )［9］，菱形搜索算法DS (Diamond Search)［10］。其中菱形搜索算法因为同时具有较高的搜索速度和精度而被被纳入MPEG－4标准的验证模型。最近，Ben-Artzi等人提出基于格雷码核GCK(Gray Code Kernel)［11］的滑动窗快速算法。Moshe和Hel-Or提出利用GCK进行视频快速运动估计［12］，比菱形搜索算法具有更快的搜索性能。

图1　构造一维GCK的树结构(k=3)

针对快速视频块运动估计问题，在格雷码核(GCK)算法的基础上，下面提出一种改进的子搜索格雷码核(Sub-GCK)算法，在保证编码质量的前提下，尽可能降低计算复杂度，从而保证视频编码的实时性。

1　格雷码核［11］

1.1一维格雷码核

定义1:

式中:αkv表示数αk乘以核v，“Ⅱ”表示串联过程。该组核的递归定义可以由一个深度为k的二叉树来表示，图1为k= 3的二叉树。处于二叉树第i层的节点就是的核，包含2i个核。图中二叉树的树叶就是V(3)s的8个核，树枝上标记的是α的值，用以产生这些核。

定义2:当序列α=α1，α2，…，αk，αi∈{ +1，－1}唯一确定了一个核，则称该序列为v的α索引。

定义4:连续α相关的一组有序核v0，v1，…，vn组成格雷码核GCK(Gray Code Kernels)，该序列称为格雷码序列GCS(Gray Code Sequence)。定义5:给定两个α相关的核，它们的和vp与差vm定义如下:

GCK算法主要根据两个α相关的核v+，v－∈在空间上的相关性来做快速计算的。设两个α相关核v+，v－的索引序列分别为()、()，它们存在一个共同的长度为Δ= 2r－1(r为索引序列中出现不同索引的序号)的向量，则以下关系式成立:

式中: 0Δ表示由Δ个零组成的向量。由上式推导出以下公式:

设b+，b－分别为信号序列x与滤波核v+，v－的线性卷积，即:

则b+(i)，b－(i)有如下关系:

上式提供了一种计算信号与GCK滤波核线性卷积的快速算法(图2)。当获得某个线性卷积结果b－(b+)后，只需要两次运算就能得到与之α相关的滤波核对应的线性卷积结果b+(b－)，并且与核大小无关。对于定义1，当s=［1］时，就是一维沃尔什－哈达玛变换WHT(Walsh-Hadamard Transform)滤波核序列。

图2　一维信号与GCK滤波核线性卷积的快速算法［11］

1.2二维格雷码核

二维格雷码核算法的输入信号和滤波核都为二维。

定义6:设v01(i1，i2)、v02(i1，i2)是两个二维滤波核:

若v1，v2为α相关的一维滤波核，并且有一个共同的长度为Δ的向量，由文献［7］可知v01(i1，i2)、v02(i1，i2)存在如下关系:

若b1=I·v01为图像在滤波核v01上的滤波结果，若b2=I·v02为图像在滤波核v02上的滤波结果，则有如下关系［7］:

由上式可知，在二维情况下，计算图像的一个滤波值需要两次运算。当s=［1］时，v01(i1，i2)即为二维沃尔什－哈达玛(WHT)滤波核，所以可使用式(8)来实现WHT的快速算法，即滑动窗WHT算法。图3(a)描述了8×8的二维WHT滤波核，图3 (b)描述了我们取前m个投影值的顺序。

2　基于GCK WHT的运动估计方案［12］

文献［12］提出了一种基于GCK WHT算法的快速运动估计方案:设或为第j帧图像Ij在位置(x，y)上的宏块，宏块周围的搜索区域为SA)，使用序列Sq中的前m个二维WH滤波核。设宏块的第i个滤波值为。

对于第j帧图像做运动估计的过程:

(1)使用滑动窗WHT计算Ij中的所有宏块p(j)对应的前m个WH滤波值，将结果保存起来。

图3　二维沃尔什－哈达玛滤波核

(2)对于Ij中的某一宏块做如下计算

①计算参考帧Ij－1中搜索区域内每个宏块的前m个滤波值。

④重复步骤2。

3　改进的基于Sub-GCK WHT的运动估计方案

本文在文献［12］的基础上，提出一种改进的基于Sub-GCK WHT的运动估计方案。由式(8)可知，使用GCK WHT算法计算位置(i，j)下的WH滤波值时，需要使用位置(i，j－Δ)下的滤波值，所以GCK WHT算法，可以应用于子搜索区域的搜索中。在滑动窗GCK算法中，Δ=2r－1(r为两个α相关滤波核的索引序列中出现不同索引的序号)，最大搜索间隔Δ取决于用于运动估计的所有WH滤波核中r的最小值。由于实际中使用的WH滤波核对应的r最小为3，所以子搜索区域的最大搜索间隔Δ= 4。出于搜索精度的考虑，我们使用Δ= 2，在GCK算法的基础上提出一种子搜索格雷码核Sub-GCK(Sub Search GCK)运动估计方案，其过程如下:

对于第j帧图像做运动估计的过程:

(1)使用滑动窗WHT计算Ij中的所有宏块p(j)对应的前m个WH滤波值，将结果保存起来。

(2)对于Ij中的某一宏块做如下计算

①计算参考帧Ij－1中子搜索区域内每个宏块的前m个滤波值。

⑤重复步骤2。

4　改进方案的计算复杂度以及硬件实现复杂度分析

4.1计算复杂度分析及比较

假设加法、减法、取绝对值以及乘2操作均需要一次运算。设宏块大小为k×k，搜索范围为n×n，滤波核个数为m，m个滤波核中包含的所有黑色矩形块的个数为b，改进方案中步骤②取t个块，步骤③取q个块。以下我们将分析对单个宏块做运动估计时，5种搜索算法的计算复杂度。这5种搜索算法为全搜索算法(FS)、3步搜索算法(TSS)［9］、菱形算法(DS)［10］、GCK［12］以及提出的Sub-GCK。

用积分图［13］计算当前宏块的前m个滤波值需要3+3b+2(m－1)次运算。由于子搜索区域有n2/4个搜索点，并且计算图像块的一个滤波值需要2次运算，所以计算所有搜索点的投影值需要mn2/2次运算。步骤②，找出n2/4个搜索点中的滤波值最小的前t个点需要tn2/4次运算。步骤③，计算t个点的所有领域搜索点的滤波值需要8t［3+3b+2(m－1)］次运算。在这9t个点(包括t个点本身)中，找出滤波值最小的前q个点需要9qt次运算。步骤④，用SAD准则对这q个点做匹配运算得到最佳匹配点，需要q(3k2－1) +(q－1)次运算。所以，对单个宏块做匹配运算的计算复杂度为3+3b+2(m－1) +mn2/2+tn2/4+8t［3+ 3b+2(m－1)］+9qt+q(3k2－1) +(q－1)，简化为(8t+ 1) (3b + 2m + 1) + (2m + t) n2/4 + 3q (k2+ 3t)－1。表1比较了5种算法的计算复杂度(取实验中的m=5，搜索范围15×15)。注意GCK的计算复杂度受4个方面因素影响:宏块大小为k×k，搜索范围n× n，滤波核个数m以及块的个数q。

由于实验中我们使用的宏块大小为16×16，选取的较优候选块个数q=4，改进方案中第一次排除后剩下的候选块个数t = 3。所以，FS、TSS、DS、GCK以及Sub-GCK对应的运算量分别为172 800、19 200、11 904、10 193、2 253。改进后的算法Sub-GCK的运算量大约为GCK的22.1%。

表1　5种搜索算法的计算复杂度

4.2硬件实现复杂度分析

在这一小节，类似于文献［14－15］，我们将在乘法/加法器和蝶形处理器两种情况下分析提出的Sub-GCK的算法硬件实现中的空间－时间复杂度。

4.2.1乘法/加法器系统

文献［14］指出，在单乘法器硬件中(比如: DSP微机)，由乘法和加法共同决定执行时间。在这些情况下，以上5种算法的空间复杂度一样，都是一个乘法/加法器的空间。因此，空间－时间复杂度的大小主要决定于计算时间的长短。从表1看出，提出的Sub-GCK的硬件计算时间要优于其他5种算法

4.2.2基于蝶形计算的多核处理器

考虑到提出的Sub-GCK具有时序的特点，即利用前一个时间计算出来的投影值来计算当前的投影值，所以类似于文献［15］，我们可以采用串行硬件结构实现(即“串入串出”结构)。串行实现的过程中可以采用移位寄存器或者RAM实现数据的收集。对于大小为k×k的宏块，我们只需要2个加法器和2k个数据存储空间。

5　实验结果及分析

我们使用视频压缩标准H. 264的标准测试软件来进行实验，版本为JM86。PC配置为:操作系统Windows 7(32位)，处理器Intel(R) Core(TM) 2 Quad CPU Q8400 @ 2.66 GHz 2.67 GHz，内存4 Gbyte。选择的测试序列为City，Coastguard，Football，Motherdaughter，视频格式为YUV，大小为352×288。选择亮度分量的峰值信噪比(Y-PSNR)，比特率(Bit-Rate)以及运动估计时间(ME Time)作为比较参数。Y-PSNR能反应编码后视频图像的质量，Bit-Rate的高低反应视频的压缩效果，ME Time反应搜索算法的速度。

表2　5种运动估计算法(FS、TSS、DS、GCK、Sub-GCK)的视频编码结果比较

由表2可以得到如下结论:

(1)分析各视频序列编码后的Y-PSNR数据可知，编码后的视频质量由高到低依次是: FS、GCK、 Sub-GCK、DS、TSS，并且Sub-GCK的Y-PSNR与GCK非常接近，大约相差0.04 db，与FS相差大约0.18 db。所以，采用Sub-GCK与采用GCK的视频编码质量在客观上是基本相同的。

(2)分析各视频序列编码后的Bit-Rate数据可知，TSS、DS、GCK、Sub-GCK的比特率比全搜索算法(FS)的比特率分别多出约31.1%、4.6%、2.3%、3.4%。其中改进算法Sub-GCK与原算法GCK相比，多出约1.1%的比特率。

(3)分析各视频序列编码的ME Time数据可知，FS、TSS、GCK、Sub-GCK算法的运动估计时间比较稳定，DS算法由于搜索点数不固定，所以实际搜索时间不稳定(例如视频序列Football中DS的运动估计时间远大于TSS)，但是多数情况下DS的速度还是比TSS快。运动估计时间最少的是Sub-GCK，约为改进前的算法GCK的41.9%。这个数值高于理论值22.1%，初步判断是因为运动估计过程不仅仅包含搜索过程，还包括初始化和运动矢量预测等过程。

图4给出了Mother-daughter视频序列的利用FS、GCK、Sub-GCK算法编码前后的部分图像(原图、QP =28、QP =36三幅图)的主观效果图。由图4可知，虽然Sub-GCK算法的客观编码效果比FMEGCK略差，但是主观差异微乎其微，甚至与客观效果最好的全搜索算法(FS)相比，也很难看出两者之间的差异。

图4　Mother-daughter视频序列利用FS、GCK、Sub-GCK算法编码前后的主观效果图(a1)～(a3)分别为FS算法下的原图、QP = 28、QP = 36的主观效果图; (b1)～(b3)分别为GCK算法下的原图、QP=28、QP=36的主观效果图; (c1)～(c3)分别为Sub-GCK算法下的原图、QP=28、QP=36的主观效果图

6　结论

针对快速视频块运动估计问题，本文提出一种改进的子搜索格雷码核(Sub-GCK)算法。与其他几种运动估计算法的比较结果显示: Sub-GCK的Y-PSNR与GCK非常接近，因此Sub-GCK与GCK的视频编码质量在客观上是基本相同的，与FS略有差异。主观效果上，Sub-GCK与GCK基本相同，与FS的差异也很小。运动估计时间方面，消耗最少的是提出的Sub-GCK，约为改进前GCK算法的41.9%。综合来看，改进后算法Sub-GCK在保证编码质量的前提下，有效降低了运动估计时间，并且在编码速度和编码质量上都优于TSS、DS算法。

参考文献:

［1］胡栋.静态图像编码的基本方法与国际标准［M］.北京:北京邮电大学出版社，2003: 3.

［2］刘纪红，刘祚，李中帆.基于特征分析的人脸检测算法的DSP实现［J］.电子器件，2013，36(6) : 774－778.

［3］杨彦.基于人脸检测和多线索融合的实时人脸跟踪系统［J］.电子器件，2013，36(3) : 304－308.

［4］张美燕，蔡文郁.无线视频传感器网络有向感知K覆盖控制算法研究［J］.传感技术学报，2013，26(5) : 728－733.

［5］秦晅.一种视频图像目标抗遮挡跟踪算法［J］.指挥信息系统与技术，2011，2(6) : 50－54.

［6］罗丽莉，秦晅.基于视频图像序列的动目标跟踪定位技术研究［J］.指挥信息系统与技术，2011，1(3) : 22－27.

［7］Wiegand T，Sullivan G J，Bjontegaard G，et al.Overview of the H. 264/AVC Video Coding Standard［J］.IEEE Transactions on Circuits and Systems for Video Technology，2003，13(7) : 560－576.

［8］Li N，Mak C M，Cham W K.Fast Block Matching Algorithm in Walsh Hadamard Domain［C］/ /Computer Vision—ACCV 2006.Springer Berlin Heidelberg，2006: 712－721.

［9］Koga T.Motion-Compensated Interframe Coding for Video Conferencing［C］/ /Proc NTC’81.1981: 5－3.

［10］Zhu S，Ma K K.A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation［J］.IEEE Transactions on Image Processing，2000，9(2) : 287－290.

［11］Ben-Artzi G，Hel-Or H，Hel-Or Y.The Gray-Code Filter Kernels ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29(3) : 382－393.

［12］Moshe Y，Hel-Or H.Video Block Motion Estimation Based on Gray-Code Kernels［J］.IEEE Transactions on Image Processing，2009，18(10) : 2243－2254.

［13］Crow Franklin C.Summed-Area Tables for Texture Mapping［C］/ / Proceedings of the 11th Annual Conference on Computer Graphics and Interactive Techniques.1984: 207－212.

［14］Richards M A.On Hardware Implementation of the Split-Radix FFT［J］.IEEE Trans Acoust，Speech，Signal Process，1988，36 (10) : 1575－1581.

［15］Bi G，Aung A，Ng B P.Pipelined Hardware Structure for Sequency-Ordered Complex Hadamard Transform［J］.IEEE Signal Process Lett，2008，15: 401－404.

王　冠(1982－)，男，汉族，江苏南京人，现就职于中国电子科技集团公司第二十八研究所，硕士研究生，工程师。主要研究方向为信息系统软件研发与集成，52guantou@ 163.com。

Applications of Delay Precise Calibration in the Equivalent Sampling Based on FPGA

LIU Wenbin1，ZHU Mingri1*，ZHENG Danping2，YAO Xin1，PAN Kai1
(1.School of Electronic Engineering and Automation，Guilin University of Electronic Technology，Guilin Guangxi 541004，China; 2.School of Computer Science and Engineering，Guilin University of Electronic Technology，Guilin Guangxi 541004，China)

Abstract:For some high-frequency signals，such as ultra-wideband radar echo signal，because its bandwidth is often in the hundreds of megabytes and it is difficult to make real-time sampling，so equivalent sampling is usually implemented by adopting FPGA and in combination with programmable delay device.There is a difference between the delay value of each delay device and delay value of programmable delay device which exists temperature drift.Delay precise calibration based on FPGA is designed to minimized the delay value of programmable delay device with temperature drift.Experiment results show that the delay precise calibration is effective，and there is a good reference value in the acquisition of high frequency signals.

Key words:FPGA; equivalent sampling; delay precise calibration; temperature drift

中图分类号:TP391

文献标识码:A

文章编号:1005－9490(2015) 03－0699－07

收稿日期:2014－07－21修改日期: 2014－08－22

doi:EEACC: 7210G10.3969/j.issn.1005－9490.2015.03.046