数据压缩基础学习教案.pptx

《数据压缩基础学习教案.pptx》由会员分享，可在线阅读，更多相关《数据压缩基础学习教案.pptx（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据压缩数据压缩(sh j y su)基础基础第一页，共81页。2主要主要(zhyo)内容内容n n数据压缩概述数据压缩概述n n数据压缩编码数据压缩编码n n统计统计(t(t ngj)ngj)编码编码霍夫曼编码霍夫曼编码n n算术编码算术编码n n预测编码预测编码n n行程编码行程编码n n变换编码变换编码n n词典编码词典编码n n分析综合编码分析综合编码第1页/共81页第二页，共81页。3什么什么(shn me)是数据压是数据压缩缩 数据压缩就是在一定的精度(jn d)损失条件下，以最少的数码表示信源所发出的信号信源编码信道编码信道信道译码信源译码信源信宿第2页/共81页第三页，

2、共81页。4多媒体信源引起了“数据爆炸(bozh)”如果不进行数据压缩 传输和存储都难以实用化。多媒体数据数据压缩数据压缩(sh j y su)的必要性的必要性第3页/共81页第四页，共81页。5分钟数字音频信号(xnho)需要的存储空间1第4页/共81页第五页，共81页。6分钟数字(shz)视频信号需要的存储空间1第5页/共81页第六页，共81页。7常见(chn jin)的图像数据冗余（1）空间冗余。在任何一幅图像中，均有由许多灰度或颜色都相同的邻近像素组成的区域，它们形成了一个性质相同的集合块，即它们相互之间具有空间（或空域）上的强相关性，在图像中就表现为空间冗余。（2）时间冗余。这是序列

3、图像（电视图像、运动图像）表示中经常包含的冗余。图像序列中两幅相邻(xin ln)的图像有较大的相关，这反映为时间冗余。（3）结构冗余。在有些图像的纹理区，图像的像素值存在着明显的分布模式。例如，方格状的板图案等，我们称此为结构冗余。已知分布模式，可以通过某一过程生成图像。第6页/共81页第七页，共81页。8（4）知识冗余。有些图像的理解与某些知识有相当大的相关性。例如(lr)：狗的图像有固定的结构，比如，狗有四条腿，头部有眼、鼻、耳朵，有尾巴等。这类规律性的结构可由先验知识和背景知识得到，我们称此类冗余为知识冗余。（5）视觉冗余。人类视觉系统的一般分辨能力估计为26灰度等级，而一般图像的量化

4、采用的是28的灰度等级。像这样的冗余，我们称之为视觉冗余。空间冗余和时间冗余是将图像信号看作为随机信号时所反映出的统计特征，因此有时把这两种冗余称为统计冗余。第7页/共81页第八页，共81页。9时间域压缩迅速传输媒体信源频率域压缩并行开通更多业务空间域压缩降低存储(cn ch)费用能量域压缩降低发射功率数据压缩数据压缩(sh j y su)的好处的好处第8页/共81页第九页，共81页。10压缩比要大恢复后的失真小压缩算法要简单、速度快压缩能否用硬件(yn jin)实现数据压缩数据压缩(sh j y su)技术实现技术实现的衡量标准的衡量标准第9页/共81页第十页，共81页。11 无损压缩是指使

5、用压缩后的数据(shj)进行重构(或者叫做还原，解压缩)，重构后的数据(shj)与原来的数据(shj)完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。有损压缩是指使用压缩后的数据(shj)进行重构，重构后的数据(shj)与原来的数据(shj)有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。数据压缩数据压缩(sh j y su)技术的分类技术的分类第10页/共81页第十一页，共81页。12根据压缩(y su)原理的分类（1）预测编码。它是利用空间中相邻数据的相关性来进行压缩(y su)数据的。通常用的方法有脉冲编码调制（P

6、CM）、增量调制（DM）、差分脉冲编码调制（DPCM）等。这些编码主要用于声音的编码（2）变换编码。该方法将图像时域信号转换为频域信号进行处理。这种转换的特点是把在时域空间具有强相关的信号转换到频域上时在某些特定的区域内能量常常集中在一起，数据处理时可以将主要的注意力集中在相对较小的区域，从而实现数据压缩(y su)。一般采用正交变换，如离散余弦变换（DCT）、离散傅立叶变换（DFT）第11页/共81页第十二页，共81页。13（3）统计编码（信息熵编码）。依据信息熵原理，让出现概率大的信号用较短的码字表示，反之用较长的码字表示。常见的编码方法有Huffman编码、Shannon编码以及算术编码

