数字图像处理 第九章 图像压缩编码

数字图像处理DigitalImageProcessing第九章图像压缩编码引言无损编码213有损编码4预测编码

变换编码

混合编码562第九章图像压缩编码引言无损编码213有损编码4预测编码

变换编码

混合编码5639.1引言信息传输方式发生了很大的改变通信方式的改变

文字+语音图像+文字+语音通信对象的改变

人与人人与机器，机器与机器由于通信方式和通信对象的改变带来的最大问题是：传输带宽、速度、存储器容量的限制。4数码图像的普及，导致了数据量的庞大。图像的传输与存储，必须解决图像数据的压缩问题。对于电视画面的分辨率640*480的彩色图像，每秒30帧，则一秒钟的数据量为：640*480*24*30=221.12M

播放时，需要221Mbps的通信回路。在10M带宽网上实时传输的话，需要压缩到原来数据量的0.045，即0.36bit/pixel。9.1引言5

数据冗余例子我们从发送一封电报的例子来体会数据冗余的概念。你的妻子，Helen，将于明天晚上6点零5分在上海的虹桥机场接你。

(23*2+10=56个半角字符)你的妻子将于明天晚上6点零5分在虹桥机场接你

(20*2+2=42个半角字符）

Helen将于明晚6点在虹桥接你

(10*2+6=26个半角字符）9.1引言6图像信息冗余数字化后的图像信息数据量非常大，图像压缩利用图像数据存在冗余信息，去掉这些冗余信息后可以有效压缩图像。常见图像的冗余类型主要表现在：空间冗余时间冗余视觉冗余9.1引言7空间冗余一幅图像表面上各采样点的颜色之间往往存在着空间连贯性。图像内部相邻像素之间的相关性所造成的冗余。

1

2

3

4这是一幅2*2的图像，图像的第一个像素是红的，第二个像素是红的，第三个像素是红的，第四个像素是红的。这是一幅2*2的图像，整幅图都是红色的。9.1引言8时间冗余视频图像不同帧之间的相关性所造成的冗余，运动图像相邻帧往往包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同，所以后一帧的数据与前一帧的数据有许多共同之处，称为时间冗余。9.1引言9视觉冗余人眼不能感知或不敏感的那部分图像信息，人类视觉系统对图像的敏感度是非均匀的。但是，在记录原始的图像数据时，通常假定视觉系统是近似线性的和均匀的，对视觉敏感和不敏，感的部分同等对待，从而产生视觉冗余。9.1引言10举例(248,27,4)(251,32,15)(248,27,4)(248,27,4)33K15K9.1引言11其他的冗余还有：结构冗余：图像中存在很强的纹理结构或自相似性。知识冗余：有些图像中还包含与某些先验知识有关的信息。图像编码的目的就是尽量减小各种冗余信息，特别是空间冗余、视觉冗余，以少的比特数来表示图像。9.1引言12数据压缩技术的理论基础是信息论从信息论的角度来看，压缩就是去掉信息中的冗余，即保留不确定的信息，去掉确定的信息（可推知的）。9.1引言9.1.2信息量和信息熵信息论中信源编码理论解决的主要问题：（2）数据压缩的基本途径（1）数据压缩的理论极限13信息量等于数据量与冗余量之差I=D-du数据是用来记录和传送信息的，或者说数据是信息的载体。信息量与数据量的关系：du—冗余量I—信息量D—数据量真正有用的不是数据本身，而是数据所携带的信息。9.1引言14在日常生活中，极少发生的事件一旦发生是容易引起人们关注的，而司空见惯的事不会引起注意，也就是说，极少见的事件所带来的信息量多。如果用统计学的术语来描述，就是出现概率小的事件信息量多。比如，抢劫银行事件所带来的信息量要比单车被盗事件的信息量大得多。因此，事件出现的概率越小，信息量越大。即信息量的多少是与事件发生频繁（即概率大小）成反比。信息量的度量9.1引言15信息量En=log2(Pn-1)=-log2(Pn)即表示该符号所需的位数考虑用0和1组成的二进制数码为含有n个符号的某条消息编码。假设符号Fn在整条消息中重复出现的概率为Pn，则该符号的信息量概率Pn即是指某事件在一次实验中发生的可能性的大小。信息量的计算公式被确定为事件发生概率的倒数的对数。即概率越大的事件，信息量就越少，反之，则越多。9.1引言16信息熵Entropy信息熵就是平均信息量大多数情况下，研究一个单独的事件发生的信息量是不够的，还应该了解一系列事情整体的性质，也就是整体平均信息量，或称为信息熵。9.1引言pj

每个信息出现的概率17输入字符串：aabbaccbaaa、b、c出现的概率分别为0.5、0.3和0.2，他们的信息量分别为：Ea=-log2(0.5)=1Eb=-log2(0.3)=1.737Ec=-log2(0.2)=2.322总信息量也即表达整个字符串需要的位数为：E=Ea*5+Eb*3+Ec*2=14.855位举例说明：如果用二进制等长编码,需要多少位?20位9.1引言18平均码长与信息熵如果对字符aj的编码长度为Lj，则信号L的平均码长为：m:信号中所出现不同字符的个数。9.1引言19平均码长≈H(X)(稍大于H(X))：平均码长>>H(X)：平均码长<H(X)：熵值是平均码长的下限

有冗余，不是最佳；不可能是最佳编码9.1引言20符号S1S2S3S4出现概率1/21/41/81/8该数据流的信息熵及相应编码方式的平均码长?举例：输入数据流：S1S2S1S3S2S1S1S4等长编码00011011霍夫曼010110111H(X)=1.75L1=2L2=1.759.1引言21数据压缩的理论极限是信息熵。只要信源不是等概率分布，就存在着数据压缩的可能性。数据压缩的基本途径之一：使各字符的编码长度尽量等于字符的信息量。9.1引言22一个典型的信号压缩系统如图所示：通过时间轴上采样和幅度量化将连续信号变成离散数字信号。将信号中绝大部分能量集中在少数几个变换系数上，去除信号中的相关性。信号压缩真正体现在量化阶段。一般先是游程编码，然后Huffman编码或算术编码进一步提高压缩比。9.1引言23图像压缩编码分类：根据时间第一代压缩编码八十年代以前，主要是根据传统的信源编码方法。9.1引言像素编码变换编码预测编码位平面编码增量调制熵编码算术编码DCT变换DPCM调制第一代压缩编码其他编码行程编码24第二代压缩编码八十年代以后，突破信源编码理论，结合分形、模型基、神经网络、小波变换等数学工具，充分利用视觉系统生理心理特性和图像信源的各种特性。子带编码模型编码分层编码分型编码第二代压缩编码9.1引言25根据编码原理：熵编码：无损编码，给出现概率较大的符号赋予一个短码字，而给出现概率较小的符号赋予一个长码字，从而使得最终的平均码长很小。预测编码：基于图像数据的空间或时间冗余特性，用相邻的已知像素（或像素块）来预测当前像素（或像素块）的取值，然后再对预测误差进行量化和编码。变换编码：将空间域上的图像变换到另一变换域上，变换后图像的大部分能量只集中到少数几个变换系数上，采用适当的量化和熵编码就可以有效地压缩图像。9.1引言26无损编码重构图像与原图像完全一样。对原始信号的准确程度要求高的场合。在医疗或商业文件的归档，有损压缩因为法律原因而被禁止。卫星成像的收集，考虑数据使用和所花费用，不希望有任何数据损失。X光拍片，信息的丢失会导致诊断的正确性。减少像素间冗余减少编码冗余9.1引言27无损编码霍夫（Huffman）编码其它变长编码算术编码LZW编码位平面编码无损预测编码9.1引言28有损编码解码后重新构造的图像与原始图像存在不同。利用心理冗余和空间冗余。容易取得较好的压缩比。9.1引言29图像编码评价评价图像压缩算法的优劣主要有以下4个参数：

1）算法的编码效率

2）编码图像的质量

3）算法的适用范围

4）算法的复杂度9.1引言30第九章图像压缩编码引言无损编码213有损编码4预测编码

变换编码

混合编码56319.2.1哈夫曼编码9.2.2香农-范诺编码9.2.3行程编码9.2.4轮廓编码9.2.5位平面编码9.2.6LZW编码9.2.7算术编码9.2无损编码32先统计数据中各字符出现的概率，再按字符出现频率高低的顺序分别赋以由短到长的代码，从而保证文件整体的大部分字符是由较短的编码所构成。哈夫曼（Huffman）编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。即使在今天，在许多知名的压缩工具和压缩算法里（如WinZip、gzip和JPEG），也都有HuffmanCoding的身影。编码思想9.2无损编码9.2.1Huffman编码33将信源符号按概率递增顺序排列；将两个最小的概率加起来作为新符号的概率；并保证每层节点左小，右大；重复步骤①和②，直到概率和等于1；完成上述步骤后沿路径返回进行编码。寻找从每一信源符号到概率为1处的路径，每层有两个分支，左节点标0，右节点标1。编码从根节点开始到叶子节点得到每个符号的编码。9.2无损编码编码过程9.2.1Huffman编码343010402020402002020303020402040灰度值：010203040出现频率：1/161/167/163/164/169.2无损编码9.2.1Huffman编码统计出每级灰度出现的频率：35灰度值：010304020出现频率：1/161/163/164/167/1630104020204020020203030204020409.2无损编码9.2.1Huffman编码从左到右把上述频率按从小到大的顺序排列。36选出频率最小的两个值（1/16，1/16）作为二叉树的两个叶子节点，将频率和2/16作为它们的根节点,新的根节点再参与其它频率排序：1/161/162/169.2无损编码9.2.1Huffman编码灰度值：010304020出现频率：1/161/163/164/167/162/163/164/167/1637选出频率最小的两个值（2/16，3/16）作为二叉树的两个叶子节点，将频率和5/16作为它们的根节点,新的根节点再参与其它频率排序：

1/161/162/163/165/162/16

3/164/167/16

4/165/167/169.2无损编码9.2.1Huffman编码38选出频率最小的两个值（4/16，5/16）作为二叉树的两个叶子节点将频率和9/16作为它们的根节点,新的根节点再参与其它频率排序：1/161/162/163/165/164/169/16

4/165/167/167/169/169.2无损编码9.2.1Huffman编码39最后两个频率值（7/16，9/16）作为二叉树的两个叶子节点，将频率和1作为它们的根节点。1/161/162/163/165/164/169/167/1617/16

9/169.2无损编码9.2.1Huffman编码403010402020402002020303020402040分配码字。将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各级灰度的编码.01003014002001110灰度值：010304020出现频率：1/161/163/164/167/169.2无损编码9.2.1Huffman编码41各灰度的编码如下：

灰度值：

204030100哈夫曼编码：01011111011100则图所示的图像哈夫曼编码为：11111010100101100000111111010100共用了32比特，原图像占128比特，压缩比较高。0100301400200111030104020204020020203030204020409.2无损编码9.2.1Huffman编码42常用的且有效的方法是将图像分割成若干的小块，对每块进行独立的Huffman编码。8*8分块的编码效率为47.27%16*16分块的编码效率约为61%9.2无损编码9.2.1Huffman编码43假设某个字符的出现概率为80%，该字符只需要-log2(0.8)=0.322位编码，但Huffman编码一定会为其分配一位0

或一位1

的编码。由此可得知，整个信息的80%在压缩后几乎相当于理想长度的3倍左右。存在问题分析：编码中每个符号的编码长度只能为整数，如果源符号集的概率分布不是2的负n次方的形式，则无法达到熵极限。为可变长度码,译码复杂。需要事先知道输入符号集的概率分布。编码效率高只在图像灰度分布不均匀的时候。霍夫曼编码的局限性：9.2无损编码9.2.1Huffman编码44香农-范诺编码的理论基础是符号的码字长度Ni完全由该符号出现的概率来决定，即：式中，D为编码所用的数制。香农－范诺编码与Huffman编码相反，采用从上到下的方法。在理想意义上，它与哈夫曼编码一样，并未实现码词（codeword）长度的最低预期；然而，与哈夫曼编码不同的是，它确保了所有的码词长度在一个理想的理论范围。9.2无损编码9.2.2香农-范诺编码45首先将编码字符集中的字符按照出现频度和概率大小进行排序。编码（从根结点开始）。用递归的方法分成两部分，使两个部分的概率和接近于相等。给前一个子集合赋值为0，后面的赋值为1直至不可再分，即每一个叶子对应一个字符。具体步骤：9.2.2香农-范诺编码9.2无损编码46如：设一副灰度级为8的图象中，各灰度所对应的概率分别为0.04，0.05，0.06，0.07，0.10，0.10，0.18，0.40

现在对其进行二分法香农－范诺编码。9.2.2香农-范诺编码9.2无损编码47s0,s1,s2,s3,s4,s5,s6,s7s2,s3,s4,s5,s6,s7s0,s10.580.42s2,s3s4,s5,s6,s7s0s1s4,s5s6,s7s2s3s4s5s6s7s00.40s1s2s3s4s5s60.180.100.100.07s70.060.050.040.200.220.130.0901010101010101S0:00S1:01S2:100S3:101S4:1100S5:1101S6:1110S7:11119.2无损编码48香农－范诺编码效率不如霍夫曼编码。9.2.2香农-范诺编码9.2无损编码编码方案取决于分组方案的效果是否最佳，当信源中消息的数量较多时，寻找最佳分方案将是一件费力的事。49行程编码又称行程长度编码（RunLengthEncoding，RLE)，是一种熵编码，其编码原理是将具有相同值的连续串用其串长和一个代表值来代替，该连续串就称为行程，串长称为行程长度。图像中—行程：具有相同灰度值的像素序列。将一行中颜色值相同的相邻象素（行程）用一个计数值（行程的长度）和该颜色值（行程的灰度）来代替，从而去除像素冗余。RLE编码简单直观，编码/解码速度快，因此许多图形、图像和视频文件，如.BMP、.TIFF及AVI等格式文件的压缩均采用此方法。9.2无损编码9.2.3行程编码50定长行程编码：编码的行程长度所用的二进制位数固定。变长行程编码：不同范围的行程长度用不同编码位，需要增加标志位来表明所使用的二进制位数。问题？不知道各行程应在何处分断。下面介绍：二值图变长行程编码的一种方法。例1：aabbbcddddd的行程编码为2a3b1c5d。9.2无损编码9.2.3行程编码513124911110010010011111001001001分断？变长行程编码：编码规则

b+[(Code)2-1]可表示行程长度值编码b？？编码长度

1-40??35-810???59-16110????717-321110?????933-6411110??????1165-128111110???????13如：1100的编码为：1100-1=1011（十进制11）行程编码为：11010119.2无损编码9.2.3行程编码52

0101101011011110100031249111100100100110101111100001011010110111101000还原方法：从符号串左端开始往右搜索，遇到第一个0时停下来，计算这个0的前面有几个1。设1的个数为K，则在0后面读K+2个符号，这K+2个符号所表示的二进制数加上1的值就是第1个行程的长度。9.2无损编码9.2.3行程编码53开始搜索第一个0该0前1的个数为0读0+2个字符10+01=11第二个0该0前1的个数为2读2+2个字符1011+0001=1100第三个0该0前1的个数为0读0+2个字符11+01=100第四个0该0前1的个数为2读2+2个字符1000+0001=1001第五个0该0前1的个数为0读0+2个字符00+01=01(1)01011101101111100000000000009.2无损编码9.2.3行程编码1249111100100100154对于有大面积色块的图像，压缩效果很好。对于纷杂的图像，压缩效果不好，最坏情况下（图像中每两个相邻点的颜色都不同），会使数据量加倍，所以现在单纯采用行程编码的压缩算法用得并不多，PCX文件算是其中之一。9.2无损编码9.2.3行程编码55二维行程编码要解决的核心问题是：将二维排列的像素，采用某种方式转化成一维排列的方式。之后按照一维行程编码方式进行编码。两种典型的二维行程编码的排列方式。9.2无损编码9.2.3行程编码56数据量：64*8=512(bit)9.2无损编码9.2.3行程编码57如果按照方式(a)扫描的顺序排列的话，数据分布为：130，130，130，130，130，130，130，130，130；129，129，129，129，130，130，129；127，128，127，129，131，130，132，133，133；133，133，132，130，129，128，127，128，127，128，127，125，126，129，129；127，129，133，132，131，129，130，130；129，130，130，130，129，130，132，132；131，131，130，126，128，128，127，127行程编码为:规定行程码长度为3bit数据量为:43*（3+8）=473(bit)(94.22%)（7，130），（2，130），（4，129），（2，130），（1，129）；（1，127），（1，128），（1，127），（1，129），（1，131），（1，130），（1，132），（4，133），（1，132），（1，130），（1，129），（1，128），（1，127），（1，128），（1，127），（1，128），（1，127），（1，125），（1，126），（2，129），（1，127），（1，129），（1，133），（1，132），（1，131），（1，129），（2，130），（1，129），（3，130），（1，129），（1，130），（2，132），（2，131），（1，130），（1，126），（2，128），（2，127）9.2无损编码58通常，为了达到比较好的压缩效果，一般不单独使用行程编码，而是和其他编码方法结合使用。如：在JPEG中，就综合使用了行程编码、DCT、量化编码以及哈夫曼编码。9.2无损编码9.2.3行程编码59任何编码的技术的成功与否，最终取决于他与给定的图像结构匹配的如何。设计一个好的编码器，首先是了解原始图像的结构，然后选择一种适合哪种结构的最佳编码方法。在某些应用中，原始图像显示出一些简单的图像结构，如灰度级较少的气象云图，大幅人头像等，边界往往是感兴趣的结构特性。本节介绍的轮廓编码就是针对这种图形的编码方法。9.2.4轮廓编码（或等值线编码）9.2无损编码60编码思想：一幅数字图像的灰度级是有限的，我们可以把一幅数字图像看做由和那多等灰度区所构成的。如图：其中每条等值线刻画出一条等灰度区的边界，如能将各个灰度去边界的位置和灰度级进行编码、传输、在接收端就可以重现原始图像；且因各个灰度区内部的像素部可编码，从而使数据得到大量的压缩。关键：确定等值线的起点和移动方向来编码。9.2无损编码9.2.4轮廓编码（或等值线编码）61IP例：左图为图像f(x,y)中的目标区域，采用八方位码。45671023八方位码9.2无损编码9.2.4轮廓编码（或等值线编码）则区域链码0422412242614261716162一种能有效减少像素间冗余的技术，对相关性强的图像，它的编码效率比霍夫曼码更高。基本方法：将多级图像（灰度图像或彩色图像）分解成一系列的二值图像，然后对二值图像应用二值图像编码方法，以达到对多值图像编码的目的。位平面分解的两种方法二值图像位平面灰度编码位平面9.2.5位平面编码9.2无损编码63设灰度图像的灰度级需要m比特表示，那么任意一个灰度级g都可以表示成一个以2为底的多项式：（二进制计算）其中ai=0/1，i=0,1,2,…,m-1图像的同一个比特位的系数的集合就是一个二值图像，称为一个“位平面”。位平面编号从0开始，直到m-1。将m个位平面组合，显然又可以恢复原来的灰度图像。127（011111112）和128（100000002）二值图像位平面分解：9.2无损编码9.2.5位平面编码6412810000000127011111110111111012501111101128127126125灰度级就差一位黑白很分明！！缺点：图像在灰度级上稍有变化就会对位平面的复杂性产生显著影响。9.2无损编码9.2.5位平面编码659.2无损编码9.2.5位平面编码二值图像位平面二值图像位平面灰度编码位平面灰度编码位平面66灰度编码分解位平面为减少这种小灰度值变化的影响可用1个mbit的灰度码来表示图像。灰度码（格雷码）和二进制码的互相转换可由右式计算：异或格雷码的优点：差值为1的两个数值的格雷码只有一位不同。127（01000000g）,128（11000000g），转换后就只在第7个位平面有一个0到1的变化。127（011111112）128（100000002）m=89.2无损编码9.2.5位平面编码67灰度码（格雷码）128110000001270100000001000001125010000111281271261259.2无损编码9.2.5位平面编码68位平面分解方法总结低位面图比高位面图复杂，即低位面图比高位面图包括的细节要多，也更随机。灰度编码表达的位面图复杂度较低，但具有视觉意义信息的位面图数量更多。图形图像或文本图像。大量的是连续的白色背景，对这些连续的块指定短码字，可以达到压缩的效果。9.2.5位平面编码9.2无损编码69利用了文本类图像中空白较多的特点。将图像的一行分成若干段，规定每段有k个象素；若k个象素全是空白，则用“0”表示；否则用“1”表示，后接直接编码。例：不同的10个像素，它们相应的代码如下：10个象素 相应的代码0000000000 0000000000110000000001100000000111000000001当k=10时，对大多数文本文件比较合适。9.2无损编码9.2.6空白编码70

9.2无损编码9.2.6空白编码扩展到二维，是对图像中大片的连续的1或0的区域（黑白块）进行识别编码。设图像被分解为若干块，每一块的大小一致，为a

b。这些块只有三种类型：全白色、全黑色、混合区域。统计这三类区域的出现概率。码字分配：出现概率最大的类型用1比特码字“0”表示，其他的用2比特码字“10”和“11”表示，后接对应区域的直接编码。71进一步提高编码效率的方法是使用迭代的方法将二值图像分解为越来越小的块，逐层进行编码。逐层编码算法：纯白色的图像块用1比特码字“0”表示。其他类型图像用1比特码字“1”表示，并且对图像进行四等份分割，得到四个子块。对每一个子块重复过程(1)(2)，

一直到规定的最小子块尺寸。图像最小子块采用原图像信息的直接编码。9.2无损编码9.2.6空白编码72LZW（Lempel-Ziv&Welch）编码又称字串表编码，属于一种无损编码，LZW编码与行程编码类似，也是对字符串进行编码从而实现压缩，但它在编码的同时还生成了特定字符串以及与之对应的索引字符串表。9.2无损编码9.2.7LZW编码73LZW压缩使用字典库查找方案。它读入待压缩的数据并与一个字典库（库开始是空的）中的字符串对比，如有匹配的字符串，则输出该字符串数据在字典库中的位置索引，否则将该字符串插入字典中。算法思想9.2无损编码9.2.7LZW编码74对LZW算法的分析：LZW算法的适用范围是原始数据串最好是有大量的子串多次重复出现，重复的越多，压缩效果越好。反之则越差，可能真的不减反增了。LZW压缩技术对于可预测性不大的数据具有较好的处理效果，常用于GIF格式的图像压缩，其平均压缩比在2:1以上，最高压缩比可达到3:1。除了用于图像数据处理以外，LZW压缩技术还被用于文本程序等数据压缩领域。对于任意宽度和像素位长度的图像，都具有稳定的压缩过程。压缩和解压缩速度较快。9.2无损编码9.2.7LZW编码75如果“否”，则输出与当前前缀S1相对应的码字；将S1＋S2添加到词典中；步骤1：将词典初始化为包含所有可能的单字字符，当前前缀S1初始化为空。步骤2：当前字符S2:=字符流中的下一个字符。LZW编码算法9.2无损编码9.2.7LZW编码令S1:=S2，现在的S1仅包含一个字符S2步骤3：判断S1＋S2是否在词典中如果“是”，则用S2扩展S1，即让S1:=S1＋S2步骤4：判断码字流中是否还有码字要译如果“是”，就返回到步骤2；如果“否”把代表当前前缀P的码字输出到码字流；结束。76初始化字符串表字符串索引a0Hb1Hc2Hd3HLZW_CLEAR4HLZW_EOI5HLZW编码实例aabcabbbbd

9.2无损编码9.2.7LZW编码77输入数据S2S1+S2输出结果S1生成的新字符串及索引NULLaabcabbbbdNULLNULLaaaaa0H0Habbccaababbbbbbbbd1H2H7H1HBH3H5Hbcaabbbbbdaa<6H>ab<7H>bc<8H>ca<9H>abb<AH>bb<BH>bbd<CH>S1+S2在字符表中,S1=S1+S2aa不存在,故输出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“a”ab不存在,故输出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“b”S1+S2结果已存在,故输出结果为空S1+S2在字符表中,S1=S1+S2此时已无输入输出S1的索引3H输出LZW_EOI标志的索引78HuffmanCoding并没有彻底达到信息熵的极限，直观上可以看做是由于限制了每个符号的编码必须是整数位二进制数所造成的。如果能够采用不一定整数长度的编码(

譬如0.112个0或0.555个1?)就使编码的长度能够真正朝信息熵极限逼近。二十多年前，天才数学家们用一种巧妙的思路完美地解决了这个问题--算术编码。算术编码绕过了用一个特定的代码替代一个输入符号的想法,用一个浮点输出数值代替一个流的输入符号,较长的复杂的消息输出的数值中就需要更多的位数。信源符号概率接近时,建议使用算术编码,这种情况下其效率高于Huffman编码。

9.2无损编码9.2.8算术编码79算术编码有两种模式：一种是基于信源概率统计特性的静态算术编码。另一种是针对未知信源概率模型的自适应模式。在静态算术编码中，信源符号的概率是固定的。

9.2无损编码9.2.8算术编码80用一个例子来说明一下固定算数编码的过程：

待编码的数据序列为“dacab”，那么我们规定信源中的符号取值范围是{a,b,c,d},各符号出现的概率依次为：P(a)=0.4，P(b)=0.2，P(c)=0.2，P(d)=0.2。初始时，取区间为[0，1]；这个区间内我们认为被a,b,c和d按各自概率划分了，其中：a=［0,0.4）b=［0.4,0.6）c=［0.6,0.8）d=［0.8,1.0]9.2无损编码9.2.8算术编码81a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）StartN=StartB+LeftC×L

