基于笔画特征的在线笔迹匹配算法

邹杰 孙宝林 於俊

基于笔画特征的在线笔迹匹配算法

邹杰1,2孙宝林2於俊1

针对现有在线笔迹匹配算法鲁棒性不强的问题,本文提出将合并规则和跳跃规则引入到动态规划的迭代过程,以跳跃规则应对书写中的多、漏笔现象,以合并规则应对因多种书写不一致造成的分割点多提取、漏提取现象.在累计差异矩阵计算中,提出以笔画特征,特别是笔画形状信息来度量笔画间的差异.在SVC2004和SUSIG签名数据库上与现有主要在线笔迹匹配算法进行比较.实验结果表明,本文方法能较好应对多种局部书写和分割的不一致,从而获得更准确、鲁棒的笔画对应关系.

在线笔迹认证,笔迹匹配,笔画差异值度量,动态规划

现代社会,计算机网络已走进人们生产生活的方方面面.网络环境下,方便快捷、安全可靠地对用户身份进行认证成为亟待解决的问题.手写笔迹作为一种行为特征,相对于其他生理特征,例如指纹、虹膜、DNA等,具有主动的特征提取过程、模板内容可更换等特点,更适合于网络环境下的应用,受到人们广泛关注[1−2].

按获取信息的方式,笔迹认证分为离线和在线两种.前者依据书写后留下的静态笔迹图像数据进行认证[3−4],后者依靠专门的设备实时获取书写过程中产生的各种信息进行认证.本文主要讨论在线笔迹认证.

在线笔迹认证的特征提取通常分为参数法和函数法[5].参数法是指用一组参数表示笔迹,通过参数的比较来判断测试笔迹的真实性.常用的参数特征包括笔迹书写时间、落笔书写长度、长宽比、各种极值点个数、各种域变换系数等[5−6].由于书写活动的复杂性以及这些特征对笔迹书写细节描述能力的不足,通常认证系统还会采用函数法提取特征.

函数法是指将手写笔迹的各种信号看作时间的函数,通过直接比较模板和测试笔迹时间函数来判别真实性.常用的函数特征提取方法包括动态时间规整(Dynamic time warping,DTW)[7−8]、隐马尔科夫模型(Hidden Markov model,HMM)[8−9]等.在小样本约束条件下,通过函数法挖掘笔画特征具有重要意义.这是因为:1)稳定性.尽管在微观细节上笔迹特征差异可能较大,但从宏观上看,例如笔顺、笔画的形状、长短、笔画间的相对位置关系、前后笔画间的转折承接方式、笔迹整体结构布局等,具有较高的稳定性.2)个性化.笔迹学研究发现,受自身成长环境、感知能力等因素影响,人们在笔画的运笔方式、起落笔方式、笔画间相对位置关系、前后笔画间的转折书写用力、书写节奏上有着多种多样的表现形式,从根本上反映出书写者自身的书写习惯,具有较高的鉴别价值[10].然而,提取上述笔画特征却并非易事,需要以鲁棒地建立笔画对应关系为前提.

典型的匹配算法包括笔迹分割和笔画匹配两个步骤.国内外学者对此进行了广泛深入的研究.简单的笔迹分割方法有等长分割法[11]和起落笔点选取法[12].由于笔迹书写长度和提落笔的不一致,简单分割法的匹配结果往往难以令人满意.其他分割方法还包括:1)遗传算法[13].该方法选用模板笔迹集合中两两分割点序列的DTW差异值的均值作为适配函数,使适配函数最小的点被选为分割点.2)直线近似法[13].以笔迹中任意两点构成的直线代替对应的曲线运笔,若曲线运笔与直线围成的面积大于某一阈值,则在曲线中寻找一个点将运笔分为前后两段.重复上述步骤直到所有直线与曲线的面积都小于预设的阈值.3)小波变换法[14].其思路是小波变换的过零点往往对应书写中的视觉关键点. 4)极值点法.包括速度极小值、角度、曲率极大值等[15−16].5)模糊综合法.考虑到书写的任意性,单一的极值并不完全与笔画的起止点对应,而应综合考虑多方面的信息[17],由此定义分割点的隶属度函数,函数值由角度、速度共同决定,其值越大,越可能是关键点.6)视觉拐点法[18].计算前后某一长度运笔中采样点在弯曲程度上对中间点的贡献值,其值越大,越可能是视觉拐点.

按建立分割点对应关系的方式,文献中的匹配方法大致分为三类:1)事先无需提取分割点[19].该方法采用HMM模型寻找分割点对应关系.具体地,模型选用左右状态转移结构,状态发生变化的采样点被定义为分割点.该方法依据状态转移路径中状态发生变化的位置得到分割点对应关系.2)仅提取模板笔迹的分割点,分割点对应关系依DTW全局匹配路径计算得到[19].首先,提取模板笔迹中的分割点;然后采用DTW算法建立模板与测试笔迹之间的全局匹配路径;最后根据全局匹配路径,找出与模板笔迹分割点对应的测试笔迹采样点,以此得到分割点对应关系.3)提取模板和测试笔迹的分割点,利用优化方法建立分割点对应关系.首先,对模板和测试笔迹按笔画进行分割;其次,计算分割点的各种属性值,例如分割点类型[20−24]、开口方向[12,23]、相邻分割点之间的距离[23−24]、角度[22,25]等;再次,以这些采样点特征构造目标函数;最后,采用优化算法求目标函数极值,与极值对应的即为所求的分割点对应关系.文献中常见的优化算法包括:遗传算法[13]、最小化二次适应判定方程方法(Quadratic fitting criterion equation)[26]、动态规划方法[27]、最小化薄板样条函数(Thin-plate spline)扭曲能量(Warping energy)[28]的退火算法.