7、。（4）量化与矢量量化编码。对模拟信号进行数字化时要经历一个量化的过程。为了使整体量化失真最小，就必须依据统计的概率分布设计最优的量化器。最优的量化器一般是非线性的，已知的最优量化器是Max量化器。我们对像元点进行量化时，除了每次仅量化一个点的方法外，也可以考虑一次量化多个点的做法，这种方法称为矢量量化。即利用相邻数据间的相关性，将数据系列分组进行量化。（5）子带（subband）编码。将图像数据变换到频率(pnl)后，按频率(pnl)分带，然后用不同的量化器进行量化，从而达到最优的组合。或者分布渐进编码，在初始时，对某一个频带的信号进行解码，然后逐渐扩展到所有频带。第12页/共81页第十三页

8、，共81页。14算法(sun f)概要 JPEG(Joint Photographic Experts Group)是一个由 ISO和CCITT两个组织机构联合组成的一个图像专家小组，负责制定静态的数字图像数据压缩编码标准，这个专家组开发的算法称为JPEG算法，并且成为国际上通用的标准。JPEG是一个适用范围很广的静态图像数据压缩标准，既可用于灰度图像又可用于彩色图像。JPEG不仅适于静止图像的压缩，电视图像的帧内图像的压缩编码，也常采用此算法。JPEG标准还可以大范围地调节图像压缩率及其保真度。标准主要采用了两种基本的压缩算法，一种是采用以离散余弦变换(DCT)为基础的有损压缩算法，另一种是

9、采用以预测(yc)技术为基础的DPCM无损压缩算法。JPEG编码标准编码标准第13页/共81页第十四页，共81页。15JPEG编码标准编码标准n n基于基于DPCMDPCM的无损编码模式：压缩比可以达到的无损编码模式：压缩比可以达到(d(d do)2:1do)2:1。n n基于基于DCTDCT的有损顺序编码模式：压缩比可以达到的有损顺序编码模式：压缩比可以达到(d(d do)10:1do)10:1以上。以上。n n基于基于DCTDCT的递增编码模式的递增编码模式n n基于基于DCTDCT的分层编码模式的分层编码模式JPEG规定了4种运行(ynxng)模式，以满足不同需要：第14页/共81页第十

10、五页，共81页。16JPEG有损顺序编码算法(sun f)的主要计算步骤如下：1.将源图像分成几个颜色平面（分量图像）。2.分成88数据块进行正向离散余弦变换(FDCT)。2.量化(quantization)。3.Z字形排列量化结果(zigzag scan)。4.使用差分脉冲编码调制(differential pulse code modulation，DPCM)对直流系数(DC)进行编码。5.使用行程长度编码(run-length encoding，RLE)对 交流系数(AC)进行编码。6.熵编码(entropy coding)。JPEG编码标准编码标准第15页/共81页第十六页，共81页。

11、17JPEG编码标准编码标准第16页/共81页第十七页，共81页。18译码或者叫做解压缩(y su)的过程与压缩(y su)编码过程正好相反。IDCTJPEG编码标准编码标准第17页/共81页第十八页，共81页。19正向(zhn xin)离散余弦变换 对每个单独的彩色图像分量，把整个分量图像分成(fn chn)88的图像块，如图所示，并作为两维离散余弦变换DCT的输入。通过DCT变换，把能量集中在少数几个系数上。DCT变换(binhun)使用下式计算逆变换使用下式计算JPEG编码标准编码标准第18页/共81页第十九页，共81页。20量化 对于有损压缩算法，JPEG算法使用如图所示的均匀(jny

12、n)量化器进行量化，量化步距是按照系数所在的位置和每种颜色分量的色调值来确定。JPEG编码标准编码标准第19页/共81页第二十页，共81页。21量化 因为人眼(rn yn)对亮度信号比对色差信号更敏感，因此使用了两种量化表：亮度量化值和色差量化值。此外，由于人眼(rn yn)对低频分量的图像比对高频分量的图像更敏感，因此图中的左上角的量化步距要比右下角的量化步距小。JPEG编码标准编码标准第20页/共81页第二十一页，共81页。22DC系数DPCM编码和AC系数Z形排列(pili)之后采用RLE编码JPEG编码标准编码标准第21页/共81页第二十二页，共81页。23熵编码(bin m)使用熵编