EndN=StartB+RightC×L

首先读入d：令初始间隔为［0.8,1.0)第二个输入a：令新的间隔为StartN=0.8+0×(1.0-0.8)=0.8则“a”的实际编码区间在［0.8,0.88)之间。“a”的取值范围应在前一符号间隔［0.8,1.0)的［0,0.4)子区间内EndN=0.8+0.4×(1.0-0.8)=0.88dacab9.2无损编码82a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）输入c：StartN=0.8+0.6×(0.88-0.8)=0.848“c”的取值范围应在前一符号间隔［0.8,0.88)的［0.6,0.8)子区间内EndN=0.8+0.8×(0.88-0.8)=0.864“c”的实际编码区间在［0.848,0.864)之间dacab9.2无损编码StartN=StartB+LeftC×L

EndN=StartB+RightC×L

83输入a：StartN=0.848+0×(0.864-0.848)=0.848“a”取值范围应在前一符号间隔［0.848,0.864)的［0,0.4)子区间内EndN=0.848+0.4×(0.864-0.848)=0.8544“a”的实际编码区间在［0.848,0.8544)之间dacab9.2无损编码a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）StartN=StartB+LeftC×L

EndN=StartB+RightC×L

84输入b：StartN=0.848+0.4×(0.8544-0.848)=0.85056“b”取值范围应在前一符号间隔［0.848,0.8544)的［0.4,0.6)子区间内EndN=0.848+0.6×(0.8544-0.848)=0.85184“b”的实际编码区间在［0.85056,0.85184)之间9.2无损编码dacaba=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）StartN=StartB+LeftC×L

