第14卷第2期 智能系统学报 Vol.14 No.2 2019年3月 CAAI Transactions on Intelligent Systems Mar.2019 D0:10.11992/tis.201709038 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20180417.1720.010.html 基于图表示和匹配的表单定位与提取 谭婷1，吕淑静2，吕岳2 (1.华东师范大学上海多维度信息处理重点实验室，上海200062：2.中国邮政集团公司上海研究院图像分析 与智能系统联合实验室，上海200062) 摘要：为了实现对不同类型、分辨率和方向的快递表单上用户感兴趣区域信息的获取，本文提出了一种基于 图表示和匹配的表单定位与提取方法。选择参考表单中已有的印刷图案或字符等关键区域作为基准位置，进 行图的表示。基于图像分割得到的候选关键区域对待处理表单进行图表示。然后，根据图的属性计算待处理 表单与参考表单的相似度。最后，将最大相似度对应的同构图作为参考表单图的最优匹配，并建立同构图与参 考表单图位置映射，定位出表单。本文实验数据集来源于真实场景下采集的快递包裹表单图像。实验结果表 明：本文算法在快递包裹表单图像上具有良好的性能，对旋转、光照变化、局部遮挡具有较好的鲁棒性。 关键词：图像分割：表单提取：表单定位：图表示：图匹配：同构图：快递包裹分栋 中图分类号：TP751.1文献标志码：A文章编号：1673-4785(2019)02-0231-08 中文引用格式：谭婷，吕淑静，吕岳.基于图表示和匹配的表单定位与提取J.智能系统学报，2019,14(2)：231-238. 英文引用格式：TAN Ting,LYU Shujing,LYU Yue..Form location and extraction based on graph representation and matching Jl, CAAI transactions on intelligent systems,2019,14(2):231-238. Form location and extraction based on graph representation and matching TAN Ting',LYU Shujing,LYU Yue2 (1.Shanghai Key Laboratory of Multidimensional Information Processing,East China Normal University,Shanghai 200062,China; 2.ECNU-SRI Joint Lab for Pattern Analysis and Intelligent System,Shanghai Research Institute of China Post,Shanghai 200062. China) Abstract:To obtain information of a user's interested region on express package images of different types,resolutions, and directions,a form location and extraction method based on graph representation and matching is proposed in this pa- per.A reference form is needed in this method.First,key regions such as the existing printed patterns or characters in the reference form are chosen as nodes to build the reference graph.Second,graph representation is conducted on the form to be processed based on the candidate key region derived from image segmentation.Then,the similarity between the reference form and the candidate form is calculated according to attributes of the graph.Finally,the isomorphic graph with the maximum similarity is chosen as the optimal matching of the reference form and graph,and the position mapping of the isomorphic graph and the reference form and test image is established to locate the form.The experi- mental datasets in this paper originate from express package images collected in practical scenarios.Experimental res- ults indicate that the proposed algorithm has good performance on express form images.Especially,good robustness is achieved for rotated,illuminated,and partially shaded images. Keywords:image segmentation;form extraction;form location;graph representation;graph matching;isomorphic graph;express package sorting 表单作为重要的信息载体在实际生活和工作 符号等都有可能包含用户感兴趣的重要信息，如 中有着广泛的运用，表单中某些特定字段、图案、 订货单中的订单号、发票的具体项目及金额、快 收稿日期：2017-09-20.网络出版日期：2018-04-18. 递运单中的收货地址和手机号码等。人工录入的 通信作者：谭婷.E-mail:tanting_.hn@l63.com. 方式采集数据，费时费力，而且容易出错，因此利
DOI: 10.11992/tis.201709038 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20180417.1720.010.html 基于图表示和匹配的表单定位与提取 谭婷1，吕淑静2，吕岳1,2 （1. 华东师范大学 上海多维度信息处理重点实验室，上海 200062; 2. 中国邮政集团公司上海研究院 图像分析 与智能系统联合实验室，上海 200062） 摘 要：为了实现对不同类型、分辨率和方向的快递表单上用户感兴趣区域信息的获取，本文提出了一种基于 图表示和匹配的表单定位与提取方法。选择参考表单中已有的印刷图案或字符等关键区域作为基准位置，进 行图的表示。基于图像分割得到的候选关键区域对待处理表单进行图表示。然后，根据图的属性计算待处理 表单与参考表单的相似度。最后，将最大相似度对应的同构图作为参考表单图的最优匹配，并建立同构图与参 考表单图位置映射，定位出表单。本文实验数据集来源于真实场景下采集的快递包裹表单图像。实验结果表 明：本文算法在快递包裹表单图像上具有良好的性能，对旋转、光照变化、局部遮挡具有较好的鲁棒性。 关键词：图像分割；表单提取；表单定位；图表示；图匹配；同构图；快递包裹分拣 中图分类号：TP751.1 文献标志码：A 文章编号：1673−4785(2019)02−0231−08 中文引用格式：谭婷, 吕淑静, 吕岳. 基于图表示和匹配的表单定位与提取 [J]. 智能系统学报, 2019, 14(2): 231–238. 英文引用格式：TAN Ting, LYU Shujing, LYU Yue. Form location and extraction based on graph representation and matching[J]. CAAI transactions on intelligent systems, 2019, 14(2): 231–238. Form location and extraction based on graph representation and matching TAN Ting1 ，LYU Shujing2 ，LYU Yue1,2 (1. Shanghai Key Laboratory of Multidimensional Information Processing, East China Normal University, Shanghai 200062, China; 2. ECNU-SRI Joint Lab for Pattern Analysis and Intelligent System, Shanghai Research Institute of China Post, Shanghai 200062, China) Abstract: To obtain information of a user’s interested region on express package images of different types, resolutions, and directions, a form location and extraction method based on graph representation and matching is proposed in this paper. A reference form is needed in this method. First, key regions such as the existing printed patterns or characters in the reference form are chosen as nodes to build the reference graph. Second, graph representation is conducted on the form to be processed based on the candidate key region derived from image segmentation. Then, the similarity between the reference form and the candidate form is calculated according to attributes of the graph. Finally, the isomorphic graph with the maximum similarity is chosen as the optimal matching of the reference form and graph, and the position mapping of the isomorphic graph and the reference form and test image is established to locate the form. The experimental datasets in this paper originate from express package images collected in practical scenarios. Experimental results indicate that the proposed algorithm has good performance on express form images. Especially, good robustness is achieved for rotated, illuminated, and partially shaded images. Keywords: image segmentation; form extraction; form location; graph representation; graph matching; isomorphic graph; express package sorting 表单作为重要的信息载体在实际生活和工作 中有着广泛的运用，表单中某些特定字段、图案、 符号等都有可能包含用户感兴趣的重要信息，如 订货单中的订单号、发票的具体项目及金额、快 递运单中的收货地址和手机号码等。人工录入的 方式采集数据，费时费力，而且容易出错，因此利 收稿日期：2017−09−20. 网络出版日期：2018−04−18. 通信作者：谭婷. E-mail：tanting_hn@163.com. 第 14 卷第 2 期 智 能 系 统 学 报 Vol.14 No.2 2019 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2019
·232· 智能系统学报 第14卷 用计算机对表单图像进行自动化信息提取有着强 图匹配的方法对定位的正确性进行验证。 烈的应用需求，可以大幅度降低工作量，提升工 作效率。 1表单图表示 表单自动化处理的主要过程包括表单图像采 11参考表单的图表示 集、表单定位、信息区域提取、识别等。其中表 11.1参考表单关键区域的选取 单定位和提取是表单识别前重要的预处理过程， 本文在建立参考表单图表示时，由用户手动 预先获取表单关键信息区域有利于更方便、准确 选择能反映表单特征的关键区域，比如具有可区 地识别表单填写的内容信息。本文方法主要工作 分特征的表单公司标志、特定图案、字符块等。 是对物流快递表单中与用户信息相关的文本区域 由于表单图像上字符较多，背景较为复杂，后续 进行定位和提取，如快递表单上收/寄件人姓名、 图匹配过程需要足够多的关键区域实现配准，同 电话号码、地址等信息。该处理过程得到文本图 时匹配计算量适度，建议选取5~8个图案完整、 像块可用于后续识别工作的输入数据，建立字符 清晰、大小适中的图像块作为关键区域，图1给 图像数据库，图像特征学习的训练样本，具有广 出一个从邮政快递包裹面单上选取关键区域的 阔的应用前景。 例子。 表单提取过程中常见的方法是检测表单中的 直线，将其作为表单提取的参考位置。基于直 阳内小包件领年 香职 线的检测法所处理的对象更倾向于类似于表格类 结构化的表单，但对缺乏框线和非固定形式的非 结构化表单的处理存在明显的不足。 另一类表单定位与提取的方法是采用对表单 的布局或表单元素进行描述的方法，如建立搜索 分类树或设定提取信息的关联指令。这种对 图1参考表单关键区域选取样例 表单的布局或表单元素进行描述的方法缺乏灵活性。 Fig.1 An example for key area selection of reference form 表单图像具有特定的布局方式，因此采用参 1.1.2关键区域的图表示 考模板来提取表单也是一种重要的研究方法，如 以关键区域为图结点，建立如图2(a)所示参 使用空白表单模板与待匹配表单基准点对齐6刀 或使用傅里叶-梅林变换重定向表单1的方向。 考表单的全连接无向图表示。将该无向图定义为 Cesarini9提出通过属性图结点的具体数值和图 q=(VE:o,p,其中V为图结点，对应表单的关键 的模型特征实现刚性配准，建立待处理图和参考 区域。E为图的边，对应结点间的相互连接关 图的对应。 系。0表示每个结点v的结点属性，p表示每个 以往的模板匹配方法依赖于对基准点的严格 结点v在图q中的结构属性。图2(b)为图2(a) 要求和预先约定，而基于非层次有向关系属性图例 中结点，的结构属性表示。 方法在寻找对应区域位置时，难以避免预先识别 关键字。本文将模板匹配和图匹配的方法相结 合，提出一种基于图表示和匹配的表单定位与提 取方法。 图匹配方法在计算机视觉领域有着广泛的应 用，如特征点对应0川、形状匹配2)、目标检测和 (a)参考表单图表示 (b),的结构属性 识别1、视频分析6，图像的视觉特征在图匹配 图2参考表单图样例 过程中考虑两图之间最小结构失真以实现对应。 Fig.2 An example for graph of reference form 本文方法在处理多个类别的表单图像时，需 1)结点属性o。SIFT对图像局部特征的描述 要预先选取对应类别表单图像中已有的图案区域 具有良好旋转和尺度不变性，对光照有较强的鲁 设计匹配待处理表单的参考表单模板图，该过程 棒性。采用SIFT来描述图的结点属性表示为 避免了对字符的识别，简化了分类提取的过程。 0=fa,f2,…,fm}m=1,2,…,M(1) 另外，图匹配方法适用于混杂场景下目标检测和 式中：f为128维的SIFT特征向量，表示v,中第 异常点判别，结合这一优势，在定位表单时采用 j个特征点；M为正整数，表示结点y,的特征维度
用计算机对表单图像进行自动化信息提取有着强 烈的应用需求，可以大幅度降低工作量，提升工 作效率。 表单自动化处理的主要过程包括表单图像采 集、表单定位、信息区域提取、识别等[1]。其中表 单定位和提取是表单识别前重要的预处理过程， 预先获取表单关键信息区域有利于更方便、准确 地识别表单填写的内容信息。本文方法主要工作 是对物流快递表单中与用户信息相关的文本区域 进行定位和提取，如快递表单上收/寄件人姓名、 电话号码、地址等信息。该处理过程得到文本图 像块可用于后续识别工作的输入数据，建立字符 图像数据库，图像特征学习的训练样本，具有广 阔的应用前景。 表单提取过程中常见的方法是检测表单中的 直线，将其作为表单提取的参考位置[2-3]。基于直 线的检测法所处理的对象更倾向于类似于表格类 结构化的表单，但对缺乏框线和非固定形式的非 结构化表单的处理存在明显的不足。 另一类表单定位与提取的方法是采用对表单 的布局或表单元素进行描述的方法，如建立搜索 分类树[4] 或设定提取信息的关联指令[5]。这种对 表单的布局或表单元素进行描述的方法缺乏灵活性。 表单图像具有特定的布局方式，因此采用参 考模板来提取表单也是一种重要的研究方法，如 使用空白表单模板与待匹配表单基准点对齐[6-7] 或使用傅里叶−梅林变换重定向表单[8] 的方向。 Cesarini [9] 提出通过属性图结点的具体数值和图 的模型特征实现刚性配准，建立待处理图和参考 图的对应。 以往的模板匹配方法依赖于对基准点的严格 要求和预先约定，而基于非层次有向关系属性图[9] 方法在寻找对应区域位置时，难以避免预先识别 关键字。本文将模板匹配和图匹配的方法相结 合，提出一种基于图表示和匹配的表单定位与提 取方法。 图匹配方法在计算机视觉领域有着广泛的应 用，如特征点对应[10-11] 、形状匹配[12] 、目标检测和 识别[13-15] 、视频分析[16] ，图像的视觉特征在图匹配 过程中考虑两图之间最小结构失真以实现对应。 本文方法在处理多个类别的表单图像时，需 要预先选取对应类别表单图像中已有的图案区域 设计匹配待处理表单的参考表单模板图，该过程 避免了对字符的识别，简化了分类提取的过程。 另外，图匹配方法适用于混杂场景下目标检测和 异常点判别，结合这一优势，在定位表单时采用 图匹配的方法对定位的正确性进行验证。 1 表单图表示 1.1 参考表单的图表示 1.1.1 参考表单关键区域的选取 本文在建立参考表单图表示时，由用户手动 选择能反映表单特征的关键区域，比如具有可区 分特征的表单公司标志、特定图案、字符块等。 由于表单图像上字符较多，背景较为复杂，后续 图匹配过程需要足够多的关键区域实现配准，同 时匹配计算量适度，建议选取 5~8 个图案完整、 清晰、大小适中的图像块作为关键区域，图 1 给 出一个从邮政快递包裹面单上选取关键区域的 例子。 1.1.2 关键区域的图表示 q = (V,E;o,φ) 以关键区域为图结点，建立如图 2(a) 所示参 考表单的全连接无向图表示。将该无向图定义为 ，其中 V 为图结点，对应表单的关键 区域。E 为图的边，对应结点间的相互连接关 系。ω 表示每个结点 v 的结点属性，φ 表示每个 结点 v 在图 q 中的结构属性。图 2(b) 为图 2(a) 中结点 v7 的结构属性表示。 1) 结点属性 o。SIFT 对图像局部特征的描述 具有良好旋转和尺度不变性，对光照有较强的鲁 棒性。采用 SIFT 来描述图的结点属性表示为 oi = {fi1, fi2,··· , fim} m = 1,2,··· , M (1) 式中：fij 为 128 维的 SIFT 特征向量，表示 vi 中第 j 个特征点；M 为正整数，表示结点 vi 的特征维度。 图 1 参考表单关键区域选取样例 Fig. 1 An example for key area selection of reference form (a) 参考表单图表示 (b) v7 的结构属性 v1 v2 v4 v5 v6 v8 v3 θ58 e78 v7 v1 v2 v4 v5 v6 v7 v8 v3 图 2 参考表单图样例 Fig. 2 An example for graph of reference form ·232· 智 能 系 统 学 报 第 14 卷
第2期 谭婷，等：基于图表示和匹配的表单定位与提取 ·233· 2)结构属性p。p表示结点y,结构属性，它包 考表单图全连接不同的是，对应同一关键区域的 括两个子属性：结点权重属性ω和夹角属性0，结 3个候选关键区域间不连接。随后，对图G中标 点y,的结构属性表示为g={w,}。 签互异的候选子图g进行结点和结构属性描述。 权重属性仙。该属性表示以结点y,为固定端 点，y,与其所有邻接点y连接边e的长度的向量 集合。该属性表示如下： d={e1,e2,…,el}i,j=1,2,…,N,i≠j(2) 如v,射线簇属性为{e71,e72,e3,e74,e5,e6 夹角属性0：。a(ee)表示图中以结点v:为 (a2)(a;)(a 顶点，eg和e分别为与邻接点y和连接边缘所 (a)参考表单图q (b)待处理表单图G 组成的夹角，结点"：所具有的夹角属性表示为以 ⊙ C y为顶点的夹角向量集合0，表示如下： 0={a(ee)}i,j,k=1,2,…,N,i≠j≠k(3) 根据上述描述，q=(W,E:o,p)即为参考表单关 a a 键区域的图表示。 (c)候选同构图g 1.2待处理表单的图表示 图4候选同构图 1.2.1待处理表单候选关键区域的选取 Fig.4 Candidate isomorphic graph 本文采用选择性搜索方法叨将待处理表单分 2表单图匹配 割得到许多图像小块，这些图像块中包含与参考 表单关键区域对应的区域或部分的区域。如图3 由于图像分割策略局限性，分割的候选关键 所示，该算法使得灰度相似且位置相近的像素合 区域可能出现欠分割和过分割的问题。另外，对 并，然后根据图像块的大小、灰度梯度实现图像 应于关键区域的位置出现局部遮挡，容易得到错 块粗略过滤，选择图案、字符相对较集中的区域 误的候选关键区域。为此，通过对参考表单与待 作为待处理表单图像的候选关键区域。 处理表单进行图匹配，验证和确认关键区域是否 对应准确。 2.1候选同构图 给定G=(V,E)和G=(W,E)是两个图，假设 存在双射s:V→V,使得对所有x,y∈V均有 xy∈E等价于s(x)s0y)∈E1,则称G和G,是同构 sO物国d男S0 的。假设参考表单图表示为q=(V,E9;o,p),待 选择性搜索分割过滤 候选关键区域 处理表单图表示为G=(V,Ec:o,),图g与图 图3待处理表单候选关键区域选取样例 q中对应的候选结点赋予与q中相同的标签，如 Fig.3 An example for candidate key area selection of 图4(a)中的{a}对应于图4(b)中的{a1,a2,a}。图 test form G中结点标签互异的图g与图9，恰好满足s这一 1.2.2候选结点筛选 映射关系，故称图g为图q的同构图。因此，图像 为提高匹配参考表单图的效率，比较候选关 匹配过程为从图G中寻找一个与图q最相似的同 键区域与关键区域的结点属性o相似度，筛选出 构图g,或寻找与子图qs最相似的同构子图gs, 相似度最高的前3个图像块作为图匹配的候选结 是一个图匹配的问题。通过度量同构图g与图 q的相似性，找到相似差异最小的同构图gm或同 点，建立关键区域与候选关键区域的对应关系， 构子图g5m,作为与图q最佳匹配图。如图4所 去除大量相似度过小的候选关键区域，降低匹配 示，按照同构映射s的定义，在图4(b)所示图 复杂度。 G中，图4(a)所示图q:{a,b,c,d对应的候选同构图 1.2.3候选关键区域图表示 有g1:{a1,b1,C1,d1},82:{a1,b1,a,d2},864:{a3,b3 对候选结点参照参考表单图建立的过程，建 c3,d}。图匹配目的即为在图4(b)所示的图G中 立如图4b)所示待处理表单的全连接图G。与参 找到最佳匹配的候选同构图gm:{a2,b1,C2,d2}。s表
φ φ ω θ φi = {ωi ,θi} 2) 结构属性 。 表示结点 vi 结构属性，它包 括两个子属性：结点权重属性 和夹角属性 ，结 点 vi 的结构属性表示为 。 权重属性 ωi。该属性表示以结点 vi 为固定端 点，vi 与其所有邻接点 vj 连接边 eij 的长度的向量 集合。该属性表示如下： ωi = { ei1, ei2,··· , ei j} i, j = 1,2,··· ,N,i , j (2) 如 v7 射线簇属性为{e71, e72, e73, e74, e75, e76, e78}。 θi α ( ei j, eik) θi 夹角属性 。 表示图中以结点 vi 为 顶点，eij 和 eik 分别为与邻接点 vj 和 vk 连接边缘所 组成的夹角，结点 vi 所具有的夹角属性表示为以 vi 为顶点的夹角向量集合 ，表示如下： θi = { α ( ei j, eik)} i, j, k = 1,2,··· ,N,i , j , k (3) 根据上述描述， q = (V,E;o,φ) 即为参考表单关 键区域的图表示。 1.2 待处理表单的图表示 1.2.1 待处理表单候选关键区域的选取 本文采用选择性搜索方法[17] 将待处理表单分 割得到许多图像小块，这些图像块中包含与参考 表单关键区域对应的区域或部分的区域。如图 3 所示，该算法使得灰度相似且位置相近的像素合 并，然后根据图像块的大小、灰度梯度实现图像 块粗略过滤，选择图案、字符相对较集中的区域 作为待处理表单图像的候选关键区域。 1.2.2 候选结点筛选 为提高匹配参考表单图的效率，比较候选关 键区域与关键区域的结点属性 ω 相似度，筛选出 相似度最高的前 3 个图像块作为图匹配的候选结 点，建立关键区域与候选关键区域的对应关系， 去除大量相似度过小的候选关键区域，降低匹配 复杂度。 1.2.3 候选关键区域图表示 对候选结点参照参考表单图建立的过程，建 立如图 4(b) 所示待处理表单的全连接图 G。与参 考表单图全连接不同的是，对应同一关键区域的 3 个候选关键区域间不连接。随后，对图 G 中标 签互异的候选子图 g 进行结点和结构属性描述。 2 表单图匹配 由于图像分割策略局限性，分割的候选关键 区域可能出现欠分割和过分割的问题。另外，对 应于关键区域的位置出现局部遮挡，容易得到错 误的候选关键区域。为此，通过对参考表单与待 处理表单进行图匹配，验证和确认关键区域是否 对应准确。 2.1 候选同构图 ς : V → V1 ς(x)ς(y) ∈ E1 q = (V q ,E q ;o q ,φq ) G = (V G ,E G ;o G ,φG ) ς ς ς 给定 G=(V，E) 和 G1=(V1，E1 ) 是两个图，假设 存在双射 使得对所 有 x , y ∈ V 均 有 xy∈E 等价于 ，则称 G 和 G1 是同构 的。假设参考表单图表示为 ，待 处理表单图表示为 ，图 g 与图 q 中对应的候选结点赋予与 q 中相同的标签，如 图 4(a) 中的{a}对应于图 4(b) 中的{a1 ,a2 ,a3}。图 G 中结点标签互异的图 g 与图 q，恰好满足 这一 映射关系，故称图 g 为图 q 的同构图。因此，图像 匹配过程为从图 G 中寻找一个与图 q 最相似的同 构图 g，或寻找与子图 qs 最相似的同构子图 gs， 是一个图匹配的问题。通过度量同构图 g 与图 q 的相似性，找到相似差异最小的同构图 gm 或同 构子图 gsm，作为与图 q 最佳匹配图。如图 4 所 示，按照同构映射 的定义，在 图 4(b) 所 示 图 G 中，图 4(a) 所示图 q:{a,b,c,d}对应的候选同构图 有 g1 :{a1 ,b1 ,c1 ,d1}, g2 :{a1 , b1 , a, d2 },···,g64: {a3 ,b3 , c3 ,d3}。图匹配目的即为在图 4(b) 所示的图 G 中 找到最佳匹配的候选同构图 gm:{a2 ,b1 ,c2 ,d2}。 表 选择性搜索分割 过滤 候选关键区域 图 3 待处理表单候选关键区域选取样例 Fig. 3 An example for candidate key area selection of test form (a) 参考表单图 q (b) 待处理表单图 G c1 c3 b3 b1 b2 a2 a3 a1 d2 d3 d1 c2 a c d b (c) 候选同构图 g b1 a2 c2 d2 c1 b1 a1 d2 c1 b1 a1 d1 c3 b3 a2 d3 … … g1 g2 gm g64 图 4 候选同构图 Fig. 4 Candidate isomorphic graph 第 2 期 谭婷，等：基于图表示和匹配的表单定位与提取 ·233·
·234· 智能系统学报 第14卷 示筛选与对应关键区域最相似的前3个候选关键 较高的纹理相似度会对图的相似度有一定程度的 区域，这些候选区域中，可能包含了纹理相似，但 干扰；同样的，当夹角、射线簇边缘相似度过高 在表单上位置不同的图案区域，从而导致候选图 同样会影响该结点的整体相似度的评判。故需对 中对应的结点出现较大幅度的位置偏差，如图 当前匹配的g中的结点剪枝，对结点v,中d() 4b)中b2和d2。因此，需要进一步度量图结构的 d()、d()设置一定的阈值，不符合条件的，设值 相似度，寻找图G中与参考表单图q最相似的同 为离群点，同时将离群点纳入相似度量的整体评 构图，如g,或去除误匹配结点的最相似的同构 价中，即对g和g的子图进行匹配，寻找一个与 子图，如果d2为误匹配结点，则目标匹配为同构 q最相似的同构子图gsm。该离群点相似度度量 子图gSm:{a2,b1,c2}o 如下： 2.2距离度量 离群点相似度，用经剪枝过后的离群点数量 将表单进行图表示和属性定义，然后通过度 (outlier Number,ON)表示： 量G中同构图g和q间的属性差异，衡量两图间 的距离，距离越小则表示子图g和g的结构越相 dum=ON (9) Na 似，根据属性的差异，确定最相似的同构图gm 式中：d小m∈0,1]，W表示图g中结点V的数量，图 或同构子图gSm。可以从以下几个方面度量图的 g和图q的相似距离表示为 差异。 3 1)结点相似度 NN>cd(i)+do(+d(dm(10) d(q.8)= 对g和g中结点V和V的SIFT特征点采取最 式中：c,∈{0,1}，0表示离群点，1表示符合阈值 近邻匹配进而得到匹配特征点对的F-Score值 要求的结点，d(q,g)值越小则两图的相似度越大； F(o,o),则图结点间的相似距离定义为 故在G中，将与g相似距离最小的gm或gsm作为 d(i)=1-F1(o,o) (4) G与g的最终匹配结果： 式中：o、o分别为g和q结点的纹理，d()∈[0,1。 D(q,G)=argmind(q.g) (11) 2)结构相似度 通过图相似性度量，得到与参考表单图最佳 夹角相似度。图中和v,的夹角相似度用其 匹配的同构图gm或同构子图gSm,图5给出了一 向量余弦相似度来表示： 个待处理热敏表单最佳匹配结果。 d()=1-cos(0,0) (5) 参考表单 待处理表单 式中d(①∈[0,1。 权重相似距离，即以连接结点和，所有边缘 长度比，作为g和g中结点和v权重相似距离；如 果两个图结点处于完全对应的位置，则该结点相 连接的对应边具有相同的相似比，这里将两图中 新中国的 对应边的长度比设为X={x,2,…,x},其中 x=le/le卧，表示边e的长度，i表示当前结点标 图5热敏表单图匹配结果 号，j表示i的邻接点，n表示与结点i连接的结点 Fig.5 Graph matching result for free form 数量。通过X的离散程度来计算图中对应结点 23待处理表单定位 所有连接边缘的整体相似距离： 如图5所示，参考表单与待处理表单的关键 sim(of.)=exp (6) 区域仅实现了部分对应，且匹配出的图像块不完 式中：EX、DX分别为变量X的均值和方差。则 整或轮廓不吻合，这是由于图像分割算法对复杂 该图的权重相似距离为 的字符图案分割不准确所致，这将直接导致表单 d(i)=1-sim(wf,w) (7) 式中d()∈0,1o 提取的位置不准确。因此，本文在提取后处理过 同构图g和图q对应结点的相似度定义为 程中对匹配关键区域的位置进行修正，即迭代建 D(q(),g(0)=d()+d(0+d() (8) 立参考表单与待处理表单的位置映射函数，以此 在进行参考表单q与g的图匹配时，考虑到 提高表单提取的准确性。通过映射函数，实现待 g与q对应结点缺失或选择错误的情况，若g与 处理表单上任意感兴趣区域的定位，从而完成表 q对应结点纹理极为相似，但实际位置并不匹配， 单信息的提取
示筛选与对应关键区域最相似的前 3 个候选关键 区域，这些候选区域中，可能包含了纹理相似，但 在表单上位置不同的图案区域，从而导致候选图 中对应的结点出现较大幅度的位置偏差，如图 4(b) 中 b2 和 d2。因此，需要进一步度量图结构的 相似度，寻找图 G 中与参考表单图 q 最相似的同 构图，如 gm，或去除误匹配结点的最相似的同构 子图，如果 d2 为误匹配结点，则目标匹配为同构 子图 gsm:{a2 ,b1 ,c2}。 2.2 距离度量 将表单进行图表示和属性定义，然后通过度 量 G 中同构图 g 和 q 间的属性差异，衡量两图间 的距离，距离越小则表示子图 g 和 q 的结构越相 似，根据属性的差异，确定最相似的同构图 g m 或同构子图 gsm。可以从以下几个方面度量图的 差异。 1) 结点相似度 V g V F1(o g i , oi) 对 g 和 q 中结点 和 的 SIFT 特征点采取最 近邻匹配进而得到匹配特征点对的 F-Score 值 ，则图结点间的相似距离定义为 do(i) = 1− F1(o g i , oi) (4) o g i 式中： 、oi分别为 g 和 q 结点的纹理， do(i) ∈ [0,1]。 2) 结构相似度 v g i 夹角相似度。图中 和 vi的夹角相似度用其 向量余弦相似度来表示： dθ(i) = 1−cos( θ g i ,θi ) (5) 式中 dθ(i) ∈ [0,1]。 v g i vi g q v g i vi X = {x1, x2,··· , xn} xi = |e q i j|/|e g i j| | · | ei j 权重相似距离，即以连接结点 和 所有边缘 长度比，作为 和 中结点 和 权重相似距离；如 果两个图结点处于完全对应的位置，则该结点相 连接的对应边具有相同的相似比，这里将两图中 对应边的长度比设为 ，其中 ， 表示边 的长度，i 表示当前结点标 号，j 表示 i 的邻接点，n 表示与结点 i 连接的结点 数量。通过 X 的离散程度来计算图中对应结点 所有连接边缘的整体相似距离： sim( ω g i ,ω q i ) =exp− DX EX2 (6) 式中：EX、DX 分别为变量 X 的均值和方差。则 该图的权重相似距离为 dω(i) = 1−sim( ω g i ,ω q i ) (7) 式中 dω(i) ∈ [0,1]。 同构图 g 和图 q 对应结点的相似度定义为 D(q(i),g(i)) = do(i)+dθ(i)+dω(i) (8) 在进行参考表单 q 与 g 的图匹配时，考虑到 g 与 q 对应结点缺失或选择错误的情况，若 g 与 q 对应结点纹理极为相似，但实际位置并不匹配， do(i) dθ(i) dω(i) 较高的纹理相似度会对图的相似度有一定程度的 干扰；同样的，当夹角、射线簇边缘相似度过高， 同样会影响该结点的整体相似度的评判。故需对 当前匹配的 g 中的结点剪枝，对结点 vi 中 、 、 设置一定的阈值，不符合条件的 vi 设值 为离群点，同时将离群点纳入相似度量的整体评 价中，即对 g 和 q 的子图进行匹配，寻找一个与 q 最相似的同构子图 gsm。该离群点相似度度量 如下： 离群点相似度，用经剪枝过后的离群点数量 (outlier Number，ON) 表示： dNum = ON Nq (9) dNum ∈ [0,1] N q 式中： ， 表示图 q 中结点 V 的数量，图 g 和图 q 的相似距离表示为 d(q,g) = 3 Nq −ON ∑N i ci[do(i)+dθ(i)+dω(i)]+dNum (10) d(q,g) 式中：ci∈{0，1}，0 表示离群点，1 表示符合阈值 要求的结点， 值越小则两图的相似度越大； 故在 G 中，将与 q 相似距离最小的 gm 或 gsm 作为 G 与 q 的最终匹配结果： D(q,G) = argmind(q,g) (11) 通过图相似性度量，得到与参考表单图最佳 匹配的同构图 gm 或同构子图 gsm，图 5 给出了一 个待处理热敏表单最佳匹配结果。 2.3 待处理表单定位 如图 5 所示，参考表单与待处理表单的关键 区域仅实现了部分对应，且匹配出的图像块不完 整或轮廓不吻合，这是由于图像分割算法对复杂 的字符图案分割不准确所致，这将直接导致表单 提取的位置不准确。因此，本文在提取后处理过 程中对匹配关键区域的位置进行修正，即迭代建 立参考表单与待处理表单的位置映射函数，以此 提高表单提取的准确性。通过映射函数，实现待 处理表单上任意感兴趣区域的定位，从而完成表 单信息的提取。 参考表单 待处理表单 图 5 热敏表单图匹配结果 Fig. 5 Graph matching result for free form ·234· 智 能 系 统 学 报 第 14 卷
第2期 谭婷，等：基于图表示和匹配的表单定位与提取 ·235· 3 实验及分析 MAP=num(AO≥T) 1 (13) 3.1数据集 式中：num(AO≥刀表示阈值为T时准确定位的图 对快递包裹分拣机中采集的两类快递表单图 像数量，I为测试图像的数量。 像，建立多联表单(table like form,TF)和热敏表 此外，采用标注工具Lablelmg标记待处理表 单(free form,FF)两类实验数据集，TF和FF共计 单中提取区域真值，计算真值与检测目标交叠率 1477幅灰度快递表单图像。这些表单图像的分 (intersection-over-union,IOU,准确表示为 辨率偏转角度不同，且未进行归一化处理。其中 DetectionResultnGroundTruth IOU= (14) T℉为表格类图像，该类表单由制表单位统一印 DetectionResult UGroundTruth 刷，表单内容依据表格线布局，包括中国邮政国 其中，IOU DetectionResult和GroundTruth表示信 内快递小包邮件详情单(C-XB)和EMS国内标准 息提取区域检测位置和工具标注区域真值位置。 快递(EMS-MULT),这些图像的字符和图案较为 3.3实验结果及分析 清晰，其中有部分图像具有褶皱、模糊、扭曲或缺 通过实验对TF、FF数据集分别计算了阈值 损、遮挡或字迹重叠等问题。FF数据集为非表格 T为0.5、0.6、0.7、0.8、0.9时图像的平均准确率和 类表单图像，该类表单常见于物流集散点、商家 图像的平均重叠率(mean average overlap,MAO)。 网点自行打印，包括EMS标准快递(EMS-FLAT) 当T=0.8时，表示验证过程中参考表单和待处理 和韵达快递表单(YUNDA),除存在上述TF数据 表单中关键区域相互映射的重叠区域高于80%， 集中特点以外，该数据集中表单印刷墨迹清晰度 实验表明：此时用于定位的映射关系相对准确， 不一。另外，为验证算法在光照、尺度、旋转变换 能实现大部分图像的准确定位和提取。因此本文 等情况下具有良好的鲁棒性，本实验将TF、F℉数 实验将该阈值对应的MAP作为算法准确定位的置信度。 据集记为o-i,对o-i进行了旋转、缩放、亮度调节 表1是TF、FF数据集的平均准确率和重叠 等扩展数据集。旋转扩展是对0-i分别旋转45°、 率的实验统计情况，其中MAO反映了样本中通 90°、135°、180°，新增r-1、r-2、r-3、r-4扩展数据 过映射关键区域的整体重合情况。数据显示： 集。缩放扩展是对0-i缩扩放至原表单图像的 TF、FF中原图像数据集和扩展数据集的MAO主 75%、50%、125%、150%,新增s-1、s-2、e-1、e-2扩 要分别在90%以上和80%以上，说明根据图匹配 展数据集。亮度调节扩展是对o-i的亮度提高至 建立的关键区域映射关系，能较好的实现待处理 原来的125%、150%和降低至原来的75%、50%， 表单与参考表单上关键区域的位置对应，因此可 新增b-1、b-2、d-1、d-2扩展数据集。经过数据集 以通过这种映射进行表单的提取。TF、FF数据集 扩充，本文实验的表单图像共计19201幅。 的MAP大部分在87%98%和75%~86%，这表明 3.2评价标准 本文算法对多联表单和热敏表单具有良好的定 本文通过表单图匹配的置信度和表单相关信 位准确率。图6中，当T=0.9时，FF数据集的 息的提取结果准确率来分析算法的性能。 MAP相对TF数据集低约20%~30%，波动幅度较 首先，采用表单图匹配的置信度来衡量根据 大，原因有以下两点：1)T℉数据集中，关键区域均 图匹配所建立的参考表单图像与待处理图像的映射 为表单出厂印制图案和字符，同类表单的差异较 是否可靠，该置信度由重叠率(average overlap,AO) 小，FF数据集表单印制要求不统一，故而差异较 和平均准确率(mean average precision,.MAP)来评 大；2)FF数据集为非表格类表单，其内容的自由 定。如果映射的置信度高，那么表单信息提取的 度较大，选取关键区域的难度较大，可参照的关 准确性也会提高。重叠率定义为映射过程中关键 键区域少，因此建立表单映射时严格匹配的特征 区域重合度比例的均值： 点对较少，因此对阈值高的AO的MAP值相对较 1 AO= 低。图6，T℉中原图像数据集在进行旋转、亮度 overlap(vgt) (12) n 调节变换后，平均准确率的变化趋于重合，F℉数 式中：n,为关键区域的数量，vg为参考表单关键 据集的平均准确率仅有小幅度范围内的波动。因 区域的位置，为待处理表单图像上关键区域的 此，该表单提取算法对旋转和亮度变化的图像具 定位结果，overlap()表示区域的重叠率。 有良好的稳定性。另外，图6中图像缩至75%，T= MAP是当重叠率AO高于某一阈值T时，则 0.8时，TF、FF数据集的分别为79.83%、70.11%， 待处理表单的匹配位置为准确位置，故MAP表 与原图像数据集o-i相比MAP分别下降了48.89%、 示为 19.54%,T℉数据集s-2与原图数据集o-i和其他
3 实验及分析 3.1 数据集 对快递包裹分拣机中采集的两类快递表单图 像，建立多联表单 (table like form，TF) 和热敏表 单 (free form，FF) 两类实验数据集，TF 和 FF 共计 1 477 幅灰度快递表单图像。这些表单图像的分 辨率偏转角度不同，且未进行归一化处理。其中 TF 为表格类图像，该类表单由制表单位统一印 刷，表单内容依据表格线布局，包括中国邮政国 内快递小包邮件详情单 (C-XB) 和 EMS 国内标准 快递 (EMS-MULT)，这些图像的字符和图案较为 清晰，其中有部分图像具有褶皱、模糊、扭曲或缺 损、遮挡或字迹重叠等问题。FF 数据集为非表格 类表单图像，该类表单常见于物流集散点、商家 网点自行打印，包括 EMS 标准快递 (EMS-FLAT) 和韵达快递表单 (YUNDA)，除存在上述 TF 数据 集中特点以外，该数据集中表单印刷墨迹清晰度 不一。另外，为验证算法在光照、尺度、旋转变换 等情况下具有良好的鲁棒性，本实验将 TF、FF 数 据集记为 o-i，对 o-i 进行了旋转、缩放、亮度调节 等扩展数据集。旋转扩展是对 o-i 分别旋转 45°、 90°、135°、180°，新增 r-1、r-2、r-3、r-4 扩展数据 集。缩放扩展是对 o-i 缩扩放至原表单图像的 75%、50%、125%、150%，新增 s-1、s-2、e-1、e-2 扩 展数据集。亮度调节扩展是对 o-i 的亮度提高至 原来的 125%、150% 和降低至原来的 75%、50%， 新增 b-1、b-2、d-1、d-2 扩展数据集。经过数据集 扩充，本文实验的表单图像共计19 201 幅。 3.2 评价标准 本文通过表单图匹配的置信度和表单相关信 息的提取结果准确率来分析算法的性能。 首先，采用表单图匹配的置信度来衡量根据 图匹配所建立的参考表单图像与待处理图像的映射 是否可靠，该置信度由重叠率 (average overlap，AO) 和平均准确率 (mean average precision，MAP) 来评 定。如果映射的置信度高，那么表单信息提取的 准确性也会提高。重叠率定义为映射过程中关键 区域重合度比例的均值： AO= 1 nl ∑nl i=1 overlap(vgtq i , v q i ) (12) vgtq i v q i overlap(·) 式中：nl 为关键区域的数量， 为参考表单关键 区域的位置， 为待处理表单图像上关键区域的 定位结果， 表示区域的重叠率。 MAP 是当重叠率 AO 高于某一阈值 T 时，则 待处理表单的匹配位置为准确位置，故 MAP 表 示为 MAP = num(AO ⩾ T) I (13) 式中：num(AO ⩾ T) 表示阈值为 T 时准确定位的图 像数量，I 为测试图像的数量。 此外，采用标注工具 LableImg 标记待处理表 单中提取区域真值，计算真值与检测目标交叠率 (intersection-over-union，IOU)，准确表示为 IOU = DetectionResult∩GroundTruth DetectionResult∪GroundTruth (14) 其中，IOU DetectionResult 和 GroundTruth 表示信 息提取区域检测位置和工具标注区域真值位置。 3.3 实验结果及分析 通过实验对 TF、FF 数据集分别计算了阈值 T 为 0.5、0.6、0.7、0.8、0.9 时图像的平均准确率和 图像的平均重叠率 (mean average overlap，MAO)。 当 T=0.8 时，表示验证过程中参考表单和待处理 表单中关键区域相互映射的重叠区域高于 80%， 实验表明：此时用于定位的映射关系相对准确， 能实现大部分图像的准确定位和提取。因此本文 实验将该阈值对应的MAP作为算法准确定位的置信度。 表 1 是 TF、FF 数据集的平均准确率和重叠 率的实验统计情况，其中 MAO 反映了样本中通 过映射关键区域的整体重合情况。数据显示： TF、FF 中原图像数据集和扩展数据集的 MAO 主 要分别在 90% 以上和 80% 以上，说明根据图匹配 建立的关键区域映射关系，能较好的实现待处理 表单与参考表单上关键区域的位置对应，因此可 以通过这种映射进行表单的提取。TF、FF 数据集 的 MAP 大部分在 87%~98% 和 75%~86%，这表明 本文算法对多联表单和热敏表单具有良好的定 位准确率。图 6 中 ，当 T=0.9 时 ， FF 数据集的 MAP 相对 TF 数据集低约 20%~30%，波动幅度较 大，原因有以下两点：1)TF 数据集中，关键区域均 为表单出厂印制图案和字符，同类表单的差异较 小，FF 数据集表单印制要求不统一，故而差异较 大；2)FF 数据集为非表格类表单，其内容的自由 度较大，选取关键区域的难度较大，可参照的关 键区域少，因此建立表单映射时严格匹配的特征 点对较少，因此对阈值高的 AO 的 MAP 值相对较 低。图 6，TF 中原图像数据集在进行旋转、亮度 调节变换后，平均准确率的变化趋于重合， FF 数 据集的平均准确率仅有小幅度范围内的波动。因 此，该表单提取算法对旋转和亮度变化的图像具 有良好的稳定性。另外，图 6 中图像缩至 75%，T= 0.8 时，TF、FF 数据集的分别为 79.83%、70.11%， 与原图像数据集 o-i 相比 MAP 分别下降了 48.89%、 19.54%， TF 数据集 s-2 与原图数据集 o-i 和其他 第 2 期 谭婷，等：基于图表示和匹配的表单定位与提取 ·235·
·236· 智能系统学报 第14卷 扩展数据集偏离幅度较大，FF数据集也有明显的 位置出现偏差，建立表单的映射关系缺乏准确的 降低。出现这种变化的原因有：图像缩小比率过 参考点，则重合度偏差大，准确率下降，定位不准 大时，表单图像上关键区域块纹理信息损失较 确。总体来说，算法对旋转、亮度调节、放大变 多，这将导致图匹配时可参考的正确位置少，同 换、小幅度缩小变换的表单图像的提取能保持良 时过度缩小的图像使得关键区域中对应的特征点 好的稳定性。 表1多联表单和热敏表单的平均重叠率和平均准确率 Table 1 Mean average overlap(MAO)and mean Average Precision(MAP)of TF and FF datasets 数据集 o-i b-1 b-2 d-2e-1e-2s-1s-2r1r-2 r-3 r-4 MAP0.9270.9050.8760.9260.9040.9390.9450.7980.4380.9220.8980.9290.989 多联表单(TF) MA00.9240.9160.9000.9250.9080.9370.9380.8280.5670.9220.9120.9310.937 MAP0.8280.816 0.7590.8510.8280.7930.8050.7010.6320.7930.8160.7360.862 热敏表单(FF) MA00.8550.8500.8150.8780.8550.8320.8470.8010.7720.8460.8490.8330.870 1.00 的定位。据此，图7~10所示为表单图像中用户感 《 0.80 兴趣关键区域的定位与提取结果，其中图7和 0.60 图8为TF类表单图像，图9和图10为FF类表单 0.40 ★-1+-2--1 图像。图7~10中(b)图的提取结果自上往下分别 el◆-e-2er4-bl ◆一米-2×n2e-n3h2 表示提取的收货人地址、姓名、手机号。上述 0.20 0.5 0.6 0.7 0.8 0.9 4组表单图像具有不同分辨率、亮度、方向偏转、 重叠率 (a)多联表单 面单褶皱和形变的差异，定位结果说明本文算法 能适应不同图像质量差异和不同类别的图像。由 1.00 于保证了准确定位的置信度，分割得到的表单区 0.80 域的字符较为完整、清晰、准确。此外，对表单分 量0-1 ±b-1◆b-2 ★-1 +s-2--nl 割得到的图像块进行简单的字符连通域合并，得 0.40 -e-l g--2-日-八4 到图7中4组表单相关信息的提取结果。 0.20 d1*d小2×-r29r3 0.5 0.60.7 0.8 0.9 表2多联表单和热敏表单的提取准确率 重叠率 Table 2 Extraction precision of TF and FF datasets (b)热敏表单 准确率 图6多联表单和热敏表单平均准确率 平均 数据类别 Fig.6 Mean average precision(MAP)of TF and FF I0U≥0.8 10U≥0.9 交叠率 本文实验通过计算提取结果与Lablelmg工具 多联表单(TF) 0.9741 0.8645 0.9348 标记真值交叠率来评估定位的准确性。常见目标 热敏表单(FF) 0.8393 0.6676 0.8166 检测系统中常将0.8交叠率值作为正确检测阈 值，本文在评估提取区域的准确率和平均交叠率 本文方法与文献[10,13-14中方法类似，均 时，这两组值变化趋势与映射置信度变化大致相 为采用模板匹配的方法解决表单填写内容提取的 似。因此，仅在表2中列出两类图像评估结果的 问题，该方法的关键问题是实现参考表单和待处 平均情况。对比表1和表2，说明图匹配结果越 理图像配准。文献[10,13]中采用傅里叶-梅林算 准确映射变换置信度越高，定位和提取的准确率 法以表单局部区域或全局图像为配准目标，能实 越高。当IOU阈值为0.8时，多联表单和热敏表 现不同方向的表单矫正，但该方法难以适应参考 单提取准确率分别为97.41%和83.93%，说明本 表单和待处理表单不同尺度的情况，不能准确找 文算法对这两类表单具有良好的定位与提取效果。 到表单图案的对应位置。此外文献[13]提取文本 通过图匹配结果对待处理表单的候选关键位 字符时的像素投票策略对图像噪声较为敏感，处 置进行修正，使参考表单到待处理表单的位置映 理分拣机中现实采集到的污损和局部遮挡难以达 射关系更加准确。通过对上述图匹配和映射后置 到理想的提取效果。文献[14]中预先设定表单配 信度的评估，验证了算法能对表单图像进行良好 准起始和终止参考点，作为表单方向校准的基准
扩展数据集偏离幅度较大，FF 数据集也有明显的 降低。出现这种变化的原因有：图像缩小比率过 大时，表单图像上关键区域块纹理信息损失较 多，这将导致图匹配时可参考的正确位置少，同 时过度缩小的图像使得关键区域中对应的特征点 位置出现偏差，建立表单的映射关系缺乏准确的 参考点，则重合度偏差大，准确率下降，定位不准 确。总体来说，算法对旋转、亮度调节、放大变 换、小幅度缩小变换的表单图像的提取能保持良 好的稳定性。 本文实验通过计算提取结果与 LableImg 工具 标记真值交叠率来评估定位的准确性。常见目标 检测系统中常将 0.8 交叠率值作为正确检测阈 值，本文在评估提取区域的准确率和平均交叠率 时，这两组值变化趋势与映射置信度变化大致相 似。因此，仅在表 2 中列出两类图像评估结果的 平均情况。对比表 1 和表 2，说明图匹配结果越 准确映射变换置信度越高，定位和提取的准确率 越高。当 IOU 阈值为 0.8 时，多联表单和热敏表 单提取准确率分别为 97.41% 和 83.93%，说明本 文算法对这两类表单具有良好的定位与提取效果。 通过图匹配结果对待处理表单的候选关键位 置进行修正，使参考表单到待处理表单的位置映 射关系更加准确。通过对上述图匹配和映射后置 信度的评估，验证了算法能对表单图像进行良好 的定位。据此，图 7~10 所示为表单图像中用户感 兴趣关键区域的定位与提取结果，其中图 7 和 图 8 为 TF 类表单图像，图 9 和图 10 为 FF 类表单 图像。图 7~10 中 (b) 图的提取结果自上往下分别 表示提取的收货人地址、姓名、手机号。上述 4 组表单图像具有不同分辨率、亮度、方向偏转、 面单褶皱和形变的差异，定位结果说明本文算法 能适应不同图像质量差异和不同类别的图像。由 于保证了准确定位的置信度，分割得到的表单区 域的字符较为完整、清晰、准确。此外，对表单分 割得到的图像块进行简单的字符连通域合并，得 到图 7 中 4 组表单相关信息的提取结果。 本文方法与文献 [10, 13-14] 中方法类似，均 为采用模板匹配的方法解决表单填写内容提取的 问题，该方法的关键问题是实现参考表单和待处 理图像配准。文献 [10, 13] 中采用傅里叶−梅林算 法以表单局部区域或全局图像为配准目标，能实 现不同方向的表单矫正，但该方法难以适应参考 表单和待处理表单不同尺度的情况，不能准确找 到表单图案的对应位置。此外文献 [13] 提取文本 字符时的像素投票策略对图像噪声较为敏感，处 理分拣机中现实采集到的污损和局部遮挡难以达 到理想的提取效果。文献 [14] 中预先设定表单配 准起始和终止参考点，作为表单方向校准的基准 o-i b-1 b-2 d-1 d-2 s-1 s-2 r-1 r-2 r-3 e-1 e-2 r-4 o-i b-1 d-1 d-2 b-2 s-1 s-2 r-1 r-2 r-3 e-1 e-2 r-4 0.20 0.40 0.60 0.80 1.00 0.5 0.6 0.7 0.8 0.9 准确率 重叠率 0.20 0.40 0.60 0.80 1.00 0.5 0.6 0.7 0.8 0.9 准确率 重叠率 (a) 多联表单 (b) 热敏表单 图 6 多联表单和热敏表单平均准确率 Fig. 6 Mean average precision (MAP) of TF and FF 表 1 多联表单和热敏表单的平均重叠率和平均准确率 Table 1 Mean average overlap (MAO) and mean Average Precision (MAP) of TF and FF datasets 数据集 o-i b-1 b-2 d-1 d-2 e-1 e-2 s-1 s-2 r-1 r-2 r-3 r-4 多联表单（TF） MAP 0.927 0.905 0.876 0.926 0.904 0.939 0.945 0.798 0.438 0.922 0.898 0.929 0.989 MAO 0.924 0.916 0.900 0.925 0.908 0.937 0.938 0.828 0.567 0.922 0.912 0.931 0.937 热敏表单（FF） MAP 0.828 0.816 0.759 0.851 0.828 0.793 0.805 0.701 0.632 0.793 0.816 0.736 0.862 MAO 0.855 0.850 0.815 0.878 0.855 0.832 0.847 0.801 0.772 0.846 0.849 0.833 0.870 表 2 多联表单和热敏表单的提取准确率 Table 2 Extraction precision of TF and FF datasets 数据类别 准确率 平均 IOU≥0.8 IOU≥0.9 交叠率 多联表单（TF） 0.974 1 0.864 5 0.934 8 热敏表单（FF） 0.839 3 0.667 6 0.816 6 ·236· 智 能 系 统 学 报 第 14 卷
第2期 谭婷，等：基于图表示和匹配的表单定位与提取 ·237· 点，该方法更适用于具有相同分辨率、亮度和对 4结束语 比度的扫描图像，另外，当基准点出现异物遮挡 或缺损的情况难以灵活处理。本文方法采用表单 本文提出了一种基于图表示和匹配的表单定 图匹配的方法以解决上述处理过程中存在的不 位与提取方法，实验表明：本文方法适用于局部 遮挡和不同类别、分辨率、方向、旋转、光照条件 足，根据不同表单已有的图案选取多个参考关键 下的表单图像的处理，是一种通用的表单图像准 区域构建图，采用图匹配的配准方式以解决单一 确定位和相关区域的提取方法。虽然本文方法实 参考基准点鲁棒性差的问题。此外图匹配配准方 现了大部分表单图像相关信息的准确定位和提 式能更好的适应不同尺度、方向、分辨率、光照条 取，但在缩小和单面形变幅度较大的图像上表现 件的图像，以及基准位置局部遮挡的问题。 效果不佳，下一步将考虑采用不同方法建立表单 关键区域的映射，以适应缩小比例大和较大范围 香红字成由款它以空益有北企区 形变图像的处理，同时，采用更为准确的后处理 本海过号中被通股位有闲公通止金组二 方法，去除无关的空白区域，使表单相关信息的 褚斌 提取精确到完整的字符串。 38967870167 参考文献： (a)定位结果 (b)提取结果 [1]SHARMA D V,LEHAL G S.Form field frame boundary 图7CXB表单定位和提取结果 removal for form processing system in Gurmukhi Fig.7 Results for C-XB form Location and extraction script[C]//Proceedings of the 10th International Confer- 品是B记E4 ence on Document Analysis and Recognition.Barcelona. Spain,2009:256-260. [2]CHEN J L,LEE H J.An efficient algorithm for form struc- ture extraction using strip projection[J].Pattern recogni- 300411G033 ion,1998,31(9):1353-1368. (a)定位结果 (b)提取结果 [3]LIU Wenyin,DORI D.From raster to vectors:extracting visual information from line drawings[J].Pattern analysis 图8EMS-MULT表单定位和提取结果 and applications,1999,2(1):10-21. Fig.8 Results for EMS-MULT form Location and [4]WATANABE T,LUO Qin,SUGIE N,et al.Layout recog- extraction nition of multi-kinds of table-form documents[J].IEEE transactions on pattern analysis and machine intelligence, 1995.17(4):432-445 [5]LAM S W.SRIHARI S N.Multi-domain document layout 韩偷巧 understanding[C]//Proceedings of International Confer- 18221423567 ence on Document Analysis and Recognition.1991: 112-120 (a)定位结果 (b)提取结果 [6]SACHDEVA R.SHARMA D V.Data extraction from 图9 YUNDA表单定位和提取结果 hand-filled form using form template[J].International Fig.9 Results for YUNDA form Location and extraction journal on recent and innovation trends in computing and communication,2015,3(8):5311-5317. 海方浦东新区东方路160号仁济 [7]NING L W,SIAH Y K,KHALID M,et al.Design of an 门诊楼5楼检科533室 automated data entry system for hand-filled forms[C]//Pro- 王亚福 ceedings of 2000 TENCON.Kuala Lumpur,Malaysia, 2000:162-166 881782141 [8]BENSEFIA A.Extraction of Arabic handwriting fields by (a)定位结果 (b)提取结果 forms matching[J].Journal of signal and information pro- 图10 EMS-FLAT表单定位和提取结果 cessing.2015,6(1):53424. Fig.10 Results for EMS-FLAT form Location and [9]CESARINI F.GORI M,MARINAI S,et al.INFORMys:a extraction flexible invoice-like form-reader system[J].IEEE transac-
点，该方法更适用于具有相同分辨率、亮度和对 比度的扫描图像，另外，当基准点出现异物遮挡 或缺损的情况难以灵活处理。本文方法采用表单 图匹配的方法以解决上述处理过程中存在的不 足，根据不同表单已有的图案选取多个参考关键 区域构建图，采用图匹配的配准方式以解决单一 参考基准点鲁棒性差的问题。此外图匹配配准方 式能更好的适应不同尺度、方向、分辨率、光照条 件的图像，以及基准位置局部遮挡的问题。 4 结束语 本文提出了一种基于图表示和匹配的表单定 位与提取方法，实验表明：本文方法适用于局部 遮挡和不同类别、分辨率、方向、旋转、光照条件 下的表单图像的处理，是一种通用的表单图像准 确定位和相关区域的提取方法。虽然本文方法实 现了大部分表单图像相关信息的准确定位和提 取，但在缩小和单面形变幅度较大的图像上表现 效果不佳，下一步将考虑采用不同方法建立表单 关键区域的映射，以适应缩小比例大和较大范围 形变图像的处理，同时，采用更为准确的后处理 方法，去除无关的空白区域，使表单相关信息的 提取精确到完整的字符串。 参考文献： SHARMA D V, LEHAL G S. Form field frame boundary removal for form processing system in Gurmukhi script[C]//Proceedings of the 10th International Conference on Document Analysis and Recognition. Barcelona, Spain, 2009: 256–260. [1] CHEN J L, LEE H J. An efficient algorithm for form structure extraction using strip projection[J]. Pattern recognition, 1998, 31(9): 1353–1368. [2] LIU Wenyin, DORI D. From raster to vectors: extracting visual information from line drawings[J]. Pattern analysis and applications, 1999, 2(1): 10–21. [3] WATANABE T, LUO Qin, SUGIE N, et al. Layout recognition of multi-kinds of table-form documents[J]. IEEE transactions on pattern analysis and machine intelligence, 1995, 17(4): 432–445. [4] LAM S W, SRIHARI S N. Multi-domain document layout understanding[C]//Proceedings of International Conference on Document Analysis and Recognition. 1991: 112–120. [5] SACHDEVA R, SHARMA D V. Data extraction from hand-filled form using form template[J]. International journal on recent and innovation trends in computing and communication, 2015, 3(8): 5311–5317. [6] NING L W, SIAH Y K, KHALID M, et al. Design of an automated data entry system for hand-filled forms[C]//Proceedings of 2000 TENCON. Kuala Lumpur, Malaysia, 2000: 162–166. [7] BENSEFIA A. Extraction of Arabic handwriting fields by forms matching[J]. Journal of signal and information processing, 2015, 6(1): 53424. [8] CESARINI F, GORI M, MARINAI S, et al. INFORMys: a flexible invoice-like form-reader system[J]. IEEE transac- [9] (a) 定位结果 (b) 提取结果 图 10 EMS-FLAT 表单定位和提取结果 Fig. 10 Results for EMS-FLAT form Location and extraction (a) 定位结果 (b) 提取结果 图 7 C-XB 表单定位和提取结果 Fig. 7 Results for C-XB form Location and extraction (a) 定位结果 (b) 提取结果 图 8 EMS-MULT 表单定位和提取结果 Fig. 8 Results for EMS-MULT form Location and extraction (a) 定位结果 (b) 提取结果 图 9 YUNDA 表单定位和提取结果 Fig. 9 Results for YUNDA form Location and extraction 第 2 期 谭婷，等：基于图表示和匹配的表单定位与提取 ·237·
·238· 智能系统学报 第14卷 tions on pattern analysis and machine intelligence,1998 2016,38(3:532-545 20(7):730-745 [16]LEORDEANU M,SUKTHANKAR R,Hebert M,et al. [10]CHO M,SUN Jian,DUCHENNE O,et al.Finding Unsupervised learning for graph matching[].Internation- matches in a haystack:a max-pooling strategy for graph al journal of computer vision,2012,96(1):28-45. matching in the presence of outliers[C]//Proceedings of [17]UIJLINGS J RR.VAN DE SANDE K EA.GEVERS T. 2014 IEEE Conference on Computer Vision and Pattern et al.Selective search for object recognition[J].Interna- Recognition.Columbus,OH,USA,2014:2091-2098. [11]SUH Yumin,ADAMCZEWSKI K,LEE K M.Subgraph tional journal of computer vision,2013,104(2):154-171. matching using compactness prior for robust feature cor- 作者简介： respondence[C]//Proceedings of 2015 IEEE Conference on Computer Vision and Pattern Recognition.Boston, 谭婷，女，1992年生，硕士研究 MA,USA.2015:5070-5078. 生，主要研究方向为图像处理与计算 [12]SHARMA A,HORAUD R,CECH J,et al.Topologically- 机视觉。 robust 3D shape matching based on diffusion geometry and seed growing[C]//Proceedings of 2011 IEEE Confer- ence on Computer Vision and Pattern Recognition. Providence,RI,USA,2011:2481-2488. [13]DUCHENNE O.JOULIN A,PONCE J.A graph-match- 吕淑静，女，1977年生，高级工程 ing kernel for object categorization[C]//Proceedings of 师博士，主要研究方向为图像处理与 2011 IEEE International Conference on Computer Vision. 计算机视觉。 Barcelona.Spain,2011:1792-1799. [14]ZHANG Quanshi.SONG Xuan.SHAO Xiaowei.et al. Attributed graph mining and matching:an attempt to define and extract soft attributed patterns[C]//Proceed- 吕岳.男，1968年生，教授.博士 ings of 2014 IEEE Conference on Computer Vision and 生导师，主要研究方向为模式识别、图 Pattern Recognition.Columbus,OH,USA,2014: 像处理、生物特征识别、信息检索、数 1394-1401. 据挖掘、自然语言处理、机器视觉系 [15]ZHANG Quanshi,SONG Xuan,SHAO Xiaowei,et al. 统。9次获得省部级科学技术奖，其 Object discovery:soft attributed graph mining[J].IEEE 中一等奖4次。授权发明专利 transactions on pattern analysis and machine intelligence. 13项。发表学术论文100余篇
tions on pattern analysis and machine intelligence, 1998, 20(7): 730–745. CHO M, SUN Jian, DUCHENNE O, et al. Finding matches in a haystack: a max-pooling strategy for graph matching in the presence of outliers[C]//Proceedings of 2014 IEEE Conference on Computer Vision and Pattern Recognition. Columbus, OH, USA, 2014: 2091–2098. [10] SUH Yumin, ADAMCZEWSKI K, LEE K M. Subgraph matching using compactness prior for robust feature correspondence[C]//Proceedings of 2015 IEEE Conference on Computer Vision and Pattern Recognition. Boston, MA, USA, 2015: 5070–5078. [11] SHARMA A, HORAUD R, CECH J, et al. Topologicallyrobust 3D shape matching based on diffusion geometry and seed growing[C]//Proceedings of 2011 IEEE Conference on Computer Vision and Pattern Recognition. Providence, RI, USA, 2011: 2481–2488. [12] DUCHENNE O, JOULIN A, PONCE J. A graph-matching kernel for object categorization[C]//Proceedings of 2011 IEEE International Conference on Computer Vision. Barcelona, Spain, 2011: 1792–1799. [13] ZHANG Quanshi, SONG Xuan, SHAO Xiaowei, et al. Attributed graph mining and matching: an attempt to define and extract soft attributed patterns[C]//Proceedings of 2014 IEEE Conference on Computer Vision and Pattern Recognition. Columbus, OH, USA, 2014: 1394–1401. [14] ZHANG Quanshi, SONG Xuan, SHAO Xiaowei, et al. Object discovery: soft attributed graph mining[J]. IEEE transactions on pattern analysis and machine intelligence, [15] 2016, 38(3): 532–545. LEORDEANU M, SUKTHANKAR R, Hebert M, et al. Unsupervised learning for graph matching[J]. International journal of computer vision, 2012, 96(1): 28–45. [16] UIJLINGS J R R, VAN DE SANDE K E A, GEVERS T, et al. Selective search for object recognition[J]. International journal of computer vision, 2013, 104(2): 154–171. [17] 作者简介： 谭婷，女，1992 年生，硕士研究 生，主要研究方向为图像处理与计算 机视觉。 吕淑静，女，1977 年生，高级工程 师，博士，主要研究方向为图像处理与 计算机视觉。 吕岳，男，1968 年生，教授，博士 生导师，主要研究方向为模式识别、图 像处理、生物特征识别、信息检索、数 据挖掘、自然语言处理、机器视觉系 统。9 次获得省部级科学技术奖，其 中一等 奖 4 次。授权发明专 利 13 项。发表学术论文 100 余篇。 ·238· 智 能 系 统 学 报 第 14 卷