一种基于DTW的动态笔迹识别算法

雷海武 刘任任 刘新

摘要：随着移动互联网技术的快速发展，智能手机、平板电脑等移动设备也得到了广泛使用。移动设备在网上购物、在线支付、转账等方面具有方便、快捷的特性，网上电子商务交易量越来越大，导致移动平台上电子商务信息的安全隐患越发突出，信息安全技术在移动平台上的应用越来越重要。基于生物特征的身份鉴别由于克服了传统身份鉴别方式的很多缺陷而得到了广泛的应用。手写笔迹是生物特征识别的重要领域之一，因具有采集设备简单、易采集、安全等优点，被广大用户所接受。针对在移动平台上识别手写笔迹的问题，提出一种基于DTW的动态笔迹识别算法。算法结合了FastDTW算法中限定路径弯折斜率，保证了识别效率;并通过放松时间弯曲时对起始端点的对齐，提高了识别的准确率。实验结果表明，算法的错误拒绝率（FRR）和错误接纳率（FAR）分别为4.5%和1.5%，识别效率和识别准确率较于经典DTW算法和FastDTW算法有所提高。

关键字：动态笔迹;DTW;身份识别;信息安全

中图分类号：TP391.43

文献标志码：A

1 引 言

基于生物特征的身份识别技术是当前信息安全技术领域的热点。而生物特征的普遍性、唯一性、稳定性和容易采集，使得生物特征应用在人的身份识别上更加安全可靠。随着移动互联网技术的发展以及智能手机等移动设备广泛普及，移动平台的安全性也成为了一个备受瞩目的信息安全技术问题。随着移动平台上的网上支付手段、交易方式被广大的用户所接纳，传统的以用户名密码方式的身份识别方式存在着极大的风险，因此在移动平台设备上采用以生物特征识别身份的方式对于个人信息和财产的安全性具有重大的意义。

动态笔迹识别是通过采集手写者的笔迹，然后检验笔迹的真伪性，从而实现身份识别的一种技术。动态笔迹可以采集手写者手写时笔划、笔顺与时间的关系以及书写速度和压力等信息，比静态笔迹的身份识别更加精确。

在动态笔迹识别方面，已有许多种成熟的算法，包括隐马尔可夫（ Hidden Markov Models，HMM）[1]、动态时间规整（Dynamic TimeWarping，DTW ）c2]、人工神经网络（ArtificialNeural Network，ANN）[3]、支持向量机（SupportVector Machine，SVM）c4]等。其中HMM算法和DTW算法的应用最为广泛，但是由于DTW算法所需样本少且简单有效，更适用于资源受限的移动平台上，因此DTW算法在这方面的应用更为广泛。20世纪60年代，日本学者Itakura将DTW算法运用到语音识别后，DTW算法很快地被引入到了笔迹识别当中。Wirtz[5]、Martens和Claesen[6]等人先后研究了DTW算法在笔迹识别中的应用。随着更深入的研究，很多研究者对DTW算法提出了各种改进算法，并得到了更好的认证效果。Hao Feng等提出采用规整特殊点的序列来代替DTW算法中对整个数据序列的规整，以提高规整的效率[7]。KarB提出了一种基于DTW的以笔段划分的多阶段匹配的方法[8]。胡金平等[9]通过限定弯折的斜率来减少计算量，从而提高效率。由于移动设备的传感器获取数据时可能会出现时间延迟的原因，目前已有的各種方法应用到移动平台上时，识别精度都会有所下降。因此，本文在结合了FastDTW算法中限定匹配路径弯折斜率的原理，并在路径搜索时自定义了一个路径搜索方式，同时放松起始端点的对齐，减少了路径匹配时的计算量以及占用的系统的空间，保证了识别效率和准确率。

2 算法原理

2.1 DTW基本原理

如图1中，定义一组时间序列相似性关系的连续元素集合，我们称之为规整路径W，这条路径需满足以下约束条件[10]：

1）边界条件：由于一个人的手写笔迹各部分的先后次序是不会改变的，因此所选的匹配路径必定是从左下角出发，在右上角结束。

2）连续性：匹配路径上某点只能和其相邻的点进行连接。这样可以保证参考模板R和待匹配模板T中的每个坐标都可能在时间规整函数上中出现。

3）单调性：弯曲路径起始点（m，n）的下一个起始点必定是（ m+l，n）、（m，n+l）或（m+l，n+l）3个点中的一个，因此路径是单调的。

设（m，n）为匹配路径中的一点，则根据DTW匹配路径规则，其下一个点为（ m+l，n）、（m，n+1）或（ m+l，n+l）中的一点，取点（m，n）到这3个点的距离最小的一点为下一个出发点，距离递推公式如下，

