| 连续排除算法SEA(Successive elimination algorithm)[7]的基本思想是应用三角不等式，用块的和范数差值SND(sumnorm difference)先进行判断，排除 SAD 不可能最小的搜索位置，避免计算运算复杂度很高的块匹配误差，不断更新目前最佳匹配位置，连续不断地排除不可能的位置，加快搜索速度。它在不损失任何性能的基础上，有效加快搜索速度， 16×16 宏块运动估计中 SEA 算法实际计算了大约 6%～10%的块的 SAD 值，约可提高速度10 倍左右。
早停止技术，主要思想可归纳为“找到足够好的匹配，而并非一定要最好的匹配”。一般的做法是预先设定一个闽值。当匹配误差小于这个闽值时，立即停止搜索过程。由于不需要完成整个搜索，因此可以达到加速的目的。
3.2 混合快速算法
下面是综合运用多个提升搜索速度的途径得到兼有各类快速算法优点的混合快速算法。
在十字模型中如果考虑到图象的中心倾向特性形成双十字搜索算法[5]。该算法在搜索的初始阶段使用小十字搜索模型SCSP和大十字搜索模型LCSP对小运动矢量进行搜索；而在后继的搜索步骤中，充分考虑大运动矢量概率分布的方向性，对大运动矢量进行搜索，从而加快了运动矢量的搜索速度。该算法不仅保持与其他快速块匹配运动估计算法相当的搜索质量,而且可提高大约40%的搜索速度。
将连续排除算法SEA和菱形搜索法结合起来形成连续消除菱形运动估计算法SEDS[6]，再结合准确的运动矢量初始位置选择、提前终止判断、有效的菱形搜索模式等方法，从而大幅度降低运动估计运算量，同时保持编码性能，块匹配误差计算量为快速全搜索算法的 0.2%~1%。或者也可将SEA和六边形和小菱形搜索法结合在一起形成连续排除六边形算法[7]将SEA和全搜索法结合在一起形成连续排除全搜索法。SEA和各类算法结合都有提高速度，减少时间的作用。与SEA有类似作用的还有亚像素估计法，子抽样法等。
基于运动矢量的统计分布特性的双起点大小正方形算法DBSS (Double Big Small Square)，算法的其中一个策略是采用预测点和当前分块所在位置两点作为搜索起点，使得在出现相关性预测误差大时，仍能把握运动的方向；另外就是采用大小正方形的搜索模式，模板如图1所示，内部是一个小的正方形，外部是一个大的正方形。
DBSS算法主要步骤:
(1)当MBD（Minimun Block Distortion）出现在大的正方形四个顶点，表明物体运动幅度很大，则仍选用原有的搜索模式;
(2)当MBD出现在小的正方形的四个顶点，表明物体运动幅度很小，则以MBD的正方形顶点为中心，采用小钻石搜索方式进行搜索。
(3)当MBD出现在大小正方形的中心，说明图像没有运动，结束搜索。
从BSS的搜索方式中我们可以看出BSS算法不必一定经历从较大搜索步长到小搜索步长的变换，而是根据物体运动情况来确定搜索步长。从直观上可看出，大小正方形分别用来粗细定位，这本质上体现了一种并行处理的思想。
  
图1 DBSS算法的搜索模板
Fig 1 The search pattern of DBSS algorithm
实验结果表明，采用DBSS算法的峰值信噪比十分接近FS算法，而优于DS算法； DBSS算法的比特率略高于FS算法，但明显低于DS算法； DS算法的编码时间大概是FS全搜索的1 /25，而DBSS算法大概是采用FS全搜索的1/30，也就是说DBSS算法大大提高了编码速度，比DS算法更有效节约了运算时间。也就是说，DBSS算法取得了运算复杂度和搜索精度之间的折中，在保证视频性能相对高的前提下，大大降低了运算复杂度，提高了编码速度。
4 结论
混合快速算法结合了各类典型算法的优点，在速度与准确度两方面做出折中，使能够满足视频传输的需要，近年来已被多个视频压缩标准采纳。
参考文献
[1]A.M.Tekalp,'DigitalVideo Processing',Englewood Clifs:Printice Hall,1995.
[2]王建.H.264 中运动估计的研究与实现.[硕士毕业论文],江苏:南京邮电学院,2005.
[3]刘根林.H.264 实时视频编码技术研究及其 DSP 实现.[硕士毕业论文],上海:上海交通大学,2004.
[4] Li W, Salari E.Successive Elimination Algorithm for Motion Estimation[J]. IEEE Trans. on ImageProcessing, 1995, 4(1):105-107.
[5]刘海华,雷 奕,谢长生.双十字搜索算法的快速块匹配运动估计.计算机研究与发展,43(9):1666~1673,2006.
[6]杨铭.H.264 视频编码快速算法与算术编码检错研究.[硕士毕业论文],北京:清华大学,2004.
[7]黄 帅,宋国新.基于连续消除的六边形自适应搜索算法.计 算 机 工 程,2006 年 11 月,Vol.32 No.21.
2/2 首页 上一页 1 2 |
