多媒体信息的数据压缩PPT课件

1 5多媒体数据压缩技术 1 5 1多媒体数据的冗余类型 图像数据表示中存在着大量的冗余 图像数据压缩技术就是利用图像数据的冗余性来减少图像数据量的方法 常见图像数据冗余类型如下 1 空间冗余 2 时间冗余 3 视觉冗余 空间冗余 一幅图像表面上各采样点的颜色之间往往存在着空间连贯性 基于离散像素采样来表示物体表面颜色的像素存储方式可利用空间连贯性 达到减少数据量的目的 例如 在静态图像中有一块表面颜色均匀的区域 在此区域中所有点的光强和色彩以及饱和度都是相同的 因此数据有很大的空间冗余 时间冗余 运动图像一般为位于一时间轴区间的一组连续画面 其中的相邻帧往往包含相同的背景和移动物体 只不过移动物体所在的空间位置略有不同 所以后一帧的数据与前一帧的数据有许多共同的地方 这种共同性是由于相邻帧记录了相邻时刻的同一场景画面 所以称为时间冗余 同理 语音数据中也存在着时间冗余 视觉冗余 人类的视觉系统对图像场的敏感度是非均匀的 但是 在记录原始的图像数据时 通常假定视觉系统近似线性的和均匀的 对视觉敏感和不敏感的部分同等对待 从而产生比理想编码 即把视觉敏感和不敏感的部分区分开来的编码 更多的数据 这就是视觉冗余 数字压缩技术三个重要指标 1 信息存储量之比大2 压缩的算法简单3 恢复效果好 1 5 2数据压缩方法 什么是熵数据压缩不仅起源于40年代由ClaudeShannon首创的信息论 而且其基本原理即信息究竟能被压缩到多小 至今依然遵循信息论中的一条定理 这条定理借用了热力学中的名词 熵 Entropy 来表示一条信息中真正需要编码的信息量 考虑用0和1组成的二进制数码为含有n个符号的某条信息编码 假设符号Fn在整条信息中重复出现的概率为Pn 则该符号的熵也即表示该符号所需的位数位为 En log2 Pn 整条信息的熵也即表示整条信息所需的位数为 E En 举个例子 对下面这条只出现了abc三个字符的字符串 aabbaccbaa字符串长度为10 字符abc分别出现了532次 则abc在信息中出现的概率分别为0 50 30 2 他们的熵分别为 Ea log2 0 5 1Eb log2 0 3 1 737Ec log2 0 2 2 322整条信息的熵也即表达整个字符串需要的位数为 E Ea 5 Eb 3 Ec 2 14 855位回想一下如果用计算机中常用的ASCII编码 表示上面的字符串我们需要整整80位呢 现在知道信息为什么能被压缩而不丢失原有的信息内容了吧 简单地讲 用较少的位数表示较频繁出现的符号 这就是数据压缩的基本准则 模型从上面的描述 我们明白 要压缩一条信息 首先要分析清楚信息中每个符号出现的概率 不同的压缩程序通过不同的方法确定符号的出现概率 对符号的概率计算得越准确 也就越容易得到好的压缩效果 在压缩程序中 用来处理输入信息 计算符号的概率并决定输出哪个或哪些代码的模块叫做模型 难道对信息中字符的出现概率这么难以估计以至于有各种不同的压缩模型吗 对上面的字符串我们不是很容易就知道每个字符的概率了吗 不过上面的字符串仅有10个字符长呀 那只是例子而已 考虑我们现实中要压缩的文件 大多数可是有几十K甚至几百K长 几M字节的文件不是也屡见不鲜吗 是的 我们可以预先扫描文件中的所有字符 统计出每个字符出现的概率 这种方法在压缩术语里叫做 静态统计模型 但是 不同的文件中 字符有不同的分布概率 我们要么先花上大量的时间统计我们要压缩的所有文件中的字符概率 要么为每一个单独的文件保存一份概率表以备解压缩时需要 糟糕的是 不但扫描文件要消耗大量时间 而且保存一份概率表也使压缩后的文件增大了不少 所以 在实际应用中 静态统计模型 应用的很少 真正的压缩程序中使用的大多是一种叫 自适应模型 的东西 自适应模型可以说是一台具有学习功能的自动机 他在信息被输入之前对信息内容一无所知并假定每个字符的出现概率均等 随着字符不断被输入和编码 他统计并纪录已经出现过的字符的概率并将这些概率应用于对后续字符的编码 也就是说 自适应模型在压缩开始时压缩效果并不理想 但随着压缩的进行 他会越来越接近字符概率的准确值 并达到理想的压缩效果 自适应模型还可以适应输入信息中字符分布的突然变化 可以适应不同的文件中的字符分布而不需要保存概率表 编码通过模型 我们已经确定了对某一个符号该用多少位二进制数进行编码 现在的问题是 如何设计一种编码方案 使其尽量精确地用模型计算出来的位数表示某个符号 最先被考虑的问题是 如果对a用3个二进制位就可以表示 而对b用4个二进制位就可以表示 那么 在解码时 面对一连串的二进制流 我怎么知道哪三个位是a 哪四个位是b呢 所以 必须设计出一种编码方式 使得解码程序可以方便地分离每个字符的编码部分 于是有了一种叫 前缀编码 的技术 该技术的主导思想是 任何一个字符的编码 都不是另一个字符编码的前缀 反过来说就是 任何一个字符的编码 都不是由另一个字符的编码加上若干位0或1组成 看一下前缀编码的一个最简单的例子 符号编码A0B10C110D1110E11110有了上面的码表 你一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了 1110010101110110111100010 DABBDCEAAB 无损压缩 无损压缩常用在原始数据的存档 如文本数据 程序以及珍贵的图片和图像等 其原理是统计压缩数据中的冗余 重复的数据 部分 常用的有 RLE runlengthencoding 行程编码Huffman编码算术编码LZW lempel ziv welch 编码 Shannon Fano编码讨论之前 我们假定要编码字符的出现概率已经由某一模型统计出来 例如 对下面这串出现了五种字符的信息 40个字符长 cabcedeacacdeddaaabaababaaabbacdebaceada五种字符的出现次数分别 a 16 b 7 c 6 d 6 e 5 Shannon Fano编码的核心仍然是构造二叉树 构造的方式非常简单 Shannon Fano编码进入Huffman先生构造的神奇二叉树之前 我们先来看一下它的前身 由ClaudeShannon和R M Fano两人提出的Shannon Fano编码 讨论之前 我们假定要编码字符的出现概率已经由某一模型统计出来 例如 对下面这串出现了五种字符的信息 40个字符长 cabcedeacacdeddaaabaababaaabbacdebaceada五种字符的出现次数分别 a 16 b 7 c 6 d 6 e 5 Shannon Fano编码的核心仍然是构造二叉树 构造的方式非常简单 1 将给定符号按照其频率从大到小排序 对上面的例子 应该得到 a 16 b 7 c 6 d 6 e 52 将序列分成上下两部分 使得上部频率总和尽可能接近下部频率总和 我们有 a 16 b 7 c 6 d 6 e 53 我们把第二步中划分出的上部作为二叉树的左子树 记0 下部作为二叉树的右子树 记1 4 分别对左右子树重复23两步 直到所有的符号都成为二叉树的树叶为止 现在我们有如下的二叉树 根 root 0 1 0 10 1 abc 0 1 de 于是我们得到了此信息的编码表 a 00b 01c 10d 110e 111可以将例子中的信息编码为 cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010 码长共91位 考虑用ASCII码表示上述信息需要8 40 240位 我们确实实现了数据压缩 Huffman编码Huffman编码构造二叉树的方法和Shannon Fano正好相反 不是自上而下 而是从树叶到树根生成二叉树 现在 我们仍然使用上面的例子来学习Huffman编码方法 1 将各个符号及其出现频率分别作为不同的小二叉树 目前每棵树只有根节点 a 16 b 7 c 6 d 6 e 5 2 在1中得到的树林里找出频率值最小的两棵树 将他们分别作为左 右子树连成一棵大一些的二叉树 该二叉树的频率值为两棵子树频率值之和 对上面的例子 我们得到一个新的树林 11 a 16 b 7 c 6 de3 对上面得到的树林重复2的做法 直到所有符号都连入树中为止 这一步完成后 我们有这样的二叉树 根 root 0 1 0 1 0 10 1 a bcde由此 我们可以建立和Shannon Fano编码略微不同的编码表 a 0b 100c 101d 110e 111 对例子中信息的编码为 cabcedeacacdeddaaabaababaaabbacdebaceada101010010111111011101010101 码长共88位 这比使用Shannon Fano编码要更短一点 让我们回顾一下熵的知识 使用我们在第二章学到的计算方法 上面的例子中 每个字符的熵为 Ea log2 16 40 1 322Eb log2 7 40 2 515Ec log2 6 40 2 737Ed log2 6 40 2 737Ee log2 5 40 3 000信息的熵为 也就是说 表示该条信息最少需要86 601位 我们看到 Shannon Fano编码和Huffman编码都已经比较接近该信息的熵值了 有损压缩 预测编码 根据某一数据模型利用以往的样本值对新样本值进行预测 然后将样本实际值与预测值的差值进行编码 如果模型足够好 且样本序列的时间相关性较强 那么误差信号的幅度将远小于原始信号 可以用较少的值对其差值量化 得到较好的压缩效果 预测编码常用的是差分脉冲编码调制 DPCM 和自适应的差分脉冲编码调制 ADPCM 分形编码 分形的方法是把一幅数字图像 通过一些图像处理技术 如颜色分割 边缘检测 频谱分析 统理变化分析等原始图像分成一些子图像 然后在分形集中查找这样的子图像 分形集实际上并不是存储所有可能的子图像 而是存储许多迭代函数 通过迭代函数的反复迭代 可以恢复出原来的图像 混合压缩 混合压缩是利用了各种单一压缩的长处 以求在压缩比 压缩效率及保真度之间取得最佳折衷 该方法在许多情况下被应用 如JPEG和MPEG标准就采用了混合编码的压缩方法 音频信号编码的分类 1 基于音频数据的统计特性进行编码2 基于音频的声学参数 进行参数编码3 基于人的听觉特性进行编码 音频信号的编码方式 1 波形编码 如PCM APC ATC等 2 分析合成方法 参数编码方法 如PLC 3 混合编码方法 MP3的全名是MPEGAudioLayer 3 简单的说就是一种声音文件的压缩格式 1987年德国的研究机构IIS InstituteIntegrierteSchaltungen 开始着手一项声音编码及数字音频广播的计划 名称叫做EUREKAEUl47 即MP3的前身 之后 这项计划由IIS与Erlangen大学共同合作 开发出一套非常强大的算法 经由150国际标准组织认证之后 符合ISO MPEGAudioLayer 3标准 就成为现在的MP3 ISO MPEG音频压缩标准里包括了三个使用高性能音频数据压缩方法的感知编码方案 perceptualcodingschemes 按照压缩质量 每Bit的声音效果 和编码方案的复杂程度分别是Layer1 Layer2 Layer3 所有这三层的编码采用的基本结构是相同的 它们在采用传统的频谱分析和编码技术的基础上还应用了子带分析和心理声学模型理论 也就是通过研究人耳和大脑听觉神经对音频失真的敏感度 在编码时先分析声音文件的波形 利用滤波器找出噪音电平 NoiseLevel 然后滤去人耳不敏感的信号 通过矩阵量化的方式将余下的数据每一位打散排列 最后编码形成MPEG的文件 而音质听起来与CD相差不大 MP3的好处在于大幅降低数字声音文件的容量 而不会破坏原来的音质 以CD音质的Wave文件来说 如抽样分辨率为l6bit 抽样频率44 1kHz 声音模式为立体声 那么存储l秒钟CD音质的Wave文件 必须要用l6bit 44100Hz 2Stereo 1411200bit 也就是相当于1411 2kbit的存储容量 存储介质的负担相当大 不过通过MP3格式压缩后 文件便可压缩为原来的1 10到l 12 每l秒钟的MP3只需大约112 128kbit就可以了 声音品质与MP3压缩比例关系表如下 1 5 3视频编码的国际标准 静止图像压缩标准 国际标准化组织 ISO 和国际电报电话咨询委员会 CCITT 联合成立的 联合照片专家组 JPEG jointphotographicexpertsgroup 于1991年提出的 多灰度静止图像的数字压缩编码 简称JPEG标准 这是一个适应于彩色和单色多灰度或连续色调静止数字图像的压缩标准 JPEG标准支持很高的图像分辨率和量化精度 它包含两部分 1 基于DCT的有损压缩方法2 基于预测方法的无损压缩方法 视频信号的压缩编码 一 视频信号的压缩编码分类无损压缩 利用数据的统计特性来进行数据压缩 典型的编码 Huffman编码 算术编码等 不失真压缩比低有损压缩 利用人的视觉特性使解压缩后的图像看起来与原始图像一样 压缩比高如 预测编码 变换编码 模型编码及混合编码等 运动图