基于图像统计学聚类的非规则表格处理算法

吕志刚，李亮亮，王洪喜，王 鹏，李晓艳

(1.西安工业大学 机电工程学院，陕西 西安 710021；2.西安工业大学 电子信息工程学院，陕西 西安 710021)

0 引言

在军工、航空航天等部门，早期的机械表格类档案大多以纸质版形式存在，不但不便于存储、检索、运输，还容易受外部环境破坏和人为折损。因此，对纸质版的机械表格类档案进行数字化，并对其有效元素进行光学字符识别(Optical Character Recognition, OCR)的提取与管理，可以达到有效管理机械产品的目的。机械表格类档案中的有效元素包括表格、字符、图形等，由于制表技术的限制，早期纸质版表格类档案中包含不规则因素，表现为表格纵向直线不连续、表格框线错位、表格跨页、特殊字符、油渍污染等。目前的表格提取算法主要采用传统形态学和深度学习的方法，两种方法各有优劣。

王绪等[1]通过投影特征和结构特征实现对表格文本与非文本的分类；邝振等[2]采用投影法提取横纵直线坐标和构造表格特征点来识别选票表格；段露等[3]采用水平投影对问卷表格进行行分割；XIAO等[4]采用Hough和Opencv中的形态学函数进行表格定位分割，但存在一定的局限性。文献[1-4]的算法执行效果取决于水平框线和垂直框线的提取质量，需要有针对地调节阈值才能取得较好的效果，因此不能实现自适应阈值且鲁棒性欠佳。

白伟等[5]采用基于游程和同线直线的聚类提高对复杂表格高度的识别率，但也在一定程度上加大了算法的时间开销；BANSAL等[6]提出基于定点模型的表格提取算法，然而算法复杂度较高，不便于实际应用；SHI等[7]提出一种基于表格模型的单元格检测方法，但建立表格驱动模型比较繁琐，工作量较大，其可行性和鲁棒性受到很大限制；LIANG等提出一种鲁棒的表格识别系统，其采用改进的Sauvola鲁棒二值化算法能够更好地处理光照不均匀和成像模糊的图像，并基于形态学检测方法提取表格横纵直线，虽然具有一定可行性，但是未对鲁棒性进行大量复杂的表格测试，且形态学检测方法不能自适应处理表格，存在局限性[8]。

文献[9-11]为基于深度学习模型的表格识别，最终得到的是表格边界坐标，其算法执行依赖于硬件设备的质量及大量数据集的前期训练测试，虽然在很大程度上限制了应用的普及，但是相对传统的表格布局分析方法提高了检测准确率。文献[12-14]为基于深度学习模型的OCR，是本文数字化复现的基础，其中卷积递归神经网络(Convolutional Recurrent Neural Network,CRNN)能够获取不同尺寸的输入图像，并产生不同字符序列长度的预测，其直接在粗粒度的标签(如单词)上运行，训练阶段不需要详细标注每个单独的元素(如字符)[12-14]，因此选用CRNN模型作为OCR数字化复现框架。

1 本文相关工作

在倾斜表格校正和表格检测过程中，针对以上算法不能自适应处理表格、鲁棒性欠佳且表格单元分割算法陈旧等问题，改进现有算法。首先，改进传统的表格图像倾斜校正算法；其次，给出一种基于图像统计学聚类的表格定位提取算法，以处理多分辨率、不同成像质量的表格图像；再次，给出一种基于局部小区域内像素占比的跨页判别拼接算法，以保证表格单元分割图像的完整性；最后，选择端到端的CRNN作为OCR的网络框架，针对分割出来的单元格图像识别文字信息。综上所述，本文的主要工作总结如下：

(1)改进传统倾斜表格矫正算法。

(2)提出一种基于图像统计学聚类的直线方程拟合算法，在不同分辨率和不同成像质量的表格图像(包括不规则表格图像)中定位提取表格信息。

(3)提出一种基于局部小区域内像素占比的跨页拼接算法。

