多媒体图像编码分类-PPT精选.ppt

多媒体图像编码分类-PPT精选
多媒体核心技术：压缩
数据压缩起源于 40 年代由 Claude Shannon 首创的信息论，其基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这条定理借用了热力学中的名词“熵”(,a2,a3,a4}组成，这些符号的概率分别是（,,,).
a1,a2,a3,a4四个符号的二进制编码分别为00，01，10，11
符号序列S=a3 a1 a4 a1 a3 a4 a2的二进制序列为10 00 11 00 10 11 01
编码：把S映射到（0，1）之间的实数的
过程, 见教材
译码:见教。
RLE编码（Run Length Encoding）
是一种使用广泛的简单熵编码，它被用于BMP、JPEG/MPEG、TIFF和PDF等编码之中，还被用于传真机。
RLE原理：
图像（静止图像）的相邻像素相关性（灰度、彩色）。
用二元组（行程，灰度或彩色值）表示。
例子
假定一幅灰度图象，第n行的象素值为
用RLE编码方法得到的代码为：80315084180。代码中用蓝色数字是行程长度，蓝字后面的数字代表象素的颜色值。
50代表有连续50个象素具有相同的颜色值，它的颜色值是8
：随机色彩丰富的图像，平均码长增加。不是单独使用RLE一种编码方法，而是和其他压缩技术联合应用。
词典编码
思想
Huffman编码：符号的概率已知，概率大的符号分配较短的码字。字符间的相关性信息没有用上。
将长度不同的符号串（短语）编码成一个个新的单词。每个符号串分配一个编码。编码等长（如12位二进制）。
2. 提出：以色列J. Ziv 与A. Lempel,
LZ77,LZ78,
1984,T. A. Welch提出LZW,在Unix中应用。
LZ系列算法
应用范围
LZ77 、LZSS 、LZ78 、LZW算法以及它们的各种变体几乎垄断了整个通用数据压缩领域，我们熟悉的PKZIP、WinZIP、WinRAR、gzip等压缩工具以及ZIP、 GIF、PNG等文件格式都是LZ系列算法的受益者，甚至连PGP这样的加密文件格式也选择了LZ系列算法作为其数据压缩的标准。
词典编码举例
LZ77编码
术语
输入字符流(input stream):一串字符
字符(character)：一个符号
编码位置(coding position)：输出的编码
前向缓冲器(lookahead buffer)：单词编码
窗口(window)
指针(pointer)
词典编码举例
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编码举例
字符流为：ABBCBCABA
词典与码字流（输出）
位置
字符
1
A
2
B
3
B
4
C
5
B
6
C
7
A
8
B
9
A
序
号
位置
词
典
输
出
1
1
A
(0,A)
2
2
B
(0,B)
3
3
BC
(2,C)
4
5
BCA
(3,A)
5
8
BA
(2,A)
LZ78译码
收到信息（码字，字符）流：(0,A)(0,B)(2,C)(3,A)(2,A)
自动构造词典
算法
步骤一：开始时 词典是空的
步骤二：当前码字W:=下一个码字
步骤三：当前字符C:=紧随码字之后的字符
步骤四：把当前码字的缀－符串（）输出到字符流，然后输出字符C
步骤五：+C添加到词典中
重复直到所有（码字，字符）流结束
重构出来的词典与编码时生成的词典完全一样

与LZ78相比，有如下特点
所有可能出现的字符都事先放在字典中。
输出的码