第五节　二值图像编码

　　一、概述

　　我们在前几节讨论的图像编码是针对灰度图像（多灰度级图像），当然也包括二值图像。所谓二值图像是指只有两个灰度级的图像即图像内容“非白即黑”。例如由文字组成的文件图、气象图、工程图、地图、军用势态图和指纹卡片等等。由于二值图像只有两个灰度值，因此其统计特性和灰度图像不同。为了压缩描述二值图像的比特数，针对它们本身的统计特性的特点，研究一些图像信源编码方法就很有必要。下面介绍一些基本的二值图像编码方法原理。

　　二值图像编码，如每一个象素用一位二进制码(0或1)代表就称为直接编码。显然用直接编码时，代表一幅图像的比特数也就是图像的象素数。而单位长度的象素称为分辨率。当然分辨率越高图像细节也越清楚，图像质量也就愈高 ，但表示一幅图像的比特数也就愈多 ，这样使传输时间增加，存贮器容量增大，处理运算时间加长。究竟需要用多少分辨率。视图像种类以及应用要求而定 。在一般情况下 ，用主观测试方法确定结果表明。

　　CCLTT建议采用两种分辨率：1728象素／行(8取样／mm)3.58行／mm；1728象素／行（8取样／mm）7.7行／mm。

　　直接编码一幅图像所需总比特数 是由图片的幅面大小 及分辨率决定的。如我国常用公文纸幅面 。(常用的国际标准如CCITT规定的是A4为 )。若分辨率取5点／mm，直接编码时所需比特数为：

　　 兆比特

　　对于这么多的比特，若用我国现在常用的速率为 2.4千比特／秒数传机传送，约需9分钟才能送完。若要达到CCITT规定的三类传真机的传输标准，即每传送一帧公文需１分钟。那么必须将上述表示图像的数码比特数压缩9倍。可见研究二值图像的编码是很有必要的。

　　设 为彩用某种方法编码前后的压缩比，则

　　 （5.5.1）

　　由式（5.5.1）可见：压缩比 取决于图像内容、分辨率、不同的编码方法。二值图像编码压缩一般采用熵编码，以求信息保持而不丢失有效信息。

　　目前二值图像应用颇广，这一方面是由于灰度图像虽能传送更多的信息，但信息量大，实现起来代价高。在许多情况下，用二值图像代替灰度图像也能够满足需要。另一方面许多信源本身就只有二个灰度级。或者传输 、处理时也只要二个灰度级就可以了 。下面仅就常用的跳过白色块编码、游程长度编码、准最佳可变长度编码、预测差值量化编码、识别编码及方块编码方式编码的基本原理介绍一下。

　　二、跳过白色编码WBS

　　大多数二值图像中的黑象素只占图像象数总数很水的一部分。因此若能跳过白色区域 ，只对黑色象素编码 ，这样表示这些图像的比特数将减少，每个象素平均比特数也就可以减少。这就是 WBS编码的基本概念。以下介绍一下一维WBS、二维WBS编码及自适应WBS编码方法。

　　（一）一维WBS编码

　　将图像的每条扫描线分成为若干段，每段有 个象素。对全部是白色的象素段用1比特码字“0”表示。对于至少有一个黑色象素的象素段采用 个比特编码，即第一个比特人为地规定为1，其余的 比特采用直接编码(白色为“0”黑色为“1”码字)。如 ，当某一块为“黑白白黑”时，就用“11001”表示。之所以要在非全白象素段码字前加一个“1”码元，无非是为了可以构成非续长代码，使得一连串码字可以唯一地区分开来。虽然非全白象素段码字增加了一个比特，但由于全白象素段出现概率大，而所用的码字最短，只有一个比特，因而总的比特数还是少的。

　　一维WBS编码平均码字长度 ：

　　 （5.5.2）

　　式中 是段长为 象素段出现全白的概率。可以想象出，段长 不同，全白概率 敢不同。为了获得最小的平均码字长度，对给定的一幅二值图像应有一个最佳 值。

　　（二）二维WBS编码

