（信号与信息处理专业论文）基于粒子群的视频运动估计算法研究与优化.pdf

摘要 摘要 随着近年来多媒体技术的飞速发展，许多应用领域对视频图像的实时压缩提 出了更高的要求，快速、高效的压缩算法是解决这一问题的关键。运动估计作为 实现视频压缩的核心技术，也是压缩编码中运算最复杂、最耗时的环节，在视频 编码中，运动估计的计算量占5 0 8 0 ，从而成为这一领域最有挑战性的研究课 题。另一方面，由于基于块匹配的运动估计简单且易于实现，因此被当前的所有 视频编码国际标准所采用。 基于块匹配的运动估计由于其简单易实现性而被当前的所有视频编码国际标 准所采用。全搜索块匹配法是最简单最直接的块匹配运动估计法，但是由于其运 算复杂度太高很难应用于实时视频编码中，从而业界提出了很多种快速块匹配运 动估计方法。 本文首先分析了块匹配运动估计中运动矢量的分布特点，得到运动矢量中心 偏置性和时空相关性的两个重要特性，并对现有文献中比较经典和著名的快速算 法进行了科学合理的归类分析。 在对运动估计和粒子群优化算法( p s o ) 进行深入分析的基础上，本文创造 性的将p s o 算法应用于块匹配运动估计领域，并对p s o 算法中涉及到的参数通 过理论及实验分析，并确定最终取值。 最后，本文分析了标准p s o 算法在运用于块匹配运动估计领域存在的三方面 不足，在将标准p s o 算法结合了运动矢量分布特性及粒子变异特性的基础上，对 标准p s o 算法的三个不足进行了改进，提出了改进的p s o 算法，使得改进后的 p s o 算法拥有更快的搜索速度和更佳的搜索性能。 关键词：视频编码，运动估计，粒子群算法 a b s t r a c t a b s t r a c t w i mm er e c e n tr a p i dd e v e l o p m e n to fm u l t i m e d i at e c l m 0 1 0 9 y ，1 1 i g h e rd 锄a i l do f r e a l t i m ev i d e oi m a g ec o m p r e s s i o ni nm a n ya p p l i c a t i o n s ， r a p i d a 1 1 de 伍c i e n t c 0 i n p r e s s i o na l g o r i t h mi sm ek e y t os o l v et 1 1 i sp r o b l e m m o t i o ne s t i m a t i o n ，m ec o r e v i d e 0c o n l p r e s s i o nt e c h n 0 1 0 9 y ，i sa l s oa o n eo fm em o s tc o m p l e xa 1 1 dt i m e c o n s u m i n g 唧e c to fc o d i n go p e r a t i o n 1 1 1v i d e oc o d i n g ，m o t i o ne s t i m a t i o na c c o u l l t s 南ra b o u t5 0 t 08 0 o fm ew h o l ee i l c o d i n gc o m p u t a t i o i l s oi ti st l l em o s tc h a l l e l l 西n gr e s e a r c ht o p i c i n 、r i d e o e n c o d i n g o nt l l eo 也e r h a n d ， m o t i o ne s t i m a t i o nw m 6 hb a s e do n b l o c k m a t c m n gi ss i m p l ea i l de a l s yt oi m p l 锄e n t ，t h e r e f o r e ，m i se s t i l n a t i o nu s e db ya 1 1 a l r i 锄ti n t e m a t i o n a lv i d e oc o d i n gs t a i l d a r d s f a s tf i l l l s e a r c hm a t c h i l l ga l g o r i m mi so n eo fm em o s td i r e na i l ds i m p l e s t b l o c k - n l a t c h i n g m o t i o n鹳t i m a 廿o nm e m o d s b e c a u s eo fi t s 1 1 i g l lc o m p u t a t i o n c o m p l e x i t ) ，d i 伍c u l tt 0a p p l yi l lr e a l t i m ev i d e 0e i l c o d i n g ，m a l l y 凤tb l o c k - m a t 出n g m 砸o ne s t i l l l a t i o nm e t l l o d sa r ed e d u c e di 1 1p r a c t i c a la p p l i c a t i o n s h lt h i sd i s s e r t a t i o 玛廿l ed i s t r i h l t i o no fm o t i o nv e c t o r si n 吐1 eb l o c k m a t c l l i n g m 硝o ne s t i m a t i o na r ea 1 1 a l y z e d s p a t i a la i l dt e i i l p o r a lc o r r e l 撕o no f 廿1 ec e n t 昏b i a s e d m o 廿o nv e c t o ra r ep r o p o s e d ，m o r ec l a l s s i c a la i l dw e l l k n o w nf 如ta l g o r i t l l mo f 廿1 e e x i s t i n g1 i t 蹦l n 聪a r ec l a l s s i f i e d 0 l i l 也eb a s i so fi n - d e p t l l 鲫m y s i so fm o t i o ne s t i m a t i o na r l dp a r t i d es w 姗 0 p t i m i z a t i o n ( p s o ) ，l i sd i s s e n a t i o nc o n d u c tp s oa l g o r i 恤ni i la p p l i c a t i o no fm e a r e a o fb l o c k m a t c h i n gm o t i o ne s t i m a t i o n ，a n dt h r o u 曲m em e o r e t i c a la n de x p 耐m e n t a l a 1 1 a l y s i so fm ei 1 1 v 0 1 v e dp a 删n 曲e r si np s oa l g o r i t h mp a r a m e t e r s ，t h ef i n a lv a l u e sa r c d e t a m i n e d f i n a l l y ，衄e ea s p e c t so fi n a d e q u a c y o fm es t a n d a r dp s oa l g o r i 蛆 i i l b l o c k - m a t c h i n gm o t i o ne s t i m a t i o na r ea i l a l y z e di nt 1 1 i sd i s s e n a t i o n 1 1 1 ec h 姗c t 舐s t i c s o fm o t i o nv e c t o rd i s 仃i b u t i o nc 由i n e sv a 打a t i o nc h a r a 曲。r i s t i c so fp a r t i c l e si nt h e s t a i l d 莉p s oa l g o r i t l l i i lt 0m a l ( em ei m p r o v 锄e n t so ft h ei n a d e q u a c y t 1 1 ea d v a n c e d p s oa l g o r i t l l i i li sp r e s e i l t e ds 0a st oo b t a i n 风t e rs p e e da j l db 甜e rs e a r c hp e r f o 肌a n c e i i a b s t r a c t k e y w o r d s ： v i d e o e n c o d i n 吕 m o t i o ne s t i m a t i o n a l g o d t s ， p a n i c l es w a n n o p t i m i z a t i o n i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名： 王半 日期：加口9 年争月2 日 f 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存j 汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 至圣导师签名： 日期：矽- 7 第一章绪论 1 1 课题背景 第一章绪论弟一早珀t 匕 近年来，随着信息技术的快速发展，多媒体通信业务的需求也与日俱增。尽 管人们在增加信道带宽以及提高信道传输效率方面做了很多努力，也取得了不错 的效果，但信息数字化直接带来的影响就是“信息爆炸 ，使其成为多媒体技术 发展中的一个非常棘手的瓶颈问题。比如：1 幅6 4 0 4 8 0 分辨率的彩色图像( 2 4 比特像素) ，其数据量约为7 3 7 2 8 m b i t ，如果以每秒2 5 帧的速度播放，则视频 信号的传输速率高达1 8 4 3 2 m b p s 【。另一方面，如果存放在6 5 0 m b 的光盘中， 在不考虑音频信号的情况下，每张光盘也只能播放2 8 2 秒。因此我们可以发现数 字视频信息的数据量是非常非常巨大的，如果不经过压缩，数字视频信息传输所 需要的高传输速率和数字视频存储所需要的巨大容量将成为推广应用数字视频技 术的最大障碍。所以要解决多媒体信息存储容量大、数据传输率高的难题，就需 要采用视频编码对图像进行压缩。 现阶段，运动估计是所有与视频编码相关的国际标准中的一项关键技术。它 是一种实现帧间编码的方法，其原理为利用前后两帧或若干帧之间的时间相关性， 去除时间冗余度，也正是由于在一般视频序列的两帧之间有很大的空间结构相似 性【2 】，因此帧间编码才能够能减少冗余度。前后两帧之间的差帧则可以用比帧内 编码所需少很多的比特数来进行编码。运动估计算法能够实现帧间编码的过程是 通过将运动估计得到的运动矢量和误差图像都送到接收端，并在接收端将预测图 像与误差图像进行叠加，从而叠加生成原始图像。 作为视频编码的关键技术，运动估计关键需要解决的问题是如何提高它的估 算精度和速度。但在实际计算过程中这两个指标往往无法同时达到最优，因此如 何能够解决这个折衷问题就具有很高的理论价值和实际意义，这是图像处理领域 和图像通信领域一个极其重要的研究课题，运动估计的研究和应用必将促进图像 通信、计算机通信和多媒体技术的长足发展。 电子科技大学硕士学位论文 1 2 视频压缩技术研究概述 1 2 1 视频压缩原理 以尽可能少的比特数表征原始图像数据就是数字视频图像压缩的最终目的， 并要求能够保持重构图像的质量，使其达到应用场合的要求。视频图像压缩之所 以可以成为实现，关键原因是由于视频图像数据中存在多种冗余： 1 时间冗余：视频序列中，相邻帧图像间存在的很强的相关性称之为时间冗余。 2 空间冗余：一幅图像中，相邻的像素之间存在的空间相关性称之为空间冗余。 3 统计冗余：对于一串由很多字符组成的数据而言，倘若其中部分字符经常出现， 而另外一些字符却很少出现，则这种统计上的不均匀性则构成了统计冗余。 4 视觉冗余：人眼视觉系统( h 啪a i lv i 刚s y s t e m ) 的响应频率随空间频率的增 长而程降低趋势，并且这种对应关系在色差通道上表现非常明显。 5 其它冗余：例如知识冗余等。 因此，视频图像压缩原理就是通过充分利用视频图像本身所固有的各种冗余 来实现减少图像信息冗余度并最终获得满意的图像复原质量。针对上述各种冗余， 人们提出了与之相对应的去除冗余方法，表卜1 按冗余的类型列出了一些常用的 压缩方法。 表1 1 冗余类型及对应压缩方法 冗余类型举例对应压缩方法 时间冗余帧间像素间的相关性运动估计与运动补偿 空间冗余帧内相邻像素间线性相关预测编码和变换编码 每个像素值不论数值大小熵编码，如h u 胁a i l 编 统计冗余 都用8 b i t 表示码和算术编码 人眼视觉系统( h v s ) 对亮度色度 视觉冗余量化 信号视觉敏感性的不同 知识冗余人的肩头结构，人脸结构的确定性模型基编码 1 2 2 经典视频图像压缩方法 经典图像编码方法是以s h 锄o n 的信息理论为基础，它利用图像中存在的各 种相关性消除冗余【3 1 。常用的有变换编码、运动估计法、熵编码和量化编码等。 2 第一章绪论 经典图像编码方法根据是否引入失真可分为有损编码方法和无损编码方法；又可 根据图像的不同属性分为单色图像、彩色图像以及多光谱图像的压缩，二值图像、 多值图像与灰度图像编码方法；根据编码方法原理，还可分为基于图像特征提取、 基于图像统计特性和基于人眼视觉特性等方澍4 1 。 ( 1 ) 变换编码 变换编码并不是直接对空域图像信号编码，而首先是将空域图像信号先映射 变换到另外一个正交矢量空间也即变换域，并对产生的变换系数进行重新编码【5 】 【6 1 。通常情况下变换域中的能量往往只存在于很少的几项系数上，比空间域中的 能量更加集中，因此只要在变换域中保留很少的几项系数，经反变换后就能够得 到非常好的重建效果。 在变换编码中，为了保证图像相关性和平稳性，同时也是为了保证运算量尽 量小，通常情况下先在编码器中将待编码图像分成若干子块，再对每个子块一一 进行正交变换，从而生成变换域中的系数矩阵样本，此后系数选择器选择其中若 干系数进行量化、编码以及传输操作。在解码器中，经解码、反量化操作后得到 的具有一定量化失真的变换系数再经反变换就可得到恢复的图像信号。变换编码 方法应用于图像编码中首先是从傅立叶( f o 埘神变换开始的，随后又依次出现了 哈达码( h a r d 锄a r d ) 变换、k l ( k a r b 啪e n l o e v e ) 变换、余弦变换( d c t ) 和小波变换 等【刀，正是他们的出现推动了变换编码的发展。 变换编码能够有效的消除图像数据之间的空间冗余，已经被证明为是一种高 效的图像压缩编码方法，同时也是迄今为止所有国际编码标准的基础之一。 ( 2 ) 熵编码 熵编码也称为统计编码，是一类无损编码方法，并因其编码后的平均码字长 度接近信源熵而得名，其编码原理是基于信源的统计冗余特性。熵编码可以去除 信源内在的相关性并改变概率分布不均匀的特点，从而实现图像压缩的目的。当 前，经典的熵编码方法有霍夫曼编码、算术编码和游程编码。前两个利用了信源 概率分布的不均匀性，后一个利用信源自身的相关性【8 】。 1 9 5 2 年，首先由霍夫曼( d a h u m n a l l ) 提出了一种不等长编码方法，他规定 这种编码的码字长度的排列与符号的概率大小的排列是严格逆序的，目前理论上 已经证明了其平均码长最短，因此被称为最佳码。熵编码与有损的量化相比，它 是无失真的编码技术，在视频图像压缩中一般在变换量化之后。熵编码是以信息 论知识为基础的，并利用统计特性将每个系数编为长短不同的比特串。 算术编码的编码效率受编码模式( 概率统计与范围分配) 影响，它的优点是其 3 电子科技大学硕士学位论文 自适应模式能够不需预先定义概率模型， 况，但算术编码的缺点也是非常明显的， 实际问题中不利于硬件实现。 因而可以适用于无法实现概率统计的情 其实现方法较霍夫曼编码复杂很多，在 游程编码方法则是通过统计出现相同符号段的长度( 称为一个游程) ，并结合 该符号值来表示该符号段。游程编码方法充分利用了符号自身的相关性，从而达 到压缩数据的效果。 ( 3 ) 运动估计法 运动估计法则充分利用了视频序列的时间冗余特性，通过运动估计法得到待 编码图像和参考图像的差值，再将差值进行编码进而实现对视频图像压缩的目的。 当前运动估计法分为两大类：像素递推法和块匹配法【9 】。 像素递归技术是基于递归的思想。在连续帧中像素数据变化的原因是由于物 体的移位造成的，因此如果沿着梯度方向对某像素周围的若干个像素作迭代操作， 最终会收敛到一个固定的运动估计矢量，从而实现该像素位移的预测。 而块匹配技术则是基于当前帧中一定大小的块，在当前帧的前一帧和后一帧 的某一固定范围内，以一定的匹配准则搜索当前像素块的最佳匹配块作为其预测 块。尽管像素递归技术对比较复杂的运动情况而言，其预测精度比块匹配技术高 一些，但是因为像素递归技术的计算量比块匹配技术要大很多，并且块匹配技术 本身也具有较好的预测性能，因此基于匹配误差最小化的块匹配技术得到了广泛 的应用，它也是本文讨论的重点。 ( 4 ) 量化 量化是数据压缩中的一种非常有效的压缩方法，也是图像压缩编码会产生失 真的主要根源【1 0 1 。量化所完成的作用则是按一定的准则对取样值作近似处理，使 量化器输出的幅值大小仅为有限整数值。可以这样理解，图像压缩中如果没有量 化就不能很好地实现数据的压缩，或者数据压缩比较小。因此，量化器的设计原 则是既要得到尽可量高的压缩比，同时还要减少量化失真，尽可能的保持较高的 图像质量。量化分为标量量化和矢量量化。 ( 5 ) 塔型编码 b u r t 等人提出了塔型编码方法，它的基本原理是通过将原图像分解为空间分 辨率不同的一系列子图像，并对每个子图像进行编码传输，则在解码端得到的就 是一个逐渐清晰的图像。 4 第一章绪论 1 3 视频压缩技术发展概况及国际标准 绝大多数视频相关国际标准的制定都与图像编码技术的快速发展以及大力应 用有关。当前，在视频压缩的国际标准中，大致分来有两大类标准最为重要，第 一类为国际标准化组织( i s o ) 和国际电工委员会( i e c ) 联合组织的运动图像专 家组( m p e g ) 的m p e g 系列标准m p e g l 2 4 ，第二类为由国际电信联盟组织( i t u ) 制定的h 2 6 x 系列标准h 2 6 1 3 4 。h 2 6 4 是目前最新的编码标准，它在i t u t 称 为h 2 6 4 ，而在m p e g 则称为m p e g 4 a v c ( p a n1 0 ) 。h 2 6 4 同以往的其它标准 相比较，拥有极高的编码效率，简洁的表现形式和良好的抗误码性能。 1 3 1m p e g 系歹l j 随着视频压缩技术的飞速开展，在1 9 9 8 年国际标准化组织终于成立了运动图 像压缩编码组织m p e g 。m p e g 专家组的最重要的工作就是致力于制定运动图像 压缩编码标准。在所有专家的长期不懈的努力下，诞生了一系列针对视频数据的 存储、广播电视和视频流的网络传输等应用场合的视频压缩编码国际标准产生了。 ( 1 ) m p e g 1 标准 m p e g ( m o v i n gp i 嘶鹪e x p e n sg m u p ，活动图像专家组) 的正式名称为 i s 伽e cj t c l s c 2 9 厂w g l l 。m p e g 1 是m p e g 工作组制定的第一个标准( i s o i e c 1 1 1 7 2 ) ，标题是：信息技术一具有1 5 m b s 数据传输率的数字存储媒体运动图像 及其伴音的编码。我国也拥有相应的国家标准g b 厂r 1 7 1 9 1 信息技术具有1 5 m s 数据传输率的数字存储媒体运动图像及其伴音的编码。m p e g 1 标准的全称是 “c 0 d i n go fm o v i n gp i c t u l 懿趾da s s o c i a t e da u d i o f o rd i 百t a ls t o r a g em e d j aa tu pt o a b o u t1 5 i t s ”，m p e g 1 的视频压缩部分也同样是基于块匹配运动补偿的，在 这点上与后面要介绍的h 2 6 l 标准非常近似。但m p e g 1 与h 2 6 l 相比，它还另 外多了两个新的特性：运动补偿中的亚像素( 1 2 像素) 精确度和双向运动补偿。 m p e g 1 作为m p e g 制定的第一个标准，综合考虑了系统、视频、音频三方 面的内容，在多媒体存储领域获得巨大的成功，极大的推动了以v c d 等为代表 的多媒体业务的迅速发展【1 2 】。 ( 2 ) m p e g 2 标准 由于m p e g 1 是m p e g 制定的第一个标准，因此在m p e g 1 中仍然存在着很 多问题没有解决，例如不能满足日益增长的多媒体技术、数字电视技术、多媒体 分辨率和传输率等方面的技术要求的缺陷，而这些问题在m p e g 2 中得到了很好 5 电子科技大学硕士学位论文 的解决。m p e g 2 的出现直接带出了运动图像及其伴音的通用压缩技术标准的发 展。m p e g 2 除了用于d v d 外，还可以为广播、有线电视网、电缆网络以及卫 星直播提供广播级的数字视频，另外现在的v o d 系统和高清晰度电视h d t v 系 统大多采用m p e g 2 标准。 m p e g 2 标准是m p e g 制定的第二个视频压缩标准，它在m p e g 1 的基础上 还做了多方面的改进和扩展：例如针对电视信号的隔行扫描特性，增加了“按场 编码模式，同时在该模式中，支持以场为基础的d c t 和运动补偿；扩大了重要 的参数值，支持更大的画面码率、格式以及运动矢量长度；还另外增加了“可分 级性 ，并且支持解码器从一个编码数据流中得到不同质量等级或者不同时空分辨 率的视频信号；同时，m p e g 2 还定义了档次( p r o f i l e ) 和等级( l e v e l ) ，它们共同构 成了m p e g 2 的特殊子集及其参数范围，其参数范围在比特流的头中具有标识信 号。m p e g 2 的全称是“g 饥嘶cc o d i n go fm o v i l l gp i m 鹏sa n da s s o c i a t e da u d i o ”， 其视频部分采用了同样由i t u t 建议的h 2 6 2 【1 4 】。 ( 3 ) m p e g 4 标准 m p e g 4 【1 5 】第l 版于1 9 9 9 年1 月正式公布，它是一种基于对象的低码率视频 压缩编码标准，并且于1 9 9 9 年1 2 月又公布了第2 版。m p e g 4 标准的全称为 “c o d i n go f m o v i n gp i 咖e s 觚da u d i o ”，它是迄今为止最最为复杂的有关多媒体编 码的国际标准，甚至超过了后面要介绍的h 2 “。在m p e g - 4 中一共包含十个部 分，按照顺序依次为系统、视频、音频、一致性、参考软件模型、传输多媒体集 成框架、m p e g _ 4 工具软件、基于p 架构的m p e g - 4 、参考硬件描述和高级视频 编码。将基于编码的检索与内容的检索结合起来共同考虑，并提出了基于内容的 压缩编码是m p e g 4 的主要贡献。m p e g 一4 这种基于对象编码可以有很多好处， 例如能够将不同对象进行随意拼接、能够降低码率、能够便利的进行虚拟现实和 能够针对对象分配带宽等。然而，作为这种编码方法的基础，对视频对象进行分 割却一直没有效果稳定且普遍适用的方法。正因如此m p e g 的发展也了受到很大 制约，目前在一些计算机动画等人工生成视频对象的领域有比较大的发展【l 6 1 。 1 3 2h 2 6 x 标准 ( 1 ) h 2 6 l 标准 1 9 9 0 年1 2 月，国际电报电话咨询委员会( c c i t t ) 的第1 5 研究组建立的一个 专家组完成和批准了h 2 6 1 【1 7 】标准。但是，此后国际电信联盟i t u 吸收了c c i t t ， 6 第一章绪论 因此，c c l l 可h 2 6 1 也相应地变为r r u h 2 6 1 。 h 2 6 1 的全称是“d e 0c o d e cf o ra u d i o v i s u a ls e 州c e sa tp 奉6 4k b i t s s ”是基于块 匹配运动补偿的视频压缩标准。h 2 6 1 拥有与j p e g 静态图像压缩类似的帧内压缩 编码模式，都是基于8 x 8 像素块的d c t 变换；而h 2 6 1 帧间压缩模式却是简单 的前向单帧( 基于前一帧) 的块匹配运动补偿，它支持的图像格式是c i f ( 3 5 2x 2 8 8 像素点) 和q c ( 1 7 6 x 1 4 4 像素点) 格式，应用对象为电视会议与可视电话。h 2 6 1 作为第一个被广泛应用的视频压缩标准，其在设计上与此后出现的视频压缩标准 比较相对简单了一些，其优点是有利于低成本的大规模集成电路( v l s i ) 实现，有 利于产品的大规模推广。 ( 2 ) h 2 6 3 标准 1 9 9 5 年国际电信联盟通信标准化组( i t u t ) 发布了h 2 6 3 【1 8 】，次年国际电信联 盟通信标准化组完善了在公用电话网上传输甚低码率视频的编解码标准。h 2 6 3 标准的全称为“d e 0c o d i n gf o rl 0 wb i tr a t ec o m m u l l i c a t i o n ，除基本版本外， h 2 6 3 还有增强版本h 2 6 3 + 和h 2 6 3 + + 。与h 2 6 1 相比，h 2 6 3 除了新加设了带 运动矢量预测的亚像素( 1 2 像素精确度) 运动估计功能，而且又增加了4 个与帧间 编码相关的可选特性。 在制定h 2 6 3 时远远没有想到后来所提出的技术与最终达到的效果能如此 好，大大超过了制定时对h 2 6 3 的期望，也正因为如此h 2 6 3 的应用领域被扩展 了很多，当然h 2 6 3 对此后视频压缩标准的影响也是非常巨大的。 ( 3 ) h 2 6 4 a v c 标准 2 0 0 3 年发布的m p e g 4 标准的第十部分高级视频编码( a d v a n c e d d e 0 c o d i n g a v c ) 也就是i t u t 的最新建议h 2 6 4 a v c 【1 9 】， 全称i t u t r e c o i l l 【i l e l l d a t i o nh 2 6 4a i l di s o i e cm p e g 4 ( p a n1o ) a d v a l l c e d d e 0c o d i n g 。 h 2 6 4 a v c 在视频编码中又增加了许多项新技术，这也使得h 2 6 4 a v c 标准编码 效率提高很多：在相同信噪比条件下，h 2 6 4 a v c 的平均码率仅为h 2 6 3 + 的5 0 。 另外，与现有标准相比h 2 6 缈a v c 所新采用的视频编码技术主要有以下几种【2 0 】： 更精确的1 4 像素精确度的运动补偿 基于多个参考帧的运动补偿 基于多种块类型的运动补偿 取消参考帧的选用限制 帧内编码的空间预测 小块整数变换 7 电子科技大学硕士学位论文 加权预测 基于上下文的熵编码 闭环去块效应滤波器。 通过以上分析我们能够发现h 2 6 4 a v c 的出色表现绝不是由于某一项新技 术的引入，而是由上述多个视频编码技术共同作用的结果。 1 4 本文的主要成果及章节安排 1 4 1 本文的主要成果 本文在对运动估计和粒子群优化算法( p s o ) 进行深入分析的基础上，创造 性的将p s o 算法应用于运动估计领域，并结合运动矢量分布特性对标准p s o 算 法进行了改进，使得改进后的p s o 算法具有更快的搜索速度和更佳的搜索性能； 在对j m 平台进行充分研究后，成功将p s 0 算法程序嵌入j m 平台，从理论及实 验上验证了p s o 算法应用于运动估计领域的可行性和高效性，进而在运动估计领 域提出了新的理论研究对象。 概括的说，本文的工作和主要创新点为： 1 分析了运动估计中运动矢量的分布特性，对已有运动估计算法进行了科学合 理的归类分析，并通过实验验证了各个算法的效果； 2 在对优化算法如遗传算法( g a ) 、粒子群算法( p s o ) 和神经网络算法( b p n n ) 进行研究后，发现p s 0 算法是这些算法中思想最简单、最易实现，且在运动 估计问题上效果最佳的，在理论分析后成功的将p s o 算法应用于运动估计领 域，并在j m 平台上对p s o 算法的有效性进行了验证； 3 在将标准p s o 算法成功应用于运动估计中后，又针对标准p s o 算法提出了三 点改进：1 采用提前终止技术，加强了对静止块的判断，减少了搜索点数；2 在p s o 算法中结合运动矢量分布特性，采用改进的初始种群技术，有效增强 了对初始搜索点位置的判断，大大提高了搜索效果；3 针对运动剧烈的序列容 易陷入局部最优问题，采用部分粒子变异技术，进一步降低p s o 算法陷入局 部最优的概率。 4 最后，本文通过实验证明了改进的p s o 算法搜索性能优于标准p s o 算法，更 优于g a 算法。与g a 相比，改进后的p s o 算法在搜索点数上不到g a 算法 的5 0 ，而且搜索效果也明显优于g a 算法，具有很好的应用价值和理论研 8 第一章绪论 究价值。 1 4 2 本文章节安排 基于以上工作完成工作，本文章节结构安排如下： 第一章介绍了本课题的研究背景与意义，阐述了视频压缩技术的基本原理以 及经典视频图像压缩方法，并对视频压缩标准做了简单回顾，总结了本文的主要 工作。 第二章介绍了块匹配运动估计的基本概念，重点介绍了块匹配运动估计的基 本原理及技术指标，并对运动矢量分布情况进行了详细的分析与研究，从而得到 了运动矢量中心偏置和时空相关的重要特性。 第三章对已有传统运动估计算法进行了分类，并对每种算法展开了详细分析， 特别是对启发式搜索算法和最优化搜索算法。 第四章详细介绍了标准p s 0 算法的基本原理，并对标准p s o 算法中出现的 参数通过实验进行定量分析，以使p s o 算法能够更好的应用于运动估计中。在第 四章的最后，通过实验证明对标准p s o 算法无论在搜索点数还是搜索性能上都比 同为优化算法的g a 算法效果更佳，且对于运动剧烈的序列p s o 搜索效果只比全 搜索( f s ) 效果差，但搜索点数远少于全搜索。 第五章对标准p s o 算法进行了进一步分析，并对标准p s o 中存在的不足提 出了的改进思想，得出了基于粒子群的运动估计优化算法，并通过实验证明本文 提出的算法搜索效果非常理想，对绝大多数序列搜索效果只比全搜索差，且搜索 点数也较遗传算法和全搜索下降很多，从而使得改进的p s o 算法在应用于运动估 计时具有更佳的搜索性能。 第六章对本文工作做全面总结，并对下一步工作进行了展望。 9 电子科技大学硕士学位论文 第二章块匹配运动估计原理 通过上一章的分析我们知道因为视频序列图像在时间上具有较强的相关性， 而运动估计( m e ) 和运动补偿( m c ) 技术能够显著减少时间相关性，所以几乎所有视 频压缩编码方案中都会采用该技术。运动估计的作用是估计物体的位移，得到其 运动矢量；而运动补偿则是根据之前已经得到的运动矢量再对前一帧中由于运动 所产生的位移进行修正，进而尽可能计算出接近原始帧的预测帧。因此我们可以 发现，如果运动估计算法越优秀，计算出的运动矢量就越准确，那么运动补偿的 性能就越好，从而使预测误差越小，这样编码后所需传输的信息量也就能够大大 减少了，整个编码系统的码率压缩效果必然能够得到非常大的提升。基于以上原 因，运动估计( m e ) 和补偿技术( m c ) 己经成为视频序列图像编码系统中减少时间相 关性、提升视频图像压缩比的一项关键技术。m p e g 和h 2 6 x 等标准均采用基于 块匹配的运动估计与运动补偿的帧间压缩编码方案，实际证明其压缩效果与基于 帧内压缩的标准( 如j p e g ) 相比要好的多。 在视频压缩编码中，无论采用哪种搜索算法运动估计都是最费时间的步骤， 比如在h 2 6 x 的编码过程中，即使在采用经典的四步快速搜索算法的情况下，运 动估计还是会占用所有视频编码过程中的绝大部分计算量。因此，运动估计是视 频压缩技术发展的瓶颈。 基于以上原因，快速的、高效的运动估计算法一直是视频压缩领域的研究热 点。 2 。1 运动估计简介 因为在视频序列中相邻帧之间存在着很大的时间冗余，所以如果能够尽可能 的消除这种时间冗余，那么就可以大大提高视频压缩编码技术的压缩效率 2 1 1 。而 基于块匹配的运动估计( m o t i o ne s t i m a t i o n ，m e ) 因其算法简单且易于实现等优势 在这方面得到了迅速推广。运动估计的原理为将视频序列的每一帧图像分为若干 个m x n 的宏块，再按照一定的匹配规则对当前帧的所有宏块在其前后帧的某给 定搜索范围内搜索与当前宏块最为匹配的最佳匹配块，并通过比较最佳匹配块的 1 0 第二章块匹配运动估计原理 问的位置偏移。这种位置偏移是以运动矢量来描述的，一个运动矢量代表水平和 垂直两个方向上的位移。 2 2 块匹配运动估计的基本原理 运动估计可以看作是对相邻图像帧时域相关性的检测，通过对相邻图像帧之 间相似部分的搜寻来获得图像中景物对象的运动信息。运动估计和补偿的基本过 程是通过一定的方法在参考帧图像中搜索当前帧图像的运动信息，再根据这些运 动信息在参考图像上进行相应的运动补偿操作，得到一个当前帧的重构图像。由 于运动估计时得到了当前图像与参考图像的相关信息，这个重构图像与当前图像 的差值往往比直接用参考图像和当前图像作差而得到的比特数要少得多，因此， 运动估计与补偿技术能有效减少相邻帧之间的数据冗余，从而获得更高的压缩比， 降低视频压缩编码后的码率。 运动估计的基本思想是尽可能准确地获得序列图像帧间的运动位移，即运动 矢量。因为运动估计越准确，预测补偿的图像质量越高，补偿的残差就越小，补 偿编码所需位数越少，需要传输的比特率就越小。利用得到的运动矢量在帧间进 行运动补偿。补偿残差经过变换、量化、编码后与运动矢量一起经过熵编码，然 后以比特流形式发送出去【引。 运动估计算法中，块匹配算法因具有简单、实用的特点而得到广泛应用。如 不做特别说明，下面的运动估计都是指块匹配运动估计。块匹配运动估计将当前 帧分成大小为n 删的互不重叠的像素块，每个像素块在参考帧中对应一个 ( 一w ，w 1 ) 大小的搜索窗( w 为最大位移量) ，如图2 1 所示，其目标是在搜索窗 中寻求最匹配的帧间图像块。 图2 1 块匹配搜索窗 搜索窗越大，搜索的精度也就越高。因此，搜索的区域最好是整帧图像。但 电子科技人学硕十学位论文 从实用和计算的角度来考虑，搜索通常被限定在一定大小的窗口内；同样的道理， 参考帧数目也有一定的限制，比如h 2 6 4 参考帧就最多支持5 帧：此外，搜索精 度还和搜索像素精度有关，一般来说，半像素、1 4 像素等分数精度搜索算法与 整像素精度搜索相比较，估计精度有较大的提高，特别是对于低清晰度视频。但 是，应用分数像素步长，搜索算法的复杂性会大大增加。 2 3 块匹配运动估计的技术指标 块匹配运动估计可以从以下三个方面进行研究：块的模式选择、块匹配准则、 算法评定指标。 2 3 1 块的模式选择 块匹配方法隐含着如下假设：同一块内的像素的运动是一致的。显然这个假 设具有一定的片面性，但选择合适的块形状与大小可在一定的程度上消除这种片 面性。一般来说，块形状选用正方形是比较自然的选择，这样既便于图像的划分， 又有利于块匹配准则函数的计算。 关于块的大小，显然块越小，得到的残差块越小，但这会导致块内进入较多 的运动矢量，可能降低编码的效率。作为折衷，通常选择1 6 x 1 6 的宏块作为单位。 2 3 2 常见的块匹配准则 块匹配估计准则是判断块相似程度的依据，因此匹配准则的好坏直接影响了 运动估计的精度；另一方面，匹配运算复杂度、数据读取复杂度和内存管理复杂 度在很大程度上取决于所采用的块匹配准则。因此，提高运动估计算法的速度可 以有两种途径：一种是减少搜索匹配的点数，另外一种是降低块匹配准则来减少 复杂度。常用的块匹配准则有以下几种： 1 ) 平均绝对误差函数( m e a no f a b s o l u t ee 玎0 r ，m a e ) 刎( f ，) = 去l 石( m ，疗) 一六一。( 朋+ f ，以+ 州 ( 2 - 1 ) m 。ln 2 l ( 圪，0 ) = 嘞心盹，) ( 2 - 2 ) 其中，五表示第k 帧图像在像素点( m ，n ) 处的亮度值，运动估计的块的大小为 n x n 像素点，块的运动矢量为( 圪，功，d 表示搜索区域。以下同此。 1 2 第一二章块匹配运动估计原理 2 ) 互相关函数( c r o s sc o r r e l a t i o nf u n c t i o n ，c c f ) ( 肌，一) 石一( 所+ f ，疗+ ) 善善五川卜荟善五脚“一+ 力 ln nlnn ( ，1 ) = 田8 苎c f ( f ，- ，) ，e d 3 ) 均方误差函数( m e a no f s q u a r ee 舯r ，m s e ) 朋陋( f ，) = 吉l 厶( 肌，疗) 一五一。( 朋+ f ，厅+ 州2 l_ j 册= ln = i ( 1 ，0 ) 2 嚣1 2 稻e ( ，力 4 ) 最大误差最小函数( m m e ) ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) f 砸( f ，) = 。翌a x i 石【册，一) 一厶一。( 册+ f ，开+ _ ，) l ( 2 - 7 ) 一s 用月s 1 ( 匕，_ ) = 嘞脚( f ，_ ，) ( 2 - 8 ) 5 ) 绝对误差和( s u mo f a b s 0 1 u t ed i c e ，量d ) 黝烈f ，) = i 石( 朋，n ) 一五一。( 册+ f ，疗+ 州 ( 2 - 9 ) 肿= 1 月= i ( _ ，0 ) = 嚣1 2 5 h d ( f ，_ ，) ( 2 - 1 0 ) 通过对上述五种准则函数的每次块匹配计算复杂度的比较可以看出，m m e 匹配函数过于简单，没有充分利用匹配块所包含的特征信息，因此运动估计的精 度不高；c c f 匹配函数的计算过于复杂，算法耗时太多。试验结果表明，m s e 匹配函数运动估计的精度最高，匹配效果接近于人眼的觉察力；与m s e 相比较， m a e 匹配函数的计算量相对较小，效果接近于m s e ，试验表明，m a e 准则函数 具有很好的跟踪能力；s a d 准则函数是m a e 准则的简化，舍弃了求平均值过程 中的除法运算，运算量最小，且便于硬件实现，所以应用较多。 2 3 3 算法评定指标 运动估计算法的设计目的是尽可能准确地为当前帧建立一个模型( 因为这样 可能获得更好的压缩性能) ，同时在可以接受的计算复杂度内。通过观察匹配的效 果和搜索的时间复杂度可以评判一个运动估计算法的好坏，具体说来，匹配效果 可通过人眼主观和一些客观的指标来评价重构图像的质量。人眼对图像质量的评 1 3 电子科技人学硕十学位论文 价是许多因素的一个交互过程，包括人类视觉系统( h v s ) ，眼睛和大脑系统等。 人类视觉感知受空| 、日j 保真度和时问保真度的影响，同时还受到其它凶素的影响， 如观察环境、观察者的精神状态等。这些都具有较大的随意性，不易进行准确的 和定量的比较。 鉴于以上视频效果主观判断的局限性，视频压缩和视频处理的开发者越来越 倾向于客观的判断，应用最广泛的就是峰值信噪比p s n r ( p e a l ( s i 舯a lt 0n o i s e r a t i o ) 和平均m s e 。m s e 在前面已经有介绍，p s n r 的计算公式如下： 删- 1 0 l o g i o l 篇l ( 2 - 1 1 ) p s n r 的计算非常简单和快捷，因此成为一种应用广泛的客观图像质量评定 方法。通常地，p s n r 值高表示图像具有比较高的质量，p s n r 值低则表示图像具 有比较低的质量。因此从p s n r 值可以很好的反应图像的质量。 时间复杂度可通过搜索点数和搜索时间进行比较。由于搜索时间受到运行平