（通信与信息系统专业论文）基于单应性关系的运动估计算法.pdf

一liliii孑3召ii45。ii! 摘要 。v u u 多媒体中的视频编码技术主要通过消除帧内的空间冗余和帧间的时间冗余来 实现对数据的压缩。在消除时间冗余方面帧间块匹配技术是比较完善的，其原理 是用参考帧中的一个图像块来最大地近似当前的编码块。如何尽快地找到这个最 佳块即是快速搜索算法需完成的工作 新的视频编码标准h 2 6 4 采用了许多与以往协议不同的编码技术，如多参考 帧的选择、可变块的大小、整数d c t 变换以及更高精度的运动估计技术等。这些 新技术的采用使得h 2 6 4 编码具有低码率、高画质、高压缩比等特点。整个编码 过程中运动估计所占时间最大，因此希望可以在保持相近编码质量的前提下对其 编码器进行优化。全角度摄像机进行受限运动，这种摄像机拍摄的视频具备帧间 几何约束关系。本文针对全角度摄像机拍摄的视频序列，利用帧间几何约束关系， 结合提前终止策略，提出一种全新的基于单应性矩阵的搜索算法( 船s ) 。该算法 可有效减少视频编码时间，获得较高的编码效率。同时可以使得各视频的客观参 数( b i t r a t e ，p s n r ) 等较全搜索算法基本保持不变。 关键词：视频编码h 2 6 4 快速搜索算法单应性关系运动估计h b s 算法 a b s t r a c ti i i a b s 仃a c t d a t ac o m p r e s s i o ni sb a s e do nt h ep r i n c i p l et h a tt h e r ea r ev a r i o u sr e d u n d a n c i e si n t h eo r i g i n a ld a t a t h ei n t e r - f l a m eb l o c km a t c h i n gt e c h n o l o g yi s q u i t ep e r f e c t i n e l i m i n a t i n gt h et i m er e d u n d a n c y ，i tu s e sar e f e r e n c ef r a m e 舔t h ea p p r o x i m a t i o no ft h e c u r r e n tc o d i l 唱b l o c k h o wt og e tt h eo p t i m a lb l o c ki st h ef u n c t i o no ft h er a p i ds e a r c h a l g o r i t h m t h en o v e l t yv i d e oc o d i l l gs t a n d a r dh 2 6 4h a st h ec h a r a c t e r so fl o wb i tr a t e ，h i 曲 d e f i n i t i o n , a n dh i 曲c o m p r e s s i o nr a t ef o rd i f f e r e n tc o d i n gt e c h n o l o g yi sa d o p t e da s b e f o r e ，l i k et h em u l t i - f r a m es e l e c t i o n , b l o c ks i z ev a r i a b l e ，i n t e g e rd c tt r a n s f o m a t i o n a n dm o r ea c c u r a t em o t i o ne s t i m a t i o nt e c h n o l o g y , e t c t h em o t i o ne s t i m a t i o nt a k e s m u c ht i m ew h i l ec o d i i l ga s e q u e n c e ，s ow ef o c u so l lo p t i m i z i n gt h ec o d e cp a r t i nt h i s p a p e r , w ep r o p o s ea n o v e lh o m o g r a p h y b a s e ds e a r c h ( h b s ) a l g o r i t h mf o rb l o c km o t i o n e s t i m a t i o ni nc o d i n gt h es e q u e n c e sc a p t u r e db yp tc a m e r a s ，w h i c hw e l lu t i l i z e st h e h o m o g r a p h yb e t w e e nt w of r a m e s i na d d i t i o n , a d a p t i v et h r e s h o l d sa r ea d o p t e di no u r m e t h o dt oc l a s s i f yd i f f e r e n tk i n d so fb l o c k s c o m p a r e d 、析t ho t h e rt r a d i t i o n a lf a s t a l g o r i t h m s ，t h ep r o p o s e df i b sa l g o d t h r ni sp r o v e dm o r ee f f i c i e n tf o rt h es e q u e n c e s c a p t u r e db yp tc a m e r a s k e y w o r d ：v i d e oc o d i n g h 2 6 4f a s ts e a r c h i n ga l g o r i t h mm o t i o ne s t i m a t i o n h o m o g r a p h y - b a s e ds e a r c ha l g o r i t h m h b s 第一章绪论 第一章绪论 1 1 引言 随着信息技术的迅猛发展，人们对多媒体通信业务的需求与日俱增。尽管人 们在努力增加信道带宽和提高信道传输效率，但很明显并不能够满足“爆炸性” 的数据量的存储和传输要求。要解决多媒体信息存储容量大、数据传输率高的难 题，就需要采用压缩技术。 压缩数据量的重要方法是消除冗余数据。原始图像中存在着大量的冗余信息， 如时间冗余、空间冗余、信息熵冗余、谱间冗余、几何结构冗余、视觉冗余和知 识冗余等等。一般情况下画面的大部分区域信号变化缓慢，尤其是背景部分信号 几乎不变。因此，视频图像在相邻像素间、相邻行间、相邻帧间存在相关性，这 种相关性表现为空间冗余和时间冗余。视频图像的空间冗余一般通过离散余弦变 换( d i s c r e t ec o s i n et r a n s f o r m ，d c t ) 、离散小波变换( d i s c r e t ew a v e l e t t r a n s f o r m ，d w t ) 等变换来去除，而视频图像的时间冗余则通常使用运动估计和运动补偿来完成。 运动估计( ) 和运动补偿技术已广泛用于视频压缩的一些国际标准中，如 m p e g - 4 ，i t u th 2 6 4 。在这些视频压缩国际标准中，运动估计是最关键的技术之 一。运动估计在整个系统中的计算复杂度最大，针对运动估计的研究是目前视频 压缩工作的研究热点之一。 运动估计的块匹配算法因其算法简单，性能良好，已被广泛应用于当前的视 频编码标准中，例如h 2 6 x , m p e g - x 都采用了这种运动估计方法。其中最简单易 懂的方法是全搜索法( f s ) 。f s 可以获得全局最优运动矢量m v ，但这种方法耗时 巨大。为了提高块匹配算法的运行时间，很多快速块匹配都基于全搜索法进行了 改良。改良方法如下：第一，研究运动矢量的分布特征，改进搜索模板【1 7 】；第二， 通过研究空间或者时间相关性，取得更优的宏块搜索起点【8 9 l ；第三，采用提前终 止算法，在性能和复杂度之间作一个折中【9 ，l o 】。 对于一些运动特征比较特殊的视频序列，采用这些改进通常会使性能得到一 定的提高。如果将这些方法综合使用，将使性能大幅改进，这种综合起来的方法 近来发展迅速【11 , 1 2 】。 2 基于单应性关系的运动估计算法 1 2 本文应用场景 将引言中介绍的方法综合使用，性能将比只使用其中一种要好得多。但是这 些方法只能在一些具有特定运动特征的视频序列的编码中才可以使用。在水平、 竖直方向做0 - 3 6 0 度旋转运动的的摄像机( p t 相机) 广泛应用于监视系统，病患护 理，侦察和空间探测。由于受限运动，在这种摄像机拍摄的视频的帧间具备一定 的几何约束关系。这种关系被运用于运动检测和跟踪【1 3 ，1 4 1 ，但还几乎没有在视频 编码中被利用过。 本文针对p t 相机拍摄的视频序列，提出一种全新的基于单应性矩阵的搜索算 法( h b s ) 。这种空间几何约束关系被很好地运用在这种全新的方法中。 1 3 本文完成工作 视频图像一般存在空间冗余、时间冗余、信息熵冗余、视觉冗余等大量冗余 信息。图像压缩编码技术的核心思想是：尽可能去除视频帧之间的相关性，减少 冗余。本文所提的h b s 算法将计算机视觉领域单应性矩阵的概念融入帧间运动估 计，为搜索过程设定阈值以完成宏块归类，或者使得搜索提前终止。此算法能够 在保证视频编码质量的同时有效减少编码时间，提高编码效率。本文共分五章， 主要内容安排如下： 第一章：绪论 本章简单介绍了当前视频编码中运动估计算法的发展和本文算法应用的范 围，最后介绍了本文的主要内容。 第二章：h 2 6 4 视频编码标准 本章简要介绍了h 2 6 4 视频编码标准的分级结构，包括其档次结构及系统层级 结构等，并介绍了v c l 的一些关键技术( 整数变换、量化处理、帧内帧间预测和 编码、熵编码、去方块滤波、码率控制) 。 第三章：经典运动估计算法的实现及分析 本章首先介绍了运动估计的基本原理，然后介绍并分析了几个比较经典的搜 索模型及这些搜索模型的局限性。介绍了目前运动估计算法的主要研究方向和传 统的提前终止策略。 第四章：h b s 算法的原理及算法分析 在本章中提出一种基于单应性矩阵的运动估计方法( h b s ) ，将单应性矩阵的 几何关系采用到帧间运动估计，为搜索过程设定阈值以完成宏块归类及搜索的提 前终止。该算法有效地减少了编码时间，提高了编码效率。 第一章绪论 第五章：h b s 算法的实验结果及结果分析 为t i 9 1 , t j 试h b s 算法在编码系统中的性能，在h 2 6 4 1 拘参考软件j m l 0 0 中对其进 行测试。 第六章：总结与展望 本章为全文总结，并提出了可以进一步研究的方向。 第二章h - 2 6 4 视频编码标准 第二章h 2 6 4 视频编码标准 2 1h 2 6 4 简介 目前国际上制定视频编解码技术标准的组织有国际电信联盟( i t u ) 及国际标 准组织( i s o ) 。由i t u t 指定的国际标准通常被称为建议( r e c o m m e n d a t i o n s ) ，如 视频会议电视编码的标准在h 的子集里( h 2 6 1 、h 2 6 3 、h 2 6 3 + 等) 。m p e g ( m o v i n g p i c t u r ee x p e r tg r o u p ) 是在i s o 和i e c ( i n t e r n a t i o n a le l e c t r o t e c h n i c a lc o m m i s s i o n ， 国际电工委员会) 内运作的一个工作组。m p e g 标准主要用于广播电视、d v d 和 视频流媒体。m p e g 标准主要有以下五个，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 等。 为了进一步扩展和增加h 2 6 3 标准以及h 2 6 l ”】标准( i t u t 的视频编码专家组 v c e g 研究的视频编码标准) ，提高编码效率。在2 0 0 1 年1 2 月，由e g 和v c e g ( v i d e oc o d i n ge x p e l sg r o u p ) 的专家共同成立了联合视频小组( j o i n tv i d e ot e a m , t ) ，开发新的t 标准，采用很多先进技术，进一步完善了h 2 6 l 模型【1 6 1 ，使其 发展成为新的视频编码国际标准，并且使其在约束码率和图像质量、延时的限制、 复杂度、差错恢复、语法定义、网络友好性( n e t w o r k - f r i e n d l y ) 等方面具备良好 的特点1 1 7 j 。新标准于2 0 0 3 年5 月正式颁布，在i t u t 中名称分别为i t u tr e c h 2 6 4 ， 而在i s o i e c 中正式名称为m p e g - 4p a r t1 0 a v c ( 或1 4 4 9 6 1 0 a v c ) 1 8 1 ，简称h 2 6 4 。 2 0 0 2 年1 2 月，t 形成最后的标准草案。一方面，h 2 6 4 把h 2 6 3 中的一些已经证明 行之有效的可选模式作为h 2 6 4 中的基本模式固定下来，例如先进的帧内编码模式 和基于语法的算法编码模式等：另一方面，又加入了一些新的研究成果，形成了 自己的新的特性。 h 2 6 4 是v c e g 和m p e g 联合制定的新一代数字视频压缩标准，采用了“回归 基本 的简洁设计，获得了比以往标准好得多的压缩性能。h 2 6 4 具有以下特点： 低码流；图像质量高；容错能力强；网络适应性强。 h 2 6 4 视频编码标准包含了一系列新的特征，使得它比起以前的编解码器在编 码质量和压缩比上都有明显的提高，并且为“对话方式”或“非对话方式( 存储、 广播或流等) 等应用提供一个简单和直接的视频编码规范。在相同的主观质量下， h 2 6 4 编码效率比h 2 6 3 和m p e g - 4 提高了5 0 左右。此外，h 2 6 4 视频编码标准能够 在各种网络环境下的应用中使用，具有更好的网络友好性【1 9 】【2 0 】【2 1 1 。h 2 6 4 能工作 在低延时模式，同时又能很好地工作在没有延时限制的应用，如视频存储和以服 务器为基础的视频流式应用。 6基于单应性关系的运动估计算法 2 2 1h 2 6 4 的档次结构 2 2h 2 6 4 的分级结构 h 2 6 4 中视频的一场或一帧可用来产生一个编码图像，一个编码图像通常被划 分成若干个宏块。每幅图像中，若干宏块被排列成片的形式，分别有i 片、p 片、 b 片。 i 宏块是利用从当前片中己解码的像素作为参考进行帧内预测：p 宏块是利用 前面已编码图像作为参考图像进行帧内预测；b 宏块则是利用双向的参考图像( 当 前和未来的己编码图像帧) 进行帧内预测。i 片只包含i 宏块，p 片可包含p 和i 宏块，而b 片可包含b 和i 宏块。 h 2 6 4 规定了三种档次，每个档次支持一组特定的编码功能，并支持一类特定 的应用。 1 ) 基本档次：利用i 片和p 片支持帧内和帧间编码，支持利用基于上下文的 自适应的变长编码进行的熵编码( c o n t e x t a d a p t i v ev a r i a b l e l e n g t h c o d i n g ，c a v l c ) 。 主要用于可视电话、会议电视、无线通信等实时视频通信。 2 ) 主要档次：支持隔行视频，采用b 片的帧问编码和采用加权预测的帧内编 码；支持利用基于上下文的自适应的算术编码( c o n t e x t b a s e da d a p t i v eb i n a r y a r i t h m e t i cc o d i n g ，c a b a c ) 。主要用于数字广播电视与数字视频存储。 3 ) 扩展档次：支持码流之间有效的切换( s p 和s i 片) 、改进误码性能( 数据 分割) ，但不支持隔行视频和c a b a c 。 2 2 2h 2 6 4 系统层级结构 在系统层面上，h 2 6 4 提出了一个新的概念，在视频编码层( v i d e oc o d i n gl a y e r , v c l ) 和网络提取层( n e t w o r ka b s t r a c t i o nl a y e r , n a l ) 之间进行概念性分割，前者 是对视频内容的核心压缩内容的表述，后者是对通过特定类型网络进行递送的表 述，这样的结构便于信息的封装和对信息进行更好的优先级控制。 v c l 数据即编码处理的输出，它表示被压缩编码后的视频数据序列，视频编 码层主要规定如何有效地表示视频内容。在v c l 数据传输或存储之前，这些编码 的v c l 数据，先被映射或封装进n a l 单元中。网络提取层n a l 负责为编码后的 数据进行打包并提供头信息，以适应网络传输或者媒体存储的需要。每个n a l 单 元包括一个原始字节序列负荷( r b s p ) 、一组对应于视频编码数据的n a l 头信息。 v c l 主要研究基于常规的运动补偿、系数变换编码、熵编码等编码技术来提高视 频信号编码效率，研究的主要目的是希望基于兼容当前视频编码的流行标准h 2 6 3 第二章h 2 6 4 视频编码标准 和m p e g - 4 技术找到一种新的标准，用于取代目前视频编码标准。 h 2 6 4 系统层级结构如图2 1 所示。在v c l 和n a l 之间定义了一个基于分组 方式的接口，打包和相应的信令属于n a l 的一部分。这样，高编码效率和网络友 好性的任务分别由v c l 和n a l 来完成 2 2 】。 视频编码层( v c l ) j 片宏块结构 数据分割器 1 分组结构 i 网络提取层( n a l ) 文件格式h 3 2 x 系列分组r t p u d p i p 格式 2 2 3v c l 新技术简介 图2 1h 2 6 4 系统层级结构 v c l 编解码器的工作原理主要包括i n t r a i n t e r 预测和编码、变换、量化处理、 熵编码等关键技术( 实际上，我们可以利用运动估计和补偿技术对视频流u p b 帧 处理的关系来理解它) 。 使用5 个参考帧进行预测比只使用一个参考帧可以节省5 1 0 的码率；使用 基于内容的二进制自适应算术编码可以节省1 0 的码率下面我们简单叙述这些关 键技术 ；3 - 2 6 。 1 整数变换 虽然v c l 采用的变换类似于d c t 的变换，但是它使用的是4 x 4 的整数块， 而d c t 使用的是8 8 的浮点块。这样，由于它使用的是以整数为基础的空间变换， 因此其反变换不存在取舍误差的问题，同时能够解决编码器使用反变换的解码器 之间的误匹配问题。此外，采用小的形状块有助于降低块效应和明显的人工处理 痕迹。 输入的视频图像通常被划分为宏块分别进行编码，宏块的大小通常是1 6 1 6 的亮度块信息和对应的色度块信息。然后使用分块的运动补偿从已编码的帧对当 前帧的数据进行预测。之后，使用块变换或者子带分解来减少空域的统计相关性。 最常见的变换是8 8 的离散余弦变换( d c td i s c r e t ec o s i n et r a n s f o r m ) ，变换的输 8基于单应性关系的运动估计算法 出系数接下来被量化。 2 量化处理 量化步长是对宏块数据压缩的一个重要组成部分。类似于h 2 6 3 使用3 1 个不 同的量化步长，v c l 提供了3 2 个不同的量化步长，此外，v c l 使用非固定宽度 的尺度量化方法对变换系数进行量化，这些步长的增加按1 2 5 的混合速率增加， 通过使用精确的量化步长，更能改进色度部分的精度。量化变换的系数对应不同 的频率，一个对应d c 值，其余的分别对应不同的频率值，v c l 将所有的变换系 数放在一个数组中，采用z i g z a g 扫描和双扫描对数组中的数据进行读取。双扫描 只用于使用较小量化级的块内，由于它的步长小，从而有助于提高编码效率。 h 2 6 4 采用了整数变换与量化【2 7 】技术。为了解决以往标准采用的8 8 的d c t 逆过程出现失配问题，h 2 6 4 采用的是4 x 4 的整数离散余弦变换技术。h 2 6 4 对输 入的4 x 4 采样差值矩阵进行前向变换，然后进行分级量化和缩放，并根据图像动 态范围确定量化参数。 3 i n t r a 预测和编码 i n t r a 编码研究利用一个视频图像中的空间冗余来提高编码效率的问题与基于 1 6 x 1 6 像素宏块的m p e g - 4i n t r a 预测编码技术所不同的是，v c l 的i n t r a 预测技术 是利用相邻像素块的相关性，先将q c i f ( 1 7 6 1 4 4 ) 格式的图像分成9 9 个1 6 x 1 6 宏 块，然后分成4 x 4 像素块执行预测编码。对每个4 x 4 像素块，提供6 种预测4 x 4 相 邻亮度块的模式，其中模式0 是直流d c 预测模式和模式1 5 是邻近像素的方向预 测模式，同时，v c l 能够基于对块周围编码模式的检测规则找到最常用的模式， 然后通过对这此模式采用最短的符号表示，这种方式可以提高对每个块的预测模 式编码效率。 h 2 6 4 帧内预测( i n t r a - p r e d i c t i o n ) 是利用图像邻近像素间存在强烈的空间相 关性 2 8 - 3 0 ，编码时利用已解码重构的邻近块像素来实现对当前编码块的预测，对 预测块和当前编码块的残差进行变换、量化和熵编码以消除像素间大量的空域冗 余。对亮度像素而言，可对4 x 4 子块或者1 6 x 1 6 宏块进行帧内预测。色度块的帧 内预测模式，类似于1 6 x 1 6 亮度块预测模式。ip c m 编码模式是一种特殊的帧内 编码模式，它不经过预测和变换，直接编码。 帧内预测主要用于去除空间冗余，能够极大提高i 帧的压缩率，当然h 2 6 4 中 帧内预测不仅可以用在i 帧还可以用在p 帧或b 帧中。 4 i n t e r 预测和编码 i n t c r 预测编码是使用运动估计和运动补偿技术，通过消除有效帧之间的时间 冗余来提高编码效率。除了支持其它的视频标准通常使用的i 帧、p 帧和b 帧以外， v c l 还支持一种新的码流间可转换帧s p 帧。通过使用一个比特流中的s p 帧， v c l 可以在那些有类似内容但有不同码率的码流之间快速切换，并同时支持随机 第二章h 2 6 4 视频编码标准 9 访问和快速回放模式。此外，v c l 所支持的运动估计策略具有更多的关键特征， 能够增加帧间预测模式的数量和精度，以及通过增加运动估计的灵活性和功能来 改进运动估计的效率。 活动图像是由时间上连续图像帧组成的时间图像序列，它在时间上比在空间 上具有更大的相关性。大多数视频相邻帧间细节变化是很小的，即视频图像帧间 具有很强的相关性，利用帧与帧之间所具有的相关性进行帧间编码，可获得比帧 内编码高得多的压缩比。 h 2 6 4 帧间预测( i n t e r - p r e d i c t i o n ) 是利用已编码视频帧场和基于块的运动补 偿的预测模式【3 1 - 3 3 1 。运动补偿( m o t i o nc o m p e n s a t i o n ) 是一种描述相邻帧( 相邻 在这里表示在编码关系上相邻，在播放顺序上两帧未必相邻) 差别的方法，具体 来说是描述前面一帧的每个小块怎样移动到当前帧中的某个位置去。h 2 “帧间预 测中块的大小可以是1 6 x1 6 、1 6 x 8 、8 x1 6 、8 x 8 、8 x 4 、4 x 8 、4 x 4 。比起以前的 视频编码标准，h 2 6 4 以更灵活的方式使用已编码的更多帧来作为参考帧，h 2 6 4 中最多可从1 5 个参考图像中进行选择，选出最佳的匹配图像。一般对于平坦区域 使用大尺寸的块而细节多的区域使用小尺寸的块。灵活的宏块划分方式使得在帧 间预测时能够根据内容灵活地划分宏块大小，从而得到较小的预测差信号，提高 h 2 6 4 的编码效率。 “j 5 熵编码 我们把自信息量的概率平均值，即随机变量的数学期望值叫做信息熵或简称 熵( e n t r o p y ) 。数据压缩技术的理论基础就是信息论。信息论中的信源编码理论解 决的主要问题：数据压缩的理论极限；数据压缩的基本途径。根据信息论的 原理，可以找到最佳数据压缩编码的方法，数据压缩的理论极限是信息熵。如果 要求编码过程中不丢失信息量，即要求保存信息熵，这种信息保持编码叫熵编码， 是根据消息出现概率的分布特性而进行的。熵编码是无损压缩编码方法，它生成 的码流可以经解码无失真地恢复出原始数据。熵编码是建立在随机过程的统计特 性基础上的。 在视频编码中，熵编码把一系列用来表示视频序列的元素符号转变为一个用 来传输或是存储的压缩码流。输入的符号可能包括量化的变换系数，运动向量( 对 于每个运动补偿块的向量值x 和y ) ，标记( 在序列中用来表示重同步位的点) ，头 ( 宏块头，图像头，序列的头等) 以及附加信息( 对于正确解码来说不重要的信息) 。 在h 2 6 4 a v c 在视频编码层v c l 中的熵编码( e n t r o p yc o d i n g ) 技术采用基于内 容的自适应变长编码c a v l c ( c o n t e x t b a s e da d a p t i v ev a r i a b l el e n g t hc o d i n g ) 与 一致变字长编码u v l c ( u n i v e r s a lv a r i a b l el e n g t hc o d i n g ) 相结合的编码和基于内 容的自适应二进制算术编码c a b a c ( c o n t e x t b a s e da d a p t i v eb i n a r ya r i t h m e t i c c o d i n g ) ，_ 轴 1 0 基于单应性关系的运动估计算法 6 去方块滤波 h 2 6 4 相对以往标准有效地提高了编码效率和编码质量，其原因之一是在编解 码时引入去方块滤波器。h 2 6 4 在编码时将编码帧分割为不重叠的宏块，使用d c t 变化和熵编码。其中每个宏块单独编码，没有考虑相邻块之间的相关性，从而在 重建图像时会出现方块效应。另外，对变换系数进行量化在反变换时也会产生误 差，在宏块边界也会产生方块效应。此外，由于宏块的划分使得相邻的宏块可能 参考不同的帧，使得运动补偿时产生误差，在重建时会产生宏块边界的不连续。 在视频编解码器中加入去方块滤波器的方法有两种：后置滤波器和环路滤波 器。后置滤波器只处理编码环路外的显示缓冲器中的数据。环路滤波器处理编码 环路中的数据。在编码器中，被滤波的图像帧作为后续编码帧运动补偿的参考帧； 在解码器中，滤波后的图像输出显示。 7 码率控制 码率控制的目的是在给定码率下高效地传输数据，保证良好稳定的接收端质 量。由于视频序列中的图像内容随着空间与时间的不同而变化很大，需要为图像 的不同部分选择不同的编码参数进行压缩编码。h 2 6 4 编码器采用基于l a g r a n g i a n 优化算法的率失真优化模型实现视频编码的控制。h 2 6 4 的编码器通过最小化 l a g r a n g i a n 代价函数实现对每一个宏块的编码模式的选定。编码宏块的l a g r a n g i a n 代价函数如式( 2 1 ) 所示。 j ( m v ，丑刀n ，) = s a d ( s ，c ( m v ) ) + z , o l i o n r ( m z 一尸)式( 2 - 1 ) 其中s a d ( 绝对差值和) 计算公式如下： b r 一，b y s a d ( s ，c ( ) ) = 乏：is x ，y 卜c x m v x ，y m v , i t ，髟= 1 6 ，8 0 r 4 式( 2 2 ) ，一1 y = l 其中s 是当前进行编码的原始数据，而c 是已经编码重建的用于运动补偿的参 考帧的数据。m v 为候选的运动矢量，刀洲为拉格朗日常数，p m v 为预测矢量， r ( m v p m v ) 代表了运动矢量差分编码的比特数。e ，b 。表示块的水平和垂直 像素数，取值1 6 、8 或4 。 2 3h 2 6 4 编码器和解码器 与早期的标准一样，为了实现的灵活性以及便于竞争，h 2 6 4 只规定了经编码 的视频比特流的句法和该比特流的解码方法，并没有明确地规定一个编解码器【3 4 】 如何实现。在实际工作中，一对互相匹配的编解码器可能包含如图2 2 和图2 3 所 示的功能组成部分。 第二章h 2 6 4 视频编码标准 2 3 1h 2 6 4 编码器 典型的数字视频编码器的第一步是将从摄像机输入的视频从r g b 色度空间转 换到y c b c r 色度空间，而且通常还伴有色度抽样来生成4 ：2 ：0 格式的视频( 有时 候在隔行扫描的情况下会采用4 ：2 ：2 的抽样方式) 。转换到y c b c r 色度空间会带来 两点好处：这样做可以解除部分色度信号中的相关性，提高了可压缩能力； 这样做可以将亮度信号分离出来：由于亮度信号对视觉感觉是最重要的，相对 来说色度信号对视觉感觉就不是那么重要，因此可以将色度信号抽样到较低的分 辨率( 4 ：2 ：0 或者4 ：2 ：2 ) 而不影响人观看的感觉。 编码时，输入的视频图像通常被划分为宏块分别进行编码，每个宏块经预测 编码、变换、量化、熵编码等过程完成编码。 解码过程与编码过程大致相反。其中不能完全恢复原来信息的步骤是量化。 这时候，要尽可能接近的恢复原来的信息，这个过程被称为反量化，尽管量化本 身是个不可逆过程。知 在实际应用中，为了使编码的码流具有互操作性( 即由a 编码器编成的码流 可以由b 解码器解码，反之亦然) ，仅仅对解码器的解码过程进行规范就足够了。 通常编码的过程并不完全被一个标准所定义，用户有设计自己编码器的自由，。只 要用户设计的编码器编码产生的码流是符合解码规范的就可以了。 h 2 6 4 编码器功能组成如图2 2 所示，输入部分由当前编码帧f n 和参考帧f n - 1 组成，输出部分是重建帧f n 。在编码过程中，当前编码帧f n 被划分为1 6 1 6 的 宏块，具体编码是以宏块为单位。每个宏块在进行编码时，帧间编码经运动估计 m e 得到运动补偿m c 后得到预测值p 。当前块减去预测值p 产生预测的残差d n ， 此残差经变换( t ) 、量化( q ) 产生变换系数x ，此后经过重排序和熵编码处理形 成便于存储、传输的码流。其中，残差d n 经变换量化后可通过反量化( q 1 ) 和 反变换( t - 1 ) 得到d n ，d n 和预测值p 相加产生u f n ，再通过滤波后得到重建帧 f 1 1 。 1 2基于单应性关系的运动估计算法 图2 2h 2 6 4 编码器 h 2 6 4 编码器具有以下主要特点：提高预测编码部分( m c m e ) 的设计； 提高变换和编码部分效率的设计；提高抗无码丢包以及增强在不同网络环境 下操作的灵活性设计。 2 3 2h 2 6 4 解码器 h 2 6 4 解码器功能组成如图2 3 所示。编码器产生的码流经传输或存储后可通 过解码器恢复出重建图像( 重建帧) 。解码过程是编码的逆过程。编码后的码流首 先经过熵解码和重排序产生变换系数x ，然后采取反量化( q - 1 ) 和反变换( t 。1 ) 得到残差d 1 1 ，利用解码器产生的预测值p 和d a 相加得到u f 1 1 ，在经过滤波处理 就产生重建帧，也就是解码器的输出。 图2 3h 2 6 4 解码器 h 2 6 4 是目前性能最优的视频编码标准，并且已经得到了越来越多的应用。该 标准引入了一系列新的能够大大提高压缩性能的技术，并能够同时在高码率端和 低码率端大大超越以前的诸标准。 2 4 本章小结 2 0 0 3 年5 月由t 正式颁布的h 2 6 4 视频编码标准具有一系列新的特征，在 相同的主观质量上，编码效率比h 2 6 3 和m p e g - 4 提高了5 0 左右，并且能够在 各种网络环境下的应用中使用，具有良好的网络友好性。 本章主要从h 2 6 4 的结构、编码器和解码器以及关键技术等几个方面简要介 绍了h 2 6 4 视频编码标准。其中h 2 6 4 的结构包括档次结构和系统层级结构；系 统层级结构中，视频编码层v c l 部分的关键技术包括帧内预测、帧间预测、整数 变换和量化、熵编码、去方块滤波、码率控制等。本文在第四章提出的基于单应 性关系的运动估计算法- 璐s 算法就是基于h 2 6 4 标准而设计的。 第三章经典运动估计算法的实现与分析 1 3 第三章经典运动估计算法的实现与分析 随着3 g 的快速发展和在国际上的正式使用，视频和多媒体等技术的广泛使 用将成为必然趋势，适应于网络环境传输的视频编码标准h 2 6 4 自提出就成为研 究的热点。在h 2 6 4 标准中，使用运动估计和补偿技术来提高压缩效率。在本章 中，将以具体分析提高块匹配运动估计算法性能的主要技术、方法以及各个经典 的运动估计算法的实现过程为重点，最后通过性能比较，总结出各种运动估计算 法的优缺点，为第四章中提出的算法提供依据。 运动估计( m o t i o ne s t i m a t i o n , m e ) 研究的主要内容是如何快速、有效地获得 高精度的运动矢量( m o t i o nv e c t o r , m v ) 【3 5 j 。运动估计算法的目的在于使运动矢 量尽可能的精确，在有较好的压缩性能的同时降低算法的复杂度，提高图像质量、 加快估计速度、减小比特率等。在实际中要把图像分割成不同运动的物体比较困 难，通常采用两种较简单的方法。一种是把图像分为矩阵子块，适当选择块的大 小，估计出块的位移，进行预测传输，另一种是对每个像素的位移都进行估计。 在视频编码领域使用的运动估计算法有块匹配法、像素递归法、相位相关法、 以及针对由摄像机运动引起图像全局运动的全局运动参数估计等 3 6 】。 1 ) 块匹配法( b l o c km a t c h i n ga l g o r i t h m ，b m a ) 块匹配法( b m a ) 是目前最常用的运动估计算法，它假设块内各个像素都只 做相等的平移。在视频压缩编码国际标准中，如h 2 6 1 ，m p e g i - 一4 和h 2 6 4 ，都采 用基于块的运动估计方法。 块匹配法的原理是：将当前帧划分为m x n 图像子块( b l o c k ) ，在参考帧中设 定一个大小为( m + 2 w x ) x ( n + 2 w y ) 的一块搜索区域，利用m x n 子块在改搜 索区域内寻求最优匹配来得到运动矢量的估计( d x ，d y ) 。衡量匹配好坏的准则有 归一化互相关函数( n c c f ) 、均方误差( m s e ) 和帧间绝对差( ) 。最优匹 配的搜索方法中最简单可靠的是穷尽搜索法。 块匹配法存在以下三个问题：块尺寸的选择；估计得到的运动矢量场一 致性不够好；块内包含前景背景两个不同区域时的运动估计。 2 ) 像素递归法( p i x e lr e c u r s i v e a l g o r i t h m ，p r a ) 像素递归法能够适应运动补偿帧内插中对每个像素的运动进行精确到亚像素 级的估计的要求。由于每个像素都有一个对应的运动矢量，为降低码率不可能将 其都传输到接收端。解决办法是让接收端在与发端同样的条件下使用与发端相同 的方法进行运动估计。代价是接收端较复杂，不利于一发多收的应用。 如果孤立地考察单个像素，像素递归法的估计精度和可靠性总是难以得到根 1 4 基于单应性关系的运动估计算法 本性的提高。但如果在估计某像素的运动矢量的同时考虑其邻域点，则性能可得 到显著改进。这与块匹配法为改善估计性能而引用邻近像素信息类似，因而也有 学者将像素递归法和块匹配法归于同一大类，并采用块递归法、梯度法等名词来 描述把块递归和迭代修正相结合的运动估计算法。 3 ) 相位相关法 由于物体的空间位移与其相位变化相对应，因而运动位移估计也可在频率域 进行。相位相关法的提出基于下列现象：对于平移运动，相位相关函数将产生比 互相关函数尖锐得多的尖峰。因此，利用相位相关函数进行运动估计十分有利。 采用相位相关法进行运动位移估计受到一些限制【3 7 1 。一是要求运动物体是孤 立物体，而且背景要均匀。另外，像块尺寸的选择要适当。尺寸太小无法保证相 位相关法的优越性能，但尺寸太大，块内做不同运动的物体太多，峰点太多，难 以判断，且运算量迅速上升。 一种将相位相关法与块匹配法结合的运动位移估计算法【3 8 】步骤是：先将每帧 编码图像划分成n x n 大小的像块，例如n = 1 2 8 ，计算每个像块的相位相关函数； 再选择相位相关函数中的几个峰值作为候选位移矢量；然后用块匹配法，围绕几 个峰值，逐小块地在这些候选位移矢量附近搜索，选定一个最终的运动位移矢量 估计值。 4 ) 全局运动参数法 由摄像机的运动引起的图像运动是全局的。车载、机载摄像或摄像机做推镜 头、摇镜头时的序列图像都含有全局运动分量。可以用少数几个参量结合适当的 运动模型来描述这种全局性的运动。 从以上众多算法的提出可以看出，运动估计具有其重要的研究价值。如何在 足够的精度下实现实时运动矢量场的估计，并以尽可能少的附加信息传输运动矢 量信息，还面临着许多问题，下面对这些问题做个小结。 ( 1 ) 块大小的选择 为了满足块匹配法的前提条件，必须合理选择块大小，以保证块内各像素做 平移运动。第二章中提到，块匹配法中块的大小受到两个矛盾的约束。块大时， 影响估计的精度；块小时，则易受噪声干扰，估计不够可靠，而且所需传输的附 加信息也大大增加。因此必须恰到好处地选择块的大小，以做到两者兼顾。目前 的压缩标准，如h 2 6 1 ，m p e g 等，一般多以1 6 x1 6 大小的块作为块匹配单元，而 h 9 - 6 4 允许采用1 6 1 6 ，1 6 x 8 ，8 1 6 ，8 8 ，8 x 4 ，4 x 8 ，4 x 4 多重可变块大小形式。 ( 2 ) 匹配准则 通常，由于s a d 准则计算量小，许多算法采用s a d 作为匹配准则。在h 2 6 4 中的块匹配准则也是s a d 。 ( 3 ) 搜索策略 第三章经典运动估计算法的实现与分析 1 5 搜索策略的好坏会极大地影响算法的计算复杂度和可靠性，基本算法是全搜 索法，它虽然简单可靠，但计算量太大，不宜实时应用，为了减少计算量，发展 了许多块快速搜索算法。现代的块运动估计搜索算法一般都考虑了运动矢量m v 的中心偏移分布的特性。 ( 4 ) 估计精度 在h 2 6 3 和m p e g 2 中，运动估计精确到半像素，而最新的国际标准h 2 6 4 中运动矢量的精度目前可达到1 4 像素，甚至1 8 像素精度。一般半像素精度、1 4 及1 8 像素精度参考帧的获得均可借助于简单的双线性内插来实现。而h 2 6 4 在此 方面也有所不同。 ( 5 ) 运动矢量场的一致性 上述的许多块匹配法将图像分割成子块，孤立地逐块进行匹配，没有利用块 间的相关性。常常造成所求得的运动矢量场一致性不好，这也将影响运动补偿的 效果。解决的办法之一是修改匹配准则，加上块间运动矢量一致性约束项。另外， 分层块匹配法也可解决运动矢量场的一致性问题。 ! ( 6 ) 块内运动的不一致性 在会议电视等应用中，常常遇到“边界块”，即块内一部分为背景，一部分为 运动前景。此时块匹配法的块内各像素做相同的平移运动的前提是假设不成立， 无法估计到准确的运动，这种情况的解决办法是分区，对两个性质不同的区域分 别进行运动检测，但带来了如何分区和传送边界信息的困难。m p e g 2 算法中引入 b 帧结构，对b 帧分别用前帧和后帧进行运动估计，以此解决背景与前景运动不 一致的问题。h 2 6 3 的算法可选项中采用将1 6 x1 6 子块进一步分成四个8 8 块分 别进行运动估计的方法来解决块内运动不一致的问题。而h 2 6 4 算法更是引进了 多达7 种的块尺寸，很好的解决了这个问题。 3 1 目前运动估计算法的主要研究方向 大量的研究论文显示，目前视频图像编码运动估计的研究主要集中在以下几 个方面： ( 1 ) 不断的改进运动估计搜索模型，旨在减少搜索点数，使搜索尽快收敛到 最佳匹配点。从而减少搜索时间，提高编码的速度。如三步搜索法( t h r e e s t e ps e a r c h , t s s ) 【3 9 】、梯度下降法b b g d s t 4 0 i 、菱形搜索( d i a m o n ds e a r c h , d s ) 【4 1 1 、混合的 非对称多六边形搜索算法( h y b r i du n s y m m e t r i c a l c r o s sm u l t i h e x a g o n g r i ds e a r c h , u m h e x a g o n s ) 1 4 2 】等。块运动估计搜索的方法经过了从全搜索、规定最大搜索步数 的快速搜索、搜索步数不限的快速搜索以及混合模板搜索法四个阶段的发展。目 前最