第4章图像压缩编码

1第五章图像压缩编码§1概述§2熵编码方法§3预测法编码§4变换编码方法§5二值图像编码§6图像压缩编码主要国际标准2§1概述图像压缩编码问题的提出在图像数字化中，若对图像的取样值以最基本和最简单的PCM编码（pulsecodingmodulation脉冲编码调制），这样获得的图像数据量（比特数）将非常具大。减少量化级数即编码比特数b，势必又引起量化信噪比大大下降(/)qSN31.几种图像的数据量：计算机图像处理中的数字图像其灰度多数用8bit来度量，一幅最简单的黑白照片,若按512×512点阵取样,表示这幅图像的二进制数据量:512×512×8=2048Kbit=2Mbit=256KB而医学图像处理和其他科研应用的图像的灰度量化可用到12bit以上，因而所需数据量太大。1024×1024×12=12Mbit遥感图像如SAR图像用8bit量化，100公里X100公里，10m分辨率的图像的大小为10000X10000。这样一个地区的图像需108B以上。这无疑对图象的存储、处理、传送带来很大的困难。42.图像压缩的主要目的：传输与存储从传送图像的角度来看:某些图像采集有时间性；图像存储体的存储时间也有限制。它取决于存储器件的最短存取时间，若单位时间内大量图像数据来不及存储，就会丢失信息。从图像存储的角度：通过压缩可以减少存储设备的用量，产生经济效益。5图像中像素之间，行或帧之间都存在着较强的相关性3.图像数据压缩的可能性：从统计观点出发，简单直观地讲，就是某个像素的灰度值，总是和其周围的其他像素灰度值某种关系，应用某种编码方法提供并减少这些相关特性，使可实现图像信息的数据压缩。从信息论观点出发，就是减少图像信息中无用的冗余信息，仍然保留有效信息，这样既减少了描述信息的数据量，又保证图像有效信息没有丢失，实现所谓信息保持编码。从另一种角度出发，图像信息的信宿往往是人眼，而人的视觉系统接受信息的能力是有限的，如灰度和空间分辨率都不能太高。即使是纪录或显示设备，也往往受本身特性的限制，只能接受某种程度量的信息，而并不能全部接受，如电视监视器其灰度特性、空间分辨率都是很有限的。64.数字图像数据压缩按应用不同可分为三类：（1）信息保持编码（无误差编码）它要求压缩图像的比特数而不丢失任何信息。主要用在图像信息保存中，要求图象存储能保持信息并能快速存取图象。例如短时随机存取主要用于处理过程中的各个环节的存储，它要求经过不同存储介质多次重复不变质、不失真。（2）保真度编码（非信息保持编码）传送图像应能适应通信的通道限制，若接收端是人观看的情况，由于人眼的生理特性不需过高的空间分辨率和灰度分辨率，因此在压缩过程中允许丢失一些人感觉不到的信息，这就是一种允许微量失真的图像压缩，数字电视、图像传输和多媒体中常用这种压缩。（3）特征抽取（保持）编码许多图像处理的目的是为了计算机的识别、分析、控制，这时并不需要图像的全部细节及灰度细节。只要能保存图像中的感兴趣的特征信息，无用信息都可丢掉。7§2熵编码方法MkkkPPH12log特例：肯定发生的事：H＝0一.基本概念1.图像熵假定图像中的各像素间取何种灰度级是相互独立的，称为无记忆信息熵值或0阶熵，记为：。设数字图像像素灰度级集合为（W1，W2，…，WM），其对应的概率分别（P1，P2，…，PM），按信息论中信源信息熵定义，数字图像的熵H为：)(0H82.平均码字长度给（W1，W2，…，WM）每个灰度级赋予一个编码Ck，称为码字,其中k=1,2,…,M(二进制)，。设为数字图像第k个码字Ck的长度（二进制代码的位数）。其相应出现的概率为Pk，则数字图像所赋予的码字平均长度R为：kMkkkbitpR1)(93.编码效率：式中H为信源熵，R为平均码字长度根据信息论信源编码理论，可以证明：HR总可以设计出某种无失真编码方法HR表明这种方法效率很低，占用比特数太多HR为最佳编码HR丢失信息图像失真(%)RH10在变长编码中，对出现概率大的信息符号赋予短码字，而对于出现概率小的信息符号赋予长码字，如果码字长度严格按照所对应符号出现概率大小逆序排列，则编码结果平均码字长度一定小于任何其他排列方式。定理内容：4.变长最佳编码定理11设：可变长度编码所用码元进制为D（一般为2），被编码的信息符号总数为N，第i个符号出现的概率为，与其对应的码字长度为ipit5.可变长度最佳编码的平均码字长度1loglogDHRDHBB121loglogloglogDPtDPBiBiBiB由此可以引导出对某一个信息符号存在下式1loglog22iiiPtP对二进制码进一步简化为：可见码字长度是由信息符号出现的概率来决定的。这就是下面要介绍的香农编码方法理论基础13（a）续长代码和非续长代码非续长代码：不能在某一代码后面添加一些码元而构成另一个码字。例如：[0，10，11]是非续长代码；[0，01，11]是续长代码。6.唯一可译编码为了减少表示图像的平均码字长度，对码字之间往往不加同步码，这样就要求所编码字序列能被唯一译出来。满足这个条件的编码称为唯一可译编码，或单义可译码。（b）单义代码任意有限长的码字序列，只能被唯一地分割成一个个码字。单义代码的充要条件是满足克劳夫特（kraft）不等式：11nitiD14例如：15二.哈夫曼（Huffman）编码方法（紧凑码）哈夫曼编码的一般算法如下：（1）（2）把最小的两个概率相加合并成新的概率，与剩余的概率组成新的概率集合。（3）对新的概率集合重新排序，再次把其中最小的两个概率相加，组成新的概率集合。如此重复进行，直到最后两个概率的和为1（4）分配码字。码字分配从最后一步开始反向进行，对于每次相加的两个概率，给大的赋“0”，小的赋“1”（也相反，如两个概率相等，则从中任选一个赋“0”），读出时由该符号开始一直走到最后的概率和“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该16例一：17编码效率计算：%7.9761.255.2RH18仔细看一下编码过程：1S00.400.180.100.100.070.060.050.040.090.130.190.230.370.601.00011111100000010010110000010001010001000011码字信源符号出现概率S1S2S3S4S5S6S719例二：001100100001110010.050.10.150.20.250.255P6P4P3P2P1P20对不同概率分布的信源，哈夫曼编码的编码效率有所差别。根据信息论中信源编码理论，对于二进制编码，当信源概率为2的负幂次方时，哈夫曼编码的编码效率可达100%，其平均码字长度也很短，而当信源概率为均匀分布时，其编码效果明显降低。在信源概率接近于均匀分布时，一般不使用哈夫曼编码。结论：21香农-范诺（Shannon-Fannon）编码也是一种常见的可变字长编码。与哈夫曼编码相似，当信源符号出现的概率正好为2-i（i0）时，采用香农-范诺编码同样能够达到100%的编码效率。香农-范诺编码的理论基础是符号的码字长度ti完全由该符号出现的概率来决定，即：三.香农-范诺（Shannon-Fannon）编码1loglog22iiiPtP22（1）输入灰度级按出现的概率从大到小排列；（2）计算码字长度；（3）计算累加概率；（4）十进制转换为二进制；（5）去掉多余尾数。编码步骤:23编码效率计算：1loglog22iiiPtP根据：24算术编码是一种从整个符号序列出发，采用递推形式连续编码的方法。它将一个符号序列映射为一个实数。算术编码中，单个源符号和码字间的一一对应关系并不存在。四.算术编码方法算术编码是60年代初期提出:在信源概率分布比较均匀情况下，它的编码效率高于哈夫曼编码。1.算术编码的方法如何给每个信源符号赋予非整数个比特？25[例5．2]已知信源，试对l011进行算术编码。（1）二进制信源符号只有两个“0”和“1”，设置小概率：Qc＝1／4大概率：Pc=1-Qc＝3／4。（2）设B为子区的左端起始位置，L为子区的长度(符号概率)符号“0”的子区为[0，l／4]；左端B＝0，长L＝1／4；符号“1”的子区为[1／4，1]；左端B＝1／4，长L＝3/4。解：26（4）初始子区为[0,1]，编码算法：步序符号子区左端子区长度a10+1／4*1=1/41*3／4=3/4b01/4+0*3/4=1/43/4*1/4=3/16c11/4+1/4*3/16=19/643/16*3/4=9/64d19/64+1/4*9/64=85/2569/64*3/4=27/256（3）在编码运算过程中，随着消息符号的出现，子区按下列规则缩小：规则A：新子区左端＝前子区左端十当前符号子区左端×前子区长度规则B：新子区长度＝前子区长度×当前符号子区的长度。27最后的子区左端(起始位置)：B＝(85／256)d＝(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。281个算术码字要赋给整个信源符号序列，而码字本身确定0和1之间的1个实数区间。随着符号序列中的符号数量增加，用来代表它的区间减小而用来表达区间所需的信息单位(如比特)的数量变大。每个符号序列中的符号根据区间的概率减少区间长度。与哈夫曼方法不同，这里不需要将每个信源符号转换为整数个码字(即1次编1个符号)，在理论上它可达到无失真编码定理给出的极限。解码过程是逆过程，首先将区间[0，1]按Qc靠近0侧，Pc靠近1侧分割成两个子区间，判断被解码字落在哪个子区，而赋予对应符号。注：29二值图像：只有两个灰度级的图像，即图像内容“非白即黑”。典型的有传真。二值图像直接编码：如每一个像素用一位二进制码(0或1)代表就称为编码。分辨率：单位长度的像素数。CCITT（国际电话电报咨询委员会）建议在传真中采用两种分辨率：1728像素／行(8取样／mm)，3．85行／mm；l728像素／行(8取样／mm)，7.7行／mm。一.概述§3二值图像编码30设Cr为采用某种方法编码前后的压缩比：取决于图像内容、分辨率、编码方法。二值图像编码压缩一般采用熵编码。31WBS编码：二.跳过白色块编码(WhiteBlockSkipping,WES)将图像的每条扫描线分成若干段，每段有N个像素。对全部是白色的像素用1bit“0”表示。对于至少有一个黑色像素的像素段采用N十1个比特编码．即第一个比特人为地规定为1．其余的N比特采用直接编码(白色为“0”．黑色为“1”码字)。1.一维WBS编码跳过白色区域，对黑色像素编码．这样表示这些图像的比特数将减少，每个像素平均比特数也就可以减少。32分成五段：段长N＝400000010000001000000编码0100100101000一维WBS编码平均码字长度为PN:段长为N的全白像素段出现的概率。b4＝1.25-P4。全白概率必须大于1／4才可能获得压缩效果。段长N不同，全白概率也不同。为了获得最小的平均码字长度，对给定的一幅二值图像应有一个最佳N值，不同图像的最佳段长N值不同。NNNNPNNPPNb11)]1)(1(1*[133一维WBS编码可以方便地推广到二维。一维的像素段二维中像素块假设像素块尺寸为M×N，全部为白色的像素块用“0”表示，非全白像素块用(M×N+1)个比特码表示。其中第一个比特为“1”。其余M×N个比特采用直接编码。00000000100001010000000001001000101010002.二维WBS编码34二值图像的自适应WBS编码：根据图像的局部结构或统计特性，改变其像素块尺寸大小、则WBS编码所用的比特数一定会更少。自适应增加了设备的复杂性。实