《第七章图像压缩编码课件》由会员分享，可在线阅读，更多相关《第七章图像压缩编码课件（46页珍藏版）》请在金锄头文库上搜索。
1、,第七章图象数据压缩技术,压缩技术简史 压缩技术基础 Huffman编码 算术编码 LZ77和LZW算法 JPEG算法 小波分析用于静止图像编码,压缩技术分类,通用数据压缩（均为无损压缩）,多媒体数据压缩（无损和有损压缩）,基于统计模型 的压缩技术,基于字典模型 的压缩技术,Huffman 编码,算术编码,LZ77,LZ78,LZW,图像压缩,音频和视频压缩 MPEG等,二值图像 CCITT JBIG等,灰度图像 FELICS JPEG等,彩色图像 RLE编码 JPEG等,矢量图像 PostScript WMF CAD等,压缩技术的应用,电报、传真(CCITT),通讯(Modem/网络协议),
2、存储(压缩池),文件系统(压缩扇区),图像(GIF/TIFF/JPEG),音频(MP3),视频(MPEG/RM),数据库(B+树),归档(TAR/ZIP),密码学(消除数据的原始特征),全文索引(倒排索引表),编译(JAVA),程序设计(算法/空间和时间效率),人工智能(专家系统/知识树),压缩技术起源,信息压缩技术的起源 比计算机的发明早几千年,信息论,信息存在冗余,通过采用一定 的模型和编码方法， 可以降低这种冗余度,贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano 几乎同时提出了最早的对符号进行有效编码 从而实现数据压缩的 Shannon-Fano 编码方法。
3、,D.A.Huffman,1952 年 发表论文：“最小冗余度代码的构造方法” A Method for the Construction of Minimum Redundancy Codes,UNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是 Huffman 0 阶自适应编码的具体实现,80 年代初，Huffman 编码又在 CP/M 和 DOS 系统 中实现，其代表程序叫 SQ,Huffman时代：60 年代、70 年代乃至 80 年代的早期,接近极限熵,80年代早期，数学家们设计出算术编码方法(Arithmetic Coding),可以证明，算术编码得到的压缩效果可以
4、最大地减小 信息的冗余度，用最少量的符号精确表达原始信息内容,但是，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，却要消耗也许几十倍的计算时间,算术编码是部分匹配预测(Predication by Partial matching, PPM)技术的变体,以色列人,Jacob Ziv 和 Abraham Lempel,1978 年 发表论文：“通过可变比率编码的独立序列的压缩” Compression of Individual Sequences via Variable-Rate Coding,字典编码时代：LZ77和LZ78压缩算法,1977 年 发表论文：“顺序数据压缩的一个
5、通用算法” A Universal Algorithm for Sequential Data Compression,LZW算法,Terry Welch,Welch 实现了 LZ78 算法的一个变种 LZW算法 UNIX：使用 LZW 算法的 Compress 程序 MS-DOS：ARC 程序，以及PKWare、PKARC 等仿制品。,1984 年 发表论文：“高性能数据压缩技术” A Technique for High-Performance Data Compression,通用数据压缩,80年代中期以后，对LZ77算法进行改进,Haruyasu Yoshizaki(Yoshi) 的
6、LHarc Robert Jung 的 ARJ,从PKZip到WinZip： 通用数据压缩格式标准 ZIP,LZ77、LZ78、LZW 一起垄断当今的通用数据压缩领域,多媒体数据压缩,国际电报电话咨询委员会( CCITT ) ：针对二值图像的一系列压缩标准，如 CCITT Group3、CCITT Group4 等 (此外还包括CCITT与ISO共同制订的JBIG标准) 。 70 年代末 80 年代初：数学家们提出了损失压缩精度以换取压缩率的崭新思路。国际标准化组织( ISO )和 CCITT 联合组成了两个委员会：静态图像联合专家小组( JPEG )和动态图像联合专家小组( MPEG )。诞
7、生了 JPEG、MPEG-1、MPEG-2、MPEG-4、MPEG-7 等系列标准。 PostScript矢量图形格式：起源于 1976 年的 Evans & Sutherland 计算机公司，当时的名字是 Design System。1978 年，John Warnock 和 Martin Newel 将其演变为 JAM 语言。1982 年，John Warnock 和 Chuck Geschke 创建了著名的 Adobe System 公司，第三次设计和实现了这个语言，并称其为 PostScript。,技术准备：什么是熵,熵来源于40年代由Claude Shannon创立的信息论中的一条定
8、理，这一定理借用了热力学中的名词“熵”( Entropy )来表示一条信息中真正需要编码的信息量：,考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的二进制位数为： En = - log2( Pn ) 整条信息的熵也即表示整条信息所需的二进制位数为： E = knEn,例：对信息aabbaccbaa，字符串长度为 10，字符a、b、c分别出现了5、3、2次，则 Ea=-log2(0.5)=1 Eb=-log2(0.3)=1.737 Ec=-log2(0.2)=2.322 E= 5Ea + 3
9、Eb + 2Ec =14.855 位 对比一下，我们用ASCII编码表示该信息需要80位,技术准备：模型,使用模型：得到字符或单词在信息中出现的概率,静态/半静态模型,自适应模型,Claude Shannon的“聚会游戏”(party game)： 他每次向听众公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符，一次猜一个，直到猜对为止。然后，Shannon 使用猜测次数来确定整个信息的熵。（人的语言经验）,静态字典模型,自适应字典模型,统计模型,字典模型,技术准备：编码,通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型
10、计算出来的位数表示某个符号。 前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。,最简单的前缀编码,1110010101110110111100010 D A B B D C E A A B,技术准备：压缩=模型+编码,输入,模型,编码,输出,符号,概率,代码,Shannon-Fano编码,cabcedeacacdeddaaabaababaaabbacdebaceada,a 16 b 7 c 6 d 6 e - 5,a 16 b 7 - c 6 - d 6 e - 5,例子中的信息编码为： 11 00 01 11 101 100 101 00 11 00 11 . 码长共91位，而使
11、用ASCII编码表示上述信息共需要240位,a 00 b 01 c 11 d 100 e 101,root,0,0,1,1,1,a,b,Huffman编码,cabcedeacacdeddaaabaababaaabbacdebaceada,a 16 b 7 c 6 d 6 e - 5,例子中的信息编码为： 001 1 000 001 011 010 011 1 001 1 001 . 码长88位，比Shannon-Fano编码略短一些,a 1 b 000 c 001 d 010 e 011,整数位编码与信息熵,cabcedeacacdeddaaabaababaaabbacdebaceada,该信
12、息的熵经计算可知为86.601位,另：Huffman编码还有一个变种范式Huffman编码，可以有效减少编码字典的存储空间。,Huffman编码的模型选择,奇怪的段落 If Youth，throughout all history，had had a champion to stand up for it；to show a doubting world that a child can think；and，possibly，do it practically；you wouldnt constantly run across folks today who claim that a chil
13、d dont know anything.“ - Gadsby by E.V.Wright, 1939.,算术编码,假设某个字符的出现概率为 80%，该字符事实上只需要 -log2(0.8) = 0.322 个二进制位进行编码,难道真的能只输出 0.322 个 0 或 0.322 个 1 吗？,算术编码的输出是：一个小数,算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于0和1之间的二进制小数。 例如算术编码对某条信息的输出为1010001111，那么它表示小数0.1010001111，也即十进制数0.64,算术编码,例：考虑某条信息中可能出现的字符仅有 a b c 三
14、种，我们要压缩保存的原始信息为 bccb,第一步：在没有开始压缩进程之前，假设我们对 a b c 三者在信息中的出现概率一无所知（我们采用的是自适应模型），即认为三者的出现概率相等，也就是都为1/3，我们将0-1区间按照概率的比例分配给三个字符，即a从0.0000到0.3333，b从0.3333到0.6667，c从0.6667到1.0000。用图形表示就是：,1.0000,0.6667,0.3333,0.0000,Pc = 1/3,Pb = 1/3,Pa = 1/3,算术编码,第二步：现在我们拿到第一个字符b，让我们把目光投向b对应的区间0.3333-0.6667。这时由于多了字符b，三个字符
15、的概率分布变成：Pa=1/4，Pb=2/4，Pc=1/4。好，让我们按照新的概率分布比例划分0.3333-0.6667这一区间，划分的结果可以用图形表示为：,0.6667,0.5834,0.4167,0.3333,Pc = 1/4,Pb = 2/4,Pa = 1/4,例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb,算术编码,第三步：接着我们拿到字符c，我们现在要关注上一步中得到的c的区间 0.5834-0.6667。新添了c以后，三个字符的概率分布变成Pa=1/5，Pb=2/5，Pc=2/5。我们用这个概率分布划分区间0.5834-0.6667：,
16、0.6667,0.6334,0.6001,0.5834,Pc = 2/5,Pb = 2/5,Pa = 1/5,例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb,算术编码,第四步：现在输入下一个字符c，三个字符的概率分布为：Pa=1/6，Pb=2/6，Pc=3/6。我们来划分c的区间0.6334-0.6667：,0.6667,0.6501,0.6390,0.6334,Pc = 3/6,Pb = 2/6,Pa = 1/6,例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb,算术编码,第五步：输入最后一个字符b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的b的区间为0.6390-0.6501，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进制0.1010001111，去掉前面没有太多意义的0和小
