图像压缩编码讲稿.ppt

图像压缩编码第一页，讲稿共四十六页哦第二页，讲稿共四十六页哦压缩技术的应用电报、传真(CCITT)通讯(Modem/网络协议)存储(压缩池)文件系统(压缩扇区)图像(GIF/TIFF/JPEG)音频(MP3)视频(MPEG/RM)数据库(B+树)归档(TAR/ZIP)密码学(消除数据的原始特征)全文索引(倒排索引表)编译(JAVA)程序设计(算法/空间和时间效率)人工智能(专家系统/知识树)第三页，讲稿共四十六页哦压缩技术起源信息压缩技术的起源比计算机的发明早几千年第四页，讲稿共四十六页哦信息论信息存在冗余信息存在冗余通过采用一定通过采用一定的模型和编码方法，的模型和编码方法，可以降低这种冗余度可以降低这种冗余度贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的 Shannon-Fano 编码方法。第五页，讲稿共四十六页哦D.A.Huffman1952 年 发表论文：“最小冗余度代码的构造方法”A Method for the Construction of Minimum Redundancy CodesUNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是 Huffman 0 阶自适应编码的具体实现 80 年代初，Huffman 编码又在 CP/M 和 DOS 系统中实现，其代表程序叫 SQHuffman时代：时代：60 年代、年代、70 年代乃至年代乃至 80 年代的早期年代的早期第六页，讲稿共四十六页哦接近极限熵80年代早期，数学家们设计出算术编码方法(Arithmetic Coding)可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容 q但是，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，却要消耗也许几十倍的计算时间 算术编码是部分匹配预测(Predication by Partial matching,PPM)技术的变体第七页，讲稿共四十六页哦以色列人1978 年 发表论文：“通过可变比率编码的独立序列的压缩”Compression of Individual Sequences via Variable-Rate Coding字典编码时代：字典编码时代：LZ77和和LZ78压缩算法压缩算法1977 年 发表论文：“顺序数据压缩的一个通用算法”A Universal Algorithm for Sequential Data Compression第八页，讲稿共四十六页哦LZW算法Welch 实现了 LZ78 算法的一个变种 UNIX：使用 LZW 算法的 Compress 程序MS-DOS：ARC 程序，以及PKWare、PKARC 等仿制品。1984 年 发表论文：“高性能数据压缩技术”A Technique for High-Performance Data Compression 第九页，讲稿共四十六页哦通用数据压缩80年代中期以后，对LZ77算法进行改进Haruyasu Yoshizaki(Yoshi)的 LHarcRobert Jung 的 ARJ 从PKZip到WinZip：通用数据压缩格式标准 ZIPLZ77、LZ78、LZW 一起垄断当今的通用数据压缩领域一起垄断当今的通用数据压缩领域第十页，讲稿共四十六页哦多媒体数据压缩q国际电报电话咨询委员会(CCITT)：针对二值图像的一系列压缩标准，如 CCITT Group3、CCITT Group4 等(此外还包括CCITT与ISO共同制订的JBIG标准)。q70 年代末 80 年代初：数学家们提出了损失压缩精度以换取压缩率的崭损失压缩精度以换取压缩率的崭新思路新思路。国际标准化组织(ISO)和 CCITT 联合组成了两个委员会：静态图像联合专家小组(JPEG)和动态图像联合专家小组(MPEG)。诞生了 JPEG、MPEG-1、MPEG-2、MPEG-4、MPEG-7 等系列标准。qPostScript矢量图形格式：起源于 1976 年的 Evans&Sutherland 计算机公司，当时的名字是 Design System。1978 年，John Warnock 和 Martin Newel 将其演变为 JAM 语言。1982 年，John Warnock 和 Chuck Geschke 创建了著名的 Adobe System 公司，第三次设计和实现了这个语言，并称其为 PostScript。第十一页，讲稿共四十六页哦技术准备：什么是熵熵熵来源于40年代由Claude Shannon创立的信息论中的一条定理，这一定理借用了热力学中的名词“熵”(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.322E=5Ea+3Eb+2Ec=14.855 位对比一下，我们用ASCII编码表示该信息需要80位第十二页，讲稿共四十六页哦技术准备：模型使用模型：得到字符或单词在信息中出现的概率静态/半静态模型自适应模型Claude Shannon的“聚会游戏”(party game)：他每次向听众公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符，一次猜一个，直到猜对为止。然后，Shannon 使用猜测次数来确定整个信息的熵。（人的语言经验）静态字典模型自适应字典模型统计模型字典模型第十三页，讲稿共四十六页哦技术准备：编码通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。最简单的前缀编码字符字符编码编码A0B10C110D1110E111101110010101110110111100010 D A B B D C E A A B 第十四页，讲稿共四十六页哦技术准备：压缩=模型+编码输入模型编码输出符号概率代码第十五页，讲稿共四十六页哦Shannon-Fano编码cabcedeacacdeddaaabaababaaabbacdebaceada a 16b 7c 6d 6e-5 a 16b 7-c 6-d 6e-5 例子中的信息编码为：例子中的信息编码为：11 00 01 11 101 100 101 00 11 00 11.码长共码长共91位，而使用位，而使用ASCII编码表示上述信息共需要编码表示上述信息共需要240位位a 00b 01c 11d 100e 101root00111abc01de第十六页，讲稿共四十六页哦Huffman编码cabcedeacacdeddaaabaababaaabbacdebaceada a 16b 7c 6d 6e-5 例子中的信息编码为：例子中的信息编码为：001 1 000 001 011 010 011 1 001 1 001.码长码长88位，比位，比Shannon-Fano编码略短一些编码略短一些a 1b 000c 001d 010e 011root01a011bcde001第十七页，讲稿共四十六页哦整数位编码与信息熵cabcedeacacdeddaaabaababaaabbacdebaceada 该信息的熵经计算可知为86.601位符号符号理想位数理想位数（熵）（熵）S-F编码需编码需要位数要位数Huffman编编码需要位数码需要位数a1.32221b2.51523c2.73723d2.73733e3.00033总计总计86.6019188第十八页，讲稿共四十六页哦另：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 child 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 三种，我们要压缩保存的原始信息为 bccb第一步第一步：在没有开始压缩进程之前，假设我们对 a b c 三者在信息中的出现概率一无所知（我们采用的是自适应模型），即认为三者的出现概率相等，也就是都为1/3，我们将0-1区间按照概率的比例分配给三个字符，即a从0.0000到0.3333，b从0.3333到0.6667，c从0.6667到1.0000。用图形表示就是：1.00000.66670.33330.0000Pc=1/3Pb=1/3Pa=1/3第二十一页，讲稿共四十六页哦算术编码第二步第二步：现在我们拿到第一个字符b，让我们把目光投向b对应的区间0.3333-0.6667。这时由于多了字符b，三个字符的概率分布变成：Pa=1/4，Pb=2/4，Pc=1/4。好，让我们按照新的概率分布比例划分0.3333-0.6667这一区间，划分的结果可以用图形表示为：0.66670.58340.41670.3333Pc=1/4Pb=2/4Pa=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：0.66670.63340.60010.5834Pc=2/5Pb=2/5Pa=1/5例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb第二十三页，讲稿共四十六页哦算术编码第四步第四步：现在输入下一个字符c，三个字符的概率分布为：Pa=1/6，Pb=2/6，Pc=3/6。我们来划分c的区间0.6334-0.6667：0.66670.65010.63900.6334Pc=3/6Pb=2/6Pa=1/6例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb第二十四页，讲稿共四十六页哦算术编码第五步第五步：输入最后一个字符b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的b的区间为0.6390-0.6501，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进制0.1010001111，去掉前面没有太多意义的0和小数点，我们可以输出1010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程0.66670.65010.63900.6334Pc=3/6Pb=2/6Pa=1/6例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb输出输出:(0.64)10=(0.1010001111)2第二十五页，讲稿共四十六页哦自适应模型的阶h(t)(t)gh(t)igh(t)例文：例文：the weight of.0阶阶1阶阶2阶阶3阶阶问题：半静态模型和自适应模型转义码的使用1.存储空间问题第二十六页，讲稿共四十六页哦LZ77算法字典模型：现代汉语词典以及下面的例子第二十七页，讲稿共四十六页哦LZ77算法LZ77算法的基本流程：“滑动的窗口”1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤 1。第二十八页，讲稿共四十六页哦LZ77算法应用实例：窗口大小为10个字符，刚编码过的10个字符为“abcdbbccaa”，即将编码的10个字符为“abaeaaabaee”。我们首先发现，可以和待编码字符匹配的最长串为ab(off=0,len=2),ab的下一个字符为a，我们输出三元组：(0,2,a)现在窗口向后滑动3个字符，窗口中的内容为：dbbccaaaba下一个字符e在窗口中没有匹配，我们输出三元组：(0,0,e)窗口向后滑动1个字符，其中内容变为：bbccaaabae我们马上发现，要编码的aaabae在窗口中存在(off=4,len=6)，其后的字符为e，我们可以输出：(4,6,e)这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。解压缩时，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符c输出（如果off和len都为0则只输出后继字符c)即可还原出原始数据。第二十九页，讲稿共四十六页哦LZ77算法三元组的编码方法（编码方式取决于数据的分布概率）：对于第一个分量窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况。但对于普通的窗口大小来说，这一差别可以忽略不计，我们用固定的位数来表示它：即编码off需要的位数为upper_bound(log2(MAX_WND_SIZE)对于第二个分量字符串长度，它的值在大多数时候不会太大，大字符串的匹配的发生概率很小。显然可以使用一种变长的编码方式来表示该长度值。我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件。其实 Huffman 编码也可以在此处使用，但却不是最好的选择。适用于此处的好的编码方案很多，我们将在稍后介绍其中两种应用非常广泛的编码：Golomb编码和编码。对三元组的最后一个分量字符 c，因为其分布并无规律可循，我们只能老老实实地用 8 个二进制位对其编码。第三十页，讲稿共四十六页哦假设对正整数x进行Golomb编码，选择参数m，令b=2mq=INT(x-1)/b)r=x-qb 1则x可以被编码为两部分，第一部分是由q个1加1个0组成，第二部分为m位二进制数，其值为 r。值值 xm=0m=1m=2m=3100 00 000 0002100 10 010 001311010 00 100 0104111010 10 110 011511110110 010 000 1006111110110 110 010 101711111101110 010 100 1108111111101110 110 110 111911111111011110 0110 0010 000第三十一页，讲稿共四十六页哦假设对x编码，令q=int(log2x)则编码的前一部分是q个1加一个0，后一部分是q位长的二进制数，其值等于(x-2q)值值 x编码编码10210 0310 14110 005110 016110 107110 1181110 00091110 001第三十二页，讲稿共四十六页哦LZ77算法的其他问题其他的编码方式：输出匹配串时不输出后续字符输出0表示下面是一个匹配串，输出1表示下面是一个单个字符对匹配串长度加以限制如何查找匹配串：限制匹配串的长度，在内存中组织二叉有序树将窗口中每个长度为3的字符串建立字典索引使用Hash表建立索引使用字符树建立索引窗口滑动时内存中的索引重建问题：建立环状偏移以环状偏移为基础建立窗口索引第三十三页，讲稿共四十六页哦内存词典：内存词典：第二步：压缩串第二步：压缩串“AD.”在内存词典中仍无法找到匹配串，则输出二元组在内存词典中仍无法找到匹配串，则输出二元组(0，“A”)并将字串并将字串“A”置入内存词典置入内存词典第一步：压缩串第一步：压缩串“DAD.”在内存词典中无法找到匹配串，则输出二元组在内存词典中无法找到匹配串，则输出二元组(0，“D”)二元组中第一个元素表示词典的索引，第二个元素表示后续字符。二元组中第一个元素表示词典的索引，第二个元素表示后续字符。并将字串并将字串“D”置入内存词典置入内存词典内存词典：内存词典：LZW算法LZW算法是LZ78的改进，其基本思路是在内存中维护一个动态的字典，输出的代码是该字典的索引例：待压缩的信息为例：待压缩的信息为 DAD DADA DADDY DADO.索引索引0词条词条null索引索引01词条词条null“D”第三十四页，讲稿共四十六页哦第三步：压缩串第三步：压缩串“D D.”在内存词典中可以找到最大匹配串在内存词典中可以找到最大匹配串“D”，输出，输出二元组二元组(1，“”)以此对字串以此对字串“D”进行了编码，然后将进行了编码，然后将“D”置入内存词典置入内存词典内存词典：内存词典：内存词典：内存词典：第四步：压缩串第四步：压缩串“DAD.”在内存词典中可以找到最大匹配串在内存词典中可以找到最大匹配串“D”，则输出，则输出二元组二元组(1，“A”)以此对字串以此对字串“DA”进行了编码，然后将进行了编码，然后将“DA”置入内存词典置入内存词典LZW算法例：待压缩的信息为例：待压缩的信息为 DAD DADA DADDY DADO.索引索引012词条词条null“D”“A”索引索引0123词条词条null“D”“A”“D”第三十五页，讲稿共四十六页哦LZW算法例：待压缩的信息为例：待压缩的信息为 DAD DADA DADDY DADO.第九步后，内存词典的情况如下：第九步后，内存词典的情况如下：索引索引01234词条词条null“D”“A”“D”“DA”索引索引56789词条词条“DA”“DAD”“DY”“”“DADO”每一步的输出如下（每一步输出均为二元组）：每一步的输出如下（每一步输出均为二元组）：步骤步骤12345输出输出(0,”D”)(0,”A”)(1,”)(1,”A”)(4,”)步骤步骤6789输出输出(4,”D”)(1,”Y”)(0,”)(6,”O”)第三十六页，讲稿共四十六页哦JPEG图像压缩算法qJPEG 是有损压缩算法qJPEG 核心是“离散余弦变换(Discrete Cosine Transform,DCT)”qJPEG 压缩算法的基本步骤为：1、离散余弦变换DCT Transformation2、系数量化Coefficient Quantization 3、无损压缩Lossless Compression第三十七页，讲稿共四十六页哦一维波第三十八页，讲稿共四十六页哦二维波第三十九页，讲稿共四十六页哦离散余弦变换 DCTDCT操作X、Y、Z坐标轴上的三维信号。X、Y坐标轴是平面图像的两个维度，Z轴表示图象的象素值。对NN的象素矩阵进行DCT变换的公式如下：10102)12(2)12(),()()(21),(NxNyNjyCosNixCosyxPixeljCiCNjiDCT10102)12(2)12(),()()(21),(NiNjNjyCosNixCosjiDCTjCiCNyxPixel离散余弦变换(Discrete Cosine Transform,DCT)公式：反向离散余弦变换(Inverse Discrete Cosine Transform,IDCT)公式：)0(1)0(21)(xxxC其中：但是：按照上述基本公式写出的程序实现存在一个严重的问题时间复杂度太高第四十页，讲稿共四十六页哦使用矩阵运算的DCT替代公式矩阵乘法）（注：上面的乘号表示象素矩阵可表示为，则函数即的转置矩阵为且满足：余弦变换矩阵tttCCDCTDCTijCjiCCCiifNijCosNjiCiifNjiCC:),(),(02)12(2),(01),(Matrix)Transform(Cosineq实现上面的替代公式的程序代码的时间复杂度就大大降低了。进一步的改进还包括将余弦函数由浮点运算改为整数运算、改进傅立叶变换技术等。第四十一页，讲稿共四十六页哦量化 QuantizationDCT变换的输入是8位的象素值（0255，JPEG实现时将其减去128，范围变成-128127），但输出范围是从1024到1023，占11位。量化即通过整除运算减少输出值的存储位数。使用量化矩阵（Quantization Matrix）来实现量化。量化公式为：量化后的值(i,j)=ROUND(DCT(i,j)/量子(i,j)逆量化公式为：DCT(i,j)=量化后的值(i,j)*量子(i,j)量化是JPEG算法中损失图像精度的根源第四十二页，讲稿共四十六页哦量化表Quantum Table4710131619222571013161922252810131619222528311316192225283134161922252831343719222528313437402225283134374043252831343740434610192837465564731928374655647382283746556473829137465564738291100465564738291100109556473829110010911864738291100109118127738291100109118127136quality=4quality=9Quantumij=1+(1+i+j)*quality)第四十三页，讲稿共四十六页哦Zig-Zag编码(0,0)-(0,1)-(1,0)-(2,0)-q将量化的矩阵按Zig-Zag顺序排列q将原始数列转换为差值数列q对差值数列进行编码，可以使用Huffman编码、算术编码或熵编码等方法第四十四页，讲稿共四十六页哦第四十五页，讲稿共四十六页哦JPEG的其他问题第四十六页，讲稿共四十六页哦