一种嵌入式小波四叉树帧间编码算法

一种嵌入式小波四叉树帧间编码算法 Acta Scientiarum Naturalium ()Universitatis Pekinensis , Vol . 38 , No . 1 J an ,2002 1) 一种嵌入式小波四叉树帧间编码算法 王明辉彭立中 () 北京大学数学科学学院 ,北京 ,100871 摘 要 提出了一种新的嵌入式小波四叉树帧间编码算法 。算法对于运动补偿余量误差帧首先 进行小波变换 ,并选取适当的阈值 ,用重要图 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示大于该阈值的重要系数 。根据残差帧小波系数 的统计特性 ,用四叉树方法编码重要图 ,并对重要系数作位面编码 ,生成嵌入式码流 。实验表明 , 与 EZW ,ZTE 等算法相比较 ,该算法编码效率高 ,复现图像质量好 。 关键词 小波视频编码 ; 嵌入式编码 ; 四叉树编码 中图分类号 TN 911121 0 引言 基于运动补偿的变换编码算法是非常成功的视频压缩方案 ,得到了广泛的研究 ,并为各种视频压缩国际 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 所采用 。通过运动估计和运动补偿 ,得到了当前帧的运动矢量场和运动补 () 偿预测误差 残差帧,而帧间图像的压缩也就是如何有效的编码和传输它们 。其中运动矢量 采用熵编码方法 ,在最终的码流中只占有相对较小的份额 。因此压缩效率的提高在很大程度 上取决于如何减少用于传输运动补偿预测误差的信息量 ,即如何有效地编码残差帧 。 对残差帧的编码大多采用了变换编码的方法 ,尤其是分块的 DCT 变换 。但是在甚低比特 率下 ,这会产生严重的块效应 ,影响视觉感受 。与 DCT 变换相比 ,小波变换是全局变换 ,不会 产生块效应 。它具有良好的时频局部特性 ,可以很好的去除残差帧的空间相关性 ,达到能量压 缩的目的 。同时 ,它把非平稳的视频信号分解成一组多尺度的子图像 ,这种小波表示符合人类 视觉系统的特性 ,且每个子图像是相对平稳的 ,可以有效的进行编码 。特别的 ,小波分解适合 于分层编码和累进传输 。因此 ,小波变换被广泛应用于图像压缩和视频编码 。 对残差帧作小波变换后 ,要实现压缩的目的 ,还需要对变换系数进行量化和熵编码 。这可 以通过保留低频系数 ,舍弃高频系数来实现 。然而残差帧主要反映前后两帧运动边界的信息 , 具有较多的边缘信息 ,使得小波变换系数的高频子带具有较多的能量 ,因此舍弃高频分量会造 1 2 成运动模糊和边缘模糊 ,即产生振铃效应 ,严重影响视觉感受 。与此不同 , EZW与 SPIHT算 法利用了小波系数在相同方向上不同子带之间的相似性 ,采用树型量化方法 ,能够将图像数据 压缩成嵌入式码流 ,实现累进式图像编码 ,这便于质量伸缩性编码与码流控制 。许多优秀的视 频编码算法 ,如文献3 的 SAMCow 算法 ,文献4 的 ZTE 算法等都是建立在零树编码的基础上 () ( ) ) 1国家自然科学基金69735020 ,19872006与 973 项目G1999075105资助课题 () 北 京 大 学 学 报 自 然 科 学 版 第 38 卷2 的 。 本文结合残差帧小波系数的统计特性 ,指出了残差帧小波系数已经不适合用零树方法来 编码 。利用残差帧大幅值区域与小波图的对应关系 ,提出了一种对小波系数重要图的四叉树 编码方法 ,并用位面方法编码重要系数得到嵌入式码流 。本文第二节详细介绍了算法的实现 过程 ,第三节是算法中阈值参数的选择 ,第四节给出了模拟结果 ,最后进行了 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 。 1 算法实现 111 用四叉树编码重要图 嵌入式编码 ,指的是输出码流是按照重要性排列的 ,重要的码排在前面 ,不重要的码排在 后面 。从输出码流开始部分截取任何长度的码列都可以反解出一个重建数据流 。因此 ,重要 性编码是其中最基本的思想 。在小波变换系数中 ,幅值大的系数具有更多的能量 ,先对它们进 行编码可以更快的减少图像失真 。因此 ,重要性的判定可以以幅值大小为基础 。对于给定的 阈值 T ,如果某个系数幅值大于 T ,则称该系数是重要的 ; 否则称为非重要的 。标识这些重要 系数位置的二值图称为重要图 。EZW 算法在每一次位平面量化编码的主控过程中 ,通过零树 结构表示那些随意分布的零系数区域 ,从而有效编码重要图 。这些大系数被放到大系数列表 中通过从属过程逐渐细化逼近 。零树编码的一个前提假设是 :如果某系数是非重要的 ,则它的 各子节点系数很大可能都是非重要的 。在自然图像中确实是这样的 ,但对于残差帧情况却有 () ( ) 所不同 。如图 1 所示 ,图 1 a是 Foreman 序列第二帧原始图像的小波变换图像 ;图 1 b是以原 图 1 原始帧与残差帧的小波变换图像及其对零树假设失效点的分布情况 Fig. 1 Wavelet coefficient images and the violation points of the hypothesis 第 1 期王明辉等 : 一种嵌入式小波四叉树帧间编码算法3 始序列第一帧为参考帧 ,作运动补偿所得第二帧的残差帧的小波变换图像 。从中可以看出 ,残 () ( ) ( ) 差帧小波变换图像的高频子带也具有较多的能量 。图 1 c与图 1 d分别表示了图 1 a,图 1 ( ) b对零树假设的符合情况 。其中的白色点表示零树假设的失效点 ,即该点的幅值小于某个子 () ( ) 节点系数的幅值 。图 1 c中的白色点个数为 1 797 ,图 1 d中的白色点个数为 3 049 ,大大多于 前者 ,且多集中在低频子带中 。说明对于残差帧的小波变换系数已经不适合用零树方法来编 码 。 四叉树是一种简单的图像分级表示技术 ,曾成功应用于二值图像的压缩 。它算法简单 ,可 以根据内容进行自适应的区域分解 。文献5 ,6 等应用四叉树方法直接对残差帧编码 ,效果很 好 。这是由于残差帧中的大部分区域幅值近似于零 ,只是在高运动区域才会出现较大的幅值 , 呈现出“线模式”。这种特性使得它适于用四叉树来编码 。然而残差帧小波系数中的重要系数 无规则的散布于整个变换图像中 ,直接对小波变换系数的重要图进行四叉树编码显然是不合 适的 。小波系数中的大幅值系数多是由残差帧中的高运动区域造成的 ,如果能够建立残差帧 与小波系数的对应关系 ,就可以把这些无规则分布的重要系数有效的组织起来 ,利于四叉树编 码 。文献4 中所提的 ZTE 算法 ,把每棵小波树的系数组织成一个小波块 ,如图 2 所示 。每个 小波块包含了空间域相应位置上像素值的各个尺度各个方向的小波系数 ,提供了相应位置上 () 空间内容与小波系数之间的对应关系 。图 3 a是 Foreman 序列中第 21 帧的残差帧以 6 为阈值 ( ) ( ) 的重要图 ,图 3 b是该残差帧小波变换系数以 17 为阈值的重要图 ,图 3 c是相应的小波块图 像 。从中可以看出 ,小波块与残差帧中相应位置的能量有很大关系 ,高运动区域的能量大 ,与 其对应的小波块也就包含较多的重要系数 。由于残差帧绝大部分区域近似于 0 ,因此大多数 () 小波块不含或只含很少的重要系数 。如果只保留图 3 c中重要系数个数超过 3 的小波块 ,所 ( ) () 得图像为图 3 d,它比图 3 c只少了 41 个点 。可以看出 ,大多数重要系数集中到少数的小波 块中 ,适于四叉树编码 。 图 2 小波树与小波块的对应关系 Fig. 2 Reorganization of a wavelet tree into a wavelet block 由此 ,采用四叉树方法编码残差帧的小波块重要图 。为了提高运算速度 ,减少内存开销 ,本文采用队列操作来实现小波系数重要图的四叉树编码过程 。定义队列 WorkQuene ,它的每 ( ) ) ) 一项表示四叉树的一个结点 ,用四元组 x, y, x, y来表示 ,代表范围[ x, x×[ y, y内 1 1 2 2 1 2 1 2 () 的所有系数的集合 。如果这个集合中有重要系数 ,就称该项 结点是重要的 ;否则称为非重要 的项 。 () 北 京 大 学 学 报 自 然 科 学 版 第 38 卷4 图 3 残差帧及其小波系数的重要图 Fig. 3 The significant maps of MCP error image and wavelet coefficient image 对重要图的四叉树编码算法 : () 1初始化 。 ) 把小波系数重要图中的每一棵小波树转化为小波块 ,其对应的空间范围是[ x, x×[ y,1 2 1 ) ( ) y,把每个小波块以项 x, y, x, y的形式加入到队列 WorkQuene 中 ,四叉树的分解过程就 2 1 1 2 2 是对每个这样的小波块进行的 。 () 2分解与编码 。 ( ) 取出 WorkQuene 的第一项 x, y, x, y:1 1 2 2 当 x- x> 1 时 :若 该 项 是 重 要 的 , 则 输 出 符 号‘1 ’, 并 把 以 下4 项2 1 x+ xy+ y y+ y x+ x x+ xy+ y 1 2 1 21 2 1 21 21 2 , , 和x, y, , x, , , y, y, x, 1 1 1 22 2 2 2 2 2 2 2 x+ x y+ y 1 2 1 2 分别加在队列的末尾 。否则 ,该项是非重要的 ,输出符号‘0’。, , x, y 2 22 2 当 x- x= 1 时 :表明该结点代表单一的系数 ,若该系数是重要系数 ,则输出符号‘1’,否2 1 则输出符号‘0’。 () 3判断队列是否为空 。 () 如果此时队列 WorkQuene 为空 ,算法到此结束 ,退出 ;否则 ,转向 2。 算法中生成的‘0’ [ 7 ] ‘、1’符号流经自适应算术编码器熵编码后 ,放到输出码流中去 。需要 指出的是 ,该算法编码的实际上是每一个小波块中重要系数的位置 ,利用小波树与小波块的对 第 1 期王明辉等 : 一种嵌入式小波四叉树帧间编码算法5 应关系 ,可以得到小波系数重要图 。在低比特率情况下 ,我们需要牺牲一些不重要的信息 ,来换取高的压缩比。当小波块中的重要系数个数较少时 ,其对应空间区域的运动变化不会很剧 烈 ,这些重要系数的绝对值往往不是很大 。因此可以设置一个合适的阈值 T,当小波块中包 1 含的重要系数个数小于 T时 ,就把它们舍弃。另一方面 ,第一层分解的 3 个高频子带中包含 1 的重要系数的幅值一般不会很大 ,且人眼对高频信息不如低频信息敏感 。因此当这 3 个子带 中的重要系数个数小于某阈值 T时 ,就可以把它们舍去 。这样 ,每个小波块只需编码其左上2 1 ) ) 角的 区域 。相应地 ,在上述算法的第一步中 , 对范围是 [ x , x ×[ y , y 的小波块 , 以项1 2 1 2 4 x+ xy+ y 1 2 1 2 的形式加入到队列 WorkQuene 中即可 。这些措施可以减少编码重要x, y, , 1 1 2 2 图的比特数 ,从而大大提高编码效率 。 112 用位面方法编码重要系数 一般知道 ,零树编码是采用位平面量化的方法通过逐次逼近小波系数从而生成嵌入式码 流 ,每一次位平面量化的过程包括主控过程和从属过程 。从属过程只是将已经被确认为是大 系数的那些系数后继平面上的比特值送入自适应算术编码器进行无损压缩 ,运算量很小 。但 是主控过程的运算复杂度就比较高了 ,且前一次的主控过程要影响后一次主控过程 ,因此反复 循环的主控过程不能够并行实现 。基于上述想法 ,文献[ 8 ] 提出了一种改进的零树编码算法 , 只使用一次主控过程 ,并保留零树结构来编码大系数的位置 ,从属过程对所有大系数作算术编 码。其不足点在于所生成的码流不具有嵌入式的性质 。 本文算法首先根据码率控制的要求与小波系数幅值的分布情况 ,选择合适的阈值 T 。幅 值大于 T 的系数称为重要系数 ,使用上一小节的小波块四叉树方法编码重要图 ,标记这些重 要系数的位置 ,这相当于一次主控过程 。对重要系数的符号与幅值分别进行编码 ,首先把所有 重要系数的符号编码 。对重要系数的幅值 ,则用位面编码的方法 ,得到嵌入式码流。设 T 为 )(阈值 ,Max 为所有系数幅值的最大值 ,则任一个重要系数的幅值可以用形如 c = T + Max - T aaa1 2 3 ( ) ? + + + ,其中 a = 0 或 1 , i = 1 ,2 , 的二进制表示 。这样幅值 c 就可以用一个 i 2 3 2 22 ( ) 位序列 a, a, a, 表示 。所有重要系数的位序列在同一位置的比特的集合 ,组成一个位1 2 3 平面 。按照从前到后的次序 ,依次编码这些位面 ,就可以得到一个嵌入式码流 。为了减少码流 长度 ,减少不必要的开销 ,我们首先把重要系数按照它们所属的不同子带分为不同的集合 S , i 1 1 ) ) (( 分别求它们的最大幅值 M,并寻找 t,使得 T + Max - T? ?M < T + Max - T? ,这i i i tt- 1 ii 2 2 表示集合 S 中的元素在前 t- 1 个位面编码中都取零值。在位面编码前输出每个集合 S 的 ti i i i值 ,这表示在前 t- 1 个位面编码中就可以不对集合 S 中的元素编码了 。一般来讲 ,低频子带 i i 集合的 t较小 ,高频子带集合的 t值较大 。实验表明 ,这种做法大大减小了编码的比特率。 i i 2 算法中阈值参数的选择 判断重要系数的阈值 T ,四叉树编码中的阈值参数 T, T的选择对于码率的大小与重构 1 2 帧的质量好坏有重要影响。 () 北 京 大 学 学 报 自 然 科 学 版 第 38 卷6 阈值 T 的大小决定了重要系数所占范围的大小 。反过来 ,也可以通过设定重要区域所占的 重要系数个数 比率 ratio =,来控制阈值的大小 。 所有小波系数的个数 ) ( 首先把大于 255 的小波系数幅值截取为 255 ,并求该帧像素点幅值的直方图 Hi st i,0 ?i j ) () ( ?255 。令 T= arg min Hi st i? N ×1 - ratio,其中 N 为该帧的像素点总个数。则 T0 0 ?j i = 0 就是所求阈值。在低比特率情况下 ,ratio 的值不能取得很大 。可以设置一个初始值如 ratio =1 % ,并根据输出缓冲区的满溢情况 ,以及前几帧 PSNR 值的变化情况对 ratio 的值适当地加以 调节 ,从而自适应的选取阈值 T ,达到码率控制和质量控制的目的 。 阈值 T和 T的选取直接影响四叉树编码的码流大小 , T的取值不能太大 ,否则会影响复1 2 1 现图像质量 ,取 T= 3 即可 ; T的选取与重要系数的个数有关 ,可取为 T= N ×ratio ×10 % 。 1 2 2 3 实验结果 本文对 MPEG4 的若干 QCIF 格式的亮度图像序列做了一些实验 。对于残差帧以 927 双正 交小波滤波器做四层分解 ,因此每个小波块的大小为 16 ×16 。为了衡量算法的编码效率 ,与 EZW ,ZTE 方法作了比较 。为方便起见 ,本文算法记为 EWQC 。 首先 ,对 Foreman 序列的前 100 帧进行编码 ,第 1 帧与第 51 帧采用相同方法做帧内编码 , 其余各帧分别以相同比特数用 ZTE , EWQC 和 EZW 做帧间编码 。图 4 显示了这几种算法编码 质量的差异 。EWQC 的 PSNR 值明显大于 ZTE 与 EZW 。 其次 ,还对多个不同序列的前 100 帧做了类似实验 ,其中帧频为 10 fΠs ,比特率为 24 kbΠs 。 每 30 帧做一次帧内编码 , 其余帧做帧间编码 。结果如表 1 所示 。算法 EWQC 编码的平均 PSNR 也总是大于 ZTE 与 EZW ,这说明本 文算法编码效率高 ,复现图像质量好 。 表 1 对不同序列前 100 帧的 平均 PSNR 值对比结果 Table 1 Average PSNR result for image sequences 图像序列ZTE EZW EWQC hall monitor 32 . 56 32 . 02 32 . 81 — mother daughter 34 . 01 33 . 56 36 . 12 — 31 . 34 30 . 87 34 . 14 silent voice — 33 . 94 32 . 20 33 . 98 akiyo 图 4 Forman 序列前 100 帧编码的 PSNR 对比情况coast guard 25 . 23 25 . 36 25 . 43 — Fig. 4 PSNR comparison for Foreman sequence 5 总结 运动补偿预测误差图像主要反映运动物体边界的信息 ,其小波高频子带中包含了大量能量 ,使得零树算法的编码效率大大降低 。本文通过建立残差帧大幅值区域与小波系数重要图 的对应关系 ,提出了一种新的小波块四叉树方法有效地编码重要图 ,并采用位面方法编码重要 第 1 期王明辉等 : 一种嵌入式小波四叉树帧间编码算法7 系数生成嵌入式码流 。通过调整几个阈值参数 ,可以控制码率 ,但更好的码率控制方法是本文 下一步的研究重点 。 参 考 文 献 1 Shapiro J M. Embedded Image Coding Using Zerotrees of Wavelet Coefficients. IEEE Trans on Signal Processing , () 1993 ,41 2:3 445,3 462 Said A ,Pearlman W. A New , Fast and Efficient Image Coder Based on Set Partitioning on Hierarchical Trees. IEEE 2 () Trans on Circuits and System for Video Technology ,1996 ,6 3:243,250 Shen Ke , Edward J Delp . Wavelet Based Rate Scalable Video Compression. IEEE Trans on Circuits and System for 3 () Video Technology ,1999 ,9 1:109,121 Stephen A Martucci , Iraj Sodagar ,etc . A Zerotree Wavelet Video Coder. IEEE Trans on Circuits and System for Video 4 () Technology ,1997 ,7 1:109,118 () Strobach P. Tree2Structured Scene Adaptive Coder. IEEE Trans on Communications ,1990 ,38 4:477,486 5 Sullivan G J ,Baker R L . Efficient Quadtree Coding of Images and Video . IEEE Trans on Image Processing ,1994,3 () 6 3:327,331 Witten Ian H ,Neal Radford M ,Cleary John G. Arithmetic Coding for Data Compression. Communication of the ACM , () 1987 ,30 6:520,540 7 邢桂伟. 基于小波的图像压缩编码研究 : 学位论文 . 北京 :北京大学数学科学学院 ,2000 8 An Embedded Wavelet Qua dtree Interfra me Coding Algorithm WANG Minghui PENG Lizhong ( )School of Mathematical Sciences , Peking University , Beijing , 100871 () Abstract Motion compensated prediction MCPerror image has significant amplitudes mainly along the bound2 aries of moving objects ,correspondingly its wavelet coefficients contain large energy in high frequency bands. This greatly reduces the coding efficiency of EZW. It is first provided that the correspondence between the significant amplitudes area of the MCP error image and the wavelet coefficient significant map ,then encode the significant map efficiently using quadtree approach ,followed by bit2plane coding the significant coefficients to produce an em2 bedded data stream. Experiment result shows that compared to EZW and ZTE ,the proposed algorithm is more effi2 cient and has better performance . Key words wavelet video coding ; embedded coding ; quadtree coding