EndN=StartB+RightC×L

85数据序列“dacab”已被描述为一个实数区间［0.85056,0.85184］，在此区间内的任一实数值都惟一对应该数据序列。这样，就可以用一个实数表示这一数据序列。把区间［0.85056,0.85184］用二进制形式表示为［0.110110011011,0.110110100001］。消息的编码输出可以是最后一个间隔中的任意数。9.2无损编码9.2.8算术编码860.110110100001–0.000000000001=0.110110100000》0.1101100110110.1101101位于这个区间内并且其编码最短，故把其作为数据序列“dacab”的编码输出。不考虑“0.”，把1101101作为本例中的数据序列的算术编码。由此可见，数据序列“dacab”用7比特的二进制代码就可以表示，平均码长为1.4比特／字符。解码是编码的逆过程。9.2无损编码9.2.8算术编码87第九章图像压缩编码引言无损编码213有损编码4预测编码

变换编码

混合编码56889.3有损编码有损压缩编码：通过牺牲图像的准确率来达到加大压缩率的目的压缩比：在图像压缩比大于30:1时，仍然能够重构图像在图像压缩比为10:1到20:1时，重构图像与原图几乎没有差别无损压缩的压缩比很少有能超过3:1的有损无损压缩方法的根本差别在于有没有量化模块89源数据编码与解码的模型源数据编码的模型源数据解码的模型符号解码器数据数据量化器符号编码器9.3有损编码90量化器基本思想：减少数据量的最简单的办法是将图像量化成较少的灰度级，通过减少图像的灰度级来实现图像的压缩。这种量化是不可逆的，因而解码时图像有损失。例：如果输入是256个灰度级，对灰度级量化后输出，只剩下4个层次，数据量被大大减少。sts1s2s3t1t2t39.3有损编码91第九章图像压缩编码引言无损编码213有损编码4预测编码

