数字媒体技术导论.

数字媒体技术导论数字媒体技术导论第八章数字媒体压缩技术教学目标：（1）了解数字媒体数据压缩的原因。（2）理解数字媒体数据压缩技术的不同分类。（3）掌握通用的数据压缩编码算法。（4）了解各种数字媒体数据压缩的标准。数字媒体技术导论学习内容：8.1数据压缩及分类8.2通用的数据压缩技术8.3数字媒体压缩标准数字媒体技术导论8.1.1压缩的可能性与信息冗余经过数字化处理后的图形、图像、视频和音频等媒体信息的数据量非常大，如果不进行数据压缩，计算机系统就无法对它进行存储、交换和传输。1）数字图像2）数字视频3）数字音频（数据量的计算）8.1数据压缩及分类数字媒体技术导论8.1.1压缩的可能性与信息冗余数据能够被压缩的主要原因在于媒体数据中存在数据的信息冗余。信息量包含在数据之中，一般的数据冗余主要体现在：1）空间冗余2）结构冗余3）时间冗余4）视觉冗余5）知识冗余6）信息熵冗余8.1数据压缩及分类数字媒体技术导论8.1.2数据压缩分类数据压缩分类数据压缩方法分类数字媒体压缩标准分类统计编码预测编码变换编码分析—合成编码图像压缩视音频压缩JPEG等运动图像MPEGH.26x系列声音AVSMP3数字媒体技术导论按信息压缩前后比较是否有损失进行划分：•无损压缩指使用压缩后的数据进行重构（还原或解压缩），重构后的数据与原来的数据完全相同。常用的无损压缩算法有霍夫曼(Huffman)算法和LZW算法。也称为可逆编码。•有损压缩指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。也称为不可逆编码。数字媒体技术导论按数据压缩编码的原理和方法进行划分：•统计编码：主要针对无记忆信源，根据信息码字出现概率的分布特征而进行压缩编码，寻找概率与码字长度间的最优匹配。•预测编码：是利用空间中相邻数据的相关性来进行压缩数据的。•变换编码：是将图像时域信号转换为频域信号进行处理。•分析–合成编码：是指通过对源数据的分析，将其分解成一系列更适合于表示的“基元”或从中提取若干更为本质意义的参数，编码仅对这些基本单元或特征参数进行。数字媒体技术导论无记忆信源【无记忆信源】（1）存在一个或多个基本符号集；（2）将多个基本符号集做笛卡儿积，形成一定长度的联合概率空间；（3）运用外力的功（电动势）将单个符号或一定长度的符号序列从随机事件转化成必然事件，或者说，将一个随机系统转化成一个必然系统；并且回退到原始空间中来，该原始空间的概率分布不因为事件的发生而改变。【有记忆信源】（1）存在一个或多个基本符号集；（2）将多个基本符号集做笛卡儿积，形成一定长度的联合概率空间；（3）运用外力的功（电动势）将单个符号或一定长度的符号序列从随机事件转化成必然事件，或者说，将一个随机系统转化成一个必然系统；不能回退到原始空间中来，即原始空间的概率分布因为事件的发生而改变。数字媒体技术导论按照媒体的类型进行压缩划分：•图像压缩标准：JPEG等•声音压缩标准：MP3•运动图像压缩标准：MPEG、H.26x系列、AVS目录数字媒体技术导论8.2通用的数据压缩技术–行程编码–字典编码–熵编码等–PCM–DM–DPCM通用的压缩方法具有压缩比低、通用性强等特点无损压缩技术有损压缩技术目录数字媒体技术导论8.2.1编码的理论基础•数据压缩技术的理论基础是信息论。•根据信息论的原理，可以找到最佳数据压缩编码方法，数据压缩的理论极限是信息熵。•熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。数字媒体技术导论信息与信息量•信息量是指信源中某种事件的信息度量或含量。一个事件出现的可能性愈小，其信息量愈多，反之亦然。•若pi为第i个事件的概率为0≤pi≤1，则该事件的信息量为•一个信源包括的所有数据叫数据量，而数据量中包含有冗余信息。信息量=数据量-冗余量数字媒体技术导论信息熵•信息熵就是将信源所有可能事件的信息量的平均。•设从N个数中选定任一个数xj的概率为p(xj)，假定选定任意一个数的概率都相等，即p(xj)＝1/N，则I(xj)＝log2N＝-log21/N＝-log2p(xj)=I[p(xj)]上式中，p(xj)是信源X发出xj的概率。I(xj)的含义是信源X发出xj这个消息（随机事件）后，接收端收到信息量的量度。数字媒体技术导论信息熵(续)•信源X发出的xj(j=1,2,…,n)共n个随机事件的信息量的统计平均，即•H(X)=E{I(xj)}=H(X)称为信源X的“熵”，即信源X发出任意一个随机变量的平均信息量。•其中，等概率事件的熵最大，假设有N个事件，此时熵为：H(X)＝＝njjjxPxP12)(log)(NNNj1log121N2log数字媒体技术导论信息熵(续)•当P(x1)＝1时，P(x2)＝P(x3)＝…＝P(xj)＝0，此时熵为H(X)＝－P(x1)＝0•由上可得熵的范围为：0≤H(X)≤)(log12xPN2log数字媒体技术导论信息熵(续)•在编码中用熵值来衡量是否为最佳编码。若以Lc表示编码器输出码字的平均码长，其计算公式为：Lc＝（j=1,2,…,n）其中：P(xj)是信源X发出xj的概率，L(xj)为xj的编码长。njjjxLxP1)()(数字媒体技术导论信息熵(续)•平均码长与信息熵之间的关系为：–Lc≥H(X)有冗余，不是最佳。–Lc＜H(X)不可能。–Lc＝H(X)最佳编码（Lc稍大于H(X)）•熵值为平均码长Lc的下限。数字媒体技术导论8.2.2霍夫曼编码•霍夫曼编码（Huffman）是运用信息熵原理的一种无损编码方法，这种编码方法根据源数据各信号发生的概率进行编码。•在源数据中出现概率大的信号，分配的码字越短；出现概率越小的信号，其码字越长，从而达到用尽可能少的码表示源数据。数字媒体技术导论霍夫曼编码的算法：1.初始化，根据符号概率的大小顺序对符号进行排序。2.把概率最小的两个符号组成一个新符号(节点)，即新符号的概率等于这两个符号概率之和。3.重复第2步，直到形成一个符号为止（树），其概率和等于1。4.分配码字。码字分配从最后一步开始反向进行，即从最后两个概率开始逐渐向前进行编码，对于每次相加的两个概率，给概率大的赋“0”，概率小的赋“1”（也可以全部相反，如果两个概率相等，则从中任选一个赋“0”，另一个赋“1”）。数字媒体技术导论•霍夫曼编码构造出来的编码值不是唯一的。•对不同信号源的编码效率不同。•由于编码长度可变，因此译码时间较长；编码长度的不统一，也使得硬件实现有难度。霍夫曼编码的特点：数字媒体技术导论8.2.3行程编码•行程编码又称行程长度编码（RunLengthEncoding，RLE），是一种熵编码。这种编码方法广泛地应用于各种图像格式的数据压缩处理中。•行程编码的原理是在给定的图像数据中寻找连续重复的数值，然后用两个字符取代这些连续值。即将具有相同值的连续串用其串长和一个代表值来代替，该连续串就称为行程，串长称为行程长度。数字媒体技术导论8.2.3行程编码•假定一幅灰度图像，第n行的像素值为：•用RLE编码方法得到的代码为：4160841140。代码斜黑体表示的数字是行程长度，黑体字后面的数字代表像素的颜色值。1111888……8881111000000000000004个160个84个114个0数字媒体技术导论行程编码分类：•定长编码–定长编码是指编码的行程长度所用的二进制位数固定•不定长编码–变长行程编码是指对不同范围的行程长度使用不同位数的二进制位数进行编码。使用变长行程编码需要增加标志位来表明所使用的二进制位数。数字媒体技术导论8.2.4词典编码词典编码（dictionaryencoding）技术属于无损压缩技术，主要是利用数据本身包含许多重复的字符串的特性。可以用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。数字媒体技术导论词典编码的种类：•第一种方法的思想是查找目前正在压缩的字符序列在以前输入的数据中是否出现过，然后用出现过的字符串代替重复的部分，它的输出仅仅是指向早期出现过的字符串“指针”。•这里所指的词典是指用以前处理过的数据表示编码过程中遇到的重复部分。这类编码的所有算法都是以LZ77算法为基础的。输入数据AABBCCDDXX输出数据ABCMMP.......………….............数字媒体技术导论词典编码的种类：•第二种算法的思想是从输入的数据中创建一个“短语词典”，这类短语不一定有具体的含义，可以是任意字符的组合。在编码过程中遇到在“短语词典”中出现的短语是，编码器就输出这个词典中的短语“索引号”，而不是短语本身。输入数据输出数据A4B1CCXXADY编码词典1.AB2.AX4.AXX3.AE5.BXDAADY..........数字媒体技术导论8.2.4.1LZ77算法•LZ77是以以色列计算机专家AbrahamLempel和JakobZiv在1977年开发和发表的。•此算法的一个改进算法是由Storer和Szymanski在1982年开发的，称为LZSS算法。•LZ77算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的、可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。数字媒体技术导论LZ77算法中涉及的概念1.输入字符流(inputstream)：要被压缩的字符序列。2.字符(character)：输入数据流中的基本单元。3.编码位置(codingposition)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。4.前向缓冲存储器(Lookaheadbuffer)：存放从编码位置到输入数据流结束的字符序列的存储器。5.窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。6.指针(pointer)：指向窗口中的匹配串且含长度的指针。数字媒体技术导论LZ77算法具体步骤（1）把编码位置设置到输入数据流的开始位置。（2）找窗口中最长的匹配串（3）以“(Pointer,Length)Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个符。（4）如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤（2）。数字媒体技术导论8.2.4.2LZW算法•LZW压缩算法是一种新颖的压缩方法，它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮串，从而使图像文件的压缩效率得到较大的提高。•LZW编码是围绕称为词典的转换表来完成的。数字媒体技术导论LZW算法中的术语和符号1.前缀(Prefix)：在一个字符之前的字符序列。2.缀-符串(String)：前缀＋字符。3.码字(Codeword)：4.码字流(Codestream)：5.词典(Dictionary)：缀-符串表。6.当前前缀(Currentprefix)：7.当前字符(Currentcharacter)：8.当前码字(Currentcodeword)：数字媒体技术导论LZW编码算法执行步骤1.开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；2.当前字符(C)：=字符流中的下一个字符；3.判断缀-符串P+C是否在词典中1）如果“是”：P：=P+C//(用C扩展P)；2）如果“否”：①把代表当前前缀P的码字输出到码字流；②把缀-符串P+C添加到词典；③令P：=C//(现在的P仅包含一个字符C)；•判断字符流中是否还有字符要编码1）如果“是”，就返回到步骤2；2）如果“否”：①把代表当前前缀P的码字输出到码字流；②结束。数字媒体技术导论8.2.5脉冲编码调制•脉冲编码调制(PCM)就是将模拟调制信号的采样值变换为脉冲码组。•PCM编码包括如下三个