02-信息处理技术基础

北京交通大学电子信息学院1第2章：信息处理技术基础卢燕飞课程：《多媒体信息处理和传输技术》北京交通大学电子信息学院2信息压缩编码的基本过程数字化：把媒体信息变化为数字的方式采样和量化编码：以编码的方式来变现数字化的内容编码的基本理论：香农理论编码的主要方法分类无损编码：熵编码有损编码：熵压缩编码北京交通大学电子信息学院3第一节：数字化：采样和量化采样和量化是一个信源数字化的过程；用空间或时间函数表示的物理量；电信号；数字量——bit；数字化的过程：采样：时间（空间）的离散化；量化：信号幅度的离散化；编码：以最佳的方式保存量化值，变为码字；北京交通大学电子信息学院41.1采样对模拟信号在时间或空间上进行离散化一个模拟信号的一般表示：S=f(t),S=f(x,y,z),S=f(x,y,z,t)对于f(t)，以时间间隔Ts采样，采样值为f(nTs);–其中：Ts称为采样周期，fs＝1/Ts为采样频率；采样定理：如果对某一模拟信号进行采样，则采样后可还原的最高信号频率分量只有采样频率的一半，或者说只要采样频率高于输入信号最高频率的两倍，就能从采样信号系列重构原始信号。fs=2f或者Ts=T/2其中f为被采样信号的最高频率。北京交通大学电子信息学院5图像采样的一个例子北京交通大学电子信息学院61.2量化量化就是要在幅度上离散化采样值的取值范围为无穷；要把对采样值的表示限定在一定范围之内，就要量化；量化分为：标量量化和向量（矢量）量化北京交通大学电子信息学院71.标量量化标量量化：对单个样本或单个参数的幅值进行量化(1)均匀量化（线性量化）等间隔对采样值进行量化；过载：输入超过最大值或最小值；颗粒噪声：输入值在范围之内,量化误差在量化间隔的一半以内;北京交通大学电子信息学院8(2)非均匀量化针对均匀量化的局限性量化误差的绝对值较平稳，相对值差异较大；不同样本概率分布采用相同的策略；非均匀量化的策略小样本值，量化步长小，大样本值，量化步长大；–PCM编码中的A律和μ律；小概率值，量化精度低，大概率值，量化精度高；北京交通大学电子信息学院9图像像素量化的一个例子北京交通大学电子信息学院10使得量化器达到最佳效果压缩效果：尽量好失真效果：尽量小实现方法：客观准则：最小均方误差量化器主观准则：对人感觉敏感的数据提高量化精度；对人感觉不敏感的数据降低量化精度；一个概念：最佳量化二者相互矛盾北京交通大学电子信息学院112.矢量量化定义：对样本值进行数据分组，每组K个数，构成一个K维矢量，然后以矢量为单元，逐个矢量进行量化，称为矢量量化VQ矢量量化的基本过程K0i模式0模式I模式k数据流矢量0数据流矢量1数据流矢量n原始数据流码本量化后的数据北京交通大学电子信息学院12码本码本搜索（发送端）查表（接收端）传送向量在码表中最佳匹配的索引矢量量化的编解码框图输出矢量输入矢量•码本的确定和匹配原则的确定是矢量量化的难点；北京交通大学电子信息学院13利用矢量量化进行编码北京交通大学电子信息学院14利用矢量量化进行编码北京交通大学电子信息学院15第2节：压缩编码的基本理论压缩编码的理论基础是——信息论。从信息论的角度看,压缩就是：去掉信息中的冗余,即保留不确定的信息,去除确定的信息(可推知的)；也就是用一种更接近信息本质的描述来代替原有冗余的描述。这个本质的东西就是信息量(即不确定因素)。北京交通大学电子信息学院16信息量的计算例如要从256个数中选定某一个数可以先提问“是否大于128？’，不论回答是与否，则半数的可能事件被取消。如果继续询问下去，每次询问将对应一个1bit的信息量。随着每次询问，都将有半数的可能事件被取消，这个过程由下列公式表示：log2256＝8bit从公式看出，对于256个数的询问只要进行8次，即可确定一个具体的数。设从N个数中选定任意一个数x的概率为产p（x）．假定选定任意一个数的概率都相等，即p（x）=1/N，则信息量为：)]([)(/1)(logloglog222xpIxpNNxI北京交通大学电子信息学院17举个例子，对下面这条只出现了abc三个字符的字符串：aabbaccbaa，字符串长度为10，字符a,b,c分别出现了5,3,2次，则abc在信息中出现的概率分别为0.5,0.3,0.2，他们的熵分别为：Ea=-log2(0.5)=1Eb=-log2(0.3)=1.737Ec=-log2(0.2)=2.322整条信息的熵也即表达整个字符串需要的位数为：E=Ea*5+Eb*3+Ec*2=14.855位如果按照常规处理，需要多少位（bit）？北京交通大学电子信息学院18第二节：无损编码对于多媒体数据压缩编码的方法根据其解码后信息量有无损失，分为：有损编码无损编码也叫冗余压缩或熵编码，目的是去除数据中的冗余（相关性）；压缩前的数据＝＝解码后的数据主要用于文本和数据压缩；北京交通大学电子信息学院19有损编码和无损压缩北京交通大学电子信息学院202.1无损编码的基础根据信息论的原理可以找到的最佳数据压缩编码方法；数据压缩的理论极限是信息熵；信息与熵信息是用不确定性的度量来定义；熵就是这种度量信息熵编码原理Shannon理论认为，无失真编码的极限就是信源中包含的熵；如何理解？熵编码的方法Huffman、游程编码、算术编码等；北京交通大学电子信息学院212.2变长编码1、什么是变长编码定长码（fixed-lengthcode）：采用相同的位数（bit）对数据进行编码。大多数存储数字信息的编码系统都采用定长码。–如我们常用的ASCII码就是定长码，其码长为1（Byte）。汉字国标码也是定长码，其码长为2（Byte）。变长码（variable-lengthcode）采用不相同的位数（bit）对数据进行编码，以节省存储空间北京交通大学电子信息学院22变长编码应用场合：编码各事件出现的概率是不同的，有的出现的概率非常高，有的则非常低。根据统计，英文字母中“E”的使用概率约为13％，而字母“Z”的使用概率则为0.08％。编码策略：对经常出现的事件数据指定较少的位数表示，对不常出现的事件指定较多的位数表示。用这种方法得到的代码，其码的位数，也即码长就是不固定的，故称为变长码。总体的效果是节省了存储空间。北京交通大学电子信息学院23Huffman编码Huffman编码是最常用的一种变长编码方法；其核心是用变长的码字来表示不同发生概率的事件确定表示不同概率事件的码字是关键；这种码字的特点是：在码字集合中任一码字都不能是其他码字的字头；举例：事件ABCD发生概率40%35%15%10%定长编码00011011北京交通大学电子信息学院24A：40%B：35%C：15%D：10%25%60%100%101001表示各事件的码字分别是：A-1、B-00、C-010、D-011编码方法：•将事件按照概率递减排列；•将最小两个概率相加，得到一个新的概率，重复第一步，直到概率和为1（终点）；•对每次组合的上边指定为1，下边为0（也可以相反）；•画出每个事件到终点的路径，路径从终点到事件源点所经过的01码就是编码值；北京交通大学电子信息学院25HUFMAN编码性能分析假设：以上事件发生100次；采用定长编码：总码长＝每事件码长＊100=200；每事件的码长为2bit/symbol采用Huffman编码：总码长=40*1+35*2+15*3+10*3=185平均每事件的码长=1.85bit/symbol熵的计算E=-0.4log2（0.4）-0.35log2(0.35)-0.15log2(0.15)-0.1log2(0.1)=1.808从熵的角度分析：可见变长编码的作用北京交通大学电子信息学院26补充讨论编码:a:0b:100c:101d:110e:111根据熵的知识，使用我们学到的计算方法，上面的例子中，每个字符的熵为：Ea=-log2(16/40)=1.322Eb=-log2(7/40)=2.515Ec=-log2(6/40)=2.737Ed=-log2(6/40)=2.737Ee=-log2(5/40)=3.00040个码的信息熵为：E=Ea*16+Eb*7+Ec*6+Ed*6+Ee*5=86.601也就是说，表示该条信息最少需要86.601位。我们看到，Shannon-Fano编码和Huffman编码（40个码需要88位）都已经比较接近该信息的熵值了北京交通大学电子信息学院27霍夫曼编码是变长编码的最常用的一种；基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的霍夫曼码表。实际应用中，霍夫曼编码也常与别的编码方法一起结合起来使用。如把霍夫曼编码与增量调制编码结合起来对图像进行编码，得到的压缩比要比采用单一的编码方法所得的压缩比高，效果更好。北京交通大学电子信息学院28算术编码算术编码的特点不需要huffman编码的码表，具有自适应能力；较为复杂；在JPEG,JBIG中得到应用；基本原理：也是基于概率分布的一种变长编码北京交通大学电子信息学院29编码前提条件编码过程中信源符号的概率分布不变；基本的实现方法根据信源符号概率分布在0～1之间划分；对于第一个信源码确定所在区间，接下来的信源码在前面确定的区间内再进行划分确认；依次进行；最后对确定的区间所代表的实数进行编码；北京交通大学电子信息学院30算术编码举例映射到实线的范围为[0,1]概率的排列顺序可以随意但是解码时必须保持相同的排列顺序各个符号被分成不同的部分:1:[0,0.8):0,0.799999…92:[0.8,0.82):0.8,0.819999…93:[0.82,1):0.82,0.999999…9北京交通大学电子信息学院31编码：输入符号为1321编码终止:Encodethelowerend(0.7712)tosignaltheend.难点:1.对于长的符号序列编码时需要很高的精度；2.只有整个序列都被处理后才有输出北京交通大学电子信息学院32编码过程的PseudoCode程序low=0.0,high=1.0;while(notEOF){n=ReadSymbol();RANGE=HIGH-LOW;HIGH=LOW+RANGE*CDF(n);LOW=LOW+RANGE*CDF(n-1);}outputLOW;此程序中有3个主要参数：low，high和range，只需知道两个就可以。CDF是该符号的概率分布函数；北京交通大学电子信息学院33算术编码解码过程缺点:每一步都需要重新计算所有的门限值北京交通大学电子信息学院34一种简单的解码方法每一次的比较都在[0,1]范围进行；不需要重新计算门限；rangelowxx解码公式：北京交通大学电子信息学院35Huffman和算术编码比较HuffmanCoding:TheRetiredChampion用码字来代替输入的符号需要概率分布难以适应变化的统计特性需要存储码字表最小码字的长度是1bitArithmeticCoding:TheRisingStar用浮点数代替完整的输入自适应编码实现容易不需要保存和发送码字表可以实现小于1的码字长度总体效果：算术编码可以得到更接近熵的编码效果，目前在一些新的图像编码算法中采用；北京交通大学电子信息学院362.3其他无损编码方法1.行程编码（runlengthcode）基本的思路：用重复数据的行程和一个重复数据来表示所有的重复数据；例如：0000111117777777777444444444可以记做:(4,0)(5,1)(10,7)(9,4)广泛的应用于：一般的数字图像压缩；文件数据压缩在传真标准中得到了广泛的应用；