CN1319384C - 硬件计算能力资源在运动估计中的优化分配方法 - Google Patents

Abstract

本发明公开了一种硬件计算能力资源在运动估计中的优化分配方法。H.264是新一代的视频编码标准，它吸取了现有视频编码标准的优点，同时又提出了许多新的算法，大幅度提高了编码效率和图像质量。然而，H.264编码效率的提升是以计算复杂度增加为代价的，需要有各种硬件的支持。因此针对不同硬件的不同计算能力而言，本发明提出了针对H.264中运动估计这一方面进行优化，从而达到较好的硬件资源分配的目的，进而取得最优化的峰值信噪比和码率，同时具有一定的可扩展性，可以实现运算复杂度与预测精度之间的均衡调节。

Description

硬件计算能力资源在运动估计中的优化分配方法

技术领域

本发明涉及在不同硬件条件支持下的多媒体技术领域，特别是涉及一种硬件计算能力资源在运动估计中的优化分配方法。

背景技术

H.264是ITU-T和MPEG组联合专家组JVT制定的目前最新的视频编码标准，这一编码标准可以获得很高的编码效率，尤其是在低码率方面比MPEG-4有明显的提高，非常适合低宽带、高质量网络视频应用的需要。但是，H.264为了提高编码效率，采用了许多高计算复杂度的算法，使得编解码计算量很大，因此对软硬件的要求甚高，同时也加大了编解码的难度。因为在通常情况下，很多方法无法实现在有限硬件支持的条件下，使得编码质量达到最优。

为了使H.264能比较容易的在低码率高时性的应用系统中实现，必须对其编码算法进行优化。对H.264编码器各个算法模块进行分析可以得出，运动估计模块的计算量占了整个编码器运算量的80％以上。因此，要对整个编码器进行优化，运动估计模块应作为首选。

H.264在进行运动估计时，首选进行运动向量预测，经预测获得初始运动向量以后，把这个初始的运动向量作为搜索中心进行块匹配搜索，收缩时采用全搜索算法，即给出搜索中心周围的一个范围，对该范围内矩形区域内的所有的点，都要计算一次匹配结果，从中选出最佳匹配点作为整像素搜索的结果。H.264的全搜索算法，优点是可以找到限定范围内的全局最优匹配结果，运动估计精度很高。其不足在于算法的复杂度太高，成为整个编码体系中最为耗时的一部分，因此，在尽可能小的质量损失前提下，提高运动估计搜索速度，是对H.264进行优化的关键。

目前由于各种硬件设备的特性不同，因此其运算能力和工作能力也不同，例如随着便携移动设备的普及，基于便携移动设备的多媒体应用大量涌现。由于便携移动设备存在计算能力弱等问题，而多媒体中，视频解码的计算复杂度相对较高，因此传统的视频编码方式用于便携移动设备，无法满足用户对多媒体尤其是视频技术相关应用的需求。因此针对不同硬件设备计算能力的不同，需要在运动估计时进行优化，从而达到较好的硬件资源分配的目的，进而取得最优化的PSNR和码率。

发明内容

本发明的目的在于提供一种硬件计算能力资源在运动估计中的优化分配方法，针对现有硬件具有不同计算能力的情况，在H.264做运动估计时需要进行优化，达到有限硬件资源的合理分配，最终取的最优的效果。

本发明采用的技术方案如下：

(1)基于宏块的绝对误差和的大小进行优先级划分，根据帧的大小分割成16×16的宏块，然后对当前帧的一个宏块与前一帧对应的宏块进行差值，得到绝对误差和，根据所计算的绝对误差和的大小对宏块进行优先级划分，并且当两个宏块的绝对误差和的差值在100的范围内时，认为这两个宏块的优先级等同，同时规定绝对误差和大的宏块其优先级越高，反之则越低，绝对误差和的计算公式如下：

$\mathrm{SAD}=\underset{i=0}{\overset{15}{\mathrm{\Σ}}}\underset{j=0}{\overset{15}{\mathrm{\Σ}}}|f(i,j)-g(i,j)|$

