基于缝隙裁剪的满文单词分割和提取方法研究

张 晶，许 爽，贺建军，李 敏，郑蕊蕊

(1. 大连民族大学 信息与通信工程学院，辽宁 大连 116600； 2. 中央民族大学 理学院，北京 100081)

0 引言

满文作为清代法定推广和使用的文字，历经数百年，形成了大量的满文古籍文档。这些满文文档涉及广泛，包括政治、经济、军事、历史、文艺、宗教、风俗等各个方面，是清代通史和各种专史的珍贵资料，具有重要的价值和意义，亟待研究[1]。相对汉语、英语等语言，我国少数民族语言的文档分析研究还没有充分展开，对满文文档的分析研究更是处于起步阶段，而文档分析中，行列分割作为离线图像文本识别和检索中重要的一步，现在已成为国内外较为热门的研究话题之一。现有的文本行分割算法主要包含以下五类：基于投影的方法、基于笔画特征的方法、基于霍夫变换的方法、基于随机模型的方法和基于聚类的方法。文献[2]提出了一种基于投影的古汉字切分方法，该方法的优点在于计算复杂度较低，实现起来简单，但缺点也十分明显。首先，相对较短的文本行在投影直方图上没有明显的峰值，容易被漏检；其次，对于存在粘连或重叠的文本行，由于没有明显的谷值，导致文本行不能被分割开。文献[3]通过笔画特征分析的方法分割字符，这种方法不仅耗时间，而且对含有大量离散笔画的文本行分割的准确率不高，容易跨行分割，难以达到分割期望。基于霍夫变换的方法[4]，更适用于版面简单的字母类文档，对于版面复杂的文字文档效果不佳。基于随机模型[5]的行分割算法能够较好地适应书写风格的变化，但计算复杂度非常高。文献[6]提出了自底向上的聚类方法，将连通域聚类成文本行，此方法对存在弯曲现象的文本行非常有效，但通常需要启发式合并规则和人工调参。

针对以上问题，本文提出了一种适用于满文文档图像的单词分割和提取方法。首先采用最小能量缝自适应剪裁图像的方法来计算相邻行列间的分割线；然后通过中线区域约束得到不损坏满文文字部件的最佳分割线；最后依据分割线提取独立的满文文本列和满文单词。该方法对自上而下书写形式复杂、文本列长度不一、离散附属笔画较多、列间弯曲和倾斜及间距不均匀的满文文档能够正确分割和提取，且分割精确度较高。

1 本文算法的整体框架

本文建立的满文单词分割和提取方法包含三个主要部分，即预处理部分、文本分割部分和文本提取部分，整体框架如图1所示。

图1 本文算法的整体框架

(1)预处理部分首先对输入满文文档图像进行预处理以减小干扰，提高图像质量。预处理过程包括：灰度化和高斯滤波。

(2)文本分割部分文本分割部分包括内侧缝计算、分割缝计算、中缝区域约束和分割后处理。采用投影轮廓匹配方法[7]进行内侧缝计算，确定文本列数目并初步涂抹，对相邻列间进行中缝区域约束，在受约束的两两相邻文本列间采用缝隙裁剪算法[8]动态地计算最小能量，从而得到不切损文字部件的最佳分割线，并延伸所有分割线至页面底端，再对漏切分行列进行再切分。

(3)文本提取部分文本提取部分包括文本列提取和满文单词提取。依据分割线对满文文档区域分割，选取背景中值进行背景补齐填充，提取独立的文本列和满文单词。

2 预处理

原始的满文文档通常已有百年以上历史，由于年代久远，扫描获取的满文文档图像质量较差，存在大量的噪声、污点、笔迹褪色、倾斜等现象。除了年代久远，扫描过程中也会引入噪声。为了保证后续工作的顺利进行，有必要对扫描后的满文文档图像进行有效的预处理，以减小干扰，提高图像质量。一般的预处理步骤中普遍将图像二值化处理，图2(a)为二值化后的结果，图2(b)为原始满文手写奏折文档图像。可以看出，二值化会使原文档图像丢失一部分信息，使分割后文字不完整，所以，本文为更好地保留原始文档信息，直接在灰度图像和彩色图像上进行处理，并且，本文方法不需要对满文文档图像进行倾斜矫正等预处理，在对图2(d)中具有倾斜角度的满文文档也可以有效分割。本文预处理步骤包括两个部分。

