无损数据压缩课件

多媒体图像编码分类多媒体数据压缩编码PCM量化预测编码DPCM基于频率变换编码子带编码小波变换编码基于统计哈夫曼编码算术编码游程编码RLE国际标准JPEG标准（静态图像）MPEG标准（电视图像）H.261（可视通信）MHEG标准（超媒体）多媒体图像编码分类多媒体数据压缩编码PCM量化预测编码DPC多媒体核心技术：压缩数据压缩起源于40年代由ClaudeShannon首创的信息论，其基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这条定理借用了热力学中的名词“熵”(Entropy)来表示一条信息中真正需要编码的信息量考虑用0和1组成的二进制数码为含有n个符号的某条信息编码，假设符号Fn在整条信息中重复出现的概率为Pn，则该符号的熵也即表示该符号所需的位数多媒体核心技术：压缩数据压缩起源于40年代由Claud考虑用0和1组成的二进制数码为含有n个符号的某条信息编码，假设符号Fn在整条信息中重复出现的概率为Pn，则该符号的熵也即表示该符号所需的位数位为：

En=-log2(Pn)

整条信息的熵也即表示整条信息所需的位数为：E=∑En

举个例子，对下面这条只出现了abc三个字符的字符串：

aabbaccbaa

字符串长度为10，字符abc分别出现了532次，则abc在信息中出现的概率分别为0.50.30.2，他们的熵分别为：

Ea=-log2(0.5)=1

Eb=-log2(0.3)=1.737

Ec=-log2(0.2)=2.322

整条信息的熵也即表达整个字符串需要的位数为：

E=Ea*5+Eb*3+Ec*2=14.855位