变换编码

混合编码5692主要内容预测编码原理无损预测编码有损预测编码DM有损预测编码9.4预测编码93利用视频图像帧间的相关性，即时间相关性，来达到图像压缩的目的，广泛用于普通电视、会议电视、视频电话、高清晰度电视的压缩编码。无损预测编码有损预测编码

9.4预测编码9.4.1预测编码原理94（1）系统组成：编码器+解码器（有相同的预测器）

9.4预测编码9.4.2无损预测编码第95页（2）编码过程：输入序列：f1,…,fn-1

计算预测：（舍入成整数）计算预测差值：

差值编码：在符号编码器中用变长码编产生压缩数据流的下一个元素。

解码预测，输出序列：1,…,fn-1

获得当前帧：

哪里取得了压缩？只传输预测与实际的差值9.4预测编码第96页

（3）几种预测器

m阶线性预测：

在1-D线性预测编码中，设扫描沿行进行，预测值可写：

一阶1-D线性预测：round是舍入函数，ai是预测系数9.4预测编码第97页9.4预测编码（4）举例对于输入序列{10，15，20，15，10}采用一维线性编码进行无损预测编码。预测值等于上一个像素的值f0=null编码f1=10f2’=10f2=15e=5,解码f1=10f2’=10f2=f2’+e=15编码f2=15f3’=15f3=20e=5,解码f2=15f3’=15f3=f3’+e=20编码f3=20f4’=20f4=15e=-5,解码f3=20f4’=20f4=f4’+e=15编码f4=15f5’=15f5=10e=-5,解码f4=15f5’=15f5=f5’+e=10第98页

