数字压缩编码技术
时间:2006-07-10 15:54:52 来源:本站搜集整理 作者:Eric
1 数字压缩的必要性
数字信号有很多优点，但当模拟信号数字化后其频带大大加宽，一路6MHz的普通电视信号数字化后，其数码率将高达167Mbps，对储存器容量要求很大，占有的带宽将达80MHz左右，这 样将使数字信号失去实用价值。数字压缩技术很好地解决了上述困难，压缩后信号所占用的频带大大低于原模拟信号的频带。因此说，数字压缩编码技术是使数字信号走向实用化的关键技术之一，表4－1列出了各种应用的码率。
表4－1 各种应用的码率
有线电视网中数字压缩技术主要包括用于会议电视系统的H.261压缩编码， 用于计算机静止图像压缩的JPEG和用于活动图像压缩的MPEG数字压缩技术。
2 图像压缩编码的可能性
从信息论观点来看，图像作为一个信源，描述信源的数据 是信息量(信源熵)和信息冗余量之和。信息冗余量有许多种，如空间冗余，时间冗余，结构冗余，知识冗余，视觉冗余等，数据压缩实质上是减少这些冗余量。可见冗余量减少可以减少数据量而不减少信源的信息量。从数学上讲，图像可以看作一个多维函数，压缩描述这个 函数的数据量实质是减少其相关性。另外在一些情况下，允许图像有一定的失真，而并不妨碍图像的实际应用，那么数据量压缩的可能性就更大了。
3 图像压缩编码方法的分类
编码压缩方法有许多种，从不同的角度出发有不同的分类方法，比如从信息论角度出发可分 为两大类：
(1)冗余度压缩方法，也称无损压缩，信息保持编码或熵编码。具体讲就是解码图像和压缩 编码前的图像严格相同，没有失真，从数学上讲是一种可逆运算。
(2)信息量压缩方法，也称有损压缩，失真度编码或熵压缩编码。也就是讲解码图像和原始图像是有差别的，允许有一定的失真。
应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分类为：
(1)无损压缩编码种类
·哈夫曼编码
·算术编码
·行程编码
·Lempel zev编码
(2)有损压缩编码种类
·预测编码：DPCM，运动补偿
·频率域方法：正文变换编码(如DCT)，子带编码
·空间域方法：统计分块编码
·模型方法：分形编码，模型基编码
·基于重要性：滤波，子采样，比特分配，矢量量化
(3)混合编码
·JBIG，H261，JPEG，MPEG等技术标准
衡量一个压缩编码方法优劣的重要指标是：
(1)压缩比要高，有几倍、几十倍，也有几百乃至几千倍；
(2)压缩与解压缩要快，算法要简单，硬件实现容易；
(3)解压缩的图像质量要好。
最后要说明的是选用编码方法时一定要考虑图像信源本身的统计特征；多媒体系统(硬件和 软件产品)的适应能力；应用环境以及技术标准。
4 压缩编码方法简介
压缩编码的方法有几十种之多，并在编码过程中涉及较深的的数学里理论基础问题，在此仅介绍 几种常用的压缩编码方法，主要是从物理意义上作一定的解释，读者如对数据压缩专题感兴 趣的话，请参看讲座结束后所附的参考资料。
4.1 莫尔斯码与信源编码
莫尔斯码即电报码，其精华之处在于用短码来表示常出现的英文字母，用长码来表示不常出 现的字母，以减小码率。这种方法非常有效，故延用至今。电视信号经过变换后，例如经差值脉冲编码后，发现前后像素幅度差值小的概率大，而差值大的概率小，因此可用短码表示 概率大的信号，而用长码来代表概率小的信号，从而达到压缩码率的目的。
4.2 差值脉冲编码
电视图像基本上是由面积较大的像块(如蓝天、大地、服装等)组成。虽然每个像块的幅值各 不相同，但像块内各样值的幅度是相近的或相同的，幅值跃变部分相应于像块的轮廓，只占整幅图像的很小一部分。帧间相同的概率就更大了，静止图像相邻帧间的相应位置的像素完 全一样，这意味着前后像素之差或前后帧间相应位置像素之差为零或差值小的概率大，差值 大的概率小。这就是差值编码的基本想法，其原理框图见图4－1(a)。发端将当前样值和前一 样值相减所得差值经量化后进行传输，收端将收到的差值与前一个样值相加得到当前样值。 在这个原理图中，输出的当前样值是输出的前一样值加上收到的差值，由于在当前差值中包 括当前的量化误差，而输出的前一样值又包括前一样值的量化误差，这就造成了量化误差的 积累。因此实用电路为图4－1(b)。这时输入当前样值不是与输入的前一样值相减，而是与 输 出的前一样值相减，因此在差值中已经包含了前一样值的量化误差的负值，在与输出的前一 个样值相加时，这部分量化误差被抵消，只剩下当前的量化误差，这就避免了量化误差的积累。
4.3 预测编码
预测编码利用像素的相关性，可进一步减小差值。
从前面的分析可以看出，如果差值编码中小幅度出现的机会增加，由于其对应的码长较短， 总数码率会进一步减小。如果能猜出下一个样值，那么差值就会是零，当然这种情况是没有 意义的，因为若预先知道下一样值，就不需要进行通信了。但可以肯定，如果我们不仅利用 前后样值的相关性，同时也利用其它行、其它帧的像素的相关性，用更接近当前样值的预测 值与当前样值相减，小幅度差值就会增加，总数码率就会减小，这就是预测编码的方法。预 测编码的电路与差值编码类似，或者说差值编码就是以前一样值为预测值的预测编码，又称为一维预测。如果用到以前行的像素或以前帧的像素，则称为二维或三维预测。在美国国际 电话电报公司(ITT)生产的数字电视机芯片中有一个视频存储控制器芯片VMC2260就用了二维 预测编码，预测器用了三个像素作为下一个像素的预测值，即预测值等于1/2前一像素加1/4 上一行相应像素再加上1/4上一行相应的前一像素。这样不仅利用了前一像素的相关性，也 利用了上一行相应像素的相关性，这样做要比差值编码有更大的码率压缩。如果再用上前一 帧的像素会进一步降低数码率。但为了得到前一帧的像素必须要使用帧存储器，造价比较高 。只用到帧内像素的处理称为帧编码(Intraframe Coding)，用到前后帧像素的处理称为帧 间编码(Interframe Coding)。要得到较大的码率压缩就必须使用帧间编码。JPEG是典型的帧内编码方案，而MPEG是帧间编码方法。前者大多用于静止图像处理，而后者主要用于对运 动图像的处理。
4.4 哈达玛特变换
这是一种有效地去除噪波的方法，噪波的存在往往容易和小幅度变化的信号相混淆，利用多帧平均的方法，对于静止图像，各帧相同，平均的结果其值不变，对于噪波，多帧平均趋于零。
但如果图像中有运动，多帧平均就会造成运动模糊，故不能简单地进行平均，需要根据运动的大小来调节反馈量，即调节平均的程度，做到运动自适应降噪。
大多数情况下是利用帧差信号来判断图像中是否有运动，如果帧差小于一定值，就可视为是因噪波引起的，可取较大的反馈量；如果帧差大于一定值，就可视为图像中有运动。
但在许多情况下，仅从幅度的大小来判断是杂波还是图像是很困难的，如移动的云，近摄的 绿草地等图像信号所得到帧差信号也很小，所以BKU-904采用二维哈达玛特变换(Hadamard Transform)来区分是噪波还是图像信号。先将输入值按4×2分成小块，分别进行实时快速哈 达玛特变换(FHT)。
图像经变换后，转换成相应成分的系数，这些系数分别代表直流分量；水平方向细节和色度 分量等；垂直方向细节；斜方向细节及色度分量等，而噪波变换后均匀散在各系数中。这样 就更有效地区分出信号和噪波，从而达到更有效地进行自适应降噪的目的。
4.5 离散余弦变换
离散余弦变换(Discrete cosine Transform)简称DCT。任何连续的实对称函数的傅里叶变换 中只含余弦项，因此余弦变换与傅里叶变换一样有明确 的物理量意义。DCT是先将整体图像分成N×N像素块，然后对N×N像素块逐一进行DCT变换。 由于 大多数图像的高频分量较小，相应于图像高频成分的系数经常为零，加上人眼对高频成分的 失真不太敏感，所以可用更粗的量化，因此传送变换系数所用的数码率要大大小于传送图像 像素所用的数码率。到达接收端后再通过反离散余弦变换回到样值，虽然会有一定的失真 ，但人眼是可以接受的。
N代表像素数，一般N=8，8×8的二维数据块经DCT后变成8×8个变换系数，这些系数都 有 明确的物理意义：U代表水平像素号，V代表垂直像素号。如当U=0，V=0时，F(0，0)是原 64个 样值的平均，相当于直流分量，随着U、V值增加，相应系数分别代表逐步增加的水平空间频 率分量和垂直空间频率分量的大小。
4.6 量化(Q)
严格说DCT本身并不能进行码率压缩，因为64个样值仍然得到64个系数，如图4－2所示。这 里 给出了一个8×8像块的具体例子，经DCT变换后，比特数增加了。在这个例子中样值是8比特 ，从0~225得到的直流分量的最大值是原来256的64/8倍，即0~2047，交流分 量的范围是-1024~1023。只是在经过量化后，特别是按人眼的生理特征对低频分量和高频分 量设置不同的量化，会使大多数高频分量的系数变为零。一般说来，人眼对低频分量比较敏 感，而对高频分量不太敏感。因此对低频分量采用较细的量化，而对高频分量采用较粗的量 化。
所谓量化，即根据不同的要求，设置不同的量化等级，从而降低数码率。
4.7 游程长度编码
读出数据和表示数据的方式也是减少码率的一个重要因素。读出的方式可以有多种选择 ，如 水平逐行读出、垂直逐列读出、之字型读出和交替读出等，其中之字型读出(Zig－Zag) 是最常用的一种。由于经DCT变换以后，系数大多数集中在左上角，即低频分量区，因此之 字型读出实际上是按二维频率的高低顺序读出系数的，这样一来就为游程长度编码(Runleng th Encoding)创造了条件。所谓游程长度编码是指一个码可同时表示码的值和前面几个零， 这样就可以把之字型读出的优点显示出来了。因为之字型读出在大多数情况下出现连零的机 会比较多，尤其在最后，如果都是零，在读到最后一个数后只要给出“块结束”(EOB)码， 就可以结束输出，因此节省了很多码率。
游程长度指的是由字构成的数据流中各个字符连续重复出现而形成字符串的长度。 基本的游程编码就是在数据流中直接用三个字符来给出上述三种信息，其数据结构如图4－3 所示。
SC表示有一个字符串在此位置，X代表构成串的字符，CC代表串的长度。
游程编码和哈夫曼编码等属于统计编码。
4.8 霍夫曼编码
霍夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。下面引证一个定理，该定 理保证了按字符出现概率分配码长，可使平均码长最短。
定理：在变字长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平 均码字长度为最小。
现在通过一个实例来说明上述定理的实现过程。设将信源符号按出现的概率大小顺序排列为 ：
U：
( a1 a2 a3 a4 a5 a6 a7 )
0.20 0.19 0.18 0.17 0.15 0.10 0.01
给概率最小的两个符号a6与a7分别指定为“1”与“0”，然后将它们的概率相加再与原来的 a1~a5组合并重新排序成新的原为：
U′：
( a1 a2 a3 a4 a5 a6′)
0.20 0.19 0.18 0.17 0.15 0.11
对a5与a′6分别指定“1”与“0”后，再作概率相加并重新按概率排序得
U″：（0.26 0.20 0.19 0.18 0.17）…
直到最后得 U″″：（0.61 0.39）
分别给以“0”，“1”为止，如图4－4所示。}
霍夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。
例如a7从左至右，由U至U″″，其码字为0000；
a6按践线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为0001…
用霍夫曼编码所得的平均比特率为：Σ码长×出现概率
上例为： 0.2×2 0.19×2 0.18×3 0.17×3 0.15×3 0.1×4 0.01×4=2.72 bit
可以算出本例的信源熵为2.61bit，二者已经是很接近了。
4.9 运动估计的运动补偿编码
这是一种帧间编码的方法，其原理是利用帧间的空间相关性，减小空间冗余度。 帧间编码为什么可以减小冗余度，这是因为两帧之间有很大的相似性。如果将前后两帧相减 (移动物体作相应位移)得到的误差作编码所需比特要比帧内编码所需的比特少，帧间差集中 在零附近，可以用短的码字传送。
实现帧间编码的方法是运动估计和运动补偿。用图4－5来说明这个过程。
当前帧在过去帧的窗口中寻找匹配部分，从中找到运动矢量；
根据运动矢量，将过去帧位移，求得对当前帧的估计；
将这个估计和当前帧相减，求得估计的误差值；
将运动矢量和估计的误差值送到接收端去。
接收端根据收到的运动矢量将过去帧作位移(也就是对当前帧的估计)，再加上接收到的误差 值，就是当前帧了。
图4－7 运动估计的全局搜索块匹配 实际上，在做运动估计和运动补偿时，是以16×16的块(称宏块)逐个进行的，如图4－6所示 ，这是将当前帧划分为N×N(16×16)的块。对每一块在过去帧中范围为
的范围内进行搜索，以求得最优匹配，从而得到运动矢量的估值(dx,dy)。衡量匹配好坏 的准则可以是均方误差最小准则。搜索方法可以是全局搜索法，即对搜索范围内的每一点都 计算均方误差，选最小值即对应最优匹配，如图4－7所示。
数字信号有很多优点，但当模拟信号数字化后其频带大大加宽，一路6MHz的普通电视信号数字化后，其数码率将高达167Mbps，对储存器容量要求很大，占有的带宽将达80MHz左右，这 样将使数字信号失去实用价值。数字压缩技术很好地解决了上述困难，压缩后信号所占用的频带大大低于原模拟信号的频带。因此说，数字压缩编码技术是使数字信号走向实用化的关键技术之一，表4－1列出了各种应用的码率。
表4－1 各种应用的码率
有线电视网中数字压缩技术主要包括用于会议电视系统的H.261压缩编码， 用于计算机静止图像压缩的JPEG和用于活动图像压缩的MPEG数字压缩技术。
2 图像压缩编码的可能性
从信息论观点来看，图像作为一个信源，描述信源的数据 是信息量(信源熵)和信息冗余量之和。信息冗余量有许多种，如空间冗余，时间冗余，结构冗余，知识冗余，视觉冗余等，数据压缩实质上是减少这些冗余量。可见冗余量减少可以减少数据量而不减少信源的信息量。从数学上讲，图像可以看作一个多维函数，压缩描述这个 函数的数据量实质是减少其相关性。另外在一些情况下，允许图像有一定的失真，而并不妨碍图像的实际应用，那么数据量压缩的可能性就更大了。
3 图像压缩编码方法的分类
编码压缩方法有许多种，从不同的角度出发有不同的分类方法，比如从信息论角度出发可分 为两大类：
(1)冗余度压缩方法，也称无损压缩，信息保持编码或熵编码。具体讲就是解码图像和压缩 编码前的图像严格相同，没有失真，从数学上讲是一种可逆运算。
(2)信息量压缩方法，也称有损压缩，失真度编码或熵压缩编码。也就是讲解码图像和原始图像是有差别的，允许有一定的失真。
应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分类为：
(1)无损压缩编码种类
·哈夫曼编码
·算术编码
·行程编码
·Lempel zev编码
(2)有损压缩编码种类
·预测编码：DPCM，运动补偿
·频率域方法：正文变换编码(如DCT)，子带编码
·空间域方法：统计分块编码
·模型方法：分形编码，模型基编码
·基于重要性：滤波，子采样，比特分配，矢量量化
(3)混合编码
·JBIG，H261，JPEG，MPEG等技术标准
衡量一个压缩编码方法优劣的重要指标是：
(1)压缩比要高，有几倍、几十倍，也有几百乃至几千倍；
(2)压缩与解压缩要快，算法要简单，硬件实现容易；
(3)解压缩的图像质量要好。
最后要说明的是选用编码方法时一定要考虑图像信源本身的统计特征；多媒体系统(硬件和 软件产品)的适应能力；应用环境以及技术标准。
4 压缩编码方法简介
压缩编码的方法有几十种之多，并在编码过程中涉及较深的的数学里理论基础问题，在此仅介绍 几种常用的压缩编码方法，主要是从物理意义上作一定的解释，读者如对数据压缩专题感兴 趣的话，请参看讲座结束后所附的参考资料。
4.1 莫尔斯码与信源编码
莫尔斯码即电报码，其精华之处在于用短码来表示常出现的英文字母，用长码来表示不常出 现的字母，以减小码率。这种方法非常有效，故延用至今。电视信号经过变换后，例如经差值脉冲编码后，发现前后像素幅度差值小的概率大，而差值大的概率小，因此可用短码表示 概率大的信号，而用长码来代表概率小的信号，从而达到压缩码率的目的。
4.2 差值脉冲编码
电视图像基本上是由面积较大的像块(如蓝天、大地、服装等)组成。虽然每个像块的幅值各 不相同，但像块内各样值的幅度是相近的或相同的，幅值跃变部分相应于像块的轮廓，只占整幅图像的很小一部分。帧间相同的概率就更大了，静止图像相邻帧间的相应位置的像素完 全一样，这意味着前后像素之差或前后帧间相应位置像素之差为零或差值小的概率大，差值 大的概率小。这就是差值编码的基本想法，其原理框图见图4－1(a)。发端将当前样值和前一 样值相减所得差值经量化后进行传输，收端将收到的差值与前一个样值相加得到当前样值。 在这个原理图中，输出的当前样值是输出的前一样值加上收到的差值，由于在当前差值中包 括当前的量化误差，而输出的前一样值又包括前一样值的量化误差，这就造成了量化误差的 积累。因此实用电路为图4－1(b)。这时输入当前样值不是与输入的前一样值相减，而是与 输 出的前一样值相减，因此在差值中已经包含了前一样值的量化误差的负值，在与输出的前一 个样值相加时，这部分量化误差被抵消，只剩下当前的量化误差，这就避免了量化误差的积累。
4.3 预测编码
预测编码利用像素的相关性，可进一步减小差值。
从前面的分析可以看出，如果差值编码中小幅度出现的机会增加，由于其对应的码长较短， 总数码率会进一步减小。如果能猜出下一个样值，那么差值就会是零，当然这种情况是没有 意义的，因为若预先知道下一样值，就不需要进行通信了。但可以肯定，如果我们不仅利用 前后样值的相关性，同时也利用其它行、其它帧的像素的相关性，用更接近当前样值的预测 值与当前样值相减，小幅度差值就会增加，总数码率就会减小，这就是预测编码的方法。预 测编码的电路与差值编码类似，或者说差值编码就是以前一样值为预测值的预测编码，又称为一维预测。如果用到以前行的像素或以前帧的像素，则称为二维或三维预测。在美国国际 电话电报公司(ITT)生产的数字电视机芯片中有一个视频存储控制器芯片VMC2260就用了二维 预测编码，预测器用了三个像素作为下一个像素的预测值，即预测值等于1/2前一像素加1/4 上一行相应像素再加上1/4上一行相应的前一像素。这样不仅利用了前一像素的相关性，也 利用了上一行相应像素的相关性，这样做要比差值编码有更大的码率压缩。如果再用上前一 帧的像素会进一步降低数码率。但为了得到前一帧的像素必须要使用帧存储器，造价比较高 。只用到帧内像素的处理称为帧编码(Intraframe Coding)，用到前后帧像素的处理称为帧 间编码(Interframe Coding)。要得到较大的码率压缩就必须使用帧间编码。JPEG是典型的帧内编码方案，而MPEG是帧间编码方法。前者大多用于静止图像处理，而后者主要用于对运 动图像的处理。
4.4 哈达玛特变换
这是一种有效地去除噪波的方法，噪波的存在往往容易和小幅度变化的信号相混淆，利用多帧平均的方法，对于静止图像，各帧相同，平均的结果其值不变，对于噪波，多帧平均趋于零。
但如果图像中有运动，多帧平均就会造成运动模糊，故不能简单地进行平均，需要根据运动的大小来调节反馈量，即调节平均的程度，做到运动自适应降噪。
大多数情况下是利用帧差信号来判断图像中是否有运动，如果帧差小于一定值，就可视为是因噪波引起的，可取较大的反馈量；如果帧差大于一定值，就可视为图像中有运动。
但在许多情况下，仅从幅度的大小来判断是杂波还是图像是很困难的，如移动的云，近摄的 绿草地等图像信号所得到帧差信号也很小，所以BKU-904采用二维哈达玛特变换(Hadamard Transform)来区分是噪波还是图像信号。先将输入值按4×2分成小块，分别进行实时快速哈 达玛特变换(FHT)。
图像经变换后，转换成相应成分的系数，这些系数分别代表直流分量；水平方向细节和色度 分量等；垂直方向细节；斜方向细节及色度分量等，而噪波变换后均匀散在各系数中。这样 就更有效地区分出信号和噪波，从而达到更有效地进行自适应降噪的目的。
4.5 离散余弦变换
离散余弦变换(Discrete cosine Transform)简称DCT。任何连续的实对称函数的傅里叶变换 中只含余弦项，因此余弦变换与傅里叶变换一样有明确 的物理量意义。DCT是先将整体图像分成N×N像素块，然后对N×N像素块逐一进行DCT变换。 由于 大多数图像的高频分量较小，相应于图像高频成分的系数经常为零，加上人眼对高频成分的 失真不太敏感，所以可用更粗的量化，因此传送变换系数所用的数码率要大大小于传送图像 像素所用的数码率。到达接收端后再通过反离散余弦变换回到样值，虽然会有一定的失真 ，但人眼是可以接受的。
N代表像素数，一般N=8，8×8的二维数据块经DCT后变成8×8个变换系数，这些系数都 有 明确的物理意义：U代表水平像素号，V代表垂直像素号。如当U=0，V=0时，F(0，0)是原 64个 样值的平均，相当于直流分量，随着U、V值增加，相应系数分别代表逐步增加的水平空间频 率分量和垂直空间频率分量的大小。
4.6 量化(Q)
严格说DCT本身并不能进行码率压缩，因为64个样值仍然得到64个系数，如图4－2所示。这 里 给出了一个8×8像块的具体例子，经DCT变换后，比特数增加了。在这个例子中样值是8比特 ，从0~225得到的直流分量的最大值是原来256的64/8倍，即0~2047，交流分 量的范围是-1024~1023。只是在经过量化后，特别是按人眼的生理特征对低频分量和高频分 量设置不同的量化，会使大多数高频分量的系数变为零。一般说来，人眼对低频分量比较敏 感，而对高频分量不太敏感。因此对低频分量采用较细的量化，而对高频分量采用较粗的量 化。
所谓量化，即根据不同的要求，设置不同的量化等级，从而降低数码率。
4.7 游程长度编码
读出数据和表示数据的方式也是减少码率的一个重要因素。读出的方式可以有多种选择 ，如 水平逐行读出、垂直逐列读出、之字型读出和交替读出等，其中之字型读出(Zig－Zag) 是最常用的一种。由于经DCT变换以后，系数大多数集中在左上角，即低频分量区，因此之 字型读出实际上是按二维频率的高低顺序读出系数的，这样一来就为游程长度编码(Runleng th Encoding)创造了条件。所谓游程长度编码是指一个码可同时表示码的值和前面几个零， 这样就可以把之字型读出的优点显示出来了。因为之字型读出在大多数情况下出现连零的机 会比较多，尤其在最后，如果都是零，在读到最后一个数后只要给出“块结束”(EOB)码， 就可以结束输出，因此节省了很多码率。
游程长度指的是由字构成的数据流中各个字符连续重复出现而形成字符串的长度。 基本的游程编码就是在数据流中直接用三个字符来给出上述三种信息，其数据结构如图4－3 所示。
SC表示有一个字符串在此位置，X代表构成串的字符，CC代表串的长度。
游程编码和哈夫曼编码等属于统计编码。
4.8 霍夫曼编码
霍夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。下面引证一个定理，该定 理保证了按字符出现概率分配码长，可使平均码长最短。
定理：在变字长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平 均码字长度为最小。
现在通过一个实例来说明上述定理的实现过程。设将信源符号按出现的概率大小顺序排列为 ：
U：
( a1 a2 a3 a4 a5 a6 a7 )
0.20 0.19 0.18 0.17 0.15 0.10 0.01
给概率最小的两个符号a6与a7分别指定为“1”与“0”，然后将它们的概率相加再与原来的 a1~a5组合并重新排序成新的原为：
U′：
( a1 a2 a3 a4 a5 a6′)
0.20 0.19 0.18 0.17 0.15 0.11
对a5与a′6分别指定“1”与“0”后，再作概率相加并重新按概率排序得
U″：（0.26 0.20 0.19 0.18 0.17）…
直到最后得 U″″：（0.61 0.39）
分别给以“0”，“1”为止，如图4－4所示。}
霍夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。
例如a7从左至右，由U至U″″，其码字为0000；
a6按践线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为0001…
用霍夫曼编码所得的平均比特率为：Σ码长×出现概率
上例为： 0.2×2 0.19×2 0.18×3 0.17×3 0.15×3 0.1×4 0.01×4=2.72 bit
可以算出本例的信源熵为2.61bit，二者已经是很接近了。
4.9 运动估计的运动补偿编码
这是一种帧间编码的方法，其原理是利用帧间的空间相关性，减小空间冗余度。 帧间编码为什么可以减小冗余度，这是因为两帧之间有很大的相似性。如果将前后两帧相减 (移动物体作相应位移)得到的误差作编码所需比特要比帧内编码所需的比特少，帧间差集中 在零附近，可以用短的码字传送。
实现帧间编码的方法是运动估计和运动补偿。用图4－5来说明这个过程。
当前帧在过去帧的窗口中寻找匹配部分，从中找到运动矢量；
根据运动矢量，将过去帧位移，求得对当前帧的估计；
将这个估计和当前帧相减，求得估计的误差值；
将运动矢量和估计的误差值送到接收端去。
接收端根据收到的运动矢量将过去帧作位移(也就是对当前帧的估计)，再加上接收到的误差 值，就是当前帧了。
图4－7 运动估计的全局搜索块匹配 实际上，在做运动估计和运动补偿时，是以16×16的块(称宏块)逐个进行的，如图4－6所示 ，这是将当前帧划分为N×N(16×16)的块。对每一块在过去帧中范围为
的范围内进行搜索，以求得最优匹配，从而得到运动矢量的估值(dx,dy)。衡量匹配好坏 的准则可以是均方误差最小准则。搜索方法可以是全局搜索法，即对搜索范围内的每一点都 计算均方误差，选最小值即对应最优匹配，如图4－7所示。 上一篇：视频编解码标准汇总及比较
下一篇：流媒体客户端的结构与原理浅析
文章评论
共有 1 位网友发表了评论 此处只显示部分留言 点击查看完整评论页面