视频压缩中运动估计块匹配算法分析与研究

在介绍运动估计原理的基础上,对常见运动估计算法进行了分析,并提出了自适应探测搜索新算法,对新算法的搜索模式和搜索方法进行了介绍,描述了新算法的步骤,新算法减少了搜索点数。

信息产业 l l i郭孝存 胡文江’

科； 骊

视频压缩中运动估计块匹配算法分析与研究(、 1内蒙古科技大学信息工程学院，内蒙古包头 0 4 1 2包头师范学院信息科学与技术学院， 10 0、内蒙古包头 04 3 ) 10 0摘要：在介绍运动估计原理的基础上，对常见运动估计算法进行了分析，并提出了自适应探测搜索新算法，对新算法的搜索模式和搜索方法进行了绍，述了新算法的步骤。介描新算法减少了索点数。搜关键词：额压缩；视l运动估计；匹配；块算法

众所周知，视频图像相邻帧之间存在很大的时间相关性，即时间冗余，去除这些冗余是视频压缩编码研究的主要内容。运动估计( tn Mo o i

E￣ ao,】 s- fnME是减少时间冗余的关键技术m ni,运动估计方法多种多样，其中基于块匹配的运动估计算法简单、便于实现等优点得到了广泛

应用。 1运动估计的基本原理 11动估计的基本思想 .运运动估计的基本思想是将帧分成许多互不重叠的宏块或其它大小的块，假设当前帧中的象素块是前一帧或后一帧图像中某个象素块移动而来，未发生移动，或宏块中的每个象素均做相同的运动并认为宏块内所有像素的位移量都相同。然后根据匹配准则。对当前帧中的每一块到前一帧或后一帧在某一给定搜索范围内找出与当前块最相似的块，即最佳匹配块。由最佳匹配块与当前块的相对位置计算出运动位移， 该位移即为当前块的运动矢量。 1 .匹配准则 2块块匹配准则是判断块相似程度的依据，因此匹配准则的好坏直接影响了运动估计的精参考文献度，也是提高运动估计算法的速度的一种途径。 算法采用比较实用的绝对误差和 D准刚。 A ) 与的运动矢量之差的绝对值都小于给定的 I le og L uWe u . lc— a e at— l￣ n i. i nB o k B sd F s t S Mo in t mai n l o i h n d, o e— 2常见运动估计搜索算法与分析阈值 L,则认为与 c块相邻的各块之间运动的 to Esi to A g rt ms i Vi e, C mprs i m h￣ Au u s 4 1 98 8 1 .最简单的块匹配运动估计是全搜索法相关性较高，表明该区域的变化比较平缓。否 so T e, g e t 2

. 9:— 0 (u er, S,它穷尽参考帧搜索窗内所有则。 F l Sa h F ) l c认为与 c块相邻的各块之问运动的相关性【】 2叶学兵.视频压缩中运动估计的研究【】 D.硕表明该区域变化比较剧烈日 。士论文：化工大学 2 0 .1 1北京 051: . 3可能的点进行比较。找到块匹配运动估计最小较低， r1德宝.于 H. 4的帧内与帧间预测方法 3王基 2 6的匹配块。F是最直接的搜索方法， S也是精度 3 D A法搜索模板的选择 .AS算 3最高的搜索方法。但运算量大，占到整个编 D.硕合 0. 94 . 5:由于 A S D A算法搜索过程中要判断搜索方研究『1士论文：肥工业大学20 7 3—4 4李戌祯.频压缩中运动估计算法的研究【】视 D. 码运算量的 7‰ 9 O∞。 向并按搜索方向进行探测，以采用的搜索模 f】所 SS 2 0 .4 57 F s巨大的时问开销不利于视频实时编码式应该具有较强的方向性。 D P方向性较强符太原理工大学硕士论文，0 8: . 5宗 H. 6朔压的应用，因此，很多学者研究并提出了各种类型合这一点被本算法采用，同时采用了六边形模『1怡. 2 4视 li缩关键技术的研究与应用的快速算法：三步搜索法、交叉搜索法、四步法、式， 并对其搜索方向进行了极化：由六边形搜索[I士论文：大学， 0 . 1. D.硕中北 2 8:3 0 5作者简介：郭孝存( 7 -,山东成武人， 1 7) 9男， 菱形搜索法、六边形搜索法等。这些算法中菱形得出的 S D值最小点非中心点时， A如果最小点内蒙古科技大学信息工程学院在读硕士， 搜索算法性能比较优越，被国际视频压缩标准的 Y坐标与中心点同，则直接用中心点到该点讲师，视 H24 .标准和 M E -标准所采用。六边形搜的方向为新的搜索方向；否则取与中心点到该研究方向：频图像压缩研究。 6 PG4索算法是菱形搜索法的一种改进算法，它将菱点的方向相近似的 Y轴方向为新的搜索方向。 形搜索法(S的大菱形搜索模式(D P改成六 I) ) L S) 34 A A算法的步骤 . DS 第一步，根据时空上的相关性确定出当前边形模式，小菱形搜索模式( S )j S P然保留。 D￣改进后的优点为：六

