（通信与信息系统专业论文）基于dsp的低码率视频编码技术研究与实现.pdf

基于d s p 的低码事视频编码技术研究与实现 摘要 基于d s p 的低码率视频编码技术研究与实现 摘要 随着社会的发展，人们对信息的需求量越来越大。并且由于互 联网与多媒体技术的不断发展，人们对图像信息的需求也日益增长。 因此，为适应有限带宽要求而发展起来的低码率视频编码技术，成 为了当今视频通信的研究重点。同时，随着数字信号处理器( d s p s ) 的进一步完善与发展，其应用已经深入到信号处理的各个领域，包 括数字视频信号的处理。本文着重对低码率视频编码技术进行了研 究，并利用d s p 芯片对其进行了实现。 r 本文主要包括以下内容： 首先介绍了低码率视频编码的原理，并给出了混合压缩编码方 式的系统框图。混合压缩编码是现今主要的数字视频编码标准( 包 括h 2 6 3 ，m p e g 协议) 的基本结构。在此基础上，对混合压缩编 码中两个最主要的模块离散余弦变换和运动估计，分别提出了 各自的快速算法。对不同快速算法的性能进行比较与分析后，选择 了最适合于d s p 芯片的快速算法并加以实现。 然后介绍了利用d s p 芯片实现的低码率视频编码标准一一 i t u - h 2 6 3 协议。详细说明了视频信源的编码算法以及同编码器实 现相关的一些模块，包括预测、运动估计庭动补偿、量化和编码控 制等。还介绍了用于改善图像质量或提高压缩比的四个可选技术项 上海交通大学硕士学位论文2 0 0 1 年1 2 月 无限制运动矢量、增强预测、p b 帧和基于句法的算术编码。 接着在d s p 系统设计中，首先对实现h 2 6 3 协议所需的处理能 力进行估算，然后分析和比较了多种常用的数字信号处理器的性能 与特点，选择了最优的数字信号处理器。随后讨论了在实现中需要 考虑的一些问题，例如数字信号处理器的结构特点、资源分配和程 序的编写规范与调试等。 在汇编语言实现的过程中，首先利用c 代码实现编码器，然后 针对数字信号处理器的特点，对c 代码进行了优化与修正，在此基 础上，利用数字信号处理器的汇编语言实现了编码器的主要模块， 并对实现结果同c 代码的实现结果进行了比较与分析。最后，利用 汇编语言实现了离散余弦变换和运动估计的快速算法，以提高整个 d s p 系统的性能。实验结果表明，利用数字信号处理器来实现低码 率视频编码是完全可行的。) 关键词：低码率视频编码，h 2 6 3 协议，数字信号处理器，离散余 弦变换，运动估计 u 基于d s p 的低码事视频编码技术研究与实现摘要 t h ed s p b a s e ds t u d ya n d i m p l e m e n t a t i o n0 f l o wb i t r a t ev i d e 0c o d i n g a b s t r a c t ，i mt h ei m p r o v e m e n to ft h em o d e mw o r l da n dt h ed e v e l o p m e n to f m u l t i m e d i at e c h n o l o g i e s ，t h ed e m a n df o rv i d e oi n f o r m a t i o nh a sg r e a t l y i n c r e a s e d m a n ye f f o r t sh a v eb e e nd e v o t e dt o w a r d s t h er e s e a r c ho fl o w b i t - r a t ev i d e oc o d i n g ，w h i c hi sd e v e l o p e dd u et ot h el i m i t e db a n d w i d t h a tt h es a m et i m e w i t hi t sf 1 2 t h e rd e v e l o p m e n t , t h ea p p l i c a t i o no f d i g i t a l s i g n a lp r o c e s s o r s ( d s p s ) h a v e a f f e c t e dm a n yf i e l d sw h i c hi n v o l v ei nt h e s i g n a lp r o c e s s i n g ，i n c l u d i n gt h ed i g i t a lv i d e op r o c e s s i n g t h i sp a p e ri s f o c u s e do nt h et e c h n o l o g yo fl o wb i t - r a t ev i d e oc o d i n ga n dt h ed s p i m p l e m e n t a t i o n o fi t f i r s t ，t h ep r i n c i p l eo fl o wb i t - r a t ev i d e oc o d i n gi si n t r o d u c e d ，a n d a l s o ，t h es y s t e ms t r u c t u r e o fh y b r i d - c o d i n gs c h e m ei s p r e s e n t t h e h y b r i d - c o d i n g s c h e m ei st h eb a s i cs t r u c t u r eo fm o s ti n t e r n a t i o n a l s t a n d a r d so f d i g i t a lv i d e oc o d i n g ，s u c ha sr e c o m m e n d a t i o nh 2 6 3 a n d m p e g b a s eo nt h es c h e m e ，t h i s p a p e rg i v e s s o m ef a s t a l g o r i t h m s r e s p e c t i v e l y f o rt h ed i s c r e t ec o s i n et r a n s f o r ma n dt h em o t i o n e s t i m a t i o n ，w h i c h a r et h em o s t i m p o r t a n tc o m p o n e n t s o ft h e i i i 上海交通太学硕士学位论文 2 0 0 1 年1 2 月 h y b r i d - c o d i n gs c h e m e a f t e rt h ec o m p a r i s o na n da n a l y s e so ft h e s e a l g o r i t h m s ，w ec h o o s et h em o s ts u i t a b l ea l g o r i t h m st ob er e a l i z e di n d s p s y s t e m s e c o n d l y , t h i sp a p e r i n t r o d u c e st h eh 2 6 3r e c o m m e n d a t i o nf o rv e r y l o wb i t r a t ec o m m u n i c a t i o n ，w h i c hi si n t e n d e dt ob ei m p l e m e n t e dw i t h d s p s t h ec o d i n ga l g o r i t h ma n ds o m ee s s e n t i a lm o d u l e sa r e e x p l a i n e d i nd e t a i l ，s u c ha st h ep r e d i c t o r , m o t i o ne s t i m a t i o n m o t i o nc o m p e n s a t i o n a n dc o d ec o n t r o l l e r f o u rn e g o t i a b l ec o d i n go p t i o n s ，w h i c hc a r l _ i m p r o v e t h ei m a g eq u a l i t yo ri n c r e a s et h ec o m p r e s s i o nr a t e ，a r ea l s oi n t r o d u c e d i nt h e p a p e r t h e s ef o u rn e g o t i a b l ec o d i n go p t i o n s a r eu n r e s t r i c t e d m o t i o nv e c t o rm o d e ，a d v a n c e dp r e d i c t i o nm o d e ，p bf r a m em o d ea n d s y n t a x - b a s e d a r i t h m e t i cc o d i n gm o d e t h e n ，w em a k er o u g he s t i m a t i o no f t h e p r o c e s s i n gc a p a b i l i t yn e e d e d f o rt h eh 2 6 3i m p l e m e n t a t i o n b a s e do nt h a te s t i m a t i o n s o m ec o n n o n d i g i t a ls i g n a lp r o c e s s o r s a r ee v a l u a t e dw i t ht h e i r p e r f o r m a n c e a n d c h a r a c t e r i s t i c st oc h o o s et h eo p t i m a lo n et or e a l i z et h ee n c o d e r s o m e i s s u e sa r e d i s c u s s e d ，f o re x a m p l e ，t h e s t r u c t u r eo ft h e d s p s ，t h e d i s t r i b u t i o no f r e s o u r c e s ，t h es t r i c tc r i t e r i o no fp r o g r a m m i n g ，e t c a f t e rt h e i m p l e m e n t a t i o n s i ncc o d e ，s o m em o d i f i c a t i o n sa n d o p t i m i z a t i o n s h a v eb e e nd o n et om a k et h ec o d ec o n f o r m st ot h e c h a r a c t e r i s t i c so fd s p s t h e n ，t h em o s t i m p o r t a n t m o d u l e so ft h e e n c o d e ra r er e a l i z e dw i t hd s p a s s e m b l yl a n g u a g e t h er e s u l t ，i n c l u d e t t h eo u t p u ts t r e a ma n dt h er e c o n s t r u c t e d i m a g e s ，a r ec o m p a r e dw i t ht h a t o ft h ecc o d e f i n a l l y , t o i m p r o v et h es y s t e mt h r o u g h p u t ，t h ef a s t a l g o r i t h m so fd i s c r e t ec o s i n et r a n s f o r ma n dm o t i o ne s t i m a t i o na t ea l s o a c h i e v e dw i t ha s s e m b l yl a n g u a g e t h ee x p e r i m e n t a lr e s u l ts h o w st h a t t h ed s pi m p l e m e n t a t i o no fl o wb i t - r a t e v i d e o c o d i n g i s a b s o l u t e l y v i a b l e k e y w o r d s ：l o wb i t - r a t e v i d e o c o d i n g ，h 2 6 3r e c o m m e n d a t i o n ， d i g i t a ls i g n a lp r o c e s s o r , d i s c r e t ec o s i n et r a n s f o r m ，m o t i o ne s t i m a t i o n v 1 1 引言 第一章绪论 自6 0 年代以来，随着计算机和信息科学的飞速发展，数字信号处理技术 应运而生并迅速发展，现已形成一门独立的学科体系。简单地说，数字信号处 理( d i g i t a ls i g n a lp r o c e s s i n g ，d s p ) 是利用计算机或专用处理设备，以数值计 算的方法对信号进行采集、变换、综合、估值与识别等加工处理，借以达到提 取信息和便于应用的目的。近2 0 多年来，数字信号处理是紧紧围绕理论、实 现及应用三个方面迅速发展起来的。 信号处理需要高性能的数字压缩方法。因此，数字压缩的进展和数字信号 处理技术的进展有着密切的关系。许多先进的信号处理技术对计算机提出了很 高的要求，实现这些技术就要在微电子领域有突破性进展，使得在计算机电路 尺寸、复杂性和能源消耗上取得飞跃。数字信号处理芯片( d s p s ) 对压缩算法 的实现提供了强有力的支持。 随着多媒体的发展，d s p 技术在图像及视频处理方面获得了广泛应用。九 十年代以来，数字图像及视频技术的应用已经渗透到通信、多媒体、广播电视 和计算机等各个角落。数字图像及视频技术的广泛应用大大提高了人类的生活 质量。如多媒体电脑、数字视频和数字相机等在家庭中的日益普及，让人们能 够充分领略到数字技术所带来的乐趣。而v c d 、d v d 和数字式高清晰度电视 机进入家庭，更给我们带来了高品质的视听享受。在这一领域，许多新的应用 也正在不断涌现，如远程医疗、可视电话和数字图书馆等。 由于数字图像及视频的信息量是相当大的，可以利用原始图像的空间冗余 度、时间冗余度、符号冗余度和视觉冗余度进行压缩。从这个意义上讲，数字 图像及视频技术的发展里程，也是图像及视频压缩技术的发展里程。对于这一 课题，无论是学术界还是产业界都投入了大量的人力和物力进行研究。进入九 十年代以来，随着视频编码技术的日益成熟，国际标准化组织( i s o ) 和国际 电讯联盟( i t u ) 相继推出了一系列视频压缩编码的国际标准：h 2 6 1 、h 2 6 3 、 m p e g 1 、m p e g 2 和m p e g - 4 等。这些标准在不同的领域里都得到了相当广 泛的应用，为数字图像及视频技术的普及做出了极大的贡献。 1 2 数字信号处理器的发展与应用 上海变通大学硕士学位论文2 0 0 1 年1 2 月 1 2 1 数字信号处理的优点 数字信号处理( d s p ) 是利用专门或通用的数字信号芯片，以数字计算的 方法对信号进行处理，具有处理速度快、灵活、精确、抗干扰能力强、体积小 等优点【5 1 。 数字信号处理与模拟信号处理相比，具有以下优点： 信号处理的动态范围大，有比模拟信号大3 0 d b ( 几十倍) 的动态范围， 因而有更高的精度。 数字信号处理仅受量化误差和有限字长的影响，处理过程不产生其它噪 声，具有更高的信噪比。 具有高度灵活性，能够快速处理、缓存和重组数据，可以时分多用、并 行处理，还可以灵活地改变系统参量和工作方式，实现可编程处理。 具有极好的重现性、可靠性和预见性。 算法具有直接的可实现性。 可以对白噪声和多径干扰进行相应的最佳化处理。 以上优势是数字信号处理在各领域中广泛应用的重要保证。 1 2 2 数字信号处理器的发展历史 数字信号处理器的发展历程大致分为三个阶段：7 0 年代理论先行，8 0 年 代产品普及，9 0 年代突飞猛进。 7 0 年代d s p 是基于数字滤波和快速傅立叶变换( f f t ) 的经典数字信号 处理，其系统由分立的小规模集成电路组成或在通用计算机上编程来实现 d s p 处理功能，当时受到计算机速度和存储量的限制，一般只能脱机处理，主 要在医疗电子、生物电子、应用地球物理等低频信号处理方面获得应用。 8 0 年代d s p 有了快速发展，理论和技术进入到以快速傅立叶变换为主体 的现代信号处理阶段，出现了具有可编程能力的通用数字信号处理芯片，例如 美国德州仪器公司( t e x a si n s t r u m e n t ) 的t m s 3 2 0 1 0 芯片，在全世界推广应用， 在雷达、语音通信、地震等领域获得应用，但芯片价格较贵，还不能进入消费 领域应用。 9 0 年代d s p 技术的飞速发展十分惊人，理论和技术发展到以非线性谱估 计为代表的更先进的信号处理阶段，能够用高速的d s p 处理技术提取更深层 的信息，硬件采用更高速的d s p 芯片，能实时地完成巨大的计算量，以t i 公 司推出的t m $ 3 2 0 c 6 x 芯片为例，片内有两个高速乘法器、6 个加法器，能以 2 0 0 m h z 频率完成8 段3 2 位指令操作，每秒可以完成1 6 亿次操作，并且利用 成熟的微电子工艺批量生产，使单个芯片成本得以降低。并推出了c 2 0 0 0 、 c 5 0 0 0 和c 6 0 0 0 等不同应用范围的系列，使新一代的d s p 芯片在移动通信、 基于d s p 的低码率视频犏码技术研究与实现第一章绪论 数字电视和消费电子领域得到广泛应用，数字化的产品性能价格比得到很大提 高，占有巨大的市场。 1 2 3 数字信号处理器的发展 系统级集成d s p 是潮流 缩小d s p 芯片尺寸始终是d s p 的技术发展方向。当前的d s p 多数基于 r i s c ( 精简指令集计算) 结构，这种结构的优点是尺寸小、功耗低、性能高。 各d s p 厂商纷纷采用新工艺，改进d s p 芯核，并将几个d s p 芯核、m p u 芯 核、专用处理单元、外围电路单元、存储单元统统集成在一个芯片上，成为 d s p 系统级集成电路。 可编程d s p 是主导产品 可编程d s p 给生产厂商提供了很大的灵活性。生产厂商可在同一个d s p 平台上开发出各种不同型号的系列产品，以满足不同用户的需求。同时，可编 程d s p 也为广大用户提供了易于升级的良好途径。人们已经发现，许多微控 制器能做的事情，使用可编程d s p 将做得更好更便宜。 追求更高的运算速度 目前一般的d s p 运算速度为1 0 0 2 0 0 m i p s ( 兆指令每秒) ，即每秒钟可运 算1 亿 2 亿条指令，但仍嫌不够快。由于电子设备的个人化和客户化趋势， d s p 必须追求更高更快的运算速度，才能跟上电子设备的更新步伐。d s p 运算 速度的提高，主要依靠新工艺改进芯片结构。目前，n 的t m s 3 2 0 c 6 x 芯片由 于采用v l i w ( v e r yl o n gi n s t r u c t i o nw j r d ，超长指令字) 结构设计，其处理速 度已高达2 0 0 0 m i p s ，这是迄今为止的最高速度。当前d s p 器件大都采用 0 1 8 1 t m 0 2 5 9 mc m o s 工艺，按照c m o s 的发展趋势，d s p 的运算速度再提 高1 0 0 倍( 达到1 6 0 0 g i p s ) 是完全有可能的。 定点d s p 是主流 从理论上讲，虽然浮点d s p 的动态范围比定点d s p 大，且更适合于d s p 的应用场合，但定点运算的d s p 器件的成本较低，对存储器的要求也较低， 而且耗电较省。因此，定点运算的可编程d s p 器件仍是市场上的主流产品。 1 3 图像编码的发展 上海交通大学硕士学位论文2 0 0 1 年1 2 月 图像编码领域是非常活跃的，其中最为活跃的是低码率运动图像编码，这 当然是与通信网的现状，尤其是与目前的接入网现状相关的。目前在绝大部分 国家与地区。用户的主要接入手段仍是双绞线，尽管近几年来话带数据技术有 了突破性进展，但也只有3 0 4 0 k b i t s ( 双向) 的数据传送能力，因而要开放多 媒体业务首先要解决低速率运动图像的编码问题。 近十年来，对低速运动图像的编码研究取得了巨大的进展，其中最有代表 性的是h 2 6 3 和m p e g - 4 协议，h 2 6 3 主要用于对话方式的多媒体业务中，而 m p e g 4 主要用于存储回放式多媒体业务中。h 2 6 3 是由i t u 提出的，m p e g 4 是由i s o 提出的，这两种算法的基础都是变换域编码中的离散余弦变换算法。 两种算法在很多方面采用了十分类同的技术，它们两者是可以进行互通的。这 两种算法的推出，对于低速多媒体业务系统是一个很大的促进。需要指出的是， 近年来低速运动图像编码成就的取得，很大程度得益于微电子技术的发展，由 于d s p 芯片能力越来越强，芯片的容量越来越大使得原来无法达到的处理 能力现在能够达到了，从而产生高效优质的编码算法。但从算法的基础来说， 近二十年来基本没变化，采用的仍是运动补偿加离散余弦变换算法。 近年提出的其它算法，如：小波变换、分形变换和模型编码都没能达到太 规模商用的程度，已经国际标准化的算法仍然还是基于离散余弦变换( d c t ) 算法的，因而近年来运动图像编码进展取得主要是靠挖掘离散余弦变换加运动 补偿算法的潜力取得的。 1 4 本文内容安排 本文主要研究了低码率视频编码的d s p 实现，并充分利用d s p 芯片的硬 件结构，对软件实现的指令进行优化，发挥数字信号处理器的功能。因此，本 文主要就数字信号处理器及其在视频处理中的应用展开讨论，具体内容安排如 下： 第二章介绍了低码率图像压缩编码的原理，并针对其中的主要模块 d c t 变换和运动估计，提出了几种快速算法。 第三章介绍了低码率视频编码标准h 2 6 3 协议，并对其中涉及编码器实现 的模块进行了介绍。 第四章针对h 2 6 3 协议以及d s p 芯片的特点，选择了合适的数字信号处理 器，并对所选用的c 5 4 x 芯片的结构与特点进行了说明。 第五章介绍了低码率视频编码的d s p 实现，包括c 代码的实现，针对d s p 芯片的c 代码的优化，以及汇编语言的实现，最后用汇编语言实现了第二章中 4 基于d s p 的低码率视额编码技术研究与实现第一章绪论 所述的快速算法，以提高系统性能，并对结果进行了分析和讨论。 上海交通大学硕士学位论文2 0 0 1 年1 2 月 2 1 引言 第二章图像压缩编码的原理与算法优化 图像压缩编码是在1 9 4 8 年o l i v e r 提出电视信号的线性p c m 编码理论开始 的，经过四十多年的发展，图像编码理论日趋走向成熟。同时，随着多媒体与 信息技术的不断进步，在低码率情况下的图像压缩技术得到了极大的发展，并 在多个领域中加以应用，如可视电话、多媒体电子邮件、远程医疗等。 本章介绍了低码率情况下的图像压缩原理与系统结构。并对其中两个主要 模块一d c t 变换和运动估计的多种快速算法进行了说明。 2 2 低码率图像压缩的原理与系统结构 2 2 1 图像压鳍的j 再理 由于活动图像的数据量很大，因此要在低码率的信道中传送活动图像，必 须要对图像数据加以压缩。图像数据压缩之所以可以实现，首先是因为原始图 像中存在着很大的冗余度，例如，一幅图像内邻近像素之间的相关性( 空间相 关性) 、图像前后帧之间的相关性( 时间相关性) 等；其次，许多应用领域通 常允许有一定的失真，这就为提高压缩比提供了有利的条件；第三，由于人眼 是图像信息的最终接受者，如果在图像压缩时能够充分利用人眼的视觉特性， 就可以在保证重建图像质量的前提下进一步提高压缩比。 一般来说，图像压缩编码的方法分为两种：基于波形的编码和基于模型的 编码。 基于波形的编码是将一幅图像作为一个二维的信号波形或是将一组图像 序列作为一个三维的信号波形，然后利用其特有的统计特性加以编码。绝大多 数的图像编码技术都是属于这种编码方式，例如变换域编码、予带，小波编码、 分形编码等。基于模型的编码则是将图像作为一个二维的投影或是三维的立体 场景，然后在编码端提取图像的模型参数，并在解码端利用提取和量化后的模 型参数对图像进行合成。这里主要讨论基于波形的编码。 在基于波形的编码方式中，主要运用的压缩原理为以下三种： 1 、预测编码 6 基于d s p 的低码率视频犏码技术研究与实现第二章田像压缩稿码的蜃理与算法优化 预测编码又称为差分脉冲编码调制( d p c m ) 。在预测编码中，编码器对 当前样本值和预测值之间的差值信号进行p c m 编码并传输；解码器将收到的 码字解码并与预测值相加，得到重建样本值。预测编码之所以能够达到压缩数 据的目的，源于这样一个事实：预钡4 信号的标准差要远小于原始图像数据的标 准差。因此，对误差信号进行可变长编码便可以达到压缩数据的目的。对图像 视频信号而言，待编码的就是一个图像序列，预测时可利用前后帧之间在时间 轴上的相关性进行称为帧间预测，若辅助以运动估计和运动补偿技术，则可 进一步压缩数据。预测编码的一个缺点是抗干扰能力差，若在传输中出现误码， 其影响将不只局限于一个像素，而会扩散开去，造成明显的横条干扰。 2 、频域编码 实现频域编码方法主要依据两个基本原则：一、通过合适的滤波或变换， 可以在频域中得到数目较少、相关性较小的分量，从而提高编码效率；二、利 用接受者( 观众) 的视觉特性，来提高编码器的主观性能。考虑到图像中像素 间的相关性变换编码通常对子像块进行。 在诸多交换编码中，k l 变换( k a r h u n e a - l o e v et r a n s f o r m ) 后的结果的均 方误差最小。但是k l 变换的算法比较复杂并不利于实时的实现。而d c t 变换( 离散余弦变换) 由于其性能十分接近k l 变换且其算法简单，因而得 到了广泛的应用。与d p c m 不同，d c t 变换的误码所造成的错误被限制在一 个像素块中，不会引起误码扩散。 3 、熵编码 熵编码，即信息保持编码，又称无失真编码。根据s h a n n o n 的无干扰编码 理论，在无干扰条件下，存在一种无失真的编码方法，使得编码的平均长度与 信源的熵任意接近。目前主要有三种典型的熵编码方法：h u f f m a n 编码、算术 编码和游程编码。前两者利用了信源概率分布的不均匀性，后一个利用信源自 身的相差性。 2 2 2 图像压缩编码的系统结构 低码率情况下的图像压缩编码系统，应该有效的去除空间域、时间域和频 域的冗余信息。因此必须有效将空间域压缩和时间域压缩技术结合起来，构 成一个完整、高效的压缩编码系统。 对于空阃域和时间域的压缩技术，一般有两种结合方式：一是将空间和时 间分开进行处理，称为混合压缩编码方式；二是将空间和时间统一进行处理， 称为3 d 压缩编码方式【8 】。后一种方式包括三维子带编码、三维分形编码和三 维小波变换等。由于其算法复杂，且在运动变化较大的情况下会降低图像质量 等原因，并没有得到广泛的应用，但在近几年，这种编码方式的发展很快，但 主要运用在较高码率的应用中。目前的低码率图像压缩应用，主要采用的都是 第一种混合压缩编码方式。 混合编码压缩方式根据空间域和时间域处理的先后顺序，也分为两种。其 系统结构如图2 - l ( a ) 所示。图中t 表示变换，q 表示量化，而q 1 表示反量化 ( 即重建) 。 图2 1 混合编码方式系统框图( e l ) 方式i 和方式i i ( b ) 方式i ii 运动补偿的d c t 变换编码方式 f i g u r e 2 - lh y b 喇c o m p r e s s i o n ( a ) s c h e m e ia n di i c o ) s c h e m ei l im o t i o n - c o m p e n s a t e dd c tc o d i n g 混合编码方式i 是先进行时域的预测，再进行空间域的压缩( 即频域变换) ， 而混合编码方式i i 则是先进行频域变换，再进行预测。经过多年的发展，混合 编码方式i 发展为混合编码方式i ，即运动补偿的d c t 变换编码方式 ( m c d c t ) ，其系统结构如图2 - 1 ( b ) 所示。这种编码方式已经成为一种典型的 算法，无论是h d t v ，m p e g 协议或h 2 6 1 、h 2 6 3 协议，采用的都是这种压 缩编码方式。 运动补偿的d c t 变换编码，具有以下几个主要的优点： 1 、较高的编码效率 2 、成熟的编码方式与编码技术 3 、较短的编码延时 在运动补偿的d c t 变换编码方式中，d c t 变换和运动估计是两个最重要 的模块。有效的提高这两个模块的运行效率，就能够极大的改善整个系统的效 率。因此，通过对这两个模块的研究，发展出了许多快速算法，以求提高系统 性能。下面的两个小节，就分别对d c t 变换和运动估计的快速算法进行了阐 述。 2 3 快速d c t 变换 对于一个n x n 块的d c t 受换，其定义如下： ，v ) - ，i n - i n 脚- if(x,y)cos百(2x+1)unc08百(2y+1)vxf(uy ) c o ( 2 y + 1 ) v x x = oi ( 2 1 ) ，v ) = f 。0 8 了i ( 2 1 ) 1 l 卜o 二 z v i 其中： c ( “) ，c ( v ) = 1 ? 2 ”，兰：二品一， c z - 2 ， 上式中的二维d c t 变换，可以分解为两次一维d c t 变换，即： 脚m=圭州隙扣)乏n-im咖s-(2x2+v1)uxljcosl(2y+厂1)vxy=0 0j ( 2 _ 3 ) 二 i二 j v z v i 因此，对于二维的快速d c t 变换，可以由一维的快速d c t 变换来实现。 下面就介绍两种主要的快速算法。 2 3 1 快速d c t 算法1 的原理 由w h c h e n ，c h s m i t h 和s c f r a l i c k 提出的快速d c t 算法【1 司是基于 矩阵分解的思路。 对于一维d c t 变换，有 肋) = 扣篓m c o s l ( 2 i + r 1 ) m r ( 2 4 ) 则对于一个n 点的一维d c t 变换，可以写成： 州= j 1 l q ( 2 5 ) 其中 f l 为n x l 的矢量，圆为变换后的n x l 矢量， a n 】= 【c ( n ) c o s ( 2 i + 1 ) n r d 2 n ：i ，u 2 0 1 ，( n - 1 ) ，整个快速算法的思路就是对矩阵【a n 】进行分 解。 观察矩阵【a n 】，可以发现如下的递归形式： 【”】= 目】 一苫2r 。0 ，： 【b 。】 ( 2 6 ) 其中 【月。，：】= ic ( “) c 。s 蔓垒二学| ；行= o 1 ，2 1 ( 2 7 ) p n 是- - 个n x n 的变更矩阵其作用是将位码倒序的矢量变为自然顺序的 矢量，矩阵 b n 的定义如下： 耻舷划 协s ， 其中【，。】是单位阵， i n ，： 是反对角单位阵。 对于矩阵【r n ，2 】可进一步进行分解，分解成为多个简单矩阵的乘积。例如 n = 8 ，则有： 1 s m 一石 1 6 o o s 1 n 一石 1 6 11 11 o0 0o o0 0o 一11 ll o c o s 一疗 1 6 c o s 一石 1 6 o lo 0 一c o s 三 4 0c o s 兰 4 00 1 c o s 一石 1 6 0 0 c o s 一万 1 6 o0 c o s 三0 4 c o s 兰0 4 o1 ( 2 9 ) 如此，就可以将复杂的矩阵相乘，变为多个简单矩阵的乘法，以此来减少 l o 厅 嵋，o，叫m，卜m o 口 出 s ! 目! 目! ! ! ! ! ! ! ! g ! _ ! 自! | 自! ! ! g 目自g 吝三g 量釜三；苫：髻= = ：= = 2 = 乘法和加法的次数，达到快速变换的目的。 n = 8 的快速一维d c t 变换的流图如图2 2 所示。 从图中可以看到，作一个8 点的d c t 变换，该快速算法只需1 6 次乘法和 2 6 次加法就可以完成。同原先的矩阵相乘所需的6 4 次乘法和5 6 次加法相比， 大大减少了计算量。 图2 - 2 快速d c r 变换算法l 的流图n = 8 f i g u m 2 - 2 f l o w g r a p ho f f a s t d c t m e t h o d if o r n = 8 2 3 2 侠递d c t 算法2 的原理 由b gl e e 提出的快速d c t 算法 1 刀是基于d c t 变换的对称性，类似于 快速f f t 算法。 一维d c t 变换如式( 2 - - 4 ) 所示，则有 f ( i ，= 鲁以珂) c o s 产( 2 - 1 0 ) 上式即为一维的逆d c t 变换( i d c t ) 。 若定义c 等“ 如下： q 秒= c o s 可( 2 i + 1 ) m r ( 2 1 1 ) 则n 点的逆d c t 变换就变为： ，( f ) = 户( 功c ( 2 1 2 其中 一 f ( n ) = 二a c ( ”) f ( n ) ( 2 1 3 ) 将f ( i ) 按n 分为奇数和偶数列( 设n 为偶数) ，则有 ，( j ) = g ( f ) + ( f )( 2 1 4 a ) 砷 h n m n ：2 n 丌 内 n i b 凡 巧 佑 仃 厂( 一1 一i ) = g ( i ) 一 ( f ) ，i = 0 , 1 ，一，n 2 1( 2 1 4 b ) 其中 很显然，g ( i ) 构成了一个n 2 点的逆d c t 变换，因为 c ”= c 1 2 ”m = q 搿酱 对于h ( i ) 可以写成如下形式： n ，2 - 1 ( d = 户( 2 n + 1 ) c 豺 n 1 0 也构成了一个n 2 点的逆d c t 变换。因为 2 q g 。- , 2 ( 2 i “”= q 秽2 “+ c 伽“ 则有 如果定义 f ( 2 n 一1 ) 1 。o = 0 并且有c h ”= c 2 “1 = 0 ，则 故此，式( 2 - 1 9 ) 可以写成： n ，2 一l 2 , - 、。( 。2 i “h ( f ) = ( f ( 2 n + 1 ) + f ( 2 n 一1 i 。2 2 n “m ” 即式( 2 1 7 ) 的形式。 然后定义 g ( 阿) = f ( 2 n ) h ( n ) = f ( 2 n + 1 ) + f ( 2 n - 1 ) ，n = 0 , 1 ，n 2 1 ( 2 1 5 a ) ( 2 1 5 b ) ( 2 1 6 ) ( 2 1 7 ) ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) ( 2 2 1 ) ( 2 2 2 ) ( 2 - 2 3 a ) ( 2 2 3 b ) j 2 h “q 玎 q _ l f 一 = “g 肿n “q +玎 犯 l f = u h 肿 w c d +行 0 _ ( f 一m + 抽 qd +订 犯 一( f 一 1 1 0 n q 2 h 计 c d 一糟 q - ( f 一 = 肿 _ 吉q +行 0 ， 一 以及 a r ，2 - l 蚋= g ( 盯) c 别磊 ( 2 2 4 a ) n - 0 = h ( 行) q ( 2 m i + 1 ) n ) ，i = o 1 - ，n 2 1 ( 2 - 2 4 b ) n = o 则式( 2 1 4 ) 可写成 ，( f ) = g ( f ) + o ( 2 c ；等“) ) - 矗( f ) ( 2 2 5 a ) f ( n 一1 一f ) = g ( 0 - ( 1 ( 2 c 箝“) ) ( f ) ，f = o ，1 ，n 2 1 ( 2 2 5 b ) 如此，就将n 点的逆d c t 变换，分解成为两个n 2 点逆d c t 变换的和。 重复以上步骤，就可以继续分解逆d c t 变换。 按照如上步骤也可以分解d c t 变换，但是，由于d c t 变换是正交变换， 因此只要将逆d c t 变换转置后，就完成d c t 变换。图2 - 3 给出了快速d c t 变换的流图。 图2 - 3 快速i e t 变换算法2 的流图n = 8 f i g u r e 2 - 3f l o wg r a p ho f f a s td c t m e t h o d 2f o rn = 8 从图中可以看到，该算法作一次8 点的d c t 变换，只需要1 2 次乘法和 2 9 次加法。同前一种快速d c t 变换算法相比，减少了乘法的次数，增加了加 法的次数。 2 4 运动估计的快速算法 运动补偿帧间预测编码是通过运动估计获取图像序列中物体运动的矢量， 阳 h 咒 两 n h 卧盯 m n o i 仃 佑 h ! 。 上海交通大学硬士学位论文2 0 0 1 年1 2 月 然后根据运动矢量进行运动补偿以获取帧间图像信号的最佳预测，从而最大限 度地除去序列图像的冗余度，达到图像压缩的目的。因此实现运动补偿帧间预 测编码的关键是运动估计，而作为实用的运动估计算法，要求在保证运动估计 的准确性的前提下尽量减少计算复杂度及要传输的附加信息。 本节从块匹配算法的原理开始，介绍了四种常用的块匹配运动估计快速算 法。 2 4 1 块匹配法原理 运动补偿帧间预测编码是当今视频编码中最流行最有效的方法之一。从 h 2 6 1 ，m p e g 1 ，m p e g 2 到h 2 6 3 以及m p e g - 4 验证模型中都采用了运动补 偿帧间预测编码，而运动估计则是运动补偿帧间预测编码的关键。运动估计效 果的好坏直接影响到运动补偿帧间预测编码，影响到编码的效率。也正因为如 此，各国学者在运动估计方法上做了大量的工作，形成了块匹配法、像素递归 法、相位相关法、光流法等一系列运动估计方法。其中，块匹配法因为它的算 法简单有效，以及易于集成在视频编码芯片中而得到广泛应用，当今的所有视 频编码标准都采用块匹配法。 在块匹配法中，图像被分成诸多大小固定，互不重叠的像素块，通过将每 一个像素块在上一帧一定范围内搜索其最优匹配，得到的偏移矢量即为该像素 块的运动矢量。上述基本思想的前提是块内各像素只作相同的平移运动。虽然 实际上块内各点运动可能并不一致，也不一定只有平移运动；但当所选像素块 较小时，上述假设可以近似成立，该假设的优点是简化了块匹配法计算复杂度。 下面是块匹配的算法。 设像素块大小为n x n ，可能的最大偏移矢量为w ，则搜索范围为( n 也w ) ( n + 2 w ) 。图2 - 4 示出了待匹配像素块与搜索区的几何位置关系。以五0 ) 表示第k 帧n x n 像素块中( i ，j ) 点的像素值，位移矢量v = ( 埘，z ) ，则可以 定义该点位移帧差d f d k ( i ，力如下： d f d k ( i , j ) = 以( f ，) 一 ( i - m ，j 一刀) ( 2 2 6 ) 1 4 基于d s p 的低码率视频糖码技术研究与实现第二章圈像压蟾擤码的原理与算法优化 图2 - 4 持匹配像素块与搜索区的几何位置关系 f i g u r e 2 4r e l a t i o n s h i pb e t w e e n c u r r e n tb l o c ka n ds e a r c ha r e a 根据( 2 2 6 ) 式，对n x n 像素块作全局搜索，匹配准则采用最小绝对误 差和s a d 准则，可求得该像素块最优匹配的运动矢量圪。( 工，少) ： k = a r g m i n k ( j ，) 一 一( f m ，一n ) 1 ) ( 2 2 7 ) - t i l j = l 户1 其中： q = 帆，l w m w ，一w 竹w j ( 2 2 8 ) 块匹配法的特点是简单，易于硬件实现。上述算法也表明，如何在足够的 匹配精度情况下，尽量减少运动估计的运算量，并以尽可能少的附加信息传输 运动矢量，它面临以下几个问题： 1 、块大小的选择：