EZW算法的实现及其应用

《EZW算法的实现及其应用》由会员分享，可在线阅读，更多相关《EZW算法的实现及其应用（4页珍藏版）》请在金锄头文库上搜索。

1、2004 年 4 月 第 20 卷第 2 期武警工程学院学报JOURNAL OF EN GG COLL EGE OF ARMED POL ICE FORCEApr. 2004 Vol. 21 No. 2【研究生论文选登】EZW 算法的实现及其应用张孝杰张专成(武警工程学院 研究生队 ,陕西 西安 710086)【摘要】 嵌入式小波零树 ,即 EZW 图像编码算法由于其优越的压缩性能 ,引起了人们的普遍关注 。 根据 EZW 算法的基本原理 ,可优化出编码实例并得出相应实验结果 。 【关键词】 小波变换 ;嵌入式编码 ;渐进量化引言 图像是信息交流最为重要的载体 ,同时也是含信息量最大的信号之一

2、 ,正因为这样 ,图像给信息的传输 和存储提出了很大的挑战 。由于压缩算法对数据容量有着显著的影响 ,所以 ,人们一直在探索不同的图像压 缩编码 ,来提高压缩比 ,同时改善恢复质量 。1993 年 Shaprio 提出的嵌入式小波零树图像编码算法 ( EAW : Embedded zerotree wavelet coding algorithm) ,由于充分利用小波系数的不同尺度对应空间的相关性 ,使图像 压缩编码技术提高到了一个新的水平 。1变换编码系统的基本组成 典型的低比特率图像变换编码系统包括三部分 :变换 ,量化和数据压缩 ,如图 1 所示 。原始图像经过变 换产生变换系数 ,目的

3、是去相关性 ,变换过程认为是无损的 。为了使代码能在低比特率下进行熵编码 ,变换 系数经过量化生成代码流 ,量化过程是损耗信息的主要地方 。代码流在数据压缩阶段被尽可能的压缩 ,这也 是个无损压缩过程 。对 EZW 算法来说 ,图 1 中的变换器指的就是离散小波变换 。图像 变换系数 代码流 比特流 图 1 通用变换编码器图图 2 小波零树结构图图 3 小波零树编码扫描顺序图 收稿日期 :2003 - 11 - 06第一作者 :张孝杰(1979 ) ,男 ,湖南洞口人 ,2001 年毕业于武警工程学院通信工程系 ,现为武警工程学院研究生队学员。变换器(无损和 去相关)量化器(有损)压缩器(高效

4、无损)22EZW 算法原理 2. 1零树结构 一幅图像经过 M 层小波分解形成 3M + 1 个子频带 ,图 2 为图像经 3 层小波分解的示意图 。零树结构 中每个父系数有四个子系数 ,每个子系数像他们的父系数一样 ,又有四个子系数 ,依次类推 。较低频率子带 中的系数在邻近较高频带中含有四个子系数 ,这些子系数中的每个系数又都有四个子系数在邻近高频带中 , 如图 2 所示 。子系数与父系数的空间位置的相关性 ,对 EZW 算法中存储系数的位置信息是十分重要的 。 零树中系数的绝对值从父系数到子系数有下降趋势 。这个特性对 EZW 算法特别重要 ,因为如果一个系数 发现是不重要的 ,他的所有

5、后代系数将在很大程度上也是不重要的 ,所以这个树将认为不含任何重要信息 , 被定义为零树 。用这种方法 ,整棵零树就可用一个代码来表示 ,达到了数据压缩的目的 。2. 2算法原理 给定一幅图像 ,图像压缩程序将对他进行二维离散小波变换 。将变换结果传给 EZW 算法 ,量化器对其 进行量化 ,根据公式 T0 = 2 log ( k) 求得初始阈值其中 T0 初始阈值 , k 为系数的最大绝对值 。由此可以看出 , 初始阈值为小于系数最大绝对值 2 的最大整数次方 。运用初始阈值 ,对所有系数进行主扫描 ,确定哪些是绝 对值大于初始阈值即重要的 。完成主扫描后 ,当前阈值减半 ,然后进行辅扫描

