1、Chap 10 图象压缩与编码要点：要点：信息量，熵，联合熵，率失真函数 编码效率，冗余度，压缩比 无失真编码，有失真编码 霍夫曼编码 行程编码 预测编码 DCT编码 混合编码图象压缩与编码 数字图象通常要求很大的比特数，这给图象的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。如一幅512x512的黑白图象的比特数为 512x512x8=。再如一部90分钟的彩色电影，每秒放映24帧。把它数字化，每帧512x512象素，每象素的、三分量分别占8 bit，总比特数为图象压缩与编码 90 x60 x24x3x512x512x8bit=。如一张CD光盘可存600兆字节数据，这部电影光图象
2、（还有声音）就需要张CD光盘用来存储。对图象数据进行压缩显得非常必要。本章讨论的问题：在满足一定条件下，能否减小图象bit数，以及用什么样的编码方法使之减少。英文字母出现相对频率英文字母出现相对频率图象编码密码图象编码密码图象压缩与编码1图象数据压缩是可能的：一般原始图象中存在很大的冗余度。用户通常允许图象失真。当信道的分辨率不及原始图象的分辨率时，降低输入的原始图象的分辨率对输出图象分辨率影响不大。用户对原始图象的信号不全都感兴趣，可用特征提取和图象识别的方法，丢掉大量无用的信息。提取有用的信息，使必须传输和存储的图象数据大大减少。图象压缩与编码2原始图象越有规则，各象素之间的相关性越强，它
3、可能压缩的数据就越多。值得指出的是：当前采用的编码方法得到的结果，离可能压缩的极限还相差很远，这说明图象数据压缩的潜力是很大的，直到目前为止，它还是个正在继续研究的领域。图象压缩与编码3图象结构的性质，大体上可分为两大类，一类是具有一定图形特征的结构，另一类是具有一定概率统计特性的结构。基于不同的图象结构特性，应采用不同的压缩编码方法。图象压缩与编码4全面评价一种编码方法的优劣，除了看它的、和以外，还要看它的，是否。常采用混合编码的方案，以求在性能和经济上取得折衷。随着计算方法及VLSI的发展，使许多高效而又比较复杂的编码方法在工程上有实现的可能。信源编码的基本概念 图象数据压缩的是在满足一定
4、图象质量条件下，用尽可能少的比特数来表示原始图象，以提高图象传输的效率和减少图象存储的容量，在信息论中称为。信源编码可分为两大类，一类是，另一类是或称。无失真编码又称或。从N个相等可能发生的事件中，选出其中一个事件所需的信息度量，称为。无失真编码要辨识1到32中选定的某一个数，可先提问：“是否大于16？”，得到回答就消去半数可能事件。每提问一次得到回答，可以得到1bit信息量（二进制位）。这里共需5次，因此所需的信息量为 。532log2无失真编码从N个数选定一个数s的概率为p(s)，且等概率，p(s)=1/N。设信源符号表为 s=s1,s2,sq，其概率分布为P(s)=p(s1),p(s2)
5、,p(sq)，则信源的为)()(log1loglog)(222spIspNNsIqiiiqiiispIspspspH112)()()(log)()(s无失真编码 s作为灰度，共q级，出现概率均等时，p(si)=1/q，当灰度只有两级时，即si=0,1，且0出现概率为p1，1出现概率为p2=1-p1，其熵qqqHqi212log1log1)(s12112111log)1(1log)(ppppHs无失真编码 当p1=1/2，p2=1-p1=1/2时，H(s)=1为最大值。如图所示。无失真编码（1）熵是一个非负数，即总有H(s)0。（2）当其中一个符号sj的出现概率p(sj)=1时，其余符号si(i
6、j)的出现概率p(si)=0，H(s)=0。（3）当各个si出现的概率相同时，则最大平均信息量为log2 q。（4）熵值总有H(s)log2 q。无失真编码(一)可以证明，在无干扰的条件下，存在一种无失真的编码方法，使编码的平均长度 L 与 信 源 的 熵 H(s)任 意 地 接 近，即L=H(s)+，其中为任意小的正数，但以H(s)为其下限，即LH(s)，这就是。L)(sHL)(sHL无失真编码(二)对于无失真图象的编码，原始图象数据的压缩存在一个下限，即平均码组长度不能小于原始图象的熵，而理论上的最佳编码的平均码长无限接近原始图象的熵。原始图象定义为：1)(1sHLr原始图象的熵原始图象平
7、均码长无失真编码 将定义为：rLsH11)(冗余度接近于0，或编码效率接近于1的编码称为。无失真编码 若原始图象的平均比特率为n，编码后的平均比特率为nd，则C定义为：dnnC 由Shannon定理，无失真编码为：)()(sHnsHnCM无失真编码 令q=2L，其中L等于自然二进制码的长度。可以证明，对于独立信源，等概率分布时，具有最大熵HM(s)=L比特，因而冗余度r=L/HM(s)-1=0，不可能压缩。（1），又称，符号si 的出现，与其他的符号无关。qiiispspH12)(log)()(s无失真编码 非等概率分布时的熵，一般有H1(s)0，还有可能压缩。（2）又称，它的统计特性要用或来
8、描述。m阶Markov信源，是指某个符号si出现的概率只与前面m个符号有关。无失真编码 设s=s1,s2,sq，则转移概率 p(si/si1,si2,sim)乃是前m个符号为si1,si2,sim时，第 m+1个符号为si的概率。I(si/si1,si2,sim)=-log2 p(si/si1,si2,sim)无失真编码 对符号表取平均的信息量 ),(),(log),(),(),(),(211212211212121miiiqimiiiimiiiiqimiiimiiimiiisssHsssspsssspsssIssspsssIssss 这是在给定序列si1,si2,sim的条件下，信源的条件熵
9、。无失真编码 再考虑序列si1,si2,sim发生的概率，可将定义为：),(log),(),(log),(),(),(),()(212112111212211121111212111121212miiiiqiqiimiiiqiqimiiiimiiiiqiqimiiiqiqiqimiiimiiiqiqisssspsssspsssspsssspssspsssHssspHmmmss无失真编码（四）无干扰编码定理只指出存在一种无失真的编码，可使 。它并没有指出具体的编码方法。下面介绍几种具体的编码方法。（1）它是长度不均匀的，其平均长度最短的即时可译码。其是对经常出现的符)(sHL英文字母出现相对频率
10、英文字母出现相对频率国际莫尔斯电码符号无失真编码号赋予最短的码字，然后按出现概率减少的次序，逐个赋予较长的码字，这样可使码的平均长度qiiilpL1具有最小值，pi-si出现概率，li-对si编码的长度。无失真编码 i.将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。无失真编码ii.把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。iii.重复上述做法，直到最后剩下两个概率为止。iv.从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个二进制码，如对概率大的赋予码元0，对概率小的赋予码元1。H
11、uffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman编码输入S1S2S3
12、S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101
13、010101S1=1Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S3=011Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30
14、.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S5=01010Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011无
15、失真编码（2）在某些应用中，编码器输入符号集合的概率分布服从乘幂律：pk=k-r,k=1,2,q。r为正常数，则用B码，它接近于最佳编码。B码是一种非等长码，由两部分组成，一部分叫“”，一部分叫“”。延续比特的作用是标注一个码字究竟延续多长，信息比特的作用是表示不同的信息符号。无失真编码 将信源符号按出现概率从大到小排序，然后按B1码的前后顺序分别赋予相应符号，便得到各符号的B1码。其中信息码是按二进制的长度及数的顺序排列的，即0，1，00，01，10，11，000，001，。延续码C是在编码过程中确定的，可将C=0赋予前一个码字，将C=1赋予后一个码字，再将C=0赋予下一个码字。无失真编码
16、例如，编码器输入符号序列为s4s1s5s2,则B1码为：0 1，0，1 0，1，或者 0 1，0，1 0，1，延续码改变，表示前一个码字结束，后一个码字开始。编码方法简单，容易实现。无失真编码（3）对具有单调减小概率的输入信号相当有效的非等长码。S2码由2bit长的码字组成，总共包含四个不同的码字：C1=00，C2=01，C3=10，C4=11，C4的个数用来表示该符号的序数超过3的次数。符号编码：C1，C2，C3，C4C1，C4C2，C4C3，C4C4C1，C4C4C2，C4C4C3，这种编码方法更简单。几种编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.0
17、60.04L几种编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14L几种编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14B1码C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14L几种编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼码10001101
18、0001010010112.20.9750.0251.362.14B1码C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14S2码0001101100110111102.40.8950.1151.252.14L几种编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14B1码C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14S2码0001101100110111102.40.8950.1151.252.14自然
19、码00000101001110010130.7130.40212.14L限失真编码 严格的无失真编码的压缩比一般是不大的。编码效率的提高往往要以采用较复杂的编码方法为代价；另一方面，用户通常允许图象有一定的失真，这为图象数据压缩提供了较大的可能性，因此人们非常注意限失真编码问题。在给定失真条件下，信源编码所能达到的压缩率的极限码率，称为，D为失真上限。限失真编码 ，收到的信号序列不存在相关性时，等号成立。D，R(D)。允许失真度D越小，则所需率失真函数值R(D)就越大，要求信源编码效率也越高。p.436图象编码模型映射变换器量化器编码器原始图象码字图象编码模型 将输入数据从象素域变换到另一个域
20、，在变换域中则能以较少的比特数对图象进行量化编码。对映射变换器的要求，要从数据压缩的有效性、保真度和经济实用方面考虑，应该是i.高度去相关的、ii.可逆的、iii.重现的均方误差最小、iv.易于实现的。图象编码模型 把沿着扫描行的象素序列x1,x2,xN映射为行程序列(g1,l1),(g2,l2),(gk,lk)。gi灰度级 ligi的行程长度 因为象素序列可以根据行程序列来重建，故行程映射变换是可逆的。因它包含灰度鉴别和行程计数，故它是非线性的。图象编码模型 矩阵形式：nnxxxxyyyy3213211100011000110001图象编码模型 或 矩阵A是非奇异的，因而这种映射变换是可逆的。是一种最简单的线性预测编码。AXY 图象编码模型 各种正交变换都是可逆的线性变换。应用正交变换的图象编码常称为。正交变换有傅立叶变换(FFT)、余弦变换(DCT)、沃尔什-哈达玛变换(WHT)、小波变换(DWT)等。
