用于手写签名识别的演化超网络

王 进，谢水宁，颉小凤，LEE Chongho，陈乔松，邓 欣

(1.重庆邮电大学 计算智能重庆市重点实验室，重庆 400065；2.Department of Information and Communucation Engineering, Inha University, Incheon 402-751, Korea)

0 引 言

生物特征认证技术凭借其可靠性、稳定性以及唯一性，已成为身份认证领域的一个研究热点。生物特征认证技术是指利用人固有的生理特征或行为特征进行个人身份认证的技术，主要包括指纹、虹膜、人脸、声音等认证技术，尽管这些生物特征认证技术已有部分实用产品，但其必须有专门的设备，成本高，不易普及使用。而手写签名[1-2]是被大众普遍接受的社会行为，是众多基于生物特征认证系统最自然和最友好的方式，是一种利用人的签名这种行为特征进行身份鉴定的技术。通常手写签名认证技术主要分为在线和离线2种方式[3]。离线手写签名认证因其只采集签名的静态特征，处理签名的形状来鉴定签名，忽略了速度、压力等动态特征，给离线签名认证系统带来了特征提取困难、易模仿等问题。与此相反，在线手写签名认证则可以采集签名的笔顺、速度、位置和方向等动态信息与真实签名样本进行对比，以实时鉴定手写签名的真伪，具有操作简单、难模仿等特点，所以比离线签名更容易鉴定，精确度更高。

目前，比较常见的在线手写签名认证方法主要有神经网络(neural network，NN)、动态时间弯曲(dynamic time warping，DTW)、隐马尔可夫模型(hidden markov model，HMM)等。神经网络[4]因其良好的非线性映射特性，易自我改进和学习的优点，使得该算法很容易为签名认证系统增加学习特性，以适应签名者的书写风格。神经网络针对在线英文手写签名认证已得到很好的应用[5]。为了提高手写签名安全性，克服单一模型的缺点，Alhaddad等[6]将概率模型和神经网络2个模型进行结合，提出了BPNN/PM模型；针对手写体汉字具有类别多、结构复杂、相似字多、字形的多样化等特点，Yang等[7]借助深层卷积神经网络强大的特征表达能力，对汉字手写签名进行鉴定，在一定程度上降低了错误率。然而，由于神经网络提取有限的结构特征和动态特征，很难适应手写体的复杂性和多样性，达不到理想的匹配结果；动态时间弯曲[8]是一种基于动态规划思想的非线性优化算法，并在签名认证系统中得到很好的应用[9-10]，但其算法过于复杂，且效果没有明显优于其他算法。经典的DTW算法是基于欧几里德距离实现样本分类，然而欧几里德距离对特征矢量的各维度是平等对待的，且忽略了签名时间序列长度的影响以及局部差异的重要性，同时使得部分真实样本由于偶尔出现的畸变点而被拒绝；隐马尔科夫模型能够很好地描述时间连续的动态过程，专门针对语音识别和汉字识别等领域而提出，由于签名数据具有语音信号某些相似的性质，因此，HMM模型被引入到在线签名识别领域[11]，但其算法识别率不高，训练收敛时间较长。本文使用一种新的签名认证方法──演化超网络(evolutionary hypernetwork)来对手写签名进行鉴定。

超网络(hypernetwork)是受生物分子网络启发而建立的一种基于超图(hypergraph)的认知学习模型[12]，由大量的超边组成。超网络演化学习过程，是通过不断地对超边进行匹配、选择、放大，从而准确拟合训练数据，挖掘出特征间的高阶相关性。超网络具有流体性、可重置的分子结构，能够有效模仿人类认知学习过程。目前，超网络在模式识别领域已得到广泛应用[13-14]。王进等[15]提出了一种结合最优类别信息离散(optimal class-dependent discretization，OCDD)的细粒度演化超网络算法，旨在解决超网络只能处理二值化数据的缺陷；孙开伟等[16-17]为了解决多标签分类问题，通过扩展传统超网络模型提出了一种多标签超网络的算法(multi-label hypernetwork，MLHN)；Choi等[18]提出了一种基于超图融合语义信息子网标识的场景分类算法，通过利用超图挖掘语义信息间的高阶关联特性对场景进行分类。本文将超网络引入到手写签名认证中，提出了一种基于演化超网络的手写签名认证方法，通过对签名者的笔迹进行真伪判断是否为本人真实签名。

