第七章 图像压缩编码

第七章图象数据压缩技术压缩技术简史压缩技术基础Huffman编码算术编码LZ77和LZW算法JPEG算法小波分析用于静止图像编码压缩技术分类通用数据压缩（均为无损压缩）多媒体数据压缩（无损和有损压缩）基于统计模型的压缩技术基于字典模型的压缩技术Huffman编码算术编码LZ77LZ78LZW图像压缩音频和视频压缩MPEG等二值图像CCITTJBIG等灰度图像FELICSJPEG等彩色图像RLE编码JPEG等矢量图像PostScriptWMFCAD等压缩技术的应用电报、传真(CCITT)通讯(Modem/网络协议)存储(压缩池)文件系统(压缩扇区)图像(GIF/TIFF/JPEG)音频(MP3)视频(MPEG/RM)数据库(B+树)归档(TAR/ZIP)密码学(消除数据的原始特征)全文索引(倒排索引表)编译(JAVA)程序设计(算法/空间和时间效率)人工智能(专家系统/知识树)压缩技术起源信息压缩技术的起源…… 比计算机的发明早几千年……信息论信息存在冗余通过采用一定的模型和编码方法，可以降低这种冗余度贝尔实验室的ClaudeShannon和MIT的R.M.Fano几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的Shannon-Fano

编码方法。D.A.Huffman1952年发表论文：“最小冗余度代码的构造方法”AMethodfortheConstructionofMinimumRedundancyCodesUNIX系统上一个不太为现代人熟知的压缩程序

COMPACT就是Huffman0阶自适应编码的具体实现80年代初，Huffman编码又在CP/M和DOS系统中实现，其代表程序叫SQHuffman时代：60年代、70年代乃至80年代的早期接近极限——熵80年代早期，数学家们设计出算术编码方法(ArithmeticCoding)可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容但是，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，却要消耗也许几十倍的计算时间算术编码是部分匹配预测(PredicationbyPartialmatching,PPM)技术的变体以色列人JacobZiv

和AbrahamLempel1978年发表论文：“通过可变比率编码的独立序列的压缩”CompressionofIndividualSequencesviaVariable-RateCoding字典编码时代：LZ77和LZ78压缩算法1977年发表论文：“顺序数据压缩的一个通用算法”AUniversalAlgorithmforSequentialDataCompressionLZW算法TerryWelchWelch实现了LZ78算法的一个变种——LZW算法UNIX：使用LZW算法的Compress程序MS-DOS：ARC程序，以及PKWare、PKARC

等仿制品。1984年发表论文：“高性能数据压缩技术”ATechniqueforHigh-PerformanceDataCompression通用数据压缩80年代中期以后，对LZ77算法进行改进Haruyasu

Yoshizaki(Yoshi)的LHarcRobertJung的ARJ从PKZip到WinZip：

通用数据压缩格式标准——ZIPLZ77、LZ78、LZW一起垄断当今的通用数据压缩领域多媒体数据压缩国际电报电话咨询委员会(CCITT)：针对二值图像的一系列压缩标准，如CCITTGroup3、CCITTGroup4等(此外还包括CCITT与ISO共同制订的JBIG标准)。70年代末80年代初：数学家们提出了损失压缩精度以换取压缩率的崭新思路。国际标准化组织(ISO)和CCITT联合组成了两个委员会：静态图像联合专家小组(JPEG)和动态图像联合专家小组(MPEG)。诞生了JPEG、MPEG-1、MPEG-2、MPEG-4、MPEG-7等系列标准。PostScript矢量图形格式：起源于1976年的Evans&Sutherland计算机公司，当时的名字是DesignSystem。1978年，JohnWarnock和MartinNewel将其演变为JAM语言。1982年，JohnWarnock和ChuckGeschke

创建了著名的AdobeSystem公司，第三次设计和实现了这个语言，并称其为PostScript。技术准备：什么是熵熵——来源于40年代由ClaudeShannon创立的信息论中的一条定理，这一定理借用了热力学中的名词“熵”(Entropy)来表示一条信息中真正需要编码的信息量：考虑用0和1组成的二进制数码为含有n个符号的某条信息编码，假设符号Fn

在整条信息中重复出现的概率为Pn，则该符号的熵也即表示该符号所需的二进制位数为：En=-log2(Pn)整条信息的熵也即表示整条信息所需的二进制位数为：E=∑knEn例：对信息aabbaccbaa，字符串长度为10，字符a、b、c分别出现了5、3、2次，则Ea=-log2(0.5)=1Eb=-log2(0.3)=1.737Ec=-log2(0.2)=2.322E=5Ea+3Eb+2Ec=14.855位对比一下，我们用ASCII编码表示该信息需要80位技术准备：模型使用模型：得到字符或单词在信息中出现的概率静态/半静态模型自适应模型ClaudeShannon的“聚会游戏”(partygame)：他每次向听众公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符，一次猜一个，直到猜对为止。然后，Shannon使用猜测次数来确定整个信息的熵。（人的语言经验）静态字典模型自适应字典模型统计模型字典模型技术准备：编码通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。最简单的前缀编码字符编码A0B10C110D1110E111101110010101110110111100010DABBDCEAAB技术准备：压缩=模型+编码输入模型编码输出符号概率代码Shannon-Fano编码cabcedeacacdeddaaabaababaaabbacdebaceada

