搜索
多媒体技术基础----无损压缩编码主要内容•概述•统计编码•RLE编码（行程编码）•词典编码主要内容•概述•有损压缩•无损压缩•统计编码•RLE编码（行程编码）•词典编码主要内容•概述•统计编码•信息量与熵•香农范诺编码•霍夫曼编码•算术编码•RLE编码（行程编码）•词典编码主要内容•概述•统计编码•RLE编码（行程编码，游长编码）•词典编码•指针型•LZ77•LZSS•词典型•LZ78•LZW概述•无损压缩使用压缩后的数据进行重构（或者叫做还原，解压缩），重构后数据与原来的数据完全相同•有损压缩使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。统计编码给已知统计信息的符号分配代码的数据无损压缩方法•信息量与熵•香农范诺编码•霍夫曼编码•算术编码不定长编码广泛用在JPEG,MPEG,H.26X等各种信息编码标准中统计编码—信息量与熵•信息量与熵•熵的大小表示非冗余的不可压缩的信息量•某个符号的信息量与对该符号进行编码时需要的位数相等。•熵是字符集的平均信息量•如果对数的底数用2，熵的单位就用“香农(Sh)”，也称“位(bit)”。•“位”是1948年Shannon首次使用的术语。22()log[1/()]log()Ixpxpx事件概率统计编码—香农范诺编码•香农范诺编码•“从上到下”的熵编码•首先按照符号出现的频度或概率排序•使用递归方法分成前后两个部分分割规则：两个部分频度（概率）和值差最小•形成二叉树，左枝为0，右枝为1•问题：错误传播顺序读取统计编码—算术编码•算术编码•基本思想是用0和1之间的一个数值代表整个输入字符流，而不是给输入流中的每个字符分别指定一个码字•首先在0和1之间为每个字符根据其概率分配一个子间隔，使这些字符合集为整个[0,1]空间，交集为空•根据当前输入字符确定进入某子间隔，以这个子间隔作为分配单元进行二次分配•所有字符输入完毕后，从最终间隔区间选数统计编码—算术编码•算术编码•问题•精度导致溢出问题---比例缩放•必须接受到所有位数之后才可以开始译码•错误敏感度高•应用在图像数据压缩标准中（如JPEG、JBIG）中扮演了重要角色RLE编码•RLE编码•利用重复的数据单元有相同的数值这一特点对数据进行压缩。•思想：对相同的数值只编码一次，同时计算出相同值重复出现的次数。•应用：在JPEG，MPEG，H.261和H.263等压缩方法中，RLE用来对图像数据变换和量化后的系数进行编码RLE编码•RLE编码词典编码文本中的词用它在词典中表示位置的号码代替的一种无损数据压缩方法。•指针类•LZ77•LZSS•词典类•LZ78•LZW词典编码—指针类•指针类编码算法•用已经出现过的字符串替代重复的部分•编码器的输出仅仅是指向早期出现过的字符串的“指针”词典编码—指针类—LZ77•编码输出比编码信息大：对于绿色行，(Pointer，Length)Characters大于其编码的信息。•额外输出：未匹配字符被输出了，但是它们完全可以和后面的字符构成新的匹配，例如蓝色行，输出的B实际上也可以构成匹配，但是却被直接输出了窗口前向窗口匹配串字符输出AABCBBABC--A(0，0)AAABCBBABCAB(1，1)BAABCBBABC--C(0，0)CAABCBBABCBB(2，1)BAABCBBABCABC$(5，3)$AABCBBABC词典编码—指针类—LZSS位置1234567891011字符AABBCBBAABC窗口前向窗口匹配串输出AABBCBBAABC--AAABBCBBAABCAAAABBCBBAABC--BAABBCBBAABCBBAABBCBBAABC--CAABBCBBAABCBB(3，2)AABBCBBAABCAAB(7，3)AABBCBBAABCCCAABBCBBAABC词典编码—指针类—LZSS•文档压缩程序都使用了LZSS的思想，例如PKZip，ARJ，LHArc和ZOO等，差别仅仅是指针的长短、窗口的大小等有所不同•LZSS同样可以和熵编码联合使用•ARJ与霍夫曼编码联用•PKZip与Shannon-Fano联用词典编码—词典类•词典类编码算法•从输入的数据中创建一个“短语词典”•编码器输出词典中的短语“索引号”，而不是短语词典编码—词典类—LZ78位置123456789字符ABBCBCABA步骤（相当于码字）字符流输出词典1ABBCBCABA(0，A)A2BBCBCABA(0，B)B3BCBCABA(2，C)BC4BCABA(3，A)BCA5BA(2，A)BA词典编码—词典类—LZ78•优点：LZ77需要搜索遍历搜索窗口以寻找最大匹配字符串，而LZ78之需要比较W+C和词典的字符串是否相同，这是它的最大优点•问题：与LZ77类似词典编码—词典类—LZW位置123456789字符ABBABABAC步骤字符流输出词典11(1)(4)AB22(2)(5)BB33(2)(6)BA44(4)(7)ABA56(7)(8)ABAC6--(3)----词典编码—词典类—LZW•GIF文件采用该压缩算法，在其他系统中该算法也的到广泛应用•该算法拥有专利，商业化使用该算法要支付专利费•注意：译码问题