图像编码与压缩课件

数字图像处理数字图像处理Digital Image Processing河北大学数学与计算机学院河北大学数学与计算机学院马颍丽马颍丽Ma Yingli CMC HBU第五章第五章 图像编码与压缩图像编码与压缩n5.1 概述概述n5.2 统计编码统计编码n5.3 预测编码预测编码n5.4 变换编码变换编码n5.5 二值图像编码二值图像编码n5.6 新型的图像压缩编码方法新型的图像压缩编码方法n5.7 图像压缩编码标准图像压缩编码标准Ma Yingli CMC HBU知识要点n信息论中的有关概念信息论中的有关概念n信息，信息量，信息熵，冗余度信息，信息量，信息熵，冗余度n编码方法编码方法n统计编码统计编码n预测编码预测编码n变换编码变换编码n混合编码混合编码n静态图像压缩标准静态图像压缩标准nJPEG、JBIG、JPEG2000等等Ma Yingli CMC HBU5.1 概述概述n数据编码的目的各异数据编码的目的各异n信息保密信息保密n信息的压缩存储与传输等信息的压缩存储与传输等n数码相机数码相机图像编码与压缩技术成功的范例。图像编码与压缩技术成功的范例。n本章主要介绍静态图像压缩编码的原理、应本章主要介绍静态图像压缩编码的原理、应用及有关的国际标准。用及有关的国际标准。Ma Yingli CMC HBUMa Yingli CMC HBU5.1.1 数据压缩的基本概念数据压缩的基本概念n数据压缩数据压缩n以较少的数据量表示信源以原始形式所代表的信息以较少的数据量表示信源以原始形式所代表的信息n目的在于节省存储空间、传输时间、信号频带或发送目的在于节省存储空间、传输时间、信号频带或发送能量等。能量等。Ma Yingli CMC HBU信源编码的基本概念 图像数据压缩的目的是在满足一定图像质量条件下，用尽可能少的比特数来表示原始图像，以提高图像传输的效率和减少图像存储的容量，在信息论中称为信源编码。Ma Yingli CMC HBUMa Yingli CMC HBU图图5.1 数据压缩系统组成图数据压缩系统组成图 Ma Yingli CMC HBU数字通信系统模型数字通信系统模型信源信源信源编码信源编码信道编码信道编码调制调制传输信道传输信道噪声噪声解调解调信道解码信道解码信源解码信源解码信宿信宿Ma Yingli CMC HBU压缩压缩检、纠错检、纠错Ma Yingli CMC HBUu熵（熵（Entropy）n代表信源所含的平均信息量。代表信源所含的平均信息量。n若信源编码的熵大于信源的实际熵，则信源中的若信源编码的熵大于信源的实际熵，则信源中的数据一定存在冗余度。数据一定存在冗余度。n冗余数据的去除不会减少信息量。冗余数据的去除不会减少信息量。n信息量与数据量的关系可由下式表示信息量与数据量的关系可由下式表示 I I D D dudu （5.15.1）Ma Yingli CMC HBU5.1.2 图像编码压缩的必要性图像编码压缩的必要性n图像信号的数据量图像信号的数据量V(volume)（byte，B）:n V w h d/8 （5.2）nw、h、d 分别表示图像数据量分别表示图像数据量（字节，（字节，byte，B）、图像宽度图像宽度width（像素数，（像素数，pel）、图像高度、图像高度height（像（像素数，素数，pel）、图像深度、图像深度depth（位，（位，bit）。）。n图像的尺寸为：图像的尺寸为：wh。Ma Yingli CMC HBUMa Yingli CMC HBU典型图像的数据量典型图像的数据量 图像种类图像种类图像参数图像参数 数据量数据量 二值传真图像二值传真图像 A4（210 297 mm）大小、）大小、1728 2376 2色分辨率色分辨率501 KB 灰度图像灰度图像 512 512，8 bit灰度等级灰度等级 256 KB VGA图像图像 640 480 256色色 300 KB CIF视频图像视频图像 352 288 256色，亮度取样率为色，亮度取样率为3 MHz，亮度和两色差按，亮度和两色差按4 1 1取样，取样，亮色量化位数共亮色量化位数共12 bit，帧频，帧频29.97，按，按1 s计算计算 4.3 MB HDTV亮度信号亮度信号 1280 720，量化位数为，量化位数为8 bit，帧频，帧频30 Hz，按，按1 s计算计算 52.7MBMa Yingli CMC HBU5.1.3 图像编码压缩的可能性图像编码压缩的可能性一般图像中存在着以下数据冗余因素一般图像中存在着以下数据冗余因素:编码冗余编码冗余 像素间的相关性形成的冗余像素间的相关性形成的冗余 视觉特性和显示设备引起的冗余视觉特性和显示设备引起的冗余Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU5.1.4 图像编码压缩的技术指标图像编码压缩的技术指标常用的图像压缩技术指标常用的图像压缩技术指标:图像熵与平均码长（图像熵与平均码长（Entropy and average code lenthgh）图像冗余度与编码效率（图像冗余度与编码效率（Coding efficiency）压缩比（压缩比（Compression ratio）客观评价客观评价 SNR 主观评价主观评价Ma Yingli CMC HBU 1、熵：信源的平均信息量 设图像像素灰度级表为设图像像素灰度级表为 s=s1,s2,sq，其概率分布为，其概率分布为P(s)=p(s1),p(s2),p(sq)，则信源的，则信源的熵熵熵熵为为Ma Yingli CMC HBU s作为灰度，共作为灰度，共q级，出现概率均等时，级，出现概率均等时，p(si)=1/q，当当灰灰度度只只有有两两级级时时，即即si=0,1，且且0出出现现概概率率为为p1，1出出现现概概率率为为p2=1-p1，其熵，其熵Ma Yingli CMC HBU 当p1=1/2，p2=1-p1=1/2时，H(s)=1为最大值。如图所示。Ma Yingli CMC HBU熵的性质：熵的性质：（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。Ma Yingli CMC HBU 2、平均码长：平均码长：码字长度的数学期望码字长度的数学期望3、冗余度、冗余度定义为：定义为：Ma Yingli CMC HBU 4、编码效率、编码效率定义为：定义为：冗余度接近于冗余度接近于0 0，或编码效率接近于，或编码效率接近于1 1的编码称为的编码称为高效码高效码。Ma Yingli CMC HBU 5、压压缩缩比比：若若原原始始图图象象的的平平均均比比特特率率为为n，编编码码后后的的平平均均比比特特率率为为nd，则则压缩比压缩比C定义为：定义为：Ma Yingli CMC HBU 6、客观评价、客观评价信噪比信噪比SNR定义为：定义为：Ma Yingli CMC HBU表表5.1 图像质量的主观评价等级图像质量的主观评价等级Score评价评价Notes5优秀优秀图像质量非常好图像质量非常好4良好良好图像质量高图像质量高,有很小的干扰但不影响观看有很小的干扰但不影响观看3中等中等图像质量可接受图像质量可接受,但有一些干扰但有一些干扰,对观看稍有妨碍对观看稍有妨碍2差差图像质量差图像质量差,对观看有妨碍对观看有妨碍1很差很差,劣劣图像质量很差图像质量很差,无法观看无法观看7、主观评价、主观评价：Ma Yingli CMC HBU图像编码主、客观评价的内在关系图像编码主、客观评价的内在关系图像类型图像类型高分辨率广播电视高分辨率广播电视普通数字广播电视普通数字广播电视数据库图像数据库图像会议电视会议电视传输数码率传输数码率客观评价客观评价SNR主观评价主观评价74 Mb/s48dB4.5分分34 Mb/s43dB4.0分分识别图像识别图像36dB.0分分64kb/s30dB2.5分分压缩后图像压缩后图像Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU5.1.5 数据压缩方法的分类数据压缩方法的分类1.1.无损压缩无损压缩（Lossless Compression）:nHuffman编码编码 nShannon编码编码n游程编码游程编码n算术编码算术编码n轮廓编码轮廓编码Ma Yingli CMC HBU2、有损压缩（、有损压缩（Lossy Compression）n预测编码预测编码 n变换编码变换编码 n混合编码混合编码现代压缩编码方法：现代压缩编码方法：n分形编码分形编码n模型基（模型基（Model-based）编码）编码Ma Yingli CMC HBU 图像编码图像编码/压缩主要分无损图像压缩和有损图像压缩两大块，按其发展历程压缩主要分无损图像压缩和有损图像压缩两大块，按其发展历程可分为：可分为：l第一代压缩编码第一代压缩编码 八十年代以前，主要是根据传统的信源编码方法。八十年代以前，主要是根据传统的信源编码方法。l第二代压缩编码第二代压缩编码 八十年代以后，突破信源编码理论，结合分形、模型基、神经网络、小波变换等数学工八十年代以后，突破信源编码理论，结合分形、模型基、神经网络、小波变换等数学工具，充分利用视觉系统生理心理特性和图像信源的各种特性。具，充分利用视觉系统生理心理特性和图像信源的各种特性。图像压缩方法的分类图像压缩方法的分类Ma Yingli CMC HBU像素编码像素编码变换编码变换编码预测编码预测编码位平面编码位平面编码增量调制增量调制熵编码熵编码算术编码算术编码DCTDCT变换变换DPCMDPCM调制调制 第第一一代代压压缩缩编编码码其他编码其他编码行程编码行程编码Ma Yingli CMC HBU子带编码子带编码模型编码模型编码分层编码分层编码分型编码分型编码第第二二代代压压缩缩编编码码Ma Yingli CMC HBU预测编码预测编码混合编码混合编码变换编码变换编码DFT、DCT变换变换ADPCMDPCM调制调制KLTKLT、WHTWHT、SLTSLT、WTWT变换变换变换变换 数数 据据 压压 缩缩其他编码其他编码增量调制增量调制 无无损损压压缩缩 有有损损压压缩缩统计编码统计编码Huffman、Shannon编码编码算术编码算术编码行程编码行程编码轮廓编码轮廓编码Ma Yingli CMC HBU5.2 统计编码统计编码n统计编码统计编码n根据信源的概率分布特性，分配具有惟一可译性的根据信源的概率分布特性，分配具有惟一可译性的可变长码字，降低平均码字长度，以提高信息的传可变长码字，降低平均码字长度，以提高信息的传输速度，节省存储空间。输速度，节省存储空间。n基本原理基本原理n在信号概率分布情况已知的基础上，概率大的信号在信号概率分布情况已知的基础上，概率大的信号对应的码字短，概率小的信号对应的码字长，这样对应的码字短，概率小的信号对应的码字长，这样就降低了平均码字长度。就降低了平均码字长度。Ma Yingli CMC HBU可变码长最佳编码定理可变码长最佳编码定理n 在变长编码中，如果码字长度严格按照信在变长编码中，如果码字长度严格按照信号中符号出现概率大小的相反顺序排列，则平号中符号出现概率大小的相反顺序排列，则平均码字长度一定小于其他符号顺序排列方式的均码字长度一定小于其他符号顺序排列方式的平均码字长度。平均码字长度。Ma Yingli CMC HBU英文字母出现相对频率英文字母出现相对频率字母字母字母字母A AB BC CD DE EF FGGHHI IJ JKKL LMM百分比百分比百分比百分比8.28.21.51.52.82.84.34.312.712.72.22.22.02.06.16.17.07.00.20.20.80.84.04.02.42.4字母字母字母字母N NOOP PQQR RS ST TU UV VWWX XY YZ Z百分比百分比百分比百分比6.76.77.57.51.91.90.10.16.06.06.36.39.19.12.82.81.01.02.42.40.20.22.02.00.10.1Ma Yingli CMC HBU英文字母出现相对频率Ma Yingli CMC HBU国际莫尔斯电码符号国际莫尔斯电码符号SymbolSymbolA AB BC CD DE EF FG GHHI IJ JK KL LMMCodeCode.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-SymbolSymbolNNOOP PQQR RS ST TU UV VWWX XY YZ ZCodeCode-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.SymbolSymbol0 01 12 23 34 45 56 67 78 89 9CodeCode-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.SymbolSymbol.,?:;-/“CodeCode.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.Ma Yingli CMC HBU5.2.1 Huffman编码编码n1前缀码（前缀码（Prefix Code）n一组唯一可译码的任一个码字都只与一种信号一组唯一可译码的任一个码字都只与一种信号存在对应关系。存在对应关系。n为保证唯一可译码，任一码字都不能是其他码为保证唯一可译码，任一码字都不能是其他码字的前缀。字的前缀。n例：例：f(i)=0,10,110,111Ma Yingli CMC HBU5.2.1 Huffman编码编码n1前缀码（前缀码（Prefix Code）4 4层树形结构的编码情况层树形结构的编码情况Ma Yingli CMC HBUf(i)=0,10,110,111为其子树。为其子树。Ma Yingli CMC HBU2Huffman编码编码算法：算法：将图像的灰度等级按概率大小进行将图像的灰度等级按概率大小进行升升/降降序排序。序排序。在灰度级集合中取两个最小概率相加，合成一个概率。在灰度级集合中取两个最小概率相加，合成一个概率。新合成的概率与其他的概率成员组成新的概率集合。新合成的概率与其他的概率成员组成新的概率集合。在新的概率集合中，仍然按照步骤在新的概率集合中，仍然按照步骤的规则，直至新的规则，直至新的概率集合中只有一个概率为的概率集合中只有一个概率为1 1的成员。这样的归并过程可以的成员。这样的归并过程可以用二叉树描述。用二叉树描述。从根节点按前缀码的编码规则进行二进制编码。从根节点按前缀码的编码规则进行二进制编码。Ma Yingli CMC HBUMa Yingli CMC HBU 信号源 s=s1,s2,s3,s4,s5,s6，其概率分布为p1=0.4 p2=0.3 p3=0.1 p4=0.1 p5=0.06 p6=0.04，求最佳Huffman码。方法：I.将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。Ma Yingli CMC HBUii.把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。iii.重复上述做法，直到最后剩下两个概率为止。iv.从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个二进制码，如对概率大的赋予码元0，对概率小的赋予码元1。Ma Yingli CMC HBUHuffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04Ma Yingli CMC HBUHuffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Ma Yingli CMC HBU输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman编码Ma Yingli CMC HBU输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman编码Ma Yingli CMC HBU输入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.4Huffman编码Ma Yingli CMC HBU输入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编码Ma Yingli CMC HBU输入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=1Huffman编码Ma Yingli CMC HBU输入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编码Ma Yingli CMC HBU输入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编码Ma Yingli CMC HBU输入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.40101010101S4=0100Huffman编码Ma Yingli CMC HBU输入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编码Ma Yingli CMC HBU输入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=01011Huffman编码Ma Yingli CMC HBU编码结果输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04代码10001101000101001011码长123455Ma Yingli CMC HBU1 10 00 01 1S1S21 11 11 10 00 00 0S5S4S3S6编码效率：Ma Yingli CMC HBU【例5.1】n第第1行和第行和第2行列举了一个信源的统计特性行列举了一个信源的统计特性n结果如第三行所示结果如第三行所示符号集符号集xi x1 x2 x3 x4 x5 x6 概率分布概率分布pi 0.400.200.120.110.090.08Huffman编码编码 101000000101100111Ma Yingli CMC HBUHuffman编码示意图编码示意图n上图所示为建立码的过程上图所示为建立码的过程n下图所示为从根开始，经各下图所示为从根开始，经各中间节点到叶节点的路径采中间节点到叶节点的路径采用二进制编码的情况用二进制编码的情况Ma Yingli CMC HBU【例】Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU3Huffman编码的性能编码的性能n优点：优点：n实现实现Huffman编码的基础是统计源数据集中各信号的概率编码的基础是统计源数据集中各信号的概率分布。分布。nHuffman编码在无失真的编码方法中效率优于其他编码方编码在无失真的编码方法中效率优于其他编码方法，是一种最佳变长码，其平均码长接近于熵值。法，是一种最佳变长码，其平均码长接近于熵值。n缺点：缺点：n当信源数据成分复杂时，庞大的信源集致使当信源数据成分复杂时，庞大的信源集致使Huffman码表码表较大，码表生成的计算量增加，编译码速度相应变慢较大，码表生成的计算量增加，编译码速度相应变慢n不等长编码致使硬件译码电路实现困难。上述原因致使不等长编码致使硬件译码电路实现困难。上述原因致使Huffman编码的实际应用受到限制。编码的实际应用受到限制。Ma Yingli CMC HBU4图像的图像的Huffman编译码系统编译码系统Ma Yingli CMC HBUClaude Elwood Shannon(19162001)Claude Elwood Shannon(April 30,1916 February 24,2001)was an American mathematician,electronic engineer,and cryptographer known as The father of Information Theory.Ma Yingli CMC HBU5.2.2 Shannon编码与编码与Fano编码编码5.2.2 Shannon编码与编码与Fano编码编码n1.Shannon提出了将信源符号依其概率降序排列，用提出了将信源符号依其概率降序排列，用符号序列累积概率的二进制表示作为对信源的唯一可符号序列累积概率的二进制表示作为对信源的唯一可译编码。其应用于图像编码的步骤如下：译编码。其应用于图像编码的步骤如下：（1 1）将）将N N个灰度级个灰度级x xi i按其概率递减进行排列。按其概率递减进行排列。（2 2）求概率分布）求概率分布p pi i的第的第i i个灰度级的二进制位数个灰度级的二进制位数n ni i。(5.10)(5.10)（3 3）计算与）计算与p pi i相对应的累积概率相对应的累积概率P Pi i,把与把与P Pi i相对应的二相对应的二进码和接下去与进码和接下去与p pk k（k k i i）相应的码相比较，前面的）相应的码相比较，前面的n ni i位至少有一位以上的数字是不同的。位至少有一位以上的数字是不同的。Ma Yingli CMC HBU【例5.2】由表5.3计算该信源的Shannon编码n平均码字长度为平均码字长度为2.92，较，较Huffman编码为长。编码为长。Ma Yingli CMC HBU2.Fano编码编码步骤步骤（1）将图像灰度级）将图像灰度级xi其概率大小按递减顺序进行排序。其概率大小按递减顺序进行排序。（2）将）将xi分成两组，使每组的概率和尽量接近。分成两组，使每组的概率和尽量接近。给第一组灰度级分配代码给第一组灰度级分配代码“0”，第二组分配代码，第二组分配代码“1”。（3）若每组还是由两个或以上的灰度级组成，重复上述步）若每组还是由两个或以上的灰度级组成，重复上述步骤，直至每组只有一个灰度级为止。骤，直至每组只有一个灰度级为止。Ma Yingli CMC HBU【例5.3】图5.6以表5.3的信源为例说明Fano编码。Ma Yingli CMC HBU5.2.3 算术编码算术编码Ma Yingli CMC HBUMa Yingli CMC HBU5.2.3 算术编码算术编码n在信源各符号概率接近的条件下，算术编码是一种优于在信源各符号概率接近的条件下，算术编码是一种优于Huffman编码的方法。编码的方法。n【例例】根根据据信信源源的的概概率率分分布布进进行行算算术术编编码码。已已知知信信源源的的概概率分布为率分布为n求二进制序列求二进制序列01011的编码。的编码。Ma Yingli CMC HBUn解：步解：步骤如下：如下：n（1）二二进进制制信信源源只只有有x1=0和和x2=1两两种种符符号号，相相应的概率为应的概率为pc=2/5,pe=1-pc=3/5 n（2）设设s为为区区域域左左端端起起始始位位置置，e为为区区域域右右端端终终止止位置，位置，l为子区的长度，则为子区的长度，则 n符号符号“0”的子区的子区为0，2/5），子区），子区长度度为2/5 ;n符号符号“1”的子区的子区为2/5 ，1，子区，子区长度度为3/5 。举例举例2 2Ma Yingli CMC HBU（3）随着序列符号的出现，子区按下列公式减少长度）随着序列符号的出现，子区按下列公式减少长度:n新子区左端新子区左端=前子区左端前子区左端+当前子区左端当前子区左端前子区长度前子区长度n新子区长度新子区长度=前子区长度前子区长度当前子区长度当前子区长度n设初始子区为设初始子区为0，1，步序为，步序为step，则编码过程参见，则编码过程参见实例实例。n可见，最后子区左端起始位置可见，最后子区左端起始位置 Ma Yingli CMC HBUn最后子区长度n最后子区右端终止位置 n编码结果为子区起始位置与终止位置之中点 =0.0011。n所以，二进序列的算术编码为0011。Ma Yingli CMC HBU算术编码算法的计算步骤实例算术编码算法的计算步骤实例step x s l 1002/5 210+（2/5）（2/5）=4/25（2/5）（3/5）=6/25 302/5+0 6/25=4/25（6/25）（2/5）=12/125 414/25+（2/5）（12/125）=124/625（12/125）（3/5）=36/625 51124/625+（2/5）（36/625）=692/3125（36/625）（3/5）=108/625 Ma Yingli CMC HBU举例举例2 2Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU算术编码的过程：Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU算术编码与Huffman编码的比较：Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU5.3 预测编码预测编码预测编码的基本思想：预测编码的基本思想：在某种模型的指导下，根据过去的样本序列在某种模型的指导下，根据过去的样本序列推测当前的信号样本值，然后用实际值与预推测当前的信号样本值，然后用实际值与预测值之间的误差值进行编码。测值之间的误差值进行编码。如果模型与实际情况符合得比较好且信号序如果模型与实际情况符合得比较好且信号序列的相关性较强，则误差信号的幅度将远远列的相关性较强，则误差信号的幅度将远远小于样本信号。小于样本信号。Ma Yingli CMC HBUMa Yingli CMC HBU图像差值幅度的概率分布Ma Yingli CMC HBU5.3.1 预测编码基本原理预测编码基本原理n对实际值与预测值之间的误差值进行编码n差分脉冲编码调制nDifferential Pulse Code ModulationnDPCMMa Yingli CMC HBU图图5.8 DPCM系统的组成系统的组成 Ma Yingli CMC HBU5.3.2 线性自适应预测编码线性自适应预测编码n假设经扫描后的图像信号假设经扫描后的图像信号x（t）是一个均值为零、方）是一个均值为零、方差为的平稳随机过程。线性预测就是选择差为的平稳随机过程。线性预测就是选择ai（i 1，2，N 1）使预测值）使预测值 n并且使差值并且使差值en的均方值为最小。的均方值为最小。n预测信号的均方误差（预测信号的均方误差（MSE）定义为）定义为 Een=E(xn-xn)2Ma Yingli CMC HBU设计最佳预测的系数设计最佳预测的系数ai，采用，采用MMSEn最小均方误差准则。可以令最小均方误差准则。可以令n定义定义xi和和xj的自相关函数的自相关函数 R（i，j）=Exi，xjn写成矩阵形式为写成矩阵形式为Yule-Walker方程组方程组 若若R（i）已知，该方程组可以用递推算法来求解）已知，该方程组可以用递推算法来求解ai。Ma Yingli CMC HBU通过分析可以得出以下结论：通过分析可以得出以下结论：n图像的相关性越强，压缩效果越好。图像的相关性越强，压缩效果越好。n当某个阶数已使当某个阶数已使EeN,eN 1 0时，即使再增加预时，即使再增加预测点数，压缩效果也不可能继续提高。测点数，压缩效果也不可能继续提高。n若若xi是平稳是平稳m阶阶Markov过程序列，则过程序列，则m阶线性预阶线性预测器就是在测器就是在MMSE意义下的最佳预测器。意义下的最佳预测器。Ma Yingli CMC HBU图图5.9 当前像素与邻近像素的位置关系当前像素与邻近像素的位置关系Ma Yingli CMC HBU常用预测器方案常用预测器方案n前值预测：用前值预测：用x0同一行的最近邻近像素来预测同一行的最近邻近像素来预测 =x0 n一维预测：如一维预测：如上图上图中的中的x1、x5。n二维预测：如二维预测：如上图上图中的中的 x1、x2、x3、x4、x5、x6、x7等。等。n三维预测三维预测Ma Yingli CMC HBU5.3.3 自适应预测编码自适应预测编码n自适应预测自适应预测n预测参数根据信号的统计特性来确定，以达到最预测参数根据信号的统计特性来确定，以达到最佳预测佳预测n预测编码的优点预测编码的优点n直观快捷、便于实现直观快捷、便于实现n预测编码的缺点预测编码的缺点n压缩比不够高压缩比不够高Ma Yingli CMC HBU5.4 变换编码变换编码5.4.1 变换编码的基本原理变换编码的基本原理n 通过数学变换可以改变信号能量的分布，从而压通过数学变换可以改变信号能量的分布，从而压缩信息量。缩信息量。n以傅里叶变换的概念说明合理的变换可以改变信以傅里叶变换的概念说明合理的变换可以改变信号能量分布的基本原理。号能量分布的基本原理。Ma Yingli CMC HBU变换可以改变信号能量的分布（Ma Yingli CMC HBU5.4.2 变换编码的系统结构变换编码的系统结构图图5.10 变换编码系统变换编码系统正正交交变变换换量量化化编编码码传传输输/储储存存解解码码反反交交换换图图像像输输入入图图像像输输出出Ma Yingli CMC HBU5.4.3 变换编码的实现变换编码的实现在变换编码中有以下几个问题值得注意：在变换编码中有以下几个问题值得注意：n图像变换方法的选取图像变换方法的选取n子图像大小的选取子图像大小的选取n常用的图像编码方法常用的图像编码方法n区域编码区域编码n阈值编码阈值编码n混合编码混合编码Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU变换编码Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU帧内混合编码原理图帧内混合编码原理图变换编码变换编码变换编码预测编码信信道道传输/存存储预测编码反反变换 f(1,n)F(1,n)e(1,n)e(1,n)f(2,n)F(2,n)e(2,n)e(2,n)f(M,n)F(M,n)e(M,n)e(M,n)f(1,n)f(2,n)f(M,n).Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUDCTDCT变换：变换：正变换：正变换：逆变换：逆变换：其中：其中：Ma Yingli CMC HBUMa Yingli CMC HBUHuffman:42bits；编码效率编码效率32.8%Huffman:16bits;编码效率：编码效率：12.5%例：例：原图像为：原图像为：DCTDCT变换变换除以量化系数，取整除以量化系数，取整Ma Yingli CMC HBUMa Yingli CMC HBUDCT变换编码实例原图原图解压图解压图Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU5.4.4 整数小波变换与图像压缩整数小波变换与图像压缩n量化器的设计是决定图像保真度的关键环节，而传统的DCT和经典小波变换在图像变换后会产生浮点数，因而必须对变换后的数据进行量化处理，这样就产生不同程度的失真。n新一代的整数小波变换（又叫第二代小波变换）采用提升方法能够实现整数变换，因而能够实现图像的无损压缩，显然它是一种很适合于医学等图像的压缩方法。n新的静态图像压缩标准JPEG2000中采用了基于提升方法的整数小波变换。Ma Yingli CMC HBU提升方法构造小波分为分裂、预测和更新提升方法构造小波分为分裂、预测和更新3 3个步骤。个步骤。n1分裂（分裂（split）n 将一原始信号序列sj按偶数和奇数序号分成两个较小的、互不相交的小波子集sj-1和dj-1：n2.预测（预测（predict）n 由于数据间存在相关性，因而可以定义一个预测算子P，用P(sj-1)来预测 dj-1.。n这样可用相邻的偶数序列来预测奇数序列。n用dj-1与P(sj-1)的差值代替d j-1，则数据量要比原始d j-1要小得多。n3更新（更新（update）n 上述两个过程一般不能保持原图像中的某些整体性质（如亮度）,为此我们要构造一个U算子去更新s,使之保持原有数据集的某些特性。Ma Yingli CMC HBU5.5 二值图像编码二值图像编码n只有只有“白白”（用（用“0”表示）和表示）和“黑黑”（用（用“1”表示）表示）两个灰度级称之为二值图像（两个灰度级称之为二值图像（binary image）。）。n二值图像通常是由人为产生的，如由文字组成的文档文二值图像通常是由人为产生的，如由文字组成的文档文件、表格、工程图纸、地图等。件、表格、工程图纸、地图等。n一幅二维图像按位平面进行分解可以得到若干个二值图一幅二维图像按位平面进行分解可以得到若干个二值图像，因而二值图像的编码方法为逐进编码模式奠定了基像，因而二值图像的编码方法为逐进编码模式奠定了基础。础。Ma Yingli CMC HBU5.5.1 跳跃空白编码跳跃空白编码(skip blank coding)n将图像的每一条扫描线分成若干等长的段，每段有将图像的每一条扫描线分成若干等长的段，每段有m个像个像素，一般素，一般m=812。n这些扫描线段的组成可能出现二类情况：（1 1）全是）全是“0”0”像素。像素。n这种线段称为这种线段称为“空白块（空白块（blankblank）”，常表示二值图像的背景成分。，常表示二值图像的背景成分。n编码时编码时“空白块空白块”用码字用码字“0 0”表示。表示。（2 2）全是）全是“1”1”像素或由像素或由“0”0”、“1”1”像素混合而成。像素混合而成。n编码时，这种线段用编码时，这种线段用“1”1”加加直接编码直接编码表示。表示。Ma Yingli CMC HBUn上述方法很容易推广的在二维情形中。上述方法很容易推广的在二维情形中。n将图像划分为若干个子图像。当将图像划分为若干个子图像。当子图像像素全为子图像像素全为0 0时，时，编码为编码为“0”0”;否则，子图像的否则，子图像的编码首位为编码首位为“1”1”，其其余码位余码位（code position）采用像素的直接编码采用像素的直接编码表示表示。Ma Yingli CMC HBU5.5.2 游程长度编码游程长度编码RLC(Run Length Coding)n一种简单的无损编码技术，它改变连续出现相同字符的表一种简单的无损编码技术，它改变连续出现相同字符的表达方式，以降低码长。达方式，以降低码长。n传真的二值图像中，连传真的二值图像中，连“0”0”或连或连“1”1”总是成串出现，总是成串出现，称为称为“白游程白游程”和和“黑游程黑游程”。n非二值的相同连续数据串，同样简化为两个符号：一非二值的相同连续数据串，同样简化为两个符号：一个符号代表个符号代表数据数据，第二个代表，第二个代表串串长长。n游程长度编码一般不直接单独使用，通常配合其他编码方游程长度编码一般不直接单独使用，通常配合其他编码方式使用来提高压缩效果。式使用来提高压缩效果。Ma Yingli CMC HBU二维行程编码要解决的核心问题是:将二维排列的像素，采用某种方式转化成一维排列的方式。之后按照一维行程编码方式进行编码。(a)(b)两种典型的二维行程编码的排列方式两种典型的二维行程编码的排列方式Ma Yingli CMC HBU如果按照行扫描的顺序排列的话，数如果按照行扫描的顺序排列的话，数据分布为：据分布为：行程编码为行程编码为:（3，130），（），（1，129），（），（1，134），（），（1，133），（），（1，129），（），（4，130），（），（1，129），（），（1，134），（），（1，133），（），（5，130），（），（1，129），（），（2，132），（），（2，130），（），（1，129），（），（2，130），（），（1，129），（），（2，130），（），（2，129），（），（1，127），（），（1，128），（），（1，127），（），（1，129），（），（1，131），（），（1，129），（），（1，131），（），（1，130），（），（1，127），（），（1，128），（），（1，127），（），（1，128），（），（1，127），（），（1，128），（），（2，132），（），（1，125），（），（1，126），（），（2，129），（），（1，127），（），（1，129），（），（1，133），（），（1，132），（），（1，127），（），（1，125），（），（2，128），（），（1，126），（），（1，130），（），（2，131）数据量为数据量为:46*:46*（3+83+8）=506(bit)(98.83%)=506(bit)(98.83%)数据量：数据量：64*8=512(bit)【例例】Ma Yingli CMC HBU如果按照列扫描的顺序排列的话，如果按照列扫描的顺序排列的话，数据分布为：数据分布为：行程编码为行程编码为:数据量为数据量为:42*:42*（3+83+8）=462(bit)(92.03%)=462(bit)(92.03%)（3，130），（），（1，129），（），（2，127），（），（1，125），（），（1，127），（），（4，130），（），（2，128），（），（1，126），（），（1，125），（），（4，130），（），（2，127），（），（1，129），（），（1，128），（），（5，129），（），（1，128），（），（1，129），（），（1，128），（），（2，134），（），（1，132），（），（1，130），（），（1，131），（），（2，127），（），（1，126），（），（2，133），（），（1，132），（），（1，130），（），（1，129），（），（1，128），（），（1，129），（），（1，130），），（1，129），（），（2，130），（），（1，129），（），（1，131），（），（1，132），（），（1，133），（），（1，131），（），（3，130），（），（1，129），（），（1，130），（），（2，132），（），（1，131）Ma Yingli CMC HBU如果按照方式如果按照方式(a)(a)扫描的顺序排扫描的顺序排列的话，数据分布为：列的话，数据分布为：行程编码为行程编码为:数据量为数据量为:43*:43*（3+83+8）=473(bit)(94.22%)=473(bit)(94.22%)（7，130），（），（2，130），（），（4，129），（），（2，130），（），（1，129）；（）；（1，127），（），（1，128），（），（1，127），（），（1，129），（），（1，131），（），（1，130），（），（1，132），（），（2，134），（），（2，133），（），（1，132），（），（1，130），（），（1，129），（），（1，128），（），（1，127），），（1，128），（），（1，127），（），（1，128），（），（1，127），（），（1，125），（），（1，126），（），（2，129），（），（1，127），（），（1，129），（），（1，133），（），（1，132），（），（1，131），（），（1，129），（），（2，130），（），（1，129），（），（3，130），（），（1，129），（），（1，130），（），（2，132），），（2，131），（），（1，130），（），（1，126），（），（2，128），（），（2，127）Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU 该压缩算法常用于二值图像编码中，如位平面编码(bit-plane coding)Ma Yingli CMC HBUMa Yingli CMC HBU5.6 新型的图像压缩编码方法新型的图像压缩编码方法n经典的编码方法利用去除图像数据的相关性等方法对图像经典的编码方法利用去除图像数据的相关性等方法对图像进行压缩，其压缩效果受到一定的限制。进行压缩，其压缩效果受到一定的限制。n模型编码利用对图像建模的方法对图像参数进行估计。由模型编码利用对图像建模的方法对图像参数进行估计。由于参数的数据量远远少于图像的数据量，因而用模型编码于参数的数据量远远少于图像的数据量，因而用模型编码对压缩数据量极其有效。对压缩数据量极其有效。n常见的模型编码有：常见的模型编码有：n分形编码（分形编码（fractal coding）n自适应网格编码（自适应网格编码（self-adaptive mesh coding）Ma Yingli CMC HBU5.6.1 分形分形(fractal)的基本概念的基本概念n与经典的编码方法相比，分形编码在思路上有新的突与经典的编码方法相比，分形编码在思路上有新的突破，其压缩比高出一般编码方法破，其压缩比高出一般编码方法23个数量级。个数量级。n压缩过程时间长但解压缩速度快的特点将使其在大数据量、压缩过程时间长但解压缩速度快的特点将使其在大数据量、高质量的多媒体应用、高速网络等场合中发挥重要的角色。高质量的多媒体应用、高速网络等场合中发挥重要的角色。n分形的基本思想来源于数学上对客观世界一些现象的分形的基本思想来源于数学上对客观世界一些现象的自相似性描述。自相似性描述。n分形是一种由许多与全局相似的局部所构成的形体。分形是一种由许多与全局相似的局部所构成的形体。n对于集合对于集合A，如果描述其中的点需要，如果描述其中的点需要d个坐标，则称该个坐标，则称该集合集合A是是d维的，即维的，即 dim(A)=d （5.37）n在分形几何学中，在分形几何学中，d可以扩展为分数，这时可以扩展为分数，这时d称为分维。称为分维。Ma Yingli CMC HBU5.6.2 分形压缩的基本方法分形压缩的基本方法n分形压缩将图像分解成若干子图像，利用图像的仿射分形压缩将图像分解成若干子图像，利用图像的仿射变换可以寻找出子图像间的自相似性。变换可以寻找出子图像间的自相似性。n仿射变换是指对子图像进行旋转、伸缩、位移变换。仿射变换是指对子图像进行旋转、伸缩、位移变换。n仿射变换的特性有：仿射变换的特性有：n（1）仿射变换的逆变换也是仿射变换。）仿射变换的逆变换也是仿射变换。n（2）仿射变换是线性变换。）仿射变换是线性变换。n（3）两平行线经过仿射变换后仍然是平行线，所以平行四边）两平行线经过仿射变换后仍然是平行线，所以平行四边形经仿射变换后变成另外一个平行四边形。形经仿射变换后变成另外一个平行四边形。n（4）可以通过变换参数求解变换后平面图形的面积与原平面）可以通过变换参数求解变换后平面图形的面积与原平面图形面积的比值。图形面积的比值。n（5）选择合适的参数，仿射变换为相似变换。）选择合适的参数，仿射变换为相似变换。Ma Yingli CMC HBUn通过用数据量极小的系数代替数据量较大的实际像素值而将图像表示成压缩形式。n目前采用全自动的分形压缩，对灰度图像一般可以达到4:1100:1，对彩色图像压缩比还可以更高些。n压缩时间较慢，而解压缩时间极快。n用户常常关心的是解压缩时间，因而分形压缩的这种不对称性对使用数据的用户是很有用的。n如果采用这种技术制作VCD、DVD将使其具有广泛的市场前景。n分形压缩的另一个特点是压缩特性与分辨率无关n利用分形压缩的图像可以按不同分辨率实现无级缩放而计算量相同。Ma Yingli CMC HBUMa Yingli CMC HBU5.7 图像压缩编码标准图像压缩编码标准n在静态图像压缩编码标准中，比较著名的有JPEG、JBIG等标准。n视频可看成是一幅幅不同但相关的静态图像的时间序列。n静态图像的压缩技术和标准可以直接应用于视频的单帧图像。n介绍：n适用于静态图像的JPEG标准和JBIG标准n新的JPEG2000压缩国际标准Ma Yingli CMC HBU5.7.1 彩色与灰度图像压缩标准彩色与灰度图像压缩标准JPEG 1JPEG算法与系统nJPEG基本系统nJPEG扩展系统n信息保持压缩系统Ma Yingli CMC HBU2JPEG基本系统基本系统每个单独的彩色图像分量的编码算法：n 将量化精度为8位的待压缩图像分成若干个88样值子块，做基于88子块的DCT。n 根据最佳视觉特性构造量化表，设计自适应量化器并对DCT的频率系数进行量化。n 为了增加连续的0系数的个数，对量化后的系数进行Z字形重排。n 用Huffman码作变字长熵编码器对量化系数进行编码，进一步压缩数据量。Ma Yingli CMC HBUJPEG编/解码器算法框图Ma Yingli CMC HBU上述算法的几点说明n（1）彩色空间转换问题n（2）量化 最佳的亮度量化表和色度量化表。n（3）Z字形重排n（4）DCT系数的编码n（5）JPEG位数据流Ma Yingli CMC HBU亮度量化表 1611101624405161121214192658605514