计算机研究与发展
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999　Vol.36　No.7　P.888-891



黑白文档图像的高倍压缩
任明武　曹雨龙　唐振民　胡钟山　杨静宇
摘　要：黑白文档图像不同于常规的文本文件和图像文件，使用常规的压缩算法难以取得较高的压缩倍数.文中分析了常规文档的特性及使用常规算法的优缺点；并针对其特殊性，提出了一种无失真压缩算法，大大提高了压缩倍数，它采用文中提出的分块编码和游程编码的混合编码方法.实验证明，该方法的压缩比字典序压缩（ARJ，PKZIP，LZW等）约提高0.5～1.2，比常规游程编码提高约0.3～0.8.
关键词：无失真压缩，熵，游程编码，分块编码
分类号：TP391
DOCUMENT BINARY IMAGE EFFECTIVE
LOSSLESS COMPRESSION 
REN Ming-Wu
（Department of Computer Science, Nanjing University of Science and Technology, Nanjing 210094）
CAO Yu-Long
（Department of Computer Science, Nanjing University of Science and Technology, Nanjing 210094）
TANG Zhen-Min
（Department of Computer Science, Nanjing University of Science and Technology, Nanjing 210094）
HU Zhong-Shan
（Department of Computer Science, Nanjing University of Science and Technology, Nanjing 210094）
YANG Jing-Yu
（Department of Computer Science, Nanjing University of Science and Technology, Nanjing 210094）
Abstract：Document binary image is different from text file and general image file. It's very difficult to reach high compress ratios using general compressing algorithms. In this paper, the characteristic of document is analyzed and a lossless mixed coding algorithm is proposed, which uses the block coding and run length coding (RLC). Experiments prove it can increase higher compress ratios by 0.5 to 1.2 compared with dictionary-based coding (ARJ, LZW, PKZIP etc.) and by 0.3 to 0.8 compared with general RLC.
Key words：lossless compression, entropy, run length coding, block coding▲
1　引言
　　信息数字化的高速进行给数据压缩带来严重的挑战.在不同的领域，出现了各种各样的压缩方法［1～5］，例如基于熵的统计编码（Huffman编码、Shannon编码、算术编码等）［2～5］，基于字典的ARJ，LZH，PKZIP等压缩方法［2］，分形编码、小波变换等变换编码［1,3］，分块编码［5］，以及JPEG，MPEG［3］等.
　　熵编码和基于字典的压缩用于压缩常规文本文件和灰度图像的无失真压缩.由于文本文件中大量词句的重复，基于字典的压缩通常能比熵编码取得更好的文本文件压缩效率；分形编码、小波变换等变换编码主要用于灰度图像和彩色图像的有失真压缩，不适用于二值图像和文本图像的压缩；分块编码主要用于二值图像的压缩；JPEG、MPEG专用于静止和运动图像的有失真压缩.
　　文档图像的处理正成为数字信息处理的重要应用之一.文中第二部分分析了二值文档图像的特点和常规的压缩算法；第三部分中，提出了一种高倍压缩的方案；第四部分是实验结果和总结.
2　二值文档图像的压缩
　　我们提出了6个能指导二值图像压缩的参数：黑白比例、细节量、黑占空比、黑长和白长、游程个数和目标个数，分析了二值文档图像的特性；比较分析了常规的WPS、分块编码、熵编码、字典编码、游程编码等二值图像压缩方法.文中像素按比特存储.
2.1　二值文档图像的特点
　　文档的扫描分辨率一般采用能不丢失纵向笔画的最小分辨率，笔画宽度为1～2个像素，是一种弱分辨率图像.二值文档图像在6个方面不同与常规的灰度图像、二值图像和文本文档，主要表现在以下几个方面.
　　（1） 细节量极大.因为黑色像素来源于字符的笔画，且分辨率弱.采用边缘点总数占全部黑色像素总数的比例表示细节量；也可以采用平均笔画宽度来表示细节量.
　　（2） 黑长的种类太少而白长的种类太多.黑色像素来自字符的笔画，所以其种类不多；而由于行间空白、短行、左右边界、页头页尾、字内空白等的存在，白长的种类异常丰富.
　　（3） 游程数目众多.从一个字符到另一个字符之间存在间隙，字符的内部一个个的笔画之间也存在间隙，黑白频繁交叠，导致游程数目众多.
　　（4） 目标小而多.一个字符可能就是一个目标，甚至一个笔画就是一个连通的目标.
　　（5） 黑色像素只占全部像素中极小的比例，一般在5%～20%之间.
　　（6） 黑色像素的散布范围大.文档的行由黑色字符组成，行的分布范围从头到尾，导致黑色像素的散布范围大.我们采用N×N的非全白块的概率表示.设行宽为Wr，行间距为Wg，令：N=Wr+Wg.
2.2　压缩方法分析
　　二值图像的无失真压缩是研究较早的数据压缩方法［5］，存在跳白块编码WBS、游程长度编码RLC和分块编码等多种方法.表2给出了图1、图2的压缩比及平均码长.


