04数据压缩基础课件

数据压缩基础...数据压缩编码技术概述多媒体数据压缩的必要性和可行性衡量多媒体数据压缩技术的指标： 压缩比 算法简单，压缩解压缩速度快 尽可能地恢复原始数据压缩方法分类 无损压缩：Huffman编码、游程编码、算术编码、LZW编码 有损压缩：预测编码、变换编码、模型编码、基于重要性的编 码、混合编码新一代的数据压缩方法：矢量量化和子代编码、基于模型的压 缩、分形压缩、小波变换压缩等等。...

压缩的必要性

音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。 例如，一幅具有中等分辨率（640×480）的真彩色图像（24b/像素），它的数据量约为7.37Mb/帧，一个700MB（Byte）的硬盘只能存放约100帧图像。若要达到每秒25帧的全动态显示要求，每秒所需的数据量为184Mb，而且要求系统的数据传输率必须达到184Mb/s。对于声音也是如此，若采用16b样值的PCM编码，采样速率选为44.1kHZ，则双声道立体声声音每秒将有176KB的数据量。...数据压缩的好处

时间域压缩──迅速传输媒体信源 频率域压缩──并行开通更多业务 空间域压缩──降低存储费用 能量域压缩──降低发射功率...数据压缩技术实现的衡量标准

压缩比要大 恢复后的失真小 压缩算法要简单、速度快 压缩能否用硬件实现...多媒体数据压缩技术分类

平均信息量编码──可逆压缩──去冗 余──统计特性 源编码──不可逆压缩──有失真编码 特征提取等 两种压缩技术不互斥，两种压缩技 术的结合，可以达到最高可能的压缩率。...

多媒体数据压缩技术分类

无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。

有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不会使人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。...无损数据压缩

主要介绍目前用得最多和技术最成熟的 无损压缩编码技术，包括： 霍夫曼编码 算术编码 游程编码RLE 词典编码LZW...

霍夫曼(Huffman)编码

霍夫曼(Huffman)在1952年提出了另一种编码方法，即从 下到上的编码方法。

几个个问题值得注意：1.霍夫曼码没有错误保护功能；2.霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码;3.接收端需保存一个与发送端相同的霍夫曼码表。...字母频率编码A25%01B15%110C10%111D20%10E30%00霍夫曼(Huffman)编码...信源消减信源符号集B={b1,b2,b3,b4}

概率矢量u={0.1，0.38，0.22，0.3}

步骤1：信源消减...步骤2：对信源符号赋值平均码长Lavg=1.946...霍夫曼码的特点1，块码（组码）

2，即时码

3，唯一可解码...霍夫曼码改型亚最优牺牲编码效率来换取编码速度截断霍夫曼码前M个符号用霍夫曼编码其余用前缀码+定长码（自然码）平移霍夫曼码分组：相同符号数用霍夫曼编码编第1组其余组用平移符号+第一组霍夫曼码...霍夫曼码改型

...霍夫曼(Huffman)编码 依赖于信源的统计特性，必须先统计得到信源 的概率特性才能编码，这就限制了实际的应用。 缺乏构造性，即它不能用某种数学方法建立起 消息和码字之间的一一对应关系，而只能通过 某种查表的方法建立起它们的对应关系。 如果消息数目很多，那么所需存储的码表也很 大，这将影响系统的存储量及编、译码速度。...练习初始信源：a1：0.1，a2：0.4，a3:：0.06，a4:0.1，a5：0.04，a6：0.3....练习...算术编码只需要用到加法和位移运算从整个符号序列出发算术编码不再是块码，采用递推形式连续编码

...算术编码的特点：1种从整个符号序列出发，采用递推形式连续编码的方法不存在源符号和码字间的一一对应关系1个算术码字要赋给整个信源符号序列，而每个码字本身确定了0和1之间的1个实数区间算术编码过程只需用到加法和移位运算

...算术编码

b1=0.1b2=0.38b3=0.22b4=0.30.0000100120.0351562510码串：b1；b2；b3；b4...

