第十章 小波图像编码

第九章小波图像编码 前言 由于小波变换技术在20世纪90年代初期已经比较成熟 因此也出现了多种新颖的小波图像编码方法 其中包括EZW SPIHT EBCOT等 由于EZW算法的开拓给后来者带来很大启发 它是一种有效而计算简单的图像压缩技术 本章将重点介绍 第一节从子带编码到小波编码 子带编码子带编码的基本概念是把信号的频率分成几个子带 然后对每个子带分别进行编码 并根据每个子带的重要性分配不同的位数来表示数据 20世纪70年代 子带编码开始用在语音编码上 20世纪80年代中期开始在图像编码中使用 多分辨率分析S Mallat于1988年在构造正交小波基时提出了多分辨率分析的概念 从空间上形象地说明了小波的多分辨率的特性 提出了正交小波的构造方法和快速算法 叫做Mallat算法 如果在一级分解之后继续进行分析 这种分解过程叫做多分辨率分析 实际上就是多级小波分解的概念 使用多级小波分解可以得到更多的分辨率不同的图像 这叫多分辨率图像 滤波器组与多分辨率为了压缩语音数据 在1976年Croisier Esteban和Galand介绍了一种可逆滤波器组 使用滤波和子采样的方法用来把离散信号f n 分解成大小相等的两种信号 并且使用叫做共轭镜像滤波器的一种特殊滤波器来取消信号的混叠 这样可从子采样的信号中重构原始信号 正交小波的多分辨率理论已经证明 任何共轭镜像滤波器都可以用来刻画一种小波 而且快速离散小波变换可以使用串联这些共轭镜像滤波器来实现 连续小波理论和离散滤波器组之间的等效性揭示了数字信号处理和谐波分析之间的关系 小波分解图象方法 包括 均匀分解 非均匀分解 八带分解和小波包分解 其中八带分解使用最广泛 它属于非均匀频带分割方法 它把低频部分分解成比较窄的频带 而对每一级分解的高频部分不再进一步分解 失真的度量方法 在图象编码系统中 评估编码系统性能用 失真度量法 用峰值信号噪声比来衡量 定义 最大像素值与均方差之比 其他方法 规格化均方差 信噪比 平均绝对误差 平均主观平分 EZW编码 简介 EZW主要用于与小波变换有关的二维信号的编码 但不局限于二维信号 EZW是 嵌入式零树小波算法 的简称 它是一种用于熵编码的高效算法 零树 小波变换系数之间的一种数据结构 嵌入 渐进编码技术的另一种说法 含义是指一幅图象可以分解成一幅低分辨率图象和分辨率由低到高的表示图象细节的许多子图象 图象合成和分解过程相反 使用子图象生成分辨率不同的图象 小波图象编码的一般结构主要由 小波变换 量化和熵编码等三个模块组成其中小波变换 不损失数据 它是EZW算法具有渐进性的基础 量化模块 对数据会产生损失 损失程度取决于量化阈值的大小 EZW算法指的就是此模块的算法 熵编码模块 对每个输入数据值精确地确定它的概率 并根据这些概率生成一个合适的代码 使输出码流小于输入码流 9 3 2算法对整幅图象编码一次 生成一种分辨率图象 编码一次叫做一遍扫描 每一遍扫描包含三个步骤 1 设置阈值2 每个小波系数与阈值进行比较3 量化系数和重新扫描 零树的定义 子孙系数都为零的树 零树定义的意义 如果一棵树是零树 那么这棵树就可以用一个预先定义的符号来代表整棵树 从而提高压缩比 EZW编码树的构造 扫描方法 EZW算法对小波系数进行编码的次序叫做扫描 包括两种方法 1 光栅扫描2 迂回扫描 9 3 3算法举例P173 第四节SPIHT编码 9 4 1简介SPIHT是EZW的改进算法 可叫做 层树分集 算法 优越性 图象的渐进传输 较高的PSNR 复杂度较低 计算量较少 位速率容易控制等 9 4 2渐进图象的传输SPIHT算法采用的方法是幅度大的系数先传送 它要求对系数进行排序 若传送的系数已按要求排序且用二进制形式表示 由幅度大的系数先传送的原则 必然按照最高有效位最先传送的原则进行传输 这种方法叫位平面 bitplane 方法 9 4 3分集排序算法SPIHT编码算法的一个特点 不单独传输系数的排序信息 基本依据 任何排序算法的执行路径都是使用分支点的比较结果进行定义的 如果编码器和解码器使用相同的排序算法 解码器就可重复编码器的执行路径 因此排序信息可从执行路径中重新获得 分集排序算法不对所有系数排序 其选择发送的系数的规则是 其中 实际上就是EZW算法中的阈值 编码时每扫描一遍 新的阈值就设置为 若对给定的n 就称系数是重要的 否则就称系数是不重要的 按照参数选择原则 分集算法把像素集分成许多子集 并对子集中的系数幅度作如下测试 如果回答是否定的 则说明这个子集是不重要的 解码器也就知道这个子集中的系数都是不重要的 如果回答是肯定的 则说明这个子集是重要的 解码器接收到这个信号之后 按照编码器的规则把这个子集 分成新的子集 然后对新的子集做如上相同的测试 这个子集分割过程一直到对所有重要子集完成幅度测试为止 目的是标识每一个重要系数 9 4 4类型和变量SPIHT算法定义的编码树的结构中 树的每一个节点与一个系数相对应 并用坐标 i j 来标识 每一个节点的直接子孙或者叫做子节点与相同空间方向的高一级子带的系数相对应 编码树定义 每一个节点有 个直接子孙或者没有直接子孙 在SPIHT算法中 使用坐标标记的方法定义了4种坐标集来表示小波系数的类型 并用下面的符号表示 O i j 所有子节点 i j 的坐标集D i j 所有子孙节点 i j 的坐标集H i j 所有树根的坐标集L i j D i j O i j 除子节点之外的所有子孙节点的坐标集 在SPIHT编码算法中 使用最频繁的坐标集是D i j 和L i j 如果说一个坐标集是重要的 则要求在此坐标集中至少有一个系数的幅度大于等于阈值 由于测试重要系数的次序的重要性 在实际执行SPIHT算法的过程中 重要信息存储在3种次序列表变量中 3种次序列表变量的定义 1 LIP 不重要像素表 用于存放单个不重要的系数 用低通子带的系数初始化 2 LIS 不重要子集列表 用于存放不重要的系数树 用DC子带中不重要的系数集的坐标初始化 3 LSP 重要像素表 用于存放重要系数 初始化成空集 在这3种列表中 每一个表项都使用坐标 i j 来标识 在LIP和LSP中 坐标 i j 用来表示单独的系数 在LIS列表中 坐标 i j 用来代表所有子孙节点 i j 的坐标集D i j 或者代表除子节点之外的所有子孙的坐标集L i j 为便于描述LIS中的坐标集 又把坐标集D i j 命名为A型树 把坐标集L i j 命名为B型树 1 A型树也称D型树 LIS代表坐标集D i j 编码时需要检查所有的子孙系数以确定是否重要 2 B型树也称L型树 LIS代表坐标集L i j 编码时需要检查除子系数之外的所有子孙系数以确定是否重要 9 4 5算法 9 4 6算法举例下例是AgnieszkaC Miguel在分析SPIHT算法时提供的一个例子 执行SPIHT算法的步骤 1 计算阈值和初始化 初始化把低通子带中的所有根节点的系数赋给LIP 把所有树赋给LIS 把LSP初始化为空集 2 检查LIP中的所有系数以确定是否重要 A 如果重要 输出 1 和符号位 然后把该系数移到LSPB 如果不重要 输出 0 3 按照树的类型 检查LIS中所有重要的树 A 对D型树 如果该树是重要的 输出 1 然后对子节点的系数进行编码 如果子节点的系数是重要的 输出 1 和符号位 然后把它移到LSP中如果子节点的系数是不重要的 输出 0 然后把它移到LIP中如果子节点有后裔 就把这棵树移到LIS列表的末端 并作为L型树如果该树不重要 输出 0 B 对L型树 如果该树是重要的 输出 1 把每一个子节点移到LIS的末端作为D型树 然后把父树从LIS中删除如果该树不重要 输出 0 4 减少阈值 然后返回到 2 第五节EBCOT编码简介 9 5 1介绍EBCOT 最佳截断嵌入码块编码 是DavidTaubman在1999年发表的一种编码算法 现在处于进一步开发中 EBCOT算法是一种对小波变换产生的子带系数进行量化和编码的方法 基本思想 把每一个子带的小波变换系数分成独立编码的码块 并且对所有的码块使用相同的编码方法 如图9 21 独立编码的码块 概括的说 EBCOT编码的主要想法是把嵌入码块编码方法与码块位流的最佳截断方法结合在一起 使重构图象失真最小 它的主要特性包括分辨率可变 信噪比可变和随机访问 9 5 2质量层的概念EBCOT编码算法引入了一个 质量层 的概念 图象的最终码块位流以质量层的形式组织 每一层都包含每一个码块对图象的贡献 如图9 22 若某些码块对质量没有贡献的层用 空 表示 EBCOT算法包含两种不同的编码器来体现它的性能 这两种编码器分别叫做层1编码器和层2编码器 T1编码器处理变换图象的小波变换系数 并把截断点放到码块中 后者把来自T1编码器的零碎码块放到不同的质量层 与不同的位速率相对应 并生成实际的压缩位流和文件 9 5 3位速率失真最佳EBCOT算法把表示图象的子带分成相对比较小的许多码块i表示第i个码块 每一个码块中的位流可以被截断成各种长度的位流在重构图象时计算由这些截断位流引起的失真 把对重构图象产生的失真用表示 并假设失真度量是相加的 整个图象的失真表示为 其中 表示码块选择的截断点 相加性的失真度量可用均方差MSE或加权的均方差MSE 对某一组截断点 位流中某一层的位速率用R表示EBCOT算法的目的就是在的限制条件下找一组截断位流使失真D最小 这个问题可使用拉格郎日乘法求解 把问题转化为求解使函数最小化的问题 其中的值必须进行调整 直到使该函数最小时的截断位流产生的速率满足 第六节JPEG2000简介 9 6 1JPEG2000是什么JPEG2000是由ISO IECJTC1SC29标准化小组负责并正在制定的新的静态图象编码的国际标准 文献中涉及的组织简介 JPEG 联合图象专家组 是由国际标准化组织和国际电工技术委员会组成的专家组 ISO 是1946年成立的一个自愿参加和无条约约束的国际组织 主要负责制定包括计算机 通信等众多领域的国际标准 以方便国际间信息 科学 技术 经济等活动领域的相互交流合作 其成员为各个国家的国家标准化组织 目前共有89个国家参加了该组织 IEC 是1906年成立的制定国际性的电 电子器件和系统标准的一个委员会 有40多个国家参加 JTC1是ISO和IEC的合作领导小组 其中SC29负责JPEG2000系列标准的制定 SC29分为WG1 WG11和WG12三个小组 WG1负责JBIG和JPEG标准的制定 其中JBIG叫做 联合二值图象专家组 负责制定二值图象的压缩标准 WG11负责MPEG标准的制定 MPEG 运动图象专家组 WG12负责MHEG标准的制定 MHEG 多媒体超文本专家组 9 6 2JPEG2000的基本结构JPEG2000编码器的方框图如9 24 A 首先对源图象数据进行变换 再对变换的系数进行量化 然后在形成代码流或位流之前进行熵编码 解码器与编码器正好相反 JPEG2000标准是以图象块作为单元进行处理的 这就意味着图象数据在进入编码器之前要对它进