（通信与信息系统专业论文）静态图像压缩编码算法的若干研究.pdf

一 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：2 堂二赶日期：丛生：垒：兰! 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件和 电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：2 茎二敌导师签名： 山东大学硕士学位论文 = = = = = 暑= 昌= 昌= 昌= = = 盲= = = = = = = = = = = 昌暑= = = 皇昌= = 暑葛昌= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 皇= = = = = = = = = = = = = = = 皇皇= 目录 摘要l j 6 l 1 3 s t r a c t 3 符号说明5 第一章绪论。6 1 1 图像压缩编码综述6 1 2 数字图像质量的评价一8 1 3 本文的组织结构l o 第二章图像编码及压缩技术1 1 2 1 信息论基础知识f 2 1 - 2 2 1 1 2 1 1 信息和信息量1 l 2 1 2 信息冗余l2 2 2 图像压缩基础理论。1 3 2 3 主要编码方法【2 5 之7 1 1 4 2 3 1 霍夫曼编码1 4 2 3 2 行程编码l5 2 3 3 方块编码1 6 2 3 4 位平面编码l8 2 3 5 变换编码19 2 4 数字图像压缩的国际化标志【2 6 3 引2 0 2 4 1 二值图像标准压缩技术2 0 2 4 2 静止图像标准压缩技术2 0 第三章矩形划分编码及改进算法研究2 2 3 1 二值图像矩形划分编码2 2 3 1 1 不重叠矩形划分编码2 2 3 1 2 重叠矩形划分编码2 5 3 2 窗口滑动搜索的矩形划分编码2 6 3 2 1 矩形划分编码的局限2 6 3 2 2 矩形窗口滑动搜索算法2 8 山东大学硕士学位论文 3 2 3 解码过程3 2 3 2 4 实验仿真结果及分析3 3 3 3 基于预处理的矩形划分算法3 4 3 3 1 图像预处理的原理3 5 3 3 2 图像预处理3 7 3 3 3 预处理后的矩形划分3 7 3 3 4 实验仿真及分析3 9 3 4 本章小结4 0 第四章基于小波变换的灰度图像压缩4 2 4 1 小波变换理论4 2 4 2 小波系数的特点4 5 4 3 嵌入式零树编码( e z w ) 及改进4 6 4 3 1 零树表示4 7 4 3 2e z w 的实现。4 9 4 3 3e z w 的改进。5 0 4 4 实验仿真结果5 2 4 5 本章小结5 3 第五章总结与展望一5 5 5 1 本论文内容总结5 5 5 2 下一步研究的设想5 6 参考文献5 7 致谢6 2 攻读硕士学位期间发表论文6 3 2 山东大学硕士学位论文 c o n t e n t s c h i n e s ea b s t r a c t 1 e n g l i s ha b s t r a c t 3 s y m b o ld e s c r i p t i o n 5 c h a p t e r1 i n t r o d u c t i o n 6 1 1s u m m a r yo ti m a g ec o m p r e s s i o nc o d i n g o 一一 一 ， 1 2d i g i t a li m a g eq u a l i t ye v a l u a t i o n 8 1 3p a p e ro r g a n i z a t i o n 1 0 c h a p t e r2i m a g ec o d i n ga n dc o m p r e s s i o nt e c n o l o g y 1 1 2 1b a s i ck n o w l e d g eo f i n f o r m a t i o nt h e o r y 【2 1 - 2 2 1 1 2 1 1i n f o r m a t i o na n di n f o r m a t i o ne n t r o p y 1 1 2 1 2r e d u n d a n c y 1 2 2 2b a s i ck n o w l e d g eo fi m a g ec o m p r e s s i o n 1 3 2 3m a i nm e t h o d so f i m a g ec o d i n g 【2 5 - 2 7 1 4 2 3 1h u f f m a nc o d i n g 1 z i 2 3 2r u n - l e n g t hc o d i n g 1 5 2 3 3b l o c kc o d i n g 1 6 2 3 4b i tp l a n ec o d i n g 1 8 2 3 5t r a n s f o r mc o d i n g 1 9 2 4d i g i t a li m a g ec o m p r e s s i o ns t a n d a r d 2 6 ，3 8 2 0 2 4 1b i n a r yi m a g ec o m p r e s s i o ns t a n d a r d 2 0 2 4 2s t a t i ci m a g ec o m p r e s s i o ns t a n d a r d 2 0 c h a p t e r3r e s e a r c ho fi m p r o v e da l g o r i t h mb a s e do nr e c t a n g u l a rp a r t i t i o nc o d i n g 2 2 3 1b i n a r yc o d i n gu s i n gr e c t a n g u l a rp a r t i t i o n 2 2 3 1 1 r e c t a n g u l a rp a r t i t i o n i n g 2 2 3 1 2o v e r l a p p i n gr e c t a n g u l a rp a r t i t i o n i n g 2 5 山东大学硕士学位论文 3 2r p cb a s e do nw i n d o w ss l i p p i n gs e a r c h i n g 2 7 3 2 1t h el i m i t a t i o n so fr p c 2 7 3 2 2r e c t a n g u l a rw i n d o w ss l i p p i n gs e a r c h 2 9 3 2 3d e c o d i n g 3 2 3 2 4s i m u l a t i o na n dr e s u l ta n a l y s i s 3 3 3 3r p cb a s e do np r e p r o c e s s i n g 3 5 3 3 1t h ep r i n c i p l eo fi m a g ep r e - p r o c e s s i n g 3 5 3 3 2i m a g ep r e p r o c e s s i n g 3 7 3 3 3r p ca f t e rp r e - p r o c e s s i n g 3 8 3 3 4s i m u l a t i o na n dr e s u l ta n a l y s i s 3 9 3 4s u m m a r y 4 1 c h a p t e r4c o m p r e s s i n gc o d i n go fs t a t i ci m a g e sb a s e d o nw a v e l e tt r a n s f o r m 4 2 4 1t h e t h e o r yo f w a v e l e t t r a n s f o r m 4 2 4 2t h ec h a r a c t e r i s t i c so fw a v e l e tc o e f f i c i e n t s 4 5 4 3e z wa n di m p r o v e m e n t 4 6 4 3 1z e r o t r e er e p r e s e n t a t i o n 4 7 4 3 2i m p l e m e n t a t i o n 4 9 4 3 3i m p r o v e m e n t 5 0 4 4s i m u l a t i o na n dr e s u l ta n a l y s i s 5 2 4 5s u m m a r y 5 3 c h a p t e r5p r o b l e m sa n ds o l u t i o n si nd e b u g g i n go fs y s t e m 5 5 5 1 s u m m a r yo ft h ei s s u e 5 5 5 2t h ei d e ao ff u r t h e rs t u d y 5 6 r e f e r e n c e s 5 7 a c k n o w l e d g e m e n t 6 2 p a p e r s 6 3 摘要 在当今社会，随着计算机及通信技术的发展，越来越多的业务需要信息技术 的支持。其中，绝大部分的信息是以图像信息的形式表示的。它们以数字化的方 式表示、存储、记录和传输，这就给数据压缩提出了非常高的要求。图像压缩编 码是专门研究图像数据存储压缩的技术。近年来，随着计算机技术的迅速发展， 图像编码技术取得了很大的进步，出现了许多新的编码思想和方法，如小波变换 和分形编码等。 二值图像是一类特殊的灰度图像，本身只包含黑白两种颜色。它是一类常见 而重要的信息来源，在实际生活中以及图像处理、模式识别等科研领域都占据着 重要的地位。日常中的文本文件，传真报等都是二值图像。由于二值图像是一种 灰度图像，所以如果能够找到一种有效压缩这类图像的方法，将对灰度图像编码 有着很大的推动作用。 作为图像压缩的一个分支，对二值图像压缩编码的研究工作具有非常重要的 意义，也一直没有停止。在对探索一些二值图像压缩算法的过程中，我们发现了 一种有效的编码方法一矩形划分编码算法。这种算法根据两点确定矩形的方法 来划分黑色像素，将图像划分成不同大小的矩形，通过对矩形对角顶点的编码来 实现二值图像的压缩编码。实验证明，这种方法比现阶段应用比较广泛的行程编 码要有效的多。由于图像中有些二值图像的像素比较混乱，用矩形划分编码对图 像进行压缩并不是非常理想。本文根据这种图像的特点提出了两种改进的二值图 像矩形划分编码算法。一是直接将二值图像像素划分成规则的区域，进行矩形划 分并将矩形的顶点进行编码；同时保留剩余区域混杂的黑白像素，以完成对图像 的编码。另一种算法是对图像进行预处理，使得图像能够保留尽可能少的前景信 息，这样图像中的前景信息将会很混乱的掺杂在一起，对背景信息进行矩形划分 编码。实验证明，改进的算法对于许多二值图像来说比原算法要好的多，也能够 达到很高的压缩比。 从二值图像延伸到扶度图像，我们根据小波变换后小波系数的特点，将行程 山东大学硕士学位论文 编码算法进行了改进，结合小波变换对灰度图像进行编码。通过实验证明，该方 法比原始的算法在压缩效率上有一定的提高。 关键词：二值图像；矩形划分；小波变换；行程 2 山东大学硕士学位论文 a b s t r a c t n o w a d a y s ，w i t ht h eh i g h - r a p i dd e v e l o p m e n to fc o m p u t e ra n dc o m m u n i c a t i o n s t e c h n o l o g y , m o r ea n d m o r eb u s i n e s sn e e d st h es u p p o r to fi n f o r m a t i o nt e c h n o l o g y m o s t 铆i n f o r m a t i o ni sb a s e do ni m a g e s ，w h i c hi se x p r e s s e d ，s t o r e d ，r e c o r d e da n dt r a n s p o r t e di n t h ed i g i t a lw a y s oa h i g h e rd a t ac o m p r e s s i o nm e t h o di sn e e d e d i m a g ec o d i n gi so n eo f t h et e c h n o l o g i e st h a tw o r k so nt h ec o m p r e s s i o no fi m a g e sd a t a a st h eb o o s to f c o m p u t e rt e c h n o l o g y , i m a g ec o d i n gt e c h n i q u eh a sg r e a tp r o g r e s s e s ，a n dal o to fn e w c o m p r e s s i n ga p p r o a c h e sw a r ep r o p o s e d ，s u c ha sf f a c t a lc o d i n ga n dw a v e l e tt r a n s f o r m c o d i n gr e c e n ty e a r s b i n a r yi m a g e sa r eas p e c i f i ck i n do fg r a yi m a g e s ，w h i c hc o n t a i n st w ok i n d so f p i x e l s ：b l a c ka n dw h i t e a sac o m m o na n di m p o r t a n ts o u r c eo fi n f o r m a t i o n ，t h eb i n a r y i m a g ei sv e r yi m p o r t a n tb o t hi nu s u a ll i f ea n dm a n ya r e a so fs c i e n t i f i cr e s e a r c hl i k e _ i m a g ep r o c e s s i n ga n dp a r e mr e c o g n i t i o n t e x tf i l e s ，f a x ，n e w s p a p e r sc a nb ea l l c o n s i d e r e da sb i n a r yi m a g e s a st h eb i n a r yi m a g ei sap o p u l a rk i n do fg r a yi m a g e s ，i f w ec a nf o c u so na ne f f e c t i v em e t h o do fb i n a r yi m a g e sc o m p r e s s i o n s ，i tm a ym a k eg r a y i m a g e sc o d i n gt r e m e n d o u sb o o s t a l t h o u g ht h eb i n a r yi m a g e sc o d i n gi sa ni m p o r t a n tb r a n c ho fi m a g ec o m p r e s s i o n s a n dt h er e s e a r c hw o r kh a sn o ts t o p p e d ，t h eb i n a r yi m a g ec o d i n gh a sas l o we v o l u t i o n , a n di tc a nn o tm e e tt h ea c t u a ln e e d s a m o n gt h eb i n a r yi m a g ec o m p r e s s i o na l g o r i t h m s ， r e c t a n g u l a rp a r t i t i o n i n gi sa ne f f i c i e n to n e a c c o r d i n gt ot h ep r i n c i p l et h a tt w op o i n t s d e t e r m i n ear e c t a n g u l a r , w ec a nd i v i d eb l a c kp i x e l sr e g i o n so ft h eb i n a r yi m a g ei n t o 幅r e c t a n g l e so fd i f f e r e n ts i z e s ，a n da c h i e v ei m a g ec o m p r e s s i o nc o d i n gb yc o d i n gt h e r e c t a n g l ed i a g o n a lv e r t e x e s n u m e r i c a lr e s u l t ss h o wt h a tt h i sa l g o r i t h mi sm o r ee f f e c t i v e t h a no t h e ra l g o r i t h m s ，s u c ha sr u n - l e n g t hc o d i n g ，w h i c hi sa p p l i e dw i d e l ya tt h i ss t a g e h o w e v e ls i n c ep i x e l so fs o m eb i n a r yi m a g e sa r ec h a o t i c ，i ti sv e r yh a r dt oa p p l yt h e r e c t a n g u l a rp a r t i t i o na l g o r i t h md i r e c t l y b a s e do nt h ec h a r a c t e r i s t i c so ft h ei m a g e sw e p r e s e n t e dt w ok i n d so fi m p r o v e da l g o r i t h m s t h ef i r s ta l g o r i t h mi st od i v i d et h eb i n a r y 山东大学硕士学位论文 i m a g e sd i r e c t l yi n t or e g u l a rr e g i o n sw h i c hi se n c o d e db yu s i n gr e c t a n g u l a rp a r t i t i o n a l g o r i t h m ，a n dp r e s e r v et h er e m a i n i n ga r e ao fm i x e db l a c ka n dw h i t ep i x e l s a n o t h e r a l g o r i t h mi st op r e p r o c e s st h ei m a g ef i r s t l yt om a k ei m a g e sr e t a i ni n f o r m a t i o na sl i a l e a sp o s s i b l eo nt h ef o r e g r o u n d ，a n dd i v i d et h eb a c k g r o u n do ft h ei m a g ei n t or e c t a n g l e s f o rc o d i n g n u m e r i c a lr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mi sm u c hb e t t e rt h a nt h e o r i g i n a la l g o r i t h m ，a n di tc a na c h i e v ev e r yh i g hc o m p r e s s i o nr a t i o a n o t h e rr e s e a r c hi st h ec o d i n go fg r a yi m a g e s w ec o d et h eg r a yi m a g e sc o m b i n e d i m p r o v e dr u n - l e n g t he n c o d i n ga l g o r i t h m 、析t hw a v e l e tt r a n s f o r ma c c o r d i n gt o t h e c h a r a c t e r i s t i c so ft h ew a v e l e tt r a n s f o r i l lt o e 伍c i e n t s n u m e r i c a lr e s u l t ss h o wt h a tt h e m e t h o dh a sam o r ei m p r o v e m e n ti nc o m p r e s s i o ne f f i c i e n c yt h a nt h eo r i g i n a la l g o r i t h m k e y w o r d s ：b i n a r yi m a g e ；r e c t a n g l ep a r t i t i o n ；w a v e l e tt r a n s f o r m ；r u n l e n g t h 4 m s e p s n r e r ，t e z w s a q c r m e a ns q u a r ee r r o r均方误差 p e a ks i g n a lt on o i s er a t i o峰值信噪比 e r r o rr a t e 失真率 w a v e l e tt r a n s f o r m小波变换 e m b e d d e dz e r o t r e ew a v e l e t嵌入式零树小波编码 s u c c e s s i v e a p p r o x i m a t i o nq u a n t i z a t i o n 逐次逼近量化 c o m p r e s s i o nr a t e 压缩比 5 山东大学硕士学位论文 1 1 图像压缩编码综述 第一章绪论 视觉作为人类最高级的感知器官，在人类感知中扮演着最重要的角色。图像 作为人类最丰富的视觉信息来源，具有直观、形象和易懂的特点。图像是指用模 仿、对照等方法制成的人或物的形象，也包括光线经反射、折射形成与原物体相 同或者相似的一系列的图形。 随着科学技术的发展，当今社会以计算机通信技术为主的信息技术发展日益 成熟，使得越来越多的业务需要信息技术的支持，它们改变着整个社会的生活方 式。在这种的信息环境下，大量信息都是用数字化形式来表示、存储、记录和传 输，而这些信息中图像信息又占了绝大部分。数字化图像信息在图像质量、图像 传输的稳定性以及便捷性等方面具有很多的优势。然而，数字化图像所占的空间 非常大，不仅导致存储空间的需求很大，而且要求传输频带过宽。为了对图形信 息能够更好地进行处理，进行图像压缩编码是必然选择，只有这样才能更好地对 数字图像信息进行存储和传输【1 j 。 图像编码是从二十世纪四十年代末开始进行研究，迄今为止已有近六十年历 史。1 9 6 9 年，首届“图像编码会议”( p i c t u r ec o d i n gs y m p o s i u m ) 在美国举行，此 次会议表明图像编码将以独立的学科跻身于学术界。二十世纪七十年代后，随着 计算机技术的迅速发展，图像编码技术取得了很大的进步，有关图像编码的理论 得到了深入讨论，各种新的编码方法在计算机上进行大量实验，并诞生了一系列 静止、运动图像的诸如j p e g 、j b i g 、j p e g 2 0 0 0 等的编码标准【2 7 】。 据研究发现，静态图像内部以及视频序列中相邻图像之间存在大量的冗余信 息。图像压缩的目标是利用各种方法、使用尽量少的比特数表示和重建原始图像。 图像压缩就是利用各种信源编码方法，使得图像在重建时保证质量的同时，除去 图像中多余的冗余信息。冗余信息的减少是数据量的减少，而没有去除信源的信 息量。从数学角度讲，图像可以看作一个多维函数，压缩用来描述这个函数的数 据量实质上是减少其相关性。通过一定的处理，去除原始图像信号中的冗余信息， 6 ， 山东大学硕士学位论文 就可以达到压缩图像的目的。此外，利用人眼的视觉特性，剔除人眼不能觉察或 不易感知的客观信息，也能够进一步提高压缩效率。另外一些情况下，利用人眼 的感官视觉特性，在不妨碍图像在实际应用时需要的主观质量的前提下，恢复图 像时允许一定程度的客观失真，那么可以更大可能性地减少图像的数据量。这样， 我们就可以从原始图像信息中提取有效的信息，尽可能地去掉图像中那些没用的 冗余信息，高效率地进行图像传输或存储。重建图像时仍能获得与原始图像形同 或相差不多的图像，保持图像的有效信息。 图像压缩编码的技术有多种分类方法【8 l 。根据编码对象的不同，可分为静态图 像编码、动态图像编码、传真文件编码、二值图像编码、灰度图像编码、黑白图 像编码和彩色图像编码等。根据压缩过程有无信息损失，可分为有损压缩编码和 无损压缩编码，或称不可逆编码和可逆编码。有损编码允许图像信号有失真，解 码图像与原始图像之间存在一定的误差，但要保证视觉效果可以被接受，它可以 达到较高的压缩比，主要用于网络图像传输等。有损编码方法有预测编码、变换 编码、子带编码以及分形编码等。无损编码要求图像信息无丢失，通过解码可以 完整地重建原图像，压缩倍数比较小，主要应用于图像数字存储及医学图像分析 等。无损编码方法有霍夫曼编码、算术编码、游程编码以及跳白块编码等。 经典的图像压缩编码算法，其基本出发点是将数字图像作为一个信源，依据 图像本身固有的统计特性对图像进行编码。预测编码是最早的图像压缩算法，它 是以像素为处理单元，利用数字图像行内、行间的高度相关性，以已经传出的近 邻像素值作为参考预测当前像素值，将预测值和原值之差进行量化编码，以减小 相关性，达到压缩数据的目的。预测编码方法简单，宜于硬件实现，可实时运算， 复原图像质量较好，但压缩比较低。最常用的是差分脉冲编码调制( d p c m ) 9 - - 1 0 】。 二十世纪六十年代后，变换编码得到了很大的发展。变换编码主要是依据信 号能量与信息的分布关系，将图像对应的像素值通过选取合适的正交变换转换成 一组更为合适的图像系数，然后根据人的主观视觉特性对各变换系数进行不同精 度的量化后编码的技术。正交变换的目的是为了解除像素之间的空间相关性，图 像信号经过正交变换后能量相对集中，各系数之间的相关性下降，通过去掉或分 配较少的比特数对能量较少的分量进行编码就可以压缩图像信息。正交变换包括 7 山东大学硕士学位论文 离散傅里叶变换( d f ，i ) 、沃尔什一哈达玛变换( w h t ) 、哈尔变换( h r t ) 、斜变换( s l t ) 、 离散余弦变换( d c t ) 、k - l 变换等，其中离散傅里叶变换目前已经成为多种静止和 运动图像的国际编码标准1 1 1 2 】。 进入八十年代以后，计算机图形学、模式识别和计算机视觉被大量引入图像 压缩编码中，给图像编码提供了新的研究途径，使得图像编码有了突破性进展。 像子带编码【1 3 1 4 1 、小波变换【1 5 - 16 1 、矢量量化【1 7 1 、分形【1 8 之们、神经网络等新一代算 法发展起来，形成了新一代的压缩编码方法，这些方法更依赖人眼的视觉特性， 使得图像的压缩比可以达至f j 2 0 至8 0 倍，甚至更高。 除了上述所介绍的主要编码算法以外，还有很多其它的经典编码算法，例如 将多值图像转化为二值图像编码的比特平面编码，包含许多国际标准如霍夫曼编 码、算术编码、游程编码等统计编码。 1 2 数字图像质量的评价 图像压缩的目的是减少图像的冗余信息，这就导致真实的或者一定数量的视 觉信息的丢失。因为可能丢失重要信息，所以需要一种来评定丢失信息和范围定 量的方法。图像质量评价标准通常采用保真度( f i d e l i t y ) 准则，分为客观保真 度准则和主观保真度准则。 客观保真度准则是指图像压缩重建之后图像和原图像之间的均方差误差或者 压缩后图像的均方根信噪比。当图像信息损失的程度可以表示成原图像和被压缩 后被解压的重建图像之间的函数时，这个函数就是基于客观保真度准则的。设原 图像为f ( x ，y ) ，压缩后解压重建得到的图像为g ( x ，y ) ，x 、y 取值范围均为图像 的坐标范围。如果一副图像大小为m n 像素，对于x 和y 的所有值，两幅图像之 间的误差或者编码噪声e ( x ，y ) 可定义为 e ( x ，y ) = g ( x ，y ) 一f ( x ，y ) ( 卜1 ) 两幅图像的总体误差为 m l | 一i e = g ( 工，y ) - f ( x ，y ) ( 1 2 ) x - - oy - - - o 两幅图像之间的均方误差可表示为 8 山东大学硕士学位论文 m s e = 面1 m 刍- i 哥n - i g ( w ) 一m 硝 ( 1 - 3 ) 一种更为紧密的客观保真度准则是压缩解压图像的均方信噪比，g ( x ，y ) 表示 原始图像，看做是f ( x ，y ) 和噪声信号e ( x ，y ) 的和，则压缩解压后的重建图像的 信噪比s n r 可定义为 ，一1 - i 9 2 ( x ，y ) s n r = l o l o g l o 丽两型型i _ ( 1 - 4 ) g ( x ，y ) - l ( 训) 2 另一种常用的数字图像保真度度量是峰值信噪比p s n r ，定义为 ： 亨肛1 = 丝：型 一=(i-5psnr1 0 1 0 93 - ) ： y 竺竺兰了() 其中a 是最大像素值。 虽然客观保真度准则提供了一种便捷的图像信息损失的评估标准，但是大部 分图像解压重建后还是需要由人观察。图像主观保真度就是以人作为图像观察者， 用人的视觉对图像的质量进行评价。实际应用中，具有相同客观保真度的不同图 像，其人的主观感觉会受到许多因素的影响而产生变化。同时，人的视觉系统有 一些独特的特点，例如人的视觉系统对灰度突变特别敏感，使得图像边缘轮廓附 近的误差影响更为严重。这些引起视觉明显差异的因素，会使得客观保真度往往 无法表现出来。因此，主观保真度来评价图像也是非常必要的。通常，主管保真 度准则将图像的保真情况分为以下几个不同的等级。如表1 1 所示。 表1 1 图像的等级量表 9 山东大学硕士学位论文 1 3 本文的组织结构 本文的主要工作是针对二值图像的压缩编码展开并进行探讨和研究的。为了 改善目前二值图像压缩比不高的现状，本文对一种已有的典型无损压缩算法做了 改进，将图像的压缩比得到提高。本文的主要研究工作如下： 第一，针对矩形编码的局限性提出了新的改进方案，增加了编码预处理，有 效地减少了黑色像素的数目。 第二，提出了一种基于矩形编码的二值图像编码方法，针对图像黑白像素均 衡的图像进行窗口滑动搜索算法，对图像进行窗口首先搜索，然后进行不均匀矩 形划分，将图像划分为尽量大的矩形块，这样我们可以在保证图像质量的前提下 进一步提高了二值图像的压缩效率。 论文一共分为五个部分： 第一章是绪论，介绍了图像压缩编码这一领域的相关背景知识和研究内容， 并具体指出本文的研究内容和组织结构； 第二章是对数字图像特征及其编码压缩技术做了简要介绍，对最新的压缩算 法进行了阐述； 第三章是论文的中心内容，介绍了二值图像矩形划分算法，并详细阐述了本 文对基于矩形划分编码算法的改进研究，并且通过实验仿真和数据对比分析证明 了改进算法的成功； 第四章是对灰度图像进行小波变换后的数据研究及相关改进； 第五章是全文的总结部分，总结了全文工作和不足之处，并对将来的工作提 出进一步的设想。 l o 山东大学硕士学位论文 第二章图像编码及压缩技术 图像压缩编码属于数据压缩范畴，信息论中关于数据压缩的理论同样适用于 图像数据。数据压缩的历史可以追溯到1 8 4 3 年出现的莫尔斯( m o r s e ) 代码。1 9 3 9 年美国贝尔实验室的h d u d l e y 发明了通道声码器，将声音频谱的能量划分为有限 数目的频带，并且在每个频带内传输相应的能级，能够得到较高的压缩。从上世 纪5 0 年代开始，随着数字信号处理( d s p ) 、时间序列分析、参数估计、离散变换、 模式识别以及自适应技术的进展，图像压缩技术得到了极大的发展。 2 1 信息论基础知识【z 啦l 2 1 1 信息和信息量 信息是信息论中的术语，常常把消息中有意义的内容称为信息。1 9 4 8 年，美 国数学家、信息论的创始人仙农在他的论文中指出【2 3 】：“信息是用来消除随机不定 性的东西”。信息之所以成为人们研究的对象，一方面在于信息的不确定性；另一 方面在于信息是可以量度的。 在一个随机事件e ，如果它出现的概率是p ( e ) ，那么它所包含的信息为： 1 1 。1 0 9 高= - l o g p 饵) ( 2 - 1 ) i 称为e 的自信息。如果p ( e ) = l ，即事件总在发生，那么i = o 。 对于一个离散信息x 的符号集合为x = 而，而，矗 ，它所包含符号的概率 分别为p = p ( 而) ，p ( 屯) ，p ( 而) ) 。如果各个符号的出现都是相互独立的，那么 对于任意一个x ，它的信息量定义为： ，( 一) = - l o g p ( 薯) ( 2 - 2 ) 从式2 2 我们可以看到，如果一个随机事件出现的概率越小，则其所携带的 信息量越大；反之，信息量越少；如果该事件必然出现或必然不出现，则信息量 山东大学硕士学位论文 为0 。信息量i 表示随机信号单个符号的不确定性，这种不确定性的平均值，我们 定义为随机变量x 的熵： h ( x ) = e e i ( x ；) = 一p ( x i ) l o g p ( x i ) ( 2 - 3 ) 熵是对随机变量的平均不确定性的一个度量。在数值上等于为描述随机变量 所需要的平均比特数，其值总是非负的。对于一个随机变量来说，它的熵也称为 自信息。对于两个随机变量来说，它们之间的互信息反映了两个变量之问相互依 赖的程度。 假设一副数字图像一共有q 种灰度值置，8 2 ，并且其出现概率分别为 p = p l ，p 2 ，岛 ，那么每一个灰度所具有的信息量分别为一l o g p l ，- l o gp 2 ， 一l o g 见，其平均信息量，即图像的熵为 h = 一圭p 。l 。g p 。( 2 - 4 ) i = l 图像的熵是像素各个灰度级比特数的统计平均值，即给出了对此灰度进行编 码时所需要的平均位数值的下限。 2 1 2 信息冗余 冗余度是在进行信息处理时信息中所包含的多余信息。在编码器部分进行编 码时，信息中的冗余信息将会产生额外编码，如果去除这些冗余信息，就能够减 少消息量。信息冗余是数字图像压缩的主要问题，它不是一个抽象概念，可以用 数学公式进行量化。如果