第 6 讲 数据压缩原理与方法第三章 数据压缩技术
3.1 数据压缩的基本原理
3.1.1 数据压缩的可行性
3.1.2 压缩模型的构成原理
3.2 数据压缩方法分类
3.3 常用压缩编码方法
3.3.1 信息熵编码
1,熵编码的基本原理
2,Huffman编码方法
3,行程编码方法
4,算术编码方法第三章 数据压缩技术多媒体应用普及的难题：巨量数据的存储和传输解决途径：
① 大容量的光盘存储技术 （ 如,CD-ROM）
② 高速 CPU／ Cache／图形加速器 — 芯片集成
③ 宽带高速网络通信技术
④ 数据压缩技术 （ 软件算法,专用芯片 ）
3.1 数据压缩的基本原理压缩目的,① 减少存储量,以节省存储开销
② 降低实时传输量,以提高数据传输效率
③ 提取结构数据特征,以供模式识别与特征分析
3.1.1 数据压缩的可行性
1,数据压缩的必要性
① 视频数据量：根据采样定理,对 NTSC彩电信号进行数字化
Idate = (4 + 1.5 + 0.5)MHz× 2× 8bit／ s = 96Mbit／ s
② 音频数据量：由实验得出,语音带宽为 4KHz,数字化后
Adate = 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)=1
③ 沿 Huffman树自顶向下生成码字
a.从根节点开始遍历树,按从左到右顺序依次给每个节点的路径赋予二进制代码 （ 1,0） 值
b.取出从根节点到每个叶节点的路径上的代码组合,
得到该叶节点的码字；这就是信源符号 Xi的编码结果
c.各信源符号的码字及码长 Li可填列在 Huffman码表中
④ 计算信源符号集 {Xi}的平均码长 La，
并以 {Xi}的最小码长比较最小平均码长：
比较验证：
⑶ 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}符号串编码的取值范围计算公式：设编码间隔的低端为 L,高端为 H,间隔长度为 R；
符号分配间隔的低端为 RL,高端为 RH,则：
初值,L0 = 0,H0 = 1,R0 = 1
Li = Li-1 + Ri-1× RLi
Hi = Li-1 + Ri-1× RHi
Ri = Hi - Li (i=1,2,…… n)
其中：下标 i标识当前值,i-1标识上一次的计算值
⑵ 应用实例,待编码符号串为 X1,X2,X3,X4,X5
讨论：
① 依信源 {Xi}的概率大小对区间 [0,1]进行分割,
以确定符号分配间隔 （ 初始子区间 ）
② 逐次迭代计算求取编码间隔值,计算过程如下
X1编码取值,L1 = L0 + R0× RL1 = 0 + 1× 0 = 0
H1 = L0 + R0× RH1 = 0 + 1× 0.3 = 0.3
R1 = H1 - L1 = 0.3 – 0 = 0.3
X2编码取值,L2 = L1 + R1× RL2 = 0 + 0.3× 0.3 = 0.09
H2 = L1 + R1× RH2 = 0 + 0.3× 0.4 = 0.12
R2 = H2 - L2 = 0.12 - 0.09 = 0.03
依次类推：求得 X3,X4和 X5的编码表示范围；
整个计算结果填在上表中算术编码处理过程的编码区间分配可用图解法表示：
以少代多思想,用最终求得的编码表示范围子区间的任何值 （ 如,0.106）,来替代被编码符号串 X1X2X3X4X5
3.1 数据压缩的基本原理
3.1.1 数据压缩的可行性
3.1.2 压缩模型的构成原理
3.2 数据压缩方法分类
3.3 常用压缩编码方法
3.3.1 信息熵编码
1,熵编码的基本原理
2,Huffman编码方法
3,行程编码方法
4,算术编码方法第三章 数据压缩技术多媒体应用普及的难题：巨量数据的存储和传输解决途径：
① 大容量的光盘存储技术 （ 如,CD-ROM）
② 高速 CPU／ Cache／图形加速器 — 芯片集成
③ 宽带高速网络通信技术
④ 数据压缩技术 （ 软件算法,专用芯片 ）
3.1 数据压缩的基本原理压缩目的,① 减少存储量,以节省存储开销
② 降低实时传输量,以提高数据传输效率
③ 提取结构数据特征,以供模式识别与特征分析
3.1.1 数据压缩的可行性
1,数据压缩的必要性
① 视频数据量：根据采样定理,对 NTSC彩电信号进行数字化
Idate = (4 + 1.5 + 0.5)MHz× 2× 8bit／ s = 96Mbit／ s
② 音频数据量：由实验得出,语音带宽为 4KHz,数字化后
Adate = 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)=1
③ 沿 Huffman树自顶向下生成码字
a.从根节点开始遍历树,按从左到右顺序依次给每个节点的路径赋予二进制代码 （ 1,0） 值
b.取出从根节点到每个叶节点的路径上的代码组合,
得到该叶节点的码字；这就是信源符号 Xi的编码结果
c.各信源符号的码字及码长 Li可填列在 Huffman码表中
④ 计算信源符号集 {Xi}的平均码长 La，
并以 {Xi}的最小码长比较最小平均码长：
比较验证：
⑶ 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}符号串编码的取值范围计算公式：设编码间隔的低端为 L,高端为 H,间隔长度为 R；
符号分配间隔的低端为 RL,高端为 RH,则：
初值,L0 = 0,H0 = 1,R0 = 1
Li = Li-1 + Ri-1× RLi
Hi = Li-1 + Ri-1× RHi
Ri = Hi - Li (i=1,2,…… n)
其中：下标 i标识当前值,i-1标识上一次的计算值
⑵ 应用实例,待编码符号串为 X1,X2,X3,X4,X5
讨论：
① 依信源 {Xi}的概率大小对区间 [0,1]进行分割,
以确定符号分配间隔 （ 初始子区间 ）
② 逐次迭代计算求取编码间隔值,计算过程如下
X1编码取值,L1 = L0 + R0× RL1 = 0 + 1× 0 = 0
H1 = L0 + R0× RH1 = 0 + 1× 0.3 = 0.3
R1 = H1 - L1 = 0.3 – 0 = 0.3
X2编码取值,L2 = L1 + R1× RL2 = 0 + 0.3× 0.3 = 0.09
H2 = L1 + R1× RH2 = 0 + 0.3× 0.4 = 0.12
R2 = H2 - L2 = 0.12 - 0.09 = 0.03
依次类推：求得 X3,X4和 X5的编码表示范围；
整个计算结果填在上表中算术编码处理过程的编码区间分配可用图解法表示：
以少代多思想,用最终求得的编码表示范围子区间的任何值 （ 如,0.106）,来替代被编码符号串 X1X2X3X4X5
