作者简介：朱洁（1983-），女，硕士研究生，主要研究方向：智能计算、模式识别；彭晓琳（1982-），女，硕士研究生，主要研究方向：智能计算、模式识 别；黄樟灿（1960-），男，教授，主要研究方向：智能计算、模式识别。
收稿日期：2008-05-06 修回日期：2008-08-12
朱 洁，彭晓琳，黄樟灿：一种新的在线手写签名认在
很大的误差。因此，需要对两条曲线进行分段，再进行逐段匹
配。在分段匹配中必须对某段进行平移和伸缩变换，经变换后
乙 i i
xi+1
i
i
的距离定义为：d（f1 ，f2）= xi |kf1（ax+b）+h-f2（x）|dx；其中 k 和 h
分别是垂直方向上的伸缩比例和平移分量。
178 2008，44（31）
Computer Engineering and Applications 计算机工程与应用
◎图形、图像、模式识别◎
一种新的在线手写签名认证算法
朱 洁，彭晓琳，黄樟灿 ZHU Jie，PENG Xiao-lin，HUANG Zhang-can
武汉理工大学 理学院，武汉 430070 Wuhan University of Technology，Wuhan 430070，China E-mail：jessy5242@
信号，比较参考签名与测试签名是否匹配，就是要比较参考签
名和测试签名对应的两对曲线是否能够匹配，可以根据两条曲
线的相似性来确定。
乙c1
定义 1[3] 给定函数 f（1 x），f（2 x），称 d（f1，f2）= |f（1 x）-f（2 x）|dx c0
为两个函数之间的距离，[c1，c2]为函数的定义域；如果对于给定 的值 ε，d（f1，f2）≤ε；则称 f（1 x）、f（2 x）相似，否则称它们不相似。
的非空子集{Pi}i=1，…，k，使得
P =<p i
ni-1 +1
，…，pni>和
0=n0<n1<…<nk=n；
（2）给定两个多边形链 A=<a1，…，am>，B=<b1，…，bn>，一个
沿着 A 和 B 的组合步是一个沿着 A 的 k 步{Ai}i=1，…，k 和一个沿
着 B 的 k 步{Bi}i=1，…，k 组成，使得对于 1≤i≤k，要么|Ai|=1，要么
的至高点划分成 k 部分，使得每一部分中有一条曲线至少含有
一个至高点。这里的 Fréchet 排列其实是一个 NP 困难问题。假
设有测试签名和参考签名提取出的特殊点（这里以至高点为
例） 组成的曲线 A、B，分别找出曲线的至高点将它们表示成
A=<a1，…，am>，B=<b1，…，bn>，且 m≤n（a1，…，am 是链 A 的 m 个至高点，b1，…，bn 是链 B 的 n 个至高点），那么则以峰值点少 的链 A 为基准，利用 Fréchet 排列的定义将峰值点多的链 B 划
ZHU Jie，PENG Xiao -lin，HUANG Zhang -can.New algorithm of on -line handwriting signature verification .Computer Engineering and Applications，2008，44（31）：178-181.
签名认证的算法主要有特征值法和函数法两大类。比较有 代表性的有：Mohankrishnan 和 Paulik 提出了一个基于自回归 （Autoregressive）模型的签名认证方法[1]。而 Yang 和 Widjaja 提
出了隐马尔可夫模型（Hidden Markov Model）法[2]。郑建彬等人 提出了一种基于演化计算的签名认证算法[3]，该算法将参考签 名分割成曲线段，以一定长度的搜索窗在测试签名曲线上进行 动态搜索，实现与参考签名曲线段自适应的动态分割与匹配。 在算法中引进了演化计算中的分级和加速技术，使算法的搜索 速度和匹配效果有了一定程度的提高。实验结果表明了该算法 的有效性。但是由于签名的特征的多样性，在签名中取何种特 征，至今还没有定论。而对于函数法，由于每个人的签名都有很 大的随意性，且签名曲线是由离散的点构成的，在判别过程中 要将曲线用函数的形式表达很困难，而且对于曲线的拟合有很 高的要求，最后还要将曲线进行平移和伸缩变换[4]，因此，目前 很难提出一个较好的评判签名相似性的准则，从而给比较测试 签名和参考签名相似度带来很大困难。目前 Hausdorff 距离被 广泛的应用于判断两个点集间的相似性，而 Alt 和 Godau 两人[5]
摘 要：提出了一种新的在线手写签名认证算法，着重研究签名曲线中的特殊点的匹配情况。该算法将签名曲线中特殊点的位置 坐标提取出来，然后提取出特殊点中的关键特征至高点与至低点，并且用离散 Fréchet 距离作为距离的测度来对至高点与至低点 进行研究，提出了一种新的关于曲线相似性的定义，并且在这种定义的基础上建立了一种新的判断签名曲线相似性的数学模型， 此模型中隐含了对签名曲线的平移和伸缩变换。由于模型的求解是一种 NP 困难问题，针对这种情况，提出了一种新的多项式的求 解算法，最后通过对实验结果的分析验证了此算法用于签名认证的有效性，且适用于判别离散曲线的相似性。 关键词：签名认证；离散 Fréchet 距离；组合步；Fréchet 排列 DOI：10.3778/j.issn.1002-8331.2008.31.051 文章编号：１００２－８３３１（２００8）31-0178-04 文献标识码：Ａ 中图分类号：TP391
dF（A，B），这个组合步称为链
A 和 B 的 Fréchet 排列。
由于离散 Fréchet 距离仅仅能够考查峰值点间的距离，对
于判断曲线的相似性方面是远远不够的，故本文提出了新的判
断曲线相似性的定义。
定义 4 设 A=<a1，…，am>，B=<b1，…，bn>为两条由离散点组
1
2
成的曲线，称 dF 为它们的至高点间的离散 Fréchet 距离，dF（A，
2008，44（31） 179
提出的连续 Fréchet 距离则被用来研究两个连续曲线相似性， Eiter 和 Mannila 两人[6]在连续 Fréchet 距离的基础上提出了离 散 Fréchet 距离的定义，而江明辉等人将其运用到了判断蛋白 质的结构排列中去，收到了一定的效果[7]。在签名曲线的特殊点 中提取出关键特征至高点与至低点，并且用离散 Fréchet 距离 作为距离的测度来对至高点与至低点进行研究，提出了一种新 的关于曲线相似性的定义，并且在这种定义的基础上建立了一 种新的判断签名曲线相似性的数学模型，此模型中隐含了对签 名曲线的平移和伸缩变换，最后针对签名认证提出了具体的算 法。该算法相比于其他的签名认证算法有着显著的优点，相对 于将整条签名曲线进行匹配的方法，通过在计算机上运行的结 果分析，它有着较低的时间冗余度。实验表明，该方法提高了算 法的效率，收到了较好的效果。
B）为它们的至低点间的离散 Fréchet 距离；如果对于给定的值 ε，
1
2
|dF（A，B）-dF（A，B）|≤ε；则称 A、B 相似，否则称它们不相似。
2.2 基于离散 Fréchet 距离的判别签名曲线相似性
的算法设计
在离散 Fréchet 距离定义中有个关于 Fréchet 排列的定义，
如果用在判断两条签名曲线的相似性的时候，即是把两条曲线
Abstract：In this paper，a new algorithm of on-line handwriting signature verification is proposed.Our researches are mainly on the matching of special points of signature curves.The authors pick up the position coordinates of the special points in signature curves first，and then pick up the key characters vertices and rock bottom from the special points.The authors take the discrete Fréchet distance as the distance measurement and introduce a new curves similarity definition.The authors present a new mathematical model for the signature curves similarity judgment，which implies carrying on the translation and the stretching to the curves.Because the model solution is one kind of NP difficult problem，the authors propose one kind of new multinomial solution algorithm，and finally take online handwriting signature verification as example to confirm the mathematical model.The experimental result confirms the validity of this method in the signature verification，and it is also used to the discrete curves similarity judgment. Key words：signature verification；discrete Fréchet distance；paired walk；Fréchet alignment