其中

SAD是绝对误差和，

f是当前帧的像素函数，

g为前一帧的像素函数；

(2)根据优先级的大小对当前优先级最高的宏块E(如果有相同最高优先级的宏块，则选择比较居中的宏块作为目标宏块)的左边A、上方B、右上方C的相邻宏进行运动估计，再把所得到的相邻宏块A、B、C的运动矢量MV_A、MV_B、MV_C和MV_median作为宏块E的候选预测点，最后对当前宏块E进行运动估计，计算当前宏块和其匹配的各参考宏块的误差，选择误差最小的宏块为最佳参考宏块，最后得到当前宏块E的运动矢量；

(3)如果当前有相同最高优先级的宏块，根据它们各自的相邻宏块(左边A、上方B、右上方C)已知的MV数目的多少进行选择，如果某宏块E相邻宏块已知的运动矢量数目越多，则把该宏块E作为目标宏块；

(4)根据当前计算能力的现况做出是否停止对该帧宏块的运动估计，如果判断为停止，则对剩下没有做运动估计的宏块认为其运动矢量等于0，同时准备对下一帧继续进行运动估计。

步骤(2)中在第一次选择最高优先级宏块时，如果当前有相同最高优先级的宏块，则把比较居中的宏块作为目标宏块E；

步骤(2)中对当前宏块E需要求出其左边A、上方B、右上方C相邻宏块的运动矢量。如果右上方C不在当前帧中，则选择左上方的宏块C’代替右上方宏块C；

步骤(2)中对当前宏块E的左边A、上方B、右上方C的相邻宏块求MV时，如果其SAD＜事先预设的值，则采用水平垂直搜索方法，否则采用菱形搜索法；

步骤(2)中对当前宏块E做预测时，候选预测点有(0，0)、MV_A、MV_B、MV_C、MV_median；

步骤(2)中对当前宏块E做运动估计时，计算当前宏块和其匹配的各参考宏块的绝对误差和，选择绝对误差和最小的宏块为最佳参考宏块，最后得到当前宏块E的运动矢量；

步骤(3)中如果当前有相同最高优先级的宏块，则根据它们的相邻宏块(左边A、上方B、右上方C)已知的运动矢量数目的多少进行选择，如果某宏块的相邻宏块已知的运动矢量越多，则把该宏块作为目标宏块。

本发明具有的有益的效果是：可以对各种格式的视频信号进行运动估计，尤其在硬件计算能力有限的情况下更能体现出该发明的优越性，如果在硬件计算能力很强的情况下，本发明并不影响运动估计后得到的最终优化结果，因为此时对于每一帧中的每一个宏块都做了运动估计。相反，如果在硬件计算能力有限的情况下，本发明充分体现了其内在的优越性，因为本发明提出的方法使一帧中那些绝对误差和较大的宏块首先进行运动估计，按优先级从大到小对各宏块进行运动估计，当然在运动估计期间，本发明也充分考虑到硬件的计算能力的限度，所以采用各种方法进行处理，从而达到最优化的效果。

附图说明

图1为已有的空间域中当前宏块与相邻宏块的位置关系示意图；

图2为本发明的宏块优先级判定方法示意图；

图3为已有的菱形搜索方法示意图；

图4为已有的水平垂直搜索方法示意图；

图5为本发明的目标宏块选择方法一示意图；

图6为本发明的目标宏块选择方法二示意图；

图7为本发明的目标宏块选择方法三示意图。

具体实施方式

本发明提出的用于在硬件计算能力有限的前提下对运动估计进行硬件计算能力资源合理分配的方法主要适用于具有不同计算能力硬件支持的条件下使用。主要按如下步骤进行：

1.宏块优先级的划分

把当前帧进行宏块的划分，分成16×16的宏块，然后把当前帧的一个宏块与前一帧对应的宏块进行差值，得到绝对误差和。再根据绝对误差和的大小对宏块进行优先级划分。当两个宏块的绝对误差和的差值在100的范围内时，认为这两个宏块的优先级等同。同时规定绝对误差和大的宏块其优先级越高，反之则越低。其中当前宏块与相邻宏块的位置关系见图1。