尽管国内外学者在匹配问题上做了大量工作,但目前仍未取得令人满意的匹配结果.造成现有算法鲁棒性不强的原因可归纳为:1)在笔迹分割方面,以采样点特征为依据的笔迹分割方法,难以克服书写的各种不一致(停笔、顿笔、抖笔、多笔、少笔、绕笔、异化笔、虚提笔、简化笔等),从而得到一致的笔迹分割结果;2)在笔画匹配方面,由于存在不一致的笔迹分割结果,且后继优化方法未采取相应的应对措施;更糟的是,在错误分割基础上采用易受干扰且可分性不强的采样点特征来计算目标函数,造成现有方法难以克服多种书写不一致,进而得到正确的笔画对应关系.

由此可见,当存在上述各种书写不一致且仅有采样点特征可用的条件下,笔迹分割的不一致几乎是不可避免的.分析运笔特点可发现,造成不一致分割的书写不一致大体分为两类:1)整体一致条件下局部出现的多笔、少笔;2)整体一致条件下局部因简化笔、抖笔、顿笔、异化笔等造成的分割点多提取或漏提取.对此,本文采取的应对方法为:1)如果模板笔迹中出现多笔或漏笔,在测试笔迹相应位置处将没有或多出笔画与之匹配.由此,在寻优过程中引入跳跃规则.2)如果模板笔迹中出现分割点多提取或漏提取,那么,正确的笔画对应关系应该是模板笔迹中的多个或一个笔画与测试笔迹的一个或多个笔画相对应.因此,引入合并规则.

现有工作大多基于分割点特征构造目标函数.由于抗干扰能力不强、包含信息量有限,分割点特征并不足以区分前后相邻的笔画.笔迹学研究指出,笔画有着丰富表现形式.以横画为例,有平直横、上弧横、下弧横(弧的弯曲程度有大有小),以及蚕头燕尾横(以向下点笔开始、接着向上运笔、最后以向下顿笔结束)等.在笔画差异度量方面,常见的方法仅利用了采样点位置[29−30]、速度[31]、曲率[32]等信息.匹配结果表明,这些信息未能充分体现笔画中的差异,使得算法鲁棒.对此,本文提出从笔画长短、重心位置、方位角、笔画形状四个方面对笔画差异进行度量.

最后,在SVC2004[33]和SUSIG[34]公共签名数据库上,将本文方法的匹配结果与现有主要匹配算法的进行比较[12,20−25,30],以此验证本文方法的有效性.

1 基于笔画特征的笔迹匹配

建立笔画间对应关系问题可描述为:对于模板和测试笔迹笔画序列,在时序性约束条件下,在所有可能的笔画对应关系序列中,寻找一个使笔画间累计差异值之和最小的笔画对应关系序列.

考虑到求解过程的复杂度,一种基于迭代的动态规划方法被引入进来[35].其中,采用何种规则来计算累计差异值矩阵D成为匹配算法是否准确和鲁棒的关键.

针对前文分析的造成算法不够鲁棒的原因,本文采用抗干扰能力更强、信息量更丰富的笔画特征.利用笔画特征的直观性,在迭代过程中引入多种物理含义明确的合并和跳跃规则来计算累计差异值矩阵D.

1.1 笔迹匹配步骤

笔迹匹配步骤如下:

步骤1.按Brault等提出的视觉关键点将笔迹按笔画进行分割[18],得到笔画序列.两个按视觉关键点分割后的笔迹如图1所示.

图1 按视觉关键点得到的笔迹分割结果示例Fig.1 Examples of handwriting segmented by perceptually important points

步骤2.将合并规则和跳跃规则引入迭代过程,计算累计差异值矩阵D.

图2给出了因关键点多(漏)提取造成的笔迹分割不一致示例,右图中“的”字横竖弯钩运笔部分因弯曲程度不够明显造成分割点的漏提取.为应对此类不一致,在累计差异矩阵计算中引入合并规则.具体为:如式(1)中[a]～[j]项所示(分别为1:1,1: 2,2:1,···,1:4,4:1合并规则),如果存在某一合并规则,使按该规则得到的对应笔画间差异值小于阈值P,则本轮累计差异矩阵的取值由那个使对应笔画差异值与上轮累计差异矩阵取值之和最小的合并规则而定.式(1)中dmer(i−1,i),j表示合并模板笔迹中的(i−1)～i段笔画后与测试笔迹中的第j段笔画间的差异值,下标mer(x,y)表示合并笔画序列中的x～y段笔画,该符号出现的位置与笔迹对应,左(右)侧表示合并模板(测试)笔迹.dij表示第i段模板笔画与第j段测试笔画的差异值.

图2 因弯曲程度不够造成的笔迹分割不一致Fig.2 Inconsistent segmentation caused by over and less curving strokes

图3给出了因多(漏)笔造成的分割不一致示例,左图中“孟”字的第1笔被漏写了.对此类不一致,引入跳跃规则,如式(1)中[k]～[l]项所示,其中,Dij表示累计差异值矩阵中第i行第j列元素, 1≤i≤N,1≤j≤M,其中N和M 分别表示模板和测试笔迹的笔画数.

图3 因多笔造成的笔迹分割不一致Fig.3 Inconsistent segmentation caused by superfluous and loss strokes

一般来讲,如果出现多笔,该多出的笔画与前后笔画的差异可能很大.基于这一观察,定义跳跃规则为:如果笔画间的差异大于阈值P,则模板或测试笔迹中的当前笔画被跳过.式(1)中阈值P需要预先设定.在本文实验部分将对阈值P的设定方法和不同取值对匹配结果的影响进行讨论.