(4)提出一种基于图像统计学聚类的表格交点提取算法，处理多分辨率、多成像质量表格图像和跨页拼接图像。

(5)在处理分割后的Cell(单元格)图像时，针对性地构建文本信息数据集，训练CRNN网络结构，并成功识别与复现文字信息。

图1所示为本文的主算法流程，图2所示为本文算法进行的可视化演示。

2 算法模型的建立

2.1 倾斜矫正算法的改进

本文基于Hough横向直线检测拟合的水平矫正方法进行改进，因为直接采用Hough横向直线检测会产生很多误检测直线，所以通过自定义构造水平检测结构元素来自适应提取形态学阈值的横向直线，再用Hough重构横向直线，从而极大提高了横向直线的检测准确率及矫正准确性。

主要操作流程如下：

(1)将多分辨率的表格图像进行灰度化处理，然后进行腐蚀膨胀，并采用大津法(OTSU)进行二值化处理。

(2)构造水平检测结构元素，再对二值化图像进行形态学处理，提取图像中的横向直线信息。

假设输入图像像素为rows×cols，构造水平检测元素height=1，width=cols/10，选择MORPH_RECT进行形态学检测，即可实现对横向直线的自适应判别。

(3)采用Hough重构横向直线，以避免形态学检测时出现间断直线，重构后得到连续的横向直线集合。

(4)Hough变换计算平均旋转角度。将图像从图像空间变换到参数空间，变换公式为

ρ=xcosθ+ysinθ。

(1)

式中：直角坐标系中的变量空间(x,y)为已知量，k为直线斜率；极坐标下，以原点为起点，做直线y=kx+b的垂线，ρ为原点到该直线的距离；设(x,y)与原点之间的连线为l，θ为l与X轴正向的夹角。

变换以后，图像空间中的一个点在参数空间为一条曲线，而图像空间共线的各点在参数空间为交于一点的多条曲线。对所有曲线的旋转角度进行累加并取平均值，得到步骤(5)所需的平均旋转角度。

(5)计算二维旋转仿射变换矩阵。

(6)基于原尺寸逆时针旋转图像角度。

2.2 表格定位分割

本文在扫描的A4大小文档图像中提取表格信息，图3所示为本文所研究的不规则表格类型。可见，表格的横线完整，竖线不完整，因此表格检测，特别是表单元分割比较困难，为本文解决的难题之一。

在进行表格定位分割时，需提取表格标题1和测试时间信息，以便数字化复现分类存储管理；因为研究对象——横向直线均连续完整，并在表格检测之前已经进行了倾斜矫正，所以得到的图像近似为横平竖直且行间距相同。

定位分割操作流程如下：

(1)采用Harris进行角点检测，预框选感兴趣区域(包括本页文档图像中所有表格区域和非表格区域)，并进行灰度腐蚀二值化，记录感兴趣区域纵向极值Ymax和Ymin。

(2)预提取横向直线，并用Hough重构直线(与倾斜矫正算法类似，不做详细说明)，得到仅含横向直线的二值化图像。

(3)进行基于拟合直线方程的表格定位分割。

设输入的本页文档图像表格列数为col，第i条横向均值坐标即直线方程为y=yi，可知本页文档行间距为yi+1-yi，因为本文研究的表格图像存在标题和时间信息，行距占据一行且表格与表格之间至少有1.5倍行间距，所以设计如下表格定位分割规则：

规则1若(yi+2-yi+1)-(yi+1-yi)≥10或(yi+1-yi)-(yi+2-yi+1)≥10(i=0,1,2,3,…)，则表格之间可能存在分割直线方程。其中，yi+1为上一个表格的结束直线方程，yi+2为下一个表格的开始直线方程。

规则2若满足规则1，且在输出(yi+2,yi+1)开区间范围内不存在col条纵向直线，则确定yi=0，yi+1，yi+2为当前输入文档图像页的表格间隔分割直线方程。

规则3若基于规则2提取标题和时间信息(不包含不规则表格上下文信息)，则得到最终确定表格中的第一条直线方程为：

