（电路与系统专业论文）小波分析及在数字图像压缩中的应用与研究[电路与系统专业优秀论文].pdf

摘要 随着计算机多媒体技术的发展，人们期望更高性能的图像压缩技术的出现。出于图 像存储技术和图像通信的考虑，良好的图像压缩技术不仅能够实现高压缩率和高保真 率，还能满足诸如渐进传输、图像渐现等网络应用的需要。因此，为了满足实际应用的 需要，有必要对图像数据压缩处理进行深入细致的研究，目前已发展成为专门的研究领 域：图像编码。常见的主要编码方法有预测编码、变换编码、矢量量化编码、小波编码、 分形编码等等。 小波变换不仅可以去除图像数据中的相关，而且它提供了利用人眼视觉特性的良好 机制，因此基于小波变换的图像压缩技术己成为当前的研究热点。本文详细研究了基于 小波变换和矢量量化的静态图像压缩编码方法。首先，本文给出了图像压缩的一般概念， 回顾了图像压缩技术的发展，并简要介绍了几种常用的图像压缩编码方法。然后，从信 号处理的角度介绍了小波变换，并通过实验的方法研究了其在图像压缩中的应用，包括： 小波基的选择、边界延拓方法以及图像小波系数的分布特点等。接下来，本文详细研究 了小波树嵌入图像压缩编码算法，包括经典的嵌入零树编码( e 2 w ) 算法和在其基础上的 集分割树( s p i h i t ) 算法和x 树图像编码。并根据e z w 算法在量化过程中存在的问题，提 出了一种改进的零树量化编码算法。 最后，在小波树的基础上，通过对矢量量化的研究，本文提出了一种基于四叉树结 构新的小波树矢量量化压缩编码算法，实验证明，在较高压缩比的情况下，使用此方法 得到的重构图象质量( 视觉效果和峰值信噪比) 比通常的小波压缩算法有了较大的提高。 关键词： 图像编码；小波变换：嵌入零树编码：矢量量化 n 小波分析及在数字图像压缩中的应用与研究 a b s 仃a c t w i 血t h ee v e r - g r o w i n gm u i 血n e d i at e c h n i q u e ，p e o p i ea r el o o k i n gf o r w a r dt on e wi m a g e c o m p r e s s i o nt e c h i l i q u e s 、i t l lb e 他rp e r f i o n 卸c e t a k i n gt h es t o r a g ea 1 1 dt r a _ n s f e ro fm a s s i m a g ed a t ai m oc o n s i d e r a t i o n ，肿to i l l yc o u l df 打o r a b l ei m a g ec o m p r e s s i o nt e c l l i l i q u e s a c h i e v eh i 曲c o m p f e s s i o nr a t i oa n df i d e l i t y ，t l l e ys h o da l s om e e tt 1 1 ed e m a n d so fw c b 印p l i c a t i o n s ，i m a g ec o m p r e s s i o nn e e d 铀曲e rd e t a i l e ds m d y ，t l l u sh a v i n gd e v e l o p e di n t oa s p e c i a l i z e dr e s e a r c h 矗d dk r l o w na si m a g ee o d i n g f r e q u e n t l yu s e dm 萄o rc o d i n gm e m o d s i n c l u d ep r e d i c a lc o d e ，t r a n s f l o mc o d e ，v e c t o lq u a n t i z a t i o n ，w a v e l e t 仃a 1 1 s f o mc o d e ，f h c t a l c o d e e c t 。 t h ew a v e l e tt r a n s f o m a t i o nc a np r o v i d eag o o dm e c h 枷s mt oe x p i o r eh u m a nv i s u a l s y s t e m ，w h i l ei tr e m o v e st 1 1 ed a t ac o r r c l a t i o ni ni m a g e s ot h ei m a g ec o m p r e s s i o nc o d i n g a l g o r i t h mb a s e do nw a v e l e t 姐n s f o m a t i o n h 嬲b e c 姗er e s e a r c l l i n gh o t s p o ti nr e c e n ty e a r s i nm i sd i s s e n a t i o n ，ai m a g ec o m p r e s s i o nc o d i n gm e t l l o db a s e do n 啪v e l e tt r a n s f o m a t i o na 1 1 d v e c t o r q u a m i z a t i o ni s d i s c u s s e di nd e t a i l f i r s t l y ， t l l e g e n e m lc o n c e p t i o n o fi m a g e c o m p r e s s i o ni sp r e s e n t e d ，t 1 1 eh i e fd e v c l o p i n gh i s t o r yo fi m a g ec o m p r e s s i o nt e c 王l 【1 i q u ei s r e v i e w e da n ds e v e r a li m a g ec o m p r e s s i o n 越g o r i m ma r ei n 廿0 血c e db r i e n y t h e n ，t l l e c o n c e p t i o no fw a v e l e t 拄a n s f o 椭a _ 七i o ni si n 仃o d u c e df r o m 也ev i e w p o i n to fs i g i l a lp r o c e s s i n g ， a i l di t sa p p l i c a t i o ni nh a g ec o m p r e s s i o n ，i n c l u d i l l gt l l es e l e c t i o no fw a v e l e tb a s i sa 1 1 dt h e d i s t r i b u t i o no f w a v e l e tc o e f i c i e n t s ，i sr e s e a r c h e db y 1 ee x p e r i m e n t a lw a y s t h e n ，w ef o c u so n e m b e d d e dw a v e l e t a l g o r i t ，i n c l u d e e m b e d d e dz e r o l f c e sw a v e l e t a l g o r i t h n l ，s e t p a n 试o n i n gi nh i e r a r c h i c a lt r e e sa l g o 咖1 n 1a n dx - t r c ei m a g ec o d i n ga l g o 珊l i l l t 1 1 r o u 曲 a n a t o m i z i n ge z wc o d i n ga l g o r i 恤n a n dt 描n g 也ee 髓c t so fh u m a l l b e i n g s v i s i o n c h a f a c t e r i s t i c so nq u a l i t yo fr e c o n s t i t u t 访gi m g e ai m p r o v e dz e r e t r e e sa i g o r i t l l ma r ep u t f o n a r d ” a tj a s tan e wi m a g ec o m p r c s s i o ne n c o d 协ga l g o r i t h mb a s e do nw a v e l c t 舰n s f o r n la n d v e c t o rq u a l l t i z a t i o ni sp u tf b n v a r d t h ee x p e r i m e n ts h o w ，i nv e r yl o wb i tr a t e ，u s i n g l e p r o p o s e da l g o r j 血m ，t l l er e c o n s t n l c t e di m a g ei ss u p e r i o rt ot h a to fe z w i nb o t ho fp e r c e p t i o n a n d p s n r k e y w o r d s ：i m a g ec o d i n g，w a v e l e tt r 趾s f b 珊， e m b e d d e dz e r o 仃e e s c o d i n g，v c c t o r q u a l l t i z a t i o n ， u i - 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名 弘) 智 日期：弘衫年牟月f ，日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阕。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 ， 2 、不保密曰。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 萝) 窘 日期：沙年手月f ，日 、曼日期： 年月日 第一章绪论 1 1 图像压缩的基本原理及研究现状 1 1 1 图像数据压缩的必要性 在当前这样一个信息爆炸的社会中，人们在交换图像声音等媒体信息方面的 需求越来越大，对交换的质量要求也越来越高。通常图像经数字化后形成的数据 量非常大。例如，一副分辨率为1 0 2 4 7 6 8 的2 4 b i t 真彩色静止图像，就有2 3 6 m b 的数据量。如果进行视频处理，假设每秒3 0 帧，则每秒产生近7 0 m b 的数据，也 就是说，一张普通的光盘只能容纳9 s 的图像。 就图像的传输来说，工业监视系统中的黑白视频信号的数据量也非常的庞大， 我国黑白电视是每秒传送2 5 幅画面( 帧) ，每帧6 2 5 行，采用隔行扫描分成两场， 每场3 1 2 5 行，其中2 5 行为消隐时间，故每场有效信号是2 8 7 5 行，前一场传奇 数行，后一场传偶数行。因为显示屏的宽度与高度比为4 ：3 ，所以每行有( 4 3 ) 6 2 5 = 8 3 2 个象素，整个屏幕由6 2 5 8 3 2 = 5 2 0 0 0 0 个象素组成，故视频信号为 2 5 5 2 0 0 0 0 2 = 6 5 m h z 如果p c m 用于数字信号，每个取样值若用2 5 6 个量化层。对 每个象素用r = 8 比特编码，则p c m 黑白电视传输码率为9 6 m b s 。 面对数据量如此巨大的数字化图像的传输、存储、处理和交换等问题，图像压 缩编码成为当今通信与信号处理领域中的一个重要研究课题。 1 1 2 图像压缩的基本概念 所谓压缩，其实就是考虑一种实现方法，髓够去除掉整个图像数据中无关的 或者是重复的数据( 即冗余量) ，最终用较少的信息量就可表达出原图像。 图像能够进行压缩的依据主要是图像数据中存在冗余，如下式表示： ，= d 一咖 ( 1 1 ) 其中，d ，幽分别为信息量，数据量与冗余量。 上式中所涉及的冗余主要包括： 1 空间冗余。在一幅图像中，规则物体和规则背景( 所谓规则就是指表面 有序而不是完全杂乱无章的排列) 等所具有的相关性，应用一些算法提 取并减少这些图像象素之间的相关性就可以达到数据压缩的目的。 2 时间冗余。这是指序列图像( 电视图像，运动图像) 所包含的相邻图像 之间的相关性。 3 结构冗余。有些图像有着非常强的纹理结构，如草席的图案等，称之为 结构上的冗余。 硕士学位论文 4 知识冗余。某些图像的理解与基础知识有很大的相关性，如人脸固定结 构。对这些冗余称之为知识冗余。 5 视觉冗余。人眼接收信息能力是有限的，对图像的分辨能力也是有限的， 冗余根据这种特性去掉或减弱无用或不敏感的信息，从而达到压缩的目 的。 6 信息熵冗余。根据数据的统计结果对数据重新分配比特数，从而达到数 据总量的减少。 1 1 3 图像压缩技术研究的起源与发展 图像压缩的研究起源于2 0 世纪4 0 年代。1 9 4 8 年，0 l i v e r 首先提出了电视信 号的线性p c m 理论，开辟了图像压缩理论的先河。随后，1 9 5 8 年g r a h a m 采用计 算机模拟试验的方法，提出了静止图像压缩的前值预测编码法，该方法能获得约 4 b i t s p i x 的图像质量。7 0 年代a h a b i b i t 进行了帧问预测编码的研究，并在8 0 年 代初针对运动补偿( m c ) 所用的运动估值( m e ) 进行了研究。 这些早期的预测编码方法都是对象素为处理单元，其理论是线性预测理论。 这些预测理论的思想至今仍被广泛应用，但由于预测编码的最小方差不能反映人 的视觉特性及它的压缩比的限制，导致其在9 0 年代开始被编码效率更高的变化编 码所取代。 1 9 6 8 年h c a n d r e w s 等人提出了变换编码的概念，采用的是二维离散傅立叶 变换。此后相继出现了用其它变换方法的变换编码，其理论基础是把图像看成广 义平稳随机场，用线性变换去实现相关，如k l 变换，d c t 变换等。其实现方 法均是通过正交变换把图像从相关性很强的空间域变换到相关性很弱的频域，再 保留方差较大的变换系数，忽略方差较小的变换系数，从而实现图像压缩。 1 9 9 0 年通过的i t u t & h 2 6 l 建议，是图像编码技术走向实用化的重要一步。 它是图像编码4 0 年研究结果的结晶。9 0 年代初相继提出的m p e g 1 ，m p e g 2 h 2 6 3 等等都是在h 2 6 1 的基础上发展和改进的。这些国际建议普遍采用的混合编码技 术是当今最实用的高效编码方法，得到了广泛的推广应用，已成为当今图像编码 方法的主流。 但基于线性方法( 预测法和分块d c t 相结合) 的h 2 6 1 m p e g 的核心算法既 不能有效的反映图像的固有统计特性，也不能有效的反映人们的视觉特性，这两 方面还有待理论上的突破。因此，随后人们针对这两方面的不足进行了深入的分 析和研究提出了许多新的理论和方法。 目前已提出和正在进行研究的图像编码方法列举如下： 1 小波变换图像编码。 2 利用人工神经网络的压缩编码。 小波分析及在数字图像压缩中的应用与研究 3 利用分形集合的图像编码( i f s 编码) 。 4 利用数学形态学的图像编码等。 1 2 本论文的研究背景 长期以来，傅立叶变换一直是信号处理的核心，但由于傅立叶变换存在严重 的局限性( 傅立叶变换在频域上定位是非常准确的，而在时域上无任何定位) 。 对一些常见的非平稳的信号没有有效的处理方法，在这种情况，小波变换在数学 家和工程人员的共同研究下诞生。1 9 8 7 年，m a l l a t 将计算机视觉领域内的多尺度 分析思想引入到小波分析中，小波函数的构造以及信号按小波变换的分解与重构， 其相应的算法【卜3 】( m a l l a t 算法) 有效的应用于图像的分析与重构。与此同时， d a u b e c h i e s 构造了具有有限紧支集的正交小波基。这样初步建立了小波理论。 近几年来，小波技术成为科学研究的一个热点，它不仅在数学上已形成了一 个新的分支，而且在应用上，如信号处理、图像处理、模式识辨、量子物理以及 众多非线性领域都具有良好的局部化特性，而且由于对高频采取逐渐精细的时频 或空频域，从而可以聚焦到分析对象的任意细节，因而获得了“数学显微镜”的美誉。 由于小波变换具有空一域局部化，能量压缩性，子带内小波系数的聚类性， 子带间小波系数的相似性，小波系数幅度从低频子带到高频子带的衰减性，和人 类视觉特性相匹配等性质，因此小波变换的数据结构非常适合编码的要求【4 1 。近几 年，小波图像压缩取得了巨大的成功，这些算法都是成功使用了各自不同具有创 新的策略，更好的组织和表示了塔式结构的小波系数，从而更好和更完整的利用 了小波系数所具有的统计特性，在这些算法中，应用比较广泛的有s h a d i r o 提出的 嵌入式零树小波( e z w ) 编码算法和在其基础上改进的s p i h i 算法。 1 。3 本文所做的具体工作及研究方法概述 1 对小波理论进行了较深入的研究，采用双正交小波基( b i o r t h o g o n a lw a v e l e t ) 对图像进行分解，对经典的小波基进行了仿真实验，经过峰值信噪比( p s n r ) 和主 观效果的对比找到一组适合于本文算法的小波基。 2 对嵌入式零树【5 】( e z w ) 算法做了系统的阐述和验证，并在该算法的基础上， 综合比较了各种最新小波树编码技术算法，并对嵌入式零树编码方案进行了改进。 3 通过小波树结构内相关性的研究，提出了一种基于四叉树结构新的小波树与 矢量量化相结合的压缩编码方法。该方法对低比特率图像压缩有明显的改进。 1 4 本文的结构 木文的安排如下： 第1 章介绍了课题的研究背景，主要包括图像编码的必要性和可能性，图像压 缩编码的起源与发展。 第2 章对目前已有的多种静态图像压缩编码方法进行了比较分析，如变换编 3 硕上学位论文 码、矢量量化编码和分形编码等。 第3 章通过小波变换的介绍，分析了小波的多分辨率分析特性和时频局部化特 性。经过分析后得出小波变换应用于图像压缩的本质特性和本文采用小波变换用 于图像分解的原因。 第4 章对基于小波变换的e z w 算法、s p i h i t 算法m 1 、x 树图像编码算法1 进 行了详细的分析与讨论。并对e z w 算法进行了改进。 第5 章在对矢量量化l b g 1 算法进行分析的基础上，提出了一种基于四叉树 结构新的基于小波树的矢量量化压缩编码方法，该算法特别适合于要求高压缩比的 图像。 小波分析及在数字图像压缩中的应用与研究 2 1 信息论基础 第二章数字图像压缩编码技术 1 9 4 8 年，s h a i l n o n 发表了通信的数学原理，应用概率论对信息作了定量的描述。 作为s h a n n o n 信息论的研究对象一信息，被假设为由一系列的随机变量所代表，它 们往往用随机出现的符号来表示。我们称输出这些符号集的源为“信源”。由信源输 出的随机符号，如果其取值于某一连续区间，就叫连续信源；如果取值于某一离散 集合，就叫离散信源。我们研究的是数字化系统，均为离散信源，本文讨论的数 字图像为离散空间函数x ( x ，们。 2 1 1 自信息量和一阶熵 记字符玎，出现的概率为p ( 口，) ，那么按概率的公理化定义必须有 o s p j 1 ( ，= 1 ，2 ，m ) p j = l ( 2 1 ) 则s h a n n o n 信息论把字符出现的自信息量定义为 j ( 口j ) = 一l o g 所 ( 2 2 ) 式中的符号可以保证其为正值。在计算机科学系统中，通常对对数的底取2 ， 单位为比特( b i t ) j ( 口，) 亦称为自信息函数，其含义是：随机变量x 取值为d ，时所携带的信息的度 量。 我们把信息量的概率平均值，即随机变量j ( 口，) 的数学期望，叫做信息熵或者 简称熵( e n t r o p y ) ，记为 日( ) = p ，) = 一所l o g p ， ( 2 3 ) j 一1，= 1 单位为比特字符，通常也称为一阶熵，它代表每个字符所给出的平均信息量。 于是，日( x ) 就是离散信源进行无失真编码的基本极限( 不经映射变换，只作熵编 码1 。 2 1 2 压缩基本方法之一一概率匹配 如果对字符d ，的编码长度为三，则显然三，也是一个非负的随机变量，不妨记 做： 三j = 一l o g g j( o q l ，j _ 1 ，2 m ，吼= 1 ) ( 2 4 ) j = l 那么对信源爿，编码的平均码长就是 硕士学位论文 ，= p ，上，= 一p ，l o g g ， ( 2 5 ) 而信息论中已经证明熵有极值性，即 ( x ) = p ，( 口，) = 一p ，l o g p ， ( 2 6 ) j = 1j = l 其中等号仅在p ，= g ，时成立。这就告诉我们，对于离散无记忆源，必须准确 得到字符集率，对各字符的编码长度都达到它的自信息量。在式( 2 6 ) 中，若令 q ，= 1 m ，便得到最大离散熵定理，所有概率分布p ；所构成的熵，以等概率时为最 大。即： ( x ) l o g m ( 2 7 ) 在数字化系统中，通常使川= 2 “。若各字符以等概率出现，则 p ( 口，) = 1 2 8 = 2 ，则( d ，) = 一1 0 9 2 = r ( 6 疗) ，此时可以说，r 的二进制码字包含 有r b i t 的自信息量。对2 5 6 级灰度图像，样本数目为m = 2 5 6 ，最大熵为8 b i t 字符， 如果各字符以非等概率出现，日。就减少。因此，最大值与熵之间的差值，就是信 源x 所含有的冗余度( r e d u n d a i l c y ) ，即 ，2 h 一( x ) 2 l o g m h ( ) ( 2 8 ) 由此可见，离散无记忆信源的冗余度隐含在信源字符的非等概率分布之中。 只要信源不是等概率分布的，就存在着数据压缩的可能性。 在数据压缩技术中，般将压缩前每个信源字符的编码位数( 1 0 9 拼) 与压缩后 每个字符的编码位数( ，) 之比，定义为数据压缩比( c r ：c o m p r e s s i o nr a t i o ) ：l o g7 形( 2 9 ) 也可以使用c r 的倒数来衡量压缩效果，称为压缩率。 2 1 3 压缩基本方法之二一条件概率 若信源x 的各分量不是相互独立的，就称为有记忆信源，实际上信源大多是这 种信源。在遮掩的一个信号序列中，任意字符的出现总是要附带的接触前面的或 后面字符的若干不确定性，即各字符是相关的，要用条件概率和条件熵的方法来 处理。而且，字符间的相关性越强，对前面的字符知道的越多，下一个字符的信 息量越小因此，对于离散有记忆信源，可以利用条件概率进行编码，减少信源的 极限熵 2 2 无损图像压缩编码 无损图像是利用数据的统计特性，在无损压缩中，压缩后重建图像其数值等 于原图像。虽然无损压缩没有信息丢失，达到理想要求，然而只能实现适量压缩。 小波分析及在数字图像压缩中的应用与研究 无损压缩的压缩率一般为2 ：卜一5 ：1 。典型的无损压缩技术有游程编码、l z w 编 码、霍夫曼编码和算术编码旧1 等。 2 2 1 游程编码 游程编码i lo j ( r l c ) 是对传真图像的标准压缩方法。它的基本理论是对一组 从左到右扫描得到的连续的0 或1 游程用它们的长度来编码。这里需要建立确定 游程值的协定，常用的方法有：1 指出每行第一个游程的值；2 设每行都由白色游 程开始。通过用变长码来对游程的长度编码有可能取得更高的压缩比。我们可将 黑和白的游程长度分开，并根据它们的统计特性分别用变长码编码例如符号口，是 由某个想象中的黑色游程信源产生出来的概率。用类似的方法就可得到白色游程 信源熵的估计h 。这样图像的游程熵就近似为： 玎j 玎 日n = 芸毕 ( 2 1 0 ) “+ l 。 其中变量厶和三。分别代表白色和黑色游程长度的平均值。 2 2 2l z w 编码 同r l e 类似，它也是对字符编码从而实现压缩。然而与r l e 不同的是，它在 对文件进行编码的同时，生成了特定的字符序列的表以及它们对应的代码。例如， 一个由8 位字节组成的文件可以被编成1 2 位的代码。在这4 0 9 6 个可能的代码中， 2 5 6 个代码代表可能的单个字符( 8 位) ，剩下的3 8 4 0 个代码分配给在压缩过程 中数据里出现的字符串。 每当表中没有的字符串头一次出现时，它就被原样存起来，同时将分配给它 的代码一起保存。之后当这个串再次出现时，只将它的代码存起来。这样就去掉 了文件冗余信息，不但字符表在压缩中动态生成的，而且字符串表也不必存在压 缩文件中，因为解压缩算法由信息中文件重构它。 2 2 3 霍夫曼编码 霍夫曼( h u f f m a n ) 编码是消除编码冗余最常用的技术，其原理如下： 设一个信源的符号是a ，通过把两个概率最小的字符组合起来，就得到一个新 的信源。它的符号个数为a 一1 。假设这个新信源的编码字是已知的，那么可以证 明：新信源中还没有组合起来的符号的编码字等于原来信源中对应符号的编码字： 而两个组合符号的编码字，可以通过在新信源中组合符号编码后，为“0 ”或“l ”得到， 因而霍夫曼编码由只有两个符号“o ”和“1 ”组成的编码。 根据以上原理，可以得到如下构造霍夫曼编码的方法： 1 反复组合两个最小概率的符号，得到一个新的简化信源，直到被简化的 信源中只有两个符号，分配这两个符号编码为“o ”或“1 ”。 硕士学位论文 2 反复的求出最小概率编码字的两个组合符号编码，通过在上一步中求出 编码右侧加上“o ”或者“1 ”直到找到原来信源。 一旦霍夫曼码获得后，编码或者简码都可以用简单的查表方式实现。这种码 有三个特点：1 它是一种块码，因为各个信源符号都被映射成一组固定次序的码 符号；2 它是一种即时码，因为一串码符号中的每个码字都可以不考虑其后的符 号解出来：3 它是一种可唯一解开的码，因为任何符号串都只能以一种方式解。 根据这些特点，任何霍夫曼码都可通过从左到右检查各个符号进行解。然而，霍 夫曼编码使用整数个二进制位对符号进行编码，实际上这种方法在许多情况下无 法得到最优的压缩效果。假设某个字符的出现概率为8 0 ，该字符事实上只需要 o 3 2 2 位编码，但霍夫曼编码一定会为其分配一位0 或一位l 的编码，整个信息的8 0 在压缩后都几乎相当于理想长度的3 倍左右，压缩效果很不理想，而算术编码可克 服这个问题。 2 2 4 算术编码 算术编码的思想最早由香农提出，当时香农将符号依概率排序，用累积概率 的二进制表示作为对符号的编码。之后，经r i s s a n e n 、p a s c o 和l a n g d o n 等人的研究， 算术编码日臻成熟。1 9 8 7 年，w i t t e n “等人发表了一个实用的算术编码器，即 c a c m 8 7 。自此以后，这一技术引来越来越多人的注意，被认为是基于统计的、无 损数据压缩效率最高的方法，几乎总强于霍夫曼编码。 算术编码是用【0 ，1 ) 间的一个实数间隔来表示符号序列。符号序列越长，间隔 越小，表示它的数据位数就越多每编码符号序列的一个符号，都依该符号出现的 概率进一步缩小间隔，而且出现概率大的符号比出现概率小的符号缩小间隔得较 少，因此需要在表示它的数据上加入较少的位数。 在符号被编码前，间隔为整个区间l o ，1 ) 。每编码一个符号，以分配给该符号的 比例将间隔缩小。算术编码的过程实际上就是依据信源符号的出现概率对区间进 行分割的过程。下面以一个例子具体说明该过程。假定信源的符号集为： 口，p ，f ，d ，甜，! ，各符号的出现概率和分配的区间见表2 1 。需要编码的符号序列为： p d f 扎当编码第一个符号时，编码器将区间缩小为分配给符号g 的区间l o 2 ，o 5 ) 。 当编码第二个符号口时，编码器以分配给口的比例( 【o ，o 2 ) ，相对于整个区间【o ，1 ) ) 将区间 0 2 ，0 5 ) 缩小，得到【o 2 ，0 2 6 ) 如此进行，直至最后一个符号被编码，我们可 得到最终缩小的区间为：【o 2 3 3 5 4 ，o 2 3 3 6 ) ，如图2 1 所示。 解码是编码的逆过程。如果解码器收到的区间为【o 2 3 3 5 4 ，0 2 3 3 6 ) ，因为该区 间完全落在信源模型分配给符号8 的区间内( 表5 3 ) ，解码器立即可以译出第一个符 号为e 。然后，解码器将区间缩小为【o 2 ，o 5 ) ，因为接受到的区间落在符号a 的区间 o 2 ，o 2 6 ) 内，所以可译出第二个符号为口。以此类推，可译出所有的码来。 小波分析及在数字图像压缩中的应用与研究 表2 1 编码符号概率表 信源符号符号的索引出现概率分配的区间 a60 2 【o ，0 2 ) e 5 0 3 【o 2 ，0 5 ) i40 1 【o 5 ，0 6 ) o30 2 【o 6 ，0 8 ) u20 1 【o 8 ，0 9 ) f 1 0 1 【o 9 ，1 ) 开始 o o 5 ，0 2 6 口f i 口f f jj i 暑 一 口 - - 0 2 o 2 3 ，- 2 3 3 6 vl o | i 2 3 3 图2 1 算术编码流程图 显然，无须传输编码区间的两个端点，因为该区间内的任何一个点都能够译 出正确的码来。但是，解码时会碰到一个问题：如何判断消息的终点? 例如，数据 o 0 可以表示n ，日，4 口口中的任何一个。解决这个问题的办法是在消息的末尾加入 一个特殊的表示消息结束的符号e o f ，如在上例中的符号! 。解码器一碰到该符号 就立即停止饵码。 2 3 有损图像压缩 有损压缩方案，容许图像的质量有所下降，但与无损压缩相比，它的编码比 特率有较大的改善，而且重建图像的质量相对于人眼的视觉特性并没有明显的下 降。有损图像压缩可以达到几十倍的压缩比。通常有损图像压缩编码方案有变换 编码、预测编码和矢量量化编码( v q ) 等2 3 1 2 3 1 失真度理论和有损压缩 信息源的编码率性能界限( 即信号源的熵) 取决于无损编码的数据。在许多 实际情况下，编码后重建图像存在一定程度的失真( 即图像降级) 是允许的。 在保持某一图像级水平时，对给定的图像信息源编码所需要最小比特率时多 ，材 ， 掌 4 弘 融 曩 船 o l ，州il o ， ，球 d j 婴圭竺竺兰兰 大? 回答这一一问题是信息论中一个分支要解决的问题，即失真度理论所讲的一个 基本问题。失真度理论为达到某一高保真度标准的有损压缩建立了一个理论的性 能界限。对于广播级的失真度，计量以及信息源的模型，这一理论提供了具有一 下性质的失真度方程胄( d ) ： 1 对于任何级别的失真度d ，可以找到一种编码方案，其比特率可以任意接 近r ( d ) ，其平均失真度可以任意接近d ； 2 不可能找到一种编码方案，使得编码比特率比月( d ) 低，而失真度是d 或 者更好，可以证明，r ( d ) 是一个u 型的，连续单调下降函数。 对于具有有限个字符的离散信号源，由图2 ，2 可以看出其典型的失真度特性： 1 当d = o 时，无失真r ( d ) 的值大于或等于信息源的熵。 2 一般来说，比较复杂的编码方案可以较好的刻画信息源的统计特性，因而其 性能可以较好的接近r ( d ) 的界限。 图2 2 失翼度界限和典型编码性能 2 3 2 变换编码 变换编码的基本思想是把空间域的图像信号转换到变换域。若变换是正交 变换，则变换域的能量与空域相等并且熵保持不变。但是变换前后信息能量得到 了重新分布。空间域中的像素之间存在很强的相关性，而变换域中能量则主要集 中在直流和少数低频的变换系数上，这部分占图像信息的9 0 。而高频部分的幅值 很小或几乎为零。同时变换系数间基本上是统计独立的，相关性较小。因此，可 小波分析及在数字图像压缩中的应用与研究 以仅对低频的变换系数进行量化、编码和传输，而对高频部分则不予编码，从而 达到图像压缩的目的。实际中一般采用阈值编码法：即事先设定一个闽值，只对大 于此阈值的变换系数编码，这样可使图像的某些高频成分得到保留，重建图像时 图像品质得到改善。有很多类型的正交变换，如k l ( 离散信号的h o t e i l i n g ) 变换、 离散余弦变换( d c t ) 、沃尔什一哈达玛变换和斜变换等。在这些正交变换中， 采用均方误差最小准则的k - l 变换是最佳变换，但其无快速算法且依赖于信源的统 计特性，所以很难进行实时编码。基本变换编码的框图如图2 _ 3 发送端： 接收端： 图2 3 变换编码流程图 2 3 3 预测编码 预测编码是数据压缩技术的一个重要分支，其理论基础主要是现代统计学和 控制论。图像的相邻像素之间存在着高度的相关性，即原始数据中存在着大量的 冗余。去除这些冗余，信号就可以有效的压缩编码。预测技木是最简单和有效的 压缩方法。发送者( 和接收者) 以某个固定的顺序( 如由左到右，逐行进行的光栅扫 描方式) ，在己经被传送( 接收) 的像素的基础上预测当前像素值。假设以p l f ，l 表示 当前像素值，以p 【f ，爿闪滚示其预测值，预测残差e = p d ，爿一p p ，爿需要被传送。如 果预测相当精确，那么预测残差的分布就集中在零值附近，其零阶熵比原始图像 的零阶熵大大降低。图像的像元和邻近像元有很大的相关性，因此可以用某一点 的相邻像元预测该点的值，预测误差将有较小的熵。预测编码有线性预测和非线 性预测两类。它们可以在一幅图像内进行( 帧内预测编码) ，也可以在多幅图像之间 进行( 帧间预测编码) 。预测编码基于图像数据的空间和时间冗余特性，用相邻的已 知像素( 或图像块) 来预测当前像素( 或图像块) 的取值，然后再对预测误差进行量化 和编码，这些相邻像素( 或图像块) 可以是同行扫描的，也可以是前几行或前几帧的， 相应的预测编码分别称为一维、二维和三维预测，其中一维和二维预测是帧内预 测，三维预测是帧间预测。预测编码的关键是在于预测算法的选取，这与图像信 号的撅率分布有很大关系，实际中常根据大量的统计结果采用简化的概率分布形 硕士学位论文 式来设计最佳的预测器，有时还使用自适应预测器以较好的刻画图像信号的局部 特性，提高预测效率。线性预测编码i ”j 又称为差分脉码调制，即d p c m ( d i f 诧r e n t i a l p u l s ec o d em o d u l a t i o n ) 。帧内预测编码一般采用像素预测形式的d p c m 。图2 4 为 d p c m 的编码流程图。 d p c m 是一种简单易行的预测编码方法，其优点是算法简单，易于硬件实现， 缺点是对信道噪声及误码很敏感会产生误码扩散，使图像质量大大下降。 x 图2 4 线性预测( d p c m ) 编码流程图 预测器用已经编码的邻近像素x 一1 ) ，x 0 2 ) x 0 一p ) 来计算x ( h ) 的估计值 与估计值的差值p ( 行) = x ( h ) 一t ，用于存储和传输。预测器的预测精度越高，预测 偏差越低，压缩比越高。 2 3 4 矢量量化编码 矢量量化【1 5 】的基本思想是根据s h a r h l o n 的信息理论，对符号序列在多维空间内 进行联合编码，以获得更高的压缩效率。其方法是：将输入图像数据序列分成多个 组，每一组m 仲 2 ) 个数据构成一个m 维空间中的一个矢量。在m 维空间中，将其 划分成x 个区域，每个区域内所有矢量用此区域内的中心矢量代替。对z 个量化矢 量分别赋一个索引值，则某个索引区内的所有矢量都可以用索引值来表示。编码 时只传输或存储该索引值，解码端采用与编码端相同的空间划分方法，则可由此 索引值得到对应的量化矢量，因而能有效地对图像数据进行压缩。 上述的空间划分称为矢量码书训练。矢量码书是通过大量样本的训练或学习 或自组织特征映射神经网络方法，得到一系列的标准图像模式，每一个图像模式 就称为码字或码矢，这些码字或码矢合在一起称为码书，码书实际上就是数据库。 输入图像块按照一定的方式形成一个输入矢量。编码时用这个输入矢量与码书中 的所有码字计算距离，找到距离最近的码字，即找到最佳匹配图像块。输出其索 引( 地址) 作为编码结果。解码过程与之相反，根据编码结果中的索引从码书中找到 索引对应的码字( 该码书必须与编码时使用的码书一致) ，构成解码结果。如图2 5 所示 小波分析及在数字图像压缩中的应用与研究 图2 5 矢量量化编码流程图 由于矢量量化有效地利用了矢量中各分量间的四种相关性( 线性依赖性、非线 性依赖性、概率密度函数的形状和矢量维数) 去除冗余度。因此，其结果要好于标 量量化。实际上，矢量量化可看成是标量量化的多维扩展。 2 3 5d c t 变换编码 d c t 变换【1 6 】是变换编码方法中的一种，但由于它是j p e g 【1 7 】建议书中的核心 压缩编码方案，我们在这里拿出来单独作为一节讨论，以便我们在下一章中将要 提到的离散小波变换( d w t ) 相比较。 在变换用于图像压缩时，我们期望有如下性质： a 1 减少图像相关：理想变换将完全消除图像块中的数据相关，即把绝大部 分能量压缩进最小的系数中去。 b ) 基本函数与图像无关：由于图像问统计特征变化大，最佳的变换通常依 赖于图像的本身，但是要求这种于图像无关是件很费计算时间的任务。 如果图像块不是静态的，就必须使用多组，以便高度的减少相关性，而 这样的处理不仅费时，而且需要附加信息把组号传送到解码端，从而降 低压缩效率，所以一般期望用与图像无关的基本函数变换替换最优性能 变换。 c ) 快速实现：n 点变换需要d ( n 2 ) 操作，而一些变换有快速算法，其操作次 数可以减少为d ( 疗l o g m ) 次，如果是2 维变换，那么操作次数就从d ( 以4 ) 减 少到0 ( 2 n 2l o g n ) 次。 k l t 变换是一种能量打包的最优变换，然而k l t 变换函数是图像依赖的，且不 存在快速算法，在对图像信号的变换中，d c t 和k l t 相差无几，而且d c t 变换有其 它变换无法比拟的优点，即：实数变换，确定性变换函数( 变换核) 、可分离的 变换。 二维d c t 变换为： 脚，= 击c 壤篓m 棚c o s 笺产c o s 号笋 泣 甲匈 田 暑一 索一 亨团 硕士学位论文 m 朋= 击善篓c c c 州c o s 与竽c o s 簧产 可见，二维变换都有相同的变换函数，且是可分离的： 舳拟咖娜她归砉c o s 产吾c o s 鼍笋 汜 2 3 6 小波编码 小波分析是当前数学中一个迅速发展的新领域，它同时具有理论深刻和应用 十分广泛的双重意义它与f o u r i e r 变换、窗口f o u r i e r 变换( g a b o r 变换) 相比，这是一 个时间和频率的局域变换，因而能有效的从信号中提取信息，通过伸缩和平移等 运算功能对函数或信号进行多尺度细化分析( m u l t i s c a l ea n a l y s i s ) ，解决了f o u r i e r 变换不能解决的许多困难问题，从而小波变化被誉为“数学显微镜”，它是调和分析 发展史上里程碑式的进展。与傅立叶分析相似，小波变换( w a v e l e tt r a n s f o r m ) 是一 种同时具有时一频二维分辨率的变换。其优于傅氏变换之处在于它具有时域和频 域“变焦距”特性，十分有利于信号的精细分析。 小波图像压缩方法是近年来受到广泛重视并己逐步得到应用的变换编码技 术。与传统的d c t 变换相比，离散小波变换( d w t ) 具有良好的时频局部化特性和较 好的能量集中特性，同时由于小波变换是对整个图像进行的，因此基于小波的图 像压缩方法能够很好地克服方块效应；此外，小波变换具有天然的塔式分解数据特 征，可直接应用于图像的多分辨率分解的多分辨率特性提供了利用人眼各种视觉 特性的良好机制。正是由于这些原因，众多学者对基于小波的图像压缩方法进行 了研究。图2 6 为三层小波分解图 l l 3h l 3 h l 2 l h 3h h 3 h l l l h 2h h 2 h l l h h l 图2 6 三层小波分解示意图 一：= ：= ：一一：些些望堡塑墼塑皇塑：一：。：! 一。： 2 3 ，7 分形编码 分形图像编码是在m a n d e l b r o t 分形几何理论【1 8 j 的基础上发展起来的一种编码 方法。分形理论是欧氏几何相关理论的扩展，是研究不规则图形和混沌运动的一 门新科学，它描述了自然界物体的自相似性，这种自相似性可以是确定的，也可 以是统计意义上的。m b a m s l e y 引入了迭代函数系统( i f s ，i t e r a t e df u i l c t i o ns y s t e m ) 来刻划这种自相似性，并将其用于图像编码，对某些特定图像获得了1 0 0 0 0 ：l 的压 缩比。m b a r n s l e y 的方法需