基于局部离群因子和波动阈值的古籍版面图像分析方法

贾 运， 田学东， 左丽娜

(河北大学网络空间安全与计算机学院， 保定 071002)

中国历史悠久，珍贵的古籍藏书丰富。随着计算机技术的高速发展，利用计算机辅助古籍研究是必由之路。古籍文献版面成分丰富，除汉字外，还包括雕版印刷框线、插图等成分，需要自动、高效地对其进行分析，定位其中的字形成分，以便通过文字切分提取出单个的汉字图像，从而为实现古籍汉字图像的识别与检索打下基础。

目前，专门针对古籍文献图像的版面分析研究相对较少，可供参考的是传统的面向印刷文献的版面分析方法，包括自顶向下方法、自底向上方法和混合方法等3类[1-2]。基于投影的方法是最典型的自顶向下方法，该方法简单且速度快，适用于排版规范的版面，复杂版面效果不佳。自底向上方法的代表是基于连通区域分析的方法，此法可处理复杂版面，但计算量较大且效率低。混合方法是将自顶向下和自底向上两种方法组合运用，解决了单一方法的不足。

针对排版较为规范的印刷文档版面图像，研究者提出了多种版面分析方法。Dai-Ton等[3]提出自适应过分割和融合的印刷版面分割方法。利用背景白色矩形信息将图像过分割，通过连通区域分析得到候选文本，根据预定义的规则将字体大小相同、距离相近的候选文本组合成一个连通区域，使用段落分布模型将不同段落分割开。此方法在处理现代报纸、杂志等出版物取得了较好的效果。Yadav等[4]提出基于角点检测的图像文本块提取方法，将文本图像均分成较小的块, 利用角点密度对图像块进行分类。此方法在不同语言的印刷图像数据集上都得到了较好的结果。段露等[5]提出连通区域和神经网络相结合的问卷图像版面分析方法，利用水平投影分割图像得到问卷行，提取问卷行首个连通区域定位图像表格问卷行，并对其进行表格区域分布分析和表格类型判断,得到可能的答案区域，利用神经网络筛选答案区域的类型，得到最终的答案填写区域。该算法可以准确地识别各种问卷图像中的信息填写区域。任荣梓等[6]提出基于反馈合并的中英文混排印刷文档图像版面分析方法，采用投影法分割图像，设立评估系数、评估标志位和反馈因子实现粘连字符的检测和二次分割。该方法成功分离出中英文混合文档中的中文、英文和数字字符，较好地解决了传统方法对粘连字符处理效果不佳的问题。郭晓宇等[7]提出基于连通区域的传真图像版面分割与分类算法，以连通区域为单位，通过合并连通区域快速分割图像，根据区域的大小建立矩阵，提取表征区域信息的八维特征，使用BP神经网络进行分类。该方法优点为分类过程充分使用分割过程获取的信息，减小了计算量,提高了运算速度。

近年来，随着古籍文献数字化和相关研究的深入，对古籍图像的版面分析方法研究受到关注，该类方法多依赖于所处理图像的版面特点，通常针对不同的古籍版面布局使用特定的版面分析方法。Chen等[8]提出基于超像素分类的无监督学习方法来分析历史文献版面，利用简单线性迭代聚类(simple linear iterative clustering，SLIC)算法将历史文献图像过度分割为超像素，通过堆叠卷积自动编码器提取超像素特征，使用支持向量机(support vector machine，SVM)分类器对超像素进行分类。与原有方法相比，此方法具有更快的速度和更好的性能。Bukhari等[9]提出基于机器学习的手写阿拉伯历史文献图像版面分割方法，提取连通区域的形状特征和上下文特征组成特征向量，利用自多层感知机(auto multi-layer perception，AutoMLP)分类器并结合最近邻分析实现正文和侧边注释的分割。张西群等[10]提出基于卷积降噪自编码器的藏文历史文献版面分析方法，对藏文历史文献进行超像素聚类，训练卷积降噪自编码器提取特征，使用SVM分类器进行分类预测，最终实现了对藏文历史文献的不同版面元素的有效分离。

上述版面分析方法在各自的适用范围上取得良好的效果。由于古籍版面的规范度远低于现代印刷版面，且年代久远，版面质量退化现象较为普遍，需要有针对性地开展研究。现面向《四库全书》版面，基于对其版面特点的分析与归纳，提出基于局部离群因子(local outlier factor，LOF)和波动阈值的古籍图像版面分析方法，通过版面分析、分割过程中所需阈值动态获取等措施，增强算法对古籍文献版面的适应性。