　　一维WBS编码可以方便地推广到二维。一般的象素段，在二维中变为象素块。假设象素块尺寸为 ，全部为白色的象素块用“0”表示，非全白象素块用 个比特码表示。其中第一个比特为“1”。其余 个比特采用直接编码。

　　（三）自适应WBS编码

　　实验表时：如果能根据图像的局部结构或统计特性，改变其象素块尺寸大小，则WBS编码所用的比特数一定会更少。这就是二值图像的自适应WBS编码。对一维WBS编码，若一条扫描线全为白象素时，则用1比特码“0”表示。非全白象素扫描行，先赋于“1”码元，接着这一行用正常的一维WBS编码。

图 5-5-1　连续白象素代码

　　下面提出一种更复杂的自适应方案。这种方案将象素块分级处理。例如，在一维情况下，先看这一行是否为全白象素。若是，就用1比特“0”码表示，即 行象素数，如1024，若不是，再看看这一行是否有64个连着的全白象素。若有，令 ；若无，再将 取小些如 等等。假若这一行连4个连在一起的全白象素也没有，就用直接编码。因此在一行之前就要加上表示 等于多少的代码。例如 就用代码“10”表示， 用“1110”表示。自适应WBS编码可以使表示图像的比特数下降很多，但为了能够自适应而增加了设备的复杂性。实际先选用时要根据应用要求和具体图像内容综合考虑其经济性和有效性。

　　三、游程长度编码RLC

　　对二值图像从每一扫描行来看，总是由若干段连着的黑象素和连着的白象素组成，我们分别称其为“黑长”和“白长”。当然，黑长和白长总是交替发生。对于不同长度按其发生概率分配以不同长度码字，这就是游程长度编码的基本概念。RLC编码过程中可以将黑长和白长混编起来编码，也可以将两者分别编码。下面交付这两种形式的RLC的比特率分析一下。

　　（一）RLC比特率估计

　　设某二值图像中有长度为 等不同长度的黑长与白长， 为一个扫描行的象素数。若不分黑长和白长都为“游程长度”进行统一编码，则该图像对游程长度的熵 为：

　　 （5.5.3）

　　式中 为游程长度为 黑长和白长所发生的概率。

　　游程平均长度 （即所包含的平均象素数）为：

　　 （5.5.4）

　　那么，游程长度的符号熵 （即象素的熵）为：