1 方法介绍

基于演化超网络的手写签名识别系统的学习过程，主要是对采集到的签名样本不断地进行选择、放大和匹配。在采集签名样本特征过程中，为了平滑噪声、构造出可读性强的笔迹特征集，采用了向量化和平滑采集点的方法对签名样本进行预处理，从而提取出位置和方向特征属性；采用演化超网络模型对笔迹特征集进行学习分类，尝试提升模型在小样本训练集下的泛化能力，挖掘签名样本之间的高阶关联性。图1为在移动终端实现的手写签名识别系统流程。由图1可知，签名认证过程可分为2个步骤：①签名注册，即根据用户训练样本建立签名模型；②签名认证，即利用给定的超网络模型判别待认证签名的真伪。

图1 系统流程图Fig.1 System flow diagram

2 签名样本处理流程

2.1 预处理

对签名样本数据预处理包括向量化、平滑等步骤。向量化旨在对提取有效的笔迹特征，增强特征数据的可读性；平滑旨在平滑噪声笔迹，从而构造出能够适应于超网络分类器的签名特征集。

2.1.1 向量化

为了方便记录签名笔迹的位置，将手写签名面板划分为50×50的网格，从落笔点开始采集样本。在获取手写签名的过程中，通过判别位置点是否有落笔来判断是否存在笔迹特征，用‘1’表示该网格存在笔迹特征属性，‘0’表示无笔迹特征属性，并记录样本特征值为‘1’的点坐标(x,y)。签名者在签名鉴定面板上签名，记录并获取笔迹点位置坐标的过程如图2所示。

图2 获取手写签名面板特征点坐标过程Fig.2 Get feature point process from handwritten signature board

2.1.2 平 滑

平滑是在线手写签名认证中广泛采用的数据预处理方法之一，其主要目的是去掉各种噪音和失真，降低对特征提取产生的干扰。本文采用五点三次平滑公式对坐标点数据进行平滑，利用多项式的最小二乘法逼近对采样点实现平滑滤波。

设n个等时间间隔ti(i=0,1,…,n-1)上的坐标点数据为Y(t)0,Y(t)1,…,Y(t)n-1，则可在每个数据点的前后各取2个相邻的点，用三次多项式Y(t)=a0+a1t+a2t2+a3t3进行逼近。用最小二乘法来确定方程(t)中的待定系数，令

(1)

可得到五点三次平滑公式为

(2)

(3)

(4)

(5)

(6)

对于笔划中间的数据点，采用(4)式进行平滑，对于笔划开头的点用(2)式和(3)式进行平滑，对于笔划结束的2点则用(5)式和(6)式进行平滑。

2.2 特征提取

特征提取是签名认证的关键，能反映签名者的个人独有信息，所以能区别于签名伪造者。在模仿过程中，虽然仿造者容易模仿出真实签名者的签名形态，但对于笔迹的位置、方向、速度、压力等因个人签名习惯而形成动态特征则难以模仿。本文主要提取签名的位置和方向特征。

2.2.1 位置特征提取

笔划位置参数包括随时间变化的x和y坐标，能够表征签名位置随时间变化趋势。从落笔点开始到结束，签名按等时间间隔划分成50段，并记录每一段的位置坐标(x,y)，从而得到横纵位置坐标序列x(i)和y(i)，其中，i=0,1,…,49，通过(7)式计算得到位置特征Pi。由于在线签名是一个动态的过程，每次签名的位置也不同，从而导致即使同一用户签名，其采集到的位置特征也不同。

(7)

2.2.2 方向特征提取

将签名鉴定面板的平面空间划分为8个区域，每个区域代表一个方向，即可构造平面方向向量图如图3所示。其中，不同象限和不同角度的取值范围如表1所示，每个区域的大小为45°。

图3 平面方向向量图Fig.3 Plane direction vectors diagram

