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