图像压缩方法探索：LZW算法与商图像—余图像优秀毕业论文.pdf

分类号 u d c 密级 学号 彳房火季 硕士学位论文 论文题目 图像压缩方法探索 l z w 算法与商图像一余图像 论文作者 赵品勇 煮亲 教i 里嚣蓉 傅鹂教授 重庆大学 职称 作单位 傅咧教残 重厌大芋 申请学位级别 硕士 专业名称 运筹学与控制论 论文提交日期 2 0 0 2 年4 月2 3 日答辩日期 年月 日 学位授予单位 重庆大学授位日期 年月日 答辩委员会主席 论文评阅人 2 0 0 2 年4 月2 3 日 重庆大学硕士论文 摘要 图像压缩方法探索 l z w 算法与商图像一余图像 摘要 基于对l z w 压缩算法的认识 本文引入了 商图像 和 余图像 的概念 并对 商图像 和 余图像 在l z w 压缩方法下的压缩特征 进行了一系列的讨论 根据讨论的结果 本文相继提出了两种改进的 图像压缩方法 经过大量实验证明 这两种方法都可以在一定程度上 提高图像的压缩率 关键词 图像压缩l z w 压缩算法商图像余图像 重庆大学硕士论文摘要 e x p l o r i n gi m a g ec o m p r e s s i o n l z w a l g o r i t h ma n dq u o t i e n t r e m a i n d e r im a g e a b s t r a c t b ye x p l o r i n gt h el z wi m a g ec o m p r e s s i o na l g o r i t b j n w ed e v e l o p e dt h e c o n c e d t so f q u o t i e n ti m a g e a n d r e m a i n d e ri m a g e m a n yi n t e r e s t i n g p r o p e r t i e so f q u o t i e n ti m a g e a n d r e m a i n d e ri m a g e w e r er e v e a l e db yt h e i n v e s t i g a t i o no fl z wa n dt h e s et w os p e c i a li m a g e s b a s e do nt h er e s e a r c h w ep r e s e n tt w om o d i f i e di m a g ec o m p r e s s i o nm e t h o d s t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt h em o d i f i e dm e t h o d sa r eg o o di ni m p r o v i n gi m a g e c o m p r e s s i o nr a t i ot os o m ee x t e n t k e yw o r d s i m a g ec o m p r e s s i o n l z wc o m p r e s s i o nm e t h o d q u o t i e n t i m a g e r e m a i n d e ri m a g e 2 重庆大学硕士论文引言 1 1问题背景 第一章引言 随着社会的发展 科技的进步 人们对信息量的需求越来越大 而这种需求 不再仅限于单纯的语音 数据的需求 更多的是对图像信息的需求 这一方面是 因为人从外界获得的信息中9 0 以上是通过视觉获得的 另一方面是因为视频信号 中包含了比语音 数据等多得多的信息量 丰富多彩 生动逼真的画面带给人们 信息时代的享受远非电话 电报所能比拟 人们获得的图像多种多样 如卫星云图 遥感遥测 高清晰度电视 多媒体 技术等 其量化后得到的数字图像信息量特别大 存储时占用媒体多 传输时占 用信道容量大 传输时间长 对于大多数应用来说 这显然是不可接受的 为此 图像压缩技术应运而生 并得到长足的发展 近年来 图像压缩技术发展飞速 按其信息保持的程度 图像压缩可分为有 损压缩和无损压缩两大类 有损压缩允许一定程度的信息丢失 在满足应用的条 件下能够取得非常高的压缩率 因而在多媒体交互式系统 视频传输业务和家庭 娱乐等领域内得到了广泛的应用 但是相对而言 无损压缩因不允许信息丢失 压缩效率难以提高而发展较慢 可是在遥感图像 医用图像处理等众多的应用领 域内 对于高效的无损压缩方法和高保真度的压缩方法有着极为迫切的需要 1 2 图像无损压缩的发展现状 无损压缩方法已经从单纯的熵编码发展为基于一定的模型解相关后再进行熵 编码 而各种压缩算法的主要区别在于解相关所采用的模型不同 其中采用预测 模型的有差分编码调制d p c m d i f f e r e n t i a lp u l s ec o d em o d u l a t i o n 方法 1 及 一些改进的预测编码方法1 2 j 采用多分辨率模型的有分层内插法 h i e r a r c h i c a l i n t e r p o l a t i o n 3 i 差值金字塔法 d i f f e r e n c ep y r a m i d 4 1 等 而d c t 法 5 w a l s h h a d a m a r d 变换法 j 和小波分解法瑙j 州等是基于变换模型的 另外还有基于自 适应倍增回归模型的方法 1 0 1 1 而h u f f m a n 1 2 1 3 1 1 4 l z w 压缩方澍1 5 在无损压 缩方法中都各自占着很重要的一席之位 1 2 1h u f f m a n 压缩方法 h u f f m a n 压缩方法是一种常用的压缩方法 是1 9 5 2 年为文本文件的压缩建立 的 其基本原理就是用较短的代码代替频繁使用的数据 而用较长的代码代替很 少使用的数据 这样形成的代码都是二进制码 各不相同 且长度是可变的 通 常称之为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 编码方法简单有效 因而得到广泛的应 用 如众所周知的w i n z i p 就采用了h u f f m a n 编码方法 重庆大学硕士论文引言 1 2 2l z w 压缩方法 l z w 压缩方法比其它大多数的无损压缩技术都复杂 压缩效率也较高 其基本 原理是把每一个第一次出现的字符串用一个数值来编码 在还原程序中再将这个 数值还成原来的字符串 如用数值o x l 0 0 代替字符串 a b c c d d e e e 这样每当出 现该字符串时 都用0 x 1 0 0 代替 起到了压缩作用 至于o x 0 0 与字符串的对应 关系则是在压缩过程中动态生成的 而且这种对应关系是隐含在压缩数据中 随 着解压缩的进行 这张编码表会从压缩数据中逐步得到恢复 后面的压缩数据再 根据前面数据产生的对应关系产生更多的对应关系 直到压缩文件结束为止 l z w 是可逆的 所有信息全部保留 由于图像无损压缩方法不允许图像信息的失真 这使其研究工作进展缓慢 难以有较大的突破 但医学 军事领域的迫切需要 促使该方向的研究必须深入 下去 1 3 本文工作简介 本文着重探索l z w 方法用于图像压缩 主要工作有 1 讨论l z w 压缩方法的两个基本结论 2 引入 商图像 和 余图像 的概念 并讨论它们在l z w 压缩方法下的一 些特征 3 提出两种改进的图像压缩方法 半图压缩法 商余综合压缩法 并对之进 行充分的实验验证 重庆大学硕士论文数据压缩概要 第二章数据压缩概要 2 1 数据压缩的内容 意义和用途 2 1 1 什么是数据压缩 数据压缩 d a t ac o m p r e s s i o n 就是以最少的数码表示信源所发的信号 减少 容纳给定消息集合或数据采样集合的信号空间 2 1 2 数据压缩的必要性 1 庞大的数据量 采用数字化技术 或系统 具有许多优越性 是时代发展的趋势 但这也使 得数据量大增 而庞大的数据量给数据传输和数据存储都带来了极大的挑战 首先从数据传输角度看 表2 1 列举了一些常见的数字化音 视频的采样频率工 如果对每个取样的 幅度值用r 位二进制编码 叫做r 比特 其中比特 b i t 的涵义为二进制数字 即b i n a r y d i g i t 表示 就得到数字信号的传输速率或比特率 即 i r b w s 或b s 2 1 这就是该信号在通信线路上每秒钟应传送的比特数 或者保存一秒钟信号样值所 许占用的存储容量 表2 1 数字音 像格式 数字音频格式取样率 k h z 带宽 k h z 频带 h z 电话 8 3 22 0 0 3 4 0 0 会议电视 1 675 0 7 0 0 0 紧凑盘 c d 4 4 1 2 0 2 0 2 0 0 0 0 数字音带 d a t 4 82 02 0 2 0 0 0 0 数字电视格式时间 空间分辨率取样率 通用中间格式 c i v 3 5 2 2 8 8 3 03 m h z 7 2 0 4 8 0 3 0 1 3 5 m h z 国际无线电咨询委员会 c c i r 7 2 0 x 5 7 6 2 5 1 3 5 m h z 高清晰度电视亮度信号一例 1 2 8 0 7 2 0 6 06 0 m h z 数字电话的取样率最低 按每一取样用8 b i t 压扩量化 通常也需要 8 8 6 4 k b s 的数码率 亦写作6 4 k b p s 一路p a l 制彩色数字电视 若用3 倍副载频采样 每像素 p i x e l 常简写为p e l 8 b i t 编码 数码率为 4 4 3 3 8 1 0 6 3 m b s 若实时传送 需占用上述数字话路1 6 6 0 个 即使黑 白电视也要占近9 0 0 个数字话路 重庆大学硕士论文数据压缩概要 再从数据存储角度看 一幅5 1 2 5 1 2 像素 8 b i t p e l 的黑白图象占2 5 6 k b 一幅5 1 2 x5 1 2 像素 每分 量8 b i t 的彩色图象则占3 2 5 6 7 6 8 k b 一幅2 2 9 1 2 1 9 0 x8 b i t 的气象卫星红外云图 占4 9 0 m b 而一颗卫星每半 j 时即可发回一次全波段数据 5 个波段 每天的数 据量高达1 2 g b 1 2 数据压缩的益处 信息时代的特征之一是 信息爆炸 随着信息时代的不断发展 数据压缩 的作用及其社会效益 经济效益将越来越明显 1 较快地传输各种信源 降低信道占有费用 一时间域的压缩 2 在现有通信干线上开通并行业务一频率域的压缩 3 降低发射机功率一能量域的压缩 4 紧缩数据存储容量 降低存储费用 一空间域的压缩 3 一些数据压缩的事例 从目前来看 数据压缩的应用领域颇为广泛 诸如通信 语音和图象处理 模式识别 信息恢复 信息存储和保密学等等 美国国家海洋气象局 n o a a 从卫星上接收到的地面图象 从指令数据录取 站向数据处理和分析中心传输时 用了一条3 3 0 k m 的微波信道 由于要接收和传 输高分辨率的气象图片 因此南3 h j h 大学为其研制了一整套压缩算法供其使用 1 9 7 3 年后正式投入运行 其方法是预测编码在加上统计编码的复合技术 压缩比 是2 1 硬件是用计算机来实现 据报道 使用效果良好 在美国著名的阿波罗宇航计划中 从载人空间飞行网络站到哥达特空间飞行 中心之间 有一条传输阿波罗数字遥测数据的线路 其容量为2x2 4 0 0 b i t s 但实 际上从飞船向地面传来的遥测数据是5 1 2 k b i t s 因此越翰霍普金斯大学为其研制 了一套数据压缩算法 主要也是预测编码与统计编码的复合运用 在最新的航天飞机实施计划中 语音的传输已采用某种自适应的预测编码技 术 把一路数字语音从6 4 k b i t s 压缩到3 2 或2 4 k b i t s 并准备在后续型号中 对电 视图象采用二维预测编码技术 可将6 4 m b i t s 的码率压缩到1 3 1 m b i t s 对上行传 真图片 则采用统计编码 压缩比可达5 1 在大型计算中心 常有浩大的数据库存在 为缓减这种日益增长的存储压力 加拿大贝尔公司就运用统计编码方法进行数据压缩 其压缩比为3 0 7 2 1 3 数据压缩技术的发展史 由于数据压缩在时域 频域 能量及空域几方面都可能带来好处 不一定同 时 因此 数据压缩技术几乎与通信系统的设计同时发展 1 8 4 3 年出现的莫尔斯 m o r s e 电报是最原始的变长码数据压缩实例 1 9 3 9 年美国贝尔实验室 b e l ll a b 的答德利 h d u d l e y 发明了通道声码器 v o c o d e r 重庆大学硕士论文数据压缩概要 即v o i c e c o d e r 成为第一个语音压缩系统 把语音谱划分为有限的频带 各带 宽内传输其能量电平 压缩比大于1 0 0 倍 1 9 3 8 年里夫斯 r e e v e s 1 9 4 6 年德劳雷恩 e m d e l o r a i n 以及1 9 5 2 年贝尔 公司的卡特勒 c c c u t l e r 分别取得了脉冲编码调制 p u l s e c o d e m o d u l a t i o n 简 写为p c m 增量调制 d e l t a m o d u l a t i o n 简写为 m 和差分脉冲调制 d i f f e r e n t i a l p c m 简写为d p c m 的专利 三个在数字信息传输中非常有名的方法 1 9 5 2 年霍夫曼 d a h u f f r n a n 给出了最优变长码的构造方法 同年贝尔实验 室的奥利弗 b m o l i v e r 等人开始了先行预测编码理论研究 1 9 6 0 年马克斯 j m a x 发明了确知分布信号最佳标量量化算法 1 9 6 3 年黄 j j y h u a n g 等人 又提出了对相关随机变量先正交变换再分组量化的方法 但是 有关数据压缩的理论研究 还是在仙侬 c e s h a n n o n 信息论基础上 开始的 1 9 4 8 年仙依的经典论文 通信的数学原理 中首次提到信息率一失真函 数概念 1 9 5 9 年他又进一步确立了率失真理论 从而奠定了信源编码的理论基础 随后又由伯节 t b e r g e r 1 9 7 1 等人进行了深入研究 对各种语言 音频 图片和视频信号的实用压缩技术研究 更多地得益于数 字信号处理 d s p 时间序列分析 参数估计 离散变换 模式识别 自适应技 术以及感知生理一心理学的理论进展 由于对人的发声机理 听觉特性以及对语 言信号本身的自回归模型研究较早 以及与视频信号相比 语音只有一维且频率 低易于实时处理 因此语音编码比图象编码更成熟 除音质要求较高者仍采用波 形编码外 低码率传输普遍采用了基于分析一合成思想的各种声码器 图象编码直接借鉴了语音压缩的许多成熟技术 1 9 6 6 年奥尼尔 j b o n e a l 对比分析了d p c m 和p c m 并提出了用于电视的实验数据 1 9 6 9 年进行了线性预 测编码的实际实验 此后 出现了各种改进的帧内和帧间线性预测编码方法和自 适应预测编码方法 1 9 7 5 年以来 有人通过测量电视图象只能感运动物体的位移 来进行帧间预测 结果使数码率进一步降低 这一方法不仅用于电视传输 提高 图象质量 也可用于可视电话和会议电视 变换编码是1 9 6 8 年安德鲁斯 l c a n d r e w s 等人提出的 他们采用的是二 维离散傅立叶变换 2 d d f t 此后 相继出现了沃尔什一哈达玛 w a l s h h a d a m a r d 变换 斜 变换 k l 变换 离散余弦变换 d c t 等 变换编码是从 频域 变换域 的角度减小图象信号的相关性 但实现起来要比预测法复杂得多 1 9 7 3 年哈比 a h a b i b i 提出了兼有二者优点的变换一d p c m 混合编码 为在世界范围内促进数据压缩技术的应用 1 9 8 0 年以来 国际标准化组织 i s o 国际电工委员会 i e c 和国际电信联盟 i t u 简称国际电联 下属的 国际电报电话咨询委员会 c c i t t 陆续完成了各种数据压缩与新的标准和建议 这些标准的建立不仅极大地推进了数据压缩技术的实用化 产业化 同时也将在 一定意义上刺激信源编码理论研究的进一步拓展 2 1 4 数据压缩技术的应用前景 多媒体 i s d n 与现代化传播技术所具有的广阔应用领域 实际上也正是数据 重庆大学硕士论文数据压缩概耍 压缩技术的用武之地与发展前景 1 多媒体通信系统 这是多媒体与i s d n 相结合的产物 图2 1 数据压缩是其中的关键技术之一 这种系统可提供可视通信 远程监视 桌面系统 原端教学 集中图像管理和声 像资料连网传输管理等功能 多显示器 媒扬声器 体 打印机 电传真机 脑绘图仪 图2 1多媒体技术在通信系统中的应用 2 多媒体教育 训练及研究系统 采用声 文 图 形 数一体化效果 使复杂内容简单直观 一目了然 受 训者如同身临其境 在各行各业都能发挥其威力 具体应用于 教学 职业培训 员工教育 c a i 外语练习及新一代的电化教学等 训练 驾驶 飞行 军事 操作 核武器模拟 战争模拟 体育训练等 科研 将一些抽象 枯燥的数据用三维动态图形及声音表示出来 使科学 计算可视化 形象化及生动具体化 3 多媒体演示与咨询服务系统 利用以多媒体计算机为核心的三维特技编辑与字幕编辑可以制作动画 电视 图文 c d 音响等节目并任意重放 具体应用包括 商品和服务展示 无人解说 顾客随意查阅 例如各类 触摸屏 产品 可广泛用于商场 酒家 宾馆 古玩店 博物馆 物资交流中心等 v 工厂 公司 机关 学校的简报 多姿多彩 可随时补充修改 突破了幻 灯片 投影片的使用局限 咨询服务 服务内容包括官方信息发布 商业咨询提供 生活资料查询 消遣活动指引 旅游购物指南 大楼方向导引等 娱乐 游戏 由简单的动画效果向图声并茂 实体模拟方向发展 发型 设计 服装配色等 4 电子出版物 目前一张c d r o m 光盘片通常有6 5 0 m b 或7 2 0 m b 容量 可作为一个廉价的 信息载体用于各种声 文 图一体化的多媒体电子出版物 形成一种崭新的 无 纸 大众传播手段 c d r o m 不但是多媒体的技术支撑 同时也提供了数据压缩 技术大显身手的场所 成倍地压缩显然将成倍地提供光盘的存储信息 重庆大学硕士论文 数据压缩概要 5 办公自动化 o a 与分布式多媒体系统 利用多媒体图 文编辑功能 制作各种精美醒目的文件和报表 利用多媒体 通信网络功能 传递统计数据 下达电子文件 直拨可视电话和召开计算机化的 电子会议 利用多媒体信息存储与数据库功能 原貌保存管理各类文件 资料 图片和音像资料 节省大量的存储费用 纸张 文件柜 资料室 保管员等 如 果将这些信息存入各类手提式电脑 笔记本电脑 掌上型电脑 还可用作随身携 带的 电子秘书 电脑推销员 进一步与通信线路接口 由可构成便携式传真 机 可视大哥大 等产品 6 家用m p c 家用m p c 将可提供声像一体的交互式教育功能 游戏功能 电视和音响功能 电子琴功能 作曲功能 卡拉o k 功能和用于家庭事务管理及家用电器控制 特 别是可以通过电话线等联网 得到各种公共服务一天气预报 股市行情 商品价 格 交通状况 报纸新闻 旅游娱乐 体育赛事 职业教育 图书资料等 7 利用多媒体技术制造i t v 和h d t v 现在有人提出用多媒体技术制造h d t v 的应用前景 1 7 1 8 利用多媒体技术支 持任意变化的分辨率和任意尺寸窗口的输出 同时为h d t v 赋予视频特技和交互 功能 使h d t v 更方便地用于教育和娱乐 2 1 5 数据压缩技术的分类 数据压缩的分类方法繁多 有人统计 仔细分来可达2 0 4 0 种 到目前尚未 统一 而多数学者认同的比较一致的分类方法 是将数据压缩分为无损压缩和有 损压缩两大类 无损压缩 无损压缩也叫无失真压缩或者无噪声编码 n o i s e l e s sc o d i n g 仙侬在创立信 息论时 提出把数据看作是信息和冗余度的组合 1 9 无损压缩的工作机理 是去 除 至少是减少 那些可能是后来插入数据中的冗余度 因而始终是一个可逆过 程 无损压缩的一个简单例子 是去除重复的数据 如果发送的数据在一段长时 间内不变 则许多连续采样值将是重复的 避免这种情况出现的显而易见的方法 是计算两个变化采样值之间重复采样值的数目 然后将变化的采样值与该重复树 木一起发送 这其实就是行程编码方法的工作原理 有损压缩 有损压缩就是失真 l o s s y 编码 信息论中叫熵压缩 e n t r o p yc o m p r e s s i o n 有损压缩的一个简单例子 是在监测采样值时设置某个域值 只有当采样值 超过指定的域值时 才传送数据 如果这个事件不常出现 就会实现信号空间的 较大压缩 但实际的原始采样值就不可能精确恢复丢失了信息 重庆大学硕士论文数据压缩概要 2 2 数据压缩与信源编码 2 2 1 数据压缩与信息论 在1 9 4 8 年香农 s h a n n o n 所创立的信息论 对数据压缩这门学科来说 有 着重要的指导意义 它一方面给出了数据压缩的理论极限 而另一方面又指明了 数据压缩的技术途径 香农信息论认为信源所含有的平均信息量 或称为熵 就是进行无损压缩的 理论极限 举例来说 如将由2 6 个字母和一个间隔符号所组成的英文文件看成是 某个信源的话 那么该信源的熵可算出为 h x 1 2 b i t 字符 由于计算机内的文件是不允许有任何失真的 所以对这种信源进行压缩的平均字 长 就不能低于h x 换句话说 低于此极限h x 的无失真编码方法是找不到的 而只要不低于此极限 那就总能找到某中适宜的编码方法 使 任意地逼近h x 就压缩途径而言 香农信息论认为信源中含有的冗余度一方面来自于信源本 身的相关性 另一方面来自于信源概率分布的不均匀性 于是只要找到去除信源 相关性 或改变信源概率分布不均匀性的方法和手段 就可以实现有效的压缩 例如 目前计算机中英文文件的编码 普遍采用了a s c i i 码 每字符占用7 个比 特 这就是该信源含有较多自然冗余度 其原因就在于文件中字符之间 通常具 有较大的关联性 而并不是相互独立的 同时 2 6 个字母出现的机会也远非均等 一般来说 字母 e 出现的概率最大 而 q 的概率最小 2 2 2 信源编码模型 香农信息论的两大分支是信源编码 s o u r c ec o d i n g 和信道编码 c h a n n e l c o d i n g 信源编码是面向信源的一种信息处理手段 而信道编码是面向信道的另 一种处理手段 其中信源编码模型 示于图2 2 中 图2 2 信源编码模型 通常把信源看成是一个随机数据发生器 而整个数字传输系统的功能 就是 有效而又可靠地将此随机数据传送到用户那里 因而对信源编码器来说 它的任 务首先就是将信源的输出 变换成相应的数字序列 假如信源本身能产生数字输 出的话 那么信源编码器就一一对应地将其变换成另一种适宜的数字序列 而信 源译码器就一一地反变换成原始的数字数据 但是 客观世界的许多物理量 往往是渐变的和连续的 所以 它的输出就 不再是数字序列 而是在时间上和幅度上都为连续变化的模拟信 或者说 它的 重庆大学硕士论文 数据压缩概要 取值是一个不可数的无限集合 因此这时的信源编码器就做不到一一对应的变换 而只能在容忍一定失真的条件下 变换成数字序列 当然信源译码器也只能做到 近似的反变换 在这种情况下 信源编码器要完成模一数变换功能 而信源译码 器则可能要完成数一模变换功能 不过 信源编码器有着更为重要的主题内容 就是数据压缩 这意味着如何 能以最少的比特数 来表述所给定的信源 并在信源译码器那里 能准确地或尽 可能准确地再现出信源数据 因此 信源编码作为信息论的一个分支来讲 其核 心内容仍是个数据压缩问题 况且 从广义上讲 模数转换实质上也是个数据压 缩问题 所以 可以把信源编码和数据压缩这两个概念等同起来 重庆大学硕士论文 图像压缩的基本途径 第三章图像压缩的基本途径 图像压缩属于数据压缩的范畴 而数据压缩的概念可以等同于信源编码一信 息论的两大分支之一 根据前一章的知识 信息论在理论上指明了数据压缩的两 个基本途径 1 去除信源相关性 2 改变信源概率分布不均匀性 因此 可以通过讨论信源 比如离散无记忆信源的熵来寻求图像压缩基本途 径的理论支持 3 1离散无记 乙信源的熵蚴 1 3 1 9 3 1 1 离散无记忆信源定义 定义3 一l 若信源具备下述特性 1 它的输出是一随机变量x 而此变量是从某个有限字母集合 a p l a 2 口 e p 选取 2 某个字符a 出现的概率p a j p 也已确定 3 信源送出的随机变量 与前一对刻和后一时刻的输出互相独立 则称此信源为离散无记忆信源 d i s c r e t el d e m o r y l e s ss o u r c e d m s 本章所有 的讨论 都将限于这种信源而不再附加说明 3 1 2 信息 在人们日常生活中 如果收到一封电报 接到一个电话 或收到一组数据 从信息论的观点来看 这些都只能被叫做收到 消息 而不能说收到 信息 信息寓于消息中 同样一个消息会带有不相等的信息量 因为一个消息为消息接 收者解除的不肯定性会因时因地而异 所以信息的度量可以定义为 定义3 2 用户在收到消息之前 是处于某中不肯定状态之中 而在收到信息 之后 就解除或部分解除了此不肯定性 从而获得了信息 因此解除不肯定性的 多少 就可作为信息的度量 3 1 3 不肯定性的数学描述 用什么数学模型来描述不肯定性昵 香农信息论则是应用了 概率 这一概 念 也就是说 事件出现的概率小 则相当于不肯定性多 反之则小 如在上例 中 可能出现的时间是二个 即成功与失败 如设成功事件为a 其概率为 p a p 失败事件为口 其概率为p a p 则可记不肯定性是p 的函数 重庆大学硕士论文 图像压缩的基本途径 为 王 p 但问题还在于要找到一个确切的函数关系 为了科学地定义不肯定性函数 王 a 必须考虑到如下几个基本要求 1 当事件为肯定事件时 即p 1 则要有 甲 p 0 3 1 此时 即毫无肯定性可言 2 当p 愈小时 不肯定性甲 p 愈大 反之则愈小 3 如有二个事件集同时存在 则有联合不肯定性掣 只 研p d b i 存在 其中p a b 是二个事件的联合概率 但当二个事件集互相独立时 能有 王 尸 口 b 壬r p d 甲 尸 钆 3 2 根据这三条最低要求 人们终于找到了不肯定性的适宜表达式 定义3 8 事件口j 的不肯定性可定义为 甲 p 一l o g p f 3 3 式中的负号是必须的 由于p 1 敌 这样就保证不肯定性总是非负值 显见 式 3 3 满足了上述 1 2 两条基本要求 对于 3 来说 由于 二个时间集互相独立 就意味着p a b p a j p 以 由于取对数的关系 相乘 就变成相加 因而也就满足式 8 2 3 1 4 平均信息量 熵 对一个信源而言 它既可能送出事件口1 也可能送出别的事件n i 因此从统 计平均观点来看 它所含有的信息量就是平均信息量的概念 借用热力学的名词 把它叫做熵 e n t r o p y 因此 若信源的概率模型写为 x 2 僻嚣p i 嘏 3 4 i p j p 2 j 其中 a a 1 a 2 a 3 5 为信源的字符集 则该信源熵可定义为 定义3 4 信源的熵就是各事件不肯定性的数学期望 即 日 工 一 p l o g p 3 6 其中 p 1 p 0 重庆大学硕士论文图像压缩的基本途径 顺便指出 熵还有另两种习惯表示法 当强调各事件的概率分布 并构成向量 p p l p p 时 则熵可写为 p 峨 p p 一 p 一 p l o g p k l 另外若n 2 2 时 则p l p p 2 1 一p 故有 h p 一p l o g p 一 1 一p l o g 1 一p 这里强调熵是p 的函数 3 7 3 8 可以证明 熵h x 就是离散无记忆信源进行无失真编码时的基本极限 举例 来说 若信源有四个字符 z j4 l 4 2巳 t l 1 1 21 41 81 8 l 根据式 3 6 可求得其熵h x 1 7 5 b i t 字符 若采用某种二进制编码 如 q 2a 3a 4 o1 01 1 01 1 1 则其平均长度 1 7 5 比特 字符 正好达到了该基本极限 而在目前 还找不到 平均字长比其更短的任意的无失真编码方法 这就充分证实此基本极限的严格性 3 2 熵与概率分布的依从关系一图像压缩的基本途径之一 根据熵的定义 可以引申出若干条性质 这些性质可归为两大类 其 是j 劳 与凝事分j 声韵关系 其二是角t 号事移相关拦的关系 根据这些关系 就可分别找 到具体的有关图像压缩的两条途径 在这一节里 主要阐述熵与概率分布的关系 3 2 1 熵的渐化性 1 3 定理2 2 设有熵函数h p 1 p 2 合并为一个事件时 且 p p 0 一 p 若其中有两个事件 设为a 和 2 则新的信源熵为 h 1 p 1 p 2 p 3 p h p l p 2 一 p 一 p p 2 h 2 兰l 一 兰l 3 9 p t p 2p 1 十p 2 证明 先引入函数 地 r 苫g 一 篡3 显然有 l x y x y l o g x y 一x y l o g x x y l o g y y l 功 x l y 3 1 1 1 4 重庆大学硕士论文图像压缩的基本途径 于是再引入新的参量 p p l p 2 口 旦 p 十p 2 则p p 1 一g p p q 故运用式 3 1 1 就能得到 日 a p 2 p 胃 p 1 一g p q p 3 p l p 1 一g 上 p q e o j 3 f z p p 皿 1 一茸 三 g i 3 h 一1 p i p 2 p 3 p p 1 p 2 h 2 l l 定理表明 由于p 1 p 2 0 故有 a p 2 p 3 p 0 则有 莩p s 詈 萃p ic 詈一 2 莩 一莩p 一 即得式 3 1 2 且当p q 时 等号成立 重庆大学硕士论文图像压缩的基本途径 根据此不等式 就可以证明熵的最大性 也就是在何种概率分布下 熵才取 得最大值 定理3 4 熵有下式成立 巩 p p p s 日 三 土 一 三 1 g n 3 i 3 甩开刀 式中 l o g 即为最大熵 1 根据式 3 1 2 并令q 1 n 即可 d b 证明此定理 显见 此性质说明了当詹翟歹俞e 中各事释是等概率分布时 萁平均信繇量譬 为霞尤 如以 2 为例 则h p 变化的芏d 4 规律可见于图3 一l 中 仅当p l l 2n7 时 h p 1b i t 非此情形 则h p 就 减小 当p 0 或p 1 时 h p 0 即 u 成为肯定事件集合 从物理意义上来说 图3 1n 2 的熵函数 通常常数或存储的一个二元字符 1 或0 其所含的信息量总低于i b i t 只有当 字符i 或0 的概率p 1 p o 1 2 时 才 含有习惯上所叫的l b i t 的信息量 因而 此最大值与熵之间的差值l o g n h x 就是信源所含有的冗余度 r e d u n d a n c y 3 2 3 图像压缩基本途径之一 由上可知 信源只要不是等概率分布 就存在着数据压缩的可能性 而其基 本途径就是改变原有的概率分布 使之逼近或达到等概率分布 依据上述四个定 理 便有如下的结论 结论3 一l离散无记忆信源的冗余度寓于概率的非等分布之中 因此作为图像 压缩的基本途径之一 就是改变图像信源的概率分布 以期尽可能达到等概率分 布的目的 这一结论所体现的基本思想 在统计编码方法 如h u f f m a n 编码方法中可以得 到体现 3 3 熵与信源相关性的依从关系一图像压缩的基本途径之二 众所周知 客观世界中的事物往往不是孤立而单独存在的 它与周围发生的 事物之间 通常都有一定的依从关系 因此仅仅研究单个信源的信息量 己不足 以充分揭示出信息领域中更有意义的本质来 因为多个信源的信息含义 已不再 是单个信源基础上的简单重复或迭加 由于多个信源之问存在着关联 就使得总 体上的信息概念 出现质的飞跃 从而导出了数据压缩的第二条基本途径 我们 将从信息论中有关熵的另一些重要性质里 逐步引申出这些重要的结论 3 3 1 熵的强加法性 如果设想有同一型号的二台仪器联合 同时 参加实验 除了考虑单独一台 重庆大学硕士论文图像压缩的基本途径 仪器的成败事件以外 还要在总体上考虑它们的各种可能性 因此若分别定义二 个信源概率模型为 x 2 卜 2 p 2q 2 l ajl g t j 从而形成一个联合事件集 其概率模型为 z y 4 tn 6 1 口 n 如4 n 6 z 口 n 6 1 lr 2 2 2 j 其中 n 表示集合 交 的概念 而勺表示联合概念 一般地 若有两个信源模型 z 口1 吒 l 3 1 4 i p ip 2 p j y p6 z 6 m l 31 5 q i g 2 q mj 则其联合概率模型为 m c i c 1 2 cotl 协 2 0j 其中 f 口 n b j 勺 p j 弓 q j 局 巳 p b a 为条件概率a 于是可得到如下两 个定义 审义3 5 联合事件集的熵为 h x y e 一l o g s j 一 勺l 0 9 5 s 3 1 7 i lj l 称之为联合熵 j o i n te n t r o p y 或叫共熵 它表述了两个事件集联合发生时所 能得到总的平均信息量 定义2 6 在给定x 的条件下 y 集合所具有的熵 即条件熵为 h y x e 卜l o g p j i 一 o1 0 9 3 1 8 i 1j l i 同理 在给定y 的条件下 一集合所具有的条件熵为 h x o 一 ol o g 孚 3 1 9 j 2 lj l1 由上述两个定义可知 由于五与y 两个集合之间存在着一定的关联 所以在解除z 重鏖查堂堡主丝塞 望堡里塑堕堕翌 堑丝 不肯定性的同时 也解除了一部分y 的不肯定性 但此时y 还残剩有部分不肯定性 即为h y x 的含义 另外要注意 在对一l o g p j j 进行统计平均时 由于要对口 和 b 进行两次 所以用的是联合概率勺a 不难想到 在联合熵 y 和条件熵日 y x 之间 必定存在某种数学关系 可从下述定理得到 定理3 5 联合熵有下式成立 h x y h x h y x h y h x y 3 2 0 证明将式 3 1 8 展开为 h y x 一 ol o g r 口 ol o g p j l ii 1 5 h x y p i l o g p 易 i 1j l 由于 易 l 故得式 3 2 0 i 通过本定理可以看到 1 从概率角度来看 0 p p 是相乘的关系 但映射到熵的概念里来 却变成了相加关系 2 由于两个集合之间有关联存在 因此总熵就等于一个集合所具有的熵 再加上另一集合所剩余的熵 3 随着两个集合间相关性的增加 则此剩余的熵 即条件熵就会减少 这 一原理可用著名的文氏 v e n n 图来解释 如图3 5 所示那样 两个圆圈分别表 示何 z 和日 r 而每个圆内不重叠部分则表示条件熵 显然 二圆重合时 条 件熵为零 联合熵就等于单个信源的熵 这表明两个集合完全相关a r 一h x y 1 x h y 图3 5 文氏图 4 上述定理 表明了熵的相加性质 而且由于不附加条件 适用性比较广 泛 故称其为强加法性 重壅查兰婴主堡苎 里堡墨箜堕茎奎堡垒 3 3 2 条件熵的极限性 从文氏图中可见 当两个圆相互离开时 条件熵就增大 也就是由于相关性 的减弱而使得剩余不肯定性随之增大 但此条件熵的增大有无极限 极限在哪 里 可由下述定理给出 定理2 6 条件熵有下式成立 h y x 日 f h x y h x 3 2 1 证明若将式 3 1 0 中引出的函数 z 对x 进行二次微分 即得 砉m 三 1 3 这样 a 1 3 的颜色集合中每个元素的平均重复率分别为s m 和 s n 因此 b 通常就比a 具有更强的图像模式 所以 经l z w 压缩后 b 可以比a 取得更高的压缩率 2 从熵的渐化性角度来看 把图像的每个颜色看作是一个事件 则颜色集合中每减少一个元素就可以看 作此颜色所代表的事件与另外某个颜色所代表的事件合并成了一个事件 因此图 像信源的熵通常会因之减小 而图像的物理存储空间又保持不变 所以图像的冗 余度便增加了 示例 一幅2 5 6 色位图d o g b m p 颜色集合为t 0 2 5 5 将其每一个像素值除以x 后保留商 且记所形成的相应图像为d o g x b m p 则d o g x b m p 的物理存储空间与 d o g b m p 大小相等 而其颜色集合应该为 0 2 5 5 的一个子集 下面的表格展示了 x 分别取2 4 8 1 6 3 2 6 4 2 8 时对应d o g x b m p 的压缩情况 原始图像d o g b m p 大小 4 9 7 k 压缩后代码长度 2 5 4 k x 的取值图像名称压缩代码长度压缩率 x 2 d 0 9 2 b m p 2 1 8 k0 5 6 x 4 d 0 9 4 b m p 1 8 0 k0 6 4 x 8 d 0 9 8 b m p 1 4 1 k 0 7 2 x 1 6 d o g l 6 b m p 1 1 3 ko 7 7 x 3 2 d 0 9 3 2 b m p 8 5 k0 8 3 x 6 4 d 0 9 6 4 b m p 5 8 k 0 8 8 x 1 2 8 d 0 9 2 5 6 b m p 2 3 k0 9 5 表4 4 重庆大学硕士论文 l z w 算法与商图像 佘图像 4 2 商图像 与 余图像 对于一幅2 5 6 色图像 若取出每一个像素值除以数x 后的商 则可以形成 卜与原图像同等大小的图像 在这里我们称之为关于数x 商图像 同样地 若取出每一个像素值除以数x 后的余 也可以形成一个与原图像同 等大小的图像 我们称之为关于数x 余图像 注 从理论上讲 x 可以是1 到2 5 6 之间的任一个值 但在本文中 x 只取l 到2 5 6 之间可以整除2 5 6 的值 即x x f m o d 2 5 6 x 0 结合上面关于l z w 压缩的两个基本结论 可以进一步得到关于 商图像 和 余图像 的一些结论 1 对于一幅图像而言 其本身与其 商图像 余图像 三者大小相等 分析 根据 商图像 和 余图像 的定义可知 它们与原始图像的像素之间是一 一对应关系 又2 5 6 色位图中每个像素值都占用一个字节的长度 所以 商图像 余图像 及原始图像三者大小相等 2 无论是图像的 商图像 还是图像的 余图像 其图像模式都不会比原 始图像的图像模式弱 从数学知识可以知道 对一系列数据求商 求余的过程实际上就是在对这些 数据进行光滑的过程 所以 商图像 和 余图像 的光滑度 即图像模式不会 弱于原始图像 若设x 4 则 商图像 的光滑度来源 原始图像中属于 4 k 4 k 3 k o 6 3 集合中的4 个像素值都映射成为 商图像 中的一个像素值k 同样设x 4 余图像 的光滑度来源 原始图像中属于 4 k 4 k t k o 6 3 集合中的6 4 个像素值都映射成为 余图像 中的一个像素值t t 0 3 由此可见 商图像 和 余图像 既能够继承原始图像的图像模式 也能够 在原始图像的基础上产生新的图像模式 这就说明了它们的图像模式都不会比原 始图像弱 3 商图像 和 余图像 的压缩率一定不低于原始图像的压缩率 根据结论3 显见此结论成立 无须赘述 例如 设原图像中的一段图像数据 为1 6 81 7 01 7 21 7 0 1 7 42 3 417 42 3 82 3 4 则这段图像数据分别关于1 2 4 8 1 6 的 商图像 和 余图像 所对应的数据段如下表所示 商图像 与 余图像 对应的图像数据表 x 商图像 余图像 l1 6 817 01 7 21 7 0 1 7 42 3 41 7 42 3 82 3 4000 0 00000 28 48 58 68 58 71 1 78 71 1 91 1 70o0 oo00 0 0 重庆大学硕士论文 l z w 算法与商图像 余图像 44 24 24 34 24 35 84 35 95 80 2 0222 22 2 8 2 l2 l 2 l2 1 2 12 92 12 92 9o24262662 1 61 0 1 01 01 01 01 41 01 41 481 01 2l o1 41 01 4j 41 0 表4 5 进一步可以得到原图像 商图像和余图像的在l z w 压缩下产生的压缩代码表 原始图像 商图像 和 余图像 的压缩代码表 原图像的压缩代码i1 6 8 1 7 01 7 2 1 7 01 7 42 3 41 7 42 3 82 3 4 x商图像的压缩代码余图像的压缩代码 l1 6 81 7 01 7 21 7 0 1 7 42 3 41 7 42 3 8 2 3 402 5 8 2 5 92 5 8 28 4 8 58 b8 58 71 1 7 8 71 1 91 1 702 5 8 2 5 92 5 8 44 24 24 32 5 95 84 35 95 8 o2 2 5 8 2 6 12 6 2 82 l2 5 82 5 82 92 12 92 9 o2 426 2 6 2 6 2 1 61 0 2 5 82 5 81 4l o1 41 481 01 2l o1 42 6 2 6 2 表4 6 从上面两个表中 可以注意到如下现象 原始图像的颜色集合为 1 6 81 7 0 1 7 21 7 42 3 42 3 8 而当x 2 时 商 图像 的颜色集合为 8 48 58 68 71 1 71 1 9 二者的颜色集合大小相同 且两个集合中的元素呈一一对应关系 即二者具有相同的图像模式 所以 它们的压缩率相同 当x 4 时 商图像 的颜色集合为 4 24 3 j 85 9 它与原始图像 的颜色集合构成一对多的映射 例如 商图像 中的4 2 同时对应着原图 像中的1 6 8 和1 7 0 两个元素 这时 商图像 的图像模式在原图像的基 础上就得到了加强 所以 商图像