6、,它是对重要系数的细节信息 进行渐进编码 。这个过程 (从主扫描开始) 反复进行直到希望的精度实现为止 ,如图 4 所示 。希望的精度是指阈值达到最小值或者是预定的性能指标实现 。最常用的性能指标是压缩后图像的每像 素比特数 ,当达到预定的每像素比特数就停止编码 。因为每像素比特数是可以可控的 ,这可以确保准确的压 缩比 。另一个性能指标是编码误差 ,追踪原始图像和重构图像间最大绝对值像素误差 ,当误差落入预定范围 时停止编码 。2. 3主扫描图 4EZW 算法原理流程图图 5 主扫描原理流程图在当前阈值下 ,主扫描扫描系数确定重要系数和零树 。它生成四个代码 : POS ,N EG , ZT

7、R , IZ。POS(正 系数) 表示大于阈值的正系数 ,用 p 表示 ;N EG(负系数) 表示绝对值大于阈值的负系数 ,用 n 表示 ; ZT (零树 根) 表示零树 ,用 t 表示 ; IZ(弧立零) 表示自身小于阈值但却有重要的后代数存在 ,用 z 表示 。这些代码传递 给熵编码器来消除代码间的冗余 。图 5 说明了主扫描怎样选择输出代码 。第一步检查当前系数是否是已检 出的重要系数 ,如果是就跳过 ,不输出任何代码 。如果系数在当前阈值下是重要的 ,系数绝对值减去阈值后 加到辅助列表 ,同时输出 P 或者 n 。辅助列表记录所有的重要系数 。如果系数在当前阈值下是不重要的 ,下 一步

8、则检查该系数是否为已检出零树的子系数 ,如果是 ,不输出任何代码 ;否则为新的零树根或者是孤立零 , 输出相应的代码 t 或者得 z。82系数的扫描顺序十分重要 。低频带中的系数必须先于高频带中的系数扫描 ,目的是充分最大化用零树 结构编码非重要系数获得的增益 。但是 ,子带内的扫描顺序可以不同 。最普遍的扫描顺序是 Morton 顺序 , 如图 3 所示 ,其中子带内的扫描是按 Morton 顺序进行 ,低频带总是先被扫描 。其他扫描方法也可以用 ,只要 最低频带被最先扫描 。2. 4辅扫描 主扫描是 EZW 的核心 ,辅扫描是对系数的进一步细化 。辅扫描检查辅助列表中的每个系数 ,如果大于

9、 当前阈值输出“1”到熵编码器 ,否则输出“0”到熵编码器 。图 6 为辅扫描过程的流程图 。2. 5 解码图 6 辅扫描流程图图 7 3 层小波分解图解码是编码的逆过程 。EZW 解码仍然采用主扫描和辅扫描 。主扫描从数据流中载入主扫描代码来恢 复系数的重要信息 。采用与编码时保存系数重构位置同样的扫描顺序是至关重要的 。当碰到代码 p 或者 n ,当前系数的位置加入输助列表 。当图像中的所有系数已被扫描 ,主扫描就停止 。辅扫描从数据流中为辅 助列表中的每个系数载入 1 个比特 。这个比特与当前阈值相乘后加到正系数上或者从负系数中减去 。当预 定的性能指标达到或者数据流已为空时 ,解码就停

10、止 。3编码举例以图 7 所示 3 层小波分解的 8 3 8 系数矩阵为例 ,运用 EZW 算法对其进行编码 。Di 为第 i 次主扫描编 码结果 ,Si 为第 i 次辅扫描编码结果 。编码结果如下 :D1 :pnztptttztttttttptt S1 :1010D2 :ztnptttttttt S2 :100110D3 :zzzzzzppnppnttnnptpttnttttttttptttptttttttptttttttttttt S3 :10011101111011011000D4 :zzzzzzztztznzzzzpttptpptpnptnttttttptpnpppptttttptpt