在迭代过程中,跳跃规则被执行时可能的笔画对应关系状态如图4所示.图中以圆或三角形表示笔画,其中,实心圆表示到上一轮为止已确立对应关系的笔画,空心圆表示在计算当前Dij时若干候选的待跳过笔画,三角形表示未确定对应关系的笔画,黑色直线表示已确立的笔画对应关系.如式(1)中[k]～[l]项所示,被跳过的笔画依上轮迭代得到的累计差异阵取值而定.

图4 跳过测试笔迹的第j段笔画(左)和跳过模板笔迹的第i段笔画(右)Fig.4 Jumping the jth stroke of testing handwriting (left)and jumping the ith stroke of template(right) handwriting

图5给出了合并规则被执行时可能的笔画对应关系状态.为简便起见,仅以2:1和1:2两种情况为例,图5中空心圆表示计算当前Dij时若干候选笔画,灰色直线表示候选的笔画对应关系,图中其他符号的含义与图4中相同.

图5 2:1(左)和1:2(右)合并规则Fig.5 2:1(left)and 1:2(right)merging rule

显然,引入越多的合并规则,算法应对各种复杂不一致的能力越强.但是合并规则越多,算法复杂度越高,产生过匹配[24]的可能性越大.

式(1)中w表示寻优搜索的窗口宽度,w=β ×N,其中N表示模板笔迹的笔画数.

步骤3.采用式(1)给出的合并规则和跳跃规则,从i=1,j=1开始,迭代地计算累计差异值矩阵D,设初值D00=0.

步骤4.从DNM开始,依据被选取的合并规则和跳跃规则,回溯得到笔画对应关系.

1.2 笔画差异度量

手写活动是非常细腻的,由此产生的笔画具有丰富的表现形态.准确度量笔画间差异对提高算法准确性具有重要意义.文献中对笔画差异度量主要采用了采样点各种差异特征的累计加权求和,包括位置[29−30]、速度[31]、曲率[31]等信息.分析发现:1)笔画间至少包含大小、位置、方位角以及笔画形态等方面的差异,仅用其中一种特征对差异的描述显然不够全面.2)基于采样点特征的求和使得少数决定笔画形态的转折处差异淹没在其他多数平缓的运笔中,使本应有的差异体现不出来.3)采样点特征易受噪声、抖动的干扰.为克服这些问题,本文依据由分段点分得的笔画特征计算差异.下面以图6中“九”字“横竖弯”笔画为例,介绍本文笔画差异度量方法.

1)大小差异度量

其中,AMaxX,AMaxY,AMinX,AMinY,BMinY, BMinX,BMaxX,BMaxY分别表示模板和测试笔画在X和Y轴上的最大、最小值.

2)位置差异度量其中,GA和GB分别表示两段笔画的重心位置坐标.

图6 两个汉字笔迹“九”Fig.6 Two handwriting examples of Chinese character“nine”

3)方位角差异度量

其中,0°≤αA≤180°,0°≤αB≤180°分别表示与两段笔画最大特征值对应的特征向量与X轴的夹角[29].

4)形状差异

形状差异是指除去笔画间的大小、方位、位置差异后,单纯从形态上所体现的差异.本文采用关键点的对应关系来度量形状差异.

步骤 1.对笔画进行缩放[36]、旋转[29]和平移变换[29],去除掉笔画间的大小、方位、位置差异.为了防止缩放失真,对笔画的长宽按等比例进行缩放[36].为便于比较,统一将max(width,height)设置为100,其中width、height分别表示缩放后笔画的宽度和高度.对图6中笔画除去大小、位置和方位差异后的结果如图7所示.其中,S1,S2分别表示模板和测试笔画.

图7 两段归一化后“九”字的横竖弯笔画Fig.7 Two normalized compound strokes in Chinese character“nine”

步骤2.利用角度极大值点对笔画进行分割.分割后的结果如图8所示.图8中D2、D3、d2表示角度极大值分割点.由于弯曲不够明显,S1第二个转折处分段点d3被漏提取.

步骤3.采用经典DTW算法计算笔画S1与S2的点点对应关系[35].结果如图9所示.

图8 笔画分割结果,D2、D3、d2为角度极大值点Fig.8 Two compound strokes segmented by angle maximum points D2,D3,and d2

图9 采用经典DTW得到的点点对应关系Fig.9 Point-to-point corresponding calculated by the classical DTW

步骤4.对匹配偏差加以纠正,得到分段点对应关系.从图9可以看出,由于书写的不一致,S1中的分段点d2并未与S2中的分段点D2匹配上.但是,由于DTW在这里仅限于局部的笔画匹配,累积的错误并未产生过大偏差.该特性将被用来消除匹配错误.

规则1.设q是S2中与S1中分段点d2对应的点,D2是S2中与q点距离最近的分段点,若点q到D2的距离小于距离阈值T,则判定S2分段点D2与S1分段点d2相匹配.

规则2.设d3是S1中与S2中分段点D3对应的点,若S1中不存在与点d3的距离小于距离阈值T的分段点,则判定分段点D3与采样点d3相匹配.

规则1和规则2中的距离阈值T=η×L,其中,L表示模板笔画S1的长度,η为比例因子.

利用上述规则,纠偏后的分段点对应关系如图10所示.

图10 纠偏后的分割点对应关系Fig.10 Revised segmentation point corresponding

依据得到的分段点对应关系,采用式(7)计算笔画间形状差异.

图11 以相邻分割点构成的向量近似表示笔画Fig.11 Stroke approximated by vectors consisting of adjacent segmentation points

按式(8)对所求四种差异值进行融合

其中,µ,σ分别表示在自建签名笔迹数据库上计算得到的所有对应笔画间关于大小、位置、方位角和笔画形状差异的均值和方差.

2 实验

本节在公共签名数据库SVC2004任务2数据集上验证本文方法4个预设参数对匹配结果的影响.然后,将所获得的最优阈值应用到SUSIG有视觉反馈数据集上,在SVC2004和SUSIG上,将本文方法的匹配结果与文献[12,20−25,30]进行比较,以此检验本文方法的有效性.

