基于H.264视频压缩快速运动的估计算法

0 引言

H.264采用了减少视频图像各帧间冗余度的运动估计算法。运动估计算法传统的有全搜索(FS)、三步搜索(TSS)、新三步搜索(NTSS)、四步搜索(FSS)等;常用的是钻石搜索(DS)和非对称十字交叉多层次六边形格点运动搜索算法(UMHexagonS)。运动估计是整个视频编码中运算量最大的模块，可占整个软件编码器运算量的70%以上。因此视频系统中编码器的复杂部分取决于运动估计算法体系结构的复杂性。

1 运动估计算法分析

1.1 钻石搜索(DS)算法

DS算法即钻石搜索算法，被MPEG-4国际标准采用并收入验证模型VM(Verification Model)中，是MPEG-4建议采用的快速运动估计算法。 DS算法采用了两种搜索模板，分别是有9个检测点的大模板和有5个检测点的小模板。搜索时先用大模板LDSP在搜索区域中心及周围8个点处进行匹配计算，当最小块误差出现在中心点处时，将大模板LDSP换为SDSP，再进行匹配计算，这时5个点中的MBD(Minimum Block Distortion)即为最优匹配点;否则，改变中心位置，仍用LDSP重复计算。

1.2 菱形十字搜索(DCS)算法

菱形十字搜索算法(DCS)算法是在DS算法基础上改进而来，DCS的匹配模板是建立在两种不同的搜索模板之上的，即大菱形十字型(LDCSP)和小菱形十字型(SDCSP)，如图1所示。其中，十字型可以对应于实际的运动的矢量分布，而交叉型则是为了加速搜索效果。

edatop.com

DCS算法在进行运动估计匹配运算时，有三种可能的情况：

(1)若MBD点位于LDCSP中心位置，说明图像是静止的，DCS算法一步结束;

(2)若MBD点位于LDCSP小十字位置，说明图像的运动较小，则在此基础上按照SDCSP模板反复进行交叉搜索。

(3)若MBD点位于LDCSP大十字位置，说明图像的运动较大，则在此基础上按照LDCSP模板反复进行交叉搜索。

由此可以看出，DCS算法的优点是，可以根据图像的运动类型(如上述三种情况)，白适应选择下一步相应的搜索模板，使搜索与图像内容有关(基于内容的搜索)，从而得到较好的搜索效果;DCS算法的搜索并不一定要经历模板由大到小的必然过程，有时一步即可完成搜索;用DCS搜索时，十字形模板对应于实际的运动矢量分布，交叉形模板则有准确性“聚焦”特性，这从本质上体现了DCS是粗定位和准确定位的有效结合。

edatop.com

实验结果及说明

用搜索时间和PSNR值两个指标来验证DCS的性能。本节实验用到的所有视频文件均为QCIF(Quartet commonintermediate format)格式。实验以主频1．8GHz的PC机上运行的VisualC++6．0为平台。测试对象为：missa、salesman、news、grandmother、foreman、carphone、claire，搜索范围为16×16的矩形框，量化范围为2～12，测试序列中每帧图像的大小为176×144。

4．1 搜索时间的比较

为了时间测试的准确性，测试时采用的是VC++提供的两个精确时间函数：QueryPerformanceFrequency()和OuerPerformanceCounter()精度对标准测试序列missa、salesman、news、grandmother、foreman、carphone进行精确测定，得表1(数据均为三次测量所求得的平均值)。

从表1可知：a．FS搜索效果最佳，但耗时太长,DS算法有较大改进，可以实现实时压缩,DCS比DS，运行时间都有不同程度的减少，故DCS算法在搜索速度有优势。b．从单个序列来看，DCS算法对missa和salesman时间优化最为显著，分别只占FS算法的7．42％、7．50％和DS算法的98．17％、97．49％,对carphone序列的搜索速度也有很大优化，占FS搜索算法的7．97％和DS算法的97．82％。综合视频特性可知：DCS算法针对运动平缓的视频对象搜索速度优化明显。

4．2 信噪比的比较

对标准测试序列claire和carphone序列进行测定，计算PSNR得表2。

edatop.com

表2中FS的平均PSNR最高，达到42．38，但搜索时间最长,DS的PSNR最低，为42．31，而DCS为42．35，高于DS算法，且仅低于FS算法0．03dB。从单个序列来看，DCS算法对claire的优化程度最大，超过了FS的PSNR值，说明DCS算法身体静止仅面部表情运动特点视频适用。用DCS算法计算得到的carphone的PSNR值虽然低于FS算法，但高于DS算法,missa序列的DCS算法的PSNR值和FS、DS法的相差不大。故DCS算法在搜索速度、图像质量上均有保证。

5 结束语

本文从搜索时间和图像质量两方面对各种块匹配运动估计算法进行了性能分析比较。实验结果表明，将菱形十字交叉搜索算法和阈值判断结合，在搜索速度方面，有很大程度的优化，而且能得到与FS、DS搜索算法相当的图像质量。DCS算法针对运动平缓的视频作用明显，由此推知该算法适用于电视电话、远程教育等实时视频压缩。