Chap图象压缩与编码实用PPT课件

1、图象压缩与编码图象压缩与编码 数字图象通常要求很大的比特数，这给图象的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。 如一幅512x512的黑白图象的比特数为 512x512x8=。 再如一部90分钟的彩色电影，每秒放映24帧。把它数字化，每帧512x512象素，每象素的 、 、 三分量分别占8 bit，总比特数为第1页/共64页图象压缩与编码图象压缩与编码 90 x60 x24x3x512x512x8bit=。 如一张CD光盘可存600兆字节数据，这部电影光图象（还有声音）就需要张CD光盘用来存储。 对图象数据进行压缩显得非常必要。 本章讨论的问题：在满足一定条件下，能否减小图

2、象bit数，以及用什么样的编码方法使之减少。第2页/共64页英文字母出现相对频率英文字母出现相对频率第3页/共64页英文字母出现相对频率英文字母出现相对频率第4页/共64页图象编码图象编码密码密码第5页/共64页图象编码图象编码密码密码第6页/共64页图象压缩与编码图象压缩与编码1图象数据压缩是可能的：一般原始图象中存在很大的冗余度。用户通常允许图象失真。当信道的分辨率不及原始图象的分辨率时，降低输入的原始图象的分辨率对输出图象分辨率影响不大。用户对原始图象的信号不全都感兴趣，可用特征提取和图象识别的方法，丢掉大量无用的信息。提取有用的信息，使必须传输和存储的图象数据大大减少。 第7页/共64

3、页图象压缩与编码图象压缩与编码2原始图象越有规则，各象素之间的相关性越强，它可能压缩的数据就越多。 值得指出的是：当前采用的编码方法得到的结果，离可能压缩的极限还相差很远，这说明图象数据压缩的潜力是很大的，直到目前为止，它还是个正在继续研究的领域。第8页/共64页图象压缩与编码图象压缩与编码3图象结构的性质，大体上可分为两大类，一类是具有一定图形特征的结构，另一类是具有一定概率统计特性的结构。 基于不同的图象结构特性，应采用不同的压缩编码方法。第9页/共64页图象压缩与编码图象压缩与编码4全面评价一种编码方法的优劣，除了看它的、和以外，还要看它的，是否。 常采用混合编码的方案，以求在性能和经济

4、上取得折衷。 随着计算方法及VLSI的发展，使许多高效而又比较复杂的编码方法在工程上有实现的可能。第10页/共64页信源编码的基本概念信源编码的基本概念 图象数据压缩的是在满足一定图象质量条件下，用尽可能少的比特数来表示原始图象，以提高图象传输的效率和减少图象存储的容量，在信息论中称为。 信源编码可分为两大类，一类是，另一类是或称。第11页/共64页无失真编码无失真编码又称或。 从N个相等可能发生的事件中，选出其中一个事件所需的信息度量，称为。第12页/共64页 无失真编码无失真编码要辨识1到32中选定的某一个数，可先提问：“是否大于16？”，得到回答就消去半数可能事件。每提问一次得到回答，可

