第5期 张文超，等：几何信息与SFT特征相结合的特定人手写关键词检测 ·547. 周围的梯度统计信息。利用式(3)可以对匹配特征 件的几何意义是，分布于汉字上的特征点随笔画的 点对进行初步筛选： 随意性移动的范围不会超过一定的阈值。因为相同 |0-0.1<P1 的汉字具有相同的笔画结构和笔顺，相应的特征点 0,1 也应当具有类似的分布。 P2< (3) C p2 ‖d,-d.I2<p3 式中：0，、o,、d,和0.、0.、d.分别表示关键词图 像和窗口图像的特征点方向角、尺度、特征矢量。 P1、P2、P,分别是对应的阈值。匹配点经过初步筛 窗口图像 选后的结果如图2所示。 性 也气促使症状发： 关键词图像 图2匹配特征点初步筛选后结果 Fig.2 Feature matching after initial selection 图3窗口内匹配点的分布信息 图中截取了滑动窗口在文本图像中的一个片 Fig.3 Location information of matching points 段，矩形框为窗口的位置，下面显示的是关键词的图 当存在越多的正确匹配点时，GCG图中互相连 像，细直线连接了两幅图像中匹配的特征点。可以 接的顶点将会越多。为了得到一个存在最多正确匹 看到图中依然存在很多误匹配的点对，这是由汉字 配点对的子集，就要在GCG中找到一个最大子图， 重复的结构信息引起的。利用特征点在文字的空间 在这个子图中所有的顶点都是互相连接的，可使用 分布建立几何约束，可以进一步删除误匹配点对。 最大团查找(maximal clique matching,MCM)算法来 几何约束原理就是：关键词图像上存在一定位置关 实现，其具体过程如下 系的两个特征点，它们在窗口图像中对应的两个匹 1)初始化候选顶点集C=V,最大团顶点集为 配点也具有相似的位置关系。通过这个原理可以在 M=9; 特征点对之间建立几何约束图，再通过图论中的最 2)计算V中每个顶点的度，记为集合Deg(V): 大团查找算法获得正确的匹配，点对集合。几何约束 3)选择C中Deg(V)最大的顶点to,将其加入 图(geometric constraint graph,GCG)建立步骤如下 M,即M=MU{o}; 1)设S={s1,s2,…,sm}为关键词图像特征点 4)将。从C中删除，并且只在C中保留和。相 集，W={01,02,…,0n}为文本图像中与之匹配的 连接的顶点，即C=C\o,C=CUN(o)。其中 特征点集。无向图G=(V,E)表示几何约束图。V= V()表示o的邻接顶点集。 {1,2,"}为G的顶点集合，其中：=(s,0:), 5)如课C=p,算法结束，否测转到重复上述过程。 表示S和W中每一对匹配点就对应G中的一个顶 通过建立几何约束图和最大团查找算法，可以 点。ECV×V为G边的集合。 删除大量误匹配点对，图2中的初始匹配经过几何 2)按照如下方法添加G的边，对于任意两个特 约束处理后结果如图4所示。线连接了两幅图中匹 征点对：=(5,0)和=(s,四)，满足约束条件 配的特征点对，从图4中可以看到，笔画上的特征点 基本上是正确匹配的。 |(x-x）-(x:-xg)|<p4×Avg(c,) I-y,)-(,-y)1<5×Ag(a,)(4) 性 色会侯使症状袭 则在顶点，和之间添加一条边。式中x,和x。表 示特征点在关键词图像和窗口图像内的横坐标，而 图4匹配特征点进一步筛选结果 y、y.则表示其纵坐标，参考图3示例。P4和P5是 Fig.4 Location information of matching points 两个阈值，为了适应不同关键词图像的尺寸，式(4) 2.3窗口筛选和合并 中的右值应当与其平均尺度值成正比。该式约束条 结合几何约束对匹配点进行筛选之后，每个窗周围的梯度统计信息。 利用式（３）可以对匹配特征 点对进行初步筛选： θｓ － θｗ ＜ ｐ１ ｐ２ ＜ σｓ σｗ ＜ １ ｐ２ ‖ ｄｓ － ｄｗ‖２ ＜ ｐ３ （３） 式中： θｓ 、 σｓ 、 ｄｓ 和 θｗ 、 σｗ 、 ｄｗ 分别表示关键词图 像和窗口图像的特征点方向角、尺度、特征矢量。 ｐ１ 、 ｐ２ 、 ｐ３ 分别是对应的阈值。 匹配点经过初步筛 选后的结果如图 ２ 所示。 图 ２ 匹配特征点初步筛选后结果 Ｆｉｇ．２ Ｆｅａｔｕｒｅ ｍａｔｃｈｉｎｇ ａｆｔｅｒ ｉｎｉｔｉａｌ ｓｅｌｅｃｔｉｏｎ 图中截取了滑动窗口在文本图像中的一个片 段，矩形框为窗口的位置，下面显示的是关键词的图 像，细直线连接了两幅图像中匹配的特征点。 可以 看到图中依然存在很多误匹配的点对，这是由汉字 重复的结构信息引起的。 利用特征点在文字的空间 分布建立几何约束，可以进一步删除误匹配点对。 几何约束原理就是：关键词图像上存在一定位置关 系的两个特征点，它们在窗口图像中对应的两个匹 配点也具有相似的位置关系。 通过这个原理可以在 特征点对之间建立几何约束图，再通过图论中的最 大团查找算法获得正确的匹配点对集合。 几何约束 图（ｇｅｏｍｅｔｒｉｃ ｃｏｎｓｔｒａｉｎｔ ｇｒａｐｈ，ＧＣＧ）建立步骤如下 １）设 Ｓ ＝ ｛ｓ１ ，ｓ２ ，．．．，ｓｍ ｝ 为关键词图像特征点 集， Ｗ ＝ ｛ｗ１ ，ｗ２ ，．．．，ｗｍ ｝ 为文本图像中与之匹配的 特征点集。 无向图 Ｇ ＝ （Ｖ，Ｅ） 表示几何约束图。 Ｖ ＝ ｛ｖ１ ，ｖ２ ，．．．，ｖｍ ｝ 为 Ｇ 的顶点集合，其中 ｖｉ ＝ （ｓｉ，ｗｉ） ， 表示 Ｓ 和 Ｗ 中每一对匹配点就对应 Ｇ 中的一个顶 点。 Ｅ ⊆ Ｖ × Ｖ 为 Ｇ 边的集合。 ２）按照如下方法添加 Ｇ 的边，对于任意两个特 征点对 ｖｉ ＝ （ｓｉ，ｗｉ） 和 ｖｊ ＝ （ｓｊ，ｗｊ） ，满足约束条件 （ｘｓ ｉ － ｘｓ ｊ ） － （ｘｗｉ － ｘｗｊ ） ＜ ｐ４ × Ａｖｇ（σｓ） （ｙｓ ｉ － ｙｓ ｊ ） － （ｙｗｉ － ｙｗｊ ） ＜ ｐ５ × Ａｖｇ（σｓ） （４） 则在顶点 ｖｉ 和 ｖｊ 之间添加一条边。 式中 ｘｓ 和 ｘｗ 表 示特征点在关键词图像和窗口图像内的横坐标，而 ｙｓ 、 ｙｗ 则表示其纵坐标，参考图 ３ 示例。 ｐ４ 和 ｐ５ 是 两个阈值，为了适应不同关键词图像的尺寸，式（４） 中的右值应当与其平均尺度值成正比。 该式约束条 件的几何意义是，分布于汉字上的特征点随笔画的 随意性移动的范围不会超过一定的阈值。 因为相同 的汉字具有相同的笔画结构和笔顺，相应的特征点 也应当具有类似的分布。 图 ３ 窗口内匹配点的分布信息 Ｆｉｇ．３ Ｌｏｃａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｍａｔｃｈｉｎｇ ｐｏｉｎｔｓ 当存在越多的正确匹配点时，ＧＣＧ 图中互相连 接的顶点将会越多。 为了得到一个存在最多正确匹 配点对的子集，就要在 ＧＣＧ 中找到一个最大子图， 在这个子图中所有的顶点都是互相连接的，可使用 最大团查找（ｍａｘｉｍａｌ ｃｌｉｑｕｅ ｍａｔｃｈｉｎｇ，ＭＣＭ）算法来 实现，其具体过程如下 １）初始化候选顶点集 Ｃ ＝ Ｖ ，最大团顶点集为 Ｍ ＝ φ ； ２）计算 Ｖ 中每个顶点的度，记为集合 Ｄｅｇ（Ｖ）； ３）选择 Ｃ 中 Ｄｅｇ（Ｖ） 最大的顶点 ｖ０ ，将其加入 Ｍ，即 Ｍ ＝ Ｍ ∪ ｛ｖ０ ｝ ； ４）将 ｖ０ 从 Ｃ 中删除，并且只在 Ｃ 中保留和 ｖ０ 相 连接的顶点，即 Ｃ ＝ Ｃ ＼ｖ０ ， Ｃ ＝ Ｃ ∪ Ｎ（ｖ０ ） 。 其中 Ｎ（ｖ０ ） 表示 ｖ０ 的邻接顶点集。 ５）如果Ｃ ＝ φ ，算法结束，否则转到重复上述过程。 通过建立几何约束图和最大团查找算法，可以 删除大量误匹配点对，图 ２ 中的初始匹配经过几何 约束处理后结果如图 ４ 所示。 线连接了两幅图中匹 配的特征点对，从图 ４ 中可以看到，笔画上的特征点 基本上是正确匹配的。 图 ４ 匹配特征点进一步筛选结果 Ｆｉｇ．４ Ｌｏｃａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｍａｔｃｈｉｎｇ ｐｏｉｎｔｓ ２．３ 窗口筛选和合并 结合几何约束对匹配点进行筛选之后，每个窗 第 ５ 期 张文超，等：几何信息与 ＳＩＦＴ 特征相结合的特定人手写关键词检测 ·５４７·