《EZW算法的实现及其应用.doc》由会员分享，可在线阅读，更多相关《EZW算法的实现及其应用.doc（4页珍藏版）》请在三一办公上搜索。
1、EZW 算法的实现及其应用张孝杰张专成( 武警工程学院 研究生队 ,陕西 西安 710086)【摘要】 嵌入式小波零树 ,即 EZW 图像编码算法由于其优越的压缩性能 ,引起了人们的普遍关注根据 EZW 算法的基本原理 ,可优化出编码实例并得出相应实验结果 。【关键词】 小波变换 ;嵌入式编码 ;渐进量化引言图像是信息交流最为重要的载体 ,同时也是含信息量最大的信号之一 ,正因为这样 ,图像给信息的传输 和存储提出了很大的挑战 。由于压缩算法对数据容量有着显著的影响 ,所以 ,人们一直在探索不同的图像压 缩编码 ,来提高压缩比 ,同时改善恢复质量 。1993 年 Shap rio 提出的嵌入式
2、小波零树图像编码算法 ( EA W : Embedded zerot ree wavelet co ding algo rit hm) ,由于充分利用小波系数的不同尺度对应空间的相关性 ,使图像压缩编码技术提高到了一个新的水平 。1变换编码系统的基本组成典型的低比特率图像变换编码系统包括三部分 :变换 ,量化和数据压缩 ,如图 1 所示 。原始图像经过变 换产生变换系数 ,目的是去相关性 ,变换过程认为是无损的 。为了使代码能在低比特率下进行熵编码 ,变换系数经过量化生成代码流 ,量化过程是损耗信息的主要地方 。代码流在数据压缩阶段被尽可能的压缩 ,这也是个无损压缩过程 。对 EZW 算法来说
3、 ,图 1 中的变换器指的就是离散小波变换 。 图像图 1通用变换编码器图图 2 小波零树结构图图 3 小波零树编码扫描顺序图收稿日期 :2003 - 11 - 06第一作者 :张孝杰 ( 1979 ) ,男 ,湖南洞口人 ,2001 年毕业于武警工程学院通信工程系 ,现为武警工程学院研究生队学员 。变换器(无损和 去相关)变换系数量化器(有损)代码流压缩器(高效 无损)比特流2EZW 算法原理2 . 1零树结构一幅图像经过 M 层小波分解形成 3M + 1 个子频带 ,图 2 为图像经 3 层小波分解的示意图 。零树结构 中每个父系数有四个子系数 ,每个子系数像他们的父系数一样 ,又有四个子
4、系数 ,依次类推 。较低频率子带 中的系数在邻近较高频带中含有四个子系数 ,这些子系数中的每个系数又都有四个子系数在邻近高频带中 ,如图 2 所示 。子系数与父系数的空间位置的相关性 ,对 EZW 算法中存储系数的位置信息是十分重要的 。零树中系数的绝对值从父系数到子系数有下降趋势 。这个特性对 EZW 算法特别重要 ,因为如果一个系数发现是不重要的 ,他的所有后代系数将在很大程度上也是不重要的 ,所以这个树将认为不含任何重要信息 ,被定义为零树 。用这种方法 ,整棵零树就可用一个代码来表示 ,达到了数据压缩的目的 。2 . 2算法原理给定一幅图像 ,图像压缩程序将对他进行二维离散小波变换 。
5、将变换结果传给 EZW 算法 ,量化器对其进行量化 ,根据公式 T0 = 2 lo g ( k) 求得初始阈值其中 T0 初始阈值 , k 为系数的最大绝对值 。由此可以看出 ,2初始阈值为小于系数最大绝对值 2 的最大整数次方 。运用初始阈值 ,对所有系数进行主扫描 ,确定哪些是绝对值大于初始阈值即重要的 。完成主扫描后 ,当前阈值减半 ,然后进行辅扫描 ,它是对重要系数的细节信息 进行渐进编码 。这个过程 (从主扫描开始) 反复进行直到希望的精度实现为止 ,如图 4 所示 。希望的精度是指阈值达到最小值或者是预定的性能指标实现 。最常用的性能指标是压缩后图像的每像 素比特数 ,当达到预定的
6、每像素比特数就停止编码 。因为每像素比特数是可以可控的 ,这可以确保准确的压 缩比 。另一个性能指标是编码误差 ,追踪原始图像和重构图像间最大绝对值像素误差 ,当误差落入预定范围 时停止编码 。图 4 EZW 算法原理流程图图 5 主扫描原理流程图2 . 3 主扫描在当前阈值下 ,主扫描扫描系数确定重要系数和零树 。它生成四个代码 : PO S ,N E G , ZTR , IZ。PO S ( 正 系数) 表示大于阈值的正系数 ,用 p 表示 ; N E G(负系数) 表示绝对值大于阈值的负系数 ,用 n 表示 ; ZT ( 零树根) 表示零树 ,用 t 表示 ; IZ(弧立零) 表示自身小于
7、阈值但却有重要的后代数存在 ,用 z 表示 。这些代码传递给熵编码器来消除代码间的冗余 。图 5 说明了主扫描怎样选择输出代码 。第一步检查当前系数是否是已检 出的重要系数 ,如果是就跳过 ,不输出任何代码 。如果系数在当前阈值下是重要的 ,系数绝对值减去阈值后 加到辅助列表 ,同时输出 P 或者 n 。辅助列表记录所有的重要系数 。如果系数在当前阈值下是不重要的 ,下结构编码非重要系数获得的增益 。但是 ,子带内的扫描顺序可以不同 。最普遍的扫描顺序是 Mo rto n 顺序 ,如图 3 所示 ,其中子带内的扫描是按 Mo rto n 顺序进行 ,低频带总是先被扫描 。其他扫描方法也可以用
8、,只要 最低频带被最先扫描 。2 . 4辅扫描主扫描是 EZW 的核心 ,辅扫描是对系数的进一步细化 。辅扫描检查辅助列表中的每个系数 ,如果大于 当前阈值输出“1”到熵编码器 ,否则输出“0”到熵编码器 。图 6 为辅扫描过程的流程图 。图 6 辅扫描流程图图 7 3 层小波分解图2 . 5 解码解码是编码的逆过程 。EZW 解码仍然采用主扫描和辅扫描 。主扫描从数据流中载入主扫描代码来恢 复系数的重要信息 。采用与编码时保存系数重构位置同样的扫描顺序是至关重要的 。当碰到代码 p 或者 n ,当前系数的位置加入输助列表 。当图像中的所有系数已被扫描 ,主扫描就停止 。辅扫描从数据流中为辅
9、助列表中的每个系数载入 1 个比特 。这个比特与当前阈值相乘后加到正系数上或者从负系数中减去 。当预 定的性能指标达到或者数据流已为空时 ,解码就停止 。3编码举例以图 7 所示 3 层小波分解的 8 3 8 系数矩阵为例 ,运用 EZW 算法对其进行编码 。Di 为第 i 次主扫描编 码结果 ,Si 为第 i 次辅扫描编码结果 。编码结果如下 :D1 :p nztp t t tzt t t t t t tp t tS1 :1010D2 :zt np t t t t t t t tS2 :100110D3 :zzzzzzpp npp nt t nnp tp t t nt t t t t t t
10、 tp t t tp t t t t t t tp t t t t t t t t t t t tS3 :10011101111011011000D4 :zzzzzzztztznzzzzp t tp tpp tp np t nt t t t t tp tp npppp t t t t tp tp t t tp npS4 :11011111011001000001110110100010010101100D5 :zzzzztzzzzztpzzzt tp t t t t np tpp t tp t t t npp nt t t tp nnp t tp t tpp t tS5 :1011110011
11、0100010111110101100100000000110110110011000111D6 :zzzt tzt t tzt t t t t nnt t t4实验结果与 J P E G 算法相比 , EZW 算法具有允许用户选择目标比特率的突出优点 ,J P EC 史允许用户设定品质因 子 。对于 8bpp , 512 3 512Barbara 图 , 在同一比特率下进行编码 实 验 , 比 特 率 选 择 为 01399bpp , 字 节 数 为12886 ,用 J P E G 编码峰值信噪比 PSN R 为 26199dB ;用 EZW 编码峰值信噪比 PSN R 为 29139,明显
12、地高于J D E G 编码 。在同一信噪比下进行编码实验 ,峰值信噪比 PSN R 选择为 26199 ,用 J P E G 编码结果比特率为01399bpp ,字节数为 12886 ;用 EZW 编码 ,结果比特率为 0127bpp ,字节数为 8820 ,明显地低于 J P E G 编码 。从视觉效果上看 ,在同样比特率下 , EZW 重构图像明显好于 J P E G 重构图像 ,虽然两者都有信息损耗 ,但在J P E G 重构图像中有明显的马赛克现象 。5 结束语EZW 算法是一种简单 ,高效的图像编码算法 ,它不要求图像的先验知识 ,也不要求大的内存容量 ,并且 采用了嵌入的方式 ,压
13、缩效果也比较理想 ,而且允许用户自己的需要设定压编比 ,是一个具有很大潜力的编码算法 。EZW 具有以上的优点是因为采用了四个新技术 :离散小波变换 ,零树编码 ,渐进量化和自适应算术编码 。离散小波变换有效地消除了原始图像像素间的相关性 ,使大多数系数可以作为按指数增长的零树的 一部分被有效地编码 ;零树编码通过跨尺度预测不重要系数 ,获得了巨大的编码增益 ,远远超过了针对重要 图的一阶熵编码 ;渐进量化通过对多级重要图采用零树编码 ,可使编码和解码在不同的位率下随时停止 ; 自适应算术编码进一步消除了比特流自身的冗余 。参考文献 :Shapiro . Embedded Image Co d
14、ing U sing Zerot rees of Wavelet Coefficient s. I EEE Trans. o n Signal Processing ,1993 ,41 ( 12) ,3445 - 3463 .Said A , Pearlman W A. A new fast and efficient image co dec based o n set partitio ning in hierarchical t ree . I EEE Transactio ns o n Circuit s and sys2tems fo r Video Technology ,1996
15、 ,6 ( 6) :243 - 249 .黄贤武 ,王加俊 ,李家华. 数字图像处理与压缩编码技术. 电子科技大学出版社 ,2000 . Amir Said , Example of Applicatio n fo r Image Co mp ressio n ,1999 .C. Valens. Embedded Zerot ree Wavelet Enco ding. 1999 .Eduard Kriegler ,An implementatio n of t he EZW algo rit hm. ht tp : els. ee . sun . ac . za .(责任编辑 :余炳毛)12
16、3456中科院院士增选名单公布陕西省 14 名中科院院士中国科学院院士增选每两年进行一次 ,2003 年增选 了 58 名新院士 ,其中数学物 理学部 10 名 ,化学部 10 名 , 生物 学 部 11 名 , 地 学 部 10名 ,技术科学部 17 名 。经过 这次增选 , 中国科学院院士 总人数为 688 人 , 陕西省现 在共 有 沈 绪 榜 、保 铮 、安 芷 生 、陈学俊 、侯洵 、朱显谟 、周尧和 、周惠久 、鞠躬 、姚熹 、李 济生 、高鸿 、张国伟 、邢球痕14 名中科院院士 。( 华商报2003 . 11 . 25 .第 3 版)姓名工作单位研究领域沈绪榜箭载计算机等方面保
17、 铮西安电子科技大学雷达和雷达信号处理等方面安芷生中科院 西安分院第四纪地质和全球变化等方面陈学俊西安交通大学多相流热物理学 、动力工程等方面侯 洵西安光机所瞬态光学技术等方面朱显谟中 国 科 学 院 西 北 水土保持研究所土壤研究等方面周尧和西北工业大学铸造学科的现代理论和铸造工程技术等方面周惠久西安交通大学材料工程技术等方面鞠 躬第四军医大学神经系统与免疫系统研究和中枢神经系统再生的方法 研究等方面姚 熹西安交通大学纳米材料科学等方面李济生西安卫星测控中心卫星测控中心精密轨道确定等方面高 鸿西北大学近代极谱分析基础理论和新技术 、新方法和研究等方面张国伟西北大学造山带和前寒武纪地质研究等方面邢球痕航天四院多种战略 、战术导弹固体发动机等方面
