（电路与系统专业论文）基于组合分类器的手写中文签名认证系统的研究[电路与系统专业优秀论文].pdf

摘要 手写签名认证系统是通过鉴别用户签名确定其身份的系统。签名的采集、预 处理、特征提取和认证分类器的设计是其关键技术。 本文针对在线手写中文签名认证中的关键技术展开研究。首先我们剥签名进 行重采样，提出了一种等间隔采样方法，然后引入了基于遗传算法( g a ) 的个 性化特征选择方法，并提出一种边缘间隔适应度评估函数，对不同人自动地选 择不同特征子集，实现个性化特征选择。 我们提取签名的y 轴极值点作为分段点列签名进行分段，相对其他方法， 陔方法简单易行，运行时间较短。 组合分类器较单个分类器有较高分类准确率。本文将其引入在线手写签名认 证，对串行和并行两种组合方式进行研究。融入了动态时间弯曲算法( d y n a m i c t i m ew a r p i n ga l g o r i t h m ) 、隐马尔可夫模型( h i d d e nm a r k o vm o d e l ) 、支持向量 机( s u p p o r t v e c t o r m a c h i n e ) 等多种方法，取得了较好的效果。 为便于用户检验系统性能，开发了一个在线中文手写签名演示系统，该系统 具有训练与测试功能，可实时鉴别输入签名的真伪。 a b s t r a c t t h eh a n d w r i t i n gs i g n a t u r ev e r i f i c a t i o n ( h s v ) i st h es y s t e mw h i c hv e r i f y t h e p e r s o nb yi d e n t i f y i n g t h e a u t h e n t i c i t yo fh i ss i g n i n g s i t s i m p o r t a n t t e c h n o l o g ya r es a m p l i n g ，p r e p r o c e s s ，f e a t u r ee x t r a c t i o na n dt h ed e s i g no f c l a s s i f i e r m yp a p e rm a i n l yd i s c u s ss o m eo ft h e m w eu s ea ne q u a ld i s t a n c es a m p l i n gm e t h o dt od e a lw i t ht h es i g n i n gd a t a a n dw ep r e s e n taad i s t a n c ee v a l u a t i o nf u n c t i o n ，w h i c hu s e di ng e n e t i c a l g o r i t h m ，t os e l e c tt h ep e r s o n a l i z e ds u b s e to f f e a t u r e s t h ea p e x e so fya x i sa r ee x t r a c t e dt o s e g m e n tt h e c u r v eo fs i g n i n g c o m p a r i n gw i t ht h eo t h e rm e t h o d ，i ti se a s ya n dq u i c k w eu s et h ec o m b i n gc l a s s i f i e ri nh s va n dr e s e a r c ht h es e r i a la n dp a r a l l e l s t y i eo fc o m b i n g t h ed t w a ( d y n a m i ct i m ew a r p i n ga l g o r i t h m ) 、h m m ( h i d d e nm a r k o vm o d e l ) 、s v m ( s u p p o r tv e c t o rm a c h i n e ) a r eu s e da st h es u b e l a s s i f i er f o rt h ec o n v e n i e n c eo ft e s t i n gt h ep e r f o r m a n c eo ft h es y s t e mb yt h eu s e r s ， w ed e v e l o p e da l lo n l i n ec h i n e s eh a n d w r i t i n gs i g n a t u r ev e r i f i c a t i o ns y s t e m ( d e m o ) i th a st h ef u n c t i o no ft r a i n i n ga n dt e s t i n g w ec a n u s e i tt oi d e n t i f y t h ep e r s o n ss i g n i n ga ta n ym o m e n t 中国科学技术大学倾卜学位论文 第一章绪论 1 1 课题背景 第一章绪论 随着计算机网络技术、电子通讯技术、电子商务的日益普及和发展，信息安 全问题的重要性越来越突出，计算机身份认证实现的可靠性成为一个迫在眉睫的 问题。目前，生物特征识别技术在计算机身份认证领域得到快速的发展。从指纹 识别，到人脸识别，以及掌纹、虹膜、手写签名等等，这些技术主要利用人体本 身所固有的物理及行为特征的不变性，通过图像处理和模式识别的方法来鉴别个 人的身份。 作为信息安全领域身份认证的一种重要技术，手写签名认证技术与其它身份 认证技术相比具有明显的优点： ( 1 ) 与口令字、身份证、密码等方式相比，它不会丢失、遗忘、泄密，因 此更加可靠和方便： ( 2 ) 与指纹、脸部特征、语音、虹膜等其它生物特征识别相比，它不需要 专门而且复杂的采样设备，只需常规输入手段：手写输入板( 在线) 或扫描仪( 离 线) ； ( 3 ) 可以随时产生，不需“携带”。 根据输入以及采样设备的不同，可以把手写签名认证技术分为两种：在线 ( o n l i n e ) 手写签名认证和离线( o f f - l i n e ) 手写签名认证。离线手写签名认证通 常以扫描仪作为输入设备，把签名作为图像来处理，通过传统的图像处理技术和 模式识别方法，认证主要依赖于从签名笔迹中提取的灰度特征。这种方式的弊端 是只采集签名的静态特征作为认证的依据，从而易于模仿和伪造；而在线手写签 名认证除了考虑签名的静态特征外，还会考虑到签名过程中记录下签名的动态特 征，包括签名曲线的时间信息、采样点的速度、加速度，一些具有压力以及电磁 感应传感器的输入设备还能记录下笔书写时的压力和倾斜角等信息 2 】。由于在 线签名同时蕴涵动态和静态信息，可获取的信息量比离线签名更加丰富，而动态 信息又较难模仿，因此在线签名具有较高的可靠性，实际的识别效果也优于离线 中田科学技术人学 i ! i i j 学位沱文 第一章绪论 签名。同时，它的输入设备简便，在实际应用中具有更强的可行性，因此在线签 名认证技术已成为目前计算机签名认证技术的主要发展方向，它的应用前景非常 广阔 1 。 1 2 签名认证技术概括 1 2 1 签名认证技术特点 个人手写签名虽然不是一种固有生理特征的外在表现，但是由于签名基本上 是一种自在的手腕运动，个人签名时在握笔姿势、运笔习惯、用力轻重等方面都 有自己的特点。j j d e n i e r ，v g o n 和j t h u r i n g 等认为手写签名是一种“弹道运 动”，是个人无意识的习惯动作f 3 。手写签名认证就是根据个人书写的特点来比 较当前签名与预先存储的签名样本或模板之间的相似程度，通过相似程度来判断 签名的真伪并相应地决定接受或拒绝当前的签名者。从表面上看，它是一个标准 的二类模式识别问题，但是其中涉及到的技术和理论非常丰富和复杂，与其它相 关的识别技术和生物特征认证技术相比有如下的特点： ( 1 ) 与手写字符识别的比较 手写签名认证与手写字符识别既有区别又有联系。它们的一般处理步骤基本 相同，都包含了：数据采集、预处理、特征提取、匹配和验证等过程，但是在细 节上它们的差异很大。手写字符识别的基本方法是为每个字符建立多个模板，识 别时，每个字符和模板库中的所有模板都进行比较，取最相似的作为识别的结果。 不同人手写汉字的差异较大，手写字符识别要尽可能的消除这些差异，因此它对 字符不强调细节上的处理。然而，手写签名认证的目的是为了把他人仿冒的签名 和本人的签名区别丌，真伪签名其实是内容相同的字符串。真、伪签名在形状上 有可能会非常相似。手写识别需要用到的一些几何特征有时在手写签名认证中反 而成了干扰因素。另外，同一签名者的不同签名也会有差异存在，这些差异和真 伪签名间的差异不易区分开，因此签名认证要求认证算法具备分析细微特征的能 力。 ( 2 ) 与其它生物特征识别的比较 其它生物特征，例如，指纹和虹膜等是基本固定的，不随时白j 、地点和本人 的生理和心理状态而变化。与它们相比，手写签名具有相当程度的不稳定性，例 第一章绪论 如，一个人在成年后的签名，和在青少年时期的签名会存在显著的差异；同一个 人在同一时期的签名也会受其生理利心理状态的影响而有所变化。因此，签名认 正系统要求所选择的特征具有一定的适应签名者本人签名不稳定性的能力，而这 种不稳定性几乎是无法进行精确的分析和预测的。在实际应用中，可以让签名者 不定期的向签名数据库中录入一些本人的签名，通过建立多模板的方法使样本库 包含真签名样本的不同模式，从而减小签名不稳定性的影响。 ( 3 ) 与语音识别的比较 在线签名认证技术和语音识别技术非常相似，都需要对具有明显特点但又具 备不稳定性的时变信号进行分析。语音识别领域的一些基本技术，例如l p c 编 码、动态匹配( d pm a t c h i n g ) 、高斯混合模型( g m m ) 和隐马尔可夫模型( h m m ) 等，也被广泛的应用于在线手写签名认证领域中 1 1 1 6 。和语音识别相比，在线 签名认证可以利用的除了时变信号波形本身，还可以从签名静态的图像中提取形 态几何特征，因此其特征量和认证手段更丰富。 1 2 2 签名认证系统的设计与性能评估 一个手写签名认证系统( h a n d w r i t t e nv e r i f i c a t i o ns y s t e m ，o rh s v ) 通常由 五个部分组成：数据采集、预处理、特征提取、认证和性能评估。 图11 签名认证系统框图 中罔利学技术人学倾i j 学位论文 第一幸绪论 其中，匹配和确定判决门限的过程可以看作是分类器的设计过程，它和特征 提取过程是整个系统设计的核心问题和难点所在。 每个人的签名都不可能与标准字型一致，具体的偏差因人而异，在数学上可 以称之为相互独立。签名认证系统的设计正是根据这一点区分真伪签名。但是， 到底签名中的哪些部分是独特的，如何提取这些特殊的信息，这些信息在全局或 者局部特征中是如何反映出来的，这些问题仍然没有得到完全的解决。因此，签 名认证系统的一个难点在于特征提取和选择。 通常，可以利用两个指标来评估一个签名认证系统的。陛s m 1 ：一是真签名 被拒绝的概率，称为一类错误率或误拒率( f a l s er e j e c t i o nr a t e ，或f r r ) ；二是 伪签名通过认证的概率，称为二类错误率或误纳率( f a l s e a c c e p tr a t e ，或f a r ) ， 如图1 2 所示。一个好的认证系统，应当能够使类内距离尽可能小而类问距离尽 可能大。在理想情况下，如果能选出区分能力最强的特征，真伪签名可以完全区 分开，但在实际情况中，往往并非如此。真实签名之间的区别和伪签名之间的区 别有时很难甚至无法通过肉眼分辨出来，单凭几何或形态上的特征是无法取得好 的认证效果的。在实际应用中，因为二类错误造成的损失比一类错误要大得多， 因此，通常先把二类错误限制在可以接受的范围内( 如果可以实现的话) ，再调 整系统使一类错误概率最小。 c ，广， 一 戮一曩 -黟 o 中国科学技术大学坝卜学位硷文 第一章绪论 ( b ) 图12 分类和判决示意图：( a ) n 想情况；( b ) 实际情况 1 3 在线签名认证技术 多年来对签名产生机理的研究发现，每个人的签名产生过程都是经过训练的 快速熟练过程，是一个弹道式运动，签名过程实际上是一个函数发生器。这就为 建立签名产生模型提供了理论依据 3 。 在线签名认证方法大致可分为两类 1 】。一类是把采样或经计算获得的时间函 数作为特征函数，称作函数法。另一类是把整个签名表征成特征矢量的方式，称 作特征矢量法。 采用函数法，对签名的分析与对语音的分析类似，关键是在于签名曲线匹配 算法的设计。函数法可以利用的一些重要的时间函数有： 位置( 坐标) 信息降( f ) ，y ( f ) ：采样获得的原始的横坐标与纵坐标的离散序 列，这也是大部分采用函数法的系统都不会忽略的信息。 压力信息p ( t j ：笔尖在书写时对手写板的压力，通过特殊的压力传感器获取。 配合其它特征函数，可以提高认证系统的性能。目前，随着手写板采样技术的发 展，越来越多的系统都将书写时的压力作为一个重要的特征。 运笔的速度v ( f ) ，v ，( f ) ，v ，( f ) ：它是表征签名动态信息的重要因素。它可以通 过计算 x ( o ，y ( r ) 的一阶导数获得，也可以直接由特定的设备读取。 加速度以( f ) ，a ，( f ) ，a y ( f ) ：根据书写的抛物线理论，加速度是重要的特征函 中田科学技术大学坝l 学位论文 第一章绪论 数，它和运笔时的速度也是伪造者最难模仿的特征。它可以通过计算 x ( f ) ，y ( o 】 的二阶导数或计算v ( f ) ，v ，( f ) ，v y ( f ) 的一阶导数获得。 采用特征矢量法，它的关键是在于如何从各种特征中选择一部分分辨力最强 的特征。签名包含的特征通常可以分为两类：局部特征和全局特征。特征矢量法 需要解决三个最基本的问题： 第一是特征选择的依据。在f a r 等于f r r ，即等错误率的前提下，选择最 稳定和辨别能力最强的特征。一般地，这种选择在大多数情况下是由经验决定的， 也有一些研究人员认为，可以预先给定一组特征，如果有好的算法，可以让系统 根据不同的人的签名的特点自动的进行特征选择。在这种方案下，根据什么衡量 标准进行特征选择，如何设计合理的算法显得尤为重要。 第二是特征的最佳数目是多少。在签名者较少的情况下，可以比较容易的压 缩特征的维数而不至于引起认证系统性能明显下降。这样可以简化识别过程并提 高效率，但是在签名人数较多的情况下，特征维数的压缩本身就是一个很难解决 的问题。 第三是由于训练信息的匮乏，无法获得真签名相对于伪签名分布的完全的统 计模型。这使得特征选择的常规的统计方法( 如贝叶斯方法等) 变得不可行，或 效果大受影响。 特征矢量的比较则比较直观。签名以特征空间中的矢量的形式出现： f = ( z ， 一，i n ，) 两个签名矢量之间的比较有多种方式，比较简单的有计算矢量间欧式距离等。 不论是采用函数法还是特征矢量法的系统，分类器的设计在整个系统设计中 都占有很重要的地位。分类器的设汁一般是利用签名的全局特征和局部特征分别 进行，再综合给出分类的结果。局部特征，例如签名笔划段内的速度、加速度分 量等，一般很难为人模仿。但由于局部特征数量巨大，因此在设计的时候比较困 难。目前应用的分类器主要可分为以下几种： ( 1 ) 基于全局特征的分类器 基于全局特征的分类器大多应用于采用特征矢量法的系统中。签名认证可使 中圉科学挫术人学倒l 学位论文鹅一章绪论 用的全局特征有很多，例如签名的时间、笔划数；签名外接矩形的长宽比、签名 的最大速度、加速度等等。根据以上关于特征矢量法的论述，在特征选择之后就 可以利用常规识别方法，如线性判别函数、距离判别函数或神经网络的方法来设 计分类器。 ( 2 ) 基于模板匹配的分类器 基于模板匹配的分类器根据所采用的模板数又可分为单模板匹配方法 4 、5 和多模板匹配方法 6 。模板匹配要解决的问题包括参考模板的选择和生成以及 如何度量参考模板与待认证样本之间的相似度。 对于单模板匹配系统，可以根据样本之间的相似度选取与其它训练样本相似 度最高的样本作为模板。 6 中提出了一种多模板的选择和生成方法，利用动态 时间弯曲( d y n a m i ct i m ew a r p i n g ，或d t w ) 距离来衡量两个签名样本的相似 程度，通过k - m e a n s 聚类的方法生成签名者的多个模板，匹配时将待认证签名与 模板一一进行匹配，获得了较好的识别效果。 参考模板与待认证样本间相似度的度量除了利用d t w 距离外，还可使用区 域相关算法( r e g i o n a lc o r r e l a t i o n ，或r c ) 以及树匹配( t r e em a t c h i n g ，或t m ) 算法等。 1 9 】综合比较了三种信号匹配算法在手写英文签名认证中的效率和性能，指 出r c 的效率最高而t m 的效率最低，在不同的情况下三者在性能上互有高低。 而我们实验室先前的研究工作表明：在汉字签名认证中，利用过零小波变换提取 签名的拐点分段并结合d t w 进行匹配，能够得到相对较好的识别效果。而r c 则没有表现出相对英文签名中的良好效果，这可能是由汉字签名的书写特点决定 的，比起英文签名，汉字签名可能持续时间更长、更加不稳定，采样信号波形在 时间轴上非线性的形变表现的更明显 5 。 ( 3 ) 基于统计模型的分类器 如第二节所述，在线签名认证技术和语音识别技术非常相似，因此语音识别 领域的一些基本技术也可以应用于在线手写签名认证领域。上述的信号匹配算法 就是从语音识别领域引入在线手写签名认证中的。语音识别中的一些统计模型也 中田科学技术人学坝i 学位硷文第一章绪论 可以用来对在线的签名进行建模，例如隐马尔可夫模型、高斯混合模型等。 ( 4 ) 基于组合方法的分类器 分类器的组合方法大致可分为串行和并行两种，以上也是本课题研究的方 向。串行又称多级分类器。在签名认证系统中，多级分类器的各级分别过滤伪造 程度不同的各类伪签名，能通过各级分类器的则是真签名。2 0 、2 1 分别介绍了 他们所没计的多级分类器签名认证系统，特定的签名样本集上取得了较好的效 果。并行也称多专家系统。其通过综合多个不同分类器的输出从而给出最终判决 结果。一般来说多专家系统， f 2 2 、2 3 介绍了两种多专家系统，他们的结构大 致相似，各分类器( 专家) 采用不同的特征进行判决，通过对其进行加权可以突 出个性化特征，从而达到好的效果。 1 4 在线签名认证动态 签名认证技术在国外开展的比较早，上世纪七、八十年代就有过这方面的研 究论文发表，但真正蓬勃发展起来应该在上世纪九十年代。1 9 8 9 年p l a m o n d o n 和 l o r e t t e 在他们的论文 1 中详尽而准确的对当时签名认证技术的现状、方法的分 类以及存在的问题做了总结。后来各国的研究人员通过各自的实验，采用多种方 法对签名认证进行了研究，发表了多篇学术论文，在线手写签名认证技术发展到 了一个新的阶段。而在我国，关于签名认证的研究发展的比较晚，也比较缓慢。 产生这种状况的原因有很多。相对于国内，国外对手写签名认证上的市场需求要 大的多，需要签名的场合很多，例如，各种票据、支票、账单以及公文等，它们 的真伪大多都要靠持有者的签名来鉴别。在技术层面上，手写汉字的字型、结构 比西文要复杂的多，这也在很大程度上增加了手写汉字签名认证的难度。 在线手写签名认证技术按照上一节所述可分为两大类，其中采用模板匹配作 为分类器的系统设计思路大体相同，都是先将签名曲线用一定的方法进行分段， 然后依照建立起的段一段之i b j 的对应关系进行签名分段之间的匹配，匹配的算法 大多采用动态匹配算法或者d t w 算法。但国内外研究人员在签名分段上采用的 研究方法又各不相同，b r a u l t 和p l a m o n d o n 在 2 8 1 中提出了一种寻找离散序列中 的转折点的方法，他们认为转折点和拐点是签名笔划曲线中具有重要意义的关键 中国科学技术大学删士学位论文第一章绪论 点，在这些点附近蕴涵着丰富的信息。他们采用转折点作为签名曲线的分段点的 方法，也广为其他研究人员所采用。在 4 、5 、6 中，利用过零小波变换提取签 名曲线的拐点，再利用拐点作为分段点，也获得了较好的效果，等错误率在5 一6 左右。f r i e d e r i k e 采用签名曲线中曲率的极值点作为签名的分段点，并结合 了一些全局特征进行匹配，获得了2 8 的f a r 和1 6 的f r r 。张葵等人提出 了一种用模糊逻辑提取拐点的方法，特殊点匹配正确率达到9 9 2 9 1 。李胜春等 设计的在线签名认证系统，采用动态匹配方法，识别准确率为9 2 2 9 1 。 组合多种分类器的签名认证系统目前较少，但是由于组合分类器较之单一分 类器的性能优势，所以逐渐有研究者将其应用于在线与离线手写签名认证系统。 2 1 介绍的多级分类器系统，其两类错误率达到0 和5 8 。 2 3 采用多个h m m 组合的多专家系统达到1 6 和2 4 的两类错误率。 在手写签名认证领域，对认证系统性能进行评估是一大难题。虽然国外的研 究人员丌始制定一定的标准，另外奋国外市场上也有一些商业化产品，但是在研 究领域还没有出现类似于人脸及字符等通用的数据库，不同的研究人员采用的测 试数据差异很大，因此所给出的错误率一般来说可信度不够高。但近两年来，随 着个人数字助理( p d a ) 的普及、掌上电脑的流行和微软的平板电脑的发售，手 写输入技术越来越受到人们的关注，在线手写签名认证技术相应的也有快速发展 的趋势。2 0 0 4 年，香港科技大学举办了第一届国际签名认证竞赛( s v c2 0 0 4 ：f i r s t i n t e r n a t i o n a ls i g n a t u r ev e r i f i c a t i o nc o m p e t i t i o n ) 3 2 。主办方为参赛者提供了两组 训练和测试用的数据库：一组数据只包含签名的坐标信息；另一组数据除了签名 的坐标信息之外，还包括笔的方向角和压力信息，这两组数据分别对应两个任务。 全球9 个国家的研究团队参加了这次竞赛，参与任务一的有1 5 支队伍，而参与 任务二的有1 2 支。对他们系统的评估进行两次，一次在训练集上进行，另一次 是在测试集上进行。该测试集有6 0 个签名者，每个签名者的样本包含了1 0 个真 签名和2 0 个刻意模仿的伪签名。最后，土耳其的团队在两个任务上都取得了最 低的等错误率而夺冠，他们在两个任务上的测试结果分别为2 8 4 h2 8 9 的等 错误率。这次竞赛也是有史以来较为完整和公开测试结果的一次公共的在线签名 认证的测试。相信随着s v c 的举办，用于科研的通用的签名数据库也会建立和 完善，而且也会推动在线手写签名认证研究的不断发展。 中国科学技术大学坝i 学位论文 批一章绪论 1 5 本文主要研究工作 第二章首先提出一种等间隔重采样方法，然后在此基础上对在线手写签名的 特征选择进行研究，引入了个性化特征选择，使用的方法是g a ( 遗传算法) ， 并提出一种基于间隔的适应度评估函数。 第三章对串行分类器组合方式进行研究。提出一种分段点的提取和分段对准 方法。在串行方式采用的由粗到细的认证的思想，设计三级的认证系统。在最后 一级提出一种多模板加权的方法。 第四章对并行分类器组合方式进行研究。融入了h m m 和s v m 。通过实验 验证其有效性。 第五章介绍开发的在线手写中文签名身份认证演示系统。 第六章为全文总结。 0 中国科学技术大学坝_ 一学位论文 第一章预处理、特征抽取与个性化特征选择 第二章预处理、特征抽取与个性化特征选择 本文试验采用的数据是s v c 2 0 0 4 签名数据，它是用户书写的原始数据，每 1 0 m s 一个采样点，每个采样点包含的信息有该点的横、纵坐标，该采样点笔尖 是否接触到手写板，该点的压力。由于人书写时会随机产生有抖动等无意识的行 为，这些情况会给认证带来不良影响，所以需要对签名进行预处理。预处理包括 大小归一化和重采样。 签名认证系统是基于人的生物特征的身份认证系统，其关键问题是尽可能减 小同一个签名者签名之间的差别，而与伪签名之间的差别则要加大。对由手写板 采集的签名原始数据作处理可以得到签名长宽比、重心位置、方向直方图等一些 静态特征，还可以得到速度，加速度，压力变化量等一些动态特征。传统的认证 系统对于不同人均使用同一个特征集，其缺乏针对性。这一方面使特征空间维数 过高，另一方面又降低了认证的精度，为此必须根据各人不同的书写风格，选择 不同的特征集，在签名认证系统中采用的方法是在一个基本特征集基础上再对不 同人选择不同特征子集。我们采用遗传算法( g a ) ，对每个人搜索其个性化特征。 对于签名认证，特征主要分为整体特征和局部特征，整体特征指对整个签名 提取的特征，如签名的长宽比、笔划数、速度均值等，而局部特征是对签名进行 分段，然后对每段提取特征。局部特征较整体特征更能区别细微的不同之处，而 整体特征能够从全局把握签名的基本特点，两者结合使用能达到比较好的效果。 本章所介绍的g a 个性化特征选择是在整体特征集的基础上进行选择。 2 1 预处理 s v c 2 0 0 4 数据的每个签名是由一个五维的原始采样点序列g ，y 。，s ，p ，) 。x 。 和”是当前采样点的坐标值，i 是采样点序列号。r 表示当前的采样时间，以毫 秒为单位。s 表示当前笔的状态，若笔尖与手写板接触该值为l ，若出现抬笔则 采样过程停止，当再次笔尖接触到手写板时，该点标记为0 。p ，是签名在该采样 点处的压力值。 中罔爷 学控术人学坝l j 学位论文 第一章预处理、特征抽取l _ 个- 陛化特征选择 图21 签名原始采样点横纵坐标 由于书写者在输入签名时会出现颤动的情况，并且由于签名的大小不一致， 这会给后面的特征提取以及判决过程带来不便，因此预处理主要由以下几部分组 成：1 对签名大小进行归一化；2 对数据进行平滑处理；3 对笔划的点距归一化。 最终得到大小归一化的，平滑的签名数据序列。 签名坐标的尺度归一化就是把签名各采样点坐标按最大横坐标和纵坐标进 行归一化。 数据平滑处理和笔划点距归一化可以通过等距的差值重采样得到。重采样的 过程是，首先计算整个签名的轨迹长度，然后除以采样间隔的个数。采样间隔是 采样点的个数减l 并且减去抬笔次数可得，抬笔次数就是当笔离丌手写板即计为 一次。这样可以得到一个距离值d ，将此距离值称以系数c ，c 取一个小于1 的 数，本文一般取0 9 ，令a = c d ，a 即为重采样的距离间隔。根据对签名进 行重采样方法如下：以原始数据第一个采样点为开始点，依次计算后续采样点到 其距离，直到某个点到其距离d 大于a 为止，取该点为结束点。然后计算该点与 开始点组成矢量的斜率从而计算出x 和y 方向坐标的增量缸和y ，再令结束点 的时间f ：减去丌始点的时间f ，得到时间增量a t ，则该差值点的采样时间 t = ，i + ( a d ) a t 。若结束点的状态为0 则该采样点取o ，否则该点取1 。压力 中国科学技术大学坝h 学位论义 第一章预处理、特征抽取一7 个肚化特征选择 p = p 1 d 十p ：( d a ) d 式中p 和p ：分别式丌始点利结束点的压力值。然后 再以该采样点为开始点，向后寻找结束点。知道到原始数据的最后一个点。 通过这种重采样方法可以去除由于用户书写时的颤动产生的毛刺，并且使采 样点的疏密达到一致，方便后续的处理。 图22 重采样前笔习 圈23 重采样后平滑、等间隔采样的笔划段 中固科学技术人学坝i 擘位论义 雏一章顶处理、特征 南取_ 个h 化特瓶选择 图2 4 采样前签名 图25 采样后签名 中国科学技术人学坝l 学位论义 第一章预处理、特征抽取与个陆化特征选择 2 2 初始整体特征集的确定 对于个性化特征选择来说，首先需确定初始的特征集，然后在此基础上用具 体的搜索算法和评价标准来确定个性化特征集。本文对每个签名提取的整体特征 如下： 表21 初始特征集 1 横向纵向最大值之比2 熏心位置的x 坐标3 重心位置的y 坐标 4 x 方向均值与最小值之差5 y 方向均值。= ，塌小值之差6 x 方向屉大值与屉小值之比 7 y 方向最大值与摄小值之比 8 方向为- 4 5 , - - 4 5 度矢量个数9 方向为4 5 1 3 5 度矢量个数 10 方向为13 5 2 2 5 艘矢量个数 l i 方向为2 2 5 3 i5 度矢量个数1 2 笔划数 i3 - b 写时l 司 1 4 抬笔时间与整体书写时间比15 重心位置x 坐标( 压力加权) 1 6 重心位置y 坐标( 压力加权)1 7 x 方向、f 均速度 18x 方向最大证速度 1 9 x 方向绝对值最大的负速度2 0 x 方向速度绝对值的平均值2 1x 方向正速度的平均值 2 2x 方向负速度均值的绝对值 2 j y 卉向谏席的青善4 x 青向慎庸柏n 的电的个数 2 5 y 方向，i i 均速度2 6 y 方向最大正速度2 7 y 方向绝对值摄大的负速度 2 8 y 方向速度绝对值的均值2 9y 方向正速度均值3 0y 方向负速度均值的绝对值 3 1y 方向速度的方差 3 2 y 方向速度为0 的点的个数3 3 方向平均加速度 3 4 x 方向塌大正扣i 速度 3 5 x 方向绝对值最大的负加速3 6 x 方向加速度绝对值的均值 度 3 7x 方向f 加速度的均值3 8x 方向负加速度均值的绝对 3 9 x 方向加速的方差 值 4 0x 方向加速度为0 点的个数4 i y 方向平均i 速度4 2 y 方向最大正加速度 4 3 y 方向绝对值强大负加速度 4 4y 方向加速度绝对值的均值 4 5 y 方向正加速度的均值 4 6 y 方向加速度的方差 4 7 x 方向负加速度均值的绝对4 8 y 方向j i l 速度为0 的点的个数 值 4 9 压力平均值5 0 压力屉大值 5 1 压力最小值 5 2 压力的方差 5 3 压力一阶变化量的均值5 4 压力一阶变化量的晟大值 5 5 压力一阶变化量绝对值最大5 6 压力一阶变化量正值的均值5 7 压力一阶变化量负值平均值的 的负值 绝对值 5 8 压力一阶变化量绝对值的均5 9 压力一阶变化量为0 点个数6 0 压力一阶变化量的方差 值 以上特征集中的速度和加速度特征包括x 、y 两个方向。速度通过分别对x 、 y 坐标分别求一阶差分得，加速度为x 、y 坐标的二阶差分。 对签名数据基本特征提取后再进行线性定标，将其范围确定在1 到1 之间。 中固科学技术大学 i i j ! 学位论义 第一幸顶处埋、特征抽耿7 j 个化特征选择 2 。3 基于g a 的个性化特征选择 遗传算法( g a ) 是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算 法 3 3 。遗传算法的主要特点是群体搜索策略和群体中个体之f 刮的信息交换，搜 索不依赖于梯度信息。它尤其适用于处理传统搜索方法难于解决的复杂非线性问 题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。 选择、交叉和变异是遗传算法的3 个主要操作算子。 遗传算法中包含了如下五个基本要素： 1 ) 参数编码； 2 ) 初始群体设定； 3 ) 适应度函数设计； 4 ) 遗传操作设计； 5 ) 控制参数设定( 主要是指群体大小和使用遗传操作的概率等) 。 2 3 1 特征向量的遗传编码 根据基础特征集的大小，设定染色体上基因数为6 0 与6 0 维特征相对应。每 个基因可取o 或l ，分别代表这个特征的删除和选择。如下图： + 一染色体有6 0 个基冈+ 第5 个特征被选中 2 3 2 初始群体的设定 图26 染色体结构 第5 7 个特征来被选中 根据试验设定种群大小为5 0 。染色体上的基因取0 或1 由随机决定。 2 3 3 选择 选择的目的是为了从种群中选出优良的个体使他们有机会作为父代为下一 代繁殖子孙。判断个体优良与否的准则是各自的适应度值。本文采用联赛方式来 中同科学技术大学坝：k 学位论文 第一章预处理、特征抽取与个性化特征选择 决定各个体的选择份数。所谓联赛选择，就是从群体中任意选择一定数目的个体 ( 称为联赛规模) ，其中适应度最高的个体保存到下一代。这一个过程反复执行， 知道保存到下一代的个体数达到预先设定的数目为止。联赛规模取2 。 2 3 4 交叉 采用一点交叉操作。首先对当前种群中个体进行随机配对；然后，在配对 个体中随机设定交叉处，配对个体彼此交换部分信息。 2 3 5 变异 设定变异概率p 。= o 0 0 1 ，对种群中每个染色体的每个基因取随机数，若小 于尸 则该基因位取反。 2 3 6 适应度函数及评估检测 本文采用一种基于边缘间隔的适应度评估方法。 对于手写签名来说，一般认为一个人的不同签名虽然在不同情况下存在不同 之处，但可以认为基本稳定。所以在小样本情况下对其求统计参数也是合理的a 伪签名样本由于是由其他人伪造，伪造人可以是非真用户的任何人，伪造人的书 写风格，伪造技巧千差万别。但是在实际应用中伪签名样本也不可能取得很多， 所以这是一个制约签名认证系统性能的重要因素。对于仅有的一些伪签名样本， 用它来估计统计参数将导致很大的偏差。 f a l 理想情况分布( b ) 实际情况分布 图27 特征空间中真伪样本的分布 主旦! ! 兰堡垄查兰型! ! 兰些堡兰 塑二童堡竺型：塑堑塑里兰尘苎些塑篁丝堡 在理想情况下，真、伪签名在特征空间中可以被完全分开。 实际情况中在特征空间罩真签名样本相对伪签名是有限的，其分部形状也可 预计，而伪签名样本是无限的，并且两类签名样本还会有一定程度的混合，并不 能完全分丌。 本文的边缘问隔a 的适应度评估方法定义如下： 锨一呵n ，z 一s 警，l ( g 0 厂。( g j ；怜一埘c | l ，： ，j r 忆一m “i i 式中g 摩：l ，一) 为真样本， 为真样本个数。l j ( = 1 ，n ：) 为伪样本， z 为伪样本个数。m 。为真签名样本特征向量的均值。 图28 真伪签名样本之间的边缘间隔 假定真签名在特征空间种的分部为一个圆，其圆心为其真签名样本的均值向 量，半径等于各真签名样本中到真签名样本中心距离的最大值。此最大值加上 即伪签名样本到真签名样本中心的最小距离。 越大则真、伪签名之归j 的距离越大，分类推广能力越好。 2 3 7g a 的终止条件 遗传操作代数为5 0 。经观察到达5 0 次后，g a 算法基本收敛。 中囝科学挝术大学坝卜学位论文 第一章颀处删、特征抽取1 个降化特缸选择 2 4 试验对比 根据表1 提取每个签名样本的6 0 个特征，并对其作归一化处理。由于签名 认证是小样本模式识别问题，从文献 3 4 1 中可知，支持向量机( s v m ) 是目前最 适合于小样本的机器学习方法，它是在v a p n i k 等人提出的统计学习理论的基础 上发展起来的。实践证明它能有效克服神经网络等遇到的困难。所以本文采用 s v m 分类器进行认证。限于篇幅，有关s v m 的原理此处从略。 s v c 2 0 0 4 签名数据集由1 4 个人组成，对每个人的样本集通过随机划分分为 原始训i 练集和原始测试集。训练集和测试集中样本个数相等。每个集合中包括真 签名样本1 0 个；伪签名样本1 0 个。由原始训练集通过g a 特征筛选可得到个性 化特征集，然后再用原始测试集进行测试，此过程循环1 0 次。由于g a 算法有 其不确定性，因此1 0 次所得个性化特征子集不完全相同。本文的解决方法是首 先去除1 0 次中误纳率和误拒率高于1 0 次平均水平的个性化特征子集，然后根据 所剩特征子集，对存在于所省特征子集中的特征进行投票，对票数高于所剩特征 子集个数一半的特征保留，否则删去，最后对每个特定人其个性化特征子集只有 一个。1 4 个人中6 0 个特征经过筛选得到的个性化特征个数平均为3 4 个，平均 特征压缩率4 3 3 。最大为4 3 个，压缩率为2 8 3 3 。最小为2 4 ，压缩率为6 0 。 部分人的个性化特征子集如下表： 表1 2 部分人个性化特征子集 i d 个性化特征数个性化特征子集 22 4 l ，3 , 9 ，1 1 ，1 4 ，1 6 ，1 7 ，t 8 ，2 0 ，2 2 ，2 4 ，2 5 ，2 7 ，3 i ，3 2 ，4 0 ，4 5 ，4 7 ，4 8 ，5 2 ，5 3 ，5 5 ，5 6 ，5 9 32 93 ，4 ，6 ，7 ，9 ，i o ，i l ，1 2 ，1 3 ，1 4 ，1 6 ，1 8 ，2 0 ，2 1 ，2 2 ，2 4 。2 8 ，2 9 ，3 0 ，3 2 ，3 6 ，3 7 ，4 0 ，4 9 ，5 1 ，5 3 ，5 6 ，5 8 ，5 9 42 7 i ，3 , 6 ，i l ，i2 ，1 4 ，i5 ，1 6 ，i7 , 2 1 , 2 2 ，2 9 ，3 0 ，3 1 , 3 2 ，3 6 ，4 0 ，4 8 ，4 9 ，5 0 ，5 2 ，5 3 ，5 5 ，5 6 ，5 7 ，5 8 ，6 0 72 9i ，3 , 4 ，5 ，6 ，8 ，1 0 ，1 l ，1 2 ，1 4 ，1 6 ，17 ，1 8 ，2 2 ，2 3 。2 9 ，3 3 ，3 5 3 7 ，4 2 ，4 4 ，4 5 ，4 8 ，5 0 ，5 4 ，5 6 ，5 7 ，5 8 ，5 9 系统认证首先将样本再次随机划分为训练集和测试集两部分，训练集中包括 真签名l o 个，伪签名1 0 个。测试集中真签名1 0 个，伪签名l o 个。 将训练集和测试集分别用个性化特征子集和原始特征全集输入s v m ，可得 两种系统的f r r 利f a r 。对1 4 个人进行试验，经过g a 个性化特征筛选后f a r 和f r r 都有下降的有1 0 个，f a r 和f r r 一项下降的有4 个。经过g a 个性化 特征筛选后1 4 个人的平均f a r 为9 5 ，平均f r r 为4 2 。不用特征筛选的平 均f a r 为1 7 0 8 ，平均f r r 为47 9 ，改善率分别为4 4 3 8 和1 6 2 5 。 中国科学技术人学顺卜学位论文 第一章预处理、特征抽取，个陛化特缸选择 1 4 个人经过g a 特征筛选同无特征筛选试验对比结果如图7 。 ( a ) 误纳率比较 图29 试验结果对比 ( b ) 误拒率比较 可见，用g a 进行特征筛选之后f a r 和f r r 较之无特征筛选方法都有所下 降。并且由于训练时只用到有技巧伪签名，而在测试时包含有随机伪签名，可以 说明用g a 进行特征筛选之后由于两类样本边缘间隔的增大，所以推广能力变 强。 2 5 本章小结 本章介绍了预处理和特征提取的过程。 通过预处理可以把原来非等距并且含有由用户书写时无意识的抖动产生的 毛刺的原始数据转换成等距、平滑的签名数据。 我们引入了个性化特征选择的方法。首先确定初始的特征集，然后在此特征 集的基础上用遗传算法( g a ) 有针对性地选择特征子集。为此我们提出了一种 基于边缘间隔的适应度函数。实验显示经g a 进行个性化特征选择之后，不仅 压缩了特征维数，而且还使认证的错误率有了不同程度的降低。 中国科学技术大学谚j 学位论文第二章蜒十串行组合方止的多分类 | 系统 第三章基于串行组合方式的多分类器系统 本章介绍了串行组合方式的多分类器手写签名认证系统。在该系统中首先需 对签名进行分段处理，我们提取签名的y 轴方向的转折点作为分段点，并定义 稳定度，删除稳定度较低的分段点后，根据真样本分段点计算得到一个分段标准， 用该分段标准对签名分段可以使得签名的段数相等。 串行组合方式的设计思路略不同于单个分类器，要优先考虑误拒率。本章介 绍了一种三级串行组合认证系统。每一一级的特征和分类方法不同，它们分别针对 不同类型的伪签名。由于第三级分类器中要用到d t w a 算法，因此先对该算法 进行简述。 3 1 提取签名分段点 况 本文提取的分段点是签名轨迹y 轴方向上的转折点。对应的转折点有6 种情 i + l ( a ) ， y h 且y ， y ( e ) y ， y h 且y ，= y ( dy 图3 1 六种情况分段点 i + l 提取以上六种采样点作为分段点，然后对签名y 轴方向轨迹进行分段。 ( a ) ( b ) 剀32y 轴分段点提取情况 中国科学技术丸学倾卜学位论文 第三章基于串行组台方式昀多分娄器系统 然而由于签名涉及非常复杂的肌肉运动，有时签名者的手腕会出现抖动等现 象，这些不规则运动是轻微和不规律的，但是可能会被检测出来( 如图3 2 中a 、 b 、c 点) ，因此，即使真实签名之间仍然可能存在分段点数目的差异。那么， 如何正确建立分段点的一一对应关系，成为必须要解决的问题。如果出现分段点 的错误匹配，就会出现段的错位，严重影响签名的匹配结果。 如果能够从分段点序列中滤除这些对应于局部抖动或畸变的分段点，分段点 对齐的难度将降低。为每个分段点建立稳定度的概念： 月，= m i n l d i s ，d i s 。+ ll j 一1 , 2 ，月 ( 1 ) 其中d i s ，表示第i ，j 个分段点之削签名轨迹的长度。 由抖动产生的分段点，其由式( 1 )