第10章-图像编码--数字图像处理-教学课件.ppt

《第10章-图像编码--数字图像处理-教学课件.ppt》由会员分享，可在线阅读，更多相关《第10章-图像编码--数字图像处理-教学课件.ppt（106页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十章 图像编码 第十章 图像编码 10.1 图像编码概述 10.2 哈夫曼编码10.3 香农-范诺编码10.4 行程编码10.5 LZW 编码 10.6 算术编码10.7 JPEG 编码10.8 编程实例 第十章 图像编码 10.1 图像编码概述 10.1.1 图像编码基本原理 虽 然 表 示 图 像 需 要 大 量 的 数 据，但 图 像 数 据 是 高 度 相 关 的，或 者 说 存 在 冗 余（Redundancy）信 息，去 掉 这 些 冗 余 信 息 后 可 以有 效 压 缩 图 像，同 时 又 不 会 损 害 图 像 的 有 效 信 息。数 字 图 像 的冗 余 主 要 表 现

2、为 以 下 几 种 形 式：空 间 冗 余、时 间 冗 余、视 觉 冗 余、信息熵冗余、结构冗余和知识冗余。空 间 冗 余：图 像 内 部 相 邻 像 素 之 间 存 在 较 强 的 相 关 性 所 造 成的冗余。时间冗余：视频图像序列中的不同帧之间的相关性所造成的冗余。第十章 图像编码 视觉冗余：是指人眼不能感知或不敏感的那部分图像信息。信 息 熵 冗 余：也 称 编 码 冗 余，如 果 图 像 中 平 均 每 个 像 素 使用 的 比 特 数 大 于 该 图 像 的 信 息 熵，则 图 像 中 存 在 冗 余，这 种 冗余称为信息熵冗余。结构冗余：是指图像中存在很强的纹理结构或自相似性。知

3、 识 冗 余：是 指 在 有 些 图 像 中 还 包 含 与 某 些 先 验 知 识 有 关的信息。第十章 图像编码 图 像 数 据 的 这 些 冗 余 信 息 为 图 像 压 缩 编 码 提 供 了 依 据。例如，利 用 人 眼 对 蓝 光 不 敏 感 的 视 觉 特 性，在 对 彩 色 图 像 编 码 时，就 可 以 用 较 低 的 精 度 对 蓝 色 分 量 进 行 编 码。图 像 编 码 的 目 的 就是 充 分 利 用 图 像 中 存 在 的 各 种 冗 余 信 息，特 别 是 空 间 冗 余、时间 冗 余 以 及 视 觉 冗 余，以 尽 量 少 的 比 特 数 来 表 示 图 像。

4、利 用 各种 冗 余 信 息，压 缩 编 码 技 术 能 够 很 好 地 解 决 在 将 模 拟 信 号 转 换为 数 字 信 号 后 所 产 生 的 带 宽 需 求 增 加 的 问 题，它 是 使 数 字 信 号走 上 实 用 化 的 关 键 技 术 之 一，表10-1 中 列 出 了 几 种 常 见 应 用 的 码率。第十章 图像编码 第十章 图像编码 10.1.2 图像编码的方法 根 据 编 码 过 程 中 是 否 存 在 信 息 损 耗 可 将 图 像 编 码 分 为 有 损 压缩 和 无 损 压 缩。无 损 压 缩 无 信 息 损 失，解 压 缩 时 能 够 从 压 缩 数 据精 确

5、 地 恢 复 原 始 图 像；有 损 压 缩 不 能 精 确 重 建 原 始 图 像，存 在 一定 程 度 的 失 真。根 据 编 码 原 理 可 以 将 图 像 编 码 分 为 熵 编 码、预 测编码、变换编码和混合编码等。（1）熵 编 码。熵 编 码 是 纯 粹 基 于 信 号 统 计 特 性 的 编 码 技 术，是 一 种 无 损 编 码。熵 编 码 的 基 本 原 理 是 给 出 现 概 率 较 大 的 符 号 赋予 一 个 短 码 字，而 给 出 现 概 率 较 小 的 符 号 赋 予 一 个 长 码 字，从而 使 得 最 终 的 平 均 码 长 很 小。常 见 的 熵 编 码 方

6、法 有 行 程 编 码（Run Length Encoding）、哈夫曼编码和算术编码。第十章 图像编码（2）预 测 编 码。预 测 编 码 是 基 于 图 像 数 据 的 空 间 或 时 间 冗余 特 性，用 相 邻 的 已 知 像 素（或 像 素 块）来 预 测 当 前 像 素（或像 素 块）的 取 值，然 后 再 对 预 测 误 差 进 行 量 化 和 编 码。预 测 编码 可 分 为 帧 内 预 测 和 帧 间 预 测，常 用 的 预 测 编 码 有 差 分 脉 码 调制（Differential Pulse Code Modulation，DPCM）和运动补偿法。（3）变 换 编 码

