（通信与信息系统专业论文）运动估计算法的fpga仿真与实现研究.pdf

中文摘要 随着通信技术和计算机技术的发展，多媒体的应用与服务越来越广泛，视频 压缩编码技术也随之成为非常重要的研究领域。运动估计是视频压缩编码中的一 项关键技术。由于视频编码系统的复杂性主要取决于运动估计算法，因此如何找 到一种可靠、快速、性能优良的运动估计算法一直是视频压缩编码的研究热点。 运动估计在视频编码器中承担的运算量最大、控制最为复杂，由于对视频编码的 实时性要求，因此运动估计模块一般都采用硬件来设计。 本文的目的是在f p g a 芯片上设计实现一种更优的易于硬件实现的块匹配 运动估计算法一二步搜索算法。全文首先讨论了块匹配运动估计理论及其主要 技术指标，介绍了运动估计技术在m p e g 4 中的应用，然后在对典型的运动估计 算法进行分析比较的基础上讨论了一种性能和硬件实现难易度综合指数较高的 二步搜索算法。本文对已有的用于全搜索算法实现的v l s i 结构进行了设进，设 计了符合二步搜索算法要求的f p g a 实现结构，并在对其理论分析之后，对实现 该算法的运动估计模块进行了功能模块的划分，并运用v e r i l o gh d l 硬件描述语 言、i s e 及m o d e l s i m 开发工具在s p a r t a n l i ex c 2 s 3 0 0 ef p g a 芯片上完成了对各 功能模块的设计、实现与时序仿真。最后，对整个运动估计模块进行了仿真测试， 给出了其在f p g a 上搭建实现后的时序仿真波形图与占用硬件资源情况，通过对 时序仿真结果可知本文设计的各功能模块工作正常，并且能够协同工作，整个运 动估计模块能够正确的实现二步搜索运动估计算法，并输出正确的运动估计结 果；通过对占用硬件资源及时钟频率情况的分析验证了本文设计的二步搜索运动 估计算法的f p g a 实现结构具备先进性和实时可实现性。 关键词：运动估计 f p g a块匹配二步搜索运动估计算法 w i t ht h e d e v e l o p m e n t o fc o m m u n i c a t i o n sa n d c o m p u t e r s ，m u l t i m e d i a t e c h n o l o g yh a sb e e nw i d e l ya p p l i e dt o v a r i o u sa p p l i c a t i o n sa n dp l a y sam o r ea n d m o r ei m p o r t a n tr o l ei nc u r r e n ti n f o r m a t i o ns o c i e t y r e a lt i m ev i d e oe n c o d i n gh a s b e c o m eah o tr e s e a r c hf i e l d m o t i o ne s t i m a t i o ni sak e yt e c h n o l o g yo fv i d e oc o d i n g s t a n d a r d t h ec o m p l e x i t yo f v i d e oc o d i n gs y s t e mm a i n l yl i e so nt h em o t i o ne s t i m a t i o n a l g o r i t h m s oh o w t om a k et h es e a r c ho fm o t i o ne s t i m a t i o na l g o r i t h m sr o b u s t ，f a s t e r a n dm o r ee f f e c t i v eb e c o m e sah o tr e s e a r c ht o p i c f u r t h e r m o r e ，m o t i o ne s t i m a t i o ni s t h em o s tc o m p u t a t i o n a l l yd e m a n d i n gp a r to fv i d e oe n c o d e r h e n c e ，i tu s u a l l yr e q u i r e s h a r d w a r ef o rar e a l - t i m ei m p l e m e n t a t i o n t h i st h e s i sa i m sa tt h er e s e a r c h i n go nf p g ah a r d w a r ei m p l e m e n t a t i o no f2 s s m o t i o ne s t i m a t i o na l g o r i t h m ，w h i c hh a sb e t t e rp e r f o r m a n c ea n dc a l lb ee a s i l yr e a l i z e d i nh a r d w a r e i nt h i sp a p e r , w ef i r s t l yd i s c u s st h ep r i n c i p l ea n dt e c h n i c a li n d e x e so f b l o c km a t c h i n gm o t i o ne s t i m a t i o n a n dm a k eas i m p l ep r e s e n t a t i o na b o u tt h e a p p l i c a t i o no fm o t i o ne s t i m a t i o ni nm p e g 一4 t h e n2 s sa l g o r i t h mi sp r o p o s e db a s e d o nt h ea n a l y s e so fs o m et y p i c a lm o t i o ne s t i m a t i o na l g o r i t h m s ，a na r c h i t e c t u r e i m p l e m e n t e do nf p g ai sd e s i g n e df o r2 s s t h i sa r c h i t e c t u r ei sd e v e l o p e df r o ma p a r a l l e l v l s ia r c h i t e c t u r ef o rf s m o r e o v e r , f u n c t i o nm o d u l e so f2 s sm o t i o n e s t i m a t i o na r es e to f f a n dt h e ya r ed e s i g n e d ，i m p l e m e n t e da n ds i m u l a t e dw i t hv e r i l o g h d l ，i s ea n dm o d e l s i mo i ls p a r t a n l i ex c 2 s 3 0 0 ef p g ac h i p s a tl a s t ，t h ew h o l e m o t i o ne s t i m a t i o nm o d u l ef o r2 s si st e s t e d a c c o r d i n gt ot h es i m u l a t i o nw a v e sa n d e x p e r i m e n t sd a t a , w ec a nd r a ws o m ec o n c l u s i o n sa sf o l l o w s ：f i r s t ，t h em o t i o n e s t i m a t i o nm o d u l ed e s i g n e di nt h i st h e s i sc a ni m p l e m e n t2 s sa l g o r i t h mc o r r e c t l ya n d c a ne x p o r tt h er i g h tr e s u l t s e c o n d l y , t h ea r c h i t e c t u r ed e s i g n e df o r2 s si sp r o v e dt o b ea d v a n c e da n dr e a l - t i m er e a l i z a b l et h r o u g ht h er e s e a r c ho nt h eu s eo fh a r d w a r e r e c o u r s e sa n dc l o c kf r e q u e n c y k e yw o r d s ：m o t i o ne s t i m a t i o n ，f p g a ，b l o c km a t c h i n g ，2 s s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤叠盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：王加新签字日期：2 0 0 5 年2 月1 5 日 学位论文版权使用授权书 本学位论文作者完全了解苤壅盘生有关保留、使用学位论文的规定。 特授权墨鎏盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 瑰拍 i 导师签名： ， 签字日期：刁枘年7 月- - ) 7 日 签字日期：以“年p 月1 日 第一章绪论 第一章绪论 1 1 视频压缩技术及其发展概况 由于通信技术及信号处理技术的快速发展，使得人类在生产消费与休闲娱乐 上有革命性的转变，多媒体的应用与服务也越来越广泛。多媒体信息主要包括图 像、声音和文本三大类，其中视频、音频等信号的信息量是非常大的，无论是传 送还是存储都需要占用大量的带宽和资源。以c i f ( c o m m o ni n t e r m e d i a t ef o r m a t ) 格式的彩色视频信号为例，其未被压缩时的比特率为1 8 2 m b s ，要使其在5 6 k m o d e m 的常用网络设备上以5 6 k k b p s 的信道传输，则压缩率高达1 ：3 2 5 。可见， 在多媒体通信中，采用既能保持较好的视频质量又很高效的视频压缩编码技术已 经成为非常重要的研究领域。 1 1 1 视频压缩编码技术的基本原理 数字视频信息可以进行压缩，是因为视频数据的表示中存在大量的冗余，并 且这些冗余在编解码后钉j 以无失真地恢复。因此可以通过去除这些兀余数据来减 少原始视频的数据量，从而达到数据压缩以解决视频传输数据量巨大的目的。视 频数据中通常存在以下几种冗余： 空间兀余：这是静态图像存在的最主要的- - 9 一数据冗余。研究表明，图像帧 内的行、列相邻点之间的相关性可以达到0 9 以上。 时间冗余：这是视频序列图像中经常包含的冗余。祧频序列前后帧之间存在 着较大的相关性。研究表明，活动图像相邻帧同一位置上前后样值的相关性f 帧 间相关性) 也达到0 9 以上。确人统训，l m b v s 的可视电话中前后相邻帧平均只有 4 的像暴发生变化。 视觉冗余：人类的视觉系统对图像场的敏感性是非均匀的和非线性的。人的 视觉系统( n v s ) 对于某些失真并不敏感。然而，在记录的原始图像数据时，通常 假设视觉系统是线性的和均匀的，对视觉敏感和不敏感的部分同等对待，从而产 生了比理想编码( 即把视觉敏感和不敏感的部分区分开来编码) 更多的数据，这就 是视觉冗余。 是视觉冗余。 第一章绪论 1 1 2 视频压缩编码标准的国际发展历程 从1 9 4 8 年o l i v e r 提出电视信号的线性p c m 编码理论之后，经过这几十年 的发展，视频压缩编码理论日趋走向成熟。 1 9 8 4 年，c c i t t 的第1 5 研究组针对i s d n 成立了一个专门研究会议电视和 可视电话的数字视频压缩编码问题的专家小组，该小组于1 9 8 8 年1 0 月提交了 i s d n 中可视电话会议电视的c c i t th 2 6 1 建议草案，即“p * 6 4 k b i t s 声像业务的 图像编码”，h 2 6 1 标准于1 9 9 0 年1 2 月完成并被批准。h 2 6 1 视频压缩编码标 准是图像压缩编码领域4 0 年研究成果的结晶，是第一个在国际上产生广泛影响 的视频压缩编码标准，随后的m p e g 系列标准中的视频压缩编码算法从原理和 基本框图来看都是以h2 6 1 为基础的，是对h ，2 6 1 的重大发展和改进。 1 9 8 6 年，i s o 与c c i t t 联合成立了“联合图片专家组( j p e gj o i n tp h o t o g r a p h i c e x p e r t sg r o u p ) ”，于1 9 9 1 年3 月提交了用于灰度等级和颜色两方面连续变化静 止图像编码的j p e g 建议草案，与1 9 9 2 年7 月通过正式标准，j p e g 有两个操作 模式，一是以d c t 为基础的有损压缩方法；二是以熵编码为基础的无损压缩方 法。 1 9 8 8 年，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 ) 运动图像专家组成立，它 致力于运动图像及其伴音编码标准化工作，包括m p e g 系统，即m p e g 视频及 m p e g 音频。原先共有三个版本m p e g 一1 、m p e g 2 、m p e g 一3 ，后又增加了 m p e g - 4 、m p e g 一7 和m p e g 2 1 ，不同版本表示了不同用途和质量，对多媒体通 信的发展起到了革命性的推动作用。 ( 1 ) m p e g 一1 m p e g 一1 制定于1 9 9 3 年，是针对1 5 m b p s 以下数据传输率的数字存储媒质 运动图像及其伴音编码的国际标准。m p e g 1 用于在c d - - r o m 上存储同步和彩 色运动视频信号，可优化为中等分辨率，并在其优化模式下，采用标准交换格式 ( s i f ) 。它可针对s i f 标准分辨率( 对于n t s c 制为3 5 2 x 2 4 0 ；对于p a l 制为 3 5 2 2 8 8 ) 的图像进行压缩，传输速率为1 5 m b i t s s e c ，每秒播放3 0 帧。m p e g 一1 对色差分量采用4 ：l ：1 的二次采样率。m p e g 1 旨在达到v r c 质量，其视频 压缩率为2 6 ：l 。m p e g 1 现已成为常规视频标准的一个子集。 ( 2 ) m p e g 一2 m p e g 一2 制定于1 9 9 5 年，它追求的是c c i r6 0 1 建议的图像质量d v b 、h d t v 和d v d 等制定的3 m b p s 1 0 m b p s 的运动图像及其伴音的编码标准。m p e g 一2 在n t s c 制式下的分辨率可达7 2 0 x 4 8 6 ，m p e g 一2 能够提供广播级的视像和c d 级的音质。由于m p e g 一2 在设计时的巧妙处理，使得大多数m p e g 2 解码器也 第一章绪论 可播放m p e g 1 格式的数据，如v c d 。同时，由于m p e g 一2 的出色性能表现， 己能适用于h d t v 。除了做为d v d 的指定标准外，m p e g 一2 还可用于为广播、 有线电视网、电缆网络以及卫星直播提供广播级的数字视频。m p e g 2 的另一特 点是，其可提供一个较广的范围改变压缩比，以适应不同画面质量、存储容量以 及带宽的要求。对于最终用户来说，由于现存电视机分辨率的限制，m p e g 2 所 带来的高清晰度画面质量( 如d v d 画面) 在电视上效果并不明显，到是其音频特 性( 如加重低音，多伴音声道等) 更引人注目。 ( 3 ) m p e g 一3 m p e g 3 是i s o i e c 最初为h d t v 开发的编码压缩标准。但由于m p e g 2 的高速发展，m p e g 一3 的功能已被淘汰，其原来的工作由m p e g 2 小组承担。 ( 4 ) m p e g 一4 m p e g 一4 于1 9 9 8 年1 1 月公布，该标准提出了基于对象编码的概念，不仅 针对一定比特率下的视频、音频编码，更加注重多媒体系统的交互性和灵活性。 m p e g 一4 标准主要应用于视像电话( v i d e op h o n e ) ，视像电子邮件( v i d e oe m a i l ) * l l 电子新闻( e l e c t r o n i c n e w s ) 等，其传输速率要求较低，在4 8 0 0 6 4 0 0 0 b i t s s e c 之间， 分辨率为1 7 6 1 4 4 。m p e g 一4 利用很窄的带宽，通过帧重建技术，压缩和传输数 据，以求以最少的数据获得最佳的图像质量。与m p e g - l 和m p e g 2 相比， m p e g 4 的特点是其更适于交互a v 服务以及远程监控。m p e g 一4 是第一个使用 户由被动变为主动的动态图像标准，从根源上说，m p e g 。4 将自然物体与人造物 体相溶合( 视觉效果意义上的) ，其试图达到两个目标：低比特率下的多媒体通信 及多工业的多媒体通信的综合。据此目标，m p e g - 4 引入了a v 对象 ( a u d i o v i s a u lo b j e c t s ) ，使得更多的交互操作成为可能。 m p e g 一4 的应用前景非常广阔。它的出现将对以下各方面产生较大的推动 作用：数字电视、动态图像、万维网( w w w ) 、实时多媒体监控、低比特率下 的移动多媒体通信、基于内容存储和检索多媒体系统、i n t e m e t i n t r a n e t 上的视频 流与可视游戏、基于面部表情模拟的虚拟会议、d v d 上的交互多媒体应用、基 于计算机网络的可视化合作实验室场景应用、演播电视等。 m p e g 一4 技术还在不断的完善和发展过程中，新的m p e g 一4 标准的应用正在 促进多媒体压缩技术经历另一次重大变化。这一变化将会与1 9 9 0 年m p e g 一2 压 缩标准的推出一样巨大，而且随着视频通信应用的快速发展，m p e g 4 标准势将 影响到范围广泛的多种应用领域。 ( 5 ) m p e g 7 继m p e g 一4 之后，要解决的矛盾就是对日渐庞大的图像、声音信息的管理和 迅速搜索。针对这个矛盾，m p e g 提出了解决方案m p e g 一7 。m p e g 一7 力求能够 第一章绪论 快速且有效地搜索出用户所需的不同类型的多媒体信息。m p e g 一7 将对各种不同 类型的多媒体信息进行标准化的描述，并将该描述与所描述的内容相联系，以实 现快速有效的搜索。该标准不包括对描述特征的自动提取，它也没有规定利用描 述进行搜索的工具或任何程序。其正式的称谓是“多媒体内容描述接口”。 目前，m p e g 系列国际标准已经成为影响最大的多媒体技术标准，对数字电 视、视听消费电子产品、多媒体通信等信息产业的重要产品产生了深远影响。 1 1 3 视频压缩编码技术在我国的发展现状 近年来，我国的科研人员在国际标准的制定中开始发挥比较重要的作用，也 为我国制定具有自主知识产权的视、音频压缩标准奠定了基础。自1 9 9 7 年至今， 我国己有2 0 余项提案提交m p e g 专家组，参与单位包括：中国科学院计算技术研 究所、清华大学、微软亚洲研究院、哈尔滨工业大学、北京工业大学、香港科技 大学等。2 0 0 0 年7 月，第5 3 次m p e g 会议成功在北京举行该次会议上，微软 中国研究院的可伸缩性视频编码中的容错技术被m p e g 4 国际标准采纳，这是国 内进入m p e g 系列国际标准的第一项技术。此外，清华大学的快速全局运动估 计算法、哈尔滨工业大学和中科院计算所的快速s p r i t e 生成算法也已经进入 m p e g 一4 国际标准。2 0 0 3 年1 1 月5 日，g d b n2 0 0 3 ( b 1 第七界广东国际广播电视 信息网络展览会暨2 0 0 3 华南国际媒体技术与网络展览会) 在广州锦汉展览中心新 馆召开。目前，我国在音视频技术、标准和产业上正面临着一次难得的发展机遇。 1 2 本文的研究对象及主要工作 本课题对视频压缩中的运动估计算法在f p g a 上的设计与实现进行了研究。 课题的任务为设计一种更优的易于硬件实现的运动估计搜索算法的实现结构，并 在f p g a 上对其进行设计与实现，使之在保证匹配性能的基础上尽可能的降低计 算复杂度，减少计算量。 1 2 1 运动估计技术概述 由前面的介绍可知，视频信息中含有大量的冗余信息，主要是空间冗余和时 间冗余，可以通过数据压缩去除这些信息数据之间的时间空间函数的自相关性和 互相关性( 即去除冗余) ，保留相互独立的信息分量，从而可以节约存储空间， 第一章绪论 提高传输效率，同时使视频信息在较低速率的信道上进行实时传送成为可能。运 动估计能够有效的去除视频信息之间的时间冗余，它占整个视频压缩编码量的 6 0 8 0 ，直接影响着编码的速度和效率，是视频编码的一项关键技术。 传统的运动估计方法己经能很好的进行图像匹配，但是是以牺牲速度来获得 最好的预测效果的。而快速算法计算相对简单，搜索时间较短，但是其估值精度 则相对较低，匹配性能相应降低。同时，在运动估计处理过程中，需要用到大量 的对图像的求和，求差运算，数据量很大，又要求保证系统的实时性，因此对处 理的速度要求较高，但是运算本身的结构比较简单。此外，在进行搜索时，因为 搜索范围比较大，需要把搜索窗口分成并行部分处理。目前，存在一些采用d s p 进行视频压缩处理的方案。但是通常用d s p 开发需要使用专门的汇编语言和开 发工具，开发难度大，而且芯片功耗较大，不易并行处理。与d s p 相比，使用 f p g a 可以达到更高的工作频率，程序可读性好，而且具有更高的设计自由度， 便于调试，可以很方便地修改、扩充程序的功能，而无需重新绘制印刷电路板 ( p c b ) ，可以并行地处理数据，功耗较小，成本较低，可供选择地开发工具也 较多，因此对于本课题更适于用f p g a 进行硬件实现。 1 2 2f p g a c p l d 的发展与概述 在这个数字化、信息化的时代，数字集成电路得到了非常广泛的应用。数字 集成电路本身在不断地进行更新换代。它由早期的电子管、晶体管、小中规模集 成电路、超大规模集成电路( v l s i c ) 逐步发展到今天的专用集成电路( a s i c ) 。 a s i c 的出现降低了产品的生产成本，提高了系统的可靠性，减少了产品的体积 和功耗。但是由于a s i c 是为某种专门用途而设计的集成电路，一般来讲，要比 通用型集成电路的用量少的多，因此设计和制作成本很高，设计制造周期较长。 随着产品市场竞争的加剧，更新换代速度的加快，硬件工程师更愿意根据需要在 实验室里自己设计、更改大规模数字逻辑，研制自己的a s i c 并立即投入实际应 用，可编程逻辑器件( p l d ) 就是基于这个基本思想出现的。可编程逻辑器件是 作为一种通用型的器件生产，然而其逻辑功能又是由用户通过对器件编程来自行 设计。它可以把个数字系统集成在一片p l d 上，而不必由芯片制造厂商去设 计和制作专用的集成芯片。因此p l d 兼具了通用型器件批量大、成本低和专用 型器件体积小、电路可靠等特点。早期的可编程逻辑器件只有可编程只读存储器 ( p r o m ) 、紫外线可擦除只读存储器( e p r o m ) 和电可擦除只读存储器 ( e e p r o m ) 三种，它们只能完成简单的数字逻辑功能。其后，出现了结构上稍 复杂的可编程芯片p a l ( 可编程阵列逻辑) 和g a l ( 通用阵列逻辑) 。它们可以实 第一章绪论 现速度特性较好的逻辑功能，但其过于简单的结构也使它们只能实现中小规模的 数字逻辑电路。随着微电子制造工艺的发展，p l d 的集成规模越来越大，2 0 世 纪8 0 年代中期，已从低密度的p a l 和g a l 器件发展到万门以上的c p l d ( 复 杂组合逻辑) 与f p g a ( 现场可编程逻辑阵列) 。 同以往的p a l 、g a l 相比，c p l d f p g a 规模较大，可以替代几十甚至几千 块通用i c 芯片可以完成较大规模的数字逻辑功能。它们具有体系结构和逻辑单 元灵活、集成度高、适用范围广等特点。与其他a s c 相比，它们又具有设计开 发周期短、设计制造成本低、开发工具先进、标准产品无需测试、质量稳定以及 可实时在线检验等优点，因此这种芯片受到了世界范围内电子工程设计人员的广 泛关注和欢迎。随着半导体工艺技术的发展与市场的需要，超大规模、高速、低 功耗的新型f p g a c p l d 不断推陈出新。新一代的f p g a 其设计性能已完全能与 a s i c 相媲美，而且由于f p g a 的逐步普及，其性价比也足以与a s i c 抗衡。f p g a 在片上系统设计( s o c ) 中占据着越来越重要的地位。 l - 2 3 全文结构安排 全文共分为七章。 第一章主要介绍视频压缩编码技术以及本文的研究对象及研究内容。 第二章介绍块匹配运动估计的原理及主要技术指标，并对些典型的运动 估计算法进行了分析讨论。 第三章介绍目前流行的m p e g 一4 视频压缩标准及其中的运动估计技术，以 此来理解整个运动估计系统架构和运动估计在整个编码系统中的地 位和作用。 第四章确定本文的设计任务和设计流程，分析本设计采用的二步搜索运动 估计算法，并完成对实现该算法的阵列结构的设计。 第五章介绍本设计开发所用的f p g a 器件、v e r i l o gh d l 硬件描述语言以及 开发工具。 第六章介绍本文设计的运动估计模块中各功能模块的划分、设计思路及其 仿真实现结果，然后，对整个运动估计模块进行测试，通过仿真结 果及数据分析讨论本设计的正确性、先进性和实时可实现性。 第七章总结 第二章块匹配运动估计技术及典型算法分析 第二章块匹配运动估计技术及典型算法分析 运动估计占整个视频压缩编码量的6 0 8 0 ，运动估计算法的优劣直接 影响着编码的速度和效率，因此运动估计算法成了多年来视频压缩编码的研究热 点。运动估计算法主要分成两大类：像素递归法和块匹配法。考虑到复杂度和实 时实现的要求，块匹配法已经成为目前最常用的方法，在 l 2 6 l ，h 2 6 3 ，m p e g 等有关视频编码的国际标准中，均采用了这种方法。本文研究的算法亦属于块匹 配运动估计算法，因此本章将重点介绍块匹配运动估计算法，并对其主要技术指 标及典型算法的性能进行分析讨论。本章的内容为全文的设计研究提供了必要的 理论基础和依据。 2 1 运动估计技术概述 由第一章的介绍可知，通过对视频信号进行压缩，可以节约存储空间，提高 传输效率，同时使视频信息在较低速率的信道上进行实时传送成为可能。运动估 计就是利用视频序列时间上的冗余度以及人眼视觉系统的特性，采用已知的参考 帧对当前帧像素进行预测，来达到视频压缩的目的。由于视频序列图像在时间轴 上具有较强的相关性，运动估计( m e l 及运动补偿( m c ) 技术可以有效的减少时间 相关性，因此该技术被广泛应用于各种视频压缩编码方案中。运动估计用来估计 物体的位移，得到运动矢量；运动补偿根据得到的运动矢量，对前一帧中由运动 而产生的位移进行调整，从而得到尽可能接近本帧的预测帧。由此可见，运动估 计算法越完善，估计出的运动矢量越准确，运动补偿的性能就越好，从而使预测 误差越小，编码后需要传输的信息量也将随之大大减少，整个系统的码率压缩比 将得到很大的提高，因此运动估计和补偿技术己经成为视频序列图像编码系统中 减少时间冗余、提高压缩比的重要技术。 运动估计与补偿的过程为：首先，当前帧在过去帧( 参考帧) 的窗口中寻找 匹配部分，从中找到运动矢量：然后，根据运动矢量，将过去帧位移，求得对当 前帧的估计；将这个估计与当前帧相减，求得估计的误差值；将运动矢量和估计 的误差值送到接收端去。接收端根据收到的运动矢量将过去帧作位移( 也就是对 当前帧的估计) ，再加上接收到的误差值，就是当前帧。 第二章块匹配运动估计技术及典型算法分析 2 1 块匹配运动估计概述 根据参与匹配的单元，可将运动估计算法分为像素递归法和块匹配算法 饵m a ) 。像素递归法是根据像素间亮度的变化和梯度，通过递归修正的方法来估 计每个像素的运动矢量。由于这种方法需要传送大量的运动矢量，无法降低数码 率，因而并不适用。与像素递归法相比，块匹配的运动估计算法精度较低，但是 它的位移跟踪能力强，而且复杂度低，容易实现，对于实际运动来说是通用的方 法，因此h 2 6 x 和m p e g 标准都采用块匹配法来进行运动估计。 2 2 1 基于块的运动模型 帧k + 1 视频图像编码主要研究的是运动物体的二维运 动。在基于块的运动模型中，我们假设图像是由运 动的块构成的，并且我们只考虑这种模型中最简单 的平移形式，这种形式限制每个块作单纯的平移 运动。例如，帧k 中有一个中心位于n _ ( n l ，1 1 2 ) 的 n x n 块b ，其对应的运动模型如图2 1 所示，它运 动( 认为是平移运动) 成为帧k + l 中同样尺寸的块。 对所有的( n l ，n 2 ) b ，其运动简化模型为： s ( n l ，n 2 ，k ) = s ( r a + d l ，n 2 + d 2 ，k + 1 )式( 2 - 1 ) 其中d 1 ，d 2 是块b 位移( 平移) 矢量分量，d 1 ， 图2 - 1 基于块的运动模型d 2 是整数。 但是，当运动物体在帧间有旋转、缩放和局部变形等变化时，采用式2 - 1 所 表示的运动模型作运动估计，就会产生很大的估计误差。为此，有人曾提出过具 有1 2 个参数的运动模型来解决这个问题，但是因为需要进行很复杂的参数估计， 因此并不实用。 块匹配法的运动模型的前提假设：块匹配法的前提是块内各像素作相同的平 移运动。实际上，在块匹配时，虽然块内各点运动不一定相同，也不一定只有平 移运动，但是当m x n 较小时，上述简化可以近似成立，从而简化运算。这是块 匹配法成立的前提。因此现在的视频压缩技术都采用平移运动的运动模型来完成 运动估计。 第二章块匹配运动估计技术及典型算法分析 2 2 2 块匹配运动估计原理 视频中的图像序列相邻帧之间的变化在大多数情况下是很小的，存在很强的 相关性。块匹配的基本思想就是将当前帧分成若干个大小为m x n ，且互不相交 的块，并且假设块内所有像素都作相同的运动，且只作平移运动。然后，对每一 个块( 当前块) ，分别在参考帧中的一定区域( 称为搜索区) 内，按照一定的匹配准 则搜索与之最匹配的块( 称为预测块) 。假设一组图像序列在t 时刻对应于第k 帧 图像( 当前帧) ，其前一时刻对应于k 一1 帧( 参考帧) ，图2 2 表示了当前块与 搜索区之间的位置关系。 j v + 2 咖 j 1 7 i i - 咖。 ， _ 出。 川 k 帧m n 像素块 1 k - l 帧的搜索醒 图2 2 待匹配像素块与搜索区的几何位置关系 其中，当前块的大小为m n ，d r 一为水平方向上可搜索的最大位移，咖一 为垂直方向上可搜索的最大位移，则搜索区的大小为( m + 出) ( n + d y 。) 。 预测块与当前块间的位移称为运动矢量，他们的像素间的差值称为残差块， 这样当前帧中的每一块都可用一个残差块和一对运动矢量来表示。这样只需对运 动矢量和残差块编码传输就可以在解码端恢复当前块的图像，从而达到压缩的目 的。图2 3 为块匹配运动估计示意图。 第二章块匹配运动估计技术及典型算法分析 赖k 一1 图2 - 3 块匹配运动估计示意图 2 3 块匹配运动估计技术指标的确定 基于块匹配的运动估计算法，在实际应用中，首先需要确定以下几个方面的 问题：分块的大小，匹配准则，搜索范围，估计精度和搜索策略。前四个问题相 对简单，将在下面给予介绍，而搜索策略最为复杂，它决定了一个算法的好坏， 也是本文重点讨论的内容之一，所以将在2 4 节中对具有代表性的一些块匹配运 动估计搜索算法做详细的分析比较。最后，本小节对块匹配法存在的运动矢量场 的一致性和块内运动的不一致性问题做了简单的探讨。 2 3 3 分块大小的确定 在2 2 1 节中提到，块匹配法有个前提假设：同一个块内像素的运动是一致 的。为了满足这个假设，就必须要合理的选择块的大小。块大时，块内各像素作 平移运动的假设易被破坏，影响估计的精度；块小时，则易受噪声影响，估计不 够可靠，而且还会导致产生较多的运动矢量，使得运算量增加，所需传输的附加 信息也增加，降低了编码的效率。因此必须恰到好处地选择块的大小，以做到两 者兼顾。目前的视频压缩标准，如h 2 6 x 和m p e g 等，一般均以1 6 1 6 大小的 块作为块匹配单元，这是一个已为实践证明的较好的折衷结果。并且，h 2 6 3 和 m p e g - 4 在进行1 6 1 6 的宏块运动估计的基础上，又加入了8 8 块的运动矢量处 理，使得预测的精度进一步得到了提高。 2 3 4 匹配准则的确定 块匹配准则是判断块相似程度的依据，因此匹配准则的好坏直接影响了运动 第二章块匹配运动估计技术及典型算法分析 估计的精度：另一方面，匹配运算复杂度、数据读取复杂度在很大程度上取决于 所采用的块匹配准则。因此，提高运动估计算法的速度可以有两种途径：一种是 减少搜索匹配的点数，另外一种是降低块匹配准则的计算复杂度。 在块匹配法中，衡量最优匹配有三种最优匹配准则：最小绝对差( m a d ) 、 最小均方误差函数( m s e ) 和归一化互相关函数( n c c f ) 。分别定义如下： ( 1 )归一化互相关函数( n c c f ) ( m ，n 城一，m + i x n + ，) n c c f ( i ，舻匿了坐l 可面丁1 式2 - 2 ) l m ，”) 觅。“n + j ) l l m = 1h = 1jl m = ln = lj n c c f 的值最大为最优匹配点。 ( 2 ) 最小均方误差函数( m s e ) m s e 2 高蚤善阢， ) 一 一，胁+ 如+ j ) 】 2 - 3 ) l，_r， m s e 的值最小为最优匹配点。 ( 3 ) 最小绝对差( m a d ) 捌。= 杰萎m 善n 阮，z ) 一 。( 聊+ 细+ ，】 ( 式z a ) m a d 达到最小时，该点即为最优匹配点。 在式2 2 、2 3 、2 - 4 中，( i ，) 为位移矢量，一w i ，j + 形，矽为搜索范围， m x n 为块的大小，和丘一，分别为当前帧和上一帧图像的灰度值。因为人跟对 灰度比较敏感，而且灰度反映了运动的信息，所以匹配时只考虑视频帧图像的灰 度值。 实验表明，m s e 匹配函数运动估计的精度最高，但其众多的乘方运算在硬 件实现中比较困难；m a d 匹配函数略差，但是因为匹配准则的不同对匹配精度， 也就是位移矢量估计的精度影响不太大，因此不需作乘法运算又易于硬件实现的 m a d 算法比较实用，一度得到广泛的应用。但是当s a d 准则出现后，便迅速取 代m a d 被各种运动估计算法采用，因为它与m a d 的匹配效果等价，又去掉了 实际运算中不必要的除法，再次降低了计算量。s a d 的公式如下： 第二章块匹配运动估计技术及典型算法分析 n - 】 s a d ( i ，) = j c o ，j ) - r ( i + m ，j + n 】 m = 0 ( 式2 5 ) 式2 5 中，c 为当前块的灰度值，月为搜索区的像素灰度值。n x n 为块的 大小。 2 3 5 搜索范围的确定 搜索区域最合适的大小取决于三个方面： 每一帧的清晰度：更高的清晰度要求更大的搜索区域； 画面的类型：高速运动的画面要比低速运动的画面更适合采用大的搜索区域； 可用的处理资源：由于大的搜索区域带来更多的运算比较操作，因此需要更多 的处理。 因此，并不一定搜索区域越大就越适合。当搜索区域加大时，运动估计的性 能得到了提高，但是，需要处理的运算量也加大了。因此如何选择搜索区域的大 小要根据实际处理的图像来确定。下面举例来说明这个问题。表2 1 给出的是一 组骑自行车的图像序列在运动估计时选用不同大小的搜索区域得到的性能参数。 表21 不同大小的搜索区域的性能比较 由表2 1 中数据可见，当搜索区域由+ 7 增 l ：i 至l j + - 1 5 时，s a d 的性能仅仅 得到了很小的提高，而付出的代价却是比较操作的数量增加了4 倍，出现这种情 况是因为对于骑车这样的低速运动的图像，其运动估计的大部分性能增益都可以 在+ 一7 内得到，因此当增加了搜索区域，带来的性能改善却不明显。所以，搜索 区域的大小的确定要具体情况具体分析。 2 3 6 估计精度 在最开始的视频压缩标准里，运动估计采用的是基于1 6 x 1 6 块的块匹配，整 像素精度。这是由算法的复杂度和当时硬件的运算能力所决定的。 但是在实际中，常常遇到图像中的物体在帧间的真实位移一般与帧取样网格 不相关的情况，因此，整像素运动估计的精度就显得不够了。随着算法的改进和 第二章块匹配运动估计技术及典型算法分析 硬件处理能力的提高，目前，在m p e g 一4 和h 2 6 3 中，运动估计的精度已要求精 确到半像素( 即亚像素) ，提高了运动估计的性能。这也是考虑到运动估计的实时 实现，需传输的附加信息量等多种因素的折衷结果。 半像素级搜索是指在整像素搜索的基础上，为了寻找更好的匹配而进一步在 像素的插值空间上所进行的搜索。一般是在整像素搜索的匹配点周围的一定区域 ( 通常为8 个半像素点) 作全搜索，如图2 - 4 所示。 j 整荡 。上i 土 r 1 t 。il kl 厂 p 咫 ， | 繁 运动矢量 整像素搜索点 半像素搜索点 半像素运动矢量 图2 - 4 半像素搜索示意图 一般半像素精度参考帧的获得是借助于简单的双线性内插来实现的。双线性 内插技术将在第三章中详细讨论。 2 3 7 块匹配法还需要注意的一些问题 前面已经分析了如何解决块大小的选择，匹配准则，搜索范围和估计精度等 问题。此外，块匹配法还存在运动矢量场的一致性和块内运动的不一致性问题， 这里做简要的说明。 ( 1 ) 运动矢量场的一致性 当平移运动物体的图像较大，包含了多个子块时，这些相关子块的运动矢量 应该是十分接近的。但由于前述的块匹配法将图像分割成子块，孤立地逐块进行 匹配，没有利用块间的相关性，常常造成所求得的运动矢量场一致性不好，解决 的办法之一是修改匹配准则，加上块间运动矢量一致性约束项。 ( 2 ) 块内运动的不致性 块匹配法的前提是块内各像素作相同的平移运动，因此，如何解决假设不成 立时运动估值也是一个非常重要的问题。这种情况的解决办法是分区，对两个性 质不同的区域分别进行运动检测，但带来了如何分区和传送边界信息的困难。 h 2 6 3 的算法中采用将1 6 1 6 子块进一步分成四个8 8 块分别进行运动估计的方 第二章块匹配运动估计技术及典型算法分析 法来解决块内运动不一致的问题。 2 4 典型块匹配运动估计算法的分析比较 评价块匹配运动估计算法的优劣可以从以下两个方面考虑：准确度和匹配速 度。对于准确度，主要是看求出运动矢量后，进行运动补偿求残差，看残差是否 大，残差越小，准确度越好。匹配速度主要是看需要匹配的像素点的数目，也就 是估计一个运动矢量的平均搜索点个数。下面介绍几种典型的块匹配运动估计算 法，以此来分析块匹配运动估计算法的优劣的判定。 2 4 1 全搜索法( f s ) 全搜索法是对搜索窗内的所有块进行搜索，因此能够得到搜索窗内与当前块 最为匹配的块。全搜索的方式可以有两种：“光栅式”搜索和“螺旋型”搜索。如图 2 5 所示。当使用“早结束算法时”，“螺旋型”搜索的顺序有一定计算上的优势， 因为最好的匹配( s a d 最小) 最有可能出现在靠近搜索区中心的地方。但是“光 栅式”搜索方式更易于硬件实现。 ( 。) “光栅式，全搜索 ”o ( b ) ，? 螺雏型”全搜索 ( 起始点在中心位置) 图25 全搜索示意图 全搜索法是最直接同时运算量也最大的块匹配方法，需要( 2 + 1 ) 2 次搜索， ( 其中矿为最大搜索范围，下同) ，占整个视频压缩编码过程的5 0 8 0 的计 算量，这就限制了视频压缩编码实时性的实现。为了减小全搜索算法的运动搜索 复杂度和数据读取复杂度，近2 0 年来，出现了许多改进的快速运动估计算法。 但是，必须指出的是，全搜索算法虽然计算量大，但是最简单、可靠，找到 篇二章块匹配运动估计技术及典型算法分析 的也一定是全局最优的结果。该算法简单划一，在硬件搜索中非常适用，易于 a s i c 芯片实现，因此非常具有实用价值。目前，己有多种a s i c 芯片能实现实 时全搜索，如l 6 4 7 2 0 ，s t l 3 2 2 0 等。这些芯片单片能实现m n = 1 6 1 6 、 d