将每个样本按等时间间隔划分为50段，每一段代表一个方向向量特征，即方向向量代表了该样本每一段笔划在此处的倾斜值，因此，利用最小二乘法拟合出来的方程的斜率值进行反正切公式(8)计算，得到角度θi。将样本角度θi通过映射关系，映射到表1即可得到该方向角所隶属的方向向量区域，从而可得到签名方向向量特征集Di。

(8)

采集方向向量的过程如图4所示。其中，Xi为某一段提取出来的方向向量集，Yi为样本类别标签集，由于签名认证为二分类问题，因此，样本标签取值为{0,1}，表示不是本人签名或是本人签名，通过最小二乘法对各个片段进行拟合得到方向向量特征集。由图4可知，前4个签名为本人签名，最后一个为非本人签名。

表1 方向向量表Tab.1 Direction to the scale

图4 平面方向向量采集过程Fig.4 Plane direction vectors collection process

3 基于演化超网络识别手写签名

3.1 超网络的定义

超网络是超图[19]的推广，是由大量具有权值的超边(hyperedges)组成的任意超图结构。利用三元组H={V,E,W}表示一个超网络，其中，V={v1,v2,…,vn}为超网络n个顶点集合，E={e1,e2,…,em}为m条超边集合，W={w1,w2,…,wm}为m条超边的权值集合。超边e={vi1,vi2,…,vik,yi}由k个顶点及类别标识yi组成，其中，k(2≤k≤n)称为超边的阶数(order)，如果一个超网络中所有超边的阶数都为k，则这个超网络被称为k阶超网络。图5为一个包含8个顶点4条超边的超网络，在图5中，超边线条的粗细代表了超边权值的大小，线条越粗，权值越大。

图5 包含8个顶点4条超边的超网络Fig.5 Hypernetwork contains eight vertices and four hyperedges

3.2 超网络分类器

超网络可用作概率性的联想存储器[12]，通过演化学习将数据集以一定的概率检索出来，实际上代表输入样本X与输出类别Y的联合概率P(X,Y)，即样本X隶属于类别Y的概率，可根据点估计计算公式(9)得到。在分类过程中，通过计算样本X隶属于每个类别的条件概率y*，选取出条件概率值最大的类别作为分类结果，如(10)式和(11)式所示。该过程主要利用超边数量众多这一特性，使得分类能力具有较强的鲁棒性。

(9)

(10)

超网络分类器的分类步骤如下。

步骤1对超边集合L进行点估计，得到经验概率分布P(X,Y)；

步骤2输入训练样本Xi；

步骤3根据以下步骤对输入样本Xi进行分类。

①将X与L中所有超边进行匹配运算，并将与X匹配的超边放入集合M中；

②根据超边的类别标识，对集合M中的超边划分：类别为0的超边归类到M0中，将类别为1的超边归类到M1中；

3.3 基于演化超网络识别手写签名

采用演化超网络对签名样本进行分类时，超边库[15,17]决定了演化超网络的性能。在每次迭代过程中，超边经过不断地匹配、替代和放大操作对权值进行调整，从而形成一种能够再现训练数据的超网络。超网络演化学习算法流程如下。

输入:集合X：训练集；Y：类别数；t：每个样本生成的超边数；k：超边阶数；w：超网络学习率。

输出:超边库L。

步骤1初始化超边库。

fori=1 tondo

样本Xi生成t条k阶超边，置每条超边的fitw=0，fitc=0，将超边加入L。fitw为超边不能正确分类训练样本的适应值，fitc表示超边正确分类训练样本的适应值。

end for

步骤2训练样本分类。

fori=1 tondo

若当前超网络模型正确分类样本Xi，则将Xi加入集合XC，否则加入集合XW；

end for

计算错误分类比例r=|XW|/|X|；

步骤3计算适应值。

fori=1 tondo

forj=1 tomdo

end for

fork=1 topdo

end for

end for

步骤4超边排序。

根据fitw将超边降序排序，对于fitw值相同的超边，将其按照fitc降序排序。

步骤5计算超边替代数目。

步骤6替换经过排序后适应值最低的substCnt条超边。