(1) 彩色图像转灰度图

假设输入的满文图像为灰度图像I∈Rn×m，如果是RGB彩色图像，将根据式(1)的加权平均法将其转化为灰度图像，其中符号I(i,j)表示图像在第i行、第j列的值，如式(1)所示。

(1)

(2) 高斯滤波

运用二维的高斯函数对图像进行高斯滤波，如式(2)所示。

(2)

其中，a,b是像素的坐标位置，ρ是正态分布的标准偏差。图像中的像素值是由邻域内的其他像素值和其本身像素经过加权平均后计算得到的[9]。其本身的像素值具有最大的高斯分布值，所以权重最大，而相邻像素随着距离原始像素越来越远，其权重也越来越小。这样进行模糊处理比其他的均值模糊滤波能更好地保留了原始文档的边缘信息。

图2 二值化和倾斜校正前后、满文文档分割结果示图

3 文本分割

3.1 内侧缝计算

(3)

(4)

如果式(4)中(Ⅰ)和(Ⅱ)的上述位置匹配一致，则它们用线连接。重复上面的过程，直到所有的切片被处理。文本列区域可以用矩阵Lh,j(h=1,…,l,j=1,…,n)表示。其中，元素Lh,j表示第h行的第j个坐标，l表示找到的最后列数。匹配完成后，得到初步涂抹的文本列。文本列数目及列间内侧缝已计算得到。此时，定义任意两个相邻的内侧缝间为计算分隔缝时的约束区域。该区域将分割缝约束在相邻的两文本列之间，避免跨列分割。

3.2 分割缝计算

本文采用提出的缝隙剪裁算法计算分割缝。

(1) 计算图像能量图Ei,j。能量图是灰度文档图像的导数图像，如式(5)所示。

(5)

其中，Iσ是原始灰度图像经过标准偏差为σ的高斯滤波器平滑滤波获得的图像。在能量图中，高能量区域对应文本分量，低能量区域对应纸张背景。用Eh=EJ表示两个文本列之间的能量图。其中J是宽度为m的二维网格，第j列包含两个文本列位置之间的所有中间坐标i，即Jj={Lh,j,…,Lh+1,j}T,h=1,…,l-1,j=1,…,n。一个垂直穿过图像网格Eh的接缝Sh可以定义为：

(6)

其中，yh:[1,…,n]→[Lh,j,…,Lh+1,j]。

(7)

从左到右遍历图像网格Eh，计算每个像素位置(yh(j),j)的所有连接缝的累积最小能量M，如式(8)、式(9)所示。

M最后一列为最小值时，分割缝计算结束。

(3) 更新能量图。遍历累积能量M向后找到最优的分割缝路径，对每个图像网格Eh重复上述过程，不断更新能量图，直到整个满文文档图像全部被处理。图3为《军机处满文准噶尔使者档译编》[11]的手写体满文文档的分割结果，其中图3(a)为原始满文文档图像，图3(b)为列涂抹后的满文文档图像，图3(c)为列分割后的满文文档图像。

图3 手写体满文文档图像分割结果

图4 中缝区域约束后印刷体满文文档分割结果

3.3 中缝区域约束

(10)

图5 中缝区域约束后手写体满文文档分割结果

3.4 分割后处理

(1) 延伸分割线

由于满文文本列长短不一，所以存在一些分割线只延伸到短文本列长度，没有贯穿整个文档页面。为了下一步实现独立文本列的分割，在后处理中将分割线向文档页面末端延伸。首先，提取文档图像中的文字连通域cc，找到较短文本列对应的连通域ccs，然后，选取较短文本列相邻左右两列的中间位置对短文本列ccs进行扩展，直至图像文档页面的底部，分割线也将延伸至文档图像底部。