边形模式更接近于以 2为块的预测运动矢量，出初始搜索点并作为搜 得半径的圆，使得搜索效率更高 .. L S b比 D P减少索中心点。 第二步，由相关性分析判断出搜索当前搜 2个搜索点。 以上算法中基本都是先用大搜索模式在索块与相邻块之间的运动相关性，如果相邻块则进入第三步；否则进人第定范围内搜索，再用小模式进行“聚焦”位。之间的相关性较低，定 但是这些算法在背景静止的视频序列中，其四步搜索。尤 是对那些运动矢量近乎为零的块的运动估计搜 第三步，选择六边形搜索模式搜索匹配计个 A A索，在很大的计算冗余，存而且对所有的参考图算相应的 7点的 S D值，如果最小 S D值像都采用固定的步长。无法兼顾对运动剧烈的不在中心，则将该点标记为准最优匹配点，进入否则转入第四步。 图像和变化缓慢的图像：对于运动剧烈的图像第五步，第四步，选择 S S模式搜索匹配计算相 DP会出现局部最优现象。对于变化缓慢的图像出应的5个点的 S D值，如果最小 S D值在中 A A现计算冗余现象。一

3自适应探测搜索新算法在分析了以上算法的基础上，同时参考了 DS E算法的搜索思想，提出了一种改进算法： 自适应探测搜索新算法 ( e dp v e e N w A a t eD t t i ee Sa loi m, S。 emh Agrh AD A) t 3 D A算法初始搜索点的选择 .AS 1利用相邻块之间的运动矢量具有高度的时空相关性，可以根据与当前块相邻块的运动矢量来预测当前块的初始运动矢量，预测的运动矢量可对当前块的搜索起点提高良好的预测。 AD A算法采用“ S加权预测法”进行预测， 设 Mv、 v、 V L IM分别是与当前块 c相邻的左 M 侧、上侧和右上侧的块的运动矢量，则对 M L、 v Mv、 v别乘以 0 0再求和值即搜Ⅱ。分 M… 0、. 4 4 2索起点的预测值。 32 A S . D A算法运动相关性的判断 根据相邻块运动矢量在空问上的相关性。 来预测本块的运动矢量，依此可判断运动剧烈程度。 设 C为当前待编码的块， U、 D分为其 L、 R、左侧、上侧、右侧和下侧的相邻块，c、 U、 fk、 f、 D分别为前一帧中相对应的块， k U、 f

f设、l、 c、 D的运动矢量分别为 V一 f ,如果各运动矢量 V

心，则该中心为为最优匹配点，结束搜索。如果最小 S D值不在中心则将该点标记为准最优 A匹配点，进入第五步。 第五步，标记原搜索模式的中心点为起点， 标记准最优匹配点为终点。计算起点到终点的方向上的紧挨终点下—个点的 S D值， A并将此新点的 S D值与终点 (最优匹配点 ) S A准的 A D值进行比较，若新点的 S值小于终点的 S D A D A值，则将终点标记为起点，此新点标记为准最优匹配点 (即新的终点 )复第五步。则进入第，重否四步。 4结论提出的改进算法CD A在六边形搜索算法 A s)的基础上。对六边形搜索模式优化了搜索方向。 对于运动比较剧烈的块直接进人大范围搜索， 不至于出现局部最优现象；同时对运动剧烈程度不大或趋于静止的块，能较好的避免经历大过程和 S S D P移动和搜索模式时多余的搜索点，有效降低了搜索点数，相对于六边形搜索算法减少搜索点数高达约 5%( 0静止块情况下 ),提高了搜索效率。A S D A算法良好的自适应性满足了运动缓慢和运动剧烈等情况下的搜索。