四川大学计算机学院多媒体基础无损压缩

多媒体技术基础四川大学计算机学院陈虎huchen@数字化原理1模拟信号模拟信号指幅度的取值是连续的（幅值可由无限个数值表示）。现实中涉及的许多媒体对象是模拟信号

例如：声音、图像、视频等数字信号数字信号是人为抽象出来的在时间上的不连续信号，是离散时间信号的数字化表示，通常由模拟信号获得。计算机处理的对象是数字信号（二进制数“0”

和“1”）

例如：英文字符以的ASCII代码，汉字字符的国标GB2312-80代码表示都是二进制数字串多媒体系统的数模与模数转换传感器(声音、图像、视频等--模拟）A/D计算机（数字）输出设备（数字）D/A输出设备（声音、电视--等模拟）模数转换-采样概念：

从连续时间信号中提取离散样本的过程；或者说在某些离散的时间点上提取连续时间信号值的过程称为采样。采样按采样间隔可分为:均匀采样与非均匀采样。采样的必要性

例如，电影的连续画面，实际上是由一组时间样本快速播放实现的，数字通信系统，微处理器系统对连续时间信号的处理，都是通过采样来实现的。采样是连续时间信号和离散时间信号之间的桥梁，对连续信号而言，随着数字处理技术的发展，越来越迫切地要求连续信号的离散化。采样示例采样当取出的样本一样时，样本对应的连续时间函数却不是唯一的。采样此外，对同一个连续时间信号，当采样间隔不同时也会得到不同的样本序列。结论：没有任何条件限制的情况下，从连续时间信号采样所得到的样本序列，不能唯一地确定原来的连续时间信号，即：一个连续时间信号必须在某一种条件下才能由其样本来表示。采样分析采样样本：采样函数：采样分析已采样信号的频谱：采样函数频谱：原连续时间信号：采样分析对连续时间信号在时域理想采样，就相当于在频域以采样频率s为周期延拓，幅值减小1/T。要使频谱不混迭，就必须使信号带限，且上述即为时域采样的约束条件从而我们得到怎样抽取样本，样本才能唯一地表征原信号的取样条件，下面为上述分析的一个完整总结－－采样定理。采样定理

设是某一个带限信号，在||>M时，X（j）=0。如果采样频率

s>2

M，其中

s＝2/T,那么就唯一地由其样本所确定。已知这些样本值，我们能用如下办法重建：让采样后的信号通过一个增益为T,截止频率大于M，而小于（s

M）的理想滤波器，该滤波器的输出就是。2

M称为奈奎斯特率；

M称为奈奎斯特频率。数据压缩2压缩的必要性音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。

例如：一幅中等分辨率（640×480）的真彩色图像（24b/像素），它的数据量约为0.9MB/帧，若要达到每秒25帧的全动态显示要求，每秒所需的数据量约为22MB。对于声音也是如此，CD音质的声音每秒将有约为172KB的数据量。信息论1948年C.E.Shannon香农发表了题为“通信的数学理论”的论文。运用通信技术与概率论、随机过程、数理统计的方法系统讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论：

1.阐明通信系统传递的对象就是信息

2.对信息给予科学的定量描述

3.提出了信息熵的概念信息论科学体系香农信息论压缩理论有失真信源编码无失真信源编码率失真理论压缩编码等长编码定理变长编码定理最优码构成Huffman码Fano码传输理论有噪声信道编码理论码构成纠错码代数编码卷积码网络信道网络信息理论网络最佳码保密理论保密系统的信息理论保密码信息论之父TheFatherofInformationTheory——

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA熵定义：设随机变量X，取值空间Ω，Ω为有限集合。X的分布密度为p(x)，p(x)=P(X=x)x∈X，则该随机变量的取值不确定程度，即其熵为：当使用log2时，熵的单位为比特反映一个信源发出不同信号，具有的平均信息量。熵为什么能够进行压缩

信息论认为：若信源编码的熵大于信源的实际熵，该信源中一定存在冗余度（信息熵冗余）。

冗余的基本概念

指信息存在的各种性质的多余度举例：（1）广播员读文稿时每分钟约读180字，一个汉字占两个字节；文本数据量为360B；（2）如果对语音录音，由于人说话的音频范围为20Hz到4kHz，即语音的带宽为4kHz，若设量化位数为8bit,则一秒钟的数据量为：

4×2×8=64kbit/s=8KB/s则一分钟的数据是480KB。360B480KB数据冗余的类别空间冗余时间冗余统计冗余信息熵冗余结构冗余知识冗余视觉冗余听觉冗余数据冗余的类别●空间冗余规则物体和规则背景的表面物理特性都具有相关性，数字化后表现为数据冗余。●时间冗余序列图像（如电视图像和运动图像）和语音数据的前后有着很强的相关性，经常包含着冗余。在播出该序列图像时，时间发生了推移，但若干幅画面的同一部位没有变化，变化的只是其中某些地方，这就形成了时间冗余。数据冗余的类别空间冗余和时间冗余是把图像信号看作概率信号时反应出的统计特性，因此，这两种冗余也被称为统计冗余。●统计冗余●信息熵冗余信息熵实际情况又称编码冗余。信息熵是指一组数所携带的信息量。●结构冗余数字化图像中的物体表面纹理等结构往往存在着冗余数据冗余的类别由图像的记录方式与人对图像的知识差异所产生的冗余称为知识冗余。●知识冗余

人类的视觉系统对于图像场的注意在非均匀和非线性的，视觉系统并不是对图像的任何变化都能感知。●视觉冗余

●听觉冗余

人耳对不同频率的声音的敏感性是不同的，并不能察觉所有频率的变化，对某些频率不必特别关注，因此存在听觉冗余。信息冗余从信息论关系中图像信息中冗余信息，如果一个图像的灰度级编码，使用了多于实际需要的编码符号，则该图像包含了信息冗余例：如果用8位表示下面图像的像素，我们就说该图像存在着编码冗余，因为该图像的像素只有两个灰度，用一位即可表示。统计冗余从统计的观点，某点像素的灰度与其邻域灰度有密切关系。因此任何给定的像素值，原理上都可以通过它的相邻像素预测到，单个像素携带的信息相对是小的。对于一个图像，很多单个像素对视觉的贡献是冗余的。例：原图像数据：234223231238235压缩后数据：23411-8-73空间冗余

规则物体表面有相关性，数字化后表现出冗余。图像相邻像素之间色彩、明度相同或相似，产生信息（有意义的内容）冗余时间冗余时间发生了推移，若干幅画面的同一部位没有变化，于是产生了冗余结构冗余

数字化图像中具有规则纹理的表面产生的冗余。取其中一块编码，其余只记录坐标视觉心理冗余一些信息在一般视觉的处理中比其它信息的相对重要程度要小，可以忽略不计，这种信息就被称为视觉心理冗余。33K15K数据压缩的评价-压缩比设：n1和n2是输入数据和输出数据

压缩比为：CR=n1/n2

例如：图像512×480，24位

输入＝(512×480×24)/8=737280B

输出15000B

压缩比＝737280/15000＝49

相对数据冗余： RD=1–1/CR=(n1-n2)/n2数据压缩的评价-压缩质量客观质量评价：压缩过程对信息的损失能够表示为原始信息与压缩并解压缩后信息的函数。（信噪比（SNR））例如，图像中

数据压缩的评价-压缩质量主观质量评价：以人的主观感受作为评价标准。例如：通过视觉比较两个图像，给出一个定性的评价，如很粗、粗、稍粗、相同、稍好、较好、很好等，可以对所有人的感觉评分计算平均感觉分来衡量。评分评价说明1优秀的优秀的具有极高质量的图像2好的是可供观赏的高质量的图像，干扰并不令人讨厌3可通过的图像质量可以接受，干扰不讨厌4边缘的图像质量较低，希望能加以改善，干扰有些讨厌5劣等的图像质量很差，尚能观看，干扰显著地令人讨厌6不能用图像质量非常之差，无法观看压缩解压缩速度算法复杂－压缩解压慢，压缩效果好算法简单－压缩解压快，压缩效果差在许多应用中，压缩和解压可能不同时用，在不同的位置不同的系统中。所以，压缩、解压速度分别估计。

例如静态图像中，压缩速度没有解压速度严格；动态图像中，压缩、解压速度都有要求，因为需实时地从摄像机或其他设备中抓取动态视频。压缩编码的分类数据压缩(datacompression)与信号编码(signalcoding)往往含义相同压缩(compress)解压缩/还原/重构(decompress)编码(encode/coding)解码/译码(decode)相关学科：信息论、数学、信号处理、数据压缩、编码理论和方法压缩编码的分类编码压缩的方法目前有很多，其分类方法根据出发点不同而有差异。一般根据根据解码后数据与原始数据是否完全一致将编码压缩分为：无损压缩编码有损压缩编码压缩编码的分类无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。图像、声音压缩编码的分类压缩有损压缩无损压缩行程编码LZW编码哈夫曼编码算术编码无损预测编码位平面编码有损预测编码分形编码模型编码子带编码神经网络编码变换编码K-L变换Haar变换Walsh.Hadamard变换离散余弦变换离散傅立叶变换斜变换小波变换压缩编码的分类从信息语义角度分为：熵编码、源编码和混合编码熵编码(entropyencoding)（也称平均信息量编码）

熵编码是一种泛指那些不考虑被压缩信息的性质的无损编码。它是基于平均信息量的技术把所有的数据当作比特序列，而不根据压缩信息的类型优化压缩。也就是说，平均信息量编码忽略被压缩信息的语义内容。如RLE（runlengthencoding行程编码）、LZW（Lempel-Ziv-Walch基于词典的编码算法）、Huffman编码。压缩编码的分类源编码(SourceCoding)

源编码的冗余压缩取决于初始信号的类型、前后的相关性、信号的语义内容等。源编码比严格的平均信息量编码的压缩率更高。当然压缩的程度主要取决于数据的语义内容，比起平均信息量编码，它的压缩比更大。简而言之，利用信号原数据在时间域和频率域中的相关性和冗余进行压缩的有语义编码。如：预测编码：DM、ADPCM变换编码：DCT、DWT分层编码：如子采样、子带编码其他编码：如矢量量化、运动补偿、音感编码压缩编码的分类混合编码(hybridcoding)

混合编码=熵编码+源编码大多数压缩标准都采用混合编码的方法进行数据压缩，一般是先利用信源编码进行有损压缩，再利用熵编码做进一步的无损压缩。如H.261、H.263、JPEG、MPEG等。压缩编码的分类此外，也可根据不同的依据对数据的压缩算法进行其它不同的分类，如：按作用域在空间域或频率域：空间方法、变换方法、混合方法按是否自适应：自适应性编码和非适应性（静态）编码按码长：定长码和变长码香农-范诺香农-范诺编码(Shannon–Fanocoding)在香农的源编码理论中，熵的大小表示非冗余的不可压缩的信息量在计算熵时，如果对数的底数用2，熵的单位就用“香农(Sh)”，也称“位(bit)”

。“位”是1948年Shannon首次使用的术语。最早阐述和实现“从上到下”的熵编码方法的人是Shannon(1948年)和Fano(1949年)，因此称为香农-范诺(Shannon-Fano)编码法香农-范诺编码举例有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A，B，C，D和E表示。40个像素中出现灰度A的像素数有15个，出现灰度B的像素数有7个，出现灰度C的像素数有7个，其余情况见表2-1(1)计算该图像可能获得的压缩比的理论值(2)对5个符号进行编码(3)计算该图像可能获得的压缩比的实际值符号ABCDE出现的次数157765出现的概率15/407/407/406/405/40香农-范诺编码举例理论值按照常规的编码方法，表示5个符号最少需要3位，如用000表示A，001表示B，…，100表示E，其余3个代码(101，110，111)不用。这就意味每个像素用3位，编码这幅图像总共需要120位。按照香农理论，这幅图像的熵为香农-范诺编码举例这个数值表明，每个符号不需要用3位构成的代码表示，而用2.196位就可以，因此40个像素只需用87.84位就可以，因此在理论上，这幅图像的的压缩比为120:87.84≈1.37:1，实际上就是3:2.196≈1.37香农-范诺编码举例(2)符号编码对每个符号进行编码时采用“从上到下”的方法。首先按照符号出现的频度或概率排序，然后使用递归方法分成两个部分，每一部分具有近似相同的次数香农-范诺编码举例（3）压缩比的实际值按照这种方法进行编码需要的总位数为30+14+14+18+15＝91，实际的压缩比为120:91≈1.32:1霍夫曼编码霍夫曼编码(Huffmancoding)霍夫曼(D.A.Huffman)在1952年提出和描述的“从下到上”的熵编码方法根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少广泛用在JPEG,MPEG,H.26X等各种信息编码标准中霍夫曼编码基本原理通过减少编码冗余来达到压缩的目的。统计符号的出现概率，建立一个概率统计表将最常出现(概率大的)的符号用最短的编码，最少出现的符号用最长的编码。霍夫曼编码具体步骤：步骤①：按照符号出现概率大小的顺序对符号进行排序步骤②：把概率最小的两个符号组成一个节点P1步骤③：重复步骤②，得到节点P2，P3，P4，……，PN，形成一棵树，其中的PN称为根节点步骤④：从根节点PN开始到每个符号的树叶，从上到下标上0(上枝)和1(下枝)，至于哪个为1哪个为0则无关紧要步骤⑤：从根节点PN开始顺着树枝到每个叶子分别写出每个符号的代码霍夫曼编码举例

aaaa

bbb

cc

d

eeeee

fffffff

432157（共22*8=176bits)霍夫曼编码举例

