1、0303 数据压缩技术数据压缩技术 多媒体应用普及的难题：巨量数据的存储和传输多媒体应用普及的难题：巨量数据的存储和传输 解决途径：解决途径：大容量的光盘存储技术（如：大容量的光盘存储技术（如：CD-ROMCD-ROM）高速高速CPUCPUCacheCache图形加速器图形加速器 芯片集成芯片集成 宽带高速网络通信技术宽带高速网络通信技术 数据压缩技术（软件算法，专用芯片）数据压缩技术（软件算法，专用芯片）3.1 数据压缩的基本原理数据压缩的基本原理 压缩目的：压缩目的：减少存储量，以节省存储开销减少存储量，以节省存储开销 降低实时传输量，以提高数据传输效率降低实时传输量，以提高数据传输效率
2、提取结构数据特征，以供模式识别与特征分析提取结构数据特征，以供模式识别与特征分析3.1.1 3.1.1 数据压缩的必要性与可能性数据压缩的必要性与可能性 1.数据压缩的必要性数据压缩的必要性1分钟数字视频信号的存储空间数字电视格 式空间时间分辨率取样率(MHz)量化位数存储容量(MB)公用中间格式（CIF）35228830亮度 3；亮度、色差4:1:1 共 12270PAL720CCIR 60148030亮度 13.5 亮度、色 差1620号建议NTSC7204:2:2共 16162057625HDTV亮度信号12807206060836003.1.1 3.1.1 数据压缩的必要性与可能性数据
3、压缩的必要性与可能性 1.数据压缩的必要性数据压缩的必要性 视频数据量：根据采样定理，对视频数据量：根据采样定理，对NTSCNTSC彩电信号进行数字化彩电信号进行数字化 IdataIdata=(4+1.5+0.5)MHz=(4+1.5+0.5)MHz2 28bit8bits=96Mbits=96Mbits s 音频数据量：由实验得出音频数据量：由实验得出,语音带宽为语音带宽为4KHz.4KHz.数字化后数字化后 AdataAdata=4KHz=4KHz2 28bit8bits=64Kbits=64Kbits s 可见，数字图像是数字音频数据量的可见，数字图像是数字音频数据量的10001000倍
4、以上倍以上 光盘存储能力：一张光盘存储能力：一张CD_ROMCD_ROM光盘的标准容量是光盘的标准容量是650MB650MB；由于每字节含由于每字节含2 2位校验位，即附加数据占位校验位，即附加数据占25%25%，故，故 光盘的视频存放量光盘的视频存放量6506508 8(96(96(1+0.25)(1+0.25)43sec43sec 结论：结论：即使拥有大容量的光盘存储设备和高速即使拥有大容量的光盘存储设备和高速CPUCPU的计算机，的计算机，仍需采用数据压缩技术，使仍需采用数据压缩技术，使PCPC机能适应运动图像处理要求机能适应运动图像处理要求 2.2.数据的可压缩性数据的可压缩性 数据压
5、缩的可能性：各种媒体数据内部存在冗余及相关性；数据压缩的可能性：各种媒体数据内部存在冗余及相关性；可采用不同编码与解码算法以减弱相关性，达到压缩目的可采用不同编码与解码算法以减弱相关性，达到压缩目的 数据冗余类型：是有效采用各种压缩算法的基本依据数据冗余类型：是有效采用各种压缩算法的基本依据 空间冗余空间冗余 图像灰度或颜色等特性基本相同的视觉区域图像灰度或颜色等特性基本相同的视觉区域 编码符号序列中的码字冗余，称信息熵冗余编码符号序列中的码字冗余，称信息熵冗余 例：像素点例：像素点P(x,y)P(x,y)具有邻域强相关性具有邻域强相关性 空间冗余空间冗余 时间冗余时间冗余 相邻图幅间（帧间）
6、或相邻音域间的重复与渐变部分相邻图幅间（帧间）或相邻音域间的重复与渐变部分 人眼视觉暂留特性导致感受与实际之间存在瞬间差异人眼视觉暂留特性导致感受与实际之间存在瞬间差异 例：例：F1F1和和F2F2间时域相关间时域相关 具有时间冗余具有时间冗余 其他冗余：其他冗余：结构冗余；知识冗余结构冗余；知识冗余 小结：小结：数据可压缩性可用数据可压缩性可用 数据数据D D所携带的信息量所携带的信息量I I及其冗余特征来表示，即及其冗余特征来表示，即 I I D D dudu 其中，其中，D D为数据量，为数据量，dudu为为D D中的数据冗余量中的数据冗余量3.1.2 3.1.2 压缩模型的构成原理压缩
7、模型的构成原理 1.1.数据压缩的基本思想数据压缩的基本思想 针对特定的数据冗余类型，采用合适的压缩编码方法；针对特定的数据冗余类型，采用合适的压缩编码方法；对压缩对象的样本空间合理进行样本点划分，对压缩对象的样本空间合理进行样本点划分，建立以少代多或以局部代全体的数据变换关系；建立以少代多或以局部代全体的数据变换关系；从而以最少的数码表示信源或信道信号，从而以最少的数码表示信源或信道信号，减少数据的按位贮存空间和位传输率减少数据的按位贮存空间和位传输率 空间压缩：把相同视觉区（集合块）当作一个整体，空间压缩：把相同视觉区（集合块）当作一个整体，以极少的信息量来表示以极少的信息量来表示 时间压
8、缩：把连续帧间的重复部分时间压缩：把连续帧间的重复部分 或渐变过程中的相似部分当作一个整体，或渐变过程中的相似部分当作一个整体，用极少的信息量（样本值）表示用极少的信息量（样本值）表示 2.2.压缩过程的框架构成压缩过程的框架构成 编码过程：原始数据符号化；体现压缩算法及正变换编码过程：原始数据符号化；体现压缩算法及正变换 （有内容信息（有内容信息无内容的信号序列）无内容的信号序列）信源编码器：完成大多数压缩任务；可充当信号分析器信源编码器：完成大多数压缩任务；可充当信号分析器 把输入数据量压缩到与存储器容量相适应的水平把输入数据量压缩到与存储器容量相适应的水平 把数据传输速率降低到传输介质所
9、能支持的水平把数据传输速率降低到传输介质所能支持的水平 信道编码器：侧重解决码制可靠性问题（传输可靠性）信道编码器：侧重解决码制可靠性问题（传输可靠性）把压缩的位流转译成既适应存储又适合传输的信号把压缩的位流转译成既适应存储又适合传输的信号 降低信号调制解调过程中的误码率降低信号调制解调过程中的误码率 解码过程：码元恢复与信号合成；体现解压算法及逆变换解码过程：码元恢复与信号合成；体现解压算法及逆变换 （无内容的编码数据（无内容的编码数据有内容的还原数据）有内容的还原数据）对称非对称压缩：压解实时；压缩非实时，解压实时对称非对称压缩：压解实时；压缩非实时，解压实时3.2 数据压缩方法分类数据压
10、缩方法分类 3.2.1 3.2.1 图像压缩编码分类图像压缩编码分类 信息熵编码：信息熵编码：HuffmanHuffman编码，行程编码，算术编码，编码，行程编码，算术编码，LZWLZW编码编码 预测编码：差分线性预测预测编码：差分线性预测DPCMDPCM，自适应线性预测，自适应线性预测ADPCMADPCM，运动补偿帧间线性预测；非线性预测运动补偿帧间线性预测；非线性预测 变换编码：最优正交变换（变换编码：最优正交变换（KLTKLT）,离散傅立叶变换（离散傅立叶变换（DFTDFT）离散余弦变换（离散余弦变换（DCTDCT）,WHT,WHT变换，变换，waveletwavelet变换变换 矢量量
11、化编码：多段式，分离式，全搜索式矢量量化编码：多段式，分离式，全搜索式 子带编码：分频带法，块切割法子带编码：分频带法，块切割法 模型编码（参数编码）：结构编码，基于知识的编码，模型编码（参数编码）：结构编码，基于知识的编码，分析识别合成编码，分形（分析识别合成编码，分形（FractalFractal）编码）编码 混合编码：混合编码：JPEGJPEG编码，编码，MPEGMPEG编码，编码，P P6464编码编码3.3 常用压缩编码方法常用压缩编码方法 第一代编码技术：主要利用数据的统计冗余来达到压缩目的第一代编码技术：主要利用数据的统计冗余来达到压缩目的 常用方法：信息熵编码，预测编码，变换编
12、码；矢量量化编码常用方法：信息熵编码，预测编码，变换编码；矢量量化编码 3.3.1 3.3.1 信息熵编码信息熵编码 1.1.熵编码的基本原理熵编码的基本原理 信息熵：信源数据所携带的平均信息量信息熵：信源数据所携带的平均信息量 设：信源设：信源X X的符号集为的符号集为X Xi i（i=1,2,i=1,2,N N），），X Xi i出现的概率为出现的概率为P(XP(Xi i)；等概率值的单位信息量为等概率值的单位信息量为-logP(X-logP(X).).故信源故信源X X的熵定义为的熵定义为 这就是熵编码原理的数学依据：这就是熵编码原理的数学依据：信源符号集的平均码长信源符号集的平均码长S
13、(X)S(X)按熵值来定义信源符号集的最小平均码长，可得到理想编码方案按熵值来定义信源符号集的最小平均码长，可得到理想编码方案 熵编码的基本思想：熵编码的基本思想：根据信源符号出现的概率分布特性，根据信源符号出现的概率分布特性，用短码字表示出现概率大的信息，用短码字表示出现概率大的信息，用长码字表示出现概率小的信息；用长码字表示出现概率小的信息；从而减少符号序列中的冗余度，从而减少符号序列中的冗余度，提高符号的平均信息量，达到数据压缩的目的提高符号的平均信息量，达到数据压缩的目的 可变字长的统计编码方法可变字长的统计编码方法 数据压缩标准中常用的熵编码方法：数据压缩标准中常用的熵编码方法：Hu
14、ffman Huffman编码编码 算术编码算术编码 行程编码行程编码 2.Huffman编码方法编码方法 哈夫曼编码：无失真编码的优选算法；哈夫曼编码：无失真编码的优选算法；已用于已用于JPEG标准的基本系统标准的基本系统 Huffman算法设计过程算法设计过程 统计信源符号出现的概率，以建立统计信源符号出现的概率，以建立Huffman码表码表 把信源符号按概率递减排列，以建立把信源符号按概率递减排列，以建立Huffman树树 沿沿H树自顶向下对每个符号节点的路径赋予二进制值，树自顶向下对每个符号节点的路径赋予二进制值，以生成符号编码以生成符号编码 计算信源符号集的平均码长，以验证编码方案的
15、合理性计算信源符号集的平均码长，以验证编码方案的合理性 算法实现实例算法实现实例 例：设有一组待编码符号例：设有一组待编码符号Xi|i=1,2,8,其出现频度的统计值为其出现频度的统计值为 15，10，8，6，6，2，2，1，试用，试用Huffman算法进行编码算法进行编码 讨论：讨论：求出信源符号集求出信源符号集 X Xi i 中每个符号出现的概率中每个符号出现的概率P(XP(Xi i),),以建立初始以建立初始HuffmanHuffman码表其中：码表其中：根据根据P(XP(Xi i)计算值，计算值，按概率递减序把符号集按概率递减序把符号集 X Xi i 排列成一棵二叉树排列成一棵二叉树
16、a.a.设置各符号设置各符号X Xi i的叶节点位置；的叶节点位置；自底向上计算两个最小概率项之和，自底向上计算两个最小概率项之和，作为新的复合项，且以中间节点表示作为新的复合项，且以中间节点表示 其中，底层叶节点的概率值为左大右小其中，底层叶节点的概率值为左大右小 b.b.沿二叉树逐次计算两个最小概率项之和，沿二叉树逐次计算两个最小概率项之和，并逐次归并成一个复合项，并逐次归并成一个复合项，以作为中间节点；直至最后一项到达顶层的根节点以作为中间节点；直至最后一项到达顶层的根节点 c.c.可以验证：根节点的概率值必为可以验证：根节点的概率值必为1 1；即；即 P(XP(Xi i)=1)=1 X
17、3 X4 X5 X6 X7 X8 0.16 0.12 0.12 0.04 0.04 0.020.060.100.220.28X1 X2 X3 X4 X5 X6 X7 X80.30 0.20 0.16 0.12 0.12 0.04 0.04 0.02 X2 0.20 0.42 X1 0.30 0.581.0010101010101010信源符号信源符号:概率概率:X1=11X2=00X3=101X4=100X5=011X6=0100X7=01011X8=01010 沿沿HuffmanHuffman树自顶向下生成码字树自顶向下生成码字 a.a.从根节点开始遍历树，按从左到右顺序从根节点开始遍历树，
18、按从左到右顺序 依次给每个节点的路径赋予二进制代码（依次给每个节点的路径赋予二进制代码（1 1，0 0）值）值 b.b.取出从根节点到每个叶节点的路径上的代码组合，取出从根节点到每个叶节点的路径上的代码组合，得到该叶节点的码字；这就是信源符号得到该叶节点的码字；这就是信源符号X Xi i的编码结果的编码结果 c.c.各信源符号的码字及码长各信源符号的码字及码长L Li i可填列在可填列在HuffmanHuffman码表中码表中 计算信源符号集计算信源符号集XXi i 的平均码长的平均码长LaLa，并与并与XXi i 的最小码长比较的最小码长比较 1()2 0.302 0.203 0.163 0
19、.123 0.124 0.045 0.045 0.02naiiiLl P X 2.6621()()log()2.63niiiS XP XP X 最小最小平均平均码长：码长：平均码长平均码长:Huffman Huffman算法小结算法小结 适用场合：可用于非均匀概率分布的信源编码适用场合：可用于非均匀概率分布的信源编码 只要码表的信源概率以大量统计数据为基础，只要码表的信源概率以大量统计数据为基础，就能获得足够好的压缩效果就能获得足够好的压缩效果 注意点：对于均匀概率的信源，编码会产生定长码注意点：对于均匀概率的信源，编码会产生定长码 失效失效 实际实际HuffmanHuffman树及编码不是唯
20、一的，与信源初始条件和树及编码不是唯一的，与信源初始条件和 左右节点赋值左右节点赋值(0,1),(1,0)(0,1),(1,0)的选择有关；的选择有关；但任意策略的平均码长应相等，故压缩效率相同但任意策略的平均码长应相等，故压缩效率相同 在构建在构建HuffmanHuffman树时，若节点不能逐次依概率降序排列，树时，若节点不能逐次依概率降序排列，则码字位长会过于参差不齐，致使硬件实现很不方便；则码字位长会过于参差不齐，致使硬件实现很不方便；同时，平均码长会增大，因而压缩率降低同时，平均码长会增大，因而压缩率降低 3.3.行程编码方法行程编码方法 行程编码：适用于二值图像压缩，是传真编码的标准
21、压缩方法行程编码：适用于二值图像压缩，是传真编码的标准压缩方法 用于灰度图像时，可作混合编码的一部分用于灰度图像时，可作混合编码的一部分 在在JPEGJPEG编码中，用于处理编码中，用于处理DCTDCT交流系数交流系数 行程：具有相同灰度值的连续符号位串长度；行程：具有相同灰度值的连续符号位串长度；或图像帧内相邻像素之间的相对距离或图像帧内相邻像素之间的相对距离 编码格式：编码格式：沿某一特定方向进行扫描时，沿某一特定方向进行扫描时，对含有连续多个相同值的像元序列，对含有连续多个相同值的像元序列，用一个代表值和一个连续位串长度值来代替即用一个代表值和一个连续位串长度值来代替即 （相同值的代表值
22、（相同值的代表值N N，连续位串的长度，连续位串的长度L L）图像灰度行程可描述为：图像灰度行程可描述为：（像素的相同灰度值，像素元素的个数）（像素的相同灰度值，像素元素的个数）实例：实例：把一幅两维图像划分成许多把一幅两维图像划分成许多8 88 8子块时，子块时，每个子块每个子块B(i,j)B(i,j)便含有便含有6464个像元之间的灰度值分布情况；个像元之间的灰度值分布情况；水平扫描后得到的行程为水平扫描后得到的行程为 编码结果：用编码结果：用1313对（对（N,LN,L）数值取代了）数值取代了6464个像元的灰度值个像元的灰度值 以少代多思想：以少代多思想：编码后，只要存储或传输两个数值
23、（编码后，只要存储或传输两个数值（N,LN,L），），就可取代就可取代L L个像元的相同灰度值个像元的相同灰度值N N；从而代替大量邻域冗余；从而代替大量邻域冗余 4.4.算术编码方法算术编码方法 算术编码：在算术编码：在JPEGJPEG扩展系统中，取代扩展系统中，取代HuffmanHuffman编码优点：编码优点：可在不知信源概率情况下找到合适的编码算法可在不知信源概率情况下找到合适的编码算法自适应模式自适应模式 用在信源概率分布较均匀的场合；与用在信源概率分布较均匀的场合；与HuffmanHuffman编码形成互补编码形成互补 数据压缩效率高出数据压缩效率高出HuffmanHuffman编
24、码约编码约5%5%算术编码的基本原理算术编码的基本原理 基本思想：基于递归概率区间划分的二进制编码具体过程：基本思想：基于递归概率区间划分的二进制编码具体过程：把信源符号序列把信源符号序列XXi i|i|i=1,2,=1,2,n,n发生的概率发生的概率 用实数区间用实数区间00，11上的间隔（上的间隔（X Xi i的取值范围）来表示；的取值范围）来表示；按符号概率大小来分配符号间隔，按符号概率大小来分配符号间隔，使使00，11随迭代计算次数的增加而逐次变窄；随迭代计算次数的增加而逐次变窄；所求最后范围便是替代所求最后范围便是替代XXi i 符号串编码的取值范围符号串编码的取值范围设输入数据为e
25、aiou，其出现的概率和设定的取值范围如下：字符aeiou概率0.20.30.10.20.2范围0，0.20.2,0.50.5,0.60.6,0.80.8,1.0设编码的数据串为eaiou，令high为编码间隔的高端，low为编码间隔的低端，range为编码间隔的长度，rangelow为编码字符分配的间隔低端，rangehigh为编码字符分配的间隔高端。初始high=1,low=0,range=high-low一个字符编码后新的low和high按下式计算：low=low十range X rangelowhigh=low+range X rangehigh算术编码实例算术编码实例算术编码实例算术
26、编码实例(1)在第1个字符e被编码时,e的rangelow0.2，rangehigh0.5，因此：low0十1 X 0.20.2high=0十1 X 0.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的
27、rangelow=0.5,rangehigh=0.6,因此：low0.2+0.06 X 0.5=0.23high=0.2+0.06 X 0.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.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,换句话说,在此范围的数值代码都惟一对应于字符串eaiou。