y=yi=0-(yi+1-yi)×1.5，i=0；

y=yi+2-(yi+1-yi)×1.5，i>0。

(2)

修正i=0，如果式(3)成立，则yi=0=Ymin，表示表格框线中包含不完整信息；否则，yi=0=yi=0-(yi+1-yi)×1.5,i=0(包含不规则表格上下文信息)。另外，

yi=0-(yi+1-yi)×1.5-Ymin∈[(yi+1-yi)×1.5,

yi=0-(yi+1-yi)×1.5]，i=0。

(3)

规则4若满足规则3，则可以确定最后一个表格的最后一条直线方程y=yi+1(表示表格框线中未包含不完整信息)。

根据式(4)修正编号4表格的最后一条直线方程规则(包含不规则表格上下文信息)：

y=yi+1+((yi+1-yi)·thresh)∈

[(yi+1-yi)·thresh,Ymax]，i>0。

(4)

需要根据不规则表格残缺类型确定阈值thresh，不规则表格的残缺类型分为有内容无页码残缺、无内容无页码残缺、有内容有页码残缺、无内容有页码残缺。本文以有内容无页码为例，介绍阈值thresh的求解过程。图4所示为有内容无页码的残缺示意图，根据屏幕像素尺寸和实际文档像素比例求解阈值。从图可知屏幕像素尺行间距为22 pixel，最后一条直线方程与表格底部的差值为20 pixel，因此thresh=20/22=0.909。其中，是否包含页码元素，并不影响最终阈值的确定，为满足实际需求，设各种类型残缺表格的thresh=0.909。

根据规则4确定的横向直线方程，以y=yi=0和y=yi+1为上下边界进行处理。图5所示的右上角外围虚线框内为冗余处理后的图像，对其进行Hough检测处理，得到构成横向直线的各点坐标。设坐标最小值为xmin，最大值为xmax，为保证获取表格纵向直线边界，将xmin-15和xmax+15作为表格左右纵向直线的边界。

根据本节设计的表格定位分割规则进行扫描文档的表格定位分割，其中第一个表格和最后一个表格中包含不规则表格的上下文信息，需要进一步处理，将当前分割定位的表格信息存入集合table={tablei}(i=0,1,2,3,…)。

2.3 完整性检测及跨页拼接

本节主要对包含不规则表格中的残缺表格上下文信息的表格图像进行处理，在残缺表格上下文信息中剔除非表格冗余信息，保留有效表格信息，并通过判断表格的完整性决定是否进行跨页拼接。设计跨页拼接规则时，首先制定跨页判定规则，然后根据该规则判定残缺表格，具体如下：

通过上述跨页判定规则可以明确表格是否存在跨页现象，是则拼接残缺表格的上下文信息。根据残缺状态矩阵制定以下跨页拼接规则：

规则5拼接时下一页顶表补上一页底表(当前页大于2且tablei=0完整)。

规则6拼接时上一页底表与下一页顶表宽度相同。

规则7拼接图像数量大于等于2，在内存允许下，可连续跨页拼接N页(N为正整数)。

在满足规则5～规则7的前提下，用残缺状态矩阵进行跨页拼接。跨页拼接流程如图6所示。

本文提出一种基于局部小区域内像素占比的跨页拼接算法，本算法可以剔除不完整表格信息并检测完整性，根据规则5～规则7进行跨页拼接，图7a所示为两张跨页表格，分别为上一页底部残缺和下一页顶部残缺，根据跨页拼接算法及拼接规则进行跨页拼接得到图7b。

2.4 表单元分割

针对跨页拼接完毕的表格图像，本文提出一种基于图像统计学聚类的表格交点提取算法，以分割多种分辨率的表单元。图8所示为本文所提表单元提取算法流程图，其中横向直线方程拟合算法思路与2.2节介绍的表格定位分割流程类似，此处主要针对纵向直线方程拟合进行详细说明。