7、。变 换 编 码 通 常 是 将 空 间 域 上 的 图 像 经 过 正 交变 换 映 射 到 另 一 变 换 域 上，使 变 换 后 的 系 数 之 间 的 相 关 性 降 低。图 像 变 换 本 身 并 不 能 压 缩 数 据，但 变 换 后 图 像 的 大 部 分 能 量 只集 中 到 少 数 几 个 变 换 系 数 上，采 用 适 当 的 量 化 和 熵 编 码 就 可 以有效地压缩图像。第十章 图像编码（4）混 合 编 码。混 合 编 码 是 指 综 合 了 熵 编 码、变 换 编 码 或预测编码的编码方法，如JPEG 标准和MPEG 标准。根 据 对 压 缩 编 码 后 的 图 像

8、 进 行 重 建 的 准 确 程 度，可 将 常 用的图像编码方法分为三类：（1）信 息 保 持 编 码：也 称 无 失 真 编 码，它 要 求 在 编 解 码 过程 中 保 证 图 像 信 息 不 丢 失，从 而 可 以 完 整 地 重 建 图 像。信 息 保持 编 码 的 压 缩 比 较 低，一 般 不 超 过3:1，主 要 应 用 在 图 像 的 数字存储方面，常用于医学图像编码中。第十章 图像编码 第十章 图像编码（3）特 征 提 取：在 图 像 识 别、分 析 和 分 类 等 技 术 中，往往 并 不 需 要 全 部 图 像 信 息，而 只 要 对 感 兴 趣 的 部 分 特 征 信

9、 息 进行 编 码 即 可 压 缩 数 据。例 如，对 遥 感 图 像 进 行 农 作 物 分 类 时，就 只 需 对 用 于 区 别 农 作 物 与 非 农 作 物，以 及 农 作 物 类 别 之 间 的特 征 进 行 编 码，而 可 以 忽 略 道 路、河 流、建 筑 物 等 其 他 背 景 信息。第十章 图像编码 10.1.3 图像编码新技术 图 像 编 码 已 经 发 展 了 几 十 年，人 们 不 断 提 出 新 的 压 缩 方 法。如，利 用 人 工 神 经 网 络（Artificial Neural Network，ANN）的压 缩 编 码、分 形 编 码（Fractal Cod

10、ing）、小 波 编 码（Wavelet Coding）、基 于 对 象 的 压 缩 编 码（Object Based Coding）和 基于模型的压缩编码（Model Based Coding）等等。第十章 图像编码 第十章 图像编码 2）小波编码 1989年，S.G.Mallat 首 次 将 小 波 变 换 用 于 图 像 编 码。经 过 小波 变 换 后 的 图 像，具 有 良 好 的 空 间 方 向 选 择 性，而 且 是 多 分 辨率 的，能 够 保 持 原 图 像 在 各 种 分 辨 率 下 的 精 细 结 构，与 人 的 视觉特性十分吻合。3）模型编码 模 型 编 码 是 近 几

11、 年 发 展 起 来 的 一 种 很 有 前 途 的 低 比 特 率 编码 方 法，其 基 本 出 发 点 是 在 编、解 码 两 端 分 别 建 立 起 相 同 的 模型，编 码 时 利 用 先 验 模 型 抽 取 图 像 中 的 主 要 信 息 并 用 模 型 参 数的形式表示，解码时则利用所接收的模型参数重建图像。第十章 图像编码 第十章 图像编码 设 一 幅 灰 度 级 为N 的 图 像，图 像 中 第k 级 灰 度 出 现 的 概 率 为Pk，图 像 大 小 为NxNy，每 个 像 素 用d比 特 表 示，每 两 帧 图 像 间 隔t，则 按 信 息 论 中 信 息 熵 的 定 义，

12、数 字 图 像 的 熵H 由 下 式 定义：（10-1）由 此 可 见，图 像 熵H 表 示 各 灰 度 级 比 特 数 的 统 计 平 均 值。对于一种图像编码方法，设第k 级灰度的码字长度为Bk，则该图像的平均码字长度R 为（10-2）第十章 图像编码 于是，可定义编码效率 为 每秒钟所需的传输比特数bps 为（10-3）（10-4）压缩比r 为（10-5）由 于 同 一 压 缩 算 法 对 不 同 图 像 的 编 码 效 率 会 有 所 不 同，因 此常 需 定 义 一 些“标 准 图 像”，如 国 际 上 流 行 的 三 幅 图 像Lena、Barbara 和Mandrill。一 般