步骤7返回步骤2，直到substCnt=w×r×|L|substCnt=0。

用户签名样本的训练是针对二分类问题，通过对用户签名进行训练，对待测签名进行测试时，只需判别能否和训练库的信息进行匹配即可。因此，通过步骤1将提取后的笔迹特征字符串作为输入信息，并随机生成一个初始化超网络，即构造签名样本向量集，通过演化学习，阶数设为10，从而得到学习库样本。

从上述超网络的演化学习过程中可以看出，超网络的最大可能超边数目是2k×C(n,k)，其中，n为签名样本的特征维数，k为超边阶数。由于超网络演化学习过程中，超边的数目会随着输入空间的维数n增加而急剧增加，如果初始化后的超网络没有包含那些对分类重要的超边，则在演化学习过程中超网络的分类性能提升是非常有限的。基于此，本文采用超边替代的演化学习方法来演化学习低阶超网络(演化学习步骤5)，把那些适应值低的超边用新的超边替代，以搜索更大的解空间。如果步骤2的错分样本较多时，步骤5被替代的超边数目也越多，即被替代的超边数目与步骤2中样本错分的比例成正比关系。在步骤1中，每个签名样本生成相同数量的超边，为了防止超网络只对某些类别的样本有较好的分类效果，因此，步骤6随机选取与被替代的超边具有相同类别的样本来生成新的超边。步骤4对超边进行排序时，之所以考虑将超边按照其降序排序，是为了达到替代那些分类错误的超边的目的。

采用签名识别优化改进后的高效超边替代超网络分类器对笔迹特征进行学习分类，保存为离线低阶超边库，搜索具有决策能力的最佳超边，演化完成后的超网络能够利用大量具有决策能力的超边共同对样本进行分类，具体实现方式如图6所示。

图6 超网络的演化学习过程Fig.6 Learning process of evolutionary hypernetwork

4 实验结果和分析

4.1 样本数据采集

测试环境为Android 4.4.2，机型名称为华为荣耀X1，分辨率为1 200像素×1 920像素。

基于上述移动终端环境，分别对20个签名用户采集40个真实签名和20个伪造签名进行实验，即共采集到1 200个签名样本，包括800个真实签名和400个伪造签名，如表2所示。在实验过程中，应用每个用户的20个真实签名样本作为训练集，其余20个真实签名样本和20个伪造签名样本为验证测试集。

在签名验证过程中，签名伪造通常会有以下3种类型[8]。

1)简单伪造(simple forgery)：伪造者不作任何努力来模仿一个真正的签名，即按照伪造者书写风格进行伪造，但知道签名者的签名。

2)随机伪造(random forgery)：伪造者不了解原始签名的构造，并使用伪造者自身的签名进行随机伪造测试。

3)熟练伪造(skilled forgery)：伪造者可以看到签名者真正的签名，有时间来练习模仿并试图尽可能模拟真正签名。

本文主要以随机伪造和熟练伪造进行伪造签名测试，测试样本数分别为200个，如表2所示。

表2 20个签名者样本数据Tab.2 Algorithm flowchart of evolutionary hypernetwork

为了验证签名识别系统的性能，本文采用误拒率、误纳率、以及识别率[8]3个指标进行评价。其中，误拒率(false rejection ratio，FRR)是指当系统不能鉴定原始真实签名并拒绝伪造的尝试，被定义为发生虚假拒绝尝试鉴定的百分比；误纳率(false acceptance ratio，FAR)则指当系统出现错误接收伪造签名，把其视为真实签名进行鉴定，被定义为错误接收鉴定的百分比。由于本文签名伪造主要采取随机伪造和熟练伪造2种形式，因此，采用随机伪造误纳率(random FAR)和熟练伪造误纳率(skill FAR)分别评价2种形式下得到的误纳率，并通过均衡两者得到平均伪造误纳率(average FAR)；识别率(verification accuracy，VA)则指综合考虑了由于误拒和误纳行为导致出现的错分样本，而得到的正分样本占总样本的比例。各评价指标的计算公式为

(11)

(12)

(13)

(14)