9.4.3有损预测编码（LossyPredictiveCoding)增加了量化器，量化器插在符号编码器和预测误差产生处之间，且把原来无损编码器中的整数舍入模块吸收了进来。它的作用是将预测误差映射进有限个输出中。9.4预测编码99算法的演变有损预测编码的演变——引入量化：将en

用 编码：

解码：9.4预测编码1009.4预测编码9.4.4德尔塔调制(增量调制)DM(Deltamodulation) 预测器 量化器预测系数a≤

1，常数c>0101DM编码示例a=1，C=6.5输入序列：14,15,14,15,13,15,15,14,20,26,27,28,27,27,29,37,47,62,75,77,78,79,80,81,81,82,82102失真问题：1）颗粒噪声：当c远大于输入中的最小变化时，如n＝1、n＝7等2）斜率过载：当c远小于输入中的最大变化时，如n＝14到n＝21输入信号斜率大，量化跟不上：因为每个抽样间隔内只容许有一个量化电平的变化，所以当输入信号的斜率比抽样周期决定的固定斜率大时。9.4预测编码103第九章图像压缩编码引言无损编码213有损编码4预测编码

变换编码

混合编码561049.5.1变换编码（TransformCoding）系统图像分解：减少变换的计算复杂度图像变换：解除每个子图像内部像素之间的相关性，或者说将尽可能多的信息集中到尽可能少的变换系数上压缩不是在变换中而是在量化变换系数时及编码取得的9.5变换编码第105页子图像尺寸选择:影响变换编码误差和计算复杂度（压缩量和计算复杂度都随子图像尺寸的增加而增加）两个条件： ①相邻子图像之间的相关（冗余）减少到某个可接受的水平；②子图像的长和宽都是2的整数次幂最常用的子图像尺寸：8