SVC2004和SUSIG分别收集了40和100位用户的真实签名笔迹.为了体现签名随时间的波动性,两个库的组织者分两次对每位用户的签名进行采集,采集间隔至少一周,每次各采集10个样本.这样,共获得2800个样本.

为了验证匹配算法的准确性,将匹配结果与人工得到的理想匹配结果相比较.具体步骤为:对数据库中每位用户的20个真实签名,任选其中1个作为模板样本,剩下19个作为测试样本.计算模板与每个测试样本之间的关键点对应关系.然后,将其与人工得到的匹配结果进行比较.设

表示Patha中与距离之和最近的一对关键点对应关系,1≤j′≤n,Len(·,·)表示笔迹序列中两个采样点间的运笔长度.

式(11)或式(12)成立.

设匹配错误率

其中,c表示Patha中正确匹配个数.

图12列出了4组由人工给出分割点的理想对应关系示例,图中用星号表示分割点,星号旁边的数字表示该分割点在关键点序列中的序号.两个序号相同的分割点相对应.

图12 由人工给出的四组笔迹分割点的理想对应关系Fig.12 Four group of ideal segmentation point corresponding

2.1 窗口宽度阈值选取实验

本节讨论式(1)中窗口宽度阈值w的选取对匹配结果的影响.设w=β×N,其中,N表示模板笔迹被分割的笔画数.其他阈值预设为:采用式(1)列出的所有10种合并规则;T=0.1×L;P=u+3 ×σ;其中,L表示模板笔画的长度,u,σ含义如第2.3节所述.不同β取值在SVC2004库40组签名上得到的平均匹配错误率如表1所示.

表1 β取值对平均匹配错误率(%)的影响Table 1 Average matching error rate(%)for various values of β

从表1可以看出,过小和过大的β取值,匹配错误率较高.因为过小的窗口宽度使本应正确的匹配笔画被排除在窗口以外;而过大的窗口则引入了过多的错误匹配笔画.当0.15≤β≤0.20时,β的取值对匹配结果影响不大,因为尽管多笔少笔普遍存在,但从以笔画作为笔迹构成单位来看,多数人笔迹具有较好的书写一致性,没有出现严重的少笔多笔问题.因此相对较松的窗口阈值即可将正确的笔画包含进来.

2.2 距离阈值选取实验

本节讨论距离阈值T=η×L选取对匹配结果的影响.基于第2.1节的实验结果,设β=0.175,其他阈值的预设值与第2.1节所述相同.不同η取值在SVC2004库40组签名上得到的平均匹配错误率如表2所示.

表2 η取值对平均匹配错误率(%)的影响Table 2 Average matching error rate(%)for various values of η

从表2可以看出,在一个相对较小的阈值上,得到最小的匹配错误率.因为本文方法中DTW仅被应用于局部笔画间的采样点匹配.相对于全局笔迹匹配中普遍存在的严重错误累积问题,由于受限于笔画长度,该问题并不明显,因此给定较小的距离阈值即可将匹配错误纠正过来.实验结果表明,当η=0.10时,算法得到最低的匹配错误率.

2.3 差异阈值选取实验

本节讨论式(1)中差异阈值P的选取对匹配结果的影响.设差异阈值P=u+ασ,其中,u,σ分别表示在自建签名笔迹数据库上计算得到的所有对应笔画间差异值的均值和方差,α是比例因子.其中,自建签名笔迹数据库包含利用手写板采集的34位书写者的签名笔迹,每位书写者提供了30个真实签名,共1020个真实签名,以及针对每位书写者10个专业伪造签名和10个随机伪造签名,共680个伪造签名.

基于前述实验得到的最优窗口和距离阈值,调整比例因子α,采用式(1)列出的10种合并规则,在SVC2004库40组签名上得到的平均匹配错误率如表3所示.

表3 α取值对平均匹配错误率(%)的影响Table 3 Average matching error rate(%)for various values of α

从表3可以看出,随着比例因子α的逐步增加,本文方法平均匹配错误率迅速降低.因为过小差异阈值使很多本应匹配的笔画被排除在迭代候选项之外,从而造成匹配错误.随着α的加大,错误率随之降低.但随着α的进一步加大,匹配错误率反而随之增加.因为虽然过大的差异阈值能将书写一致性较差的正确匹配包含进来,但是,由于式(1)中引入了过多合并规则,一些错误笔画也被包含进来.若正确笔画间的差异值在所有候选项中不是最小时,则产生匹配错误.

2.4 合并规则选取实验

本节将对式(1)中列出的10个合并规则进行讨论.关于少笔或多笔现象,由于多个少笔或多笔可用多个跳跃规则的叠加来处理,因此迭代过程采用式(1)中的[k]、[l]两个跳跃规则即可.

依据前述实验得到的3个最优阈值,在相同实验条件下,依次增加合并规则,观察到不同合并规则组合方案在SVC2004库40组签名上得到的平均匹配错误率如表4所示.

表4 不同合并规则对匹配错误率(%)的影响Table 4 Average matching error rate(%)for different merging rule combination schemes

从表4可以看出,起初随着一步迭代方程中引入更多的合并规则,本文方法的平均匹配错误率逐步降低.说明本文引入的合并规则能较好地应对书写中的不一致,从而得到正确的匹配结果.但是,当到达一定程度后,平均匹配错误率开始上升.因为如果本应匹配笔画由于书写的不一致,造成差异值过大,以至于大过错误匹配笔画的差异值时,将发生匹配错误.特别是引入合并规则的个数越多,发生上述错误的可能性越大.此外,引入过多的合并规则还将增加计算量.

实验结果表明,当采用方案4时,本文方法的平均匹配错误率达到最低.

