CN101090502B - 一种预测质量可控的快速运动估值方法 - Google Patents

Abstract

本发明公开了一预测质量可控的快速运动估值方法，为解决现有的快速运动估值搜索算法在预测质量和搜索速度之间缺乏可控性问题而发明。包括步骤A，当前宏块在参考帧中预设一搜索窗口，在所述搜索窗口中预测当前宏块的初始搜索中心位置；步骤B，判断当前宏块在参考帧中的最佳匹配点是否就是所述初始搜索中心位置；步骤C，如果不是，当前宏块相对于参考帧为运动状态时，调整搜索窗口大小；步骤D，对当前宏块按照一定比例采样后，得到若干像素块，对所述像素块进行统计分析；步骤E，根据统计分析结果，对方差最大的像素块进行预测质量可控的块匹配运算。本发明可减少运动估计的计算量，加快编码速度，并在预测质量和搜索速度之间增加可控性。

Description

一种预测质量可控的快速运动估值方法

技术领域

本发明涉及多媒体通信领域中的数字视频压缩技术，具体的说涉及视频压缩标准中的运动估值方法。

背景技术

视频数据的存储和传输需要对数据进行压缩编码，压缩就是从时域、空域两方面去除冗余信息，编码方法的选择不但要考虑压缩比、信噪比，还要考虑算法的复杂性，太复杂的编码算法可能会产生较高的压缩比和信噪比，但也会带来较大的CPU开销，影响视频通信的实时性。

视频压缩国际标准中，采用的均是带有运动补偿的预测编码与DCT变换编码相结合的混合压缩编码方法，运动补偿中运动估计的计算量是影响编码速度的关键因素。因此，对于设计一个高效快速的视频编码器而言，用较小的计算量进行运动估计来获得准确的运动矢量是至关重要的。

运动估计是视频编码和计算机视觉领域中的一项关键技术，在计算机视觉领域中，研究的重点更多地放在由物体的二维运动来估计其三维运动，而在视频编码领域中则更多地关心物体的二维运动。二维运动是由被拍摄物体的运动和摄像机的运动共同造成的，二维运动估计方法有光流分析法、像素递归法和基于块的匹配方法等。

光流分析法的优点是能够探测独立运动的对象，不需要预先知道场景中的任何信息，并且可用于摄像机运动的场景，但光流分析法计算复杂耗时，除非有特殊的硬件支持，否则很难实现实时探测。

像素递归法的出发点是通过对灰度的梯度变化进行分析来求像素的位移，由于该方法的最小搜索单元是一个一个的像素点，因而对物体的运动有较高的灵敏度，运动估计的精度也高，对复杂运动画面具有较强的适应性，但它跟踪的位移范围很小，另外，由于像素递归法对位移的估计是通过梯度运算得到的，所以其运算代价大，硬件实现的复杂度高。

基于块的匹配方法将当前帧划分为若干个M*N大小的图像子块，利用M*N子块在上一帧中开辟的搜索区根据某种匹配准则寻求最优匹配来得到运动矢量，该方法相对简单且易于直接用硬件实现，是目前最常用的运动估计算法，视频编码国际标准中都采用基于块的匹配方法进行运动估计，同时由硬件实现的运动估计也多采用基于块的匹配方法来实现，因此，本发明研究基于块匹配方法的运动估计算法。

基于块的匹配方法中，衡量匹配好坏的准则有互相关函数(CCF)、均方误差(MSE)和绝对差值和(SAD)等，采用三种准则所得的估值结果差别不大，因绝对差值和的计算不需要进行复杂的乘法运算，计算量相对较小，所以用的较多。

在已知匹配准则的情况下，如何搜索匹配误差最小的块就是基于块匹配的运动估计搜索算法所要解决的问题.匹配块的搜索并不需要在整帧图像上进行，一般来说，一个块的运动分布一般集中在该块位置附近，因此，块匹配的搜索只需在一定的范围内进行.假设块的运动分布在水平和垂直方向上是各向均匀的(即不在其中某个方向上占优)，那么搜索范围应该是以当前块所在位置为中心的正方形，显然，最佳的块匹配搜索算法是全搜索块匹配算法(FS)，它搜索参考窗中的所有参考位置，精度高，硬件易实现，是目前应用最为广泛的运动估计算法，但其运算量非常大，将耗费编码器一半以上的计算资源.基于此，许多学者提出很多基于减少搜索位置数的改进型块匹配算法，如三步搜索法(TSS)、二维对数搜索法(2DLOG)、共扼方向搜索法(CSA)、新三步搜索法(NTSS)、四步搜索法(4SS)、环状搜索法(DS)等.

