主要内容uu编码编码及信息及信息及信息及信息论论概述概述概述概述uu行程行程行程行程编码编码uuLZWLZW编码编码uu霍夫曼霍夫曼霍夫曼霍夫曼编码编码uu预测编码预测编码uu变换编码变换编码uu压缩标压缩标准准准准简简介介介介* *一幅512512的灰度图像的比特数为：一、编码及信息论概述一、编码及信息论概述1、图像压缩的必要性可见：数字图像通常要求很大的比特数，这给图像的传输和存储带来一定的困难。要占用很多的资源，花很高的费用。5125128 = 2,097,152 bit 2,097,152 bit = 256k256k。一部90分钟的彩色电影，每秒放映24帧。把它数字化，每帧512x512象素，每象素的R R、G G、B B三分量分别占8bit，总比特数为：一、编码及信息论概述一、编码及信息论概述1、图像压缩的必要性若一张CD光盘可存600兆字节数据，这部电影图像（不包括声音）就需要160160张CD光盘用来存储。90602435125128bit= 97,200 97,200 (M)(M)因此，对图像数据进行压缩显得非常必要。一、编码及信息论概述一、编码及信息论概述 本章讨论的问题：在满足一定条件下，能否减小图像bit数，以及用什么样的编码方法使之减少。n 编码一、编码及信息论概述一、编码及信息论概述n 图像编码n 信号空间是用符号数码元素表示信号、消息或事件的过程。是研究图像数据的编码方法。期望用最少的码字表示信源发出的图像信号，使数据得到压缩，减少图像数据占用的信号空间和能量，降低信号处理的复杂程度。物理空间存储器、磁盘等数据存储介质；时间空间传输给定消息集合所需要的时间；频谱空间传输给定消息集合所需要的带宽。n图像中像素灰度出现的不均匀性，造成图像信息熵冗余，即用同样长度比特表示每一个灰度，则必然存在冗余。n图像能量在变换域内分布的不均匀性，比如大部分能量集中在低频部分，而小部分能量集中在高和较高的频率部分。n图像像素灰度在时间和空间上的相关性造成信息冗余。2、图像压缩的可能性 一、编码及信息论概述一、编码及信息论概述n数据冗余一、编码及信息论概述一、编码及信息论概述空间冗余，邻近像素灰度分布的相关性很强；频间冗余，多谱段图像中各谱段图像对应像素之间灰度相关性很强；时间冗余，序列图像帧间画面对应像素灰度的相关性很强。如果用8 bit表示下面图像的像素，可以说该图像存在着编码冗余。例析例析1 1：因为该图像的像素只有两个灰度，用1 bit即可表示。 对于一幅图像，很多单个像素对视觉的贡献是冗余的。这可以建立在对邻域值预测的基础上。例析例析2 2：例如：原图像数据：250253251252250压缩后数据：250312040bit14bitn应用环境允许图像有一定程度失真一、编码及信息论概述一、编码及信息论概述(1)接收端图像设备分辨率较低，则可降低图像分辨率；(2)根据人的视觉特性对不敏感区进行降分辨率编码（视觉冗余）；(3)应用方关心图像区域有限，可对其余部分图像可采用空间和灰级上的粗化；(4)对于识别，图像特征抽取和描述也是数据压缩。33K15K例析例析1 1：n 视觉心理冗余视觉心理冗余一些信息在一般视觉处理中比其它信息的相对重要程度要一些信息在一般视觉处理中比其它信息的相对重要程度要小，这种信息就被称为小，这种信息就被称为视觉心理冗余视觉心理冗余。无失真编码（无损压缩、可逆压缩）是一种经编、解码后图像不会产生失真的编码方法。可重建图像，但压缩比不大；有失真编码（有损压缩、不可逆压缩）解码时无法完全恢复原始图像，压缩比大但有信息损失。3、图像编码分类一、编码及信息论概述一、编码及信息论概述失真失真是指编码输入图像与解码输出图像之间的随机误差；压缩比压缩比指原图像比特数与压缩后图像比特数之比。变换编码变换编码统计编码统计编码预测编码预测编码图像压缩方法图像压缩方法有损压缩有损压缩行行程程编编码码编编码码哈哈夫夫曼曼编编码码算算术术编编码码其其他他无无损损预预测测有有损损预预测测其其他他编编码码变变换换其其他他无损压缩无损压缩一、编码及信息论概述一、编码及信息论概述数学上，信源是一概率场。若信源可能产生的信息是 ，这些信息出现的概率分别是 。则该信源可表示为：一、编码及信息论概述一、编码及信息论概述n信源的定义信源即能够产生信息的事物。信息量：从N个相等可能发生的事件中，选出其中一个事件所需的信息度量，称为信息量。4、信息量和熵一、编码及信息论概述一、编码及信息论概述例如：要辨识1到32中选定的某一个数，可先提问：“是否大于16？”，得到回答就消去半数可能事件。每提问一次得到回答，可以得到1bit信息量(二进制位)。这里共需5次，因此所需的信息量为：n 信息量的计算n 熵的计算一、编码及信息论概述一、编码及信息论概述从N个数选定一个数s的概率为p(s)，且等概率，p(s)=1/N。设信源符号表为s=s1, s2, , sq，其概率分布为P(s)=p(s1), p(s2),p(sq)，则信源的熵为： 编码中，熵表示信源中消息的平均信息量平均信息量。在不考虑消息间的相关性时，是无失真编码平均长度比特数的下限。例：信源说明：该信源编码平均码长最短情况下为7/4，不能再小，否则就会引起错误。而平均码长比此数大许多时，就表明还有待改进。一、编码及信息论概述一、编码及信息论概述n 熵的作用一、编码及信息论概述一、编码及信息论概述 (1)熵是一个非负数，即总有H(s)0。(2)当其中一个符号sj的出现概率p(sj)=1时，其余符号si(ij)的出现概率p(si)=0，H(s)=0。(3)当各个si出现的概率相同时，则最大平均信息量为log2q。(4)熵值总有H(s)log2q。n 熵的性质(1) s作为灰度，共q级，出现概率均等时，p(si)=1/q，(2)当灰度只有两级时，即si = 0,1，且0出现概率为p1，1出现概率为p2=1-p1，其熵：一、编码及信息论概述一、编码及信息论概述n图像的熵(3)对位图像，s作为灰度，共256级，其熵为：(4)当图像由单一灰度级组成时（即灰度均匀分布图像）,其熵为：n图像的熵一、编码及信息论概述一、编码及信息论概述编码器是用符号集中的符号构成输出代码，并建立输入信号单元与输出代码的对应关系。5、信息编码过程消息集合消息集合输出代码输出代码符号集符号集 符号符号(码元码元)编码器编码器一、编码及信息论概述一、编码及信息论概述在无干扰的条件下，存在一种无失真的编码方法，使编码的平均长度L与信源的熵H(s)任意地接近，即L=H(s)+其中为任意小的正数，但以H(s)为其下限，即LH(s)，这就是香农(Shannon)无干扰编码定理。6、无失真编码定理一、编码及信息论概述一、编码及信息论概述ClaudeShannon(1916-2001)编码效率定义为：冗余度接近于0，或编码效率接近于1的编码称为高效码。(1)编码效率一、编码及信息论概述一、编码及信息论概述 若原始图像的平均比特率为n，编码后的平均比特率为nd，则压缩比压缩比C定义为： 由Shannon定理，无失真编码最最大大可可能的数据压缩比能的数据压缩比为：(2)压缩比一、编码及信息论概述一、编码及信息论概述 对于无失真图像的编码，原始图像数据的压缩存在一个下限，即平均码组长度不能小于原始图像的熵，而理论上的最佳编码的平均码长无限接近原始图像的熵。 原始图像冗余度定义为：7、熵与相关性、冗余度的关系一、编码及信息论概述一、编码及信息论概述主要内容uu编码编码及信息及信息及信息及信息论论概述概述概述概述uu行程行程行程行程编码编码uuLZWLZW编码编码uu霍夫曼霍夫曼霍夫曼霍夫曼编码编码uu预测编码预测编码uu变换编码变换编码uu压缩标压缩标准准准准简简介介介介统统计计编编码码1、概念： 行程：具有相同灰度值的像素序列。2、编码思想： 去除像素冗余。即用行程的灰度和行程的长度代替行程本身。二、行程编码二、行程编码(Run Length Encoding)(Run Length Encoding)例：设重复次数为iC,重复像素值为iP，则编码为：iCiPiCiPiCiP编码前：aaaaaaabbbbbbcccccccc编码后：7a6b8c二、行程编码二、行程编码二、行程编码二、行程编码n分析l对于有大面积色块的图像，压缩效果很好；l对于纷杂的图像，压缩效果不好，最坏情况下，会加倍图像。主要内容uu编码编码及信息及信息及信息及信息论论概述概述概述概述uu行程行程行程行程编码编码uuLZWLZW编码编码uu霍夫曼霍夫曼霍夫曼霍夫曼编码编码uu预测编码预测编码uu变换编码变换编码uu压缩标压缩标准准准准简简介介介介* * 1985年,美国人Welch将LZ压缩技术从概念发展到实用阶段,简称LZW压缩技术。广泛用于图象压缩领域。 LZW（Lempel-Ziv&Welch）编码又称字字串串表表编编码码，属于一种无损编码。LZW编码与行程编码类似，也是对字符串进行编码从而实现压缩，但它在编码的同时还生成了特定字符串以及与之对应的索引字符串表。三、三、LZWLZW编码编码 1977年,以色列人Lempel和Ziv共同提出了查找冗余字符和用较短的符号标记替代冗余字符的概念，简称LZ压缩技术。 1、简介三、三、LZWLZW编码编码(1) 在压缩过程中动态地形成一个字符序列表(字典)。(2) (a)每当压缩扫描图像发现一个字典中没有的字符序列，就把该字符序列存到字典中； (b)并用字典的地址（编码）作为这个字符序列的代码，替换原图像中的字符序列； (c)下次再碰到相同的字符序列，就用字典的地址代替字符序列。2、基本思想 去除像素冗余。F步骤步骤1：将词典初始化为包含所有可能的单字将词典初始化为包含所有可能的单字F步骤步骤2：当前字符当前字符C:=C:=字符流中的下一个字符。字符流中的下一个字符。字符，当前前缀字符，当前前缀P P初始化为空初始化为空( (NULL) )。3、基本步骤三、三、LZWLZW编码编码令令P:=CP:=C，现在的，现在的P P仅包含仅包含一个字符一个字符C CF步骤步骤3 3：判断判断P PC C是否在词典中是否在词典中? ?（1 1）如果）如果“是是”，则用，则用C C扩展扩展P P，即让，即让P:=PP:=PC C（2 2）如果）如果“否否”，则，则输出与当前前缀输出与当前前缀P P相对应的码字；相对应的码字；将将P PC C添加到词典中；添加到词典中；三、三、LZWLZW编码编码F步骤步骤4 4：判断码字流中是否还有码字要译判断码字流中是否还有码字要译? ?（1 1）如果）如果“是是”，就返回到步骤，就返回到步骤2 2；（2 2）如果）如果“否否”把代表当前前缀把代表当前前缀P P的码字输出到码字流；的码字输出到码字流；结束。结束。三、三、LZWLZW编码编码初始化字符串表 字符串索引(16进制)a0Hb1Hc2H d3HLZW_CLEAR（初始化标记）4HLZW_EOI（结束标记）5HLZWLZW编码例析编码例析如：对字符串如：对字符串“aabcabbbbd” 进行编码进行编码输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成的新字符串及索引生成的新字符串及索引NULLNULLa aa ab bc ca ab bb bb bb bd dNULLNULLNULLNULLa aa aa aaaaa4H4H0H0H0H0Hababbcbccacaabababbabbbbbbbbbbbbdbbd1H1H2H2H7H7H1H1HBHBH3H3H5H5Hb bc ca aababb bb bbbbbd daa aa ab ab bc bc ca ca abb abb bb bb bbd bbd S1为NULL,故输出结果为空S1+S2在字符表中,S1=S1+S2aa不存在,故输出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“a”ab不存在,故输出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“b”S1+S2结果已存在,故输出结果为空S1+S2在字符表中,S1=S1+S2输入结束输出S1的索引3H输出LZW_EOI标志的索引LZW编码例析：“aabcabbbbd”主要内容uu编码编码及信息及信息及信息及信息论论概述概述概述概述uu行程行程行程行程编码编码uuLZWLZW编码编码uu霍夫曼霍夫曼霍夫曼霍夫曼编码编码uu预测编码预测编码uu变换编码变换编码uu压缩标压缩标准准准准简简介介介介霍夫曼(Huffman)编码是可变字长编码(Variablelengthcoding，VLC)的一种。Huffman于1952年提出的一种编码方法。该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，常被称作Huffman编码，有时称之为最佳编码， 1、简介四、霍夫曼四、霍夫曼(Huffman)(Huffman)编码编码四、霍夫曼四、霍夫曼(Huffman)(Huffman)编码编码2、基本思想通过减少编码冗余来达到数据压缩的目的。a)统计各个符号出现的概率。b)建立一个概率统计表。将最常出现(概率大的)的符号用最短的编码；最少出现的符号用最长的编码。例例如如：信号源 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码。步骤如下：将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。四、霍夫曼四、霍夫曼(Huffman)(Huffman)编码编码把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。重复上述做法，直到最后剩下两个概率为止。从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个二进制码，如对概率大的赋予码元0，对概率小的赋予码元1。四、霍夫曼四、霍夫曼(Huffman)(Huffman)编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04HuffmanHuffman编码例析编码例析输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1HuffmanHuffman编码例析编码例析输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1HuffmanHuffman编码例析编码例析输入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3HuffmanHuffman编码例析编码例析输入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.4HuffmanHuffman编码例析编码例析输入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101HuffmanHuffman编码例析编码例析输入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101S1=1HuffmanHuffman编码例析编码例析输入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101S2=00HuffmanHuffman编码例析编码例析输入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101S3=011HuffmanHuffman编码例析编码例析输入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101S4=0100HuffmanHuffman编码例析编码例析输入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101S5=01010HuffmanHuffman编码例析编码例析输入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101S6=01011HuffmanHuffman编码例析编码例析一首英文歌曲：BecauseImbad,IambadcomeonBad,badreally,reallybadYouknowImbad,ImbadBad,badreally,reallybadYouknowImbad,Imbadcomeon,youknowBad,bad-really,reallybadHuffmanHuffman编码树结构编码树结构短语符号频率概率BecauseB10.03ImI60.17BadB150.43ComeonC20.06ItI10.03ReallyR60.17YouknowY40.11HuffmanHuffman编码树结构编码树结构S6S5S3S2S1B 0.43(Bad)10(1.00)S40001I 0.17(Im)R 0.17(Really)Y 0.11(You know)C 0.06(Come on)B 0.03(Because)I 0.03(It)010011001000010001010100001001(0.57)(0.23)(0.12)(0.06)(0.34)HuffmanHuffman编码树结构编码树结构短语符号频率概率代码长度编码BecauseB10.03501001ImI60.173001BadB150.4311ComeonC20.0640101ItI10.03501000ReallyR60.173000YouknowY40.113011HuffmanHuffman编码树结构编码树结构平均码长：平均码长：L=0.035+0.173+0.431+0.064+0.035+0.173+0.113=2.32HuffmanHuffman编码树结构编码树结构熵：熵：H=-(0.03log0.03+0.17log0.17+0.43long0.43+0.06log0.06+0.03log0.03+0.17log0.17+0.11log0.11)=2.29编码前：35log27=98.3,编码后：81位压缩比：(98.3-81)/98.317.6%。主要内容uu编码编码及信息及信息及信息及信息论论概述概述概述概述uu行程行程行程行程编码编码uuLZWLZW编码编码uu霍夫曼霍夫曼霍夫曼霍夫曼编码编码uu预测编码预测编码uu变换编码变换编码uu压缩标压缩标准准准准简简介介介介* *n预测编码五、预测编码五、预测编码l基本思路：利用前面已经出现过的符号来预测当前的符号，然后将实际上的符号与预测相减得到预测误差值。l利用预测编码的好处在于预测误差值的范围比原信号的数字范围小，如果预测足够精确的话。l通常会对预测误差值进一步编码（quantization）。l可分为有损和无损预测，但预测本身不会造成失真。属于时间域 (Time domain)的编码方法。五、预测编码五、预测编码1、无损预测编码(LosslessPredictiveCoding)(1)基本思想基本思想l去除像素冗余。l 认为相邻像素的信息有冗余。当前像素值可以用先前的像素值来获得。l用当前像素值fn，通过预测器得到一个预测值 ，对当前值和预测值求差。对差编码，作为压缩数据流中的下一个元素。五、预测编码五、预测编码1001021011001001011001021021001001031001021011001001001021001011011001001001002-1-101-120-2-13-32-10002-210-100n例：利用前一个像素预测五、预测编码五、预测编码一般情况下，利用前m个像素的线性组合来预测，即预测器为：其中，round为取最近整数，i为预测系数(可为1/m)，y是行变量。注意：前m个像素不能用此法编码，可用哈夫曼编码。n原理例析例析预测值：五、预测编码五、预测编码(2)编码步骤第步：压缩头处理。第步：预测值。第步：求预测误差值。第步：对误差e(x,y)编码，作为压缩值。重复、步预测器器最接近最接近的整数的整数+ -符号符号编码压缩图像输入图像enfn fn五、预测编码五、预测编码(3)编码原理图pp 基本概念基本概念pp 量化器量化器pp 编码原理编码原理五、预测编码五、预测编码2、有损预测编码(Lossy Predictive Coding)(1)有损压缩的基本概念n有损压缩：n通过牺牲图像的准确率来达到增大压缩率的目的。通过牺牲图像的准确率来达到增大压缩率的目的。n如果容忍解压后的结果中有一定的误差，那么压缩率可以显著提高。如果容忍解压后的结果中有一定的误差，那么压缩率可以显著提高。n有损压缩的压缩比：n在图像压缩比大于在图像压缩比大于30:130:1时，仍然能够重构图像。时，仍然能够重构图像。n在图像压缩比为在图像压缩比为10:110:1到到20:120:1时，重构图像与原图几乎没有差别。时，重构图像与原图几乎没有差别。n无损压缩的压缩比很少有能超过无损压缩的压缩比很少有能超过3:1的的（Why ?）。n有损与无损压缩的根本差别在于有没有量化器模块有没有量化器模块。五、预测编码五、预测编码数据源编、解码的一般模型n编码模型编码模型n解码模型解码模型符号符号解解码器器反向反向映射器映射器映射器映射器量化器量化器编码器器五、预测编码五、预测编码(2)量化器n减少数据量的最减少数据量的最简单的的办法是将法是将图像量化成像量化成较少的灰少的灰度度级，通，通过减少减少图像的灰度像的灰度级来来实现图像的像的压缩；n这种量化是不可逆的，因而解种量化是不可逆的，因而解码时图像有像有损失。失。例如： 如果输入是256个灰度级，对灰度级量化后输出，只剩下4个层次，数据量被大大减少。五、预测编码五、预测编码n量化器的定义五、预测编码五、预测编码l阶梯形量化函数梯形量化函数t=q(s)，是一个，是一个s的奇函数（即的奇函数（即q(-s) =-q(s)），它可以通），它可以通过L/2、si和和ti来完全描述，从而定来完全描述，从而定义了了一个量化器。一个量化器。lsi 被称被称为量化器的量化器的决策决策级（阈值）；）； ti 被称被称为量化器的量化器的重构重构级（代表（代表级）。）。 L：是量化器的是量化器的级数。数。l由于由于习惯的原因，的原因，si被被认为是映射到是映射到ti，如果它在半开区，如果它在半开区间(si,si+1。inputs1s2S(L/2)-1outputstt1t2t(L/2)-t(L/2)S-(L/2)-1t = q(s)决策决策级( (阈值) )重构重构重构重构级级( ( ( (代表代表代表代表级级) ) ) )注：量化的对象可能是负数五、预测编码五、预测编码n量化器的定义(3)无损到有损算法演变五、预测编码五、预测编码基本思想：基本思想：对无损预测压缩的误差进行量化，通过消除视觉心理冗余，达到对图像进一步压缩的目的。 引入量化引入量化(Quantification)五、预测编码五、预测编码 将en量化： 用： 近似 编码： 解码：n编、解码原理及过程 n编码流程图： n = Q( fn - fn)+ -符号编码预测器压缩图像输入图像enfn fn量化器n五、预测编码五、预测编码压缩图像 n解码流程图： fn = n + fn+ +符号解码预测器解压图像 fn fnn五、预测编码五、预测编码预测器器预测器器编码编码fn解码解码fn五、预测编码五、预测编码注意：上述方案的压缩编码中，预测器的输入是fn，而解压中的预测器的输入是fn ，要使用相同的预测器，编码方案要进行修改。n修改后的有损预测编码 n = Q( fn - fn)符号符号编码压缩图像+ -en输入图像fn量化器量化器n预测器器 fn+ + fn fn = n + fn五、预测编码五、预测编码n n DPCM简介l1950年，卡特勒申请专利;l1952年，获得批准;l1958年，格雷厄姆（Graham)开始计算机模拟研究编码方法；l1966年，奥尼尔（ONeal)对电视信号预测编码进行理论分析以及计算机模拟；l1971年投入使用。五、预测编码五、预测编码差分脉冲编码调制(Differential Pulse Code Modulation, DPCM)，采用反馈方法预测估值。量化器编码器解码器预测器预测器五、预测编码五、预测编码n编码原理图五、预测编码五、预测编码n量化器n预测器 一般是一个小于1的预测系数。例如：量化器设： = 6.5+6.5-6.5ee有损预测编码有损预测编码DPCMDPCMn举例： = 1， = 6.5计算：两个像素f0=14、f1=15，则：有损预测编码有损预测编码DPCMDPCM(预测结果预测结果)(预测误差预测误差)(预测误差预测误差)(重构结果重构结果)(重构误差重构误差) 输入 编码 解码 误差n f f e e f f f f-f0 14 - - - 14.0 - 14.0 0.01 15 14.0 1.0 6.5 20.5 14.0 20.5 -5.52 14 20.5 -6.5 -6.5 14.0 20.5 14.0 0.03 15 14.0 1.0 6.5 20.5 14.0 20.5 -5.5 . . . . . . . . 14 29 20.5 8.5 6.5 27.0 20.5 27.0 2.015 37 27.0 10.0 6.5 33.5 27.0 33.5 3.516 47 33.5 13.5 6.5 40.0 33.5 40.0 7.017 62 40.0 22.0 6.5 46.5 40.0 46.5 15.5有损预测编码有损预测编码DPCMDPCM3、预测器的一般模型器的一般模型可以是固定的，也可以是自适应的；可以是线性的，也可以是非线性的。 预测器设计得越好，对输入的数据压缩就越多。五、预测编码五、预测编码n 一维线性预测预测器模型预测器模型 选ak使2d(n)最小。 设x(n)是广义平稳的，且e(n)均值为0，则预测器模型预测器模型(1)最佳线性预测 假设x(n)是各态遍历的，且训练样本数N相当大，则x(n)的自相关函数 把(3-1)式写成矩阵形式：预测器模型预测器模型若x(n)是非平稳的，或是分段近似广义平稳，则可采用边送数据边测量与估计x(n)的自相关函数，求出相应的最佳预测系数。随之，相应的最佳预测系数随着x(n)的统计特性的变化而变化，这就是自适应线性预测。预测器模型预测器模型(2)自适应线性预测原始图象用f(m,n)表示： 预测的差值定义为：这里Z为对象素f(m,n)进行预测的相关点的集合。预测器模型预测器模型n n二维线性预测 方程的解 a1,a2, am 便是 一组最佳的预测系数。压缩效果可用方差2e(n)来衡量， 原始序列相关性越强， R(k)越大，2e(n)越小，压缩效果越显著；原始序列互不相关，即R(k) =0，k0，则，2e(n)=2x(n)一点也不能压缩。预测器模型预测器模型主要内容uu编码编码及信息及信息及信息及信息论论概述概述概述概述uu行程行程行程行程编码编码uuLZWLZW编码编码uu霍夫曼霍夫曼霍夫曼霍夫曼编码编码uu预测编码预测编码uu变换编码变换编码uu压缩标压缩标准准准准简简介介介介* *六、变换编码六、变换编码1、变换编码的基本思想n用一个可逆的、线性的变换用一个可逆的、线性的变换(如如FFT、DFT)，把图像映，把图像映射到变换系数集合射到变换系数集合;n然后对该系数集合进行量化和编码然后对该系数集合进行量化和编码;n对于大多数自然图像，对于大多数自然图像，重要系数的数量是比较少的重要系数的数量是比较少的，因，因而可以用量化而可以用量化(或完全抛弃或完全抛弃)，且仅以较小的图像失真为，且仅以较小的图像失真为代价。代价。5255 6166 706164736359 6690 1098569726259 6811314410466736358 7112215410670696761 681041268868707965 6070 776858758571 6459 556165838779 6968 65767894六、变换编码六、变换编码例如：原图像原图像DCT变换系数DCT编码dctdemo.mDEMOn编码、解码流程图符号符号解解码码器器逆逆变换变换正变换量化器符号编码器构造nn的子图合成nn的子图输入图像NN压缩图像压缩图像解压图像六、变换编码六、变换编码n构造nn的子图Nnnnnnnnnnnnn六、变换编码六、变换编码N六、变换编码六、变换编码2、变换编码的基本原理将FFT逆变换表达式进行改写：F(u,v)记为：T(u,v)expj2(ux+vy)/n记为：H(x,y,u,v)变换编码,即要用等式的右部近似原图像。六、变换编码六、变换编码基本理论基本理论进一步改写：其中：1)F是一个包含了f(x,y)的象素的nn的矩阵；2)Huv的值只依赖坐标变量x,y,u,v，与T(u,v)和f(x,y)的值无关。被称为基图像。可以在变换前一次生成，对每一个nn的子图变换都可以使用。六、变换编码六、变换编码基本理论基本理论基图像Huv：六、变换编码六、变换编码基本理论基本理论n变换系数截取模板函数通过定义变换系数截取模板函数，消去冗余。对于：近似：1 1 1 1 0 0 0 01 1 1 1 0 0 0 01 1 1 0 0 0 0 01 1 0 0 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0六、变换编码六、变换编码基本理论基本理论n误差评估：六、变换编码六、变换编码基本理论基本理论n误差评估其中，|F F|是(F F)的矩阵范数， 2T(u,v)是变换在(u,v)位置上的系数方差。最后的简化是基于基图像的规范正交，并假设F的像素是通过一个具有0均值和已知协方差的随机处理产生的。n小结六、变换编码六、变换编码基本理论基本理论（1）总的均方近似误差是丢弃的变换系数的方差之和（也即对于m(u,v)=0的系数方差之和）。（2）能把大多数信息封装到最少的系数里去的变换，可得到最好的子图像的近似，同时重构误差也最小。（3）在导致等式成立的假设下，一个NN的图像的(N/n)2个子图像的均方误差是相同的。因此，NN图像的均方误差（是平均误差的测量）等于一个子图像的均方误差。六、变换编码六、变换编码3、变换编码几个关键问题 变换的选择 对变换的评价 子图尺寸的选择 压缩的位分配（编码）六、变换编码六、变换编码基本理论基本理论n变换的选择(1)Karhunen-Loeve变换(KLT)(2)离散傅立叶变换（DFT）(3)离散余弦变换（DCT）(4)Walsh-Hadamard变换（WHT）(5)离散小波变换(DWT)六、变换编码六、变换编码几个关键问题几个关键问题n对变换的评价按信息封装能力排序： KLT，DCT，DFT，WHT，HaarT但KLT的基图像是数据依赖的，每次都要重新计算Huv。因而很少使用。 DFT的块效应严重。常用的是DCT，现已被国际标准采纳，作成芯片。其优点有： (1) 基本没有块效应。 (2) 信息封装能力强，把最多的信息封装在最少的系数中。六、变换编码六、变换编码几个关键问题几个关键问题n子图尺寸的选择子图尺寸的选择有两个原则：(1)如果n是子图的维数，n应是是2的整数次方的整数次方。为便于降低计算复杂度。(2)n一般选为8x8或16x16，可由试验得到。(3)随着n的增加，块效应相应减少。六、变换编码六、变换编码几个关键问题几个关键问题六、变换编码六、变换编码几个关键问题几个关键问题n压缩位的分配（编码）定义：截取、量化、系数编码统称为位分配。主要解决m(u,v)的设计、编码问题。截取和量化一般有两种方法：(1)子带编码。(2)阈值编码(适应性编码)。1 1 1 1 1 0 0 01 1 1 1 0 0 0 01 1 1 0 0 0 0 01 1 0 0 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0可消去87.5%的系数的模板六、变换编码六、变换编码几个关键问题几个关键问题(1)子带编码基本思想： 所有子图像使用相同的编码模板。六、变换编码六、变换编码几个关键问题几个关键问题(a) 大部分的信息应该包含在最大方差的变换系数中。u每一个DCT变换系数被认为是一个随机变量；u该变量的分布可以在所有变换子图像的集合上进行计算。 (b) 在(N/n)2个子图找出取最大方差的m个系数的位置。u同时确定了系数的坐标u和v；u对所有子图像，这m个系数的T(u,v)值是保留的，其他的T值被抛弃；um是一个可选常数。六、变换编码六、变换编码几个关键问题几个关键问题n算法的实现1计算模板：方差最大的地方置1，其它地方置0;2量化系数：例如最优Lloyd-Max量化器;3结果编码：有两种分配二进制位的编码方法： 系数被赋予相同数量的二进制位; 系数之间固定地分配一定的二进制位。8764321076543210654331104433210033321100221110001110000000000000六、变换编码六、变换编码几个关键问题几个关键问题例如： 系数之间固定地分配一定的二进制位的用位模板。六、变换编码六、变换编码几个关键问题几个关键问题(2)阈值编码(适应性编码)基本思想：没有一个取舍系数的固定模板。不同的子图保留不同的系数。通过一个阈值T，来决定一个系数的去留。 If a(系数) T(阈值) m(u,v) = 1 else m(u,v) = 0 由于其简单性，阈值编码是实际应用中经常使用的编码方法。1 1 0 1 0 0 0 01 1 1 1 0 0 0 01 1 0 0 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0六、变换编码六、变换编码几个关键问题几个关键问题n理论根据(1)取值最大的变换系数，在重构子图的质量中起的作用也最重要。(2)最大系数的分布随子图的不同而不同。六、变换编码六、变换编码几个关键问题几个关键问题n算法的实现(1)所有子图使用同一个全局阈值。压缩率的大小随图像的不同而不同。由超过全局阈值的系数的个数所决定。1.阈值的选取，常有三种取法。(2)对每个子图使用不同的阈值。每个子图保留的系数的个数事先确定，即总保留N个最大的。称为N-最大化编码。对于每个子图同样多的系数被丢弃。因此，每个子图的压缩率是相同的，并且是预先知道的。16 11 10 16 24 40 51 6112 12 14 19 26 58 60 5514 13 16 24 40 57 69 5614 17 22 29 51 87 80 6218 22 37 56 68 109 103 7724 35 55 64 81 104 113 9249 64 78 87 103 121 120 10172 92 95 98 112 100 103 99六、变换编码六、变换编码几个关键问题几个关键问题(3)阈值作为子图系数位置的函数。所有子图使用同一个全局阈值模板，但阈值的选取，与系数的位置相关，阈值模板给出了不同位置上系数的相应阈值。例如：六、变换编码六、变换编码几个关键问题几个关键问题2、对系数的编码(1) 将系数按45度对角顺序展开成序列，得到有一个有长串为零的序列。 例： -19 -20 5 21 6 0 0 0 0 0 0 0 0 0(2) 用RLE编码对上述序列编码。015614152728247131626294238121725304143 9111824314044531019233239455254202233384651556021343747505659613536484957586263六、变换编码六、变换编码几个关键问题几个关键问题n 对系数编码的展开顺序zig-zag排序主要内容uu编码编码及信息及信息及信息及信息论论概述概述概述概述uu行程行程行程行程编码编码uuLZWLZW编码编码uu霍夫曼霍夫曼霍夫曼霍夫曼编码编码uu预测编码预测编码uu变换编码变换编码uu压缩标压缩标准准准准简简介介介介* *七、压缩标准简介七、压缩标准简介n图像压缩标准JPEGJointPhotographicExpertsGroupMPEGMovingPictureExpertsGroup静止帧黑白、彩色压缩(JPEG)连续帧单色、彩色压缩(MPEG)(1) JPEG(1) JPEG压缩标准压缩标准有三种压缩系统：(1)基线编码系统：面向大多数有损压缩的应用，采用DCT变换压缩。(2)扩展编码系统：面向递进式应用，从低分辨率到高分辨率逐步递进传递的应用。(3)独立编码系统：面向无损压缩的应用，采用无损预测压缩，符号编码采用哈夫曼或算术编码。一个产品或系统必须包括对基线系统的支持。符号解码器DCT逆变换量化器DCT正变换构造8x8的子图输入图像NN符号编码器压缩图像压缩的图像合成8x8的子图解压图像颜色空间转换零偏置转换颜色空间转换零偏置转换JPEGJPEG压缩标准压缩标准nJPEG压缩流程MPEG1/2/4/7MPEG1/2/4/7标准标准MPEG1/2/4/7标准由ISO/IEC制定的。ISO(International Organization for Standardization)是国际标准化组织。IEC(International Electrotechnical Commission)是国际电工委员会，是非政府性国际组织，是世界上成立最早的专门国际标准化机构,正式成立于1906年。nMPEG的第一个成果MPEG-1于1992年推出，是VCD的基础。由于有限的352288像素分辨率，MPEG-1只适用于家庭环境，获得的视频质量及数据率相当低。n1995推出MPEG-2。720576的像素以及更高的分辨率大大提高了视频质量。n1999年12月发布了MPEG-4。nMPEG-7为多媒体内容描述接口标准。 从MPEG组织成立至今，其任务和方向都发生了很多变化。MPEG-1和MPEG-2已经是成熟的编码标准，现在的热点主要集中在MPEG-4 和 MPEG-7上。MPEG1/2/4/7MPEG1/2/4/7标准标准n 简介MPEG1/2/4/7MPEG1/2/4/7nMPEG1 视频CD_ROM存储、视频消费。DCT变换前向、双向运动补偿预测Zig-zag排序霍夫曼编码、算术编码每15帧至少要有一个I帧应用范围：编码技术MPEG1/2/4/7MPEG1/2/4/7DCT变换前向、双向运动补偿预测zig-zag排序霍夫曼编码、算术编码每15帧至少要有一个I帧编码技术应用范围：数字电视、高质量视频、有线电视、视频编辑、视频存储。 nMPEG2MPEG1/2/4/7MPEG1/2/4/7应用范围：互联网、交互视频、移动通信。DCT变换、小波变换前向、双向运动补偿预测zig-zag排序脸部动画、背景编码霍夫曼编码、算术编码每15帧至少要有一个I帧编码技术nMPEG4MPEG1/2/4/7MPEG1/2/4/71998年10月被提出，它的正式名称是“多媒体内容描述借口”。其用途非常广泛：即可用于存储(在线或离线)，也可应用于流式结构(如广播、将模型假如Internet)。还可用于实时或非实时环境下。 nMPEG7q音视数据库的存储和检索；q广播媒体的选择（广播、电视节目）；q因特网上的个性化新闻服务；q智能多媒体；q教育领域的应用；q远程购物；q社会和文化服务；q调查服务q遥感；q监视；q生物医学应用；q建筑、不动产及内部设计等。MPEG-7MPEG-7的应用领域的应用领域H.261/263/264H.261/263/264nH.261/263H.261/263标准是由CCITT(国际电话与电报咨询委员会)制定的。CCITT现在被称为ITU-T(国际标准化组织电讯标准化分部)，是世界上主要的制定和推广电讯设备和系统标准的国际组织.它位于瑞士的geneva。H.261/263/264H.261/263/264应用范围：ISDN视频会议。DCT变换前向运动补偿预测zig-zag排序脸部动画、背景编码霍夫曼编码编码技术运动补偿nH.261H.261/263/264H.261/263/264应用范围：可视电话。DCT变换双向运动补偿预测zig-zag排序脸部动画、背景编码霍夫曼编码编码技术nH.263H.261/263/264H.261/263/264H.264是ISO/IECMPEG(运动图像专家组)与ITU-T(视频编码专家组)组成的JVT(联合视频组）提出的新视频编码标准，并于2003年5月确定为国际标准。同时还作为MPEG-4的PART10(称为为MPEG4AVC)。nH.264H.261/263/264H.261/263/264nH.264H.264视频编解码标准的压缩效率可以达到以往标准(如H.263或MPEG-4)的1.52倍，与H.263标准相比,H.264采用了许多新技术，如对44点残差数据块进行整数变换L采用44点整数变换,计算复杂度低,峰值信噪比(PSNR)却只降低0.02Db。主要内容uu编码编码及信息及信息及信息及信息论论概述概述概述概述uu行程行程行程行程编码编码uuLZWLZW编码编码uu霍夫曼霍夫曼霍夫曼霍夫曼编码编码uu预测编码预测编码uu变换编码变换编码uu压缩标压缩标准准准准简简介介介介* *本章作业本章作业1、已知符号,其出现的概率分别是0.1,0.4,0.06,0.1,0.04,0.3,对其进行哈夫曼编码，给出码字、码字的平均长度和编码效率。nImagecompression:图像压缩nImagecoding:图像编码nEncoding:编码nDecoding:解码，译码nCryptography:密码学nDecompression:解压nEncoder:编码器nDecoder:解码器nRedundant:冗余的TermsnIrrelevant:不相干的nCompressionratio:压缩比nDictionary-basedencodingtechniques:基于字典的编码技术nStatisticalencodingmethod:统计编码方法nLosslessimagecompression:无损图像压缩nReversibleencoding:可逆编码nError-freeencoding:无误差编码nInformationpreservingencoding:信息保持编码TermsnLossyimagecompression:有损图像压缩nFidelity:保真度nEncodingmodel:编码模型nInformation:信息nSourceofmessages:信源，消息源nMemorylesssourceofmessages:无记忆信源nMemorysourceofmessages:有记忆信源nEntropy:熵TermsnHuffmancoding:霍夫曼编码nBcode:B码nShiftcode:移位码nRun:行程nRunlengthencoding(RLE):行程编码nContourencoding:轮廓编码nLZWalgorithm:Lemple-Ziv-Welch编码nIsoprefrencecurves:等值线，等优线nFreemanschaincode:Freeman链码TermsnMapping:映射nScalarquantization:标量量化nRatedistortiontheory:率失真理论nDaterate:数据率nDistortion:失真度nRatedistortionfunction:率失真函数nReconstructionerror:重构误差nTransformimageencoding:变换图像编码nBlockencoding:块编码TermsnBitallocation:位分配，比特分配nDifferentialencoding:微分编码nPredictiveencoding:预测编码nPredictor:预测器nPredictivecoefficient:预测系数nDifferentialpulsecodemodulation(DPCM):微分脉冲编码调制nHybridencoding:混合编码TermsnSubbandcoding:子带编码nKarhunen-Loevetransform:卡洛变换nK-Ltransform:卡洛变换nSingularvaluedecompositiontransform:奇异值分解变换nSVDtransform:奇异值分解变换nEigenvalue:特征值nEigenvector:特征向量nHartleytransform:哈特雷变换TermsnHadamardtransform:哈达玛变换nWalshtransform:沃尔什变换nSlanttransform:斜变换nHaartransform:哈尔变换nMarkovprocess:马尔科夫过程nCovariancematrix:协方差矩阵Terms