2.5 笔画差异量度比较实验

基于前述实验得到各个最优阈值和最优合并规则,将第1.2节所描述的笔画差异度量方法与现有的方法[29−32]进行比较,在SVC2004库40组签名上的平均匹配错误率如表5所示.

从表5可以看出,本文方法能有效降低匹配错误率.对此的解释是:本文方法更全面考虑了笔画间各种差异,使得笔画间的可区分性更强.图13给出了在相同三组签名上分别采用新差异度量方法和已有方法得到的匹配结果,其中,第1栏和第2栏是本文方法的匹配结果,第3栏和第4栏是已有方法的.第1栏和第3栏是模板笔迹,第2栏和第4栏是测试笔迹.图13中以直线表示对应的笔画,直线起点处的数字表示相应的笔画序号,序号相同的直线相匹配.若直线起点处没有数字则表示该笔画没有对应的匹配.如图13中箭头所示,已有方法在多处产生了匹配错误,而本文方法能克服多种书写不一致,得到合理的匹配结果.例如箭头A所示的第一组“王丹”笔迹的起始“横竖”运笔处.显然,模板笔迹中的“横竖”运笔与测试笔迹中的“竖”画运笔是存在明显差异的,然而已有方法得到的笔画“横竖”与“竖”间的差异却比“竖”与“竖”间的小,致使随后的迭代过程选取了错误匹配路径.同样的错误还出现在箭头B到F处.本文方法由于更全面反映了笔画间差异,避免了上述错误,得到正确的笔画对应关系.

表5 本文笔画差异度量方法与已有方法比较Table 5 Comparison of the proposed stroke difference measurement method and the existing method

图13 本文方法和已有笔画差异度量方法在匹配结果上的比较(第1栏和第2栏给出了本文方法的匹配结果示例,第3栏和第4栏给出了相同笔迹在已有方法上的匹配结果示例)Fig.13 Comparison of matching results based on stroke difference measurement between the proposed (the 1 and 2 columns)and existing methods(the 3 and 4 columns)

2.6 匹配结果比较实验

将本文方法在SVC2004和SUSIG两个公共签名数据库上,与已有笔迹匹配方法进行比较,以此验证本文方法的准确性和鲁棒性,以及多个先验阈值设定的有效性.将SVC2004和SUSIG数据库每个用户的签名按字形一致性,从高到低人为地分为4组.分组数据如表6和表7所示.为了方便比较,在同一实验平台上(Windows7.0,Matlab2007b,4GB内存,4核2.4GHz CPU)编程分别实现了本文及公开文献中给出的几种主要笔迹匹配算法[12,20−25,30].在每一组签名上,将本文方法与已有方法的匹配结果进行比较,平均匹配错误率如表8所示.

从表8可以看出,在两个数据库的每一组签名上,本文方法均获得最小的匹配错误率.说明本文方法的匹配准确性和鲁棒性是最好的.图14和图15分别给出了本文方法与已有方法在两个公共签名数据库上的匹配结果示例.图中,第1栏和第2栏为本文方法的匹配结果,第3栏和第4栏为相同笔迹在已有方法上的匹配结果.图14和图15中各种符号含义与图12和图13相同.图14和图15中用箭头标出了造成现有方法出现匹配错误的两类原因:1)不一致的笔迹分割,主要表现为落笔时的抖动(A,T)、转折处的顿笔造成的关键点多提取(E,D,J,R,U, W)、连笔处的虚提笔(I)、圆滑转笔造成的关键点漏提取(G,P)、伪关键点提取(K);2)各种不一致的运笔,主要有不一致的笔顺(B)、多笔、少笔(C, F,L,Q,S)、一致性较差的小碎笔(H,M,N)、简化笔(O,V).通常情况下,上述现象是混合出现的,这进一步增加了解决匹配问题的困难程度.

表6 SVC2004的签名分组表Table 6 SVC2004 signature group table

表7 SUSIG的签名分组表Table 7 SUSIG signature group table

表8 在SVC2004和SUSIG上,本文方法与已有方法在4组笔迹上平均匹配错误率(%)比较Table 8 Average matching error rate(%)comparison on four group signatures between our method and existing methods on SVC2004 and SUSIG

