快速运动估计算法的研究和比较

1、快速运动估计算法MasikkkZxWt小组分工masikkk(H.263协议)三步法(TSS)新三步法(NTSS)四步法(FSS)zx(H.264协议)非对称十字型多层次六边形格点搜索算法(UMHexagonS)自适应范围的快速运动估计算法wt(MPEG系列协议)菱形搜索算法(DS)运动矢量场自适应搜索算法(MVFAST)预测矢量自适应搜素算法(PMVFAST)简介运动估计(Motion Estimation)是视频编码中广泛使用的一种技术，由于视频原始图像间存在着大量的信息冗余，所以需要采用运动估计和运动补偿(Motion Compensation)技术来消除视频信号的冗余以提高编码效率。运

2、动估计：压缩编码过程中计算当前帧和参考帧间的运动矢量。运动补偿：解码过程中根据运动矢量和当前帧恢复出下一帧。基本思想运动估计的基本思想是尽可能准确地获得序列图像帧间的运动位移，即运动矢量。因为运动估计越准确，预测补偿的图像质量越高，补偿的残差就越小，补偿编码所需位数越少，需要传输的比特率就越小。运动估计算法的目标：效率准确性算法分类 全局搜索算法(穷尽搜索) 空域运动估计 基于块的运动估计 基于像素点的运动估计 快速搜索算法 基于区域的运动估计 基于网格的运动估计 频域运动估计算法分类a 全局运动估计c 基于块的运动估计b 基于象素点的运动估计d 基于区域的运动估计基于块的匹配策略 基于块的匹

3、配策略是最常用的运动估计方法，其思想是把图像帧划分为若干互不重叠的块，并认为宏块内所有像素的位移量都相同，以块为单位寻找目标帧中每块在参考帧（上一帧或者其它帧）中最优匹配的块的相对位置，例如常用的有将一帧图像分为16*16个块。每个块都会得到一个对应的运动矢量，并对运动矢量以及块的选择方式进行编码和传输。算法评价准则（1）平均绝对误差MAD在有些时候也用绝对差和SAD的形式：由于MAD或SAD没有乘除操作，实现简单方便，所以使用较多。算法评价准则（2）均方误差（3）归一化互相关函数H.261、H.263中的运动估计H.261的设计目的是为了编码能够在带宽为64kbps的倍数的综合业务数字网上传

4、输的质量可接受的视频信号。H.261中使用的是基于块匹配的运动估计，但并没有规定具体的运动估计算法（后续协议也基本如此），只定义了解码器，允许开发者在编码器的设计上拥有相当的自由，只要产生的码流能够被所有按照H.261规范制造的解码器解码就可以。H.261运动估计的规定：只支持整像素的搜索。每个块只有一个运动向量。只支持P帧，并不支持双向预测帧（B帧）。H.263对H.261的升级：运动估计支持半像素搜索。支持双向预测（B帧）。全搜索(FS)对搜索区域的所有 位置进行穷尽搜索。精度最高计算复杂，难以实时 处理必须研究相应的运动 估计快速算法三步法（TSS）搜索范围为-7,7搜索模板半径依次减半

5、缺点：对小运动检测效果不好新三步法(NTSS)考虑运动矢量的中心偏置特性增加了中心8个近邻点的搜索有效处理细小运动2/25/2022新三步法(NTSS)搜索示意图四步法（FSS） 以起始点为中心的5*5方形模版 反复使用55方形模板进行搜索。 在最后一步或模板中心处误差最小时再用33模板搜索一次确定最佳匹配位置。对比分析PSNR：峰值信噪比，评价处理后图像和原图像之间的差异，公式中含有MSE的倒数。搜索算法搜索算法耗时耗时(秒秒)准确度准确度(PSNR)FS(全搜索)3.96385838.0220TSS(三步法)0.90928035.4990NTSs(新三步法)0.90003537.2834F