11、ttpnp S4 :11011111011001000001110110100010010101100D5 :zzzzztzzzzztpzzzttpttttnptppttptttnppnttttpnnpttpttppttS5 :10111100110100010111110101100100000000110110110011000111D6 :zzzttztttztttttnnttt 4实验结果 与 J PEG算法相比 , EZW 算法具有允许用户选择目标比特率的突出优点 ,J PEC 史允许用户设定品质因 子 。对于 8bpp , 512 3 512Barbara 图 , 在同一比特率下进

12、行编码实验 , 比特率选择为 01399bpp , 字节数为 12886 ,用 J PEG编码峰值信噪比 PSNR 为 26199dB ;用 EZW 编码峰值信噪比 PSNR 为 29139,明显地高于 JDEG编码 。在同一信噪比下进行编码实验 ,峰值信噪比 PSNR 选择为 26199 ,用 J PEG 编码结果比特率为83(责任编辑 :余炳毛)01399bpp ,字节数为 12886 ;用 EZW 编码 ,结果比特率为 0127bpp ,字节数为 8820 ,明显地低于 J PEG 编码 。 从视觉效果上看 ,在同样比特率下 , EZW 重构图像明显好于 J PEG 重构图像 ,虽然两者

13、都有信息损耗 ,但在 J PEG重构图像中有明显的马赛克现象 。5结束语 EZW 算法是一种简单 ,高效的图像编码算法 ,它不要求图像的先验知识 ,也不要求大的内存容量 ,并且 采用了嵌入的方式 ,压缩效果也比较理想 ,而且允许用户自己的需要设定压编比 ,是一个具有很大潜力的编 码算法 。EZW 具有以上的优点是因为采用了四个新技术 :离散小波变换 ,零树编码 ,渐进量化和自适应算术 编码 。离散小波变换有效地消除了原始图像像素间的相关性 ,使大多数系数可以作为按指数增长的零树的 一部分被有效地编码 ;零树编码通过跨尺度预测不重要系数 ,获得了巨大的编码增益 ,远远超过了针对重要 图的一阶熵编

14、码 ;渐进量化通过对多级重要图采用零树编码 ,可使编码和解码在不同的位率下随时停止 ;自 适应算术编码进一步消除了比特流自身的冗余 。参考文献 : 1 Shapiro. Embedded Image Coding Using Zerotrees of Wavelet Coefficients. IEEE Trans. on Signal Processing ,1993 ,41 (12) ,3445 - 3463 . 2 Said A , Pearlman W A. A new fast and efficient image codec based on set partitioning i

15、n hierarchical tree. IEEE Transactions on Circuits and sys2 tems for Video Technology ,1996 ,6 (6) :243 - 249 . 3 黄贤武 ,王加俊 ,李家华. 数字图像处理与压缩编码技术. 电子科技大学出版社 ,2000 . 4 Amir Said , Example of Application for Image Compression ,1999 . 5 C. Valens. Embedded Zerotree Wavelet Encoding. 1999 . 6 Eduard Kriegl

16、er ,An implementation of the EZW algorithm. http : els. ee. sun. ac. za.中科院院士增选名单公布中国科学院院士增选每 两年进行一次 ,2003 年增选 了 58 名新院士 ,其中数学物 理学部 10 名 ,化学部 10 名 , 生物学部 11 名 , 地学部 10 名 ,技术科学部 17 名 。经过 这次增选 ,中国科学院院士 总人数为 688 人 ,陕西省现 在共有沈绪榜 、 保 铮 、 安 芷 生 、陈学俊 、 侯 洵 、朱显谟 、 周 尧和 、周惠久 、 鞠 躬 、 姚 熹 、 李 济生 、高鸿 、张国伟 、邢球痕 14 名中科院院士 。陕西省 14 名中科院院士 华商报2003. 11