算术编码在算术编码中需要注意的几个问题：1.由于实际计算机精度不可能无限长，运算中溢出是明显的问题，但多数机器都有16位、32位或者64位的精度，因此可使用比例缩放法解决。2.算术编码器对消息只产生一个码字，这个码字是在[0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。3.算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。...算数编码练习初始信源：a1：0.1，a2：0.4，a3：0.5，码串：a1，a1，a2，a3...

游程RLE编码RLE(runlengthencoding）编码的概念

用RLE编码方法得到的代码为：80315084180。代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。 译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。...

词典编码

词典编码的思想

第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。...词典编码

词典编码的思想

第二类算法的想法 是企图从输入的数据中 创建一个“短语词典

(dictionaryofthe phrases)”，这种短语可 以是任意字符的组合。 编码数据过程中当遇到 已经在词典中出现的“短 语”时，编码器就输出这 个词典中的短语的“索引 号”，而不是短语本身。...

词典编码

J.Ziv和A.Lempel在1978年首次发表了介绍上述第二类编码方法的文章。在他们的研究基础上，TerryA.Welch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-ZivWalch)压缩编码，

LZW算法

在编码原理上，LZW与LZ78相比有如下差别：①LZW只输出代表词典中的缀-符串(String)的码字(codeword)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。②由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-characterprefix)，因此在词典中搜索的第1个缀-符串有两个字符。

LZW编码是围绕称为词典的转换表来完成的。...

词典编码

LZW算法

LZW编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedyparsingalgorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Currentcharacter)作为该前缀的扩展字符，形成新的扩展字符串——缀-符串(String)：Prefix.C。这个新的缀-符串(String)是否要加到词典中，还要看词典中是否存有和它相同的缀-符串String。如果有，那么这个缀-符串(String)就变成前缀(Prefix)，继续输入新的字符，否则就把这个缀-符串(String)写到词典中生成一个新的前缀(Prefix)，并给一个代码。...

词典编码

LZW算法

LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。

LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司—Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法。...

词典编码压缩算法基于以下的中心思想

1. 为原始文本文件中的每个字母分配一个代码并存储到 一个代码表中

2. 设置一个循环，每次从文件中获取一个字符。将使用 一个缓冲字符串，把从文件中取出的字符连接在一起

3. 在每次循环中，读取一个字符接到缓冲字符串的后 面，形成一个新的临时字符串。如果该临时字符串以前 曾经出现过就把它移到缓冲区里

4. 如果临时字符串不出现在代码表中，就为它分配一个 代码，并把字符串和代码存储到代码表中，同时发送缓 冲字符串所对应的代码 重新设置缓冲字符串为刚刚读取的单个字符。...JPEG算法概要JPEG(JointPhotographicExpertsGroup)是一个由ISO和IEC两个组织机构联合组成的一个专家组，负责制定静态的数字图像数据压缩编码标准，这个专家组开发的算法称为JPEG算法，并且成为国际上通用的标准，因此又称为JPEG标准。JPEG是一个适用范围很广的静态图像数据压缩标准，既可用于灰度图像又可用于彩色图像。使用有损压缩算法时，在压缩比为25:1的情况下，压缩后还原得到的图像与原始图像相比较，非图像专家难于找出它们之间的区别，因此得到了广泛的应用。V-CD、DVD-Video。

图像和视频的压缩技术...

图像和视频的压缩技术JPEG压缩的三个阶段

离散余弦变换（DiscreteCosineTransform,DCT） 量化（Quantization） 编码阶段（EncodingPhase）压缩图像原始图像DCT阶段量化阶段编码阶段...1.离散余弦变换 下面对正向离散余弦变换(FDCT)变换作几点说明。 (1)对每个单独的彩色图像分量，把整个分量图像分成8×8的图像块，并作为两维离散余弦变换DCT的输入。通过DCT变换，把能量集中在少数几个系数上。

...离散余弦变换阶段P(x,y)经DCT变换之后，T(0，0)是直流系数，其他为交流系数。在计算两维的DCT变换时，可把两维的DCT变换变成一维的DCT变换...图像和视频的压缩技术2.量化阶段量化是对经过FDCT变换后的频率系数进行量化。量化的目的是减小非“0”系数的幅度以及增加“0”值系数的数目。量化是图像质量下降的最主要原因Q=integer(T/U)其中：DCT变换系数T；U是量化器步长，它是量化表的元素。...图像和视频的压缩技术

量化器步长1520-480-80-7013579111315T=00000000357911131517-480380-30205791113151719U=

00000000-80-30130-10 0000 0000-7 020-1070 0000 0000

79111315171921 911131517192123111315171921232513151719212325271517192123252729...Q=图像和视频的压缩技术

根据公式，量化后将得到

1520-100-10-10 00000000-100400000

