多媒体技术ppt好资源-第03讲多媒体数据压缩基础_第1页
多媒体技术ppt好资源-第03讲多媒体数据压缩基础_第2页
多媒体技术ppt好资源-第03讲多媒体数据压缩基础_第3页
多媒体技术ppt好资源-第03讲多媒体数据压缩基础_第4页
多媒体技术ppt好资源-第03讲多媒体数据压缩基础_第5页
已阅读5页,还剩54页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、123(1)数据压缩的必要性图像信号:黑白480360,8bit;大小是480 3601024=168.45KB彩色大小是480 36031024=506.25KB视频:PAL制每秒数据量506.25KB25帧/秒=12.36MB/s(2)数据压缩的可能性空间冗余时间冗余结构冗余视觉冗余知识冗余信息熵冗余45(1 1)空间冗余)空间冗余静态图像静态图像中存在的最主要的一种数据冗中存在的最主要的一种数据冗余余在同一幅图像中,规则物体和规则背景在同一幅图像中,规则物体和规则背景的表面物理特性具有相关性的表面物理特性具有相关性即对同一景物表面上采样点的颜色之间即对同一景物表面上采样点的颜色之间存在着

2、空间连贯性存在着空间连贯性例如:图像中一片连续的区域,其像素例如:图像中一片连续的区域,其像素为相同的颜色为相同的颜色空间冗余空间冗余6(2 2)时间冗余)时间冗余序列图像序列图像( (电视图像、动画电视图像、动画) )和语音数据中所经常包含的和语音数据中所经常包含的冗余冗余一组连续的画面之间往往存在着时间和空间的相关性一组连续的画面之间往往存在着时间和空间的相关性例如:唱歌的歌手、两人谈话时背景一致等例如:唱歌的歌手、两人谈话时背景一致等7(3 3)统计冗余)统计冗余 是空间冗余和时间冗余的总称。在数据处理是空间冗余和时间冗余的总称。在数据处理时,往往采用统计事件出现概率的办法来鉴别空时,往

3、往采用统计事件出现概率的办法来鉴别空间冗余和时间冗余,因此空间冗余和时间冗余具间冗余和时间冗余,因此空间冗余和时间冗余具有统计特性。有统计特性。8(4 4)结构冗余)结构冗余在某些场景中,存在着明显的分布模式在某些场景中,存在着明显的分布模式结构结构结构可以通过特定的过程来生成结构可以通过特定的过程来生成例如:方格状的地板,蜂窝,砖墙等例如:方格状的地板,蜂窝,砖墙等9(5 5)信息熵冗余)信息熵冗余信息熵:一组数据所携带的信息量。信息熵:一组数据所携带的信息量。冗余的产生是因为:在信源符号的表示冗余的产生是因为:在信源符号的表示过程中未遵循信息论下最优编码而造成。过程中未遵循信息论下最优编码

4、而造成。通过熵编码进行压缩通过熵编码进行压缩10(6 6)视觉冗余)视觉冗余可以根据这些视觉特性来对图象信息进行取舍可以根据这些视觉特性来对图象信息进行取舍人类的视觉系统对图像场的敏感性:非均匀和非线性的人类的视觉系统对图像场的敏感性:非均匀和非线性的对亮度变化敏感,而对色度的变化对亮度变化敏感,而对色度的变化相对不敏感相对不敏感在高亮度区,人眼对亮度变化敏感在高亮度区,人眼对亮度变化敏感度下降度下降对物体边缘敏感,内部区域相对不对物体边缘敏感,内部区域相对不敏感敏感对整体结构敏感,而对内部细节相对整体结构敏感,而对内部细节相对不敏感对不敏感11(7 7)知识冗余)知识冗余有许多图像的理解与某

5、些有许多图像的理解与某些基础知识有相当大的相关基础知识有相当大的相关性性这类规律性的结构可以由先验知这类规律性的结构可以由先验知识和背景知识得到识和背景知识得到例如:人脸的图像例如:人脸的图像知识冗余是模型编码的基础知识冗余是模型编码的基础12多媒体数据压缩的性能指标多媒体数据压缩的性能指标13多媒体数据压缩的性能指标多媒体数据压缩的性能指标14(3) 数据压缩编码分类 无损压缩无损压缩 指使用压缩后的数据进行重构(或者叫做还原,解压缩),重构后的数据与原来的数据完全相同。 无损压缩算法一般压缩比24。 常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv &

6、 Welch)压缩算法。 有损压缩有损压缩 指使用压缩后的数据进行重构,重构后的数据与原来的数据有所不同,但不影响人对原始资料表达的信息造成误解。 图像和声音的压缩就可以采用有损压缩,因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息,丢掉一些数据而不至于对声音或者图像所表达的意思产生误解,但可大大提高压缩比。15压缩技术分类通用数据压缩(均为无损压缩)多媒体数据压缩(无损和有损压缩)基于统计模型的压缩技术基于字典模型的压缩技术Huffman编码算术编码LZ77LZ78LZW图像压缩音频和视频压缩MPEG等二值图像CCITTJBIG等灰度图像FELICSJPEG等彩色图像RLE编