cbdafe7/225/224/222/22f=00e=10a=11b=011c=0100d=01011/221022/223/229/220113/22016/22103/2201编码形式不唯一4/22)*log2(22/4)+(3/22)*log2(22/3)+(2/22)*log2(22/2)+(1/22)*log2(22/1)+(7/22)*log2(22/7)+(5/22)*log2(22/5)＝2.3678霍夫曼编码举例aaaa

bbb

cc

d

eeeee

fffffff

（共22*8=176bits)432157

经过Huffman编码之后的数据为：11111111011011011010001000101101010101000000000000000(共7*2+5*2+4*2+3*3+2*4+1*4=53bits)

霍夫曼编码a10.20a20.19a30.18a40.17a50.15a60.10a70.01100.11100.2610.3500.610010110.391.00码字码长1021120003001301030110401114平均码长：2.72熵：2.58霍夫曼编码局限性利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限。输入符号数受限于可实现的码表尺寸译码复杂需要实现知道输入符号集的概率分布没有错误保护功能应用举例在图像的编码中首先计算频率并以二叉树方式进行排序来获得编码值，其次用编码值取代图像数据进入图像文件中。编码值的不唯一性灰度分布很不均匀和很均匀时的效率构造性差常用的且有效的方法是：将图像分割成若干的小块，对每块进行独立的Huffman编码。例如：分成8×8的子块，就可以大大降低不同灰度值的个数（最多是64而不是256）。应用举例8*8分块的编码效率为47.27%16*16分块的编码效率约为61%全图的编码效率为91.47%霍夫曼编码Huffman编码讨论Huffman编码是唯一可译码。短的码不会成为更长码的启始部分；Huffman编码的平均码长接近于熵缺点：需要多次排序，耗费时间算术编码Huffman编码的局限性：

