聚类+连体段判别的维吾尔文档图像单词切分
2020-07-17徐学斌吾尔尼沙买买提阿力木江艾沙朱亚俐库尔班吾布力
徐学斌，吾尔尼沙·买买提，阿力木江·艾沙，朱亚俐，库尔班·吾布力
1.新疆大学 信息科学与工程学院，乌鲁木齐 830046
2.新疆大学 图书馆，乌鲁木齐 830046
3.新疆大学 教师工作部，乌鲁木齐 830046
1 引言
文档图像检索作为信息检索的重要分支，一直是研究的热点。对于中文和英文等语言而言，字符都是独立书写，不存在字符与字符黏连书写的情况，此类印刷体文档图像检索一般是通过OCR（Optical Character Recognition）转化后进行检索，准确率高，检索速度快。对于我国新疆地区的少数民族语言维吾尔语而言，其字母既可以独立书写，也可以有多个字母通过不同的顺序组合相连书写，因此对印刷体维吾尔文档图像进行字母切分与识别时准确率不高，用OCR技术对维吾尔文档图像进行检索的研究相对滞后。近年来有学者提出针对维吾尔文档图像的关键词检索，首先对文档图像进行单词切分，然后对输入单词图像在切分好的单词图像库中进行特征匹配，返回单词图像库中匹配成功的图像所属的文档图像。由于只需对文档图像中的单词进行切分和特征匹配，无需精确识别所有字母，因此系统复杂度大大降低，同时检索效率较高。
文档图像的关键词检索系统首先要对文档图像进行准确的单词切分，切分效果直接影响检索结果。目前针对印刷体维吾尔文档图像的切分研究大多集中在字母切分方向，单词切分方向的文献较少。针对印刷体维吾尔文档图像的单词切分，文献[1]对投影得到的连体段进行聚类分析，通过计算连体段的重叠率来合并属于同一单词的连体段，平均单词切分准确率达到了97%。文献[2]针对手写体维吾尔文档图像的单词切分采用FCM（FuzzyC-means）融合K-means的聚类算法对文字区域之间的空白间距进行聚类，把距离分成单词内距离和单词间距离，从而得到单词的切分点信息，平均切分正确率为80.68%。以上文献在统计实验结果时均忽略了“<< >>”“（ ）”“[]”等特殊标点符号漏切分的影响，未对文本行末尾被拆分书写的单词进行合并处理，而且切分准确率有待提高。针对以上问题对关键词检索结果的影响，本文采用K-means算法[3]对印刷体文本行图像投影后连体段之间的空白间隙进行聚类分析，得出最佳间距判别阈值，同时对与空白间隙相邻的连体段进行筛选和识别，结合二者信息得到最佳切分点的位置信息和需要进行单词合并的单词位置信息，实现对印刷体维吾尔文档图像准确的单词切分。
2 维吾尔文单词切分规则概述
2.1 单词划分
词是维吾尔语中能独立运用的最小语言单位 ，词与词之间有明显的间隙分隔开，不存在像汉语中单词切分时的分词问题。因此词与词之间的间距是维吾尔语文档图像中确定单词切分点时最重要的依据，多数关于单词切分的文献都是以单词与单词之间的间距为基础。本文通过对文本行中所有连体段之间的间距进行聚类分析来设置间隙判别阈值，区分单词间的间距和单词内部的间距，连体段之间的间距大于设定阈值则说明此相邻连体段属于不同的单词。
2.2 标点符号的影响
维吾尔语中，一般而言标点符号与单词之间的间距小于词与词之间的间距，但明显大于单词内部各连体段之间的间距，比如“.”“،”“!”“：”“؛”等标点符号。因此，设置合适的间距判别阈值，即可获得此类标点符号与单词之间的切分点坐标。然而对于“<< >>”“（ ）”“[]”等标点符号，通常是左半部分与单词的间距略大于单词内连体段的间距，而右半部分与单词的间距和单词内连体段的间距相同，因此无法根据这类标点符号与单词的间距来确定单词的切分点位置。文献[1]中将此类标点符号看作与其间距最小的单词的一部分来进行切分，不符合后续关键词检索系统的需要，本文中将所有的标点符号看作一个独立的切分单元进行切分。
2.3 合并拆分书写的单词
由于维吾尔语中不同单词的长度一般不同，某些长度较长的单词位于行末时，由于书写位置不够往往被拆分成两个部分进行书写，一部分位于第一行的行末位置，并在末尾用符号“-”进行标示，另一部分位于下一行的开始位置。在印刷体维吾尔文档中这种写法大量存在，被拆分的部分没有词意，属于无意义切分。本文中对所有按这种书写方式书写的单词在切分时进行合并处理，生成完整的单词图像。
2.4 本文方法系统框图
与基于形态学操作的切分方法相比，对文档图像直接进行投影[4]的切分方法计算量较大，但是直接投影法[5]能够获得单词图像最底层的纹理特征，可操作性强，能够使切分更加准确。因此，本文选择在对文本图像直接进行投影的基础上，对投影所得的数据进行综合分析与判断，从而找到单词图像的精确切分点。本文方法的系统流程图如图1所示。
3 预处理
3.1 文档图像收集
文档图像的来源为新疆大学出版社出版发行的书籍《马列主义经典著作选编》的维吾尔语版本，为模拟不同的办公环境，用不同型号的打印机将纸质书籍扫描为文档图像，尺寸为716×1 011。由于长期翻阅导致文档发黄，加上扫描的环境不同以及纸质文档是双面打印的影响，收集的文档图像带有各种各样的噪声，如倾斜、椒盐噪声等，一些图像甚至带有较明显的重影，如图2所示。
3.2 图像去噪
图1 单词切分系统流程图
图2 原始文档
为最大限度保留文档图像上文字的笔画信息，去除其他干扰信息，首先需要对所收集的文档图像进行去噪处理。图像上的噪声基本是在纸质文档印刷后引入的，如翻阅、扫描等过程，与图像上的文字信息无关。维纳滤波[6]当噪声与信号无关时有很好的的效果，因此本文通过维纳滤波来去除图像上的噪声。
3.3 图像增强
为了能够使图像中文字的笔画信息更加清晰，突出文字像素和背景像素之间的差别，同时减小不同图像之间的亮度和对比度差别，本文选取线性灰度增强的方式对原始图像进行增强处理。设原始图像 f(x,y)在变换前的灰度范围是[a,b]，增强后F(x,y)灰度范围为[c,d]，则线性灰度增强函数的表达式为：
其中saturate_cast表示将增强后的像素值归一化至0～255范围内，通过调整a、b、c、d的值使增强后的图像中像素的灰度差异性变大，易于设置阈值来区分文字像素与背景像素。
3.4 倾斜校正
所收集的部分文档图像在扫描过程中引入了不同程度的倾斜，而利用水平和垂直投影对维吾尔文档图像进行连体段切分时要求图像的倾斜角不能大于0.5°，因此需要对所收集的文档图像进行倾斜校正。本文通过对常用的霍夫直线倾斜角检测方法[7]进行优化，来实现文档图像的倾斜校正。由于部分图像的文本倾斜角小于1°，计算倾斜角时误差较大，因此本文首先统一对所有收集的文档图像逆时针旋转2.5°，然后进行霍夫直线检测，根据检出的直线上两个点的坐标求得该直线的倾斜角。最后删除数值明显过大的倾斜角，对剩余的倾斜角求均值，将求得的均值作为该文档图像的倾斜角，利用此倾斜角顺时针旋转文档图像，从而实现倾斜校正，降低检测误差造成的影响。
3.5 图像的灰度化与二值化
图像的灰度化采用常用的加权平均法，设原图像为f(x,y)，灰度化后的图像为g(x,y)，则表达式如下：
g(x,y)=0.299R(x,y)+0.578G(x,y)+0.114B(x,y)（2）其中，R(x,y)、G(x,y)、B(x,y)分别为原图像的三个颜色通道的像素值。图像的二值化采用最大类间方差法[8]，即按图像的灰度特性，将图像分成文字信息和背景图像两部分，寻找使背景和文字像素之间的类间方差最大时的阈值，作为图像二值化的全局阈值，文档图像经过预处理后的效果如图3所示。
图3 预处理效果图
4 单词切分
4.1 文本行切分
设 p(x,y)为图像上任意一点的像素值，将经过预处理后的文档图像的每一行的像素值进行累加，P(y)为每一行的像素累加值，P(Y)为所有行像素累加值的最大值，表达式如下所示：
其中，m为图片宽度，n为图片高度，j为图片上任意行坐标，i取0到m-1之间的所有整数。设区分空白行与文字行的阈值为K，用每一行的行像素累加值与K比较大小，大于K则判定该行中没有文字信息，为背景行，反之则判定该行中存在文字信息。由于经过预处理后的文档图图像仍然存在残留噪声点的干扰，因此根据经验设阈值为所有行像素累加值的最大值减去200，来
降低残存噪声点的干扰。根据阈值K获取任意文本行在垂直方向的切分点坐标的表达式如下：
P(yi-1)>K⋂P(yi)>K⋂P(yi+1)
4.2 连体段切分
连体段[9]是对文本行进行垂直投影时彼此相连，没有空白间隙的单元，独立的字母、几个字母相连以及标点符号等都视为一个连体段，连体段是最小的切分单元。与文本行切分原理一样，设 p(x,y)为文本行图像上任意点的像素值，P(x)为文本行图像上任意一列的像素累加值，P(X)为所有列的像素累加值的最大值，设区分文本行图像中空白列与文字列的阈值为H，表达式如下：
其中，l为已读取文本行图像的高度，i为图像上任意列的坐标，j取0与l-1之间的整数。同理阈值H取值为P(X)-100，若图像上列像素累加值大于H则视为空白列，反之则为带文字信息列，依据此规则计算连体段的切分位置坐标的表达式如下：
其中，i、j为文本行图像上任意行坐标，且i-j>3,i与j分别为连体段初始位置和末端位置的行坐标，根据位置坐标即可将连体段切分出来，效果图如图5所示。
4.3 合并连体段
4.3.1 自适应阈值计算
利用维吾尔语单词内部连体段之间的间距和单词之间的间距的差别，设置合适的阈值来区分各连体段，若相邻两连体段之间的间距大于阈值，则其属于不同的单词，在此间隙处进行切分处理。若相邻两连体段之间的间距小于阈值，且经过分析间距两侧的连体段都不是标点符号，则对此间隙两侧的连体段进行合并处理，若此间隙两侧连体段经过分析存在标点符号，则在此间隙处进行切分处理。设判别阈值为M，为了适应不同字体、字号与格式的文档图像，用K-means算法对任意文本行中的所有连体段之间的间距进行聚类分析，计算出适合此文本行的判别阈值。任意文本行图像上连体段之间的间距分为两类，第一类为单词之间的间距以及标点符号与单词之间的间距，第二类为单词内部连体段之间的间距。计算阈值M的表达式如下：
其中，A与B分别为两类间距的聚类中心，在求聚类中心时根据经验去除了数值过大的间距值，来消除页边距空白处残留的噪声点对聚类结果的影响。
4.3.2 标点符号处理
对于“.”“،”“!”“：”“؛”等标点符号[10-11]，其与单词之间的间距一般大于M，根据此类标点符号与单词之间的间距大小即可将其正确切分。“<< >>”“（ ）”“[]”等标点符号因其与单词之间的间距与单词内部连体段之间的间距相似，无法根据阈值M判断切分点，对于这类标点符号通过对其提取特征来进行区分。由于标点符号的宽度一般都小于2M，因此在对文本行中的连体段进行切分时，针对宽度小于2M且与相邻连体段之间的间距小于M的连体段，首先提取其轮廓的高度、宽度，以及距文本行上下边界的距离等特征。若以上特征值满足表达式（12）或表达式（13），说明该连体段可能为要寻找的标点符号，但仍需对其做进一步判断，表达式如下：
图4 文本行投影图
图5 连体段投影图
其中a、b、c、d分别为连体段的宽度、高度，以及与上下边界的间距值，表达式（12）为判断符号“（）”与“[]”的条件，表达式（13）为判断符号“<< >>”的条件。用间距判别阈值M作为判别基础是因为M本身包含了文本行中文字的字体与字号等信息，将其作为对连体段的简单轮廓特征进行判别与筛选的基础，能够减小字体字号等变化带来的影响。随着文字的字体变化，标点符号的轮廓大小在整个文本行中所占的比例也会变化，因此在根据连体段的轮廓特征对其进行判别和筛选时，在筛选范围值中加入了一定的缓冲量，以此来消除字体等变化对筛选结果的影响。
根据连体段的简单轮廓特征可以将其与多数连体段区分开来，但无法区分与其有相似轮廓特征的符号，比如符号“”“”“”“”的轮廓大小与符号“（ ）”“[]”相似，符号“”“”轮廓大小与“<< >>”相似，因此需进一步提取特征来判断。对于“（）”“[]”等符号而言，其特点是宽度较窄且高度较高，同时构成符号的黑像素彼此相连，没有被背景像素隔开的黑像素。对于与其大小相似的符号而言，构成这类符号的黑像素都被背景像素分割成了几部分。因此，在筛选与“（）”等标点符号相似的连体段时，首先将连体段图像放大四倍，然后进行水平投影，根据放大后的连体段的高度信息以及放大后的图像在水平投影中得到的连体段数目信息即可将与其相似的标点符号区分开来。构成符号“<< >>”的黑像素的特点是被背景像素分隔成两部分，而与其轮廓大小相似的符号的黑像素彼此相连，没有被背景像素分开，因此根据这一特点可将与其相似的符号进行区分。由于符号“<< >>”无法根据投影来获取连体段的数目，因此用凸包检测[12]的方法来获得连体段的数目。对连体段做进一步特征提取的示意图如图6所示。
图6 特殊标点判别示意图
图6 中e为对符号“（）”“[]”及与其轮廓大小相似的图像按原图高度的四倍和宽度的两倍放大后进行水平方向投影，得到的连体段数目；f为放大后符号的高度，根据实验下限取值为阈值M的9倍时，满足切分要求；g为将符号“<< >>”及与其轮廓大小相似的图像放大3倍后检测到的凸包的数目，这里凸包检测的方式设为只检测最外围轮廓[13]，包含在外围轮廓内的内围轮廓被忽略，并且在检测时略去了轮廓范围太小的凸包，来消除笔画边缘噪声点对检测结果的影响。符号“（）”“[]”以及符号“<< >>”的判别条件分别如式（14）和式（15）所示：
4.3.3 合并拆分书写单词
维吾尔语中当单词宽度大于文本行的剩余位置能够容纳的宽度时，单词被拆分成两个部分书写[14]，并在行末用连接符“-”进行标注。当检测到文本行的最后一个连体段为符号“-”时，说明此文本行末尾有单词被拆分书写。连接符“-”的宽度会随着字体的变化而变化，但其高度一般与单词的笔画宽度相同。检测连接符“-”的过程如下，首先将位于文本行末尾且宽度满足表达式（16）的连体段筛选出来，宽度判别表达式如下所示：
其中，a为位于文本行末尾连体段的宽度，将筛选出的连体段图像按两倍高度和四倍宽度的比例放大，检测放大后连体段的高度和宽度。图像放大的目的是增大连接符“-”与其他连体段的轮廓大小的差值范围，减小噪声和图像质量退化对检测结果的影响。设放大后连体段的高度为h，宽度为l，若h和l满足式（17）时：
则说明此文本行末尾有单词被拆分，记录此连体段右侧被拆分单词以及下一行第一个单词的位置信息，表达式（16）与（17）为对不同字号的文本进行实验时根据实验数据得出的取值范围。
根据记录的被拆分部分单词图像合成完整单词时，首先分别对两部分图像进行水平投影，分别找出每一行行像素累加值的最小值所在的行坐标。该行坐标即为单词的基线所在行的坐标，合并被拆分的两部分单词图像时按基线在同一条水平线的规则将被拆分图像在垂直方向上对齐。当单词拆分点位于单词内两相邻连体段之间的空白处时，采用有间距合并的方式，即将基线对齐后的两部分单词图像中相邻连体段之间留出空白间距，间距值等于文本行中单词内部间距的聚类中心B。若拆分点在连体段上，进行合并时将基线对齐后的两部分单词图像上拆分点处相邻的连体段紧密相连，单词合并示意图如图7所示。
图7 拆分单词合并规则示意图
为判断拆分点位置，分别检测拆分点两侧连体段的边缘高度。设拆分点两侧连体段的边缘高度分别为g1、g2,若g1与g2满足判别式（18），则说明拆分点位于连体段上，应采用无间距合并，反之则说明拆分点位于单词内连体段之间的间隙处，采用有间距合并。判别式（18）如下所示：在检测边缘高度时，检测宽度设为两个像素，并且去除了连体段上的附加符号比如“¨”“∴”等，来减小检测误差。高度判别阈值设为M-2是因为拆分点位于连体段上时，其边缘高度即为单词的基线高度，根据实验基线高度总是小于M-2的。当拆分点位于单词内连体段之间的间隙时，其边缘高度一般远大于M-2。
4.4 切分效果图
这里只截取了一张完整文档图像的一部分，从图中可以看出一些比较难切分的标点符号都被准确地切分了出来，满足后续基于关键词检索系统对单词切分的需要，切分效果图如图8所示。
5 实验结果与分析
为了验证本文所提出的方法针对印刷体维吾尔文档图像的单词切分效果，从收集的文档图像数据库中选取包含不同字号、行间距，以及清晰度的100张文档图像进行实验。特殊标点符号如“<< >>”“（ ）”“[]”往往是单词错误切分的主要来源，因此首先从已有的100张文档图像中选取5张特殊标点符号数目较多的文档图像进行切分实验，实验结果如表1所示。
从表1可知在选取的5张文档图像中“<< >>”“（）”“[]”三类标点符号共有80个，全部都切分正确，证明本文方法对此类与单词间间隙较小的标点符号的切分有很好的效果，同时保持较高的单词切分准确率。为验证本文方法对合并被拆分单词的有效性，从已有的100张文档图像中选取5张被拆分单词数目较多的文档图像进行单词切分实验，实验结果如表2所示。
表1 包含较多特殊标点符号的维吾尔文印刷体文档图像单词切分实验结果统计
表2 包含较多被拆分单词的维吾尔文印刷体文档图像单词切分实验结果统计
从表2可知在选取的5张文档图像中共有57个单词被以拆分的形式书写，经过本文方法处理后有54个单词被正确合并，合并准确率达到94.73%，证明本文方法对被拆分单词的合并有很好的效果。为观察本文方法对不同数量的印刷体维吾尔文文档图像进行单词切分时错误切分率的变化范围，随机从已有的100张文档图像中分别选取数量分别为5、10、15、25、50张的文档图像进行单词切分实验，实验结果如表3所示。
表3 随机选取不同数量的维吾尔文印刷体文档图像单词切分实验结果统计
图8 印刷体维吾尔文档图像单词切分效果图
表3通过随机选取不同数量的文档图像进行实验，降低了偶然性对统计切分结果时的影响。在本实验中将标点符号看作独立的切分单元，并且将被拆分书写的单词在切分时进行了合并。从表3可以看出，单词切分的准确率依据文档图像及其数量的不同会有小范围波动，但是切分准确率都在99%以上，证明本文方法对印刷体维吾尔文档图像单词切分有很好的的效果。
为对比本文方法与已有方法的相比的差异性，从已有数据库中随机选取了10幅印刷体维吾尔文档图像，与直接投影法[15]以及形态学梯度算法[16]进行了对比实验。由于对比文献中的方法未考虑单词拆分影响，因此在统计切分结果时忽略单词拆分的影响，对比实验结果如表4～6所示。
表4 固定阈值+直接使用水平和垂直投影算法的印刷体维吾尔文档图像单词切分实验结果
表5 使用形态学梯度算法的印刷体维吾尔文档图像单词切分实验结果
从表中数据可知，在选取的10幅印刷体维吾尔文图像中共有2 257个单词，基于全局阈值的直接投影法的平均切分错误率为5%，共切错112个，基于形态学梯度算法平均切分错误率为2.6%，共切错62个单词，切分效果优于直接投影法，平均切分错误率降低了2.4个百分点。本文提出的间距聚类融合连体段判断的方法平均错误率为0.9%，共切错21个单词，平均切分错误率比直接投影法降低了4.1个百分点，比形态学梯度算法降低了1.7个百分点。分析可知直接投影法只利用了单词间的空白间距信息来确定切分点，并且使用全局阈值来对多幅图像进行切分，对版面格式的适应性差，故切分错误率较高。形态学梯度算法通过膨胀和腐蚀[17]操作，使用膨胀后的单词图像减去腐蚀后的单词图像，从而得到整个单词的边缘轮廓信息。该方法能够适应不同版面格式的变化，因此效果优于直接投影法，但两种方法本质都只利用了连体段之间的空白间距信息，因此对一些无法根据间距信息切出的特殊符号无效。本文提出的基于间距聚类和连体段判断的维吾尔文图像单词切分方法通过间距聚类，计算动态阈值来适应不同版面格式的变化，同时结合连体段的轮廓信息能够去除无法用间距信息去除的特殊标点符号，因此切分准确率较高。但由于本文是在投影法的基础上进行，对文档图像的质量较高，因此图像预处理算法仍然需要改进。三种切分方法切分效果对比图如图9所示。
表6 间距聚类+连体段判别的印刷体维吾尔文档图像单词切分实验结果
图9 三种方法错误切分单词数目对比图
6 结束语
为了后续开发基于关键词的印刷体维吾尔文档图像检索系统，首先需要对文档图像进行准确的切分。现有的切分方法中基于膨胀腐蚀的形态学操作方法与基于连体段聚类的投影切分方法都存在着标点符号漏切分，被拆分书写单词未合并等问题。本文通过投影法获取文本行中连体段的位置、大小、基本形状等信息，然后对连体段之间的间隙进行K-means聚类分析获取自适应间隙判别阈值，结合二者信息来获得单词的精确切分点，同时合并被拆分书写的单词。投影法对文档图像的对比度、清晰度等要求较高，图像质量差是影响本文切分效果的主要因素。不同的质量、文本格式的文档数据库会影响本文方法对单词切分的准确率，因此如何提高本文对噪声干扰严重、模糊以及不同文本格式的图像的切分效果，进一步提高本文对不同质量与种类的文档图像的鲁棒性，将是下一步的研究重点。