13、通 过 测 量 不 同 压 缩 算 法 对 同 一 组“标 准图像”的编码性能来评价各图像压缩算法的编码效率。第十章 图像编码 第十章 图像编码 主 观 质 量 评 价 是 指 由 一 批 观 察 者 对 编 码 图 像 进 行 观 察 并 打分，然 后 综 合 所 有 人 的 评 判 结 果，给 出 图 像 的 质 量 评 价。客 观质 量 评 价 能 够 快 速 有 效 地 评 价 编 码 图 像 的 质 量，但 符 合 客 观 质量 评 价 指 标 的 图 像 不 一 定 具 有 较 好 的 主 观 质 量。主 观 质 量 评 价能够与人的视觉效果相匹配，但其评判过程缓慢费时。第十章 图

14、像编码 3）算法的适用范围 特 定 的 图 像 编 码 算 法 具 有 其 相 应 的 适 用 范 围，并 不 对 所 有图 像 都 有 效。一 般 说 来，大 多 数 基 于 图 像 信 息 统 计 特 性 的 压 缩算 法 具 有 较 广 的 适 用 范 围，而 一 些 特 定 的 编 码 算 法 的 适 用 范 围较窄，如分形编码主要用于自相似性高的图像。第十章 图像编码 4）算法的复杂度 算 法 的 复 杂 度 即 指 完 成 图 像 压 缩 和 解 压 缩 所 需 的 运 算 量 和硬 件 实 现 该 算 法 的 难 易 程 度。优 秀 的 压 缩 算 法 要 求 有 较 高 的 压

15、缩 比，压 缩 和 解 压 缩 快，算 法 简 单，易 于 硬 件 实 现，还 要 求 解压 缩 后 的 图 像 质 量 较 好。选 用 编 码 方 法 时 一 定 要 考 虑 图 像 信 源本 身 的 统 计 特 性、多 媒 体 系 统(硬 件 和 软 件 产 品)的 适 应 能 力、应用环境以及技术标准。第十章 图像编码 10.2 哈夫曼编码 1.哈夫曼编码的理论基础 根 据 信 息 论 中 信 源 编 码 理 论，当 平 均 码 长R 大 于 等 于 图 像 熵H时，总 可 设 计 出 一 种 无 失 真 编 码。当 平 均 码 长 远 大 于 图 像 熵 时，表 明 该 编 码 方 法

16、 效 率 很 低；当 平 均 码 长 等 于 或 很 接 近 于（但 不 大于）图 像 熵 时，称 此 编 码 方 法 为 最 佳 编 码，此 时 不 会 引 起 图 像 失真；当 平 均 码 长 大 于 图 像 熵 时，压 缩 比 较 高，但 会 引 起 图 像 失 真。在 变 长 编 码 中，如 果 码 字 长 度 严 格 按 照 对 应 符 号 出 现 的 概 率 大 小逆 序 排 列，则 其 平 均 码 字 长 度 为 最 小，这 就 是 变 长 最 佳 编 码 定 理。变长最佳编码定理是哈夫曼编码的理论基础。设D 为编码所使用的数制，则变长最佳编码的平均码字长度R的范围为(10-8)

17、第十章 图像编码 2.哈夫曼编码算法 哈 夫 曼 编 码 是 以 信 源 概 率 分 布 为 基 础 的，但 一 般 无 法 事 先知 道 信 源 的 概 率 分 布，通 常 采 用 对 大 量 数 据 进 行 统 计 后 得 到 的近 似 分 布 来 代 替，这 样 会 导 致 实 际 应 用 时 哈 夫 曼 编 码 无 法 达 到最 佳 性 能。通 过 利 用 根 据 输 入 数 据 序 列 自 适 应 地 匹 配 信 源 概 率分 布 的 方 法，可 以 较 好 地 改 进 哈 夫 曼 编 码 的 性 能。哈 夫 曼 编 码的一般算法如下：（1）首 先 统 计 信 源 中 各 符 号 出

18、 现 的 概 率，按 符 号 出 现 的 概率从大到小排序。（2）把最小的两个概率相加合并成新的概率，与剩余的概率组成新的概率集合。第十章 图像编码 第十章 图像编码 例10-1 设 一 幅 灰 度 级 为8（分 别 用S0、S1、S2、S3、S4、S5、S6、S7表 示）的 图 像 中，各 灰 度 所 对 应 的 概 率 分 别 为0.40、0.18、0.10、0.10、0.07、0.06、0.05、0.04。现对其进行哈夫曼编码 编码过程如图10-1 所示，具体步骤如下：(1)首 先 对 信 源 概 率 从 大 到 小 排 序，选 出 最 小 的 两 个 概 率（0.04和0.05），相

