（应用数学专业论文）基于小波零树和分形理论的图像压缩研究.pdf

学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取 得的研究成果。 3 、本论文中除引文外，所有实验、数据和有关材料均 是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或 其它机构已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声 明并表示了谢意。 作者签名：鬲南星 日 期；塑缸：s 学位论文使用授权声明 本人完全了解南京信息工程大学有关保留、使用学位论文 的规定，学校有权保留学位论文并向国家主管部门或其指定机 构送交论文的电子版和纸质版：有权将学位论文用于非赢利目 的的少量复制并允许论文进入学校图书馆被查阅；有权将学位 论文的内容编入有关数据库进行检索；有权将学位论文的标题 和摘要汇编出版。保密的学位论文在解密后适用本规定。 作者签名：高凼垂 日 期：2 迪! s 摘要 随着信息网络化的发展，多媒体技术的日益进展，数字图像信息作为最重要的 信息之一，被愈来愈广泛的使用。因其数据量大，图像压缩技术显得越来越重要。 本文介绍了当前几种最为广泛使用的图像压缩编码：小波零树编码和分形编码，讨 论了它们的优缺点及发展前景，并分别对多级树集合分裂算法和d c t 域分形图像编 码进行改进。最后对图像压缩算法进行了总结和展望。本文就是在这种情况下对图 像压缩编码方法做了一些研究工作，主要包括三个方面的内容： 对s p i h t 进行了研究，提出了基于9 7 整数小波变换的改进的s p i h t 。它首先对 图像整数小波分解，然后对低频子带图像采用d p c m 预测编码，对高频子带改变扫 描方式来获得最大系数和按照频率优先的原则输出系数。实验结果表明算法在相同 的输出码率情况下不仅得到了更好的恢复效果，而且缩短了编码时间。 对d c t 域的分形编码算法进行了研究，提出了改进的算法。首先，基于人跟视 觉系统选择平坦块。然后选择出d c t 域中的均匀部分，直接将其直流部分编码输出， 不需分形匹配。为了降低匹配时间，在d c t 域中，定义域块的8 种变换的计算可以 简化为两组内积。结果表明，在相同的匹配误差的情况下，该算法得到了更好的恢 复效果，并且缩短了编码时间。 在对小波系数特征结构分析的基础上针对小波系数的两大特点，分别利用分 形和零树的方式进行小波系数编码。对于分形编码，针对小波高频系数无直流分量 的特点，改变了传统误差距离的选取，通过加入误差校正矩阵，减少了误差累积现 象。理论分析和实验结果表明，相对于一般的分形及零树编码方式，在图像效果方 面和压缩比上，都有很大的提高。 关键词：图像压缩，嵌入零树小波，多级树集合分裂算法，分形，离散余弦变换 a b s a t r a c t w i 廿1t h ed e v e l o p m e n to fi n f o r m a t i o nn e t w o r ka n dm u l t i m e d i at e c h n o l o g y , d i g i t a l i m a g e ，a sak i n do ft h em o s ti m p o r t a n tm e d i a , i su s e dm u c hw i d e l y i m a g ec o m p r e s s i o n b e c o m e sm o r ea n dm o r ei m p o r t a n tf o r g r e a td e a lo fd a t a i nt h i sp a p e r , s o m em o s t p o p u l a rc o m p r e s s i o nc e d i n g ：w a v e l e tz e r o t r e ec o d i n ga n df r a c t a lc o d i n ga n d a r e i n t r o d u c e d ，t h ea d v a n t a g e s ，d i s a d v a n t a g e sa n dd e v e l o p m e n t so ft h e s ea l g o r i t h m sa r e d i s c u s s e d t h ei m p r o v e m e n t sa r em a d eo ns p i h ta n dt h ef m t a li m a g ec o d i n gi nd c t d o m a i n f i n a l l y , t h ec o n c l u s i o n sa n de x p e c t n i o n so fi m a g ec o m p r e s s i o na l g o r i t h m sa r e g i v e n t h em a i nw o r ki n c l u d e st h ef o l l o w i n gf o u ra s p e c t s ： o nt h er e s e a r c ho fs p i h t ，t h i sp a p e rp r e s e n t sa ni m p r o v e ds p l h ta l g o r i t h mo nt h e b a s i so f 9 7 - t a pi n t e g e rw a v e l e tt r a n s f o r m i nt h ei m p r o v e da l g o r i t h m ，a tf i r s tt h ei m a g ei s d e c o m p o s e db yu s i n gi n t e g e rw a v e l e gt h e nt h el o w - - 抒e q u e n c ys u b - i m a g ew a v e l e t c o e f f i c i e n t sa r ep r o c e s s e du s i n gp r e d i c t i v ec o d i n g ，m e a n w h i l e ，t h eh i g h - f r e q u e n c yo n e s a r ep r o p o s e dc h a n g i n gs c a n n i n gm o d et oo b t a i nt h eb i g g e s tc o e f f i c i e ma n du s i n g 行e q u e n c y p r i o r 崎t oe x p o r tt h ec o e f f i c i e n t s t h er e s u l ts h o w sf o rt h es a m eo u t p u tb i t r a t e ，t h i sa l g o r i t h mn o to n l ym a k e st h ei m a g ec o m p r e s s e de f f e c t i v e l yw i t hh i g hp s n r ， b u ta l s oi na ne f f i c i e n tw a yt or e d u c ep r o c e s s i n gt i m e o nt h er e s e a r c ho ft h ef f a c t a li m a g ec o d i n gi nd c td o m a i n ，t h i sp a p e rp r e s e n t sa n i m p r o v e da l g o r i t h m i nt h ei m p r o v e da l g o r i t h m ，a tf i r s t ，p l a i nb l o c k sa r es e l e c t e db a s e d o nh u m a nv i s u a ls y s t e m t h e nb ys e l e c t i n go u tt h eu n i f o r mp a r t si nt h ed c td o m a i n ，t h e d i r e c tc u r r e n te n c o d ed i r e c t l yw i t h o u ta n yf r a c t a lm a t c h i n g f o rm a t c h i n gl i m er e d u c i n g , t h em e a ns q u a r e de r r o rc o m p u t a t i o n so ft h ee i g h to r i e n t a t i o n so ft h ed o m a i nb l o c k sa r e s i m p l yr e d u c e di n t ot w og r o u p so fi n n e rp r o d u c t si nt h ed c td o m a i n t h er e s u l ts h o w s f o rt h es a m em a t c h i n ge r r o r s ，t h i sa l g o r i t h mn o to n l ym a k e st h e i m a g ec o m p r e s s e d e f f e c t i v e l yw i t hh i g hp s n ra n dm u c hb e t t e rv i s u a le f f e c t ，b u ta l s oi na l le f f i c i e n tw a yt o r e d u c ep r o c e s s i n gt i m e b a s e do nt h ec h a r a c t e r i s t i cs t r u c t u r eo fw a v e l e tt o e m c i e n t s ，c o m b i n e dw i t ht w o c h a r a c t e r s ，w eu s ef r a c t a la n dz e r o t r e ec o d i n gt oc o d et h ei m a g e w h e nw eu s et h ef r a c t a l c o d i n g ，w ec h a n g et h ec o n v e n t i o n a lm s eb e c a u s et h e r ei sr i od i r e c tc u r r e n ti nt h ew a v e l e t c o e 塌c i e n t sa n dw eu s et h ee r r o re m e n d a t i o nm a t r i xt or e v i s ew a v e l e tc o e 佑c i e n t s t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l t sp r e s e n t e di nt h ep a p e rs h o wt h a tt h e r ea r e h i g h e rc o m p r e s s i n gr a t ea n dq u a i l t yo f t h ei m a g et h a nt h ec o m m o n l yf r a c t a la n dz e r o t r e e c o d i n gm e t h o d s k e y w o r d s ：i m a g ec o m p r e s s i o n ，e z w ，s p i h t , f r a c t a l ，d c t 2 第一章绪论 在信息化程度越来越高的今天，每天都有大量的信息用数字进行存储、处理和 传送，如医学图像、卫星遥感图像以及办公自动化。尤其近几年来，随着多媒体技 术和互联网技术的迅猛发展，许多信息都是以图像、图形形式存储的，例如，一幅分 辨率为1 0 2 4 7 6 8 ，8 位2 5 6 色的图像需要7 6 8 k b 的存储空间，这对于信息的存储、 访问、处理以及在通信线路上的传输都是巨大的负担。因此，所面临的一个关键问 题就是如何有效地存储、传输图形、图像数据，其中数据压缩方法比起数据的存储 和传输具有更为突出的实用价值和商业意义。其中，图像数据作为数据量最大的一 类，在满足一定的图像质量要求的前提下，如何高效地对图像进行压缩，并且保持 较好的图像质量，这是图像编码人员一直努力研究的重点。 1 , 1 图像编码简介 图像多媒体数据中最为重要的数据类型，其信息量丰富丽且数据量庞大，一幅 数字图像所占的总数据量，由其总像素的灰度所需的二进制数( 即比特数) 决定。 例如，一幅2 5 6 x 2 5 6 的数字图像，如果具有2 5 6 个灰度级，即每个像素用8 b i t ( 一 个字节) 表示，那么其总数据量就是6 4 k 。虽然图像的数据量很大，但是图像的数 据之间高度相关的。一幅图像内部以及视频序列中相邻图像之间有大量的冗余信息， 如空间冗余、时间冗余、结构冗余、信息熵冗余、知识冗余、视觉冗余等。这些冗 余信息是压缩图像数据的出发点。图像编码方法就是尽可能消除这些冗余信息，以 降低表示图像所需要的数据量。 訇像压缩编码技术可以追溯到1 9 4 8 年提出的电视信号数字化，已有5 0 多年的 历史。2 0 世纪五六十年代的图像压缩编码技术由于受到电路技术的制约，仅仅停留 在预测编码、亚采样以及内插复原等技术的研究，还很不成熟。1 9 6 9 年在美国召 开的第一届“图像编码会议”标志着图像编码作为一门独立学科的诞生。到了七八 十年代，图像压缩技术的主要成果体现在变换编码技术上，矢量量化编码技术也有 较大的发展。8 0 年代末，小波变换理论、分形理论、人工神经网络理论、视觉仿真 理论建立，人们开始突破传统的信源编码理论，图像压缩编码向着更高的压缩率和 更好的压缩质量的方向发展，进入了一个崭新的发展时期。 图像压缩编码可分为两类【】j ：一类压缩是可逆的。从压缩后的数据可以完全恢 复原来的图像，信息没有损失，称为无损压缩编码；另类压缩是不可逆的，即从 压缩后的数据无法完全恢复原来的图像，信息有一定损失，称为有损压缩编码。常 用的无损压缩编码有行程长度编码m e ) 、算术编码、霍夫曼编码( h u f f m a n e n c o d i n g ) 等，无失真压缩编码由于其压缩率有一定的极限，目前已经不是研究的 热点，现在主要集中在有损压缩编码和综合编码上。有损压缩编码就是压缩后图像 的某些信息会丢失，可有较高的压缩率。其中变换编码就是将图像光强度矩阵( 时 域信号) 变换到系数空间f 频域信号) 上进行处理的方法。在空间上具有强相关性的 信号，反映在频域上是某些特定的区域内能量常常被集中在一起，或者是系数矩阵 的分布具有某些规律。我们可以利用这些规律在频域上减少量化比特数，达到压缩 的目的。常用的变换编码有k l 变换编码( 均方误差准则下最佳变换编码) 和d c t 编码( 离散余弦变换编码) 。由于d c t 编码性能接近k l 变换编码而运算量小且可 采用快速离散余弦变换f c t 算法，实际中应用更广泛。 而分形编码和小波变换编码是当今最流行和比较适用的两种方法。 分形( f r a c t a l ) 是m a n d e l b r o t 提出的几何学新概念。分形压缩编码的基本原 理是利用分形几何中的自相似性原理来进行图像压缩。所谓自相似性就是指无论几 何尺寸如何变化，景物的任何一小部分的形状都与较大部分的形状极其相似。与 d c t 编码不同，分形编码利用“自相似性”不是临近样本的相关性，而是大范围的 相似性，即图像块的相似性。对相似性的描述是通过仿射变换来确定的，用图像中 的一个子块经过自仿射分形变换来逼近同一图像的另一子块。若给定一幅图像b ， 可以构造一个具有一系列仿射变换的迭代函数系统： 。 x ：w 。，m = 1 , 2 ，使b = r v ( b ) = ij w 。( b ) ( 1 - 1 ) n = l 可以通过存储和传输仿射变换矿的参数实现对图像的编码，即编码的对象就是 仿射变换的参数，由于图像存在高度的仿射冗余度，仿射变换的参数的数据量小于 图像块的数据量，因而可阻实现压缩的目的。分形压缩编码一般分为以下3 步： ( 1 ) 图像划分。一般划分为互不重叠的大小相等的方块。 ( 2 ) 区块与域块的匹配。一般采用比区块大1 倍的域块，由于随机的搜索匹配 比较费时，应事先将域块分类，或事先做好域块库。 ( 3 ) 确定映射参数。使重建图像与原图像之间的范数最小。 分形压缩编码的仿射变换只能逼近原始图像，而不能等于原始图像，因而是有 损压缩，压缩比较高。分形压缩编码是不对称的，它的编码时间比解码时间要长得 多，主要是因为第2 步搜索耗时太长。分形理论与计算机技术结合后发展迅速，用 分形方法在计算机上可实现图像压缩编码，b a m s l e y 采用迭代函数系统i f s 和递归 迭代函数系统r i f s 对几幅图像进行压缩编码，获得了高达1 0 0 0 ：1 的压缩比。随 着分形图像压缩技术的不断改进和完善，它在图像压缩中越来越显示优势。 小波变换的理论是近年来兴起的新的数学分支，它是继1 8 2 2 年法国科学家傅 里叶建立傅里叶变换之后又一里程碑式的发展，解决了很多傅里叶变换不能解决的 难题。傅里叶变换虽然已经广泛地应用于信号处理领域，较好地描述了信号的频谱 特性，取得了很多重要的成果，但傅里叶变换却不能较好地解决突变信号和非平稳 信号的问题。小波变换可以被看作是傅里叶变换的发展，即它是空间( 时间) 和频 率的局部变换。与傅里叶变换一样，小波变换的基本思想是将信号展成一族基函数 之加权和，即用一族函数来表示或逼近信号或函数。这一族函数是通过基本函数的 平移和伸缩构成的。 4 一维信号，( f ) ，其小波变换系数f ( 工k ) 可表示为f ( t ) 和似( 刁的内积，即 f ( j ，女) = 歹j 劢( 茁) 出 吩，女( x ) 是基本小波，其在时间轴上平行移动、频率伸缩可得所有的基波： 吵，。( z ) ：2 彳v ( 2 x 一七) ( 1 - 3 ) 小波逆变换为： 加) = ，( ，后) 歹( 2 。x 一_ j ) ( 1 - 4 ) ， 其中j ，七分别表示尺度、位移参数。 小波变换用于图像编码的基本思想就是把图像进行多分辨率分解，分解成不同 空间、不同频率的子图像，然后再对子图像进行系数编码。系数编码是小波变换用 于压缩的核心，压缩的实质是对系数的量化压缩。根据s m a l l a t 的塔式分解算法， 图像经过小波变换后被分割成4 个频带：水平、垂直、对角线和低频，低频部分还 可阱继续分解。 图像经过小波变换后生成的小波图像的数据总量与原图像的数据量相等，即小 波变换本身不具有压缩功能。之所以将它用于图像压缩是因为生成的小波图像具 有与原图像不同的特性，表现在图像的能量主要集中在低频部分，水平、垂直和对 角线部分的能量则很少：水平、垂直和对角线标征了原图像在水平、垂直和对角线 的边缘信息，具有明显的方向特性。低频部分可以称作亮度图像，水平、垂直和对 角线部分可以称作细节图像。对所得的4 个子图，根据人类的视觉生理和心理特点 分别作不同的量化和编码处理。人眼对亮度图像部分的信息特别敏感。对这一部分 的压缩应尽可能减少失真或者无失真，例如采用无失真的d p c m 编码；对细节图像 部分可采用压缩比较高的编码方案，例如矢量量化编码、d c t 编码等。由于小波变 换具有空间频率局部性、方向性、多分辨率性和带宽在对数频率上等宽的优点， 并与视觉特性接近，可以利用统计特性和视觉特性来提高编码效率，并且用qm f 和金字塔算法还可以实现图像的正交、无冗余分解。基于这些优点，利用小波变换 可以较好地实现图像的变换编码。 s h a p i r o 提出小波零树编码方案后，由于充分利用小波系数的不同尺度对应空间 的相关性，使图像压缩编码技术提高到了一个新的水平。对图像进行小波变换，研 究表明，在众多的小波变换编码方法中，零树编码利用不同尺度小波系数之间的自 相似性。在不损失编码效率的前提下，能够产生嵌入式码流，被认为是迄今为止最 有效的小波系数编码方法。 由于分形编码和小波零树编码有以上优点，因此今后主要研究方向应在改进小 波零树与分形编码与结合小波零树和分形进行编码。 1 2 本文主要研究工作和创新点 围绕当今图像压缩的热点，本文针对小波零树编码和分形编码在静止灰度图像 上的应用展开研究，在多级树集合分裂算法和基于d c t 域分形的编码算法分别进行 改进，减少了算法的复杂度，在同等比特率的情况下缩短了运行时间和提高了图像 恢复质量： f 1 ) 对s p i h t 进行了研究，提出了基于9 - 7 整数小波变换的改进的s p i h t 。它首 先对图像整数小波分解，然后对低频子带图像采用d p c m 预测编码，对高频子 带改变扫描方式来获得最大系数和按照频率优先的原则输出系数。实验结果表 明算法在相同的输出码率情况下不仅得到了更好的恢复效果，而且缩短了编码 时间。 f 2 1 对d c t 域的分形编码算法进行了研究，提出了改进的算法。首先，基于人 眼视觉系统选择平坦块。然后选择出d c t 域中的均匀部分，直接将其直流部分 编码输出，不需分形匹配。为了降低匹配时间，在d c t 域中，定义域块的8 种变换的计算可以简化为两组内积。结果表明，在相同的匹配误差的情况下， 该算法得到了更好的恢复效果，并且缩短了编码时间。 1 3 章节安排 全文共分七章。 第一章对图像编码进行简介。 第二章主要介绍图像压缩的基本原理和方法以及评价的技术指标。 第三章介绍小波变换的特点之后，主要介绍嵌入式小波零树编码的各种方法。 第四章主要介绍分形图像压缩的理论基础和压缩过程并阐述当今分形图像压 缩的现状和前景。 第五章主要介绍了对多级树集合分裂算法的缺点并对其进行改进。 第六章主要介绍了基于d c t 域分形图像编码算法及其缺点并对其进行改进。 第七章主要介绍了结合小波零树和分形理论的基于小波系数分类的混合编码， 并与分形预测图像编码进行比较。 6 第二章图像压缩的基本原理和方法 2 1 图像压缩的基本原理 图像信息是人类世界和人类自身的重要源泉。图像是用技术手段将二维或者三 维空间中具有明暗( 灰度) 或色彩变化的景物再现出来的视觉信怠。 图像具有以下特性：确切性，视觉信息比听觉信息易于确认： 由于图像信息具有以上特性，它的信息量特别庞大。 数据压缩就是以最小的数码( 比特数) 表示信源所发出的信号，减少必须分配 给指定消息集合或者数据采样集合的信号空间的数值。数据压缩的原理应从信源和 信宿两个方面进行分析。信息论的观点认为信源中或多或少地含有自然冗余度，这 些冗余度即来自信源本身的相关性，又来自信源概率分布的不均匀性。从信息论我 们可得到两个重要的结论： ( 1 ) 离散无记忆信源的冗余度寓于信源符号的非概率分布之中，这是数据压缩 的基本途径之一。 ( 2 ) 联合信源的冗余度也寓于信源间的相关性中，消除或减少它们之间的相关 性，使之成为几乎不相关信源，是数据压缩的又一条基本途径。因此消除或减少信 源的冗余度是数据压缩的基本依据。图像数据的冗余包括以下几类： ( i ) 空间冗余。在同一幅图像中，规则物体或规则背景的表面物理特征具有相 关- 胜。这些相关性在相应的数字图像数据中表现为数据冗余。 ( 2 ) 时间冗余。图像序列中前后两帧图像之间的相关性很大，这反映为时间冗 余。空间冗余和时间冗余是图像数据中广泛存在而最重要的冗余。 ( 3 ) 信息熵冗余。信息熵是信源的平均信息量。信源以等概率分布时，熵为最 大值。熵最大值和非等概率分布时熵值之间的差值就是熵值的冗余度，称为信息熵 冗余。 ( 4 ) 视觉冗余。人类的视觉系统对图像的感知是非线性和非均匀的。充分利用 视觉特性是图像压缩编码从信宿角度获得数据压缩的基本依据。 ( 5 ) 结构冗余。有些图像在较大的区域存在很强的纹理结构，称为结构冗余。 如果已知这些纹理的分布模式，可以通过某一过程生成图像。 ( 6 ) 知识冗余。对许多图像的理解、分析综合与一些基础知识有关。对于某些 图像内容确定的特定场合，可由先验知识、背景知识一类规律化的结构，建立图像 背景模型。 f 7 ) 局部相似性冗余。给定图像菜一区域，往往可以在该区域附近找到一个更 大的区域，两者在仿射变换下相等或非常接近。 ( 8 ) 图像区域的相同性冗余。在图像的两个或多个区域所对应的所有像素值相 同或相近，从而产生的数据重复性存储。 ( 9 ) 纹理的统计冗余。有些图像纹理在统计意义上服从某一分布规律，利用这 种性质也可以减少表示图像的数据量。 7 2 2 图像压缩方法的分类和评价的技术指标 图像压缩就是去掉各种冗余和不相干的信息，保留有用信息，将一个大的数据 文件转化成较小的数据文件。图像压缩的过程就叫做编码，图像恢复的过程叫做解 码。根据解码后的数据是否与原始数据一致，图像编码方法可以分为无损编码和有 损编码两种。前者在对原图像编码后的经对应的解码算法处理可以获得与原图像完 全一样的重建图像；后者生成的图像经解压算法处理后与原图像在视觉上保持一致， 但有一定的信息损失。一般说来，压缩比越大，视觉上的一致性越差。 图像编码常用的技术指标主要有两个方面”j ：压缩比或压缩率( 见公式2 - 1 ) 和保真度( 包括主观失真和客观失真) ；此外，压缩和解压缩过程消耗的时间也经常 需要关心的。 蹴t = 器裂糕压释丽1 协， 压缩前的图像比特数一压缩比 7 压缩后的图像允许有一定误差，对图像质量的评价方法以保真度为准则，它包 括客观和主观两个方面。前者是以压缩前后图像的误差来度量，目前采用较广的是 峰值信噪比( p s n r ) 。 其中，m ，为图像的宽和高，g 如力指原始图像，m 力指压缩后的图像。 被处理的图像最终由人来观察和评价的，用人的主观感觉来评价具有实际意 义。因为同一幅图像在不同人看来可能有不同的观察效果，主观质量评价是一种统 计意义上的结果，主观质量评价标准如下表2 - 1 ： 表2 1编码质量的主观评价标准 数值判分 54321 质量级别极好良好通过勉强不满意 失真级别不察觉刚察觉但不察觉且稍微可厌但不反很差令人反 讨厌 讨厌 感感 2 3 图像编码方法的介绍 ( 1 ) 行程长度编码( r l e ) 行程长度编码( r u n 1 e n g t he n c o d i n g ) 是压缩文件的一种最简单的方法。它的做法 是把一系列的重复值( 例如图像像素的灰度值) 用一个单独的值再加上一个计数值 来取代，比如有这样一个字母序列a a b b b c c c c d d d d d ，它的行程长度编码就是 2 a 3 b 4 c 5 d 。这种方法实现很容易，而且对于具有长重复值的串的压缩编码很有效。 例如对于有大面积的连续阴影或者颜色相同的图像。使用这种方法压缩效果很好。 f 2 1 霍夫曼编码 霍夫曼( h u f f m a ne n c o d i n g ) 是常用的压缩方法之一，它是通过更有效的代码代 替数据来实现的。它的基本思路是出现频率越高的值，其编码长度越短，反之出现 频率越低的值，其对应的编码长度越长。 霍夫曼编码很少达到8 ：1 的压缩比，此外它有两个不足：1 1 它必须精确统计出 原始文件中每个值的出现频率，如果没有这个精确统计，压缩的结果大打折扣，甚 至达不到压缩的效果。霍夫曼编码通常要经过两遍操作，第一遍进行统计，第二遍 产生编码，所以编码的过程是比较慢。另外由于各种长度的编码的译码过程也是比 较复杂的，因此解压缩的过程也比较慢2 ) 它对于位的增删比较敏感。由于霍夫曼编 码的所有位都是合在一起的而不考虑字节分位，因此增加一位或者减少一位都会使 译码结果面目全菲。 ( 3 ) 预测及内插编码 一般在图像中局部区域的像素是高度相关的，因此可以用先前的像素的有关灰 度知识来对当前像素的灰度进行统计。这就是预测。而所谓内插就是根据先前的和 后来的像素的灰度知识来判断当前像素的灰度情况。如果预测和内插是正确的，则 不必对每一个像素的灰度进行压缩，而是把预测值和实际像素值之间的差值经过熵 编码后发送到接受端。在接受端通过预测值加差值信号来重建原像素。 预测编码是数据压缩技术的一个重要分支，它可以获得比较高的编码质量，并 且实现比较简单。但这种方法的压缩能力有限，而且精确的预测有赖于图像特性的 大量的先验知识，并且必须作大量的菲线性运算，因此一般不单独使用，丽是通常 与其他编码方法配合使用。如在j p e g 中，使用预测编码技术对d c t 直流系数进行 编码，而对交流系数则使用量化十游程编码+ 霍夫曼编码。 ( 4 ) 矢量量化编码 矢量量化编码利用相邻图像数据阀的赢度相关性，将输入图像数据序列分组， 每一组m 个数据构成n l 维矢量，一起进行编码，即次量化多个点。根据香农率 失真理论，对于无记忆信源，矢量量化编码总是优于标量量化编码。 在v q 算法中，图像的各种相关信息( 如：各像素点间、各块之间以及相邻编 码地址间等) 可通过有效的码书设计得以充分消除。编码前，先通过大量样本的训 练或学习或自组织特征映射神经网络方法，得到一系列的标准图像模式，每一个图 像模式就称为码字或码矢，这些码字或码矢合在一起就称为码书，码书实际上就是 数据库。输入图像块按照一定的方式形成一个输入矢量。编码时用这个输入矢量与 码书中的所有码字计算距离，找到距离最近的码字即找到最佳匹配图像块。输出 其索引( 地址) 作为编码结果。解码过程与之相反，根据编码结果中的索引从码书 中找到索引对应的码字( 该码书必须与编码时所用的码书一致) ，构成解码结果。由 9 此可知，矢量量化编码是有损编码。目前使用较多的矢量量化编码方案主要是随机 型矢量量化，包括变化域矢量量化，有限状态矢量量化，地址矢量量化，波型增益 矢量量化，分类矢量量化以及预测矢量量化等。 f s ) 变换编码 变换编码就是将图像光强矩阵( 时域信号) 变换到系数空间( 频域信号) 上进 行处理的方法。在空间上具有强相关的信号，反映在频域上是某些特定的区域内能 量常常被集中在一起，或者是系数矩阵的分布具有某些规律。我们可以利用这些规 律在频域上减少量化比特数，达至q 压缩的目的。由于正交变换的变换矩阵是可逆的 且逆矩阵和转置矩阵相等，使解码运算是有解的且运算方便；更重要的是正交变换 在变换结果上可使能量向低频成分方向集中，边缘信息和高频信息在高频成分上得 到反映，从而图像压缩率被压缩；编码方面，对低频成分分配较多的比特数，对高 频成分分配较少的比特数。 变换总是选用正交变换来做，常用的变换有k - l 变换、d c t 变换和小波变换等。 f 6 ) 分形编码 分形( f r a c t a l ) 的概念是数学家bbm a n d e l b r o t 于1 9 7 5 年提出的，他把分形定义 为“一种由许多个与整体有某种相似性的局部所构成的形体”。b b m a n d e l b r o t 通过 分析大量的传统数据发现，小尺度下的波动特性与大尺度下的波动特性有相似性。 基于此，他提出了分形这个区别于传统的、超越尺寸的新概念，即不把微小的变化 与宏观的、大的变化分离开来，而是把它们紧密联系起来。也就是说分形无所谓大 尺度与小尺度，而是超越一切尺度，并存在着大小尺寸的相似性。这就是分形概念 的核心。 概括地说，分形压缩的方法是利用图像处理技术把原始图像分割成若干子图 像，然后为每一个子图像寻找迭代函数( i t e r a t e df u n c t i o n ) ，子图像以迭代函数的形 式存储。由于这样的迭代函数一般只需要几个数据表示即可，所以分形压缩可以达 到很高的压缩比。解压缩时，只要调出每一个子图像对应的迭代函数进行反复迭代， 就可阻恢复出原来的子图像。 分形压缩是一种思想新颖、很有潜力的图像压缩技术，与经典的静态图像压缩 技术d c t 相比，它具有如下特点： 1 ) 压缩比高压缩比取决于图像分割后所产生的子块的大小。子块取得越大， 压缩比就越高 2 ) 不受分辨率的影响由于分形变换可把图像划分成大得多、形状复杂得多的 分区， 故压缩所得的文件的大小不会正比于图像象素数目的增加即分辨率的提高。 3 ) 非对称性分形压缩编码是非对称的，压缩时计算量较大，所需时间较长， 而解压缩速度很快。 这些特点使得分形压缩技术特别适用于一次压缩、多次解压缩的场合。 o 3 1 小波变换 第三章嵌入式小波零树编码方法 传统的变换编码一般都是基于d f t 变换( 即傅立叶变换) 的。傅立叶变换揭示 了时间餐数与频谱函数之闻的内在联系，反映了信号在“整个”对问范围内的“全 部”频谱成分。从而用傅立叶变换的方法提取信号频谱时，需要利用信号的全部时 域信号，以至信号的局部发生变化会影响到整个频谱。例如，对于一个低频信号， 如果给它在某一时刻t o 增加一个冲激，那么它的频谱就立刻变成宽带频谱。值得注 意的是，根据这个宽带频谱只能辨别出信号中存在着冲激，但无法确定这个冲激发 生的时间位置。这表明傅立叶分析没有时间定位或时间局域化的能力。具体到图像 压缩中，可以看到利用d f t 变换压缩后的图像在水平和垂直方向上易出现晕圈和幻 影，产生“斑块”效应。为了改进傅立叶变换，产生了w f t 变换( 即窗口傅立叶 变换) ，即用一个具有适当宽度的窗函数从信号中取出一段来做傅立叶分析，于是得 到信号在这段时间内的局部频谱，如果再让窗函数沿时问轴不断移动便能够对信号 逐段进行频谱分析。但是w f t 变换对不同的频率总是使用宽度相同的窗，即不能 按照不同的频率来自适应调整窗的宽度，然而在实际应用中，为了精确确定信号中 的高频现象发生的时间位置应该使用窄时域窗，为了全面观察低频现象应该使用宽 时域窗“。 为了继承傅立叶变换的优点，同时克服它的缺点，提出了小波变换。小波变换 可以看成是一组短时傅立叶变换的汇集，这些短时傅立叶变换对不同的信号使用了 宽度不同的窗函数，即高频用窄时域宙，低频用宽时域窗。与傅立叶变换相比，小 波变换是时间和频率的局域变换，能更加有效的提取信号和分析局部信号。此外 小波变换可以将图像层按小波基展开，所以可以根据图像信号的性质以及事先给定 的图像处理要求确定到底要展开到哪一级为止，从而不仅能有效地控制计算量，满 足实时处理的需要，而且可以方便的实现渐进传输；利用小波变换具有的放大、缩 小和平移功能，可以方便地产生各种分辨率的图像，从而适应于不同分辨率的图像 设备和不同的传输速率的通信系统【”。 连续小波变换( c w t ) 的定义为f 4 ( c i v t g f ) ( a , b ) = l a i 。“e f v 吣一b ) a ) d tb ，1 1 其中，函数系虬。o ) = j a i 。”p ( 0 6 ) 口) 称为小波函数。连续小波变换的逆变 换( i c w t ) 为： 厂( r ) = q 。e e ( c 胛；似，6 ) y 叩( f ) a 2 d a d b ( 3 - 2 ) 将连续小波的尺度参数a 和时移参数b 离散化，并取口= 2 和6 = k 2 j ，而且信号 在时间上也离散化为f i n ) ，则可得离散小波( d w t ) 为： ( d 嘿厂) ( 2 7 ，k 2 ) = 2 - ：2 ，( h ) 孑( 2 一，”一七) ( 3 - 3 ) 其逆变换为【“1 ： + ( n ) = 2 - j 2 ( d 啊，似2 ，k 2 7 ) y ( 2 一，m 一女) ( 3 - 4 ) 将一维小波推广到二维可得二维小波为p y j 。，。( x ，y ) = 2 - j 妒( 2 7 x m ，2 一。y h )( 3 5 ) 在小波的选择上，一般尽量选择具有紧支撑集、对称的、正交的小波作为母小 波来构造小波函数。小波级数的系数一般采用塔式算法( m a l l a t 算法) 来计算。由 于根据定义来计算离散小波复杂度很高，所以离散小波一般采用快速算法，最主要 的算法有 l r o u s 算法和m a l l a t 算法。图3 - i 为离散小波的分解和重建示意图。 团园 勰 固毋 叵 团9 固毋 团 团团围困 一一一一 野 丑 卧 趴 4 团 母 卜 + 争 下采样：对列滤波时，两列去一列，对行滤波时，两行去一行 上采样：对列滤波时，两列中加0 ，对行滤波时，两行中加0 图3 - 1小波分解和重建算法示意图 对图3 - i 所示的二维小波分解与重构，利用其可分离特性，在实现时分别由按 行进行一维小波变换，然后再对按行变换后的数据按列进行一维小波变换来完成。 由于图像信号总是有限区域的，存在如何处理边界的问题。典型的处理方法是周期 扩展和反射扩展。在用小波变换进行图像压缩时，由于边界的不连续性，会使得在 边界处的小波变换系数的衰减变慢，从而影响图像的压缩比，因而在图像压缩应用 中，若使用的是具有对称性质的双正交小波滤波器，一般对边界采用反射扩展的方 式，使边界保持连续，以提高压缩性能。 在图像变换中使用的正交小波并不是严格正交的。因为各滤波器组系数的个数 有限且不是对称的，所以用这种有限长离散滤波器构造的有限支集标准正交小波基， 由于其系数不对称，将导致出现非线性相位，从而对图像编码不利。为了使小波基 具有对称性以获得线性相位，从而必须放宽对小波基的正交性要求。所以图像变换 中的正交性指低通分析滤波器h w 与高通合成滤波器g 。正交，低通合成滤波器吃 与高通分析滤波器g 一。正交。各滤波器组的系数个数有限且是对称的，从而能够获 得线性相位，并且系数对称还会带来运算结构简单和便于边界处理等优点。 图像信号经第一层小波分解后得到4 个子带，即1 个逼近信号( 水平和垂直方 向均为低频分量) 和3 个细节信号( 水平和垂直方至少有一个高频分量) 。逼近信号 可继续进行第二层分解。一般而言，分解层数为k 时，分解后的总子带数为3 k + l 。 分解层数越多，越能充分利用各层细节子带中具有相同方向和位置的系数之间的相 关性，有利于提高图像压缩编码的效率。但同时应注意到，当一个子带要被分解成 更小的4 个子带时，从编码角度来看只有当分解所需的总位数比分解前更小( 即分 解后的信息熵值更小) 时，才值得分解，因此实际中选择的分解层数通常为3 。图 3 2 为3 层小波分解示意图。 通过小波变换，图像能量分布发生了变化，主要能量集中在少数几个小波系数 上，从而有限的少数小波系数就能代表整幅图像。对这些系数进行量化和适当的位 分配，即可达到压缩编码的目的。 编码一般采用两种小波变换，即9 7 小波变换和5 3 小波变换。9 7 小波变换是 不可逆的，用于有损压缩，但是变换后得到的小波系数绝对值比较小，适合比特平 面编码。5 3 小波变换是可逆的，主要用于无损压缩，也可用于有损压缩，但是变 换后得到的小波系数绝对值比较大，从而经比特平面编码后得到的码流比较大。以 x ( n ) 表示原始输入信号，y ( n ) 表示输出信号，下面将给出两种小波的一维离散变 换公式。注意：在正变换后对信号进行了下采样，在反变换前进行了上采样。要得 罱 到对应的二维小波变换只须对行列分别进行一维小波变换。 l l 3h l 3 h l 2 l h 3h h 3 h l l l h 2h h 2 l h lh h l 图3 - 2 图像信号的3 层正交小波分解后的子带位置 5 3 离散小波变换的计算式如下【”： f 】，( 2 蚱+ 1 ) = x ( 研+ 1 ) 一i 2 i 望! l 笋l 旧m c 咖f 蓝等f 。石 5 3 离散小波反变换的计算式如下1 5 9 7 离散小波变换的计算式( 注意此计算式是多步计算式) 如下【5 】 ( 3 7 ) y ( 2 n + 1 ) - - - x ( 2 n + 1 ) + ( 口+ x ( 2 n ) + x ( 2 n + 2 ) 】) y ( 2 n ) 卜x ( 2 n ) + ( + ( y ( 2 n - 1 ) + y ( 2 n + 1 ) 】) ，y ( ( 2 2 珂n ) + 卜1 ) y - ( - 2 y 胛( ) 2 + n ( + j 1 ) 即+ ( y 胛* 一 y 1 ( ) 2 + n ) y + ( 2 y ( + 1 ) 】2 n + ) 2 ) 】) ( 3 - 8 ) ，( 2 珂) 一y ( 2 胛) + ( j + 】，( 2 胛一1 ) + y ( 2 胛+ 1 ) ) 、 y ( 2 n + l 、k + r ( 2 n 4 - 1 ) y ( 2 n ) 卜( 1 足) + y ( 2 n ) 1 4 9 7 离散小波反变换的计算式( 同样此计算式也是多步计算式) 如下【5 l 爿( 2 厅) 七_ k + y ( 2 n ) x ( 2 n + 1 ) _ 一( 1 k ) + y ( 2 n + 1 ) x ( 2 n ) 卜x ( 2 n ) 一( 占4 x ( 2 n 1 ) + x ( 2 n + 1 ) 】) ( 3 - 9 ) x ( 2 n + 1 ) 一x ( 2 n + 1 ) 一( y4 ，r ( 2 月) + x ( 2 n + 2 ) ) 、 x ( 2 n ) 4 - - x ( 2 n ) 一( + ( x ( 2 n - 1 ) + x ( 2 n + 1 ) ) x ( 2 n + 1 ) 卜x ( 2 n + 1 ) 一( 口4 x ( 2 n ) + x ( 2 n + 2 ) ) 其中在9 7 离散小波变换和反变换中，常数的取值如下：a 一15 8 6 1 3 4 3 4 2 ，b 一0 0 5 2 9 8 0 1 1 8 ，y =