第5章多媒体数据压缩技术文库.

1、第5章多媒体数据压缩技术5.1数据压缩基本原理多媒体信息的数据量数据压缩条件数据冗余5.2数据压缩算法数据压缩算法分类雷夫曼编码 JPEG编码51数据压缩基本原理5.1.1多媒体信息的数据量文本若1024 X 768显示分辨率、16X16点阵文字、4 Byte/字，则一屏 汉字的总数据战为：(1024/16)X(768/16)X4= 12288 By2 (12KB)图像若采用1024X768显示分辨率，则满屏图像的总数据量为： 1024X768Xlog2 256 二 786432 Byte (768 KB)音频若采样频率为441(M)Hz, 16bit (2Byte),立体声(2声道)，则1分

2、钟的总数据量为：44100X2 Byte X 2 (STEREO) X60s= 10336 KB (10MB)5.1.2数据压缩条件数据存在冗余（重复数据、可忽略数据）不敏感因素（颜色、亮度、频率、细节）«重复数据口J忽略数据（ 45.1 kHz/Stereo 1.3MB 22.0kHz/Nomo 0.3MB Stop J数据传输与存储空间的限制（压缩T传输或存储-解压缩）513数据冗余冗余基本概念冗余信息所具有的各种性质中多余的无用空间冗余度一多余的无用空间的程度信息量与冗余的关系I = D duI倍息量D数据量du 冗余量，包含在D中冗余举例播音员 180字/分钟，2Byte个字

3、，36（）Byte （合（L35KB/分钟） 音频数据 kH乃釆样X«bitX60秒=3«4（KBit （合4X0KB/分钟）冗余分类1空间冗余-规则物体的物理相关性声音频率12时间冗余一一-视频与动IBI面间的相关性3统计冗余一-具有空间冗余和时间冗余文字组句4结构冗余一-规则纹理、相互重叠的结构表面色彩渐交5信息埔冗余-编码冗余，数据与携带的信息主观意识6视觉冗余一-视觉、听觉敏感度和非线性感觉|7知识冗余一-凭借经验识别 “m其他冗余-上述7种以外的冗余52数据压缩算法521数据压缩算法分类无损圧缩编码圧缩数据还原后，与原始数据一致.无损失有损压缩编码一压缩后再还原的

4、数据有损失无损压缩编码（可逆编码）霍夫曼编码行程编码算术编码有损压缩编码（不可逆编码）预测编码PCM/ADPCM混合编码JPEG / MPEGXZ对称压缩压缩的算法和解压缩的算法一样不对称压缩压缩和解压缩的运算速率互不相同5.2.2霍夫曼编码霜夫曼编码一无损编码编码原理出现频率高的数据编码长度短，反之亦然 LU源的数据按照出现概率递减的顺序排列2 合并两个最小出现概率，作为新数据出现概率3 車复进行12,直至槪率相加为1为止4 合并运算时，概率大者取1,概率小者取05 记录槪率为1处到信源的“、1序列编码特点【II编码长度可变，压缩与解压缩较慢2 硬件实现困难3 编码效率取决于信号源的数据出现

5、概率霍夫曼编码示例设有6个符号的信源X= (Xj. X2. X, X, X" X6)其概率分布P=p (X,) 0.40, 0.26, 0.15, 0.1(), 0.06, 0.03佑源符弓X0.40Xi0.26AT,Xa0 06.1"60030 10.5010100.090I 1 0.190103401)6010阳字0001111111011100111码长（伤123455霍夫曼编码示例523香农范诺编码香农范诺(Shannon-Fannon)编码也是一种典世的可变字长编码。 与哈夫曼编码相似，当信源符号出现的概率正好为2的负幕次方时, 香农范诺编码的编码效率可以达到10

6、0%。香农范诺编码的理论基础是符号的码字长度Ni完全由该符号山 现的概率来决定，对于二进制编码即有：-!og2+1 > >-log7 pi编码步骤：(1) 将信源符号按其出现的概牢由大到小顺序排列，若两个符号的概 率相等，则相等概率的字符顺序可以任意排列；(2) 根据编码式计算出各槪率符号所对应的码字长度Ni；(3) 将各符号的概率累加，计算累加概率P,即：=0=Po=p, PPo + Pi + PlPo + Pl + Pl = E-I + Pl(4) 把各个累加概率P由十进制转换为二进制；(5) 根据编码式取二进制累加概率前Ni位的数字，并省去小数点前的 “0严字符，即为对应信源

