第六章图像编码技术()

第六章图像编码技术6.1引言

图像编码又称为图像压缩。（在信息论中，数据压缩又称为信源编码）。

图像编解码系统模型 通过信道连接的两个结构模块图像压缩

1.必要性：对于电视画面的分辨率640*480的彩色图像(RGB)，假设每秒30帧，则一秒钟的数据量为:640*480*3*30=27M100M仅能存储100/27=3.7秒。若视频为DVD格式2小时的电影需要200张碟片。

2.图像存在着数据冗余（可行性）（rong）数据冗余是指那些代表了无用信息，或是重复的表示了其他数据已表示信息的数据。P146

３.

数据冗余分为几种冗余

像素冗余、编码冗余、视觉心理冗余像素冗余：

由于任何给定的像素值，原理上都可以通过它的相邻像素预测到。对于一个图像，很多单个像素对视觉的贡献是冗余的。例：原图像数据：234223231238235

压缩后数据：23411-8-73，我们可以对一些接近于零的像素不进行存储，从而减小了数据量。编码冗余：如果一个图像的灰度级编码，使用了多于实际需要的编码符号，就称该图像包含了编码冗余.例：如果用8位表示下面图像的像素，我们就说该图像存在着编码冗余，因为该图像的像素只有两个灰度，用一位即可表示。一些信息在一般视觉处理中比其它信息的相对重要程度要小，这种信息就被称为视觉心理冗余。33K15K6.2保真度准则——评价压缩算法的准则

P150

保真度准则：图像压缩经过解压缩后并不能令图像完全恢复原状。因此需要度量以描述解压缩图像相对原始图像的偏离程度。这一测度称为保真度准则。常有准则可分为：客观保真度准则、主观保真度准则。1.最常用的客观保真度准则是原图像和解码图像之间的均方根误差和均方根信噪比两种。令f(x,y)代表原图像，代表对f(x,y)先压缩又解压缩后得到的f(x,y)的近似，对任意x和y，f(x,y)和之间的误差定义为：),(ˆyxf),(ˆyxf均方根（erms）误差点误差图误差均方根信噪比将归一化信噪比并用分贝（dB）表示.令则有峰值信噪比（PSNR）2.主观保真度准则 观察者对图像综合评价的平均

P151例6.2.1电视图像质量评价6.3基础理论信息量 概率为P(E)的随机事件E的信息量I(E)称为E的自信息（随概率增加而减少） 特例：P(E)=1（即事件总发生），那么I(E)=0信息的单位：比特（log以2为底）

产生单个信源符号的自信息：I(aj)=–logP(aj)信源平均信息（又称为熵）：输入字符串:aabbaccbaa

a、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位熵?如果某种编码方法产生的平均码长等于信息源的熵，那么它就没有任何冗余信息，达到了编码的最优状态。信源字母集概率码A码B码C码Da1a2a3a40.50.250.1250.1250111100100110101101111010110111前缀编码最需考虑的问题是，如果a1用0表示，而对a3用00表示，那么，在解码时，面对0011的二进制流，我怎么知道是解码为a1a1a2a2，或a1a1a4，还是a3a4？所以，必须设计出一种编码方式，使得解码程序可以方便地分离每个字符的编码部分。于是有了一种叫“前缀编码”的技术。该技术的主导思想是，任何一个字符的编码，都不是另一个字符编码的前缀。蓝色编码就是前缀编码一个最简单的例子。如何判断是不是前缀编码下述那一个不是前缀编码？

A(00,01,10,11)

B(0,1,,00,11)

C(0,10,110,111)

D(1,01,000,001)

2.不是前缀编码的是：

A(0,10,110,1111)

B(11,10,001,101,0001)

C(00,010,0110,1000)

D(b,c,aa,ac,aba,abb,abc)

前缀编码就是任一字符的编码不能是另一字符编码的前缀

再通俗点，

1题，B选项：0是00的前缀，1是11的前缀

2题，B选项：10是101的前缀。等长编码哈夫曼编码均为前缀编码整体的大部分字符是由较短的编码从而保证文件出现频率高低的顺序分别赋以由短到长的代码，先统计数据中各字符出现的概率，再按字符所构成。哈夫曼编码(Huffman)：1952年问世，依据变字长编码理论基本思想：P154哈夫曼编码(Huffman)

将信源符号按概率递减顺序排列(排序)

；

把两个最小的概率加起来，作为新符号的概率(合并)

；

重复

和

，直到概率和达到1为止(重复)

；

完成上述步骤后，再沿路径返回进行编码。每层有两个分支，分别赋予0和1（对概率大的赋予编码0，概率小的赋予编码1，反之亦可，但同一过程中赋值的方法必须一致）(赋值)

；

对每一符号写出从码树的根到终节点1、0序列(编码)

。步骤：P155设某信源有5种符号x={A1，A2，A3，A4，A5}。在数据中出现的概率p={0.25，0.22，0.20，0.18，0.15}，试给出Huffman编码方案，写出每个符号对应的Huffman编码。答案1：A1:10A2:01A3:00A4:111A5:110答案2：A1:01A2:10A3:11A4:000A5:001哈夫曼的编法并不惟一（1）P156例6.4.1例：单符号离散无记忆信源，用两种不同的方法对其编二进制哈夫曼码。方法一：合并后的新符号排在其它相同概率符号的后面。哈夫曼的编法并不惟一（2）

Wi改错这两种编码哪一种更好呢，我们来计算一下二者的码长。方法二：合并后的新符号排在其它相同概率符号的前面。两种编码的平均码长是一样的，都是2.2，那一种更好呢，我们可以计算一下平均码长的方差。定义码字长度的方差σ2：可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有两种不同的码长；显然，第二种编码方法更简单、更容易实现，所以更好。结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。符号S1S2S3S4出现概率1/21/41/81/8H(X)=1.75L1=2L2=1.75源S1S2S1S3S2S1S1S4等0001001001000011霍01001101000111等长编码00011011霍夫曼010110111输入数据流:S1S2S1S3S2S1S1S4香农－范诺编码(Shannon-Fano

)香农－范诺编码与Huffman编码相反，采用从上到下的方法。具体步骤为：（1）首先将编码字符集中的字符按照出现频度和概率进行排序。（2）用递归的方法分成两部分，使两个部分的概率和接近于相等。直至不可再分，即每一个叶子对应一个字符。（3）编码。香农－范诺编码举例s00.40s1s2s3s4s5s60.180.100.100.07s70.060.050.04s0,s1,s2,s3,s4,s5,s6,s7s2,s3,s4,s5,s6,s7s0,s10.580.42s2,s3s4,s5,s6,s7s0s1s4,s5s6,s7s2s3s4s5s6s70.200.220.130.0901010101010101S0:00S1:01S2:100S3:101S4:1100S5:1101S6:1110S7:1111例：对下面这串出现了五种字符的信息(40个字符长):cabcedeacacdeddaaabaababaaabbacdebaceada五种字符的出现次数分别：a-16，b-7，c-6，d-6，e-51)将给定符号按照其频率从大到小排序。对上面的例子，应该得到：