如果用计算机中的ASCII编码，表示上面的字符串需要整整80位呢！简单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。考虑用0和1组成的二进制数码为含有n个符号的某条3无损数据压缩概念方式：无损,有损无损(losslesscompression,redundancyreduction)压缩后的数据能够完全恢复，如磁盘上的数据文件，压缩后是原来的1/2—1/4算法有：Huffman,RLE,算术编码，词典编码有损：lossy,不可逆压缩。声音、图像中的变换编码，例如，DM,APCM,DPCM(图3-14）由于存在量化器无损数据压缩概念方式：无损,有损4.1Shannon的信息论与数据压缩1.1948年Shannon香农创立的信息论：数据压缩理论极限。数据压缩的技术途径。压缩原理：信源中信息分布不均匀；信源中信息含有冗余（相关性）4.1Shannon的信息论与数据压缩1.1948年Sh举例26个字母和一个分隔符，共27个字符组成的英文文件，看成信源，该信源的极限(根据字符出现的频率不同)：H(x)=1.4bit/字符原因：27个字符编码，5bits分布不均匀：如a,b,c的出现频率比x,y,z高信源相关系：er,ture,ed,ing等举例26个字母和一个分隔符，共27个字符组成的英文文件，看成2.信息熵entropy问题：随机变量的一个取值a，携带的信息量是多少？相关概念：消息：数据、电报、电话。信息：对消息加工，有特定价值一个信息带有一定的信息量，大小不等例子一个消息：某试验成功试验人员预计成功的可能性99%：信息量很小试验人员预计成功的可能性1%：信息量很大2.信息熵entropy3.信息量：在收到信息以前，处于某种不确定状态中，收到信息之后，消除或部分消除了此不确定性。消除不确定性多少，就可以作为信息的度量。4.Shannon用概率说明这一概念事件出现的概率小，相当于不确定性多，反之，则少。Pi为事件ai发生的概率，则ai出现后的自信息量为I(ai)=-logpi3.信息量：在收到信息以前，处于某种不确定状态中，收到信息5.信息熵（Entropy） 表示每出现一个字符所给出的平均信息量。5.信息熵（Entropy）“底”不同而值不同，因而单位也就不同当取底为r的整数时，则熵的信息单位称作r进制信息单位r=2,单位为bit（比特）r=e,单位为Nat（奈特）r=10,单位为Hart(哈特)log不特别说明时，取为2“底”不同而值不同，因而单位也就不同

6.信息熵的理解：处于事件发生之前，根据先验概率Pj,就有不同的确定性存在，I(ai)与H(x)都是不确定性度量。当处于事件发生之时，是一种惊奇性的度量但出于事件发生之后，不确定性已被解除，则是获得信息的度量可以认为是事件随机性的度量，因其仅仅对概率Pj取另个坐标而已。7.H(x)就是对离散信源进行无失真编码时的码长极限。6.信息熵的理解：8.举例信源取4个符号a1,a2,a3,a4,概率1/2，1/4，1/8，1/8信源的熵H(x)=…=1.75bit/字符若用编码(0,10,110,111),则平均码长=…=1.75考虑以下几种变长编码：码Ｂ唯一可译

例1：例4.1例2：8个字符具有等可能性例3：字符的分布已知：P=(0.9,0.02,0.02,0.02,0.01,0.01,0.01,0.01)H(p)=0.74bit/字符信源字母概率码A码B码Ca1１／２０００a2１／４１１０１０a3１／８１１１１０１０１a4１／８１１１１１１１１１8.举例信源字母概率码A码B码Ca1１／２０００a2１／４１12练习信源X中有16个随机事件，即n=16。每一个随机事件的概率都相等，即P(x1)=P(x2)=P(x3)=…=P(x16)=1/16，计算信源X的熵。练习信源X中有16个随机事件，即n=16。每一个随机事件的概13无损数据压缩课件149.Huffman编码H(S)=(15/39)*log2(39/15)+(7/39)*log2(39/7)+…+(5/39)*log2(39/5)=2.1859

压缩比1.37:1。9.Huffman编码练习信源符号的概率如下，画出其Huffman编码的编码树并给出各符号的编码以及码长，最后求出平均码长XX1X2X3X4X5X6P(X)0.350.200.150.100.100.10练习信源符号的概率如下，画出其Huffman编码的编码树并给哈夫曼编码X101X210X311X4000X50010X60011平均码长：=2.45哈夫曼编码４.2算术编码提出Rissanen1976年提出。在JPEG与JBIG（Bi-levelimage)中都有算术编码的内容。2.思想把信源符号构成的串S,唯一地映射到实数轴上（0，1）之间的一个实数。前提：知道信源每个符号的概率。４.2算术编码提出3.举例假设信源由四个符号{a1,a2,a3,a4}组成，这些符号的概率分别是（0.1,0.4,0.2,0.3).a1,a2,a3,a4四个符号的二进制编码分别为00，01，10，11符号序列S=a3a1a4a1a3a4a2的二进制序列为10001100101101编码：把S映射到（0，1）之间的实数的过程,见教材译码:见教。3.举例4.3RLE编码（RunLengthEncoding）是一种使用广泛的简单熵编码，它被用于BMP、JPEG/MPEG、TIFF和PDF等编码之中，还被用于传真机。RLE原理：图像（静止图像）的相邻像素相关性（灰度、彩色）。用二元组（行程，灰度或彩色值）表示。4.3RLE编码（RunLengthEncoding）例子假定一幅灰度图象，第n行的象素值为用RLE编码方法得到的代码为：80315084180。代码中用蓝色数字是行程长度，蓝字后面的数字代表象素的颜色值。50代表有连续50个象素具有相同的颜色值，它的颜色值是8例子假定一幅灰度图象，第n行的象素值为50代表有连续50个象3.不足：随机色彩丰富的图像，平均码长增加。不是单独使用RLE一种编码方法，而是和其他压缩技术联合应用。无损数据压缩课件4.4词典编码思想Huffman编码：符号的概率已知，概率大的符号分配较短的码字。字符间的相关性信息没有用上。将长度不同的符号串（短语）编码成一个个新的单词。每个符号串分配一个编码。编码等长（如12位二进制）。2.提出：以色列J.Ziv与A.Lempel,LZ77,LZ78,1984,T.A.Welch提出LZW,在Unix中应用。LZ系列算法4.4词典编码思想应用范围LZ77、LZSS、LZ78、LZW算法以及它们的各种变体几乎垄断了整个通用数据压缩领域，我们熟悉的PKZIP、WinZIP、WinRAR、gzip等压缩工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者，甚至连PGP这样的加密文件格式也选择了LZ系列算法作为其数据压缩的标准。应用范围LZ77、LZSS、LZ78、LZW算法以及它词典编码举例LZ77编码术语输入字符流(inputstream):一串字符字符(character)：一个符号编码位置(codingposition)：输出的编码前向缓冲器(lookaheadbuffer)：单词编码窗口(window)指针(pointer)词典编码举例LZ77编码词典编码举例LZ78编码术语字符流:一串字符字符：一个符号码字流：输出的编码码字：单词编码前缀缀—符串词典：缀—符串、码字构成的对应表词典编码举例LZ78编码LZ78算法思想：不断从字符流中形成新的缀—符串缀—符串作为新的词条存入字典中，并给该词条分配一个码字。对字符流的编码就用“(缀的编码,字符)”表示输出码字流由“(缀的编码,字符)”编码算法译码算法LZ78算法思想：LZ78编码算法