8和16

169.5变换编码106变换编码重建误差与子图像尺寸的关系:9.5变换编码第107页原理：根据傅立叶变换的性质，如果变换函数是一个连续的实偶函数，既存在f(x)=f(-x)时，则有下面结果：变换后只含有余弦项。故称为余弦变换。因为余弦函数是偶函数，所以变换后的频率函数也是偶函数。如果把离散序列拓展成某种偶对称函数，那么他的离散傅里叶变换也就只包含余弦项了。9.5变换编码9.5.2一维DCT的变换108

定义如下：设{f(x)|x=0,1,…,N-1}为离散的信号列。式中，u,x=0,1,2,…,N－1。令9.5变换编码109分开表示：式中F(u)是第u个余弦变换系数，u是广义频率变量，u=1,2,…,N-1；f(x)是时域N点序列x=0,1,2,…,N-1。

9.5变换编码110将变换式展开整理后，可以写成矩阵的形式，即F=Gf其中9.5变换编码111举例：如果令N=4，由一维解析式定义可得如下展开式：写成矩阵形式：[F(u)]=[G][f(x)]G=9.5变换编码112

一维DCT的逆变换IDCT定义为式中，

x,u=0,1,2,…,N－1。可见一维DCT的逆变换核与正变换核是相同的。9.5变换编码113N=4，可得到反变换展开形式：写成矩阵形式：[f(x)]=[A]T[F(u)]9.5变换编码1149.5.3二维离散余弦变换式中，C(u)和C(v)的定义同前面；x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。二维DCT定义如下：设f(x,y)为M×N的数字图像矩阵，则9.5变换编码115二维DCT逆变换定义如下：式中：x,u=0,1,2,…,M－1；

y,v=0,1,2,…,N－1。9.5变换编码116式中：C(x)和C(y)的定义同前；x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。9.5变换编码同时，由上面的两个式子可知二维DCT的逆变换核与正变换核相同，且是可分离的，即117类似一维矩阵形式的DCT，可以写出二维DCT的矩阵形式如下：F=GfGT9.5变换编码第118页

余弦变换的物理意义：先将整体图像分成N×N像素块,然后对N×N像素块逐一进行DCT变换其中N是像块的水平、垂直像素数，一般取N=8。N大于8时效率增加不多而