03_数据压缩技术

03数据压缩技术多媒体应用普及的难题：巨量数据的存储和传输解决途径：①大容量的光盘存储技术（如：CD-ROM）②高速CPU／Cache／图形加速器—芯片集成③宽带高速网络通信技术④数据压缩技术（软件算法，专用芯片）3.1数据压缩的基本原理压缩目的：①减少存储量，以节省存储开销②降低实时传输量，以提高数据传输效率③提取结构数据特征，以供模式识别与特征分析3.1.1数据压缩的必要性与可能性1.数据压缩的必要性1分钟数字视频信号的存储空间数字电视格式空间×时间×分辨率取样率(MHz)量化位数存储容量(MB)公用中间格式（CIF）352×288×30亮度3；亮度、色差4:1:1共12270PAL720×CCIR601480×30亮度13.5亮度、色差1620号建议NTSC720×4:2:2共161620576×25HDTV亮度信号1280×720×6060836003.1.1数据压缩的必要性与可能性1.数据压缩的必要性①视频数据量：根据采样定理，对NTSC彩电信号进行数字化Idata=(4+1.5+0.5)MHz×2×8bit／s=96Mbit／s②音频数据量：由实验得出,语音带宽为4KHz.数字化后Adata=4KHz×2×8bit／s=64Kbit／s可见，数字图像是数字音频数据量的1000倍以上③光盘存储能力：一张CD_ROM光盘的标准容量是650MB；由于每字节含2位校验位，即附加数据占25%，故光盘的视频存放量＝650×8／(96×(1+0.25))＝43sec结论：即使拥有大容量的光盘存储设备和高速CPU的计算机，仍需采用数据压缩技术，使PC机能适应运动图像处理要求2.数据的可压缩性数据压缩的可能性：各种媒体数据内部存在冗余及相关性；可采用不同编码与解码算法以减弱相关性，达到压缩目的数据冗余类型：是有效采用各种压缩算法的基本依据⑴空间冗余①图像灰度或颜色等特性基本相同的视觉区域②编码符号序列中的码字冗余，称信息熵冗余例：像素点P(x,y)具有邻域强相关性—空间冗余⑵时间冗余①相邻图幅间（帧间）或相邻音域间的重复与渐变部分②人眼视觉暂留特性导致感受与实际之间存在瞬间差异例：F1和F2间时域相关—具有时间冗余⑶其他冗余：结构冗余；知识冗余小结：数据可压缩性可用数据D所携带的信息量I及其冗余特征来表示，即I＝D－du其中，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编码，P×64编码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)=1X3X4X5X6X7X80.160.120.120.040.040.020.060.100.220.28X1X2X3X4X5X6X7X80.300.200.160.120.120.040.040.02X20.200.42X10.300.581.0010101010101010信源符号:概率:X1=11X2=00X3=101X4=100X5=011X6=0100X7=01011X8=01010③沿Huffman树自顶向下生成码字a.从根节点开始遍历树，按从左到右顺序依次给每个节点的路径赋予二进制代码（1，0）值b.取出从根节点到每个叶节点的路径上的代码组合，得到该叶节点的码字；这就是信源符号Xi的编码结果c.各信源符号的码字及码长Li可填列在Huffman码表中④计算信源符号集{Xi}的平均码长La，并与{Xi}的最小码长比较1()20.3020.2030.1630.1230.1240.0450.0450.02naiiiLlPX2.6621()()log()2.63niiiSXPXPX最小平均码长：平均码长:⑶Huffman算法小结①适用场合：可用于非均匀概率分布的信源编码只要码表的信源概率以大量统计数据为基础，就能获得足够好的压缩效果注意点：对于均匀概率的信源，编码会产生定长码—失效②实际Huffman树及编码不是唯一的，与信源初始条件和左右节点赋值{(0,1),(1,0)}的选择有关；但任意策略的平均码长应相等，故压缩效率相同③在构建Huffman树时，若节点不能逐次依概率降序排列，则码字位长会过于参差不齐，致使硬件实现很不方便；同时，平均码长会增大，因而压缩率降低3.行程编码方法行程编码：适用于二值图像压缩，是传真编码的标准压缩方法用于灰度图像时，可作混合编码的一部分在JPEG编码中，用于处理DCT交流系数行程：具有相同灰度值的连续符号位串长度；或图像帧内相邻像素之间的相对距离编码格式：沿某一特定方向进行扫描时，对含有连续多个相同值的像元序列，用一个代表值和一个连续位串长度值来代替．即（相同值的代表值N，连续位串的长度L）图像灰度行程可描述为：（像素的相同灰度值，像素元素的个数）实例：把一幅两维图像划分成许多8×8子块时，每个子块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，其出现的概率和设定的取值范围如下：字符aeiou概率0.20.30.10.20.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的rangelow＝0.2，rangehigh＝0.5，因此：low＝0十1X0.2＝0.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.2high=0.2+0.3X0.2=0.26range=high-low=0.26-0.2=0.06此时分配给ea的范围为[0.2,0.26]。算术编码实例（3）在第3个字符i被编码时，i的rangelow=0.5,rangehigh=0.6,因此：low＝0.2+0.06X0.5=0.23high=0.2+0.06X0.6=0.236range=high—low=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.2336high=0.23+0.006X0.8=0.2348range=high-low=0.2348-0.2336=0.0012此时分配给eaio的范围为[0.2336,0.2348]。(5)在第5个字符u被编码时，u的rangelow=0.8,rangehigh=1.0,因此：low=0.2336+0.0012X0.8=0.23456high=0.2348+0.0012X1.0=0.2360range=high-low=0.2360-0.23456此时分配给eaiou的范围为[0.23456,0.2360]。由此，可用[0.23456,0.2360]表示数据串eaiou,换句话说,在