H.264快速帧间编码模式选择算法

摘 要：本文提出了一种用于H.264编码的快速帧间编码模式选择算法。这种算法有效地减少了原图像编码过程中待测编码模式的数量，从而提高了编码速度。
关键词：H.264；块模式；下采样；MVFAST

引言
H.264是新一代的视频编码标准，大幅度提高了编码效率和图像质量。然而，H.264编码效率的提升是以计算复杂度的增加为代价的。与MPEG-4简单配置相比，H.264主要配置下解码复杂度提高了3倍以上，而编码复杂度更是增加了10倍。
实验表明，H.264编码效率的提高有很大部分来源于不同块形状的运动估计与R-D优化，然而这一模式选择增加了计算复杂度。如果能够事先对待测模式进行筛选，获得一个相对较小的待测模式集，便可有效提高编码速度。本文提出了一种基于低分辨率缩略图的预编码算法，可以加速帧间块模式的选择。

快速帧间编码模式选择算法
此算法的主要思想是首先将原始图像下采样为2:1的低分辨率缩略图，然后对此缩略图进行编码和R-D优化，选择出编码缩略图中每个8×8块所使用的帧间编码模式。在编码原始图像的一个16×16宏块过程中，参考缩略图中对应位置的8×8块所使用的帧间编码模式，并将其映射为一个待选模式的子集，使用这个子集中的模式进行编码和R-D优化，并最终选择出最优的帧间编码模式。由于对2:1的低分辨率缩略图编码所耗时间较少(基本上为对原始分辨率图像编码时间的1/4)，而经过预编码后待测模式子集将变得很小，从而在整体上提高了编码速度。此算法对应的编码器结构如图1所示。
预编码过程
在进行帧间(P帧或B帧)图像编码时，首先使用7段滤波(-1,0,9,16,9,0, -1)在水平和竖直方向上对原始图像和参考图像进行2：1的下采样，获得低分辨率缩略图。若下采样后图像的长或宽不是16的整数倍，则扩展成16的整数倍，扩展出的点使用边界点的值。
预编码与实际编码过程基本相同，区别在于：
?H.264在编码过程中是基于16×16宏块做R-D优化的，根据2:1的比例关系，缩略图中就应以8×8块做R-D优化。因此预编码过程中不使用16×16、16×8和8×16模式，而只使用基于8×8子划分的块模式。
?缩略图中的运动搜索范围应该减少到原图像运动搜索范围的一半。
?由于低分辨率下R-D优化的结果并不一定是原始分辨率下最优的，在缩略图编码的R-D优化过程中，应同时保存最优和次优的模式作为对原始分辨率图像编码的候选模式。
预编码器将获得的最优和次优宏块帧间编码模式，以及在此模式下获得的所有运动向量输出给实际编码器。
实际编码过程
在编码原始图像的一个16×16宏块过程中，参考缩略图中对应位置的8×8块所使用的帧间编码模式，并将其按1:2比例关系映射为一个待选模式的子集。
H.264中定义的最小块为4×4的块，由于预编码的块模式和实际编码的块模式存在1:2的比例关系，因此预编码过程中获得的块模式无法反映出实际编码过程中8×8以下的块模式。在编码过程中使用8×8以下的小块，这是因为宏块中包含了多个独立运动的对象，而使用较小的块编码可以使各个独立运动的对象包含在不同的块中，分别做运动估计，从而提高了编码的效率。因此，可根据宏块中不同对象的分布来对8×8以下的模式进行预判。
首先使用Sobel边界算子对宏块中对象的边界进行提取。宏块中的每一象素可以得到一边界向量：
dxi,j=pi-1,j+1+2×pi,j+1+pi+1,j+1-pi-1,j-1-2×pi,j-1-pi+1,j-1
dxi,j=pi+1,j-1+2×pi+1,j+pi+1,j+1-pi-1,j-1-2×pi-1,j-pi-1,j+1 (1)
定义：
(2)
(3)
建立水平和竖直方向上的边缘方向直方图(Edge direction histogram)。

(4)
k=1表示水平方向，2表示竖直方向，3表示其他方向。
8×8以下的块模式选择根据对象边界的方向划分。
if(Histo(1)>2xHisto(2) and Histo(1)>2x Histo(3))
选择8×4模式
else if(Histo(2)>2xHisto(1) and Histo(2)>2x Histo(3))
选择4×8模式
else
选择4×4和8×8模式
预编码获得的运动矢量同样可被利用。本算法中运动估计部分采用了MVFAST算法，而MVFAST算法搜索前设置一个初始运动向量集，包括了(0，0)向量和相邻块的运动向量。搜索前首先对运动情况进行分类。
Vi(xi,yi)∈初始向量集
定义：

若motion=low，选用小菱形模式进行菱形运动搜索，直至搜索中心的SAD值最小，搜索中止。
若motion=medium，选用大菱形模式进行搜索，直至搜索中心的SAD值最小。以此点为搜索中心，转入小菱形模式进行搜索，直至搜索中心的SAD值最小。搜索中止。
若motion=high，则需首先对初始向量集中的运动向量进行测试，获得SAD值最小的点作为搜索中心。选用小菱形模式进行菱形运动搜索，直至搜索中心的SAD值最小，搜索中止。
在本算法中，建立了两个初始运动向量集：S1包括(0，0)向量和相邻块的运动向量，S2包括了预编码过程中获得的所有运动向量分别在水平和竖直方向上放大2倍后的向量。首先检测S2中的所有运动向量，计算SAD值和最小SAD值：
(5)
若SADmin小于门限T1，则停止运动搜索过程，产生最小SAD值的运动向量作为最终的运动向量。这里T1可以设置为被检测块类型所包含的象素个数。
若SADmin不小于门限T1，S1和S2合并为初始运动向量集S，并使用MVFAST运动搜索算法搜索。
在算法中利用预编码过程中产生的运动向量，可以使初始搜索中心更为精确。

测试结果
该快速帧间块模式选择算法在JVT提供的参考软件JM61上实现。为了加快测试速度，事先对JM61做了适当优化，运动估计采用了MVFAST算法，帧内预测采用快速帧内预测算法。在下面，称未使用快速帧间块模式选择算法的JM61编码器为JM_OLD(带有MVFAST＋快速帧内预测算法)，而实现了快速帧间块模式选择算法的JM61编码器为JM_NEW(带有MVFAST＋快速帧内预测算法＋快速帧间块模式选择算法)。
这里分别对5种标准测试序列进行了测试。QP值取20~40，步长为2。其中对于JM_OLD，分别测试了使用全部7种帧间块模式、仅使用16×16一种块模式以及仅使用16×16和8×8 两种块模式的情况用于同JM_NEW的PSNR图做比较。
测试环境为P4 1.5GHz PC，256MB内存，WINDOWS XP操作系统。测试序列如表1所示。
测试结果如表2所示。由于篇幅限制，表中仅列出了QP=24、28、32，JM_OLD使用全部7种块模式进行帧间预测时，同JM_NEW之间的性能比较。
从测试结果来看，这种快速帧间模式选择算法能使编码速度提高将近一倍，同时码率增加不超过3%，PSNR下降不超过0.2dB。

结语
本文提出了一种用于H.264编码的快速帧间模式选择算法。此算法首先对视频图像进行2:1的下采样，以获得长宽各为原图像1/2的低分辨率缩略图，并对此缩略图进行R-D优化获得低分辨率下帧间编码宏块使用的最佳块模式，然后将该最佳模式映射为原分辨率图像中对应宏