　　 (5.5.5）

　　根据测得的游程长度概率 ，就用最佳编码方法，根据信源编码定理，则每个游程的平均长度（即所用平均比特数） 应满足下式：

　　 (5.5.6)

　　对式(5.5.6)各项除以平均游程长度 得到：

　　 （5.5.7）

　　因此，每个象素的熵 即为应用游程长度编码所得的最小比特率的估计值。

　　为了进一步减少表示每个象素的平均比特数即比特率，可以将黑长和白长分开分别编码。这是因为它们出现的概率不同。下面讨论一下它们的最少比特率。

　　设图像白长熵 为：

　　 （5.5.8）

　　式中 表示白长为 个象素发生的概率。

　　则对白长进行最佳编码后，根据信源编码定理应满足下式：

　　 （5.5.9q）

　　式中 为各个白长的平均比特数。

　　为了估算RLC编码的最小比特率，必须知道图像游程长度的概率分布。这是一项十分复杂的测量技术，往往采用某些实用的游程长度概率模型来估算。

　　四、准最佳可变长度码

　　前面我们曾经介绍过哈夫曼编码，对于给定的消息概率集是最为有效。但是，由这种编码结果的码字长度变化大，结构复杂，实现起来困难。下面介绍两种准最佳可变长度编码方法，虽然最小比特率比最佳编码大些，但编码设备却简单多了。

　　（一）线性码（ 码）

　　所谓线性码是一种码字的长度近似地正比于游程长度，常称其为 码。这种码对每一种游程长度分配一个或多个（整数）固定长度块的二进制码字。下面介绍一下这种码的一般构成方法。

　　设 为游程长度， ，其对应的概率分别为 。

　　 为每块的象素数，如果

　　 (5.5.17)

　　其中 是正整数（包括零）， 是满足下列不等式的整数

　　 (5.5.18)

　　则游程长度为 的码字有 比特。其中前面 个比特全为“0”，后面的 个比特为 的二进制表示。

　　例5-3 用 码结构求出游程长度 的码字形式。

　　解：对 码来讲， 。根据式（5.5.18） 应满足：

　　　　

　　根据 的取值范围在1～7之间，再由式（5.5.17）看出 时， 只能取2。将 代入式（5.5.17）即可解出 ，即：

　　

　　码字 个比特为 个“0”。后面N=3比特即为 的二进制表示即010，因此合起来游程长度 的 码表示为：

000

000

010

　　 码对游程长度概率分布呈指数型的图像很有效。如气象图、线条图案和电路图等。详细的分析过程见参考。

　　（二）对数码（ 码）

　　所谓对数码是一种码字长度和游程长度的对数近似成正比的码字结构，简称 码。和 码一样， 码的码字也是由一个或多个固定长度块所组成。但每块的组成方法不同。 码的每块长度为 比特，每块的第一比特为“连续比特”（若采用多个“连续比特”，可以在灰度图像编码中应用），接下去的 比特为“信息比特”。

　　当码字包含 块时，共有 种可能的信息比特组合。在码字内连续比特是相同的。如 码即 。包含两块即 ，则共有 种组合即 四种。

　　若 个游程长度 满足下列不等式：

　　 （5.5.19）

　　则分配给包含 块长度的码字。例如应用 码 ，对游程长度 进行编码。根据式送（5.5.19）取 ，即分配给包含4块长度的码字。可以验证若取 或 就不能满足式（5.5.19）。

　　在译码时，若某块的连续比特和前一块的连续比特相同，则该块和前一块属于同一个码字，否则为新码字的起点（对应于图像中黑白交界处）。 码实现起来简单。实验表明它常常接近于最佳编码，当 码对游程长度 服从以下分布时具有最佳性能。

　　 （5.5.20）

　　当 足够大时，式（5．5．20）变为：

　　 （5.5.21）

　　式（5.5.21）意味着每个游程长度的平均信息量随游程长度的对数增加而增加。

　　五、预测差值量化编码PDQ

　　游程长度编码只利用了沿扫描线方向的象素间相关性。如果进一步利用行间象素相关性则可能达到更高的压缩效果。这就是预测差值量化编码PDQ。可见PDQ实际是一种二维游程编码，它不是对游程长度本身进行编码，而是对扫描线（行）之间的代表两个游程长度变化的差值进行编码。可以推想比特率一定会下降。以下图为例扼要说明一下。

图 5-5-2　PDQ示例

　　 表示游程长度差值量化值；

　　 和 取值为 。

　　 为一条扫描线内的象素个数。

　　编码时对各个 和 及起点和终点按其概率大小分配以适当的码字。用“函数”这个词表示 、 、起点、终点的统称。根据测得的概率，计算出每个函数的熵值 以及各个函数的平均象素数 （图内总象素数除以图像中所有函数的数目），可得出每个象素的熵 为：

　　 （5.5.22）

　　可见这样的测量十分麻烦。一般是用 、 的概率模型[5·18]。据上述资料介绍，在低分辨率时，游程长度编码的压缩比高于PDQ。而在高分辨率时，PDQ压缩比高于游程长度编码。

　　六、一维修正哈夫曼码MHC和改进型READ码

　　（一）一维修正哈夫曼码MHC

　　前面已经介绍过哈夫曼码是一种最佳编码方法。但在一行内象素数多于1000时，实现较为困难。为此，CCITT第十四研究组于1977年提出 建议草案。推荐一维MHC作为文件传真三类机的一维标准码。它具有效率高，差错灵敏度低和容易扩展等优点。而且基本上适合中文文件传真的样张。故提出来供读者参考选用。

　　一维MHC码的格式如下图所示：

图 5-5-3　MHC码结构

　　其中DATA为有效数据。其构成原则是：出现概率大的游程长度分配以较短的码字。当游程长度在0～63之间时用终端码。若游程长度超过63时用形成码+终端码。黑白游程长度所用的终端码和形成码和形成码规定见。

　　EOL为行终了码，以便于在误码后再建同步。其码字规定为11个“0”加1个“1”即“000000000001”。每一行的 还不够每行最小传输时间 时，则填加FILL码。RTC称为返回控制码，由6个EOL组成，在文件结束时应用。

　　（二）改进型READ码

　　CCITT第十四组接受日本1978年推荐的READ码，并结合英国意见综合成改进READ码。作为二维编码。作为二维编码的标准方案之一推荐，它实际上是一维MHC码的扩展。先将图像分块，每块由 行象素组成。其中第一行用MHC码，其余 行用二维编码。

　　七、识别编码

　　对于打字和印刷文字来说，可以利用图形识别的方法来提高压缩效果。如果发送端能识别字符，则每个字符只需传送一个简短的代码就可以了。例如，当允许传送100个不同的字符（对英文字母等来讲已足够）时，则每个字符只要用7比特就足够了。但是如果这些这符用直接方法，将需用很大数量的比特数（视图像要求的清晰度不同而异）。如设每个字约占 英寸，分辨率为100点／英寸，那么直接编码要用 比特。因此采用识别编码压缩比达 。

　　当然这种识别编码方法，实际应用有一定局限性。目前只限于印刷、打字之类的字符图像。对于手写体，由于变化太多，识别困难，目前应用还比较困难。当然这种方法在发端应有字符识别器，而在接收端应有字符发生器。

　　识别编码的常用方法是相关识别。例如对每个英文字母以一定比特编码后，如“ ”用码字{1100010}表示。其它各个字母各用不同的七位二进制码表示，这些码字就作为样本。例如待识别的码字为{1100000}，则将其为 的样本{1100010}相比较（如用模2相加），只得一个“1”字的不同，而与其它样本相比都大于1个“1”字的不同，则可识别{1100000}为“ ”字。

　　如果允许图像有一定的降质，应用某些近似地识别编码方法可使压缩比提高很多。资料中提出一种近似的识别编码方法。它对报纸和图片用1000点／英寸分辨率取样，以 个象素为单元把图像分成若干块。如果只使用图形中全部象素可能的排列中的一小部分。对其进行编码作为样本，如对 单元的 种可能的排列中选出62种排列图形就能得到满意的图像。这样不必使用任何统计编码就可以得到 的压缩比。( ，即每块只需6比特码就行了，原来直接编码需64比特)。在接收端待识别的图形如不属于给定的样本，就用与其最匹配的样本来代替。这就引起了失真。只要原来选择的样本合适，图形降突飞猛进不会太大。

　　八、方块编码

　　所谓方块编码，就是把图像分成若干块，每块包括一定的象素 ， 和 分别是该方块中水平和垂直方向的象素数，然后按每块内象素的不同排列所出现的概率分配以不同长度的码字。一般是经常出现的分配短码，不常出现的分配长码，从而使平均码长缩短来提高压缩比。

　　方块编码最先用于二值编码，如传真图像，后来推广应用到灰度图像。由于设备简单，可以用于实时处理或传输系统中，因此引起了人们越来越广泛的重视。例如用于航天飞机上传送二值图像。在低清晰度图像的传输方面也获得了令人鼓舞的结果，自适应新高度块编码出现使方块编码能适应变化的图像。

　　（一）二值图像的方块编码

　　在二值图像中取方块尺寸 ，则方块中象素可能有 个不同的排列，即为 个消息集合。为了取得最高的压缩比，对这些方块可以用哈夫曼码。但当方块尺寸大于 时，消息集合数量太大，以致使哈夫曼码很难应用，因此就提出了次最佳的编码方法。

　　从对下图方块结构的统计分析可以看出，全白的方块最经常出现。因此分配给最短的码字“0”，而其他结构用直接编码，所用码字为 比特，并附加前缀码“1”。这种码也可以讲是可变长度码，不过只有两种长度，即1比特和 比特。若设全白方块出现的概率为 ，则方块的平均码字长度 为

图 5-5-4　前缀方块码结构

　　 （5.5.23）

　　从式（5.5.23）可以看出 大一些可以使平均码字长度 短些。但是若已给定图像清晰度和方块尺寸 ，那么 也就决定了。在这种情况下要进一步压缩 ，就必然引入一定失真。例如我们将方块中不超过 个黑象素的方块也算作为全白方块。那么 必然增加了，使压缩比提高。实验表时这是允许的，因为人的眼睛分辨率有限，对于一些所谓“不显眼”的失真往往感觉不出来。根据人的视觉特性选择合适的 （称 为失真因素），来提高压缩比，这种方法也称视觉心理编码。

　　（二）二值图像的自适应方块编码

　　由于二值图像（如传真图片）具有很高的非恒稳性，也就是说这些图像的黑白占空比变化很大，或者说图像的信息量变化很大。针对这个情况，人们设计出随其局部活动性变化而变化各种自适应方块编码，以改善前缀方块编码的性能。有连续适应方块编码；适应逐行方块编码；镶嵌方块编码以及自适应方块编码等。前三种压缩比提高不大，约10%左右。下面我们简介一下自适应方块编码：

　　自适应编码是这样进行的，开始图像被分成大方块，称其为起始方块，并被编码。如果某起始方块中所有象素均为白象素，则该方块编码为“0”。否则，加前缀“1”。然后再将这些有前缀的方块分成若干小方块，按上面同样方法进行编码，直到最后用通常的前缀方块编码的基本方块为止。这种逐级划分方块比较简单，因为只需找出全白方块。

　　1.自动适应一维方块编码

　　设只用两种方块 和 ，而且 。其中 为大于1的整数。对于宽度为 的全白方块编为“0”码，而其他宽度为 的 个小方块非全白方块加前缀“1”，再用一般的前缀方块码给予编码。那么每一个宽度为 的方块的平均长度为：

　　 （5.5 24）

　　每个象素的平均比特数 则为 ，而对方块宽度从 到 的一般表示式为：

　　 （5.5.25）

　　利用马尔柯夫模型，在一定的条件下，利用式（5.5.26）可以得出最佳的方块尺寸 。不过，一般常用有二类宽度的方块尺寸(对一维分割情况)为：

　　（1）1024、25、5个象素的方块

　　（2）1024、64、16、4个象素的方块

　　后者能给出更高的压缩比，而且可以利用方块尺寸为2的幂数的优点。

　　2.用一维分割二维自动适应方块编码

　　一维分割二维自动适应方块编码和一维自动适应方块编码十分相似，只是用 方块来代替 即可。因此每个象素的比特数为：

　　 （5.5.26）

　　3.用二维分割二维自动适应方块编码

　　为分析方便，假设方块只有两种尺寸即 ； 且 。因此一个 方块中包含了 个 方块。一个 方块的平均码长度为：

　　 （5.5.27）

　　在一般情况下：

　　 （5.5.28）

　　同样应用马尔柯夫模型也可以得出最佳的 。常用方块尺寸： 、 、 、 。

　　4.自动适应方块编码的引伸

　　为了改进自动适应方块编码的性能，又提出了更为复杂的编码方法。下面仅介绍

　　（1）修正自动适应 、 、 和 方块编码：

　　根据二值图像的结构统计特性分析出全白象素方块出现的可能性最大，因此给予“0”码表示。而全黑象素方块出现的可能性仅次于全白象素方块，因此用稍长的码“11”表示，而其他结构方块（即非全白或非全黑方块）则以“10”为前缀码，在“10”码字后面再用直接编码方法。实验表明这样修正后又可以提高压缩比10%左右。

　　（2）自动适应 、 、 和 哈夫曼方块编码：

　　由于自动适应方块划分到最后即最小的方块只有 个象素，只有 不同的概率，所以对 方块可用哈夫曼码。实验表明这种方法以修正自动适应方块编码又可以提高10－20%的压缩比。

　　（3）模2的一维自动适应方块编码

　　这种方法首先使每一个象素灰度和上一行相邻的象素进行模2加。因此得到了差值图像用一维自动适应方块编码。可见对于图像中有许多垂直线条的图像（如工程图表等）特别适用。面对如气象图之类的就没有多少价值。