Huffman编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为80%，该字符事实上只需要-log2(0.8)=0.322位编码，但Huffman编码一定会为其分配一位0或一位1的编码。可以想象，整个信息的80%在压缩后都几乎相当于理想长度的3倍左右。算术编码例1：在信源的符号数目很小的情况X:abP(X):0.90.1H=0.4690ab1a=0,b=1算术编码例2：信源的符号的概率严重不对称：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symbolHuffman编码：a 0b 11c 10l=1.05bits/symbol冗余（Redundancy）=l-H=0.715bits/sym(213%!)算术编码基本思想：考虑对两个字母序列而不是单个字母编码l=1.222/2=0.611冗余=0.276bits/symbol（27%）LetterProbabilityCodeaa0.90250ab0.0190111ac0.0285100ba0.01901101bb0.0004110011bc0.0006110001ca0.0285101cb0.0006110010cc0.0009110000算术编码该思想还可以继续扩展考虑长度为n的所有可能的mn

序列(已做了32)理论上：考虑更长的序列能提高编码性能实际上：字母表的指数增长将使得这不现实例如：对长度为3的ASCII序列：2563=224=16M需要对长度为n的所有序列产生码本很多序列的概率可能为0分布严重不对称是真正的大问题：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symboll1=1.05,l2=0.611,…当n=8时编码性能才变得可接受但此时|alphabet|=38=6561!!!算术编码基本思想：算术编码不是将单个信源符号映射成一个码字，而是把整个消息表示为实数线上的0到1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。采用算术编码每个符号的平均编码长度可以为小数算术编码符号串编码：将串中使用的符号表按原编码（如字符的ASCII编码、数字的二进制编码）从小到大顺序排列成表。计算表中每种符号si出现的概率pi，然后依次根据这些符号概率大小pi来确定其在[0,1)期间中对应的小区间范围[xi,yi)：其中，p0=0，显然，符号si所对应的小区间的宽度就是其概率pi算术编码输入串编码：设串中第j个符号cj为符号表中的第i个符号si，则可根据si在符号表中所对应区间的上下限xi和yi，来计算编码区间