(2) 漏切分列再切分

在分割过程中，可能出现一些文本列没有被分割开，此时需要检测到这些漏切分的列对其进行再次切分。通过向满文文档图像的竖直方向投影，得到单一列的最大宽度Lwmax。若切割得到的列宽Lw大于最大宽度Lwmax，则此列为漏切分列，对漏切分列采用缝隙裁剪的方法再切分，直到所有的列都被成功分割。

4 文本提取

4.1 列提取

文本列分割作为离线文本分析中重要的一步，是字符识别和检索的前提。实现字符的识别和检索，文本列的提取也是必不可少的关键任务。对满文文档列进行线分割后，进一步以分割线切割相邻文本列实现独立文本列的提取。弯曲的分割线使得分割得到的文本列边缘层次不齐，为得到完整的文本列图像，需要将不规则的分割边缘补齐。输入分割线图像I′∈Rn×m′，第一步是区域分割提取，第二步将背景补齐融合，得到背景完整的独立满文列图像。

设(x,y)是输入满文文档分割后带有分割线的图像平面坐标，其灰度级的取值范围是G={0,1,2,…,Z-1}，位于坐标点(x,y)上的像素点的灰度级表示为f(x,y)。设q∈G为分割阈值，B={b0,b1}代表一个二值灰度级，并且b0,b1∈G。于是图像函数f(x,y)在阈值q上的可以由式(11)表示，以《军机处满文准噶尔使者档译编》中手写体文档分割为例，图6(a)为列分割后的满文文档，图6(b)为区域分割结果。

(11)

图6 满文文档图像区域分割结果

分割后的文本列边缘由于弯曲的切割线而参差不齐，本文选用分割后文本列图像背景的中值作为融合背景图像。背景的中值为n×m′阶矩阵Ib，其中第i行j列处点的值表示为b(i,j)(i≤n,j≤m′)，切分后的独立列为n×m′阶矩阵It，第i行j列处点的值表示为t(i,j)(i≤n,j≤m′)，α∈(0,1)表示融合权重，是背景图像在结果图像中所占的比例。融合结果图像Ir由式(12)得出，图7为对应于图6(a)中的每列独立文本列的提取结果。

Ir=α·Ib+(1-α)·It

(12)

图7 满文文本列提取结果 每一列对应图6(a)中的每列

4.2 单词提取

图8 印刷体满文单词提取结果

图9 手写体满文单词提取结果

5 实验结果

5.1 数据集

本文所采用的满文数据集来源于满文图书和大连民族大学图书馆古籍馆获取的满文档案。为了保证得到的图像具有较高的质量，将原始满文文档分别用600dpi和350dpi分辨率扫描获得电子满文文档图像。满文文档数据集如表1所示，包含四个(Ⅰ、Ⅱ、Ⅲ、Ⅳ)满文文档子集，数据集Ⅰ选取自胡增益主编的《新满汉大词典》中的目录部分，共包括107页639列15 950个满文单词。数据集Ⅱ选取自中国第一历史档案馆和中国边疆史地研究中心合编的《清代新疆满文档案汇编》。从中随机选取100页满文印刷体文档，包括1 490列9 040个满文单词。数据集Ⅲ为《清代新疆满文档案汇编》中随机选取的100页满文手写体文档，包括1 471列8 905个满文单词，数据集Ⅳ为中国第一历史档案馆收录的真实满文手写扫描档案《军机处满文准噶尔使者档译编》。从中随机选取50页包括735列7 350个满文单词，其中数据集Ⅰ、Ⅱ为印刷体满文文档，Ⅲ、Ⅳ为手写体满文文档。

表1 满文文档数据集

5.2 评价方法

为了验证本文分割算法的有效性，需要采用相应的评价指标来对算法进行衡量。在现有的研究中，一些研究人员采用人工评价的方法，也有朱宗晓、杨兵[14]等采用匹配度作为评价指标。本文采用匹配度作为评价指标。以如下评价方法对分割结果进行评价，设G为数据集中实际的列，R为程序处理分割出来的列，文本对实际列G与分割结果R定义了匹配度，如式(13)所示。

