当前位置:文档之家› 无损数据压缩

无损数据压缩

第4章 无损数据压缩

第4章无损数据压缩 数据压缩可分成两种类型,一种叫做无损压缩,另一种叫做有损压缩。 无损压缩是指使用压缩后的数据进行重构(或者叫做还原,解压缩),重构后的数据与原来的数据完全相同;无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平,无损压缩算法一般可以把普通文件的数据压缩到原来的1/2~1/4。一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)压缩算法。 有损压缩是指使用压缩后的数据进行重构,重构后的数据与原来的数据有所不同,但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如,图像和声音的压缩就可以采用有损压缩,因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息,丢掉一些数据而不至于对声音或者图像所表达的意思产生误解,但可大大提高压缩比。 本章主要介绍目前用得最多和技术最成熟的无损压缩编码技术,包括包含霍夫曼编码、算术编码、RLE编码和词典编码。对于不打算开发压缩技术和编写压缩程序的读者可不必深究编译码的详细过程。 4.1 香农-范诺与霍夫曼编码 香农-范诺编码算法需要用到下面两个基本概念: 1. Entropy(熵)的概念 1.熵是信息量的度量方法,它表示某一事件出现的消息越多,事件发生的可能性就越 小,数学上就是概率越小。 2.某个事件的信息量用表示,其中为第个事件的概率, 2. 信源S的熵的定义 按照仙农(Shannon)的理论,信源S的熵定义为 其中是符号在S中出现的概率;表示包含在中的信息量,也就是编码 所需要的位数。例如,一幅用256级灰度表示的图像,如果每一个象素点灰度的概率均为,编码每一个象素点就需要8位。

无损压缩算法的比较和分析

Adaptive-Huffman-Coding 自适应霍夫曼编码 压缩比:1.79 分析: 霍夫曼算法需要有关信息源的先验统计知识,而这样的信息通常很难获得,即使能够获得这些统计数字,符号表的传输仍然是一笔相当大的开销。 自适应压缩算法能够解决上述问题,统计数字是随着数据流的到达而动态地收集和更新的。概率再不是基于先验知识而是基于到目前为止实际收到的数据。随着接收到的符号的概率分布的改变,符号将会被赋予新的码字,这在统计数字快速变化的多媒体数据中尤为适用。 Lempel-Ziv-Welch 基于字典的编码 压缩比:1.86 分析: LZW算法利用了一种自适应的,基于字典的压缩技术。和变长编码方式不同,LZW使用定长的码字(本次实验使用12位定长码字)来表示通常会在一起出现的符号/字符的变长的字符串。 LZW编码器和解码器会在接受数据是动态的创建字典,编码器和解码器也会产生相同的字典。 编码器的动作有时会先于解码器发生。因为这是一个顺序过程,所以从某种意义上说,这是可以预见的。

算术编码(arithmetic coding) 压缩比:2 分析: 算术编码是一种更现代化的编码方法,在实际中不赫夫曼编码更有效。 算术编码把整个信息看作一个单元,在实际中,输入数据通常被分割成块以免错误传播。 算术编码将整个要编码的数据映射到一个位于[0,1)的实数区间中。并且输出一个小于1同时大于0的小数来表示全部数据。利用这种方法算术编码可以让压缩率无限的接近数据的熵值,从而获得理论上的最高压缩率。 比较分析: 一般来说,算术编码的性能优于赫夫曼编码,因为前者将整个消息看作一个单元,而后者受到了必须为每一个符号分配整数位的限制。 但是,算术编码要求进行无限精度的实数运算,这在仅能进行有限精度运算的计算机系统是无法进行的。随着研究的深入,有学者提出了一种基于整数运算的算术编码实现算法。在编码和解码的过程还需要不时的调整区间大小,以免精度不足,加大了实现的难度。 在3种无损压缩算法中,LZW算法相对来说,实现最为简单,但其压缩效果要在数据源足够大的时候,才能显现出来。

多媒体数据处理中几种无损压缩算法的比较概要

119 摘要:为了使大容量的多媒体数据在网 络上有效的传输,必须对多媒体数据进行压缩。对多媒体数据压缩中的几种无损压缩方法进行了比较,并对每种方法用一个例子说明。 关键词:数据压缩;霍夫曼树;LZW;二 叉树 引言 随着网络发展的速度越来越快,视频, 音频的广泛应用使得大数据量的传输显得尤为重要,如何更快、更多、更好地传输与存储数据成为数据信息处理的首要问题。 在压缩算法中分为无损压缩和有损压 缩。相对于有损压缩来说,无损压缩的占用空间大,压缩比不高,但是它100%的保存了原始信息,没有任何信号丢失并且音质高,

