信 息 技 术 2009 NO.08 SCIENCE & TECHNOLOGY INFORMATION 科技资讯 基于哈夫曼编码的图像压缩技术研究 （1.山东理工大学 山东淄博 255049 ； 2. 山东化工职业学院 山东淄博 255400 ） 田端财 1 , 2 殷晓丽 1 , 2 摘 要：哈夫曼编码是一种数据编码方式，以哈夫曼树——即最优二叉树，用带权路径长度最小的二叉树，对数据进行重编码，经常应 用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损压缩。本文主要介绍了基于哈 夫曼编码图像压缩技术的原理、算法、过程，并利用VB6.0作为编程开发工具，开发了一个对256色BMP图像进行压缩/解压缩的软件系统， 验证了算法的合理性和可行性。 关键词：哈夫曼编码 二叉树 熵 无损压缩 中图分类号：T P 3 1 1 . 1 2 文献标识码：A 文章编号：1672-3791(2009)03(b)-0029-02 哈 夫 曼 编 码 是 一 种 常 用 的 压 缩 编 码 算 法 , 采 用 变 长 码 编 码 , 属 于 无 损 压 缩 算 法 的 一 种 , 在 无 损 压 缩 的 编 码 范 畴 中 , 哈 夫 曼 (Huffman)编码方法是一种较有效的编码方 法 , 是 哈 夫 曼 在 1 9 5 2年 根 据 香 农 在 1 9 4 8年 和范若在1949年阐述的一种编码思想提出 的一种不定长(变长)编码的方法,也称霍夫 曼 编 码 。 哈 夫 曼 编 码 在 图 像 压 缩 应 用 中 具 有 非 常 重 要 的 意 义 , 哈 夫 曼 编 码 是 一 种 实 用 的 无 损 压 缩 技 术 , 经 过 多 年 的 不 断 改 进 , 已 经 形 成 了 系 统 的 理 论 和 方 法。目 前 主 要 有 两 种 类 型 的 哈 夫 曼 编 码 方 式 , 即 静 态 哈 夫 曼 编 码 和 动 态 哈 夫 曼 编 码 。 图 像 压 缩 编 码 技 术 可 以 追 溯 到1948年 提 出 的 电 视 信 号 数 字 化 , 到 今 天 已 经 有 6 0 多 年 的 历 史 了。在 此 期 间 出 现 了 很 多 种 图 像 压 缩 编 码 方 法 , 本 课 题 主 要 研 究 基 于 哈 夫 曼 编 码 对 图 像 进 行 无 损 压 缩 , 基 于 哈 夫 曼 编 码 的 图 像 无 损 压 缩 过 程 通 常 分 为 两 步, 即 去 除 相 关 和 编 码。去 除 相 关 就 是 要 去 除 图 像 数 据 的 冗 余 部 分 , 降 低 信 源 熵 , 这 是 对 图 像 数 据 的 压 缩 过 程 ; 编 码 就 是 对 去 除 冗余后的图像数据重新用一种新的符号编 码 代 替 , 这 也 是 对 图 像 数 据 的 重 编 码 进 行 存 储 的 过 程。　 　 1 哈夫曼编码原理 1 . 1 理论基础 为 了 节 省 空 间 , 在 对 数 据 进 行 编 码 时 , 可以对那些经常出现的数据指定较少的位 数 表 示 , 而 那 些 不 常 出 现 的 数 据 指 定 较 多 的 位 数 表 示 , 从 而 降 低 冗 余 , 这 样 从 总 的 效 果 看 就 节 省 了 存 储 空 间 。 基 于 哈 夫 曼 编 码 图 像 压 缩 的 基 本 原 理 是 频 繁 使 用 的 数 据 用 较 短 的 代 码 代 替 , 较 少 使 用 的 数 据 用 较 长 的 代 码 代 替 , 每 个 数 据 的 代 码 各 不 相 同 , 这 是 一 种 典 型 的 无 损 编 码 方 式。这 些 代 码 都 是 二 进 制 码, 且 码 字 长 度 是 不 均 匀 的、平 均 码 率 可 以 接 近 信 息 源 熵 值 的 一 种 编 码。编 码 过 程 是 先 对 图 像 数 据 扫 描 一 遍 , 计 算 出 各 种 像 素 出 现 的 概 率 , 按 概 率 的 大 小 建 立 最 优 二 叉 树 ( 二 叉 树 的 叶 子 节 点 刚 好 表 示 的 图 像 中 的 某 种 像 素)并给二叉树的每个分支赋特定权值(0或 1 ) , 然 后 通 过 遍 历 二 叉 树 读 取 从 根 节 点 到 叶 子 节 点 的 路 径 权 值 字 符 串 , 即 给 每 种 像 素 指 定 了 不 同 长 度 的 唯 一 编 码 , 由 此 得 到 一 张 该 图 像 所 有 像 素 的 哈 夫 曼 编 码 表。编 码 后 的 图 像 数 据 记 录 的 是 每 个 像 素 的 码 字 , 而 码 字 与 实 际 像 素 值 的 对 应 关 系 记 录 在 码 表 中 , 码 表 是 附 在 图 像 文 件 中 的 。 基 于 哈 夫 曼 编 码 图 像 压 缩 技 术 借 用 了 图 1 信源的哈夫曼编码 热力学中的名词“熵”(Entropy)来表示一条 信 息 中 真 正 需 要 编 码 的 信 息 量: 如 考 虑 用 0 和1组成的二进制数码为含有n个符号的某 条 信 息 编 码 , 假 设 符 号 E n 在 整 条 信 息 中 重 复 出 现 的 概 率 为 Pn , 则 该 符 号 的 熵 也 即 表 示 该 符 号 所 需 的 位 数 为 : , 整条信息的熵也即表示整条信息所需的位 数 : 。 1 . 2 编码具体过程 1 . 2 . 1 建 立 最 优 二 叉 树 的 过 程 ( 1 ) 如 下 图 所 示 , 在 每 个 结 点 上 标 出 信 源 字 母 的 概 率 。 ( 2 ) 找 出 两 个 具 有 最 小 概 率 的 节 点 , 在 本例中是0.01和0.04,把它们放在同一个父 节 点 的 两 个 字 节 点 上 。 (3)在其父结点上标出子节点的概率之 和,如图所示,应是0.01+0.04=0.05。进行下 一 轮 找 最 小 概 率 节 点 , 由 于 这 个 父 节 点 代 表 了 原 来 的 两 个 节 点 , 因 此 现 在 只 考 虑7 个 节 点 。 (4)在这7 个节点中还没有产生父节点, 在 其 中 找 两 个 最 小 概 率 的 , 这 里 是 0 . 0 5 和 0 . 0 5 , 把 它 们 放 在 同 一 个 父 节 点 的 两 个 子 节 点 上 , 并 在 其 父 节 点 上 标 上 子 节 点 的 概 率之和0.05+0.05=0.1。 ( 5 ) 继 续 这 样 的 合 并 , 每 一 步 都 将 两 个 节 点 合 并 到 一 个 父 节 点 之 下 , 对 于 两 个 概 率 相 同 的 可 以 任 意 挑 选 一 个 , 直 到 形 成 的 父 节 点 为 1 为 止 , 此 节 点 即 为 根 节 点 。 1 . 2 . 2 编码过程 分 别 给 建 成 的 最 优 二 叉 树 中 每 个 节 点 的 左 右 分 支 分 别 标 0 和 1 , 作 为 权 值 , 这 样 , 从根节点到每一个叶子节点有一条唯一的 路 径 , 读 出 每 条 路 径 上 的 权 值 就 会 产 生 一 个 对 应 节 点 的 唯 一 码 字。如 图1 所 示 , 二 叉 树 左 右 分 支 的 0 、1 标 号 并 不 是 确 定 的 , 本例 中 左 分 支 是 1 , 右 分 支 是 0 , 也 可 以 相 反 , 如 图2 所 示 。 上面这两种Huffman编码方式的平均 码 长 分 别 为 : 图 2 另一种编码 可 见 , 尽 管 这 两 种 编 码 设 定 不 同 , 但 它 们 都 有 相 同 的 平 均 码 长 , 要 真 正 实 现 压 缩 科技资讯 S C I E N C E & T E C H N O L O G Y I N F O R M A T I O N 29 

