多媒体数据压缩技术

第四章数据压缩技术

DataCompressionTechnologies本章主要介绍目前用得最多和技术最成熟的数据压缩编码技术。数据压缩可分成两种类型，一种叫做无损(lossless)压缩，另一种叫做有损(lossy)压缩。无损压缩编码技术包括霍夫曼编码、算术编码、RLE编码和词典编码。有损压缩技术如离散余弦变换、小波变换等。2024/5/141内容提纲4.1

数据压缩技术概述4.2

霍夫曼(Huffman)编码算法4.3

算术(Arithmetic)编码算法4.4RLE编码(RunLengthEncoding)算法4.5

词典(Dictionary)编码算法参考文献与作业2024/5/142作业运用Huffman,算术编码，LZ77分别对下段文字进行编解码：(Huffman编码可设置码表)Gridcomputingisbecominganimportantframeworkforenablingapplicationstoutilizewidelydistributedcollectionsofcomputationalanddataresources,howevercurrentgridsoftwareisstillimmatureandratherdifficulttouse.TheGlobusGridToolkitisasetoflow-leveltools,protocolsandservicesthathasbecomeadefactostandardforbasicgridcomputinginfrastructure.TheGlobusResourceAllocationandManagement(GRAM)serviceprovidesforthemanagementandremoteexecutionofjobsdefinedusingastandardResourceSpecificationLanguage(RSL).Currently,theGRAMhasverylimitedfunctionality,whichmakesitmoredifficulttodevelopgridapplications.Onelimitationisthelackofsupportforapplicationsthatrequireaspecialexecutionenvironment,suchasJavaapplicationsthatrunwithinaJavaVirtualMachine.Cumbersomeworkaroundsarenecessarytorunsuchapplications.ThecurrentGRAMaddressestheseproblemsinaratheradhocwayforcertainspecificcases,howeverthereisnogeneral,well-definedmechanismforsupportingarbitraryexecutionenvironments.HereweoutlinesomeoftheproblemswiththecurrentGlobusGRAMspecificationandprovideaproposalforhowtheymightbeaddressedbydefiningsomeextensionstothestandardRSLsupportedbytheGRAM,aswellassomemodificationstothedesignoftheGRAMthatwouldenableittosupportarbitraryexecutionenvironments.WegiveexamplesofhowourproposedsystemcanprovideimprovedsupportforJavaapplicationsandclustermanagementsystems,anddescribeourongoingworkinimplementingprototypesoftheseproposedGRAMextensions.2024/5/143参考文献题名：多媒体数据压缩技术丛编题名：全国高技术重点图书ISBN号：7-5053-2206-0出版项：北京电子工业出版社1994.4著者：高文题名：数据压缩技术及其应用丛编题名：计算机科学大众丛书ISBN号：

7-5053-3253-8出版项：北京电子工业出版社1995著者：袁玫,袁文题名：数据压缩技术原理与范例ISBN号：

7-03-004846-6出版项：北京科学出版社1995著者：(美)MarkNelson题名：数据压缩技术及其应用ISBN号：7-115-03835-X出版项：北京人民邮电出版社1989.6著者：(美)林奇(Lynch,T.J.)2024/5/144数据压技术缩概述

AnIntroductiontoDataCompression基本概念与定义数据压缩技术的分类常用的数据压缩方法§4.12024/5/145数据压缩的必要性数据通信数据存储…24BitBitmap(193k)JPEG(10k)2024/5/146考虑的因素不能失真磁盘文件。。。允许失真在不影响“质量”的情况下ABCAACBBCABCAACBBC#$%^&*压缩编码数据还原256color(66k)24bit(193k)2024/5/147基本概念无损压缩(LosslessCompression)是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同。有损压缩(LossyCompression)是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2～1/4。一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)压缩算法。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。2024/5/148数据压缩技术的分类2024/5/149统计编码中“熵”的基本概念熵(Entropy)熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。某个事件的信息量用表示，其中pi为第i个事件的概率，0<pi

≤1。信源s的熵的定义：按照香农(Shannon)的理论，信源s的熵定义为

其中：pi

为si

在s中出现的概率，表示包含在si

