（计算机应用技术专业论文）基于mpeg4的运动估计和码率控制技术的研究.pdf

中文摘要 摘要 有效的视频压缩编码技术对视频处理中大量数据的存储和传输来说是至关 重要的。新一代动态视频压缩标准m p e g 一4 的推出，使得针对视频压缩编码的研 究进入了一个新的层次。 本论文研究了m p e g 一4 标准，在实现m p e g 一4 视频编解码器软件原型的基础上， 重点研究了编码过程中的两项关键技术：运动估计和码率控制。 运动估计是编码过程中最重要，耗时最长的部分。本论文对运动估计算法进 行分类，着重介绍了启发式搜索法和基于时空相关性的搜索法两大类，在对 h e x b s 和m v f a s t 算法分析的基础上，进行了改进。 码率控制技术可以保证视频数据在通道内传输时充分利用带宽。本论文深入 研究了码率控制技术，在对经典码率控制算法，尤其是m p e g - 4 码率控制算法分 析的基础上，针对其存在的问题和低码率应用环境的需求进行了改进，取得了良 好的效果。 关键词：m p e g - 4 ，运动估计，码率控制，视频编码 英文摘要 a b s t r a c t e f f i c i e n tv i d e o c o m p r e s s i o nt e c h n i q u e s 8 x e v e r yi m p o r t a n tt o t h es a v ea n d t r a n s m i s s i o no ft h ei n c r e a s i n gd a t ai nv i d e op r o c e s s e s r e c e n ty e a r s ，m p e g - 4 ，t h e l a s t e s tv i d e oc o m p r e s s i o ns t a n d a r dh a sl e a dt h er e s e a r c hi nr e l a t e df i e l d s t h i sp a p e rr e s e a r c ht h em p e g - 4s t a n d a r da n dr e a l i z et h es o f t w a r ep r o t o t y p eo f t h em p e g - 4v i d e oc o d e c t h ep a p e re m p h a s i z et w ok e yt e c h n i q u e si nm p e g 一4 e n c o d e r ：m o t i o ne s t i m a t i o na n db i tr a t ec o n t r 0 1 m o t i o ne s t i m a t i o nt a k e st h el a r g e s tt i m ei na l lp a r t so fm p e g - 4e n c o d e r t h i s p a p e rc a t e g o r i z et h em o t i o ne s t i m a t i o na l g o r i t h m s ，m a i n l y r e s e a r c ht h eh e u r i s t i ca n d t i m e s p a c e r e l a t e ds e a r c h ，a n di m p r o v e dt w oa l g o r i t h m s b i tr a t ec o n t r o lc a ng u a r a n t e eu s i n gt h eb a n d w i d t hf u l l yi nt r a n s m i s s i o no ft h e v i d e od a t a t h i sp a p e rr e s e a r c ht h et e c h n i q u eo fb i tr a t ec o n t r o l ，b a s e do nt h e a n a l y s i so f m p e g - 4 a l g o r i t h m ，i m p r o v e ds o m ea g a i n s ti t se x i s t i n gp r o b l c m sa n dl o w b i tr a t ea p p l i c a t i o ne n v i r o n m e n t t h et e s tr e s u l ti ss a t i s f i e d k e y w o r d s ：m p e g 一4 ，m o t i o ne s t i m a t i o n ，b i tr a t ec o n t r o l ，v i d e oc o d i n g 1 j 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：丕：i i 。曼日期：彬年f 月f 踟 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丕丛) i 曼 导师签 日期： 第一章引言 1 1 选题背景 第一章引言 随着现代电子与计算机技术的飞速发展，人们与数字图像接触的机会越来越 多，数字图像取代模拟图像已经成为一种趋势。作为有效传输和存储数字图像的 基本技术数字图像压缩编码技术得到了迅速发展，成为图像处理领域必不可 少的分支学科，并占有越来越重要的地位。上个世纪八十年代以来，随着传真技 术、电视会议、可视电话、高清晰度电视、图像检索、可视图文、多媒体及计算 机网络等技术的兴起与发展，图像业务的数据量越来越大，这就对图像压缩编码 提出了更高的要求，同时也促进了图像编码技术的发展。随着一系列国际标准的 制订和专用数字处理芯片的推出，高质量的数字编码方法也从理论研究走向实用 化。 未经压缩的数字化后的图像拥有巨大的数据量。一幅5 1 2 x 5 1 2 未经压缩的 真彩图像( 2 4 b i t s p i x e l ) ，其原始数据量达6 3 m b i t ，一张6 5 0 m 的c d - r o m 盘只 能存放8 0 0 多幅。如果是序列图像，每秒3 0 帧，只能存放2 8 秒钟的图像数据， 其数据传送率约为1 5 7 m b i t s 。这样大的数据量，无论存储还是传输都是极其困 难的。又比如按照h 2 6 3 标准的最低要求：q c i f 图像、8 帧秒、彩色格式为4 ：1 ：l ， 则该图像序列数据率为2 3 m 比特秒，不压缩的话一个e l ( 2 0 4 8 m 比特秒) 信道 也传输不了，更不用说用模拟电话线，这类应用不仅需要压缩，还需要实时地进 行压缩。因此，图像压缩编码是十分必要的。 1 2 论文工作 自从1 9 9 9 年i s o 推出新一代动态图像压缩标准m p e g 一4 以来，m p e g - 4 技术 迅速成为研究热点，众多的学者和厂商投入到相关研究中。m p e g 一4 技术被认为 会在相当长的一段时间内成为动态图像压缩方向的主流技术。 本论文我们着重关心以下方面的应用： 1 随着m p e g 一4 技术的兴起以及移动设备的日益普及，嵌入式m p e g 一4 视频 通信系统的研究成为热点。在众多嵌入式系统方案中，嵌入式芯片的处理速度并 不能满足m p e g 一4 算法的实时性要求，因此有必要对现有m p e g 一4 算法进行改进， 以提高编码速度。 2 ，a l p e g 一4 编码中耗时最大的是运动估计m e ( m o t i o ne s t i m a t i o n ) 部分，大 约占总耗时的6 0 8 0 ；同时，运动估计寻找到的运动矢量是否精确，对恢 第一章引言 复图像的质量非常关键。关于m e 的研究时来已久，近年来又出现了一些新的思 想，通过对算法的研究进而改进，能够提高整个编码过程的速度和质量。 3 在视频图像信息远程实时传输系统中，利用码率控制技术可以使图像在 通道内传输时充分利用带宽。 根据阱上背景所述，本论文的工作主要包括以下几方面： 1 研究m p e g - 4 标准，针对实时极低比特率应用的m p e g - 4s p 方案进行了编 解码器的软件原型实现，同时也是本论文算法分析的基础平台。 2 对影响m p e g - 4 编解码速度的关键技术运动估计技术进行研究。首先对 m e 算法进行分类，然后着重介绍了启发式搜索法和基于时空相关性的搜 索法，在对h e x b s 和m v f a s t 算法分析的基础上，进行了改进，通过实验 与现有算法进行了比较。 3 对码率控制技术进行了研究，在着重分析d p e g 一4 码率控制算法的基础 上，针对其存在的问题和实际的应用需求进行了改进，并对改进算法的 性能进行了评估。 1 3 论文组织结构 第二章简要介绍了图像压缩基本思想和m p e g 系列运动图像压缩标准，并对 当前视频通信系统的发展和应用前景进行了展望。 第三章研究了m p e g 一4 编码过程中的运动估计技术，对现有运动估计算法进 行了分类，着重介绍了启发式搜索法和基于时空相关性的搜索法两大类。 第四章研究了码率控制技术，对经典码率控制算法，尤其是m p e g 一4 码率控 制算法进行了分析。 第五章简要介绍了新一代动态图像压缩标准m p e g 一4 ，详细分析了基于 m p e g - 4s p 视频编解码器的结构和功能，完成了编解码器软件原型的实现。 第六章是本论文的重点工作部分。在运动估计算法h e x b s 和m v f a s t 的基础 上分别进行了改进；针对低码率应用环境，对m p e g 一4 码率控制算法也进行了改 进，并通过实验进行了性能评估。 第七章是论文的结论。主要总结了研究成果，指出论文工作中存在的不足， 并对今后的工作提出了建议。 第二章图像压缩 2 ，1 图像压缩简介 第二章图像压缩 压缩机制通常可以分成两种有损压缩和无损压缩。在无损压缩中，我们 关心的是精确重建没有信息丢失的数据，无损压缩通常被用于文本文件的压缩 中。 对于有损压缩，我们允许压缩后产生质量上的误差。有损压缩机制的优点是 可以得到比无损压缩高得多的压缩比，但是它只能用于可以用近似的数据代替原 始数据，而这种相似数据又是容易被压缩的情况。例如一幅和原图像在视觉上没 有区别的图像可以看作是原图像的近似。 任何压缩机制的根本思想都是除去数据中存在的相关性。所谓相关性，就是 能够根据给出的一部分数据来判断其相邻的数据。一般的图像编码算法是在对数 字图像进行大量统计分析的基础上，充分利用图像自身相关性强的特点，减少图 像信息的冗余度，降低数据率。实际中存在很多种数据相关性，常见的三种是： ( 1 ) 空间相关性。可以根据图像中某一点的像素值推断其相邻点的像素值。 ( 2 ) 频域相关性。一个信号的傅立叶变换通常是光滑的，这意味着可以根据 某一部分的频率来推断其相邻部分的频率。 ( 3 ) 时间相关性。在数字视频中，时间上相邻两帧图像的大部分像素的值变 化很小。 有损压缩的标准过程是变换编码。基本思想是用一个和原来不同的数学基来 表示数据。在这种新的表示下，数据的相关性能够显露出来或被拆开，新基下大 部分的系数都接近零，可以忽略，于是可以将余下的信息存储在一个较小的数据 包中。压缩就是通过数据变换，把域值以下的系数置零，对非零的数据进行无损 的编码来实现的。 2 2 运动图像编码标准简介 数字视频技术广泛应用于通信、计算机、广播电视等领域，带来了电视会议、 可视电话、数字电视及媒体存储等一系列应用，促使了许多视频编码标准的产生。 i t u t 与i s o i e c 是制定视频编码标准的两大组织，i t u t 制定的标准有h 2 6 1 、 h 2 6 3 、h 2 6 4 等，主要应用于实时视频通信领域；m p e 6 系列标准是i s o i e c 制 定的，主要应用于视频存储、广播电视、因特网或无线网上的流媒体等。两个组 第二章图像压缩 织也共同制定了一些标准，h 2 6 2 标准等同于m p e g 一2 的视频编码标准，最新的 h 2 6 4 标准则被纳入m p e g - 4 的第1 0 部分。下面我们对m p e g 系列标准作一些简 单的介绍。 ( 1 ) m p e g l m p e g l 主要针对速率大约为1 5 m b s 的视频信号的压缩。为了提高压缩比， 它同时采用了帧内图像数据压缩和帧间图像数据压缩技术。帧内压缩算法与 j p e g 压缩算法大致相同，都是采用基于d c r 的变换编码技术，用以减少空域冗 余信息；帧间压缩主要采用预测法和差补法，预测误差再通过d c t 变换编码处理， 进一步压缩，帧间压缩减少了时域和空域的冗余信息。 ( 2 ) m p e g - 2 由于m p e g 一1 不能满足日益增长的多媒体技术、数字电视技术对分辨率和传 输率等的要求，因此m p e g 推出了第二代运动图像压缩标准m p e g - 2 。m p e g 一2 视频 标准与m p e g 一1 视频向前兼容并与e d t v 、h d t v 、s d t v 格式向上或向下兼容。它支 持固定比特率传送、可变比特率传送、随机访问、分级编码等功能。m p e g 一2 主 要特点如下： 提供了框架( p r o f i l e ) 和级( l e v e l ) 。框架是m p e g 一2 标准中定义的语法的 子集；级是一个特定框架中参数所取值的集台。一个框架可以包含一个或多个级 别。框架和级的定义，为不同应用领域之间的数据交换提供了方便和可行性。 视频压缩编码的视频数据是分层的比特流结构，第一层为基本层，基本 层可以被独立解码，其它层称为增强层，增强层的解码依赖于基本层。 ( 3 ) m p e g 一4 1 9 9 9 年，m p e g 推出了新一代运动图像压缩标准m p e g 一4 。m p e g - 4 的目标定义 为：支持多种多媒体应用，可根据应用要求：不同来现场配置解码器。m p e g 一4 的 编码系统是开放的，可以随时加入新的有效算法模块，这对于以前基于专用硬件 的压缩编码方法是不可想象的。与前面的m p e g 标准相比，m p e g 一4 在思想上有两 个主要特点： m p e g 4 的编码是基于对象的，这样就便于操纵和控制对象。由于传输带 宽的限制，必须对压缩比特率进行控制，这将直接影响图像的质量。以往标准中， 编码是基于每一帧的，因此在比特率较低时，整帧图像的质量都受到影响，没有 灵活性可言。而在m p e g 一4 中对比特率的控制是基于对象的，在低带宽时，可以 对用户感兴趣的对象多分配一些比特，而对不感兴趣的对象少分配一些比特，这 样图像的主观质量就可以得到有效保证。 第二章图像压缩 m p e g 一4 在扩展性上具有很好的灵活性，可进行时域和空域的扩展。这在 m p e g - 2 中已经有所体现，但并不是很突出。在m p e g 一4 中，可根据现场带宽和误 码率的客观条件，在时域和空域进行扩展。，时域扩展是根据不同的带宽在增强层 中进行帧率的调整，以达到充分利用带宽的目的；空域扩展是指对基本层中的图 像进行采样插值，增加或减少空间分辨率。 上面两点思想的改变使得在m p e g - 4 编码器的具体实现过程中，与前面的标 准有了很大不同。例如，在m p e g 一4 中把前景对象和背景对象分别进行编码。由 于m p e g 一4 算法的开放性，人们可以针对不同的应用进行算法的改进，使得编码 的速度和质量达到一个最佳的结合点。 ( 4 ) m p e g 一7 随着越来越多的声像信息以数字形式存储和传输，人们可以利用的信息大大 增加。但随之而来的问题是：随着网络上信息爆炸性的增长，如何从海量的信息 中找到我们感兴趣的信息却越来越难。传统的基于关键字和文件名的检索方法显 然不适合声像数据，因此近年来一个研究热点是声像数据的基于内容的检索。 m p e g 注意到这方面的需求，开始制定了专门支持多媒体信息基于内容检索的编 码方案m p e g 一7 。m p e 6 7 将为各种类型的多媒体信息规定种标准化的描述，这 种描述与多媒体信息的内容本身一起，支持用户对其感兴趣的各种资料的快速、 有效的检索。这种标准化的描述可以加到任何类型的多媒体资料上，不管多媒体 资料的表现格式和压缩形式如何，理论上加了此种标准化描述的多媒体数据就可 以被索引和检索。 ( 5 ) m p e g 一2 1 m p e g 一2 l 是1 9 9 9 年1 0 月提出的，其目标是定义一个交互式多媒体框架，跨 越大范围内不同的网络和设备，使用户能够透明而广泛地使用多媒体资源。为此， 这就需要了解框架中各成分的关系并明确其相互之间的间隙，然后形成综合标准 以获得协调的多媒体内容管理技术，并进一步发展新规范，用以支持以下功能： 通过网络或设备，存取、使用并交互多媒体对象；实现多种业务模型，包括在价 值链中对版权和支付交易的自动管理：对内容使用者隐私的尊重。 2 3 视频通信系统的发展 第二代移动通信技术正进行得如火如茶，第三代移动通信技术3 g 又在推广 之中，通信技术使人们的生活发生了翻天覆地的变化。如今人们可以随时随地进 行语音通信。但是研究表明，视频因素在人的交流中占据了一半以上，因此人们 在想办法提高语音通信技术的同时，也在不断开发视频通信技术。 第二章图像压缩 2 0 年前，世界首台商用电视会议系统的问世，拉开了视频通信系统飞速发 展的序幕。视频传输技术和压缩技术的不断进步，使更多更先进的视频通信系统 在市场上出现。例如，美国m a c r o 公司推出了无线相机，利用无线局域网技术实 现图像数据在有限范围内的无线传输，可方便地应用于一定范围的监控；日本众 多手机厂商推出的带摄像头的手机，可以实现点到点的小分辨率图片的传输等。 从手机、掌上电脑等便携式产品的日益普及可以预测视频通信系统的发展方 向：如果能够将一种高压缩率的视频压缩算法集成到芯片上，在视频数据采集的 同时进行压缩实现实时通信，就可以做出一种嵌入式的、便携一体化的、实时压 缩视频通信系统。这种系统有着广阔的应用前景： 首先是在新闻报道上。每次遇到重大会议或者比赛，总会有个新闻中心， 记者必须将拍摄到的视频数据送到新闻中心才能发送回总部。这对争分夺秒的新 闻业来说是件很痛苦的事情。如果有了这种便携一体化的、实时压缩无线传输 的视频通信系统就可以随时随地的将资料在第一时间发送出去，不但提高新闻报 道的速度，也省去了来回奔波的麻烦。 其次，在平流层通信或者卫星通信中也可以将拍摄到的视频或者图像实时地 压缩传输至d 接收端进行解压缩并分析。 如果能够降低系统成本，完全可以在家庭中进行普及。试想一下，如果你和 朋友出去郊游，你就可以用一台数码摄像机在拍摄下欢乐场面的同时，将视频数 据实时传输到别的地方，让你的亲朋好友一块分享你的快乐。 另外，在视频监控、手机通信等领域也有着巨大的应用前景。 正因为以上市场需求的存在，众多厂商都已经把嵌入式视频通信系统的开发 作为发展重点。 2 4 小结 本章简要介绍了图像压缩基本思想和m p e g 系列运动图像压缩标准，并对当 前视频通信系统的发展和应用前景进行了展望。 第三章运动估计技术 第三章运动估计技术 运动估计是运动图像压缩的核心组成部分，预测估计的效率高低将对压缩 全过程产生重大影响。因此，我们首先对运动估计技术进行分析。 3 1 研究意义 完整的m p e g 一4 编码过程主要包括运动估计、d c t 变换和量化、运动补偿、 反d c t 变换和反量化、系数的变长编码以及帧重构等几个主要部分。每一个部 分所占用的时间是不一样的，表3 - 1 显示了以上各部分在整个编码过程中所占 时间的大致比例( 数据基于标准测试序列c o a s t g u a r d , c i f 格式，每秒2 5 帧进 行测试得到) 。 表3 - 1m p e g 一4 编码器各部分所占时间比例 所占编码 模块 时闺比铡 m o r o ne s t i m a b o n ( m e )6 15 d c ta n d0 u a n t 旺a t i o n2 0 m o t i o nc o m p e n sa f j d n ( m c )6 4 j d c ta n d l 03 0 v a r i a b l el e n g 廿1e n c o d i n g ( v l e )7 1 v o pr e c o n s t r u c 廿o n2 0 t 0 t a i1 0 0 由表3 一l 可知，运动估计在整个编码过程中消耗时间最多。因此，运动估 计速度的提高是整个编码速度提高的关键。此外，由运动补偿原理可知，所寻 找的运动矢量是否精确，将对恢复图像的质量产生决定性影响。 3 ，2 运动补偿原理 在m p e g 系列标准中，引入了运动补偿技术来提高压缩效率。运动补偿实际 上是对运动图像进行压缩时采用的一种帧间编码技术。由于运动的连续性，图 像序列中的第n 帧图像可以看作是前面预测帧第n 帧( 例如第n 一1 帧) 图像经 过一定平移得到的。因此在实际编码中，为了节省编码比特，并不传输第n 帧 的全部数据，而是利用运动估计技术计算出第n 帧与预测帧y 。的差值。如果 运动估计比较有效，则中的概率分布基本上在零附近，从而导致的能量很 小，相应的编码传输所需要的比特数也很少。在解码端，根据预测帧n 和差 第三章运动估计技术 值，就可以基本恢复出初始的第n 帧图像。这就是运动补偿技术能够去除信 源中时间冗余度的本质所在。 运动估计算法是运动补偿过程中的核一c - 算法。它通常被归纳为两大类，一 类是像素递归算法p r a ( p j x e lr e c u r s i v ea 1 9 0 r i t h m ) ；另一类是块匹配算法 b m a ( b 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 算法本身也拥有较好的性能，因此m p e g 推荐b m a 算法。 b m a 算法是一种非常直观的运动估计算法，它是基于平移运动的机理来进 行运动估计的。在平移运动中，物体上的每一点均有相同的速度大小和方向， 在物体运动的轨迹上，当前时刻所处的位置是由前一时刻位置偏移得到的。将 b m a 算法运用到上面所述的运动补偿原理中：当前帧图像被分成二维8 8 或者 1 6 1 6 像素的子块，假定每个子块内的像素都做相等的平移运动，在其相邻帧 中相对应的几何位置周围的一定范围内，通过某种匹配准测，寻找这些像素子 块的最佳匹配块。一旦找到，便将最佳匹配块与当前块的相对位移( d x ，d y ) ， 即通常所说的运动矢量( m o t i o nv e c t o r ) 送出，并传输到接收端。图3 - 1 显示了 采用b m a 算法求解运动矢量的方法。 图3 - l 求解运动矢量示意图 从b m a 算法运用于运动补偿的过程可以看到，有两个问题需要解决：匹配 准则和运动估计方式。 运动估计算法中常用的匹配准则有三种：平均绝对误差m a d ( m e a na b s o l u t e 第三幸运动估计技术 d if f e r e n c e ) 、均方误差m s e ( m e a ns q u a r ee r r o r ) 和归一化互相关函数n c c f 。 在一些应用中也使用子采样匹配准则。 ( 1 ) m a d 的表达式为： 删。( “) = 嘉姜善| 正( m ，”) 一五m + 咖+ 川 式( 3 一1 ) 其中( f ，) 为位移量，五和工一，分别为当前帧和上一帧的灰度值，m x n 为 宏块的大小，若在某一点( 乇，五) 处m a d ( i o ，j o ) 达到最小，则该点为要找的最优匹 配点。 ( 2 ) m s e 的表达式为： m s e ( ) = 赤薹善m 一 m + 咖r + 川2 式( 3 2 ) m s e 值最小的为最优匹配点。 ( 3 ) n c c f 的表达式为： 五( m ，功工。( m + i ，n + 力 n c c f ( i ，j ) = 面耳卫生垂砑育一 式( 3 3 ) 【工2 ( m ，”) 】i ，2 【甜沏+ ”+ j ) p n c c f 值最大的为最优匹配点。 ( 4 ) 子采样匹配准则的表达式为： s a d ( i , j ) = ( m ，疗) 一五一。( m + ”+ ，) f p ( m ，力 式( 3 4 ) 舯叫刚，= 托”篙 子采样匹配准则大大降低了计算复杂度，运算量只有原来的1 4 ，在一些 多候选点算法中，可以采用子采样匹配准则。 匹配准则对匹配的精度影响不是很大。其中m a d 因便于计算( 不含乘除法) 和易于硬件实现，而获得广泛应用。 3 。3 运动估计算法分析 在众多运动估计算法中，计算量最大、精度最高的是全搜索算法。它是在 搜索窗s w ( s e a r c hw i n d o w ) 中所有可能的偏移位置上对当前块均进行一次匹配 9 - 第三章运动估计技术 运算，最后对所有结果进行比较，从而得到最佳匹配及运动矢量。单从匹配角 度看，全搜索无疑是最好的方法，但由于其巨大的运算量，很少被采用。近2 0 年来，运动估计技术会聚了很多研究人员的焦点，提出了多种快速运动估计算 法，大多数算法都是基于块匹配的。我们可以将各种快速块匹配算法进行以下 分类：启发式搜索法、基于快速配准技术的搜索法、多分辨率搜索法、基于时 空相关性的搜索法、基于率失真优化的搜索法和快速穷尽搜索法等。下面主要 介绍启发式搜索法和基于时空相关性的搜索法两大类。 3 3 1 启发式搜索法 在全搜索法中，为找到最佳匹配块，遍历了搜索窗口的每个参考位置， 启发式搜索法试图减少遍历的搜索窗口中的参考位置来降低运算量。这类快速 算法都基于一种假设：参考位置距离最佳匹配位置越远，对应的匹配误差越大。 实验表明这种假设在大多数情况下是成立的。启发式搜索法都是从( 0 ，0 ) 矢量 为初始出发点向四周进行先粗后细的搜索过程。这类搜索法典型的代表有三步 搜索法、共轭方向搜索法、二维对数搜索法、四步搜索法、新三步搜索法、新 四步搜索法、钻石搜索法、六边形搜索法等。 3 3 1 1 三步搜索法( t s s ，t h r e es t e ps e a r c h ) - 6420246 x x 黑 y 累累粒 人 、 k 搭侉 丫 、! 厂_ 杏， l 飞旷， 一、 ，、 、小 丫 u v 图3 2 三步搜索法( t s s ) 过程 三步法是一种由粗到精的搜索算法，快速而且高效，它基本保持了全搜索 法的性能，但其计算量只有其2 0 左右。它使用m a d 准则，通过三步搜索，逐 步减小搜索步长。每次搜索都是以上一步的搜索结果为中心，进行周围定步 6 4 2 0 2 4 6 第三章运动估计技术 长的3 3 像素搜索，搜索精度为】个像素。图3 - 2 显示了t s s 的全过程： ( 1 ) 以窗口中心为中心搜索点，步长为4 ，包括周围的8 个像素点，根据 最小绝对误差原则得到一个最佳匹配点，共搜索g 个点： ( 2 ) 以上步最佳匹配点为中心，步长为2 ，继续搜索周围8 个点得到匹配 点，共搜索8 个点： ( 3 ) 同上一步，只是步长为1 ，最后得到的最佳匹配点就是要得到的运动 估计的点，从而得到运动矢量进行图像的预测。 图中数字表示第几步搜索到的点，例如数字2 表示第二步搜索到的点。本 章后面的图中数字都是此意，以后不做说明。 针对一个1 6 1 6 的像素子块，t s s 共搜索2 5 个点，而f s 要进行1 6 1 6 = 2 5 6 个点的搜索，运算时间明显减少，性能只是稍有下降。因此，它是一种 很好的运动估计算法。 3 3 1 2 共轭方向搜索法( c i ) s ，c o n j u g a t ed ir e c t i o n a ls e a r c h ) 共轭搜索法也是使用m a d 作为匹配准则。图3 - 3 显示了c d s 的全过程 x y 巧 一4 - 20246 6 罴 4 累 2 累 京 厂x 必蒋 0 y一 2 4 - 6 图3 - 3 共轭方向搜索法( c d s ) 过程 ( 1 ) 在x 轴方向上进行搜索，固定y 轴方向砂= 0 ，对横向的1 5 个点进行 逐一匹配，按m a d 最小原则得到一个点( d x o ，0 ) ； ( 2 ) 保持d x o 不变在y 轴方向搜索，又搜索了1 4 个点，得到最佳匹配点 第三章运动估计技术 ( 出u ，d y u ) a 算法共搜索了2 9 个点。这种算法简单，实现容易，但由于只对两个方向进 行搜索，得到的匹配点可能与真正的最佳匹配点有差距。因此，性能上与t s s 基本相同，但搜索点数比t s s 多5 个，搜索时间要长一些。 3 3 1 3 二维对数搜索法( t d l t w o d i m e n s i o nl o g a r i t h m j cs e a r c h ) 二维对数搜索法从运动矢量( 0 ，0 ) 开始，以十字形分布的5 个点构成每次 搜索的点群，搜索其中的最小姒d 点。如果最小m a d 点出现在十字形点群的边 缘，则下次搜索以该点为中心，步长不变；如果最小点出现在十字点的中心， 则下次搜索仍以该点为中心，步长减半：如果搜索过程中，新的十字形点群中 心在搜索窗的边缘，步长也要减半。如此循环操作直到步长为1 ，这时进一步 搜索当前最佳位置周围8 个点，得到l f i a d 最小的匹配点就是最优匹配点。二维 对数搜索法的性能比t s s 、c d s 略差一点，但速度快了许多。图3 - 4 显示了t d l 的过程。 粼裂裂 丫粼 ，：、 弋沪筒。 旷 弋y a s i ) s pu ) s p 一 s 1 3 s p 图3 一l ll d s p 中测试点重叠的三种情况 3 3 1 7 六边形搜索法( h e x b s ，h e x a g o n - b a s e ds e a r c h ) d s 算法和前面所述算法，都是基于种假设：搜索窗口内s a d 只有个最 小值，并且离最小值点越近对应s a d 越小。但是我们来分析下图3 1 2 所示d s 算法的一个例子。 图3 1 2d s 算法特性示例 图3 1 2 中，点9 距离点4 为互，距离点5 为2 ，假若本次搜索点9 对应 的s a d 值最小，那么点4 对应的s a d 值应该比点5 对应的小，这与上次搜索的 结果相矛盾，所以说点9 在本次搜索中并不是个好的参考点。同理点1 1 、1 3 有相同的结论。从图上我们看出造成这个结论的主要原因是点9 、1 0 、l l 、1 2 、 第三章运动估计技术 】3 距离中心点5 的距离不致引起的。我们可以想象，如果参考点均匀分布在 以中心点为圆心的圆上，那么就不会有这个矛盾，并且会得到最快的搜索速度。 六边形很好地符合了这种特性，从而引出了六边形搜索法。 六边形搜索法有两种搜索模式：大六边形模式和小六边形模式。如图3 1 3 所示。实际上小六边形模式退化为s d s p 。 血正h 碍 ， 一j矗h 一，1r 一 一 t 一 一r 一一 一r1，1， 一 ( a ) 大六边形模式 小六边形模式 图3 1 3 六边形搜索法的两种模式 6- 4 - 2 0246 、爪 丫村 h一 涔 小 厂 弋1 种 i 厂 ， l -f 装蛤 r 弋r h 小 、 t厂0y 小， l 厂弋 图3 1 4 六边形算法搜索实例 六边形搜索过程具体描述如下： ( 1 ) 以( 0 ，0 ) 为中心，搜索大六边形模式下的7 个点。若最佳点在中心， 贝0 转至u ( 3 ) ，否贝0 转至0 ( 2 ) ； ( 2 ) 以上次最佳点为中心，以大六边形模式搜索。若最佳点在中心，转到 6 4 2 0 2 4 6 第三章运动估计技术 ( 3 ) ，否则重复( 2 ) ： ( 3 ) 以上次中心为中心，搜索小六边形模式下的5 个点，找到的最佳点即 为运动矢量对应点。 从搜索过程可以得出，六边形搜索法需要搜索的参考位置为：7 + 3 x n + 4 ， 其中”为第二步执行的次数。图5 - 1 4 给出了个六边形搜索实例，运动矢量为 ( 4 ，一4 ) 。 h e x b s 算法与d s 算法相比，无论对于小运动矢量还是大运动矢量，遍历的 参考位置都要少，并且运动矢量范围越大，这种优势越明显。在目前的启发式 搜索算法中，六边形搜索算法收敛最快，匹配最好，拥有很好的性能。 3 3 2 基于时空相关性的搜索法 前面提到的各种运动估计算法尽管提高了速度，但都以牺牲一定的图像质 量为代价。此外，这些算法一个共同的缺点是：它们寻找运动矢量都是基于某 一个子块内部的最小形变规则，例如s a d 最小规则。换句话说，这些算法对运 动矢量的寻找是独立的，没有考虑运动矢量之间的相关性。实际上，考虑到视 频对象运动的整体性，其相邻子块的运动应该是具有一定同一性的，因此，可 以利用相邻的、已得到的运动矢量来预测当前的运动矢量，增加所得运动矢量 的精确性。 3 3 2 1 运动矢量区域适应搜索技术( m v f a s t ，m o t j o nv e c t o rf j e i da d a p t j v e s e a r c ht e c h niq u e ) 新加坡南洋理工大学的k a i k u a n gm a 和p r a b h u d e vi r a p p ah o s u r 提出了 运动矢量区域适应搜索技术m v f a s t 。2 0 0 1 年，m v f a s t 被m p e g 一4 组织推荐为优 化运动估计的算法。 m v f a s t 算法幂用了现实视频序列的中心偏置特性，提出更好的方法。 ( 1 ) 检测静态块 在m v f a s t 中，针对静态块引入了早期搜索排除( e a r l ye l i m i n a t i o no f s e a r c h ) 技术作为整个搜索过程的第一步。由于大量低运动视频序列有很多接近 ( 0 ，0 ) 的运动矢量，这些不运动宏块的发现可以仅仅通过计算其在( 0 ，0 ) 点的 s a d 值来实现。搜索中，如果在中心点( 0 ，0 ) 所得到的s a d 值小于某- - r 7 限值丁， 则针对此宏块的搜索立即停止。大量实验发现，将近9 8 的静态子块在( 0 ，0 ) 点的s a d 值小于5 1 2 ，因此，在实现中将r 值定为5 1 2 来作为实现早期搜索排 除技术的门限值。 第三章运动估计技术 ( 2 ) 判断局部运动行为 局部运动矢量在一个宏块中被定义为对此宏块有贡献的区域r o s ( r e g i o n o fs u p p o r t ) 中运动矢量的集合。一个宏块的r o s 区域包括”个相邻的宏块，在 m v f a s t 中，定义胛= 3 ，如图3 一】5 所示： 图3 1 5m v f a s t 定义的r o s 区域 定义r o s 的运动矢量集合v = ( v o ，k ，k ，巧) ，其中k 为( 0 ，o ) ，k 为图3 1 5 中相应宏块对应的运动矢量。矢量k ( 蕾，以) 的