多媒体图像编码分类.ppt

多媒体图像编码分类,多媒体数据压缩编码,PCM,量化,预测编码,DPCM,基于频率,变换编码,子带编码,小波变换编码,基于统计,哈夫曼编码,算术编码,游程编码RLE,国际标准,JPEG标准（静态图像）,MPEG标准（电视图像）,H.261（可视通信）,MHEG标准（超媒体）,多媒体核心技术：压缩,数据压缩起源于 40 年代由 Claude Shannon 首创的信息论，其基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这条定理借用了热力学中的名词“熵”( Entropy )来表示一条信息中真正需要编码的信息量 考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的位数,考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的位数位为： En = - log2( Pn ) 整条信息的熵也即表示整条信息所需的位数为：E = En 举个例子，对下面这条只出现了 a b c 三个字符的字符串： aabbaccbaa 字符串长度为 10，字符 a b c 分别出现了 5 3 2 次，则 a b c 在信息中出现的概率分别为 0.5 0.3 0.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 位呢！简单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。,无损数据压缩概念,方式：无损,有损 无损(lossless compression,redundancy reduction) 压缩后的数据能够完全恢复，如磁盘上的数据文件， 压缩后是原来的1/21/4 算法有：Huffman, RLE,算术编码，词典编码 有损：lossy,不可逆压缩。 声音、图像中的变换编码， 例如，DM, APCM, DPCM(图3-14）由于存在量化器,4.1 Shannon的信息论与数据压缩,1. 1948年Shannon香农创立的信息论： 数据压缩理论极限。 数据压缩的技术途径。 压缩原理： 信源中信息分布不均匀； 信源中信息含有冗余（相关性）,举例,26个字母和一个分隔符，共27个字符组成的英文文件，看成信源，该信源的极限(根据字符出现的频率不同)： H(x)=1.4bit/字符 原因： 27个字符编码，5bits 分布不均匀：如a,b,c的出现频率比x,y,z高 信源相关系：er,ture,ed,ing等,2. 信息熵entropy 问题：随机变量的一个取值a，携带的信息量是多少？ 相关概念： 消息：数据、电报、电话。 信息：对消息加工，有特定价值 一个信息带有一定的信息量，大小不等 例子 一个消息：某试验成功 试验人员预计成功的可能性99%：信息量很小 试验人员预计成功的可能性1%：信息量很大,3. 信息量：在收到信息以前，处于某种不确定状态中，收到信息之后，消除或部分消除了此不确定性。消除不确定性多少，就可以作为信息的度量。 4. Shannon 用概率说明这一概念 事件出现的概率小，相当于不确定性多，反之，则少。 Pi为事件ai发生的概率，则ai出现后的自信息量为 I(ai)=-log pi,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)就是对离散信源进行无失真编码时的码长极限。,8.举例 信源取4个符号a1,a2,a3,a4,概率1/2，1/4，1/8，1/8 信源的熵H(x)=1.75 bit/字符 若用编码(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/字符,练习,信源X中有16个随机事件，即n=16。每一个随机事件的概率都相等，即P(x1)=P(x2)=P(x3) =P(x16)=1/16，计算信源X的熵。,9. Huffman 编码,H(S) = (15/39) * log2 (39/15) + (7/39) * log2 (39/7) + + (5/39) * log2 (39/5) = 2.1859 压缩比1.37:1。,练习,信源符号的概率如下，画出其Huffman编码的编码树并给出各符号的编码以及码长，最后求出平均码长,哈夫曼编码 X1 01 X2 10 X3 11 X4 000 X5 0010 X6 0011 平均码长：= 2.45,.2 算术编码,提出 Rissanen1976年提出。在JPEG与JBIG（Bi-level image)中都有算术编码的内容。 2. 思想 把信源符号构成的串S, 唯一地映射到实数轴上（0，1）之间的一个实数。 前提：知道信源每个符号的概率。,3. 举例 假设信源由四个符号a1,a2,a3,a4组成，这些符号的概率分别是（0.1,0.4,0.2,0.3). 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）之间的实数的 过程, 见教材 译码:见教。,4.3 RLE编码（Run Length Encoding）,是一种使用广泛的简单熵编码，它被用于BMP、JPEG/MPEG、TIFF和PDF等编码之中，还被用于传真机。 RLE原理： 图像（静止图像）的相邻像素相关性（灰度、彩色）。 用二元组（行程，灰度或彩色值）表示。,例子,假定一幅灰度图象，第n行的象素值为 用RLE编码方法得到的代码为：80315084180。代码中用蓝色数字是行程长度，蓝字后面的数字代表象素的颜色值。,50代表有连续50个象素具有相同的颜色值，它的颜色值是8,3.不足：随机色彩丰富的图像，平均码长增加。不是单独使用RLE一种编码方法，而是和其他压缩技术联合应用。,4.4 词典编码,思想 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,词典与码字流（输出）,LZ78译码,收到信息（码字，字符）流：(0,A)(0,B)(2,C)(3,A)(2,A) 自动构造词典 算法 步骤一：开始时 词典是空的 步骤二：当前码字W:=下一个码字 步骤三：当前字符C:=紧随码字之后的字符 步骤四：把当前码字的缀符串（string.W）输出到字符流，然后输出字符C 步骤五：把string.W+C添加到词典中 重复直到所有（码字，字符）流结束 重构出来的词典与编码时生成的词典完全一样,2.LZW 与LZ78相比，有如下特点 所有可能出现的字符都事先放在字典中。 输出的码字流中仅由词典中的码字组成。 编码算法思想Greedy parsing algorithm: 检查字符流中的字符串，Prefix.C, 其中 Prefix是字典中最长的字符串，C是一个字符 Prefix.C不在字典中。 Prefix.C放入字典中。 输出 Prefix.C的编号 例 ABBABABAC,LZW编码算法,步骤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的码字输出到码字流,2.LZW 译码算法（略） 词典中