Ij=[lj,rj)。其中，dj=rj-lj为区间Ij的宽度，初值l0=0，r0=1，d0=1。显然，lj↑而dj与rj↓。串的最后一个符号所对应区间的下限ln就是该符号串的算术编码值.算术编码通常，对任意序列x=x1x2…xn只需知道信源的cdf，即信源的概率模型算术编码：编码和解码过程都只涉及算术运算（加、减、乘、除）

举例2字符概率a0.3b0.7aba要编的字符串算术编码010.3aba[0,0.3)b[0.3,1)1.划分范围2.开始编码“aba”00.3ab第一个为a，编码范围限制在0～0.3范围内1算术编码00.30.09ab00.3ab1对已知区间进行再次分割第二个为b，编码范围限制在0.09～0.3范围内00.30.09ab算术编码0.090.30.153ab0ab0.3对已知区间进行再次分割第3个为a，编码范围限制在[0.09,0.153)范围内0.090.090.153ab0.3算术编码在[0.09,0.153)中任选一个浮点数来标识这个区间，如0.15，即可表示我们要编的消息为“aba”把该浮点数转变为二进制编码:0010特性：区间越窄，说明符号串越长，二进制码长越长举例2假设信源符号为{00,01,10,11}，它们的概率分别为{0.1,0.4,0.2,0.3}对二进制消息序列10001100101101…进行算术编码算术编码初始化：根据信源符号的概率把间隔[0,1)分成如表2-4所示的4个子间隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)。其中[x,y)的表示半开放间隔，即包含x不包含y，x称为低边界或左边界，y称为高边界或右边界

符号00011011概率0.3初始区间[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)算术编码确定符号的编码范围编码时输入第1个符号是10，找到它的编码范围是[0.5,0.7]消息中第2个符号00的编码范围是[0,0.1)，它的间隔就取[0.5,0.7)的第一个十分之一作为新间隔[0.5,0.52)编码第3个符号11时，取新间隔为[0.514,0.52)编码第4个符号00时，取新间隔为[0.514,0.5146)依此类推……消息的编码输出可以是最后一个间隔中的任意数算术编码算术编码算术编码算术编码