图1　英文文章(跳过的部分以灰色表示)


图2　中文文件(跳过的部分以灰色表示)
表1　二值文档图像图1、图2的特性

　图像长宽行宽行间距离笔画宽度黑色比例黑色散布细节黑长种类白长种类游程个数目标个数
图像115099.6132.1710%57%80%23773993954898
1059　　　　　　　　　　
图像210471710.61.427%51%79%52386345931505
760　　　　　　　　　　


表2　二值文档图像图1、图2的压缩比

　熵WBS分块编码ARJRLC压缩比
2×24×41×82×22×32×4Bitbyte
图像12.72.463.272.923.463.854.143.33.94.975.35
图像23.52.743.983.354.364.835.174.15.96.436.90


　　由于二值文档图像是一种弱分辨率图像，线宽为1～2个像素；而且字数太多，即目标太多.使用常规的二值图像轮廓编码，因为大量边缘点的重复跟踪和大量的轮廓起点，甚至达不到一般的压缩效率.
　　WBS基于二值图像中黑色像素只占图像中很小的比例，因此它跳过全白区域而对非全白区域直接编码.在文档图像中，虽然黑色像素只占图像中很小的比例，但因黑色像素的散布范围非常大，得不到高的压缩比.
　　与WBS相比，分块编码采用最佳变长编码定理，按每块内像素的不同排列所出现概率的不同进行变长编码，其压缩比高于WBS.在文档图像中，由于细节非常丰富、黑色像素比例非常小而散布范围非常大、黑色的行和白色的行间交织，当分块较小时，使得除全白块外太多和全黑块太少外，其它块的概率相差不大，从而得不到较高的压缩比且难以自适应分层编码.
　　在二值图像中，有一个有趣的特性就是黑白交织.基于字典序的编码可以有效利用…B0B1…Bn…W0W1…Wm…B0B1…Bk…的序列特性建立字典进行编码.但由于黑长种类很少而白长种类极多，可知大小一定的黑长和大小一定的白长的相关性很小，编码字典中较长词组被使用的概率较小，难以达到高的压缩比.表2中分别给出了以bit（1个像素）和Byte为单位（8个像素）建立字典得到的压缩比.
　　RLC是文档图像压缩中常用的方法，其压缩比高于WBS和分块编码，它能充分利用文档图像的内在属性：（1）黑长来自字符的笔画，笔画的使用显然是不均匀的，而且黑长的种类较少，便于使用最佳变长编码定理；（2）使用白长能把多行连续的行间空白、页头页尾空白、上一行的右边空白和下一行左边空白的仅表示为一个白长.其压缩比高于基于字典序编码，但因白长的种类太多，压缩后得到的白长的平均码长较大，在一定程度上降低了压缩比. 图1、图2的白长和黑长的平均码长分别为4.06/2.41，4.64/2.51. 
3　高倍压缩
　　本文提出了一种基于减少白长种类、从而减小白长的平均码长，提高RLC压缩比的方法.使用分层编码，依据行宽、行间距、笔画宽度等参数选择一定的块大小，将图像分成2层，每层分别使用RLC编码.第一层记录块信息，将全白块赋以1个比特‘0’、非全白块赋以1个比特‘1’.第二层中只把标记为‘1’的块参加游程的计算，从而有效地减小了白长、白长的种类.
　　由于行间空白、短行、左右边界、页头页尾、字内空白等的存在，又白色像素的占空比达到80%～90%，跳掉大量的白块，可使白长的种类大大减少.仅在极少情况下，跳白块刚好跳掉相邻黑长之间的白长，所以认为跳白块处理后游程个数不变、黑长的种类不变.
　　设hb为直接对黑长编码的熵，hw为直接对白长编码的熵，Nw为白长的个数，Nb为黑长的个数，S为图像的像素点总数，b为图像的平均码长，r为图像的压缩比，则有：
|Nw-Nb|≤1　　　　(1)
　　　(2)
　　(3)
　　由式(3)可知，图像压缩比反比于白长平均码长与黑长平均码长之和.已知跳白块处理后白长的种类N′w小于原图像中白长的种类Nw，令，n=Nw-N′w,设h′w为跳白块后图像的白长平均码长，pi为种类数减少1的过程，则经过p1p2…pn-1后，白长的种类数由Nw变至N′w.设hiw为经过pi后白长的平均码长，根据熵的渐化性［1］，可得：hw>h1w>h2w>…>，又，hn-1w=h′w,即跳白块后图像的白长平均码长小于原图像的白长平均码长.
　　设r′1为跳白块后得到的压缩比，I为原图像压缩后的长度，I′1为跳白块压缩后得到的长度，则有：
　　　(4)
　　(5)
　　因为h′w<hw，所以I′1<I.
　　设I′2为块信息压缩后的长度，若I′2<I-I′1，则证明跳白块后增加了图像的压缩比.因为I-I′1>0，因此只需要选择合适的分块大小N×M，即可增加压缩比.设原图像长宽分别为Tb，Tw，则有：
　　　(6)
　　其中r′2是分块信息的压缩倍数，r′2>1；［］表示取最接近的整数.
　　由此可知，分块越大，则I′2可能越小；但白长种类的减少可能越小，I′1可能越大.对特定的应用背景，可选择固定的分块大小，取得最优的压缩比.
表3　图2的压缩结果