近来，一些快速搜索算法在不减少搜索位置数的情况下，通过宏块降采样，如交替降采样搜索算法(ASSA)，或按照某种渐进累积的失真准则快速判断参考宏块是否为最佳匹配宏块，如标准化局部失真搜索算法(NPDS)，来减少实际参与运算的像素点数目，不仅提高了运算速度，并能尽可能地找到全局最优值，获得接近于全搜索算法的图像质量。

三步搜索法(TSS)、二维对数搜索法(2DLOG)、共扼方向搜索法(CSA)、新三步搜索法(NTSS)、四步搜索法(4SS)、环状搜索法(DS)等快速块匹配算法均是利用一定的算术准则通过减少搜索位置数来节省计算资源，虽然比起全搜索块匹配算法大大减少了运算量，但往往只能找到搜索窗内的局部最优值，而不能找到全局最优值，使估计出的运动矢量信息不够准确，影响解码后的重建图像质量。

交替降采样搜索算法(ASSA)、标准化局部失真搜索算法(NPDS)均是通过减少块匹配运算中实际参与运算的像素点数目来提高运算速度，能尽可能地找到全局最优值，获得接近于全搜索算法的图像质量。但是，这些算法在预测质量和搜索速度之间缺乏可控性，且其搜索速度与全搜索算法相比提高的理论极限均为16倍，还有待改进。

发明内容

针对上述快速运动估值搜索算法的不足，本发明提供一种预测质量可控的快速运动估值方法(PQAS)，该方法通过对搜索窗中所有位置进行搜索来尽可能地找到运动估计的全局最优值，通过有针对性地选择某些像素点进行块匹配运算来减少运动估计的计算量，加快编码速度，并在预测质量和搜索速度之间增加可控性。

为达到上述目的，本发明采用以下技术方案：一种预测质量可控的快速运动估值方法，包括如下步骤：

步骤A，当前宏块在参考帧中预设一搜索窗口，在所述搜索窗口中预测当前宏块的初始搜索中心位置；

步骤B，判断当前宏块在参考帧中的最佳匹配点是否就是所述初始搜索中心位置；如果是，则当前宏块相对于参考帧是静止状态，当前宏块在参考帧中的最佳匹配点是所述初始搜索中心位置，则跳过步骤C-E，对下一待编码的宏块进行运动估值，即转到步骤A；

步骤C，如果不是，则当前宏块为运动状态，调整所述搜索窗口大小；

步骤D，对当前宏块按照一定比例采样后，得到若干像素块，对所述像素块进行统计分析；

步骤E，根据步骤D的统计分析结果，对方差最大的像素块进行预测质量可控的块匹配运算；

所述步骤E具体为：

步骤E1，把当前宏块中方差最大的一个8*8像素块分割成四个4*4大小的小块，再把其中的一个或多个小块分成若干个子块；对上述分割得到的各个子块标记为1，...，g，...，G，G是当前宏块被分割后的子块的子块总块数；

步骤E2，让当前宏块中标记为g的子块中的像素点与搜索窗中与该像素点对应的像素点进行SAD运算得到d_g，其中g的初值为1，按照公式(11)获得该子块参与运算后的失真值D_g，

D_g＝d_g+D_g-1                                    (11)

其中D₀＝0；

经过若干参考位置后，得到这些参考位置中的一个最小失真值D_MIN，及其各子块的最小失真值D_g，MIN；

步骤E3，根据公式(12)、(13)

(D_g/f(n，k))＞(D_MIN/N²)                        (12)

D_g＞D_g，MIN                                    (13)

判断是否终止当前匹配运算；

步骤E4，如果不满足公式(12)、(13)，则令g←g+1，转入步骤E2继续匹配过程直到g＝G，此时D_MIN＝D_g；

步骤E5，如果满足公式(12)、(13)，此时D_MIN对应的参考位置即为当前宏块的最佳匹配点；

步骤E6，转入下一参考位置进行渐进式块匹配运算，即转入步骤E2；

在步骤E3的公式(12)中，f(n，k)是控制预测质量与搜索速度的调节函数，其公式为

f(n，k)＝(1-k)n+kN²，0≤k≤1                        (14)

其中n为当前宏块中已参与基本运算的像素数目，当n为常量的情况下，f(n，k)是k的单增函数，其最小值为n，最大值为参与渐进式块匹配运算的最多像素数N²。

优选地，所述步骤A包括如下步骤：