根据拟合得到的纵向直线方程和横向直线方程求得表格交点，进而对表单元进行分割。图9所示为表单元分割的可视化演示。

本文设2.2节和2.3节处理后的表格图像中的横向直线方程集合为y={sheetyj}(j=0,1,2,3,…)，该方程集合可以在横向直线方程拟合阶段得到。

基于纵向投影直方图的纵向直线方程拟合的主要步骤如下：

(1)纵向直线重构

该部分采用构造纵向形态学检测结构元素对纵向直线进行预提取，同时拼接连续跨N页图像，导致纵向直线检测极为困难，本文基于横向直线方程构造垂直检测结构元素height=(sheetyj+1-sheetyj)/4，width=1，选择MORPH_RECT进行直线逼近并输出检测。可以看出，结构体元素的height与表格实际行高建立关联，即实现了阈值的自适应选择。然后，对输出图像进行Hough重构，得到仅含纵向直线的二值化图像。

(2)纵向直线预处理

处理区域为[sheetyj+thresh_sheet(sheetyj+1-sheetyj),sheetyj+1-thresh_sheet(sheetyj+1-sheetyj)]，其中根据图5 中A区域里的细虚框线确定thresh_sheet=4/22=0.182。

将所求处理区域的像素值赋值为0，对处理后的图像进行纵向直方图投影，得到X方向的像素区域集中分布图及X坐标集合sheetx={sheetxi}(i=0,1,2,3,…)。

(3)对预提取的纵向坐标集合进行顺序排序

对集合sheetx按sheetxi+1>sheetxi(i>0)进行排序。

(4)将同一聚类中相邻坐标偏差较小且区间内极差偏移量较小的一组直线作为同一类纵向直线

聚类条件为sheetxi+1-sheetxi

(5)根据输入的表格列数和波峰提取聚类数

设当前输入表格的列数为sheet_col，即有效聚类数为sheet_col+1。首先，提取sheetxnew集合，用集合sheetxj值代替sheetxnewi{sheetx{sheetxj}}集合中的sheetx；其次，对集合sheetxnew按sheetxnewi>sheetxnewi+1(i>0)进行排序，在集合sheetxnew中提取sheet_col+1个集合，构成新的集合sheetxnew_ok={sheetxnew_oki{sheetx{sheetxj}}}(i=0,1,…,sheet_col,j=0,1,2,3,…)。

(6)取聚类结果的平均值，输出纵向区间均值坐标

在集合sheetxnew_ok中，将同一组纵向直线的坐标取平均值，得到纵向直线的均值坐标sheetxsumi，并将sheetxsumi更新为集合sheetxnew_ok，最终的集合为sheetxnew_ok={sheetxsumi}(i=0,1,…,sheet_col)。

(7)根据输出纵向均值坐标建立纵向直线方程

根据步骤(6)输出的确定集合构建纵向直线方程组

y=sheetxsumi,i=0,1,…,sheet_col。

(5)

2.5 文本信息识别

(1)预处理

本文方法分割的表单元，在文字左右两边有非文字空白区域，因为OCR及数字化复现会造成相应的文本错误，所以通过投影法进行进一步处理。图10所示为表格单元格边界处理流程图，图10a为输入的分割后的单元格图像，图10d为输出的处理后的单元格图像。

(2)数字化识别

数字化识别部分采用现有的CRNN模型识别和提取分割表单元内容[15]，同时有针对性地构建训练测试数据集。CRNN模型对文字和数字的识别效果较好，但不能很好地识别±，℃，%，≥，≤，Δ，Ψ，Ω，Φ，Υ，δ，ζ，μ，σ，ψ，ω等特殊符号，甚至会输出错误符号。因此，本文研究重点在于如何使用CRNN模型数字化识别特殊符号，在原来的文字和数字等数据集的基础上增加特殊符号训练数据集。该数据集来源于扫描图像，通过对大量表格图像进行扫描，分类提取带有特殊符号的表单元数据，然后进行CRNN模型训练，初步提高对特殊符号的识别率。