5、以得到1bit信息量（二进制位）。这里共需5次，因此所需的信息量为 。532log2第13页/共64页无失真编码无失真编码从N个数选定一个数s的概率为p(s)，且等概率，p(s)=1/N。设信源符号表为 s=s1, s2, , sq，其概率分布为P(s)=p(s1), p(s2), , p(sq)，则信源的为)()(log1loglog)(222spIspNNsIqiiiqiiispIspspspH112)()()(log)()(s第14页/共64页无失真编码无失真编码 s作为灰度，共q级，出现概率均等时，p(si)=1/q， 当灰度只有两级时，即si = 0, 1，且0出现概率为p1，1出现

6、概率为p2=1- p1 ，其熵qqqHqi212log1log1)(s12112111log)1 (1log)(ppppHs第15页/共64页无失真编码无失真编码 当p1=1/2， p2=1- p1 =1/2时， H(s)=1为最大值。如图所示。第16页/共64页无失真编码无失真编码（1）熵是一个非负数，即总有H(s)0。（2）当其中一个符号sj的出现概率p(sj)=1时，其余符号si(ij)的出现概率p(si) =0，H(s)=0。（3）当各个si出现的概率相同时，则最大平均信息量为log2 q。（4）熵值总有H(s) log2 q。第17页/共64页无失真编码无失真编码(一) 可以证明，在

7、无干扰的条件下，存在一种无失真的编码方法，使编码的平均长度 L与信源的熵H(s)任意地接近，即L=H(s)+，其中为任意小的正数，但以H(s)为其下限，即LH(s)，这就是。L)(sHL)(sHL第18页/共64页无失真编码无失真编码(二) 对于无失真图象的编码，原始图象数据的压缩存在一个下限，即平均码组长度不能小于原始图象的熵，而理论上的最佳编码的平均码长无限接近原始图象的熵。 原始图象定义为：1)(1sHLr原始图象的熵原始图象平均码长第19页/共64页无失真编码无失真编码 将定义为：rLsH11)( 冗余度接近于0，或编码效率接近于1的编码称为。第20页/共64页无失真编码无失真编码 若

8、原始图象的平均比特率为n，编码后的平均比特率为nd，则C定义为：dnnC 由Shannon定理，无失真编码为：)()(sHnsHnCM第21页/共64页无失真编码无失真编码 令q=2L，其中L等于自然二进制码的长度。可以证明，对于独立信源，等概率分布时，具有最大熵HM(s)=L比特，因而冗余度r=L/HM(s)-1=0，不可能压缩。（1），又称，符号si 的出现，与其他的符号无关。qiiispspH12)(log)()(s第22页/共64页无失真编码无失真编码 非等概率分布时的熵，一般有H1(s) 0，还有可能压缩。（2） 又称，它的统计特性要用或来描述。 m阶Markov信源，是指某个符号s

9、i出现的概率只与前面m个符号有关。第23页/共64页无失真编码无失真编码 设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) 第24页/共64页无失真编码无失真编码 对符号表取平均的信息量 ),(),(log),(),(),(),(211212211212121miiiqimiiiimiiiiqimiiimiiimiiisssHsssspsssspsssIssspsssIssss 这是在给定序列si1

10、, si2, sim的条件下，信源的条件熵。 第25页/共64页无失真编码无失真编码 再考虑序列si1, si2, sim发生的概率， 可将定义为：),(log),(),(log),(),(),(),()(212112111212211121111212111121212miiiiqiqiimiiiqiqimiiiimiiiiqiqimiiiqiqiqimiiimiiiqiqisssspsssspsssspsssspssspsssHssspHmmmss第26页/共64页无失真编码无失真编码 （四） 无干扰编码定理只指出存在一种无失真的编码，可使 。它并没有指出具体的编码方法。下面介绍几种具体的

11、编码方法。（1） 它是长度不均匀的，其平均长度最短的即时可译码。其是对经常出现的符)(sHL第27页/共64页英文字母出现相对频率英文字母出现相对频率第28页/共64页英文字母出现相对频率英文字母出现相对频率第29页/共64页国际莫尔斯电码符号国际莫尔斯电码符号第30页/共64页无失真编码无失真编码号赋予最短的码字，然后按出现概率减少的次序，逐个赋予较长的码字，这样可使码的平均长度qiiilpL1具有最小值，pi-si出现概率，li-对si编码的长度。第31页/共64页无失真编码无失真编码 i.将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。第32页/共64页

12、无失真编码无失真编码ii.把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。 iii.重复上述做法，直到最后剩下两个概率为止。iv.从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个二进制码，如对概率大的赋予码元0，对概率小的赋予码元1。第33页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第34页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第35页/共64页Huf

13、fman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第36页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第37页/共64页Huffman编码编码输入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.4第38页/共

14、64页Huffman编码编码输入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.40101010101第39页/共64页Huffman编码编码输入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.40101010101S1=1第40页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04

15、第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00第41页/共64页Huffman编码编码输入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=011第42页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3

16、第四步0.60.40101010101S4=0100第43页/共64页Huffman编码编码输入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=01010第44页/共64页Huffman编码编码输入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第45页/共64页无失真编码

17、无失真编码（2） 在某些应用中，编码器输入符号集合的概率分布服从乘幂律：pk=k-r, k=1,2,q。r为正常数，则用B码，它接近于最佳编码。B码是一种非等长码，由两部分组成，一部分叫“”，一部分叫“”。延续比特的作用是标注一个码字究竟延续多长，信息比特的作用是表示不同的信息符号。第46页/共64页无失真编码无失真编码 将信源符号按出现概率从大到小排序，然后按B1码的前后顺序分别赋予相应符号，便得到各符号的B1码。其中信息码是按二进制的长度及数的顺序排列的，即0，1，00，01，10，11，000，001，。延续码C是在编码过程中确定的，可将C=0赋予前一个码字，将C=1赋予后一个码字，再将

18、C=0赋予下一个码字。第47页/共64页无失真编码无失真编码 例如，编码器输入符号序列为s4s1s5s2, 则B1码为： 0 1， 0， 1 0， 1 ，或者 0 1 ， 0， 1 0， 1， 延续码改变，表示前一个码字结束，后一个码字开始。 编码方法简单，容易实现。第48页/共64页无失真编码无失真编码（3） 对具有单调减小概率的输入信号相当有效的非等长码。 S2码由2bit长的码字组成，总共包含四个不同的码字：C1=00，C2=01，C3=10，C4=11， C4的个数用来表示该符号的序数超过3的次数。符号编码：C1，C2，C3，C4C1，C4C2，C4C3，C4C4C1，C4C4C2，C

19、4C4C3， 这种编码方法更简单。第49页/共64页几种几种编码比较编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04L第50页/共64页几种几种编码比较编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14L第51页/共64页几种几种编码比较编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.1

20、4B1码C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14L第52页/共64页几种几种编码比较编码比较输入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.14L第53页/共64页几种几种编码比较编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.06

21、0.04霍夫曼码100011010001010010112.20.9750.0251.362.14B1码C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14S2码0001101100110111102.40.8950.1151.252.14自然码00000101001110010130.7130.40212.14L第54页/共64页限失真编码限失真编码 严格的无失真编码的压缩比一般是不大的。编码效率的提高往往要以采用较复杂的编码方法为代价；另一方面，用户通常允许图象有一定的失真，这为图象数据压缩提供了较大的可能性，因此人们非常注意限失真编码问题。 在给定失真条件下，信源编码所能达到的压缩率的极限码率，称为， ，