第4章 多媒体数据压缩与编码技术

第4章多媒体数据压缩与编码技术本章重点：编码模型编码压缩方法分类统计编码的基本原理预测编码的基本原理变换编码的基本原理视频编码的基本原理第4章多媒体数据压缩与编码技术4.1编码压缩的必要性与可能性4.2编码模型4.3编码压缩方法分类4.4统计编码4.5预测编码4.6变换编码4.7其他编码4.8视频编码4.9本章小结4.1编码压缩的必要性与可能性4.1.1编码压缩的必要性4.1.2编码压缩的可能性4.1.1编码压缩的必要性众所周知，图像量化所需数据量大。图像和视频的庞大数据对计算机的处理速度、存储容量都提出过高的要求。因此必须进行数据量压缩。从传送的角度来看，在信道带宽、通信链路容量一定的前提下，采用编码压缩技术，减少传输数据量，是提高通信速度的重要手段。因此，更要求数据量压缩。4.1.2编码压缩的可能性众所周知，视频由一帧一帧的图像组成，而图像的各像素之间，无论是在行方向还是在列方向，都存在着一定的相关性，即冗余度。应用某种编码方法提取或减少这些冗余度，便可以达到压缩数据的目的。常见的静态图像数据冗余包括：1.空间冗余这是静态图像存在的最主要的一种数据冗余。一幅图像记录了画面上可见景物的颜色。同一景物表面上各采样点的颜色之间往往存在着空间连贯性，从而产生了空间冗余。4.1.2编码压缩的可能性2.时间冗余在视频的相邻帧间，往往包含相同的背景和移动物体，因此，后一帧数据与前一帧数据有许多共同的地方，即在时间上存在大量的冗余。3.结构冗余在有些图像的纹理区，图像的像素值存在着明显的分布模式。例如，方格状的地板图案等。我们称这种冗余为结构冗余。4.知识冗余有些图像的理解与某些知识有相当大的相关性。例如，人脸的图像有固定的结构。这类4.1.2编码压缩的可能性规律性的结构可由先验知识和背景知识得到，我们称此类冗余为知识冗余。5.视觉冗余事实表明，人类的视觉系统对图像场的敏感性是非均匀的和非线性的。然而，在记录原始图像数据时，通常假定视觉系统是线性的和均匀的，对视觉敏感和不敏感的部分同等对待，从而产生了比理想编码更多的数据，这就是视觉冗余。6.图像区域的相同性冗余是指在图像中的两个或多个区域所对应的所有4.1.2编码压缩的可能性像素值相同或相近，从而产生的数据重复性存储，这就是图像区域的相似性冗余。7.纹理的统计冗余有些图像纹理尽管不严格服从某—分布规律，但是它在统计的意义上服从该规律。利用这种性质也可以减少表示图像的数据量，所以我们称之为纹理的统计冗余。4.2编码模型4.2.1信源编码器和信源解码器4.2.2信道编码器和解码器4.2编码模型如图4.1所示，一个压缩系统包括两个不同的结构块：一个编码器和一个解码器。图像f（x，y）输入到编码器中，这个编码器可以根据输入数据生成一组符号。在通过信道进行传输之后，将经过编码的表达符号送入解码器，经过重构后，就生成了输出图像。4.2.1信源编码器和信源解码器信源编码器的任务是减少或消除输入图像中的冗余。编码的框图如图下图(a)所示。从原理来看主要分为三个阶段，第一阶段将输入数据转换为可以减少输入图像中像素间冗余的数据的集合。第二阶段设法去除原图象信号的相关性，例如对电视信号就可以去掉帧内各种相关，还可以去除帧间相关。这样有利4.2.1信源编码器和信源解码器于编码压缩。第三阶段就是找一种更近于熵，又利于计算机处理的编码方式。下图(b)中显示的信源解码器仅包含两部分：一个符号解码器和一个反向转换器。这些模块的运行次序与编码器的符号编码器和转换模块的操作次序相反。4.2.2信道编码器和解码器当信道带有噪声或易于出现错误时，信道编码器和解码器就在整个译码解码处理中扮演了重要的角色。最有用的—种信道编码技术是由R．w．Hamming提出的。该技术基于这样的思想，即向被编码数据中加入足够的位数以确保可用的码字间变化的位数最小。例如，利用Hamming码将3位冗余码加到4位字上，使得任意两个有效码字间的距离为3，则所有的一位错误都可以检测出来并得到纠止。与4位二进制数b3b2b1b0相联系的7位Hamming(7，4)码字4.2.2信道编码器和解码器h1h2…h5h6h7是：这里表示异或运算。h1，h2和h4位分别是位字段b3b2b0，b3b1b0和b2b1b0的偶校验位。4.2.2信道编码器和解码器为了将汉明（Hamming）编码结果进行解码，信道解码器必须为先前设立的偶校验的各个位字段进行奇校验并检查译码值。一位错误由一个非零奇偶校验字c4c2c1给出，这里，4.3编码压缩方法分类数据压缩的目标是去除各种冗余。根据压缩后是否有信息丢失，多媒体数据压缩技术可分为无损压缩技术和有损压缩技术两类。数据压缩编码分类如图4.3所示。常见的无损压缩技术有：霍夫曼编码算术编码行程编码词典编码4.3编码压缩方法分类常用的一些有损压缩技术包括：预测编码变换编码基于模型编码分形编码其他编码4.3编码压缩方法分类4.4统计编码统计编码属无损编码，它是根据消息出现概率的分布特性而进行的压缩编码。统计编码又可分为定长码和变长码。常用的统计编码有Huffman编码、行程编码和算术编码三种。4.4.1哈夫曼（Huffman）编码4.4.2香农-费诺编码4.4.3算术编码4.4.4游程编码（RLC）4.4.5LZW编码4.4.1哈夫曼（Huffman）编码在一幅图像中，有些图像数据出现的频率高，有些图像数据出现的频率低。如果对那些出现频率高的数据用较少的位数来表示，而出现频率低的数据用较多的位数来表示，这样从总的效果来看还是节省了存储空间。这种编码思想首先由香农（Shannon）提出，哈夫曼后来对它提出了一种改进的编码方法，用这种方法得到的编码称为Huffman编码，Huffman编码是一种变长编码。4.4.1哈夫曼（Huffman）编码1.理论基础一个事件集合x1,x2,…，xn处于一个基本概率空间，其相应概率为p1,p2,…，pn，且p1+p2+…pn=1。每一个信息的信息量为（4-3）定义在概率空间中每—事件的概率不相等时的平均信息量为信息熵，则信息熵H可采用如下公式计算：（4-4）()log()kakIxp11{()}()lognnkkkkakkkHEIxpIxpp4.4.1哈夫曼（Huffman）编码【例4.1】信息熵的计算。设8个随机变量具有同等概率为1/8，则熵：即计算出H=3比特。2.Huffman编码Huffman编码是1952年由Huffman提出的一种编码方法。它在变长编码方法中是最佳的。82111()log388jHXbit4.4.1哈夫曼（Huffman）编码设信源A的信源空间为：其中，现用r个码符号的码符号集对信源A中的每个符号（i＝1，2，…，N）进行编码。具体编码的方法是：(1)把信源符号按其出现概率的大小顺序排列起来；(2)把最末两个具有最小概率的元素之概率加起来；1212:():()()()NNAaaaAPPAPaPaPa1()1NiiPa12:,,,rXxxxia4.4.1哈夫曼（Huffman）编码(3)把该概率之和同其余概率由大到小排队，然后再把两个最小概率加起来，再重新排队；重复步骤,直到最后只剩下两个概率为止。在上述工作完毕之后，从最后两个概率开始逐步向前进行编码。对于概率大的赋予0，小的赋予1。4.4.1哈夫曼（Huffman）编码4.4.1哈夫曼（Huffman）编码经霍夫曼编码后，平均码长为：=0.4×1＋0.30×2＋0.1×4+0.06×5+0.04×5=2.20（bit）61()iiiBPwn4.4.1哈夫曼（Huffman）编码3.Huffman编码的几点说明（1）Huffman编码是最佳的，虽然构造出来的码不唯一，但其平均码长却相同，所以不影响编码效率和数据压缩性能。（2）由于Huffman码的码长参差不齐，因此，存在一个输入、输出速率匹配问题。解决的办法是设置一定容量的缓冲存储器。（3）Huffman码在存储或传输过程中，如果出现误码，可能会引起误码的连续传播，1bit的误码可能把一大串码字全部破坏，因此，限制了Huffman码的使用。4.4.1哈夫曼（Huffman）编码（4）Huffman编码对不同信源其编码效率也不尽相同。当信源概率是2的负次幂时，Huffman码的编码效率达到100％；当信源概率相等时，其编码效率最低。这表明在使用Huffman方法编码时，只有当信源概率分布很不均匀时，Huffman码才会收到显著的效果。（5）Huffman编码应用时，均需要与其他编码结合起来使用，才能进一步提高数据压缩比。例如，在静态图像处理标准JPEG中，先对图像像素进行DCT变换、量化、Z形扫描、游程编码后，再进行霍夫曼编码。4.4.2香农-费诺编码具体编码方法如下：（1）把按概率由大到小、从上到下排成一列，然后把分成两组，，并使这两组符号概率和相等或几乎相等，即：（2）把两组分别按0，1赋值,例如将第一组赋值为0，则第二组赋值为1。然后分组、赋值，不断反复，直到每组只有一种输入为止。将每个所赋的值依次排列起来就是香农-费诺编码。1,...,nxx1,...,nxx1,...,kxxnkxx,...,111()()knijijkPxPx4.4.2香农-费诺编码以前面的数据为例，香农-编码费诺如图4.5所示。4.4.3算术编码理论上，用Huffman方法对源数据流进行编码可达到最佳编码效果。但由于计算机中存储、处理的最小单位是“位”，因此，在一些情况下，实际压缩比与理论压缩比的极限相去甚远。算术编码把要压缩处理的整段数据映射到—段实数半开区间[0，1]内的某一区段，构造出小于1且大于或等于0的数值。这个数值是输入数据流的唯—可译代码。4.4.3算术编码下面通过一个例子来说明算术编码的方法。对一个5符号信源A＝{a1，a2，a3，a2，a4}，各字符出现的概率和设定的取值范围如下表4.2：4.4.3算术编码为讨论方便起见，假定有式中Ns为新子区间的起始位置；Fs为前子区间的起始位置，Cl当前符号的区间左端；Ne为新子区间的结束位置；Fe为前子区间的结束位置；Cr当前符号的区间右端；L为前子区间的长度。按上述区间的定义，最终结果如表4.3：LCFNlss**eerNFCL4.4.3算术编码给定事件序列的算术编码步骤如下：（1）编码器在开始时将“当前间隔”[L，H]设置为[0，1）。（2）对每一事件，编码器按步骤（a）和（b）进行处理4.4.3算术编码（a）编码器将“当前间隔”分为子间隔，每一个事件一个。（b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间隔”。最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。4.4.3算术编码在算术编码中有几个问题需要注意：由于实际的计算机的精度不可能无限长，一个明显的问题是运算中出现溢出，但多数机器都有16、32或者64位的精度，因此这个问题可使用比例缩放方法解决。算术编码器对整个消息只产生一个码字，这个码字是在间隔[0，1]中的一个实数，因此译码器在接收到表示这个实数的所有位之前不能进行译码。算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。4.4.4游程编码（RLC）游程编码是一种利用空间冗余度压缩图像的方法，相对比较简单，也属于统计编码类。设图像中的某一行或某一块像素经采样或经某种方法变换后的系数为，如图4.7所示。某一行或某一块内像素值可分为k段，长度为的连续串，每个串具有相同的值，那么，该图像的某一行或某一块可由下面偶对来表示：，其中为每个串内的代表值，为串的长度。12(,,,)Mxxxixil(,)iigl,1ik121122(,,,)(,),(,),,(,)Mkkxxxglglgligil4.4.4游程编码（RLC）4.4.4游程编码（RLC）串长li就是游程长