7、符号的香农范诺编码码字。编码举例例：设一幅灰度级为8的图像中，各灰度 级分别用 SO. SI. S2. S3、S4、S5、S6、 S7表示，对应的概率分别为0. 40. 0. 18.0. 10、0. 10、0. 07. 0. 06、0. 05. 0. 04。 现对其进行编码。编码步骤如下 (1)将信源符号按其出现概率由大到小顺序排列, 为0. 40, 0. 18, 0. 10, 0. 10, 0. 07, 0. 06, 0. 05, 0. 04; (2)对于概率0. 40对应的符号S°,计算N0=2,将 累加概率0. 00转换位二进制小数为0. 00,取前 %=2位，并去除小数点前的

8、字符，即S。字符编码 为00； (3)对于概率0. 18对应的符号S,计算N=3,将 累加概率040转换位二进制小数为00110,取前 N=3位，并去除小数点前的字符，即S】字符编码 为 011; (4)对于概率0. 10对应的符号S2，计算2=4,将 累加概率0. 58转换位二进制小数为0. 10010,取前 %=4位，并去除小数点前的字符，即S?字符编码 为1001; (5)对于概率0. 10对应的符号S3,计算N3=4,将 累加概率0. 68转换位二进制小教为0. 10100,取前 血=4位，并去除小数点前的字符，即S3字符编码 为 1010; (6)对于概率007对应的符号S4,计算N

9、4=4,将 累加概率0. 78转换位二进制小数为0. 11000,取前 儿=4位，并去除小数点前的字符，即为字符编码 为 1100; (7)对于概率0. 06对应的符号计算N.=5,将 累加概率085转换位二进制小数为01101100,取 前=5位，并去除小数点前的字符，即乂字符编 码另11011; (8)对于概率005对应的符号S6，计算N6=5,将 累加概率0. 91转换位二进制小数为0. 1110100,取 前=5位，并去除小数点前的字符，即S6字符编 码为11101; (9)对于概率0. 04对应的符号S?,计算N7=5,将 累加概率0. 68转换位二进制小数为011110100, 取

10、前叫=5位，并去除小数点前的字符，即S?字符 编码为11110;香农范诺编码效能图像信息爛为丹一匕血2几Ar=O2.55 (2)平均码字长度为R =Bk pk =2x0.40 + 3x0.18 + 4x0.10 + 4x0.10 +日4x0.07 + 5x0.06 + 5x0.05 + 5x0.04= 3.17效率为：” ="x 1()0% = 2,55 = 80.4%R3.17信息兀余度为。=1- = 19.6%根据 变长最佳编码定理，Shannon-Fano编码步 骤如下：(1 )将信源中符号xi按其出现的概率，由大到 小顺序排列。(2)将信源分成两部分，使两个部分的概率和 尽可

11、能接近。重复第(2)步直至不可再分，即每一 个叶子只对应一个符号。(3 )从左到右次次为这两部分标记0, 1。(4 )将各个部分标记的0, 1串接起来就得到各 信源符号所对应的码字例结果灰度级出现概率码才码长si0.4002S20. 15100. 1511023S50. 1251113L = 22 p（.v/）/=2.2755.2.4行程长度编码4.:行程： 具有相同灰度值的像素序列。-编码思想:去除像素冗余。用彳亍程的灰度牙口彳亍程的长度代簪行程本身。 例:设重复次数为iC,童复像素值为iP编码为：iCiPiCiPiCiP编码前:bbbhbb编码后：7 6H8由于一

12、 4SB9像中有许多創I色相同的图块.用一整数对存储一*卜 像素Q颜色值及相冋颇色像素S数目(长度)。例如：(G, L) 编码时采用从左到右，从上到下的排列,f § 每为遇到一串相同数拯时就用该数据及岳 匝复次数代替原來的数据串。000000003333333333222222222226666666111111111111111111111111555555555555(0,8)(3,10) (21)67)(1,18) (1,6) (5,12) (8,18)(54) (3,4) 18)8888888888888888885555555555555533332222222222222