如表8与图14和图15中第1栏和第2栏所示,在SVC2004和SUSIG两个公共签名数据库上,与现有方法相比较,本文方法在匹配准确性和鲁棒性上均有明显提升.这是由于:1)本文提出了“采用视觉关键点分割+基于多特征融合的笔画相似性度量”的技术方案,在度量笔画相似性方面,提出了一种单纯形状差异的度量方法.虽然现有方法也主张进行分段,但大多利用X和Y分量的极大极小值对一维时序信息进行分割[12,20−25,30],在分别建立上述两种序列的波形极值点对应关系后,再通过一组规则来推导得到二维笔画的对应关系[22].波形对应规则看似简单直观(波峰对波峰、波谷对波谷),但是由于波形包含的信息量有限(峰谷大小、位置),从而在匹配峰谷大小相似但个数不同的两组时序信号时,极易产生错误匹配(这种情况在英文签名中尤为常见,例如图15中箭头P、U所示).接下来在推导二维笔画对应关系时,由于每组规则均引入了先验的阈值参数,因而在处理各种复杂的书写不一致情况时,很难设定统一的阈值以使得算法鲁棒.基于上述问题,直接利用二维笔画特征来构造目标函数的方法被提出来.例如利用分段点的开口类型特征[12,23],利用笔画的(X,Y)[12,21,30]、速度[21,30]、角度[25]、曲率[12]的差异值特征.如前文所述,由于书写活动的细腻性,仅依靠上述信息很难有效地反映笔画间所包含的细微差异.第2.5节笔画差异值度量实验结果表明,简单利用笔画的某一特征很难将其中的差异真实反映出来.这样的直接结果就是算法将两段看起来差异明显的笔画而不是更为相似的笔画匹配起来(例如图13中箭头A,B,C,D,E,F所示).相对于现有方法,本文技术方案的优点有:a)省去了两次计算一维极值点匹配再求二维关键点匹配的步骤;b)相较于波形,平面中笔画所包含的丰富信息有利于描述它们间的差异;c)笔画特征的直观性使得本文方法将多种物理意义明确的合并和跳跃规则引入到优化过程中来.2)基于融合多特征的笔画差异度量方法构造的目标函数,本文提出了将跳跃和合并规则引入到寻优过程,以应对各种复杂的书写不一致.虽然也用到了合并规则(2对1、1对2规则)[22−24],但受限于X,Y分量对笔画差异反映的间接性,文献中的合并规则只是被用来应对因书写中的顿笔、抖动而产生的X,Y分量伪波峰问题[22−24].更复杂的多笔、漏笔、简化笔、异化笔等书写不一致则无力应对(例如图14和图15中箭头C,F,H,N,O,V所示).与此相反,本文直接提取笔画特征,得益于笔画特征的直观性,更加丰富(1对1、2对1等10种规则)且物理含义明确的合并规则被引入到寻优过程中.受益于不同类型的笔画在差异值特征上表现出来的可区分性,例如撇画和捺画的方位角特征,使得跳跃规则被引入寻优过程中以应对多笔、漏笔问题.由于新笔画特征度量更真实地体现了笔画本身所具有的差异,使得算法在面对如式(1)所示的多个候选匹配项时,选取的差异值最小项最有可能为正确的匹配结果(例如图14和图15中左边两列所示).

图14 本文方法与现有方法在SVC2004上匹配结果示例Fig.14 Examples of matching result obtained by the proposed and the existing methods on SVC2004

如图14中第1行第2列“刘”字中的第一笔是因虚落笔而多出来的“提笔画”.该提笔与前后笔画均存在较大差异,以至于在如式(1)所示的所有合并规则中,基于新笔画度量方法得到的该笔画与前后对应笔画的差异值均大于阈值P,这样跳跃规则被执行.最终本文方法成功地将该多出的笔画分辩出来.由于未引入跳跃规则,现有方法需强行找一个与该多笔对应的笔画,因此导致匹配错误.进一步,该错误被传导到后继匹配而导致连锁反应,例如图14中箭头A、B所示.

相似的因多笔引起的匹配错误如图14中箭头C所示,本来应该合并模板笔迹(图14第2行第3列)中的第16～17、17～18、18～20段与测试笔迹(图14第2行第4列)中的第19～20段相匹配(这里的数字表示图中关键点的序号),然而由于现有算法没有引入合并规则,从而致使匹配错误;与之相反,在本文方法中,由于引入了多种合并规则并且新的笔画差异度量方法计算的差异值在所有合并规则中最小,从而使得期望的合理匹配被寻优方法选中,最终输出正确的匹配结果.

因快速运笔导致的分割点漏提取例子如图15第3行第1列和第2列所示.图中第1列第10段笔画由于快速书写,本应提取的两个关键点被漏提取.但是由于本文方法引入了合并规则并且根据正确合并规则(第3行第1列中的第10段笔画与第2列中的由3个子段组成的第10段笔画相匹配)得到的差异值在所有合并规则中最小,因而输出正确的匹配结果.与此相反,从图15第3行第3列和第4列给出的已有方法的匹配结果可以看出,由于同样的原因,已有方法未能输出正确匹配结果.

由于本文引入的合并规则、跳跃规则和有效的笔画差异度量方法,在面对因小碎笔(图14和图15中箭头H,M,N所示)和简化笔(图15中箭头O, V所示)导致的分割不一致问题时,本文方法均输出了正确的匹配结果(本文方法的匹配结果如图14和图15中相同行的第1行和第2行所示).本文方法得到正确匹配的原因与前述多笔、分割点漏提取的相同.

图15 本文方法与现有方法在SUSIG上匹配结果示例Fig.15 Examples of matching result obtained by the proposed and the existing methods on SUSIG

2.7 本文方法存在的问题及不足

本文方法存在以下不足及有待解决的问题:1)如图16第1行所示,若笔迹中包含如“ABAB”这样特征相似的笔画组,如笔迹“军”字中的“横折横折”运笔,且“横”笔画出现在两个笔迹中的次数不一致时,可能出现匹配错误.图16第1行中两个签名匹配错误的原因在于测试笔迹中第1个横折画与其他位置处的横折画在长度和形状上更一致.2)本文算法的匹配结果受阈值P的影响较大.不合理的设定可能产生这样的错误:本应跳过的笔画未被跳过,或者相反.如图16第2行所示,两个“王”字笔迹在起笔处均有抖动,由于抖笔长度、形态相差过大,使得本应匹配的笔画被跳过.在下个迭代步骤中,测试笔迹中本应跳过的抖笔,由于模板笔迹中的“横”与测试笔迹中的“抖横”间差异过小,从而产生错误匹配.

图16 本文方法存在的问题和不足示例Fig.16 Examples of remaining shortcomings of our method

3 总结与展望

面对因分割不一致造成的笔迹匹配算法鲁棒性不强的问题,本文提出一种引入合并规则和跳跃规则的动态规划方法,并采用笔画特征,特别是笔画间单纯意义上的形态差异特征来计算累计差异值矩阵.匹配结果表明,本文方法能有效克服多种书写不一致,例如多笔、漏笔、简化笔、异化笔等,进而得到鲁棒的笔画对应关系.在SVC2004和SUSIG签名数据库上,与同类匹配算法的实验结果验证了本文方法的有效性.