算术编码长度为n的序列的算术编码的平均码长为：算术编码的效率高：当信源符号序列很长，平均码长接近信源的熵算术编码在算术编码中需要注意的问题：由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。算术编码器对整个消息只产生一个码字，这个码字是在间隔[0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。算术编码

算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改。开发动态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。带缩放的算术编码编码器：一旦我们到达1.或2.，就可以忽略[0,1)的另一半还需要告知解码器标识所在的半区间：发送0/1比特用来指示下上界所在区间将标识区间缩放到[0,1):E1:[0,0.5)=>[0,1); E1(x)=2xE2:[0.5,1)=>[0,1); E2(x)=2(x-0.5)注意：在缩放过程中我们丢失了最高位但这不成问题—我们已经发送出去了解码器根据0/1比特并相应缩放与编码器保持同步带缩放的算术编码考虑随机变量X(ai)=i

对序列1321编码：

Input:1321Output:

Input:-321Output:

1带缩放的算术编码Input:--21Output:11Input:---1Output:110Input:---1Output:1100Input:---1Output:11000

带缩放的算术编码假设码字长为6输入：1100011000000.1100012=0.76562510第1位：1Output:1Input:110001100000Output:13Input:-10001100000(左移)Input:-10001100000(0.546875)Output:132Input:---001100000(左移)Input:--0001100000(左移)带缩放的算术编码此时解码最后一个符号Input:----01100000(左移)Input:-----1100000(左移)Input:-----100000

(左移)Input:-----100000Output:1321应用背景： 对于“局部冗余”的特殊类型。 主要应用于图象表达、处理。原因：数字化的image有大量的“局部冗余”占空间大 （一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。）语义依赖典型：行程编码（run-lengthencoding:RLE）差异映射(differencemapping)词典编码(DictionaryEncoding)语义依赖差异映射：算法思想：图象表示为相邻像素在亮度/颜色上的差异阵列，而不是像素本身的亮度/颜色值例[Laeseretal.1986]8bits/pixel(256brightness)3bits/pixel语义依赖词典编码词典：全部词语（words）常用词语+词语结束符号编码方法：指向词典的指针表指向词典的指针表（常用词语）+编码（不常用词语）语义依赖分解与编码源信息代码（长度）：block->blockblock->variablevariable->blockvariable->variable例：“aabbbccccdddddeeeeeefffffffgggggggg”

block->block(120)Sourcemassage codeworda 000b 001c 010d 011e 100f 101g 110space 111分解与编码例："aabbbccccdddddeeeeeefffffffgggggggg”variable->variable(30)

Sourcemassage codewordaa 0bbb 1ccccc 10ddddd 11eeeeeee 100fffffff 101gggggggg 110space 111分解与编码“定义字”与“自由分解”方法定义字（defined-word）方式源信息分解的长度在编码调用之前已确定自由分解（free-parse）方式编码算法本身决定源信息分解的长度（变长）分解与编码典型算法定义字方式的：Shannon-FanocodingHuffmancodingUniversalcodes(通用码)Arithmeticcoding(算术编码)自由分解方式的：Lempel-ZivcodesAlgorithmBSTW行程编码（RLE）基本原理：它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。

行程编码（RLE）行程编码(RLE）算法:x1,x2,……

xn---->(

c1,l1),(

c2,l2),……

(

ck,lk)

ci:亮度/颜色li:第i行程（相同亮度/颜色的像素的序列）的长度不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以；或者存储一个象素的颜色值，以及具有相同颜色值的行数。具有相同颜色并且是连续的象素数目称为行程长度。行程编码（RLE）例：代码字为：（0，8),（1，3),（8，50),（1，4),(0，8）行程编码（RLE）RLE所能获得的压缩比——主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。RLE是无损压缩技术。行程编码（RLE）应用：尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。（对颜色丰富的自然图像不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用。）商业数据处理（如连续多个0，空格）行程编码（RLE）特点：

利用两个字节代替连续出现的同一数据。通常需要在表示重复次数的字节中利用前一位或两位作为标志位，提示应用程序中随后的极为表示次数，另一字节表示重复数据的值。举例说明：

aaaa

bbb

cc

d

eeeee

fffffff

(共22*8=176bits)

4a3b2c1d5e7f(共12*8=96bits)BMP行程编码BI_RLE8的编码方式：由2个字节组成，第一个字节指定使用相同颜色的象素数目，第二个字节指定使用的颜色索引。此外，这个字节对中的第一个字节可设置为0，联合使用第二个字节的值表示：

第二个字节的值为0：行的结束。

第二个字节的值为1：图象结束。

第二个字节的值为2：其后的两个字节表示下一个象素从当前开始的水平和垂直位置的偏移量。

BMP行程编码例如：

0304050602780002050102780000091E0001

这些压缩数据可解释为：

0304040404

05060606060606

02787878

00020501从当前位置右移5个位置后向下移一行

02787878

0000行结束

091E1E1E1E1E1E1E1E1E1E

0001编码图象结束PCX行程编码PCX简介：真彩色图像以行为单位，按色面存放128字节的文件头图像数据调色板PCX行程编码图像数据以字节为单位进行编码按行进行压缩长度在前，灰度值在后单像素没有长度值以最高两位作为判断是重复数还是原像素。最高两位为1（B0除外），说明是重复数，否则，说明是原像素值

PCX行程编码重复像素长度iC最大值为26-1=63，如果遇到iC大于63的情况，则分为小于63的几段，分别处理。如果遇到不重复的单个像素P： 如果P<0xC0（192）直接存入该像素值， 否则先存入长度1，再存入像素值（192-255之间的单像素图像不减反增）PCX行程编码例

0X15····0X150X5A0X670X5F0X710X6911

0X35····0X350XD70XD90XCC80

[0XCB0X15]0X5A0X670X5F0X710X69

[0XFF0X35][0XD10X35][0XC10XD7][0XC10XD9][0XC10XCC]行程编码（RLE）对于有大面积色块的图像，压缩效果很好对于纷杂的图像，压缩效果不好，最坏情况下（图像中每两个相邻点的颜色都不同），会使数据量加倍，所以现在单纯采用行程编码的压缩算法用得并不多二维行程编码二维行程编码要解决的核心问题是：将二维排列的像素，采用某种方式转化成一维排列的方式。之后按照一维行程编码方式进行编码两种典型的二维行程编码的排列方式二维行程编码数据量：64*8=512(bit)二维行程编码如果按照方式(a)扫描的顺序排列的话，数据分布为：130，130，130，130，130，130，130，130，130；129，129，129，129，130，130，129；127，128，127，129，131，130，132，134，134；133，133，132，130，129，128，127，128，127，128，127，125，126，129，129；127，129，133，132，131，129，130，130；129，130，130，130，129，130，132，132；131，131，130，126，128，128，127，127二维行程编码行程编码为：

数据量：43*（3+8）=473(bit)(94.22%)（7，130），（2，130），（4，129），（2，130），（1，129）；（1，127），（1，128），（1，127），（1，129），（1，131），（1，130），（1，132），（2，134），（2，133），（1，132），（1，130），（1，129），（1，128），（1，127），（1，128），（1，127），（1，128），（1，127），（1，125），（1，126），（2，129），（1，127），（1，129），（1，133），（1，132），（1，131），（1，129），（2，130），（1，129），（3，130），（1，129），（1，130），（2，132），（2，131），（1，130），（1，126），（2，128），（2，127）比特平面编码思想：

对于灰度或彩色图像，如果每个像素用k位表示，将相同位上的0，1取出，就可以形成k个N*N的二值图像。将每一个二值图像称为一个比特平面。希望连续的0/1出现的概率增大.比特平面编码二值图像压缩标准静止图像（stillimages）包括两类：黑白（二值）静止图像连续色调（彩色或灰度）静止图像。二值图像压缩方法主要用于不包含任何连续色调信息的文档，或者连续色调信息(大多数为图片)可以用黑白的模式来获取的应用。例如办公／商业文档，手写文本、线条图形、工程图等。二值图像压缩标准二值图像压缩的标准：3类（CCITTGroup3）数字传真标准4类（CCITTGroup4）数字传真标准JBIG（JointBi-levelImageexpertsGroup，二值图像联合专家组）标准二值图像压缩标准G3和G4－由CCITT国家电话电报咨询委员会(consultativecommitteeoftheinternationaltelephoneandtelegraph)的两个小组(Group3和Group4)负责制定的，最初为传真应用而设计（1）G3采用一维行程长度编码；（2）行程采用Huffman编码；（3）0－63之间的行程，用单个码字即终止码表示；（4）大于63的游长用一个形成码和一个终止码组合表示。形成码表示实际行程对64的倍数；（5）G3能达到15：1的压缩比；（6）G4采用二维行程程度编码，压缩比比G3提高30％。二值图像压缩标准一维压缩基本思想：1）每一行行首、尾编码行首：用一个白行程码开始。如果行首是黑像素，则 用零长度的白00110101开始。行尾：用行尾编码字(EOL)000000000001结束。2）图像首、尾编码图像首行：用一个EOL开始。图像结尾：用连续6个EOL结束。3）图像内部编码内部编码：长度小于63的用哈夫曼编码，大于63的用组合编码：大于63的长度编码+小于63的余长度编码二值图像压缩标准长度小于63的哈夫曼编码行程长度白编码 黑编码0 00110101 00001101111 000111 0102 0111 113 1000 104 1011 0115 1100 001161 00110010 00000101101062 00110011 00000110011063 00110100 000001011011二值图像压缩标准长度大于63的组合编码

行程长度白编码 黑编码64 11011 0000001111128 10010 000011001000192 010111 000011001001256 0110111 000001011011320 00110110 000000110011384 00110111 0000001101001600 010011010 00000010110111664 011000 00000011001001728 010011011 0000001100101二值图像压缩标准二维压缩

1)基本思想：利用上一行相同改变元素的位置，来为当前行编码假设相临两行改变元素位置相似的情况很多且上一行改变元素距当前行改变元素的距离，小于行程的长度，从而可以降低编码长度a0b1b2a1a2参考行当前行二值图像压缩标准2)定义几个重要符号：参考行：当前处理行的前一行。改变元素：与前一个像素值不同的像素参考元素：一共有5个（当前行3个，参考行2个）：a0：当前处理行上，与前一个像素值不同的像素。 行首元素是本行的第一个a0a1：a0右边下一个改变元素。a2：a1右边下一个改变元素。b1：参考行上在a0右边，且与a0值相反的改变元素b2：b1右边下一个改变元素。a0b1b2a1a2参考行当前行二值图像压缩标准3)编码方法：对三种情况的三种编码方式：（1）通过编码方式：条件：b2在a1的左边，排除参考行两个改变元素都在 a1左边的情况编码：0001，动作：把a0移到b2的下面b1b2a1a2a0新a0二值图像压缩标准3)编码方法：对三种情况的三种编码方式：（2）水平编码方式：条件：a1到b1之间的距离大于3，放弃利用上一行编码编码：001+M(a0a1)+M(a1a2)，M：一维行程编码动作：把a0移到a2。a0b1b2a1a2a1b1二值图像压缩标准3）编码方法：对三种情况的三种编码方式：（3）垂直编码方式：条件：a1到b1之间的距离小于等于3，利用上一行编码。编码：见CCITT二维编码表（下页）动作：把a0移到a1a0b1b2a1a2a1b1二值图像压缩标准4)CCITT二维编码表