a–16b–7c–6d–6e-5a–16b–7---------c–6-----d–6e-5例子中的信息编码为：1100011110110010100110011......码长共91位，而使用ASCII编码表示上述信息共需要240位a–00b–01c–11d–100e–101root00111abc01deHuffman编码cabcedeacacdeddaaabaababaaabbacdebaceada

a–16b–7c–6d–6e-5例子中的信息编码为：001100000101101001110011001......码长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编码的模型选择奇怪的段落IfYouth，throughoutallhistory，hadhadachampiontostandupforit；toshowadoubtingworldthatachildcanthink；and，possibly，doitpractically；youwouldn'tconstantlyrunacrossfolkstodaywhoclaimthat"achilddon'tknowanything.“-GadsbybyE.V.Wright,1939.算术编码假设某个字符的出现概率为80%，该字符事实上只需要-log2(0.8)=0.322个二进制位进行编码难道真的能只输出0.322个0或0.322个1吗？算术编码的输出是：一个小数算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于0和1之间的二进制小数。例如算术编码对某条信息的输出为1010001111，那么它表示小数0.1010001111，也即十进制数0.64算术编码例：考虑某条信息中可能出现的字符仅有abc三种，我们要压缩保存的原始信息为bccb第一步：在没有开始压缩进程之前，假设我们对abc三者在信息中的出现概率一无所知（我们采用的是自适应模型），即认为三者的出现概率相等，也就是都为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例：考虑某条信息中可能出现的字符仅有abc三种，我们要压缩保存的原始信息为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例：考虑某条信息中可能出现的字符仅有abc三种，我们要压缩保存的原始信息为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例：考虑某条信息中可能出现的字符仅有abc三种，我们要压缩保存的原始信息为bccb算术编码第五步：输入最后一个字符b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的b的区间为0.6390-0.6501，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进制0.1010001111，去掉前面没有太多意义的0和小数点，我们可以输出1010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程0.66670.65010.63900.6334Pc=3/6Pb=2/6Pa=1/6例：考虑某条信息中可能出现的字符仅有abc三种，我们要压缩保存的原始信息为bccb输出:(0.64)10=(0.1010001111)2自适应模型的阶h(t)(t)gh(t)igh(t)例文：theweightof...0阶1阶2阶3阶问题：半静态模型和自适应模型转义码的使用存储空间问题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=310000000000210010010001311010001000104111010101100115111101100100001006111110110110010101711111101110010100110811111110111011011011191111111101111001100010000Golomb编码假设对x编码，令q=int(log2x)则编码的前一部分是q个1加一个0，后一部分是q位长的二进制数，其值等于(x-2q)值x编码10210031014110005110016110107110118111000091110001γ编码LZ77算法的其他问题其他的编码方式：输出匹配串时不输出后续字符输出0表示下面是一个匹配串，输出1表示下面是一个单个字符对匹配串长度加以限制如何查找匹配串：限制匹配串的长度，在内存中组织二叉有序树将窗口中每个长度为3的字符串建立字典索引使用Hash表建立索引使用字符树建立索引窗口滑动时内存中的索引重建问题：建立环状偏移以环状偏移为基础建立窗口索引内存词典：第二步：压缩串“AD...”在内存词典中仍无法找到匹配串，则输出二元组(0，“A”)并将字串“A”置入内存词典第一步：压缩串“DAD...”在内存词典中无法找到匹配串，则输出二元组(0，“D”)二元组中第一个元素表示词典的索引，第二个元素表示后续字符。并将字串“D”置入内存词典内存词典：LZW算法LZW算法是LZ78的改进，其基本思路是在内存中维护一个动态的字典，输出的代码是该字典的索引例：待压缩的信息为"DADDADADADDYDADO..."索引0词条null索引01词条null“D”第三步：压缩串“DD...”在内存词典中可以找到最大匹配串“D”，输出二元组(1，“”)以此对字串“D”进行了编码，然后将“D”置入内存词典内存词典：内存词典：第四步：压缩串“DAD...”在内存词典中可以找到最大匹配串“D”，则输出二元组(1，“A”)以此对字串“DA”进行了编码，然后将“DA”置入内存词典LZW算法例：待压缩的信息为"DADDADADADDYDADO..."索引012词条null“D”“A”索引0123词条null“D”“A”“D”LZW算法例：待压缩的信息为"DADDADADADDYDADO..."第九步后，内存词典的情况如下：索引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图像压缩算法JPEG是有损压缩算法JPEG核心是“离散余弦变换(DiscreteCosineTransform,DCT)”JPEG压缩算法的基本步骤为：1、离散余弦变换DCTTransformation2、系数量化CoefficientQuantization

3、无损压缩LosslessCompression一维波二维波离散余弦变换DCTDCT操作X、Y、Z坐标轴上的三维信号。X、Y坐标轴是平面图像的两个维度，Z轴表示图象的象素值。对N×N的象素矩阵进行DCT变换的公式如下：离散余弦变换(DiscreteCosineTransform,DCT)公式：反向离散余弦变换(InverseDiscreteCosineTransform,IDCT)公式：其中：但是：按照上述基本公式写出的程序实现存在一个严重的问题——时间复杂度太高使用矩阵运算的DCT替代公式实现上面的替代公式的程序代码的时间复杂度就大大降低了。进一步的改进还包括将余弦函数由浮点运算改为整数运算、改进傅立叶变换技术等。量化QuantizationDCT变换的输入是8位的象素值（0~255，JPEG实现时将其减去128，范围变成-12