19、加 得0.09，与 其 他 概 率 组 成 新 的 概 率 集 合0.40，0.18，0.10，0.10，0.07，0.06，0.09。第十章 图像编码(2)对 新 的 概 率 集 合 重 新 排 序，选 出 最 小 的 两 个 概 率（0.06和0.07），相 加 得0.13，组 成 新 的 概 率 集 合0.40，0.18，0.10，0.10，0.09，0.13。(3)对 新 的 概 率 集 合 重 新 排 序，选 出 最 小 的 两 个 概 率（0.10和0.09），相 加 得0.19，组 成 新 的 概 率 集 合0.40，0.18，0.13，0.10，0.19。(4)对 新 的 概

20、率 集 合 重 新 排 序，选 出 最 小 的 两 个 概 率（0.13和0.10），相 加 得0.23，组 成 新 的 概 率 集 合0.40，0.19，0.18，0.23。第十章 图像编码(5)对 新 的 概 率 集 合 重 新 排 序，选 出 最 小 的 两 个 概 率（0.19和0.18），相加得0.37，组成新的概率集合0.40，0.23，0.37。(6)对 新 的 概 率 集 合 重 新 排 序，选 出 最 小 的 两 个 概 率（0.23和0.37），相加得0.60，组成新的概率集合0.40，0.60。(7)直到最后两个概率（0.60和0.40）相加和为1。第十章 图像编码 第十

21、章 图像编码 图10-1 哈夫曼编码过程 第十章 图像编码 上 述 哈 夫 曼 编 码 方 法 形 成 的 码 字 是 可 识 别 的，即 能 够 保 证 一个 符 号 的 码 字 不 会 与 另 一 个 符 号 的 码 字 的 前 几 位 相 同。比 如 说，如 果S0的 码 字 为1，S1的 码 字 为001，而S2的 码 字 为011，则 当 编码 序 列 中 出 现0011 时，就 不 能 判 别 它 是S2的 码 字 还 是S1的 码 字 后面跟了一个S0的码字1。下面来看一下哈夫曼编码的编码效率。平均码长R 为 第十章 图像编码 第十章 图像编码 由 此 可 见，哈 夫 曼 编 码

22、 的 编 码 效 率 是 相 当 高 的，其 冗 余 度 只有2.2%。如 果 采 用 等 长 编 码，由 于 有8种 灰 度 级，则 每 种 灰 度 级别 至 少 需 要3比 特 来 表 示，对 于 例10-1 中 的 图 像 而 言，其 编 码 的平均码长为3，编码效率为85%。对 不 同 概 率 分 布 的 信 源，哈 夫 曼 编 码 的 编 码 效 率 有 所 差 别。根 据 信 息 论 中 信 源 编 码 理 论，对 于 二 进 制 编 码，当 信 源 概 率 为2的 负 幂 次 方 时，哈 夫 曼 编 码 的 编 码 效 率 可 达100%，其 平 均 码 字长 度 也 很 短，而

23、 当 信 源 概 率 为 均 匀 分 布 时，其 编 码 效 果 明 显 降低。在 表10-2 中，显 然，第 二 种 情 况 的 概 率 分 布 也 服 从2的 负 幂次 方，故 其 编 码 效 率 也 可 以 达 到100%，但 由 于 它 服 从 均 匀 分 布，其 熵 最 大，平 均 编 码 长 度 很 大，因 此 从 其 他 指 标 看（如，压 缩比r），其 编 码 效 率 最 低。也 就 是 说，在 信 源 概 率 接 近 于 均 匀 分布时，一般不使用哈夫曼编码。第十章 图像编码 10-2 啥夫曼编码在不同概率分布下的编码效果对比 第十章 图像编码 10.3 香农-范诺编码 香

24、农-范 诺（Shannon-Fannon）编 码 也 是 一 种 常 见 的 可 变 字 长编 码。与 哈 夫 曼 编 码 相 似，当 信 源 符 号 出 现 的 概 率 正 好 为2-i（i0）时，采 用 香 农-范 诺 编 码 同 样 能 够 达 到100%的 编 码 效 率。香 农-范 诺 编 码 的 理 论 基 础 是 符 号 的 码 字 长 度Ni完 全 由 该 符 号 出现的概率来决定，即（10-9）式中，D 为编码所用的数制。第十章 图像编码 香农-范诺编码的步骤如下：（1）将信源符号按其出现概率从大到小排序；（2）按照式（10-9）计算出各概率对应的码字长度Ni；（3）计算累加

25、概率Ai，即Ai=Ai-1+Pi-1 i=1,2,N-1；A0=0(10-10)（4）把 各 个 累 加 概 率Ai由 十 进 制 转 化 为 二 进 制，取 该 二 进制数的前Ni位作为对应信源符号的码字。第十章 图像编码 为 便 于 比 较，仍 以 例10-1 中 图 像 为 对 象，对 其 进 行 香 农-范诺 编 码，结 果 如 表10-3 所 示。由 于 在 此 采 用 二 进 制 对 码 字 赋 值，故 在 利 用 式（10-9）计 算 码 字 长 度Ni时，D 取 为2。以 符 号S4为 例，其 出 现 概 率 为0.07，按 照 式（10-9）计 算 得 到 它 的 码 字 长