步骤A1，当前宏块的空间相邻宏块为MB₁、MB₂、MB₃，其运动矢量为V₁、V₂、V₃，参考帧中与当前宏块位置对应的参考宏块为MB_ref，其运动矢量为V_ref，通过以下公式

x_med＝median(x₁，x₂，x₃)                        (1)

y_med＝median(y₁，y₂，y₃)                        (2)

得到中值运动矢量V_med，式中x、y分别为对应运动矢量的水平分量和垂直分量；该运动矢量V_med确定的块为MB_med，参考帧中与其位置对应的参考宏块为MB_refmed；

步骤A2，当前宏块与运动矢量V_ref、V₁、V₂、V₃、V_med在参考帧中得到的五个宏块分别做绝对差值和运算；得到相应运算结果SAD_ref、SAD₁、SAD₂、SAD₃、SAD_med；

步骤A3，比较上述五个绝对差值和运算结果，绝对差值和值最小的点对应的位置确定为当前宏块的初始搜索中心位置。

优选地，所述步骤B中的判断条件为：当前宏块与其在参考帧中的参考宏块MB_ref的绝对差值和SAD是否小于或等于门限值Th₀，如果小于或等于该门限值，则其最佳匹配点就是初始搜索中心位置，当前宏块相对于参考帧是静止状态，则跳过步骤C-E，对待编码的下一宏块进行运动估值。

优选地，所述门限值Th₀为，Th₀＝min(512，SAD₁，SAD₂，SAD₃，SAD_ref)；其中，SAD₁、SAD₂、SAD₃和SAD_ref分别为当前宏块与运动矢量V₁、V₂、V₃、V_ref在参考帧中得到的宏块的绝对差值和运算结果。

优选地，所述步骤C具体为：

步骤C1，根据与当前宏块相邻的宏块的运动矢量V₁、V₂、V₃按照公式

s_vi＝|x_i|+|y_i|  i＝1，2，3             (4)

S＝max{s_vi}  i＝1，2，3                (5)

进行分析，得到当前宏块所在的局部区域的运动剧烈程度参数S；

步骤C2，根据公式

