非文本区域优先的版面分析方法

版面分析在于提高文档电子化处理过程的智能程度, 自动完成扫描版面的倾斜检测与校正, 版面的区域分割与区域识别, 并为识别后的版面重构提供各区域相对位置等相关信息。

现有的版面分析方法通常可分为三类:自顶向下版面分析方法[1], 自底向上版面分析方法[2], 综合型版面分析方法[3]。随着版面分析算法的深入研究, 人们在原有典型版面分析方法的基础上, 加以改进和综合, 同时使用全局和局部特征来处理比较复杂的版面, 结合了自顶向下和自底向上的分析方法, 既照顾了分割的精确性, 又兼顾了分析处理的时间开销。例如, 基于背景空白的版面切分算法、基于组件的中文版面分析算法、自适应的自顶向下和自底向上算法等。每种方法虽然都有其特长的一面, 但目前尚无一种具有广泛适应性的通用方法。

1 非文本区域优先的版面分析方法

中文版面和英文版面相比, 具有很大差异。中文版面规范性较差 (包含较多的嵌入式矩形版面、文本图像、表格等) , 版面有横竖排版之分, 而且印刷质量普遍不高。再由于汉字本身特点, 有些汉字有几部分组成, 其偏旁部首有时很容易和标点符号相混淆, 甚至会对排版模式的确定造成干扰。针对中文版面的这些特点, 本文采用了非文本块优先的中文版面分析法, 较好地解决了这一问题。

本算法首先对初步划分的块进行特征监测, 优先提取不具备文字结构特征的块, 并将其去除。然后再根据统计参数确定文字块提取版面参数, 对文本区域采用基于游程平滑和最小生成树聚类的版面分析方法提取文本块的外接矩形。

1.1 去噪处理

在扫描文本得到图像时, 由于纸张质量不好, 会产生一些噪声, 对版面分割造成影响。因此, 有必要对文档图像进行去除噪声。

一般来说, 在文档图像中, 文字连通域的数目远远大于图像、标题、表格等其他版面基元的数目。由此, 对文档图像的全部连通域作高度直方图, 取峰值处连通基元的高度作为文本的高度hc。

以hc为基准, 将高度、宽度均大于某一阈值θ×hc (θ×由实验确定) 的连通域看作标题、图像或其一部分, 对这些连通域的周围进行检索, 将交叠、包含以及距离小于某阈值的连通域与其合并, 得到非文本连通域。

由于文本基元和非文本基元可能距离很近, 为了使非文本基元不会对下一步中的平滑操作造成影响, 干扰文本基元的分割, 因此将检测到的非文本连通域去除, 得到的图像称为去噪图像。

1.2 非文本区域的提取

在中文文档图像中, 一般来说, 图形、图像、表格等版面基元都是由较大的连通域组成, 且数目相对较少。而一个汉字可能由几部分构成, 每部分都是一个连通域。这些连通域可能大小、形状彼此有较大差异, 与其它字的连通域也相差较大。但是这些连通域彼此靠得很近, 或相交叠、包含。如果我们把这些连通域看作是一个汉字的连通域, 那么组成文本的连通域就是由大小均匀, 数目众多的较小连通域组成, 并且文字连通域的数目一般远远大于图像、表格等其它版面基元的连通域数目。

据此, 首先对文档图像做连通域提取, 找到文档图像的全部连通域

接着, 将存在包含、交叠情况的连通域合并到一起。包含指两个连通域recti、rectj满足recti⊃rectj。交叠指两个连通域recti、rectj满足:recti∩rectj≠φ。对那些间距小于θc的连通域也合并到一起。经合并后, 一般一个汉字的几个连通域将合并成一个。

以检测到的字体高度hc为标准, 我们可初步划分文本连通域和非文本连通域。将高、宽均大于hc的连通域划分为非文本连通域, 这些非文本连通域一般是表格、图像、标题。

经过以上提取操作后, 我们优先提取不具备文字结构特征的块, 并将其去除。结果如图1所示。

1.3 横、竖排文本分类处理

中文版面分割要求能正确区分横排和竖排这两种不同的排版方式。因此, 得到平滑图像的连通域后, 需要对这些连通域进行分类处理, 以便针对不同类的文本采用不同的聚类策略。

设Ch表示横排文本连通域集合, Cv表示竖排文本连通域集合。对每个连通域cci, 设其高度为h, 宽度为w。预分类的规则如下几个方面。

(1) 若h<μ×hc且w<μ×hc (0<μ<1) , 则检测其四边最近邻, 由最近邻的行列属性来判定它的属性。这种情况主要集中在标点符号, 平滑过程中未能与文字连在一起。

