（通信与信息系统专业论文）签名验证方法及其演化算法研究.pdf

武汉理工大学硕士学位论文 中文摘要 传统的身份鉴别方法( 如钥匙、口令等) 已不能满足社会的需要，基于生物特 征的身份鉴别技术的发展为我们提供了一种更加方便和可靠的解决方案。签名作 为一种行为特征，相比其它生物特征有着更易于获取和能够共享的优点，是身份 鉴别中应用最为广泛的生物特征之一。 演化计算是目前数学上应用得较为广泛的一种算法，与传统的算法相比，其 最主要的特点在于演化计算具有智能性和本质并行性的特征。通过算法的搜索、 加速，可以自行找到所求问题的最优解。 本文将演化计算和在线签名验证结合起来，提出了基于演化计算的签名验证 方案，方案分为两个部分，即签名验证曲线段的演化计算程序和签名曲线的动态 分割。 签名验证的演化计算程序的基本思路是通过演化计算找到波形的平移、伸缩 分量的取值，从而得到参考签名段和测试签名段的最小距离，通过比较这个最小 距离与预先设定的匹配门限的大小来判断测试签名段是否与参考签名段匹配。根 据这个思路，本文给出了签名验证的演化计算程序的数学模型，并在数学模型的 基础上，给出了签名验证的演化计算程序的具体算法。 签名曲线段的动态分割是签名验证的演化计算程序的前提，只有对签名曲线 段进行了正确的分割，才能得到签名验证的准确结果。本文首先比较了几种传统 的签名曲线分割方法，指出了签名曲线段的动态分割的必要性，然后详细的介绍 了这种动态分割的算法。 文章的最后给出了基于演化计算的签名验证方案的实验结果，并且对实验结 果进行了分析，给出了方案中各个参数的恰当的取值，并计算出了该方案的误纳 率( f a g ) 和误拒率( f r r ) 。 实验的结果表明，这种验证方法达到了较高的验证性能，具有很好的实用价 值及应用前景。 关键诃：签名验证，演化计算，动态分割，参考签名，测试签名 武汉理工大学硕士学位论文 a b s t r a c t t r 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 na n dr e c o g n i t i o nf a i lt os a t i s f yt h es o c i e t y d 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 o i q m sf o rr e c o g n i t i o na n dv e r i f i c a t i o n o 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 cf e a t u r e sw o v i d e sam o r ec o n v e n i e n ta n dm o r e r e l i a b l es o l u t i o n a sa1 【i n do fb 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 y a c q u i r e m e n ta n ds h a r i n g i tt u r n so u to n eo ft h em o s tp o p u l a rf e a t u r e s i ni d e n t i t y r e c o g n i t i o na n dv e r i f i c a t i o n e v o l u t i o n a r yc o m p u t a t i o n ( e c ) i sa c ta l g o r i t h mw h i c hi sw i d e l yu s e di n m a t h e m a t i c sn 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 em a i n s p e c i a l t yo fe ct i e si ni t si n t e l l i g e n c ea n dc 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 nf i n dt h e o 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 f t h r o u g ht h es e a r c ha n da c c e l e r a t i o n t h i sp a p e rc o m b i n e se cw i t hs i g n a t u r ev e r i f i c a t i o na n dp r o p o sas c h e m e w h i c hi ss i g n a t u r ev e r i f i c a t i o nb a s e do ne c t h i ss c h e m ed i v i d e di n t ot w op a r t s ， n a m e l y , t h ee v o l u t i o n a r yc o m p u t a t i o np r o g r a mo fs i g n a t u r ec u r v ev e r i f i c a t i o na n dt h e d y n a m i cs e g m e n t a t i o nt os i g n a t u r e t h eb a s i ci d e ao ft h ee cp r o g r a m m i n go fs i g n a t u r ev e r i f i c a t i o ni st of i n dt h e v 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 l lc a l c u l a t et h em i n i n q u n l 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 ht h e n l 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 e 伽d e t e r m i n ew h e t h e rt h e s e c t i o no f t e s ts i g n a t u r em a t c h e st h es e c t i o no f r e f e r e n c es i g n a t u r e a c c o r d i n gt ot h i s t h o u g h t ，t h i sp a p e rp m s e n t sas i g n a t u r ev e r i f i c a t i o nm a t h e m a t i c a lm o d e lo fe c p r o g r a m ，m a dp r o p o s e si t sd e t a i la l g o r i t h m t h ed y n a m i cs e g m e n t a t i o ni st h ep r e m i s eo fs i g n a t u r ev e r i f i c a t i o nb a s e do ne c o n l yw h e nw em a k et h ec o r r e c ts e g e m e n t a t i o nt ot h es i g n a t u r ec u l l ，e w ec 锄g e tt h e a c c u r a t er e s u l to fs i g n a t u r ev e r i f i c a t i o n a tf i r s t , t h i sp a p e rc o m p a r e ss e v e r a l t r a d i t i o n a ls e g m e n t a t i o nm e t h o d so fs i g n a t u r ec u r v ea n dp o i n t so u tt h en e c e s s a r i t yo f t h ed y n a m i cs e g m e n t a t i o n t h e n , t h ep a p e re x p l a i n st h ed y n a m i cs e g m e n t a t i o n a l g o r i t h mi n d e t a i l f i n a l l y , t h i sa r t i c l ep 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 so fs i g n a t u r ev e r i f i c a t i o n b a s e do ne c ，a n da n a l y 髓st h e s er e s u l t s ，p o i n t so u tt h ep r o p e rv a l u eo fv a r i o u s p a r a m e t e r si np r o g r a m a tt h ee n do f t h i sp a p e r , w ec a l c n i a t et h ef a r a n df r ro f t h i s s c h e m e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sw a yo fs i g n a t u r ev e r i f i c a t i o na c h i e v e sa n 武汉理工大学硕士学位论文 h i g h e rp e r f o r m 趾c eo f v e r i f i c a t i o n , a n dh a sg o o dp r a c t i c a la p p l i c a t i o na n dp r o s p e c t 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 , e v o l u t i o n a r yc o m p u t a t i o n , d y n a m i cs e 零n 如姗o l l i i i 独创性声明 本人声明，所呈交盼论文是本人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一丽工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保留、 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容， 可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 粹鼻l 导燃：辎期：翌! 竺 武汉理工大学硕士学位论文 1 1 背景介绍 1 1 1 问题的提出 第1 章绪论 我们生活在一个高速发展的社会里，计算机和网络的普及使得人们之间的交 往越来越频繁、越来越方便，但随之而来的安全问题却越来越突出，每天都有大 量的信用卡号码、密码和身份证件被窃取和盗用，给国家和个人带来了巨大的损 失。另一方面，在出入境管理、重要场所监控、敏感人物( 间谍、恐怖分子) 智能 监控以及网上追查逃犯等国家和公共安全领域中，传统的身份识别方法( 如护照、 身份证等) 也已很难满足实际应用的要求i i 】。 据m a s t e r c a r d 公司估计，每年约有4 5 亿美元的信用卡诈骗案发生，其中就 包括利用丢失和被盗的信用卡犯罪。如果销售场所能够准确地识别持卡人的身 份，则这类诈骗案的发生率将大大降低。另外，每年由于使用盗窃来的身份识别 码( p 烈) 而造成的移动电话通信的损失更是高达1 0 亿美元。据估计，若能利用可 靠的方法对a t m 持卡人和支票领款人的身份进行识别，可以使全美国每年由于 删诈骗案造成的损失减少3 亿元，使由于冒领造成的损失减少上亿美元。美 国联邦贸易委员会公布的资料显示，2 0 0 4 年美国有近千万人的身份被盗用，给 个人和银行造成的损失更是高达5 2 6 亿美元。另据美国移民局的统计资料，如果 在美国与墨西哥边境处采用有效的身份识别系统，可以每天查出3 0 0 0 件非法入 境案件。 如何准确识别一个人的身份，已成为当今社会急需解决的一个关键社会问 题。许多高新技术公司和科研机构正在寻找和完善基于生物特征的识别技术来更 加有效的进行身份识别b i l l g a t c s 曾做过这样的断言，生物特征识别技术将成 为今后几年i t 产业的重要革新。 1 1 2 生物特征识别的定义 生物特征识别技术( b i o m e t r i c s ) 是根据每个人独有的可以采样和测量的生物 学特征和行为学特征而进行身份识别的技术。由于生物特征不像各种证件类持有 物那样容易窃取，也不像密码、口令那么容易遗忘或破解，所以在身份识别上体 现了独特的优势，近年来在国际上被广泛研究1 2 1 。 人的任何生理和( 或) 行为特征只要满足以下要求都可以作为生物特征：l 、 武汉理工大学硕士学位论文 普遍性：这种特征是每个人都具有的；2 、独特性：任两个人的这种特征都不相 同；3 、稳定性：这种特征至少在一定时问内( 相对某种匹配准则) 是不变的；4 、 可采集性：这种特征可以被定量测量。而且在实际系统中还必须考虑性能、可接 受性、防欺骗性等问题，也即一个实际的生物特征识别系统必须满足特定的识别 准确性、速度和资源要求，对使用者无害且能被计划中实施的人群接受，对各种 欺诈和攻击手段有足够的鲁棒性唧。 一个典型的生物特征识别系统包括传感器、特征提取、匹配器和系统数据库 四个模块，可以在认证( v c r i f i c a t i o n ) 和识别( i d 胁蚯c a t i o n ) 两种模式下工作( 4 1 。认证 即通过比较获得的生物特征数据和数据库存储的生物特征模板来验证用户是否 为他所声明的身份，它是一对一的比较；识别是通过匹配获得的生物获得的生物 特征数据和数据库中储存的生物特征模板来确定用户的身份，它是一对多的比 较。 图1 1 是生物特征识别系统的原理框图。 图1 - 1 生物特征识别系统原理框图 1 1 3 主要的生物特征识别技术 ( 1 ) 指纹识别p 指纹识别是使用最早也是最成熟的生物特征识别技术。指纹是手指末端正面 皮肤上的呈有规则定向排列的纹线。指纹识别的主要关键技术包括指纹图像增 强、特征提取、指纹分类和指纹匹配几个部分。 指纹图像增强的目的在于提高指纹图像中脊线的清晰度，一般包括以下环 节：滤波、图像的二值化、方向场图、生成特征模板等，其主要问题在于图像处 理过程中相关参数和阈值的选择，选择不当会造成特征信息的损失或产生错误特 征信息。特征提取是指纹识别的重要步骤，目前最常用的细节特征是指端点、叉 点和奇异点的特征。通常情况每个清晰指纹一般有4 0 - 1 0 0 个这样的细节特征点。 指纹分类的目的是提高指纹识别的速度和效率，常见的分类方法有基于神经网络 的分类方法、基于奇异点的分类方法、基于脊线几何形状的分类方法等。指纹匹 配是指纹识别系统的核心之一，其技术关键在于如何尽量减少与克服在图像采集 过程中由于平移、旋转、挤压和拉伸等畸变造成的定位误差，主要的匹配算法包 括图匹配、结构匹配等。在实际应用的自动识别系统中，可以同时采用多种匹配 方法以提高指纹识别系统的可靠性及识别率。 2 武汉理工大学硕士学位论文 ( 2 ) 虹膜识别 虹膜是位于眼睛黑色瞳孔和白色巩膜之间的圆环状部分，总体上呈现一种由 里到外的放射状结构。包含有很多相互交错的斑点、细丝、冠状、条纹、隐窝等 细节特征，这些特征一旦形成终生不变。与其他生物特征相比，虹膜纹理具有高 度的唯一性、稳定性、随机性和防伪性1 6 j 。 为了捕获虹膜所具有的独特的空间特征，利用一系列二维g a b o r 滤波器对虹 膜图像进行分解，将虹膜图像编码为2 5 6 1 3 的虹膜码。匹配识别，一般利用两幅 图像虹膜码的海明距离来表示匹配度，这种匹配算法的计算量极小，可用于在大 型数据库中识别。由于虹膜的环状结构提供了天然的极坐标系，因此，图像处理 起来极其方便，但同时需要专门的摄像仪器来获取虹膜图像信息。 ( 3 ) 视网膜识别 视网膜识别是利用视网膜上的血管分布模式进行身份识别。视网膜读取器感 知人眼后面的视网膜脉络模式时，使用者的眼睛与设备应在1 5 r a m 之内，而且取 图像时眼睛必须处于静止状态，特征提取可获得4 0 0 多个特征点。视网膜是一种 极其稳定的生物特征，因为它是“隐藏”的，不会被伪造，使用时不需要和设备 进行直接的接触，同时，这种技术具有高度的准确性。但是视网膜识别的过程中， 图像的摄取难度较大，摄像头的激光必须直接通过角膜才可获得视网膜图像。因 此，这种技术具有一定的个人侵犯性质，可接受程度要略微低一些。此外，视网 膜扫描对戴着隐形眼镜或闭着眼睛的照片都不能进行精确识别，眼镜的反光同样 会影响视网膜识别。 ( 4 ) 掌纹识别 掌纹识别是利用手腕和手指之间的手掌内侧纹理进行身份识别的生物特征 识别技术。与指纹识别相比，掌纹识别的可接受程度较高，它的特征比指纹特征 也要明显和稳定些。 通常所说的掌纹就是指手掌中的主线、褶皱和脊线。在识别过程中，目前应 用最多的是主线特征和褶皱特征，其他可应用的信息还包括：手掌的长度、宽度 和面积、三角区域特征、细节特征等。人们对掌纹识别的研究历史并不长，但这 种生物特征识别技术极具发展潜力。近年来p c 机处理器速度有了大幅提高，各 种模式识别理论以及神经网络不断发展，掌纹自动识别技术的研究也有了很大进 展。由于掌纹图像面积较大，使得掌纹识别系统难于小型化，限制了其在某些自 动识别领域中的应用。另外，掌纹面积较大也给图像处理带来一定难度。随着计 算机处理速度的提高和存储容量的增大，掌纹识别系统会得到快速发展。 ( 5 ) 人脸识别 人脸识别是一种最自然、最直观、最容易被接受的生物特征识别技术。人脸 武汉理工大学硕士学位论文 识别的过程包括人脸检测定位和脸部特征提取两大部分。人脸检测定位的思想首 先是为脸部建模，通过将所有待测区域与人脸模型比较，从而确定脸部在图像中 的位置。由于人脸受人的表情、光照、图像质量等因素的影响，所以提取脸部特 征的困难较大。目前人脸特征提取和识别的主要方法有：基于脸部几何特征的方 法、基于特征脸的方法、神经网络的方法、局部特征的方法、弹性匹配的方法等。 ( 6 ) 语音识别 语音识别技术是一种基于人的行为特征而进行的识别技术，每个人都有自己 的发音器官特征以及说话时特殊的语言习惯，这些都反映在声音信号当中。 对于语音识别系统的实现必须解决两个基本问题：一方面是识别算法对语音 特征描述的准确性，如模板匹配法、统计建模法和用神经网络实现等：而另一个 重要的方面就是语音信号的特征提取，确定哪些是能够唯一表征个体的有效且可 靠的特征参量。但研究表明，无论是单一基于声道的l p c c 、基于临界带的m f c c ， 还是基于多种特征组合，由于客观环境的变化及人身体情况的变化，都很难作为 普遍适用的说话人特征。因此，寻找具有良好性能的特征及其提取算法是提高识 别系统性能的根本途径。 1 2 签名验证技术 1 2 1 签名验证技术概述 同1 1 - 3 节中提到的6 种方法一样，签名验证技术同样是目前热门的生物特 征识别方法。 签名是一种行为特征，它是随着时间逐步成形的个人自身的行为。人们在长 期书写过程中产生各自独有的文字书写方式，表现为不同的书写力道、笔划书写 顺序、笔划连接方式、局部装饰笔划等。而签名作为一种特殊的书写行为，继承 了笔迹的独特性，因此签名可以作为辨识个人身份的一种有效生物特征【。 签名验证是建立在每个人的签名都有自己独特的理解和写法，并且相对稳定 的基础之上的。签名不仅代表了签名者的信息，而且签名的某些内在的具有唯一 性的特征与产生签名这一信息的特定生物力学系统有关【7 】【3 】。 与其它主要的生物特征识别方法相比，采用签名进行身份识别有如下优点： ( 1 ) 签名作为一种用户的习惯行为，不会被遗忘。 ( 2 ) 自然性。签名是用户经常进行的活动，属于一种容易接受的信息采集模 式。在身份识别过程中，用户可以和平时一样，在很自然的方式下提供签名。与 其它生物特征相比，这是一个很大的优势，例如：虹膜识别虽然具有很高的识别 率，但是在数据采集阶段用户必须将眼睛睁大，站在仪器的有效感受范围内，并 4 武汉理 ：大学硕士学位论文 较长时间保持特定的姿势，这对用户而言是很不舒适的。 ( 3 ) 共享性。正因为签名是独特的，长久以来人们使用签名，并信任签名所 代表的内涵。在现代的金融领域，用户可签署函件赋予他人以代理人的权力，或 以支票的形式使他人间接地使用自己的签名，从而他人可以享有用户的部分权 力。这是用其它的生物特征所无法实现的唧。 签名一般可以通过两种途径获得，即：在线( o n - l i n e ) 蔓j 式和离线( o f f - l i n e ) 方 式。相应地，签名验证也可分为在线签名验证和离线签名验证两种。在在线签名 验证中，签名被表示成一种或几种随时间变化的信号序列，其中包含有签名的动 态信息，因此在线签名验证也称为动态签名验证。而在离线签名验证中，签名是 以所提取的二维图像特征的形式来描述的，故也称之为静态签名验证。一般说来， 在线签名识别的验证率较高，因为这种方式的特征是以输入信号的方式获得的， 可以利用书写过程中笔尖运动的速度、加速度、压力等作为识别用特征。而对于 离线签名验证，由于书写过程中的动态信息几乎全部丢失，只能依据签名图像的 静态信息，即每个人笔迹的特点和相对稳定性来有效反映签名的书写风格和书写 习惯，因此识别难度比较大，识别率也相对较低l l o j 。 本文主要讨论的是在线签名的验证技术。 1 2 2 签名验证技术国内外研究现状 由于发达国家的信息通讯技术起步早、发展快，其普及和使用程度已达 到较高的水平，而且他们的计算机管理和自动化技术亦有相当的普及率和较 高的现代化程度，因而计算机身份技术已逐步受到广泛的注意和研究。 而中文与英文识别又有着很多区别。英文签名速度较快，在y 轴上变化幅 度较小，中文则为一笔一划书写，速度较慢，坐标轴益线较明显。英文字母出现 在文本行中，其大小、高度与汉字中的偏旁部首很类似，难以区分是汉字偏旁部 首，还是英文字母；英文签名单词中字母之间的距离不等，粘连也相当普遍；汉 字签名是以横、竖等笔划为基本结构的，而英文签名则是以曲线为主。 就机理而言，签名验证同时也会涉及到哲学、心理学、生理学等许多学科 的问题，但目前的科学技术尚不能揭示手写签名的人工鉴定机制( 尚未能解释大 脑活动的机理和人类智能的本质) ，就目前的研究现状而言，利用计算机进行签 名验证的理论，从一开始就是以功能实现为目标建立的，即不追究手写签名人工 鉴定机制到底如何，只要能够实现同样的功能即可。 签名验证算法主要有参数法和函数法两大类。比较有代表性的有：d a r w i s h 和a u d a 用神经网络作为分类器，对前人提出的总共2 1 0 个签名特征参数做了比 较研究，最后共有1 2 个特征参数被选中。对9 个书写人提供的每个人1 6 个签名， 武汉理工大学硕士学位论文 8 个作为样本签名生成参考模板，8 个作为被测签名用反向传播神经网络作为 分类器，得到结果误拒率f r r ( f a l s er e j e c t i o nr a 哟为1 4 ，他们没有对伪造签 名进行实验研究i l ”。 l a i n 和m c c o r m a c k 则尝试用傅立叶变换的方法进行签名验证，对不同的签 名采用最高的1 5 个谐波作为认证特征。但是，该研究只用了一个真实签名和1 9 个对真实签名的伪造签名，难以作出较实际的性能评价【1 2 】【1 3 1 。 m o h a n k r i s h n a n 和p a u l i k 提出了一个基于自回归( a u t o r e g r e s s i v e ) 模型的签 名认证方法签名被看作一个由不同类型曲线连接的曲线序列，每个签名被分割成 8 段，而每段用一个自回归模型描述，每段由三个参数表征，因而每个签名由一 个有2 4 个元素的特征矢量描述。针对随机伪造签名，每个实验对象采用不同的 阈值，使误纳率f a r ( f a l s e a c c e p t a n c e 啮) 和f r r 相等，总错误率最低为7 9 2 ， 最高为2 1 8 3 嘣。 y a n g 和w i d j a j a 提出了隐马尔可夫模型( h i d d e n m a r k o v m o d e l ) 法，但发现鉴 别结果并不理想i l ”。 c o n n e l l 提出了基于特征矢量匹配的方法【1 6 】，同时指出选取特征值应满足简 单易计算，不受平移、旋转、尺度缩放的影响等要求。 n a k a n i s h i 采用离散小波变换d w t ( d i s c r e t ew a v e l e tt r a n s f o r m ) 来分解签名的 参数特征，对签名波形进行了8 级小波分解，利用压力进行自然分割，特征提取 用到自适应算法，匹配则选择动态规划方法，在小波分解的第8 级，伪造签名和 真实签名的差异较大【1 7 1 。 l i u 、h e r b s t 较早研究笔尖压力的参数性能，他们将压力信号与加速度参数 综合起来，用求相关函数值的匹配方式对签名进行认证，使f r r 达1 6 和f a r 不大于i l 。 n e l s o n 和k i s h o n 对h a s t i e 等提出的方法做了详细的实验分析，他们共使用 了2 0 0 个真实签名和数十个伪造签名。他们发现笔尖压力和速度在同一人的签名 样本中显出很高的重复性，因而具有较好的表征特性。他们的观点认为签名的形 状和动态特征在认证分析中起着相互补充的作用。因为对一个伪造签名来说，要 想使形状相似，就很难使动态特征相似，反之亦然【1 9 1 。 b r a u l t 和p l a m o n d o n 提出了一种手写签名的分段方法。他们所抽取的分段点 是签名曲线中曲率的极大点，即拐点( i n f l e c t i o np o i n t ) 。从拐点处将签名分开后， 每段的长度不会很长，变化也比较平稳，容易实现点之间的匹配【2 0 】。 就技术应用情况而言，当前，国内有很多科研单位和企业参与了签名验证 技术的研发，但绝大多数是引进国外签名验证模块进行系统集成，只有少数企业 拥有自己的算法，并且产品价格高，性能不稳定，其性价比不能满足市场的需求。 6 武汉理工大学硕士学位论文 相比之下，国外的签名验证技术从数据采集系统到处理、验证算法都相对成熟一 些。许多公司都有专门的机构从事该项技术的研发与应用，包括m m 、 c y b e r - s i g n 、美国智通、日本富士通等，其中美国智通公司在此领域的研究独树 一帜。 国内方面，9 0 年代后，我国许多大学和研究机构的学者也对手写汉字签名认 证进行了研究和探讨。主要有中国科学院自动化所的戴汝为、谭铁牛、王蕴红， 清华大学电子工程系的丁晓青，中国科技大学电子科学与技术系的施泽生，华中 理工大学计算机科学和技术学院金先级、裴先登以及该校图像识别与人工智能研 究所的柳健等，吉林大学在此基础上，分别与清华同方股份有限公司、北京密安 信息和通讯技术有限责任公司签订了合作开发协议【2 1 1 1 2 2 2 3 1 2 4 2 5 1 。 1 3 课题研究内容及论文组织结构 1 3 1 课题研究内容 本课题是“智能在线签名识别技术及系统设计”项目的子课题“基于演化计 算的在线签名验证”。主要的研究内容是利用目前在数学领域内应用广泛的演化 计算理论，解决在线签名的验证问题。 文章着重提出了演化计算运用于在线签名验证领域的方法，并给出了数学模 型。在数学模型的指导下，给出了完整的一套签名匹配的方案，并且对基于演化 计算的在线签名验证方案进行了实验，实验的结果证实了这种方案的可行性。 1 3 2 论文的组织结构 整篇论文分为7 章，内容组织如下： 第一章绪论：主要介绍了课题的研究背景、研究内容、在线签名验证的意义、 国内外现状以及所面临的问题。 第二章数据采集及预处理：介绍了通过手写板采集到的签名信息，以及对这 些签名信息的预处理，包括去掉飞点、漏电以及归一化等处理。 第三章演化计算：主要介绍了目前在数学上广泛应用的演化计算理论，包括 演化计算的性质以及基本算法。 第四章基于演化计算的签名验证：将演化计算和签名验证结合起来，给出了 数学模型，并且给出了基于演化计算的签名验证的具体算法。 第五章签名曲线的动态分割匹配：介绍了对签名曲线的动态分割。通过比较 几种传统的分割方法，提出了对签名曲线的动态分割方法，并详细介绍了这种动 态的分割方法。 7 武汉理工大学硕士学位论文 第六章实验结果分析：对基于演化计算的签名验证方案进行了比较详细的实 验，给出了实验数据和对实验数据的分析，并且提出了各种参数的较为恰当的取 值。 第七章总结与展望：总结了研究的不足，并提出了进一步需要解决的问题以 及研究方向。 8 武汉理工大学硕士学位论文 第2 章签名数据采集及预处理 2 1 签名数据的采集 签名数据获取工作主要由电阻式触摸屏和触摸屏控制器a d s 7 8 4 6 完成。主 要负责笔迹的包括压力信息在内的多维数据信息的采集，为后面的验证提供原始 的数据。a d s 7 8 4 6 根据控制系统的命令，向触摸屏发出对应的指令，然后接受 从触摸屏返回的模拟信号，并将其转换成数字信号，传回给控制系统网。该实 验中，对签名数据采样的间隔是每5 m s 采集一个数据。 液晶同步显示部分主要点阵式液晶显示屏和液晶控制器s e d l 3 3 5 组成。 s e d l 3 3 5 的控制能力非常灵活、快速【2 9 】。控制器s e d l 3 3 5 收到微控制器传来的 数据，转化成液晶屏的点阵数据，从而在液晶屏上显示出来。该部分作为一个实 时显示部分显示采集点的轨迹，以构成笔画供使用者作动态参考。 为了使书写者能更加直观的了解书写的笔迹，系统把书写的笔迹显示到液晶 屏上。根据实际书写的需要和习惯，选择了台湾晶彩光电科技有限公司的型号为 a t - 3 2 0 2 4 0 q 2 带有内置控制器的液晶显示屏，它是分辨率为3 2 0 2 4 0 的点阵式 f s t n 液晶屏。外观尺寸9 2 2 r a m ( w ) 7 3 o m m ( i - 王) 。 数据采集系统的原理图如图2 1 所示。 图2 一l 签名数据采集系统原理图 签名数据采集系统采集到手写签名的3 个信息：签名的x 坐标、签名的y 坐标以及签名的压力坐标。 设某签名的签名图如图2 2 所示。 9 武汉理工大学硕士学位论文 ，1 图2 2 某签名的签名图 则对图2 2 的签名，数据采集系统采集到的签名信息如下( 篇幅所限，只提 供部分数据) ： u n s i g n e di n tc o u n t = 1 5 6 1 ； u n s i g n e di n tx f l 2 9 1 7 ， 9 0 8 ， 9 1 2 ， 9 2 1 ， 9 l & 9 1 3 ， ) u n s i g n e d h a ty 口= 9 8 5 ， 9 9 0 ， 9 8 9 ， 9 8 3 ， 9 9 1 ， 9 8 9 ， u n s i g n e di n tz f l 。 l o 武汉理工大学硕士学位论文 2 3 8 ， 2 4 0 ， 2 4 2 ， 2 4 2 ， 2 4 3 ， 2 4 3 ， 签名信息第一行显示采集到的点数为1 5 6 1 个，其中每个点都有x 坐标、y 坐标以及压力坐标，也就是说x 、y 、z 数组都各自有1 5 6 1 个数据。第二行提示 下面是x 数组的信息，这里储存的是每个点的x 坐标信息，同样的，y 数组储存 的是每个点的y 坐标的信息，z 数组储存的是每个点的压力坐标的信息。 将以上的签名信息保存为后缀为h 的文件，这样就可以利用v c 以及m a t l a b 等工具进行处理了。 2 2 签名数据的预处理 对于签名数据的预处理，主要的工作是去噪、平滑信号，有时也包括对签名 数据的归一化。适当的预处理可对由于输入测量仪器或其他因素所造成的退化现 象进行复原，同时也有利于后续的验证验证工作。 l 、滤波：滤波包括对签名信号的去噪、平滑。如剔出虚假抬笔，可以采用 中值滤波；去除噪声，可以采用平滑滤波等。 2 、去零点：对签名数据的预处理，去零点不是必须的，但是有些方法需要 去除掉签名数据的零点。基于演化计算的签名验证方法中，不仅需要去掉签名数 据的零点，同时还要记录签名数据中连续出现3 0 个零点的位置。 3 、归一化：归一化处理包括按时间归一化，按位置归一化，旋转处理，恒 定分量的删除，按幅度大小归一化。通过归一化处理后，签名特征应具有时间、 位置、幅度等不变性，只与书写个性有关。在本方法中，需要对参与匹配的测试 签名和参考签名进行长度归一化 图2 3 是图2 - 2 签名原始波形的x 分量、y 分量和压力分量的原始波形。 武汉理工大学硕士学位论文 ( a ) x 坐标分量 魁 馨 ( b ) y 坐标分量 时间5 m s ( c ) 压力坐标分量 图2 3 签名原始波形 图2 - 4 是原始波形经过滤波和去零点后的波形。 ( a ) x 坐标分量 1 2 ( ”y 坐标分量 武汉理工大学硕士学位论文 魁 孽 rm i 时问s m s ( c ) 压力坐标分量 图2 4 经过预处理后的波形 武汉理工大学硕士学位论文 3 1 演化计算的性质 第3 章演化计算 近3 0 年来，人们从不同的角度对生物系统及其行为特征进行了模拟，产生 了一些对现代科技发展有重大影响的新兴学科。例如，对人类模糊思维方式的模 拟产生了模糊集合理论；对动物脑神经的模拟产生了人工神经网络理论；对自然 界中动、植物免疫机理的模拟产生了免疫算法；而对自然界中生物进化机制的模 拟，就产生了演化计算e c ( e v o l u t i o n a r y c o m p u t a t j o n ) 。- - 、 3 0 1 。 演化算法与传统的算法有很多不同之处，但最主要的差别在于演化计算具有 智能性和本质并行性的特征。 演化计算的智能性包括自组织、自适应和自学习等【3 l 】。应用演化计算求解 问题时，在确定了编码方案、适应值函数及遗传算子之后，算法将利用演化过程 中获得的信息自行组织搜索。由于基于自然的选择策略为适者生存、不适者淘汰， 故而适应度好的个体具有较高的生存概率，通常适应度好的个体具有比较好的适 应环境的基因结构，再通过杂交和基因突变等遗传操作就可能产生更适应环境的 后代【，2 】。演化算法的这种自组织、自适应特征同时也赋予了它具有能根据环境 的变化自动发现环境的特性和规律的能力。此外，自然选择消除了算法设计过程 中的一个最大障碍，即需要事先描述问题的全部特点，并说明针对问题的不同特 点算法应采取的措施。于是，利用演化计算的方法就可以解决那些结构尚无人理 解的复杂问题 3 3 j 。 演化计算的本质并行性表现在两个方耐卅： l 、演化计算是内在并行的( i a t r i n s i cp a r a l l e l i s m ) ，即演化算法本身非常适合 大规模并行，最简单的并行方式是让几百甚至数千台计算机各自进行独立种群的 演化计算，运行过程中甚至不进行任何通信比较，选取最佳个体，这种并行处理 方式对并行系统结构也没有什么限制和要求。可以说，演化计算适合在目前所有 并行机或分布式系统上进行并行处理，而且对其并行效率没有太大的影响。 2 、演化计算的内含并行性( i m p l i c i tp a r a l l e l i s m ) ，由于演化计算采用种群的方 式组织搜索，从而它可以同时搜索解空间内的多个区域，这种搜索方式使得它虽 然每次只执行与种群规模成比例的计算，而实质上已进行了大约d ( 3 ) 次有效 搜索【3 5 】。从而演化计算能以较少的计算取得较大的收益。 1 4 武汉理工大学硕士学位论文 3 2 演化计算的基本算法 演化计算求解问题的基本思想相当简单：由问题的候选解组成一个种群，然 后通过随机变化和选择等算子进行演化。其中随机变化提供了发现新解的机制， 选择则确定保持哪些解作为下一步搜索的基础【3 6 】。 适应度( f i t n e s s ) 是演化计算中的一个重要的概念，是演化计算中评价一个个 体优劣的唯一标准，反映了该个体对于生存环境的适应程度【3 0 】。演化计算的目 的就是找到合适的评价问题的适应度函数，然后通过演化计算的基本算法找到适 应度最优的个体，从而找到问题的最优结果。 3 2 1 2 4 节将着重分析演化计算的基本算法。 3 2 1 群体的分级 随机产生一组初始个体构成初始群体，评价每个个体的适应度值。根据适应 度值的大小，将个体排序。设群体有个个体，将这个个体分为三级，假设 个体而( f ) 经过排序，排在第k 位，若k n l ，则个体耳为第一级，若 n l 毒 2 + n l ，则个体而处于第二级，依次类推，将全部个个体分 级，其中适应度值越大的个体，分的级数越小。 3 2 2 新解产生的规则 在对个个体组成的群体进行分级后，将对每一级的个体确定其在下一步 的加速搜索过程中的领域半径和产生子个体的数t 3 n 。一般而言，级数越小的 个体，领域半径越小，产生子个体的数目越少。如图3 1 所示，要找出函数厂( 功 o 图3 1 级别越小的个体，搜索半径越小，产生的个体越少 武汉理工大学硕士学位论文 的最小值m i n f ( x ) ，设有两个个体而，而，个体五的级数小于个体而，即 ，( 薯) l 2 ) ，在其领域半径4 = x l d s c x , ，工) _ 中，随机 产生个子个体即可。 3 2 4 全局选择 在加速搜索中级数小的丹维个体进行单纯形加速，产生c 个子个体，加上 个体本身，一共c + 1 个个体；级数大的个体进行随机搜索，产生魄个子个体， 加上个体本身，一共粥+ 1 个个体。根据适应度值的大小，每个个体从中选择最 好的两个，进入全局选择。 个个体，每个个体在其领域内选出两个进入全局选择。对这2 n 个个体进 行选择运算，选出适应度值最好的个个体进入下一代。 下一代的个体再通过上述步骤周而复始地演化下去，直至到满足算法的终止 条件。算法的终止条件有：l 、完成预先给定的演化代数；2 、种群中的最优个体 在连续若干代没有改进或平均适应度值在连续若干代基本没有改进；3 、所求问 题的最优解达到了某一精度l 鲫j 。 3 3 演化计算的分析 演化计算理论，是模拟自然界中生物进化的机制，遵循“适者生存，物竞天 择”的原则对问题的候选解进行选择、淘汰，从而最终收敛到最优解的一种算法。 在演化计算中，对于适应度值较好的个体进行单纯形加速，其目的是为了能够找 到