MPEG-4中运动估计模块的改进与优化(1)

     关键词  MPEG-4；视频编码；运动估计；半像素搜索

 

1  引言                   

      MPEG-4在数码摄像机、无线视频通信等多媒体通信领域有着非常广泛的应用。在通用DSP平台上实现MPEG-4的实时编码系统，是当前非常流行的一种方式，但MPEG-4算法的高复杂度，使得要在DSP上实现实时编码，必须要对现有算法进行较大的改进。MPEG-4视频压缩算法^[1]主要包括帧间预测、运动估计和补偿、DCT、量化、VLC编码等环节，其中运动估计是最耗时的部分。因此提高运动估计的效率是整个编码器优化的重点。目前已有多种快速运动估计算法，例如三步法（TSS）、新三步法（NTSS）及菱形算法（DS）等^[2][3]。这些算法基本上都是通过减少搜索点数来减小运算量，但主要都是在整像素搜索的范畴内提出的，对于半像素精度的运动估计一般没有考虑在内，本文通过消除半像素运动估计过程中的冗余计算，提出了对半像素估计算法的改进方案。

      MPEG4编码器中的运动估计部分一般由三个步骤组成。

（1）16*16大小宏块的整像素搜索

（2）16*16大小宏块的半像素搜索

（3）8*8大小块的半像素搜索

      图1中描述了运动搜索方法的基本流程[4]。在第一个步骤中将当前宏块与参考帧搜索区域中的各个整像素搜索位置处的参考宏块相匹配。然后第二步中以上一步中搜索得到的最佳匹配点为搜索区域的中心，将当前宏块与搜索区域中的半像素位置处的参考宏块相比较。最后以第二步中最佳匹配点为中心，在半像素位置分别匹配当前宏块中的四个8*8块。

图1、半像素搜索过程。X代表第一步中的搜索点，+代

表步骤2种的搜索点，O代表步骤三中的搜索点

 

      从上述步骤中可以看出，在第二步和第三步搜索过程中存在着大量的冗余搜索点。如果第二步搜索过程结束后，最佳匹配宏块位于中心点的话，那么在第三步过程中所有的可能搜索点相对于第二步来说都是多余的。当最佳匹配点不在中心时，这时候第二步和第三步搜索中的冗余情况如图2所示。图中标记重合处即为冗余搜索点。

图2、第二、三步冗余点。标记同图1

图3、第一、二、三步中的冗余点。标记同图1

       同样的道理，在第一、第二以及第三步搜索中也存在着大量的冗余搜索点。如图3所示。

与以上分析的情况类似，根据第二次搜索结果的不同，一样分为三种情况。当第二次搜索结束后，得到最佳匹配宏块位于中心时，就不再需要进一步的搜索。而当最佳匹配点位于搜索区域边上时，进一步的搜索会产生七个冗余搜索点，其中第二步和第三步之间有六个（图2）。最佳匹配点位于角上的情况下，同样会有七个冗余点。

      从上面的分析可以得知，如果能够有效消除半像素搜索中的这些冗余点，那么就可以很大降低运动估计中计算的复杂度。可以考虑将16*16大小宏块搜索分解为同时执行四个8*8大小块的运动搜索。这样的话已经在第一步和第二步搜索过程中执行过的8*8运动估计就不需要继续在第三步中重复了。第三步骤中冗余搜索点的判断条件可以简单归纳如下。