数据压缩概述

数据压缩

DataCompression教材和参考书《数据压缩》，吴乐南编著，电子工业出版社第3版教材:参考书(Reference):

DavidSalomon著数据压缩原理与应用(电子工业出版社，2003年9月)KhalidSayood著数据压缩导论(人民邮电出版社，2009年8月)作业及考试形式闭卷考试课程成绩＝平时（40％）+期末（60％）数据压缩技术的分类

数据压缩的必要性

数据压缩的基本概念第一章绪论数据压缩的标准与应用数字传输系统模型解决可靠性问题，使处理过的信号在传输过程中不出错或少出错，即使出错也可以检错或纠错。本书的研究内容属于信源编码，信源编码的一个最主要的目的就是解决数据压缩的问题。

解决有效性问题，主要是对信源的压缩处理，用最少的数码传递最大的信息量。信道编码：信道编码/信道解码信源编码：信源编码/信源解码信源编码和信道编码UNIX下的COMPACT程序：Winzip、RAR等：JPEG、GIF：AVI、MPEG2、MPEG4：PostScript：Huffman编码基于字典模型的压缩技术（LZ77、LZ78、LZW算法）灰度、彩色图像的压缩矢量图像压缩声音视频信号的压缩实际应用如果你对数据的压缩原理感到惊讶和迷惑不解那么，这门课就给出了上述答案。课程包含详细的算法描述，以及进一步学习压缩技术的有效建议……如果你想知道上述的压缩工具是如何工作的如果你正要为自己的应用程序添加压缩/解压缩模块以最少的数据表示信源所发的信号，减少容纳给定消息集合或数据采样集合的信号空间：物理空间，如存储器、磁盘、磁带、光盘等数据存储介质；

时间空间，如传输给定消息集合所需的时间；电磁频谱区域，如为传输给定消息集合所要求的

带宽等。数据压缩的定义信号集合的空域、时域和频域空间，信号空间的几种形式是相互关联的，如存储空间的减少也意味着传输效率的提高和占用带宽的节省，只要采用某种方法来减少某一种信号空间，都能压缩数据。

数据压缩技术的分类

数据压缩的必要性

数据压缩的基本概念第一章绪论数据压缩的标准与应用数字传输系统的优点①数字传输质量高于模拟传输质量，经多次中继不引起严重的噪声累积，不受系统非线性影响②易于采用信道编码技术提高传输的可靠性③便于利用时分复用技术与其他通信业务相结合④易于数字加密，提高信息安全性⑤数字电路易于大规模集成⑥数字设备可靠性高，维护简便采用数字技术（或系统）具有许多优越性，但也使数据量大增。数字信号的传输速率或比特率I为：其中：数字化信号的取样频率，每个取样幅度值用R位二进制编码（Rbit）。可理解为：该信号在通信线路上每秒钟应传送的位数，或者保存一秒钟信号样值所需要占用的存储容量。当取样速率一定时，比特率(或数码率、码率、速率、数据率)也可简单地用R表示，意为每个样值Rbit。一般传输时多用I，存储时只用R。数据压缩的必要性数字音频格式取样率kHz样本精度bit频带Hz电话88300~3400AM广播11.0251650~7000激光光盘（CD）44.11620~20000数字音频磁带（DAT）481620~20000

数字视频信号格式数字电视格式图像分辨率(象素)每秒帧数样本精度bit通用中间格式（CIF）亮度信号352×288308CCIR601的亮度信号720×480/720×57630/258HDTV亮度信号一例1920×1080608数字化音频格式数字音视频格式数字音频、视频信号数据传输速率计算从传输角度：数字电话

一路广播级的彩色数字电视(若按4:2:2（亮度/色差/色差）的分量编码标准格式，用13.5/6.75/6.75MHz频率采样，每像素（pixel:pictureelement,简写为pel）用8位编码)：

等于3375路数字话路；

从存储角度：

512×512像素、8bit/pixel黑白图像：

512×512像素、每分量8bit/pixel的彩色图像：一幅2230×2230×8bit的气象卫星红外云图：B为字节低高数据量一颗卫星每半个小时即可发回一次全波段数据（5个波段），每天的数据率高达1.1GB多颗卫星？多波段？全天候？……不进行数据压缩，无论传输或存储都很难实用化，数据压缩的好处就在于：

较快地传输各种信源—

时间域的压缩；

开通更多的并行业务（电视、传真、电话、可视图文等）—

频率域的压缩；

降低发射机功率—

能量域的压缩；

紧缩数据存储容量—

空间域的压缩。

数据压缩的优势

