chap3-多媒体数据压缩技术.ppt

算术编码举例 符号 A B C D 概率 0.1 0.4 0.2 0.3 初始区间 [0, 0.1) [0.1, 0.5) [0.5, 0.7) [0.7, 1) 行程编码（RLE） 行程编码思想： 它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。例如： RTTTTTTTTABBCDG R#8TABBCDG， 其中“＃” 为转义字符，表明其后所跟的字符表示长度。 行程编码多用于黑白二值图像的压缩中。 例如:00000000111111111111000001111111 81257。 词典编码 词典编码思想： 采用一些简单的代号代替数据本身包含许多重复的字符串，从而实现压缩。 字符串与代号的对应表就是词典。 例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 词典编码算法核心： 就是如何动态地形成词典，以及如何选择输出格式以减小冗余。 第一类词典编码 第一类词典法的想法： - 查找待压缩字符序列是否在以前输入的数据中出现过； - 用已经出现过的字符串替代重复的部分； - 输出仅仅是指向早期出现过的字符串的“指针”。 LZ77算法 LZ77 算法思想： “滑动窗口压缩” 优点： - 采用滑动的窗口限制词典的大小，保证算法的效率； - 包含最近编码过的信息，要编码的字符串往往在最近的上下文中更容易找到匹配串。 LZ77编码的基本流程 1）、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。 2）、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。 3）、输出三元符号组 ( 0, 0, c )。其中 c 为正在考察的未匹配字符。然后将窗口向后滑动 1 个字符，继续步骤 1。 LZ77算法 LZ77编码举例 A A B C B B A B C A 步骤 位置 匹配串 输出 1 1 －－ 0, 0, A 2 2 A 1, 1, B 3 4 －－ 0, 0, C 4 5 B 2, 1, B 5 7 ABC 5, 3, A LZSS算法 LZ77的局限： - 空指针； - 编码器可能输出额外的字符。 LZSS算法思想： if (匹配串长度 指针长度) then 输出指针 else 输出真实字符。 LZSS编码的基本流程 1） 从当前压缩位置开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度len大于等于最小匹配串长度（len = MIN_LENGTH），则进行步骤 2，否则进行步骤 3。 2） 输出指针二元组 ( off, len)。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为匹配串的长度，然后将窗口向后滑动 len 个字符，继续步骤 1。 3） 输出当前字符c，然后将窗口向后滑动 1 个字符，继续步骤 1。 LZSS编码举例 输入数据流 位置 1 2 3 4 5 6 7 8 9 10 11 字符 A A B B C B B A A B C 步骤 位置 匹配串 输出 1 1 －－ A 2 2 A A 3 3 －－ B 4 4 B B 5 5 －－ C 6 6 BB （3，2） 7 8 AAB （7，3） 8 11 C C 编码过程 MIN_LEN =2 第二类词典编码 第二类算法的想法： 从输入的数据中创建一个“短语词典” 编码器输出词典中的短语的“索引号”，而不是短语本身。 LZ78算法 LZ78的编码思想： - 是不断地从字符流中提取新 “词条”，用码字表示； - 用码字流替换字符流，达到压缩数据的目的。 LZ78编码器的输出： 码字-字符对 (W,C) 与码字W相对应的词条+字符C进行扩展 新词条 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 LZ78编码举例 位