13、码(bin m)还可以对DPCM编码(bin m)后的直流DC系数和RLE编码(bin m)后的交流AC系数作进一步的压缩。JPEG标准规定了两种熵编码(bin m)算法：哈夫曼编码(bin m)和自适应算术编码(bin m)。哈夫曼编码(bin m)采用的一般是固定的哈夫曼编码(bin m)表，而不是临时统计出来的，并且对亮度分量和色度分量采用了不同的哈夫曼表。JPEG编码标准编码标准第22页/共81页第二十三页，共81页。24基于DPCM的无损编码模式：主要采用(ciyng)了三邻域二维预测编码和熵编码。无失真(sh zhn)编码器源图像(t xin)数据压缩的图像数据预测器熵编码器表说明

14、DPCM预测编码框图JPEG编码标准编码标准第23页/共81页第二十四页，共81页。25JPEG编码标准编码标准基于DCT的递增编码模式：此模式与顺序模式编码步骤基本一致，不同之处在于递增模式每个图像分量的编码要经过多次扫描才完成(wn chng)。第一次扫描只进行一次粗糙的压缩，然后根据此数据先重建一幅质量低的图像，以后的扫描再作较细的扫描，使重建图像质量不断提高，直到满意为止。递增模式分为两种：（1）按频段累进。（2）按位累进。第24页/共81页第二十五页，共81页。26JPEG编码标准编码标准基于DCT的分层编码模式：（1）降低原始图像的空间分辨率。（2）对已经降低分辨率的图像按照顺序编

15、码模式进行压缩并存储或传输。（3）对低分辨率图像进行解码(jim)，然后用插值法提高图像的分辨率。（4）将分辨率已经升高的图像作为原图像的预测值，并把它与原图像的差值进行基于DCT的编码。（5）重复步骤3、4直到图像达到完整的分辨率。第25页/共81页第二十六页，共81页。27统计统计(tngj)编码编码1信息(xnx)量与信息(xnx)熵 信息(xnx)量是指从N个相等的可能事件中选出一个事件所需要的信息(xnx)度量或含量，也就是在辨识N个事件中特定的一个事件的过程中所需要提问“是或否”的最少次数。设从N个数中选定任一个数xj的概率为p（xj），假定选定任意一个数的概率都相等，即p（xj）

16、，因此定义信息(xnx)量见公式4-5。定义信息(xnx)量见公式4-5。如果(rgu)将信源所有可能事件的信息量进行平均，就得到了信息的“熵”，即信息熵。式中，P(xj)是信源X发出xj的概率。I(xj)的含义是，信源X发出xj这个消息（随机事件）后，接收端收到信息量的量度。（4-5）第26页/共81页第二十七页，共81页。28熵（熵（Entropy）n n事件集合（样本空间）事件集合（样本空间）X X中每个事件的自信息中每个事件的自信息量量I(x)I(x)是定义在这个样本空间上的一个随机变是定义在这个样本空间上的一个随机变量，所以我们要研究它的统计特性。其数学量，所以我们要研究它的统计特性

17、。其数学期望为：期望为：n nH(X)H(X)表明了集合表明了集合X X中随机事件的平均中随机事件的平均(pngjn)(pngjn)不确定性，或者说平均不确定性，或者说平均(pngjn)(pngjn)信息量。信息量。n n称称H(X)H(X)为一阶信息熵或者简称为熵为一阶信息熵或者简称为熵(Entropy)(Entropy)第27页/共81页第二十八页，共81页。29熵（熵（Entropy）n n在符号出现之前，熵表示符号集中的符号出现的平均不确定性；在符号出现之后，熵代表接收一个(y)符号所获得的平均信息量。n n根据直觉，信源编码的数据输出速率（平均码长）与信源熵之间应该有某种对应关系。第

18、28页/共81页第二十九页，共81页。30信源的概率分布与熵的信源的概率分布与熵的关系关系(gun x)n n熵的大小与信源的概率分布模型有着密切的关系。n n最大离散熵定理：当与信源对应的字符(z f)集中的各个字符(z f)为等概率分布时，熵具有极大值log2m。m为字符(z f)集中字符(z f)个数。第29页/共81页第三十页，共81页。31二进制信源的熵二进制信源的熵n n二进制信源输出一个二进制数码(shm)所携带的平均信息量最大为1bit。pH10.501第30页/共81页第三十一页，共81页。32最大离散熵定理最大离散熵定理(dngl)的应用的应用n n对于同一个信源其总的信息