a-16

b-7

c-6

d-6

e-5

2)将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和。我们有：

a-16

b-7-----------------

c-6

d-6

e-5

3)我们把第二步中划分出的上部作为二叉树的左子树，记0，下部作为二叉树的右子树，记1。4)分别对左右子树重复23两步，直到所有的符号都成为二叉树的树叶为止。现在我们有如下的二叉树：根(root)

0|1

+------+------+

0|10|1

+-----+-----++---+----+

||||

abc|

0|1

+-----+-----+

||

de

于是我们得到了此信息的编码表：

a-00b-01c-10d-110e-111

码长共91位。考虑用ASCII码表示40字符需要8*40=240位，我们确实实现了数据压缩。

Huffman编码Huffman编码构造二叉树的方法和Shannon-Fano正好相反，不是自上而下，而是从树叶到树根生成二叉树。1)将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点）。

a(16)b(7)c(6)d(6)e(5)2)在1中得到的树林里找出频率值最小的两棵树,将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值为两棵子树频率值之和。对上面的例子，我们得到一个新的树林：a(16)b(7)c(6)+---+---+(0)|(1)

||

de3)对上面得到的树林重复2的做法，直到所有符号都连入树中为止。这一步完成后，我们有这样的二叉树：由此，我们可以建立和Shannon-Fano编码略微不同的编码表：根(root)

0|1+------+----------+|0|1

|

+-------+------+|

0|10|1

a

+---+---+

+---+---+

bcdea-0b-100c-101d-110e-111

码长共88位。6.4算术编码P158产生

算术编码是60年代初期提出。在信源概率分布比较均匀情况下，它的编码效率高于哈夫曼编码