6、SS(四步法)0.94807037.4156对比分析00.511.522.533.544.5耗时FSTSSNTSSFSS对比分析0510152025303540准确度FSTSSNTSSFSS对比分析结果从结果可看出：(1)全搜索效果最好，耗时最多。(2)三种快速估计算法基本都比FS快34倍，多数情况下，三种经典快速估计算法效果差不多。(3)快速估计算法的效果没有FS好，但对肉眼来说，误差可忽略不计。参考文献1一种适用于H_263建议的块匹配运动估计算法2 H_263中运动估计算法的TMS320C80实现3H.263运动估计简介http:/ 浙江大学 第13期srtp研究报告5几种经典快速块匹配

7、运动估计算法的比较研究 肖敏连H.264协议中的运动估计H.264，同时也是MPEG-4第十部分，是由ITU-T视频编码专家组（VCEG）和ISO/IEC动态图像专家组（MPEG）联合组成的联合视频组（JVT，Joint Video Team）提出的高度压缩数字视频编解码器标准。不同大小和形状的宏块分割高精度的亚像素运动补偿多帧预测一、自适应范围的快速运动估计算法针对全局搜索算法的高计算量，我们设想，如果能够根据序列本身的运动特性，自适应地确定一个搜索范围，使绝大部分最佳匹配点都落于该范围内，则可在保证性能的同时，降低运算量，提高效率。运动向量可以认为是当前块从当前帧到参考帧的偏移量，则可以用

8、运动向量的二阶矩来评价当前帧相对参考帧的运动程度。同时，研究表明视频图像序列是一个相对缓变的过程，从整体上看，其各帧运动向量的二阶矩变化也较为缓慢。2/25/2022Table tennis序列的二阶矩变化2/25/2022Grandmother序列的变化2/25/2022对比分析这两个序列运动特性不同，一个运动很大，一个运动很小，但其相邻帧运动向量二阶矩的变化幅度都相对较小。基于此项观察，提出建立在视频图像序列统计特性之上的自适应范围搜索，即根据前一帧运动向量的二阶矩来为后一帧确定一个较为合适的搜索范围，然后在该范围内进行搜索。2/25/2022自适应搜索范围定义NMv是前一帧运动向量的个数

9、，D为运动向量的二阶矩，而AR则为用于当前帧的自适应搜索范围。2/25/2022自适应范围搜索（ARS）计算得到AR，按照下列方式进行自适应范围搜索。其中(O，O)点为静止点(运动向量为0的点)，搜索范围为AR，即不搜索超出AR所限矩形范围的点。采用三步法的方式进行再搜索，直至搜索间距为1，停止搜索2/25/2022基于块的梯度下降搜索算法在检查块中，计算所有九个候选点的最小值。如果值最小点就是块中心点，停止。运动向量指向中心点。否则，将上面九个点计算得到的最小值点作为中心点，执行第一步。2/25/2022基于块的梯度下降搜索算法示意图中心为（1）点2/25/2022示意图最优点为（-2，-4

10、）2/25/2022预测搜索（PS）选取当前块的左上方、上方、左边3个块，以及前一帧相同位置以及其周围8个块的相关运动向量作为预测(起始搜索点候选点)首先找到这些候选点中的最佳匹配点，然后按照基于块的梯度下降搜索算法进行再搜索，直至该算法停止2/25/2022初始搜索（IS）初始搜索用于第1个P帧或场景突变，可以使用全搜索算法2/25/2022算法步骤(1)计算静止点的匹配误差；(2)进行PS候选点的筛取，如果候选点的最小匹配误差小于静止点，则采用基于块的梯度下降搜索算法的方式再搜索，然后转第5步；(3)如果尚无法得到相应的自适应范围AR(如第1个P帧或场景突变)，则进行IS，然后转第5步；(

11、4)进行自适应范围搜索(ARS)；(5)保存最佳运动向量，停止。2/25/2022仿真结果选择具有广泛代表性的7个标准测试序列：salesman(352288， 150 帧) carphone、Claire、foremangrandmother(176144，300帧)flower gardentabletennis(352x 240，150帧)tabletennis为大运动序列carphone、foreman、salesman为中等运动序列Claire、grandmother为小运动或几乎静止序列flower garden则包含了较多的细节与镜头平移2/25/2022仿真结果测试序列测试序列