本文采用C++调用Python文件进行数字化识别，C++与Python文件交互的关键代码及设置可参考个人博客[16]。

3 实验与分析

本文算法在Window 10操作系统、Intel(R)Core(TM)CPU i7-8700HQ 3.20 GHz 8 G内存电脑平台进行开发测试，扫描设备为Alaris E1025和EPSON Perfect v19。非深度学习部分代码采用C++语言，集成开发环境为QT5.9.8，编译器采用MSVC2015，计算机视觉库选择Opencv3.1。配置流程可参考个人博客[17]，同时调用Python 3.7.4+Tensorflow 1.13.1版本构建的CRNN深度学习模型进行OCR识别[15]。

3.1 图像预处理及倾斜矫正测试

本节主要测试所提改进倾斜校正算法的可行性。在相同条件下测试本文改进算法和原始算法，对比结果如表1所示。

因为本文在基于直线的倾斜表格矫正中增加了直线的预提取环节，以增加矫正准确率，所以算法的空间复杂度相对传统方法更高。

3.2 表格定位分割测试

针对扫描后的多种表格图像，在相同条件下，分别采用本文算法和传统算法进行处理，定位分割结果如图11和图12所示。可见，在测试样本中，本文算法可以实现100%定位分割，传统算法只有正常表格和一部分测试样本能够准确实现定位分割。因此，本文算法的识别率明显优于传统基于轮廓的识别算法。

对测试样本中的6张文档图像，采用本文算法和传统算法进行算法复杂度测试。

识别率计算公式为

recognition_rate=

(6)

如表2中的序号1～6所示，本文算法的识别率和算法复杂度均优于传统基于轮廓的识别算法，在处理图11中第6个表格图像时，虽然定位区表格范围存在交叉现象，但是仍然能够准确定位表格，如图11中的虚线框所示。出现该情况的原因是相邻两个表格间距离太近，将其作为个案在表2中加粗表示。同时，对多种低分辨率的文档图像进行测试，如表2中的序号7～10所示。分析表中数据可知，本文算法相对传统算法在空间复杂度和准确率上均有明显提高，且适应性和鲁棒性更强。

表2 表格定位算法耗时测试

3.3 完整性检测及跨页拼接测试

对定位提取后的第一个表格和最后一个表格进行完整性和跨页拼接鲁棒性测试。针对最复杂的跨N页拼接情况，采用本文提出的完整性检测、跨页拼接规则进行检测和拼接。测试条件为：依次输入N页不完整文档，保证第一页顶部和最后一页底部完整，才能完成对跨N页表格文档的拼接。跨页拼接结果如图13所示，相关量化结果如表3所示。

表3 跨页拼接算法耗时测试

跨页拼接部分算法时间包括N页文档表格定位分割时间、表格顶底完整性检测时间和跨N页分割表格拼接时间。跨页数量越多，拼接耗时及内存占用率越高。表格完整性对后续表单元分割和OCR数字化复现的质量起决定作用。

3.4 表单元分割测试

(1)算法鲁棒性和自适应性测试

图14所示为多种复杂表格纵向直方图统计过程输出图，图14d为本文算法处理后X方向的像素区域集中分布图。当前输入的有效聚类数为5，取其波峰最高的前5+1个作为最终聚类输出[18-19]，对比4种不同类型的复杂表格，均能有效得到输出聚类。

图14e为同一条件下横向直线与纵向直线使用传统算法输出的交点，白色实线框中的一部分和白色虚线框中为误检测冗余输出，可见交点检测存在一定局限性，需要针对特殊图像调节阈值，因此鲁棒性和自适应性均较差。

图15所示为横纵直线实际相交情况下，采用传统算法未输出交叉点，即使采用深度学习驱动的交点检测模型也很难准确检测出表格交点，其中表格内部大量出现“十、古、王、玉、汪、工”等文字，当字体加粗且字体直线宽度大于表格直线宽度时，会误将文字交叉点检测为表格交叉点，该方法因交点检测准确性较差且算法复杂度较高而缺乏可行性。