a1与b1的距离 编码：

a1在b1下面： 1 a1在b1右边1个 001 a1在b1右边2个 000011 a1在b1右边3个 0000011 a1在b1左边1个 010 a1在b1左边2个 000010 a1在b1左边3个 0000010二值图像压缩标准CCITTGroup3基本思想：Group3标准应用了一种非适应的，一维和二维混合的行程编码技术在该编码中，每一个K行组的最后K-1行（K=2或4），有选择地用二维编码方式。二值图像压缩标准CCITTGroup4基本思想：Group4标准是Group3标准简化或改进版本只用二维压缩编码。且为非适应二维编码方法每一个新图像的第一行的参考行是一个虚拟的白行二值图像压缩标准JBIG是“二值图像联合专家组（JointBi-levelImageexpertsGroup）”的简称。它建立于1988年，是一个由国际标准实体和主要公司提名产生的专家组，致力于制订二值图像编码标准。“联合”指的是他们同时为ISO、IEC和ITU-T制订标准。JBIG的正式名称，在ISO和IEC叫ISO/IECJTC1SC29第一工作组，在ITU-T，则称为ITU-TSG8。JBIG和JPEG一同工作，同时为JPEG和JBIG制订标准。人们常常将他们制订的这两种标准分别简称为JPEG标准和JBIG标准，或直接称为JPEG和JBIG。二值图像压缩标准JBIG1在性能上有很大提高JBIG1采用顺序传输模式来适应浏览技术(数字信息检索和恢复)的要求，这项技术已普遍用于现代图书馆和网络数据库JBIG1结合了预测建模、自适应和无损编码等技术选择算术编码作为数字压缩的基础，能够适应所遇到的图像统计概率。用细化网格里的黑色像素密度代表灰度，因为人眼的分辨能力很有限，人的视觉系统会把这些小点平滑地联起来。对计算机生成的图像。JBIG1采用干净自然的图像边缘来改善性能。二值图像压缩标准缺省的传输模式是顺序模式在顺序模式中，全分辨率图像ID从左边进入，图像经过一连串的降低分辨率达到ID-1，…，I0。最低分辨率的水平称为底层，所有的高一点的分辨率水平称为差分层。描述底层的信息最先发送，然后是逐步向上的差分层信息。除非接收到信号中止这个过程，这样一直到全分辨率。无损预测编码预测编码：