科技资讯 2009 NO.08 SCIENCE & TECHNOLOGY INFORMATION 表 1 压缩文件格式 还 得 对 新 的 编 码 进 行 按 位 存 储 。 2 哈夫曼编码具体实施 2 . 1 压缩思想 由 于 进 行 的 是 无 损 压 缩 , 所 以 要 扫 描 图 像 的 所 有 像 素 点 ,压 缩 过 程 分 为 四 步 : ① 扫 描 统 计 像 素 出 现 的 概 率 并 按 大 小 排 列 ; ② 建 立 最 优 二 叉 树 ;③ 哈 夫 曼 编 码 ; ④ 保 存 编 码 。 经 过 哈 夫 曼 编 码 后 的 图 像 中 的 不 同 像 素 分 别 用 不 同 长 度 二 进 制 编 码 表 示 , 接 下 来 的 工 作 就 是 保 存 重 编 码 后 的 像 素 , 由 于 无损压缩中编码前后一幅图像的像素点数 是 相 同 的 , 如 果 仍 然 以 像 素 为 单 位 保 存 图 像 数 据 就 无 法 实 现 压 缩 功 能 , 能 够 实 现 压 缩是因为编码前后表示像素的二进制编码 的 位 数 有 所 变 化 , 所 以 , 应 该 对 重 编 码 后 的 二进制位按位存储,由于VB6.0中没有移位 运 算 , 但 是 可 以 通 过 乘 2 、除 2 操 作 实 现 左 移、右 移。当 编 码 结 束 后, 各 像 素 的 哈 夫 曼 编码存放在hufbm(1 to 256) 中,在保存时, 把 所 有 像 素 的 哈 夫 曼 编 码 连 成 一 串 , 然 后 每 8 位 ( 字 节 ) 转 换 为 整 型 数 据 , 存 储 的 是 转 换 后 的 整 型 数 据 。 2 . 2 解压思想 压 缩 文 件 的 文 件 结 构 如 表 1 在 文 件 头 部分可利用像素与文件头的偏移量距离位 置 计 算 文 件 头 和 全 表 的 长 度 , 从 而 得 到 哈 夫 曼 编 码 树 的 起 始 位 置 。 解 码 过 程 : (1)指向huffman树的树根。 (2)根据当前一位编码为0或1从而指向 左 或 右 儿 子 节 点 。 ( 3 ) 判 断 该 节 点 的 左 , 右 儿 子 是 否 是 空 ( 即 为 0 ) 不 是 则 向 后 扫 描 一 个 编 码 , 执 行 上 一 步 , 如 是 则 完 成 一 个 解 码 , 该 叶 子 节 点 的 数 组 下 标 即 为 像 素 值 , 继 续 解 下 一 个 。 在 解 码 过 程 中 需 要 把 按 位 存 储 的 编 码 读 取 出 来 ,这 个 过 程 就 是 按 位 读 取 , 由 于 压 缩的文件长度大多小于30K, 那么编码部分 必将小于30K,VB6.0中字符型(string)的变 量最长可达65535个字符, 所以可将编码部 分一次性读取,构造一个自定义函数dtoo(s as byte), 该函数的功能是将byte型的变量 转 变 成8 位 二 进 制 数 。 至 此 , 关 于 哈 夫 曼 编 码 的 几 个 重 要 模 块 的 实 现 算 法 已 经 介 绍 完 , 通 过 模 块 测 试 都 能 达 到 预 期 效 果 , 把 这 几 个 模 块 集 成 即 可形成一个基于哈夫曼编码的图像压缩系 统( 其 中 使 用 了 一 些 用 户 自 定 义 类 型、变 量 信 息 技 术 和 关 于 图 像 的 信 息 的 常 量 , 都 在 程 序 的 公 用 模 块 中 有 定 义) 。 3 结语 图 像 压 缩 技 术 , 是 当 前 很 热 门 和 实 用 的 信 息 技 术 , 图 像 压 缩 技 术 研 究 了 几 十 年 , 取 得 了 很 大 的 成 绩 ,但 还 有 许 多 不 足 , 值 得 我们进一步研究。Huffman编码压缩作为一 种 简 单 高 效 的 编 码 方 法 , 在 文 本 , 图 像 , 音 频 等 压 缩 技 术 中 都 有 着 广 泛 的 应 用。从 整 个课题中可以看到,Huffman编码算法只对 图 像 压 缩 一 次 , 要 想 提 高 压 缩 比 , 可 以 对 图 像 进 行 两 次 压 缩 或 多 次 压 缩。另 外, 还 可 以 与 人 眼 视 觉 特 性 相 结 合 实 现 有 损 压 缩。总 之 , 图 像 压 缩 是 一 个 非 常 有 发 展 前 途 的 研 究 领 域 , 这 一 领 域 的 突 破 对 于 我 们 的 信 息 生 活 和 通 信 事 业 的 发 展 有 着 深 远 的 意 义 。 参考文献 [1] 田青 图像压缩技术[J].警察技术,2002 ( 1 ) : 3 0 ～ 3 1 . [2] 王新成.高级图像处理技术[M].第一版, 北 京 , 中 国 科 学 技 术 出 版 社 , 2 0 0 1 . [3] 孙仲康,等.数字图像处理及其应用[M]. 北 京 , 国 防 工 业 出 版 社 , 1 9 8 5 . [ 4 ] 董 士 海, 等 . 图 像 格 式 编 程 指 南 [ M ] . 北 京 , 清 华 大 学 出 版 社 , 1 9 9 4 . 《科技资讯》期刊投稿要求及说明 稿件要求 1 、稿 件 应 具 有 科 学 性、先 进 性 和 实 用 性，论 点 明 确、论 据 可 靠、数 据 准 确、逻 辑 严 谨、文 字 通 顺 。 2、计量单位以国家法定计量单位为准；统计学符号按国家标准《统计学名词及符号》的规定书写。 3、所有文章标题字数在20字以内。 4、参考文献应引自正式出版物，在稿件的正文中依其出现的先后顺序用阿拉伯数字加方括号在段末上角标出。 5、参考文献按引用的先后顺序列于文末。 6 、正 确 使 用 标 点 符 号，表 格 设 计 要 合 理，推荐使用三线表。 7 、图 片 要 清 晰，注 明 图 号 。 投稿说明 1、稿件须以电子文档形式发送。如为打印稿，请附软盘，软盘采用Word格式。请勿一稿多投。来稿一律不退，请作者自留底 稿 。 2、本刊已加入《中国学术期刊(光盘版)》、《中文科技期刊数据库》、《万方数据数字化期刊群》等网络媒体，本刊发表的文章 将在网络媒体上全文发布。 3、本刊编辑部对来稿有修改权，不愿改动者请事先说明。自收稿之日起1个月内未收到用稿通知，作者可自行处理。 4 、来 稿 请 注 明 作 者 姓 名、单 位、通 讯 地 址、邮 编、联 系 电 话 及 电 子 信 箱 。 5、如有一稿多投、剽窃或抄袭行为者，一切后果由作者本人负责。 30 科技资讯 S C I E N C E & T E C H N O L O G Y I N F O R M A T I O N