（控制理论与控制工程专业论文）混合神经网络应用于图象处理的研究.pdf

浙江大学硕士学位论文 摘要 图象处理技术包括图象复原、图象压缩、图象分割、图象增强等一系列分支， 目前它在遥感、字符识别、射线底片等众多领域得到迅速应用和推广。图象处理 技术增强了人类对大干世界知识获取的能力，例如卫星云图的摄制、医疗监控系 统的运作，乃至数字化视频光盘的压制，都随着图象处理技术的发展而逐步更新。 近几年，随着神经网络理论韵深入研究，神经网络技术的并行计算能力、非 线性映射和自适应能力等优点得到了国内外学者的充分重视，各种神经网络模型 在图象处理领域中得到了广泛的应用。 本文将立足于神经网络技术和图象处理技术实际的结合情况，做出新的探讨 和尝试。 论文的主要内容如下： 首先，作者系统的介绍了图象处理和图象编码的特点及其发展过程。全面、 系统地概述了传统编码算法的优点，并同时指出了其存在的若干问题，为本论文 指明了主要的研究方向。 然后，作者对各种流行的神经网络模型在图象处理领域中的应用进行了汇 总，根据图象处理的具体内容对这些应用进行分类叙述，阐明了神经网络技术在 图象处理领域中的优点和不足之处。 再次，作者依据自组织特征映射( s o f m ) 理论和主元分析( p c a ) 理论， 提出了一种基于p c a s o f m 混合神经网络的图象压缩编码算法，并对s o f m 网 络学习参数的优化进行了探讨。实验证明，与普通p c a + s o f m 连续编码算法和 基本s o f m 算法相比，这种混合编码算法由于占用存储空间少，因而降低了码 书设计的计算量，并改善了码书的性能。 另外，作者针对上述基于神经网络的图象压缩软件方法，提出了硬件化结构 方案，并探讨了其具体实现过程的要点和难点。 最后，作者对全文进行了概括性总结，并指出了其他有待深入研究的问题和 今后工作的重点。 关键词：图象处理，图象压缩，神经网络，变换编码，混合编码，矢量量化，自 组织特征映射，主元分析 一一 塑坚查兰竺主兰垡丝苎 a b s t r a c t i m a g ep r o c e s s i n gt e c h n o l o g yi n c l u d e si m a g er e s t o r a t i o n ，i m a g ec o m p r e s s i o n ， i m a g es e g m e n t a t i o n ，i m a g ee n h a n c e m e n t ，e t c c u r r e n t l y , i ti sw i d e l ya d o p t e di na n d s p r e a dt of i e l d ss u c ha sr e m o t es e n s i n g ，c h a r a c t e rr e c o g n i t i o n ，r a d i o g r a p h i cf i l ma n d s oo n t h et e c h n o l o g ye n l a r g e st h eu t i l i z a t i o no f i m a g e s ，w h i c hw eo b t a i nf r o mt h e b o u n d l e s su n i v e r s e a n dw ec a nd e s i g nd i g i t a lv i d e od i s c ，s a t e l l i t en e p h o g r a mc e m a r a o rm e d i c a ls u p e r v i s es y s t e mw i t hh i g h - p e r f o r m a n c eb a s e do nt h ei m a g e t e c h n o l o g y a r t i f i c i a ln e u r a ln e t w o r k st e c h n o l o g yr e s e a r c hh a sg o n ea l o n gw a yi nt h ep a s t d e c a d e t h es p e c i a l i s t sa th o m ea n da b r o a di nt h ei m a g e p r o c e s s i n gf i e l dh a v ep a i d h i g ha t t e n t i o na n db e e ne n g a g e d i nt h ea d v a n t a g e so f n e u r a ln e t w o r k t e c h n i q u e ss u c h a st h ea b i l i t i e so f p a r a l l e lc o m p u t i n g ，n o n l i n e a rm a p p i n ga n ds e l f a d a p t i v e n e s s ，a n d a p p l i e dav a r i e t yo f n e u r a ln e t w o r k m o d e l si n t ot h ei m a g e p r o c e s s i n gf i e l d a c c o r d i n g t ot h ep r a c t i c a lc o m b i n a t i o no ft h en e u r a ln e t w o r k st e c h n o l o g ya n d i m g ep r o c e s s i n gt e c h n o l o g y , t h i s t h e s i sr e s e a r c h e si n t on e w a l g o r i t h m si nd e t a i l t h em a i nc o n t e n t so f t i l i st h e s i sa r ea sf o l l o w s ： f i r s t l y , t h ea u t h o rg i v e sa no v e r v i e wo nt h ec h a r a c t e r i s t i c sa n dh i s t o r yo ft h e i m a g ep r o c e s s i n gt e c h n o l o g ya n di m a g ec o d i n gt e c h n o l o g ya n di n t r o d u c e ss o m eb a s i c c o d i n ga l g o r i t h m s i nd e t a i l t h ea u t h o ra l s od i s c u s s e so ns o m e p r o b l e m s 0 n a p p l i c a t i o n ，w h i c hw i l lb ep a r t l ys e t t l e di nt h i st h e s i s a n dt h e n ，t h ea u t h o rr e v i e w sm a n ya p p l i c a t i o n so fn e u r a ln e t w o r ki ni m a g e p r o c e s s i n ga n dd i s c u s s e st h es t a t u sq u oa n dp r o s p e c to fn e u r a ln e t w o r k a l lt h e s e a p p l i c a t i o n s a r e c a t e g o r i z e da c c o r d i n g t ot h e p h a s e s o fi m a g e p r o c e s s i n g a n d d i s c u s s e di nd e t a i l i nt h ec o n c l u s i o n o f p a p e r ，h e l i s t ss e v e r a l d i s a d v a n t a g e so f n e u r a l n e t w o r k t e c h n i q u e s c o m b i n i n g t h e s e l f - o r g a n i z i n g f e a t u r e m a pt h e o r y ( s o f m ) a n dp r i n c i p l e c o m p o n e n ta n a l y s i st h e o r y ( p c a ) ，t h e a u t h o r p r o p o s e s a n i m a g ec o m p r e s s i n g a l g o r i t h mb a s e do np c a s o f mh y b r i dn e u r a ln e t w o r k ，w h i c hh a st h ea d v a n t a g e so f b o t hp c aa n ds o f m an e wm e t h o do fs e l e c t i n gi n i t i a lc o d e b o o ka n dd i s t o r t i o n i i 浙江大学硕士学位论文 c r i t e r i o ni sp r e s e n t e dt oi m p r o v et h ee f f i c i e n c yo fs o f m n e u r a ln e t w o r k a c c o r d i n g t o t h es t a t i s t i cf e a t u r eo fp c a t r a n s f o r m a t i o n a lc o e f f i c i e n t s i m u l a t i o nr e s u l t ss h o wt h a t c o m p a r e d t os u c c e s s i v ep c aa n ds o f ma l g o r i t h mo rb a s i cs o f ma l g o r i t h m ， p c a s o f m h y b r i da l g o r i t h m h a s m a n ya d v a n t a g e s ：l e s sm e m o r yo c c u p a t i o n ； s u b s t a n t i a lr e d u c t i o ni nc o m p u t a t i o na n dt h eb e t t e rp e r f o r m a n c eo fc o d e b o o k w h a ti sm o r e ，t h ea u t h o rp r o b e si n t oh a r d w a r e b a s e dn e u r a ln e t w o r k ，w h i c hh e h a se n g a g e dw i t hi m a g ec o m p r e s s i o na b o v e f i n a l l y ，t h e a u t h o rm a k e sac o n c l u s i o na n d p r o p o s e s t h ef u t u r er e s e a r c h d i r e c t i o n s k e y w o r d s ：i m a g ep r o c e s s i n g ，i m a g ec o m p r e s s i o n ，n e u r a ln e t w o r k ，t r a n s f o r m c o d i n g ，h y b r i dc o d i n g ，v e c t o rq u a n t i z a t i o n ( v q ) ，s e l f - o r g a n i z i n g f e a t u r e m a p ( s o f m ) ，p r i n c i p l ec o m p o n e n ta n a l y s i s ( p c a ) 浙江大学硕士学位论文 序和致谢 攻读硕士的生活是在苍茫的原野上寻觅一点点闪亮的星火，点滴所获都受益匪浅，但前 行的路上必定要留下一串串踏实的印迹。也许，这是一种苦行僧的生活。在许多人眼里这样 的生活甚至是不完美的。但这丝毫不意味着我们不在阳光的沐浴下，不朝着生命的方向奔跑。 正如职业探险家刘雨田先生说的“每一种生活都很好”。没有人会被知识压垮，知识只 会使我们愈发身。矫健，适度的紧张也只会给予我们更多的活力。 感谢生活。 生活使我们有缘来到这存在里品味个中滋味快乐经常是在我们忙得焦头烂额时突然 造访，骄傲总是当我们精疲力竭时油然而生。一个又一个脚印经过的是满地绮罗，盈耳丝竹。 偶尔回首，会惊叹那原野上的星光绽放。 回首三年有多少人点亮星火，激励我探索；又有多少人伸出热情的手，让我远离徘徊。 感谢孙优贤院士。 我的导师，他那严谨而开放的治学态度、渊博而深邃的学识、敏捷深刻的洞察力和平易 近人的长者风范一直影响和鼓励着我，这将是我一生中最宝贵的精神财富，使我终生受益。 感谢卢建刚副教授。 我的副导师，三年来，他在学业上给予的指引，工作上给予的教诲，生活上给予的启发， 学生将铭记在心。 感谢林庆女士，她总是轻描淡写她给予我们的如此多的热忱帮助这在我的记 己中却不 会褪色。感谢皮道映教授、戴华平副教授，王智副研究员等老师，众多专家的指导，开拓了 我的视野。 感谢孔亚广博士、胡国龙博士、蒋鹏博士、黎善斌博士、宰守刚硕士、许锋硕士、郭济 琳硕士和张震宇硕士，无论在学习和生活中，多年共同奋斗的情义，不会被时光所剪裁。感 谢戴晓华博士、尹红霞博士、张端博士、扬旭华博士、童豪硕士、黄方硕士、单鸿亮硕士、 林斌硕士、王加成硕士、孙计硕士、任旭东硕士，张仲广硕士等同窗，犹记得我们无数次闪 亮的讨论和你们给予我的支持。 最深的感谢给我的父母和家人，一切尽在不言中。 方驶二零零四初春于求是园 浙江大学硕士学位论文 1 1 引言 第一章数字图象的基本介绍 随着计算机技术的进步以及其应用范围的扩大，数字图象处理技术也得到了 迅猛的发展。例如，在林业、农业以及水利电力等工程的开发方面，利用飞机、 卫星获得的遥感图象可以对工程进展和阶段性成果进行检测；在医学方面，利用 x 光等技术获得的图象可辅助医生进行诊治工作；在社会治安方面，公安人员可 以利用人脸识别技术和指纹图片技术，对罪犯进行追踪，迅速破获各类案件；在 与我们生活最接近的影视以及互联网方面，利用计算机图象技术所表达的各种视 觉效果，丰富了千千万万人的生活。 1 2 数字图象处理的基本概念 所谓图象，指客观景物通过某种系统的一种映射。例如，照片和电影是最直 观、最常见的图象实例。当然，世界上的各种客观事物，必须经过一定步骤的变 换处理，才可以变成计算机可识别、可处理的数字图象。所谓数字图象，指的是 利用计算机以及其它相关的数字技术，对现实世界的真实图象施加某种运算和处 理，以达到某种目的。 数字图象处理系统基本的三个部件是：处理图象的计算机、图象数字化仪和 图象显示设备。 图1 1 显示了一个完整的图象处理系统。由数字化设备产生的数字图象先进 入一个适当装置的缓存中，根据操作员的指令，计算机调用和执行程序库中的图 象处理程序。在执行过程中，输入图象被逐行读入计算机。处理结束后，计算机 逐象素生成一副输出图象，并将其逐行送入另一个装置的缓存中。 浙江大学硕士学位论文 图l 1 数字图象处理系统 在其自然形式下，图象并不能直接由计算机分析。如果希望将现实世界中一 幅真实的图象转化为计算机能描述的方式，从而使得用户可以在自己的应用程序 设计过程中方便地使用并操作它们，则最基本的步骤是将图象转化为计算机可以 接受的格式，即一连串的特定数字，这也即所谓的图象的数字化过程，这样形成 的图象一般称为数字图象。数字图象的形成过程中，最典型、最重要的几个处理 过程依次为：建立空间物体描述模型、图象的采样、图象的量化、图象数据的传 输和图象的存储方式。以下将详细介绍数字图象的形成过程。 首先，图象是对空间物体的描述，因此图象形成过程中最基础的一个步骤是 如何建立空间物体的描述模型。对于一个空间的三维物体形状的描述而言，一般 可以通过测量物体空间不同坐标位置与测量原点的距离，从而获得整个物体的轮 廓，而如果需要完全描述该物体的整体性质，例如物体构成成分的性质等，则需 要考虑物体表向的光亮度。一般情况下，光亮度为物体空间坐标( x ，y ，z 1 、照射 物体的光波长以及观察时间的函数。图象的形成过程必须对三维物体进行简化处 理，通过拍照等手段处理，得到二维图象，坐标则相应简化为( x ，y ) 。所谓数字 图象是指将物体空间坐标位置和亮度变化都用离散数字量进行表示的图象。 其次，数字图象形成过程中最关键的步骤为图象亮度公式的离散化。为了便 于计算机的处理，图象的亮度函数f ( x ，y 1 必须进行离散化处理。这涉及到两个 方面的处理：空间物体坐标( 而y ) 的离散化和函数，( e y ) 的离散化。其中，前者 在图象处理领域一般称为采样，后者称为图象的量化，两者的结合称为图象的数 字化。经过这种离散化处理后的图象称为数字图象。当然，如何进行图象的采样 与量化处理是关系到最终数字图象与空间物体接近程度的两个关键因素。一般情 浙江大学硕士学位论文 况下，连续图象j ( x ，y 1 按照等间距进行采样，即分别在爿方向与y 方向上取个 点，并将结果排列为一个n n 的矩阵，每一个点对应于连续图象中的一个元素， 这称为象素。而矩阵中每一点的值对应光亮度的离散量。在数字图象形成过程中， 如何选取值和每个象素点的光亮度级别是影响最终图象质量高低的重要因素 之一。如果的取值太小，将导致数字图象相对于原始图象有比较大的失真； 而如果的取值过大，自然可以保证数字图象与原始图象十分接近，但这要耗 费大量的资源，给后续工作增添了难度。当然，光亮度的选取也存在同样的问题。 因此，在实际操作过程中，如何对与光亮度级别的进行合理的选取，需要根 据数字图象的要求以及计算机存储空问的大小而具体确定。 远程图象传输还涉及到图象数据量化后的传输问题，例如从卫星上拍摄的云 图或者水文图，其传回地球所能利用的信道资源十分有限，数据进入信道前，必 须进行合理的编码。图1 2 是图象数据的数字传输模型。 厂_ 、，_ - _ 、，i _ _ _ _ 、 队f - _ _ ? 、厂一、 ( 图象信源吲信源编码器 = 钵 ：通道编鸸器 二二二；) l 解码器吲接受j ， 、l 二_ _ _ _ _ _ 二- _ _ ， ，、矗n ，、 图1 - 2 图象数据的数字传输模型 信源选出取样图象并发送出图象函数序列，信源编码器进行量化编码，通道 编码器进行传输用的编码，通过传输通道后，由解码器重建图象。每个象素的平 均信息率，只要不超过通道容量( 能够正确传送的最大信息流量) 的范围，被传 输的信息就不会发生错误。 另外一方面，形成数字图象数据以后，如何将这些数据存储在计算机中，也 是一个关系到最终的图象文件是否便于计算读取与处理的一个重要问题。常采用 的存储方法有两种，一种是位映射方式，另一种是矢量处理方式。其中，位映射 方式是将图象的每一点数值存放在以字节为单位的矩阵中，例如图象为单色图 象，则一个字节中可以存放8 个象素点的数据；如果图象为1 6 色，则每个字节 就都可以存放两个象素点的数据：而若图象为2 5 6 色，则一个字节中可以存放一 个象素点的数据。位映射方式正是通过这种方式描述各种不同颜色模式的图象画 面，它比较适合于存储内容相对复杂的图象，是使用最频繁的一种图象数据存储 方式，例如：b m p 、g i f 、p c x 、t i f f 等都是采用位映射方式进行图象数据存储 的典型图象文件格式。而矢量处理方式只记录图象的轮廓部分，不是每个点的信 息，从而比较适合于工程设计图一类图象的存储。因为这种图象内容多半只是一 些几何形状，矢量存储方式表达起来特别方便。例如：一个圆形图案可以仅仅通 过记录圆心位置与圆半径信息、圆形边线以及圆内部颜色等信息而比较完整地进 浙江大学硕士学位论文 行描绘，从而节省大量的存储空间。因此，在描述规则几何图象画面时，其应用 范围很广泛。例如：w m f 文件格式已经成为基于w i n d o w s 开发的各种应用软件 中比较流行的一种图象文件格式；s w f ( f l a s h ) 文件格式则成为互联网上动 画制作和传播的主流。但是，如果所涉及的图案比较复杂、不规则，则需要依次 记录图象轮廓中每个点的描述信息，这时若利用矢量存储方式则比较麻烦，既要 计算每个轮廓点的坐标信息，又要详细描绘每个矢量的信息，从而导致所产生的 文件存储空间可能远远大于位映射图象所需要的存储空间。因此，在描述内容比 较繁杂，图案形状多变的画面时，一般不采用矢量存储方式。 参考文献 1 g a b a x e s ，“d i g i t a li m a g ep r o c e s s i n g ：p r i n c i p l e sa n da p p l i c a t i o n s ”，w i l e y , n e wy o r k ， 1 9 9 4 2 】 i e e es t d6 1 0 4 - 1 9 9 0 ，“i e e es t a n d a r dg l o s s a r yo fi m a g ep r o c e s s i n ga n dp a t t e m r e c o g n i t i o nt e r m i n o l o g y ”，i e e e ，n e w y o r k1 9 9 0 浙江大学硕士学位论文 第二章图象编码以及图象压缩 2 1 引言 在利用计算机进行数字图象处理所涉及到的各种操作中，应用频率最高的莫 过于图象数据的编码和解码操作。这是因为，一副图象所涉及到数据量往往非常 大，在利用计算机进行存储或者处理时，需要占用相当多的资源。可以这么认为， 没有编码技术的发展，大容量图象信息的存储与传输是难以实现的，多媒体等新 技术在实际应用中也会碰到困难。 所谓图象编码，指的是在满足一定条件的保真情况下，压缩表示原始图象的 数据，以便于存储和传输。相对应的，所谓图象解码，就是对压缩图象数据进行 解压缩，重现原始图象数据，以备计算机进行其他处理操作。 由于各种类型的图象数据编码过程不尽相同。因此，本章首先介绍影响图象 数字编码过程的重要图象特性一颜色，以及各种颜色图象的特性与处理方式，最 后介绍几种常用图象数据压缩方法的工作原理及其压缩效率分析。 2 2 常见的图象编码方式 2 2 1 单色图象编码 除最简单的图象以外，所有的图象都具有颜色，而单色图象则是带颜色图象 中最简单的格式，它一般由黑色区域和白色区域组成，其典型的图象格式为直线 图和图表。一旦给定图象的大小，这种格式的文件内容将十分紧凑。例如：在利 用位图格式表现的单色图象文件中，每个象素点都用单独一位进行描述：1 表示 该点为黑色，0 表示该点为白色。当然，也可以利用1 表示该点为白色，0 为黑 色。 浙江大学硕士学位论文 2 2 2 灰度图象编码 在一些单色图象，如照片中，经常需要使用灰度，才能比较准确地表达图象 的真实视觉效果，这种图象常被称为灰度图象。灰度图象是图象处理技术中涉及 范围比较广泛的一种图象表示方法。 描述灰度图象有几种比较典型的处理方案。第一种是利用单色文件格式描述 灰度图象，数据点仍然可以是黑或白。这种利用黑色或者某一种单色的点描述连 续的该色灰度的过程称为半色调处理或者抖动处理，该技术适用于绝大多数的打 印图象，因为打印图象时，通常一次只能使用一种颜色的墨水。但是，这种技术 获得灰度图象的方法仍然存在着无可避免的缺点。一方面，它使图象的编辑工作 相当困难，因为大多数图象处理程序无法区分带阴影的点和用于描述直线的点； 另一方面，使用半色调处理的图象在显示灰度时层次太明显，不具备连续性与光 滑性；而且，半色调处理技术降低了灰度图象的分辨率，因为它必须使用儿个象 素点，才能描述单独一个点的灰度值。综上所述，虽然在灰色图象中增加半色调 处理技术，可以描述灰度图象，但存在一定的缺陷，因此，一般很少采纳，绝大 多数的灰度图象描述方法都是采用另外一种方法：灰度级记录方法。 灰度级记录方法是将灰度图象记录为真正的灰度级，从而简化灰度图象的编 辑工作。任何一幅真正的灰度级图象都具有一定的位深。一个灰度位图一般根据 三个尺度进行描绘：列的象素值、行的象素值以及用于表示象素亮度的位数一图 象的深，即灰度级分辨率。例如：一个8 0 0 列、6 0 0 行和具有2 5 6 个灰度级分辨 率的图象，它的粗略大小为：8 0 0 * 6 0 0 * 8 比特，即4 8 0 0 0 0 字节。记录象素灰度 级的这些位的数值即代表颜色号，通常用0 表示黑色，用最高位( 8 位象素时为 2 5 5 ) 表示白色，而介于两者之间的值代表灰度的级别。 2 2 3 彩色图象编码 最简单的彩色表示形式是有限点色。当需要为图象中的某些图形元素设置某 种颜色时，可以从输出设备可使用的基本色彩列表中选择指定的颜色。当然，点 色所表示的彩色范围相对计算机可以描述的彩色范围丽言，永远是极小的一个集 合，其描述范围的扩展也仅仅是基于计算机彩色范围扩展的延续而己。如果需要 描述比较复杂的彩色图象，则可以采用不同的方法为颜色定义数值，从而比较准 浙江大学硕士学位论文 确地定位指定象素点的颜色，这些不同的颜色数值化方法通常也称为彩色模式。 在位图表示的图象格式中，最常用的三种彩色模式是r g b 模式、c m y k 模式与 h i s 模式。 r g b 模式也称为添加模式，主要用于发光设备，其中r g b 分别代表三种基 色：红色( r e d ) 、绿色( g r e e n ) 和蓝色( b l u e ) 。图象的颜色是按照如下的方式 建立：从黑色开始，逐渐增加每种基色的颜色值，从而产生指定的象素点颜色。 由于色彩的形成是增加不同基色的光亮度而形成的，因此这种方法也称为彩色添 加模式，它是计算机显示屏最适合的彩色混合方法。本书中所介绍的绝大多数图 象格式都采用这种颜色模式描述象素点的颜色值。 c m y k 是另外一种彩色描述，也称为削减模式，常用于刊印，感光材料等。 它所使用的四种基色分别为：青色( c y a n ) 、品红( m a g e n t a ) 、黄色( y e l l o w ) 和黑色( b l a c k ) ，其特定颜色的形成过程为：首先从白色开始，然后逐渐削减四 种基色的颜色值，因此，这种方法得名为削减模式。这种颜色形成方法类似与在 一张打印纸上使用彩色喷墨技术，所以这种模式主要用于将生成的图象输出到彩 色打印机中。 由于眼睛对亮度的变化，比对颜色的变化更加敏感，因此，近年又渐渐流行 另外一种称为h s i 的彩色定义方法，它充分考虑到人眼观察颜色的方式，而且可 以独立于上述两种方法单独使用。h s l 分别代表h u e 、s a t u r a t i o n 、i n t e n s i t y ，其 中h u e 是我们所认为的某一种颜色，s a t u r a t i o n 描述白色的多少，指相同颜色 ( h u e ) 不同的发自程度，而i n t e n s i t y 则用于描述亮度。它是一个更加直观的彩 色定义方法，现在很多图形应用软件中都采用了这种方法，甚至某些图形接收器 也可以直接接收h s i 数据，但是，h s i 数据最终仍然必须转换为r g b 或名c m y k 数据，计算机才能顺利地进行处理。例如：计算机显视器仍然需要红、绿、蓝的 输入信号，因此，一个可按收h s i 信号的接收器必须同时具备将h s i 数据翻译 为r g b 数据的能力。 由于彩色图象所占用的存储空间相当大，例如：一幅8 0 0 * 6 0 0 的图象拥有 4 8 0 ，0 0 0 个象素点，如果每个象素点都采用一个3 2 位的r g b 值进行存储，则 大约需要占用2 兆字节的磁盘空间，这对于需要处理人量图象的计算机而言是一 个相当沉重的负担。因此，为了降低存储空间的需求量，如何有效地组织彩色位 图图象数据是一个比较重要的问题。 浙江大学硕士学位论文 2 3 常见的图象压缩方式 2 3 1 图象压缩的概述 数字图象通常需要占用很大的存储空间，这就降低了计算机处理图象的效 率。因此为了减轻数字图象对存储中介的需求，同时提高计算机的工作效率，一 般数字图象在存储时都需要采用一定的压缩方法来处理庞大的数据集合。 数据压缩技术利用了数据固有的冗余性和不相干性，将一个大的数据集转换 成较小的数据集。有些压缩的算法是无损的，另一些则不是。无损压缩的算法删 除的仅仅是冗余的信息，因此可以在解压缩时精确的恢复原图象。有损压缩算法 把不相干的信息也删除了，因此只能对原图象进行大致的重构。而不是精确的还 原，所以，它能得到较高的压缩比。对于大部分图象来说，轻微地损失保真度而 换来压缩比的提高是经济的；而对有些不允许任何修改的图象而言，只能进行无 损压缩。另外，解压缩所用的时间也是必须考虑的，达到最高压缩比的算法往往 不是最快的，因此必须在具体应用时进行选择。 目前，流行的数据压缩方法众多，至于这些方法哪些更好或者哪些不好，还 很难评价，而且各个算法的压缩效率也是与具体的图象数据密切相关，无法下统 一的结论。 2 3 2 图象压缩的性能准则 令图象象素灰度级集合为 d l ，d 2 ，以 ，其对应的概率分别为p ( 吐) p ( d 2 ) ，p ( 办) t 图象熵定义为： u ( d ) = 一p ( 4 ) l o g ：p 似) ( 2 1 ) i = 1 单位为比特字符。图象熵表示图象灰度级集合的比特数均值，或者说描述 了图象信源的平均信息量。 如果令m = 2 ，当灰度级集合 吐，吐，以) 中西的出现概率相等( 均为2 “) 时，熵h ( d ) 最大，等于l 比特。只有d i 不等时，h ( d ) 才会小于l 。 借助熵的概念可以定义任何编码性能的准则：平均码长度r ( d ) 一一塑垩查兰堡主堂堡堡苎 r ( d ) = z p , p ( a , ) 式中，屈是灰度级吐所对应码字的长度。显然 编码效率常用下式表示： 叩= 器( ) ( 2 2 ) r ( d ) 的单位也是比特字符。 ( 2 3 ) 如果r ( a ) 和h ( d ) 相等，编码效果最佳：r ( a ) 接近u ( a ) ，编码效果比较 好；r ( a ) 远大于u ( a ) ，编码效果差。 压缩比是衡量数据压缩程度的指标之一，常用的定义式为： ，r p = 半1 0 0 ( 2 4 ) 式中，厶为源代码长度，厶为压缩后代码长度，只为压缩比。 压缩比的物理意义是被压缩掉的数据占源数据的百分比。 2 3 3 无损压缩技术 2 3 3 1r l e 压缩方法 r l e ( r u n l e n g t he n c o d i n g ) 压缩方法通常被称为行程长度编码，是最简单 的基于字典的压缩方法之一，现在这种方法被广泛地用于各种图象格式的数据压 缩处理。其工作原理址在给定数据中寻找连续重复的数值，然后用两个字节值取 代这些连续值。例如，假设存在一组数据a a a a a b b b b c c d d d d d a a ，利用行程长度编 码处理以后，可以表示为5 a 4 b 2 c 3 d 5 d 2 a 。因此，这种方法在处理包含大量重复信 息的数据时，可以得到很好的处理效果。当处理给定的图象数据中存在着一串连 续的重复值时，就可以在这个重复值前增加一个字节，表示指定值连续重复的次 数，然后利用这两个字节值代替这串连续重复出现的同一数据，从而取得压缩数 据存储空间的效果。这种方法对于包含大面积连续阴影和颜色的图象，例如由绘 图程序产生的图象，即可以获得很高的压缩比例。但是，如果图象中存在很多不 重复出现的数据值，利用r l e 方法处理这些数据时，只能将其原封不动地写入 压缩后的图象文件中，从而很难获得较好的压缩比例，而且可能导致压缩后的编 码字节数大于处理前的字节数。综上所述，r l e 压缩算法的压缩效率与图象数 据的分布情况密切相关。 浙江大学硕士学位论文 2 3 3 2h u f f m a n 压缩方法 霍夫曼编码( h u f f m a ne n c o d i n g ) 是一种常用的统计压缩编码，它是通过用 更有效替代数据方法进行工作。该方法首先是在由h u f f m a n 提出并用于文本文件 的压缩而建立的，但是随着其不断发展，现在已经繁衍出许多变体，可以顺利地 应用于图象数据的压缩。其基本思想是为每一个图象数据值赋予一个相应的二进 制值表示码，并将这种图象数据与二进制表示码的对应关系保存在一个转换表 中。译码程序在解码对应的图象文件之前，将首先读取对应的转换表内容，从而 辅助译码过程顺利进行。 h u f f m a n 编码中，二进制表示码的长度是根据对应数据在图象中出现的频率 高低而改变的，当指定图象数据出现的频率较高时，对应二进制表示码的长度则 较短；若对应图象数据出现的频率较低时，对应的二进制表示码则较长。同时， h u f f m a n 压缩原理是以一个编码代替一个字节值，这些h u f f m a n 编码的长度最少 有一位，最多达到八位，而h u f f m a n 压缩方法正是利用这些不足8 位的编码代替 原始数据中经常出现的一些字节值，从而降低图象数据的存储空间要求，收到较 好的压缩效果。 利用h u f f m a n 方法压缩原始图象数据时，必须读取图象数据两次。其中，第 一次是为了计算每个数据出现的频率，并利用较短的二进制码代替出现频率较高 的数据，以较长的二进制码代替出现频率较低的数据，而这些长度不等的编码都 被放在一个表格矩阵中。第二次读取原始数据时，再利用表格内的编码取代原始 数据存入图象文件中，这样即利用较少的存储空间取代原始数据所占用的大量存 储空间。 在第一次读取原始数据、计算各个数据出现的频率并利用二进制数表示的过 程中，首先计算出每个图象数据的出现频率，然后利用二叉树结构排列每个字节 值。排列过程可以描述为：首先将每个字节们都看作二叉树最底层的节点，然后 开始寻找出现频率最小的两个字节值，并将这两个值的频率相加，得到其父节点 的频率值：再寻找频率最低的两个节点，并建立父节点，真至最后排列出个根 节点，代表整个二叉树的最顶层，于是排在二叉树越顶层的字节值在原始图象数 据中出现的频率越高，而排在二叉树越底层的字节值在原始数据中出现的频率越 低。 h u f f m a n 编码的最高压缩效率可以达到8 ：1 ，但是在一般实施过程中，很难 达到这种压缩比例。若图象文件中存在某个拥有长行程的字节值时，使r l e 压 浙江大学硕士学位论文 缩算法可能更好。另外，对于类如h u f f m a n 编码的统计编码而言，更先进的统计 方法能够达到更高的压缩比，但是，这是以增大编码和解码时间为代价。 2 3 3 3 字典压缩方法 目前广泛采用的字典压缩算法包括两种类型：一种是在数据压缩过程中，寻 找当前等待进行压缩处理的数据串中是否在已处理过的数据串中出现过，如果确 实曾经出现过，则利用指向该已经进行处理数据中的指针代替当前等待进行压缩 的数据串。此时，字典是隐式的，它用曾经处理过的数据描述。这类字典压缩算 法都是基于a b r a h a m 与j a k o bz i v 于1 9 7 7 提出并发表的l z 7 7 算法，该算法提出 后，s t o r e r 与s z y m a n s k i 于1 9 8 2 年对其进行了改进，并提出相应的l z s s 算法， 成为现在实践中广泛使用的该类算法的基础。另外一种字典压缩算法是为输入数 据创建一个短语字典，如果在当前等待进行压缩的数据流中发现字典中已经存在 相应的短语，则利用该短语在字典中的相应索引值取代原始数据，这种类型的算 法基于l a m p e l 与z i v 在1 9 7 8 年提出并发表的l z 7 8 算法。后来该压缩算法由 s p e r r y 公司的研究员w e l c h 于1 9 8 4 年在硬件设计过程中，改进并用于高性能磁 盘控制器的设计。同时，由l a m p e l 与z i v 在实际工作中实现，l z w 编码也由此 而得名。l z w 压缩算法现在已经派生出几种流行的算法格式，不仅可以用于文 字数据的压缩，而且也可以成功地用于某些图象数据的压缩处理。 l z 7 7 压缩算法在每个压缩过程中，首先将当前等待进行压缩处理的数据存 放到一个超前数据缓冲区域中，而将压缩处理过的图象数据放置在一个长度为l 的窗口中，然后在窗口寻找是否存在与当前超前缓冲区域中相同的数据串，如果 存在，则输出该相同数据串的指针以及下一个压缩步骤中等待进行处理的第一个 未压缩数据，同时将超前缓冲区域与窗口都进行相应的移动；如果不存在相同数 据串，则直接输出当前数据。因此，如何确定窗口大小是关系到该算法压缩效率 的一个重要因素，如果该窗口过小，则可能根本无法起到数据压缩的目的，除非 当前等待进行压缩处理的数据中存在连续的相同数据；如果窗口过于大，则导致 算法执行所需要的缓冲区域增加，而且查找过程所需要的时间也相对延长。 l z w 压缩算法不需要在编码之前构造码表，其基本压缩原理是将每一个字 节的值都要与下一个字节的值配成一个字符对，并为每一个字符设置一个代码。 当同样的一个字符对再度出现时，就用代号代替这一字符对，然后再以这个代号 与下个字符配对。在配对过程中，必须创建三个表格，分别是：字首表、字符表 和代号表。所有字符对和代号，都分别存入这三个表格中。 浙江大学硕士学位论文 对于高度图案化的图象而言，l z w 压缩算法叫以达到1 0 ：1 的压缩比例， 但l z w 压缩算法最典型的压缩比例一般在1 ：1 到3 ：l 之间，它取决于是否可 以在原始图象中查找到图案模型，并利用比较短的代码取代它。如果原始图象数 据值中带有随机变化的“噪音图象”，则很难利用l z w 算法进行压缩。同时， 与r l e 压缩算法比较，l z w 压缩算法还有一个比较突出的特点：它不仅可以对 重复数据起到压缩作用，还可以对不重复数据进行压缩操作。例如，利用l z w 压缩算法的字符配对模式，如果在图象数据中查找到某些经常出现的不同值数据 串时，即可以利用一个代号取代这些数据，而不必如r l e 压缩算法相同，只能 将原始数据存放到最终的图象文件中，从而在压缩处理不同值数据串方面，l z w 压缩方法优于r l e 压缩算法。 2 3 3 4 算术压缩方法 算术压缩方法与h u f f m a n 压缩方法相似，都是利用比较短的代码取代图象数 据中出现比较频繁的数据，而利用比较长的代码取代图象数据中使用频率比较低 的数据，从而达到数据压缩的目的。但是，它同时又采用了l z w 压缩算法的思 想，不仅压缩数据值，而且压缩值序列，从而可以达到更加突出的压缩比例，尤 其适合于大多数数据由相同的重复序列组成的图象文件。但是算术压缩算法的实 现比较复杂，其基本思想是将每个不同的序列按照出现频率映像到0 和l 之间的 想像数字线区域内，该区域表示成可以改变精度的二进制小数，其中出现频率越 低的数据利用精度越高的小数进行表示。算术压缩算法中两个基本的要素为源数 据出现的频率以及其对应的编码区间。其中，源数据的出现频率决定该算法的压 缩效率，同时也决定编码过程中源数据对应的区间范围，而编码区间则决定算术 压缩算法最终的输出数据。 算术压缩算法可以大幅度地减小文件长度，甚至可以达到1 0 0 ：1 的压缩比 例，其压缩比例主要是与源文件的数据分布及其所采用标准模式的精度有关。 2 3 4 有损压缩技术 前面介绍的几种压缩算法都属于无损压缩，即在数据处理的过程中完全遵从 原始数据的构成。但是，当处理如商业电视图象信息等不必要求十分精确的图象 时，合理的方法是有损压缩，即在处理原始图象数据过程中，摒弃某些最终不需 要的数据。例如：对于视力感知不需要的菜些高度彩色分辨率等。 浙江大学硕士学位论文 目前，有损压缩算法应用比较广泛的领域是通信应用，以便于在单位时间内 通过有限容量的通信线传输更多的图象信息。一般情况下，静止图象的压缩采用 j p e g 格式，而动态图象的压缩则采用m p e g 格式。其中，j p e g 压缩算法在对 原始数据进行压缩编码以前，首先需要对原始数据进行一些预处理操作，典型的 处理包括：彩色模式变换及采样，离散余弦变换d c t 以及量化处理等，然后才 对加工后的图象数据实施某些压缩算法，例如，r l e 压缩算法以及h u f f m a n 压 缩算法等。在预处理过程中，彩色模式变换是将r g b 全彩色值变换成为y c b c r 图象数据；采样是只保留图象数据中的部分c b 和c r 值；离散余弦变换是利用 一个三角公式，将y c b c r 图象数据变换成为频率系数。由于这些频率系数都是 一些浮点数，因此在正式压缩编码之前，还必须对这些浮点数实施一次量化处理， 将其全部转变成为整数。 2 3 5 预测编码技术 预测编码就是根据过去时刻的样本序列，运用一种模型，预测当前的样本值。 预测编码通常不直接对信号编码，而是对预测误差编码。当预测比较准确， 误差较小时，即可达到压缩的目的。图2 - l 是其原理框图。 输入 图2 - 1 预测编码原理框图 该框图中，输入值为t 时刻灰度采样值x ( r ) ，预