中的信息量，也就是编码所需要的位数，例如，一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为pi=1/256，编码每一个象素点就需要8位。2024/5/1410常用的压缩方法统计编码图像。。。预测编码音频。。。变换编码图像。。。混合编码标准量化也是实现数据压缩的一种手段2024/5/1411霍夫曼编码

HuffmanEncodingSystem霍夫曼(Huffman)在1952年提出的一种编码方法，即从下到上的编码方法。该方法根据待编码信息的统计特征(熵)，先按出现频率的大小从下到上构建编码树；然后按类似于前序(后序)遍历的方法赋予树的每条边一个码值，“0”或“1”；最后探索根到叶结点，根到叶所经历边码的序列即为该字符的“码值”。霍夫曼编码分为定长编码和变长编码两种。后者的应用比较广泛。此外，霍夫曼编码自含同步码，码串中不需要另加标记。§4.22024/5/1412编码算法主要步骤(可变长编码)统计各字符出现的频率根据贪心策略构建编码树按类似于前序遍历的方法递归地遍历编码树，对于连接左子树的边赋予边码为“0”，连接右树的边码为“1”。反过来亦可。即算从“根”到“叶”的边码序列，得到某字符的编码。0.12820.15380.15390.17950.38460.28200.33340.61541.000001001110ABCDEA:“0”B:“100”C:“101”D:“110”E:“111”2024/5/1413编码方法Huffman编码举例符号出现的次数log2(1/pi)分配的代码需要的位数A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115从下到上按贪心策略进行选择来构建二进制编码树。在进行编码树遍历时规定连接“左”子数的边码为“0”，右子树的码为“1”。反过来也可以。从根到叶的边码序列为该叶节点的编码，如C的编码为“101”。2024/5/1414霍夫曼编码小结霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码(自含同步码，在编码之后的码串中都不须要另外添加标记符号)。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码采用霍夫曼编码时有两个问题值得注意：霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(errorpropagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。2024/5/1415算术编码

ArithmeticEncodingSystem算术编码在图像数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。§4.32024/5/1416关于算术编码简要历史：20世纪60年代初，Elias提出了算术编码(ArithmeticCoding)概念。1976年Rissanen和Pasco首次介绍该实用技术。基本原理：将编码的信息用0到1之间的实数区间进行编码算术编码用到两个基本的参数：符号的概率：信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。

编码间隔：编码过程中的间隔决定了符号压缩后的输出。

2024/5/1417算术编码简介编码举例假设信源符号、出现的概率和处世间隔如下：编码过程：假设消息序列的输入顺序为：10001100101101。符号00011011概率0.10.40.20.3初始编码间隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)2024/5/1418算法描述考虑一个有M个符号ai=(1,2,…,M)的字符表集，假定ai的概率p(ai)=pi，而输入的符号用xn表示，第n个子间隔的范围用 表示，其中：

l0=0,d0=0,p0=0, ln表示间隔左边界的值， rn表示间隔右边界的值， dn=rn-ln表示间隔长度。2024/5/1419算法描述编码步骤如下：步骤1：首先在1和0之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率，初始子间隔的范围为I1。令d1=r1-l1，L=l1

和R=r1。步骤2：L和R的二进制表达式分别表示为：

和

其中uk

和vk

等于“1”或者“0”。比较u1

和v1

：①如果

，不发送任何数据，转到步骤3。反之，发送二进制符号u1。

比较u2

和v2

：①如果

，不发送任何数据，转到步骤3；反之，发送二进制符号u2。

…这种比较一直进行到两个符号不相同为止。步骤3：令n=n+1，读下一个符号。假设第n个输入符号为xn=ai

，按照以前的步骤把这个间隔分成子间隔In；并令L=In

，R=rn

和dn=rn-ln，