7、码JPEG等矢量图像PostScriptWMFCAD等1617压缩编码分类(按长度) 等长编码等长编码 ASCII编码编码 不等长编码不等长编码 编码长度是不等长的编码长度是不等长的 常见编码如常见编码如Huffman编码编码18等长与不等长编码 例如:符号序列x=“aa bb cccc dddd eeeeeeee”采用ASCII编码: a=01100001 b=01100010 c=01100011 d=01100100 e=01100101 空=00100000等长编码:24*8=192bit如用后3位进行编码只需要3*24=72bit 压缩比为:压缩比为:72/192=19等长与不等长编

8、码 不等长编码方法 字符 次数 概率 码字 字长 E81/301 D41/61003 C41/61013 空41/61103 a21/12 1110 4 B21/12 1111 4需要空间:1*8+3*4+3*4+3*4+2*4+2*4=60平均码长平均码长=总位数/字符出现次数=60/24=2.520不等长码唯一性问题 字符码1码2码3 A000 B101001 C11011011 D1110 01111对序列010110译码码1abc码2daca或ddb或abca码3bca21(1)信息熵与信息量信息量信息量是指从N个相等的可能事件中选出一个事件所需要的信息度量或含量,也就是在辨识N个事件

9、中特定的一个事件的过程中所需要提问“是或否”的最少次数。 设从N个数中选定任一个数xj的概率为p(xj),假定选定任意一个数的概率都相等,即p( xj )1/N,因此定义其信息量为:P(xj)是信源X发出xj的概率。I(xj)的含义是,信源X发出xj这个消息(随机事件)后,接收端收到信息量的量度。)()(loglog/1log)(222jjjxpIxpNNxI22(1)信息熵与信息量来源于40年代由Claude Shannon创立的信息论中的一条定理,这一定理借用了热力学中的名词“熵”( Entropy )来表示一条信息中真正需要编码的信息量。信源S发出的xj(j=1,2,n)共n个随机事件的

10、自信息统计平均,即H(X)称为信源X的“熵”,即信源X发出任意一个随机变量的平均信息量。其中:等概率事件的熵最大,为:当P(x1)1时,P(x2)P(x3)P(xj)0,由(4-6)式得此时熵为由上可得熵的范围为:由上可得熵的范围为:njjjjxPxPxIESH12)(log)()()(NNNSHNj221log1log1)(0)(log)()(121xPxPSHNSH2log)(023平均码长与熵关系在编码中用熵值来衡量是否为最佳编码。若以Lc表示编码器输出码字的平均码长,则当LcH(S) 有冗余,不是最佳。LcH(S) 不可能。LcH(S) 最佳编码(Lc稍大于H(S))。熵值为平均码长L

11、c的下限。平均码长Lc的计算公式为其中:P(xj) 是信源X发出xj的概率,L(xj)为xj的编码长。njjjcxLxPL1)()((j=1,2,n)24熵的计算范例例:对信息aabbaccbaa,字符串长度为 10,字符a、b、c分别出现了5、3、2次,则 Ia=-log2(0.5)=1 Ib=-log2(0.3)=1.737 Ic=-log2(0.2)=2.322H(S)= 0.5Ia +0. 3Ib +0. 2Ic =1.4855 如采用等长编码,则每个字符需要位;总的码长: L=5*+3* +2* = 位对比一下,我们用ASCII编码表示该信息需要80位25统计编码(熵) 统计编码是根

12、据消息出现概率的分布特性而进行的压缩编码 在消息和码字间找到明确的一一对应关系,以便恢复时能准确无误再现出来26技术准备:编码通过模型,我们可以确定对某一个符号该用多少位二进制数进行编码。现在的问题是,如何设计一种编码方案,使其尽量精确地用模型计算出来的位数表示某个符号。前缀编码规则:任何一个符号的编码都不是另一个符号编码的前缀。最简单的前缀编码字符字符编码编码A0B10C110D1110E1111011110111100010 D A B B D C E A A B 27Shannon-Fano编码 采用从上到下的方法进行编码。 仙农-范诺(Shannon- Fano)算法: 首先按照符号出

13、现的频度或概率排序, 使用递归方法分成两个部分,每一部分具有近似相同的次数(概率) 当概率和为1,进行编码28Shannon-Fano编码例 有一幅40个象素组成的灰度图像,灰度共有5级,分别用符号A、B、C、D和E表示,40个象素中出现灰度A的象素数有15个,出现灰度B的象素数有7个,出现灰度C的象素数有7个等等。如果用3个位表示5个等级的灰度值,也就是每个象素用3位表示,编码这幅图像总共需要120位。符 号ABCD E出现的次数157765H(S) = (15/40)* (40/15) + (7/40)* (40/7) + + (5/40) * (40/5) =2.196这就是说每个符号用

14、2.196位表示,40个象素需用87.84位29Shannon-Fano编码例30Shannon-Fano编码例例题:例题:cabcedeacacdeddaaabaababaaabbacdebaceada 例子中的信息编码为:例子中的信息编码为:10 00 01 10 111 110 111 00 10 00 10 .码长共码长共91位,而使用位,而使用ASCII编码表示上述信息共需要编码表示上述信息共需要320位位a 16b 7c 6d 6e - 5 a 16b 7-c 6-d 6e - 5 a 00b 01c 10d 110e 111root0010111abcde031依据信源字符出现的

15、概率大小来构造代码,对出现概率较大的信源字符,给予较短码长,而对于出现概率较小的信源字符,给予较长的码长,最后使得编码的平均码字最短。32(2) 编码过程编码过程 出现频率高的数据编码长度短,反出现频率高的数据编码长度短,反之亦然之亦然1 信号源的数据按照出现概率递减的顺序排列信号源的数据按照出现概率递减的顺序排列 2 合并两个最小出现概率,作为新数据出现概率合并两个最小出现概率,作为新数据出现概率 3 重复进行重复进行12,直至概率相加为,直至概率相加为1为止为止4 合并运算时,概率大者取合并运算时,概率大者取0,概率小者取,概率小者取15 记录概率为记录概率为1处到信号源的处到信号源的0、

16、1序列序列编码特点编码特点 1 编码长度可变,压缩与解压缩较慢编码长度可变,压缩与解压缩较慢 2 硬件实现困难硬件实现困难 3 编码效率取决于信号源的数据出现概率编码效率取决于信号源的数据出现概率33 例4-1:设输入图像的灰度级a1,a2,a3,a4,a5,a6出现的概率分别是0.4、0.2、0.12、0.15、0.1、0.03。试进行哈夫曼编码,并计算编码效率、压缩比、冗余度。 编码步骤:编码步骤:(1 1)初始化,根据符号概率的大小按由)初始化,根据符号概率的大小按由大到小顺序对符号进行排序,如图大到小顺序对符号进行排序,如图4-24-2所示。所示。(2 2)把概率小的两个符号组成一个节