不受信号源的影响,这点是有损压缩不可比拟的。而且随着时间的推移,限制无损格式的种种因素将逐渐被消除,比如说硬盘容量的急剧增长以及低廉的价格使得无损压缩格式的前景无比光明。 1、无损压缩的原理以及几种常见算法 本质上压缩数据是因为数据自身具有冗 余性。数据压缩是利用各种算法将数据冗余压缩到最小,并尽可能地减少失真,从而提 高传输效率和节约存储空间。 常见的无损压缩算法有,游长编码;香 浓-凡诺算法;霍夫曼算法;LZW算法;下面 详细介绍这些算法或编码步骤,并比较其优缺点。 2、游长编码 也叫行程编码,它是数据压缩中最简单 的一种方法。它的思想是:将图像一行中颜色值相同的相邻象素用一个计数值和该颜色值来代替。例如:aabbbccccdddddeeeeee对

其进行游长编码可得2a3b4c5d6e,可见其效 率很高。但它有两个致命缺点。 一:如果图象中每两个相邻点的颜色 都不同,用这种算法不但不能压缩,反而数 据量会增加,例如对abcdeabcde进行编码得 1a2b3c4d5e1a2b3c4d5e,可见数据量反而增 加了1倍。 二:容错性差。还是以aabbbccccddddde eeeee为例,如果在第二位a出错,例如丢失 了a,那么编码后结果为1a3b4c5d6e,虽然只 有一位发生了错误,但是在恢复数据时,将 和原始数据完全不同。 所以说游长编码在要压缩信息源中的符 号形成连续出现片段时才有效,并且它不是一种自适应的编码方式。 3、香浓-凡诺算法香浓-凡诺算法由贝尔实验室的Shannon 和MIT的Robert Fano开发的。它的编码步骤如下:一:根据符号出现的频率对符号进行排序二:递归的把符号分成两部分,每一部分中的符号具有相似的频率,直到所有的部分只有一个符号为止。这样,就得到一颗二叉树,我们把树中的左支赋为0,把树中的右支赋为1。那么从根节点到节点的路径即为它的编码。例如:对字符串abcccd编码。进行排序后为cabd。递归过程图1-图3。应当指出香浓-凡诺算法的编码结果并不是唯一的,例如在图1的时候可以交换左右子树的位置,在图3的时候也可以交换b,d的位置。香

三种无损压缩原理介绍

三种无损压缩原理介绍 1.前言 现代社会是信息社会,我们无时无刻都在跟信息打交道,如上网查阅图文资料,浏览最新的新闻,QQ聊天或者传送文件等。人类对信息的要求越来越丰富,希望无论何时何地都能够方便、快捷、灵活地通过文字、语音、图像以及视频等多媒体进行通信。在早期的通信领域中,能够处理和传输的主要是文字和声音,因此,早期的计算机和通信设备的处理能力跟人类的需求有相当大的差距。随着通信信道及计算机容量和速度的提高,如今图像信息已成为通信和计算机系统的一种处理对象,成为通信领域市场的热点之一。可是,大数据量的图像信息会给存储器的存储容量、通信干线信道的带宽以及计算机的处理速度增加极大的压力。单纯依靠增加存储器容量、提高通信网络带宽和计算机处理速度来解决问题,在技术和经济上都不太现实。显然,在信道带宽、通信链路容量一定的前提下,采用编码压缩技术,减少传输数据量,是提高通信速度的重要手段。 2.正文 2.1图像压缩编码的现状和发展趋势 1948年提出电视数字化后,就开始对图像压缩编码技术的研究工作,至今已有50多年的历史。图像压缩的基本理论起源于20世纪40年代末香农的信息理论。香农的编码定理告诉我们,在不产生任何失真的前提下,通过合理的编码,对于每一个信源符号分配不等长的码字,平均码长可以任意接近于信源的熵。在五十年代和六十年代,图像压缩技术由于受到电路技术等的制约,仅仅停留在预测编码、亚采样以及内插复原等技术的研究,还很不成熟。1969年在美国召开的第一届“图像编码会议”标志着图像编码作为一门独立的学科诞生了。到了70年代和80年代,图像压缩技术的主要成果体现在变换编码技术上,矢量量化编码技术也有较大发展,有关于图像编码技术的科技成果和科技论文与日俱增,图像编码技术开始走向繁荣。自80年代后期以后,由于小波变换理论,分形理论,人工神经网络理论,视觉仿真理论的建立,人们开始突破传统的信源编码理论,例如不再假设图像是平稳的随机场。图像压缩编码向着更高的压缩比和更好

第五讲 数据压缩技术基础