19、量是不变的，如果能够通过某种变换（编码），使信源尽量等概率分布，则每个输出符号所独立携带的信息量增大，那么传送相同信息量所需要的序列长度就越短。n n离散无记忆(jy)信源的冗余度隐含在信源符号的非等概率 分布之中。只要H（X）小于log2m，就存在数据压缩的可能。第31页/共81页第三十二页，共81页。33编码编码(bin m)信源 X1,X2,XL a1,a2,a3,aK编码器 Y1,Y2,YN b1,b2,b3,bD0,1信源字母表码元表消息(xio xi)分组码字第32页/共81页第三十三页，共81页。34平均平均(pngjn)码长与码长与熵熵n n如果采用如果采用(c(c iyng)

20、iyng)单字符二进制编码方式，单字符二进制编码方式，设字符设字符aj aj的编码长度为的编码长度为LjLj，则信源字母表的平，则信源字母表的平均码长为：均码长为：n n根据前面对二进制信源的分析，有：根据前面对二进制信源的分析，有：在Lj log2pj时，平均(pngjn)码长取得极小值H(X)第33页/共81页第三十四页，共81页。35关于关于(guny)离散无记离散无记忆平稳信源的结论忆平稳信源的结论n n一阶熵即为离散无记忆平稳信源的压缩极限。一阶熵即为离散无记忆平稳信源的压缩极限。（基本极限）（基本极限）n n只要只要(zh(zh yo)yo)信源不是等概率分布，就存在着信源不是等概

21、率分布，就存在着数据压缩的可能性。数据压缩的可能性。n n数据压缩的基本途径之一：使各字符的编码长数据压缩的基本途径之一：使各字符的编码长度尽量等于字符的信息量。度尽量等于字符的信息量。第34页/共81页第三十五页，共81页。36联合联合(linh)熵与条件熵与条件熵熵n n设随机变量设随机变量(su j bin lin(su j bin lin)X)X和和Y Y分别取值于分别取值于符号表符号表a1,a2,ama1,a2,am和和b1,b2,b3,bnb1,b2,b3,bnn n定义定义X X与与Y Y的联合熵为：的联合熵为：n n定义定义X X关于关于Y Y的条件熵为：的条件熵为：第35页/

22、共81页第三十六页，共81页。37离散离散(lsn)有记忆信有记忆信源的冗余源的冗余联合熵与其可能达到的最大值之间的差值反映了该有记忆信源所含的冗余(rn y)度，这种冗余(rn y)是由于随机变量序列之间的相关性造成的。第36页/共81页第三十七页，共81页。38关于离散有记忆平稳关于离散有记忆平稳(pngwn)信源的结论信源的结论n n离散有记忆平稳信源的压缩极限为：离散有记忆平稳信源的压缩极限为：n n压缩的基本途径之二：尽量去除各分量之间压缩的基本途径之二：尽量去除各分量之间的相关性，再对各分量进行独立的相关性，再对各分量进行独立(dl)(dl)编码。编码。n n压缩的基本途径之三：可

23、利用条件概率进行压缩的基本途径之三：可利用条件概率进行编码，阶越高越有利。编码，阶越高越有利。n n压缩的基本途径之四：可将多个分量合并成压缩的基本途径之四：可将多个分量合并成向量，利用其联合概率进行编码，联合的分向量，利用其联合概率进行编码，联合的分量越多越有利。量越多越有利。第37页/共81页第三十八页，共81页。39统计统计(tngj)编码（熵编码（熵编码）编码）n n统计编码（熵编码）包括香农范诺编码、霍夫曼编码和算术编码，其宗旨在于找到一种编码使得平均码长到达熵极限，基本思想就是(jish)对出现概率较大的符号取较短的码长，而对出现概率较小的符号取较大的码长。第38页/共81页第三十

24、九页，共81页。40霍夫曼编码霍夫曼编码(bin m)n n具体步骤：具体步骤：n n（1 1）初始化）初始化n n（2 2）合并概率最小的两个事件）合并概率最小的两个事件(shjin)(shjin)n n（3 3）排序）排序n n（4 4）如果事件）如果事件(shjin)(shjin)个数大于个数大于2 2则重复（则重复（2 2）和）和（3 3）n n（5 5）赋值）赋值n n（6 6）编码）编码第39页/共81页第四十页，共81页。41霍夫曼编码霍夫曼编码(bin m)举例举例符号S1S2S3S4出现概率1/21/41/81/8等长编码00011011霍夫曼010110111H(X)=1.