(13)

当匹配度(G,R)≥0.90时，认为分割列R正确。本文采用了召回率(R)、错误率(F)对本文的满文文档列和单词分割提取进行评价，如式(14)～式(17)所示。

5.3 实验分析

本文的实验平台为PIV2.50GHZ/4.00GBRAM，运行环境为Matlab 7.10，对象为满文文档数据集Ⅰ、Ⅱ、Ⅲ、Ⅳ。依据5.2节的评价方法，实验分别统计了满文文档列分割和单词分割的数据库理论值、实际分割得到的值和分割正确的值。定义分割正确的值占数据集理论应切割得到值的百分比为召回率，体现了分割精确度；由于文档图像版面复杂，可能产生多于理论值的分割线，从而，导致分割错误率。定义错误分割的值占实际分割得到值的百分比为错误率。实验进一步采用目前应用较为广泛的投影切分方法[15]作为比较算法。分别在两种方法下进行满文文档列和单词的分割实验，比较其分割召回率和错误率。

实验对满文文档列分割的结果如表2所示。从表2中的实验结果来看，本文的分割算法在满文数据集上获得了较高的召回率，最高可以达到98.75%。在数据集Ⅰ、Ⅱ、Ⅲ、Ⅳ上召回率逐渐降低，但相差不超过5个百分点。从这一点可以说明本文方法在对印刷体满文文档和手写体满文文档上都可以有效分割。对数据集Ⅰ，本文方法召回率最高为98.75%，高于投影法的98.28%约0.5个百分点；对数据集Ⅱ，本文方法的召回率为97.11%，高于投影法的85.64%约11个百分点；对数据集Ⅲ，本文方法召回率为95.04%，高于投影法的57.72%约37个百分点；对数据集Ⅳ，本文方法召回率为94.69%，高于投影法的58.91%约36个百分点。对于印刷体数据集Ⅰ、Ⅱ，本文方法召回率高于投影法，但相差不大；对手写数据集Ⅲ、Ⅳ，投影法召回率明显下降。本文方法召回率高于投影法超过30个百分点，投影法无法达到对手写体满文档分割预期，分割效果差。由此，相比投影法，本文算法不论是对印刷体还是对手写体满文文档，分割结果都更佳。尤其在对附属笔画较多、列间弯曲倾斜、书写复杂的手写满文文档，本文方法明显优于投影法。

表2 满文列分割实验结果

表3给出了满文单词的分割结果。从表3实验结果来看，本文方法在Ⅰ、Ⅱ、Ⅲ、Ⅳ数据集上的召回率都高于投影法，本文方法在数据集Ⅰ上召回率最高为95.02%，而投影法最高只有79.97%。就分割错误率来看，本文方法错误率低于投影法。其中对于数据集Ⅲ，投影法的错误率为46.14%，而本文方法只有3.52%，投影法的错误率远大于本文方法错误率。进一步得出，本文方法可以对满文单词有效地分割，且效果优于投影方法，错误率较低。

表3 满文单词分割实验结果

6 结论

从大篇幅的满文文档图像中分割和提取满文单词是满文文档分析的重要步骤，也是后续研究的前提。本文提出了一种基于缝隙裁剪的满文文档图像分割算法，该算法可直接应用于灰度或彩色图像。首先，利用投影轮廓匹配确定文本列数目，其次，在两个连续文本行之间进行中缝区域约束，在受约束区域，通过寻找最小能量计算得到分离缝。在没有进行二值化的灰度或彩色印刷体和手写体满文文档集上，取得了很好的分割效果，更好地保留了原始文档信息。对于文本列弯曲、有一定的倾斜角度、单词间重叠粘连的满文文档也能有效分割，且不需要复杂的启发规则。实验证明，本文方法对满文文档能有效分割，且分割的精度较高。