lecture08-数据压缩I

1、多媒体数据压缩向辉山东大学计算机学院2009年秋季10:14:50多媒体技术数据压缩2本章内容n数据压缩概念n无损压缩算法n数字音频压缩n数字图象压缩nMPEG系列标准10:14:50多媒体技术数据压缩3数据压缩概念nThe process of reducing the amount of data required to represent a given quantity of information.nTo find a way to represent the original image without or with imperceptible distortion with t

2、he minimum number of bits possiblenRD = 1 - 1/CR where CR = n1/n2 nn1 and n2 denote the number of information carrying units in two data sets that represent the same information nRD is relative data redundancy of the first data set nCR is compression ratio10:14:50多媒体技术数据压缩4出发点nhuge volume of the dat

3、anTextn1 page with 80 characters/line and 64 lines/page andn1 byte/char results in 80 * 64 * 1 * 8 = 40 kbit/pagenStill imagen24 bits/pixel, 512 x 512 pixel/image results in 512 x 512 x 24 = 8 Mbit/imagenAudionCD quality, sampling rate 44,1 KHz, 16 bits per sample results in 44,1 x 16 = 706 kbit/s s

4、tereo: 1,412 Mbit/snVideonFull-size frame 1024 x 768 pixel/frame, 24 bits/pixel, 30 frames/s results in 1024 x 768 x 24 x 30 = 566 Mbit/snMore realistic: 360 x 240 pixel/frame, 360 x 240 x 24 x 30 = 60 Mbit/s10:14:50多媒体技术数据压缩5数据压缩的一般思路n利用数据的数据冗余nTake advantage of patterns in the signal.nDescribe fre

5、quently occurring events efficientlynLossless coding: completely reversiblen引入适当的误差n删除对人的感知系统不重要的信息n根据不同的应用场合选择合适的时间、空间以及幅度等分辨率n有损编码：引入不可恢复的误差10:14:50多媒体技术数据压缩6重要参考书nThe Data Compression Book- (Imprint: M & T Books) (Imprint: M & T Books) (Publisher: IDG Books Worldwide, (Publisher: IDG Book

6、s Worldwide, Inc.) Inc.) Author: Mark Nelson Author: Mark Nelson ISBN: 1558514341ISBN: 1558514341 10:14:50多媒体技术数据压缩7典型系统Data Compression = Modeling + Coding 10:14:50多媒体技术数据压缩8模型n统计模型统计模型n基于对每个字符出现次数的统计得到字符概基于对每个字符出现次数的统计得到字符概率的率的n字典模型字典模型nsdusdu山东大学山东大学n使用一本字典，随着输入信息的读入，模型使用一本字典，随着输入信息的读入，模型找出输入信息在字

7、典中匹配的最长的字符串，找出输入信息在字典中匹配的最长的字符串，然后输出该字符串在字典中的索引信息然后输出该字符串在字典中的索引信息 10:14:50多媒体技术数据压缩9统计模型n静态统计模型：预先扫描文件中的所有字符，统计出每个字符出现的概率n自适应模型n随着字符不断被输入和编码，统计并修正已经出现过的字符的概率并用于对后续字符的编码n随着压缩的进行，他会越来越接近字符概率的准确值，并达到理想的压缩效果n自适应模型还可以适应输入信息中字符分布的突然变化，可以适应不同的文件中的字符分布而不需要保存概率表 10:14:50多媒体技术数据压缩10字典模型n匹配越长，压缩效果越好n字典模型本质上仍然

8、是基于对字符概率的计算的n使用整个字符串的匹配代替了对某一字符重复次数的统计n可以证明，字典模型得到的压缩效果仍然无法突破熵的极限 n静态字典与自适应字典10:14:50多媒体技术数据压缩11压缩算法类型n无损压缩无损压缩Lossless CompressionLossless Compressionninformation preservingn有损压缩有损压缩LossyLossy Compression CompressionnHybrid codingHybrid codingn包含无损与有损的步骤包含无损与有损的步骤nJPEGJPEG，MPEGMPEG，H.26xH.26x等等nNea

9、r-Lossless CompressionNear-Lossless Compression10:14:50多媒体技术数据压缩12无损压缩n指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同n无损压缩用于要求重构的信号与原始信号完全一致的场合n根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/21/4n一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)压缩算法n一个很常见的例子是磁盘文件的压缩10:14:50多媒体技术数据压缩13有损压缩n是指使用压缩后的数据进行重构，重构后的数

10、据与原来的数据有所不同，但不会让人对原始资料表达的信息造成误解n有损压缩适用于重构信号不一定非要和原始信号完全相同的场合n压缩比可高达100：1甚至更高n考虑人的生理与心理感知特性，例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比n算法：DPCM，DCT，DWT，VQ，Sub-band编码等10:14:50多媒体技术数据压缩14无损 vs 有损10:14:50多媒体技术数据压缩15信息熵nEntropy(熵)的概念n熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小n某个事件的信息量用Ii=-log2pi表示， 其中pi为第 个事件的概率，0 pi 4A2Bnnrun length encoding is lossless and has fixed length codewords10:14:50多媒体技术数据压缩34Run length encodingnworks best for images with solid backgroundnsuch as cartoo