图16所示为X方向上像素区域集中分布对比图，其中：图16a为准备进行表单元分割的输入图；图16b为对图16a进行Hough重构处理后的输出图；图16c为直接对图16b进行纵向投影的结果，可见很难得到有效聚类；图16d为采用本文聚类提取算法得到的纵向投影图，白色虚线框为得到的有效聚类。结合图14的实验测试证明，本文算法在多种复杂表格下均能准确得到有效聚类，具有一定的自适应性和鲁棒性。

(2)表单元分割测试

以图16a所示的复杂表格为例，通过直线方程的横纵交叉，确定横纵坐标来分割单元格，如表4所示。

表4 单元格横纵坐标表

根据表4中的各交叉点坐标分割单元格，分割结果为：输出8行5列表格，共8×5=40个单元格。如图17所示。

(3)算法复杂度测试

本节对跨N页表格和正常表格进行表单元分割，如表5所示。

表5 表单元分割算法复杂度测试

通过测试可知，本文提出的表单元交点聚类提取算法，在输入当前待分割表格列数后，可实现100%的提取分割。同时，算法在多种分辨率的表格图像提取分割中具有一定普适性，以及较强的自适应和鲁棒性。

3.5 字符识别情况

因为所提取表单元中的文本图像不包含非文字区域，所以可直接输入CRNN模型进行字符的数字化识别。本文采用CRNN模型进行构建和训练可以较好地识别印刷体文字、数字、字母，采用额外增加的带有特殊符号的样本训练集进行预训练能够较好地提高对特殊符号的识别。由于初步构建的特殊符号数据集较少，目前对单独特殊符号只构建了20个训练样本集。

3.6 定量分析

将现有147张纸质版、包含有不规则表格的测试报表，在75 dpi～400 dpi等多种成像分辨率下进行扫描脱密，随机重复抽取20张样本，采用网易、薪火、腾讯、百度、金铭、翔云、汉王、ABBYY等主流公司表格OCR进行测试，表6所示为各指标的迭代均值。

表6 表格识别算法定量分析

对于在线软件开发工具包(Software Development Kit, SDK)测试，平均一页文档处理速度在1 s以内，其中ABBYY、汉王、腾讯等表格区域定位较好，但是对纵向存在间断线的表格内部结构识别效果不佳，表格内部数字化复现效果较差。本文算法可实现对不规则表格的识别与处理，包括残缺表格定位、跨页拼接、单元格提取及字符识别，但是空间复杂度略高于现有算法，主要是跨语言交互式调用时开销较大。由于算法实现需要跨语言交互，在加载不同集成开发环境以及相互调用时，会造成较大的额外时间开销，后续可以将不同编程语言实现的功能封装成本地SDK，以减少额外的时间开销。本文算法的表格识别率和文本识别率可以分别达到97.32%，92.75%，主要原因是错位表格框线的干扰会将错位的框线识别为“1，I，|”。

4 结束语

本文提出一种基于图像统计学的聚类表格定位分割和跨页拼接算法，用于检测表格和提取表单元。该算法旨在解决纵向竖线不完整的表格定位、表单元分割，以及跨N页表的拼接，若将表格的实际列数作为算法的输入量，则可显著提高表单元格分割成功率。介绍了如何根据表格定位分割规则对不完整残缺表格进行定位和分割，如何根据跨页拼接规则完整拼接跨N页表，以及如何提取基于图像统计学的聚类表格交点。在不同成像分辨率条件下，扫描现有147张存在非规则现象的机械零部件测试报表，并进行表格定位、表格拼接、表单元分割、字符识别等操作，迭代测试实验结果表明，残缺复杂表格的识别准确率可达97.32%。本文所提算法对不完整残缺表格定位、表单元分割及跨N页表拼接的测试效果良好，且具有较好的自适应性和鲁棒性，但在处理存在较大污渍或手写字符的测试报告时效果不佳，需要借助深度学习的方法，进一步提高表格和字符的识别准确率。