（信息与通信工程专业论文）视频编码块匹配运动估计算法研究.pdf

浙江大学硕士学位论文 摘要 随着近年来多媒体技术的不断发展，视频压缩技术成为了人们研究的热点。 运动估计作为视频压缩框架中的关键技术，对视频压缩编码的质量和速度有着 举足轻重的影响。 本文首先简单介绍了视频压缩的相关概念及运动估计的研究现状，然后就 在运动估计中对运算复杂度起决定作用的匹配计算和搜索算法这两个方面进行 了研究。针对常用匹配准则s a d 、m s e 等在判决匹配误差时存在的不足，本 文提出了一种改进的块匹配准则( s ss a d 准则) ，在s a d 准则的基础上，依 据两个块的平滑相似程度来进行匹配判断，重建帧信噪比较s a d 和m s e 准则 有所提高。本文提出了一种自适应的静止块检测准则，针对视频序列中大量存 在的静止匹配块，利用前面的编码信息对每个块动态地调整判决闽值来进行静 止块检测，与使用固定阂值的检测准则相比，在错判率没有明显增加的前提下， 显著降低了漏判率。本文在总结和分析现有的快速模板算法的基础上，从人们 对运动矢量分布的现有认识和对统计数据的分析中归纳出了能更准确反映运动 矢量分布特性的水平偏置中心分布模型，并通过对视频序列中相邻运动矢量相 关性情况的统计，归纳性地将运动矢量的相关性模型分为中心偏置相关和运动 相关两种情况。基于运动矢量的水平偏置分布模型和相关性模型，提出了两个 新的运动估计快速算法h b s 和m v c b ，提高了运动估计的运算速度。 关键词：视频压缩，运动估计，块匹配，匹配准则，静止块检测，搜索算法 浙江大学硕士学位论文 a b s t r a c t w i t ht h ef a s t d e v e l o p m e n to fm u h i m e d i at e c h n i q u e s v i d e oc o m p r e s s i o n t e c h n o l o g yh a sb e c o m eah o ts p o t a so n eo ft h ek e yt e c h n o l o g i e si nv i d e oc o d i n g ， m o t i o ne s t i m a t i o nd e e p l ya f f e c t st h e s p e e d a n d q u a l i t y o f v i d e oc o d i n g c o m p r e s s i o n t h i sp a p e rf i r s ti n t r o d u c e st h ev i d e oc o m p r e s s i o nr e l a t e dc o n c e p t sa n dt h e a c t u a l i t y i ns t u d yo fm o t i o ne s t i m a t i o n t h e nr e s e a r c hi s f o c u s e do nm a t c h i n g c a l c u l a t i o na n ds e a r c ha l g o r i t h m s w h i c hc o u l dd e c i d et h ec o m p l e x i t yi nm o t i o n e s t i m a t i o n f o rt h ed e f i c i e n c yo fc u r r e n tm a t c h i n gc r i t e r i o n s ，s u c ha ss a d ，m s e ， t h i sp a p e rp r o p o s e san e wc r i t e r i o n , c a l l e ds s - s a d ，w h i c hu t i l i z e st h er e s e m b l a n c e o ft w ob l o c k ss u r f a c e si nm a t c h i n g j u d g i n g c o m p a r e dt os a da n dm s e ，t h en e w c r i t e r i o nh a sh i g h e rr e c o n s t r u c t e di m a g ep s n r a n a d a p t i v es t a t i c - b l o c kd e t e c t i o n c r i t e r i o ni sp r o p o s e di nt h i sp a p e r , w h i c hu t i l i z e di n f o r m a t i o ni nn e i g h b o u r i n gf r a m e a n db l o c k st os e tat h r e s h o l dv a l u ea c t i v e l y , w h i c hi su s e df o rs t a t i cb l o c kd e t e c t i o n c o m p a r e dt oaf i x e dt h r e s b o l dv a l u e ，t h en e wc r i t e r i o nc o u l dn o t a b l e l yd e c r e a s et h e m i s s - j u d g er a t eo fs t a t i cb l o c k s b a s e do nc u r r e n ts t u d yo fm o t i o nv e c t o r ss t a t i s t i c r e s u l t s ，t h i sp a p e rb r i n g so u tm o t i o nv e c t o rh o r i z o n t a l - b i a s e dc e n t r a ld i s t r i b u t i o n m o d e la n dm o t i o nv e c t o rc o r r e l a t i o nm o d e l b a s e do nt h en e wm o d e l s t w of a s t s e a r c ha l g o r i t h m sa r ep r o p o s e d ，w h i c hc o u l d i m p r o v et h es p e e do fm o t i o n e s t i m a t i o n k e y w o r d s ：v i d e oc o m p r e s s i o n ，m o t i o ne s t i m a t i o n ，b l o c km a t c h i n g ，m a t c h i n g c r i t e r i o n ，s t a t i cb l o c kd e t e c t i o n ，s e a r c ha l g o r i t h m 浙江大学硕士学位论文 第1 章绪论 随着信息技术的发展和社会的不断进步，人类对信息的需求越来越丰富， 人们希望无论何时何地都能够方便、快捷、灵活地通过语音、数据、图像与视 频等多种方式进行通信。多媒体技术和电视技术的进展将使用中需求得到满足。 随着i n t e m e t 技术和计算机技术的迅猛发展，现代视频通信、语音通信以及实 对数据通信已经成为目前通信和网络发展的大趋势其中，视频通信是以人类 视觉为基础的一种通信方式，目前，实时视频通信技术已出现在i p p h o n e 、v i d e o c o n f e r e n c e 、i n t e m e t t v 、手机视频通信等网络应用中。 一般情况下，视频信息中除传真外，其他的视频信号都是通过宽带来传送 的，例如电视信号的频带带宽多达6 m h z ，这相当于9 6 0 路的电话信道带宽。 即使是图像变化缓慢的可视电话，其频带宽度也达1 m h z 。同时视频图像信号 数字化后，数据量是巨大的。如帧频为3 0 h z 的c i f 格式的图像序列，数字化 后其数据量高达3 4 8 m b p s 。一路h d t v 视频信号，其数据高达约m b p s 。尽管 通信网络和存储媒体也正在向高带宽、大容量方向发展，如a d s l 和光纤通信 等技术，但是随着社会信息交互的日益广泛和新型的多媒体业务不断出现，人 们期望的是更高品质的集视频、图像、声音、文字为一体的多媒体应用服务， 这就意味着个人通信量将会成指数增长，信道的容量永远不会满足需求。因此 对视频信息进行压缩处理，使它能在较低速率的信道上实时传输是亟待解决的 问题。视频信息处理的一个主要任务就在于引入图像压缩编码技术，对庞大的 视频数据进行压缩再进行后续的存储与传输 虽然数字化的视频图像信息是非常大的，但视频图像数据间是高度相关的。 一幅图像的内部或图像序列中楣邻图像之阃有大量的冗余信息，这其中包括了 时间冗余、空间冗余、信息嫡冗余、结构冗余等形式。消除冗余是视频图像编 码压缩图像数据的出发点，视频图像编码的一个主要目的，就是在保证一定重 构质量的前提下，以尽量少的比特数来表征图像和视频信息。正是视频图像压 缩编码技术的发展进步，推动了视频图像信息的广泛应用。 1 1 视频编码的基本框架 在现有的视频信号压缩编码国际标准中，变换与量化、熵编码以及运动估 计和运动补偿等几项技术得到了最为广泛的应用，这几项技术构成了视频编码 系统的基本框架。其中，变换与量化和熵编码两项技术都是从静态图像压缩技 一卜一 浙江大学硕士学位论文 术中借鉴而来用于帧内编码压缩的，而运动估计技术则是实现帧间编码压缩的 主要手段。视频编码的基本框架如图1 1 所示 图1 l 视频编码基本框架 1 1 1 变换与量化 在进行熵编码之前，一般要将空域图像信号映射变换到另一个正交矢量空 间( 变换域) ，以削减空域图像信号相关性强，降低冗余度。目前广泛使用的正 交变换包括：d c t 变换、f o u r i e r 变换、w a l s h 变换、h a a r 变换、h a d m a r d 变 换、s l a n t 变换、k - l ( k a r h u n e n l o e v e ) 变换等k - l 变换是最小均方误差 意义下的最佳正交变换，但由于其运算复杂度过高，并不适用于实际应用。因 而通常采用性能接近k - l 变换、运算复杂度适中且有快速实现算法的d c t 变换。 变换系数一般需要进行量化，而用有限比特的量化过程是有损的因为量 化过程是一个多对一的映射过程，因此会造成信息丢失，即引入噪声。此外， 为进一步压缩图像数据，还会对变换域中不同的频率分量采用不同的量化参量。 这样做是基于人眼对高频细节不敏感的视觉特性，多去除些高频系数而保留低 频系数，可以在提高压缩比的同时使人眼难以觉察出恢复图像的失真。 一2 一 浙旺大学硕士学位论文 i i 2 熵编码 同有损的量化相比，熵编码是无失真的，在图像压缩中一般用于交换量化 之后。它以信息论的知识为基础，利用统计特性，将各个系数编成长短不同的 比特串出现概率高的系数所对应的比特串短，概率低的系数所对应的比特串 长这样可以使整体码流所占比特数较短，从而降低码率。图像压缩中，常用 的熵编码有 i u 妇陆越编码与算术编码。h 硼陆强编码方法于1 9 5 2 年闯世， 迄今经久不衰，仍广泛应用于各种数据压缩技术中相比之下，算术编码方法 要晚出现得多，也要复杂得多但它不需要像h u f f m a n 编码一样传送码表，同 时还有很强的自适应能力。因此，算术编码的效率更高，近年来的应用也愈发 广泛。 1 1 3 运动估计与运动补偿 基于块匹配的运动估计与运动补偿补偿是目前视频压缩领域中应用最广的 去除视频序列时域冗余的方法。由于视频可以看作是一系列静态图像帧构成的 缓变序列，因此其时域冗余要远远大于空域冗余。因此，在前一帧的基础上对 第二帧图像进行编码时，可以首先利用第一帧的块对第二帧进行预测，找出要 编码的帧中每一个块在参考帧中的位移( 称之为运动矢量m v ，m o t i o n v e c t o r ) ， 并对运动矢量和两个块相减的残差进行编码，从而在很大程度上去除了时域冗 余度。其中，在编码端搜索运动矢量的过程称为运动估计( ，m o t i o n e s t i m a t i o n ) ，而在解码端将预测块与预测残差相叠加的过程称为为运动补偿 ( m c ，m o t i o nc o m p e n s a t i o n ) 运动估计是视频编码的关键技术，其最基本的原理是利用相邻帧间的时间 相关性，通过预测来减少时间冗余度。在实际编码中，为了节省码率，并不传 输每一帧的全部数据，而是利用运动估计求出每一帧与其预测参考帧之间的差 值。运动估计越准确，差值的分布越趋近与零，差值块的能量越小，经过变换、 量化和熵编码后所产生的码流的比特位率也越少因此，运动估计搜索的准确 程度直接影响到了编码的压缩性能。 另一方面，运动估计是视频压缩编码系统中最耗时的一个模块，可占到编 码运算总量的6 0 0 一8 0 ，是编码过程中运算最密集的地方。要想提高视频压缩 系统的编码速度，达到实时压缩，必须缩短时间占用比例最大的运动估计所耗 费的时间。 一3 一 浙扛大学颈士学位论文 运动估计作为视频编码的关键，需要解决的问题是如何提高它的运算速度 和准确度如何解决这个关键问题具有很高的理论和实际意义，是一个图像处 理领域和图像通信领域极其重要的研究课题。它的研究和应用必将促进计算机 通信、图像通信和多媒体技术的发展 。 1 2 视频压缩标准及其中的运动估计 近年来，一系列国际视频压缩编码标准的制定极大地促进了视频压缩编码 技术和多媒体通信技术的发展。目前从事视频压缩标准制定的国际组织主要有国 际电信联盟r r u t 的视频编码专家组v c e o ( w d e oc o d i n ge x p e r tg r o u p ) 和国际 标准化组织i s o i e c 的运动图像专家组m p e g ( m o t i o np i c t u r ee x p e r tg r o u p ) 。两 个标准化组织基于不同的应用需求，采用相似的压缩编码技术，分别制定了 h 2 6 x 和m p e g 嘱系列视频压缩标准。其中r r u t 针对可视会议等应用分别 制定了h 2 6 1 、h 2 6 2 、h 2 6 3 、h 2 6 3 + 、h 2 6 3 + + 、h 2 6 l 和h 2 6 4 a v c ；i s o i e c 相继制定了m p e g - 1 、m p e g - 2 、m p e g - 4 、m p e g - 7 和m p e g - 2 1 。以上国际压 缩标准尽管应用领域不同，但是均采用了预测编码结合变换量化的混合编码模 式。其中两大视频标准化组织于1 9 9 2 年联合提出的m p e g - 2 h 2 6 2 是现有最 成功的国际视频压缩标准，后来又再次联手提出了h 2 6 4 ，即m p e g - 4 第1 0 部分。图1 - 2 给出了各个标准之间的时间关系。 叵三国固匡正瑁 臣霎s m a d m 山圈巨曰曰 lfi “l 4 l 一i 匿，i 臣习ii l g s (1 9 口1 61 螭1 9 1 9 9 21 9 9 4l 辨6i ，孵2 0 0 02 0 0 22 e 0 4 图i - 2 视频编码标准的时间关系 h 2 6 1 【l l 是u t 的前身c c i t t 针对可视电话、会议电视以及窄带i s d n 等要求实时编解码和低延时应用提出的一个编码标准，输出码率p x 6 4 k b i t s ， 其中p 为0 到3 l 的整数。h 2 6 1 标准的帧内压缩方式与j p e g 静态图像压缩标 准类似，同样是基于8 x 8 象素块的d c t 变换；而帧问模式压缩则是简单的前 向块匹配运动补偿，只有一个参考帧；运动估计的块大小为1 6 x1 6 ，运动估计 的精度只有整象素精度个选项。h 2 6 1 对编码中如何进行运动估计并未作详 一4 一 浙江大学硕士学位论文 细规定。这样做使得不同厂家的h 2 6 1 编码器在编码质量上可能会有很大差别， 但也给各厂商留下了相当的发展空间，在很大程度上促进了视频编码技术的研 究。因此这种做法在此后的标准制定过程中一直被沿用。 m p e g 1 2 1 标准的目标码率为1 2 m 比特，秒，对于c i f ( 3 5 2 x 2 8 8 ) 格式图像 可以达到实时播放，是为只读c d r o m 光盘的视频存储和播放所制定的与 h 2 6 1 相比，m p e g o l 的运动估计增加了两个新特性：双向的运动估计以及亚 象素( 1 2 象素) 精确度运动估计。双向运动估计是指在运动估计中，前向帧 和后向帧都可以作为参考帧。m p e g 1 中共有三种帧类型：i 帧( 帧内压缩) 、 p 帧( 前向运动估计) 和b 帧( 双向运动估计) 。b 帧的引入虽然带来了比较 大的编码延时，但进一步降低了码率。亚象素精确度的运动搜索相对h 2 6 1 中 的整象素精确度可以使预测残差更小，也使码率得到了降低。 m p e c - 2 【3 】的视频编码部分就是h 。2 6 2 ，该标准主要针对数字视频广搐 d v b ( d i g i t a lv i d e ob r o a d c a s t ) 、高清晰度电视h d t v ( n g hd i g i t a lt e l 州i s i o n ) 和数字光盘d v d ( d i g i t a lv i d e od i s c a r d ) 等4 - - 9 m 比特秒运动图像的编码 m p e g - 2 标准定义了不同的“档次”( p r o f i l e ) 和“等级”( 1 e v e l ) ，可满足不同 图像分辨率及相应的存储成本和处理速度的需要。与h 2 6 1 视频标准相比， m p e g 2 i 2 6 2 开始使用半象素精度的运动矢量搜索，引入了“帧”和“场” 的编码方法，支持可分级性技术，包括空间可分级性、时间可分级性和信嗓比 可分级性等。 h 2 6 3 t 4 j 是为低码率视频压缩提供的新标准，目的是支持码率小于6 4 k b i t s 的应用在h 2 6 1 的基础上，h 2 6 3 进行了重要改进，采用了半象素精度的运 动矢量搜索，增加了非限制运动矢量，增加了8 8 块的运动估计，从而达到了 进一步降低码率和提高编码质量的目的。 m p e g - 4 5 】标准既能够支持低码率的视频应用，也能够支持广播级的视频应 用。与其他标准相比，m p e g 4 标准中引入了视昕对象( a u d i o - v i s u a lo b j e c t ， a v o ) 的概念，这种编码模式能有效提高视频通信的交互能力和编码效率。 m p e g 4 还采用了诸如形状编码和自适应d c t 技术以支持任意形状视频对 象的编码，以及基于内容的可分级性操作。其自然视频编码的基本框架和h 2 6 3 标准是接近的，但是由于“基于对象的编码”尚有技术障碍，在技术专利保护 问题上迟迟难以找到有效的收费形式，因此该标准目前仍然没有得到普遍应用。 h 2 6 4 a v c 6 l 是m p e g - 4 标准的第十部分，全称为i t u - tr e c o m m e n d a t i o n h 2 6 4a n di s o i e cm p e g 4 但a r t1 0 ) a d v a n c e dv i d e oc o d m g h 2 6 4 1 a v c 在视 一5 一 浙江大学硬士学位论文 频编码中引入了很多新技术，使得其编码效率有了巨大提高：在相同信噪比条 件下，其平均码率仅为h 2 6 3 + 的5 0 n 与现有标准相比h 2 6 4 a v c 在运动估 计技术上的改进主要有：基于多种块类型的运动补偿，支持1 6 x1 6 ，1 6 8 ，8 x 1 6 ，8 x 8 , 8 x 4 ，4 8 , 4 x 4 七种分块模式；1 4 象素精度的运动估计；多参考帧运 动估计。更为精确的运动估计以及其他模块技术上的改进，使得h 2 6 4 标准的 压缩率与其他标准相比有了较大的提高 1 。3 运动估计的研究现状 运动估计算法通常分为两大类：一类是象素递归算法p r a ( p i x e lr e c u r s i v e a l g o r i t h m ) ；另一类是块匹配算法b m a 0 3 l o c km a t c h i n ga l g o r i t h m ) 。p r a 是基 于递归思想，如果连续帧中象素数据的变化是因为物体的移位引起的，算法就 会沿着梯度方向对某个象素周围的若干象素做迭代运算，使连续的运算最后收 敛于一个固定的运动估计矢量，从而预测该象素的位移；而b m a 则是基于当 前帧中一定大小的块，在当前帧的前后帧的一定区域内搜索该象素块的最佳匹 配块，作为它的预测块。尽管p r a 对比较复杂的运动形式来说，其预测精度 要高于b m a ，但是由于其计算量比b m a 大的多，同时b m a 本身也拥有较 好的性能，因此目前的视频压缩编码国际标准普遍都采用b m a 。 本文的研究都是针对块匹配的运动估计算法。在后文中，如无特别说明， 所提到的运动估计也都是指基于块匹配的运动估计 在基于块匹配的运动估计中，最直接的全搜索算法( f u l ls e a r c h ，f s ) 能够 得到全局最优的运动矢量，但该算法的运算量也相当巨大，成为了编码器实时 应用的瓶颈。为了提高运动估计的运算速度，人们不断提出针对块匹配运动估 计的改进快速算法，其目标是在保证编码质量的同时，尽可能的降低运算复杂 度。 在本节中对目前已有的基于块匹配的快速算法的优化途径进行了比较合理 的分类，将其分为了提高运动估计速度的技术，包括快速搜索模板、亚采样匹 配，搜索点预先排除、起点预测、提前中止，以及提高运动估计准确度的技术， 包括分层搜索，多起点搜索、提高搜索象素精度、可变块大小搜索等。 1 3 1 快速搜索模板 这类算法的主要想法是通过在搜索窗口内按照固定的模式( 搜索模板) 和 步骤对较少的几个点进行匹配运算来降低运算复杂度。这类快速模板算法都是 - - 6 - - 浙江大学硕士学位论文 基于一个共同的假设，即在搜索窗内有且仅有一个全局匹配误差最小点，而且 匹配误差随着当前点与全局最优点之间距离的增大而增大模板搜索快速算法 是提出最早，发展最为成熟，也是应用最为广泛的一类快速算法它的优点是 算法简单，计算量小，加速比较大；缺点是容易陷入局部极值，尤其在大运动 情况下，搜索的准确度难以保证 该类算法的经典代表有三步法研( t h r e es t e ps e a r c h , t s s ) 、2 维对数法嘲 ( 2 - d i m e n s i o nl o g a r i t h m , 2 d - l o g ) 、交叉搜索法唧( c r o s ss e a r c ha l g o r i t h m , c s a ) 、新三步法【i o i ( n e w l l l r s t e p s e a r c h , n t s s ) 、四步法1 1 ( f o u rs t e p s e a r c h , 4 s s ) 、菱形法【1 2 ( d i a m o n ds e a r c h , d s ) 、六边形搜索法【1 3 i ( h e x a g o n - b a s e ds e a r c h , h e x b s ) 、十字菱形搜索【1 4 】( c r o s sd i a m o n ds e a r c h , c d s ) 等。 1 3 2 亚采样匹配 误差计算的抽样化是指在计算匹配误差的时候，并不对块或者宏块内的全 部象素进行差值计算，而是通过一定规则对匹配象素进行选取。最简单的4 ：1 亚抽样匹配的计算公式如下： 丝卫( 1 1 ) s 4 d ( i , j ) = 阢砂一允( 坍+ 咒+ 力i 烈刀) 、 其中，当m ，n 都是偶数时，p ( m ，矽；l ；其他情况，p 似，矽= 0 。 亚采样匹配方法大大降低了运算量，在4 ：1 抽样的情况下，计算量减少为 使其减小为原来的1 4 。亚采样匹配能够显著降低运动估计的计算量，但容易 造成图像质量的下降。 1 3 3 搜索点预先捧除 在运动搜索的过程中，通过数学不等式，及时地直接或间接排除一些候选 点，可以达到提高运动所搜速度的目的。s e a ( s u c c e s s i v ee l i m i n a t i o n a l g o r i t h m ) 算法是该方面的典型算法该算法描述如下； 假设f d m , n ) 表示第k 帧坐标为佩，一，) 点的灰度值，则有； a ( m ，功一石一。( m + 月+ 力s k ( 加，帕一f k a ( m + i , n + 力l 1 2 ) 五。( 胁+ 栉+ d a ( m ，一) s i 五q ( m + 以+ d 一五( 硎 1 3 ) 令r = 阮( m ，雄) l 表示当前块所有象素灰度绝对值的和。 蝎= l 兵4 ( 掰+ f ，拧+ 刊表示前一帧候选匹配块所有象素绝对值的和。 一7 - - 浙江大学硕士学位论文 因此可以得到： r - m 。，s s 4 d ( i , j 3 ( 1 4 ) 瓦一足脚( f ，力 ( 1 5 ) 假设之前已经得到了一个运动矢量为( x ，y ) 的匹配候选块的删墨) ，) ， 实际上在搜索过程中，只有当当前块与参考块的绝对差值和洲力小于已得 到的s 似五力才需要进行匹配计算因此具有更高匹配度的块应当满足： s a d ( i , d s s a d ( x , 力 ( 1 6 ) 由公式( 1 4 ) ( 1 5 ) ( 1 6 ) 可得： r - 翩d 阮y ) s m ， r + s a d ( x , 力 ( 1 7 ) 只有满足( 1 7 ) 式的候选块才有必要进行下一步的计算。参考帧和当前帧 中块的灰度值和值需要计算一次，在搜索过程中不需要重复计算。通过搜索判 别条件排除了不需要进行匹配计算的块，有效的降低了运算量。 1 3 4 起点预测 由于相邻块之间和相邻帧之间的运动具有很强的相关性，可以利用这种相 关性先对初始搜索点进行预测，以预测点作为搜索起点【1 辄垌大量的试验证明 预测起点更加靠近最佳匹配点，降低了搜索陷入局部最优的可能性，提高了运 动估计搜索的准确度。 常用的起点预测方法有基s a 值的起点预测和利用相邻运动矢量的起点预 测。在基于s a d 值的起点预测中，首先求出当前块与它的相邻块的运动矢量所 指向的块之间的s a d 值，然后选取s a d 最小的相邻块的运动矢量作为预测矢 量。由于保存前一帧运动矢量信息在编码端要占用大量内存，使得系统复杂化， 故大多数算法利用考虑同一帧内块的空间相关的矢量来进行预测，其中一个比 较典型的方法是“平均预测”h 2 6 3 使用上、上右、左边三个相邻块的运动矢 量取其平均值来预测当前块的运动矢量。而在m p e g - 4 中使用上、上右，左边 三个相邻块的运动矢量中间大小的值来预测当前块的运动矢量。 经过预测的搜索起点往往更加接近全局最优值，因而提高了运动估计的搜 索速度，并可有效的避免陷入局部最优。 一8 一 浙江大学硕士学位论文 1 3 5 提前中止 提前中止的基本思想是“找到足够好的匹配就停止，而并非要找到最好的 匹配”，其基本方法是在运动搜索中预先设定一个阈值，当匹配误差小于这个阈 值时，立即停止搜索过程由于不需要搜索所有的候选点，因此提高了运动估 计的速度。显然，阈值的选取十分重要，它会在很大程度上影响搜索的性能 阈值过大，大部分搜索都会提前停止，虽然速度很快，但同时搜索准确度就会 较低。而阈值过小，只有少数的搜索能够提前停止，速度很难有明显的提高 虽然提前中止技术的引入，会不可避免的造成准确度的损失，但是较好的阈值 自适应计算可以以在准确度与速度问取得令人满意的折衷。 1 3 6 分层搜索 分层搜索算法 1 7 - 1 9 的基本方法是在当前帧的抽样图像层上进行运动搜索。 它可以概括为分辨率由粗到细的搜索，即从最低层的原始帧派生出多层图象， 从低层到高层，分辨率依次降低。先在高层搜索进行运动搜索，然后逐渐降低 层数，利用己有的信息不断提高精度，最后在原始帧上进行搜索，这就是分层 快速算法的主要思想。分层搜索方法首先在最高层低分辨率的图像中找到一个 最优的匹配点，然后由粗到细地以上一层的最优匹配点作为起点进行搜索，可 以有效的避免运动估计进入局部最优，提高了运动估计的精确度 1 3 7 多起点搜索 搜索时选择多个匹配度较高的点作为下一步搜索的中心位置，个数可依据 搜索速度和精度进行调整。该方法能有效避免进入局部最优，提高了搜索精度。 1 3 8 提高搜索象索精度 在h 2 6 3 中使用了半象素搜索精度，m p e g - 4 中支持1 4 精度，h 2 6 4 也支 持1 4 精度搜索，其t 2 象素使用滤波，1 4 象素用六点插值来提高插值运算精 度。通过在匹配位置周围区域内的象素进行内插，然后进一步搜索，可以找到 更精确匹配的位置。运动矢量精度的提高使经运动估计后帧闻预测误差减小， 从而降低了码率。 1 3 9 可变块大小搜索 帧间预测使可以采用大小不同的块来进行运动估计h 2 6 3 和m p e g - 4 都 一9 一 浙旺大学硕士学位论文 支持对宏块中的4 个8 x 8 块分别进行运动估计，得到4 个运动矢量。在宏块内 部各块运动不一致的情况下，利用4 个运动矢量所得的预测误差比对整个大块 进行单一运动矢量所得的预测误差小得多。在h 2 6 4 中，支持1 6 x 1 6 、1 6 x 8 、 8 x1 6 、s 8 、8 x 4 、4 x 8 、4 x 4 等七种分块模式采用不同大小的块进行帧 间预测，可使运动估计的模型更接近物体的实际运动，因此运动估计的准确度 得到提高。 1 4 本文的主要工作及内容安排 本文将着重对在运动估计对运算复杂度起决定作用的匹配计算和搜索算法 这两个方面进行研究。全文安排如下； 第一章：简要介绍视频压缩的基本框架，结合运动估计介绍视频编码标准 的发展，对现今运动估计的研究方向做一个简单的概括。 第二章：从研究匹配计算着手，提出一种改进的块匹配准则( s ss a d 准 则) ，在s a d 准则的基础上，依据两个块的平滑相似程度来进行匹配判断，使 压缩图像质量得到提高。提出一种自适应静止块检测准则，利用前面的编码信 息对每个块动态地调整判决阈值来进行静止块检测，以提高静止块判决的性能。 第三章：从研究搜索算法着手，通过总结人们对运动矢量特性的认识过程， 并结合实验统计数据分析，提出运动矢量的水平偏置中心分布模型和相关性模 型，在两个运动矢量模型的基础上，针对运动矢量的分布特性和相关特性分别 提出h b s 搜索算法和m v c b 搜索算法，以提高运动估计的运算速度。 第四章：本文工作的总结以及展望。 一l o 浙江大学硕士学位论文 第2 章运动估计匹配研究 在视频图像中存在着大量的时间冗余。视频序列实际上是一系列静止图像 的集合，当它们以每秒钟一定的帧数连续显示的时候，由于人眼的视觉暂留效 应，看起来就是连续的图像。因此，在一般情况下，相邻帧间的内容实际相差 不多( 除了场景切换等情况) ，有很大一部分甚至是完全一样的( 如图2 1 与图 2 - 2 所示) ，所以帧与帧之间存在着很大的时间相关性。采用帧间预测编码可以 在很大程度上去除时间域上的冗余度。将上一帧相同空闻位置处的象素值作为 待编码的当前帧的预测值，可以有效地提高压缩比。这种预测对图像中静止的 场景效果非常好，但是对于运动的场景，这种简单的帧间预测效果则不甚理想。 如果能知道当前帧某象素( 或象素块) 是从上一帧的哪个位置移动过来的，也 就是找出它们的运动相关性，并以该位置上的象素值作为预测值，那么帧问预 测的准确性将大为提高。实现这种预测的方法就是运动估计技术。运动估计可 以确定出当前帧的某象素( 或象素块) 是从上一帧的哪一个位置移动过来的， 然后对两象素( 或象索块) 相减得到它们的差值( 或差值块) 。运动估计的准确 性越高，差值块中的各象素灰度值也越小，经过d c t 变换、量化和熵编码后生 成的压缩码流的比特位数就越少，从而达到了压缩图像数据的目的。在常见的 运动估计算法中，基于块匹配算法的运动估计因其算法简单有效，易于实现而 被广泛应用 2 0 j 。本文的研究都是针对块匹配的运动估计算法。 图2 - 1m o b i l e 序列的第0 帧 图2 - 2m o b i l e 序列的第1 帧 浙江大学硕士学位论文 2 1 运动估计的匹配原理 基于块匹配法的运动估计的基本思想就是将当前帧分成互不重叠的大小为 m x n 块，对当前帧中的每一个块都在参考帧中的一定区域，即搜索窗口内， 按照一定的匹配准则搜索与之具有最小匹配误差的块( m i n i m a ld i s t o r t i o n b l o c k ，m d b ) ，该块即为当前块的匹配块，匹配块与当前块之间的坐标位移就 是运动矢量，匹配块与当前块的对应象素点逐个做差就的到差值块。基于这样 的方法这样，当前帧中的每一个块都可以用一个差值块和一个运动矢量来表示， 对当前帧的编码就转化为对每一块的差值块和运动矢量的编码。图2 - 3 为块匹 配运动估计的示意图。 参考帧 图2 - 3 块匹配运动估计示意图 运动估计的复杂度主要取决于匹配计算量和所采用的搜索算法这两个方 面。在下一节中将介绍在运动估计常用的一些匹配准则。 2 2 常见的匹配准则 视频压缩的一些国际标准，如h 2 6 1 ，h 2 6 3 ，m p e g - 1 ，m p e g - 2 ，m p e g - 4 中，并没有对视频编码器中的匹配函数给出统一的规定，估计精度高、运算复 杂度低的匹配准则函数仍然是视频编码中的研究热点目前常用的匹配准则有 绝对平均误差函数( m a d ) 1 2 1 1 、绝对差值和( s a d ) 、归一化互相关函数( n c f f ) 1 2 2 1 、均方误差函数( m s e ) 1 2 3 1 、最大误差最小函数( m v i e ) 1 2 4 1 、最大匹配象 素数( m p c ) 等。它们的表达式如下： ( 1 ) m a d 的表达式为： m a d ( f ，加亩蚤善i 五( m ) 一刖肼“玎+ 州( 2 1 ) 式中( j ，- ，) 为位移量，五和a 1 分别为当前帧和上一帧的灰度值，mx 一1 2 浙江大学硕士学位论文 n 为宏块的大小，若在某一点处m a d 嘞，知) 达到最小，则该点为要找的最 优匹配点。 ( 2 ) m s e 的表达式为： 脚( f ，舻上m n 兰，茎， 伽矿磊一。卅叫， 尬e “= 二m = l 行乏l l 磊脚，疗一磊一1 彻“，胛+ ，j - q 2 ( 3 ) n c f f 的表达式为。 n c f f ( i ，d = m l ( m ，栉) 五一，沏+ f ，聆+ 歹) 等当耋k = = = 了= = = = = = = = = = = = 一( 2 3 ) ，jmn一 e e l , 2 ( 肼，) j e e y , - ? ( m + 刀+ 歹) m = lr a = ll m = ln = l n c f fa d ) 值最大的点为最优匹配点 ( 4 ) s a d 的表达式为： m ， s a d ( i ，歹) = i l ( m ，九) 一以一。( 小+ ，刀+ ，) l ( 2 4 ) 捌i tn = l ( 5 ) m c l e 的表达式为； 朋7 沥伉，) = 瑚x l z ( m ，珂) 一z 一。( 肌+ 雄+ 州 ( 2 5 ) 该准则取m d e 最小者为最优运动矢量 ( 6 ) m p c 的表达式为： mn 脚c ( ，) = t ( i , j ，m ，玎) ( 2 6 ) 在表2 - 1 中比较了各个准则对n x n 大小块的运算复杂度。从表中可以看 出，n c c f 匹配函数的计算过于复杂。m m e 和m p c 匹配函数则过于简单，没 有充分利用匹配块所包含的特征信息，使运动估计的精度大大降低。m s e 匹 配函数判决的精度最高。但由于其含有乘方法运算，实现代价较大。仿真结果 表明，m a e 和m s e 的效果相似脚1 选用m a d 简化得到的s a d 则可以避免乘 法运算。m s e ，m a d ，s a d ，n c c f ，m m e ，m p c 这些准则从不同角度力求 准确而又快捷的反映出块与块之间的差异。s a d 由于其相对的简单性而被广泛 一1 3 一 川力枷珈胁以“淼 叫仉 以 以 式 浙江大学硕士学位论文 2 3 改进的块匹配准则 2 3 1s a d 匹配准则的不足 视频序列在有很多情况下帧与帧之间会表现出亮度变化、阴影遮盖等现象。 在这些情况下，仅使用s a d 来计算块的匹配程度显然是不够的，容易表现出两块 很相似的图像却具有较大的s a d 值。图2 - 4 是对当前待编码的块与两个不同的 候选块根据s a d 准则做匹配计算的实例。 其中，a 、b 两块之间的绝对差值和s a d 臼，口) = 1 6 0 ：a 、c 两块之间的 绝对差值和s a d 翻c ) = 1 5 2 。 5 05 05 0 5 0 5 05 05 0 5 0 5 0 5 0 5 05 0 5 05 05 05 0 5 08 85 05 0 5 08 85 05 0 5 08 85 05 0 5 08 85 05 0 ( a ) 当前块a( b ) 匹配块b ( c ) 匹配块c 图2 - 4s a d 匹配实例 根据s a d 匹配准则，块b 被选为块a 的最佳匹配，但是从人眼的主观质 量评价看，最佳匹配块不是c 而是b 。实际上，象素块a 和b 都是图像的平坦 区域，只是整体亮度发生了变化，人眼主观上不容易感觉出它们之问的差别， 但匹配块c 却存在一条明显的竖直亮线，因而块c 与a 的在人眼的主观感觉 一1 4 浙大学硕士学位论文 上相差很大 从上述简单例子可以看，出s a d ( m s e ) 准则只是简单地将象素块之间的 差异进行累加和平均，并以此平均效果作为匹配程度的判断准财，没有到考虑 两匹配象素块中象素差值的之间的相似程度，因而造成了主、客观评价上的差 异 2 3 2 改进的准则 视频序列中物体的剧烈运动以及图像的丰富细节是造成帧间的大的预测差 值的主要原因。较大的帧问预测误差易被人眼视觉感知，造成的图像损伤对人 眼来说也最为敏感。任何大误差形成的图像损伤都是局部性的，将局部性少量 的大误差在整个匹配块内进行空间域统计平均的方法，显然降低了匹配准则的 精确性和可靠性，匹配块尺寸愈大，这种不精确和不可靠性愈严重。因此，最 小据对差值和s a d 或最小均方误差m s e 准则从人眼主观视觉角度来说并非是 最佳的匹配准则。 另外，在帧间编码中，通过运动估计得到当前块的最佳运动矢量，并将当前 图像块与最佳运动矢量对应的预测块相减得到差值块，并在量化和编码之前对差 值块进行d c t 变换。d c l 变换的a c 系数越小，量化后得到的0 系数就越多，行程 编码和熵编码所生成的比特数就越少，压缩效率就越高。换言之，通过减少编码 生成的a c 系数，在相同的码率下，可以得到更好的图像质量。因此，如果匹配 准则使得残差经d c t 的得到的d c t 系数矩阵里的非零a c 值越小或越少，这样的 匹配准则就可以得到更好的图像质量。 在图4 - l 中的a 块和b 块的平滑程度完全相同，两块相减后差值块系数完全相 等，经过d c r 变换后只有一个d c 分量，a c 系数全部为零。将这两个块作为匹配 块编码生成的码流位数较少，且人眼主观视觉较好。由此可以得到启发，匹配准 则在计算两块之间的匹配程度时，除了依据于两块对应象素点亮度之问的差值， 还有一个很重要的判决因素就是两个块平滑程度的一致性。在此，本文提出一种 新的匹配准贝| s ss a d ( s u m o f s m o o t h n e s ss a d ，如公式( 2 7 ) 所示： 嚣一蚴= 鼢渊a b s n = 1( 毗( 冲触咖力) 一器 ) ( 2 7 ) 嚣一l d = & t d + il 幽( 力一正o + 而_ ，+ 力) 一言等il ( 2 7 ) 肿一 小 式中，l ( j ，) 为当前块坐标为“，) 的象素大小， ( f + 善，j4 - y ) 为匹 配块中坐标为矗，的象素大小。 浙扛大学硕士学位论文 s s _ s a d 不仅累加了两个块对应象素之间的差值绝对值，同时还计算了每对 对应象素点的差值与平均差值的差别大小，在匹配计算时加入了对两个块平滑相 似程度差别的判断 2 3 3 实验结果及分析 为了验证s s - s a d 准则的性能，在恒定码率下对a k i y o 、向唧1 勰和缸) t b a l l 这 几个具有代表性的序列进行了测试，比较了s s - s a d 、s a d 和的m s e 准则的重建 帧信噪比。 4 7 a 4 5 叱 z a “ o1 02 03 0 4 05 0 f m n m e n u m b e r 。 图2 - 5a i d y o 序列信噪比 一1 6 浙江大