${\mathrm{area}}_{\mathrm{sw}}=\left\{\begin{array}{cc}(1/4)\mathrm{are}{a}_{\mathrm{dsw}}& \mathrm{if}(S\&le;S_1)\\ (1/2){\mathrm{area}}_{\mathrm{dsw}}& \mathrm{if}((S_1<S\&le;S_2)\\ {\mathrm{area}}_{\mathrm{dsw}}& \mathrm{others}\end{array}\right.---\left(6\right)$

调整当前宏块在参考帧中所需搜索窗口的大小area_sw；其中，S₁、S₂为编码器预先设定的运动剧烈程度参考阈值；area_dsw表示步骤A中搜索窗口的大小；

步骤C3，利用中值运动矢量V_med的水平分量和垂直分量根据公式

W＝W_sw*(x_med/y_med)                     (7)

H＝H_sw*(y_med/x_med)                     (8)

调整当前宏块搜索窗口的水平宽度W和垂直高度H；其中，W_sw、H_sw分别为搜索窗口的水平宽度和垂直高度。

优选地，所述步骤D具体为：

步骤D1，对当前宏块进行4:1采样，可得到四个8*8的像素块；

步骤D2，根据公式

$m_i=\left(\underset{k\&Element;s_i}{\mathrm{\&Sigma;}}{I}_i(x,y,t)\right)/M---\left(9\right)$

${{\mathrm{\&sigma;}}_i}^2=\left(\underset{k\&Element;s_i}{\mathrm{\&Sigma;}}{(I_i(x,y,t)-m_i)}^2\right)/M---\left(10\right)$

对所述四个8*8的像素块进行统计分析；

步骤D3，选出方差σ_i ²最大的像素块；

所述步骤D2的公式9和10中，I_i(x，y，t)为当前帧t中的当前宏块的下采样像素块(x，y)位置处的像素灰度值，s_i为该像素块所包含像素点的集合，M为该像素块所包含的像素点数目，此处M＝64，m_i为该像素块的均值，σ_i ²为该像素块的方差。

优选地，步骤E4具体为：

步骤E41，如果不满足条件，即不能终止当前匹配运算，判断子块g是否小于子块总块数G；

步骤E42，如果g＜G，则g←g+1，转入下一子块进行渐进式块匹配运算，即转入步骤E2；

步骤E43，当g＝G，将当前参考位置获得的各级D_g赋予D_g，MIN，其中g＜G，D_G赋予D_MIN。

本发明可减少运动估计的计算量，加快编码速度，并在预测质量和搜索速度之间增加可控性。

附图说明

图1是预测质量可控的运动估计算法流程图。

图2是当前宏块的相邻宏块。

图3是4:1像素降采样。

图4是方差最大的8*8像素块的分割。

图5是小块1的分割。

图6是预测质量可控的渐进式块匹配运算实现流程。

图7是Football序列采用不同算法的结果比较。

图8是Footbal1序列第87帧在各种算法下的部分运动矢量图。

具体实施方式

下面结合附图和具体实施例对本发明做进一步详细说明：

参照附图1，本发明预测质量可控的快速运动估值方法，包括如下步骤：

步骤A，当前宏块在参考帧中预设一搜索窗口，在所述搜索窗口中预测当前宏块的初始搜索中心位置；

步骤B，判断当前宏块在参考帧中的最佳匹配点是否就是所述初始搜索中心位置；如果是，则当前宏块相对于参考帧是静止状态；

步骤C，如果不是，当前宏块为运动状态时，调整所述搜索窗口大小；

步骤D，对当前宏块按照一定比例采样后，得到若干像素块，对所述像素块进行统计分析；

步骤E，根据步骤D的统计分析结果，对方差最大的像素块进行预测质量可控的块匹配运算。

具体过程如下：

第一步、初始搜索中心位置的预测

如图2所示，当前宏块的空间相邻宏块为MB₁、MB₂、MB₃，其运动矢量为V₁、V₂、V₃，参考帧中与当前宏块位置对应的参考宏块为MB_ref，其运动矢量为V_ref，通过以下公式

x_med＝median(x₁，x₂，x₃)                    (1)

y_med＝median(y₁，y₂，y₃)                    (2)

得到中值运动矢量V_med，式中x、y分别为对应运动矢量的水平分量和垂直分量；该运动矢量V_med确定的块为MB_med，参考帧中与其位置对应的参考宏块为MB_refmed；

当前宏块与运动矢量V_ref、V₁、V₂、V₃、V_med在参考帧中得到的五个宏块分别做绝对差值和运算；得到相应运算结果SAD_ref、SAD₁、SAD₂、SAD₃、SAD_med；

比较上述五个绝对差值和运算结果，绝对差值和值最小的点对应的位置确定为当前宏块的初始搜索中心位置。

第二步、静止宏块的判定

当前宏块与其在参考帧中的参考宏块MB_rer的绝对差值和如果小于等于门限值Th₀：

SAD≤Th₀

Th₀＝min(512，SAD₁，SAD₂，SAD₃，SAD_ref)        (3)

则其最佳匹配点就是初始搜索中心位置，当前宏块相对于参考帧是静止状态；

当前宏块与其在参考帧中的参考宏块MB_ref的绝对差值和如果大于门限值Th₀，当前宏块相对于参考帧是运动状态。

第三步、搜索窗口的调整

通过对与当前宏块相邻的宏块的运动矢量V₁、V₂、V₃按照公式(4)、(5)进行分析，可得到当前宏块所在的局部区域的运动剧烈程度S，接着按照公式(6)调整当前宏块在参考帧所需参考窗口的大小area_sw，然后利用运动矢量V_med的水平分量和垂直分量按照公式(7)、(8)调整当前宏块参考窗口的水平宽度W和垂直高度H。

s_vi＝|x_i|+|y_i|  i＝1，2，3                (4)

S＝max{s_vi}  i＝1，2，3                   (5)

公式(4)中s_vi代表相邻宏块运动的剧烈程度。

${\mathrm{area}}_{\mathrm{sw}}=\left\{\begin{array}{cc}(1/4)\mathrm{are}{a}_{\mathrm{dsw}}& \mathrm{if}(S\&le;S_1)\\ (1/2){\mathrm{area}}_{\mathrm{dsw}}& \mathrm{if}((S_1<S\&le;S_2)\\ {\mathrm{area}}_{\mathrm{dsw}}& \mathrm{others}\end{array}\right.---\left(6\right)$

公式(6)中，area_dsw表示缺省搜索窗口的大小，例如±7，对应窗口15*15，area_sw为根据局部区域运动剧烈程度得到的搜索窗口的大小，通常S₁＝2，S₂＝4，公式(6)中系数1/4、1/2可根据实际情况做调整。

W＝W_sw*(x_med/y_med)                        (7)

H＝H_sw*(y_med/x_med)                        (8)

公式(7)、(8)中，W_sw、H_sw为搜索窗口的水平宽度和垂直高度。

第四步、当前宏块采样模式的选择

对当前宏块按照图3所示的像素采样方式进行4:1下采样，可得到四个8*8的像素块，即对应图中a、b、c、d四个位置像素构成的像素块，然后利用公式(9)、(10)分别对这四个像素块进行统计分析，选择方差σ_i ²最大的像素块参与预测质量可控的块匹配运算。

$m_i=\left(\underset{k\&Element;s_i}{\mathrm{\&Sigma;}}{I}_i(x,y,t)\right)/M---\left(9\right)$

${{\mathrm{\&sigma;}}_i}^2=\left(\underset{k\&Element;s_i}{\mathrm{\&Sigma;}}{(I_i(x,y,t)-m_i)}^2\right)/M---\left(10\right)$

公式(9)、(10)中，I_i(x，y，t)为当前帧t中的当前宏块的下采样像素块(x，y)位置处的像素灰度值，s_i为该像素块所包含像素点的集合，M为该像素块所包含的像素点数目，此处M＝64，m_i为该像素块的均值，σ_i ²为该像素块的方差。

第五步、预测质量可控的渐进式块匹配运算

预测质量可控的渐进式块匹配运算把当前宏块中方差最大的8*8像素块分割成四个4*4大小的小块，构成各小块的像素对应位置如图4中标号所示。同时，把小块1分成若干个子块，如图5所示(也可按照其它方式分割子块)，也可以按照其它方式分割小块，图5中(a)～(f)为对小块1采用的6种不同的分割方式，其中标注相同值的像素点(不需要一定相邻)构成小块1的一个子块，其标注值也表示其参与SAD运算的先后顺序。

预测质量可控的渐进式块匹配运算的实现过程如图6所示，图中G是一个宏块所分的级数.假设经过若干参考位置后，得到这些参考位置中的一个最小失真值D_MIN及其各级失真值D_g，MIN，按照公式(12)、(13)判断是否可终止对当前参考位置的匹配运算而转入下一参考位置，如果不能终止当前匹配运算，则g←g+1，继续上述匹配过程，以此类推，直到找到当前宏块的最佳匹配点。

D_g＝d_g+D_g-1                            (11)

(D_g/f(n，k))＞(D_MIN/N²)                (12)

D_g＞D_g，MIN                            (13)

f(n，k)＝(1-k)n+kN²，0≤k≤1           (14)

f(n，k)是控制预测质量与搜索速度之间矛盾的一个关键因素，称为调节函数，其定义见公式(14)，其中n为当前宏块中已参与基本运算的像素数目，当n为常量的情况下，f(n，k)是k的单增函数，其最小值为n，最大值为参与渐进式块匹配运算的最多像素数N²。

实验中，对八个不同运动复杂度、不同格式的视频序列做了测试，每个序列均编码100帧，其中CIF格式(352*288)的视频序列做运动估计时使用的缺省搜索窗口大小为±7，编码速率为384kbit/s，4SF格式(704*480)的视频序列做运动估计时使用的缺省搜索窗口大小为±15，编码速率为576kbit/s。

表1不同序列使用各种算法所得PSNR(单位：dB)(相对于FS的PSNR)

表2不同序列使用各种算法的搜索速度比较(与FS搜索速度相比的比值)

表1中比较了DS、ASSA、NPDS、PQAS算法相对于FS算法的PSNR(信号噪声功率比)变化情况，所有实验结果均是在公式(14)中k＝0的条件下获得的。可以看出，随着小块1分割方式的变化，重建视频图像的PSNR也随着变化，其中PQAS(m3)获得的重建视频质量最接近于ASSA、FS算法，与NPDS算法相差很小(原因在于PQAS算法中每一搜索位置最多有64个像素点参与块匹配运算，而NPDS算法中最多会有256个像素点参与块匹配运算)，PQAS(m6)次之(略高于DS算法)，然后是PQAS(m5)、PQAS(m2)、PQAS(m4)、PQAS(m1)。分析上述实验结果可以发现，在进行渐进式块匹配过程中，开始的三步中参与块匹配运算像素的数目对最终的重建视频质量影响很大，而且视频序列运动越剧烈，这种影响越明显，也就是说开始的几步中参与运算的像素数目越多，重建视频图像质量越好，反之越差，原因在于开始时参与运算的像素数越多，公式(12)、(13)发生误判的可能性越小，因此找到最佳匹配位置的可能性就越大。从表1可以发现，对于内容相同、格式不同的视频序列Football、Mobile，4SF格式采用PQAS算法所得的PSNR相对于CIF格式的PSNR要好一些，原因在于随着视频图像的放大，其细节性的东西相对就会变少，因此在渐进式块匹配算法中参与运动的像素点数目就会增多，找到最佳匹配位置的可能性增大，所以重建视频质量变好。

表2中反映了DS、ASSA、NPDS、PQAS算法所需的基本运算次数(求和、取绝对值、比较运算)与FS算法所需的基本运算次数相比得到的搜索速度变化情况，所有实验结果均是在公式(14)中k＝0的条件下获得的.可以看出，随着小块1分割方式的变化，运动估计的搜索速度也随着变化，其中PQAS(m1)搜索速度最快，PQAS(m4)次之，然后是PQAS(m2)、PQAS(m5)、PQAS(m6)、PQAS(m3)，且所有小块1分割方式的搜索速度均高于DS、NPDS算法.分析上述实验结果可以发现，在进行渐进式块匹配过程中，开始的三步中参与块匹配运算像素的数目越少，搜索速度越快，而且视频序列运动越平缓，如Mother、News，这种情况越明显，原因在于公式(6)根据局部区域的运动情况对搜索窗口大小做调整导致搜索点数的急剧下降，这种调整对运动变化剧烈的视频序列(Football、Mobile)帮助很小，搜索点数减小很小，即使这样，它们的搜索速度也会高于DS算法.从表2可以发现，对于内容相同、格式不同的视频序列Football、Mobile，CIF格式采用PQAS算法的搜索速度相对于4SF格式的搜索速度要好一些，原因在于随着视频图像的放大，其细节性的东西相对就会变少，因此在渐进式块匹配算法中参与运动的像素点数目就会增多，搜索速度变慢.

表3中比较了DS、ASSA、NPDS算法与取不同k值的PQAS(m6)算法(从搜索速度和重建图像质量两方面折中考虑选择该算法进行比较)相对于FS算法的PSNR变化情况，可以看出，随着公式(14)中k值的变化，重建视频图像的PSNR也随着变化，其中PQAS(1.00)(相当于要搜索当前采样中的全部像素点)获得的重建视频质量最接近于ASSA、FS算法，并在总体上高于NPDS算法(Mother、News视频序列由于纹理相对简单而导致公式(12)、(13)发生误判的可能性增加，所以其重建视频的PSNR低于NPDS算法)。分析上述实验结果可以发现，在进行渐进式块匹配过程中，随着k值的增大，参与块匹配运算的像素数变多，公式(12)、(13)发生误判的可能性越小，因此找到最佳匹配位置的可能性就越大，这种影响对运动剧烈的视频序列尤为明显。需要指出，视频序列Football在k＝1.00时所得的PSNR高于FS获得的PSNR约0.05dB，原因在于该视频序列水平方向运动非常剧烈且纹理相对较多，在公式(7)、(8)的作用下，搜索窗口在水平方向上被拉伸，即会在水平方向上搜索更多的点，这样找到更符合物体实际运动的趋势的可能性就会增大，因此重建视频图像的PSNR获得提高。

表3各序列使用PQAS(m6)算法取不同k值所得PSNR(单位：dB)(相对于FS)

表4各序列使用PQAS(m6)算法取不同k值的搜索速度比较(相对于FS)

表4中比较了DS、ASSA、NPDS算法与取不同k值的PQAS(m6)算法所需的基本运算次数相比于FS算法所需的基本运算次数而得到的搜索速度变化情况，可以看出，随着公式(14)中k值的增加，运动估计的搜索速度逐渐变慢，原因在于进行渐进式块匹配过程中，随着k值的增大，参与块匹配运算的像素数变多。同时，通过对表3、4比较可看出在相同的重建视频质量情况下，PQAS(m6)算法的搜索速度高于其它快速算法。

图7显示了视频序列Football(352*288)采用不同算法所得PSNR、搜索速度的变化情况，其取值均相对于FS算法。从图7(a)可以看出，PQAS算法所得的PSNR随着小块1分割方式的变化而变化，小块1分割方式中参与渐进式块匹配运算前三步中像素数越多，所得PSNR越接近于FS算法所得的PSNR，这说明由于参与渐进式块匹配运算的像素数逐渐增多，公式(12)、(13)发生误判的可能性逐渐减小，所以PSNR获得提高，但这是以搜索速度的下降为代价的(见图7(b))。图7(c)反映了选用PQAS(m6)算法采用不同k值所得PSNR，可以看出，随着k值的增加，所得PSNR越接近甚至高于FS算法所得的PSNR，同样这是以搜索速度的下降为代价的(见图7(d))。比较图7(c)、(d)可以看出，在相同的PSNR情况下(k值不同)，PQAS(m6)算法的搜索速度高于DS、ASSA、NPDS算法。

图8显示了视频序列Football使用不同算法获得的运动矢量图，从图8(b)可以看出，当k＝1.00时PQAS(m6)算法获得运动矢量大部分同FS获得算法相同，但PQAS(m6)算法获得一些运动矢量大于FS算法，这些矢量的存在导致视频序列Football采用PQAS(m6)获得的PSNR高于采用FS算法获得的PSNR，图8(c)中是k＝0.00时采用PQAS(m6)算法获得的运动矢量图，由于参与渐进式块匹配运算像素数的影响，序列Football获得的运动矢量与FS、PQAS(m6，1.00)算法有一些差别，但其运动矢量反映的运动趋势同FS、PQAS(m6，1.00)相一致，图8(d)表示了采用ASSA算法获得运动矢量图，其同FS算法获得的运动矢量很相似，图8(e)是采用NPDS算法获得的运动矢量图，它所获得的运动矢量与FS算法获得存在一些差别，但其运动矢量反映的运动趋势同FS算法基本一致，图8(f)是采用DS算法获得的运动矢量图，由于搜索点数的影响，容易使该算法获得的SAD值陷入局部最优，导致其获得的某些运动矢量会与FS算法获得的运动矢量相差较大.

Claims (7)

1.一种预测质量可控的快速运动估值方法，包括如下步骤：

步骤A，当前宏块在参考帧中预设一搜索窗口，在所述搜索窗口中预测当前宏块的初始搜索中心位置；

步骤B，判断当前宏块在参考帧中的最佳匹配点是否就是所述初始搜索中心位置；如果是，则当前宏块相对于参考帧是静止状态，当前宏块在参考帧中的最佳匹配点是所述初始搜索中心位置，则跳过步骤C-E，对下一待编码的宏块进行运动估值，即转到步骤A；

步骤C，如果不是，则当前宏块为运动状态，调整所述搜索窗口大小；

步骤D，对当前宏块按照一定比例采样后，得到若干像素块，对所述像素块进行统计分析；

步骤E，根据步骤D的统计分析结果，对方差最大的像素块进行预测质量可控的块匹配运算；

所述步骤E具体为：

步骤E1，把当前宏块中方差最大的一个8*8像素块分割成四个4*4大小的小块，再把其中的一个或多个小块分成若干个子块；对上述分割得到的各个子块标记为1，...，g，...，G，G是当前宏块被分割后的子块的子块总块数；

步骤E2，让当前宏块中标记为g的子块中的像素点与搜索窗中与该像素点对应的像素点进行SAD运算得到d_g，其中g的初值为1，按照公式(11)获得该子块参与运算后的失真值D_g，

D_g＝d_g+D_g-1                                (11)

其中D₀＝0；

经过若干参考位置后，得到这些参考位置中的一个最小失真值D_MIN，及其各子块的最小失真值D_g，MIN；

步骤E3，根据公式(12)、(13)

(D_g/f(n，k))＞(D_MIN/N²)                    (12)

D_g＞D_g，MIN                                (13)

判断是否终止当前匹配运算；

步骤E4，如果不满足公式(12)、(13)，则令g←g+1，转入步骤E2继续匹配过程直到g＝G，此时D_MIN＝D_g；

步骤E5，如果满足公式(12)、(13)，此时D_MIN对应的参考位置即为当前宏块的最佳匹配点；

步骤E6，转入下一参考位置进行渐进式块匹配运算，即转入步骤E2；

在步骤E3的公式(12)中，f(n，k)是控制预测质量与搜索速度的调节函数，其公式为

f(n，k)＝(1-k)n+kN²，0≤k≤1                    (14)

其中n为当前宏块中已参与基本运算的像素数目，当n为常量的情况下，f(n，k)是k的单增函数，其最小值为n，最大值为参与渐进式块匹配运算的最多像素数N²。

2.根据权利要求1所述的预测质量可控的快速运动估值方法，其特征在于，所述步骤A包括如下步骤：

步骤A1，当前宏块的空间相邻宏块为MB₁、MB₂、MB₃，其运动矢量为V₁、V₂、V₃，参考帧中与当前宏块位置对应的参考宏块为MB_ref，其运动矢量为V_ref，通过以下公式

x_med＝median(x₁，x₂，x₃)                        (1)

y_med＝median(y₁，y₂，y₃)                        (2)

得到中值运动矢量V_med，式中x、y分别为对应运动矢量的水平分量和垂直分量；该运动矢量V_med确定的块为MB_med，参考帧中与其位置对应的参考宏块为MB_refmed；

步骤A2，当前宏块与运动矢量V_ref、V₁、V₂、V₃、V_med在参考帧中得到的五个宏块分别做绝对差值和运算；得到相应运算结果SAD_ref、SAD₁、SAD₂、SAD₃、SAD_med；

步骤A3，比较上述五个绝对差值和运算结果，绝对差值和值最小的点对应的位置确定为当前宏块的初始搜索中心位置。

3.根据权利要求2所述的预测质量可控的快速运动估值方法，其特征在于，所述步骤B中的判断条件为：当前宏块与其在参考帧中的参考宏块MB_ref的绝对差值和SAD是否小于或等于门限值Th₀，如果小于或等于该门限值，则其最佳匹配点就是初始搜索中心位置，当前宏块相对于参考帧是静止状态，则跳过步骤C-E，对待编码的下一宏块进行运动估值。

4.根据权利要求3所述的预测质量可控的快速运动估值方法，其特征在于，所述门限值Th₀为，Th₀＝min(512，SAD₁，SAD₂，SAD₃，SAD_ref)。

5.根据权利要求2所述的预测质量可控的快速运动估值方法，其特征在于，所述步骤C具体为：

步骤C1，根据与当前宏块相邻的宏块的运动矢量V₁、V₂、V₃按照公式

s_vi＝|x_i|+|y_i|  i＝1，2，3                (4)

S＝max{s_vi}  i＝1，2，3                   (5)

进行分析，得到当前宏块所在的局部区域的运动剧烈程度参数S；

步骤C2，根据公式

${\mathrm{area}}_{\mathrm{sw}}=\left\{\begin{array}{cc}(1/4){\mathrm{area}}_{\mathrm{dsw}}& \mathrm{if}(S\&le;S_1)\\ (1/2){\mathrm{area}}_{\mathrm{dsw}}& \mathrm{if}\left(\right(S_1<S\&le;S_2)\\ {\mathrm{area}}_{\mathrm{dsw}}& \mathrm{others}\end{array}\right.---\left(6\right)$

调整当前宏块在参考帧中所需搜索窗口的大小area_sw；其中，S₁、S₂为编码器预先设定的运动剧烈程度参考阈值；area_dsw表示步骤A中搜索窗口的大小；

步骤C3，利用中值运动矢量V_med的水平分量和垂直分量根据公式

W＝W_sw*(x_med/y_med)                        (7)

H＝H_sw*(y_med/x_med)                        (8)

调整当前宏块搜索窗口的水平宽度W和垂直高度H；其中，W_sw、H_sw分别为搜索窗口的水平宽度和垂直高度。

6.根据权利要求1所述的预测质量可控的快速运动估值方法，其特征在于，所述步骤D具体为：

步骤D1，对当前宏块进行4∶1采样，可得到四个8*8的像素块；

步骤D2，根据公式

$m_i=\left(\underset{k\&Element;s_i}{\mathrm{\&Sigma;}}{I}_i(x,y,t)\right)/M---\left(9\right)$

${{\mathrm{\&sigma;}}_i}^2=\left(\underset{k\&Element;s_i}{\mathrm{\&Sigma;}}{(I_i(x,y,t)-m_i)}^2\right)/M---\left(10\right)$

对所述四个8*8的像素块进行统计分析；

步骤D3，选出方差σ_i ²最大的像素块；

所述步骤D2的公式9和10中，I_i(x，y，t)为当前帧t中的当前宏块的下采样像素块(x，y)位置处的像素灰度值，s_i为该像素块所包含像素点的集合，M为该像素块所包含的像素点数目，此处M＝64，m_i为该像素块的均值，σ_i ²为该像素块的方差。

7.根据权利要求1所述的预测质量可控的快速运动估值方法，其特征在于，步骤E4具体为：

步骤E41，如果不满足条件，即不能终止当前匹配运算，判断子块g是否小于子块总块数G；

步骤E42，如果g＜G，则g←g+1，转入下一子块进行渐进式块匹配运算，即转入步骤E2；

步骤E43，当g＝G，将当前参考位置获得的各级D_g赋予D_g，MIN，其中g＜G，D_G赋予D_MIN。

Images