25、75 L1=2 L2=1.75源S1S2S1S3S2S1S1S4等0001001001000011霍01001101000111第40页/共81页第四十一页，共81页。42霍夫曼编码霍夫曼编码(bin m)的局限性的局限性n n利用霍夫曼编码利用霍夫曼编码(bin m(bin m)，每个符号的编码，每个符号的编码(bin m(bin m)长度只能为整数，所以如果源符号长度只能为整数，所以如果源符号集的概率分布不是集的概率分布不是2 2负负n n次方的形式，则无法次方的形式，则无法达到熵极限。达到熵极限。n n输入符号数受限于可实现的码表尺寸输入符号数受限于可实现的码表尺寸n n译码复杂译码复杂

26、n n需要实现知道输入符号集的概率分布需要实现知道输入符号集的概率分布n n没有错误保护功能没有错误保护功能第41页/共81页第四十二页，共81页。43香农范诺编码香农范诺编码(bin m)n n香农范诺编码与香农范诺编码与HuffmanHuffman编码相反，采用从上编码相反，采用从上到下的方法。到下的方法。n n具体步骤为：具体步骤为：n n （1 1）首先将编码字符集中的字符按照出现频）首先将编码字符集中的字符按照出现频度和概率进行排序。度和概率进行排序。n n （2 2）用递归的方法分成两部分，使两个部分）用递归的方法分成两部分，使两个部分的概率和接近于相等。直至不可再分，即每一的概率

27、和接近于相等。直至不可再分，即每一个个(y(y )叶子对应一个叶子对应一个(y(y )字符。字符。n n （3 3）编码。）编码。第42页/共81页第四十三页，共81页。44香农范诺编码香农范诺编码(bin m)举例举例A BC D EABCD EDE符号符号ABCDE次数次数15776501010011第43页/共81页第四十四页，共81页。45算术算术(sunsh)编码编码n nHuffman Huffman 编码的局限性：编码的局限性：Huffman Huffman 编码使用整数编码使用整数个二进制位对符号进行编码，这种方法在许多个二进制位对符号进行编码，这种方法在许多情况下无法得到最优

28、的压缩效果。假设某个字情况下无法得到最优的压缩效果。假设某个字符符(z f)(z f)的出现概率为的出现概率为 80%80%，该字符，该字符(z f)(z f)事实上事实上只需要只需要-log2(0.8)=0.322 -log2(0.8)=0.322 位编码，但位编码，但 Huffman Huffman 编编码一定会为其分配一位码一定会为其分配一位 0 0 或一位或一位 1 1 的编码。可的编码。可以想象，整个信息的以想象，整个信息的 80%80%在压缩后都几乎相当在压缩后都几乎相当于理想长度的于理想长度的 3 3 倍左右。倍左右。第44页/共81页第四十五页，共81页。46算术算术(suns

29、h)编码编码n n基本思想：算术编码不是将单个信源符号映基本思想：算术编码不是将单个信源符号映射成一个码字，而是把真个信源表示为实数射成一个码字，而是把真个信源表示为实数线上的线上的0 0到到1 1之间的一个区间，其长度等于该之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要用来缩短消息序列中的每个元素都要用来缩短(sudu(sudu n)n)这个区间。消息序列中元素越多，这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就

30、需所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。要更多的数位来表示这个区间。n n采用算术编码每个符号的平均编码长度可以采用算术编码每个符号的平均编码长度可以为小数。为小数。第45页/共81页第四十六页，共81页。47算术算术(sunsh)编码举编码举例（一）例（一）符号00011011概率0.10.40.20.3初始区间0,0.1)0.1,0.5)0.5,0.7)0.7,1)第46页/共81页第四十七页，共81页。48算术算术(sunsh)编码举编码举例（二）例（二）n n最后的子区间起始位置最后的子区间起始位置 85/256=0.01010101 85/256=0.01

