整数小波的有损与无损图像压缩

整数小波的有损与无损图像压缩 第 3 1 卷 第 4 期Vol . 31 No . 4 光 学 技 术 2 0 0 5 年 7 月 J uly 2005 O P T ICAL T ECHN IQU E () 文章编号 : 100221582 20050420509204 Ξ 整数小波的有损与无损图像压缩 孙文军 , 赵海鹰 , 窦晓鸣 () 上海交通大学 , 上海 200030 摘 要 : 提出了基于整数小波变换的有损与无损图像编码 。有损编码采用无链表的 SP IH T 零树编码算法 ,它 不同于 SP IH T 和 L ZC 算法的零树分割策略和状态比特表结构 。该算法所需的存储空间小 ,有损压缩性能高 ,易于硬件 的实现 。无损编码根据不同子带小波系数的分布特性 ,采用带间预测编码 ,不同方向的子带采用不同的预测方式 ,预测 误差采用霍夫曼编码 。测试结果 ,基于整数小波的无链表有损压缩方案不仅优于 L ZC ,接近于 SP IH T ,而且易于硬 件的实现 。 关 键 词 : 整数小波变换 ; SP IH T ; L ZC ; 带间预测编码 中图分类号 : O438 ; TP391 文献标识码 : A Image coding with l ossy an d l ossless compression on integer wavelet transf orm SUN We n-jun , ZHAO Hai- ying , DOU Xiao- ming ( )Shanghai J iaoto ng U niversity , Shanghai 200030 , China Abstract : Image loss coding algorit hm and lossless coding algorit hm based o n integer wavelet t ransform were p roposed. In t he former , SP IH T wit hout list was used , t hat was different f ro m SP IH T and L ZC in zerot ree segmentatio n and bit list of state , in additio n , being wit h lit tle memory space. In t he lat ter , different p redictio ns o n each subband were adop ted. Basing o n different dist ributing p ropert y of wavelet coefficient s , p redictio n errors were encoded by Huff man. The experimental result s in2 dicate t hat t he p roposed algorit hm based o n integer wavelet are superior to L ZC and close to SP IH T , in additio n , being benefi2 cial to realizing of co mp ressio n system o n hardware. Key words : integer wavelet t ransform ; set partitio ned embedded block coder ; listless zero- t ree coding ; D PCM in subband 低了 0 . 5dB 左右 。而 EZW 和 SP IH T 的最 大 不 足 1 引言 在于 :在存储重要系数坐标和重要集合链表时所需 的存储空间较大 ,相应的存储器对读写操作要求较 多媒体图像技术的迅速发展对图像压缩技术提 出了严格的要求 。一方面 ,要求图像为高质量的无 多 ,硬件实现起来比较困难 。本文结合三者的优点损压缩 ;另一方面 ,有损压缩的需求也越来越高 。数 提出了改进的无链表的 SP IH T 编码算法 ,该算法在 较低的存储空间下可获得较高的压缩性能 ,易于硬 字图像所含有的大部分细节是人类不能敏感的 ,应 件的实现 。 尽可能地去除对人类不敏感的细节信息 ,以保证重 构图像的视觉效果 。对于大的图像数据库来说 ,图 整数小波变换2 像的快速识别是非常重要的 ,希望解码时得到所需 2 . 1 提升方案的基本原理 的图像分辨率 。 1 ( ) Shapiro 的内嵌零树编码 EZW已成为 提升方案主要分为以下三个步骤 。图 1 给出了 提升的基本结构与步骤 。在极低 比 特 率 情 况 下 图 像 压 缩 的 里 程 碑 。Said 和 2 () 1剖分 。把离散的原始样本 c分成偶数样 ( ) Pearlman 提出的集合树分裂算法 SP IH T已获得 j - 1 ( ) ( ) ( ) 本 x 和 奇 数 样 本 x 。x k = c2 k , x k= e o e j - 1 o 了比 EZW 更有效的零树编码 , 成为小波内嵌编码 ( ) c2 k + 1。 算法的通用基准 。Wen- Kuo Lin 提出的无链表零树 j - 1 7 () ( ) ( ) ( ) ( ) 编码算法 L ZC只采用两个比特位来表示系数和 2预测 。d k= x k- p [ x k] 偶数样 j o e ( 集合信息 ,它没有对 L 集合 L 的具体定义将在后 本保持不变 , 利用插值细分来预测奇数样本 , 奇数样 ) 面详细介绍进行编码 ,使得压缩性能比 SP IH T 降 本与预测值之间的差值称为细节系数 , 又称为小波 Ξ 2ma il : sunwj @sjt u. edu. cn E收稿日期 : 2004201211 ; 收到修改稿日期 : 2004209202 ( ) 作者简介 : 孙文军 1975- ,男 , 江苏省人 ,上海交通大学博士后 ,主要从事遥感图像信息处理 、奇异信号检测 、图像压缩及传输 、影像光 学与图像处理方面的研究 。 表示高通分解滤波器的消失矩阶数 ; 1 表示高通合 成滤波器的消失矩阶数 。文献 3 给出了几种常用 的整数小波 。 无损压缩3 3 . 1 预测编码( D PCM) 图 1 提升方案 系数 ,其值越小表明奇数样本预测值越准确 。预测算 图像经小波变换分解后 ,最低频子带的小波系 子 P 的构造需要考虑原始信号本身的特点 , 能反映 数代表了原始图像的平均 数据的相关关系 。在具体应用时 , 不可能由偶数样本 值 ,幅值比较大 ,几乎集中 了x 完全准确地预测奇数样本 x 的值 , 但要保证预测 e o 原 图 像 近 90 %的 能 量 。 值尽可能的接近 , 只有这样 , 得到的小波系数才会比 为了 保 证 图 像 的 重 构 质 较小 。数据的相关性越强 , 大多数小波系数的值就越 量 , 本 文 对 这 部 分 小 波 系 小 。 预测算子用预测函数来表示 ,预测函数通过插 数采用 D PCM 进行预测 , 值细分方法构造 。常用的插值细分方法有 : 分段线 2 带内和带间小波图 尽量减小预测误差 。如图 性插值和三次样条插值 。从频域的角度来看 ,小波 系数的相邻关系 2 所示 , X 为待预测像素 ,系数表示原始数据的高频成分 ,是 c恢复到 c时 j j - 1 A , B 和 C 分 别 为 X 的 相 邻 像 素 。预 测 方 案 详 见 所需的细节分量 。相应地 , 称 c为提升型系数 ,表示 j 8 J P E G 预测编码器 。 原始数据的低频成分 。 () 3 . 2 带间预测编码 内预测编码() 3更新 。为了保持能量守恒 ,小波分解的平 图像经小波分解后 ,每层都有水平 、垂直和对角 滑 分 量 需 要 利 用 小 波 系 数 值 更 新 , 以 满 足 三个方向的高频子带 。不同方向的子带可以采用两 种不同的预测方式 : 人类视觉系统对水平和垂直方 j - 1 j 向上的信息较敏感 ,这两个方向上的小波系数采用 ( ) ( ) ( ) ( ) 1/ 2 ck = 1/ 2 ck = mean , 也j j - 1 ?? k k () 式 1进行预测 ;人类视觉系统对对角方向的信息并 ( ) 就是说 , 最后一级分解所得的系数 直流分量的平 不敏感 ,但又要保证对角方向的信息损失较小 ,所以 均值mean 与原始信号的平均值相等 。更新算子 U 应 () 本文对对角方向的小波系数采用式 2进行预测 ,这 ( ) ) ( ) ( ) ( 该满足 ck= x + U d = c2 k + U d , 其 j e j j j 样就可以减小视觉冗余 ,也就是说可以去除像素之 中偶数成分为低通系数 , 奇数成分为高通系数 。 间的相关性 。图 2 中 , HC , V C 和 D C 分别为水平子 2 . 2 整数小波变换带 、垂直子带和对角子带的待预测像素 , U 和 L 为其 最简单的整数变换是 Haar 小波变换的变形 ,称相邻像素 。预测误差 e = C- P , 预测值P 为 N , 定义一步为 S 变换 。给出源信号 s , n = 1 , 2 , n 1 ( )P = | U + L | 1 S 变换为 c和 d 序列 :n n 8 d = s- s j , l j - 1 , 2 l + 1 j - 1 , 2 l 1 ( )2 P = | V C + HC | 8 d j , ls= s+ j , l j - 1 , 2 l 2 由于高频子带小波系数本来就比较小 ,所以经 ,〃 表示取整运算 。c为近似系数或低通系式中 n 过预测得到的误差值也大多在 - 128, + 127 之间 , 数 , d 为细节系数或高通系数 。在 S 变换之后 , 对低 n 只有极少数落在 - 128 , + 127 之外 。由于误差值 通系数进行线性预测 , 以产生新的高通系数, 这d j , l 是用两个字节表示的 ,所以为了进一步提高编码效 就是 S + P 变换 :率 ,在哈夫曼编码之前 ,先作如下处理 :编码时 ,若误 ( )1 = s- sd j , l j - 1 , 2 l + 1 j - 1 , 2 l差值大于 127 ,则先将误差值减去 127 ,记下该误差 ( )1 d j , l 出现的位臵 ,再进行编码 ;若误差值小于 - 128 ,则先 s= s+ j , l j - 1 , 2 l 2 将误差值 加 上 128 , 记 下 误 差 值 的 位 臵 , 再 进 行 编 ( )1 α( ) d = d + s- s+ j , l j , l - 1 j , l - 2 j , l - 1 码 。经过以上处理后 ,系数都落在 - 128, + 127 之 ( )1 α( ) α( ) βs- s+ s- s- d α0 j , l - 1 j , l 1 j , l j , l + 1 1 j , l + 1 当 - 间 ,可以用一个字节表示 。解码时 ,根据超过范围的 βαα= = 0 , 且= = 1/ 4 时 , 上式变为 Co2 hen- 1 1 0 1 误差个数以及坐标位臵 ,找到相应的误差 ,若误差值 () Daubechies- Feauveau 3 ,1双正交滤波器的整数 变 大于 或 等 于 零 , 则 将 误 差 值 加 上 127 , 否 则 , 减 去 ( ) 换形式 。Co hen- Daubechies- Feauveau 3 ,1中的 3 ( ( ) ) ( ) 128 ,这样就可以得到原来的值 。S C i , j = 1 , 则 输 出 C i , j 的 符 号 位 并 臵 n ( ) ( ) ( ) Fi , j = 1 ; 若 Fi , j = 1 , 则输出 C i , j 的第C C 4 有损压缩 n 层比特位 。 4 . 1 编码算法 ( ( ) ) ) ( ?若 Fi , j = 0 , 则 输 出 S D i , j ; 若D n 本文采用的无链表的 SP IH T 算法与 L ZC 的主( ( ( ) ) ) S D i , j = 1 , 则臵 Fi , j = 1 。n D 要区别在于 :在 L ZC 中 , L 集合没有进行重要性编 ( ) ( ) ?若 Fi , j = 0 , 且 Fi , j = 1 , 则 输 出D D 码 , 本文对 L 集合进行重要性编码 ,采用低频带优 ( ( ( ( ( ) ) ) ) ) S L i , j ; 若 S L i , j = 1 , 则臵 Fi , j =n n L 先的扫描顺序 ; 相对于 SP IH T 没有集合链表 ,只有 1 。 重要集合的标志 位 来 说 , 节 省 了 所 需 的 存 储 空 间 。 () 4高 频 子 带 编 码 。对 高 频 子 带 的 所 有 节 点具体算法描述如下 : ( ) C i , j 来说 ,有 :() () 1符号的定义如图 3 所示 。图 3 a给出了各 ( ( ) )() F C i , j = 1 , F i , j = 0 , 则输出?若 D C ( ) 集合之间的相互关系 ,图 3 b中的 F, F和 F分 C D L ( (( () ) ) ) ( 1 , 则输出 C i , j= S C i , j ; 若 S C i , j) n n 别表示小波系数 C , D 集合和 L 集合的重要性标志 () ) ( 的符号位 , 并臵 F i , j = 1 ; 若 F i , j = 1 , 则输 C C 所占的空间之间的大小关系 。 ( ) 出 C i , j 的第 n 层比特位 。 ( ( ) ) ( ) ?若 FP i , j = 1 , Fi , j = 0 , 则输出 L D ( ( ) ) ( ( ) ) ( ) S D i , j ; 若 S D i , j = 1 , 则臵 Fi , j =n n D ( ) ( ) ( ( ) 1 ; 若 Fi , j = 1 , 且 Fi , j = 0 Fi , j 存 D L L ) ( ( ( ) ) ( ) ) 在, 则输出 S L i , j ; 若 S L i , j = 1 , 则臵 n n ( ) Fi , j = 1 。 L () () 5改变量化级别 , n 减 1 ,转至执行 3。 解 码算法是编码算法的逆过程 ,只要把编码过 程的输出作为解码过程的输入即可 。图 3 小波系数的树结构 () ( ) 4 . 2 码流结构a集合关系 ; b三集合重要性所占的空间比例 。 图 4 给出了编码流的结构 。本文先对 L L 子带 ( ) ( ) C i , j :节点 i , j 处的小波系数 ; 进行扫描 ,因为 L L 子带几乎占有整个图像 90 %的 ( ) ( ) ( ) D i , j :节点 i , j 的所有后代 子孙的坐标 ( 能量 ,对重构图像的质量起决定性的作用 。这样既) ( ) ( 集合 , 不包括 i , j 点本身 。点 i , j 的直接后代 儿 保证了图像的恢复质量 ,同时也使得重构图像具有 ) 子的坐标 集 合 , 在 分 层 塔 形 结 构 的 最 高 层 R 有 渐进性 。 ( ) ) ( ) ( ( D i , j = { i + L L , j , i , j + L L , i + L L , j + ) ( ) ( ) L L } , 除 此 之 外 的 结 点 有 D i , j = { 2 i , 2 j , ( ) ( ( ) ) 2 i , 2 j + 1, 2 i + 1 , 2 j , 2 i + 1 , 2 j + 1} , 这里的 L L 为最高层 R 的尺度 ;图 4 码流结构 ( ) ( ) ( ) O i , j :节点 i , j 的所有直接后代 子孙的 ( ) 5 实验结果及分析坐标集合 , 不包括 i , j 点本身 ; ( ) ( ) L i , j :节点 i , j 除直接后代外所有后代坐 5 . 1 测试结果 标的集合 ; 3 () 本文采用 Daubechies 2 ,4整数小波变换,对( ) ( R i , j :所有根节点的坐标集合 最低频子带 ( ) 细节较丰富的 L ena 512 ×512 ×8bit s灰度图像进 ) 内; 行了测试 。图 5 给出了位率为 0 . 125bit / p m 时的重 ( ( ) ) P i , j :除根节点外 C i , j 的父亲节点坐标 ; 构图像 。测试结果表明 ,在压缩 64 倍时本文的有损 ( ) S T :判断系数或集合重要性的测试函数; n 压缩图像基本达到了 SP IH T 的重构效果 。)( ( ) ( ) logmax{ | C i , j| } , n =求出 2初始化 。 2 由表 1 可以看出 ,本文的无损压缩效果略低于 清空 F, F和 F。C D L L OCO- I 的压缩效果 , 明显高于 其 它 几 种 无 损 压 缩 () ( ) 3L L 子带编码 。对于 R i , j 内的所有节点 算法 ,但 本 文 算 法 的 复 杂 度 要 低 于 L OCO- I 算 法 。 ( ) C i , j 来说 ,有 :通过实验得知 ,对于某些图像来说 ,本文采用的无损 ( )( ( ) ) ?若 Fi , j = 0 , 则 输 出 S C i , j ; 若 C n 压缩算法要好于 L OCO- I 的压缩性能 。由此可见 , () () 本文基于整数的小波预测编码去相关能力强 ,能很512 ×1 + 1/ 4+ 1/ 16= 42 kbit s ,L ZC 压缩算法 ( ) 的存 储 空 间 为 512 ×512 ×1 + 1/ 4 = 40 kbit s 。 好地消除像素之间的相关性 ,具有较好的无损压缩 由此可见 ,本文描述的有损压缩算法所需的存储空 ( 效果 。其 中 L OCO- I Low co mplexit y lo ssless co m2 间相对于 SP IH T 算法降低了 2 个数量级 。) p ressio n fo r images用 在 J P E G2000 的 无 损 压 缩 器 ( ) 上 ; PN G Po rtable net wo r k grap hics为 网 络 图 形 和 结 论6 图像传输格式 。() 1整 数 小 波 变 换 完 全 可 以 可 逆 的 重 构 源 信 号 ,相对于浮点运算来说 ,计算起来比较容易 ,不必 ( 考虑计算机的截断误差和较复杂的信号延拓 包括 ) 对称延拓和周期延拓所带来的信号数据损失 ,这是 本文只所以能取得好的无损压缩效果和较高图像恢 ()( )()a b c 复质量的前提 。 图 5 L ena 图像的有损压缩效果 () 2试验结果证明 ,本文的有损压缩算法所需要 () ( ( ) ) a原始图像 ; bSP I H T 重构图像 位率为 0 . 125bit / p m; 的存储量低 ,运算复杂度低 ,压缩效果与 SP IH T 基 () ( ) c本文重构图像 位率为 0 . 125bit / p m。 本一致 ,为今后系统硬件的实现提供了有利的条件 。 表 1 无损编码算法的性能比较参考文献 : 方法L ena 图像方法L ena 图像1 Shapiro J M . Embedded image co ding using zerot ree of wavelet co2 Huff man7 . 468bit s/ p mJ P E GL S5 . 501bit s/ p mefficient sJ . I EEE Transactio ns o n Si gnal Processing , 1993 , 41 ( ) 12:3445 —3462 . WinRar6 . 600bit s/ p mPN G4 . 96bit s/ p m2 Said A , Pearlman W A. A new , fast , and efficient ima ge co dec Raw + WinZip6 . 352bit s/ p mL OCO- 14 . 19bit s/ p mbased o n set partitio ning in hierarchical t rees J . I EEE Transac 2 SP I H T + 算术编码4 . 478bit s/ p m本文带间预测4 . 33bit s/ p mtio ns o n Circuit s Syst . Video Technol , 1996 ,6 :243 —250 . 3 Calderbank A R , et al . Lo ssless ima ge co mp ressio n using integer to 5 . 2 所需的存储空间的比较 integer wavelet t ransfo r m J . Proceedin gs in Image Processing , SP IH T 压缩算法需要 3 个链表 ,用它们来存储 ( ) 1997 ,1 1:596 —599 . 4 Wenkuo Lin ,N g B W —H Burgess. Reduced memo ry zerot ree co d2 重要系数和重要集合信息 。存储每个像素的信息需 ing algo rit hm fo r hardware implementatio n A . I EEE Internatio nal Co nference o n Multimedia Co mp uting and System C , Flo rence I 2 要 18bit s ,存储链表所需的存储空间大约是存储像 taly ,1999 . 素信 息 所 需 存 储 空 间 的 2 倍 。对 于 512 ×512 ×5 Wheeler F W , Pear man W A. SP I H T ima ge co mp ressio n wit ho ut list sA . I EEE Int Co nf o n Aco ustics ,S peech and Signal Processing 8bit s 的图像来说 ,SP IH T 压缩算法需要的存储空间 ( ) ICASSP 2000C , Istanbul Tur ke y , 2000 . 6 Pablo Manzano , J ulian Martinez Ricci , Ana M C Ruedin . Embed 2 为 512 ×512 ×18bit s ×2 = 1 . 125Mbit s 。对本文描 ded lo ssy and lo ssless image co mp ressio n based o n integer wavelet 述的压缩算法所采用的三个标志位 F, F和 F来 t ransfo r m wit h hybrid zerot ree and bitplane co dingJ . Proceedin gs C D L of SP I E , 4478 :290 —297 . 说 ,由于重要像素的位臵信息由 F, F和 F编码 , C D L 7 Adams M D , Ko ssentini F. Low- co m plexit y reversible integer- to- integer wavelet t ransfo r ms fo r image co dingA . I EEE Pacific Rim F的大小为图像的尺寸大小 , F的大小为图像尺 C D Co nf Co mmunicatio n , Co mp uters , Signal Processing C . Canada , 1999 . 寸的四 分 之 一 , F的 大 小 为 图 像 尺 寸 的 十 六 分 之 L 8 蔡士杰 ,等. 连续色调静止图像的压缩与编码 M . 南京 : 南京 一 ,所以本文有损压缩算法所需的存储空间为 512 × 大学出版社 ,1995 . 2 W yant J C ,Bennet t V P. U sing co mp uter generated holograms to ()上接第 508 页 ( ) test asp heric wavef ro nt s J . A ppl Opt , 1972 , 11 12 : 2833 — 2839 . 大口径非球面光学元件进行了拼接测量 ,扩展了小 3 Kim C J . Pol yno mial fit of interferograms J . A ppl Opt , 1982 , 21 ( ) 24:4521 —4525 . 口径干涉仪的测量范围 ,具有高的空间分辨率和低 4 Michael Bra y. Stitching interfero meter fo r large plano optics using a standard interfero meter J . Proceedin gs of SP I E , 1997 , 3134 : 成本等优点 。这种技术可用于旋转对称的二次非球 39 —50 . 面 、高次非球面 、深型非球面的检验 ,具有很宽的适 5 程维明 ,陈明仪. 子孔径变换与多孔径扫描拼接技术 J . 光学〃 ( ) 精密工程 ,1993 ,1 1:54 —58 . 用范围 。本文介绍了这种新技术的检测原理 ,并提 6 白剑 ,程上彝. 子孔径检测及拼接的矩阵分析 J . 上海交通大学 出了子孔径数据“拼接”算法 。从 仿 真 结 果 可 以 看 ( ) 学报 ,1997 ,31 7:36 —39 . 7 张蓉竹 ,杨春林 ,许乔 ,等. 使用子孔径拼接法检测大口径光学元 出 ,该算法具有较高的拼接精度 ,是一种切实可行的 ( ) 件J . 光学技术 ,2001 ,27 6:516 —517 . 8 Maha jan V N . Zernike annular polyno mials fo r imaging systems 大口径非球面测试技术 。下一步的工作是研究高阶 ( ) wit h annular p upilsJ . J O pt Soc Am ,1981 ,71 1:75 —85 . 9 鄢静舟 , 雷凡 , 等. 用 Zernike 多项式进行波面拟合的几种算法 噪声 、随机噪声 、重叠区大小 、采样点数目等因素对 ( ) J . 光学〃精密工程 ,1999 ,7 5:119 —128 . “拼接”精度的影响 ,并对算法进行优化 。 10 Liu Y M , Geo r ge N L , Christ L K. Subapert ure testing of asp heres ( ) wit h annular zo nesJ . A ppl Opt ,1988 ,27 21:4504 —4513 . 参考文献 :11 Mauro M ,L uca P , Alessandro M . Testin g asp heric surfaces using ( ) mulitiple annular interferogramsJ . O pt Eng ,1993 ,32 5:1073 — 光电工 程 , 伍凡 , 陈强. F/ 1 . 3 抛物面零检验补偿器 J . 1 1079 . ( ) 2004 ,31 1:12 —15 .