基于匹配结果,除了采用DTW简单地计算对应笔画间各种信号的差异值特征,还可以进一步挖掘其他的笔画特征,例如起落笔方式、笔画运笔方式、笔画间转折承接方式、笔迹整体结构布局、笔画间相对位置关系等重要特征,从而提升系统认证性能.

1 Mohammed R A,Nabi R M,Mahmood S M R,Nabi R M. State-of-the-art in handwritten signature verification system.In:Proceedings of the 2015 International Conference on Computational Science and Computational Intelligence. Las Vegas,NV:IEEE,2015.519−525

2 Yu J,Wang Z F.A video,text,and speech-driven realistic 3-D virtual head for human-machine interface.IEEE Transactions on Cybernetics,2015,45(5):991−1002

3 Li Xin,Ding Xiao-Qing,Peng Liang-Rui.A microstructure feature based text-independent method of writer identification for multilingual handwritings.Acta Automatica Sinica, 2009,35(9):1199−1208 (李昕,丁晓青,彭良瑞.一种基于微结构特征的多文种文本无关笔迹鉴别方法.自动化学报,2009,35(9):1199−1208)

4 Chen Xiao-Su,Wu Zhen-Hua,Xiao Dao-Ju.Off-line Chinese signature verification based on segmentation and HMM. Acta Automatica Sinica,2007,32(2):205−210 (陈晓苏,吴振华,肖道举.一种基于签名分段和HMM的离线中文签名验证方法.自动化学报,2007,32(2):205−210)

5 Liu Y S,Yang Z H,Yang L H.Online signature verification based on DCT and sparse representation.IEEE Transactions on Cybernetics,2015,45(11):2498−2511

7 Nautsch A,Rathgeb C,Busch C.Bridging gaps:an application of feature warping to online signature verification.In: Proceedings of the 2014 International Carnahan Conference on Security Technology(ICCST).Rome,Italy:IEEE,2014. 1−6

8 Jiao Hui-Min,Wang Dang-Xiao,Zhang Yu-Ru,Fang Lei. Signature verification using handwriting friction force.Acta Automatica Sinica,2011,37(7):883−890 (焦慧敏,王党校,张玉茹,方磊.基于书写摩擦力的签名识别方法.自动化学报,2011,37(7):883−890)

9 Pirlo G,Cuccovillo V,Impedovo D,Mignone P.On-line signature verification by multi-domain classification.In:Proceedings of the 14th International Conference on Frontiers in Handwriting Recognition(ICFHR).Heraklion,Greece: IEEE,2014.67−72

10 Wang Zi-He.Identification of Practicing Imitating Handwriting[Master dissertation],Southwest University of Political Science and Law,China,2010. (王梓合.练习摹仿笔迹鉴定研究[硕士学位论文],西南政法大学,中国,2010.)

11 Ansari A Q,Kour J.Uniform segmentation in online signature verification.In:Proceedings of the 2015 Annual IEEE India Conference.New Delhi,India:IEEE,2015.1−6

12 Wang K Y,Wang Y H,Zhang Z X.On-line signature verification using segment-to-segment graph matching.In:Proceedings of the 2011 International Conference on Document Analysis and Recognition.Beijing,China:IEEE,2011.804−808

13 Wirotius M,Ramel J Y,Vincent N.Selection of points for on-line signature comparison.In:Proceedings of the 9th International Workshop on Frontiers in Handwriting Recognition(IWFHR).Tokyo,Japan:IEEE,2004.503−508

14 CaiHong-Bin,ShiZe-Sheng,FanXiao-Feng,Huang Hao,Yin She-Guang.A handwritten signature verification method based on wavelet transform to pick up inflection points.Journal of Image and Graphics,2003,8(3):261−265 (蔡洪滨,施泽生,范晓峰,黄浩,尹社广.一种基于小波变换提取拐点的手写签名认证方法.中国图象图形学报,2003,8(3):261−265)

17 Guo Hong,Jin Xian-Ji.The extract algorithm of special points in signature based on dynamic information.Journal of Wuhan University of Science and Technology(Natural Science Edition),2001,24(2):186−188 (郭宏,金先级.一种基于签名动态特征的特殊点提取算法.武汉科技大学学报(自然科学版),2001,24(2):186−188)

18 Brault J J,Plamondon R.Segmenting handwritten signatures at their perceptually important points.IEEE Transactions on Pattern Analysis and Machine Intelligence,1993, 15(9):953−957

19 Quan Zhong-Hua.A Study of the Authentication Based on Online Signatures[Ph.D.dissertation],University of Science and Technology of China,China,2007. (全中华.基于动态手写签名的身份认证研究[博士学位论文],中国科学技术大学,中国,2007.)

20 Quan Z H,Ji H W.Aligning and segmenting signatures at their crucial points through DTW.In:Proceedings of the 2005 International Conference on Intelligent Computing.Hefei,China:Springer,2005.49−58

21 Mohammadi M H,Faez K.Matching between important points using dynamic time warping for online signature verification[Online],available:http://www.cyberjournals.com/ Papers/Jan2012/01.pdf,June 24,2016

22 Li B,Zhang D,Wang K Q.Improved critical point correspondence for on-line signature verification.International Journal of Information Technology,2006,12(7):45−56

23 Lee J,Yoon H S,Soh J,Chun B T,Chung Y K.Using geometric extrema for segment-to-segment characteristics comparison in online signature verification.Pattern Recognition, 2004,37(1):93−103

24 Hao F,Chan C W.Online signature verification using a new extreme points warping technique.Pattern Recognition Letter,2003,24(16):2943−2951

25 Barkoula K,Economou G,Fotopoulos S.Online signature verification based on signatures turning angle representation using longest common subsequence matching.International Journal on Document Analysis and Recognition, 2013,16(3):261−272