4.2 结果对比分析

图7为某2个签名用户签名对比图。其中，图7a和图7e分别为用户原始签名数据；图7b和图7f为用户真实签名鉴定数据；图7c和图7g为随机伪造数据；图7d和图7h为熟练伪造数据。

通过超网络模型对所有样本进行测试，并分别记录每个签名用户的错误拒绝真实签名次数，错误接收随机伪造签名次数，以及错误接收熟练伪造签名次数，将所得数据通过(11)—(13)式计算得到FRR和FAR。图8为20个用户的FRR和FAR对比图，其中，横坐标表示用户所签名的文字，纵坐标为FRR和FAR的百分比。

图7 用户签名对比图Fig.7 Comparison diagram of the user signature

图8 用户FAR和FRR对比图Fig.8 Comparison diagram of FAR and FRR about user

结合图8的数据以及(14)式，可以得到20个签名用户的FRR，FAR和VA结果，如表3所示。其中，skill FAR比random FAR高出3.5%，主要是由于熟练伪造是在一定程度上对原始签名数据进行练习伪造。同时，通过random FAR和skill FAR可计算得出average FAR为3.75%，比skill FAR低31.82%，比random FAR高46.67%，因此，average FAR在一定程度上可表示random FAR和skill FAR。

在数据采集过程中，由于采集手段不同，即使使用同个分类器其鉴定结果也可能会导致不同。为了验证本文方法的泛化性，在同等条件下将其和目前流行的分类算法进行对比，本文采用了C4.5决策树算法(decision tree，DT)，朴素贝叶斯算法(naïve bayes，NB)，K近邻算法(K-nearest neighbor，KNN)，以及支持向量机算法(support vector machine，SVM)，其实现分别对应Weka机器学习开源项目所提供的J48，Naïve Bayes，IBk以及SMO算法[20-23]，实验结果如表4所示。

表3 误拒率，误纳率和识别率Tab.3 False rejection ratio, false acceptance ratio and verification accuracy %

表4 签名鉴定方法性能对比Tab.4 Method performance comparison of signature verification %

从表4可以看出，在手写签名识别系统中，虽然本文方法的FRR比SVM低，random FAR和SVM持平，但在其余性能方面均有所提升。且本文方法相比于DT，NB以及KNN 3种分类算法，在识别率、误拒率和误纳率等性能上优势明显。由此可见，相对于其他传统分类方法，在小样本数据下演化超网络具有较好的泛化能力，主要是因为超网络在演化学习过程中，利用了超边替代的方法，把分类效果差的超边用新的超边不断进行替换，从而使得演化学习过程中可以搜索到尽可能大的问题解空间。

5 结束语

本文基于演化超网络实现了一个手写签名识别系统。通过数据预处理，提取出能较好地反映签名者书写风格的签名特征集，验证了特征提取算法的可行性和可靠性；并对超网络分类算法的学习速度快、灵活性好、适应性高、结果可读性强等优点进行了实验验证。同其他传统分类方法相比，演化超网络具有较高的分类准确度。

参考文献：

[1] RADHIKA K S, GOPIKA S. Online and offline signature verification: a combined approach[J]. Procedia Computer Science, 2015, 46(2): 1593-1600.

[2] CPALKA K, ZALASINSKI M, RUTKOWSKI L. New method for the online signature verification based on horizontal partitioning[J].Pattern Recognition, 2014, 47(8): 2652-2661.

[4] DU Jun, ZHAI Jianfang, HU Jinshui, et al. Writer adaptive feature extraction based on convolutional neural networks for online handwritten Chinese character recognition[C]//IEEE.Proceedings of the 2015 13th International Conference on Document Analysis and Recognition. Tunis: IEEE Press, 2015: 841-845.

[5] FALLAH A, JAMAATI M, SOLEAMANI A. A new online signature verification system based on combining Mellin transform, MFCC and neural network[J]. Digital Signal Processing, 2011, 21(2): 404-416.

[6] ALHADDAD M J, MOHAMAD D, AHSAN A M. Online signature verification using probablistic modeling and neural network[C]//IEEE.Proceedings of the 2012 Spring Congress on Engineering and Technology. Xi’an, China: IEEE Press, 2012: 1-5.