00-10 00-10 00000000001000000000000000000000...对于有损压缩算法，JPEG算法使用均匀量化器进行量化，量化步长是按照系数所在的位置和每种颜色分量的色调值来确定。因为人眼对亮度信号比对色差信号更敏感，因此使用了两种量化表：亮度量化表和色差量化表。...3.Z字形编码阶段。量化后的系数要重新编排，目的是为了增加连续的“0”系数的个数，就是“0”的游程长度，方法是按照Z字形的式样编排。这样就把一个8×8的矩阵变成一个1×64的矢量。编码阶段152

0-10

0 -1 0 -1 000000000-10

0 0 0 0 0 0 000000000-1 0 0 0 0 0 0 000000000-1 0 0 0 0 0 0 000000000...4.直流系数的编码阶段 8×8图像块经过DCT变换之后得到的直流系数有两个特点：一是系数的数值比较大，二是相邻8×8图像块的直流系数值变化不大。 根据这个特点，JPEG算法使用了差分脉冲编码调制(DPCM)技术，对相邻图像块之间的直流系数的差值(Delta)进行编码，

Delta＝DC(0,0)k-DC(0,0)k-1

...5.交流系数的编码阶段量化交流系数的特点是1×64矢量中包含有许多“0”系数，并且许多“0”是连续的，因此使用非常简单和直观的游程长度编码(RLE)对它们进行编码。JPEG使用了1个字节的高4位来表示连续“0”的个数，而使用它的低4位来表示编码下一个非“0”系数所需要的位数，跟在它后面的是量化交流系数的数值。...6.熵编码阶段使用熵编码还可以对DPCM编码后的直流系数和RLE编码后的交流A系数作进一步的压缩。在JPEG有损压缩算法中，使用霍夫曼编码器来减少熵。使用霍夫曼编码器的理由是可以使用很简单的查表方法进行编码。压缩数据符号时，霍夫曼编码器对出现频度比较高的符号分配比较短的代码，而对出现频度较低的符号分配比较长的代码。这种可变长度的霍夫曼码表可以事先进行定义。...MPEG标准是面向运动图像压缩的一个系列标准。多媒体运动图像和伴音的数据压缩编码标准，即MPEG标准，实际上包括四个部分，MPEG视频、MPEG音频和MPEG系统、MPEG测试。...MPEG标准简介最初MPEG专家组的工作项目是3个，即在1.5Mbps，10Mbps，40Mbps传输速率下对图像编码，分别命名为MPEG-1，MPEG-2，MPEG-3。MPEG-3后被取消.为了满足不同的应用要求，MPEG又将陆续增加其他一些标准MPEG-4，MPEG-7，MPEG-21。...

MPEG算法编码过程和解码过程是一种非镜象对称算法(不对称)，解码过程要比编码过程相对简单些。MPEG-1和MPEG-2只规定了解码的方案，重点将解码算法标准化。最近几年，随着MPC性能的提高，软件解压功能也逐渐得到支持。...在MPEG中将图像分为3种类型：I图像：也叫I帧，就是静态图像，用JPEG帧内压缩的方法得到；P图像

用最近的前一个I图像(或P图像)预测编码得到(前向预测)，称为前向预测；而且可以作为下一个B帧或P帧的照图像。B图像B图像在预测时，既可使用了前一个图像作参照，也可使用下一个图像做参照或同时使用前后两个图像作为参照图像(双向预测)。B图像压缩比最大，I图像压缩比最小。帧间编码技术...运动视频流的组成1、允许编码端自行选择I帧的使用频率和在视频流的位置，典型每秒使用2次。2、允许编码端自行选择任何两帧参考图像（I，P）之间的B帧。插入两个B帧较为适宜。...运动图像的显示顺序与传输顺序不同显示的顺序：1234567

IBBPBBP

传输的顺序：1423756

IPBBPBB

MPEG编码器需对上述图像重新排序，以便解码器高效工作，因为参照图像必须先于B图像恢复之前恢复。...压缩技术比较...音频压缩编码标准及应用范围

G.7111972年CCITT为电话质量和语音压缩制定。其速率为

64kb/s，使用非线性量化技术，主要用于公共电话网中。

G.7221988年CCITT为调幅广播质量的音频信号压缩制定，它使用 子带编码(SBC)方案，其滤波器组将输入信号分成高低两个子带信 号，然后分别使用ADPCM进行编码。G.722能将224kb/s的调幅广播 质量的音频信号压缩为64kb/s，主要用于视听多媒体和会议电视 等。

G.7231996年ITU-T通过了——“用于多媒体传输的5.3kb/s或6.3kb/s

