（模式识别与智能系统专业论文）基于嵌入式编码的图像压缩技术的研究.pdf

中文摘要 随着计算机多媒体技术的不断发展，在存储和传输大量的图像数据时，图像 压缩将起到越来越重要的作用。嵌入式编码是一种新的编码方式，它可以提供某 种程度上的可伸缩性，也就是随着接收比特的增多，渐进的恢复图像。为了满足 目标比特率或者误差要求，通过监视编码的一些参数，嵌入式的编码器可以在任 何一点终止编码。同样解码器可以在任何一点截断比特流，重构图像。嵌入式编 码可以应用于网络，无线传输，图像浏览，特别适合于容易产生误差的环境。 本文首先介绍了小波变换和信息论与编码的基本理论，比较了各种图像压缩 的基本方法和静止图像压缩标准。对嵌入式图像编码的理论和方法进行了研究。 详细介绍了s h a p i r o 提出的嵌入式零树小波( e z w ) 算法，在e z w 算法的基础 上对s p i h t 算法进行了研究。以e z w 算法的零树结构为基础的s p i h t 算法更 高效地实现了图像的嵌入式编码，是当今最流行的图像编码方法之一。但是，在 s p i h t 算法的运算过程中，需要用到3 个链表来存储小波系数和小波系数集合的 重要性信息，耗费了大量的内存资源，不利于硬件实现。为了节省编码过程中的 内存，本文着重研究零树编码算法的无链表实现问题，详细分析了无链表零树编 码算法( l z c ) 和无链表s p i h t 算法( n l s ) ，分析了它们的基本原理和算法实 现。在n l s 算法的基础上，提出了一个更加节省内存的改进方案，即用函数代 替n l s 算法中的用来记录小波系数的后代系数最大值的向量，从而达到用更少 的内存来实现s p m t 算法的目的。 在研究过程中，用c 语言实现了改进的n l s 算法，并在w i n d o w s 平台下用 v i s u a lc + + 6 0 的编译器下编译通过。运行结果表明，在明显节省内存的情况下， 改进的n l s 算法在同样的码率下，达到了接近s p i h t 算法的重建图像效果，重 建图像质量优于l z c 算法。 关键词：嵌入式图像编码零树s p i h t 链表n l s a b s t r a c t 、矾t ht 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 i q u e i m a g ec o m p r e s s i o np l a y sam o r e i m p o r t a n tr o l e i nt h es t o r a g ea n dt r a n s f e ro fm a s si m a g ed a t a e m b e d d e di m a g e c e d i n gi san e wc o d i n gm e t h o da n dc a l lp r o v i d et h ep o s s i b i l i t yt op r o g r e s s i v e l y r e c o n s t r u c tr e p r o d u c t i o n so f t h ei m a g eb e t t e ra n db e t t e r 雒t h ec o d i n gi m a g eb i ts t r e a m i sr e c e i v c dm o r ea n dm o r e t h eo u t p u tb i ts t r e a mo ft h ee m b e d d e dc o d ec a nb e t r u n c a t e da n dt h ei m a g e sf o rp r a c t i c a la p p l i c a t i o n sc a nb er e c o n s t r u c t e dt oa c h i e v e v a r y i n gd e g r e e so fs c a l a b i l i t ya n dd i f f e r e n tt a r g e tb i tr a t e so rd i s t o r t i o n e m b e d d e d i m a g ec e d i n gi se s p e c i a l l yf i t f o rt h ec h a n g e f u la n df a l l i b l ee n v i r o n m e n t ，s u c ha s i n t e r a c t w i r e l e s st r a n s m i s s i o n ，i m a g eb r o w s e ，a n de t c t h eb a s i ct h e o r yo f w a v e l e tt r a n s f o r m ，i n f o r m a t i o na n dc o d i n ga r ei n t r o d u c e di n t h i sp a p e r s e v e r a li m a g ec o m p r e s s i o nt e c h n i q u e sa n ds t a n d a r d sa r ec o m p a r e d t h e n , t h et h e o r ya n dm e t h o d so fe m b e d d e di m a g ec o d i n ga r es t u d i e d a f t e ri n t r o d u c i n gt h e e m b e d d e dz e r o t r e ew a v e l e t ( e z w ) a l g o r i t h mi nd e t a i l ，t h es e tp a r t i t i o n i n gi n h i e r a r c h i c a lt r e e s ( s p i h t ) a l g o r i t h mi sp r e s e n t e d s p ta l g o r i t h m w h i c hi sb a s e d o nt h ez e r o t r e cs t r u c t u r e ，h a sb e e np e r f o r m e dm o r ee f f e c t i v e l yi nt h ee m b e d d e di m a g e c e d i n g i ti st h em o s tp o p u l a rm e t h o da tp r e s e n t b u ti nt h ep r o c e s so fs p i h tc o d i n g , t h r e el i s t sm u s tb eu s e d t h e yc o n s u m eal o to fm e m o r yt os a v et h es i g n i f i c a n t i n f o r m a t i o no ft h ew a v e l e tc e e m c i e n t sa n dw a v e l e tc o e f f i c i e n t ss e t s t h es p f r a l g o r i t h mi sd i f f i c u l tt ob ea p p l i e di nh a r d w a r eb e c a u s eo fi t sl a r g es p a c eo fs t o r a g e t h ep r o b l e mo f s p 王tw i t h o u tl i s t si ss t u d i e dt os a v et h em e m o r yv o l u m e a n db a s e d o na n a l y s i so ft h el i s t l e s sz e r o t r e ec o d i n g ( l z oa l g o r i t h ma n dt h en ol i s ts p i h t ( n l s ) a l g o r i t h m , an e ws c h e m eo fn l sh a sb e e np u tf o r w a r di n t h i sp a p e r 1 1 1 e s c h e m eu s e af u n c t i o nt oj u d g ew e a t h e rt h ew a v e l e tc o e f f i c i e n t ss e t sa r es i g n i f i c a n t ， i n s t e a do ft h ev e c t o rw h i c hs a v et h em a x i m u mv a l u eo ft h ew a v e l e tt o e 伍c i e n t ss e t s t h ei m p r o v e ds c h e m eo f n l sc o n s u m e sl e s sm e m o r yt h a nt h ec l a s s i cn l sa l g o r i t h m i nt h er e s e a r c hp r o c e s s t h en e ws c h e m eo fn l sh a sb e e np r o g r a m m e db yt h ec l a n g u a g e t h ep r o g r a mh a sb e e nc o m p i l e db yv i s u a lc + + 6 0c o m p i l e ri nw i n d o w s p l a t f o r m t h er e s u l t ss h o wt h a ti nt h es a n l cb i tr a t e t h eq u a l i t yo fi m a g er e s t r u c t u r e d b yt h ei m p r o v e dn l sa l g o r i t h mi sc l o s et ot h ei m a g er e s t r u c t u r e db ys p m t a n ds a v e m e m o r ym a r k e d l y 1 1 l er e c o n s t r u c t e di m a g eq u a l i t yo f t h ei m p r o v e dn l sa l g o r i t h mi s b e t t e rt h a nt h el z c k e yw o r d s ：e m b e d d e di m a g ec e d i n g ， z e r o t r e e ，s p i h t , l i s t , n l s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得叁盗盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：羿多萄 签字日期：2 。 年月re 1 学位论文版权使用授权书 本学位论文作者完全了解苤盗盘鲎有关保留、使用学位论文的规定。 特授权鑫鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：导师签名： 签字日期：2 一年月r 日签字日期：”，彳年月厂日 第一章绪论 1 1 引言 第一章绪论 随着计算机技术、通信技术、信息处理技术、微电子技术和互联网络技术的 高速发展，人类社会从工业化社会进入了信息化社会，以计算机技术为代表的信 息技术已成为现代社会发展的核心技术。在日常生活中，各种各样的信息每时每 刻都在通过信息高速公路向生活的各个角落传播。面对大量的信息，人们需要更 加直观的形式来表示信息，使之能够更好的被理解和接受。因此，集视频、图像、 音频、语言、文字等多种媒体为一体，具有集成性、同步性、交互性三大特性的 多媒体技术应运而生，并获得了空前高速的发展。 在多媒体信息中，在相同的条件和时间内，视觉图像信息给人的信息量特别 巨大，视觉要比其他感觉所感受到的信息多得多。在人们所接受的信息中，绝大 多数都是由视觉获得的。因此，视频和图像信息将成为多媒体信息的主要内容， 图像与视频信息的获取、处理、存储与传输也就相应地成为了现代信息技术研究 的热点之一。 1 2 图像压缩技术简介1 】 1 2 1 图像为什么需要压缩 图像是指光辐射能量作用在客观物体上，经过反射或透射( 或物体本身所含 发光物质所发出的光能量) 在人的视觉器官中显现出的物体视觉信息。例如，可 见光反射形成的彩色图像可以表示为： ( x ，y ，旯，f ) = i ( x ，y ，a ，t ) r ( x ，y ，a ，f ) ( 1 - 1 ) 其中，i 表示t 时刻入射光的亮度，r 表示反射系数。 为可见光的波长，t 为时间。 如果图像与 和t 无关，则为单色静止图像。图像通常来源于自然景物，其 原始的形态是连续变化的模拟量。模拟量在处理和传输过程中容易受到干扰，产 生失真。作为现代信息技术核心的计算机技术，是以数字电子技术为基础的。模 拟量不便于通过计算机进行处理，因此需要对图像信息进行数字化。通过将原始 图像信息进行离散化、量化、编码，形成数字图像，因此，数字图像是原始模拟 第一章绪论 图像的离散近似。图像以数字形式处理和传输，具有质量好，可靠性高；可以中 继传输和多次复制，而不会造成噪声和非线性失真的累积：便于进行加密，便于 用超大规模集成电路( v l s i ) 芯片实现，便于和计算机联网等一系列优点。 图像信息的数字化在给我们带来众多便利的同时，也有其不利的一面。丰富 的图像信息，意味着巨大的数据量。数字图像需要更多的比特( b i t ) 数来存储或 传输，造成存储与传输的高成本。 以下列出几种重要图像信源信号在未经压缩的情况下的原始数据速率： 图像：5 1 2 5 1 2 像素彩色图像2 4 比特像素3 m b i t 视频：6 4 0 x 4 8 0 像素彩色图像x 2 4 比特像素3 0 帧秒- 2 2 1 m b p s 高清晰度数字电视：1 2 8 0 7 2 0 像素彩色图像2 4 比特像素6 0 帧秒 = 1 3 g b p s 对于数字视频信息，一张c d r o m 容量6 5 0 m b y t e 可存储2 3 5 秒( 一部电 影要2 2 9 张c d r o m ，还达不到高清晰的视频效果) ，d v d 一5 容量4 0 千兆比特 可存储3 分钟。 此外，在一些特殊领域，如遥感、医学、虚拟现实等，都面临着信息量非常 大的数字图像对象。例如在计算机图形领域中，虚拟三维现实的数字图像中记录 着来自数百个不用空间角度的信息，一帧简单的场景就涉及几百兆的数据量【”。 由此可见，数字图像的数据量非常巨大，如果不经过压缩，数字图像传输所 需的高传输速率和数字图像存储所需的巨大容量将成为数字图像通信、存贮的障 碍【3 1 。为了体现数字化的优点，使高速传输和处理图像成为可能，必须对数字图 像进行更为本质和简洁的表达。图像压缩编码提供图像的简洁数字化表示，用尽 量少的比特数来表征图像，同时保持重建图像的质量。使它符合预定应用场合的 需求。 1 2 2 数字图像压缩的可行性【1 】【3 】【4 】 图像信息之所以可以进行压缩，是因为原始图像数据高度相关，存在很大的 冗余度。如果将所有数据都进行存储和传输，将造成了比特数的巨大浪费。冗余 从本质上表现为两大类：熵冗余和信息冗余。 熵是信息理论中的重要概念，可以理解为待编码符号序列中每个符号的平均 信息量。熵的具体定义将在第二章中介绍。 熵冗余的原因是信源本身的相关性以及信息码元在信息流中出现的概率不 均匀。以一帧n 比特精度的数字图像为例，原有的光栅矩阵格式只有当各像素完 全统计独立，而且所有2 。种可能像素值等概率出现的情况下才是最有效的存储 形式，此时没有熵冗余。而人们生活中所遇到的种种实际图像，总要表现出一定 第一章绪论 的场景和内容，这正是图像中相关性的表现，这样的图像各个像素之间就不可能 是完全独立的。 正是由于数字图像中存在熵冗余，使得去除熵冗余、进行图像压缩提供了可 能。 图像中的熵冗余有多种形式。图像内相邻像素之间存在较大的相关性，由此 引起的冗余被称为空间冗余；运动图像的相邻帧存在的相关性，引起的冗余称为 时间冗余。多光谱遥感图像各谱间存在的相关性，引起的冗余称为频域冗余；用 相同码长表示不同出现概率的符号，造成的比特数的浪费，从而引起的冗余称为 符号冗余。以上所述的冗余均属于熵冗余。 在编码时仅仅去除图像的熵冗余，并不会丢失图像的信息，这样经过压缩编 码的图像，其平均码长不会小于图像的熵。这种编码的结果使得经过对图像编码 进行解码后重建的图像能够与原始图像保持一致，称为无失真编码，也称为信息 保持编码或熵保持编码，简称熵编码。采用无失真编码方法对图形进行压缩，称 为无损图像压缩。 无失真编码不能达到很高的压缩比，但在一些特殊场合是十分有意义和有用 的。例如对医学图像和遥感图像的处理，不能允许有信息损失，一般采用无失真 编码。 除了熵冗余外，图像还存在信息冗余。对任何图像的后处理来说都可能有一 些信息不被利用或对后处理结果的影响很小，如果将这些信息直接丢掉则可以获 得压缩的效果。图像信息的这种冗余称为信息冗余。 例如在人眼的视觉系统中，对颜色的空间分辨率低于对亮度信号的分辨率， 则使用亮度色差模型y u ( c b ) v ( c r ) 【5 】时，y ：u ：v 选用4 ：2 ：2 ，即将色差信号 空间分辨率减半，减少了信息量的同时对主观效果影响不大。将这些在数字图像 中存在的一些人眼不能或不易觉察的信息称视觉冗余。 事实上，对于许多应用来说，在一定的保真度下接收信息，已能满足对信源 信息的理解乃至欣赏方面的要求。在一定限度内压缩图像的信息冗余称为限失真 编码。采用限失真编码方法对图形进行压缩，称为有损图像压缩。 冗余的存在是压缩可以实现的基础。无损压缩完全从熵冗余的角度出发，去 除图像信息中的相关性，以实现压缩的目的；而有损压缩则进一步利用信息冗余， 去除图像信息中的不重要信息，因此有损压缩可以达到更高的压缩比。 1 2 3 图像质量评价【1 】【6 】 经过压缩编码的数字图像，用更少的比特( b i t ) 数来表示原有的图像信息。 对于无损压缩，可以保证重建图像与原始图像保持一致；但对于有损压缩，其重 第一章绪论 建图像与原始图像就不可避免的产生一些误差。 为了确保图像重建后的质量，提出了图像质量评价问题。图像质量评价分两 种，一种是客观评价，另一种是主观评价。 客观评价是指建立在原始图像与重建图像的误差度量的基础上，通过指标的 计算，给出图像的质量评价。常用的有均方误差( m s e ) 和峰值信噪比( p s n r ) 等，其具体定义将在第四章中介绍。客观评价以其公正性更具有说服力，因此在 科学研究中经常采用。 主观评价以人作为图像的观察者，对图像的优劣作主观的评判。其评价出的 图像质量不仅与图像本身特性有关，还与观察者以及现实的条件有关。在大多数 通讯系统中，图像的最终接收对象是人，主观评价更符合人的视觉效果，因此在 制定国际标准时，经常采用主观评价。 为确保主观评价在统计学意义上有效，参加评分的观察者通常应在2 0 人以 上，其中包括专业人员和非专业人员。 主观评价大体上分为两类：绝对评价与相对评价。绝对评价指由观察者根据 一些事先规定的评价尺度或自己的经验对被评价图像提出质量判断；相对评价指 由观察者将一批图像由好到坏进行分类，对图像进行相互比较评分。以下列出国 际上通常采用的用于对图像质量进行绝对评价的5 级评分标准： 非常好5 分 好4 分 中等3 分 差2 分 非常差1 分 评价结果由一定数量的观察者的平均得分给出。 重建图像质量仅仅是衡量图像压缩系统性能的一个方面，一般用下面四个指 标来综合衡量一个图像压缩系统的性能【7 】： 1 压缩比； 2 重建图像的质量； 3 压缩、解压缩的速度； 4 实现压缩的硬件开销。 1 2 4 图像压缩技术国内外研究现状及发展趋势【l 】【3 】【5 1 1 2 5 】【3 9 】【加】 图像压缩的研究起源于2 0 世纪4 0 年代。1 9 4 8 年，o l i v e r 首先提出了电视信 号的线性p c m 理论，开辟了图像压缩理论的先河。随后，1 9 5 8 年g r a h a m 采用 计算机模拟试验的方法，提出了静止图像压缩的前值预测d p c m 编码法，该方 第一章绪论 法能够获得约4 b i t s p i x 的图像码流。 1 9 6 6 年j b o ”n e a l 对比分析了d p c m 和p c m ，并提出了用于电视的实验 系统，对帧内预测法和亚取样内插复原法进行了研究，并于1 9 6 9 年进行了预测 编码的实验。7 0 年代a h a b i b i 进行了帧间预测编码的研究，并在8 0 年代初针 对运动补偿( m c ) 所用的运动估计( m e ) 进行了研究。 这些早期的预测编码方法都是以像素为处理单元，其理论是线性预测理论。 这些预测的思想至今仍被广泛应用，如j p e g 中d c t 直流系统的压缩，m p e g 中宏块运动矢量的传输等，均采用了预测编码f s 】。 但由于预测编码的最小方差不能反映人的视觉特性以及压缩比的限制，导致 其在九十年代开始被编码效率更高的变换编码所取代。 1 9 6 8 年h c a n d r e w s 等人提出了变换编码的概念，采用的是二维离散傅立 叶变换。其理论基础是把图像看成广义平稳随机场，应用线性变换实现图像信息 相关性的去除。 d c t ( d i s e r e t ec o s i n et r a n s f o r m ，离散余弦变换) 是仅次于k - l 变换的次最优 变换，编码技术己趋成熟，八十年代后期提出的j p e g l 9 】【l o 】【1 1 1 标准就是基于d c t 。 j p e g 是第一个广泛采用的国际静止图像压缩标准。j p e g 标准以其优良的压缩性 能，在短短的几年内就获得极大的成功，目前已经被广泛应用于各种静止数字图 像的压缩，仅在网络上就有大约8 0 的图片采用的是j p e g 压缩格式。但是随着 多媒体和i n t e r n e t 等应用的不断扩展，人们发现已有的静止图像压缩标准j p e g 已经难以满足人们对数字化多媒体图像资料的要求。j p e g 算法本身因为要存储 三角函数而影响了运算速度和解压缩重建的精度。 2 0 0 0 年底出台的新一代静止图像压缩标准j p e g 2 0 0 0 t ”】在编码方法上进行 了革命性的创新，改用了以小波交换( w a v e l e tt r a n s f o r m ) 为主的多分辨率编码方 式，从而大大提高了编码的性能，并使图像编码在一些特殊的条件下得到了较好 的应用。 小波变换【”】是8 0 年代后期逐渐发展起来的数学方法，在图像压缩领域取得 了引人瞩目的成绩。小波图像压缩算法不仅具有较高的编码效率，而且在不损失 编码效率的前提下能够产生嵌入式码流，支持多码率解码，是目前研究的热点。 小波图像压缩的一些早期研裂1 4 】【1 5 】【1 6 1 1 7 1 给出了一些性能很好的算法，使人们对 小波变换在图像压缩中的应用有了直观的认识。j m s h a p i r o 提出的嵌入式零树 小波( e z w ) 编码方法【”j 是基于小波编码方法的典型代表。e z w 通过逐次逼近 量化产生嵌入式码流，能够实现准确的码率控制。现代有损小波变换编码技术就 是以e z w 为开端的d g 。以e z w 方法为基础，世界各地的研究者提出了很多新 的更有效的压缩算法。基于e z w 思想，s a i d 和p e a r l m a n 给出了一个更为精细的 第一章绪论 s p i h t ( s e tp a r t i t i o n i n gi nh i e r a r c h i c a lt r e e s ) 算法【2 0 】，进一步提高了压缩性能。目口使 在不使用算术编码器的情况下，s p i h t 算法仍然能取得良好的图像压缩效果。另 外，还有一些著名的嵌入式算法，如a s a d 和p e a r l m a n 提出了s p e c k ( s e t p a r t i t i o n e de m b e d d e db l o c k ) t 2 l 】算法，以及已经被j p e g 2 0 0 0 标准所采用的 e b c o t 2 2 】算法等。 随着研究的深入，新的图像压缩方法不断涌现，如可取得极高的压缩比的基 于分形几何的图像编码( s 编码) 【1 1 2 3 1 、以及基于模型编码f 1 】、利用人工神经 网络的压缩编码( “】等等。 本文的第三章将简要介绍一些常用的图像压缩方法。 1 3 本文的选题与工作概述 随着图像压缩技术的广泛应用，用户又对图像压缩技术提出了更高的要求。 如要求图像在信道条件较差，干扰较多的环境下实现低码率的图像传输，以及实 现图像质量的渐进传输。传统的编码方法难以满足图像传输的新要求，因此研究 人员提出了图像的嵌入式编码的概念。 图像的嵌入式编码的基本原理是编码器将待编码的比特流按重要性的不同 进行排序，根据目标码率或失真度大小的要求，通过监视编码的一些参数，随时 可以截断比特流，结束编码；同样，对于给定码流解码器也能够随时结束解码， 并可以得到相应比特流截断处的目标码率的重建图像。由于嵌入式编码的独特优 势，使其可以应用于网络、无线传输，图像浏览，特别适合于容易产生误差的环 境。 随着信息技术的发展，新的数字图像通讯终端，如无线远程监控系统、数字 电视机顶盒、手机、p d a 等，已经逐步进入或即将进入了人们的日常生活，成 为现代社会生产和生活不可缺少的设备。这就要求图像压缩传输系统不但有较高 的性能，还要做到智能化、集成化。这也就要求应用硬件，如现场可编程门阵列 ( f p g a ) 、超大规模集成电路( v l s i ) 技术实现图像压缩编码算法。 本文通过对图像压缩编码技术的学习与研究，掌握了小波变换和信息编码的 基础知识，并能与图像压缩的具体情况相结合，全面地了解了主要的图像压缩方 法和静止图像压缩国际标准。 在本文中，通过对嵌入式图像编码的研究，对嵌入式编码的发展和现状作了 全面的了解，并深入研究了基于零树的嵌入式编码方法，特别是e z w 和s p i h t 等经典算法，详细分析了算法的特点和不足，从而掌握了改进基于零树的嵌入式 编码方法的方向。s p i h t 算法虽然有良好的性能，但在运算过程中，需要用到3 第一章绪论 个链表来存储小波系数和小波系数集合的重要性信息，耗费了大量的内存资源， 不利于硬件实现。本文主要针对编码算法在运算中的内存应用量问题，着重研究 了节省内存的嵌入式编码方法l z c 和n l s ，在详细分析了他们的实现原理的基 础上，提出了n l s 算法的改进方案，并为改进方案的程序实现设计了相应的算 法。改进的n l s 算法用函数代替n l s 算法中用来记录小波系数的后代系数最大 值的向量，进一步降低n l s 算法的内存消耗量，从而达到用更少的内存来实现 高效的嵌入式编码算法的目的。 在研究工作中，用c 语言实现了改进的n l s 算法，并与s p m t 、l z c 等算 法经过压缩重建出的图像的峰值信噪比进行了比较，试验结果证明，改进的n l s 在内存应用量明显下降的情况下，表现出了比较优秀的性能，适用于硬件实现， 这将使得图像压缩系统更加集成化、智能化，有很大的经济效益和社会效益。 第二章理论基础 2 1 小波理论基础 第二章理论基础 2 1 1 小波理论的来源与发展【1 】 2 5 】 小波分析方法的提出可以追溯到1 9 1 0 年h a a r 提出的小“波”规范正交基及 1 9 3 8 年l i t t l e w o o d - p a l e y 对f o u r i e r 级数建立的l - p 理论，即按二进制频率成分 分组f o u r i e r 变换的相位变化本质上不影响函数的形状及大小。1 9 8 1 年s t r o m b e r g 对h a a r 系进行了改进，证明了小波函数的存在性。1 9 8 4 年法国地球物理学家 m o r l e t 在分析地震波的局部性质时，发现这类信号的长期变化趋势是稳定的，但 在局部存在突变点或不连续点。分析这类信号传统的f o u r i e r 变换难以达到要求， 于是他将小波概念引入信号分析中，对信号进行分解，以获得信号的局部特性。 理论物理学家g r o s s m a n 对m o r l e t 将地震信号按一个确定函数的伸缩、平移系展 开的可行性进行了研究，为小波分析的形成开了先河【2 6 】【2 ”。 小波变换在8 0 年代后期逐渐发展成一个数学分支，它不仅为纯粹数学的研 究提供了有力的工具，而且为图像处理理论的发展树立了一块里程碑。计算机视 觉专家d m a r 一2 8 】在他的“零交叉”理论中使用的可按“尺度大小”变化的滤波 算子。1 9 8 6 年，法国数学家y m e y e r 成功地构造出了具有一定衰减性质的光滑 函数l i t ，这个函数( 算子) 的二进尺度伸缩和二进整倍数平移产生的函数系构成 著名的函数空间l 2 限) 的标准正交基。m a l l a t 2 9 1 3 0 j 【3 1 】【3 2 1 将计算机视觉领域内的多 尺度分析思想引入到小波分析中，提出多分辨率分析概念，统一了在此之前的所 有具体正交小波基的构造，并且提出相应的分解与重构快速算法。1 9 8 8 年，比 利时数学家i d a u b e c h i e s 基于多项式方式构造出具有有限支集的正交小波基1 3 3 1 。 1 9 9 0 年，c k c h u i 和中国籍学者王建忠基于样条函数构造出单正交小波函数， 并讨论了具有最好局部化性质的尺度函数和小波函数的一般构造方法【3 4 1 。如今， 小波分析以其良好的性能，成为现代信号分析与处理的重要方法。本节将对小波 变换理论作简要的介绍。 2 1 2 连续小波变换 设y ( f ) r ( r ) ，其傅里叶变换y ) 满足容许性条件 第二章理论基础 c y = 铎 0 ，使得 d ( 形( x ) ，矿( y ) ) 冬c d ( x ，力v x ，y x ( 3 - 5 ) 则称w 是l i p s c h i t z 映射，c 为相应的l i p s c h i t z 常数。如果满足0 e l ，称相应 的l i p s c h i t z 映射w 是具有压缩常数c 的压缩映射。 设x c r 2 ，形：x _ x ，i = 1 , 2 ，n 是n 个以c f 为压缩常数的压缩映射， 即 d ( ( x ) ，阡7 ( y ) ) c t d ( x ，y ) 魄，y 置，i = 1 ，2 ，n ( 3 6 ) 定义了日( 柳上的映射矿= u 彬。 扫| 则对任何a 日( x ) ，取所有集合的并作为映射的像。对于 c = m a x c l ，c 2 ，“ ，则 d ( 矿( 4 ) ，( 口) ) c d ( 4 ，曰) v a ，b 日( 石) ( 3 7 ) 压缩映射不动点定理：( x ，d ) 是完备的度量空间，：z 呻z 是压缩常数为c 的压缩映射，则存在厂的唯一不动点石，x ，使 x r = 厂( x ，) = l i m f ( 力 v x r( 3 8 ) 由压缩映射不动点定理，对于v x x ，存在 1 d ( x ，x ) d ( x ，厂( 石) ) ( 3 - 9 ) l c 进行分形图像编码，需要在分形图像空间中推广压缩映射不动点原理。 第三章图像压缩技术概述 ( x ，d ) 是完备的度量空间，x c r 2 。如果映射形：x x ，i = 1 , 2 ，n 是n 个以c 。为压缩常数的压缩映射，则w i 构成迭代函数系统( i f s ) ， c = m a x c i ，c 2 ，) 为 f s 的压缩常数。 由任一s 出发定义的映射w 在日( x ) 上是压缩的，且存在不动点g g = w ( g ) = u 形( g ) ( 3 1 0 ) 扣1 同时g = l i m 形_ ( b ) v b 日( x ) 。称g 为s 的吸引子。g 在大多数情况下表 现为分形集合。 拼贴定理：设 x ；，阿0 ) 是一个压缩常数为c 的i f s ， v b 日( w = u 形，对 d ( g ，曰) d ( 口，矿( 占) ) ( 3 1 1 ) 其中g = l i m 矿o ( b ) 为矿的吸引子。由此可知，对于给定的图像b ，如果能找到 一个i f s ： x ；9o ，使得图像b 与w ( b ) = 【j 形( b ) 充分接近，则吸引子g ； 就与图像b 充分接近。因此可以通过分割图像b ，通过有限次拼贴 w ( b ) = u 彬) 使得它与图像b 充分接近，即可以完成图像重构。 i - l 以下举例说明分形图像编码，对于如图3 - 1 ( a ) 中的正方形图像b ，定义压缩 映射、彤、呢如式，在图3 1 ( a ) 中经压缩变换后， b = 形( 口) = 形( b ) u ( 口) u ( 曰) u ( b ) ，即可以实现原始图像的精确覆盖， 则b 为i f s x ；，呢 的不动点，即吸引子。在图3 - ( b ) 中，如果初始图 为圆形，经过多次迭代，其图像将与i f s 的吸引子( 正方形) 越来越接近。 讲一 1 牡p ： 啡 1 2m 0 h m i 2 职呲l 2 抛0 圈 既娜1 2 抛0p 瞄2 ( 3 1 2 ) ( 3 1 3 ) ( 3 1 4 ) ( 3 1 5 ) 第三章图像压缩技术概述 ( a ) 鱼超超 图3 - 1 分形图像编码举例 自然图像并不具有这种恰好的整体和局部的自相似性，在实际应用中一般采 用对图像进行两级分块，在父块中寻找子块的最佳匹配，从而构造i f s 的方法来 进行编码的。子块越小，越容易找到匹配的父块，效果越好。分形编码的计算量 巨大，算法的计算复杂度高，成为制约其发展的瓶颈之一。 3 1 5 其他图像压缩编码方法 基于的结构的图像编码也称为第二代编码。编码时首先将图像中的边界、轮 廓、纹理等结构特征求出来。然后保存这些参数信息。解码时，根据结构和参数 信息进行合成，从而恢复出原始图像。 基于知识的编码是对于拥有图像中所描述内容的先验知识，如视频电话中的 人脸信息等可用规则描述的图像，利用人们对关于图像内容知识形成一个规则 库，据此将图像内容的变化等用一些参数进行描述，从而用参数与模型就可以实 现图像编码与解码。 利用人工神经网络的压缩编码是一种广义变换编码，是非正交、非线性的降 维变换。它分为两种方法，一是h o p f i e l d 神经网络模型法，二是前向方法。这种 方法的优点是，一旦训练完成，编码的计算就十分简单，适于任何图像压缩，并 可以预先设置压缩比和信噪比。但是神经网路的学习时间较长，并且存在局部极 小值的问题，给它的应用带来了局限。 3 2 静止图像压缩标型1 】 6 】【2 5 】 3 9 1 1 4 0 l 3 2 i j p e g 国际标准化组织( i s o ) 和国际电报电话咨询委员会( c c r r t ) 联合成立的专 家组j p e g ( j o i n tp h o t o g r a p h i ce x p e r t sg r o u p ) 经过五年艰苦细致的工作后，于1 9 9 1 年3 月提出了i s oc d l 0 9 1 8 号建议草案：多灰度静止图像的数字压缩编码( 通常 第三章图像压缩技术概述 简称为p e g 标准) 。这是一个适用于彩色和单色多灰度或连续色调静止数字图像 的压缩标准。它的内容大体上可分为基于d p c m ( 差分脉冲编码调制) 的无损压缩 编码、基于d c t ( 离散余弦变换) 和h u f f m a n 编码的有损压缩算法两个部分。前者 不会产生失真，但压缩比很小；后一种算法进行图像压缩时信息虽有损失但压缩 比可以很大，例如压缩2 0 倍左右时，人眼基本上看不出失真。 p e g 标准实际上有三个过程： 1 ) 基本顺序过程( b a s e l i n es e q u e n t i a lp r o c e s s e s ) 实现有损图像压缩，重建图像 质量达到人眼难以观察出来的要求。采用的是8 x 8 像素自适应d c t 算法、量化 及h u f f m a n 熵编码器。 2 ) 基于d c t 的扩展过程( e x t e n d e dd c t b a s e dp r o c e s s ) 使用累进工作方式，采 用自适应算术编码过程。 3 ) 无失真过程( l o s s l e s sp r o c e s s ) 采用预测编码及h u f f y n a n 编码( 或算术编码) ， 可保证重建图像数据与原始图像数据完全相同。 其中的基本顺序过程是p e g 最基本的压缩过程，符合p e g 标准的硬软件 编码解码器都必须支持和实现这个过程。另两个过程是可选过程，对一些特定 的应用项目有很大实用价值。 在灰度图像中只有一个亮度分量，而彩色图像有一个亮度分量和两个色度分 量，对彩色图像编码时可以按照对灰度图像的编码方法对每一个分量进行编码。 p e g 在基本顺序过程中，对原始图像的每一个分量，首先分割成不重叠的8 8 的像素块，然后做8 8 的二维d c t 变换，得到的6 4 个系数代表了该图像块的 频率成分。在8 8 的系数矩阵中，左上角的1 个为直流( d c ) 系数，其余6 3 个为 交流( a c ) 系数。从左到右，水平频率增高，从上到下，垂直频率增高。接着，对 d c t 系数量化，再用z 形( z i g z a g ) 扫描将系数矩阵变成一维数列，各项按频率由 低到高顺序排列，最后就是具体的编码。 p e g 采用的是定长和变长相结合的编码方法。对于d c 系数，由于图像中 相邻的两个图像块的d c 分量一般非常接近，所以对量化后的d c 系数采用差值 编码，即对同一分量内相邻块的d c 系数之差进行编码。由于亮度和色度分量的 d c 差值统计特性差别较大，j p e g 分别为两者推荐了不同的h u f f m a n 码表。 对于a c 系数，由于经过量化后a c 系数中出现了较多的零，所以先对零系 数采取游程编码，然后再采用h u f f m a n 编码，连续零的个数越多，编码效率就越 高。因为高频的a c 系数多数是零，所以采用编码能有效压缩数据量。与d c 系 数的编码类似，p e g 也分别推荐了亮度和色度分量的h u f f m a n 码表。 p e g 的解码过程与编码过程相反，所以p e g 也称为对称型算法。p e g 对 图像的压缩有很大的伸缩性，图像质量与比特率的关系如下： 第三章图像压缩技术概述 - 1 5 - 2 0 b p p ：与原始图像基本没有区别( t r a n s p a r e n tq u a l i t y ) ： 1 0 7 5 1 5 b p p ：极好( e x c e l l e n tq u a l i t y ) ，满足大多数应用； 1 1 0 5 0 7 5 b p p ：好至很好( g o o d t ov e r yg o o dq u a l i t y ) ，满足多数应用； - o 2 5 0 5 b p p ：中至好( m o d e r a t et og o o dq u a l i t y ) ，满足某些应用。 其中b p p ( 比特，像素) 为码率的单位，代表编码后的码流用来表示一个像素 所花费的比特数 实际上，某个给定比特率的图像质量与该图像具体内容有关。 j p e g 编码有其不足的一面。由于进行分块的d c t 变换，j p e g 标准在低比 特率( 对于高细节化的灰度图像小于o 2 2 5 b p p ) 压缩时，主观失真度难以接受， 出现明显的方块效应，所以很难实现图像编码的高压缩比，如图3 - 2 为在码率不 断下降的情况下，j p e g 的重建图像效果；在噪声环境中传输时，比特误码会使 j p e g 压缩图像质量急剧下降；j p e g 标准不能够在同一码流中同时提供高性能的 有损压缩和无损压缩；此外，j p e g 编码的过程决定在解码时只能实现逐行解码， 也就是说要看到图像的全貌必须等整个图像全部解码完毕，这在某些应用场合造 成了很大的不便。 ( b )( c ) 图3 - 2 码率下降的情况下，j p e g 重建图像效果 3 2 2 j p e g 2 0 0 0 j p e g 2 0 0 0 是新推出的国际静止图像压缩标准，跟目前的j p e g 标准相比， 有很多优点，更适合未来的需要。j p e g2 0 0 0 与传统j p e g 最大的不同，在于它 放弃了j p e g 所采用的以离散余弦变换d c t 为主的区块编码方式，而采用小波 变换( w a v e l e t t r a n s f o r m ) 为主的多分辨率编