2.第一次选择优先级最高的目标宏块

选择当前优先级最高的宏块E时，如果没有相同优先级的宏块，则直接选择优先级最高的宏块作为目标宏块，否则如果有相同最高优先级的宏块，则选择比较居中的宏块作为目标宏块E。如图2所示当前有相同优先级的两个宏块E1和E2，它们的绝对误差和分别为S1、S2，如果|S2-S1|＜＝S(S＝100)时，则选择居中的宏块E1作为目标宏块。

3.采用不同的搜索方法

针对宏块不同的绝对误差和，采用不同的搜索方法，这是因为这样可以避免搜索多余和搜索不足。

1)采用菱形搜索法在绝对误差和较大情况下使用，从而可以快速找到最优点。分三种情况，图3a是x或y方向平移搜索，图3b是斜向平移搜索，图3c向中心搜索，分别如图3所示。

2)采用水平垂直搜索方法可以减少搜索点，并且达到较理想的效果。如图4所示：设一起始点，首先在其水平方向上寻找绝对误差和最小的点，再在水平最优点的垂直方向上寻找绝对误差和最小的点，搜索的结果为最终的最优点。因此搜索过程如下：搜索中心为1号点，在其左边与2号点比较，得出1号点的绝对误差和更小，再与1点的右边3号点进行比较，得出1号点绝对误差和最小，因此1号点为水平方向上的最优点，同理，继续在1号点的垂直方向上搜索，最终结果为5号点是最优点。

4.截止(Half-Stop)准则

当运动估计点的绝对误差和(SAD)＜T时，运动估计过程截止，其中T是域值，试验中针对16×16的宏块取定值为400。例如当检测到某个点的绝对误差和(SAD)为300，中止搜索过程，确认为最佳搜索匹配点。

5.选择优先级最高的目标宏块

如果当前有相同最高优先级且离散出现的宏块E_i、E_i+1、…、E_j(记为集合A，且1≤i，j≤M×N、i≤j，其中M×N是一帧总的宏块数，图中取6×6)，则根据它们的相邻宏块(左边A、上方B、右上方C，其中i≤p≤j)已知的运动矢量数目的多少进行选择。在判断过程中可能有多种情况，如下所示：

1)在这些优先级相同的宏块中，第一种情况希望找到唯一的一个宏块E_p，它的相邻宏块已知的运动矢量最多，此时可以把该宏块E_p直接作为目标宏块；如图5所示：E_p的相邻宏块A、B、C中有3个MV已知，而除E_p外的其它宏块E的相邻宏块已知的MV个数都不超过3个。所以选择E_p为目标宏块。

2)在这些优先级相同的宏块中，如果上述情况无法满足，即如果有多个离散出现的宏块E_m、E_m+1、…、E_n，同时它们的相邻宏块已知的运动矢量数目相同。则在这些宏块E_m、E_m+1、…、E_n中如果它们中的某一个宏块的相邻宏块已知MV≠0数目最多，则选择该宏块为目标宏块，如图6所示：E_q的相邻宏块有3个已知的MV且都不等于0，而除E_q外的其它宏块E的相邻宏块的已知MV都存在等于0的情况。所以选择E_q为目标宏块。

3)如果上述两个方法都无法选择出目标宏块时，则选择比较居中的宏块作为目标宏块。如图7所示：比较当前优先级相同的宏块E_t和E，选择比较居中的宏块E_t作为目标宏块。这样做的理由是居中的宏块作为其他宏块的预测值出现的概率比较大。

本发明已在自主开发的H.264编码器上测试通过，该编码器采用了H.264中如下技术：

1)参考帧个数：1个；

2)2)帧类型：I帧、P帧；

3)3)率失真优化(RDO)；

4)采用CAVAL熵编码；

5)整像素运动估计范围：16；