1 基于LOF和波动阈值的古籍版面分析

基于LOF和波动阈值的古籍版面分析流程如图1所示。

图1 古籍图像版面分析流程Fig.1 The flow chart of the layout image analysis of ancient Chinese books

首先，采用基于LOF的分类算法对古籍图像投影分割后的版面区域进行分类；然后，利用波动阈值对文字与框线相粘连的版面混合区域进行分割；最后，确定古籍版面中的文字区域并输出。

1.1 古籍版面图像特征分析

《四库全书》中的版面遵循如下规范[11-12]。

(1)版面框线采用雕版印刷，最外侧有一个双边矩形边框，内部有若干道间距相等的分隔框线。

(2)版面文字有大有小，大小字在同一行混合竖排列，其中单排大字为正文文字，双排小字为注文文字。

(3)版面内有16列竖排文字行，在正中间有一列版心(版心左右各有8列文字行)。

(4)版心装饰为红色单鱼尾，鱼尾上载“钦定四库全书”，鱼尾下文字双行夹写，右载书名，左载卷数，再下仅于横线上右面注页数。

一幅典型的《四库全书》版面图像的成分分布情况如图2所示。

图2 《四库全书》版面图像的成分分布情况Fig.2 Composition distribution of layout image for Imperial Collection of Four

除上述提到的规范外，《四库全书》版面还存在不少特殊情况。通过对2 000多幅《四库全书》版面图像的分析，归纳出古籍图像版面具有以下分析特征：①文字与相邻框线发生粘连的情况很多;②图像退化严重，边框线不完整或者弯曲、文字行间框线不连续和倾斜。

1.2 基于LOF的古籍版面区域分类

针对古籍版面分析特征，采用X-Y投影法[13-14]对古籍图像进行版面分割。根据框线与文字之间的空白行，通过区域内容差异判别方法，将所得到的区域分为框线区域、文字区域和混合区域等3种类型，如图3所示。其中，框线区域中仅包含独立的横竖框线，其按框线方向可分为水平或竖直框线区域；文字区域仅包含独立的文字行；混合区域为文字与框线粘连的区域。

图3 古籍图像版面区域类型Fig.3 Types of the layout areas in ancient Chinese books image

定义1 设古籍图像版面区域Di为四元组，即

Di=(ADi，Xis，Xie，WYmax_i)

(1)

式(1)中：ADi为版面区域Di的方向属性，ADi=0：水平，ADi=1：竖直；(Xis,0)、(Xie,0)分别是版面区域Di投影曲线的起点、终点坐标；WYmax_i为投影曲线的最大峰值。

定义2 设版面区域Di的宽度、面积特征分别为

WDi=Xie-Xis

(2)

SDi=(Xie-Xis)WYmax_i

(3)

根据方向属性ADi=0，快速分类出水平框线。竖直框线宽度一般是固定的或者是有限的几个值，其值远小于其他两类。使用宽度均值TL来衡量竖直框线与其他区域的差异，计算公式为

(4)

式(4)中：m为古籍图像分割后版面区域个数。

混合区域面积大于文字区域，利用这两类区域的平均面积来衡量二者的差异。但古籍版面中存在一些异常区域，这些区域的面积极大或极小，影响了分类文字区域和混合区域的正确率，采用LOF算法将其剔除。

LOF[15-18]是一种经典的异常点检测算法，该算法通过计算数据集中每个数据点的局部离群因子值来确定该点是否是异常点，且离群因子越大是异常点的可能性越大。基于文献[19]的研究，局部异常点的离群程度和其他数据点的分布有关。涉及的相关定义如下。

定义3k距离：设k为任意的正整数，数据点q的k距离是数据集B中到q距离最近的第k个点与点q之间的距离，记作k-distance(q)。

定义4k距离邻域：数据集B中与点q的距离不超过k距离的所有数据点的集合，即为

Nk-distance(q)={p∈B/{q}|d(q,p)≤k-distance(q)}

(5)

式(5)中：Nk-distance(q)简记为Nk(q)；d(q,p)表示p到q的欧氏距离。

定义5 可达距离：点q到其k距离邻域中点p的可达距离定义为

