基于离散F距的在线手写签名认证算法

1、基于离散F距的在线手写签名认证算法    摘  要  提出了一种新的在线手写签名认证算法。该算法将参考签名和测试签名曲线中特殊点的位置坐标分别提取出来，求出其离散F距，再进行判决。在算法中引入了签名曲线中特殊点的平移和删除等技术，使得匹配效果增强。     关键词  签名认证；离散F距；判决  1  引言    随着网络的普及，安全问题越来越突出。如何准确地鉴定一个人的身份，保护信息安全是当今信息化时代必须解决的一个关键问题。目前，指纹识别、语音

2、识别和签名识别在信息安全领域应用的较为广泛。而手写签名认证技术与其它身份认证技术相比具有明显的优点：与指纹、语音等其它生物学特征识别相比成本较低，并且不需要专门而且复杂的采样设备。与传统的密码、口令识别技术相比较，又不会丢失遗忘。因此，签名认证技术将会在信息安全领域有着广阔的前景。     从20世纪80年代起，有很多学者都致力于研究签名认证的算法。随着计算机科学技术的发展，签名认证的算法主要有特征值法和函数法两大类。比较有代表性的有：Mohankrishnan和Paulik提出了一个基于自回归(Autoregressive)模型的签名认证方法2。而Yang和Wi

3、djaja提出了隐马尔可夫模型(Hidden Markov Model)法3。20世纪90年代后期，一些研究者以签名波形跳变点的能量5为特征，将动态时间规整方法应用于签名的匹配。最近武汉理工大学的郑建彬教授提出了一种基于演化计算的签名认证算法4，该算法将参考签名分割成曲线段，以一定长度的搜索窗在测试签名曲线上进行动态搜索，实现与参考签名曲线段自适应的动态分割与匹配。     由于签名的特征的多样性，在签名中取何种特征，至今还没有定论。而对于函数法，由于每个人的签名都有很大的随意性，且将签名用函数表示十分复杂。因此，目前很难提出一个较好地评判签名相似度的准则，从而给

4、比较测试签名和参考签名相似度带来很大困难。本文给出了一种新的关于曲线相似性的定义，并且利用了离散F距1(Discrete Fr´echet Distance)作为距离的测度，提出了一种新的在线手写签名认证算法。该算法以签名曲线的离散F距作为评判准则来比较测试签名和参考签名的相似程度，建立数学模型，利用了签名曲线中特殊点的平移和删除等技术，提高了算法的效率，收到了较好的效果。 2  基于离散F距的签名认证算法     离散F距的数学定义如下：     定义1：给定两参数曲线f:0,1R2和g:0,1R2，它们之间的F

5、rechet距离的定义如下： 其中，涉及到所有连续非减的实函数且(0)=(0)=0 ，(1)=(1)=1  。     定义2：给定一个有n个至高点的多边形链p<p1,p2,.pn>，一个沿着p的k步，分割p的至高点成为k个不相交的非空子集，使得和。     给定两个多边形链，一个沿着A和B的组合步是一个沿着A的k步和一个沿着B的k步组成，使得对于，要么，要么 (就是说Ai，Bi中有一个恰好包含一个至高点)。     一个沿着链A和B的组合步W=(Ai,Bi)的花费(cost)就是

6、则链A和B间的离散F距就是 这个组合步W=(Ai,Bi)称为链A和B的Frechet排列。 3  算法的设计与实现    在线签名认证系统分为硬件采集数据和软件验证两个部分。硬件部分是通过手写板实时采集书写人的签名信息，签名的采样时间为每隔10ms采样一次。除了可以采集签名位置信息，还可以记录书写时的速度、运笔压力等动态信息。通常情况下我们使用的比较多的是手写板上采集到的X坐标、Y坐标、压力值等信息。图1是某人的签名和其对应的X坐标曲线。 图1 参考签名和测试签名X轴坐标对应曲线     假设参考签名提取出的特殊点(这里以波

7、峰点为例)有 个，记 ；测试签名提取出的波峰点有 个，记为 ；且 。以峰值点少的集合 为基准，利用Frechet排列的定义将峰值点多的集合 分成 部分，而这种划分假设有 种( )，则集合 和 的 种Frechet排列 。由于对于 ，要么 ，要么 (也就是说 ， 中有一个恰好包含一个峰值点)，且若 ， ，则 ， 。即是上一步的划分会直接影响到下一步的划分。 3.1  搜索空间的确定    在判断相似性的时候，如果两条曲线是相似的话，那么其中参考签名曲线的第 个峰值点只可能与测试签名的对应的第 个峰值点或其相邻的峰值点相关，故在签名认证算法中设定的搜索空间是

8、参考签名曲线的第 个峰值点只可能与测试签名曲线的对应的第0个峰值点(参考签名的第 个峰值点可能为多余的峰值点)、第 个峰值点、第 个峰值点、第 个峰值点对应匹配。这种方法实际上是利用了特殊点的平移和删除技术，压缩后的搜索空间如下：     在A和B的k种Frechet排列中对于任意一种 3.2  基于离散F距的判别签名曲线相似性的算法：    离散F距用于签名认证的算法如下：     (1)假设参考签名提取出的特殊点(这里以波峰点为例)有 个，记 ；测试签名提取出的波峰点有m个，记为，且mn。若