26、 度 应 为4，按 式（10-10）计 算 得 到 它 的 累 加 概 率A4为0.78，将0.78转 化 为二 进 制 并 取 其 前4位 即 得 符 号S4的 码 字 为1100（省 去 了“0.”，有的浮点数不能完全转化，转化时只需完成前Ni位即可）。第十章 图像编码 表10-3 香农-范诺编码 第十章 图像编码 除此之外，还有二分法香农-范诺编码方法。其步骤如下：（1）首先统计出每个符号出现的概率；（2）从左到右对上述概率从大到小排序；（3）从 这 个 概 率 集 合 中 的 某 个 位 置 将 其 分 为 两 个 子 集 合，并 尽 量 使 两 个 子 集 合 的 概 率 和 近 似

27、 相 等，给 前 面 一 个 子 集 合 赋 值为0，后面一个子集合赋值为1；（4）重 复 步 骤3，直 到 各 个 子 集 合 中 只 有 一 个 元 素 为 止；（5）将每个元素所属的子集合的值依次串起来，即可得到各个元素的香农-范诺编码。第十章 图像编码 表10-4 二分法香农-范诺编码 第十章 图像编码 10.4 行 程 编 码10.4.1 行程编码基本方法 行 程 编 码 又 称 行 程 长 度 编 码（Run Length Encoding，RLE），是 一 种 熵 编 码，其 编 码 原 理 相 当 简 单，即 将 具 有 相 同 值 的 连 续 串用 其 串 长 和 一 个 代

28、 表 值 来 代 替，该 连 续 串 就 称 为 行 程，串 长 称 为行 程 长 度。例 如，有 一 字 符 串“aabbbcddddd”，则 经 行 程 长 度编码后，该字符串可以只用“2a3b1c5d”来表示。行 程 编 码 分 为 定 长 和 不 定 长 编 码 两 种。定 长 编 码 是 指 编 码 的行 程 长 度 所 用 的 二 进 制 位 数 固 定，而 变 长 行 程 编 码 是 指 对 不 同 范围 的 行 程 长 度 使 用 不 同 位 数 的 二 进 制 位 数 进 行 编 码。使 用 变 长 行程编码需要增加标志位来表明所使用的二进制位数。第十章 图像编码 行 程 编

29、 码 比 较 适 合 于 二 值 图 像 的 编 码，一 般 用 于 量 化 后 出现 大 量 零 系 数 连 续 的 场 合，用 行 程 来 表 示 连 零 码。如 果 图 像 是由 很 多 块 颜 色 或 灰 度 相 同 的 大 面 积 区 域 组 成 的，那 么 采 用 行 程编 码 可 以 达 到 很 高 的 压 缩 比。如 果 图 像 中 的 数 据 非 常 分 散，则行 程 编 码 不 但 不 能 压 缩 数 据，反 而 会 增 加 图 像 文 件 的 大 小。为了 达 到 较 好 的 压 缩 效 果，一 般 不 单 独 采 用 行 程 编 码，而 是 和 其他 编 码 方 法 结

30、 合 使 用。例 如，在JPEG 中，就 综 合 使 用 了 行 程 编码、DCT、量 化 编 码 以 及 哈 夫 曼 编 码，先 对 图 像 作 分 块 处 理，再 对 这 些 分 块 图 像 进 行 离 散 余 弦 变 换（DCT），对 变 换 后 的 频域 数 据 进 行 量 化 并 作Z 字 形 扫 描，接 着 对 扫 描 结 果 作 行 程 编 码，对行程编码后的结果再作哈夫曼编码。第十章 图像编码 10.4.2 PCX 文件中的行程编码 PCX 文 件 分 为 文 件 头 和 图 像 压 缩 数 据 两 个 部 分。如 果 是256色 图 像，则 还 有 一 个256 色 调 色

31、板 存 于 文 件 尾 部。文 件 头 全 长128字 节，包 含 了 图 像 的 大 小 和 颜 色 以 及PCX 文 件 的 版 本 标 识 等信 息，图 像 压 缩 数 据 紧 跟 在 文 件 头 之 后。如 果 没 有 使 用 调 色 板，那 么 图 像 压 缩 数 据 存 储 的 是 实 际 像 素 值；否 则，存 储 的 是 调 色板 的 索 引 值。当 压 缩 数 据 是 实 际 的 像 素 值 时，它 们 按 颜 色 平 面和 扫 描 行 存 储，即 每 行 先 存 储 所 有R 分 量，再 存 储 所 有G 分 量，最 后 存 储 所 有B 分 量，一 行 数 据 存 储 完

