下载文档原格式
第三章多媒体数据压缩3.1 数据压缩的基本原理和方法3.1 数据压缩的基本原理和方法•压缩的必要性音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。
例如，一幅具有中等分辨率（640×480）的真彩色图像（24b/像素），它的数据量约为7.37Mb/帧，一个100MB（Byte）的硬盘只能存放约100帧图像。
若要达到每秒25帧的全动态显示要求，每秒所需的数据量为184Mb，而且要求系统的数据传输率必须达到184Mb/s。
对于声音也是如此，若采用16b样值的PCM编码，采样速率选为44.1kHZ ，则双声道立体声声音每秒将有176KB的数据量。
3.1 数据压缩的基本原理和方法•视频、图像、声音有很大的压缩潜力信息论认为：若信源编码的熵大于信源的实际熵，该信源中一定存在冗余度。
原始信源的数据存在着很多冗余度：空间冗余、时间冗余、视觉冗余、听觉冗余等。
3.1.1 数据冗余的类型•空间冗余：在同一幅图像中，规则物体和规则背景的表面物理特性具有相关性，这些相关性的光成像结果在数字化图像中就表现为数据冗余。
–一幅图象中同一种颜色不止一个象素点，若相邻的象素点的值相同，象素点间（水平、垂直）有冗余。
–当图象的一部分包含占主要地位的垂直的源对象时，相邻线间存在冗余。
3.1.1 数据冗余的类型•时间冗余：时间冗余反映在图像序列中就是相邻帧图像之间有较大的相关性，一帧图像中的某物体或场景可以由其它帧图像中的物体或场景重构出来。
–音频的前后样值之间也同样有时间冗余。
–若图象稳定或只有轻微的改变，运动序列帧间存在冗余。
3.1.1 数据冗余的类型•信息熵冗余：信源编码时，当分配给第i 个码元类的比特数b （y i ）=-log p i ，才能使编码后单位数据量等于其信源熵，即达到其压缩极限。
但实际中各码元类的先验概率很难预知，比特分配不能达到最佳。
实际单位数据量d>H （S ），即存在信息冗余熵。
数据结构中的数据压缩技术数据压缩技术是数据结构中一个重要的应用领域，它通过一系列算法和方法，将原始数据转换为更紧凑的形式，以减少存储空间和传输带宽的消耗。
在计算机科学领域，数据压缩技术被广泛应用于文件存储、网络传输、多媒体处理等方面。
本文将介绍数据结构中常见的数据压缩技术，包括无损压缩和有损压缩两种类型。
一、无损压缩无损压缩是指在数据压缩的过程中，不丢失任何原始数据信息，通过一定的编码方式将数据表示为更紧凑的形式。
常见的无损压缩算法包括：1. 霍夫曼编码（Huffman Coding）霍夫曼编码是一种基于字符出现频率的编码方式，出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示，从而实现对数据的压缩。
霍夫曼编码是一种前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀，这样可以避免编码歧义。
霍夫曼编码在文件压缩、通信传输等领域有着广泛的应用。
2. LZW压缩算法（Lempel-Ziv-Welch Compression）LZW压缩算法是一种基于字典的压缩算法，通过维护一个动态字典来实现数据的压缩。
算法首先将输入的数据序列划分为不同的子串，然后将子串映射为字典中的索引，从而实现对数据的压缩。
LZW算法在图像压缩、文本压缩等领域有着广泛的应用。
3. 等长编码（Run-Length Encoding）等长编码是一种简单有效的无损压缩算法，它通过统计连续重复出现的数据值，将重复的数据值用一个计数值和一个数据值的形式表示，从而实现对数据的压缩。
等长编码在处理连续重复数据较多的情况下有着较好的压缩效果。
二、有损压缩有损压缩是指在数据压缩的过程中，会丢失部分原始数据信息，但通过牺牲一定的精度和质量来实现更高的压缩比。
常见的有损压缩算法包括：1. JPEG压缩算法（Joint Photographic Experts Group）JPEG是一种常用的图像压缩算法，它通过离散余弦变换（DCT）将图像数据转换为频域表示，然后对频域数据进行量化和熵编码，最终实现对图像的压缩。
压缩技术压缩技术是指将某个数据或文件通过一系列的算法和方法进行处理，以减小其存储和传输所需的空间或带宽的过程。
这种技术在现代信息技术领域中广泛应用，对于节约存储资源和提高数据传输效率有着重要的作用。
本文将介绍压缩技术的概念、分类、基本原理和常见的压缩算法等内容。
压缩技术的概念非常简单明了，即通过某种方式将数据或文件的大小减小，使其可以更有效地存储和传输。
在信息技术领域中，数据量庞大，存储空间和带宽是宝贵的资源，因此对数据进行压缩处理是非常必要的。
压缩技术可以根据压缩的过程分为有无损压缩和有损压缩两类。
有无损压缩是指在压缩和解压缩之间不会丢失任何数据，数据的内容保持完整。
而有损压缩则在压缩的过程中会丢失一部分数据，但通常能够保持数据的主要特征和可用性。
在压缩技术中，有很多基本的原理和算法被广泛应用。
其中，最常见的有字典压缩、哈夫曼编码和算术编码等。
字典压缩是一种利用文件中重复出现的片段进行压缩的方法。
它通过构建一个字典，将文件中出现的片段存储在字典中，并用索引号来表示。
这样，在压缩的过程中，只需要存储索引号，而不需要存储实际的数据片段，从而达到减小文件大小的目的。
哈夫曼编码是一种根据数据出现的频率来构建编码表的方法。
在哈夫曼编码中，频率较高的数据被赋予较短的编码，而频率较低的数据被赋予较长的编码。
这样，在压缩的过程中，出现频率高的数据可以用较少的比特表示，而出现频率低的数据则用较多的比特表示。
这种编码方式能够有效地减小文件大小。
算术编码是一种根据数据出现的概率来进行编码的方法。
在算术编码中，每个数据的编码长度根据其出现的概率进行调整。
出现概率高的数据，其编码长度较短；而出现概率低的数据，其编码长度较长。
通过这种方式，可以达到减小文件大小的效果。
除了上述的基本原理和算法外，压缩技术还有很多其他的方法和算法，如Lempel-Ziv-Welch（LZW）压缩算法、Burrows-Wheeler Transform（BWT）压缩算法等。
数据压缩原理.数据压缩是一种将数据转换为更小的格式以节省存储空间的技术。
数据压缩的原理是利用数据中的重复性来减少存储需要。
通常情况下，压缩技术可分为有损压缩和无损压缩两种类型。
1. 无损压缩无损压缩技术能够在不改变数据质量的情况下减少数据的存储空间。
这种压缩方式通常利用数据的冗长性和重复性来减少存储空间。
它并不会改变数据的结构或减少数据的精度。
这种方式的典型应用包括文本文件压缩，图像压缩等。
无损压缩的两种典型方法是行程长度编码和霍夫曼编码。
有损压缩技术是指通过牺牲一定的详细信息，从而降低数据精度，以达到减少存储空间的目的。
这种方式用于图像压缩、音频压缩和视频压缩等领域。
例如，在图像压缩过程中，通过去除低频信号和高频信号来实现压缩。
虽然它会在一定程度上减少数据的精度，但由于数据的细节很少被注意到，这种压缩方法通常被接受。
3. 行程长度编码行程长度编码是一种简单的无损压缩技术。
它按照数据序列中连续重复的字符序列进行编码。
行程长度编码通常使用两个字节来表示一个字符序列，其中第一个字节包含字符的数量，第二个字节包含字符的实际值。
这种编码技术在处理文本文件时非常有效，因为在文本文件中存在很多重复的字符序列。
4. 霍夫曼编码霍夫曼编码是一种常用的无损压缩技术，它利用字符出现的概率来生成具有平衡前缀属性的可变长度代码。
霍夫曼编码使用更短的代码表示更频繁出现的字符，以尽可能减少数据的存储空间。
通过对霍夫曼编码的调整可以使得编码后的数据更加紧凑。
5. 图像压缩图像压缩技术是一种将图像数据转化为更小格式的技术。
它减少了由于储存大型图像数据产生的存储空间占用。
常见的图像压缩技术包括JPEG、PNG等。
其中最常用的是JPEG 压缩。
JPEG利用人眼对颜色变化敏感的特性来实现压缩。
6. 音频压缩8. 总结数据压缩是一种重要的技术，它可以减少数据存储空间的占用，降低储存成本。
数据压缩技术包括有损压缩和无损压缩两种类型。
在处理大型数据集和高性能计算系统时，数据压缩发挥着越来越重要的作用。
一、名词解释1、数据压缩：以最小的数码表示信源所发的信号，减少容纳给定消息集合或数据采样集合的信号空间。
2、数据压缩比：将压缩前每个信源符号（取样）的编码位数（mlog）与压缩后平均每符号的编码位数（l）之比，定义为数据压缩比。
3、均匀量化：把输入信号的取值域按等距离分割的量化称为均匀量化。
4、最优量化（MMSE准则）：使均方误差最小的编码器设计方法称为最小均方误差（MMSE）设计。
以波形编码器的输入样值与波形解码器的输出样值之差的均方误差作为信号质量的客观评判标准和MMSE的设计准则。
（能使量化误差最小的所谓最佳量化器，应该是非均匀的。
）5、信息熵定义：信息量的概率平均值，即随机变量的数学期望值，叫做信息熵或者简称熵。
6、统计编码定义：主要利用消息或消息序列出现概率的分布特性，注重寻找概率与码字长度间的最优匹配，叫做统计编码或概率匹配编码，统称熵编码。
7、变长编码：与等长编码相对应，对一个消息集合中的不同消息，也可以用不同长度码字来表示，这就叫做不等长编码或变长编码。
8、非续长码：若W中任一码字都不是另一个码字的字头，换句换说，任何一个码字都不是由另一个码字加上若干码元所构成，则W称为非续长码、异字头码或前缀码。
9、游程长度：是指字符（或信号采样值）构成的数据流中各字符重复出现而形成字符串的长度。
10、电视图像的取向：我国彩色电视制式采用逐行倒相的PAL-D制。
11、HVS的时间掩蔽特性：指随着时间变化频率的提高，人眼对细节分辨能力下降的特性。
12、HVS的空间掩蔽特性：指随着空间变化频率的提高，人眼对细节分辨能力下降的特性。
13、HVS的亮度掩蔽特性：指在背景较亮或较暗时，人眼对亮度不敏感的特性。
14、CIF格式：是常用的标准图像格式。
是一种规范Y、Cb、Cr色差分量视频信号的像素分辨率的标准格式。
像素。
15、SIF格式:是一种用于数字视频的存储和传输的视频格式。
16、压扩量化：由于低电平信号出现概率大、量化噪声小；高电平信号虽然量化噪声变大，但因为出现概率小，总的量化噪声还是变小了，从而提高量化信噪比。
数据压缩原理
数据压缩是将数据转化为更紧凑的形式，以减少存储空间或传输带宽的技术。
数据压缩的原理可以分为无损压缩和有损压缩。
无损压缩是指压缩后的数据可以完全还原为原始数据，不会损失任何信息。
其中常用的方法包括：
1. 字典压缩：建立一个字典，将数据中重复出现的序列映射为较短的编码。
在解压时通过字典进行反映射。
2. 霍夫曼编码：根据数据出现的频率构建一棵二叉树，将出现频率较高的数据编码为较短的码字。
在解压时根据二叉树进行解码。
3. 位图压缩：针对大型二进制数据，使用稀疏矩阵表示，只记录其中非零元素的位置和值。
有损压缩是指在压缩数据时会丢失部分信息，但能够保证整体视觉、听觉或感知上的一致性。
常用的方法包括：
1. 采样压缩：降低音频或视频数据的采样率，减少采样点的数量。
2. 量化压缩：通过减少数据的精度或调整数据的表示范围，从而减小数据占用的位数。
3. 基于模式识别的压缩：通过对数据中的模式进行建模，并仅
存储模型参数，以减小数据的表示大小。
值得注意的是，压缩率可以根据不同的压缩算法和数据类型而有所不同。
一般来说，无损压缩通常适用于文本、程序代码等需要完整保留信息的数据，而有损压缩则适用于音频、视频等在一定程度上容忍信息丢失的数据。
第五讲数据压缩技术基础5.1数据压缩的技术指标是什么？1.数据压缩的目的通过压缩手段把数据量压下来以压缩形式存储和传输，这样既节约了空间，又提高了传输速率，同时也使计算机可实时处理音频视频信息，以保证播放出高质量的音频、视频节目称为可能。
对图像的压缩编码有多种方法。
如亚采样编码思想：一组像素可用一个像素表示以达到压缩图像存储容量。
又如游程编码思想：对黑白图像的编码，可将每行的像素分为白段、黑段、白段、黑段、白段…后，每段像素采用其长度（计数）表示：计数1，计数2，计数3，计数4，计数5，计数6…。
实际上，一个好的编码系统都是采用多种算法、多次处理而成的。
2.数据压缩的基本理论数据压缩是通过去除多媒体中冗余数据可大大减少原始数据量，从而使数据量得到压缩。
信息论认为：若信源编码的熵（entropy）大于信源的实际熵，则该信源一定存在冗余。
去除冗余不会减少信息量，仍可原样恢复数据；但若减少了熵，则数据不能完全恢复。
不过在允许的范围内损失一定的熵，数据可得到近似的恢复。
所谓“熵”，原指热能除以温度所得的商，即热量转化为功的程度。
这里是指信源发出任意一个随机变量的平均信息量。
所谓“信息量”是指从N个相等可能事件中选出一个事件所需的信息度量。
3.原始数据的冗余类型(1)空间冗余：同一帧画面中，规则景物和规则背景的表面各采样点的颜色之间存在空间连贯性。
(2)时间冗余：在图像序列中，相邻帧图像之间同一场景所包含背景和移动物体具有共同性。
(3)结构冗余：图像的像素值存在明显的分布模式结构产生的数据冗余。
(4)知识冗余：某些规律性结构可通过先验知识和背景知识得到的冗余。
(5)视觉冗余：人眼的视觉系统对图像场视觉的敏感和不敏感同等对待而产生了更多数据冗余。
(6)区域相似性冗余：图像中的两个或多个区域所对应的像素值具有相似性使产生的数据重复存储(7)纹理的统计冗余：图像纹理在统计上服从某一分布规律的冗余。
4.压缩比压缩比（%）=压缩后的图像数据量/ 压缩前的图像数据量若原数字文件数据容量为100MB，经压缩后的数据容量为50MB，则图像压缩比为50%。
显然，压缩比越小，压缩后的图像文件数据量也越小，图像的质量有可能损失越多。
实际上，图像的压缩效果不但与压缩前的图像效果有关，也与采用的压缩方法有关。
5.数据压缩的技术指标(1)压缩比：压缩前、后所需的信息存储量之比要大。
(2)压缩和解压速度：实现数据压缩的算法要简单，压缩解压的速度要快。
(3)恢复效果：解压后的恢复效果要好，要尽可能地恢复原始数据。
5.2数据压缩编码方法如何分类？1.根据熵有无损失分类(1)无损压缩无损压缩也称为不失真压缩，是去掉或减少数据的冗余进行压缩。
这些冗余值可重新插入数据中来实现原始数据的完全恢复而不失真。
但这种压缩方法的压缩比受到统计冗余度的理论限制，一般为2：1-5：1。
该压缩方法适用于文本、数据、程序和应用场合的图像数据的压缩。
常用无损压缩的编码方案有：游程编码、Huffman编码、算术编码及LZW 编码等。
(2)有损压缩有损压缩也称为有失真压缩，是减少信息量（压缩熵）来进行压缩。
这些损失是不能再恢复的，因此这种压缩是不可逆的。
一般利用人的视觉和听觉对图像或声音中的不敏感性进行压缩，虽损失一息且不能完全恢复原始数据，但换取了高的压缩比。
该压缩方法适用于语音数据、图像数据和视频数据的压缩。
常用有损压缩的编码方案有：PCM、预测编码、变换编码、插值及外推法编码等。
2.根据数据压缩算法分类(1)统计编码统计编码也称信息熵编码，是根据信源所含有的平均信息量（熵）即无失真编码的极限的无失真编码定理进行编码。
统计编码常用的是Huffman编码（利用信源概率分布）、游程编码（利用相关性）和算术编码（利用信源概率分布）等。
(2)预测编码预测编码是根据某一数据模型利用以往样本值对新样本值进行预测，再将样本实际值与预测值的差进行编码。
若模型足够好，且样本序列的时间相关性较强，则误差信号幅度将远小于原始信号，即可用较少的值对其差值进行量化，得到较大压缩的效果。
预测编码常用的是差分脉冲编码调制（DPCM）和自适应的差分脉冲编码调制（ADPCM）。
(3)变换编码变换编码将通常在空间域描写的图像信号变换到另外一些正交矢量空间（即变化域）中进行描写。
选择合适的变换关系使变换域中描写的各信息分量之间的相关性很小或互不相关，从而达到数据压缩的目的。
(4)分析合成编码分析合成编码是通过对原始数据的分析，将其分解为一系列更适合表示的基元或从中提取若干具有更本质意义的参数，编码仅针对这些基本单元或特征参数进行。
解压时则借助一定的规则或模型按一定的算法将这些基元或参数再合成逼近原始数据的数据。
常用的编码有子带编码、小波变换编码以及分析图形编码等。
5.3统计编码的基本原理是什么？1.统计编码基本理论（P120~129）2.统计编码基本思想统计编码也称熵编码，是根据消息出现概率的分布特性进行的压缩编码。
其编码基本思想是：识别一个给定的数据流中出现概率最高的比特或字节模式，用比原始比特更少的比特数来对其进行编码，即出现概率越低的模式编码位数就越多；而出现概率越高的模式编码位数就越少。
若码流中所有模式出现的概率相等，平均信息量最大，则信源没有冗余。
统计编码的基本方法是：在消息和码字之间找到明确的一一对应关系，以便在恢复时能准确无误地再现出来，或相似地找到相当对应关系，并把这种失真或不对应概率限制在可容忍的范围（如运动图像的数据压缩）。
变长码是最常使用的方法，该编码的原始思想起源于Morse电报码及速记法。
例如Morse码中e是最常出现的，编码为“.”；而q最少出现，则编码为“..—”。
其信源符号与码字一一对应，因此可准确无误地再现。
且在编译码过程中不损失任何信息，属于冗余压缩法。
变长码的最佳编码定理：在变长码中，对出现概率大的信息符号以短字长编码，对出现概率小的信息符号以长字长编码。
若码字长度严格按符号概率大小的相反顺序排列，则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度。
3.常用的编码方案(1)游程编码将数据流中连续出现的字符（即游程）用单一的记号来表示。
如字符串abacccbbaaaa，可压缩为aba3c2b4a。
该编码的压缩效果不太好，但编码解码的速度快，因此仍得到广泛应用。
许多图像视频文件（BMP、TIF及A VI等）采样该压缩。
(2)哈夫曼编码将信源符号按概率的大小排序，概率大的为短码，概率小的为长码。
其编码过程如下：a.将信源符号按概率递减顺序排列；b.把两个最小的概率相加，作为新符号的概率；c.重复A、B，直到概率和达到1为止；e.在每次合并消息时，将被合并的消息赋予1和0或0和1；f.寻找从每一信源符号到概率为1的路径，记录下路径上的0和1；g.对每个符号写出从码树的根到终结点1、0序列。
例：信息符号概率x1 0.35 0 00x2 0.20 00.60 0 10x3 0.15 00.25 1 1.00 根010x4 0.10 10.40 1 011x5 0.10 0 1 110x6 0.06 00.10 0.20 1110x7 0.04 1 1 1111(3)算术编码将一个信源集合表示为实线上的0到1之间的一个区间。
这个集合中的每个元素都要用来缩短这个区间。
信息集合的元素越多，所得区间则越小。
当区间变小时，就需要更多的数位来表示这个区间。
算术编码初级阶段预设一个大概率为Pe，小概率为Qe。
其编码过程如下：a.设编码初始化子区间为[0，1]，Qe从0算起，则Pe=1-Qe。
随着被编码数据量符号的输入，子区间逐渐缩小；b.新子区间的起始位置= 前子区间的起始位置+当前符号的区间左端*前子区间长度；新子区间的长度= 前子区间的长度*当前符号的概率（即范围长度）；c.最后得到的子区间的长度决定了该区域内的某一个数所需位置。
△已知符号串（信源）符号由0，1组成，0出现的概率为1/4，1出现的概率为3/4。
按以上算术编码规则对符号串1011进行编码：这里，Qe=1/4，Pe=3/4，初始子区间为[0，1]序号 符号 子区间起始位置 子区间长度1 1 1/4 3/42 0 1/4 3/163 1 19/64 9/644 1 85/256 27/256最后的子区间起始位置=85/256=0.01010101B ，子区间长度=27/256=0.00011011B ，子区间尾=85/256+27/256=0.01010101B+0.00011011B=0.0111。
因此编码输出应落在子区间的头尾之间[0.0101~0.0111]。
可在此范围内选取一个码字较短的作为输出，如0.011。
传送时只传送011即可，该码字即为符号串1011的编码输出。
在算术编码中，出现概率相同的串区间长度相同；出现概率大的串码长较短。
5.4预测编码的基本原理是什么？1.预测编码基本理论基于现代统计学和现代控制论，是数据压缩理论的一个重要分支。
它指出离散信号之间存在着一定相关性，即数据在时间和空间上具有相关性的特点。
2.预测编码基本思想预测编码是利用相邻像素的相关性预测当前像素的值进行的编码。
其编码思路是：利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差（预测误差）进行量化编码。
如果预测比较准确，那么误差信号就会很小。
因此，在同等精度要求的条件下，可用较少的数码表示差值，从而达到了压缩数据的目的。
预测编码常用的是差分脉冲编码调制（DPCM ）和自适应的差分脉冲编码调制（ADPCM ）。
由于声音和图像数据均由采样得到，且相邻值之间的差不会很大，可以用较少的位数来表示差值，因此适用于声音和图像数据的压缩。
3.常用的编码方案(1)DPCM 编码PCM （脉冲调制）编码是将原始信号先经过时间采样，然后对每一个样值进行量化后作为数字信号的输出；而在DPCM （差分脉冲调制）编码中，为了压缩传输的数码，可不对每一个样值都进行量化，而是预测下一样值，并量化实际值与预测值之间的差。
解压缩时使用同样的预测器，将这一预测值与存储的已量化的差值相加，产生出近似的原始信号，从而基本恢复原始数据。
一般该编码每样值可压缩到2~4bit 。
其编码过程如下： a.测出像素（i ，j ）及相邻像素的样值；b.由以往3个相邻像素的样值相加得到当前像素的预测值：),1()1,1()1,(),(321j i f a j i f a j i f a j i f -+--+-=∧其中，1a 2a 3a 为预测系数，为待定值。
若系数为常量，则为线性预测。
c.求出预测误差，并进行量化：)],1()1,1()1,([),(),(),(),(321j i f a j i f a j i f a j i f j i f j i f j i e -+--+--=-=∧ d.由均方误差函数求出预测系数1a 2a 3a ，以得到最佳线性预测系数：232122)],1()1,1()1,([),([)],(),([(j i f a j i f a j i f a j i f E j i f j i f E e -+--+--=-=∧其中，E 是数学期望，e 2对1a 2a 3a 求偏导并令其为0，解方程得预测系数。