26 Zhang K,Pratikakis I,Cornelis J,Nyssen E.Using landmarks to establish a point-to-point correspondence between signatures.Pattern Analysis and Applications,2000,3(1): 69−75

27 Ansari A Q,Hanmandlu M,Kour J,Singh A K.Online signature verification using segment-level fuzzy modelling.IET Biometrics,2014,3(3):113−127

28 Li Bin.Research on the Technology of Online Handwritten Signature Verification.[Ph.D.dissertation],Harbin Institute of Technology,China,2006. (李彬.联机手写签名鉴别技术的研究[博士学位论文],哈尔滨工业大学,中国,2006.)

29 Ibrahim M T,Khan M A,Alimgeer K S,Khan M K,Taj I A, Guan L.Velocity and pressure-based partitions of horizontal and vertical trajectories for on-line signature verification. Pattern Recognition,2010,43(8):2817−2832

31 Kholmatov A,Yanikoglu B.Identity authentication using improved online signature verification method.Pattern Recognition Letters,2005,26(15):2400−2408

32 Kar B,Dutta P K,Basu T K,VielHauer C,Dittmann J. DTW based verification scheme of biometric signatures.In: Proceedings of the 2006 IEEE International Conference on Industrial Technology.Mumbai,India:IEEE,2006.381−386

33 Yeung D Y,George S,Kashi R,Matsumoto T,Rigoll G. SVC 2004:first international signature verification competition[Online],available:http://www.cse.ust.hk/svc2004, June 24,2016

34 Kholmatov A,Yanikoglu B.SUSIG:an on-line signature database,associated protocols and benchmark results.Pattern Analysis and Applications,2009,12(3):227−236

35 Sakoe H,Chiba S.Dynamic programming algorithm optimization for spoken word recognition.IEEE Transactions on Acoustics,Speech,and Signal Processing,1978,26(1): 43−49

36 Fischer A,Diaz M,Plamondon R,Ferrer M A.Robust score normalization for DTW-based on-line signature verification. In:Proceedings of the 13th International Conference on Document Analysis and Recognition(ICDAR).Tunis,Italy: IEEE,2015.241−245

37 Fang P,Wu Z C,Meng M,Ge Y J,Yu Y.A novel tablet for on-line handwriting signal capture.In:Proceedings of the 5th World Congress on Intelligent Control and Automation. Hangzhou,China:IEEE,2004.3714−3717

邹 杰 博士,武汉工商学院计算机科学与技术系讲师.主要研究方向为模式识别,在线笔迹身份认证和图像处理.

E-mail:qvbso@mail.ustc.edu.cn

(ZOU Jie Ph.D.,lecturer in the Department of Computer Science and Technology,Wuhan Technology and Business University.His research interest covers pattern recognition,online handwriting verification,and image processing.)

孙宝林 博士,武汉工商学院计算机科学与技术系教授.主要研究方向为现场总线和实时以太网.

E-mail:blsun@163.com

(SUN Bao-Lin Ph.D.,professor in the Department of Computer Science and Technology,Wuhan Technology and Business University.His research interest covers field bus and real-time Etherent.)

於 俊 博士,中国科学技术大学自动化系副研究员.主要研究方向为智能人机交互和智能机器人.本文通信作者.

E-mail:harryjun@ustc.edu.cn

(YU Jun Ph.D.,associate professor in the Department of Automation,University of Science and Technology of China.His research interest covers human computer interaction and intelligent robot.Corresponding author of this paper.)

Online Handwriting Matching Algorithm Based on Stroke Features

ZOU Jie1,2SUN Bao-Lin2YU Jun1

To solve the robustness problem of online handwriting matching,a novel method is proposed in which the jumping and merging rules are introduced to the iterative step of dynamic programming.Specifically,jumping rules are used to deal with the superfluous and loss strokes while merging rules are used to deal with inconsistent handwriting segmentation caused by jerk,hesitating,compound-strokes,etc.In calculation of the cumulative difference matrix,a new measurement is proposed in which stroke shape information is applied to measuring stroke differences.The matching results calculated by the proposed method are compared to those of the existing main methods on SVC2004 and SUSIG public signatures databases.It is shown that the new method can obtain better accuracy and more robust stroke correspondence with respect to various local writings and segmentation inconsistency.

Online handwriting verification,handwriting matching,stroke difference measurement,dynamic programming

邹杰,孙宝林,於俊.基于笔画特征的在线笔迹匹配算法.自动化学报,2016,42(11):1744−1757

Zou Jie,Sun Bao-Lin,Yu Jun.Online handwriting matching algorithm based on stroke features.Acta Automatica Sinica,2016,42(11):1744−1757

2015-09-06 录用日期2016-06-22

Manuscript received September 6,2015;accepted June 22,2016

国家自然科学基金(61572012,61303150),中央高校基本科研业务费专项资金重要方向培育基金项目(WK2350000002),湖北省自然科学基金重点项目(2014CFA055),湖北省高等学校优秀中青年科技创新团队计划项目(T201631),浙江大学计算机辅助与图形学国家重点实验室开放课题(A1501)资助

Supported by National Natural Science Foundation of China (61572012,61303150),the Fundamental Research Funds for the Central Universities(WK2350000002),the Key Project Natural Science Foundation of Hubei Province(2014CFA055),Hubei Province High School Outstanding Young Science and Technology Innovation Team Project(T201631),and the Open Project Program of the State Key Laboratory of CAD and CG of Zhejiang University(A1501)

本文责任编委桑农

Recommended by Associate Editor SANG Nong

1.中国科学技术大学自动化系合肥 230027 2.武汉工商学院计算机科学与技术系武汉430065

1.Department of Automation,University of Science and Technology of China,Hefei 230027 2.Department of Computer Science and Technology,Wuhan Technology and Business University,Wuhan 430065

DOI 10.16383/j.aas.2016.c150563