第五讲数据压缩技术基础 5.1数据压缩的技术指标是什么? 1.数据压缩的目的 通过压缩手段把数据量压下来以压缩形式存储和传输,这样既节约了空间,又提高了传输速率,同时也使计算机可实时处理音频视频信息,以保证播放出高质量的音频、视频节目称为可能。 对图像的压缩编码有多种方法。如亚采样编码思想:一组像素可用一个像素表示以达到压缩图像存储容量。 又如游程编码思想:对黑白图像的编码,可将每行的像素分为白段、黑段、白段、黑段、白段…后,每段像素采用其长度(计数)表示:计数1,计数2,计数3,计数4,计数5,计数6…。实际上,一个好的编码系统都是采用多种算法、多次处理而成的。 2.数据压缩的基本理论 数据压缩是通过去除多媒体中冗余数据可大大减少原始数据量,从而使数据量得到压缩。信息论认为:若信源编码的熵(entropy)大于信源的实际熵,则该信源一定存在冗余。去除冗余不会减少信息量,仍可原样恢复数据;但若减少了熵,则数据不能完全恢复。不过在允许的范围内损失一定的熵,数据可得到近似的恢复。 所谓“熵”,原指热能除以温度所得的商,即热量转化为功的程度。这里是指信源发 出任意一个随机变量的平均信息量。所谓“信息量”是指从N个相等可能事件中选出一 个事件所需的信息度量。 3.原始数据的冗余类型 (1)空间冗余:同一帧画面中,规则景物和规则背景的表面各采样点的颜色之间存在 空间连贯性。 (2)时间冗余:在图像序列中,相邻帧图像之间同一场景所包含背景和移动物体具有 共同性。 (3)结构冗余:图像的像素值存在明显的分布模式结构产生的数据冗余。 (4)知识冗余:某些规律性结构可通过先验知识和背景知识得到的冗余。 (5)视觉冗余:人眼的视觉系统对图像场视觉的敏感和不敏感同等对待而产生了更多 数据冗余。 (6)区域相似性冗余:图像中的两个或多个区域所对应的像素值具有相似性使产生的 数据重复存储 (7)纹理的统计冗余:图像纹理在统计上服从某一分布规律的冗余。 4.压缩比 压缩比(%)=压缩后的图像数据量/ 压缩前的图像数据量 若原数字文件数据容量为100MB,经压缩后的数据容量为50MB,则图像压缩比为50%。 显然,压缩比越小,压缩后的图像文件数据量也越小,图像的质量有可能损失越多。实际 上,图像的压缩效果不但与压缩前的图像效果有关,也与采用的压缩方法有关。 5.数据压缩的技术指标 (1)压缩比:压缩前、后所需的信息存储量之比要大。

用C++实现数据无损压缩、解压(使用LZW算法)

用C++实现数据无损压缩、解压(使用LZW算法) 小俊发表于 2008-9-10 14:50:00 推荐 LZW压缩算法由Lemple-Ziv-Welch三人共同创造,用他们的名字命名。LZW就是通过建立一个字符串表,用较短的代码来表示较长的字符串来实现压缩。LZW压缩算法是Unisys的专利,有效期到2003年,所以对它的使用是有限制的。字符串和编码的对应关系是在压缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进行恢复,算是一种无损压缩。 个人认为LZW很适用于嵌入式系统上。因为:1、压缩和解压速度比较快,尤其是解压速度;2、占用资源少;3、压缩比也比较理想;4、适用于文本和图像等出现连续重复字节串的数据流。 LZW算法有一点比较特别,就是压缩过程中产生的字符串对应表,不需要保存到压缩数据中,因为这个表在解压过程中能自动生成回来。 LZW算法比较简单,我是按照这本书上写的算法来编程的:

以下是源代码:

class LZWCoder { private: struct TStr { char *string; unsigned int len; }; TStr StrTable[4097]; unsigned int ItemPt; unsigned int BytePt; unsigned char BitPt; unsigned char Bit[8]; unsigned char Bits; unsigned int OutBytes; void InitStrTable(); void CopyStr(TStr *d, TStr s); void StrJoinChar(TStr *s, char c); unsigned int InStrTable(TStr s); void AddTableEntry(TStr s); void WriteCode(char *dest, unsigned int b); unsigned int GetNextCode(char *src); void StrFromCode(TStr *s, unsigned int c); void WriteString(char *dest, TStr s); public: unsigned int Encode(char *src, unsigned int len, char *dest); unsigned int Decode(char *src, unsigned int *len, char *dest); LZWCoder(); ~LZWCoder(); }; void LZWCoder::InitStrTable() { unsigned int i; for(i = 0; i < 256; i ++) { StrTable[i].string = (char *)realloc(StrTable[i].string, 1); StrTable[i].string[0] = i; StrTable[i].len = 1; } StrTable[256].string = NULL; StrTable[256].len = 0; StrTable[257].string = NULL; StrTable[257].len = 0;

相关主题
相关文档 最新文档