03_数据压缩技术

03数据压缩技术多媒体应用普及的难题：巨量数据的存储和传输解决途径：大容量的光盘存储技术（如：CD-ROM）高速CPUCache图形加速器芯片集成宽带高速网络通信技术数据压缩技术（软件算法，专用芯片）3.1数据压缩的基本原理压缩目的：减少存储量，以节省存储开销降低实时传输量，以提高数据传输效率提取结构数据特征，以供模式识别与特征分析,3.1.1数据压缩的必要性与可能性1.数据压缩的必要性,1分钟数字视频信号的存储空间,数字电视格式,空间时间分辨率,取样率(MHz),量化位数,存储容量(MB),公用中间格式（CIF）,35228830,亮度3；亮度、色差4:1:1共12,270,PAL720,CCIR601,48030,亮度13.5亮度、色差,1620,号建议,NTSC720,4:2:2,共16,1620,57625,HDTV亮度信号,128072060,60,8,3600,3.1.1数据压缩的必要性与可能性1.数据压缩的必要性视频数据量：根据采样定理，对NTSC彩电信号进行数字化Idata=(4+1.5+0.5)MHz28bits=96Mbits音频数据量：由实验得出,语音带宽为4KHz.数字化后Adata=4KHz28bits=64Kbits可见，数字图像是数字音频数据量的1000倍以上光盘存储能力：一张CD_ROM光盘的标准容量是650MB；由于每字节含2位校验位，即附加数据占25%，故光盘的视频存放量6508(96(1+0.25)43sec结论：即使拥有大容量的光盘存储设备和高速CPU的计算机，仍需采用数据压缩技术，使PC机能适应运动图像处理要求,2.数据的可压缩性数据压缩的可能性：各种媒体数据内部存在冗余及相关性；可采用不同编码与解码算法以减弱相关性，达到压缩目的数据冗余类型：是有效采用各种压缩算法的基本依据空间冗余图像灰度或颜色等特性基本相同的视觉区域编码符号序列中的码字冗余，称信息熵冗余例：像素点P(x,y)具有邻域强相关性空间冗余,时间冗余相邻图幅间（帧间）或相邻音域间的重复与渐变部分人眼视觉暂留特性导致感受与实际之间存在瞬间差异例：F1和F2间时域相关具有时间冗余其他冗余：结构冗余；知识冗余小结：数据可压缩性可用数据D所携带的信息量I及其冗余特征来表示，即IDdu其中，D为数据量，du为D中的数据冗余量,3.1.2压缩模型的构成原理1.数据压缩的基本思想针对特定的数据冗余类型，采用合适的压缩编码方法；对压缩对象的样本空间合理进行样本点划分，建立以少代多或以局部代全体的数据变换关系；从而以最少的数码表示信源或信道信号，减少数据的按位贮存空间和位传输率空间压缩：把相同视觉区（集合块）当作一个整体，以极少的信息量来表示时间压缩：把连续帧间的重复部分或渐变过程中的相似部分当作一个整体，用极少的信息量（样本值）表示,2.压缩过程的框架构成编码过程：原始数据符号化；体现压缩算法及正变换（有内容信息无内容的信号序列）信源编码器：完成大多数压缩任务；可充当信号分析器把输入数据量压缩到与存储器容量相适应的水平把数据传输速率降低到传输介质所能支持的水平信道编码器：侧重解决码制可靠性问题（传输可靠性）把压缩的位流转译成既适应存储又适合传输的信号降低信号调制解调过程中的误码率解码过程：码元恢复与信号合成；体现解压算法及逆变换（无内容的编码数据有内容的还原数据）对称非对称压缩：压解实时；压缩非实时，解压实时,3.2数据压缩方法分类3.2.1图像压缩编码分类信息熵编码：Huffman编码，行程编码，算术编码，LZW编码预测编码：差分线性预测DPCM，自适应线性预测ADPCM，运动补偿帧间线性预测；非线性预测变换编码：最优正交变换（KLT）,离散傅立叶变换（DFT）离散余弦变换（DCT）,WHT变换，wavelet变换矢量量化编码：多段式，分离式，全搜索式子带编码：分频带法，块切割法模型编码（参数编码）：结构编码，基于知识的编码，分析识别合成编码，分形（Fractal）编码混合编码：JPEG编码，MPEG编码，P64编码,3.3常用压缩编码方法第一代编码技术：主要利用数据的统计冗余来达到压缩目的常用方法：信息熵编码，预测编码，变换编码；矢量量化编码3.3.1信息熵编码1.熵编码的基本原理信息熵：信源数据所携带的平均信息量设：信源X的符号集为Xi（i=1,2,N），Xi出现的概率为P(Xi)；等概率值的单位信息量为-logP(X).故信源X的熵定义为这就是熵编码原理的数学依据：信源符号集的平均码长S(X)按熵值来定义信源符号集的最小平均码长，可得到理想编码方案,熵编码的基本思想：根据信源符号出现的概率分布特性，用短码字表示出现概率大的信息，用长码字表示出现概率小的信息；从而减少符号序列中的冗余度，提高符号的平均信息量，达到数据压缩的目的可变字长的统计编码方法数据压缩标准中常用的熵编码方法：Huffman编码算术编码行程编码,2.Huffman编码方法哈夫曼编码：无失真编码的优选算法；已用于JPEG标准的基本系统Huffman算法设计过程统计信源符号出现的概率，以建立Huffman码表把信源符号按概率递减排列，以建立Huffman树沿H树自顶向下对每个符号节点的路径赋予二进制值，以生成符号编码计算信源符号集的平均码长，以验证编码方案的合理性算法实现实例例：设有一组待编码符号Xi|i=1,2,8,其出现频度的统计值为15，10，8，6，6，2，2，1，试用Huffman算法进行编码,讨论：求出信源符号集Xi中每个符号出现的概率P(Xi),以建立初始Huffman码表其中：,根据P(Xi)计算值，按概率递减序把符号集Xi排列成一棵二叉树a.设置各符号Xi的叶节点位置；自底向上计算两个最小概率项之和，作为新的复合项，且以中间节点表示其中，底层叶节点的概率值为左大右小b.沿二叉树逐次计算两个最小概率项之和，并逐次归并成一个复合项，以作为中间节点；直至最后一项到达顶层的根节点c.可以验证：根节点的概率值必为1；即P(Xi)=1,X3X4X5X6X7X8,0.160.120.120.040.040.02,0.06,0.10,0.22,0.28,X1X2X3X4X5X6X7X8,0.300.200.160.120.120.040.040.02,X2,0.20,0.42,X1,0.30,0.58,1.00,1,0,1,0,1,0,1,0,1,0,1,0,1,0,信源符号:,概率:,X1=11X2=00X3=101X4=100X5=011X6=0100X7=01011X8=01010,沿Huffman树自顶向下生成码字a.从根节点开始遍历树，按从左到右顺序依次给每个节点的路径赋予二进制代码（1，0）值b.取出从根节点到每个叶节点的路径上的代码组合，得到该叶节点的码字；这就是信源符号Xi的编码结果c.各信源符号的码字及码长Li可填列在Huffman码表中,计算信源符号集Xi的平均码长La，并与Xi的最小码长比较,最小平均码长：,平均码长:,Huffman算法小结适用场合：可用于非均匀概率分布的信源编码只要码表的信源概率以大量统计数据为基础，就能获得足够好的压缩效果注意点：对于均匀概率的信源，编码会产生定长码失效实际Huffman树及编码不是唯一的，与信源初始条件和左右节点赋值(0,1),(1,0)的选择有关；但任意策略的平均码长应相等，故压缩效率相同在构建Huffman树时，若节点不能逐次依概率降序排列，则码字位长会过于参差不齐，致使硬件实现很不方便；同时，平均码长会增大，因而压缩率降低,3.行程编码方法行程编码：适用于二值图像压缩，是传真编码的标准压缩方法用于灰度图像时，可作混合编码的一部分在JPEG编码中，用于处理DCT交流系数行程：具有相同灰度值的连续符号位串长度；或图像帧内相邻像素之间的相对距离编码格式：沿某一特定方向进行扫描时，对含有连续多个相同值的像元序列，用一个代表值和一个连续位串长度值来代替即（相同值的代表值N，连续位串的长度L）图像灰度行程可描述为：（像素的相同灰度值，像素元素的个数）,实例：把一幅两维图像划分成许多88子块时，每个子块B(i,j)便含有64个像元之间的灰度值分布情况；水平扫描后得到的行程为编码结果：用13对（N,L）数值取代了64个像元的灰度值以少代多思想：编码后，只要存储或传输两个数值（N,L），就可取代L个像元的相同灰度值N；从而代替大量邻域冗余,4.算术编码方法算术编码：在JPEG扩展系统中，取代Huffman编码优点：可在不知信源概率情况下找到合适的编码算法自适应模式用在信源概率分布较均匀的场合；与Huffman编码形成互补数据压缩效率高出Huffman编码约5%算术编码的基本原理基本思想：基于递归概率区间划分的二进制编码具体过程：把信源符号序列Xi|i=1,2,n发生的概率用实数区间0，1上的间隔（Xi的取值范围）来表示；按符号概率大小来分配符号间隔，使0，1随迭代计算次数的增加而逐次变窄；所求最后范围便是替代Xi符号串编码的取值范围,设输入数据为eaiou，其出现的概率和设定的取值范围如下：,字符,a,e,i,o,u,概率,0.2,0.3,0.1,0.2,0.2,范围,0，0.2,0.2,0.5,0.5,0.6,0.6,0.8,0.8,1.0,设编码的数据串为eaiou，令high为编码间隔的高端，low为编码间隔的低端，range为,编码间隔的长度，rangelow为编码字符分配的间隔低端，rangehigh为编码字符分配的间隔高端。初始high=1,low=0,range=high-low一个字符编码后新的low和high按下式计算：low=low十rangeXrangelowhigh=low+rangeXrangehigh,算术编码实例,算术编码实例,(1)在第1个字符e被编码时,e的rangelow0.2，rangehigh0.5，因此：,low0十1X0.20.2high=0十1X0.5=0.5range=high-low=0.5-0.2=0.3,此时分配给e的范围为0.2,0.5。,(2)在第2个字符a被编码时使用新生成范围0.2,0.5,a的rangelow=0,rangehigh=0.2,因此：,low=0.2+0.3X0=0.2,high=0.2+0.3X0.2=0.26,range=high-low=0.26-0.2=0.06,此时分配给ea的范围为0.2,0.26。,算术编码实例,（3）在第3个字符i被编码时，i的rangelow=0.5,rangehigh=0.6,因此：,low0.2+0.06X0.5=0.23high=0.2+0.06X0.6=0.236range=highlow=0.236-0.23=0.006,此时分配给eai的范围为0.23,0.236,(4)在第4个字符o被编码时，o的rangelow=0.6,rangehigh=0.8,因此：,low=0.23+0.006X0.6=0.2336,high=0.23+0.006X0.8=0.2348,range=high-low=0.2348-0.2336=0.0012,此时分配给eaio的范围为0