（计算机软件与理论专业论文）基于小波变换的矢量量化图像压缩编码研究.pdf

i u 予科技人学硕：i ：论史 学科专业：计算机软件与理论 论文题目：基于小波变换的矢h | 化图像压缩编码研究 硕士生：王茂芝导师：孙世新教授 摘要 f 视觉在人类感知中起着极为重要的作用，而视觉感知的结果和表现形式一 一图豫，是人类认识世界的重要信息来源，因此，图像已成为多媒体技术中最 为重要的数据类型。图像的处理与分析技术已发展成为现代信号处理技术中的 专门分支学科。由于图像信息丰富、数据量大，因此，为满足实际应用需要， 有必要对图像数据进行压缩处理，而图像数据中存在着大量的冗余信息，包括 统计冗余、结构冗余以及视觉冗余等，所以为压缩提供了可能，目前已发展成 为专门的研究领域图像编码。常见的图像压缩编码方法有：统计编码，预 测编码，变换编码，子带编码，模型基编码，小波变换编码，矢量量化编码， 神经网络编码，分形编码等。l j 本文以矢量量化压缩编码和小波变换压缩编码这两种图像压缩编码方法为 主要研究对象。在概述了图像压缩编码理论的基础上，首先介绍矢量最化压缩 编码理论，提出了一种基于模拟退火的l b g 改进算法，并通过实验验证了改进 算法的性能；接着介绍小波变换及其应用于图像压缩编码的相关理论，重点介 绍了基于小波变换的嵌入零树编码( e z w ：e m b e d d e dz e r o t r e e sw a v e l e t ) 算法； 在矢量量化和小波变换的结合方面，提出了一利，基于视觉特性的小波变换跨带 矢量量化压缩编码方案，并通过实验验证了算法的性能；最后，在并行性探讨 方面，设计了一种基于数据分割的二维d c t 图像压缩编码算法，并在p v m 实验 环境下验证了算法的性能。 关键词：图像压缩编码? 小波变换，矢量量化，。模拟退火；并行算法 离散余弦变换 u 了科技人学坝：f ：论文 s p e c i a l t y ：c o m p u t e rs o f t w a r ea n dt h e o r y - t i t l e ：t h er e s e a r c ho fv e c t o rq u a n t i z a t i o nb a s e do n w a v e l e tt r a n s f o r mo ni m a g e c o d i n g m s s t u d e n t ：m a o z h iw a n g a d v i s o r ：p r o f s h 扭i ns u n a b s t r a c t v i s i o ni si m p o r t m l ti nh u m a n ss e n s a t i o n i m a g e ，a st h er e s u l to fh a m a nv i s i o n s e n s a t i o n ，i st h em o s ti m p o r t a n ti n f o r m a t i o ns o u r c ef o rh u m a nt or e a l i z et h ew o r l d s o ，i m a g eh a sn o wb e c o m et h em o s ti m p o r t a n td a t at y p ei nt h ef i l e do fm u l t i m e d i a t e c h n o l o g y , m a di m a g ep r o c e s sa n da n a l y s i st e c h n o l o g yh a sn o wb e c o m et h e s p e c i a l t yi nt h ef i e l do fm o d e ms i g n a lp r o c e s s b e c a u s eo ft h eg r e a ta m o u n to fd a t a a n di n f o r m a t i o ni ni m a g e ，i ti sn e c e s s a r yt oc o m p r e s st h ei m a g ed a t ai no r d e rt o a d a p tt ot h ep r a c t i c a la p p l i c a t i o nd e m a n d t h er e d u n d a n c yo fs t a t i s t i c ，s t r u c t u r ea n d v i s i o ni ni m a g ep r o v i d e st h ep o s s i b i l i t yt oi m a g ec o m p r e s s i m a g ec o d ei sa d e v e l o p i n gf i e l do ni m a g ec o m p r e s sa n dal o to fm e t h o d so nt h a th a sn o wg e n e r a t e d ， s u c ha ss t a t i s t i cc o d e ，p r e d i c tc o d e ，t r a n s f o r mc o d e ，s u b b a n dc o d e ，m o d e lc o d e ， w a v e l e tt r a n s f o r mc o d e ，v e c t o rq u a n t i z a t i o nc o d e ，n e u r a ln e t w o r k sc o d e ，f r a c t a lc o d e e t c i nt h i st h e s i s ，w em a i n l yd e s c r i b eo u rw o r ko nv e c t o rq u a n t i z a t i o nc o d ea n d w a v e l e tt r a n s f o r mc o d eo ni m a g ec o m p r e s s a f t e rs u m m a r i z et h eb a s i ct h e o r yo n i m a g ec o d ec o m p r e s s ，w ef i r s t l yi n t r o d u c et h ev e c t o rq u a n t i z a t i o nt h e o r y , a n dw e a l s op r o p o s eal b gi m p r o v e da l g o r i t h mb a s e do ns i m u l a t e da n n e a l i n gw i t h e x p e r i m e n t a t i o nt ov e r i f yt h ep e r f o r m a n c e s e c o n d l y ，w ei n t r o d u c et h ew a v e l e t t r a n s f o r mt h e o r ya n dt h ee z wa l g o r i t h mu s e di nt h ea r e ao fi m a g ec o m p r e s s i o n b a s e do nt h ef o r m e rt w ot h e o r i e s ，w ep r o p o s eaw a v e l e tt r a n s f o r mc r o s s b a n dv e c t o r q u a n t i z a t i o nb a s e d o nh u m a nv i s i o n ，a n dw ev e r i f yt h ec o r r e c t i o nw i t h e x p e r i m e n t a t i o n a tl a s t ，i nv i e wo fp a r a l l e l ，w ed e s i g na 2 - d i m e n s i o nd c t i m a g e c o m p r e s sc o d ea l g o r i t h m b a s e do nd a t ap a r t i t i o n ，a n dv e r i f yt h ea l g o r i t h m s p e r f o r m a n c ei nt h ep v m e n v i r o n m e n t k e yw o r d s ：l i n a g ec o d e ，w a v e l e tt r a n s f o r m ，v e c t o rq u a n t i z a t i o n s i m u l a t e da n n e a l i n g ，p a r r a l l e la l g o r i t h m ，d c t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得电子科技大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 签名： 立莲：皇 日j 田：) 年月陟日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：监导师签名：遗 日期：1 ，p j 年；月沪日 u 予科技人学顾：b 论文 1 1 研究的背景和意义 第一章绪论 视觉在人类感知中起着极为重要的作用，而视觉感知的结果和表现形式 图像，能给人们以直观而具体的物体形象，是人类认识世界的重要信息来源，因 此，图像已成为多媒体技术中最为重要的数据类型。图像的处理与分析技术已发 展成为现代信号处理技术中的专门分支学科。由于图像信息丰富、数据量大，因 此，为满足实际应用需要，有必要对图像数据进行压缩处理，目l j i 已发展成为专 门的研究领域图像编码。图像编码在通信、介质存储、数据发行等领域有着 重要的作用，它一直是信息技术中最活跃的研究领域之一。特别是到了8 0 年代 未9 0 年代初，随着多媒体技术和凼特网技术的出现，如何有效地组织、存储、 传输和恢复图像数据，即探索更有效、更高压缩比的图像编码技术，成为现代信 息处理技术中关键任务之一。 “基于小波变换的矢量量化图像压缩编码研究”这一课题就是在这种背景下 确立的。这一课题既要求对图像压缩编码的理论有一个清磁的了解，又涉及到图 像压缩编码中的一些最新技术和算法，具体有矢量量化编码理论、小波变换和予 带压缩编码理论、非线性随机优化搜索算法和理论等。而且这一课题跨度很大， 涉及计算机软件与理论、信息与计算科学、信号与信息处理等专业知识。通过这 一课题的实施，对图像压缩编码理论和算法进行了总结，同时提出了一些相应的 改进算法并进行了实验，验证了改进算法的有效性和合理性。本文作者认为本课 题的确立和完成将在图像压缩编码领域做出一些有益的探索。 1 2 研究现状 从1 9 4 8 年0 1 i v e r 提出p c m 编码理论开始，迄今已有半个多世纪的历史，人 们已研究并提出各种各样的压缩方法。根据编码技术的原理方法进行分类，图像 编码可分为：预测编码、变换编码、矢量编码、熵编码和子带编码等。预测编码 和d c t 编码是静止图像编码中的两个主要技术，对于这两个技术，人们已从理论 到硬件实现都进行了深入的研究。到7 0 年代术，图像编码同臻成熟，其标志就 是图像编码的国际标准的制定，即i s o i e c 关于静止图像的编码标准j p e g 、c c i t t 关于电视电话会议电视的视频编码标准| 2 6 1 1 1 2 6 3 和i s o i e c 关于活动图像 的编码标准m p e g 。在j p e g 和m f ) e g 标准- - ，关键技术部分足d c t 编码。图像编 u 了科技人学坝小论文 码标准的制定保证了各个生产厂商设备的兼容性和可替代性。这些图像编码算法 融合了各种性能优良的图像编码方法，也是对传统编码技术的总结。此外，新的 编码标准也在不断研究，出现如基于小波变换的j p e g 一2 0 0 0 、基于模型编码的 m p e g 一4 和m p e g - 7 等新的图像编码标准。 就本文所涉及的矢量量化编码和小波变换编码而言，主要进展如下。 自从1 9 8 0 年l i n d e 、b u z o 和g r a y 提出矢量量化编码理论中的l b g 算法以来， 码书训练算法发展已有二十多年的历史，关于码书训练算法的研究方法主要分为 以下几大类：一是l b g 算法，包括g l a ( g e n e r a l i z e dl o y dh l g o r i t h m ) 。l b c 算法可以根据给定的训练序列，经过多次递归迭代运算，求出满足要求的输入矢 量的划分，其中训练序列是从具体的应用场合中选取典型图像，从这些图像中取 出图像子块的序列；二是p n n ( p a i r w i s en e a r e s tn e i g h b o ra l g o r i t h m ) 类算 法o 】其基本思想是：在算法初始阶段，侮个训练矢量作为一个单独的类，然后 从所有类中最相近的两个类，并让这两个类合并成一个新类，用新类的中心代替 两个旧类的中心，作为新码字。重复以上步骤，直到类的个数等于码书大小为止， 或失真到达收敛阈值。三是s m ( s p l i t t i n ga n dm e r g i n gh l g o r i t h m ) 类算法”。 算法的思路是：在算法迭代过程中，对于有较大量化失真的区域进行分裂，产生 量化失真较小的两个区域，而对有较小量化失真的两个区域进行合并。重复这个 过程，直到失真无明显改善或码书达到指定大小为止：四是n e u r a ln e t w o r k 类 算法“1 。神经网络类算法主要是寻求码书训练过程中的全局最优解，避免l b g 算 法迭代过程中的局部最优解，有多种训练算法，如l v q ( l e a r n i n gv e c t o r q u a n t i z a t i o n ) ；五是f u z z yc i u s t e r ，即模糊聚类算法“1 。其基本思想是：给每 个训练矢量分配一个介于0 和l 之削的隶属值，表示训练矢量属于某个区域的程 度，其中以f u z z yc m e a n 聚类算法( f 伽) 最有代表性；六是e 】i m i n a t i n g 类算 法”1 。其基本思想是：利用码书训练中距离计算的冗余，尽量删除不必要的计算。 矢量量化( v q ) 的关键在于码书的设计。目前并没有一种通用的方法能够设 计出一种在“全局”意义下“最优”的码书。经典的码书设计算法是l b g 算法， 由于它具有如下缺陷：一是尽管l b g 算法能够保证收敛，但不能保证收敛到全局 最优点；二是l b g 算法的收敛结果对初始码书的选择敏感；三是码书中存在永不 使用的码本。针对这三个缺陷，提出了不少的改进算法。综观所有的改进算法， 不外乎从以下几个思路考虑：一是不改变l b g 的算法思想，而是针对l b g 的运算 复杂性进行考虑，这主要是从l b g 算法中“距离”的度量考虑，从而减少算法的 运算量，如文献”1 ；二是从对初始码书的敏感性这一角度考虑，从而提出了基于 自组织特征映射的矢量量化算法一s o f m ( s e l f - o r g a n i z i n g f e a t u r e m a p ) 和相 应的改进算法，如频率敏感自组织特征映射算法f s o f m ，参见文献”“；三是从 电予科技大学硕i ：论文 “全局”最优的搜索算法这一角度考虑，引入一些随机化优化技术，包括遗传算 法，如文献“、进化算法，如文献“”、以及模拟退火算法；另外一个角度就是从 对全局“最优”的度量准则的修最上考虑，如文献“；四是利用矢量量化的优点， 把l b g 算法( 所代表的矢量量化方法) 和其他方法相结合，形成- 些新的图像压 缩系统，如v q + d p c m + j p e g ，v q + w a v e l e t 等，见文献“”“”“”：五是从算法的自适 应角度考虑，如文献u ”；六是从分裂法搜索过程叶1 空胞腔的改进上考虑，如文献 “”；七就是从聚类的角度理解l b g 算法，从而对聚类的过程中引入模糊隶属度的 模糊矢量量化方法f v q ，如文献“”。但，作为图像视觉效果的主观度量如何反映 在v q 中却一直没有得到有效的考虑和利用。也许v q 的工作突破将会在v q 和其 他方法的结合上以及把主观度量考虑和引入v q 中这两个方面。 小波变换压缩编码自从s h a p i r o 的e z w ( 嵌入零树小波) 算法( 文献“”1 ) 提出之后得到了广泛的关注与研究，并取得了很多成果。s a i d 和p e a r l m a n 的 s p i h t 算法“”利用位平面分层划分的方法，间接实现了空间小波树的比特平面排 序，有效地减少位平面的编码符号集的规模，提高了压缩比。不同于前者，基于 形态学聚类编码重要图有s l c c a 压缩算法o ”和m r w d 算法o ”。基于率失真意义下 的沈化方法有x i o n g 等人提出向一空频量化( s f q ) 算法”“，和e z w ，s p h i t 相比， 尽管p s n r 有了明显的提高，但图像的主观质量相差不大。t a u b m a n 使用了优化 截断点的嵌入块编码方法( e b c o t ) 对图像进行编码1 ，e b c o t 是先将每个子带 分成相对独立的码块，然后使用优化的分层截断算法对这些码块进行编码。图像 的压缩码流不仅具有s n r 可分级性，而且具有分辨率的可分级性。相比较，e b c 0 r r 的复杂度比e z w 和s p i t l t 高，但性能有所提高。所以e b c o t 算浈的基本思想已经 应用于j p e g 2 0 0 0 方案巾”。需要说】的是，分层嵌入压缩l l | 母个系数要处理很 多次，因而时间复杂性很大，在文献1 中基于自然图像的小波域统计规律，提出 了变深度嵌入压缩算法，在相同压缩性能的情况下降低了时间复杂性。 由于e z w 充分利用了小波变换图像的良好性质，引起了图像数据压缩领域的 广泛关注。针对e z w 的特点，有不少改进算法。具体来讲，改进策略主要在以下 几个方面：1 ) 关于量化或逐次量化策略的改进，见文献3 ；2 ) 关于零树的生成 和扫描方法的调整，见文献。”。”；3 ) 和人眼视觉特性相结合的小波变换压缩编 码，见文献。2 ”1 ；4 ) 高频和低频变换数据处理的改进上，见文献“驯”“：5 ) 和 其它压缩编码方法结合：与分形结合，与游程编码结合，与塔形编码和矢量量化 的结合，见文献m 5 m 6 m “”“州；等。 基于小波变换图像压缩编码如何和人眼的视觉特性相结合，如何选择适合人 眼视觉特性的小波基和相应的滤波器组，如何优化量化和编码过程的效率，以及 如何处理高、低频图像数据是值得进一步研究的方向。 u 了科技人学坝：i ：论义 总之，图像压缩编码算法在图像数字化处理的需求产生之后，在数字图像处 理、信号和信息处理、多媒体传输处理、通信与信息处理以及计算机相关专业技 术人员的共同努力下，已取得了丰富的研究成果，同时，也扩展了这一领域的研 究内容，具有很大的发展空间。在基于小波变换的矢量量化压缩编码算法领域有 很多有价值的工作可以展开，本文在对这一研究课题回顾和总结的基础上对一些 新的研究内容进行了探讨。 1 3 作者的主要工作 在整个硕士论文期间，重点在图像压缩编码中的矢量量化压缩编码和小波变 换压缩编码这两个方面进行了探讨，本文的主要工作和创新在以下几个方面： ( 1 ) 在矢量量化压缩编码方面，提出了一种基于模拟退火的l b g 改进算法并进 行了实验，验证了改进算法的合理性和有效性。 ( 2 ) 在矢量量化和小波变换压缩编码相结合方面，提出了一种基于视觉特性的 小波变换跨带矢量量化压缩编码方案并进行了实验，验证了方案的合理性 和有效性。 ( 3 ) 图像压缩编码算法的并行性改造方面，设计了一种基于数据分割的二维 d c t 图像压缩编码并行算法实现方案，并在p v m 实验环境下进行实验，验 证了算法的合理性和有效性。 1 4 本文章节安排 全文共分七章。 第一章是绪论，介绍本文所涉及课题的研究背景和意义、国内外研究现状、 作者的主要工作以及整个文章的章节安排。 第二章介绍图像压缩编码所涉及的理论基础知识：包括图像压缩编码的基本 原理以及一些常见的压缩方法和算法及其发展趋势，同时还介绍一些常见的涉及 图像或视频压缩的国际标准和建议，如j p e g 系列、m p e g 系列，以及i t 2 6 x 系列 等。 在第二章的基础上，本文重点就图像和视频的矢量量化压缩编码以及变换压 缩编码中的小波变换压缩编码这两个方面进行展开论述。所以接下来的内容沿着 矢量量化压缩编码和小波变换压缩编码以及两者的结合和并行算法考虑这些方 面来组织。 第三章主要针对作者在矢量量化压缩编码方面所做的工作进行介绍：包括矢 量量化压缩编码的基本原理和一些常见的算法，如l b g 算法、s o f m 算法等。在 u 了科技人学硕j ：论文 第三章重点介绍了本文作者提出的基于模拟退火算法的l 1 3 g 改进算法及其实验 效果。 第四章通过介绍小波分析的相关理论引入小波变换压缩编码及其算法 嵌入零树小波压缩编码算法( e z w ：e e m b e d d e dz e r o t r e e sw a v e l e t ) 。在这一章， 重点介绍了小波分析的基本理论以及基于小波变换的图像压缩编码算法，有很大 一部分是介绍性的。在这一章重点介绍了基于小波变换的嵌入零树小波压缩编码 算法。 第五章的内容主要是针对矢量量化和小波变换压缩编码两者相结合上所做 的工作来展 。重点介纠了本文作者所挺山的一种基于视觉特性的小波变换跨，黔 矢量量化压缩编码方案及其实验效果。 第六章主要是针对对上述算法效率上的改进考虑，从而做的一些关于并行性 改造的探讨和实验工作。主要是针对图像压缩编码中常见的d c t 算法的并行性改 造及其在图像压缩编码中的应用$ n 1 1 7 1 应的实验效果，重点介绍了本文作者提 的 一种基于数据分割的d e t 图像压缩编码并行算法设计和实现方案及其实验结果。 第七章是全文工作总结以及进一步的工作展望。重点介绍了本文作者在做硕 士论文期问针对所涉及的课题而产生的一些思路和想法。这也是本文作者今后进 一步工作的方向和考虑的重点。 基于小波变换的矢星量化图像压缩编码是与多学科有联系的交叉学科，其研 究范围十分广泛，在图像压缩中的应用的涉及面也很广，其中的许多理论和实际 问题还有待进一步解决，技术发展十分迅速，新的挑战层出不穷。而且，本文作 者从事这方面工作的时问不k ，在理论或者实践方面的知彭泖l 经验欠缺，文，i i 难 免存在彳i 少缺点和不足之处，敬请读者批评指正。 电予科技火学硕士论文 第二章图像压缩编码理论概述 2 1 图像压缩编码的必要性和可能性 。图像压缩编码的目的是以尽可能少的比特数表征图像，同时保持复原图像的 质量，使它符合预定应用场合的要求。压缩数据量，提高有效性是图像压缩编码 的首要目的。通常把图像压缩编码简称为图像编码。图像编码是一种信源编码， 其信源是各种类型的图像信息。图像信息的压缩有模拟和数字两种方法，但是山 于数字压缩方法具有模拟压缩方法无可比拟的优越性，目前绝大多数系统都采用 数字压缩方法，模拟压缩方法将逐步被淘汰。本文只讨论数字图像的压缩技术， 它的最大优点是可以实现高的压缩比。 数字图像通信有数字通信的一系列优点，如：可以中继传输和多次复制，不 会造成噪声和非线性失真的累积：便于进行加密；便于用v l s i 芯片实现，制作 方便、成本低、可高性高；便于和计算机联网等。既然数字图像通信有这么多好 处，为什么没有更早地得到推广和应用呢? 这主要是因为数字图像的数据量非常 大，若不经压缩，数字图像传输所需的高传输速率和数字图像存储所需的巨大容 量将成为推广应用数字图像通信的最大障碍。这就是为什么要进行图像压缩编码 的根本原因。 现以一路电视信号为例，看看它的数字化后的数码率。按c c i r 6 0 1 标准，数 字化后的分辨率为7 2 0 5 7 6 ，每秒2 5 帧，y ：u ：v 为4 ：2 ：2 。若以8 b i t 表示 y 信号，则每像素占1 6 b i t ，数码率为1 6 5 9 m b p s 。以6 4 k b p s 作为一个数字话路， 若不加压缩，为传输一路电视要占2 5 9 2 个有效数字话路。这在实际应用中是难 以接受的。若用一个容量为i g b 的硬盘或c d - r o m 来存储这样的数据，则只能存 储不到1 分钟的图像。并且，所需的高数据吞吐率是一般的硬盘和c d r o m 难以 达到的。若不经压缩，h d t v 信号的数码率可接近1 g b p s ，更加惊人。再以指纹库 为例，若以5 1 2 x5 1 2 8 b i t 的灰度图像来存储一个手指的指纹，一个4 0 万人的 指纹库，每人十指，则共需1 0 0 0 g b 的存储量。出这些例子可以看出图像压缩编 码的必要性。 图像信号可以压缩的根据来自两个方面：一方面是图像信号中存在大量冗余 度可供压缩，并且这种冗余度在解码后还可无失真地恢复：另一方面可以利用人 的视觉特性，在不被主观视觉觉察的容限内，通过减少表示信号的精度，以一定 的客观失真换取数据压缩。 图像信号的冗余度存在于结构和统计两方面。图像信号结构上的冗余度表现 电子科技大学硕士论文 为很强的空间( 帧内的) 和时间( 帧间的) 相关性。信号统计上的冗余度来源于 被编码信号概率密度分布的不均匀。 充分利用人的视觉特点，挖掘潜力，是实现码率压缩的又一途径。人跟对图 像的细节分辨率、运动分辨率和对比度分辨率的要求都有一定的限度。对于图像 信号在空间、时间以及在幅度方面进行数字化的精细程度只要达到了这个限度即 可，超过是无意义的。并且视觉心理学和视觉生理学的研究表明，人眼对图像细 节、运动和对比度三方面的分辨能力是相互制约的。在人观察景物时，并非对这 三方面同时都具有最高的分辨能力。当人眼对图像的某种分辨率要求很高时，对 其它的分辨率则降低了要求。利用这一特点，进行图像数字化时可以采用自适应 技术，根据图像的每一局部的特点来决定对它的取样频率和量化的精度，尽量地 做到与人眼在观看这种图像局部时所反映的视觉特点相适配。这种自适应技术不 是圃定不变地总是用最高的精度对图像取样和量化，而是把三中分辨率随时调整 到“够用，又不浪费”的程度，因此，可以在不损伤图像主观质量的条件下压缩 码率。图像编码技术就是要把种种压缩的可能性变成现实。 2 2 图像压缩编码基本原理和方法 图像编码的整个过程一般由以下三个步骤完成。第一步：对表示信号的形式 进行某种映射，即变换一下描写信号的形式，通过这种映射解除或削弱存在于图 像信号内部的相关性，降低其结构上存在的冗余度：第二步：在满足图像质量一 定要求的前提下，减少表示信号的精度，这通过符合主观视觉特性的量化来实现： 第三步：利用统计编码消除最终用于编码的信号所含的统计冗余度。 图像编码的过程可以概括成图2 1 所示。原始图像经映射变换后的数据再经 量化器和熵编码器成为码流输出。也就是说，图像压缩编码过程遵循“变换 量化( 熵) 编码”这三个处理环节，而图像压缩编码有关理论的展丌也就是 围绕这三个主题中的一个或几个来进行的。 剽f 姒尸 锄，n ) 剽f 殿换 锄，”j 量化 剿胞化映射后数据l 图2 i 图像编码的一般框图 量化后数据 复原的 熵编码 码流c ) i 信道 _ 。一 码流c ，j 量化后数据 熵解码 i b 予科技大学硕士论文 2 2 1 图像压缩编码的理论基础 若以复原图像是否与原图一致为标准，图像压缩编码可分为无失真编码和限 失真编码。本小节讨论这两种编码的基本理论。讨论中将不加证明地引用信息论 中的一些结论。 2 2 i 1 无失真编码 ：无失真编码又称信息保持编码，或叫做熵保持编码。它要求在解码端复原图 像和原图像完全一致，没有任何失真，或者在编解码过程中不丢失任何信息。若 在图2 1 中不引入量化器和反量化器，在传输过程中没有误码，映射和反映射的 精度足够高，舍尾误差可以忽略不计，则可以做到复原图像，r 1 ) 和原图像 f ( m ，行) 完全相等，均方误差施f 为零。 香农的无干扰编码定理1 在无干扰条件下，存在一种无失真编码方法，使编码的平均长度t ( x ) 与信源 熵h ( x ) 任意地接近，即无失真编码的平均码长存在一个下限。 几个基本术语 编码效率：玎= 警若，其中h ( x ) 为原始图像的熵，i ( x ) 为实际编码的平均 码长。 冗余度：r = 1 一r l 。 比特率：传输或存储一个像素平均所需的比特数。 压缩比：c ：旦，其中珂为原始图像的平均比特率( 或总数据量) ，压缩编 疗d 码后降低为由上述定理，不可能比t t ( x ) 小，故无失真编码可以达到的最 本压缩出为c m 。2 殇( x ) ，此式称为无失真编码条件。 独立信源的熵 熵就是每个符号的平均信息量。独立信源又叫无记忆信源，其特点是某个位 置出现某符号的概率与其它位置上出现的符号概率无关。设信源的符号表为 “，而，) ，各符号出现的概率为 尸( - ) ，e ( x ：) ，p ( x ，) ) ，则此独立信源的熵 为”。 h ( x ) = 一尸( 一) l o g ：p ( x ，) 独立信源的熵与符号出现概率相关，等概率分布时熵最大，此时用自然二进 i u 了科技人学颂i ：论文 码效率已经达到1 。符号不等概率出现时，若仍用等长码会降低编码效率，此时 改用不等长码，概率大的符号用短码，则可减少平均码长，提高编码效率。 条件熵 对实际信源，各符号相互并不独立，但可以把它看成是一个脚阶马尔可夫信 源。若按符号出现的时间顺序排列下标，当i j 符号以x 。表示，则截止当前时刻 的符号串为，x _ 。，x 。，x 。，x 。对于n l 阶马尔可夫信源，x 。出现的概率与 前i n 个符号x ，。x 一。有关，但与x ，以前的符号无关。也就是蜕，宅f 诵u 面胛个 符号已经给定为x 。，x 。的条件下，当前符号的条佴：概率为 在已知工。，x 的条件下，接收到当前符号x 。，所得到的信息量为 l ( x 。ix ，l ，x ) = 一l 0 9 2p ( x 。1x 。1 ，x ) 则已知x 。x 。的条件下收到一个x 。的”t 均信息量为 ，f i ( x 。i x 。， 一。) = 一p ( x 。k 。，h + 。) l o g ：p ( 矗h + ，x ，) j _ 2 r i 其中信源符号表x = ( 一，工：，x 。) 。考虑到x 。，x 序列发生的概率并对这些 x 。，x 的平均信息量取平均即为条件熵 h ( k k ，j ，) = p ( x 。k + ，k 。) i ( x 。i 稚，扎一，) h l 。o th 一- 。x i tx q = 一，e ( x 。， x 。) l o g2 尸( z f x 。一”一芦，) x - 2 x 、x - _ 2 x i 信源的联合熵( 商阶熵) 从联合概率p ( x 。，x 。，矗一。) 出发，可以定义信源的联合熵( 历h l 阶熵) h 。+ i = h ( x x ，i ，x ) j dj 一 = 一z e ( x n - i x n - m ) l 0 9 2p ( x 。稚， 一。) 2 x i5 2 x i h 。就是对价“个符号同时进行编码时所需比特数的下限。 条件熵和联合熵的关系”“ 条件熵和联合熵有以下关系： u 予科技人学硕1 ：论文 h ( x 。ix ，l ，x n - m ) = h 。+ l h 。 此式表明，在已知1 1 1 个符号后再对一个符号编码至少用的比特数。 2 2 1 2 限失真编码 概述 由香农的无干扰编码定理可知，无失真编码的平均码长存在一个下限，由于 这个下限通常比较接近自然码长，因此无失真编码的压缩比不可能很高。若能允 许编码有少量失真，则压缩比可大幅度提高，失真一般足出量化引起的。在限失 真编码中，一个自然的问题是，如果允许失真不超过某个值历这时压缩比有没 有一个上限，或者说为传输一个“符号”所需的平均比特数至少是多少? 有一种 观点认为，可以把量化器斫成是一个有噪信道，并根据信息沦中有关信息在有噪 信道中传输的一些结论来推导平均传输一个符号至少需要的比特数。信息论表 明，传输信道容量至少达到某个下限时，才能以小于口的失真传输信息。那么类 似地，可推出在编码时平均每个符号至少用多少比特编码才能使编码造成的失真 小于预定的夙 根据这个观点，率失真理论中的率失真函数实际上就是所求的比特率下限， 也就是说，压缩比存在着上限。 率失真函数斤佃j 根据率失真理沦，若函数斤佃j 存在，信道容量不小于宵j ，即可以传输 信息，而且使失真小于或等于夙这个函数称为率失真函数，它指出了在给定失 真下，信道编码所能达到的比特数下限。这取口足允许的失真。口可以用均方误 差，也可以用其它标准度量。斤佃，便是在允许失真d 下信源编码所需的最小平 均信息量，在这里可以认为是比特率。 定理( 信源编码定理) ”“：划一个率失真函数为r 佃) 的信源，若5 f 均火真 为历则必存在一种编码方法，使数码率r r ( d ) + 占，而平均失真d d + 占， 其中，s ，万为任意小的正数。 率失真函数与失真度量标准及信源统计特性有十分紧密的关系，信源不确定 性大，方差大，则所需比特数厅佃) 较大，信源平稳，方差小，则厅) 也小。 2 2 2 统计编码“ 在2 1 节中介绍过，进行图像数据压缩的途径之是压缩被编码传输的符号 ( 信源符号) 中存在的统计冗余度。根据各个信源符号出现概率不同进行概率匹 配编码，即统计编码，在不引起任何失真的前提下，可将传输每一信源符号所需 的平均码长降至最低。 u 了科技人学颁i 二论文 常见的统计编码方法有h u f f m a n 码，以及基于h u f f m a n 码的准可变字长编码 ( 双字长编码) ，还有就是算术编码等。 2 2 3 预测编码m 1 在经典的图像编码技术t 1 一，预测编码和变换编码是主要的两类编码方法。预 测编码的硬件实现比较简_ f 丫f ，而对于图像质量要求高的场合，采用预测编码，例 如，差分脉冲编码调制( i ) p c m ) 可以达到与变换编码同样程度的码率压缩。目前， 在视频序列编码中，进行时间轴冗余度压缩的主要手段是运动补偿帧问预测。 在预测编码时，不直接传送图像样值本身，而是对实际样值与它的一个预测 值间的差值进行编码、传送。如果这一差值预测误差被量化后在编护5 ，这种 预测编码方式叫d p c m 。d p c m 就是通过去除相邻像素间的相关性和减少对差值的 量化层数来实现码率压缩的。 在d p c m 系统中，预测器足关键。常用的一种预测器优化设计准则l i t l 做最小 均方误差( 埘幅e ) 准则，它要求所选用的一组预测系数a ，口：，a 。能使图像中预 测误差的均方值最小。 2 2 4 变换编码“” 变换编码的基本思想是将在通常的欧几里德几何空间( 空间域) 描写的图像 信号变换到另外的j 下交向量空间( 变换域) 进行描写。如果所选的正交向量空间 的基向量与图像本身的特征向量很接近，那么同一信号在这种空问中描写起来就 会简单得多。空间域的一个n n 个像素组成的像块经过正交变换后，在变换域 变成了同样大小的变换系数块。变换前后的明显差别是，空问域像块中像素之间 存在很强的相关性，能量分布比较均匀：经过j 下交变换后，变换系数间近似是统 列独立的，相关性基本解除，并且能量主要集巾在直流和低频的变换系数上。这 样一个解相关过程也就是冗余度压缩的过程。在经过正交变换后，再在变换域进 行滤波、与视觉特点匹配的量化及统计编码就可以实现有效的码率压缩。 1 9 6 8 年丌始出现了用快速算法的离散傅立叶变换( f f t ) 进行二维图像编码， 而后又提出了不少其它类型的离散正交变换用于图像编码，如沃尔什一哈达码变 换、哈尔变换、k l 变换、斜变换、余弦变换等。这些变换，除了k l 变换之外， 都有快速算法。k - l 变换采用图像本身的特征向量作为变换的基向量，因此与图 像的统计特性完全匹配，足在最小均方误差准则寸，：图像压缩的蛀佳变换，但 因变换矩阵随图像而异，无快速算法。 在各种正交变换巾，当以自然图像为编码”勺时，j jkl 变换性能最接近的 u 了科披人学顺一i ：论文 是离散余弦变换( d c t ) 。d c t 目前已被多种静态和活动图像编码的国际标准建议 所采用。实验表明，对于自然图像，像块尺寸选8 8 或1 6 x 1 6 是合适的。像块 尺寸取得再大，需要的计算量和存储量增加而压缩效率增加不多，而像块再小压 缩效率明显下降。在国际标准建议c c i t ti i 2 6 1 、j p e g 、m p e g 中都采用8 8 的 像块做d c t 。 经过正交变换解相关后，进一步的数据压缩依靠区域滤波，匹配主观视觉特 性的量化和变字长编码等步骤来实现。 2 2 5 序列图像编码与运动估值和运动补偿州 电视信号的- 跌内编码利用图像信号的空问相关性实现信息压缩，而帧问编码 则是利用图像信号存时问轴 ：的相关性来实现信息_ i ；= 缩。统计测景表明，当景物 不含剧烈运动，不发生场景切换以及摄象机不做明显运动如推镜头( z o o m i n g ) 、 摇镜头( p a n n i n g ) 时，电视信号的帧差信号( 相邻帧间空阳】位置对应的像素差 值) 比帧内相邻像素问的差值信号具有更为尖锐的，以0 为中心的l a p l a c e 分布， 即表现出更强的相关性。 但是，山于电视信号中运动事件的存在，直接利用帧差信号编码也带来一些 问题。当场景中有快速运动物体存在时，由空间几何位置对应的像素值相减得到 的帧差信号的幅度会剧烈增加。如图2 2 所示，第k i 帧里，中心点为“，y ) 的 运动物体，若在第k 帧移动到中心点为( 一+ d x ，y 。+ d y ) 的位冠，其位移矢量 d = ( d x ，d y ) 7 。如果直接求两帧问的差值，则由于第k 帧的( 一+ d x ，y 。+ 咖) 点( 运 动物体) 与第k l 帧的对应点( 背景部分) 问相关性极小，所得差值幅度很大。 与此同h 于，第k 帧的( x ，y ) 点( 背景部分) 与笫k l f 跌对应点( 运动部分) 水 差值，也出现同样的问题。但是，若能对运动物体的位移量进行运动利- 偿，即在 图2 2q 1 将第k 帧( x ，+ d x ，y l + d y ) 点的运动物体移回到( x ，y 。) 点，- 耳与第k l 帧求差值，显然会使相关性增大，差值信号减小，从而提高压缩比。为了实现这 一目的，必须事先估测场景中运动物体的位移量，即进行运动位移估值。 在电视信号编码方面，运动位移估值的两个主要应用是运动补偿帧问预测与 运动自适应帧内插。在图像编码领域目前使用的运动估值算法有块匹配法、像素 递归法、相位相关法以及针对出摄象机运动引起图像全局运动的全局运动参数估 值等。其中块匹配法是最常用的一种方法，在运动视频编码的西际标准t 1 2 5 1 、 c c i r 7 2 3 、m p e g l 、m p e g 2 中实际都采用块匹配法做运动估值。 u 了耳 技人学坝：1 1 论文 2 2 6 子带编码“5 冈2 2 运动物体的帧问位移 子带编码的基本思想是在发送端将图像信号在频率域分裂成若二f 。r 带 ( s u b b a n d ) ，而后对每一个子带用一个与其统计特性相适配的编码器进行图像数 据压缩：在接收端，则将解码后的各子带信号综合成重建图像。1 9 7 6 年予带编 码技术首次应用于语音编码，1 9 8 6 年w o o d s 等将子带编码又引入到图像编码， 此后子带编码在视频信号压缩领域得到了很大发展。 予带编码有三个突出优点：1 ) 一个子带内的编码i 噪声( 失真) 在解码后只 局限于该子带内，不会扩散到其它予带，这样，即使有的子带信号较弱，也不会 被其它予带的编码噪声所掩盖：2 ) 可以根据主观视觉特性，将有限的数码率在 各个予带之间合理分配，有利于提高图像的主观质量。因此，在相同的压缩比下， 子带编码的图像质量略高于不划分子带而九接作d c t 编码的图像质量；3 ) 通过 频带分裂，各个子带的取样步砸率可以成倍下降。例如，若分成频谱面积相同的n 个子带，则每个子带的取样频率可以降为原始图像信号取样频率的1 n ，因而可 以减少硬件实现的难度，并便于并行处理。 子带编码由于其本身具备的频带分裂特性，非常适合于分辨率可分多级的视 频编码。有关子带编码的相关内容及其应用在本文的第四章还将继续展丌睑述。 2 2 7 图像压缩编码的其它算法 目前，图像压缩编码的理论和算法研究获得了巨大的进展，除了上面介绍的 一些经典的编码方法之外，还有模型编码、金字塔编码、小波变换编码、欠量编 u _ 了科技人学帧i ：论立 码等方法。一些代表性的算法包括：