«上一篇
 文章快速检索 高级检索

 智能系统学报  2019, Vol. 14 Issue (2): 231-238  DOI: 10.11992/tis.201709038 0

### 引用本文

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. DOI: 10.11992/tis.201709038.

### 文章历史

1. 华东师范大学 上海多维度信息处理重点实验室，上海 200062;
2. 中国邮政集团公司上海研究院 图像分析与智能系统联合实验室，上海 200062

Form location and extraction based on graph representation and matching
TAN Ting 1, LYU Shujing 2, LYU Yue 1,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.
Key words: image segmentation    form extraction    form location    graph representation    graph matching    isomorphic graph    express package sorting

1 表单图表示 1.1 参考表单的图表示 1.1.1 参考表单关键区域的选取

 Download: 图 1 参考表单关键区域选取样例 Fig. 1 An example for key area selection of reference form
1.1.2 关键区域的图表示

 Download: 图 2 参考表单图样例 Fig. 2 An example for graph of reference form

1)结点属性 ${o}$ 。SIFT对图像局部特征的描述具有良好旋转和尺度不变性，对光照有较强的鲁棒性。采用SIFT来描述图的结点属性表示为

 ${{o}_{{i}}} = \left\{ {{{f}_{{i}1}},{{f}_{{i}2}}, \cdots ,{{f}_{{im}}}} \right\}\quad m = 1,2, \cdots ,M$ (1)

2)结构属性 ${\varphi }$ ${\varphi }$ 表示结点vi结构属性，它包括两个子属性：结点权重属性 ${\omega }$ 和夹角属性 ${\theta }$ ，结点vi的结构属性表示为 ${{\varphi }_{{i}}} = \left\{ {{{\omega }_{{i}}},{{\theta }_{{i}}}} \right\}$

 ${{\omega }_{{i}}} = \left\{ {{e_{i1}},{e_{i2}}, \cdots ,{e_{ij}}} \right\}\quad i,j = 1,2, \cdots ,N,i \ne j$ (2)

v7射线簇属性为{e71, e72, e73, e74, e75, e76, e78}。

 ${{\theta }_{{i}}} = \left\{ {\alpha \left( {{e_{ij}},{e_{ik}}} \right)} \right\}\;\;\;\;i,j,k = 1,2, \cdots ,N,i \ne j \ne k$ (3)

1.2 待处理表单的图表示 1.2.1 待处理表单候选关键区域的选取

 Download: 图 3 待处理表单候选关键区域选取样例 Fig. 3 An example for candidate key area selection of test form
1.2.2 候选结点筛选

1.2.3 候选关键区域图表示

 Download: 图 4 候选同构图 Fig. 4 Candidate isomorphic graph
2 表单图匹配

2.1 候选同构图

2.2 距离度量

1)结点相似度

gq中结点 ${V^g}$ $V$ 的SIFT特征点采取最近邻匹配进而得到匹配特征点对的F-Score值 $F_1({o}_{{i}}^{{g}},{{o}_{{i}}})$ ，则图结点间的相似距离定义为

 ${d_{{o}}}(i) = 1 - F_1 ({o}_{{i}}^{{g}},{{o}_{{i}}})$ (4)

2)结构相似度

 ${d_{{\theta }}}(i) = 1 - {\rm cos}\left( {{\theta }_{{i}}^{{g}},{{\theta }_{{i}}}} \right)$ (5)

 ${\mathop{\rm sim}\nolimits} \left( {{\omega }_{{i}}^{{g}},{\omega }_{{i}}^{{q}}} \right){\rm{ = }}{\rm ex{p}^{ - \frac{{\bf{DX}}}{{\bf{E}{\bf{X}^2}}}}}$ (6)

 ${d_{{\omega }}}(i) = 1 - {\rm sim}\left( {{\omega }_{{i}}^{{g}},{\omega }_{{i}}^{{q}}} \right)$ (7)

 $D(q(i),g(i)) = {d_{{o}}}(i) + {d_{{\theta }}}(i) + {d_{{\omega }}}(i)$ (8)

 ${d_{{\rm Num}}} = \frac{{{\rm ON}}}{{{N^q}}}$ (9)

 $d(q,g) = \frac{3}{{{N^q} - {\rm ON}}}\sum\limits_i^N {{c_i}[{d_{{o}}}(i) + {d_{{\theta }}}(i) + {d_{{\omega }}}} (i)] + {d_{{\rm Num}}}$ (10)

 $D(q,G) = {\rm arg min d}(q,g)$ (11)

