（通信与信息系统专业论文）基于遗传算法的在线签名认证研究.pdf

摘要 随着计算机和网络技术的高速发展，信息安全在现代社会中显示出了前所 未有的重要性。身份鉴定作为保证系统安全的必要前提之一，在金融、国家安全、 司法、电子商务、电子政务等应用领域都突显重要。传统的身份鉴别方法( 如钥 匙、口令等) 已不能满足社会的需要，基于生物特征的身份鉴别技术的发展为我 们提供了一种更加方便和可靠的解决方案。签名作为一种行为特征，相比其它生 物特征有着更易于获取和能够共享的优点，是身份鉴别中应用最为广泛的生物特 征之一。 遗传算法是目前数学上应用得较为广泛的一种算法，与传统的算法相比，其 最主要的差别在于遗传算法具有智能性和本质并行性的特征。通过算法的选择、 交叉、变异可以自行找到所求问题的最优解。本文尝试了利用遗传算法解决在线 签名认证。文章首先对在线签名认证技术进行了详细论述，包括数据采集系统、 签名数据的预处理、签名数据库的建立、认证模型的建立，然后引入了遗传算法 实现签名曲线的匹配。先对常用的不同遗传操作算子进行了论述，然后结合从认 证数学模型中分离出的关键参数，从适应度优劣的角度对各种操作算子进行实验 比较分析，找到了效果最好的遗传操作算子组合。接下来就是进行签名曲线的分 割与匹配。当采用动态分割的方法对签名曲线进行分割后，接着利用选择、交叉、 变异策略找到曲线的平移、伸缩分量的最优取值，从而得到参考签名段和测试签 名段的最小距离，通过比较这个最小距离与预先设定的匹配门限的大小来判断测 试签名段是否与参考签名段匹配，依次逐一按段比较，从而完成对整个签名曲线 的匹配认证工作。本文同时也给出了基于遗传算法的签名认证程序实现过程。 从实验分析对比的角度，文章最后对遗传操作中的交叉率与变异率以及认证 模型中各参数的确定方法进行了详细讨论，并对建立起的签名数据库进行了实验 分析。实验的结果表明，利用遗传算法解决在线签名认证问题能取得良好的效果， 具有很好的实用价值及应用前景。 关键词：签名认证，匹配，选择算子，交叉算子，变异算子 a b s t r a c t a l o n gw i t h t h eh i g hs p e e dd e v e l o p m e n to ft h ec o m p u t e ra n dt h en e t w o r k t e c h n o l o g y ，t h ei n f o r m a t i o ns e c u r i t yd e m o n s t r a t e dt h eu n p r e c e d e n t e di m p o r t a n c e i n t h em o d e ms o c i e t y a so n eo fp r e r e q u i s i t e si ng u a r a n t e es y s t e ms e c u r i t y ，i n d i v i d u a l v e r i f t c a t i o nr e v e a l e di m p o r t a n c ei nt h ea p p l i c a t i o nf i e l d ss u c ha st h ef i n a n c e ，n a t i o n a l s e c u r i t y , j u d i c a t u r e ，e l e c t r o n i c c o m m e r c ea n de l e c t r o n i cg o v e r n m e n t a l i h i r s 1 1 a d i t i o n a lm e t h o d sf o rv e r i f i c a t i o nf a i lt os a t i s f yt h es o c i e t yd e m a n d s f o r t u n a t e l y , d e v e l o p m e n to ft h et e c h n i q u e sf o rv e r i f i c a t i o no fi d e n t i f i c a t i o nb a s e do nb i o m e t r i c f e a m r e sp r o v i d e sam o r ec o n v e n i e n ta n dm o r er e l i a b l e s o l u t i o n a sak i n do f b e h a v i o r a lf e a t u r e ，s i g n a t u r eh a sa d v a n t a g e so fe a s ya c q u i r e m e n ta n ds h a r i n g i t t u r n s o u to n eo ft h em o s tp o p u l a rf e a t u r e si ni d e n t i t yv e r i f i c a t i o n g e n e t i ca l g o r i t h mw a sa na l g o r i t h mw h i c hw a sw i d e l yu s e d i nm a t h e m a t i c s n o w a d a y s c o m p a r e dw i t ht h ec o n v e n t i o n a la l g o r i t h m s ，t h e m a i nd i f f e r e n c eo f e v o l u t i o n a r yc o m p u t a t i o nl i e s i ni t si n t e l l i g e n c ea n d c h a r a c t e r i s t i cp a r a l l e l i s m i tc a n f i n dt h eo p t i m a ls o l u t i o n st ot h ep r o b l e mb yi t s e l ft h r o u g h t h es e l e c t i o n ，c r o s s o v e ra n d m u t a t i o n g e n e t i ca l g o r i t h mw a su s e dt os o l v eo n l i n es i g n a t u r ev e r i f i c a t i o nq u e s t i o ni n t i f f sa r t i c l e f i r s t l y , o n l i n es i g n a t u r ev e r i f i c a t i o nt e c h n o l o g yw a se l a b o r a t e d ，i n c l u d i n g d a t aa c q u i s i t i o ns y s t e m ，p r e t r e a t m e n to fs i g n a t u r ed a t a , e s t a b l i s h m e n to fs i g n a t u r e d a t 2 【b a s e e s t a b l i s h m e n to fv e r i f i c a t i o nm o d e l t h e nt h eg e n e t i ca l g o r i t h m w a s i 1 1 t r o d u c e dt or e a l i z es i g n a t u r ec u r v em a t c h t h em a i nr e a l i z a t i o nm e n t a l i t yw a st o c a r r yo i lt h ee l a b o r a t i o nt ot h ed i f f e r e n tc o m m o n u s e dh e r e d i t yo p e r a t i o no p e r a t o r , t h e n i tu n i o n e dt h ee s s e n t i a lp a r a m e t e rw h i c hs e p a r a t e df r o mt h ev e r i f i c a t i o nm a t h e m a t i c a l m o d e l t h i sa r t i c l ec a r r i e do nt h ec o m p a r a t i v ea n a l y s i st oe a c hk i n do fo p e r a t i o n o p e r a t o rf r o mt h es u f f i c i e n c yf i ta n du n f i t e dq u a l i t ya n g l ea n df o u n dt h ee f f e c tb e s t h e r e d i t yo p e r a t i o no p e r a t o rc o m b i n a t i o n a f t e ru s i n gt h ed y n a m i c d i v i s i o nt h em e t h o d t oc a r r yo nt h ed i v i s i o nt ot h es i g n a t u r ec u r v e ，g e n e t i ca l g o r i t h mo p e r a t i o nw a s u s e dt o f i n dt h ev a l u e so fs c a l ef a c t o ra n ds h i f to fs i g n a t u r ec u r v ew h i c hc a nc a l c u l a t et h e m i n i m 眦d i s t a n c eb e t w e e nr e f e r e n c es i g n a t u r ea n dt e s ts i g n a t u r e b yc o m p a r e dw i t h t h em i n i m u md i s t a n c ea n dt h ep r e d e t e r m i n e dt h r e s h o l d ，w h e t h e rt h es e c t i o no f t e s t s i g n a t u r em a t c h e st h es e c t i o no fr e f e r e n c es i g n a t u r ew a sd e t e r m i n e d a tt h e s a m e t i m e ，t h i sp a p e rp r e s e n t st h ep r o g r a mr e a l i z a t i o no fs i g n a t u r ev e r i f i c a t i o nb a s e do n g e n e t i ca l g o r i t h m f i n a l l y ，t h e c r o s s o v e rr a t ea n dt h em u t a t i o nr a t ea sw e l la sm o d e lv a r i o u s i i p a r a m e t e r so fi nt h ev e r i f i c a t i o nw a sd e t e r m i n e df r o mt h et e s tc o n t r a s ti nt h i sa r t i c l e t h e nt h ea r t i c l ea n a l y z e dt h es i g n a t u r ed a t a b a s ea n dp r e s e n t st h ee x p e r i m e n t a lr e s u l t s o fs i g n a t u r ev e r i f i c a t i o nb a s e do ng e n e t i ca l g o r i t h m ，a n da n a l y z e dt h e s er e s u l t s ，p o i n t s o u tt h ep r o p e rv a l u eo fv a r i o u sp a r a m e t e r si np r o g r a m k e yw o r d s ：s i g n a t u r ev e r i f i c a t i o n ，m a t c h ，s e l e c t i o n ，c r o s s o v e r , m u t a t i o n l i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其 它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：建萎鍪日期：堡兰聋兰墨! 三旧 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有 权保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的 全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 武汉理工大学硕士学位论文 1 1 生物特征识别技术 1 1 1 问题的研究背景 第1 章绪论 在这样一个高速发展的社会里，计算机和网络的普及使得人们之间的交往越 来越频繁、越来越方便，但随之而来的安全问题却越来越突出，每天都有大量的 信用卡号码、密码和身份证件被窃取和盗用，给国家和个人带来了巨大的损失。 另一方面，在出入境管理、重要场所监控、敏感人物( 间谍、恐怖分子) 智能监控 以及网上追查逃犯等国家和公共安全领域中，传统的身份识别方法( 如护照、身 份证等) 也已很难满足实际应用的要求【l 】。 据m a s t e r c a r d 公司估计，每年约有4 5 亿美元的信用卡诈骗案发生，其中就 包括利用丢失和被盗的信用卡犯罪。如果在销售场所能够准确地识别持卡人的身 份，则这类诈骗案的发生率将大大降低。另外，每年由于使用盗窃来的身份识别 码( p i n ) 而造成的移动电话通信的损失更是高达1 0 亿美元。据估计，若能利用可 靠的方法对a t m 持卡人和支票领款人的身份进行识别，可以使全美国每年由于 a t m 诈骗案造成的损失减少3 亿元，使由于冒领造成的损失减少上亿美元。美 国联邦贸易委员会公布的资料显示，2 0 0 4 年美国有近千万人的身份被盗用，给 个人和银行造成的损失更是高达5 2 6 亿美元。另据美国移民局的统计资料，如果 在美国与墨西哥边境处采用有效的身份识别系统，可以每天查出3 0 0 0 件非法入 境案件圆。 如何准确识别一个人的身份，已成为当今社会急需解决的一个关键社会问 题。许多高新技术公司和科研机构正在寻找和完善基于生物特征的识别技术来提 高身份识别的准确率。b i l l c a r e 曾做过这样的断言，生物特征识别技术将成为今 后几年i t 产业的重要革新【2 1 。 1 1 2 生物特征识别技术概述 生物特征识别技术是根据每个人独有的可以采样和测量的生物学特征和行 为学特征而进行身份识别的技术。由于生物特征不像各种证件类持有物那样容易 窃取，也不像密码、1 2 1 令那么容易遗忘或破解，所以在身份识别上体现了独特的 优势，近年来在国际上被广泛研究【3 】o 武汉理工大学硕士学位论文 并非所有的生物特征都可用于个人的身份认证。身份认证可利用的生物特征 必须满足以下几个条件：第一，普遍性：即必须每个人都具备这种特征。第二， 差异性：即任何两个人的特征是不样的。第三，可测量性：即特征可测量。第 四，稳定性：即特征在一段时间内不改变。当然，在应用过程中，还要考虑其他 的实际因素，比如：识别精度、识别速度、对人体无伤害、被识别者的接受性等 等。现在常用的生物特征有：人脸识别、虹膜识别、手形识别、指纹识别、掌纹 识别、签名识别、声音识别等。下面将分别介绍各种生物特征识别技术：常用的 生理特征有脸像、指纹、虹膜等；常用的行为特征有步态、签名等。声纹兼具生 理和行为的特点，介于两者之间。 众多的生物特征可以用来对人体身份进行识别，大致上可以分为两种：第一 种是基于生理特征的识别技术，即直接对人体进行测量得到的特征。第二种是基 于行为特征的识别技术，即基于人体动作提取出来的特征，这些特征不能直接得 到，最主要的特点是具其有时间性【4 】。如下是对这两种生物识别技术进行介绍： ( 1 ) 基于生理特征的识别技术 基于生理特征的识别技术，主要包括指纹识别、虹膜识别、视网膜识别这几 种。常用的是指纹识别技术，就是通过取像设备读取指纹图像，然后用计算机识 别软件分析指纹的全局特征和指纹的局部特征，特征点如嵴、谷、终点、分叉点 和分歧点等，从指纹中抽取特征值，可以非常可靠地通过指纹来确认一个人的身 份。其次，虹膜识别技术也是一种经常用到的方法，虹膜是位于眼睛黑色瞳孔和 白色巩膜之间的圆环状部分，总体上呈现一种由里到外的放射状结构，包含有很 多相互交错的斑点、细丝、冠状、条纹、隐窝等细节特征，这些特征在出生之前 以随机组合的方式确定下来，一旦形成终生不变。虹膜识别技术是利用虹膜终身 不变性和差异性的特点来识别身份的，其准确性是各种生物识别中最高的。再就 是视网膜识别技术，人体的血管纹路也是具有独特性的，人的视网膜上面血管的 图样可以利用光学方法透过人眼晶体来测定。用于生物识别的血管分布在神经视 网膜周围，即视网膜四层细胞的最远处。如果视网膜不被损伤，从三岁起就会终 身不变。同虹膜识别技术一样，视网膜扫描可能具有最可靠、最值得信赖的生物 识别技术，但它运用起来的难度较大。 ( 2 ) 基于行为特征的生物识别技术 基于行为特征的生物识别技术，主要包括步态识别、签名识别这两种。步态 识别技术是一种重要的基于行为特征的生物识别技术。步态是指人们行走时的方 式，这是一种复杂的行为特征。步态识别主要提取的特征是人体每个关节的运动。 尽管步态不是每个人都不相同的，但是它也提供了充足的信息来识别人的身份。 步态识别的输入是一段行走的视频图像序列，因此其数据采集与脸相识别类似， 2 武汉理工大学硕士学位论文 据有非侵犯性和可接受性。而签名认证技术是另外一种重要的基于行为特征的生 物识别技术4 1 。签名作为身份认证的手段已经有几百年了，而且我们都很熟悉在 银行的格式表单中签名作为我们身份的标志。签名认证易被大众接受，是一种公 认的身份认证技术。 1 2 签名认证技术 1 2 1 签名认证技术介绍 签名认证是一种基于行为特征的技术，它是随着时间逐步成形的个人自身 的行为。人们在长期书写过程中产生各自独有的文字书写方式，表现为不同的书 写力道、笔划书写顺序、笔划连接方式、局部装饰笔划等。而签名作为一种特殊 的书写行为，继承了笔迹的独特性，因此签名可以作为辨识个人身份的一种有效 生物特征【5 1 。 签名认证是建立在每个人的签名都有自己独特的理解和写法，并且相对稳 定的基础之上的。签名不仅代表了签名者的信息，而且签名的某些内在的具有唯 一性的特征与产生签名这一信息的特定生物力学系统有关1 6 】【7 】。 与其它主要的生物特征识别方法相比，采用签名进行身份识别有如下优点： ( 1 ) 易记性。签名作为一种用户的习惯行为，不会被遗忘。 ( 2 ) 自然性。签名是用户经常进行的活动，属于一种容易接受的信息采集模 式。在身份识别过程中，用户可以和平时一样，在很自然的方式下提供签名。与 其它生物特征相比，这是一个很大的优势，例如：虹膜识别虽然具有很高的识别 率，但是在数据采集阶段用户必须将眼睛睁大，站在仪器的有效感受范围内，并 较长时间保持特定的姿势，这对用户而言是很不舒适的。 ( 3 ) 共享性。正因为签名是独特的，长久以来人们使用签名，并信任签名所 代表的内涵。在现代的金融领域，用户可签署函件赋予他人以代理人的权力，或 以支票的形式使他人间接地使用自己的签名，从而他人可以享有用户的部分权 力。这是用其它的生物特征所无法实现的【8 】。 签名一般可以通过两种途径获得，即：在线方式和离线方式。相应地，签名 认证也可分为在线签名认证和离线签名认证两种。在线签名认证中，签名被表 示成一种或几种随时间变化的信号序列，其中包含有签名的动态信息，因此在线 签名认证也称为动态签名认证。而在离线签名认证中，签名是以所提取的二维 图像特征的形式来描述的，故也称之为静态签名认证。般说来，在线签名认 证的认证率较高，因为这种方式的认证特征是通过采集即时签名信息的方式获 武汉理工大学硕士学位论文 得的，即可以利用书写过程中笔尖运动的速度、加速度、压力等作为认证特征。 而对于离线签名认证，由于书写过程中的动态信息几乎全部丢失，只能依据签 名图像的静态信息，即每个人笔迹的特点和相对稳定性来有效反映签名的书写风 格和书写习惯，因此识别难度比较大，识别率也相对较低【9 1 。 本文主要讨论的是在线签名认证技术。 1 2 2 签名认证技术国内外研究现状 在线签名认证的研究工作最早可以追溯到2 0 世纪6 0 年代。手写签名识别身 份认证技术是国际上公认更易被大众接受的一种身份证明方式，也是目前计算机 模式识别领域的前沿课题，这项技术直到近两三年，才在美国和日本取得突破。 由于发达国家的信息通讯技术起步早、发展快，其普及和使用程度已达到 较高的水平，而且他们的计算机管理和自动化技术亦有相当的普及率和较高的 现代化程度，因而计算机身份认证技术已逐步受到广泛的注意和研究。 而中文与英文识别又有着很多区别。英文签名速度较快，在】，轴上变化幅度 较小，中文则为一笔一划书写，速度较慢，坐标轴曲线较明显。英文字母出现在 文本行中，其大小、高度与汉字中的偏旁部首很类似，难以区分是汉字偏旁部首， 还是英文字母；英文签名单词中字母之间的距离不等，粘连也相当普遍；汉字签 名是以横、竖等笔划为基本结构的，而英文签名则是以曲线为主。 就机理而言，签名认证同时也会涉及到哲学、心理学、生理学等许多学科 的问题，但目前的科学技术尚不能揭示手写签名的人工认证机s t j ( 尚未能解释大 脑活动的机理和人类智能的本质) ，就目前的研究现状而言，利用计算机进行签 名认证的研究，从一开始就是以实现功能为目的，即不追究手写签名认证机制 到底如何，只要能够实现同样的功能即可。 目前签名认证研究属于世界上的热门课题，在国外，对英文签名的认证研究 已经取得了一定进展。签名认证算法主要有参数法和函数法两大类。比较有代表 性的有：d a r w i s h 和a u d a 用神经网络作为分类器【5 】，对前人提出的总共2 1 0 个签 名特征参数做了比较研究，该方法虽能利用采集到的丰富签名特征给出良好的 实验演示，但对签名的稳定性以及采集的签名数据要求比较高，有一定的局限性。 m o h a n k r i s h n a n 和p a u l i k 提出了一个基于自回归模型的签名认证方法【7 】，该方法 从数学的角度提出了认证模型，在理论给予了证明，但没能从实验角度分析该认 证模型的可行性。而y a n g 和w i d j a j a 提出了隐马尔可夫模型( h i d d e nm a r k o v m o d e l ) 7 去瞄j ，该方法认证效果比较明显，但并不能很好地处理签名随意性过大这 种情况。c o n n e l l 则提出了基于特征矢量匹配的方法，同时指出选取特征值应满 足简单易计算，不受平移、旋转、尺度缩放的影n 向等要求，但该方法对签名特征 4 武汉理工大学硕士学位论文 的稳定性要求比较高。j c o e t z e r 、b m h e r b s t 和j a d up r e e z 提出了一种基于离 散拉东变换( d i s c r e t er a d o nt r a n s f o r m ) 和隐性马尔可夫( h i d d e nm a r k o vm o d e l ) 相 结合的模型【9 】，该模型虽然很好解决了对签名特征的稳定性要求比较高的问题， 但认证效率比较低下。j o n g h y o ny i 、c h u l h a nl e e 和j a i h i ek i m 提出了利用g a b o r 滤波的相位进行时域偏移估计来进行签名认证的方法【l ，该方法是从滤波的角度 来分析签名认证问题，是一种新的尝试，但未能给出有说服力的实验结果演示。 而m o h a n k r i s h n a n 和p a u l i k 提出了一个基于自回归模型的签名认证方法【i ，该方 法能给出效果明显的实验演示，但认证模型中的系统参数易存在误差。 同时，国内的许多大学和科学家也对在线手写签名认证进行了研究和探讨。 武汉理工大学信息工程学院的郑建彬教授提出的基于演化计算的在线签名认证 方法，利用演化计算具有智能性和本质并行性的特征，通过算法的搜索、加速， 可以自行找到签名认证问题的最优解【l 引。华中理工大学图像识别与人工智能研究 所的金涌与柳健所研究的基于空间曲线弹性匹配的在线手写签名认证，将手写 签名笔划轨迹视为空间曲线，并采用点点加权弹性匹配对其进行鉴别的方法 1 3 1 ， 该算法从三维空间曲线的角度来处理签名曲线，对于理想稳定的签名能取得良好 的认证效果，但还不能很好处理签名随意性过大这一问题。还有其他一些签名认 证的方法理论也在研究发展中。 从上可以看出，国内外目前针对签名认证方面的方法不在少数，都取得了一 定进展，但仍然存在些难以解决的问题： ( 1 ) 涉及面广。整体研究工作将涵盖电子设备的研制，认证技术的开发( 涉及 多方面的知识及应用) ，基于计算机网络的认证体系等等。另外在签名数据库的 建立中，还要涉及到采样对象的征集。对于理想的伪造签名的采集更是一个棘手 的问题。 ( 2 ) 签名随意性过大。人的签名和指纹、虹膜不一样，即使是同一个人的签 名，随着签名环境、人的情绪等变化具有很大的随意性，这就给识别工作带来了 一定难度。 ( 3 ) 特征值提取的标准不统一。使用各种方法进行签名认证，从签名数据中 提取的特征值标准一直都相差较大，有的根据笔划提取特征信息，有的根据拐点 提取特征信息，有的根据坐标轴提取特征信息，有的根据压力和速度提取特征信 息，也有的综合其中几种进行提取。但到目前为止，要成功进行签名认证所必需 的最少特征值信息尚没有定论。 1 2 3 课题研究意义和应用前景 本文研究的是汉字的是在线手写签名认证技术，国际上对手写签名认证方面 武汉理工大学硕士学位论文 的研究主要侧重于英文签名，相比英文签名来说，汉字签名在很多方面存在着差 异。英文签名在x 轴方向上基本上是呈直接上升趋势，在】，轴方向变化很小，且 一般都是一笔直接签完，而汉字签名则在】，轴方向变化和起伏较为丰富，且一般 在字与字之间都有提笔和再次落笔的停顿，造成对汉字的处理更加复杂。 为了提高我国在身份认证技术方面的研究水平，促进信息安全技术的发展， 手写签名认证技术的研究是十分有意义的，其实际应用前景也十分广阔，不仅可 以用于银行、金融机构之间，也可以用于个人用户的身份认证和识别，蕴含着巨 大的市场潜力。 目前汉字手写签名认证研究存在很多问题，例如，由于签名的随意性，将签 名曲线用函数表示十分困难，从而对签名匹配的精度和准确性造成影响。因此， 用目前现有的方法进行手写签名匹配效果都不尽人意。遗传算法采用简单的编码 技术来表示各种复杂的结构，并通过对一组编码进行简单的遗传操作( 选择、杂 交和变异) 和优胜劣汰的竞争机制来指导对问题空间的搜索。简而言之，遗传算 法不需要了解问题的全部特征，就可以通过体现进化机制的演化过程来完成问题 的求解。当今科学技术和工程应用领域具有挑战性的实践问题大都具有高度的计 算复杂性、刻画问题特征的条件少的特点。这些是使传统方法失效的因素，而遗 传算法正好可以克服这些困难。一方面，由于遗传算法的进化机制，使得算法具 有自组织、自适应、自学习和“复杂无关性 的特征，能在搜索过程中自动获取 和积累有关搜索空间的知识，并利用问题固有的知识来缩小搜索空间，自适应地 控制搜索过程，动态有效地降低问题的复杂度，从而求得原问题的真正最优解或 满意解。另外，由于遗传算法对于刻画问题特征的条件要求很少，再加上它效率 高、易于操作、简单通用，从而使得它已经广泛应用于各种不同的领域中。遗传 在大型优化问题求解、机器学习、自适应控制、人工生命、神经网络、经济预测 等领域取得的成功，已引起了包括数学、物理学、化学、生物学、计算机科学、 社会科学、经济学及工程应用等领域科学们的极大兴趣。自8 0 年代中期以来， 世界上许多国家都掀起了遗传算法的研究热潮。由于遗传算法应用范围广泛，从 很多国际会议论文集中都可以看到有关演化计算应用方面的文章。目前，有数种 以遗传算法为主题的国际会议在世界各地定期召开，包括”i e e ei n t e m a t i o n a l c o n f e r e n c eo ne v o l u t i o n a r yc o m p u t a t i o n ( i c e c ) ”、i n t e r n a t i o n a lc o n f e r e n c eo n g e n e t i ca l g o r i t h m s ( i c g a ) ”、g e n e t i ca n de v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e ( g e c c o ) ”【lu j 等。1 9 9 3 年由m i tp r e s s 出版创刊了杂志”e v o l u t i o n a r y c o m p u t a t i o n ”弘，19 9 7 年又新创了杂志”i e e et r a n s o ne v o l u t i o n a r yc o m p u t a t i o n ”。 些国际性期刊也相继出版以遗传算法为主题的专刊f 8 1 。可以预见，遗传算法将 是2 1 世纪智能计算的关键技术之一。 6 武汉理工大学硕士学位论文 将遗传算法应用到签名认证领域，虽然目前尚没有公开的研究进展，但这是 一个很有前景的研究方案。 1 3 主要工作及论文组织情况 1 3 1 主要工作 本课题是基于在研项目“在线签名认证网上阅卷管理系统设计”的子课题“基 于遗传算法的在线签名认证”。主要的研究内容是利用目前在数学领域内应用广 泛的遗传算法理论，解决在线签名的认证。文章着重提出了遗传算法运用于在线 签名认证领域的方法，并给出了数学模型。在数学模型的指导下，给出了完整的 一套签名匹配的方案，并且对基于遗传算法的在线签名认证方案进行了实验，实 验的结果证实了这种方案的可行性 1 3 2 论文组织情况 整篇论文分为6 章，内容组织如下： 第1 章，绪论。主要介绍了课题的研究背景、研究内容、在线签名认证的 意义、国内外现状以及所面临的问题。 第2 章，在线签名认证技术。主要是对在线签名技术流程进行了详细的阐述， 包括数据采集系统、签名数据的预处理、签名数据库的建立、认证模型的建立， 然后引入遗传算法解决签名曲线的匹配问题。 第3 章，遗传算法理论。主要介绍了目前在数学上广泛应用的遗传算法理论， 包括遗传算法的特点，发展历史以及研究现状。同时对于遗传算法重要的一些基 本操作步骤进行了阐述。 第4 章，基于遗传算法的签名认证实现。由第二章引入的问题，本章具体实 现了遗传算法应用于在线签名认证。结合从认证数学模型中分离出的关键参数， 从适应度优劣的角度对各种操作算子进行比较分析，找到了效果最好的遗传操作 算子组合。 第5 章，算法设计中参数的讨论及实验结果分析。将遗传算法和签名认证结 合起来，首先结合给出的签名认证数学模型，对遗传操作中的交叉率以及变异率 进行了讨论，接着对签名认证模型中的参数进行了讨论，最后给出了基于遗传算 法的签名认证的具体算法，并对真实签名数据库与伪造签名数据库进行了实验分 析。 武汉理工大学硕士学位论文 第6 章，总结与展望。总结了研究的不足，并提出了进一步需要解决的问题 以及研究方向。 武汉理工大学硕士学位论文 第2 章在线签名认证技术 签名认证技术包括在线签名认证技术和离线签名认证技术，本章着重讨论的 是在线签名认证技术，主要是对在线签名认证技术流程进行了详细的阐述包括 签名数据采集系统、签名数据的预处理、签名数据库的建立、认证模型的建立， 然后将签名认证模型与遗传算法联系起来。 2 1 在线签名数据采集系统 在线签名数据采集系统主要是实现采集并保存即时签名坐标数据的功能。通 过手写板可以实时采集书写人的签名信息。除了可以采集签名位置信息，还可以 记录书写时的速度、运笔压力等动态信息。通常在手写板上能采集到x 分量数 据、y 分量数据以及压力信息，以用于后续的匹配认证。对于在线签名的数据获 取，不同的采集设各所采集到的手写签名的特征数据也不尽相同。考虑到采集特 征数据的准确性，本文认证算法所采用的数据都是通过w a c o m 公司生产的一 款具有1 0 2 4 级压力传感器的数位板。它有一个l c d 显示器，用户可以在上面书 写签名的同时，看见自己的签名轨迹，这样更符合人的书写习惯。 结合数位板提供的驱动程序，再利用v c6 0 开发工具，可以开发出在线手写 签名数据采集系统的界面【】2 1 ”】，数据采集的频率为每秒1 0 0 个点。整个数据采 集系统的流程图如图2 1 ，应用程序界面如图2 - 2 ： 图2 - l 签名数据采集流程图 圈2 - 2 在线签名数据采集系统界面圉 9 武汉理工大学硕士学位论文 在图2 2 中，用户应用程序界面的文件菜单里有对数据进行保存的子菜单， 点击后可以保存即时签名的坐标数据。对于上图的手写签名，采集系统可以采集 到即时手写签名的x 轴，】，轴，压力z 坐标的签名数据。将以上的签名信息保存 到一个后缀为h 的文件，这样就可以利用v c6 0 以及m a t l a b 等工具进行预处理 以及后续的签名认证工作了。 2 2 签名数据的预处理 预处理的目的是去除噪声，加强有用的签名信息，并对输入测量仪器或其他 因素所造成的退化现象进行复原。适当的预处理不仅可达成前述效果，更可对系 统认证效率有所帮助。然而，不恰当的预处理则可能造成签名信息的失真，有效 信息的丢失等问题，反而影响确认系统的认证能力。预处理包括剔除虚假抬笔、 去噪、平滑、归一化等【l 训。如图2 3 是“张巍”手写签名实例图像，图2 4 ，图2 5 分别是该实例图像经过预处理后的x ，】，分量签名曲线。 图2 3 “张巍”手写签名实例图像 图2 _ 4 ”张巍”手写签名实例图像所采集的经过剔除虚假抬笔、去噪、平滑、归一化后 的x 分量签名曲线 1 0 武汉理工大学硕士学位论文 时阆t l o b s 图2 5 “张巍”手写签名实例图像所采集的经过剔除虚假抬笔、去噪、平滑、归一化 后的】，分量签名曲线 2 3 在线签名数据库的建立 2 3 1 真实签名数据库 通过手写签名采集设备，可以保存实时的签名数据，这些采集的签名数据应 该保存至签名数据库里去，为后面的签名认证提供样本数据。为了对签名认证算 法进行全方位的分析，所以建立的数据库包括真实签名数据库和伪造签名数据 库。相比于其它有关签名认证研究中所采样的签名数据，本文签名数据库选取签 名更加广泛丰富。 整个的真实签名数据库是由”张巍”的5 0 个真实签名所组成，如图2 - 6 是”张 巍”真实签名样本之一。在签名数据采集前，实验者都要经过一个训练的过程， 训练的目的是让书写者在触摸屏上近可能真实地、自然地书写自己的签名，尽量 尽量提高书写签名的稳定性。当实验者经过反复的训练之后，签名逐渐趋于稳定 后，然后开始采集签名。通过观察，可以发现一个签名的整个书写时间范围在1 到1 5 秒之间。而一个签名的书写范围也有一个尺度，即一个签名的最小矩形范 围2 0 m m ( w ) xl o m m ( h ) 到显示屏的外观尺寸大小9 2 2 r a m ( w ) k7 3 o m m ( h ) 。 武汉理工大学硕士学位论文 2 3 2 伪造签名数据库 图2 - 6 “张巍”真实手写签名图像 伪造的签名又可以分为随机伪造、简单伪造以及精心伪造三大类。其中，精 心伪造又可分为熟练伪造、时间伪造和不同版本伪造三个类别。 随机伪造是被误作为当前用户签名的其他用户的真实签名，对签名认证系统 而言这是必须能处理的伪造类型。即伪造者仅仅只知道如何去拼写被伪造者的名 字，而关于真实签名的任何信息( 比如真实签名的尺寸大小、书写时间的长短等) 在拼写之前都不知道。换句话说，伪造者既没有空间信息，也没有时间信息。本 文采集了1 5 个“张巍”随机手写签名作为样本库之一。如图2 7 是实验者提供的 随机伪造签名。 图2 - 7 随机伪造“张巍”手写签名实例图像 图2 8 简单伪造“张巍”手写签名实例图像 简单伪造是伪造者对当前用户签名的一种伪造：伪造者只有对用户签名的印 象，按自己的记忆进行模仿。简单伪造在签名图像内容上是相同的，但外观可能 1 2 武汉理工大学硕士学位论文 因为伪造者的记忆程度、伪造能力而与真实签名相差较大。本文采集了1 5 个“张 巍”简单手写签名作为样本库之一。如图2 8 是实验者提供的简单伪造签名。 精心伪造则是伪造者对用户签名进行多次模仿后写出的笔迹，故在外形上精 心伪造与真实签名相似度较高，如果伪造者经过一系列训练过程，则在动态特征 方面也会形成较大的干扰。由此可见，随机伪造是最容易辨别的，而精心伪造是 最难辨别的。在数据采集过程中，本文将精心伪造又分为三种情况，即熟练伪造、 时间伪造和不同版本伪造。本文采集了1 5 名实验者的“张巍”精心手写签名作为 样本库之一。如图2 9 是实验者提供的精心伪造签名。 图2 9 精心伪造“张巍”手写签名实例图像 由随机伪造签名库，简单伪造签名库，精心伪造签名库合起来的4 5 个伪造 签名就就组成了本文所用的伪造签名库，本文后续的算法设计讨论过程都是基于 此样本库。 2 4 签名认证模型的建立 从手写板上可以采集到在线手写签名图像的x 分量、】，分量和压力分量z 的 曲线。比较两个签名是否可以匹配，就是要看这两个签名对应的x 分量、】，分量 和压力的曲线是否能够按照相应的规则匹配。以x 分量为例，图2 1 0 是从手写 板上采集到的”张巍”手写签名实例图像。 ( a ) “张巍”一次手写签名实例图像 武汉理工大学硕士学位论文 “张巍”二次手写签名实例图像 图2 1 0 “张巍”手写签名实例图像 图2 1 l 两次“张巍”手写签名实例经过预处理后的x 分量对比曲线 图2 1 1 是两次“张巍”手写签名实例采集到的经过预处理后的x 分量对比曲 线，其中实线是经过预处理后的参考签名曲线，虚线是经过预处理后的测试签名 曲线。可以看出，比较两次“张巍”手写签名是否相似可以归结为比较图中两条曲 线的相似性。而这两条曲线是否相似，从表面上看，这两条曲线有一定的相似之 处，但由于签名时存在时间轴的非线性，即每次签名所用时间可能不一致，所以 从表面上比较可能会带来误差。因此如何准确判别这两条曲线是否相似，是否能 匹配，就是待解决的关键问题。为了解决这一问题，下面建立在线签名认证模型。 将”张巍”一次签名作为参考签名，”张巍”二次签名作为测试签名。以图2 1 1 签名曲线x 分量为例，设参考签名的x 分量坐标的曲线对应的函数为f ，( f ) ，测 试签名的x 分量坐标的曲线对应的函数为疋，( f ) ，给出如下两个定义： 定义1 ：给定函数z ，( ，) 、五，( ，) ，称d ( z ，五) = i 阢。( ，) 一z 。( f ) ld t 为两个函数 之间的距离，这里 c o ，q 】为函数的定义域。 白 定义2 ： 对于给定的值占，若d ，z ，) 占，则称彳，( f ) 、正，( f ) 相似，否则 1 4 武汉理工大学硕士学位论文 称它们不相似。 同理，对于测试签名的】，分量坐标和压力信息，参考签名的】，分量坐标和压 力信息有相同的定义。 图2 1 2 参考签名与经过变换后的测试签名对比图 很显然，由于签名时存在时间轴的非线性、书写位置的差异以及字体大小的 局部变化等问题，直接对两个签名所对应的曲线相减求距离是不可取的。因此采 用了两种方式来减小由于签名的随机性给匹配带来的不利的影响。第一种是对曲 线进行分段，从而避免整个曲线进行匹配所产生较大误差的情况；第二种，是引 入甜、v 、a 、b 变量，对参考签名的某段进行伸缩、平移，从而找到该段与测 试签名对应段的最小距离。设参考签名第f 段与测试签名第，段进行匹配，则变 换后的曲线段距离定义为： q d ( u ，y ，口，6 ) = d 、，。t ，爿) = i i 欲7 ( a t + b ) + v - f , ( f ) i a r t ( 2 - 1 ) q 其中u 和1 ，分别是垂直方向上的伸缩比例和平移分量；a 和b 分别是水平方 向上的伸缩比例和平移分量。图2 1 2 表示图2 1 1 中测试签名曲线经过变换后与 参考签名曲线的对比情况。 从图2 1 2 可以清楚地看到，经过变换后的测试签名曲线与参考签名曲线的 距离明显小于测试签名没经过变换时的距离。同时可以看到，测试签名由于有水 平方向上的平移分量b ，因此测试签名的某段可以非常容易地在参考签名上找到 与自己距离最小的部分作为其对应段。 从上面的分析可以看出，在线签名认证问题就转化为求取两条曲线的最短距 武汉理工大学硕士学位论文 离，对于参数a ，b ，u ，v 的讨论就成了重点之处。对于随机初始化的变量口，b ，