6)运动估计模式：16×16；

7)整像素搜索。

本发明方法的试验结果表明：在E-Sitsang-PXA255硬件的支持下，用foreman，mobile，news等视频系列进行测试，格式为CIF(352×288)，结果可达35fps左右。同时获得比较好的信噪比值和码率。

Claims (7)

1.一种硬件计算能力资源在运动估计中的优化分配方法，其特征在于：

(1)基于宏块的绝对误差和的大小进行优先级划分，根据帧的大小分割成16×16的宏块，然后对当前帧的一个宏块与前一帧对应的宏块进行差值，得到绝对误差和，根据所计算的绝对误差和的大小对宏块进行优先级划分，并且当两个宏块的绝对误差和的差值在100的范围内时，认为这两个宏块的优先级等同，同时规定绝对误差和大的宏块其优先级越高，反之则越低，绝对误差和的计算公式如下：

$\mathrm{SAD}=\underset{i=0}{\overset{15}{\mathrm{\Σ}}}\underset{j=0}{\overset{15}{\mathrm{\Σ}}}|f(i,j)-g(i,j)|$

其中

SAD是绝对误差和，

f是当前帧的像素函数，

g为前一帧的像素函数；

(2)根据优先级的大小对当前优先级最高的宏块E的左边A、上方B、右上方C的相邻宏块进行运动估计，再把所得到的相邻宏块A、B、C的运动矢量MV_A、MV_B、MV_C和MV_median作为宏块E的候选预测点，最后对当前宏块E进行运动估计，计算当前宏块和其匹配的各参考宏块的误差，选择误差最小的宏块为最佳参考宏块，最后得到当前宏块E的运动矢量；

(3)如果当前有相同最高优先级的宏块，根据它们各自的相邻宏块左边A、上方B、右上方C已知的MV数目的多少进行选择，如果某宏块E相邻宏块已知的运动矢量数目越多，则把该宏块E作为目标宏块；

(4)根据当前计算能力的现况做出是否停止对该帧宏块的运动估计，如果判断为停止，则对剩下没有做运动估计的宏块认为其运动矢量等于0，同时准备对下一帧继续进行运动估计。

2.根据权利要求1所述的一种硬件计算能力资源在运动估计中的优化分配方法，其特征在于：步骤(2)中在第一次选择最高优先级宏块时，如果当前有相同最高优先级的宏块，则把比较居中的宏块作为目标宏块E。

3.根据权利要求1所述的一种硬件计算能力资源在运动估计中的优化分配方法，其特征在于：步骤(2)中对当前宏块E需要求出其左边A、上方B、右上方C相邻宏块的运动矢量，如果右上方C不在当前帧中，则选择左上方的宏块C’代替右上方宏块C。

4.根据权利要求1所述的一种硬件计算能力资源在运动估计中的优化分配方法，其特征在于步骤(2)中对当前宏块E的左边A、上方B、右上方C的相邻宏块求MV时，如果其SAD＜事先预设的值，则采用水平垂直搜索方法，否则采用菱形搜索法。

5.根据权利要求1所述的一种硬件计算能力资源在运动估计中的优化分配方法，其特征在于：步骤(2)中对当前宏块E做预测时，候选预测点有(0，0)、MV_A、MV_B、MV_C、Mv_median。

6.根据权利要求1所述的一种硬件计算能力资源在运动估计中的优化分配方法，其特征在于：步骤(2)中对当前宏块E做运动估计时，计算当前宏块和其匹配的各参考宏块的绝对误差和，选择绝对误差和最小的宏块为最佳参考宏块，最后得到当前宏块E的运动矢量。

7.根据权利要求1所述的一种硬件计算能力资源在运动估计中的优化分配方法，其特征在于：步骤(3)中如果当前有相同最高优先级的宏块，则根据它们的相邻宏块，左边A、上方B、右上方C，已知的运动矢量数目的多少进行选择，如果某宏块的相邻宏块已知的运动矢量越多，则把该宏块作为目标宏块。