17、点,)把概率小的两个符号组成一个节点,如图如图4-24-2中的中的a5a5、a6a6组成节点组成节点P1P1。(3 3)重复步骤)重复步骤2 2,得到节点,得到节点P2P2、P3P3、P4P4、P5P5,形成一棵,形成一棵“树树”,其中,其中P5P5为根节点。为根节点。(4 4)从根节点)从根节点P5P5开始到相应于每个符号开始到相应于每个符号的的“树叶树叶”,从上到下标上,从上到下标上1 1(上枝)或者(上枝)或者0 0(下枝),至于哪个为(下枝),至于哪个为1 1哪个为哪个为0 0则无关紧要,则无关紧要,最后的结果仅仅是分配的代码不同,而代码最后的结果仅仅是分配的代码不同,而代码的平均长度

18、是相同的。的平均长度是相同的。最终编码结果为:最终编码结果为:a1 =1, a2 =000 , a1 =1, a2 =000 , a3 =011, a3 =011, a4 =001, a5 =0100, a4 =001, a5 =0100,a6 =0101a6 =0101 34由公式可求得图像信源熵是:H(X)= =-(0.4log20.4+0.2log20.2+0.12log20.12+0.15log20.15+0.1log20.1+0.03log20.03)=2.25 bit njjjxPxP12)(log)(根据哈夫曼编码过程图给出的结果,由公式(4-7)可求出它的平均码字长度:Lc=0

19、.41+0.23+0.153+0.123+0.14+0.034 =2.33压缩之前8个符号需要3个比特量化,经过压缩之后的平均码字长度为2.33,由公式(4-10)得其压缩比为:2 . 133. 23C35Huffman编码例题例题2:cabcedeacacdeddaaabaababaaabbacdebaceada 例子中的信息编码为:例子中的信息编码为:101 0 100 101 111 110 111 0 101 0 101 .码长码长88位,比位,比Shannon-Fano编码略短一些编码略短一些a 16b 7c 6d 6e - 5 a 0b 100c 101d 110e 111root

20、00111abcde00136整数位编码与信息熵cabcedeacacdeddaaabaababaaabbacdebaceada 该信息的熵经计算可知为86.601位符号符号理想位数理想位数(熵)(熵)S-F编码需编码需要位数要位数Huffman编编码需要位数码需要位数a1.32221b2.51523c2.73723d2.73733e3.00033总计总计86.601918837假设某个字符的出现概率为 80%,该字符事实上只需要 -log2(0.8) = 0.322 个二进制位进行编码难道真的能只输出 0.322 个 0 或 0.322 个 1 吗?算术编码的输出是:一个小数算术编码的输出是

21、:一个小数算术编码对整条信息(无论信息有多么长),其输出仅仅是一个数,而且是一个介于0和1之间的二进制小数。例如算术编码对某条信息的输出为1010001111,那么它表示小数0.1010001111,也即十进制数0.6438 算术编码(arithmetic coding AC)是利用0和1之间的间隔来表示信源编码的一种方法,其编码值是间隔的上、下限包含的相同二进制。编码过程中的间隔决定了符号压缩后的输出。 算术编码用到两个基本的参数:符号的概率和它的编码间隔。 信源符号的概率决定压缩编码的效率,也决定编码过程中信源符号的间隔,而这些间隔包含在0到1之间。39算术编码计算方法Low=low+ra

22、nge*range_low(symbol)high=low+range*range_high(symbol) 其中:Low是前一个符号的最低值;range是之前所有符号的概率积;range_low和range_high分别是当前符号的上下值;一般编码取最小值,采用乘2取整得到二进制编码。40例 假设信源符号为A, B, C, D,这些符号的概率分别为 0.1, 0.4, 0.2, 0.3 ,根据这些概率可把间隔0, 1分成4个子间隔:0, 0.1, 0.1, 0.5, 0.5, 0.7, 0.7, 1 ,如表符号ABCD概率0.10.40.20.3初始编码间隔0,0.1 0.1,0.50.5,

23、0.70.7,1表表 信源符号、概率和初始编码间隔信源符号、概率和初始编码间隔如果消息序列的输入为:CADACDB,其编码过程如下:首先输入的符号是C,找到它的编码范围是0.5, 0.7;由于消息中第2个符号A的编码范围是0, 0.1,因此它的间隔就取0.5, 0.7的第一个1/10作为新间隔0.5, 0.52;编码第3个符号D时取新间隔为0.514, 0.52;编码第4个符号A时,取新间隔为0.514, 0.5146,。41消息的编码输出可以是最后一个间隔中的任意数,整个编码过程如图。最后在0.5143876,0.514402中选择一个数作为编码输出值:0.5143876解码时,解码器由编码

24、输出值:0.5143876,可马上解得一个字符为C,然后依次得到唯一解A,D,A,C,D,B。42是一个针对包含有顺序排列的多次重复的数据的压缩方案。其原理就是把一系列的重复值用一个单独的值再加上一个计数值来取代,行程长度就是连续且重复的单元数目。如果想得到原始数据,只需展开这个编码就可以了。 例如,计算机制作图像中,常常具有许多颜色相同的图块,而且在行上都具有相同的颜色,或者在一行上有许多连续的像素都具有相同的颜色值。这时,就不需要存储每一个像素的颜色值,而仅存储一个像素的颜色值以及具有相同颜色的像素数目就可以,或者存储一个像素的颜色值,以及具有相同颜色值的行数,这种压缩编码称为行程编码。具

25、有相同颜色的连续的像素数目称为行程长度。 43十进制小数0.6875转换为二进制小数是?方法是?答案是?0.101144假定一幅灰度图像,第n行的像素值为:用RLE编码方法得到的代码为:3150841160。代码斜黑体表示的数字是行程长度,黑体字后面的数字代表像素的颜色值。例如黑体字50代表有连续50个像素具有相同的颜色值,它的颜色值是8。 w对比RLE编码前后的代码数可以发现,在编码前要用73个代码表示这一行的数据,而编码后只要用10个代码表示代表原来的73个代码,压缩前后的数据量之比约为7:1,即压缩比为7:1。这说明RLE确实是一种压缩技术,而且编码技术实用。45RLE的性能好坏主要取决

26、于图像本身的特点。RLE压缩编码尤其适用于计算机生成的图像,对减少图像文件的存储空间非常有效。然而,由于颜色丰富的自然图像在同一行上具有相同颜色的连续像素往往很少,而连续几行都具有相同颜色值的连续行数就更少,如果仍然使用RLE编码方法,不仅不能压缩图像数据,反而可能使原来的图像数据变得更大。 译码时按照与编码时采用的相同规则进行,还原后得到的数据与压缩前的数据完全相同。因此,RLE属于无损压缩技术。46词典编码属于无损压缩技术,其根据是数据本身包含有重复代码序列这个特性。词典编码的种类较多,归纳起来有两类:第一类词典编码的基本思想是查找正在压缩的字符序列是否在前面输入的数据中出现过,如果是,则用指向早期出现过的字符串的“指针”替代重复的字符

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论