13、22222对于有大面积色块的 图像.压缩效果彳艮好"直观，经济，是一种无 损压缩对于纷杂的图像，压 缩效果不交子，最坏情 况下，会加倍图像适佥行卷貓磚的国525算术编码从理论上分析，采用哈夫曼编码可以获得 最佳信源字符编码效果；实际应用中，由于信源字符出现的概率并 非满足2的负幕次方，因此往往无法达到 理论上的编码效率和信息压缩比；算术编码的特点算术编码是信息保持型编码，它不像哈夫曼编码, 芜禽为一个符号设定一个厲字；算术编码分为固定方式和自适应方式两种编码；选择不同的编码方式，将直接影响到编码效率；自适应算术编码的方式，无需先定义概率模型， 适合于无法知道信源字符概率分布的情况；当

14、信源字符出现的概率比较接近时，算术编码效 率高于哈耒曼编码的效率，在图像通信中常用它 来取代哈夫曼编码；实现算术编码算法的硬件比哈夫曼编码复杂。编码原理算术编码方法是将被编码的信源消息表示成01 之间的一个间隔，即小数区间，消息越长，编 码表示它的间隔就越小；以小数表示间隔，表示的间隔越小所需的二进 制位数就越多，码字就越长。反之，间隔越大， 编码所需的二进制位数就少，码字就短。算术编码将被编码的图像数据看作是由多个符 号组成的字符序列，对该序対逐扫地进行算采 运算后，成为一个二进制分数；接收端解码过程也是算术运算，由二进制分数 重建图像符号序列。编码举例设图像信源编码可用a、b、c. d这4

15、个符 号来表示，若图像信源字符集为dacba, 信源字符出现的概率分别如下表所示， 采用算术编码对图像字符集编码。信源字符 a出现概率 0. 40. 2 0. 20. 2算术编码的基本步骤 (1)根据已知条件和数据可知，信源各字符在区间0, 1内的子区间间隔分别如下:a=0. 0 , 0. 4)b=0. 4 , 0. 6)c= 0. 6 , 0. 8)d= 0. 8 , 1. 0)(2)计算中按如下公式产生新的子区间：Start N = Start H + L曲( x LEndn = StartB + Rightc x L(4)第2个被压缩的字符为“犷，由于其前 (3)第1个被压缩的字符为“旷

16、，其初始子 区间为0.8 , 1. 0)面的字符取值区间为0. 8 , 1.0)范围，因 此，字符“a”应在前一字符区间间隔0. 8 ,10)的0.0 , 0. 4)子区间内，根据公式可 得：Starts =0. 8+0. 0 x (1. 0-0. 8)=0. 8Endn =° 8+0. 4 x (1. 0-0. 8)=0. 88 (5)第3个被压缩的字符为“c",由于其 前面的字符取值区间为08 , 0. 88)范 围内，因此，字符“c”应在前一字符区 间间隔0.8 , 0. 88)的0.6 , 0.8)子区 间内，根据公式可得：Startn =0. 8+0. 6 x (

17、0. 88-0. 8)=0. 848EndN =0. 8+0 8 x (0. 88-0. 8)=0. 864 (6)第4个被压缩的字符为由于其前 面的字符取值区间为0. 848 , 0. 864)范围 内，因此，字符“b”应在前一字符区间间隔 0. 848 , 0. 864)的0. 4 , 0.6)子区间内， 根据公式可得：Start弋=° 848+0. 4 x (0. 864-0. 848)=0. 8544End* =0. 848+0. 6 x (0. 864-0. 848)=0. 8576 (7)第5个被压缩的字符为“a二 由于其前 面的字符取值区间为0. 8544 , 0.8)

18、范围 内，因此，字符“矿应在前一字符区间间隔 0. 8544 , 0. 8576)的0 0 , 0.4)子区间 内，根据公式可得：Ssrt=0. 8544+0. 0 x (0. 8576-0. 8544)=0. 8544EndN =0. 8544+0. 4 x (0. 8576-0. 86544)=0. 85568经过上述计算，字符集dacba）被描述在 实数0. 8544 , 0. 85568）子区间内，即 该区间内的任一实级1值都惟一对应该符 序列dacba;因此，可以用0. 8544 , 0. 85568）内的 一个实数表示字符集dacba。 0. 8544 , 0. 85568)子区间的二进制表示形式为: 0. 1101101010000110 , 0. 1101101100001101);在该区间内的最短二进制代码为0. 11011011,去掉 小数点及其前的字符，从而得到该字符序列的算术 编码为1101101E算术编码可以通过硬件电路实现，在上述乘法运算, 可以通过右移来