基本思想将要压缩的数据映射到[0,1)实数区间中的某一区段上的实数X，该实数的二进制展开式即为原符号串的压缩编码结果算术编码通过对当前的概率区间作迭代分割来确定实数。算术编码是具体构造出的用小数表示信息的方法，因为小数随位数的增加，它的精度也随之提高，从信息的角度来说，它所含有的信息量也随之增加6.4算术编码算术编码的特点①不必预先定义概率模型,自适应模式具有独特的优点;

②信源符号概率接近时,建议使用算术编码,这种情况下其效率高于Huffman编码;

③算术编码绕过了用一个特定的代码替代一个输入符号的想法,用一个浮点输出数值代替一个流的输入符号,较长的复杂的消息输出的数值中就需要更多的位数。④算术编码实现方法复杂一些,但JPEG成员对多幅图像的测试结果表明,算术编码比Huffman编码提高了5%左右的效率,因此在JPEG扩展系统中用算术编码取代Huffman编码。整数部分从低位至高位1,2,4,8,16,32......

小数部分从小数点位置开始：1/2,1/4,1/8,1/16....

即：1010.1011=>8+2+1/2+1/8+1/16（“^”代表幂）

1101.0111=>1*2^3+1*2^2+0*2^1+1*2^0+0*2^(-1)+1*2^(-2)+1*2^(-3)+1*2^(-4)十进制数化为二进制：，就拿小数部分*2，如7/16=0.43750.4375*2=0.875整数部分为0即当前二进制数值为：0.00.875*2=1.75整数部分为1即当前二进制数值为：0.011.75去掉1后继续运算。0.75*2=1.5整数部分为1即当前二进制数值为：0.0111.5去掉1后继续运算。0.5*2=1.0整数部分为1即当前二进制数值为：0.0111去掉1后为0，运算结束。0.4375的二进制数为：0.0111P158例题例方法如下：已知灰度级试对l011进行算术编码（1)二进制信源符号只有两个“0”和“1”，设置小概率：Qc＝1／4

大概率：Pc=1-Qc＝3／4（2）设C为子区的左端起始位置，L为子区的长度(符号概率)

“0”的子区为[0，l／4]，左端B＝0，长L＝1／4；

“1”的子区为[1／4，1]；左端B＝1／4，长L＝3/4（3)在编码运算过程中，随着消息符号的出现，子区按下列规则缩小：规则A：新子区左端＝前子区左端十当前子区左端×前子区长度规则B：新子区长度＝前子区长度×当前子区的长度（4）初始子区为[0.1]，编码过程序号符号子区左端子区长度11¼3/4201/4+0*3/4=1/43/4*1/4=3/16311/4+1/4*3/16=19/643/16*3/4=9/644119/64+1/4*9/64=85/2569/64*3/4=27/256最后的子区左端(起始位置)：

C＝(85／256)＝(0.01010101)b最后的子区长度：

L＝(27/256)d＝(0.00011011)b最后的子区右端(子区间尾)：

85/256+27/256＝(7／16)d＝(0.0111)b

编码结果为子区间头尾之间取值、其值为0.011,可编码为011，原来4个符号1011被压缩为三个符号011。图解算术编码与哈夫曼编码的比较P159特点算术编码更易于实现自适应。算术编码算法同符号概率统计是相互独立的，不像哈夫曼编码那样，符号概率统计的改变需要重新建立哈夫曼树，并改变码表算术编码的缺点是算术编码不是即时码，必须等到所有信息收到后才能解码唯一性：也称为单一性。指对任意一个有限长的码符号串，只有一种分解成其各个码符号的方法满足唯一性的码称为唯一可解码（uniquelydecodeablecode）哈夫曼、香农－法诺码和算术码都是cabcedeacacdeddaaabaababaaabbacdebaceada符号00011011概率0.10.40.20.310001100101101习题：哈夫曼编码、香农－法诺码算术编码变换编码基本思想：利用图像块内像素值之间的相关性，把图像变换到一组新的基上，使得能量集中到少数几个变换系数上，通过存储这些系数而达到压缩的目的；变换编码（TransformCoding）系统常用的变换：DFT，WHT，DCT

都是正交和可分离变换

集中能力：

DCT>DFT>WHT

所需计算量：

DCT>DFT>WHT