　原始图像3×34×48×810×10
跳白后块信息跳白后块信息跳白后块信息跳白后块信息
白长种类38685152961181257313559
黑长种类525592554052425245
白平均码长4.643.093.333.503.234.103.634.203.56
黑平均码长2.512.603.102.553.422.513.882.513.91
游程个数345933340569053402137053459684534589593
压缩比6.438.363.977.724.026.963.896.863.56
6.786.906.786.73

　　跳过白块的原则是尽可能跳过文档图像中的行间空白、短行、左右边界、页头页尾及字内空白.设行宽为Wr，行间距为Wg，笔画宽度为Wp，字宽为Ww，则应：
Wp<N<min{Wg,Wr}　　　(7)
Wp<M<Ww　　　　　　　(8)
　　使用投影和Hough变换可以很容易求得上述参数［6］.表3给出了图2的压缩结果.
4　小结
　　本文提出算法可用于常规文档的无失真压缩，其对文档图像的压缩比大于常规的二值图像编码方法、熵编码和基于字典序的无失真压缩方法；而且由于白长种类的大大减少，一般少于180种，从而使得后续的对游程长度的算术编码得以快速运行.本文方法在理论和实践中得到了有力的证明，我们使用文中方法对汉字书籍、英文文章、银行支票、手写文稿、英文字典等常规的文档图像进行压缩，证明其压缩比高于常规的ARJ算法约0.5～1.2，高于常规的RLC约0.3～0.8.■
作者简介：任明武，男，1969年6月生，硕士研究生，南京理工大学计算机系讲师，主要研究　　　　　　方向为数字图像处理、计算机视觉、图像编码与压缩.
　　　　　曹雨龙，男，1965年3月生，副教授，研究方向为数字图像处理、计算机视觉等.
　　　　　唐振民，男，1961年4月生，教授，研究方向为数字图像处理、机器人等.
　　　　　胡钟山，男，1973年生，博士研究生，研究方向为图像识别，字符处理等.
　　　　　杨静宇，1941年生，教授，研究方向为人工智能、机器人等.
作者单位：任明武（南京理工大学计算机科学与工程系　南京　210094）
　　　　　曹雨龙（南京理工大学计算机科学与工程系　南京　210094）
　　　　　唐振民（南京理工大学计算机科学与工程系　南京　210094）
　　　　　胡钟山（南京理工大学计算机科学与工程系　南京　210094）
　　　　　杨静宇（南京理工大学计算机科学与工程系　南京　210094）
参考文献：
［1］许织新. 数据压缩. 北京：国防工业出版社，1990
　　　(Xu Zhixin. Data Compression (in Chinese). Beijing: National Defense Industry Press, 1990)
［2］Nelson M. Featuring Fast, Efficient Data Compression Techniques in C. M & T Books Company, USA. 1992
［3］黎洪松. 数字图像压缩编码技术及其C语言程序范例. 北京: 学苑出版社，1994
　　　(Li Hongsong. Digital Image Compression and Coding, C Samples (in Chinese). Beijing: Xueyuan Press, 1994)
［4］Castleman K R. Digital Image Processing. Englewood Cliffs, NJ: Prentice Hall, 1996
［5］陈廷标，夏良正. 数字图像处理. 北京: 人民邮电出版社，1991
　　　(Chen Tingbiao, Xia Liangzheng. Digital Image Processing (in Chinese)， Beijing: People's Post Press，1991)
［6］Schurman J, Bartnect N, Bayer T et al. Document analysis——from pixels to contents. Proc IEEE, 1992， 80(7): 1101～1119
收稿日期：1998-11-06
修稿日期：1999-03-12