(2) 若h<λ×hc且w≥λ×hc (1<λ<2) , 则判断其为横排文本, 将其添加到Ch。

(3) 若w<λ×hc且h≥λ×hc (1<λ<2) , 则判断其为竖排文本, 将其添加到Cv。

(4) 否则, 判定其为非文本域。该情况主要集中在标题部分。标题的一部分在非文本块提取中可能作为文本被保留下来, 经平滑后连接到一起, 应将其加入图像和标题的非文本连通域。

1.4 最小生成树聚类分割

本文采用压缩路径的克鲁斯卡尔算法[4]构造最小生成树。预分类处理得到的每类文本都可看作是一个带权的完全无向图G (V, E) 。其中︱V︱=n, ︱E︱= (n-1) n/2, n是该类文本所含连通域的数目。每条边edge (i, j) 权值为连通域ci, cj间的距离。用路径压缩的克鲁斯卡尔算法对每类文本进行聚类处理, 对生成的最小生成树, 去除不满足某种规则的边。

由克鲁斯卡尔算法可知, 首先需要计算出边的权值。下面以横排文本为例, 介绍最小生成树聚类分割过程。

横排文本聚类分以下两步。

1.4.1 行内聚类

对连通域cci和ccj, 若dy (i, j) =0, 则边edge (i, j) 权值为dx (i, j) 。否则, 其权值设定为一个足够大的值max_distance。最小生成树生成后, 去除权值大于或等于Tahc的边, Ta为一阈值。行内聚类后, 连通基元聚类为行基元lcc。结果如图2所示。

1.4.2 行间聚类

对行基元lcci和lccj, 若dx (i, j) =0, 则边edge (i, j) 权值为dy (i, j) 。否则其权值设定为一个足够大的值max_distance。最小生成树生成后, 去除权值大于或等于2dl的边。结果如图3所示。

由克鲁斯卡尔算法构造最小生成树边需要按权值进行排序。实验表明, 在克鲁斯卡尔算法中需要排序的边的数目大大减少, 因为权值为max_distance的边在排序的过程中可以去掉。这样有助于减少处理的时间。

竖排文本聚类与横排文本相似, 不同的是边权值的定义需要作相应的变化。

阈值Ta的值依赖于字间距, 若它的值非常小会使文本行不能合并完全。系统中选取Ta=1.5。聚类后得到的每个连通子图作为一个区域, 找出该区域的外接矩形。中文版面中包含较多的嵌入式版面, 得到的文本块可能与非文本块相交叠或包含, 需要对文本块作进一步分割处理。

2 结语

本文针对复杂中文版面, 提出了非文本区域优先的版面分析方法, 使用连通域搜索算法获取二值文档图像上的所有连通域, 然后计算各个连通基元在四个方向上的连接度, 近而对计算出来的各个连通基元的连接度进行模糊化处理, 来决定进行文字行、列的合并。为了克服标点符号对文本行合并时所造成的影响, 对标点符号采用先识别确认后合并的办法。在文本行合并成文本段的过程中, 采用最佳结构树的表示方法, 并在表示版面结构时融入排版规则知识, 可以把版面结构形象化的表示出来。利用以上这些算法进行版面分析, 对印刷质量比较好的中文版面具有较理想的分割效果。证实了该方法具有比较好的适应性和较高的智能化程度。

摘要：版面分析目前已成为提高汉字识别系统效率的关键技术之一。针对中文版面较为复杂的特点, 本文提出一种非文本区域优先的版面分析方法。该方法提取文档图像中所有连通域, 根据连通域的大小进行聚类, 从而可以得到文字连通域和非文字连通域, 以达到分割版面的目的。实验结果表明, 这种方法能够对比较规范的中文版面进行分析, 具有较高的效率和较好的适应性。

关键词：版面分析,连通域,中文版面,优先提取

参考文献

[1] Kuo-chin FAN, Liang-sheng WANG.Classification Of Document Connec-tivity Histogram, 1995 Blocks Using Density Feature And Pattern Recog-nition Letters 16 (955～962) .

[2] Xi Jie, Hu Jianming, Wu Lide. Page Segmentation of Chinese Newspapers[J].Pattern Recognition, 2002, 35 (12) :2695～2704.

[3] 章毓晋.图像分割[M].北京:科学出版社, 2001.

[4] 郭丽, 孙兴华, 王正群, 等.一种基于连通域的版面分割方法[J].计算机工程与应用, 2003 (5) .