转步骤2。2024/5/1420算法描述编码过程：步骤输入符号编码间隔编码判决110[0.5,0.7)符号的间隔范围[0.5,0.7)200[0.5,0.52)[0.5,0.7)间隔的第一个1/10311[0.514,0.52)[0.5,0.52)间隔的最后一个1/10400[0.514,0.5146)[0.514,0.52)间隔的第一个1/10510[0.5143,0.51442)[0.514,0.5146)间隔的第五个1/10开始，二个1/10611[0.514384,0.51442)[0.5143,0.51442)间隔的最后3个1/10701[0.5143836,0.514402)[0.514384,0.51442)间隔的4个1/10，从第1个1/10开始8从[0.5143876,0.514402中选择一个数作为输出：0.51438762024/5/1421算法描述译码过程步骤间隔译码符号译码判决1[0.5,0.7)100.51439在间隔[0.5,0.7)2[0.5,0.52)000.51439在间隔[0.5,0.7)的第1个1/103[0.514,0.52)110.51439在间隔[0.5,0.52)的第7个1/104[0.514,0.5146)000.51439在间隔[0.514,0.52)的第1个1/105[0.5143,0.51442)100.51439在间隔[0.514,0.5146)的第5个1/106[0.514384,0.51442)110.51439在间隔[0.5143,0.51442)的第7个1/107[0.51439,0.5143948)010.51439在间隔[0.51439,0.5143948)的第1个1/107译码的消息：100011001011012024/5/1422算术编码小结在算术编码中需要注意的几个问题：由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。算术编码器对整个消息只产生一个码字，这个码字是在间隔[0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改。2024/5/1423RLE编码

RunLengthEncodingSystem现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。在这种情况下就不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程编码，常用(runlengthencoding，RLE)表示，具有相同颜色并且是连续的象素数目称为行程长度。§4.42024/5/1424RLE简介设有一幅灰度图像第n行的象素值为：用RLE编码方法得到的代码为：80315084180。 代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。2024/5/1425RLE简介(cont.)问题：编码如何处理多行图像数据呢？RLE编码小结RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。然而，RLE对颜色丰富的自然图像就显得力不从心，在同一行上具有相同颜色的连续象素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。请注意，这并不是说RLE编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中还真少不了RLE，只不过是不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用。2024/5/1426词典编码

DictionaryEncodingSystem4.5.1

词典编码的思想4.5.2

LZ77

(Lempel–Ziv)算法4.5.3

LZSS

(Lempel–Ziv–Storer–Szymanski)算法4.5.4

LZ78

(Lempel–Ziv)算法4.5.5

LZW

(Lempel–Ziv–Waltch)算法§4.52024/5/1427词典编码的思想第一类词典编码企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。这里所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。2024/5/1428词典编码的思想(cont.)第二类词典编码企图从输入的数据中创建一个“短语词典(dictionaryofthephrases)”，这种短语不一定是具有具体含义的短语，它可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。2024/5/1429LZ77算法几个术语输入数据流(inputstream)：要被压缩的字符序列。字符(character)：输入数据流中的基本单元。编码位置(codingposition)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。前向缓冲存储器(Lookaheadbuffer)：存放从编码位置到输入数据流结束的字符序列的存储器。窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。指针(pointer)：指向窗口中的匹配串且含长度的指针。2024/5/1430LZ77算法(cont.)LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下：把编码位置设置到输入数据流的开始位置。查找窗口中最长的匹配串。以“(Pointer,Length)Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。2024/5/1431LZ77算法(cont.)LZ77算法举例位置123456789字符AABCBBABC步骤位置匹配串字符输出11--A(0,0)A22AB(1,1)B34--C(0,0)C45BB(2,1)B57ABC(5,2)C步骤：表示编码步骤。位置：表示编码位置，输入数据流中的第1个字符为编码位置1。匹配串：栏表示窗口中找到的最长的匹配串。字符：表示匹配之后在前向缓冲存储器中的第1个字符。输出：以“(Back_chars,Chars_length)Explicit_character”格式输出。2024/5/1432LZ77算法

(cont.)LZ77算法小结存在的缺点LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在如下两个方面：一是空指针二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。2024/5/1433LZSS算法LZSS编码算法的具体执行步骤如下：把编码位置置于输入数据流的开始位置。在前向缓冲存储器中查找与窗口中最长的匹配串

①Pointer：=匹配串指针。

②Length：=匹配串长度。判断匹配串长度Length是否大于等于最小匹配串长度(Length≥

MIN_LENGTH)，

如果“是”：输出指针，然后把编码位置向前移动Length个字符。

如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。如果前向缓冲存储器不是空的，就返回到步骤2。2024/5/1434LZSS算法(cont.)LZSS算法举例设有下列字符串编码步骤如下：位置1234567891011字符AABBCBBAABC步骤位置匹配串输出11--A22AA33--B44BB55--C66BB(3,2)78AAB(7,3)811CC2024/5/1435LZSS算法

(cont.)LZSS算法小结在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip,ARJ,LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。2024/5/1436LZ78算法几个术语符号字符流(Charstream)：要被编码的数据序列。字符(Character)：字符流中的基本数据单元。前缀(Prefix)：在一个字符之前的字符序列。缀-符串(String)：前缀＋字符。码字(Codeword)：码字流中的基本数据单元，代表词典中的一串字符。码字流(Codestream)：码字和字符组成的序列，是编码器的输出。词典(Dictionary)：缀-符串表。按照词典中的索引号对每条缀-符串(String)指定一个码字(Codeword)。当前前缀(Currentprefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。当前字符(Currentcharacter)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。当前码字(Currentcodeword)：在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串。2024/5/1437LZ78算法(cont.)LZ78编码算法步骤1：在开始时，词典和当前前缀P都是空的。步骤2：当前字符C：=字符流中的下一个字符。步骤3：判断P+C是否在词典中：(1)如果“是”：用C扩展P，让P：=P+C；(2)如果“否”：①输出与当前前缀P相对应的码字和当前字符C；②把字符串P+C添加到词典中。③令P：=空值。(3)判断字符流中是否还有字符需要编码①如果“是”：返回到步骤2。②如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。LZ78编码器的输出是码字–字符(W,C)对，每次输出一对到码字流中，与码字W相对应的缀-符串(String)用字符C进行扩展生成新的缀-符串(String)，然后添加到词典中。LZ78编码的具体算法如下：2024/5/1438LZ78算法(cont.)LZ78译码算法LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的缀-符串(String)用字符C进行扩展生成新的缀-符串(String)，然后添加到词典中。LZ78编码的具体算法如下：步骤1：在开始时词典是空的。步骤2：当前码字W：=码字流中的下一个码字。步骤3：当前字符C：=紧随码字之后的字符。步骤4：把当前码字的缀-符串(string.W)输出到字符流(Charstream)，然后输出字符C。步骤5：把string.W+C添加到词典中。步骤6：判断码字流中是否还有码字要译(1)如果“是”，就返回到步骤2。(2)如果“否”，则结束。2024/5/1439LZ78算法(cont.)LZ78算法举例假设有下列编码字符串：编码过程如下：位置123456789字符

ABBCBCABA步骤位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)步骤：编码步骤。位置：在输入数据中的当前位置。词典：添加到词典中的缀-符串，缀-符串的索引等于“步骤”序号。输出：以(当前码字W,当前字符C)简化为(W,C)的形式输出。与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目，而压缩率与LZ77类似。2024/5/1440LZW算法LZW算法中使用的术语与LZ78使用的相同，仅增加了一个术语—前缀根(Root)，它是由单个字符串组成的缀-符串(String)。在编码原理上，LZW与LZ78相比有如下差别：LZW只输出代表词典中的缀-符串(String)的码字(codeword)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-characterprefix)，因此在词典中搜索的第1个缀-符串有两个字符。2024/5/1441LZW算法(cont.)LZW编码算法2024/5/1442LZW算法(cont.)LZW编码算法LZW编码算法的具体执行步骤如下：步骤1：开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；步骤2：当前字符(C)：=字符流中的下一个字符；步骤3：判断缀-符串P+C是否在词典中

(1)如果“是”：P：=P+C //用C扩展P；

(2)如果“否”

①把代表当前前缀P的码字输出到码字流;

②把缀-符串P+C添加到词典;

③令P：=C //现在的P仅包含一个字符C;步骤4：判断码字流中是否还有码字要译

(1)如果“是”，就返回到步骤2；

(2)如果“否”

①把代表当前前缀P的码字输出到码字流;

②结束。2024/5/1443L