本发明公开了一种基于关键点检测的全线表表格结构识别方法，包括：采用关键点检测网络对表格图像中的关键点进行检测，得到包含所有关键点位置信息的高斯热图；将高斯热图放缩至和输入表格图像尺寸一致，并通过轮廓中心距算法得到所有关键点的坐标位置；使用扫描线法解析关键点在表格中的结构位置关系；使用连通域法检测相邻的关键点是否存在连接关系；根据关键点之间的结构位置关系和连接关系重构出表格中所有的单元格，并转换为需要的标记语言描述。本发明方法采用基于深度学习的关键点检测方法能够鲁棒地找到表格图像中的所有表格线交点，并根据这些关键点获取所有单元格的准确位置，从而高质量完成表格结构识别。
一种基于关键点检测的全线表表格结构识别方法
技术领域
[0001] 本发明属于图像处理与人工智能技术领域，特别是涉及一种基于关键点检测的全线表表格结构识别方法。
背景技术
[0002] 表格是一种简明和紧凑的内容组织方式，可视化效果好，因此具有广泛的应用价值，被广泛应用于数据可视化、计算机软件、票据记录等方方面面。随着信息时代的到来，人们的日常生活、商业交流和实验研究等中产生了更多的数据，表格的数量也随之指数级增长，这些表格数据对大数据挖掘、知识图谱等系统非常有价值。然而，表格这种结构化的数据通常不容易通过算法识别，另一方面，表格间存在单元格融合的情况，也加大了算法识别表格结构的难度。为了能高效提取出表格中的数据，表格结构识别是其中的一个关键任务，研究出一种能够有效识别表格结构的算法，辅助表格中的数据提取具有重大意义。
[0003] 传统的表格结构识别算法往往使用人工设定特殊的算子来检测表格线，并获取表格线的行列信息，再结合表格线的交点确定表格中的单元格，完成表格结构识别。然而这些方法有一定的缺陷：一方面在检测直线时候十分依赖于人工设定特殊的算子性能，检测出的表格线容易出现短线等问题；另一方面，这些方法往往只能用于PDF文件导出的规整、背景干净的表格，当面对通过扫描、拍照等得到的不规整、背景丰富多样的表格，往往性能会急剧下降。
[0004] 因此，随着深度学习的火热，基于深度学习的表格结构识别算法也应运而生。目前可以分为三类：
[0005] 第一类是基于实例分割的方法，其思想主要是通过深度学习中的实例分割算法来分割出表格中的所有单元格，然后通过一些人工预设的后处理来完成表格结构识别。但该类算法只能完成对单元格的定位，而不能识别出单元格在表格中的结构位置，因此其性能依赖于人工设定的后处理算法。另一方面，分割算法只能给出单元格所占用的区域，还需要用最小外接矩形等算法才能够获取单元格而的大致形状和位置，这都是不够准确的。
[0006] 第二类是基于图像到序列的方法，其核心在于把表格结构编码成LaTeX或HTML等序列，从而能直接通过一个图像转化序列的模型完成表格结构识别。但是该类方法没有显式利用单元格的位置和结构信息，从而限制了该类模型的性能。
[0007] 第三类是基于图神经网络的方法，其关键在于用图神经网络来完成表格中单元格关系的建模，把单元格作为节点，单元格之间的结构关系作为边，从而把表格结构识别的问题转化为边的分类问题。但是这些方法需要先通过单元格检测网络来得到单元格的位置信息，且不能和单元格检测网络端对端训练，因此其性能受限于这些单元格检测网络的性能。
[0008] 综上所述，传统方法缺少鲁棒性无法应对当今更加复杂的表格，而深度学习的方法受制于准确获取单元格的位置。因此，需要一种鲁棒的、能够准确获取单元格位置的方法来进行表格结构识别。
发明内容
[0009] 有鉴于此，有必要针对上述技术问题，提供一种基于关键点检测的全线表表格结构识别方法，所述方法把表格线的交点作为关键点，首先使用关键点检测模型检测出表格图像中的所有关键点，接着判断这些关键点在表格中的结构位置关系（所处行、列）和连接关系，最后借助关键点之间的关系重构出单元格，从而完成表格结构识别。
[0010] 本发明公开了一种基于关键点检测的全线表表格结构识别方法，包括以下步骤：
[0011] 步骤1，采用关键点检测网络对表格图像中的关键点进行检测，得到包含所有关键点位置信息的高斯热图；
[0012] 步骤2，将高斯热图放缩至和表格图像尺寸一致，并通过轮廓中心距算法得到所有关键点的坐标位置；
[0013] 步骤3，使用扫描线法解析关键点在表格中的结构位置关系；
[0014] 步骤4，使用连通域法检测相邻的关键点是否存在连接关系；
[0015] 步骤5，根据关键点之间的结构位置关系和连接关系重构出表格中所有的单元格，并转换为需要的标记语言描述。
[0016] 可选地，所述的关键点检测网络为HRNet。
[0017] 可选地，所述的关键点检测网络为DeeperCut。
[0018] 关键点检测网络使用自己构建的表格关键点数据集进行预训练，以获得检测表格关键点的能力。
[0019] 具体地，表格关键点数据集包含500张表格图像，并给出每一张表格图像中的所有表格线关键点的坐标作为关键点的坐标位置的标注。其中，表格图像数据来源为工单图像，是全线表格。
[0020] 具体地，所述的轮廓中心距算法包括以下步骤：
[0021] 对高斯热图采用高斯模糊算法，以减少高斯热图中轮廓边沿出现的噪点；
[0022] 对高斯热图进行二值化操作，得到二值化图；
[0023] 对二值化图进行轮廓检测，得到所有关键点的轮廓；
[0024] 对每一个关键点的轮廓计算中心距，所述的中心距即为所述的关键点的坐标位置。
[0025] 可选地，轮廓检测算法采用OpenCV中的findContour()方法实现。
[0026] 具体地，所述的轮廓计算中心距的计算公式如下：
[0027] 对于关键点 ，其坐标位置为 ，则， ， ；
[0028] 的计算公式如下：
[0029]
[0030] 其中， 是关键点 的轮廓，轮廓上所有点的集合 ，表示轮廓点在图中的横坐标， 表示轮廓点在图中的纵坐标， 表示 的 次方，表示 的 次方， 表示对轮廓中所有点的横坐标 和纵坐标 经过运算后
求和， 是轮廓的零阶空间矩， 和 是轮廓的一阶空间矩。
[0031] 具体地，所述的关键点在表格中的结构位置，即关键点属于第几条行表格线以及第几条列表格线。
[0032] 更进一步地，所述的扫描线法，包括以下步骤：
[0033] 把表格图像缩放到相同的高度和宽度；
[0034] 设置一条初始的直线作为行扫描线，并从上往下地在表格图像中竖直移动，每次移动固定的距离 ；
[0035] 每次移动1个距离 后，计算在行扫描线上方的关键点数 ；
[0036] 当连续移动预设的 个移动距离 ，若关键点数 都没有增加，则在当前位置设置一条行分隔线；
[0037] 根据行分隔线把所有关键点按行分开，从而得到关键点属于第几条行表格线；
[0038] 设置一条初始的直线作为列扫描线，并从左往右地在表格图像中水平移动，每次移动固定的距离 ；
[0039] 每次移动1个距离 后，计算在列扫描线左方的关键点数 ；
[0040] 当连续移动预设的 个移动距离 ，若点数 都没有增加，则在当前位置设置一条列分隔线；
[0041] 根据列分隔线把所有关键点按列分开，从而得到关键点属于第几条列表格线。
[0042] 优选地，若表格图像中的表格是倾斜的，对应的行扫描线或者列扫描线则需要矫正；
[0043] 行扫描线的矫正过程为：首先设置初始的行扫描线为水平直线，进行第一次扫描线法得到位于第一条行表格线的点，接着根据这些点的坐标使用最小二乘法求出近似斜率，把该近似斜率应用在初始的行扫描线上作为矫正后的行扫描线；
[0044] 列扫描线的矫正过程为：首先设置初始的列扫描线为垂直直线，进行第一次扫描线法得到位于第一条列表格线的点，接着根据这些点的坐标使用最小二乘法求出近似斜率，把该近似斜率应用在初始的列扫描线上作为矫正后的列扫描线；
[0045] 所述的最小二乘法求出近似斜率，计算公式如下：
[0046]
[0047] 表示矫正后的行扫描线或列扫描线的近似斜率，为第一条行表格线或列表格线上的点的坐标， 为位于第一条行表格线或列表格线上的点的点数；
[0048] 其中， 的计算公式如下：
[0049] 。
[0050] 具体地，所述相邻关键点，指的是属于同一条行表格线，且属于相邻的列表格线上的两个关键点，或属于同一条列表格线，且属于相邻的行表格线上的两个关键点。
[0051] 具体地，所述的连通域法，包括以下步骤：
[0052] 遍历所有的相邻关键点，以关键点的位置为圆心，先作一个半径为r的圆，然后得到一个包含这两个相邻关键点为圆心的圆的最小外接矩形作为裁剪区域，接着从表格图像裁剪出相邻关键点所在的局部区域图；
[0053] 把局部区域图转换为灰度图后，使用高斯低通滤波器进行平滑操作，并使用闭运算把连通域中的缝隙填充，然后使用自适应阈值算法转化为二值图像，接着找到第二大的连通域；最大的连通域为背景，而不是前景；
[0054] 取局部区域图的高度和宽度中的最大值为 ，第二大的连通域的高度和宽度中的最大值为 ，计算出占比 ，计算如下：
[0055]
[0056] 当 大于预设阈值threshold时认为相邻关键点之间存在连接关系，否则不存在连接关系。
[0057] 更进一步地，所述的存在连接关系包括存在纵向连接关系和存在横向连接关系，若局部区域图的高度大于宽度，则为存在纵向连接关系；若局部区域图的高度小于宽度，则为存在横向连接关系；
[0058] 所述的不存在连接关系包括不存在纵向连接关系和不存在横向连接关系，若局部区域图的高度大于宽度，则为不存在纵向连接关系；若局部区域图的高度小于宽度，则为不存在横向连接关系。
[0059] 更进一步地，所述的根据关键点之间的结构位置关系和连接关系重构出表格中所有的单元格的步骤如下：根据重构规则，先找到关键点中所有的左上角点，然后再找到每一个左上角点相对应的右下角点，从而重构出所有的单元格；
[0060] 所述的重构规包括：规则一，每个关键点最多只能是一个单元格的左上角点，也最多只能是一个单元格的右下角点；规则二，当相邻关键点不存在连接关系时，若不存在纵向连接关系，则位于上方的关键点不是左上角点且位于下方的关键点不是右下角点；若不存在横向连接关系，则位于左方的关键点不是左上角点且位于右方的关键点不是右下角点；规则三，一个单元格的左上角点对应的右下角点所处的列表格线位于该单元格右相邻的单元格的左上角点所处的列表格线的同一列或左方，若没有右相邻的单元格，则该单元格的左上角点对应的右下角点所处的列位于最后一条列表格线的同一列或左方；规则四，一个单元格的左上角点对应的右下角点所处的列表格线位于该单元格的左上角点所处的列表格线的右方；规则五，一个单元格的左上角点对应的右下角点为符合规则三、四的点中距离左上角点最近的。
[0061] 具体地，所述的重构出所有的单元格的步骤如下：
[0062] 把所有关键点构成的集合作为候选左上角点集合，同时把所有关键点构成的集合作为候选右下角点集合；
[0063] 根据规则二，根据所有相邻关键点之间的连接关系，当相邻关键点不存在纵向连接关系时，则将位于上方的关键点从候选左上角点集合中去掉，同时也将位于下方的关键点从候选右下角点集合中去掉，当相邻关键点不存在横向连接关系时，则将位于左方的关键点从候选左上角点集合中去掉，同时也将位于右方的关键点从候选右下角点集合中去掉，得到正式的所有左上角点集合和所有右下角点集合；
[0064] 根据规则一，由于每个点最多只能是一个单元格的左上角点，也最多只能是一个单元格的右下角点，因此左上角点集合中的左上角点和右下角点集合中的右下角点是一一对应的，接下来只要为所有左上角点集合中的左上角点找到相对应的右下角点，即可重构出所有单元格；
[0065] 根据规则三，依次取出所有左上角点集合中的一个左上角点，称其为左上角点A，找到与左上角点A位于同一行表格线上的多个左上角点，多个左上角点中位于左上角点A右方且距离左上角点A最近的一个即为左上角点A所处的单元格的右相邻的单元格的左上角点，称其为左上角点B；接下来对所有右下角点集合进行第一次筛选，去掉位于左上角点B所在的列表格线右方的右下角点，若左上角点A位于表格中的最后一条列表格线上，则不需要进行第一次筛选；
[0066] 根据规则四，对所有右下角点集合进行第二次筛选，去掉其中所有不满足所处的列表格线位于左上角点A所处的列表格线的右方的右下角点；
[0067] 根据规则五，经过两次筛选后剩下的所有右下角点中找到距离左上角点A最近的一个，该右下角点即为左上角点A对应的右下角点，成对的左上角点和右下角点构成一个单元格；
[0068] 依次找到所有左上角点集合中的左上角点对应的右下角点，即可重构出所有的单元格。
[0069] 与现有技术相比，本发明的有益效果在于，本发明方法采用基于深度学习的关键点检测方法能够鲁棒地找到表格图像中的所有表格线交点，并根据这些关键点获取所有单元格的准确位置，从而高质量完成表格结构识别。
附图说明
[0070] 图1示出了本发明实施方法的流程示意图；
[0071] 图2示出了本实施例表格的结构示意图。
具体实施方式
[0072] 为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0073] 为了引用和清楚起见，下文中使用的技术名词、简写或缩写总结解释如下：
[0074] 高斯热图：热图是一个以颜色变化来显示数据的矩阵，高斯热图即颜色变化呈现高斯分布的热图。
[0075] PDF(Portable Document Format)：便携式文档格式，一种用独立于应用程序、操作系统、硬件的方式呈现文档的文件格式。
[0076] HRNet(High Resolution Net)：高分辨率网络模型。
[0077] DeeperCut：一种关键点检测网络。
[0078] OpenCV(Open Source Computer Vision Library)：一个跨平台的计算机视觉库，封装了许多常用的图像处理的函数和类。
[0079] 行表格线：表格图像中水平的表格线。
[0080] 列表格线：表格图像中竖直的表格线。
[0081] HTML (Hyper Text Markup Language)：超文本标记语言。
[0082] LaTeX：一种排版系统。
[0083] 左上角点：表格中单元格的四个顶点中位于左上角的顶点。
[0084] 右下角点：表格中单元格的四个顶点中位于右下角的顶点。
[0085] 图1示出了本发明实施例的流程示意图。一种基于关键点检测的全线表表格结构识别方法，包括以下步骤：
[0086] 步骤1，采用关键点检测网络对表格图像中的关键点进行检测，得到一幅包含所有关键点位置信息的高斯热图；
[0087] 步骤2，将高斯热图放缩至和输入表格图像尺寸一致，并通过轮廓中心距算法得到所有关键点的坐标位置；
[0088] 步骤3，使用扫描线法解析关键点在表格中的结构位置关系；
[0089] 步骤4，使用连通域法检测相邻的关键点是否存在连接关系；
[0090] 步骤5，根据关键点之间的结构位置关系和连接关系重构出表格中所有的单元格，并转换为需要的标记语言描述。
[0091] 下面结合实例具体说明基于关键点检测的全线表表格结构识别过程。
[0092] 执行步骤1，采用关键点检测网络对表格图像中的关键点进行检测，得到一幅包含所有关键点位置信息的高斯热图。
[0093] 具体地，所述的关键点检测网络为HRNet。
[0094] 关键点检测网络使用自己构建的表格关键点数据集进行预训练，以获得检测表格关键点的能力。
[0095] 具体地，表格关键点数据集包含500张表格图像，并给出每一张表格图像中的所有表格线关键点的坐标作为关键点的坐标位置的标注。
[0096] 其中，表格图像数据来源为工单图像，是全线表格。
[0097] 执行步骤2，将高斯热图放缩至和输入表格图像尺寸一致，并通过轮廓中心距算法得到所有关键点的坐标位置。
[0098] 具体地，所述的缩放采用OpenCV中的resize()算法方法实现，并采用双线性内插。
[0099] 具体地，所述的轮廓中心距算法包括以下步骤：
[0100] 对高斯热图采用高斯模糊算法，以减少热图中轮廓边沿出现的噪点；
[0101] 对高斯热图进行二值化操作，得到二值化图；
[0102] 对二值化图进行轮廓检测，得到所有关键点的轮廓；
[0103] 具体地，轮廓检测算法采用OpenCV中的findContour()算法实现；
[0104] 对每一个关键点的轮廓计算中心距，该中心距即为上述的关键点的坐标位置；
[0105] 具体地，用轮廓中心矩算法计算关键点 的位置 ，计算如下：
[0106]
[0107] 其中， 的计算如下：
[0108]
[0109] 其中， 是关键点 的轮廓，轮廓上所有点的集合 ，表示轮廓点在图中的横坐标， 表示轮廓点在图中的纵坐标， 表示 的 次方，表示 的 次方， 表示对轮廓中所有点的横坐标 和纵坐标 经过运算
后求和， 是轮廓的零阶空间矩， 和 是轮廓的一阶空间矩。
[0110] 执行步骤3，使用扫描线法解析关键点在表格中的结构位置关系。
[0111] 具体地，所述的关键点在表格中的结构位置，即关键点属于第几条行表格线以及第几条列表格线。
[0112] 具体地，所述的扫描线法，包括以下步骤：
[0113] 把表格图像缩放到相同的高度和宽度。
[0114] 设置一条初始的直线作为行扫描线，并从上往下地在表格图像中垂直移动，每次移动固定的距离 ；
[0115] 每次移动1个距离 后，就计算在直线上方的关键点数 ；
[0116] 当连续移动人工预设好的 个移动距离 ，若点数 都没有增加，则在当前位置设置一条行分隔线；
[0117] 根据行分隔线把所有关键点按行分开，从而得到关键点属于第几条行表格线；
[0118] 设置一条初始的直线作为列扫描线，并从左往右地在表格图像中水平移动，每次移动固定的距离 ；
[0119] 每次移动1个距离 后，就计算在直线左方的关键点数 ；
[0120] 当连续移动人工预设好的 个移动距离 ，若点数 都没有增加，则在当前位置设置一条列分隔线；
[0121] 根据列分隔线把所有关键点按列分开，从而得到关键点属于第几条列表格线；
[0122] 优选地，对于倾斜的表格，初始的行扫描线斜率需要矫正；首先设置初始的行扫描线为水平直线，进行第一次扫描线法得到位于第一条行表格线的点，接着根据这些点使用最小二乘法求出近似斜率，把该斜率应用在初始的行扫描线上作为矫正的初始行扫描线。
[0123] 优选地，对于倾斜的表格，初始的列扫描线斜率需要矫正；首先设置初始的列扫描线为垂直直线，进行第一次扫描线法得到位于第一条列表格线的点，接着根据这些点的坐标使用最小二乘法求出近似斜率，把该斜率应用在初始的列扫描线上作为矫正的初始列扫描线。
[0124] 其中，最小二乘法求出近似斜率，计算如下：
[0125]
[0126] 表示矫正的扫描线的行/列近似斜率， 为第一条行/列表格线上的点的坐标， 为位于第一条行/列表格线上的点的点数；
[0127] 其中， 的计算如下：
[0128]
[0129] 执行步骤4，使用连通域法检测相邻的关键点是否存在连接关系。
[0130] 具体地，所述相邻关键点，指的是属于同一条行表格线，且属于相邻的列表格线上的两个关键点，或属于同一条列表格线，且属于相邻的行表格线上的两个关键点。
[0131] 具体地，所述连通域法，包括以下步骤：
[0132] 遍历所有的相邻关键点，以关键点的位置为圆心，先作一个半径为r的圆，然后得到一个包含这两个相邻关键点为圆心的圆的最小外接矩形作为裁剪区域，接着从表格图像裁剪出相邻关键点所在的局部区域图；
[0133] 把局部区域图转换为灰度图后，使用高斯低通滤波器进行平滑操作，并使用闭运算把连通域中的缝隙填充，然后使用自适应阈值算法转化为二值图像，接着找到第二大的连通域（最大的连通域为背景，而不是前景）。
[0134] 取局部区域图的高度和宽度中的最大值为 ，连通域的高度和宽度中的最大值为 ，计算出占比 ，计算如下：
[0135]
[0136] 最后设置一个阈值threshold，当 大于threshold时认为相邻关键点之间存在连接关系，否则不存在连接关系；
[0137] 更进一步地，存在连接关系可以分为存在纵向连接关系和存在横向连接关系，若局部区域图的高度大于宽度，则为存在纵向连接关系；若局部区域图的高度小于宽度，则为存在横向连接关系；
[0138] 更进一步地，不存在连接关系可以分为不存在纵向连接关系和不存在横向连接关系，若局部区域图的高度大于宽度，则为不存在纵向连接关系；若局部区域图的高度小于宽度，则为不存在横向连接关系。
[0139] 执行步骤5，根据关键点之间的结构位置关系和连接关系重构出表格中所有的单元格，并转换为需要的标记语言描述。
[0140] 具体地，根据关键点之间的结构位置关系和连接关系重构出表格中所有的单元格的步骤如下：
[0141] 根据五个规则，先找到关键点中所有的左上角点，然后再找到每一个左上角点相对应的右下角点，从而重构出所有的单元格。
[0142] 具体地，五个规则如下：规则一，每个关键点最多只能是一个单元格的左上角点，也最多只能是一个单元格的右下角点；规则二，当相邻关键点不存在连接关系时，若不存在纵向连接关系，则位于上方的关键点不是左上角点且位于下方的关键点不是右下角点；若不存在横向连接关系，则位于左方的关键点不是左上角点且位于右方的关键点不是右下角点；规则三，一个单元格的左上角点对应的右下角点所处的列表格线位于该单元格右相邻的单元格的左上角点所处的列表格线的同一列或左方，若没有右相邻的单元格，则该单元格的左上角点对应的右下角点所处的列位于最后一条列表格线的同一列或左方；规则四，一个单元格的左上角点对应的右下角点所处的列表格线位于该单元格的左上角点所处的列表格线的右方；规则五，一个单元格的左上角点对应的右下角点为符合规则三、四的点中距离左上角点最近的。
[0143] 所述规则一，如图2，关键点1‑22最多只能是一个单元格的左上角点，也最多只能是一个单元格的右下角点，所有点不会是多个单元格共同的左上角点或共同的右下角点；
[0144] 所述规则二，如图2，关键点7和13不存在纵向连接关系，则位于上方的关键点7不是单元格的左上角点且位于下方的关键点13不是单元格的右下角点；关键点8和9不存在横向连接关系，则位于左方的关键点8不是左上角点且位于右方的关键点9不是右下角点；
[0145] 所述规则三，如图2，一个单元格（图2中由关键点1、2、12、11围成的单元格）的左上角点（图2中关键点1）对应的右下角点（图2中关键点12）所处的列表格线位于该单元格右相邻的单元格（图2中由关键点2、3、8、6围成的单元格）的左上角点（图2中关键点2）所处的列表格线的同一列或左方。若一个单元格（图2中由关键点4、5、10、9围成的单元格）没有右相邻的单元格，则该单元格的左上角点（图2中关键点4）对应的右下角点（图2中关键点10）所处的列位于最后一条列表格线的同一列或左方；
[0146] 所述规则四，如图2，一个单元格（图2中由关键点1、2、12、11围成的单元格）的左上角点（图2中关键点1）对应的右下角点（图2中关键点12）所处的列表格线位于该单元格的左上角点（图2中关键点1）所处的列表格线的右方；
[0147] 所述规则五，如图2，一个单元格（图2中由关键点1、2、12、11围成的单元格）的左上角点（图2中关键点1）对应的右下角点（图2中关键点12）为符合规则三、四的点（图2中关键点6、12、18）中距离其最近的，即图2中的关键点12。
[0148] 具体地，重构出所有的单元格的步骤如下：
[0149] 把所有关键点构成的集合作为候选左上角点集合{1,2,…,22}，同时也把所有关键点构成的集合作为候选右下角点集合{1,2,…,22}；
[0150] 根据规则二，根据所有相邻关键点之间的连接关系，当相邻关键点不存在纵向连接关系时，则将位于上方的关键点从候选左上角点集合中去掉，同时也将位于下方的关键点从候选右下角点集合中去掉，当相邻关键点不存在横向连接关系时，则将位于左方的关键点从候选左上角点集合中去掉，同时也将位于右方的关键点从候选右下角点集合中去掉，最终得到正式的所有左上角点集合{1,2,3,4,6,9,11,12,13,14,15}和所有右下角点集合{8,10,12,14,15,16,18,19,20,21,22}；
[0151] 根据规则一，由于每个点只能是一个单元格的左上角点，也只能是一个单元格的右下角点，因此左上角点集合中的左上角点和右下角点集合中的右下角点是一一对应的，接下来只要为所有左上角点集合中的左上角点找到相对应的右下角点，即可重构出所有单元格；
[0152] 根据规则三，依次取出所有左上角点集合中的一个左上角点，这里取出左上角点3，找到与左上角点3位于同一行表格线上的多个左上角点{1,2,4}，这些左上角点中位于左上角点3右方且距离左上角点3最近的一个即为左上角点3所处的单元格的右相邻的单元格的左上角点，这里为左上角点4。接下来对所有右下角点的集合进行第一次筛选，去掉位于左上角点4所处的列表格线右方的右下角点，剩余的右下角点为{8,12,14,15,18,19,20,
21}。因左上角点3不位于表格中的最后一条列表格线上，这里需要第一次筛选；
[0153] 根据规则四，对所有右下角点的集合{8,12,14,15,18,19,20,21}进行第二次筛选，去掉其中所有不满足所处的列表格线位于左上角点3所处的列表格线的右方的右下角点，剩余的右下角点为{15, 21}；
[0154] 根据规则五，经过两次筛选后剩下的所有右下角点{15, 21}中找到距离左上角点3最近的一个，这里为右下角点15，可以看到左上角点3和右下角点15构成一个单元格；
[0155] 依次找到所有左上角点集合中的左上角点对应的右下角点，即可重构出所有的单元格。
[0156] 本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、或者计算机软件和电子硬件的结合来实现。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。
[0157] 以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。
[0158] 本领域技术人员应明白，本申请的实施例可提供为方法、系统或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD‑ROM、光学存储器等)上实施的计算机程序产品的形式。
[0159] 以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。