数据压缩技术的分类

数据压缩的必要性

数据压缩的基本概念第一章绪论数据压缩的标准与应用图1.2数据压缩的一般步骤

建立一个数学模型，能够更紧凑或更有效地“重新表达”规律性不那么明显的原始数据；

把模型参数量化为有限的精度（二次量化，与原始数据的量化不同）；

对模型参数的量化表示或消息流进行码字分配，以得到尽可能紧凑的压缩码—“熵编码(EntropyCoding)”；

数据压缩的一般方法

预测，变换…可逆压缩(LosslessCompression)冗余度压缩：去除或减少那些可能是后来插入数据中的冗余度，是一个可逆过程。香农（C.E.Shannon）信息论：数据=信息+冗余度其他术语：无损压缩、无失真、无差错编码（ErrorFreeCoding）、无噪声（Noiseless）编码、冗余度压缩(RedundaryReduction)、熵编码(EntropyCoding)、数据紧缩(Datacompaction)、信息保持编码（Lossless,Bit-preserving）。

例1-4计算不同采样值间重复采样的数目(游程)，然后将变化的采样值与该重复数目一起发送。

Compression:

针对数据内部的多余信息进行压缩；

例1-512位A/D变换，通常采用2字节来存一个采样值，多出4位冗余度，改用3个字节存4个数据，可消除冗余度。Compaction

:针对数据外在冗余度进行压缩。

举例不可逆压缩(LossyCompression)又称:有失真（Lossy）压缩、熵压缩（EntropyCompression）。

例1-6

对采样值设置门限，当采样值超过该门限时才传输—原始采样值不可能恢复，信息丢失；举例：有失真压缩（茶叶粉末无法恢复出茶叶）例1-7

茶叶压缩的例子

，直观理解冗余度压缩——无失真压缩（茶叶保持完整）

外在冗余度：空气—数据紧缩

内在冗余度：水份—冗余度压缩

茶叶压成粉末——铁罐可以装得更多茶叶（“数据”）放入铁罐（“存储器”）一般结论 ①有冗余度就可以压缩 ②压缩只能在一定程度内可逆 ③超过一定限度，必然带来失真 ④允许的失真越大，压缩的比例也可以越大实用的数据压缩技术

数

据

压

缩

冗余度压缩（熵编码）

统计编码霍夫曼编码、游程编码、二进制信源编码等算术编码基于字典的编码：LZW编码等其他编码完全可逆的小波分解+统计编码等

熵压缩特征抽取

分析/综合编码子带、小波、分形、模型基等

量化其他无记忆量化均匀量化、Max量化、压扩量化

有记忆量化

序列量化预测编码增量调制、线性/非线性/自适应/运动补偿预测等其他方法序贯量化等

分组量化直接映射矢量量化、神经网络、方块截尾等

变换编码正交变换：KLT、DCT、DFT、WHT等非正交变换其他函数变换表1.2数据压缩技术的简单分类

数据压缩技术的分类

数据压缩的必要性

数据压缩的基本概念第一章绪论数据压缩的标准与应用数据压缩技术的发展历史早在1949年，贝尔实验室的ClaudeShannon

和MIT的R.M.Fano

几乎同时提出了的对符号进行有效编码从而实现数据压缩的Shannon-Fano编码方法。Shannon-Fano编码大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方法，可以降低这种冗余度。60年代、70年代乃至80年代的早期，数据压缩领域几乎一直被Huffman编码及其分支所垄断。UNIX系统上一个压缩程序COMPACT就是Huffman0阶自适应编码的具体实现。80年代初，Huffman编码又在DOS系统中实现，其代表程序叫SQ。1952年D.A.Huffman第一次发表了他的论文“最小冗余度代码的构造方法”(AMethodfortheConstructionofMinimumRedundancyCodes)。Huffman编码80年代，数学家们从新的角度入手，遵循Huffman编码的主导思想，设计出另一种更为精确，更能接近信息论中“熵”极限的编码方法—算术编码。

算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容。算术编码虽然可以得到最好的压缩效果，但却要消耗也许几十倍的计算时间。算术编码能不能既在压缩效果上超越

Huffman，又不增加程序对系统资源和时间的需求呢？

1977年之前，数据压缩的研究工作主要集中于熵、字符和单词频率以及统计模型等方面，1977年，以色列人JacobZiv和AbrahamLempel发表了论文“顺序数据压缩的一个通用算法”(AUniversalAlogrithemforSequentialDataCompression)。字典式编码字典式编码不但在压缩效果上大大超过了Huffman，而且，对于算法的实现，其压缩和解压缩的速度也异常惊人。