12、FS3SSN3SS4SSEARSCarphone422541.0019.5018.2717.73Claire422541.0017.5617.2410.55Flower garden422541.0019.1617.9618.09Foreman422541.0019.3618.2115.56grandmother422541.0017.4617.1611.65salesman422541.0017.8917.4810.67Table tennis422541.0019.2918.1618.68平均搜索点数422541.0018.6017.7814.70仿真结果测试序列测试序列3SSN3SS4S

13、SEARSCarphone-0.28-0.13-0.20-0.01Claire-0.04-0.03-0.06-0.03Flower garden-0.33-0.03-0.130.01Foreman-0.150.00-0.040.04grandmother-0.040.00-0.020.00Salesman-0.09-0.03-0.05-0.02Table tennis-0.37-0.11-0.15-0.11平均PSNR-0.19-0.05-0.090.00二、非对称十字型多层次六边形格点搜索算法H264于2003年3月采纳了“非对称十字型多层次六边形格点搜索算法”(UMHexagonS)，该算

14、法在很大程度上提高了预测的有效性和健壮性，具有明显优于其他快速算法的性能。搜索模版UMHexagonS算法混合使用以下几个搜索模版算法流程Step1：不对称十字形搜索。获得当前的最佳预测起点。随后根据不同起始点的误差结果使用域值进行判断，分为不满意区域、满意区域和很满意区域，分别转入Step2，Step3，Step4。算法流程Step2：在不满意区域使用如下方式进行搜索Step2-1：以当前点为中心，用非对称十字型搜索模板进行搜索，获得当前最佳点，判断此处是否属于满意或很满意区，跳到相应的Step3或step4，或继续搜索；算法流程Step2-2：以当前点为中心，在(一2，2)的方形区域中逐点

15、搜索获得当前最佳点，判断此处是否属于满意或很满意区，跳到相应的Step3或Step4，或继续搜索；Step2-3：用不断扩大一倍直径的大六边形模板进行搜索，直至搜索到能符合相应阀值而进入Step3和Step4的搜索点为止；或者搜索模板完全超出搜索窗范围，也结束Step2的搜索。算法流程Step3：在满意区域中，以当前点为中心，使用六边形搜索模型进行搜索，直至最佳点在六边形中心为止。Step4：在很满意区域中，以当前点为中心，用十字型模板进行搜索，直至最佳点在十字型模板的中心点为止。2/25/2022搜索过程示意图Step1Step2-2Step2-3Step3Step4算法分析UMHexago

16、nS算法采用了内容自适应的搜索方式，且模板能对不同内容的块进行不同的搜索， 因此具有较高的编码性能。foreman part_qcifyuv视频序列进行编码，比较各快速运动估计搜索算法的运动估计时间FS总耗时3070ms SNRY/U/V分别为36.756/41.083/42.563dBUMHhexagonS总耗时2115ms SNRY/U/V分别为36.805/41.121/42.595dB参考文献1 Liu LurngKuo，Feig EphraimA blockbased gradient descent search algorithm for block motion estimat

17、ion in video codingJ2范亚琼.基于SSE4指令集的H.264编码标准的运动估计优化3李 翔 吴国威.一种适用于H264的基于自适应搜索范围的快速运动估计算法.中国图象图形学报MPEG标准中的运动估计块匹配运动估计算法是目前应用最广泛的一种运动估计算法。已被许多视频编码标准所采纳，如：MPEG-1/2/4、H.261、 H.263及H.264等。MPEG-4采用I-VOP、P-VOP、B-VOP三种帧格式来表征不同的运动补偿类型。它采用了H.263中的半像素搜索技术和重叠运动补偿技术，同时又引入重复填充技术和修改的块（多边形）匹配技术以支持任意形状的VOP区域。此外，为提高运

