冈萨雷斯版_图像压缩

图像压缩北京理工大学光电学院王岭雪•BMP格式•203KB(560*368)•JPEG格式•23.5K图像压缩imagecompression图像大小：576*720持续时间：15秒文件大小：1.4M字节无压缩时：576*720*2*25*15≈300M字节三种数据冗余1.编码冗余2.空间和时间冗余3.不相关的信息（心理视觉冗余）编码冗余•编码冗余-不考虑灰度级出现的次数，给每个灰度级都采用相同位(比特)数的存储空间所带来的数据冗余。如：8位BMP灰度图像→8位-解决办法：变长编码，出现概率大的灰度级→尽量少的位数。•计算Code2的平均码长Lavg压缩率CR•冗余度RD定义为压缩率CR=源代码长度压缩后代码长度RDCR11空间和时间冗余•变长编码减少对像素进行统一长度的编码(自然二进制编码)带来的编码冗余，但没有考虑到像素之间的相关性空间和时间冗余：空间冗余、帧间冗余、几何冗余行程编码传真图像的行程编码举例心理视觉冗余•对视觉处理过程不重要的信息，如人眼无法区分的高频信息•在不影响视觉感知的前提下，除去人眼无法区分的高频信息，适当减少灰度级(量化)IGS编码1)用当前的8位灰度级值加上前面和的灰度级值低4位，并将4个最高有效位作为IGS的编码值；2)如果当前值的4位最高有效位为1111，则用0000与之相加。保真度准则1)客观评价：原图像定义为f(x,y)，压缩图像为，均方根误差erms为圴方信噪比1010210102ms)],(),(ˆ[)],(ˆ[SNRMxNyMxNyyxfyxfyxf),(ˆyxf2)主观评价2110102rms)],(),(ˆ[1MxNyyxfyxfMNe电视图像的等级量表图像压缩系统的模型1.图像f(x,y)输入到编码器(Encoder)中，编码器可以根据输入数据生成一组符号2.通过信道(Channel)进行传输3.编码后的表达符号送入解码器(Decoder)，经过重构就生成了输出图像),(ˆyxf•某个事件x的信息量I用事件发生概率p(x)的倒数的对数表示中国举重队夺得奥运冠军！中国男子足球队勇夺奥运冠军！！！信息量与熵(Entropy))(log)(1log)(xpxpxI•能够产生信息的事物称为信源•若信源X产生的信息是x1,…xn,出现概率分别为p1,…pn,信源X的平均信息量为iniiiniippxIpXHlog)()(00信源X的熵•对数以2底时，信息量表示记录信息所用的最小位数•设一图像的灰度级集合为(W1,W2,…,WM)，出现概率分别为p1,p2…pM，图像熵定义为MkkkppH12log•描述：1)熵总是非负的2)当所有像素出现的概率相等时，熵取到最大3)对数以2底，熵的单位是：位/像素•物理意义：表示对各灰度级编码时的所需位数的统计平均值图像熵平均码字长度•设k为数字图像第k个码字Ck的长度(二进制代码的位数)，该码字的出现概率为pk，则平均码字长度R定义为bit1MkkkpR•最佳编码的定义：使平均码字长度尽量接近图像熵，既不丢失信息，又占用最小的位数压缩率CR•冗余度RD定义为压缩率CR=源代码长度压缩后代码长度RDCR11编码效率•H为熵，l为平均码长•如果编码效率≠100%，说明有冗余度%100lH42.205.0log05.010.0log10.015.0log15.020.0log20.025.0log25.025.0log25.0log)(222222612kkkppXH例子•一个信源X的霍夫曼编码表为右表，计算其信源的熵、平均码长、编码效率：码字信息概率01u10.2510u20.2511u30.20000u40.150010u50.100011u60.05熵平均码长45.210.0415.0320.0225.0225.02)(61kkkpXR编码效率%8.98%10045.242.2%100)()(XRXH计算图像的熵(P348例8.10)•一阶估计的信源熵→灰度级•二阶估计的信源熵→灰度级对数据压缩的分类•按数学理论和计算方法分类：统计编码(StatisticalCoding)、预测编码(PredictiveCoding)、变换编码(TransformCoding)•按压缩过程的可逆性分类：1)无误差压缩：去除原数据中的重复和冗余部分，不丢失任何有用信息还原后与压缩前的原数据完全一致，又称无失真编码主要用于文本、程序文件，不允许出现任何数据失真2)有误差压缩：不可逆，损失部分信息，又称率失真编码或限失真编码丢弃信息造成的失真应限制在规定范围内主要用于图像和语音数据的压缩无误差压缩之一：变长编码•码字长度是变化的、不均匀的•出现概率较大的信源符号→较短的字长•出现概率小的信源符号→较长的字长霍夫曼(Huffman)编码•Huffman编码完全依据信源字符出现的概率进行编码•Huffman编码有时也称为最佳编码Huffman编码用不同码字代表不同灰度，并非量化灰度值首先，将信源符号按出现频率由大到小排列符号a2a6a1a4a3a5出现概率0.40.30.10.10.060.04将最小的两个概率组合相加，并继续该步骤，直到概率为1第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率0.40.30.10.10.060.04第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率0.40.30.10.10.060.04第二步0.40.30.20.1•在相加的过程中，始终将较高的概率分支放在上部第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率0.40.30.10.10.060.04第二步0.40.30.20.1第三步0.40.30.3第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率0.40.30.10.10.060.04第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4第五步1.00第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率0.40.30.10.10.060.04第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4第五步1.0001每对组合的上边指定为0，下边指定为101010101第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率0.40.30.10.10.060.04第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4第五步1.000101010101画出每个信源符号到达概率1.00处的路径，记下遇到的各个1和0a2=1第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率0.40.30.10.10.060.04第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4第五步1.000101010101a6=00第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率0.40.30.10.10.060.04第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4第五步1.000101010101a2=1a6=00a1=011a4=0100a3=01010a5=010111)计算平均码长和编码效率2)对字符串010100111100进行解码Huffman编码是可唯一解码的算术编码(ArithmeticsEncoding,AE)•用一个算术码字来代替一个符号序列1)算术编码没有延用一般数据编码技术中用一个特定的码字代替一个输入符号的做法2)将要压缩的整段数据映射到实数半开区间[0,1)3)构成大于等于0且小于1的数值4)这些数值作为唯一可译代码5)源符号和码字间的一一对应关系并不存在，而是用一个算术码字来代替一个符号序列算法模型•设信源数据流为“XY︺YZ”，出现概率和设定的取值范围为字符空格XYZ概率0.20.20.40.2赋值范围[0.0,0.2][0.2,0.4][0.4,0.8][0.8,1.0)•以上赋值范围按出现次序划分，将符号划分到哪个区间，对编码并无影响。•如果信源数据流的第一个字符为X，已知其取值范围为0.2～0.4，这确定了代码最高有效位取值的范围•后续每读入一个新符号，输出代码的数值范围将进一步缩小•前一个字符编码的上、下限记为HIGH和LOW，RANGE表示HIGH与LOW之差，则新输入符号的上、下限计算公式：HIGH=LOW+RANGE×HIGH_RANCE(CHAR)LOW=LOW+RANGE×LOW_RANCE(CHAR)新输入符号当前的上、下限前一个符号的下限前一个符号上下限之差•对于数据流“XY︺YZ”HIGH=LOW+RANGE×HIGH_RANCE(CHAR)LOW=LOW+RANGE×LOW_RANCE(CHAR)输入字符X[0.2,0.4]Y[0.4,0.8]空格[0.0,0.2]Z[0.8,1.0)LOW0.20.280.280.29152RANGE0.20.080.016HIGH0.40.360.2960.2928Y[0.4,0.8]0.28640.00640.2928•随着字符的输入，代码的取值范围越来越小•当“XY︺YZ”被全部编码后，其范围[0.29152,0.2928]很小•取该范围的下限0.29152作为输出代码•用一个浮点数表示一个字符串，从而减少存储空间的占用。习题(416)•第8.1、8.3、8.13(a)、8.13(b)、8.14题