数字图像或者音频按照行或列从新排列后可以得到一个一位信号序列。预测编码就是根据这个信号序列的一些已知情况来预测以后信号可能发生的情况，然后对预测的误差进行编码而不是直接对信号进行。当预测比较准确、误差较小是，这种编码方式就能达到数据压缩的目的。无损预测编码基本思想图像相邻像素间存在很强的相关性，通过观察其相邻像素取值，可预测一像素的大概情况。预测值和实际值存在误差，称为预测误差。预测误差的方差必然比原图像像素的方差小，因此对预测误差编码必然压缩其平均码长。对预测误差进行编码的技术称为DPCM（差分脉冲编码调制）。无损预测编码无损预测编码无损预测编码预测误差的熵对比一幅图像和其差分图像的标准差和熵。不同图像的差分图像直方图分布形态大致相同，只是方差有所不同。无损预测编码预测方程式线性预测：如果ai是常数，则为时不变线性预测，否则为自适应线性预测（ADPCM）最简单的预测方程：无损预测编码预测器整数舍入符号编码器预测器符号解码器SS源数据压缩数据恢复数据预测误差,enfnf^nen+f^n++-fn压缩数据无损预测编码为实现无失真编码，通常对差分进行熵编码（通常是Huffman编码）；预测误差熵编码的步骤：建立码表和编码。通常采用一个通用码表，节省建立专用码表时间，由此带来压缩比损失较小；编码：若对差分所有灰度建立码表，则项数较多。通常对－16~16采用Huffman编码，其他直接用前缀＋实际灰度值。无损预测编码一副数字图像或一段音频可以看成一个空间点阵，图像信号不仅在水平方向是相关的，在垂直方向也是相关的。根据已知样值与待预测样值间的位置关系，可以分为：（1）一维预测（行内预测）：利用同一行上相邻的样值进行预测。（2）二维预测（帧内预测）：利用同一行和前面几行的数据进行预测。（3）三维预测（帧间预测）：利用相邻几帧（或不同波段）上的取样值进行预测无损预测编码举例：公式：中取：m=2，a1=a2=1/2f={154,159,151,149,139,121,112,109,129}预测值f2=1/2*(154+159)156 e2=151–

156=-5 f3=1/2*(159+151)=155 e3=149–155=

-6 f4=1/2*(151+149)=150 e4=139–150=-11 f5=1/2*(149+139)=144 e5=121–144=