本文的DTW算法是在DTW经典算法基础上自定义了路径搜索方式，放松了算法匹配路径中起始端点对齐的限制，由于移动平台系统中绘制事件会阻塞触屏事件的采样，在采集手写笔迹信息的过程中会产生时间延迟，因此适当的放松起始端点的对齐可以提高笔迹识别的准确率。此外，本文算法为了保证识别效率，还结合了FastDTW算法中的限定搜索路径弯曲斜率。

2.2本文算法实现原理

2.2.1 算法路径搜索方式

本文针对DTW算法中的原始路径搜索方式、倾向横轴的搜索方式、倾向竖轴的搜索方式，提出了一种如图2的路径搜索方式。

这种路径搜索方式始终保证路径从左下角出发，右上角终止。由于避免了路径向横轴和竖轴倾斜，可以减少路径匹配的计算量，从而提高了笔迹识别的效率。

2.2.2 放宽起始端点的对齐限制

DTW算法的端点对齐如图4所示。

从图3中可以看出模板T中端点a的最佳对齐点是模板R中的a。但由于移动平台系统采样具有延迟性而且数据库模板长度和待匹配模板长度大都不同，使得模板T中的端点a极大可能的匹配对齐到模板R中的端点b'。因此，适当的放松端点对齐限制，可以提高端点对齐的准确率，从而提高识别精度。对起始端点的对齐放松了k个点，设定k的范围为（2，5）。路径匹配的起始端点范围可以在横轴或者竖轴（1，k）上。

2.2.3 匹配路径约束范围

本文算法结合了FastDTW算法中模板匹配限定匹配路径的斜率（如图4）的方式，并适当放松了起始端点的对齐。参考FastDTW算法原理，本文匹配路径斜率区间限定为[l/k，k]，k为起始端点放松的额度。如图5所示。

匹配路径的约束范围为图6中虚线所包含的区域。根据FastDTW算法中匹配路径约束条件可知，虚线之外的格点的值是不需要计算的，这样

通过给定的起始端点放宽额度，从而可以得到限定的匹配路径斜率，进而能够获取路径匹配时的搜索范围。在搜索边界范围内找到最短路径，得到两个模板之间的失真度和阈值比较，从而判断动态笔迹的真实性。

2.2.4 算法描述

根据采样获得的笔迹信息包含了笔迹的坐标（x，y）和时间（t）。本文选取样本的全部采样点进行动态时间规整。两个笔迹采样点间的距离公式定义如下：

Step 6根据式（3）计算模板的累积失真度。

Step 7 将计算出来的总体失真度与阈值S比较，如果小于阈值，则判定为真实笔迹;否则，判定为虚假笔迹。

3 实验设计

动态笔迹识别过程包括训练阶段和匹配阶段，训练阶段包括手写笔迹数据采集、笔迹信息预处理、笔迹特征提取和建立模板特征数据库;匹配阶段包括手写笔迹数据采集、笔迹信息预处理、笔迹特征提取、模板匹配和结果判决。动态笔迹识别流程图如下所示。

动态笔迹识别训练阶段：

1）动态笔迹数据采集，利用移动设备上自带的传感器获取手写笔迹数据，建立动态笔迹数据库。由于条件限制，本文借用SVC 2004国际手写笔迹识别竞赛的测试数据库。由于该手写笔迹数据库包含中文和英文两种手写笔迹，并且此数据库是在相同的标准数据库和规则下建立的，该数据库对不同的笔迹识别算法的性能比较更具有说服力，因此本文算法的实验验证将采用此数据库。

2）预处理，对笔迹进行旋转、平滑处理、去噪以及大小和位置归一化等，由于移动平台系统对触屏事件的采样率过低，因此还需对笔迹进行重采样。

3）特征提取，提取手写笔迹中能体现出手写者的书写风格，同时又相对稳定的特征。本文提取的特征是动态笔迹的坐标值（x，y）和时间t。

4）模板特征数据库建立，SVC 2004国际手写笔迹识别竞赛的测试数据库中包含100个人手写笔迹数据，其中每个人的包含20个真实手写笔迹和20个熟练伪造笔迹。每个手写笔迹的文本数据首行表示笔迹序列的长度，然后采集并记录各个采样点的信息，包括横坐标、纵坐标和采样点对应的时间t等。

5）模板匹配，将待测笔迹的特征与真实手写笔迹特征进行匹配，通过本文算法计算累积失真度。

6）结果判决，将计算出的总失真度与阈值计较来判断笔迹的真实性。阈值通过实验数据来确定。

4 实验结果与分析