32、 后，接 着 存 储 下 一 行 数 据。如 果 使 用 了 调 色 板，则 不 会 分 解 为 单 独 的 颜 色 平 面 存 储。读 者可 以 查 阅 图 像 文 件 格 式 的 相 关 书 籍 了 解PCX 文 件 的 详 细 格 式。下面以256色PCX 文件为例，说明PCX 文件中的行程编码。第十章 图像编码 在256色PCX 文 件 中，每 个 像 素 占 一 字 节，压 缩 数 据 以 字 节为 单 位 逐 行 进 行 编 码，每 行 填 充 到 偶 数 字 节。PCX 文 件 规 定 编 码时 的 最 大 行 程 长 度 为63，如 果 行 程 长 度 大 于63，则 必 须

33、分 多 次 存储。对 于 长 度 大 于1的 行 程，编 码 时 先 存 入 其 行 程 长 度（长 度L 加上192 即0 xC0），再 存 入 该 行 程 的 代 表 值，行 程 长 度 和 行 程 的 代表 值 分 别 占 一 字 节。对 于 长 度 为1的 行 程，即 单 个 像 素，如 果 该像 素 的 值 小 于 或 等 于0 xC0，则 编 码 时 直 接 存 入 该 像 素 值，而 不存 储 长 度 信 息；否 则，先 存 入0 xC1，再 存 入 该 像 素 值，这 样 做 的目 的 是 为 了 避 免 该 像 素 值 被 误 认 为 长 度 信 息。例 如，连 续100个

34、灰度 值 为0 x80的 像 素，其 编 码(以 十 六 进 制 表 示)应 为FF 80 25 80。上面的编码中出现FF 的长度信息是由63与0 xC0 相加所得。第十章 图像编码 对256色PCX 文 件 解 码 时，首 先 从 压 缩 数 据 部 分 读 取 一 个 字节，判 断 该 值 是 否 大 于0 xC0，如 果 是，则 表 明 该 字 节 是 行 程 长度 信 息，取 其 低 六 位（相 当 于 减 去0 xC0）作 为 行 程 长 度L，读取 下 一 个 字 节 作 为 像 素 值 并 重 复L 次 存 入 图 像 数 据 缓 冲 区；否 则，直接将该字节存入图像数据缓冲区

35、。虽 然 几 乎 所 有 的 图 像 应 用 软 件 都 支 持PCX 文 件 格 式，但 由于它的压缩比不高，因而现在用得不是很多。第十章 图像编码 10.5 LZW 编码 10.5.1 LZW 编码方法 LZW（Lempel-Ziv&Welch）编 码 又 称 字 串 表 编 码，属 于一 种 无 损 编 码，是Welch 将Lempel 和Ziv 所 提 出 的 无 损 压 缩 技 术改 进 后 的 压 缩 方 法。LZW 编 码 与 行 程 编 码 类 似，也 是 对 字 符 串进 行 编 码 从 而 实 现 压 缩，但 它 在 编 码 的 同 时 还 生 成 了 特 定 字 符串以及

36、与之对应的索引字符串表。第十章 图像编码 LZW 编 码 的 基 本 思 想 是：在 编 码 过 程 中，将 所 遇 到 的 字 符串 建 立 一 个 字 符 串 表，表 中 的 每 个 字 符 串 都 对 应 一 个 索 引，编码 时 用 该 字 符 串 在 字 串 表 中 的 索 引 来 代 替 原 始 的 数 据 串。例 如，一 幅8位 的 灰 度 图 像，我 们 可 以 采 用12位 来 表 示 每 个 字 符 串 的 索引，前256个 索 引 用 于 对 应 可 能 出 现 的256种 灰 度，由 此 可 建 立一 个 初 始 的 字 符 串 表，而 剩 余 的3840个 索 引 就

37、 可 分 配 给 在 压 缩过 程 中 出 现 的 新 字 符 串，这 样 就 生 成 了 一 个 完 整 的 字 符 串 表，压 缩 数 据 就 可 以 只 保 存 它 在 字 符 串 表 中 的 索 引，从 而 达 到 压 缩数 据 的 目 的。字 符 串 表 是 在 压 缩 过 程 中 动 态 生 成 的，不 必 将 它保 存 在 压 缩 文 件 里，因 为 解 压 缩 时 字 符 串 表 可 以 由 压 缩 文 件 中的信息重新生成。第十章 图像编码 GIF（Graphics Interchange Format）最 初 是 由 美 国CompuServe 于1987年 开 发 的 一

