多媒体技术应用基础第3章.ppt

3 1概述3 2数据压缩的基本方法3 3JPEG彩色静止图像编码标准3 4MPEG运动图像编码标准3 5音频的数字化与压缩编码技术 第3章多媒体的数据压缩技术 返回主目录 第3章多媒体数据压缩技术 3 1概述 多媒体是先进的计算机技术和视频 音频及通信等技术集成的产物 多媒体计算机涉及的信息包括 文字 语音 音乐 静止图像 电视图像 电影 动画 图形等等 这些信息经数字化处理后的数据量非常大 那么如何在多媒体系统中有效地保存和传送这些数据就成了多媒体计算机面临的一个最基本的问题 也是最大的难题之一 以彩色电视信号为例 设Y I Q色空间各分量均被数字化为8bit 它的数据量约为100Mbit s 用现在1GB容量的CD ROM光盘 也仅能保存约1分钟的原始电视数据 此外 彩色静止图像 文件图像以及语音等等的数据量也是非常巨大的 特别是电视图像的数据量 在相同条件下要比语音的数据量大1000倍以上 况且 现在个人电脑的传输率一般是150Mbit s 无法处理更大的数据量 因此 要把这些视频 音频等信号在有限的空间上存储和在目前的电脑总线上正确传输 必须采取数据压缩技术 可见 数据压缩技术是多媒体计算机 MPC 发展的关键性技术 3 1 1数据冗余 在实际中 我们需要的是各种信号数据携带的信息 而数据中存在许多与有用信息无关的数据 这就是所谓数据冗余 如果能够有效地去除这些冗余 就可以达到压缩数据的目的 解决数据压缩技术的核心问题就是利用最少的时间和最小的空间 传输和保存多媒体的数据 数据冗余一般有6种 1 空间冗余 空间冗余在图像数据中经常存在 例如 图像中的某个区域的颜色是相同的 相邻像素的颜色信息相同 则该区像素这个颜色相关性的光成像结果在数字化图像中就表现为数据冗余 2 时间冗余 时间冗余在序列图像 电视图像 运动图像 和语音数据中经常存在 如当一景物是静止或运动较慢时 相邻两帧图像基本相同 即后一幅图像中的背景及物体与前一幅的有很强的时间相关性 再有 人说话时发音的频率是一个连续和渐变的过程 时间上不是完全独立的 这些都反映为时间冗余 空间 时间冗余是我们将图像信号看作概率信号所反映出的统计特性 也被称为统计冗余 3 信息熵冗余 编码冗余 信息熵指一组数据所携带的信息量 在实际应用中 我们数据编码的码元长按概率对应的数据量往往大于信息熵 这就是信息熵冗余 或称为编码冗余 4 结构冗余 图像存在结构上的一致 如草席 网格图像 反映为结构冗余 5 知识冗余 许多图像的理解与某些知识有很大的相关性 如人脸的图像有固定的结构 我们已知它的结构规律 此类即是知识冗余 6 视觉冗余 人的视觉系统并不是对于图像场的任何变化都能查觉的 如对色差信号的变化不敏感 这样在数据压缩和量化过程中引入了噪声 使图像发生变化 只要这个变化值不超过视觉的可见阈值 就认为是足够好 此类冗余就是视觉冗余 3 1 2量化的基本概念 一般图像 声音的特征信息都可直接由一些模拟信号来表示 而要通过计算机进行处理 就必须转化为计算机所能接受的数字信号 即进行模拟量到数字量的转换 即A D转换 这个数字化的过程就叫量化过程 量化过程可再细分为采样与量化处理两个步骤 采样的结果就是确定使用多少个像素点来表示一幅图像 它决定了图像的分辨率 要想得到高分辨率 就需对图像更多的点进行采样处理 量化处理是预先设置一组判决电平和一组重建电平 每个判决电平将覆盖一定的空间 所有判决电平要覆盖整个有效取值区间 量化时将模拟量的采样值同这些电平比较 落在某个判决电平区间上 就取这个量化级的代表值作为它的重建电平或叫作码字 量化一般可分为3类 标量量化 零记忆或一维量化 向量量化 分组量化 和序列量化 标量量化是一维量化 所有采样使用同一个量化器进行量化 每个采样的量化都与其它所有采样无关 现在市场上的A D转换器件中所使用的PCM编码器 是最典型的一维量化的实例 所谓向量量化 就是从称为码本 Codebook 的码字集合中选出最适配于输入序列的一个码字 来近似一个采样序列即一个向量的过程 这种方法以输入序列与选出码字之间失真最小为依据 显然比标量量化的数据压缩能力要强 可见 量化的过程实际上也是数据压缩的编码过程 向量量化不仅可作为单独的一种编码方法 还可与其它编码方法构成混合方法使用 它经常与变换编码相结合 对信息源进行变换后 按一定的方式形成多维向量组 然后再到码本中寻找最佳码字 量化器的好坏对于化量误差有直接影响 若要使量化的数据在其动态范围内的概率密度服从均匀分布 则量化级别可等间隔分配 但事实上属于这种情况的并不多 有些数据的概率密度服从高斯分布 有些像预测编码的误差数据服从拉普拉斯分布 因而 为使整体的量化失真最小 就需依照统计和概率分布来设计最优的量化器 它一般是非线性的 已知的最优量化器是Max量化器 除量化器的量化区间划分为非线性之外 还可对于各区间的代表值 码字的长短 作非等步长的处理 使概率密度大的区间的码字用较少的比特数表示 反之码字取较多的比特数 目前 量化器主要有以下3类 一是均匀量化器 其量化间隔是等长的 二是非均匀量化器 其量化间隔是不等长的 三是自适应量化器 其量化间隔随传送数据的特点而 变化 对于分布概率模型未知的随机过程 优化量化器的设计较为困难 虽然Lloyd提出了Lloyd Max算法来解决此问题 但从硬件实现角度来说仍是较复杂的 3 1 3数据压缩方法的一般分类 数据压缩处理一般由编码和解码两个过程组成 编码过程就是将原始数据经过某种变换编码的压缩过程 解码过程是对编码数据进行解压缩 可认为是一种反变换 使之还原成可使用数据的过程 根据解码后的数据与原始数据是否一致 数据压缩方法可划分为两类 1 可逆编码 其压缩是完全可恢复的或没有偏差的 解码图像与原始图像严格相同 故也称无损编码 2 不可逆编码方法 其还原图像较之原始图像存在一定误差 但视觉效果可以接受 根据压缩方法的原理 可将其划分为以下7种 1 预测编码 这是一种针对统计冗余进行压缩的方法 对于空间冗余来说 它表现在一幅画面内相邻像素点之间的相关性较强 因而任一像素点均可由与它相邻的且已被编码的点来进行预测 预测是根据某一模型进行的 若模型选择得好 则只需存储或传输起始像素点和模型参数就可代替整个一帧图像了 有时也需要传输预测的误差 时间冗余的预测方法与其相似 只是针对的是帧间图像 2 变换编码 这也是一种针对统计冗余进行压缩的方法 它将图像光强矩阵 时域信号 变换到系数空间 频域 上进行处理 在空间上具有强相关性的信号 反映在频域上是某些特定区域内能量被集中在一起 或是系数矩阵的分布具有某些规律 因此我们可利用这些规律分配频域上的量化比特数 从而达到压缩数据的目的 因为正交变换的变换矩阵是可逆的 且可逆矩阵与转置矩阵相等 这使得解码运算 反变换 一定有解且运算方便 所以 变换编码总是选用正交变换 3 量化与向量量化编码 我们已经知道 量化过程就是将连续的模拟量通过采样 离散化为数字量的过程 对像素进行量化时 可以一次量化多个点 这种方法就是向量量化 例如 可以每次量化相邻的两个点 这样就可将这两点用一个量化码字表示 达到数据压缩的目的 其数据压缩能力与预测编码方法相近 本质上也是针对统计冗余的压缩 4 信息熵编码 信息熵编码就是利用信息的相关性压缩冗余度 它根据信息熵原理 对出现概率大的用短的码字表示 反之用较长的码字表示 目的是减少符号序列的冗余度 提高码字符号的平均信息量 最常见的方法有哈夫曼编码 行程编码和算术编码 5 分频带编码 就是将图像数据变换到频域后 按频率分段 之后用不同的量化器进行量化 从而达到最优的组合 或者采用分步渐近编码 开始时 对某一频带的信号进行解码 逐渐扩展到所有的频带 随着解码数据的增加 解码图像也就逐渐清晰 这种方法对于远地图像模糊查询与检索的应用比较有效 6 结构编码 编码时首先将图像中的边界轮廓 纹理等结构特征求出 然后保存这些参数信息 解码时根据结构和参数信息进行合成 恢复出原图像 7 基于知识的编码 对于像人脸等可用规则描述的图像 可利用人们已知的知识形成一个规则库 据此将人脸等的变化用一些参数进行描述 这些参数和模型一起就可实现图像的编码和解码 3 1 4数据压缩系统的构成 一般数据压缩系统的构成如图3 1所示 其中 信息源编码器的构成如图3 2所示 从数据压缩系统组成框图中 可很清楚地看出多媒体信息源的数据压缩和解码流程 从中可看出 解码实际是编码的逆过程 对于不同的应用要求 其中的信息源编码器 解码器 及内部码编码器 解码器 的具体形式会不相同 它由信源数据性质所决定的有效数据压缩方法来定 下一节 我们将对应用广泛的几个基本的数据压缩方法作详细的介绍 图3 1数据压缩系统组成 图3 2信息源编码器的构成 3 2数据压缩的基本方法 3 2 1预测编码 预测编码是减少时间冗余和空间冗余 即统计冗余 的主要方法 对于时间序列数据有广泛的应用 预测编码的特点是直观 简捷 易于实现 容易设计成实时性的硬件结构 对于传输速度要求高的应用系统 经常会用到这种方法 预测编码的原理简单地说就是 存储以前的样本值 像素 帧 根据选取的适当模型来预测未来的样本值 对这两个样本值相减得到的误差进行编码 显然 这种方法可以得到较大的数据压缩结果 预测编码可分为帧内预测编码和帧间预测编码 1 帧内预测编码 用得最多的是差分脉冲编码调制 即DPCM法 DPCM法编码的基本原理如下所述 通过画面上坐标 m n 的像素点的3个相邻 或更多 点 m 1 n m 1 n 1 m n 1 的数值 预测 m n 像素点的数值 若记 m n 点的信息数值 如亮度 为Ymn 预测值用表示 则预测公式采用下式可得到预测值 公式中的a1 a2 a3为预测参数 可以通过使误差emn Ymn 的数学期望为零 均方误差最小或通过最小二乘法得到 对误差emn进行量化 编码 显然要比对原来图像的像素进行编码的比特数小得多 解码时 只要用emn数据修改预测的像素点信息 就可得到当前像素点的信息值 在量化过程中会引起信息损失 使图像失真 但只要选择合理的量化步长 使量化误差不超过人眼的可见阈值 图像质量就可以达到主观保真度要求 这种方法在有些情况下效果不好 当画面上相邻点发生全范围变化 比如 边界处由白变为黑 这时DPCM系统会过载 即系统要用许多点才能输出全黑 这是因为 每个差值像点只表示幅值的一小部分 这种现象称为斜率过载 会产生图像边缘的模糊效应 自适应DPCM编码将会有效减轻这种现象 所谓自适应DPCM编码 ADPCM 就是在DPCM的基础上 根据图像的局部特征对量化步长及预测参数进行自适应调整 即定期地重新计算协方差矩阵和相应的加权因子 充分利用其统计特性及变化 重新调整预测参数 以得到较为理想的输出 2 帧间预测编码 序列图像 运动图像 帧间有很强的时间相关性 像电视图像 每秒钟传送30帧画面 保证画面流畅 相邻帧的时间间隔只有1 30s 大多数像素的亮度信号在帧间的变化是不大的 帧间编码技术处理的对象就是这些序列图像 随着大规模集成电路的迅速发展 已有可能把几帧图像存储起来作实时处理 这样利用帧间编码技术就可减少帧序列内图像信号的冗余度 1 条件补充法 其原理是 如果帧间各对应像素的亮度差超过阈值 则把这些像素存储在缓冲存储器中 并以恒定的传输速度传送 对阈值以下的像素不传送 而以上一帧相应像素值代替 因此 一幅电视图像可能只需传送其中一部分像素 并且传送的只是它们的帧间差值 所以可得到较好的压缩比 据统计 在可视电话中 用条件补充法需传送的像素只占总数的6 左右 2 运动补偿法 使用这种方法可以提高编码压缩比 尤其对于运动部分只占整个画面较小部分的会议电视和可视电话 压缩比可以提高很多 因此它是标准化视频编码方案MPEG中的主要技术之一运动补偿技术的关键是 计算图像中运动部分位移的两个分量 运动向量 跟踪画面内的运动情况 对其加以补偿后再进行帧间预测 1 块匹配算法 如图3 3所示 块匹配算法把图像分成若干子块图像 设子块是M N块 若当前帧图像亮度信号为fK m n 前一次传送的图像的亮度信号是fK NS m n 这里NS为帧差数目 一般NS可能是1 3或7 假定当前帧中的M N子块是从第K NS帧中平行移动而来的 则M N子块内所有像素都具有同一个位移值 i j 设运动物体在NS帧差时间内 水平和垂直最大位移均为L 这样我们可在第K NS帧搜索区SR内进行搜索 SR区为 M 2L N 2L 图3 3块匹配位移量估计算法 计算子块位移值时 可以计算两帧中子块的相关函数 NCCF i j 当NCCF i j 达到最小值时的 i j 就确定为子块的位移值 实际应用中常用下面两式确定子块匹配 这样 当前帧的M N子块的任意位置 m n 上的像素 完全可用第K NS帧位置上的像素来预测 效果是很不错的 但有时使用块匹配算法后 图像容易产生 方块效应 需要另外加预处理或后处理技术来消除 3 2 2正交变换编码 正交变换编码可以解决预测编码压缩能力有限的问题 在数字信号处理中 把时序信号Y t 通过傅立叶变换或Z变换等变换到频域上 可以很方便地得到信号的频率 能量等固有特征 数据压缩也可以利用正交变换后的频谱能量与频率分布的特殊规律来进行数据编码 只要对频域空间量化器进行合理 非均匀 比特分配 即对高能量区给以较多的比特数 低能量区给以较少的比特数 就可以得到较高的压缩比 在诸多可进行变换的坐标轴中 变换编码将寻求最优的坐标系 一般变换编码运算要比预测等其它方法的计算复杂性要高 理论上可以证明 变换方法中最优的正交变换是著名的K L变换 但是K L变换尽管是最小失真正交变换 却不实用 目前 它只能作为一种方法 用来对一些新方法及其结果进行分析比较 并没有真正应用到编码系统中而具有较优的变换效果和通用性 与K L变换很接近的正交变换DCT 离散余弦变换 和DSTC 离散正弦变换 应用很广泛 下面介绍DCT变换 研究表明 DCT的编码压缩能力仅次于KLT K L变换 所以又称DCT为次最优正交变换 DCT与KLT的基向量较为相近 又可以利用FFT 快速傅立叶变换 代数分解以及矩阵分解算法快速求解 所以DCT是一种具有实用价值的正交变换 应用DCT编码时 我们要利用一些条件来降低编码的数据率 1 方差准则 根据最优变换定理 量优正交变换KLT的基向量 i i 1 2 N 是数据向量X的协方差矩阵 Y的特征向量 变换后频域上的能量主要集中在这些特征向量中的较大特征值上 因此我们在编码时 可以选择具有M个最大特征值的y i个子集 而舍弃其余子集 这不会引入太大的误差 由于特征值是协方差矩阵 Y的主对角线上的项 它们相应于变换分量yi i 1 2 N的方差 所以我们把选择M个最大方差的分量子集进行编码 舍弃其余的 N M 个分量 这种方法称为方差准则 用方差准则具体实行时 要先画出方差分布图 然后考察曲线下的面积 找出包含90 以上面积的分量数 确定为数据压缩应保留的分量 计算结果表明 对数据压缩有意义的几乎所有的信号能量 即曲线下的面积 都集中在约45个DCT的分量之内 因此可考虑选其中最大的DCT对角线项的43个分量来编码 其余分量全部置零 这43个分量均为直流和低频分量 用方差准则编码有个明显缺陷 就是高频分量的完全丢失 表现在恢复图像上是轮廓及细节模糊 解决的方法之一是阈值控制编码 即对那些高频幅值大于阈值的变换系数也进行编码输出 其余的补零 这样 在多数低频成分仍被编码输出的同时 少数超过阈值的高频成分也被编码输出 在一定程度上弥补了上面所说的缺点 2 数据块的分块考虑 设图像的数据矩阵尺寸为M M 最简单的分块就是整块 M M 这样DCT和IDCT 逆离散余弦变换 都可以一次操作 但这至少需要两方面的支持 一是足够大的存储容量 二是允许较长时间的运算 这时DCT所需的乘法操作次数为M2log2M 这对于专用LSI处理器而言并非易事 为此 考虑选择一个小于M的数N 一般选定M是2的幂 N也是2的幂 设MN k 则k也是2的幂 于是可将M M的块分割成k2个N N的块 这可使存储器的空间需求节省k2倍 计算时间T将减少为 T k2N2log2N M2 log2M log2k 即计算时间也可减少为原来的1 log2M log2k 因此 选择的N越小 k越大 得到的空间和时间改进就越多 但当N小到一定程度时 采用变换处理会带来块与块之间的边界出现不连续点 称为边界效应 已经确认DCT当N 8时边界效应明显 所以一般可选择N 16 如果选取N 16 子块F为16 16的系数块 一幅256 256的图像将被划分为k2 256162 256个子块 分别进行变换 量化 比特分配及反变换操作 3 比特分配 由前面的知识我们知道 能够产生数据压缩效果的步骤主要在于比特分配和向量量化 而比特分配又在向量量化之前 它对于系统性能的影响很大 比特分配是指对于DCT系数矩阵F的元素进行量化时 根据对各元素允许误差的范围及误差影响均等的原则 对各元素分配给不同的比特数的码字 即对于量化失真影响较大的系数分配较多的比特数 使之误差尽可能地小 反之 分配较少的比特数 根据分析得知 F具有能量主要分布在直流系数和低频系数上的特点 这些高能量区的量化失真将对整个误差产生较大的影响 因而需要分配给高能区较多的比特数 所分配的比特数之和是由压缩比决定的 如果不考虑向量量化 压缩比Cr为 3 2 3信息熵编码 信息熵编码是利用信息的相关性和概率分布的不均匀性 压缩信息冗余度 达到信息高效传输的编码方法 它是一种可逆编码 一般用在要求不丢失信息的环境中 如传真机 网络通信 某些医疗图像和卫星图像通信系统 但它的压缩率一般不会太大 总体上讲 信息熵编码的目的是减少符号序列中的冗余 提高符号的平均信息量 可以根据符号序列的统计特性 确定某种方法把符号序列变换为最短的码字序列 使各码元承载的平均信息量 即熵 最大 同时又能保证无失真地恢复原来的符号序列 所谓信息量 是指从N个相等可能事件中选出一个事件所需要的信息量度 也就是在辨别N个事件中特定的一个事件过程中 所需要提问 是 或 否 的最少次数 例如 要从64个数中选定某一个数 可先提问 是否大于32 不论回答 是 或 否 都去掉了半数的可能事件 如此继续问下去 只要提问6次 就能从64个数中选定某一个数 因为每提问一次都会得到1比特的信息量 在64个数中选定某一个数所需的信息量是log264 6 bit 将信息源所有可能事件的信息量进行平均 这个平均信息量就是熵 Entropy 那么实际编码方法依据什么原则能保证只传送所需要的信息 且以任意小的失真或零失真来接收这些信息呢 这就是信息论的创始人香农 Shannon 于1948年在其著名的论文中正式给出数据压缩的极限 我们称为信息熵原理 香农在论文中定义了一个称为信道容量的量C 并证明了只要符号速率不超过信道容量C 符号可以以任意小的差错概率在该信道中传输 他还定义和推导了作为最小平均信息源速率的速率失真函数R D 只要R D C就可保证在接收端的失真不大于规定的失真D 这是数据压缩的数学基础 同时又指明了数据压缩技术的途径 根据香农信息论 信源所含有的平均信息量 熵 就是进行无失真编码的理论极限 只要不低于此极限 那就总能找到合适的编码方法 任意地逼近熵 信息熵编码方法主要有3种 一是著名的哈夫曼编码方法 利用概率分布特性 二是行程编码方法 利用相关特性 这两种方法已广泛应用 并被国际静止图像编码专家组 JPEG 列入推荐算法的一部分 另外一种方法是算术编码方法 利用概率分布 列入了JPEG的扩展系统中 下面分别介绍这3种编码方法的基本原理 1 哈夫曼 Huffman 编码 从理论上我们可以证明一个变字长编码的最佳编码定理 它的内容是 在变字长编码中 对于出现概率大的信息符号编以短字长的码 对于出现概率小的信息符号编以长字长的码 如果码字长度严格按照符号概率大小的相反顺序排列 则平均的码字长度一定小于按任何其它符号顺序排列方式得到的码字长度 哈夫曼编码方法就是利用这个定理 按信源信号概率的递降顺序分配码字长度 具体的方法是 在分配码字长度时 首先将其中概率最小的两个符号的概率求和 并把它看作是一个新组合符号的概率 再与其它符号按概率递降顺序排列 重复上述做法 直到最后只剩下两个符号的概率为止 然后开始以相反顺序逐步进行编码 每一步有两个概率分支 各赋予一个二进制的码 可以对概率小的赋编码为0 则概率大的就赋1 也可以反过来赋编码 表3 1就是一个Huffman编码方法的具体例子 从表中我们可以看出 Huffman编码的较短码字不可能成为较长码字的前缀部分 所以 这种编码是可以辨别的 在解码时不会出现判断错误的情况 在上例中我们得到的码字平均长度是2 73bit 其熵值为2 618bit 如果用等字长的自然码表示上述的8种符号的信息 那么码字长度必须是3bit 可见 Huffman编码的平均码字长度更接近信息符号的熵值 采用和上一例子中相同的Huffman编码方法 我们可以对符号出现概率为2的负幂次方的情况具体编码 结果表明 平均字长为1 9844bit 正好与信息熵值相等 这时的编码效率应是最高 而当符号出现的概率相等时 平均字长为3bit 实际上就是等字长的自然码 这时的编码效率最低 Huffman编码方法需要说明的是 1 Huffman方法构造出来的码并不是唯一的 我们在编码过程中对于两个概率分支赋值时 可对概率小的赋0 也可对概率大的赋0 再者 对于概率相同的两个符号 谁前谁后是随机的 赋值也不确定 这样构造出来的码字肯定不是唯一的 但对于同一信源而言 这些情况并不影响它的平均码字长度 所以编码效率还是一样的 2 Huffman编码对于不同的信源概率分布 其编码效率不同 当信源概率相等时 其编码效率最低 产生定长码 所以只有当信源概率分布很不均匀时 用Huffman方法才会收到显著的效率 对信息源进行Huffman编码后 信源中的每一个符号都给定了一个编码 这样就形成了一个Huffman编码表 一般情况下 在存储与传输过程中必须先传送这一Huffman编码表 以便在解码时参照该Huffman编码表进行正确译码 并且在实际计算压缩效果时 也必须考虑此表所占有的比特数 在某些应用中 信源概率分布大致均服从某一统计分布规律 这时可以在发送端和接收端固定Huffman编码表 就省去了Huffman编码表的传送 这样做一是减少了编码时间 一般编码时要先做概率统计再编码 因此编码比解码使用的时间长 二是更便于硬件实现 编码和解码电路相对简单 Huffman编码方法是一种优化的编码方法 使码元承载的平均信息量最大 但由于其码字字长太参差不齐 所以硬件实现起来不方便 尤其是译码电路更为复杂 为此 又设计出了双字长编码 亚最佳编码 它的压缩率相对低一点 但硬件实现要相对简单 且抗干扰能力也比Huffman方法强很多 2 行程编码 Run LengthCoding 它的编码原理比较简单 就是把图像灰度值 f x y 映射为整数对 用 Gi Li 表示 其中Gi表示灰度值 Li表示具有Gi灰度值的连续像素的点数 我们称之为行程长度 例如 对图3 4中的二维图像灰度值 f x y 作水平扫描后得到 8 8 8 2 7 6 7 8 6 3 5 5 5 4 3 4 3 8 3 2 2 6 1 5 0 3 这样用13对数据就表示了图中64个像素的灰度值 行程编码可以分为定长和变长行程编码两种方式 定长行程编码时 行程长度的最大值固定 若灰度值连续相同的个数超过了固定的这个最大值 则超过部分进行下一轮行程编码 变长行程编码时 对不同范围的行程用不同的行程长度编码 这时需要增加标志位来说明长度使用的二进制位数 行程编码对传输差错很敏感 一位符号出错就会改变行程编码的长度 使整个图像出现偏移 因此 一般要用行同步 列同步的方法 把差错控制在一行一列之内 图3 4一幅图像数据 行程编码一般不直接用于多灰度图像 彩色图像 中 比较适用于二值图像的编码 如传真图像的编码 它有时和其它的编码方法混合使用 据报道 对一维黑白传真编码系统的压缩比可以达到5 1 二维中可以达到10 1 3 算术编码 算术编码与正交变换编码相比 对输入的数据没有分块的要求 而且在有些方面要优于Huffman方法 如计算效率高且容易提供自适应模式 算术编码的基本原理是 将被编码的信息表示成实数0和1之间的一个间隔 即是说 在传输信息之前的完整范围是 0 1 每处理信息中的一个字符 这一范围就随分配给此字符的那一个间隔范围而变窄 信息符号越多 编码表示它的间隔就越小 那么表示这一间隔所需的二进制位数就越多 信息源中连续的符号 根据某一模式生成概率的大小来减小范围 出现概率大的符号比出现概率小的符号减小的范围少 下面举例说明采用固定模式的算术编码过程表3 2所示 假定传输的字符串为 eaii 这里range high low 初始high 1 low 0 下一个low和high按下式计算 low low range rangelow high low range rangehigh 3 1 表3 2 解码器和编码器的初始范围为 0 1 在第一个字符e被编码时 e的rangelow 0 2 rangehigh 0 5 所以 low 0 1 0 2 0 2 high 0 1 0 5 0 5 range high low 0 5 0 2 0 3 即接收到第一个字符后 范围由 0 1 变成了 0 2 0 5 这就是第二个字符a被编码时需用的新范围 因为a的rangelow 0 rangehigh 0 2 所以 low 0 2 0 3 0 0 2 high 0 2 0 3 0 2 0 26 range 0 26 0 2 0 06 生成新范围 0 2 0 26 第三个字符是i i的rangelow 0 5 rangehigh 0 6 所以 low 0 2 0 06 0 5 0 23 high 0 2 0 06 0 6 0 236 range 0 236 0 23 0 006 依次类推计算下去 最后可以得到 lowhigh 初始 0 1 在编码e 0 2 0 5 a 0 2 0 26 i 0 23 0 236 i 0 233 0 2336 0 23354 0 2336 把这最后的范围 0 23354 0 2336 传送给解码器 根据表3 2中的各个符号概率及其所分配的范围按公式 3 1 计算 马上就可解出第一个字符为e 这样解码器范围由初值 0 1 变为 0 2 0 5 再对上述所有字符按公式 3 1 计算 并与最终范围 0 23354 0 2336 比较 不难解出第二个字符a 依次类推 解码器将唯一地解出这串字符 eaii 这里的最后一个字符 是结束标志 表示信息传输结束 解码器见到它就停止解码 算术编码时 选择编码的概率统计及范围分配模式是很重要的 它将直接影响编码效率 除了上例中所用的基于概率统计的固定模式外 还有自适应模式 自适应模式各个符号的概率初始值都相同 它们根据出现的符号而相应地改变 只要编码器和解码器使用的各个符号的概率初始值和改变值均相同 它们的概率模型将保持一致 编码器在收到下一个字符的编码之后改变概率模型 解码器根据当前的模式解码 之后再改变自己的概率模型 使用算术编码的自适应模式 可以不必预先定义概率模型 这一方法尤其适用于不进行概率统计的场合 可以减少编码时对大量信息进行概率统计的时间 前面我们已经讲过 在信源符号概率比较接近时 使用Huffman方法编码效率不理想 在这种情况下比较适合选用算术编码方法 实际测试表明 算术编码比Huffman编码能提高5 左右的效率 所以在JPEG的扩展系统中用它取代了Huffman编码 从实现方法上比较 算术编码要比Huffman编码方法复杂一些 尤其是硬件实现 3 3JPEG彩色静止图像编码标准 彩色静止图像编码在彩色传真 电话会议 卫星图片 图像文献资料 医疗图像及新闻图片等的传输与保存中有着日益广泛的应用 因此 极需要一种标准的图像压缩算法 使不同厂家的系统设备可以相互操作 以使得上述的应用得到更大的发展 而且各个应用之间的图像交换更加容易 国际标准组织 ISO 和国际电报电话咨询委员会 CCITT 联合专家组JPEG JointPhotographicExpertsGroup 于1986年成立 一直致力于这项国际标准化方案的制订工作 并于1991年推出连续色调 彩色 静止图像压缩标准 以满足几乎所有连续色调静止图像应用的需要 现在按此标准开发的图像压缩芯片及其它产品已得到应用 JPEG标准的目的是满足以下要求 1 可大范围调节图像压缩率及其相应的图像保真度 同时编码器是参数可调的 以便使用户应用时可以选择期望的压缩 质量比 2 能应用于任何连续色调数字源图像 实际应用中可遇到的图像很多 不限制图像的尺寸 色彩空间 像素长宽比等条件 不限制图像的景像内容 如复杂程度 色彩范围或统计特性等 3 计算复杂性易控制 不但使软件实现可在一定能力的CPU上完成 而且对高性能要求的应用 能在可行的成本下用硬件来实现 下面我们就具体介绍能满足上述要求的JPEG标准的技术条件和建议的标准化算法 3 3 1JPEG的标准化算法 JPEG的技术条件 1 编码应具有三层以上的逐渐恢复特性 满足评价量 第一层 10 0 25bpp 比特 像素 用于粗略图像的传送 第二层 35 0 75bpp 通常可接受的图像 第三层 5 4 0bpp 视觉保真度被描述为 很好 的图像质量 2 具有在64Kb s 比特 秒 的条件下实时解码特性 一般要求 解码器的复杂性 15 能利用通用处理器 DSP LSI等较容易地实现 以控制软硬件的成本 编码器的复杂性 10 也能利用通用处理器 DSP LSI等实现 3 能够满足通用性应用的需要 具有以下的操作方式和特性 a 序列编码 3 WB b 渐进编码层 4层 3 c 可逆编码 3 d 自适应性 3 e 误差传播与扩散 3 f 与其它编码的可兼容性 3 建议的标准压缩编码算法分为两类 1 以离散余弦变换DCT为基础的不可逆编码方式 有两种不同层次的系统 a 基本系统 即实现DCT编码和解码所需的最小功能系统 采用顺序工作模式 编码过程中只采用Huffman编码 DC AC编码表分别有两个 输入图像精度为8比特 像素 色 b 扩展系统 即满足更广领域应用要求的系统 采用渐进工作模式 编码过程除用Huffman编码 DC AC编码表各四个 外 还可采用有自适应能力的算术编码 输入图像精度为12比特 像素 色 2 以DPCM为基础的可逆编码空间方式 对于基本系统和扩展系统两个层次来说 称为独立功能 采用顺序工作模式 编码过程可用Huffman编码或算术编码 输入图像精度为2 16比特 像素 色 3 3 2JPEG的不可逆编码压缩方法 1 基于DCT的顺序工作方式编码 1 系统的总体结构 JPEG的不可逆编码系统的总体结构如图3 5所示 它表示了一个单分量 如灰度信号 的顺序工作方式的编解码过程 从图中我们可以看到 输入图像进入编码器后 经DCT变换 量化 信息熵编码后输出压缩数据 解码器对于传输过来的压缩后的图像数据实施信息熵解码 逆量化 逆DCT IDCT 变换 然后将解码后的图像输出 图3 5系统结构图 在编码器中 图像信号经DCT变换后 再经过量化 其系数矩阵分成直流 DC 与交流 AC 成分 之后经信息熵编码 信息熵编码可以有Huffman编码和算术编码两种方式 它们对于DC系数和AC系数的编码方法不同 解码器和编码器的功能恰好相反 所以它们使用的量化表 编码表必须一致 以保证解码准确无误 对于彩色图像 可看作是将各个分量 灰度 色度 输入 然后对其压缩一起输出 2 DCT变换 选用DCT变换正如前面我们介绍过的 是因为它有同KLT较为相近的基向量 其编码压缩能力是仅次于最优KLT变换的 可以用较少的比特数得到较好品质的恢复图像 其中C w 这里DCT系数矩阵中的F 0 0 称为直流系数 DC 满足瑞利分布 其余F近似满足拉普拉斯分布 F的能量主要集中于低频区 变换系数之间基本上不相关 对图像进行DCT变换前要做分块处理 考虑到块与块之间的边界效应 当 8时比较明显 所以选取N 8 则f为8 8的系数块 因而一幅256 256的图像实际被划分为1024个子块 分别进行变换 3 量化及量化表 1 经DCT变换后 图像的时域数据就转换成为频域数据 对频域数据量化可带来两方面的好处 一是增加了频域数据里0的个数 另一方面是又降低了非零数据的表示范围 因此 对量化后的数据再进行编码 可以得到较高的压缩比 有关量化的概念和方法前面已作过介绍 我们知道 对于已知分布概率及数字特征的数据来说 比较容易依据它的概率分布设计量化器的量子 以得到具有最小量化失真的优化量化器 若分布均匀则采用均匀量化器 若分布不均匀则采用变长量化器较为理想 均匀量化器易于硬件实现 所以仍为许多压缩编码所采用 对于均匀输入 均匀量化器的最佳输出应是每个量化间隔的中点 前面我们已提到 对图像输入的DCT变换 是对图像的子块进行的 则量化也是针对变换后频域子块系数矩阵进行的 子块系数矩阵的不同位置 反映了图像数据的不同频率成分 也就是反映图像的变化情形 一般来说 图像的变化是缓慢的 所以它的高频成分较少 低频成分要多些 根据图像的这一特征 我们可以将子块系数矩阵的不同位置采用不同步长进行量化 而对于同一图像的不同子块中的相同位置 采用等步长均匀量化 这样做只有简单的乘除运算 易于硬件实现 大量实验证明 当每个像素用小于或等于1比特的数据表示时 其效果十分接近于LloydMax量化器和自适应量化器 因此 在彩色静止图像压缩中 量化器的设计就采用了这种思想方法 设量化是对频域子块系数矩阵某一位置 u v 进行的 其步长是等步长的 量化公式为上式中C u v 是量化器的输出 F u v 是量化器的输入 Q u v 是量化器的步长 当输入F u v 为正数时 公式取 号 输入F u v 0时 公式取 号 因此 当输入处于区间时 输出为0 当输入处于区间时 输出为1 如图3 6所示 对图像进行恢复时 用逆量化公式 F u v C u v Q u v 其中 C u v 是逆量化器输入Q u v 在 u v 点的步长 这样 当C u v 为0时 恢复的频域值为0 当C u v 为1时 恢复的频域值为Q u v 在该量化方法中 量化过程及图像恢复过程 都需要一个记录频域子块系数矩阵的每一位置步长的量化表 下面就介绍量化表的形成 图3 6量化器示意图 2 量化表 我们知道 对于彩色图像 每个像素可通过三基色红 R 绿 G 蓝 B 表示 为了提高编码效率 彩色像素分为灰度 Y 和色度 U和V 3个成分 对应于三个分量矩阵 由于Y分量和U V分量具有不同的频率特性 同时考虑到人的视觉对亮度信号Y敏感 对色度信号U V的敏感度较差 因此 实际的数据压缩时 对Y分量和U V分量的量化处理区别对待 可以使用不同的量化表 适度降低表示U V的数据量 JPEG推荐的Y分量量化表和U V分量的量化表分别如表3 3和表3 4所示 4 分组原则 对原始图像的8 8块做完自适应DCT ADCT 和量化后 其64个系数分为直流分量和交流分量 位于左上角 坐标 u v 0 的是DC系数 其余的63个是AC系数 由于相邻8 8块之间的DC系数有很强的相关性 JPEG中对DC系数采用DPCM编码的最简单形式 即差分编码 也就是对相邻块之间的DC系数的差值 DCi DCi DCi 1进行编码 如图3 7所示 因为DC系数常常包含了整个图像能量的主要部分 所以这个特殊处理很有意义 可以降低DC系数的值及增加0的个数 图3 7DC系数差分编码 差分后得到一个差分序列 直流差分序列 由于图像在空间上的相关性 对于一般的图像来说 其差分值d的分布接近于拉普拉斯分布 即差分值d的正负是等概率出现的 且d出现概率随d值的增大而逐渐减小 为了提高后面要进行的 Huffman编码的效率 根据这一分布特点 将差分值分成若干组 每一组所含差分值的个数由组号决定 若组号为i 则第i组包含2i个差分值 且其中正负值各占一半 第i组内的差分值由附加的i个比特位来标识 即每个差分值由组号和标识位唯一确定 对标识位可以直接用二进制位的形式存储或传输 对于组号部分 提供给后面的Huffman编码进行处理 DC差分值分组和标识位的情况如表3 5所示 表3 5DC差分值分组表 对于频域内的交流分量 其分布也近似于拉普拉斯分布 所以也可按DC分组的方式分组 AC分组情况如表3 6所示 它没有0组 此外 在进行行程编码及Huffman编码之前要做 Z形扫描 5 Z形扫描 8 8 子块频域的 8 8 系数矩阵中的64个系数中 左上角一个为DC系数 其余63个为AC系数 对于交流分量 根据DCT变换的性质 这63个系数按左上角到右下角的次序分别代表图像的低频分量到高频分量 频率逐渐增高 为了将二维块用一维编码方法进行处理 同时也尽量使其频率按由低到高的次序排列 可以将系数矩阵通过Z形扫描的方法展开 见图3 8所示 这样就可以使代表相同或相近频率分量的系数 在一维系数序列中保持相临或相近的位置 使之在后面的行程编码中提高编码效率 6 行程编码 量化后很多低频分量的值均为0 这样经Z形扫描后的一维序列中就有许多连续的0 因此很适合采用行程编码 编码时采用下面的方法 由两部分来组成一个字节 第一部分为零的个数 第二部分为紧随其后的非零值的组号 每部分各占用4个比特 如图3 9所示 对零的行程采用变步长方式 限制在4位二进制位数内 即最大值为15 组号占用位和前面的分组情况是一致的 图3 8 Z形扫描示意图 图3 9行程编码示意图 零的行程限制在4比特 主要是因为 1 正好与组号合成一个字节 便于Huffman编码 2 Z扫描后 相临块的Z形扫描序列是相临的 最大固定长度不会超过63 并且每一Z形块内连续0的个数一般都不大于32 这种方法的整体编码效果比较好 例如 给定一个顺序210000000000000000001 经行程编码后得到02H 01H F0H 31H共4个字节 而不经编码需10 5个字节 每一个数需4比特 7 哈夫曼 Huffman 编码 它是基于概率统计的变长码方法 实际应用中需要有一个记录着事件与其编码的对应关系的表 哈夫曼表 按照哈夫曼表就可以对事件编码和解码 这个过程可有两种处理方法 一是随统计的信源数据形成哈夫曼表 并随之一起传输的自适应方式 二是事先做大量的统计 形成哈夫曼表 再将此表固定在发送端和接收端的固定方式 JPEG使用的是固定方式 并且对直流分量和交流分量分别编码 图3 10和图3 11是JPEG方案对DC及AC编码的处理过程 解码过程与编码过程类似 有时为了提高编码的效率 可以固定放四张哈夫曼表 两张直流 两张交流 在具体应用时 应根据应用实际情况来建立自己的哈夫曼表 8 实验结果 用上述压缩算法对中等复杂程度的彩色静止图像进行实际压缩 得到压缩比与恢复的图像质量的实验结果分如下4个等级 0 25 0 50比特 像素 中等质量 可满足某些基本应用 图3 10直流分量编码流程图 图3 11交流分量编码流程图 0 50 0 75比特 像素 好或很好 可满足多数应用 0 75 1 5比特 像素 极好 可满足绝大多数应用 1 5 2 0比特 像素 与原图像难以区分 满足较高精度应用的要求 2 基于DCT的渐进工作方式编码 前面讲的基于DCT的顺序工作方式编码 其编码过程是一次扫描完成的 基于DCT的渐进工作方式的编码步骤与顺序方式基本一致 所不同的只是每个图像分量的编码要经过多次扫描才能完成 第一次扫描只进行一次粗糙的压缩 以相对于总的传输时间快得多的时间传输这些数据 根据此粗糙的压缩数据 重建一幅质量较低的可识别图像 随后的扫描再对图像作较细的压缩 这时就只需传送增加的信息 可重建一幅质量较高的图像 就这样不断渐进 直到图像的质量达到满意为止 为了实现渐进操作 需在量化器输出与信息熵编码的输入之间 增加一个足以存储量化后的DCT系数的缓冲区 对缓冲区中存储的DCT系数 在多次扫描中分批地进行编码 渐进工作方式又可分为两种方法 1 频谱选择法 在一次扫描中 这种方法只对64个DCT变换系数中的某些频带段的系数进行编码 传送 随后在扫描过程中 以渐进的方式 对其它频带段的系数进行编码 传送 直至将全部系数传送完毕 2 按位逼进法 它沿着DCT量化系数位 表示系数精度的位数 方向分段渐进编码 比如 第一次扫描只取最高有效位的几位进行编码 传送 在随后扫描中 对剩余位分批进行编码 传送 图3 12中很直观地表示出频谱选择法和按位逼进法的渐进过程 在图中 我们把量化的DCT系数信息形象地表示成一个矩形 它的纵方向代表DCT量化系数 横向表示量化系数的精度位数 第三个方向是块的序列表示 那么 频谱选择法是把垂直方向的信息切成段 按位逼近法是在水平方向分段 图3 12渐进编码的频谱选择和按位逼近法 3 基于DCT的分层操作方式编码 分层工作方式 是将一幅原始图像的空间分辨率分成多个分辨率而进行 锥形 编码的方法 水平方向和垂直方向分辨率以2的倍数下降 如图3 13所示 其编码过程可概括如下 1 首先把原始图像空间分辨率降低 2 对已降低分辨率 小尺寸 的图像可采用基于DCT的顺序方式 渐进方式或可逆编码方式中的任何一种进行编码 3 对低分辨率的图像解码 重建图像 使用插值滤波器对它插值 恢复图像的水平和垂直分辨率 图3 13分层多分辨率编码 4 把分辨率已升高的图像作为原始的预测值 对它们的差值采用基于DCT的顺序方式 或渐进方式 也可采用可逆方式进行编码 5 重复步骤 3 4 直到图像达到完整的分辨率编码 这种分层方式编码在用低分辨率的设备来存取高分辨率的图像的应用中是很有用的 如设备没有高分辨率恢复图像的缓冲能力时 可以把图像降低到低分辨率显示 例如一幅在一个非常高质量的打印机上 以高分辨率扫描和压缩的图像 也可以在一个低分辨率的PC机上显示 1 系统的结构框图 JPEG的彩色静止图像可逆编码系统 是以无失真预测编码技术DPCM为基础的 系统结构如图3 14所示 这种压缩方法主要使用了DPCM 分组技术及算术编码或哈夫曼编码 图3 14可逆编码系统结构框图 2 DPCM预测编码 之所以采用预测编码方法 是因为它有硬件实现容易 重建图像质量好的优点 这里的DPCM预测器采用三邻域采样值 A B和C 组合而成 如图3 15所示 以表示X的预测值 X为该点的实际值 从X中减去得到差值 X 我们再对差值 X不经过量化作无失真的信息熵编码 预测值可采用表3 7中所列的8个选择值中的任意一个 表中1 2 3是一维预测器 4 5 6和7是二维预测器 0只能用在分层操作方式中的差分编码 在编码中 第一列采用X B预测 第一行采用X A 其它采用X A B C 2 预测 图3 15三邻域预测值示意图 3 4MPEG运动图像编码标准 国际标准化组织 ISO