DCT是较好的（综合）选择DCT变换和逆变换：编码过程：编码过程：DCT变换原图像除以量化系数取整压缩图像DCT逆变换压缩图像乘以量化系数取整解压图像其中：例如，将原始图像进行离散余弦变换（DCT）后，有用的信息集中到左上方，进行量化就可以大大压缩数据量5255 6166 706164736359 6690 1098569726259 6811314410466736358 7112215410670696761 681041268868707965 6070 776858758571 6459 556165838779 6968 65767894610.0000-29.1054-61.941225.332154.7500-19.7158-0.59112.07866.0824-20.5871-61.63318.011011.5283-6.6413-6.42296.7781-46.09037.955376.7267-25.5941-29.655810.13886.3891-4.7739-48.914311.770334.3051-14.2332-9.86126.19131.33551.499910.7500-7.6338-12.4520-2.0442-0.50001.3659-4.58381.5185-9.64191.40703.4120-3.2940-0.47060.41521.8119-0.3939-2.8272-1.22851.38910.07630.9187-3.51501.7733-2.7744-1.2457-0.7072-0.4869-2.6945-0.0900-0.3958-0.91030.4051

610.0000-29.1054-61.941225.332154.7500-19.715802.07866.0824-20.5871-61.63318.011011.5283-6.6413-6.42296.7781-46.09037.955376.7267-25.5941-29.655810.13886.3891-4.7739-48.914311.770334.3051-14.2332-9.86126.19131.33551.499910.7500-7.6338-12.4520-2.044201.3659-4.58381.5185-9.64191.40703.4120-3.294000.41521.81190-2.8272-1.22851.389100-3.51501.7733-2.7744-1.245700-2.69450000610.0000-29.1054-61.941225.332154.7500-19.7158-0.59112.07866.0824-20.5871-61.63318.011011.5283-6.6413-6.42296.7781-46.09037.955376.7267-25.5941-29.655810.13886.3891-4.7739-48.914311.770334.3051-14.2332-9.86126.19131.33551.499910.7500-7.6338-12.4520-2.0442-0.50001.3659-4.58381.5185-9.64191.40703.4120-3.2940-0.47060.41521.8119-0.3939-2.8272-1.22851.38910.07630.9187-3.51501.7733-2.7744-1.2457-0.7072-0.4869-2.6945-0.0900-0.3958-0.91030.4051

52.173954.813661.138065.963369.978361.019663.830173.083362.806258.988565.892490.0329109.103185.124669.006072.046362.185359.031568.4767112.7817143.4403104.354765.869472.860362.839957.734670.7860122.0376154.6302105.729670.036869.205167.501460.820168.1434104.1236125.547288.228567.523670.112078.440265.207360.176069.732877.035068.228858.355874.824085.478370.636564.091059.042755.011560.928064.632683.179586.894678.995569.068767.965564.934476.158477.973394.0095a-round(idct2(b))0000000000000000000010000000-1000-10000000100000000000000000000000>>c=dct2(a)/3c=203.3333-9.7018-20.64718.444018.2500-6.5719-0.19700.69292.0275-6.8624-20.54442.67033.8428-2.2138-2.14102.2594-15.36342.651825.5756-8.5314-9.88533.37962.1297-1.5913-16.30483.923411.4350-4.7444-3.28712.06380.44520.50003.5833-2.5446-4.1507-0.6814-0.16670.4553-1.52790.5062-3.21400.46901.1373-1.0980-0.15690.13840.6040-0.1313-0.9424-0.40950.46300.02540.3062-1.17170.5911-0.9248-0.4152-0.2357-0.1623-0.8982-0.0300-0.1319-0.30340.1350d=203.3333-9.7018-20.64718.444018.2500-6.5719002.0275-6.8624-20.54442.67033.8428-2.2138-2.14102.2594-15.36342.651825.5756-8.5314-9.88533.37962.1297-1.5913-16.30483.923411.4350-4.7444-3.28712.0638003.5833-2.5446-4.150700000-3.214001.1373-1.0980000000000-1.17170000000000>>a-round(idct2(3*d))ans=00100-21010002110-1-1-10-21-2111101-11-1-20101-3201-2-1-1-12-21102-11000-11-100-210编码器：变换编码首先要将图像分成若干个（(N/n)2个）n×n的子图像后，再分别进行变换和编码，这是因为小块便于处理，而且小块内的像素相关性较大，存在的冗余度大解码器：由于量化是不可逆的，所以缺少量化器正交变换量化器符号编码器分割图像输入图像压缩图像符号解码器逆变换合成子图像压缩图像解压图像子图尺寸的选择要遵循的原则：如果n是子图的维数，n应该是2的整数次方。为便于降低计算复杂度。n一般选为8×8或16×16。由实践得到随着n的增加，块效应相应减少DCT变换编码原图解压图图像压