[7] YANG Weixin, JIN Lianwen, XIE Zecheng, et al. Improved deep convolutional neural network for online handwritten Chinese character recognition using domain specific knowledge[C]//IEEE.Proceedings of the 2015 13th International Conference on Document Analysis and Recognition. Tunis: IEEE Press, 2015: 551-555.

[8] FAUNDEZ Z M.Online signature recognition based on VQ-DTW[J].Pattern Recognition,2007,40(3):981-992.

[9] FISCHER A, DIAZ M, PLAMONDON R, et al. Robust score normalization for DTW based online signature verification[C]//IEEE.Proceedings of the 2015 13th International Conference on Document Analysis and Recognition. Tunis: IEEE Press, 2015: 241-245.

[10] 于宏斌,吴仲城,申飞.基于HMM/DTW两级结构的签名认证方法[J].模式识别与人工智能, 2010, 23(1): 107-114.

YU Hongbin, WU Zhongcheng, SHEN Fei. Signature verification algorithm based on HMM/DTW two level architecture[J]. PR & AI, 2010, 23(1): 241-245.

[11] SHAFIEI M M, RABIEE H R. A new online signature verification algorithm using variable length segmentation and hidden markov models[C]//IEEE.Proceedings of Seventh International Conference on Document Analysis and Recognition. Edinburgh, UK: IEEE Press, 2003: 443-446.

[12] ZHANG B T.Hypernetworks: A molecular evolutionary architecture for cognitive learning and memory[J]. IEEE Computational Intelligence Magazine,2008,3(3):49-63.

[13] SUO Qi, SUN Shiwei, Hajli N, et al.User ratings analysis in social networks through a hypernetwork method[J]. Expert Systems with Applications, 2015, 42(21): 7317-7325.

[14] RUCCO M, SOUSA R D, MERELLI E, et al. Neural hypernetwork approach for pulmonary embolism diagnosis[J]. Bmc Research Notes, 2015, 8(1): 1-11.

[15] 王进,张军,胡白帆.结合最优类别信息离散的细粒度超网络微阵列数据分类[J].上海交通大学学报, 2013, 47(12): 1856-1862．

WANG Jin, ZHANG Jun, HU Baifan. Optimal class-dependent discretization-based fine-grain hypernetworks for classification of microarray data[J]. Journal of Shanghai Jiaotong University, 2013, 47(12): 1856-1862.

[16] SUN Kaiwei, LEE C H, XIE Xiaofeng.MLHN: a hypernetwork model for multi-label classification[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2015, 29(6): 1550020-1-1550020-28.

[17] SUN Kaiwei, LEE C H, WANG Jin. Multilabel Classification via Co-evolutionary Multilabel Hypernetwork[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(9): 2438-2451.

[18] CHOI S W, LEE C H, PARK I K. Scene classification via hypergraph-based semantic attributes subnetworks identification[M].Germany: Springer International Publishing, 2014: 361-376.

[19] 王进,任小龙,孙开伟,等.HSV颜色空间下用演化超网络识别道路限速标志的研究[J]. 高技术通讯, 2013, 23(7): 679-684.

WANG Jin, REN Xiaolong, SUN Kaiwei, et al. Road speed limit sign recognition using HSV color space and evolutionary hypernetwork[J]. High Technology Letters, 2013, 23(7): 679-684.

[20] QUINLAN J R. C4.5: Programs for machine learning[M]. San Mateo, CA: Morgan Kaufmann Publishers, 1993：17-55.

[21] JOHN G H, LANGLEY P. Estimating continuous distributions in bayesian classifiers[C]//Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. San Francisco: ACM Press, 1995: 338-345.

[22] AHA D W, KIBLER D, ALBERT M K.Instance based learning algorithms[J]. Machine Learning, 1991, 6(1): 37-66.

[23] KEERTHI S S, SHEVADE S K, BHATTACHARYYA C, et al. Improvements to platt’s SMO algorithm for SVM classifier design[J].Neural Computation, 2001, 13(3): 637-649.