reach-distk(p,q)=max[k-distance(q),

d(p,q)]

(6)

定义6 局部可达密度：点q的局部可达密度是点q到其k距离邻域内所有数据点的平均可达距离的倒数，即

(7)

式(7)中：|Nk(q)|是q的k距离邻域内点个数。

定义7 局部离群因子：数据点的离群程度，计算公式为

(8)

在实际应用中LOF算法存在如下两个缺陷[20]。

(1)若数据集已确定，离群因子值只和参数k有关。当k取值不同时，之前是离群点的数据可能不再是离群点。

(2)对于未知离群点个数的数据集，选择参数k以保证离群点的挖掘数量合理难以做到。

为了削弱k值对实验的影响，文献[21]对参数k设定了一个范围，k∈[Minpts,Maxpts]。对于每一个k，算法执行一次后都会得到一个离群因子。针对k的所有取值分别执行算法，对每个点获得的离群因子求均值，即

(9)

式(9)中：Minpts=1，Maxpts为B中数据点个数。

若SLOF(q)远大于1，则点q的密度与所有数据点的密度差异较大，视为离群点。若SLOF(q)越趋近于1，则点q越正常。

定义8 设TF为衡量文字区域与混合区域差异的阈值，计算公式为

(10)

式(10)中：n为离群点个数；C为离群点集；μ为浮动参数，经大量实验样本验证得到μ∈[0,0.15]，使用μ对阈值TF进行细微调节。分离古籍版面区域的具体过程如算法1所示。

算法1基于LOF的古籍版面区域分类算法：

输入已初始分割的版面区域。

输出存在分割问题的候选混合区域集V。

步骤1利用式(4)计算框线区域分离阈值TL。

步骤2设定参数k范围，并对每一个k值，利用式(7)、式(8)计算每个对象的局部可达密度及局部离群因子。

步骤3利用式(9)计算每个对象所有k值的均值离群因子，获取离群点个数n及离群点集C。

步骤4利用式(10)计算衡量文字区域与混合区域差异的阈值TF。

1.3 基于波动阈值的版面混合区域分割

古籍版面混合区域内的文字和框线存在多个交点，如果将所有交点逐一检测并进行分割，计算量大且费时。利用混合区域投影曲线中字与框线的粘连分割点来代替实际所有交点，如图4所示。

图4 混合区域投影曲线Fig.4 The projection curve of mixed area

粘连分割点表现为波动尺度较大的波谷点，因此曲线上的大尺度波谷点都可能是粘连分割位置。曲线上潜在的波谷点或波峰点分别为

(11)

假设上一轮已成功定位满足波动阈值的波谷点Pn，Pn和下一个待搜索波谷点之间存在若干小尺度波峰点，设Pj[tj,W(tj)]是Pi[ci,W(ci)]之后的一个波谷点，则

n

(12)

如果使得Pi[ci,W(ci)]和Pj[tj,W(tj)]满足：

W(ci)-W(tj)>threshod

(13)

那么Pj即为下一个大尺度波谷点。

上述大尺度波谷点搜索过程中，所用波动阈值计算公式为

threshod=|W(ctop)-W(tbot)|

(14)

在大尺度波谷点集合ΩPj={P1,P2,…,Pj,Pt,…,Pm}中，对于任意3个相邻的波谷点Pt-1、Pt、Pt+1，两两横向距离分别为dt-1,t和dt，t+1，若满足：

(15)

则判定Pt这个点是粘连分割点。式(15)中：α=[Lmin,Lmax]，Lmax和Lmin分别是框线的最大宽度和最小宽度。最后通过直线x=Pt将混合区域中的文字与框线分割开。混合区域粘连分割的具体步骤如算法2所示。

算法2基于波动阈值的版面混合区域分割算法：

输入候选混合区域v。

输出混合区域粘连分割点坐标Pt。

步骤1设上一轮已成功定位满足波动阈值的波谷点Pn，下一个待检测大尺度波谷点为Pj，利用式(12)求取Pn与Pj之间的最大高度波峰Pi。

步骤2若Pi和Pj满足不等式(13)，则Pj即为新一轮搜索到的满足波动阈值的波谷点，并存入集合ΩPj；否则j=j+1。

步骤3若Pj不等于终点坐标(Xie,0)，继续执行步骤1～2；否则执行步骤4。