双速率话音编码”标准。它采用多脉冲激励最大似然量化(MP-MLQ)

算法，此标准可应用于视频电话及IP传输电话等方面。

G.728 使用基于低时延码本激励线性预测编码(LD-CELP)算法，其速率为

16kb/s，主要用于公共电话网中。

G.729它使用8kb/s的共轭结构代数 码激励线性预测(CS-ACELP)算法，此标准在无线移动网、数字多 路复用系统和计算机通信系统中应用。...运动视频定量要求技术或标准未压缩的Mbps压缩的Mbps质量HDTV 1920Xl080／60fps未压缩的压缩的演插室质量数字电视未压缩的

压缩的常规广播质量电视

VCR品质

视频会议MPEG一2ITU-R601MPEG-2MPEG-2 MPEG-1 H.261

2000一166一一一一一25一30

3一6 2一4 1．2 0．1...视频压缩编码标准及其应用范围

目前，由国际标准化组织(ISO)和国际电联(ITU-T)

正式公布的视频压缩编码标准中，有MPEG系列和

H.26x系列建议。...

H.261

CCITT制定的国际上第一个视频压缩标准，主要用于电视电话和会议电视，以满足ISDN日益发展的需要。

H.261视频压缩算法的核心是运动估值预测和DCT编码，其许多技术(包括视频数据格式、运动估算与补偿、DCT变换、量化和熵编码)都被后来的MPEG-1和MPEG-2所借鉴和采用。...

MPEG-1标准

“运动图像和伴随声音的编码——用于速率约在1.5Mb/s以下的数字存储媒体”。 主要用于多媒体存储与再现，如VCD等。

MPEG-1采用CIF视频格式，帧速率为25帧/秒或30帧/秒，码率为1.5Mb/s(其中视频约1.2Mb/s，音频约0.3Mb/s)。MPEG-1为了追求更高的压缩率，同时满足多媒体等应用所需的随机存取要求，将视频图象序列划分为I帧、P帧和B帧，根据不同的图象类型而不同对待。 该标准草案于1991年11月完成，1992年11月正式通过。...

MPEG-2标准

基本算法也是运动补偿的预测和带有DCT的帧间内变长编码。 继MPEG-1之后，MPEG制定的又一视频压缩标准（ISO/IEC13818)（其中视频部分即为H.262）。它能适用于更广的应用领域，主要包括数字存储媒体，广播电视和通信。制定MPEG-2标准的出发点是保持通用性，适用于广泛的应用领域、比特率、分辨率、质量和服务。MPEG-2适于高于2Mb/s的视频压缩，这包括了原打算为HDTV的发展而制定MPEG-3标准的内容。 根据MPEG-2的标准CCIR601格式(702×576×25帧)的信号可压缩到4Mb/s～6Mb/s，而HDTV格式(1280×720×60帧)的信号可压缩到20Mb/s左右。...

H.263及H.263+

H.263是ITU-T的关于低于64kb/s比特率的窄带通道视频编码建议，其目的是能在现有的电话网上传输活动图象。 由于H.263是面向低速信道的，所以必须在帧频和图象失真之间作出选择。H.263是在H.261建议的基础上发展起来的，其信源编码算法仍然是帧间预测/DCT混合编码，但H.263与H.261不同的是，它采用半象素的分辨率进行运动补偿，它处理的图象格式可以覆盖从sub-QCIF到16CIF，而且，H.263还提供了4种可协商选择的编码方法：无限制范围的运动矢量、基于语法的算法编码方法、先进预测和PB帧。...

MPEG-4标准

1994年，MPEG专家组正式开始制定MPEG-4标准，到1998年11月将发布MPEG-4视频国际标准草案。它主要是针对多媒体应用的，对可移动性的视频编码速率为5～64kb/s，而对影视应用最高速率可达2Mb/s。MPEG-4标准的突出特点是对音视频数据采用基于内容(Content-based)的操作、存取及传输。 为了达到此目的，MPEG-4引入了“视频对象”(VO)的概念。这样可把视频流中的每一帧分割成任意形状的图象区域—称为视频对象平面(VOP)，然后根据每一VOP的特点和需要，分别进行编码。要获得VOP，必须使用图象分割技术，如果将纹理信息与运动信息结合起来，则可产生较好的效果。

...

MPEG-4标准

MPEG-4标准是一个开放、灵活、可扩展的结构形式，可随时加入新的、有效的算法模板