38、 种 压 缩 位 图 格 式。它 可 支 持 多 达 256 种 的 颜 色，具 有 极 佳 的 压 缩 效 率，已 成 为Internet 上 一 种 流行 的 文 件 格 式。GIF 图 像 文 件 采 用 的 是 一 种 改 良 的LZW 压 缩 算 法，通 常 称 为GIF-LZW 压 缩 算 法。GIF 图 像 文 件 以 块（又 称 为 区 域 结构）的 方 式 来 存 储 图 像 相 关 的 信 息，具 体 的 文 件 格 式 可 参 考 图像文件格式的相关书籍。下面简要介绍GIF-LZW 的编码方法。设S1、S2 为 两 个 存 放 字 符 串 的 临 时 变 量，LZW_CL

39、EAR 和LZW_EOI 分 别 为 字 符 表 初 始 化 标 志 和 编 码 结 束 标 志，GIF-LZW的编码步骤如下：第十章 图像编码（1）根 据 图 像 中 使 用 的 颜 色 数 初 始 化 一 个 字 串 表，字 串 表 中的 每 个 颜 色 对 应 一 个 索 引。在 初 始 字 串 表 的 末 尾 再 添 加 两 个 符号（LZW_CLEAR 和LZW_EOI）的 索 引。设 置 字 符 串 变 量S1、S2 并初始化为空。（2）接着输出LZW_CLEAR 在字串表中的索引。（3）从 图 像 数 据 流 中 第 一 个 字 符（假 设 数 据 以 字 符 串 表 示）开始，

40、每次读取一个字符，将其赋给字符串变量S2。（4）判 断“S1+S2”是 否 已 存 在 于 字 串 表 中。如 果 字 串 表 中存 在“S1+S2”，则S1=S1+S2；否 则，输 出S1 在 字 串 表 中 的 索 引，并在字串表末尾为“S1+S2”添加索引，同时，S1=S2。第十章 图像编码（5）重复第3和第4步，直到所有字符读完为止。（6）输 出S1 中 的 字 符 串 在 字 串 表 中 的 索 引，然 后 输 出 结 束标志LZW_EOI 的索引，编码完毕。GIF-LZW 的 解 码 过 程 比 较 复 杂，它 和 编 码 过 程 正 好 相 反，即 将 编 码 后 的 码 字 转

41、 换 成 对 应 的 字 符 串，重 新 生 成 字 串 表，然后 依 次 输 出 对 应 的 字 符 串 即 可。GIF-LZW 的 解 码 流 程 如 图10-2所示，表中的Code 和OldCode 是两个存放索引的临时变量。第十章 图像编码 图10-2 GIF-LZW 解码流程 第十章 图像编码 10.5.2 LZW 编码实例 设 有 一 来 源 于4色（以a、b、c、d表 示）图 像 的 数 据 流aabcabbbbd，现对其进行LZW 编码。编码过程如下：编 码 前，首 先 需 要 初 始 化 一 个 字 符 串 表。由 于 图 像 中 只 有四 种 颜 色，因 而 我 们 可 以

42、 只 用4比 特 表 示 字 符 串 表 中 每 个 字 符 串的 索 引，表 中 的 前4项 代 表4种 颜 色，后 两 项 分 别 表 示 初 始 化 和图 像 结 束 标 志，建 立 的 初 始 化 字 符 串 表 如 表10-5 所 示。接 着 把S1和S2 初 始 化 为 空（即NULL），输 出LZW_CLEAR 的 在 字 符 串 表中的索引值4H，接下来是对图像数据的编码。第十章 图像编码 表10-5 初始化字符串表 字符串 索引 A 0 H b 1 H c 2 H d 3 H LZW_CLEAR 4 H LZW_EOI 5 H 第十章 图像编码 读 取 图 像 数 据 流 的

43、 第 一 个 字 符“a”，赋 给S2，因S1+S2=“a”已存在字串表中，所以S1=S1+S2=“a”。接 着 读 入 下 一 个 字 符“a”赋 给S2，因S1+S2=“aa”不 存 在 于字 串 表 中，所 以 输 出S1=“a”的 索 引0H，同 时 在 字 符 串 表 末 尾 添加新字符串“aa”的索引6H，并使S1=S2=“a”。依 次 读 取 数 据 流 中 的 每 个 字 符，如 果S1+S2 没 有 出 现 在 字 符串 表 中，则 输 出S1 中 的 字 符 串 的 索 引，并 在 字 符 串 表 末 尾 为 新 字符 串S1+S2 添 加 索 引，并 使S1=S2；否 则

