（计算机应用技术专业论文）结合符号编码和零量化系数估计的ezw算法.pdf

浙江人学硕士学位论 摘要 随着网络的普及和图像数据广泛传输，图像数据的压缩成了一个热门的领 域。由于小波变换具有很好的时域和频域局部性，当前小波变换成了图像压缩的 一个有力的工具。 小波变换系数由幅值和符号组成。虽然当前对小波变换系数幅值进行编码已 有了比较高效的算法，但是现行的小波编码算法对小波变换系数符号的编码并非 如同对幅值的编码那么有效。事实上，学术界曾经普遍认为，对小波系数符号进 行熵编码不会得到压缩效益。直到最近才开始出现一些学者研究小波图像编码的 这个领域。 。 在这篇论文中，将在嵌入式小波图像编码的环境下对符号编码进行详细的探 讨。除了将内部子带小波系数应用在符号编码的上下文模型外，还将描述一种投 影技术，这种技术使非内部子带小波系数也能整合入这个上下文模型。在解码器 端，也可以用累积的符号预测统计信息来推导零量化系数估计，提高图像重建质 量。这些技术被验证会获得平均o 3 d b 的p s n r 收益，并且对任意类型的嵌入式 小波图像编码都适用。 关键字：图像压缩，符号编码，符号预测，j 、波 第1 页 浙江大学硕士学位论文 a b s t r a c t w i t ht h er a p i dp e r v a d eo fi n t e r n e ta n dt r a n s m i s s i o no f i m a g ed a t a ， i m a g ec o m p r e s s i o nb e c o m e sah o tr e s e a r c ha r e a a n db e c a u s ew a v e l e th a s ag o o dl o c a l i t yi n s p a c ea n df r e q u e n c yd o m a i n s ，i ti sau s e f u lt o o lt o i m a g ec o m p r e s s i o n w a v e l e tt r a n s f o r mc o e f f i c i e n t sa r ec o m p r i s e db yb o t ham a g n i t u d ea n d a s i g n ，w h i l e e f f i c i e n t a l g o r i t h m s e x i s tf o r c o d i n g t h et r a n s f o r m c o e f f i c i e n tm a g n i t u d e s ，c u r r e n tw a v e l e ti m a g ec o d i n ga l g o r i t h m sa r en o t a se f f i e l e n ta tc o d i n gt h es i g no ft h et r a n s f o r mc o e f f i c i e n t s i nt h i sp a p e r ，s i g nc o d i n gi se x a m i n e di nd e t a i li nt h ec o n t e x to f a ne z wi m a g ec o d e r ，i na d d i t i o nt ou s i n gi n t r a b a n dw a v e l e tc o e f f i c i e n t s i nhs i g nc o d i n gc o n t e x tm o d e l ap r o j e c t i o nt e c h n i q u ei sd e s c r i b e dt h a t a l l o w sn o n i n t r a b a n dw a v e l e tc o e f f i c i e n t st ob ei n c o r p o r a t e di n t ot h e c o n t e x tm o d e l a tt h ed e c o d e r a c c u m u l a t e ds i g np r e d i c t i o ns t a t i s t i c sa r e a l s ou s e dt od e r i v ei m p r o v e dr e c o n s t r u c t i o ne s t i m a t e sf o rz e r o q u a n t i z e d c o e f f i c i e n t s i tw i l lb es h o w nt h a tt h e s et e c h n i q u e sy i e l dh i g h e rp s n r i m p r o v e m e n t s k e y w o r d ：i m a g ec o m p r e s s i o n ，s i g nc o d i n g ，s i g np r e d i c t i o n ，w a v e l e t s 第2 页 浙江大学硕士学位论文 1 数字图像压缩技术概况 1 1 图像数据压缩概述 信息是现代社会的主特征，而人们传递信息的重要媒介是图像。许多信息诸 如天气情况、地球资源分布情况、医疗诊断信息等都可以转化为数字图像的形式。 而数据量大是数字图像的一个显著特点。如随着遥感技术的不断发展，航天遥感 器( 如星载合成孔径雷达和成象光谱仪等) 及未来的地点资源操测平台所获得的 数据量越来越大，对星上数据存储和对地数据传输系统的需求越来越高，待处理 的数据量日益庞大，这给星上的数据传输和信道符合带来过重负担，同时也使地 面数据处理难以应付。未来的星载遥感系统所要求的数据传输很可能超过信道容 量。因此，图像处理及数据压缩对现代化社会的发展起着不可忽视的作用。随着 计算机技术的发展与普及，数字图像处理与数据压缩作为- n 高技术，越来越显 示出它载社会发展中的重要地位。它既是当代信息高速公路、高清晰度( h d t v ) 、 可视电话、图文传真等技术的关键，又在航空侦察遥感、资源勘探及生物医学工 程等领域起着非常重要的作用。 图像压缩是指在满足一定图像质量的条件下，用尽可能少的数据量来表示图 像。这是由数字图像本身的特性而决定的。数字图像一般可表示为厂( f ，) ， f ，= o , 1 ，n 一1 ，它是经过对二维图像厂( x ，1 y ) 进行抽样和量化过程而得到的。 这种表示存在冗余性，图像压缩的目的就是要消除这种冗余性。近年来随着数字 信号处理技术、数字图像处理技术和大规模集成电路技术的发展，新的数据压缩、 图像压缩技术取得了长足进展，各种图像压缩技术走向成熟。 用于数据压缩的技术大体上可以分为大三类：无损压缩( 1 0 s s l e s s c o m d r e s s i o n ) 、有损压缩( 1 0 s s yc o m p r e s s i o n l 、分类( c l a s s i f i c a t i o n ) 。无损 压缩提供了不丢失任何信息的技术。也就是说，原始数据可以从压缩数据准确无 误地恢复。这种方法压缩比不高，主要用于数据需要准确形式的情况。但在很多 情况下，图像是供入眼观察的，在这样的情况下，轻微的失真是允许的。另一方 面，未来的图像系统其数据量即便采用无损压缩仍可能超过信道容量的上限，在 第5 页 浙江大学硕士学位论文 此情况下，必须舍弃一些数据，这就是有损压缩的背景。应用有损压缩可以更大 量地压缩数据。所谓分类就是指对于一个给定的数据集用户只对其中具有某一 特征的数据感兴趣a 这样抽取特征并传输符合某一特征的数据子集，而不是传输 所有数据，就可以压缩大量的数据。显然这也是有损的压缩。 1 2 当今数据压缩技术的发展现状 由于航天遥感、多媒体、i s d n ( 综合业务数字网) 与大众传播技术具有产阔 应用领域和应用前景，与其息息相关的数据压缩技术亦发展很快。在经典压缩方 法基础上，许多新算法已被提出和应用。 1 2 1 数据压缩技术的分类 编码压缩方法有许多种，从不同的角度出发有不同的分类方法，比如从信息 论角度出发可分为两大类： ( 1 ) 冗余度压缩方法，也称无损压缩，信息保持编码或熵编码。具体讲就是 解码图像和压缩编码前的图像严格相同，没有失真，从数学上讲是一种可逆运 算。 ( 2 ) 信息量压缩方法，也称有损压缩，失真度编码或熵压缩编码。也就是讲 解码图像和原始图像是有差别的，允许有一定的失真。 应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分类为： ( 1 ) 无损压缩编码种类 哈夫曼编码 算术编码 行程编码 l e m p e lz e v 编码 ( 2 ) 有损压缩编码种类 预测编码：d p c m ，运动补偿 频率域方法：砸文变换编码( 如d c t ) ，予带编码 空间域方法：统计分块编码 模型方法：分形编码，模型基编码 第6 页 浙江火学硕士学位论文 基于重要性：滤波，予采样，比特分配，矢量量化 ( 3 ) 混合编码 j b i g ，h 2 6 1 ，j p e g ，m p e g 等技术标准 1 2 2 无损压缩 为了讨论无损压缩，首先必须了解压缩的理论极限。经典的数据压缩理论建 立在信息论的基础上。作为香农( c e s h a n n o n ) 信息论研究的对象信息，被假定 f1 为由一系列随机变量所代表。它们往往用随机出现的符号集d m2 译”口z ，日一j 来 表示。输出这些符号集的源被称为信源。信息源熵值定义为： 8 h ( x ) = 一p ( a ，) l g p ( a ，) 1 = i 信息源熵值越高，所含的信息就越多。一个符号的熵定义为其概率的对数的 负值。为了用位数来确定一条消息的信息容量，我们用以2 为底的对数来表达。 整条消息的熵只是所有单个符号熵的总和。熵使用数据压缩是因为它能确定表示 一个消息实际所需的位数。例如，字符e 在文中出现的概率为1 1 6 ，则该字 符的信息容量为4 位。这样，字符串e e e e 总共有2 0 位的容量。如果我们使 用标准的8 位a s c i i 字符来为这条消息编码，实际上使用了4 0 位。2 0 位的熵与 用于编码消息的4 0 位之间的差就是数据压缩的潜力所在。 数据编码的基本途径之一，就是设法改变信源的概率分布使其尽可能地非均 匀，再用最佳编码方法使平均码长逼近信源的熵。这就是无损压缩的理论基础。 常见的无损压缩方法有霍夫曼编码、游程编码、算术编码、r i c e 算法等。 1 2 3 有损压缩 由于数据的无损压缩的最小数据量以其信息熵为下限。因而压缩数据量有 限。对于许多图像应用领域柬说，图像主要供人眼来观察，例如可视电话、电话 会议等。在这种情况下，压缩图像即便有不明显的失真，也是可以容忍的a 我们 把有损压缩也称为熵压缩。由于信息熵被压缩，结果图像压缩效率大大提高。目 第7 页 浙江大学硕。l 学位论文 前人们研究的比较多是d p c m 、变换编码、向量量化、子带编码、小波变换编码、 分形图像编码、人工神经网络等。 1 3 数字图像压缩基本概念 1 3 1 保真度准则 为了_ 对有损压缩的图像进行度量，苜先，我们匝对保真度准贝q 进行介绍。对 于有损压缩来说，不同的压缩技术对应的压缩比不同，恢复图像的质量也不同。 为了l e , 较各种压缩技术的优劣，必须确定一些测量准则来比较恢复图像的质量。 在此称为保真度准则。常用的准则可以分为两大类：( 1 ) 客观保真度准则；( 2 ) 主观保真度准则。 当所损失的信息量可用编码输入图与解码输出图的函数表示时，我们说它是 基于客观保真度准则的。最常用的一个准则是输入图和输出图之间的均方根 ( r m s ) 误差。4 1 f ( x ，) ，) 代表输入图，f ( x ，y ) 代表对，( 墨y ) 先压缩又解压缩后得 到的，( x ，_ y ) 的近似，对任意x 和y ，f ( x ，y ) 和，( x ，y ) 之间的误差定义为： p ( x ，y ) = 于( x ，_ y ) 一f ( x ，) ，) 如2 幅图的尺寸均为m n ，则它们之间的总误差为： m - i n - ir 1 旷( 训) 一( w ) j 这样( 茗，) 和，( 五y ) 之制的均方根误差8 一r 为： 一去m 萎- l 丢n - i h y ，j 另一个客观保真度准则与压缩一解压缩图的均方信噪比( s i g n a l t o - n o i s e r a t i 。s n r ) 有关。如果将，( x ，y ) 看作原始图，( 置y ) 和噪声信号8 ( x ，) ，) 的和，那 么输出图的均方信噪比5 眦m s 为： s n r 。：m - 1 n - i 氘力：崖篆阮沪m 肭f 销8 页 浙江大学硕：b 学位论文 如果对上式求平方根，就得到均方根信噪比印氓一，。 实际使用中常将限归一化并用分贝( d b ) 表示。令 夕= 击m 萎- i 荟n - i m y ) 则有： l 窆芝m y ) 一升l 【厂( w ) 一丌 一1 0 1 8 1 霞x = o 瓦y = q 焉砑l 扩( 础) 一( w ) j lj c 0y = o 如果令厶。 ，( z ，y ) ，x = 0 1 ，m 一1 ，y 2o ，1 ，一，则可得到峰值信噪比 p s n r ： f1 一_ l o 地l 韵南f ( xll 陟( 训) 一 ，y ) f i 由于图像的最终用户是人，因而估计图像质量的最可靠的方法是由观察者来 主观分类。在绝对评价中，观察者看一幅图像并通过将其归入莱一分类级别来估 1 3 2 哈夫曼编码 哈夫曼在1 9 5 2 年根据可变长最佳编码定理，提出了依据信源集中各信号出 现的概率分配不同长度即时码的哈夫曼算法。具体是，在信息概率已知的基础上， 概率大的信号配置的码字短，概率小的信号对应的码字长。这些码字与被描述对 象之间有固定对应关系。接受端在得到哈夫曼编码后，“即刻”解码得到与输入 一致的图像信号。哈夫曼编码是一种无失真编码。 过程是： ( 1 ) 将灰度等级按概率大小进行排序，大的在前，小的在后。 ( 2 ) 取两个最小概率相加，之和作为一个新的概率集合( 新的概率集合的概 第9 页 浙江大学硕士学位论文 率个数总是比执行此步骤前的概率集合少一个) 。新的概率在新的概率集合中仍 遵循降幂规则确定所处的位置。 被相加的两个最小概率所对应的灰度级称为哈夫曼树的一个叶节点，这两个 接点构造一个双亲节点。重复进行此步骤，直到只有诱个概率( 其和一定是1 ) 为止。这时，哈夫曼树到达根接点。 哈夫曼编码效率优于其它编码方法，是一种最佳变长码。实现哈夫曼编码的 基础是统计源数据集中各信号的概率分布。当源数据成分复杂时哈夫曼码表较 大，码表生成难度增加，编译速度变慢，从而限制了哈夫曼编码的实际应用。 ( 哈夫曼编码系统) ；给出了哈夫曼编码的基本过程。统计各灰度级出现的频 度是哈夫曼编码的第一步。可建立个数组，以存放各灰度级出现的次数。构造 啥夫曼编码是哈夫曼编码中的一个难点，其思路可以这样予以概述：将权重值非 零的结点定义为活动结点，在参与构造哈夫曼树的n 个活动中，找出两个权重值 最小的活动结点( 定义为一，) 并将这两个结点的权重求和，形成一个新的活 动结点，同时将膏，z m 置零，表示这两个结点变成非活动结点，不再参与构造哈 夫曼树的后继操作。新的活动结点与原来剩余的活动结点组成新一轮活动结点 集。重复上述操作，直到只有一个活动结点( 根接点) 为止。 有建成的哈夫曼树，便可生成各灰度级( 信号) 对应的哈夫曼代码。方法是依次 由树根出发，前进到每个叶片，所经路径上对应的“0 ”或“1 ”的集合便是各信 号对应的哈夫曼码。编码压缩模块的功能是将源图像文件转换成哈夫曼代码形成 存储到另一个文件中或用于信道传输。压缩后的图像文件是一些二进制的“0 ”、 “1 ”串，且没有分界符。译码模块负责将这些“0 ”、“1 ”串参照哈夫曼树恢 复为原图像信号。 1 3 3 算术编码 算术编码( a r i t h m e t i cc o d i n g ) 的概念是e l i a s 在六十年代初期提出来的， r i s s a n e n 和p a s c o 首次介绍了它的实用技术。到八十年代才出现了算术编码的 具体实现方法。 第l o 页 塑堕塑型型堕一 算术编码的基本原理是：将被编码的信息表示成实数0 和i 之间的一个间隔 ( i n t e r v a l ) 。信息越长，编码表示的间隔就越小，表示这一间隔所需的二进制 位就越多。信息源中连续的符号根据某一模式生成概率的大小来减少间隔，出现 概率大的符号比出现概率小的符号减少的范围小，因此只增加较少的比特位。 。在传输任何信息之前的信息完整范围是 o ，1 ) 。当一个符号被处理时，这 一范围就依据分配给这一符号的那部分变窄。 初始的r a n g e 是 o ，1 ，h i g h = l ，l o w = o ；然后依据下列公式： 编码模式r a n g e l o w 和r a n g e h i g h 的指定依据该符号出现的概率而定。 算术编码方法有两种编码模式：基于概率统计的固定模式及自适应模式。采 用固定模式需要事先对码书中的码字进行预扫描，以统计各码字出现的概率，此 过程计算量比较大，举例来说：一幅1 6 0 1 2 0 的图像，选用4 * 4 的矢量字，则共 有1 2 0 0 个矢量，如果选用2 5 6 个码字的码书( c o d eb o o k ) ，则每次迭代中矢量匹 配量是1 2 0 0 2 5 6 = 3 0 7 2 0 0 ，显然计算量很大，计算效率不高；若出现新的不在码 书中的码字，则图像还原效果就会比较差，因此采用此方法必须对要压缩的每一 幅图像均进行码字预扫描。 而自适应模式各个符号的概率初始值设为相同值，它们依据出现的码字而相 应的改变其概率值，若出现新的码字只需要在码书中添加上即可。只要编码器和 解码器使用相同的初始值和相同的改变值的方法，那么它们的概率模型将保持一 致。编码器接收到下一个码字对其编码，然后改变概率模型，解码器根据当前的 模式解码，然后再改变自己的概率模型。 举例来说，有a 、b 、c 、d 四个基本字符组成的字串b a c d a 。首先我们将4 个字符概率均设为0 2 5 ，即：a o ，0 2 5 ) 、b o 。2 5 ，0 5 ) 、c o 5 ，0 7 5 ) 、d o 7 5 ，1 ) 第1 1 页 浙江大学磷士学位论文 编码到字串中第五个字符即“a ”时，修改4 个基本字符的概率为ae o ，0 4 ) 、 b o 4 ，0 6 ) 、c o 6 ，0 8 ) 、d o 8 ，1 ) 。按照( 5 ) ( 6 ) 式计算后，得到： 初始值 编码b a c d a l o w l 0 ， 0 2 5 ， 0 2 5 ， 0 2 8 7 5 0 3 0 1 5 6 2 5 h i g h 1 ) 0 5 ) 0 3 5 ) 0 3 0 6 2 5 ) 0 3 0 6 2 5 ) i o 3 0 1 5 6 2 5 ，0 3 0 3 4 1 8 5 ) 其r a n g e 可用下图表示 d 一0 i 亚二 自适应算术编码的值域 解码时只要知道最后的范围r o ，3 0 1 5 6 2 5 ，0 3 0 3 4 1 8 5 ) 和改变概率的时间及值，就 可以解得这个字符串。 1 3 4 变换编码- - d c t 变换及小波变换编码 图像变换编码的研究已有相当的历史，但由于其硬件实现较复杂，故以往只 被应用于空间地球资源卫星或其它空间遥感装置中。8 0 年代以来，由于大规模 第1 2 页 1j 艿 5 如 捕 y 1 j j 巧。 o。y。 1 j 一 ； 巧 。， 。一 1 j j 浙江大学硕士学位论文 集成电路技术的发展，图像变换编码开始应用于电视、会议电视、电视电话等领 域，对图像变换编码的研究也越来越透彻。 变换编码是利用正交变换来实现图像压缩编码的方法。模拟图像经采样后， 成为离散化的亮度值，离散化的像素点可以是2 5 6 点2 5 6 点或5 1 2 点5 1 2 点也 可以是其它尺寸假如把整幅图像一次进行变换，则运算比较复杂，所需时间较长 通常把图像在水平方向和垂直方向上分为若干子区，每个子区有4 x 4 、8 8 或 1 6 1 6 点，以子区为单位进行变换，每个子区的全部像素值构成一个空间域矩 阵。 ff ( o ，0 ) ： 月妫 l ? 【，( 一1 ，o ) f ( o ，1 ) f ( 1 ，1 ) f ( o ，n 一1 ) ( 1 ，一1 ) ，( 一1 ，一1 ) 矩阵中元素f ( i ，j ) 表示予区中第i 行、第j 列像素的亮度值。对n x n 阶空 间矩阵作变换的也是n x n 阶，变换就是在空间矩阵两边乘以变换矩阵 t 得到变 换域矩阵 f p = pi ， 口 由于正交矩阵i t 是满秩的，它们有逆阵，设i t 的逆阵为 t - - 1 。在上式两 边左右两端都乘以 t 一1 ，得到 = 目】1 p 】口】- 1 以上两个式子就概括了变换编码的中变换的基本思想和基本操作 对于变换编码的物理意义。首先，假如变换矩阵是归一化正交变换矩阵，则 经变换后，空间域中的总能量在变换域中得到保持，即满足： 第1 3 页 、，l，j d f 舭叫 肌 l i 曲， 眦 浙江大学硕= k 学位论文 式中f ( i i j ，n ) 为空间域矩阵中元素，f ( i ，j ) 为变换域矩阵中元素。上式的意义 在于；空间域中能量全部转移到变换域中，丽在反变换中，变换域的能量又能全 部转移到空间域中。 经过变换之后，变换域中总能量不变，但能量将会重新分布，在空间域中， 能量分布具有一定的随机性。由于图像有一定的相关性，变换域中能量在大部分 情况下，集中于零空间频率或低空闻频率对应的变换系数，从而使具有相关性图 像的相关性减少。同时由于能量集中于零空间频率和低空间频率所对应的变换域 矩阵元素中，我们对这些元素分配较多的比特数，而对能量较少的元素分配较少 的比特数或不分配比特数，由于相关性的减少，变换域中分配的总比特数可以比 原图像的总比特数少，这样就可以使图像所需传送的比特数减少，达到压缩的目 的。 ( 1 ) d c t 变换，也就是离散余弦变换，它是变换编码中的个非常重要的成 员。顾名思义，d c t 变换中的变换矩阵只含余弦成分，例如，其n x n 像素块前 向2 - - dd c t 变换通常就表示为以下定义式： 脚，：篝掣薯薹如椭 。( 2 j + 弘1 ) u r r 湖 翻 露 j - ol _ 。 l “ jl j 后向2 - - dd c t 变换则通常表示为以下定义式： “，叼- - e 薹e 霎c 。) 。f ，v ) c 。s 垦毫 竺刁i c o s i i - 里兰芸竽竺刁 “，七) c o ) o f ，y ) c 0 5 l = 二；：二= 互i i _ 0v 0 。l一 。 c ： 去 删 i1x = 1 2 ，一1 而二维d c t 变换编码压缩和解压缩的框图可以表示如下： 薷1 4 页 浙江大学碗f ：学位论文 一对交濑数霍翘编码 一对懿张眦躺 一对交流系数霍夫曼解码卜 一对直流系数r c l 解码l 当然，从图中我们也可以看出变换编码也还包括量化、编码等步骤。将几者 结合起来，才能实现d c t 变换图像压缩编码。 在变换编码中：k a r h u n e n - l u e v e 变换( 简称卡一洛变换) 具有最好的压缩 能力，但是它的变换计算复杂，而d c t 变换在压缩效率方面与卡一洛变换相差不 多，而且能用类似f f t 的算法实现快速变换，因此，尽管d c t 在压缩效率上略逊 于卡一洛变换，但因其高效性，使它已经成为c c i t r 建议的一种图像压缩方式。 d c t 变换的作用是使空间域的能量重新分布，降低图像的相关性- d c t 变换 本身并不能达到数据压缩的作用，而要实现图像压缩，就要选择适当的比特分配 方案和量化方法。变换编码方法最重要的部分无疑就是比特分配与量化了。其实， 变换的方法很多，有好有环，然面对整个算法而言，无论你选择哪一种变换，其 好坏主要收限于量化方法。 具体的讲，变换编码的比特分配与量化，都大概遵循以下的步骤：首先选择 量化器，然后在各个变换域系数唰分配一定的比特数，使重建图像的保真度达到 最大。而o c t 变换中因为能量集中于左上部分，所以比特分配时也是对左上部分 的变换域系数分配较大的比特数，这样就可以用尽可能少的比特数达到尽可能大 的保真度。下面是一种d c t 编码中变换域系数比特分配和量化方案的框图示意： 第1 5 页 浙江大学硕士学位论文 ( 2 ) 小波变换编码 在以前j p e g 基本系统中，首先把原始图像分成大小相等的像素块，然后对 图像块进行离散余弦变换d c t ( 图像块的能量集中到少量的系数) ，再用基于人 类视觉系统( h v s ) 特性的矩阵对变换后得到的系数矩阵进行量化，从而大幅度 地压缩了矩阵系数，同时也造成了损失。最后对量化后得到的矩阵系数进行无损 熵编码。图像的重建过程是编码过程的逆过程。在高压缩比场合，y p e g 的重建 图像在水平和垂直方向出现晕圈、幻影，产生”方块”效应，就是因为对原始图像 进行了分块的d c t 变换和量化。如果不分块或分块很大丽进行d c t 变换与量化， 那么图像块中像素能量集中到少量的系数效果将交得不明显，即不利于对数据进 行量化压缩，同时还使得计算复杂度增加。这样一种现象实际上是离散余弦交换 d c t 本身的特性所造成的( 采用离散正弦变换d s t 或者离散傅立叶变换d f t ， 结果是类似的) 。d c t 反映的是信号或函数的整体特征，而在不少实际问题中我 们所关心的是信号在局部范围中的特征。另外，如果采用k a r h u n e nl o e v e ( - - 般 称作k ，l ) 变换方法，可以把连续的随机过程转变成彼此不相关的随机变量系列， 即通过f 交变换去除像素之间互相关丽达到图像数据压缩的目的。然而，k l 方 法的优美性质仅表现在信号处理理论上及数学表示的完美上。实际上该方法的计 算复杂度十分巨大，因此很难得到实际应用。 为了继承f o u r i e r 分析( 余弦变换和正弦变换都可以视为f o u r i e r 交换的特例) 的 优点，同时又克服它的许多缺点，人们一直在寻找新的方法。1 9 8 0 年法国科学 笫1 6 页 浙江大学硕士学位论文 家m o i l e r 首先提出了小波变换、t ( w a v e l e t t r a n s f o r m ) ，引起了许多数学家和工 程师的极大关注。近十多年来经过许多数学家和工程技术人员的努力探索，这门 学科的理论基础已经建立，并成为当前应用数学发展的一个新的领域。 与f o u r i e r 分析相比，小波变换是时间和频率的局域变换，能更加有效地提 取信号和分析局部信号。类似于f o u l e r 分析，在小波分析中也有两个重要的数 学实体：”积分小波变换”和叫、波级数”。积分小波变换是基小波的某个函数的反 射膨胀卷积，而小波级数是称为小波基的一个函数，用两种很简单的运算f 1 二进 制膨胀”与“整数平移”表示。通过这种膨胀和平移运算可以对信号进行多尺度的 细致表示。通过这种膨胀和平移运算可以对信号进行多尺度的细致的动态分析， 从而能够解决f o u d e r 变换不能解决的许多困难问题。利用小波变换可以一次变 换整幅图像，不仅可以达到很高的压缩比，而且不会出现j p e g 重建图像中的” 方块”效应，但编码器复杂，有潜像问题。 由于小波及小波包技术可以将信号或图像分层次按小波基展开，所以可以根 据图像信号的性质以及事先给定的图像处理要求确定到底要展开到哪_ 级为止， 从而不仅能有效地控制计算量，满足实时处理的需要，而且可以方便地实现通常 由子频带、层次编码技术实现的累进传输编码( 即采取逐步浮现的方式传送多媒 体图像) 。这样一种工作方式在多媒体数据浏览、医学图片远程诊断时是非常必 要的。 另外，利用小波变换具有放大、缩小和平移的数学显微镜的功能，可以方便 地产生各种分辨率的图像，从而适应于不同分辨率的图像i o 设备和不同传输速 率的通信系统。 相比之下，利用k l 变换进行压缩编码，只能对整幅图像进行；而利用小波 变换则能够比较精确地进行图像拼接，因此对较大的图像可以进行分块处理，然 后再进行拼接。显然，这种处理方式为图像的并行处理提供了理论依据。 实际上，由于小波变换分析具有以上许多优点，所以在最近颁布的运动图像 压缩标准m p e g4 中的视觉纹理模式就支持视觉纹理和静态图像编码。这种模式 基于零高度树小波算法，在非常宽的比特率范围内具有很高的编码效率。除了具 第1 7 页 浙江大学颂：l 学位论文 有很高的压缩效率之外，它还提供了空间和质量的可缩放性，以及对任意形状目 标的编码。其空间可缩放性高达l l 级，质量的可缩放性具有连续性。小波公式 以累进传输和时间上扩充静态图像分辨率金字塔的形式提供比特率可缩放的编 码。编码的位流也可以用于图像分辨率层次抽样。这种技术提供了分辨率的可缩 放性，以便处理在交互应用场合广泛的观察条件，以及把2 d 图像映射到3 d 虚拟 空间。 综上所述，由于小波变换继承了f o u r i e r 分析的优点，同时又克服它的许多 缺点，所以它在静态和动态图像压缩领域得到广泛的应用，并且已经成为某些图 像压缩国际标准( i nm p e g - 4 ) 的重要环节。当然，像其他变换编码一样，在压 缩比特别高的时候，小波变换压缩量化后的重建图像也会产生几何畸变。 由于小波分析克服了f o u r i e r 分析的许多弱点，因此它不仅可以用于图像压 缩，还可以用于许多其他领域，如信号分析、静态图像识别、计算机视觉、声音 压缩与合成、视频图像分析、c t 成像、地震勘探和分形力学等领域。总之，可 以说凡能用南u r i e r 分析的地方，都可以进行小波分析。小波分析应用前景十分 广阔。 小波是一个满足条件k 艇帕出。o 的函数v 通过平移和伸缩而产生的一个函数 觚。：m ) 。旷以书，酏酿圳 通常称为基本小波。 对于任意的f l 2 ( r ) ，若v l 2 ( r ) ，则给出如下定义 ( i ) f 的连续小波变换定义为： 其中地( f ) 表示v 。( t ) 的共轭函数。 ( i i ) f 的离散小波变换定义为 第1 8 页 浙江大学硕士学位论文 q * 一，c ，) 2 熙盹。 ，出圆 其中，。( t ) = a 。2 v ( a z t - n b ) ，0 a 。 l ，b 。，0 ( 4 ) 其基本原理如下图。 小波编码原理图 + j ， 进行子频段编码的关键问题，是如何设计滤波器组，除去混叠频谱分量。小 波变换恰好能提供图像的多尺度分解表示，使用小波基可以构造无叠频滤波器 组。 其工作过程是：将输入信号在水平方向和垂直方向与两个滤波器( 高通、低 通) 相卷积，可以得到四块面积为原图像1 4 的子图，分别为水平方向低频和垂 直方向低频( h h ) 、水平方向低频和垂直方向高频( h o ) 、水平方向高频和垂直方 向低频( g h ) 、水平方向高频和垂直方向高频( g g ) ，h g 、g h 、g g 称为细节子图， h h 称为原图像的低分辨率子图，以上是图像的一级小波分解；对h i 再作上述同 样的运算就可以得到图像的二级小波分解和三级小波分解。解码时，如果只合成 删子频段的信号，则可以得到普通分辨率的图像；如果将4 个子频段的信号进 行合成，就可以还原高分辨率的图像。根据这个原理，利用子频段编码在图像的 j 捌络传输中可以采取：发送端先发送 i l 子频段信号，接收端收到此信号后即可 开始解码，发送端再发送h g 、g h 、g g 各高频子带，接收端的解码工作随着高频 子带的增加，图像分辨率逐渐提高。这样可以实现图像在网络上的递进传送，使 访问该图像的用户可以先由低分辨率图像来确定它是否为用户所需要的图像。 小波变换的基本思想是用一组小波或基函数表示一个函数或信号，例如图像 第j 9 页 浙江大学硕士学位论文 一。一信号。以哈尔( h e a r ) 小波基函数为例，基本哈尔小波函数( h a a rw a v e l e t f u n c t i o 7 ) 定义如下： 吣， 1 ，当o x 1 2 1 ，当1 2 x l 0 ，其他 设有一幅分辨率只有4 个像素的一维图像，对应像素值为： 9 7 35 。 用哈尔小波变换的过程是：计算相邻像素对的平均值( a v e r a g i n g ，亦可称之为 近似值a p p r o x i m a t i o n ) ，得到一幅分辨率为原图像i 2 的新图像： 84 。这 时图像信息己部分丢失，为了能从2 个像素组成的图像重构出4 个像素的原图像， 必须把每个像素对的第一个像素值减这含像素的平均值作为图像的细节系数 ( d e t a i lc o e f f i c i e n t ) 保存。因此，原图像可用下面的两个平均值和两个细节 系数表示： 8 4 1 一1 。可以把第一步变换得到的图像进一步变换，原图像 两级变换的过程如下表所示： 哈尔小波变换过程 。 分辨率平均值细节系数 4 9735 2 84 1 - i ! - 6 2 哈尔变换过程事实上是用求均值和差值的方法对函数或图像进行分解，对于 f ( x ) = 9 73 5 ，我们可作最多2 层的分解。 对于2 维图像。同样可以用依次对行列进行小波变换得到2 维图像的分解。 这时经过次小波变换得到是2 维图像的近似值( l l ) 以及水平( l h ) 、垂直( h l ) 和对角( h h ) 细节分量值。显然，从2 维图像的l l 、l h 、h l 和h h 值可以重构出原 来的2 维图像。 m e l l e t 提出的快速塔式变换算法为小波图象编码技术的发展起到了奠基性 的作用。所谓塔式变换算法，就是将幅图象经过二维小波变换分解为一系列尺 度( 频率) 、方向、空间局部变化的子带，也称子图象。m a l l a t 二维塔式快速 小波变换的分解和重建示意图如下： 第2 0 页 浙江大学硕= l 学位论文 原图象一，。( l l ) 经过上述的二维小波分解后，可以得到4 幅子带图象 ( 图1 0 ) ：a ，( 己三1 ) 、d f ( h l l ) 、d ! ，f ( l i - t 1 ) 刹点) ；f ( h h l 它 们分别表示在尺度上的水平低通一垂直低通子图象、水平带通一垂直低通子图象、 水平低通一垂直带通予图象和水平带通一垂直带通子图象。而这4 幅子图象经过小 波反变换后，可以无失真地恢复出原图像a “f ( l l ) 。而利用上述的小波 分解算法可对子图像a z 。if l l l ) 再次小波分解，得到尺度2 广1 上的4 幅予 带图象。类似地可以对子图像a 。厂( z 上2 再次分解，以此类推可得到图象 的多级小波分解，得到不同分辩率的予带图象。 圳行 圈由一。 弦i ：圈赫铺仃中行 团袭示铘例删刊 二维小波分解示意图 ( h 。( “) ，g 。( 月) 分霸为低通彝l 甜通滤被群) 第2 i 页 浙江大学硕二t 学位论文 一 州行 1 3 5 量化 田镯揭兰， 哑圈圊- - 2 目q l h 1 鼬f l ：圈瓢辆弘f j 瓢前 困貅舯默诲 ( h 1 ( “) ，( ；1 ( ) j 脚为瓿遴霹i 带递滤波辨) 二维小波重建示意图 当一模拟信号取样后，所得到的值必须用在所用的计算机中有效比特表示， 这个被称为量化的过程可以看作是从实数向一个整数的映射。主要分为标量量化 和矢量量化。标量量化就是一般地将数逐个量化，而矢量量化则是把一个以上的 数分成一组，即组成一个矢量，然后按组进行量化编码。 标量量化：设在量化前数的取值范围为1 2 。，2 t ) ，概率分布为p ( z ) ，量化将 k 。，毛) 分成k 个子区间：k n ，无) ， g l , z 2 ) ，z i ，z i + i ) ，k 纠，气) ，芳用一 个量化值gc 来表示属于子空间慷，2 mj 的数。量化器要解决的问题是划分子区间 和设定量化值，即选定k 1 个2 ，( f = l ，女一1 ) 和k 个g t ( f _ 0 ，女- 1 ) 使量化造成 第2 2 页 幽型型型鲨l 一 的失真最小，达到最优量化。最简单的量化方案是均匀量化，即把样本值的整个 取值范围均匀地分成k 个子区问。均匀量化将【z 。，2 t j 均分成k 个子区间后，每个 区间的长度三2 ( 以一) 尼，各子区间以它的中心位置吼。( z ， j r z i + i ) 2 作为量化 量。当待量化值在，矗j 区间内均匀分布时，即j 口( z ) 等于常数时，均匀量化是 最优的，此时占2 最小，这时p 0 ) ：i k ，f 2 = r 1 2 。 1 3 6 预测编码 预测编码的基本思想是通过仅提取每个像素中的新信息并对它们编码来消 除像素间的冗余。这里的一个像素的新信息定义为该像素的当前或现实值与预测 值的差。注意这里正是由于像素问有相关性，所以才使预测成为可能。 d p c m 原理通常也称“线形预测法”。为了便于分析，把像素按某种次序排 成一维序列。b 。ln = i 2 一 ，表示某个像素的灰度值。根据条件熵理论，若 从已知的。“，o 来估计x 一( m 点估计) ，则由于相邻像素间有较大的相关性， 可以较准确地估计出。”，即估计值i 。，( x “，x m ) 近似等于z n ，或预测误差 8 ”2 矗一k 的方差d “较小，并小于原数据的方差贮，对预测值进行编码所需的 比特数要比直接对原数据编码小，从而实现压缩，比特率平坶可减少 扣笋呲瓜。 1 3 7j p e g 2 0 0 0 标准 5 p e g2 0 0 0 与传统j p e g 最大的不同，在于它放弃了j p e g 所采用的以离散 余弦变换( d i s c r e t ec o s i n et r a n s f o r m ) 为主的区块编码方式，而采用以小波转 换( w a v e l e tt r a n s f o r m ) 为主的多解析编码方式。离散子波变换算法是现代谱分 析工具，在包括压缩在内的图像处理与图像分析领域正得到越来越广泛的应用。 此外j p e g 2 0 0 0 还将彩色静态画面采用的j p e g 编码方式与2 值图像采用的j b i g 编码方式统一起来，成为对应各种图像的通用编码方式。 第2 3 页 塑咝塑生兰堡堡苎 j p e g 2 0 0 0 编码器的结构框图如下图( a ) 所示，首先对源图像数据进行离散 小波变换，然后对变换后的小波系数进行量化，接着对量化后的数据熵编码，最 后形成输出码流。解码器是编码器的逆过程如图( b ) 所示，首先对码流进行熵 解码，然后解量化和小波反变换，最后生成重建图像数据。 源图像数据 重建图像数据 j p e g 2 0 0 0 的处理对象不是整幅图像，而是把图像分成若干图像片( i m a g e t i l e s ) ，对每一个图像片进行独立的编解码操作。术语“图像片”( t i l i n g ) 是 指原始图像被分成互不重叠的矩形块，对每一个图像片进行独立的编解码处理。 在对每个图像片进行小波交换之前，通过减去一个相同的数量值对所有的图像片 进行水平移位，如下图所示。 圈慷片础豫片鞋仃离垠小溲变袅 垃 年午 也 乩 牛牛 毕 止乩 止 牛 木平移位 坫 止扯 编码器的最后使用了算术编码器，在j p e g 2 0 0 0 中使用的是姻编码器，m q 编码器在本质上与j p e g 中的q m 编码器很相似m 1 。 整个j p e g 2 0 0 0 的编码过程可概括如下 把原图像分解成各个成分( 亮度信号和色度信号) - 第2 4 页 浙江大学硕士学位论文 把图像和它的各个成分分解成矩形图像片。图像片是原始图像和重建图 像的基本处理单元。 对每个图像片实旎小波变换。 对分解后的小波系数进行量化并组成矩形的编码块( c o d e b l o c k ) 。 对在编码块中的系数“位平面”熵编码。 为使码流具有容错性，在码流中添加相应的标识符( m a k e r ) 。 可选的文件格式用来描述图像和它的各个成分的意义。 在j p e g 2 0 0 0 中，基本的编码引擎是基于e b c o t ( e m b e d d e db l o c kc o d i n gw i t h o p t i m i z e dt r u n c a t i o no ft h ee m b e d d e db i t s t r e a s m s ) 的，下面将详细描述 e b c o t 的算法思想。 j p e g 2 0 0 0 标准的核心算法是e b c o t ，它不仅能实现对图像的有效压缩，同时 产生的码流具有分辨率可伸缩性、信嗓比可伸缩性、随机访问和处理等非常好的 特性。而这些特性正是j p e g 2 0 0 0 标准所要实现的，所以联合摄影专家组才以该 算法作为j p e g 2 0 0 0 的核心算法。 e b c o t 算