第二节 熵编码方法（一） 图像熵和平均码字长度
1.图像熵（Entropy）
设数字图像象素灰度级集合为
，其对应的概率分别为
。按信息论中信源信息熵定义，数字图像的熵
为式（5.2.1）所示。
（比特） （5.2.1）
由此式可见，图像熵
是表示其各个灰度级比特数的统计平均值。
2.平均码字长度
设
为数字图像第
个码字
的长度（二进制代数的位数）。其相应出现的概率为
，则该数字图像所赋于的码字平均长度
为：
(比特) （5.2.2）
3.编码效率
在一般情况下，编码效率往往用下列简单公式表示：
（5.2.3）
式中
为信源熵，
为平违犯码字长度。
要据信息论中信源编码理论，可以证明在
条件下，总可以设计出某种无失真编码方法。当然如编码结果使
远大于
，表明这种编码方法效率很低。占用比特数太多。例如对图像样本量化值直接采用PCM编码，其结果平均码字长度
就远比图像熵
大。最好编码结果使
等于或很接近于
。这种状态的编码方法，称其为最佳编码。它既不丢失信息而引起图像失真，又占用最少的比特数。
例如下面要介绍的哈夫曼编码即属最佳编码方法。若要求编码结果
，则必然丢失信息而引起图像失真。这就是在允许失真条件下的一些失真编码方法。
熵编码的目的就是要使编码后的图像平均比特数
尽可能接近图像熵
。一般是要据图像灰度级数出现的概率大小赋于不同长度码字，概率大的灰度级用短码字，反之，用长码字。可以证明，这样的编码结果所获得的平均码字长度最短。这就是下面要介始的变长最佳编码定理。
（二）变长最佳编码定理
定理：在变长编码中，对出现概率大的信息符号赋于短码字，而对于出现概率小的信息符号赋于长码字。如果码字长度严格按照所对应符号出现概率大小逆序排列，则编码结果平均码字长度一定小于任何其它排列方式。
这个定理就是下面要介始的哈夫曼编码方法理论基础。通过对其证明的介绍进一步加强认识。
设图像灰度级为
；
各灰度级出现概率分别长度为
；
编码所赋于的码字长度分别为
。
则编码后图像平均码字长度
应为：
再令严格按照定理规则进行编码，其结果平均码字长度为
。
为奖其中任两个灰度级不按定理规则编码（即概率大的灰度级赋于长码字。反之，用短码字），而其他所有灰度级仍按定理规则编码所得图像平均码字长度。那么
应等于
加上“不按定理规则编码所啬的平均码字长度”
。只要证明
是大于零，即可以证明上述定理。
令第
和
个灰度级出现的概率分别为
和
，
。与这两个灰度级对应的码字长度分别为
和
。如果不按定理规则赋予这两个码字长度，即使
。那么演算下式：
要据前面假设条件
；
可知这个演算式结果一定大于零。将开始式展开立即可以得到：
由于上式左边第一项是对这两个灰度级不按定理规则编码获得的码字长度统计平均值，而第二项是按照定理规则编码获得的码字长度统计平均值.两项之差当然就是前面定义的
了。到此就可以直观地证明了变长编码定理。
（三）可变长度最佳编码的平均码字长度
设可变长度编码所用码元进制为
，被编码的信息符号总数为
，第
个符号出现的概率为
，与其对应的码字长度为
，这种编码结果平均码字长度
落在下列区间内：
式中
由此可以引导出对某一个信息符号存在下式：
（5.2.4）
对二进制码进一步简化为：
（5.2.5）
可见，码字的长度是由信息符号出现的概率来决定的。这就是下面要介绍的香农编码方法理论基础。
（四）唯一可译编码
有些情况下，为了减少表示图像的平均码字长度，往往对码字之间不加同步码。但是，这样就要求所编码字序列被唯一地译出来。满足这个条件的编码称其为唯一可译编码。也常称为单义可译码。单义可译码往往是采用非续长代码。
1.长代码和非续长代码
若代码中任何一个码字都不是另一个码字的续长，也就是不能在某一个码字后面添加一些码元而构成另一个码字，称其为非续长代码。反之，称其为续长代码。如二进制代码
即为非续长代码，而
则为续长代码。因为码字０１可由码字“0”后加上一个码元“1”构成。
2.单义代码
任意有限长的码字序列，只能被唯一地分割成一个个码字，则这样的码字序列称为单义代码 。单义代码的充要条件是满足克劳夫特（kraft）不等式：
（5.2.6）
式中
为代码中码元种类，对二进制
；
为代码中码字个数；
为代码中第
个码字的长度（即码元个数）.
如代码
，因为是二进制码，则
，共有4个码字
；
；
；
。其相应的长度为
；
；
；
。代入（5.2.６）式可得：
因此可以证明代码
是单义代码。读者可以自己证明代码
就不是单义码。而且可以证明，非续长代码一定是单义码，但单义代码不一定是非续长代码。
哈夫曼编码是概据可变长度最佳编码定理，应用哈夫曼算法而产生的一种编码方法。它的平均码字长度在具有相同输入概率集合的前提下，比其它任何一种唯一可译码都小。因此，也常称其为紧凑码。下面以一个具体便子来说明其编码方法。
（一）编码步骤
（１）先将输入灰度级按出现的概率由大到小顺序排列（对概率相同的灰度级可以任意颠倒排列位置）。
（２）将最小两个概率相加，形成一个新的概率集合。再按第（１）步方法重排（此时概率集合中概率个数已减少一个）。如此重复进行直到只有两个概率为止。
（３）分配码字。码字分配从最后一步开始反向进行，对最后两个概率一个赋于“0”码，一个赋于“1”码。如概率 0.6赋于“0”码，0.4赋于“1”码。（也可以将0.6赋于“1”码 ，0.4赋于“0”码。）如此反向进行到开始的概率排列。在此过程中，若概率不变仍用原码字。如表中第六步中概率0.4到第五步中仍用“1”码。若概率分裂为两个，其码字前几位码元仍用原来的。码字的最后一位码元一个赋于“0”码元 ，另一个赋于“1”码元。如表中第六步中概率0.6到第五步中裂为0.37和0.23，则所得码字分别为“00”和“01”。
（二）前例哈夫曼编码的编码效率计算
根据式（5.2.１）求出前例信源熵为：
根据式（5.2.2）求出平均码字长度为：
根据式（5.2.3）求出编码效率
为：
香农编码方法根据式（5.2.4）或式（5.2.5），按下列步骤进行，
（１）将输入灰度级（信息符号）按出现的概率由大到小顺序排列（相等者可以任意颠倒排列位置）。
（２）按式（5.2.4）或式（5.2.5）计算机各概率对应的码字长度
（３）计算各概率对应的累加概率
，即：
（４）把各个累加概率由十进制转换成二进制数。
（５）将二进制表示的累加概率去掉多于（２）步中计算机的
的尾数，即获得各个信息符号的码字。
计算机其编码效率：
平均码字长变
为：
可见香农编码效率比哈夫曼编码效率低些，但还算是一种高效编码方法。
在数字图像处理技术中，经常使用的不等长码字熵编码法，除以上介绍的哈夫曼和香农编码外，还有一些如
码，适用于输入灰度级概率服从幂律分布的图像。即
(5.2.７)
式中：
；
为一个正常数；
为第
个灰度级出现的概率。
编码效果接近于最佳，如打字图像，而且比哈夫曼编码容易实现。再如移位码（ Ｓ码 ）对具有单调减小概率的输入信号相当有效，也易于实现。所以究竟选用什么方法编码，一方面要调查研究图像本身的特性，另一方面也要从实际应用场合，具体实现的技术性和经济性出发。可以单独使用某一种编码方法，也可以几种方法混合使用。下面列出几种编码方法结果，见表5-2-1。
表 5-2-1 几种编码方法结果
表5-2-1中
码，其中一半比特为信息比特，用二进制自然码。
码即信息比特用一位二进制自然码，
码即信息比特用二位二进制自然码。另一半比特表示“连续”与否，用
表示，对每一个码字
交替赋于0或1，
不变表示码字未结束，否则就是一个新码字。这样就可以区别各个码字。如输入序列为
，其码字分别为0、001、10。用
码表示的码字序列可以是0非曲直
，也可以是
，可见只要字母下有横线的“连续”比特不变，该码字就未结束。如序列中第3到8位是一个码字，其中第3、5、7位连续比特都是1或0。
表5-2-1 中
码表示用２比特码字来实现移位编码。２比特二进制自然码共有四种形式，即
。前三个
给起始三个输入值
赋值，即
，而第四个码字
用作为移位标志。
作为一个实际应用例子 ，下面介绍一下人造卫星图像 存贮用编码方法。Landsat 用四个频道窗口，两个可见光，两个红外同时成象，每帧图像有四幅照片，每张照片包括
兆比特。即使每天有几十幅，数据量也是很大的，所以对数据压缩技术要救十分迫切。如果能将其数据量压缩一半，而又不丢失任何信息，将是很有意义的工作。
图 5-2-1 Landsat一帧四幅照片
图 5-2-1是一帧四幅Landsat实际照片，其直方图如图5-2-2所示。
从图5-2-2（ a）中可以看出128个灰度级中的大多数灰度级并不经常出现，其中三幅图大多数灰度级落在16和48之间。另一幅亮些，大多数在48和64之间。为了使编码时所占用的比特数进一步减少，往往先对输入图像灰度级进行某种“映射”（Mapping）。所谓映射 ，从数学上来讲，就是由一个数的集合变换到另一个数的集合，一般采用线性变换，即
(5.2.8)
图 5-2-2 图5-2-1中的直方图
写成矩陈形式为：
(5.2.9)
进行什么样的变换取决于矩陈A的形式，例如A选择下列形式：
(5.2.10)
即可以获得“差分映射”。差分映射前后任一无素关系式为：
(5.2.11)
差分映射是常用的。因为在一幅图像中相邻象素灰度级相差不多或基本相同，因此其差值将会比原灰度级个数小得多。故在编码时占用的比特数也就少得多。据此将图5-2-1进行差分映射，即可获得图5-2-2(b) 所示象素灰度级差值直方图。由于差值可正可负，故差值图变为
即256个灰度级。但是差值绝大部分集中在
之间的16个数值上，故选用四位二进制自然码的16个码字来构成移位码，其中14个码字
给差值
赋值，两个码字
和
分别作为负正方身移位标志。反身以此类推。
这样在－７到＋６之间用等长四比特二进制码，其它区域用不等长移位码，所获得全图每个象素平均码字长度为4.3比特。若
采用不等长码字，如哈夫曼码 ，可以使全图每个象素平均比特数降低为约3.5比特 ，这样与原来７比特编码比较要压缩一半 ，大大减少了图像存贮器容量，这对减少卫星体积和重量以及节省向地面传送时间方面是十分有价值的。但是实际应用中，不等长编码因为码字长度不等，在传输和存贮技术上要增加点麻烦。
（一）轮廓编码（Contour Encoding）的概念
一幅图像总是存在许多大小不等的灰度级相同的区域，尤其是一些所谓特写图像，或某些几何图案的物体的照片等由少数恒定灰度级区域组成的图案。这类图像经过数字化以后，所得到的数字图像，同样存在着少数灰度级量化级相同，大小不等的区域。假若我们能够将这些灰度级相同的区域从图像中找出来并给予不同的标志，那么我们只要对能够唯一确定这些区域的一些因素进行编码，也就等于对整个图像进行编码了。很明显，唯一确定某一区域只要在个因素。
（１）包围这个区域的外围边界即轮廓的方身序列。
（２）轮廓的起始点位置（行和列数）。
（３）轮廓所包围区的灰度级值。
可以看出，对每一个轮廓的三个因素编码，要比对轮廓包围区内每个象素都分配以码字节约很多比特数，而且图像细节越少，采用轮廓编码节省的比特数越多。
（二）轮廓的算法
对图像要进行轮廓编码，首先得找出图像中的轮廓，用来寻找轮廓的方法称为轮廓算法。
轮廓算法由两部份组成，一个是计算轮廓方向序列的方法称为
算法；另一个是计算轮廓起始点的方法称为IP(Initial Point)算法。
轮廓算法的步骤是由这两个算法依次交叉进行。即第一个轮廓起始点找到后，进行第一个轮廓方向序列的计算，算完后再寻找第二个轮廓起始点，接着计算第二个轮廓方向序列；如此依次交叉地进行，计算完图中所有轮廓为止。下面分别介绍一个轮廓方向序列及轮廓起始点算法。
1.向序列的计算－
算法
轮廓方向序列就是由轮廓的起始点开如到轮廓上的第二点、第三点，……，直到最后一点再返回起始点为止方向所组成的方向序列。
确定轮廓上一点走向下一点的方向是用“最先左看规则”，即从进入轮廓点（如
点）的方向看去，最先向左方向寻找，若遇到灰度级和
点相同的邻点，则轮廓由
点走向这一点，若左看没有灰度级和
点相同的点，再按向上看、向右看、向下看的顺序寻找，直到找到有灰度级相同的点时，将轮廓由
点移向该点。若四个方向都没有，表示这个轮廓只是由一个象素构成的。
2.廓方向序列的标记
（１）一个轮廓方向序列应用“最先左看规则”找出来以后，这个轮廓就被确定了 。对轮廓上的每一个点 ，概据进入的离开的方向再按所谓“方向标记规则表”给以不同标记。
（２）若遇一个轮廓点有两对进出方向时，即按“方向标记规则表”标记后有两个标志的，再按“合并规则表”合并两个标志为一个标志。见表5-2-2。
ＡＤ
ＲＲ
ＲＤ
ＤＤ
ＲＡ
ＡＡ表5-2-2 合并规则表
（３）不是轮廓上的象素一律给予
标志。可见，当数字图像标记完毕后存贮存器时，要对每一个象素额外分配两个比特来表示其标志符号
。
（三）轮廓起始点的寻找──IP算法
为了寻找轮廓起始点IP，我们使用顺序扫描搜索方法，也就是从数字图像的左角上（第一行，第一列）的象素开始，按行从左到右，按列从上到下逐点顺序扫描，直到右下角最后一个象素为止，对扫描遇到的每一个象素，进行判别是否为办廓起始点IP。如何判别每一个象素是否为IP呢？先来介绍一个“扫描搜索比较表”和“起始点判别准则”。
1.扫描搜索比较表构成规则（CPL）（Comparison Point LIST）：
（１）每扫一行制一个表，当然开始扫描前表是空的。
（２）对每一行扫描从左到右逐点进行判别。若遇到点标志为
，奖该点的灰度级值从表的右端依次填入表中。
若遇到点标志是
，将表中最靠近标志为
灰度级值划去。
若遇到点标志是
或
，表不变化，即不填也不划去什么。
（３）每一行扫描完毕，表也一定是空的，因为轮廓总是封闭的，轮廓通过某一行有向下的点
，必有向上的点
即
点数一定等于
点数。
2.轮廓起始点判别准则
在扫描搜索过程中，凡是符合下列两个条件的就是判定为轮廓起始点IP。
（１）它的标志是
（即不是已确认过的轮廓上的点）。
（２）它的灰度级值不等于扫描搜索表中最靠近的标记为
的点的灰度级值。
这里要注意冰是一幅数字图像的左上角的点（第一行，第一列），总认为是第一个轮廓起始点，这是不难理解的。
（四）应用轮廓算法的一个例子
若给定一幅数字图像如下左图所示，对其进行轮廓算法的步骤如下：
图 5-2-3 轮廓编码例图（１）先将图像各象素都标起为
，见图5-2-3左图
（２）图像左上角点（第一行、第一列）总认为是
。有了
，根据“最先左看规则”找出第一个轮廓走向序列
，同时按“方向规则表”以及“合并规则表”将轮廓
上各点标志为
或
或
等。见图5-2-3右图。
（３）按IP算法寻找第二个轮廓起点
第一扫描行的搜索表为：
扫描的第一点标志为
，其灰度级为“O”填入表的末尾。
扫描的第2、3、4、5、6、7标志为
，不填入表内，即表不变。
第8点标志为
，将表中刚才填入的“0”划去。
可见第一行扫完后，CPL表是空的，表明没有起始点。
第二行扫描搜索表为：
扫描的第一点标志为
，其灰度级为“O”填入表的末尾
扫描第二点标记为
，它的灰度级为“+”，与表中相邻的标记为
的灰度级值“O”不同，因此确定为新的轮廓起始，记为
。
再按
算法找出
，并标记好，见图5-2-4。
再按IP算法找出
，进而找出
，如此继续下去，直到找完全图为止。见图5-2-5。
图 5-2-4 轮廓编码例图
图5-2-5 轮廓编码例图
（五） 编码方法
一幅数字图像轮廓全部找出并标记完毕后，尚需给各轮廓分配码字。假设：
（１）轮廓起始点位置（行和列数）用自然码。
（２）轮廓包围区的灰度级值也用自然码（也可用哈夫曼码）。
（３）轮廓方向序列用链码表示。