2.3 待处理表单定位

3 实验及分析 3.1 数据集

3.2 评价标准

 ${\rm AO}{\rm{ = }}\frac{1}{{n_l}}\sum\limits_{i = 1}^{n_l} {{\rm overlap(vgt}_i^q,v_i^q)}$ (12)

MAP是当重叠率AO高于某一阈值T时，则待处理表单的匹配位置为准确位置，故MAP表示为

 ${\rm MAP} = \frac{{{\rm num}({\rm AO} \geqslant T)}}{I}$ (13)

 ${\rm IOU} = \frac{{{\rm DetectionResult} \cap {\rm GroundTruth}}}{{{\rm DetectionResult }\cup {\rm GroundTruth}}}$ (14)

3.3 实验结果及分析

 Download: 图 6 多联表单和热敏表单平均准确率 Fig. 6 Mean average precision (MAP) of TF and FF

 Download: 图 7 C-XB表单定位和提取结果 Fig. 7 Results for C-XB form Location and extraction
 Download: 图 8 EMS-MULT表单定位和提取结果 Fig. 8 Results for EMS-MULT form Location and extraction
 Download: 图 9 YUNDA表单定位和提取结果 Fig. 9 Results for YUNDA form Location and extraction
 Download: 图 10 EMS-FLAT表单定位和提取结果 Fig. 10 Results for EMS-FLAT form Location and extraction

4 结束语

 [1] 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. (0) [2] CHEN J L, LEE H J. An efficient algorithm for form structure extraction using strip projection[J]. Pattern recognition, 1998, 31(9): 1353-1368. DOI:10.1016/S0031-3203(97)00156-8 (0) [3] LIU Wenyin, DORI D. From raster to vectors: extracting visual information from line drawings[J]. Pattern analysis and applications, 1999, 2(1): 10-21. DOI:10.1007/s100440050010 (0) [4] 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. DOI:10.1109/34.385976 (0) [5] LAM S W, SRIHARI S N. Multi-domain document layout understanding[C]//Proceedings of International Conference on Document Analysis and Recognition. 1991: 112–120. (0) [6] 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. (0) [7] 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. (0) [8] BENSEFIA A. Extraction of Arabic handwriting fields by forms matching[J]. Journal of signal and information processing, 2015, 6(1): 53424. (0) [9] CESARINI F, GORI M, MARINAI S, et al. INFORMys: a flexible invoice-like form-reader system[J]. IEEE transactions on pattern analysis and machine intelligence, 1998, 20(7): 730-745. DOI:10.1109/34.689303 (0) [10] 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. (0) [11] 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. (0) [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 Conference on Computer Vision and Pattern Recognition. Providence, RI, USA, 2011: 2481–2488. (0) [13] 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. (0) [14] 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. (0) [15] ZHANG Quanshi, SONG Xuan, SHAO Xiaowei, et al. Object discovery: soft attributed graph mining[J]. IEEE transactions on pattern analysis and machine intelligence, 2016, 38(3): 532-545. DOI:10.1109/TPAMI.2015.2456892 (0) [16] LEORDEANU M, SUKTHANKAR R, Hebert M, et al. Unsupervised learning for graph matching[J]. International journal of computer vision, 2012, 96(1): 28-45. DOI:10.1007/s11263-011-0442-2 (0) [17] 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. DOI:10.1007/s11263-013-0620-5 (0)