实验选择FRR（错误拒绝率）和FAR（错误接受率）作为评判算法性能的标准。

在实验中，由于起始端点放松额度k是可变的，因此实验应先确定k的取值。图7所示为k取不同值时，FRR和FAR的变化曲线。从图7中可以看出，当k>5时，曲线处于稳定状态，算法的识别精度趋于稳定。而从放宽起始端点对齐限制的原理可知，放松额度k的值越大，则表示算法路径搜索的范围越大，从而使得算法的计算量越大。因此，本文算法中k的值选取为因此，本文算法中k的值选取为（2，5）。

本文实验主要将本文算法与经典DTW算法和FastDTW算法进行测试比较，三种算法的识别效果比较如表1所示。

通过实验数据可知，本文算法的FRR和FAR分别为6.33%和4.13%，比经典DTW算法要高，但是在效率上经典DTW算法;而比FastDTW算法的实验结果要低，且效率上相差不大，证明了本文算法的合理性和可行性。

5 结束语

针对在移动平台上识别手写笔迹的问题，提出一种基于DTW的动态笔迹识别算法。算法通过放松笔迹模板匹配时的起始端点对齐限制，提高了识别准确率;并通过约束路径搜索方式和限定匹配路径斜率提高了识别效率。

算法在实际应用过程中还存在一些局限性。本文动态笔迹识别时阈值对FRR和FAR有一定的影響;算法对于跨设备采集的信息识别还不能达到要求。未来将继续针对这几个方面进行研究。

参考文献

[1]栾方军，程海，宋晓宇，基于HMM的在线手写签名认证系统设计与实现[J].计算机应用与软件，2008，06：78-80.

[2] 王珂敏，基于DTW改进算法的在线签名鉴别方法[J].科技导报，2010，28（13）：101-104.

[3]许楠，基于神经网络的在线手写签名验证方法研究[D].武汉理工大学，2006.

[4] 王容霞，基于SVM的在线手写签名认证研究[D].武汉理工大学，2013.

[5] WIRTZ B.Stroke-based time warping for signature verifica-tion[C]// International Conference on Document Analysisand Recognition. IEEE，1995：179 -182.

[6]MARTENS R，CLAESEN L.Incorporating local consistencyinformation into the online signature verification process[J].Journal of Bacteriology，2007，189（ 24）：9076 - 81.

[7]HAO F，CHAN C W. Online signature verification using anew extreme points warping technique[J]. Physics LettersB，1995，355（s1-2）：27-31..

[8] KAR B，DUTTA P K，BASU T K，et al.DTW Based Verifi-cation Scheme of Biometric Signatures[C]// IEEE Interna-tional Conference on Industrial Technology. 2007：381- 386.

[9]胡金平，陈若珠，李站明，语音识别中DTW改进算法的研究[J].微型机与应用，2011，30（3）：30-32.

[10]KEOGH E J，PAZZANI M J.Derivative Dynamic TimeWarping[C]，'/ SIAM International Conference ，2002.

[11]SHIN J. OKUYAMA T. Detection of alcohol intoxicationvia online handwritten signature verification[J]. PatternRecognition Letters，2014 ，35（ 35）：101 -104.

[12]BHATTACHARYA I，GHOSH P，BISWAS S. Offline Sig-nature Verification Using Pixel Matching Technique[J].Procedia Technology，2013 ，10（1）：970 - 977.

[13]刘静，王儒.曲金玉.等，基于DTW改进算法的孤立词语音识别仿真[J].山东理工大学学报：自然科学版.2013. 27（01）：63-66.

[14]徐贵力.赵妍，姜斌.等，基于局部尺度特征描述和改进DTW技术的局部轮廓匹配算法[J].电子学报.2016. 44（01）：135-142.

[15]李成华.龚良慧.江小平.等，基于EMD和SVD的在线手写签名特征提取方法[J].中南民族大学学报：自然科学版.2016，35（01）：103-107+113.

[16] 申麗敏，语音翻译信号数字模型的构建及DTW算法的改进[J].计算机光盘软件与应用.2015，18（02）：70-72.

[17]王剑.马书月，基于几何中心静态手写签名的识别算法研究[J].计算机应用研究.2012，29（03）：1149 1151.

[18] 艾茜，基于速度和压力分区的在线手写签名验证[D].武汉：武汉理工大学.2012.

[19] 罗勇军，基于优化DTW算法的在线手写签名认证系统研究与设计[D].广州：广东工业大学.2014.

[20]黄申文，在线手写签名认证技术的研究与应用[D].南京：南京航空航天大学.2010.

[21] 罗琼，智能手机在线手写签名认证系统设计[D].武汉：武汉理工大学.2014.