步骤4将所得集合ΩPj中任意3个相邻的波谷点Pt-1、Pt、Pt+1，两两计算横向距离。若满足式(15)，则Pt为粘连分割点；否则t=t+1，继续执行步骤4。

2 实验结果与分析

2.1 版面分类结果分析

从《四库全书》中任意选取了4 080幅图像作为版面分类的实验样本，用NYB表示。为验证分类算法的优劣，使用准确率P和召回率R对分类结果进行评价。准确率和召回率公式为

(16)

(17)

式中：A表示类别中的某一类；NAR为A中分类正确的区域个数；NA为分类为A的区域个数；ND为样本中A的实际个数。

在实验中，选择文献[7]中的版面分类算法作为对比算法。需要注意的是，由于对原文献方法理解程度以及所采用实验样张方面的差异，本文的对比实验结果只是在一定程度上反映了算法的实际情况。

按式(16)、式(17)计算得到的评价值如表1所示，其中，最后的实验结果由样本图像的平均值得出。

从表1可以看出，本文算法分类结果的准确率和召回率分别达到了87.02%、81.31%，优于文献[7]算法。但实验结果中存在分类错误的版面区域，主要原因是古籍图像退化严重，版面内存在较多噪声，部分文字区域与混合区域特征极为相似，从而导致分类错误。

表1 版面分类实验结果Table 1 Experimental results of layout classification

2.2 混合区域粘连分割结果分析

从4 080幅样本中挑选存在粘连问题较多的759幅图像作为实验样本，经版面分割后共得到3 952幅混合区域图像。对其进行人工分类，其中包括单排大字图像1 064幅，中间版心图像759幅，双排小字图像2 129幅。为评价混合区域粘连分割的效果，定义分割准确率PG为

(18)

式(18)中：NR为准确分割图像个数；N为混合区域图像个数。

实验发现，版面分割结果的优劣仅通过准确率来判断不够充分。混合区域分割过程中，图像倾斜、粘连框线不完整、波动阈值选取不合适等因素都会使实际的粘连分割点定位困难，导致分割结果中残余小部分框线。这些短小框线并不影响后续的汉字切分等环节，故将这类图像定义为微错分割图像，并在原有基础上加入了微错分割准确率[22]PW的评价标准：

(19)

式(19)中：NW为微错分割图像个数。

版面分割结果如表2所示。从表2可以看出，本文算法切分单排大字效果最好，分割准确率和微错分割准确率分别为87.97%、91.92%；中间版心效果次之，分割准确率和微错分割准确率分别为83.14%、86.17%；双排小字粘连分割效果最差，分割准确率只有72.47%。最后通过计算上述3种图像的平均值得到最终的版面分割实验结果，分割准确率和微错分割准确率分别为78.69%、81.30%。

表2 版面分割实验结果Table 2 Experimental results of layout segmentation

2.3 时间性能分析

(20)

式(20)中：T为样本图像版面分析所用的总时间。

算法时间数据如表3所示。从表3可以看出，本文算法耗时少于文献[7]。因为后者以连通区域为处理元素, 重复合并连通区域分割图像，并选取BP神经网络进行版面分类，增加了时间复杂度。而本文算法根据投影分割后的版面区域特征的明显差异求取分类阈值，整个版面分析过程中未使用结构复杂的模型。

表3 两种算法时间性能对比Table 3 Comparison of time performance of two algorithms

图5所示为本文算法对一幅古籍文献版面图像的分析结果，框线区域用蓝颜色标记。可以看出文字区域完整性较高，能较好地解决古籍版面框线影响文字切分的问题。

图5 版面分析结果Fig.5 The results of layout analysis

3 结论

基于对《四库全书》版面特点的分析与归纳，提出了一种基于LOF和波动阈值的古籍版面分析方法。首先，采用基于LOF的分类算法对古籍图像投影分割后的版面区域进行分类；然后，利用波动阈值对文字与框线相粘连的版面混合区域进行分割；最后，将古籍版面中的文字区域输出。实验证明，在古籍图像具有一定程度倾斜、文字与框线存在较多粘连、框线大多不完整的情况下，本文方法分离古籍版面文字区域和框线区域仍具有较好的效果。同时本文设计的算法结构简单，执行速度较快，版面分析耗时较少。但也存在一些不足，对于盖有印章的古籍图像，印章与文字、框线交织在一起，三者的分离较为困难，分析准确率受到影响，后续将继续研究改进。