9、n-m>5，则认为参考签名和测试签名不相似，算法结束；否则执行下一步。     (2)以参考签名提取的峰值点序列A 为基准，其共有 m个波峰点；然后将集合B 的n 个峰值点分为m 部分，根据搜索空间的范围，然后找出所有满足条件的划分，假设有k 种划分情况( kR)，在每一种划分(或Frechet排列) 中， 集合B的每一部分均与集合A的每一个峰值点对应求距离。这里的峰值点之间的距离定义为 ，两个签名的每一部分的特殊点将各自对应进行匹配，选择出每一部分内部的所有对应点之间的最大距离。根据组合步的数学定义，求出每一种划分方法中的 部分距离的最大值，即  

10、;   (3)找出所有划分方法中的距离的最小值，选择出一种最佳的划分方法(即是求出最小的距离)。     (4)用此种划分对波峰和波谷分别进行研究，得出两个波峰间的最小距离和两个波谷间的最小距离；对于给定的阈值，则判定两条曲线相似，否则判定两条曲线不相似。如果越小，表示参与匹配的参考签名与测试签名的距离越小，即它们的相似度越高。     基于离散F距算法的流程图如图2所示。 图2  基于离散F距算法的流程图     同时根据以上算法求出参考签名和测试签名的波谷点的离散F距和判

11、决门限比较，若，则可以判定测试签名和参考签名匹配。 4  实验结果分析    为了初步判别出不同人的签名，需要对参考签名和测试签名进行特殊点的归一化。在初步匹配阶段，需要将提取出的特殊点的集合以第一个特殊点为基准进行位置归一化，使两条签名曲线的第一个特殊点的位置坐标重合。在匹配过程中设置当波峰点的最优值和波谷点的最优值均大于门限E时，则判定两个签名不匹配。 图3  某人的两次签名归一化前和归一化后的峰值点的曲线 (两个签名均有17个峰值点)     通过对同一个人的真实签名、不同人的签名、随机伪造签名和熟练伪造签名

12、做实验对比，可以初步设置判决门限 =150，E=900。     如果，表示参考签名和测试签名匹配。     表1选取的是签名样本库中的同一个人的若干次签名，在全局范围内求出他们的的最优值dmin，并与匹配门限比较，判断是否匹配。表1  某人10个真实签名的X坐标曲线的匹配情况   zeq01.h zeq02.h zeq03.h zeq04.h zeq05.h zeq01.h 0         zeq02.h 2 0       zeq03.h

13、 265 29 0     zeq04.h 71 88 168 0   zeq05.h 174 114 356 103 0 zeq06.h 6 8 95 89 121 zeq07.h 28 18 33 215 65 zeq08.h 30 70 83 71 71 zeq09.h 50 74 74 96 100 zeq10.h 120 67 64 88 60     从表1中可以看到，某人的真实签名的认证率达到了85.71%。在真实签名样本库中，对真实签名的认证率达到了88%。在熟练伪造签名样本库中，对于熟练伪造签名的验证率达到了80%。

14、在随机伪造签名样本库中，对于某人的随机伪造签名的验证率达到了88%。比较离散F距和演化计算这两种方法，它们对伪造签名都有着较高的验证率。相比之下，基于离散F距的算法在计算机中运行的效率比演化计算要高，而且其时间复杂度比演化计算要低。     在以前的研究中，有些研究者将演化计算的思想用于在线手写签名认证中，通过实验得到了比较理想的结果，误拒率和误纳率均可以控制在10%以下，但是其时间复杂度比较高。同时在保证有着较高的验证率的前提下，离散F距相对于演化计算和连续F距有着较低的时间复杂度，并且提高了整个签名认证系统的运行效率，有效地减少了系统运行的时间。 5 

15、0;结语    本文将离散F距应用到在线手写签名认证中，提出了一种新的判别签名相似度的准则，并对整个算法进行了初步的研究。由实验分析，离散F距算法应用到签名认证中，加快了签名的验证速度，使签名认证算法的运算结果有了较大提高，实验结果证明了该方法的可行性。利用离散F距的思想，只考虑签名曲线中特殊点的坐标特征，因此这种方法相对于神经网络和演化计算等方法，它的时间复杂度要低的多。     但是该方法还有一些问题需要解决。例如目前的算法在特殊点序列的匹配过程中，对于中间的部分冗余的特殊点没有删除，导致在某些情况下搜索到的全局范围内的最优值与实

16、际情况下的最优值产生了一定的误差，因此还需要对算法进一步改进和完善；同时对于签名曲线中特殊点的其它特征如压力、握笔倾斜度、局部加速度等并未深入考虑。 参考文献1Minghui Jiang，Ying Xu，Binhai ZhuProtein Structure-Structure Alignment with Discrete Fr´echet DistanceJuly 9，2007：p 1-12 2Mohankrishnan N， Paulik M J， and Khalil M. On-line signature verification using a nonstationar

17、y autoregresssive model representation. IEEE Int. Sym. On Circuits and Systems，1993，2：p 2303-2306. 3L. Yang，B.R. Widjaja，R. PrasadApplication of Hidden Markov Model for Signature VerificationPattern Recognition，1996，28(2)：p 180-188 4Zheng Jianbin，Zhu GuangxiNew algorithm for on-line handwriting sign

18、ature verification based on evolutionary computationWuhan University Journal of Natural Sciences，v 11，n 3， May， 2006：p 596-600 5Zheng Jianbin，Zhu GuangxiOn-line handwriting signature recognition based on wavelet energy feature matchingProceedings of the World Congress on Intelligent Control and Automa