18、动估计算法精度，MPEG-4采用了MVFAST（Motion Vector Field Adaptive Search Technique）和改进的PMVFAST（Predictive MVFAST）方法用于运动估计。2/25/2022菱形法(DS) DS算法即钻石搜索算法，被算法即钻石搜索算法，被MPEG-4国际标准采用并收入验国际标准采用并收入验证模型证模型VM(Verification Model)中，是中，是MPEG-4建议采用的快速建议采用的快速运动估计算法。运动估计算法。 搜索方式与四步法类似，只是搜搜索方式与四步法类似，只是搜索模板换为两个菱形模板。索模板换为两个菱形模板。MVF

19、AST算法MVFAST 算法是在钻石搜索法的基础上进行改进的。初始化可能性较大的预运动矢量: ( 0,0)和左边块、 上边块、 右上边块的三个运动矢量。设置阈值作为提前终止搜索的条件, 最佳匹配函数采用了绝对差之和 SAD。 这些都大大加快了搜索的速度, 同时也获得了比较理想的图像质量, 已被收录到MPEG-4中。2/25/2022MVFAST算法设左边宏块运动矢量为 V1( x 1, y 1) 上边宏块运动矢量为 V2( x 2,y 2) 右上边宏块运动矢量为 V3( x 3, y3) 根据 L 的值决定当前宏块的运动活动性2/25/2022上边左边右上L = MAX( |x 1 |+ |

20、y 1 | , | x 2 | + | y 2 | , | x 3 |+ | y3 | ) MVFAST算法若L L 1, 搜索中心为( 0, 0) 点, 采用小钻石继续搜索;若L 1 L L 2,搜索中心为( 0, 0) 点,先采用大钻石搜索, 后再采用小钻石搜索;若 L 2 L ,计算 V1, V2, V3 指向的位置的SAD值, 和SAD( 0, 0) 比较, 取其使SAD最小的位置为搜索中心, 采用小钻石继续搜索。2/25/2022PMVFAST算法如右图，O是当前块，A、B、C分别是左、上、右上邻块，E是前帧对应位置块。T1=min(SADA、SADB、SADC) T2=T1+256

21、；将T1限定在512, 1024之间，T2限定在512, 1792之间。2/25/2022OABCEPMVFAST算法1、检测MVP。 如果MinSAD256，结束搜索。 如果MV=MVE且MinSADSADE，结束搜索。2、检测MVA、MVB、MVC、MVE、0,0 如果MinSADT1，结束搜索。 如果MV=MVE且MinSADSADE，结束搜索。3、如果MVP=0,0或T21536或MVA=MVB=MVC，跳到步骤5，否则跳到步骤4。4、菱形大模板反复搜索。5、菱形小模板反复搜索，得到最终运动矢量。 2/25/2022PMVFAST和MVFAST性能比较MVFAST固定模式、 小范围搜索的方法易造成搜索冗余或陷入局部最优，而 PMVFAST算法,对所有块都进行初始搜索点的检测，能避免局部最优。MVFAST对于小运动序列 ,例如子块的最优运动矢量位于 (0, 0)附近较小的区域内 , 会增加预测带来的几个搜索点的运算量 ,使得搜索的效率下降，而PMVFAST效率却大大提高。MVFAST和 PMVFAST算法对于不同运动块各有优势 。MVFAST可通过固定阈值进行分级 ,门限可选择 ,不需要保存搜素点 ,运算复杂度低; PMVFAST不可分级 ,采用一系列强制门限 ,使运动估计速度明显提高 ,但是需要保存搜索点 ,增加了运算复杂度。2/25/2022性能比