-23 f6=1/2*(139+121)=130 e6=112–130=-18 f7=1/2*(121+112)116 e7=109–116=-7 f8=1/2*(112+109)110 e8=129–110=19无损预测编码这种压缩算法被应用到JPEG标准的无损压缩模式之中，中等复杂程度的图像压缩比可达到2:1。cabx选择值预测值0非预测1a2b3c4a+b-c5a+(b-c)/26b+(a-c)/27(a+b)/2d三邻域预测法无损预测编码视频信号的冗余度主要体现在空间相关性（帧内）、时间相关性（帧间）和色度空间表示上的相关性。对于每秒30帧的视频信号，其相继帧之间存在极强的相关性。据统计256级灰度的黑白图像序列，帧间差值超过3的象素数不超过4％。所以在活动图像序列中可以利用前面的帧来预测后面的帧，以实现数据压缩。帧间预测编码技术被广泛应用到H.261、H.263、MPEG-1和MPEG-2等视频压缩标准之中。无损预测编码运动补偿预测将前一个画面的数值作为后一个画面的预测值。编码器运动补偿图像输入运动矢量输出-译码器帧缓存运动估计预测误差输出无损预测编码无损预测编码无损预测编码无损预测编码无损预测编码无损预测编码无损预测编码词典编码文本中的词用它在词典中表示位置的号码代替的一种无损数据压缩方法。采用静态词典编码技术时，编码器需要事先构造词典，解码器要事先知道词典。采用动态辞典编码技术时,编码器将从被压缩的文本中自动导出词典，解码器解码时边解码边构造解码词典。词典编码词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余第一类编码算法第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。LZ77算法LZ77算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。LZ77算法1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤2，否则进行步骤3。2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动len+1个字符，继续步骤1。3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动1个字符，继续步骤1。LZ77算法LZ77算法AABCBBABCA步骤位置匹配串输出11－－0,0,A22A1,1,B34－－0,0,C45B2,1,B57ABC5,3,ALZSS算法LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针（匹配串长度大于等于MIN_LENGTH），否则就输出真实字符。另外要输出额外的标志位区分是指针还是字符LZSS算法1、从当前压缩位置开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度len大于等于最小匹配串长度（len>=MIN_LENGTH），则进行步骤2，否则进行步骤3。2、输出指针二元组(off,len)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为匹配串的长度，然后将窗口向后滑动len个字符，继续步骤1。3、输出当前字符c，然后将窗口向后滑动1个字符，继续步骤1。LZSS算法位置1234567891011字符AABBCBBAABC步骤位置匹配串输出11－－A22AA33－－B44BB55－－C66BB（3，2）78AAB（7，3）811CC输入数据流：编码过程MIN_LEN=2LZSS算法在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip,GZip,ARJ,LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。第二类词典编码第二类算法的想法是企图从输入的数据中创建一个“短语词典(dictionaryofthephrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。LZ78算法LZ78的编码思想是不断地从字符流中提取新的字符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Codeword)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Codeword)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的。LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。LZ78算法步骤1：将词典和当前前缀P都初始化为空。步骤2：当前字符C:=字符流中的下一个字符。步骤3：判断P＋C是否在词典中（1）如果“是”，则用C扩展P，即让P:=P＋C，返回到步骤2。（2）如果“否”，则输出与当前前缀P相对应的码字W和当前字符C，即（W，C）；将P＋C添加到词典中；令P:=空值，并返回到步骤2LZ78算法位置123456789字符ABBCBCABA步骤位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)输入数据流：编码过程：LZW算法J.Ziv和A.Lempel在1978年首次发表了介绍第二类词典编码算法的文章。在他们的研究基础上，TerryA.Welch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-ZivWalch)压缩编码。在编码原理上，LZW与LZ78相比有如下差别：LZW只输出代表词典中的字符串(String)的码字(codeword)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符。即在编码匹配时，至少可以在词典中找到长度为1的匹配串。

LZW编码是围绕称为词典的转换表来完成的。LZW算法

LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Charstream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流(Codestream)，码字代表单个字符或多个字符组成的字符串(String)。LZW算法步骤1：将词典初始化为包含所有可能的单字符，当前前缀P初始化为空。步骤2：当前字符C:=字符流中的下一个字符。步骤3：判断P＋C是否在词典中（1）如果“是”，则用C扩展P，即让P:=P＋C，返回到步骤2。（2）如果“否”，则输出与当前前缀P相对应的码字W；将P＋C添加到词典中；令P:=C，并返回到步骤2LZW算法位置123456789字符ABBABABAC步骤位置码字词典输出1A2B3C114AB1225BB2336BA2447ABA4558ABAC76－－－3输入数据流：LZW算法

LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式、TIFF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。

LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司—Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法。GIF例子：GIF和TIFF都使用LZW压缩法。下面以GIF为例进行介绍：1）GIF简介（多图像、256色）文件结构： 文件头信息：标识（GIF）、版本号 屏幕描述：屏幕长、宽、背景色等 全局调色板：长度（256x3）//三个256色的调色板GIF

图象描述：描述图像块在屏幕上的左上角位置及宽高 局部调色板:长度（256x3）//三个256色的调色板，每个图像可有一个 图像数据：用LZW方式压缩，用256字节的块来存放 扩充块描述：有四种扩充块文件头信息LZW压缩图像数据全局调色板屏幕描述图像描述局部调色板扩充数据块GIF初始化字典输出清除标记LZW_CLEARTemp=空串k=从输入流中读一个字符是结尾标志吗？Temp+k在字典中吗？输出Temp的编码把新串Temp+k加到字典中Temp=kTemp=Temp+k输出Temp的编码输出结束标记GIF编码举例：设字符集{a,b,c,d}， 串：aabdaadaa

压缩字典 临时串输入串编码

0 a T=temp+ a 1 b T=a + a0 2 c T=a + b00 3 d T=b + d 001 4 aa T=d + a 00135 ab T=a + a 6 bd T=aa + d 001347 da T=d + a