6.3无损压缩编码 信源的熵 信源 信道 信宿 图6.3.1一个简单的信息集统模型 信息的来源称为信源。信源发出信息后通过信道传送到接 收方，称为信宿。 若信源由J个符号组成信源集：A={a,a2,…,4}对应各符号出 现的概率为P(A)={P(a),P(a2),…,P(a)},且a,与a,(i≠j)不相 关，则该信源的平均随机程度或平均信息量就称为信源的熵， 表示为 H(A)=->P(a,)log2 P (a,) Digital Image Processing
Digital Image Processing Digital Image Processing ▓信源的熵 图6.3.1 一个简单的信息系统模型 信息的来源称为信源，信源发出信息后通过信道传送到接 信息的来源称为信源，信源发出信息后通过信道传送到接 收方，称为信宿。 收方，称为信宿。 ▓若信源由J个符号组成信源集： 个符号组成信源集： 对应各符号出 现的概率为 ，且 与 不相 关，则该信源的平均随机程度或平均信息量就称为信源的熵， 关，则该信源的平均随机程度或平均信息量就称为信源的熵， 表示为 6.3 无损压缩编码 { }J = 21 ",,, aaaA PA Pa Pa Pa ( ) ( ), ( ), , ( ) = { 1 2 " J } i a jia )(j ≠ 2 1 ( ) ( ) log ( ) J i i i H A Pa Pa = = − ∑
6.3无损压缩编码 a;相当于灰度级i,P(a,相当于灰度级出现的频数（概率），即直 方图。信源的熵则表示图像各灰度级的平均比特数或图像信源 的平均信息量。 基本编码定理 1.无失真编码定理 在无干扰条件下，存在一种无失真的编码方法，使编码的 Lg与信源的熵H(A)任意的接近。即 Lag=H(A)+8,廿ε>0 但以H(A)为下限，即Lamg≥H(A)。这就是Shannon的无失真编 码定理。同时，该定理也为我们提供了一个评价无失真编码的 标准。因此，我们可给出描述无失真编码性能的几个参数： Digital Image Processing
Digital Image Processing Digital Image Processing 相当于灰度级i， 相当于灰度级出现的频数（概率），即直 相当于灰度级出现的频数（概率），即直 方图。信源的熵则表示图像各灰度级的平均比特数或图像信源 方图。信源的熵则表示图像各灰度级的平均比特数或图像信源 的平均信息量。 的平均信息量。 ▓基本编码定理 1. 无失真编码定理 无失真编码定理 在无干扰条件下，存在一种无失真的编码方法，使编码的 在无干扰条件下，存在一种无失真的编码方法，使编码的 与信源的熵H(A)任意的接近。即 任意的接近。即 但以H(A)为下限，即 。这就是Shannon Shannon的无失真编 码定理。同时，该定理也为我们提供了一个评价无失真编码的 码定理。同时，该定理也为我们提供了一个评价无失真编码的 标准。因此，我们可给出描述无失真编码性能的几个参数： 标准。因此，我们可给出描述无失真编码性能的几个参数： 6.3 无损压缩编码 i a ( ) P i a Lavg = AHL + ε ε >∀ 0,)( avg AHL )( avg ≥
6.3无损压缩编码 (1)编码效率n H(A) (2)元余度R。 RD=(1-)×100% (3)压缩比CR m CR=1 其中，为采用自然编码时的码长。此时，式中分母Lg有下 限。则对应最大压缩比为： (CR m H(A) Digital Image Processing
Digital Image Processing Digital Image Processing 6.3 无损压缩编码 （1） 编码效率η （2） 冗余度 （3） 压缩比 其中，m为采用自然编码时的码长。此时，式中分母 为采用自然编码时的码长。此时，式中分母 有下 限，则对应最大压缩比为： 限，则对应最大压缩比为： ( ) avg H A L η = RD = −η × %100)1( RD CR avg R L m C = Lavg max ( ) ( ) R m C H A =
6.3无损压缩编码 2.变字长编码定理 在变字长编码中，对出现概率P(☑)大的信符☑赋予短码字， 而对P(a,小的☑，赋予长码字。如果码字长度严格按照所对应信 符的出现概率大小逆序排列，则编码的平均码长不会大于任何 其它排列方式。 即若P(a)≥P(a)≥P(a)≥…则l(a,)≤l(a)≤l(a)≤… 下面将介绍利用变字长编码定理进行无失真编码的两种常 用方法一霍夫曼编码法和算术编码法。 Digital Image Processing
Digital Image Processing Digital Image Processing 2．变字长编码定理 ．变字长编码定理 在变字长编码中，对出现概率 在变字长编码中，对出现概率 大的信符 赋予短码字， 而对 小的 赋予长码字。如果码字长度严格按照所对应信 赋予长码字。如果码字长度严格按照所对应信 符的出现概率大小逆序排列，则编码的平均码长不会大于任何 符的出现概率大小逆序排列，则编码的平均码长不会大于任何 其它排列方式。 其它排列方式。 即若 则 下面将介绍利用变字长编码定理进行无失真编码的两种常 下面将介绍利用变字长编码定理进行无失真编码的两种常 用方法－霍夫曼编码法和算术编码法。 用方法－霍夫曼编码法和算术编码法。 ( )i 6.3 无损压缩编码 P a i a ( ) P a j j a () ( ) ( ) Pa Pa Pa i jk ≥≥≥" () ( ) ( ) i jk la la la ≤ ≤ ≤
6.3无损压缩编码 ■霞夫曼编码法 覆夫曼编码法是消除编码冗余最常用的方法，它实际上是变 长编码定理的一种实现算法。其编码过程分为2步： 1.缩减信符数量 (1)将输入符号 (图像中的灰度级)☑按出现概率P(a,)由大 到小排列，即 P(a)≥P(a)≥P(a)≥… (2)将最小的两个P(α，)相加，形成一个新的概率集合（此时就 缩减了一个P(a,)，再按(1)重复直到只剩下两个概率为 止。 Digital Image Processing
Digital Image Processing Digital Image Processing 6.3 无损压缩编码 ▓霍夫曼编码法 霍夫曼编码法是消除编码冗余最常用的方法，它实际上是变 霍夫曼编码法是消除编码冗余最常用的方法，它实际上是变 长编码定理的一种实现算法。其编码过程分为 长编码定理的一种实现算法。其编码过程分为2步： 1.缩减信符数量 （1）将输入符号（图像中的灰度级） ）将输入符号（图像中的灰度级） 按出现概率 由大 到小排列，即 （2）将最小的两个 ）将最小的两个 相加，形成一个新的概率集合（此时就 相加，形成一个新的概率集合（此时就 缩减了一个 ），再按（1）重复直到只剩下两个概率为 ）重复直到只剩下两个概率为 止。 i a ( ) P i a () ( ) ( ) Pa Pa Pa i jk ≥≥≥" ( ) P i a ( ) P ai