44、，不 输 出 任 何 结 果，只是 使S1=S1+S2。所 有 字 符 处 理 完 毕 后，输 出S1 中 的 字 符 串 的 索 引，最 后 输 出 结 束 标 志LZW_EOI 的 索 引。至 此，编 码 完 毕，完 整 的 编码 过 程 如 表10-6 所 示，最 后 的 编 码 结 果 为“4001271B35”（以 十六进制表示）。第十章 图像编码 表10-6 GIF-LZW 编码过程 第十章 图像编码 下 面 对 上 述 编 码 结 果“4001271B35”进 行 解 码。按 图10-2 的解 码 流 程，首 先 读 取 第 一 个 编 码 Code=4H，由 于 它 为LZW_

45、CLEAR，因 此 需 初 始 化 字 符 串 表，结 果 如 表10-5 所 示（在 实 际 应 用 中，可 根 据 文 件 头 中 给 定 的 信 息 建 立 初 始 字 符 串表）。读 入 下 一 个 编 码Code=0H，由 于 它 不 等 于LZW_CLEAR，因此 输 出 字 串 表 中 0H 对 应 的 字 符 串“a”，同 时 使OldCode=Code=0H。读 入 下 一 个 编 码Code=0H，由 于 字 串 表 中 存 在 该 索 引，因 此输 出0H 所 对 应 的 字 符 串“a”，然 后 将OldCode=0H 所 对 应 的 字符 串“a”加 上Code=0H

46、 所 对 应 的 字 符 串 的 第 一 个 字 符“a”，即“aa”添加到字串表中，其索引为6H，同时使ldCode=Code=0H。第十章 图像编码 读 入 下 一 个 编 码Code=1H，由 于 字 串 表 中 存 在 该 索 引，因 此输 出1H 所 对 应 的 字 符 串“b”，然 后 将OldCode=0H 所 对 应 的 字符 串“a”加 上Code=1H 所 对 应 的 字 符 串 的 第 一 个 字 符“b”，即“ab”添 加 到 字 串 表 中，其 索 引 为 7H，同 时 使OldCode=Code=1H。读 入 下 一 个 编 码Code=2H，由 于 字 串 表 中

47、 存 在 该 索 引，因此 输 出2H 所 对 应 的 字 符 串“c”，然 后 将OldCode=1H 所 对 应 的字 符 串“b”加 上Code=2H 所 对 应 的 字 符 串 的 第 一 个 字 符“c”，即“bc”添 加 到 字 串 表 中，其 索 引 为 8H，同 时 使OldCode=Code=2H。第十章 图像编码 读 入 下 一 个 编 码Code=7H，由 于 字 串 表 中 存 在 该 索 引，因 此输 出7H 所 对 应 的 字 符 串“ab”，然 后 将OldCode=2H 所 对 应 的 字符 串“c”加 上Code=7H 所 对 应 的 字 符 串 的 第 一

48、个 字 符“a”，即“ca”添 加 到 字 串 表 中，其 索 引 为 9H，同 时 使OldCode=Code=7H。读 入 下 一 个 编 码Code=1H，由 于 字 串 表 中 存 在 该 索 引，因此 输 出1H 所 对 应 的 字 符 串“b”，然 后 将OldCode=7H 所 对 应 的字 符 串“ab”加 上Code=1H 所 对 应 的 字 符 串 的 第 一 个 字 符“b”，即“abb”添 加 到 字 串 表 中，其 索 引 为 AH，同 时 使OldCode=Code=1H。第十章 图像编码 读 入 下 一 个 编 码Code=BH，由 于 字 串 表 中 不 存 在

49、 该 索 引，因 此 输 出OldCode=1H 所 对 应 的 字 符 串“b”加 上 该 字 符 串 的 第 一个 字 符“b”，即“bb”，同 时 将“aa”添 加 到 字 串 表 中，其 索引为BH，同时使OldCode=Code=BH。读 入 下 一 个 编 码Code=3H，由 于 字 串 表 中 存 在 该 索 引，因 此输 出 其 对 应 的 字 符 串“d”，然 后 将OldCode=BH 所 对 应 的 字 符 串“bb”加 上Code=3H 所 对 应 的 字 符 串 的 第 一 个 字 符“d”，即“bbd”添 加 到 字 串 表 中，其 索 引 为 CH，同 时 使O

50、ldCode=Code=3H。读 入 下 一 个 编 码 Code=5H，它 等 于LZW_EOI，数 据 解 码 完 毕，最 后 的 解 码 结 果 为aabcabbbbd。为清晰起见，完整的解码过程如表10-7 所示。第十章 图像编码 表10-7 GIF-LZW 解码过程 第十章 图像编码 10.6 算 术 编 码 算 术 编 码 有 两 种 模 式：一 种 是 基 于 信 源 概 率 统 计 特 性 的 固 定编 码 模 式，另 一 种 是 针 对 未 知 信 源 概 率 模 型 的 自 适 应 模 式。自 适应 模 式 中 各 个 符 号 的 概 率 初 始 值 都 相 同，它 们 依