第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·