步骤1:将词典和当前前缀P都初始化为空.

步骤2:当前字符C:=字符流中的下一个字符.

步骤3:判断P+C是否在词典中(1)如果"是",则用C扩展P,即让P:=P+C,返回到步骤2.(2)如果"否",则输出与当前前缀P相对应的码字W和当前字符C,即(W,C);将P+C添加到词典中;令P:=空值,并返回到步骤2（3）判断字符流中是否还有字符需要编码：如“是”，返回步骤2，如“否”，若当前前缀P不是空，输出响应与当前前缀P的码字，然后结束LZ78编码算法

步骤1:将词典和当前前缀P都初始化为空.LZ78编码举例字符流为：ABBCBCABA词典与码字流（输出）位置字符1A2B3B4C5B6C7A8B9A序号位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)LZ78编码举例字符流为：ABBCBCABA词典与码字流（输LZ78译码收到信息（码字，字符）流：(0,A)(0,B)(2,C)(3,A)(2,A)自动构造词典算法步骤一：开始时词典是空的步骤二：当前码字W:=下一个码字步骤三：当前字符C:=紧随码字之后的字符步骤四：把当前码字的缀－符串（string.W）输出到字符流，然后输出字符C步骤五：把string.W+C添加到词典中重复直到所有（码字，字符）流结束重构出来的词典与编码时生成的词典完全一样LZ78译码收到信息（码字，字符）流：(0,A)(0,B)(2.LZW与LZ78相比，有如下特点所有可能出现的字符都事先放在字典中。输出的码字流中仅由词典中的码字组成。编码算法思想Greedyparsingalgorithm:检查字符流中的字符串，Prefix.C,其中Prefix是字典中最长的字符串，C是一个字符Prefix.C不在字典中。Prefix.C放入字典中。输出Prefix.C的编号例ABBABABAC2.LZWLZW编码算法

步骤1:将词典初始化为包含所有可能的单字符,当前前缀P初始化为空.

步骤2:当前字符C:=字符流中的下一个字符.

步骤3:判断P+C是否在词典中(1)如果"是",则用C扩展P,即让P:=P+C,返回到步骤2.(2)如果"否",则输出与当前前缀P相对应的码字W;将P+C添加到词典中;令P:=C,并返回到步骤2步骤4：判断码字流中是否还有码字要译，如果“是”，就返回步骤2，如果否，吧代表当前前缀P的码字输出到码字流LZW编码算法

步骤1:将词典初始化为包含所有可能的单字符,2.LZW译码算法（略）词典中包含所有的前缀根（即每个字符组成词典）译码时先记住先前码字（pW）从码字流中读出当前的码字（cW）输出当前的码字（cW）对应的单词,string(cW)string(pW)与string(cW)的第一个字符合在一起，放入词典中。例，ABBABABAC词典中有A,B,C码字流：（1，2，2，4，7，3）2.LZW练习采用LZW算法对下列输入字符流进行压缩编码，要求写出编码过程以及字典，最后给出编码结果。ababcbabababaaa练习采用LZW算法对下列输入字符流进行压缩编码，要求写出编码步骤位置词典输出码字(1)a(2)b(3)c11(4)ab(1)22(5)ba(2)34(6)Abc(4)45(7)Cb(3)57(8)Bab(5)610(9)Baba(8)711(10)Aa(1)813(11)Aaa(10)步骤位置词典输出码字(1)a(2)b(3)c1多媒体图像编码分类多媒体数据压缩编码PCM量化预测编码DPCM基于频率变换编码子带编码小波变换编码基于统计哈夫曼编码算术编码游程编码RLE国际标准JPEG标准（静态图像）MPEG标准（电视图像）H.261（可视通信）MHEG标准（超媒体）多媒体图像编码分类多媒体数据压缩编码PCM量化预测编码DPC多媒体核心技术：压缩数据压缩起源于40年代由ClaudeShannon首创的信息论，其基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这条定理借用了热力学中的名词“熵”(Entropy)来表示一条信息中真正需要编码的信息量考虑用0和1组成的二进制数码为含有n个符号的某条信息编码，假设符号Fn在整条信息中重复出现的概率为Pn，则该符号的熵也即表示该符号所需的位数多媒体核心技术：压缩数据压缩起源于40年代由Claud考虑用0和1组成的二进制数码为含有n个符号的某条信息编码，假设符号Fn在整条信息中重复出现的概率为Pn，则该符号的熵也即表示该符号所需的位数位为：

En=-log2(Pn)

整条信息的熵也即表示整条信息所需的位数为：E=∑En

举个例子，对下面这条只出现了abc三个字符的字符串：

aabbaccbaa

字符串长度为10，字符abc分别出现了532次，则abc在信息中出现的概率分别为0.50.30.2，他们的熵分别为：

Ea=-log2(0.5)=1

Eb=-log2(0.3)=1.737

Ec=-log2(0.2)=2.322

整条信息的熵也即表达整个字符串需要的位数为：

E=Ea*5+Eb*3+Ec*2=14.855位

如果用计算机中的ASCII编码，表示上面的字符串需要整整80位呢！简单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。考虑用0和1组成的二进制数码为含有n个符号的某条38无损数据压缩概念方式：无损,有损无损(losslesscompression,redundancyreduction)压缩后的数据能够完全恢复，如磁盘上的数据文件，压缩后是原来的1/2—1/4算法有：Huffman,RLE,算术编码，词典编码有损：lossy,不可逆压缩。声音、图像中的变换编码，例如，DM,APCM,DPCM(图3-14）由于存在量化器无损数据压缩概念方式：无损,有损4.1Shannon的信息论与数据压缩1.1948年Shannon香农创立的信息论：数据压缩理论极限。数据压缩的技术途径。压缩原理：信源中信息分布不均匀；信源中信息含有冗余（相关性）4.1Shannon的信息论与数据压缩1.1948年Sh举例26个字母和一个分隔符，共27个字符组成的英文文件，看成信源，该信源的极限(根据字符出现的频率不同)：H(x)=1.4bit/字符原因：27个字符编码，5bits分布不均匀：如a,b,c的出现频率比x,y,z高信源相关系：er,ture,ed,ing等举例26个字母和一个分隔符，共27个字符组成的英文文件，看成2.信息熵entropy问题：随机变量的一个取值a，携带的信息量是多少？相关概念：消息：数据、电报、电话。信息：对消息加工，有特定价值一个信息带有一定的信息量，大小不等例子一个消息：某试验成功试验人员预计成功的可能性99%：信息量很小试验人员预计成功的可能性1%：信息量很大2.信息熵entropy3.信息量：在收到信息以前，处于某种不确定状态中，收到信息之后，消除或部分消除了此不确定性。消除不确定性多少，就可以作为信息的度量。4.Shannon用概率说明这一概念事件出现的概率小，相当于不确定性多，反之，则少。Pi为事件ai发生的概率，则ai出现后的自信息量为I(ai)=-logpi3.信息量：在收到信息以前，处于某种不确定状态中，收到信息5.信息熵（Entropy） 表示每出现一个字符所给出的平均信息量。5.信息熵（Entropy）“底”不同而值不同，因而单位也就不同当取底为r的整数时，则熵的信息单位称作r进制信息单位r=2,单位为bit（比特）r=e,单位为Nat（奈特）r=10,单位为Hart(哈特)log不特别说明时，取为2“底”不同而值不同，因而单位也就不同

6.信息熵的理解：处于事件发生之前，根据先验概率Pj,就有不同的确定性存在，I(ai)与H(x)都是不确定性度量。当处于事件发生之时，是一种惊奇性的度量但出于事件发生之后，不确定性已被解除，则是获得信息的度量可以认为是事件随机性的度量，因其仅仅对概率Pj取另个坐标而已。7.H(x)就是对离散信源进行无失真编码时的码长极限。6.信息熵的理解：8.举例信源取4个符号a1,a2,a3,a4,概率1/2，1/4，1/8，1/8信源的熵H(x)=…=1.75bit/字符若用编码(0,10,110,111),则平均码长=…=1.75考虑以下几种变长编码：码Ｂ唯一可译

例1：例4.1例2：8个字符具有等可能性例3：字符的分布已知：P=(0.9,0.02,0.02,0.02,0.01,0.01,0.01,0.01)H(p)=0.74bit/字符信源字母概率码A码B码Ca1１／２０００a2１／４１１０１０a3１／８１１１１０１０１a4１／８１１１１１１１１１8.举例信源字母概率码A码B码Ca1１／２０００a2１／４１47练习信源X中有16个随机事件，即n=16。每一个随机事件的概率都相等，即P(x1)=P(x2)=P(x3)=…=P(x16)=1/16，计算信源X的熵。练习信源X中有16个随机事件，即n=16。每一个随机事件的概48无损数据压缩课件499.Huffman编码H(S)=(15/39)*log2(39/15)+(7/39)*log2(39/7)+…+(5/39)*log2(39/5)=2.1859

压缩比1.37:1。9.Huffman编码练习信源符号的概率如下，画出其Huffman编码的编码树并给出各符号的编码以及码长，最后求出平均码长XX1X2X3X4X5X6P(X)0.350.200.150.100.100.10练习信源符号的概率如下，画出其Huffman编码的编码树并给哈夫曼编码X101X210X311X4000X50010X60011平均码长：=2.45哈夫曼编码４.2算术编码提出Rissanen1976年提出。在JPEG与JBIG（Bi-levelimage)中都有算术编码的内容。2.思想把信源符号构成的串S,唯一地映射到实数轴上（0，1）之间的一个实数。前提：知道信源每个符号的概率。４.2算术编码提出3.举例假设信源由四个符号{a1,a2,a3,a4}组成，这些符号的概率分别是（0.1,0.4,0.2,0.3).a1,a2,a3,a4四个符号的二进制编码分别为00，01，10，11符号序列S=a3a1a4a1a3a4a2的二进制序列为10001100101101编码：把S映射到（0，1）之间的实数的过程,见教材译码:见教。3.举例4.3RLE编码（RunLengthEncoding）是一种使用广泛的简单熵编码，它被用于BMP、JPEG/MPEG、TIFF和PDF等编码之中，还被用于传真机。RLE原理：图像（静止图像）的相邻像素相关性（灰度、彩色）。用二元组（行程，灰度或彩色值）表示。4.3RLE编码（RunLengthEncoding）例子假定一幅灰度图象，第n行的象素值为用RLE编码方法得到的代码为：80315084180。代码中用蓝色数字是行程长度，蓝字后面的数字代表象素的颜色值。50代表有连续50个象素具有相同的颜色值，它的颜色值是8例子假定一幅灰度图象，第n行的象素值为50代表有连续50个象3.不足：随机色彩丰富的图像，平均码长增加。不是单独使用RLE一种编码方法，而是和其他压缩技术联合应用。无损数据压缩课件4.4词典编码思想Huffman编码：符号的概率已知，概率大的符号分配较短的码字。字符间的相关性信息没有用上。将长度不同的符号串（短语）编码成一个个新的单词。每个符号串分配一个编码。编码等长（如12位二进制）。2.提出：以色列J.Ziv与A.Lempel,LZ77,LZ78,1984,T.A.Welch提出LZW,在Unix中应用。LZ系列算法4.4词典编码思想应用范围LZ77、LZSS、LZ78、LZW算法以及它们的各种变体几乎垄断了整个通用数据压缩领域，我们熟悉的PKZIP、WinZIP、WinRAR、gzip等压缩工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者，甚至连PGP这样的加密文件格式也选择了LZ系列算法作为其数据压缩的标准。应用范围LZ77、LZSS、LZ78、LZW算法以及它词典编码举例LZ77编码术语输入字符流(inputstream):一串字符字符(character)：一个符号编码位置(codingposition)：输出的编码前向缓冲器(lookaheadbuffer)：单词编码窗口(window)指针(pointer)词典编码举例LZ77编码词典编码举例LZ78编码术语字符流:一串字符字符：一个符号码字流：输出的编码码字：单词编码前缀缀—符串词典：缀—符串、码字构成的对应表词典编码举例LZ78编码LZ78算法思想：不断从字符流中形成新的缀—符串缀—符串作为新的词条存入字典中，并给该词条分配一个码字。对字符流的编码就用“(缀的编码,字符)”表示输出码字流由“(缀的编码,字符)”编码算法译码算法LZ78算法思想：LZ78编码算法

步骤1:将词典和当前前缀P都初始化为空.

步骤2:当前字符C:=字符流中的下一个字符.

步骤3:判断P+C是否在词典中(1)如果"是",则用C扩展P,即让P:=P+C,返回到步骤2.(2)如果"否",则输出与当前前缀P相对应的码字W和当前字符C,即(W,C);将P+C添加到词典中;令P:=空值,并返回到步骤2（3）判断字符流中是否还有字符需要编码：如“是”，返回步骤2，如“否”，若当前前缀P不是空，输出响应与当前前缀P的码字，然后结束LZ78编码算法

步骤1:将词典和当前前缀P都初始化为空.LZ78编码举例字符流为：ABBCBCABA词典与码字流（输出）位置字符1A2B3B4C5B6C7A8B9A序号位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)LZ78编码举例字符流为：A