（信号与信息处理专业论文）基于小波变换的图像压缩编码算法研究(1).pdf

长春工业大学硕士学位论文 摘要 近年来，随着计算机网络以及现代通信技术的迅猛发展，迫切需要对庞大的图像 数据进行压缩处理，由此图像编码压缩技术目前已经发展成为当前的一个研究热点。 目前常见的主要编码方法有：熵编码，预测编码，变换编码统计编码，子带编码， 分形编码，模型编码，矢量量化编码，神经网络编码，小波变换编码等等。 小波分析是当前数学中一个迅速发展的新领域，因其克服了傅立叶变换的局限性， 且具有良好的时一频局部化性质和多分辨率性，而得到迅速发展和广泛应用。小波图 像编码是小波分析应用的一个重要方面。它的特点是压缩比高，压缩速度快，压缩后 能保持信号与图像的特征不变，且在传递过程中可以抗干扰。嵌入式零树算法则是目 前小波编码中较为有效的算法之一，它通过对小波变换后的系数特点进行分析，并对 其进行有效组织和编码，提高了编码效率。 本文主要研究基于小波变换的图像编码压缩方法。首先概述了图像编码理论的基 本原理和方法，介绍了一些常见的压缩方法和一些静态图像编码国际标准。 然后，系统介绍了小波分析理论，尤其讨论了小波变换的多分辨率分析理论和快 速m a l l a t 算法。 接着，分析研究了s w e l d e n s 提出的新的小波构造方法一一提升方案( l i f t i n g s c h e m e ) ，讨论了用提升方法构造可逆整数小波变换的方法，给出了一种新的自适应整 数小波提升算法。gp i e l l a 提出的具有完全重构功能的自适应提升结构，由于它严格限 制了更新步骤中滤波器系数之和为1 ，使得不易用它构造整数变换。为了得到整数变换， 本文将它推广到更一般的情形。该算法对图像中的边缘点和均匀区域区别对待，而且 整数变换不会产生舍入误差。这些性质在数字图像数据压缩中具有重要应用。 最后重点对基于小波变换的嵌入式小波编码算法进行了详细的讨论，比较分析了 当前主要的三种嵌入式小波编码算法：e z w 算法，s p i h t 算法以及s p e c k 算法。针 对e z w 算法的一些不足，论文给出了基于该算法的改进算法。经过m a t l a b 仿真软件 验证结果表明：本论文提出的压缩方法计算简单、压缩比高，较已有的小波零树压缩 编码，在高压缩比的时候，效果更佳。与基于传统小波变换及零树量化的方法相比， 运算简洁，速度快，重构图像质量高，取得了令人满意的效果。 关键词：图像编码，小波变换，提升方法，嵌入式零树算法 长春工业大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g ya n dm o d e mc o m m u n i c a t i o n t e c h n o l o g y , a l lo ft h e s et e c h n o l c l g i e sc a l lf o rc o m p r e s s i n gt h eg r e a ta m o u n to fi n l a g ed a t ai n o r d e rt oa d a p tt ot h ep r a e t i e a a p p l i c a t i o n , i m a g ec o d i n gh a sb e c o m ear e s e a r c hh o t s p o ti n t h ef i e l do fm o d e r ns i g n a lp r o c e s s al o to fm e t h o d so nt h a th a v en o wg e n e r a t e d ，s u c ha s e n t r o p yc o d i n g ，p r e d i c tc o d i n g ，t r a n s f o r mc o d i n g , s t a t i s t i cc o d i n g ，s u b b a n dc o d i n g ，f f a c t a l c o d i n g ，m o d e lc o d i n g ，v e c t o rq u a n t i z a t i o nc o d i n g ，n e u r a ln e t w o r ke n d i n g ，w a v e l e tc o d i n g ， e r e ，w a v e l e ta n a l y s i si san o v e lf i e l d 、i t l lr a p i dd e v e l o p m e n ti nm o d e mm a t h e m a t i c s , b e c a b s eo fo v e r c o m i n gt h ef o u r i e r sl i m i t a t i o na n dh a v i n gf e a t u r e so fg o o dt i m e f r e q u e n c y a d a p t i v ea n dm u l t i - r e s o l u t i o na n a l y s i s i th a sb e e nq u i c k l yd e v e l o p e da n dd e e p l ya p p l i e d w a v e l e tc o d i n gi so n eo ft h ea p p l i c a t i o n sf o rw a v e l e ta n a l y s i s i th a sa d v a n t a g e so fh i g h c o m p r e s s i o nr a t e ，h i g hc o m p r e s s i o ns p e e d ，a n du n c h a n g e a b l es i g n a l & i m a g ec h a r a c t e r i s t i c s a f t e rc o m p r e s s i o n , a n da n t i i n t e r f e r e n c eu n d e rt r a n s m i t t i n g a tp r e s e n t , e m b e d d e dz e r o - t r e ew a v e l e ti so n eo f t h ee f f i c a c i o u sa l g o r i t h m so nw a v e l e t c o d i n g ，i tc a ni m p r o v ei m a g ec o d i n ge f f i c i e n c yb ya n a l y z i n ga n df o r m i n gt h em o d u l u so f w a v e l e tt r a n s f o r m i n t h i sp a p e r , w es e tf o c u so nt h ei m a g ee n c o d i n gb a s e do nw a v e l e tc o d i n g ，w ef i r s t l y s u m m a r i z et h eb a s i ct h e o r yo ni m a g ec o d i n g ，i n t r o d u c es o m ef a m i l i a rc o m p r e s s i o n t e c h n i q u e sa n ds o m ei n t e m a t i o n a lc o m p r e s s i o ns t a n d a r d so ns t a t i ci m a g e a n dt h e n ，w ed i s c u s st h et h e o r yo fw a v e l e tt r a n s f o r r n ，e l a b o r a t i n gt h et h e o r yo f m u f t i - r e s o l u t i o na n a l y s i sa n dm a l l a t sf a s ta l g o r i t h m i ns u c c e s s i o n , w ea n a l y s et h et h e o r yo fl i f t i n gs c h e m eg i v e nb ys w e l d e n s ，a n dd i s c u s s t h ew a yt oc o n s t r u c ti n t e g e r - t o - i n t e g e rw a v e l e tt r a n s f o r mw i t hl i f t i n gs c h e m e a n d 锄 a d a p t i v ew a v e l e tt r a n s f o r mt h a tm a p si n t e g e r st oi n t e g e r si sp r e s e n t e d u s i n gl i f t i n gs c h e m e p r e s e n t e db ygp i e l l a , i ti sd i f f i c u l tt oc o n s t r u c tt r a n s f o r mt h a tm a p si n t e g e r st oi n t e g e r s b e c a u s eo fr e s t r i c to nt h es l i mo fc o e f f i c i e n t so fu p d a t es t e p i no r d e rt og e tt h et r a n s f o r m , r e s u l t si se x t e n d e dt om o r eg e n e r a lc a s e s t h ea d a p t i v et r a n s f o r mt r e a t se d g e sa n d h o m o g e n e o u sr e g i o n si ni m a g ed i f f e r e n t l y f u r t h e r m o r e ，i fi n p u ts i g n a l sa l ei n t e g e r s ，t h e t r a n s f o r mh a sr i ot r u n c a t i o ne t o r t h e s ep r o p e r t i e sh a v ei m p o r t a n ta p p l i c a t i o n si n c o m p r e s s i o no f d i g i t a li m a g e f i n a l ，w ea n a l y z ea n dd i s c u s st h ea l g o r i t h me m b e d d e dz e r o - t r e ew a v e l e tm i n u t e l y , d i s c u s st h ee z w , s p 珊t , s p e c kc o m p a r a t i v e y t h i n k i n go ft h es h o r t c o m i n go fe z w ：a n n 一 墨童三些查兰堡主兰堡堡苎 i m p m v e da l g o r i t h mh a sb e e nu s e d t h ee m u l a t i o nr e s u l t1 b 加峨；hm a t l a bs o n 呲i n d i c a l e s t h a tt h ec o m p u t a t i o ni s s i m p l ea n dt h ec o m p r e s s i o nr a t ei sh i g hu s i n go u t m e t h o d c o m p a r i n gw i t ht h em e t h o do f w a v e l e tz e r o - t r e ec o m p r e s s i o ne n c o d i n g ，o u rm e t h o di sb e t t e r a n dm o l ef i ti nw i t hi m a g ec o m p r e s s i o nu n d e rh i g hc o m p r e s s i o nr a t e i tc a nr e a l i z es i m p l e r c o m p u t i n g , a n dh i g h e r - q u a l i t yr e c o n s t r u c t i o nc o m p 甜e dw i t hi m a g ec o d i n ga l g o r t h mb a s e d o nt r a d i t i o n a lw a v e l e tt r a n s f o r m t h ee x p e r i m e n t a lr e s u l t sa r e s a t i s f y i n g 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 a n s f o r m , l i f t i n gs c h e m e ，e m b e d d e dz e r o - t r e ew a v e l e t i i i 长春工业大学硕士学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经 发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本声明的法律结果由本人承担。 论文作者签名： 移易 醐。叼年丝月 长春工业大学硕士学位论文 第一章绪论 1 1 引言 近十几年来，随着通信技术和i n t e m e t 的不断发展，人们对数据、语音和多媒体业 务的需求不断增加，同时人们对这些业务服务质量和服务内容的期望也越来越高。其 中，对图像信息的获取和处理更是引起了各方面人士的广泛重视。这是因为：首先， 视觉是人类最重要的感知手段，人们从自然界获取的信息大部分来自于视觉，而图像 又是视觉的基础【l l 。其次，图像在军事、医学、遥感、娱乐、气象等各个方面都有着广 泛的应用。然而用以表示这些图像的数据量很大，存储成本很高，日益不能满足现今 网络环境下进行多媒体通信的需求。为了使通信成为可能并尽可能降低通信费用，对 图像数据进行压缩是必需的，图像编码理论由此应运而生，并且迅速发展起来。 图像压缩技术促进了图像通信的发展，解决了大数据量问题，使图像信息更加方 便的交互、存储。在实际应用中，用户有时既需要快速了解图像的概貌，又需要能在 必要的时候能获得图像的全部信息。单纯的有损压缩虽然加快了图像的获取速度，但 可能损失掉一些关键信息；而单纯的无损压缩又可能使用户在得到整幅图像前对图像 的概貌无法了解，在等待中消耗了不必要的时间。这些要求对图像压缩编解码技术提 出了新的挑战，同时也是其向前发展的动力，吸引了国内外众多研究机构和研究人员 的注意，成为当前信息科学技术领域的一个研究热点。 1 2 图像压缩编码技术的发展与现状 图像压缩编码技术就是将数据压缩理论用于图像信号。从1 9 4 8 年o l i v e r 提出p c m 编码理论开始，图像压缩技术的研究已有近6 0 年历史，人们已研究并提出各种压缩方 法，如d c t 、游程编码、l z w 、d p c m 等，并在此基础上制定了一系列图像压缩标准。 1 9 6 6 年j b o q q e a l 对比分析了d p c m 和p c m 算法，并公布了用于电视的实验数 据，1 9 6 9 年进行了线性预测编码的实际试验，7 0 年代开始进行帧问预测编码的研究， 8 0 年代初开始对做运动补偿( m c ) 所用的运动估计( m e ) 算法进行研究。 1 9 6 8 年h c a n d r e w s 等提出了变换编码，采用的是二维离散傅立叶变换，此后相 继出现了采用其它变换方法的变换编码，其中包括二维d c t 等。从7 0 年代开始进行 了帧间预测编码的研究，7 0 年代末制定了静止图像编码国际标准i s o i e c 编码标准字。 1 9 8 8 年静态图像专家组j p e g 创立，并于1 9 9 1 年制定了j p e g 建议草案，1 9 9 4 年 形成正式编码标准。1 9 9 7 年，j p e g 委员会开始研究将小波技术引入到图像压缩领域的 新的压缩标准j p e g 2 0 0 0 。 这一系列国际标准的制定标志着图像编码技术的日臻成熟，大大推动了图像编码 技术的实用化和产业化。随着互联网的广泛应用和所需传送数据的大量增加，以及多 长春工业大学硕士学位论文 媒体和数字电视的逐渐普及，图像压缩技术必将得到更为广泛的应用。 1 3 基于小波变换的图像压缩技术的发展与现状 小波变换编码是近年来随着小波分析的研究而提出的一种具有很好发展前景的图 像编码方法，它是在数学界和工程界共同研究数据表示技术的过程中发展起来的。它 摈弃了传统的信号分析所必需的前提假设平稳性，已经成为分析非平稳信号的有 力工具。小波分析在时域和频域同时具有良好的局部化特性，常被誉为信号分析的“数 学显微镜”。 1 3 1 基于小波变换的图像编码技术的发展 小波分析的思想来源于伸缩与平移方法。小波分析方法的提出，最早应属于1 9 1 0 年h a a r 提出的规范正交基。但小波概念的真正出现应算于1 9 8 4 年，法匡地球物理学 家j m o r l e t 提出将信号按一个确定函数的伸缩、平移系展开。随后，他与a g r o s s m a n n 共同进行研究，发展了连续小波变换的几何体系【2 】【3 】。1 9 8 5 年以后，在ym e y e r ，a c , r o s s m a n n ，s m a l l a d 4 j 和i d a u b e c h i e s l 5 】i q 等人的共同研究下，小波分析迅速发展起来。 到8 0 年代末、9 0 年代初，小波开始应用于图像压缩。1 9 8 6 年，w o o d s 7 】构造了第 一个真正意义上小波图像编码器。1 9 9 2 年i d a u b e c h i e s 提出了9 7 滤波器，在小波压 缩领域中得到了广泛的应用。 1 9 9 3 年s h a p i r o 【s 】提出了嵌入式零树小波( e z w ：e m b e d d e dz e r o - 仃e ew a v e l e t ) 编 码算法，第一次弓i 入了小波“零树”的概念，通过定义零树根( z t r ) ，孤立零点( i z ) 、 正重要值( p o s ) 和负重要值( n e g ) 四种符号进行空间小波树递归编码，有效地剔 除了对高频系数的编码，极大地提高了小波系数的编码效率。在m p e g - 4 中，e z w 算 法已经成为压缩编码的模块之一，e z w 编码器在数据压缩史上具有里程碑式的意义。 1 9 9 6 年a s a i d 和w a p e a r l m a n g l l l o l 根据s h a p i r o 零树编码算法( e z w ) 的基本 思想，提出了一种新的且性能更优的实现方法，即基于分层树集合分割排序( 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 ) 的编码算法，这是迄今为止效果最好的小波压缩 算法之一。与e z w 相比较，它的主要成功之处在于设计了空间方向树结构，这种数据 结构不仅充分利用了不同尺度间小波系数的相关性，也充分考虑了同一尺度下小波系 数的相关性，可以更有效地组织小波系数。因此，它的编码效率也比e z w 算法有了很 大的提高，同时，通过采用比特平面的编码技术，s p i h t 也保留了e z w 实现简单、码 流具有嵌入特性等特点。 在小波图像编码的研究过程中，产生了许多非常优秀的编码算法，如s p e c k 算法、 t a r p 算法、e b c o t 算法1 ”】等。其中2 0 0 0 年由t a u b m a n 提出的具有优化截断点的内 嵌块编码算法( e b c o t 算法) 由于其更高的压缩效率更是成为新的图像编码标准 j p e g 2 0 0 0 1 2 】中所采用的核心算法。 2 长春工业大学硕士学位论文 1 3 2 小波图像编码技术的当前研究热点 小波应用于图像压缩的历史并不长，却已经显示出强大的生命力和广阔的发展前 景。与目前广泛使用的j p e g 基于d c t 变换的压缩算法相比，小波系数具有更好的时 频特性，这为下一步的量化和压缩提供了非常有利的条件，并且小波变换不存在块效 应，在实际应用中更具优势。 目前，小波图像编码技术的研究热点主要有以下几个方面： ( 1 ) 小波基的选择。采用不同的小波基分析同一个问题会产生不同的结果，而最优 小波基的选择迄今为止尚未有统一的选择标准。我们仅能参考一些参数来判定小波基 的好坏，如：平滑性、逼近精度、支撑大小和滤波频率选择等。 ( 2 ) 离散小波交换( d w t ：d i s c r e t ew a v e l e tt r a n s f o r m ) 的快速算法。自m a l l a t 算 法被提出后，很多人进行了对d w t 算法的改进研究。其中s w e l d e n s 于1 9 9 6 年提出了 提升方法( l i f t i n gs c h e m e ) u 3 i ! 。这种方法既保留了小波的特性，同时又克服了原先 小波构造中对傅立叶变换的依赖性，可以使d w t 的计算复杂度在m a l l a t 算法的基础 上降低一半，逐渐成为了主流的d w t 计算方法。 0 1 小波系数量化方法。现有的量化方法主要有标量量化和矢量量化两种。其中标 量量化由于简单易实现被大多算法采纳，如：e z w 、s p i h t 、s p e c k 等。矢量量化方 法是由a n t o n i n i 等人【1 5 1 引入的，其优越性表现在利用了相邻系数的相关性，把若干系 数看作一个矢量整体，但它涉及码书设计等问题，比标量量化复杂的多。 ( 4 ) 整数小波变换。图像的像素值是用整数表示的，对其实施整数到整数的变换后， 可以保证其能够完全重构，避免了图像的失真。而通常的小波滤波器都是小数形式， 它的输出就不是整数，此时在重构时就会产生失真。对s w e l d e n s 提出的提升方法稍加 改进，就可以得到整数到整数的小波变换1 1o j 。 1 4 论文内容安排 第一部分：是本文的绪论，介绍课题的背景，简述图像压缩技术的发展以及小波 应用于图像编码的发展过程及其当前研究热点。 第二部分：简要介绍图像编码的基础理论，包括图像编码的基础知识，性能评价 标准，以及各种常用图像编码方法和国际标准。 第三部分：简述了小波分析基本理论，其中重点介绍多分辨率理论和m a l l a t 算法。 第四部分：详细介绍了小波提升算法，研究了基于提升算法的整数小波变换方法， 在此基础上实现了一种改进的自适应整数小波提升算法。 第五部分：研究分析了嵌入式小波零树编码( e z w ) 算法，提出了一种基于e z w 的改进方案，并对该方案进行实验仿真，分析实验结果。 最后是总结和展望，对全文进行总结并指出不足之处和今后的研究方向。 长春工业大学硕士学位论文 第二章图像编码理论 图像编码是数字图像处理的重要分支，广泛应用在各种图像编码的传输、存储、 检索系统中。图像编码的一个主要目的是在保证一定重构质量的前提下，以尽量少的 比特数来表征图像的信息，以便节省信道有效带宽或存储器的容量。 2 1 图像编码基础 图像编码本质上就是对要处理的图像数据源用一定的规则进行变换和组合，从而 达到以尽可能少的代码或者符号来表示尽可能多的数据信息的目的。图像编码对图像 采用不同的表达方式以减小表示图像所需的数据量，所以也常称为图像压缩。压缩的 理论基础是信息论。从信息论的角度来看，压缩就是去掉信息中的冗余，保留不确定 的信息，去掉确定的信息，用一种更接近信息本质的描述来代替冗余量的描述。 图像表示需要大量的数据，但这些数据往往都是高度相关的，这些相关性会引起 信息的冗余，因此可以通过去除冗余信息来实现对图像数据的压缩。在一般的图像信 源中，除空间、频率和时间冗余外，还存在其他一些冗余信息。主要有以下几种1 刀【1 8 】： ( 1 ) 信息熵冗余，也称编码冗余 对于实际图像数据的每个像素，很难得到它的信息熵，因此在用数字化方式表示 一幅图像时，对每个像素是用相同的比特数表示的，这样必然存在冗余。信息熵冗余 和空间冗余、时间冗余统称为统计冗余，它们都决定于图像数据的统计特性。 ( 2 ) 结构冗余 有些图像的部分区域存在非常强的纹理结构，或是图像的各个部分之间存在着某 种关系，例如自相似性等，这些都是结构冗余的表现。 ( 3 ) 知识冗余 有些图像中包含的信息与某些先验的知识有关，例如在普通的人脸图像中，头、 眼和嘴的相对位置等信息就是一些常识，这种冗余称为知识冗余。 ( 4 ) 视觉冗余 在大多数情况下，重构图像的最终接收者是人的眼睛。为了达到较高的压缩比， 可以利用人类视觉系统的特点。这是因为虽然人类的视觉系统是世界上最好的图像处 理系统，但它远远不是完美的。人类的视觉系统对于图像的注意是非均匀的和非线性 的，并不是对于图像中的任何变化都能感知的。例如图像系数的量化误差引起的变化 在一定范围内是不能为人眼所觉察的。因此，如果编码方案有效地利用人类视觉系统 的一些特点，是可以得到高压缩比的【”】。 上述各种形式的冗余，是压缩图像数据的出发点，图像编码方法就是要尽可能的 消除这些冗余信息，以降低表示图像所需的数据量。 4 长春工业大学硕士学位论文 2 2 图像质量的评价 图像质量评价的研究是图像信息工程的基础技术之一【2 0 】。图像质量的含义包括两 个方面：图像逼真度和图像可懂度。所谓图像逼真度是描述被评价图像与标准图像的 偏离程度，图像可懂度则是表示图像能向人或计算机提供信息的能力。 目前常用的图像质量评价方法主要有主观质量评价和客观质量评价两种。在充分 考虑人眼视觉特性的基础上，又提出了一种基于感兴趣区的图像质量评价方法1 2 ”。 2 2 1 客观质量评价 客观质量评价用恢复图像偏离原始图像的误差来衡量图像恢复质量，最常用的有 均方误差( m s e ：m e a ns q u a r e de r r o r ) 和峰值信噪比( p s n r ：p e a ks i g n a l - t o - n o i s er a t i o ) 。 脚= 击善套( 乃一射 ( 2 1 ) 其中，乃、刀分别表示原始图像和恢复图像( f ，) 位置处的像素值，m 表示图像的宽度 值，n 表示图像的高度值。 粥撇：1 0 l g 2 b - - 1 ) 2 ( 2 2 ) m s e p s n r 本质上与m s e 相同，其中b 表示原始图像像素位数，p s n r 的单位是分贝( d b ) 。 p s n r 是目前用来评测解码图像质量的有效定量参数，p s n r 越高，其解码质量越 好。但是这种质量评测还不能达到真正的视觉质量评价，只是数学上的能量质量评价。 这是因为m s e 和p s n r 都是从总体上反映原始图像和恢复图像的差别，并不能反映一 副图像中少数像素点有较大灰度差别和较多像素点有较小灰度差别等各种情况。 2 2 2 主观质量评价 主观评价方法是评价者直接对同一幅图像按视觉效果的好坏进行打分，并对所有 评价者给出的分数进行加权平均。 相对于客观评价方法，主观评价结果是可靠的，但它使用起来不方便，一方面主 观评价容易受到评价者的主观因素影响；另一方面不能用数学模型对其进行描述，不 能直接用于图像编码过程中的质量评价和控制，且不能应用于实时传输的场合。 2 2 3 感兴趣区质量评价 图像最终是供人看的，因此合理地评价图像质量的方法应该充分遵循人眼视觉特 性。人眼视觉具有一定的选择性，人们在观察和理解图像时会不自觉地对其中某些区 长春工业大学硕士学位论文 域产生兴趣，定义为感兴趣区。 假设图像中只有一个感兴趣区4 ，其面积为s ，不感兴趣区4 的面积马，s 为图 像总面积s = s + 是，修改式( 2 1 ) 可得图像均方误差( i m s e ：i m a g e m e a ns q u a r e d e r r o r ) ： 一= 扎毛( 吲s2 m 。，厄( 卅2 丑s + 五曼= a s + 五p s ) = s ( 2 4 ) 其中丑、五分别为感兴趣区和不感兴趣区的加权值。 该方法的突出特点是：对图像进行评价时，将感兴趣区和非感兴趣区区别对待， 通过对图像中不同区域的加权来突出入眼对感兴趣区的兴趣程度。 由式( 2 3 ) 可知，对视觉兴趣性测量的核心任务就是如何确定加权值 、五，根据 上述视觉经验，对 、厶给出如下两个近似条件： ( 1 ) 当s 由0 增加到s 时， 将由+ _ o o 减小到1 。 ( 2 ) 当s 由0 增加到s 2 时，厶将由l 减小到某一不小于0 的常数；当s 由s 1 2 增 加到s 时，无将由该不小于0 的常数增加到1 。 2 3 图像编码效率的评价 对于一个图像编码方法，可以用冗余度、编码效率和压缩比来衡量信源特性和编 解码性能。 ( 1 ) 图像熵与平均码字长度 设图像像素灰度级集合为 而，而，丸) ，其对应的概率分别为p ( 4 ) ，p ( 畋) ， p ( 丸) ，则图像熵为： h ( d ) = - z p ( 4 ) l o g ：p ) ，；l 图像熵表示图像灰度级集合的比特数均值，即熵描述了图像信源的平均信息量。 借助于熵的概念，定义量度任何特定码的性能的准则：平均码长度 ( 2 5 ) z ：兰屈p ( z )( 2 6 ) i ；l 式中层为灰度级，碣为所对应的码字长度。z 单位也为比特字符。 6 长春工业大学硕士学位论文 ( 2 ) 编码效率 冗余度常用下式表示： r ：l 一1 h ( d ) ( 2 7 ) 由此可得相应的编码效翠为： 玎= 华= 击 亿s ，。 工 1 + r 、7 如果工与日( d ) 相等，编码效果最佳；如果三接近日( d ) ，编码效果编为佳；如何三 远大于日( d ) ，则编码效果差。 ( 3 ) 压缩比 压缩比是衡量数据压缩程度的指标之一。常用的压缩比定义如下： e = 班( 2 9 ) 其中厶表示压缩后代码的长度。压缩比的物理意义是表示源数据与压缩后的数据比值， 压缩比越高，图像压缩越大，反之亦然。 2 4 图像压缩编码技术 传统的图像编码是以香农信息论为出发点，用统计概率模型来描述信源。从该角 度出发，可将编码方法分为两类： ( 1 ) 冗余度压缩方法，也称无损压缩，信息保持编码或熵编码。解码图像和压缩编 码前的图像严格相同，没有失真。 ( 2 ) 信息量压缩方法，也称有损压缩，失真度编码或熵压缩编码。图像解码前后是 有差别的，允许有一定的失真。 由此，图像压缩编码方法从压缩编码算法原理上可以分类为： ( 1 ) 熵编码，即无损压缩编码，包括：游程编码、h u f f a n a n 编码、算术编码 ( 2 ) 信源编码，主要包括以下几种： 预测编码：d p c m 、运动补偿预测 频率域方法：正交变换编码( 如离散余弦交换d c t ) 、子带编码 空间域方法：统计分块编码 模型方法：分形编码、模型基编码 ( 3 ) 混合编码，包括j p e g 、小波图像编码 7 长春工业大学硕士学位论文 2 4 1熵编码( e n t r o p yc o d i n g ) 熵编码是纯粹基于信号统计特性的编码技术，是一种无损编码方法，解码后能无 失真地恢复原始图像。熵编码的基本原理是给出现概率较大的符号一个短码字，而给 出现概率较小的符号一个长码字，这样使得最终的平均码长很小。熵编码将待压缩的 数据流看作是简单的数字序列，而不关心数据的具体意义。 常用的熵编码方法有游程编码、h u f f m a n 编码和算术编码等三种。 2 4 1 1 游程编码( r u nl e n g t hc o d i n g ) 游程编码本质上就是计算图像信号出现的行程长度，然后将行程长度转换为代码。 它主要用于量化后出现大量零系数的情形，利用行程来表示连零码，以降低为表示零 码所用的数据量。 对于由信号 s l , s ：，l 组成的二值图像，可用“o ”，“l ”表示，它可连续出现， 也可不连续出现。连续出现0 的段称为“0 ”游程，连续出现“1 ”的段称为“1 ” 游程，它们的长度分别称为游程长度，记为l ( 0 ) 和l ( 1 1 。“0 ”、“l ”游程总是交替出 现的，对于随机的二元序列，各游程的长度也是随机变化的，其取值可为任意长度。 例如：一二元序列：0 0 1 1 1 1 1 0 0 0 1 0 1 l ，其游程编码为：2 5 3 1 1 2 。若每个元素用1 个字节来存储，则原二元序列得用1 4 个字节来存储，而对游程序列，则只需用6 个字 节来存储。由此可见，当一幅图像是由很多块颜色相同的大面积区域组成的，那么采 用游程编码的压缩比是惊人的。但是，如果图像中任何两个相邻像素点的颜色都不同， 此时使用这种算法不但不能压缩，反而会使数据量增加一倍。 2 4 1 2h u f f m a n 编码( h u f f m a nc o d i n g ) h u f f m a n 编码是d a h u f f m a n 根据可变长最佳编码定理提出的一种不等长最佳编 码方法 2 2 2 3 1 ，这里的“最佳”是指它的平均码长对相同概率分布的信源是所有有效编 码方法中最短的。 。 其基本思想【矧是：在编码过程中，对频繁使用的数据用较短的码字代替，较少使 用的数据用较长的码字代替，每个数据的码字各不相同，则其平均码字长度一定小于 按其它任何符号顺序排列方式的平均码字长度。 采用h u f f m a n 编码方法的实质是针对统计结果对字符本身重新编码，得到的单位 像素的比特数最接近图像的实际熵值。其过程可以用二叉树来说明，需要编码的字符 用树的叶节点表示，每个节点p 代指具体字符在相应子树中出现的概率。依次选择概 率最小的两个节点来构成中间节点，直到形成根节点，从而完成树的构造。显然，最 终树的根节点的概率为1 。在完成树的构造之后，所有树枝都被赋值为l 或0 ，则各输 入字符的h u f f m a n 编码就是从根到叶节点路径上的数字标识序列。 长春工业大学硕士学位论文 h u f f m a n 编码的基本步骤为： ( 1 ) 按照出现概率由大到小的顺序，将表示输入信号的符号重新排序( 相同概率的 符号可任意排列) 。 ( 2 ) 将最小的两概率相加，形成新的概率集合，重复( 1 ) ，直到只有两个概率为止。 ( 3 1 分配码字。码字分配从最后一步开始反向进行，对最后两个概率，一个赋予“0 ”， 一个赋予“1 ”。 在进行h u f f m a n 编码时，必须注意以下两个问题： ( 1 1h u f f m a n 编码构造出的码字并不是唯一的。 ( 2 1h u f f n m n 编码对不同的信源其编码效率不同，当信源概率分布很不均匀时，编 码效率会非常显著，但是当信源概率比较接近时，一般不使用h u f f m a n 编码方法。 另外，h u f f i n a n 编码需要进行先统计再编码两次处理，因此速度较慢，其译码过 程也较复杂；但因该编码方法非常简单，所以应用很广泛。 2 413 算术编码( a r i t h m e r 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 首次 介绍了它的实用技术，直到八十年代才出现了算术编码的具体实现方法。 算术编码的基本原理是：将被编码的数据序列表示成0 和1 之间的一个间隔 ( i n t e r v a l ) ，该间隔的位置与输入数据的概率分布有关。信息越长，编码表示的间隔就 越小，表示这一间隔所需的二进制位就越多。信息源中连续的符号根据某一模式生成 概率的大小来减少间隔，出现概率大的符号比出现概率小的符号减少的范围小，因此 只增加较少的比特位。其编码步骤为： ( 1 ) 将当前区间定义为l o ，1 ) 。 佗1 对输入流中的每个符号j ，重复下面的两步： 把当前区间分割为长度正比于符号概率的子区间。 为s 选择一个子区间，并将其定义为新的当前区间。 ( 3 ) 当把整个输入流处理完成后，输出应为能唯一确定当前区间的任何数字。 实际经验表明，算术编码与h u f f m a n 编码的平均压缩效果是十分相似的，只是 h u f f m a n 编码更快一些。但在未知信源概率分布的大部分情况下，算术编码要优于 h u f f n m n 编码。 2 4 2预测编码( p r e d i c t i v ec o d i n g ) 预测编码就是基于图像数据的空间冗余特性，利用像素间的相关性，用相邻的已 知像素( 或像素块) 来预测当前像素( 或像素块) 的值，然后再对预测误差进行量化 和编码。这些相邻像素或像素块可以是同行的，也可以是前几行的，相应的预测编码 分别称为一维和二维预测。 9 长春工业大学硕士学位论文 预测编码的关键在于预测算法的选取，这与图像信号的概率分布很有关系。实际 应用中常根据大量的统计结果来设计最佳的预测器，有时还使用自适应预测器以描述 图像信号的局部特性，从而提高编码效率。 预测编码有线性预测和非线性预测两大类。线性预测编码又称为差分脉冲预测编 码调制( d p c m ：d i f f e r e m i a lp u l s cc o d em o d u l a t i o n ) 。帧内预测编码( i n t r ap r e d i c t i v e c o d i n g ) 一般采用像素预测形式的d p c m ，其优点是算法简单，易于硬件实现；缺点 是对信道噪声及误差很敏感，会产生误码扩散，使图像质量大大下降，压缩比也很低。 帧间预测编码( i n t e rp r e d i c t i v ec o d i n g ) 主要利用视频序列相邻帧间的相关性，即 图像数据的时间冗余来达到压缩的目的，可以获得比帧内预测编码高得多的压缩比。 2 4 3变换编码( t r a n s f o mc o d i n g ) 变换编码是通过信号变换来消除图像数据空间相关性的一种有效方法。其基本思 想是将在空间域描述的图像信号通过变换映射到另外一个正交矢量空间( 变换域) ，使 变换后系数之间的相关性降低。在变换域上应满足： ( 1 ) 所有的系数相互独立。 ( 2 ) 能量集中于少数几个系数上。 ( 3 ) 这个系数集中于一个最小的区域内。 如果所选的正交矢量空间的基向量与图像本身的特征向量很接近，那么同一信号 在这个空间中描述起来就会简单得多。经过正交变换后，变换系数间近似统计独立， 相关性基本消除，并且能量主要集中在直流和低频的变换系数上，然后再在变换域进 行滤波、量化和统计编码就能实现有效的码率压缩了。 就数据压缩而言，所选择的变换方法最好能与图像信号的特征匹配，此外还应从 失真要求、编码比特率以及实现的复杂度等多方面来综合考虑。常见的变换编码有： 正交变换、k - l 变换、离散余弦变换、哈达玛特变换等。 ( 1 ) 正交变换 对于一个由n 个采样值组成的离散信号，可以认为它是一个在n 维空间中的矢量， 而每个采样值代表n 维空间中数据矢量x 的一个分量，为了有效表示x ，则有： y = t x ( 2 1 0 ) 其中，y 和r 分别为变换矢量和变换矩阵。如果丁为实数矩阵且t = t ”，则r 为正交 矩阵，其对应的变换为正交变换。 对于图像编码，式( 2 1 0 ) 可以写为： x = t ”】，= y , o 。( 2 1 1 ) 上式表示，将x 转换到由基矢量，( f = 1 ，2 ，n ) 生成的n 维空间，即变换域中，咒表 1 0 长春工业大学硕士学位论文 示石在( i = l ，2 ，1 上投影的大小，称为变换系数。由变换系数所构成的矢量1 7 是 信号x 在变换域中的表示。 正交变换具有能量集中性。对于图像信号，其能量大都集中在低频部分，经过正 交变换后，y 可以由低频部分的m ( m n ) 个子集来近似，并且由此恢复的信号x 不 会引起明显的误差。 ( 2 ) k - l ( k a r h u n e n l o e v e ) 变换 k - l 变换是一种最佳正交变换。它是用数据本身的相关矩阵对角化后完成的，这 种变换将产生完全不相关的变换系数。如果图像数据之间是高度相关的，经过k - l 变 换后的系数将出现多个零值，同时某些系数的值会很小。 k - l 变换的变换矩阵是由图像数据本身求得的，不同的图像数据有不同的变换矩 阵，由此造成反变换矩阵的不惟一性；另外k - l 变换矩阵的构造计算量很大，因而它 不是一种实用的变换方法，通常作为评价其他线性变换的比较基准。 ( 3 ) 离散余弦变换( d c t ：d i s c r e t ec o s i