1978年，他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(CompressionofIndividualSequencesviaVariable-RateCoding)。在这两篇论文中提出的两个压缩技术被称为LZ77和LZ78。基于这一思路的编码方法被称作“字典”式编码。1984年，TerryWelch发表了名为“高性能数据压缩技术”(ATechniqueforHigh-PerformanceDataCompression)的论文，实现了LZ78算法的一个变种—LZW。LZW继承了LZ77和LZ78压缩效果好、速度快的优点，而且在算法描述上更容易被人们接受，实现也比较简单。不久，UNIX上出现了使用LZW算法的Compress程序，很快成为了UNIX世界的压缩程序标准。紧随其后的是MS-DOS环境下的ARC程序，还有象PKWare、PKARC等仿制品。LZ78和LZW一时间统治了UNIX和DOS两大平台。另外对于

GIF格式，GIF格式可以把原始图形文件以非常小数据量存储，可以在同一个文件中存储多幅图像从而实现动画效果。知道

GIF中的图像使用什么方法压缩的吗？LZW!GIF精确地保留了原始图像的每一个像素信息，是无损图像压缩的代表。当然，GIF文件中除了经过

LZW压缩的像素信息以外，还保存有图像的各种属性信息以及图像所使用的调色板信息等。80年代中期以后，人们对LZ77进行了改进，随之诞生了一批我们今天还在大量使用的压缩程序。LZ77得以和LZ78、LZW一起垄断当今的通用数据压缩领域。目前，基于字典方式的压缩已经有了一个被广泛认可的标准，从古老的PKZip到现在的WinZip，特别是随着Internet上文件传输的流行，ZIP格式成为了事实上的标准，没有哪一种通用的文件压缩、归档系统敢于不支持ZIP格式。现在对声音、图像、视频等多媒体信息的压缩有两条思路：要么采用成熟的通用数据压缩技术进行压缩；要么根据媒体信息的特性设计新的压缩方法。根据媒体特性量身定制的压缩方法中，游程编码(RLE:Run-LengthEncoding)是最为简单、最容易被想到的一种。大多数计算机中产生的图像(和现实世界的图像例如照片不同)都具有着大面积重复的颜色块，完全可以用一个颜色值加一个重复次数来表示这一块图像，冗余度由此减小了，这就是RLE方法的基本思路。显然，它不适于用来压缩照片、声音等很少连续重复信息的数据。游程编码70年代末80年代初，人们逐渐意识到，对到多数灰度或是彩色图像乃至声音文件，没有必要忠实地保留其所有信息，在允许一定的精度损失的情况下，可以实现更为有效的压缩方法。到80年代末，许多人已经在这一领域取得了不小的收获，设计出了一批在压缩效果上让人惊讶不已的声音和图像压缩算法。在此基础上，国际标准化组织(ISO)和CCITT联合组成了两个委员会：

静态图像联合专家小组(JPEG)JPEG的压缩目标是静止图像(灰度的和彩色的)，

动态图像联合专家小组(MPEG)MPEG的目标则是声音和视频他们的基本思路是完全一样的，即保留媒体信息中最有规律、最能体现信息主要特征的数据，而略去其他不重要的数据。主要数据压缩标准和应用标准化组织

国际标准化组织（InternationalOrganization

forStandardization,简称ISO）

是目前世界上最大、最具权威性的国际标准化专

门机构。国际电工委员会(InternationalElectrotechnical

Commission，简称IEC）是世界上最早的国际性电工标准化机构。国际电信联盟的电子标准部(InternationalTelecommunicationUnion，简称ITU）是联合国的一个专门机构，国际电信界最权威的标准修订组织。1972年12月,电信标准化部、无线电通信部和电信发展部承担着ITU的实质性标准制订工作。其中，电信标准化部门由原来的国际电报电话咨询委员会（CCITT）和国际无线电咨询委员会（CCIR）的标准化部门合并而成，其主要职责是实现国际电信联盟有关电信标准化的目标，使全世界的电信标准化。表1.3主要的数据压缩标准及其典型应用标准号俗称适用信源典型应用ITU-TT.82|ISO/IEC11544JBIG-1二值图像、图形G4传真机、计算机图形ISO/IEC14492JBIG-2二值图像、图形传真、WWW图形库、PDA等ITU-TT.81|ISO/IEC10918JPEG连续色调静止图像图像库、传真、彩色印刷、数码相机等ITU-TT.87|ISO/IEC14495JPEG-LS连续色调静止图像医学、遥感图像资料的无损