31、010101n n 子区间长度子区间长度 27/256=0.00011011 27/256=0.00011011n n 子区间尾子区间尾 7/16 =0.0111 7/16 =0.0111n n取编码取编码(bin m(bin m)区间中的一个值，最后编码区间中的一个值，最后编码(bin m(bin m)为：为：011011符号01频度1/43/4消息序列1011区间起始1/41/419/6485/256区间长度3/43/169/6427/256信源分布(fnb)：第47页/共81页第四十八页，共81页。49算术算术(sunsh)编码的编码的具体实现具体实现n n因为实际只能用有限长的寄存器，

32、这就要求将已编因为实际只能用有限长的寄存器，这就要求将已编码的高位码字及时输出，但又不能输出过早，以免码的高位码字及时输出，但又不能输出过早，以免后续运算后续运算(yn sun)(yn sun)还要调整已输出的码位。（请看还要调整已输出的码位。（请看参考书上给出的算法）参考书上给出的算法）n n算术编码每次递推都要做乘法，所以效率比较低。算术编码每次递推都要做乘法，所以效率比较低。二进制算术编码是一种实用的编码算法，用移位代二进制算术编码是一种实用的编码算法，用移位代替了乘法，使效率大大提高。替了乘法，使效率大大提高。n n自适应算术编码可以在编码过程中根据符号出现的自适应算术编码可以在编码过

33、程中根据符号出现的频繁程度动态的修改分布概率，这样可以避免在编频繁程度动态的修改分布概率，这样可以避免在编码之前必须精确求出信源概率的难题。码之前必须精确求出信源概率的难题。第48页/共81页第四十九页，共81页。50自适应算术自适应算术(sunsh)编码举例编码举例cba1.00000.66670.33330.00000.66670.58340.41670.33330.66670.63340.60010.58340.66670.65010.63900.6334c1/31/42/53/6b1/32/42/52/6a1/31/41/51/6输入(shr)序列为：bcc.第49页/共81页第五十页

34、，共81页。51行程行程(xngchng)编码编码（RLE）n n行程编码（行程编码（Run-Length EncodingRun-Length Encoding）：它通过将）：它通过将信源中相同符号序列转换成一个计数字段再信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩加上一个重复字符标志实现压缩(y su)(y su)。n n例如：例如：RTTTTTTTTABBCDGRTTTTTTTTABBCDG被转换为：被转换为：R#8TABBCDGR#8TABBCDG，其中，其中“”作为转义字符，作为转义字符，表明其后所跟的字符表示长度。表明其后所跟的字符表示长度。n nHuffma

35、nHuffman编码）。编码）。第50页/共81页第五十一页，共81页。52预测预测(yc)编码编码n n预测编码是数据压缩理论的一个重要分支。预测编码是数据压缩理论的一个重要分支。它根据离散它根据离散(lsn)(lsn)信号之间存在一定相关性信号之间存在一定相关性的特点，利用前面的一个或多个信号对下一的特点，利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的个信号进行预测，然后对实际值和预测值的差（预测误差）进行编码。如果预测比较准差（预测误差）进行编码。如果预测比较准确，那么误差信号就会很小，就可以用较少确，那么误差信号就会很小，就可以用较少的码位进行编码，以达到数据压缩

36、的目的。的码位进行编码，以达到数据压缩的目的。n n第第n n个符号个符号XnXn的熵满足：的熵满足：所以参与预测的符号越多，预测就越准确，该信源的不确定性就越小，数码率就可以(ky)降低。第51页/共81页第五十二页，共81页。53DPCM编码编码(bin m)预测器xkekxkxk-ekDPCM是有损型还是(hi shi)无损型关键看对预测误差ek如何编码。第52页/共81页第五十三页，共81页。预测预测(yc)方程式方程式 线性预测(yc)：如果ai是常数，则为时不变线性预测(yc)，否则为自适应线性预测(yc)（ADPCM）最简单的预测(yc)方程：第53页/共81页第五十四页，共81

37、页。最佳最佳(zu ji)线性预测线性预测使误差函数使误差函数达到最小值的预测方程式叫做最佳达到最小值的预测方程式叫做最佳(zu ji)(zu ji)线性预测。线性预测。求最佳求最佳(zu ji)(zu ji)线性预测的各个参数线性预测的各个参数ai ai，列方程组：，列方程组：代入得到(d do)联立方程组：如果为一阶线性预测，则可求得：第54页/共81页第五十五页，共81页。56图像图像(t xin)信号的信号的预测编码预测编码n n一副数字图像可以看成一副数字图像可以看成(kn chn(kn chn)一个空间点阵，图一个空间点阵，图像信号不仅在水平方向是相关的，在垂直方向也是相像信号不仅

38、在水平方向是相关的，在垂直方向也是相关的。根据已知样值与待预测样值间的位置关系，可关的。根据已知样值与待预测样值间的位置关系，可以分为：以分为：n n （1 1）一维预测（行内预测）：利用同一行上相邻的）一维预测（行内预测）：利用同一行上相邻的样值进行预测。样值进行预测。n n （2 2）二维预测（帧内预测）：利用同一行和前面几）二维预测（帧内预测）：利用同一行和前面几行的数据进行预测。行的数据进行预测。n n （3 3）三维预测（帧间预测）：利用相邻几帧（或不）三维预测（帧间预测）：利用相邻几帧（或不同波段）上的取样值进行预测同波段）上的取样值进行预测第55页/共81页第五十六页，共81页。

39、57静止图像的二维预测静止图像的二维预测(yc)编码编码n n这种压缩算法被应用到这种压缩算法被应用到JPEGJPEG标准的无损压缩模式标准的无损压缩模式(msh)(msh)之中，中等复杂程度的图像压缩比可达到之中，中等复杂程度的图像压缩比可达到2:12:1。cabx选择值预测值0非预测1a2b3c4a+b-c5a+(b-c)/26b+(a-c)/27(a+b)/2d三邻域(ln y)预测法第56页/共81页第五十七页，共81页。58活动图像活动图像(t xin)的的帧间预测编码帧间预测编码n n视频信号的冗余度主要体现在空间相关性（帧内）、视频信号的冗余度主要体现在空间相关性（帧内）、时间相

40、关性（帧间）和色度空间表示上的相关性。时间相关性（帧间）和色度空间表示上的相关性。n n对于每秒对于每秒2525帧（帧（3030）的电视信号，其相继帧之间存在）的电视信号，其相继帧之间存在极强的相关性。据统计极强的相关性。据统计256256级灰度的黑白图像序列，帧级灰度的黑白图像序列，帧间差值超过间差值超过3 3的象素数不超过的象素数不超过4 4。所以在活动图像序。所以在活动图像序列中可以利用前面的帧来预测后面列中可以利用前面的帧来预测后面(hu mian)(hu mian)的帧，的帧，以实现数据压缩。以实现数据压缩。n n帧间预测编码技术被广泛应用到帧间预测编码技术被广泛应用到H.261H.

41、261、H.263H.263、MPEG-1MPEG-1和和MPEG-2MPEG-2等视频压缩标准之中。等视频压缩标准之中。第57页/共81页第五十八页，共81页。59具有具有(jyu)运动补偿运动补偿的帧间预测的帧间预测n n活动图像活动图像(t xin(t xin)序列中的一个画面可以大致序列中的一个画面可以大致划分为划分为3 3个区域：个区域：n n （1 1）背景区：相邻两个画面的背景区基本相）背景区：相邻两个画面的背景区基本相同。同。n n （2 2）运动物体区：可以视为由前一个画面的）运动物体区：可以视为由前一个画面的某一区域的像素平移而成。（位移矢量）某一区域的像素平移而成。（位移

42、矢量）n n （3 3）暴露区：指物体运动后而显露出来的曾）暴露区：指物体运动后而显露出来的曾被遮盖的背景区域。被遮盖的背景区域。n n运动补偿预测就是将前一个画面的背景区平运动补偿预测就是将前一个画面的背景区平移后的运动物体区作为后一个画面的预测值。移后的运动物体区作为后一个画面的预测值。第58页/共81页第五十九页，共81页。60运动运动(yndng)补偿帧补偿帧间预测编码间预测编码运动补偿帧间预测从原理上包括如下几个基本步骤：运动补偿帧间预测从原理上包括如下几个基本步骤：（1 1）图像分割：把图像划分为静止的背景和若干运动）图像分割：把图像划分为静止的背景和若干运动的物体，各个物体可能有

43、不同的位移，但构成同一的物体，各个物体可能有不同的位移，但构成同一物体的所有物体的所有(su(su y y u)u)像素的位移相同。像素的位移相同。（2 2）运动矢量估值：考察前后两个画面，利用运动估）运动矢量估值：考察前后两个画面，利用运动估值算法得到每个物体的位移矢量。值算法得到每个物体的位移矢量。（3 3）运动补偿：用运动矢量补偿物体的运动效果再进）运动补偿：用运动矢量补偿物体的运动效果再进行预测。行预测。（4 4）编码：除了对实测值与预测值之间的差值进行编）编码：除了对实测值与预测值之间的差值进行编码传送外，还要传送位移矢量以及区域分割信息。码传送外，还要传送位移矢量以及区域分割信息。

44、第59页/共81页第六十页，共81页。61运动补偿运动补偿(bchng)帧帧间预测编码间预测编码编码器运动(yndng)补偿图像(t xin)输入运动矢量输出-译码器帧缓存运动估值预测误差输出第60页/共81页第六十一页，共81页。62变换编码变换编码n n预测编码希望通过预测编码希望通过(tnggu)(tnggu)对信源建模来尽对信源建模来尽可能的预测源数据；而变换编码则考虑将原可能的预测源数据；而变换编码则考虑将原始数据变换到另一个表示空间，使数据在新始数据变换到另一个表示空间，使数据在新的空间上尽可能相互独立，而能量更集。的空间上尽可能相互独立，而能量更集。XYXY第61页/共81页第六

45、十二页，共81页。63词典词典(cdin)编码编码n n词典编码主要利用数据本身包含许多词典编码主要利用数据本身包含许多(x(x du)du)重复的重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。倒吐葡萄皮。我们如果用一些简单的代号代替这些我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。号之间的相关性。字符串与代号的对应表就是词典。n n实用的词典编码算法的核心就是如何动态地形成词典，实用的词典编码算法的核心就是

46、如何动态地形成词典，以及如何选择输出格式以减小冗余。以及如何选择输出格式以减小冗余。第62页/共81页第六十三页，共81页。64第一类词典第一类词典(cdin)编编码码n n第一类词典法的想法是企图查找正在压缩的字符序列第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后是否在以前输入的数据中出现过，然后(rnhu)(rnhu)用已用已经出现过的字符串替代重复的部分，它的输出仅仅是经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的指向早期出现过的字符串的“指针指针”。第63页/共81页第六十四页，共81页。65LZ77算法算法(sun f)n n

47、LZ77 LZ77 算法算法(sun f(sun f)在某种意义上又可以称为在某种意义上又可以称为“滑动窗滑动窗口压缩口压缩”，该算法，该算法(sun f(sun f)将一个虚拟的，可以跟随压将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行词语匹配，而不是在所有已经编码的信大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法息中匹配，是因为匹配算法(sun f(sun f)的时间消耗往往的时间消耗往往很多，

48、必须限制词典的大小才能保证算法很多，必须限制词典的大小才能保证算法(sun f(sun f)的的效率；随着压缩的进程滑动词典窗口，使其中总包含效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。码的字符串往往在最近的上下文中更容易找到匹配串。第64页/共81页第六十五页，共81页。66LZ77编码的基本编码的基本(jbn)流程流程1 1、从当前压缩位置开始，考察未编码的数据、从当前压缩位置开始，考察未编码的数据(shj)(shj)，并试图在滑动窗口中找出最长的匹

49、配，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤字符串，如果找到，则进行步骤 2 2，否则进行步，否则进行步骤骤 3 3。2 2、输出三元符号组、输出三元符号组(off,len,c)(off,len,c)。其中。其中 off off 为窗口为窗口中匹配字符串相对窗口边界的偏移，中匹配字符串相对窗口边界的偏移，len len 为可匹为可匹配的长度，配的长度，c c 为下一个字符，即不匹配的第一个为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动字符。然后将窗口向后滑动 len+1 len+1 个字符，继个字符，继续步骤续步骤 1 1。3 3、输出三元符号组、输出三元符号组(0

50、,0,c)(0,0,c)。其中。其中 c c 为下一个字为下一个字符。然后将窗口向后滑动符。然后将窗口向后滑动 1 1 个字符，继续步骤个字符，继续步骤 1 1。第65页/共81页第六十六页，共81页。67LZ77算法算法(sun f)第66页/共81页第六十七页，共81页。68LZ77编码编码(bin m)举举例例AABCBBABCA步骤步骤位置位置匹配串匹配串输出输出110,0,A22A1,1,B340,0,C45B2,1,B57ABC5,3,A第67页/共81页第六十八页，共81页。69LZSS算法算法(sun f)n nLZ77LZ77通过输出真实通过输出真实(zhnsh)(zhnsh