（计算数学专业论文）生物识别技术中的智能算法.pdf

摘要 随着信息技术的发展和对信息安全的日益迫切需求。基于生物特 征的个人身份识别技术也得到了飞速发展。基于生物特征的识别技术 是- - f - 利用人类特有的个体特征来验证个人身份的科学，它提供了一 种基于唯一的、高可靠性和稳定性的人体生物特征的新的身份鉴别途 径，是种最安全的身份识别方式。常用的生物特征包括：指纹、虹 膜、人脸、声音、笔迹等。另一方面，本文提出了一种基于粒子群与 模拟退火算法相结合的进化算法。这种算法利用模拟退火算法全局收 敛性好和粒子群算法收敛速度快等优点，取长补短，通过交换这两种 算法的信息得到最优解。本文将这种新算法应用于图像增强中参数的 自适应选择，指纹图像阂值分割和虹膜识别中优化p n n 的平滑参数， 实例计算表明该算法稳定性好，在收敛速度和求解精度方面都优于遗 传算法等一些其它进化算法。 全文共分四章，在第一章，首先介绍了生物识别技术的研究背景， 实际意义以及当前国内外研究的大致情况。 在第二章，简单介绍了模拟退火算法和粒子群算法的研究历史， 生物背景，继而提出了一种基于粒子群与模拟退火算法相结合的进化 算法。这种算法利用模拟退火算法全局收敛性好和粒子群算法收敛速 度快等优点，取长补短，通过交换这两种算法的信息得到最优解。 在第三章，提出了生物识别技术中的智能算法。将这种算法应用 于灰度图像的自适应增强，指纹图像阈值分割和虹膜识别中优化p n n 的平滑参数。 第四章，给出大量实例证明本文提出的方法简单可行，在收敛速 度和求解精度方面都优于遗传算法等些其它进化算法。 关键词：生物识别技术，模拟退火算法，粒子群算法， 图像增强，虹膜识别 a b s t r a c t t h er e c e n ta d v a n c e so fi n f o r m a ti o nt e c h n o l o g ya n dt h e i n c r e a s i n gr e q u i r e m e n tf o rs e c u r i t yh a v er e s u l t e di nar a p i d d e v e l o p m e n to fi n t e l l i g e n tp e r s o n a l i d e n t i f i c a t i o nb a s e do n b i o m e t r i c s b i o m e t r i ci d e n t i f i c a t i o nt e c h n o l o g yi sak i n do f s c i e n c e so fu s i n gi n d i v i d u a lp e r s o n a lc h a r a c t e r i s t i c st o v e r i f yi d e n t i t y i tr e p r e s e n t st h em o s ts e c u r ew a yt oi d e n t i f y i n d i v i d u a l sb e c a u s ei tp r o v i d e san o v e la p p r o a c ht or e c o g n i z e t h ei d e n t i t y ，o rv e r i f yt h ec l a i m e di d e n t i t yt h r o u g ha u n i q u e h i g h l yr e l i a b l ea n dr o b u s tp h y s i c a lc h a r a c t e r i s t i co r p e r s o n a lt r a i t g e n e r a l l y ，b i o m e t r i c si n c l u d et h ef o l l o w i n g ： f a c i a lf e a t u r e ，i r i s ，g a i t ，v o i c e p r i n t ，g e s t u r e ，f i n g e r p r i n t s ， h a n d w r i t t e ns i g n a t u r ea n ds oo n 0 nt h eo t h e rh a n d 。t h i sp a p e r p r o p o s e dan o v e lc o o p e r a t i v ee v o l u t i o n a r ya l g o r i t h mb a s e do n s i m u l a t e da n n e a l i n ga l g o r i t h m ( s a )a n d p a r t i c l e s w a r m o p t i m i z a t i o n ( p s o ) z h i s u e wm e t h o du t i l i z e s t h e g l o b a l c o n v e r g e n c ep r o p e r t yo fs aa n dt h ef a c i l i t yo fr e a l i z a t i o no f p s o ，w h i l ei ta t t a i n sa no p t i m a ls o l u t i o nb ym e a n so f t h e i n f o r m a t i o ne x c h a n g e so ft h e s et w ok i n d so fa l g o r i t h m s r e s u l t s o f e x p e ri m e n t s s h o w t h a tt h ep r o p o s e da l g o rit h mp e r f o r m e d b e t t e ri nc o n v e r g e n c es p e e da n dp r e c i s i o no fs o l u t i o n st h a n h i g a ，p s o ，a n d s a i ti sa ne f f i c i e n tm e t h o di nb i o m e t r i c i d e n t i f i c a t i o nt e c h n o l o g y t h i sa r t i c l ei sd i v i d e di n t of o u rp a r t s t h ef i r s tc h a p t e r i n t r o d u c e st h eb a c k g r o u n da n da p p l i c a t i o no ft h eb i o m e t r i c i d e n t i f i c a t i o nt e c h n o l o g ya n dt h el a t e s tr e s e a r c hi nt h ew o r l d t h es e c o n dc h a p t e rb r i e f l yi n t r o d u c e st h er e s e a r c hh i s t o r y o fs i m u l a t e da n n e a l i n ga l g o r i t h ma n dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h ma n db i o l o g i c a lb a c k g r o u n da tt h eb e g i n n i n g t h e np r o p o s e dan o v e lc o o p e r a t i v ee v o l u t i o n a r ya l g o r i t h mb a s e d o ns i m u l a t e d a n n e a l i n ga l g o r i t h m ( s a ) a n dp a r t i c l e s w a r m o p t i m i z a ti o n ( p s o ) t h i sb e wm e t h o du t ili z e st h eg l o b a l c o n v e r g e n c ep r o p e r t yo fs aa n dt h ef a c i l i t yo fr e a l i z a t i o no f p s o ，w h i l e i ta t t a i n sa no p t i m a ls o l u t i o nb ym e a n so ft h e i n f o r m a t i o ne x c h a n g e so ft h e s et w ok i n d so fa l g o r i t h m s r e s u l t s o fe x p e r i m e n t ss h o wt h a tt h e p r o p o s e da l g o r i t h m p e r f o r m e d b e t t e ri nc o n v e r g e n c es p e e da n dp r e c i s i o no fs o l u t i o n st h a n g a ，p s o ，a n ds a i nt h i r dc h a p t e r ，w e a p p l yt h e f o r m e ra l g o r i t h mi n b i o m e t r i ci d e n t i f i c a t i o nt e c h n o l o g y t h ef o r t hc h a p t e rg i v e sal o t so fe x a m p l e s ，w h i c hp r o v et h a t t h ea l g o r i t h mw ep r e s e n ti sf e a s i b l ea n ds i m p l e ，i ti sa n e f f i c l e n tm e t h o di nb i o m e t r i ci d e n t i f i c a t i o nt e c h n o l o g y i v k e yw o r d s ：b i o m e t r i ci d e n t i f i c a t i o nt e c h n o l o g y ；s i m u l a t e d a n n e a l i n g ；p a r t i c l es w a r m t i m i z a t i o n ；i m a g e e n h a n e , e m e n t ：i r i sr e c o g n i t i o n v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 、川 学位论文作者签名：勿汐i 。 厶o ( 年二月q 日 a 3 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 4 、。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 作者签名 导师签名 1 、保密口，在年解密后适用本授权书。 ， 2 、不保誉卤。 ( 请在以上相应方框内打“ ”) 6 月 f1 曰 占月汗日 年 年 q 7 沙 期期祀 日 日 生物识别技术中的智能算法 1 1 生物特征识别技术 1 绪论 信息技术已经渗透到我们生活的方方面面，无论我们学习、工作、 交流、出行、休闲、娱乐，几乎所有的日常活动或多或少与信息技术 都有关联，人类社会与信息技术结合得日趋紧密，也是因为这个原因， 信息的安全性日趋为人们所重视。对个人来说，敏感的私人数据、电 子邮箱、即时通讯工具、移动电话、银行卡这些貌似没有太大关联的 东西都与信息安全扯上了关系，一旦这些信息泄露，用户将可能遭受 不可挽回的巨大损失。而对高度发达的互联网来说，信息的安全性更 是重中之重：电子商务、网络银行、敏感数据传输、语音交互所 有这一切都是在一个开放的网络上进行，如果信息安全得不到保障， 将对互联网发展造成致命的打击。 随着a t m 取款机、电脑、移动电话、门禁系统等电子设备步入 日常生活，人类越来越依靠智能卡、身份证号码、密码等保护措施来 安全、方便地识别身份。然而，这些传统的身份认证方法( 智能卡、 身份证号码、密码) 却易于丢失、窃取、伪造、遗忘，给生活和工作 带来极大的安全隐患。以信用卡为例，国际信用卡组织v i s a 的一个 统计表明，全球每年因伪卡、盗卡造成的信用卡的消费损失高达1 6 亿美金。在信息技术飞速发展的今天，电子商务、电子银行、网络安 全等应用领域更是急需高效的自动身份认证技术，传统的个人身份认 证己不能很好地满足信息时代对于信息安全的要求。如何才能更加安 1 硕士学伊论文 全、方便地识别每个人的身份呢? 悄然兴起的生物识别技术也许能解 决这个难题。 生物识别技术( b i o m e t r i ci d e n t i f i c a t i o nt e c h n o l o g y ) 是利用人体生 物特征进行身份认证的一种技术【l 】生物特征是唯一的( 与他人不同) ， 可测量或自动识别和验证的生理特性或行为方式，分为生理特征和行 为特征。生理特征与生俱来，多为先天性的；行为特征则是习惯使然，多 为后天性的。将生理和行为特征统称为生物特征。常用的生物特征包 括：指纹、虹膜、人脸、声音、步态、笔迹、静脉等。与传统的身份 鉴定手段相比，基于生物特征识别的身份鉴定技术具有以下优点：1 ) 不易遗忘或丢失；2 ) 防伪性能好，不易伪造或被盗；3 ) “随身携 带”，随时随地可用。 生物识别技术是一个既古老又新潮的技术。以指纹识别为例，可 以追溯到几千年前的秦始皇时代。至唐朝，以“按指为书”为代表的 指纹捺印已经在文书、契约等民用场合被广泛采用。自宋朝起，指纹 则开始被用做刑事诉讼的物证。虽然我国对指纹的应用历史悠久，但 由于缺乏专门性研究，未能将指纹识别技术上升为- - l - j 科学。现代指 纹识别则起源于1 6 世纪后期。苏格兰医生h e n r y f a u l d 于1 8 8 0 1 0 2 8 首次在英国 n a t u r e 上发表论文，指出指纹人各不同，恒久不变，并利 用现场指纹来鉴定罪接着，w i l l i a m h e r s c h e l 也在( n a m e ) ) 上发表了关 于指纹研究2 0 多年来的成果，从而揭开了现代指纹识别的序幕到现 在，随着电子计算机技术的高速发展、采集系统的日臻完善、识别算 法的不断优化，人们逐渐由人工的指纹识别转向了自动指纹识别研究 2 生物识别技术中的智能算法 从1 9 世纪7 0 年代开始，自动指纹识别技术就逐步渗透到金融、医疗、 保险、海关、政府机构等诸多领域与此同时，作为个人身份认证的虹 膜、人脸、步态等非接触式生物识别技术，也引起了人们的极大关注 欧盟国家打算从2 0 0 5 年起，使用含有具有生物识别数据( 面部或虹膜 信息) 的新型护照国际生物集团的统计表明：目前国际生物特征识别 技术的市场已达l o 亿美元叠u 2 0 0 5 年底市场将达到2 2 亿美元的水平。 同时，市场每年将以超过8 0 的速度增长 2 0 0 7 年可达4 l 亿美元。业 内专家保守估计，未来5 年，我国也将形成近百亿元的市场。甚至比尔 盖茨也在2 0 0 4 年的r s a 安全会议上声称：传统密码将成为过去，微软 内部已经在使用能够储存指纹资料和眼球的扫描信息的智能卡系统 来代替密码。 进行身份认证时，生物识别系统工作模式分为验证模式 ( v e r i f i c a t i o n ) 和辨识模式( i d e n t i f i c a t i o n ) 两类【2 】验证模式又称一对一 匹l 酝d ( o n e t o o n e m a t c h i n g ) ，匹配原理为：生物特征预先登记到样本数据 库并设定一个标识码匹配时，录入生物特征并输入标识码，系统根据 标识码从数据库中提取特征样本与录入样本进行比较辨识模式又称 一对i e 配( o n e t o m a n y m a t c h i n g ) ，是把录入生物特征与样本数据库中 的所有样本逐一进行比对，直至找到相匹配的样本或搜索完整个样本 数据库后给出无对应特征的结论一般来讲，生物识别系统一般由4 大 步骤组成第l 步，通过图像采集系统采集生物特征图像；第2 步，对生物 特征图像预处理( 定位、归一化、图像增强等) ；第3 步，提取特征信息， 转化成数字代码；第4 步，将代测代码与数据库中的模板代码进行比对， 3 坝士学位论文 做出识别。 综观国内外生物识别技术的发展，未来的生物识别技术将向着 复合认证和更广泛的应用领域发展。首先是生物识别技术与智能卡等 多种识别技术的结合，以提高安防等级。其次是生物识别产品的应用 范围进一步扩大，更多涉及商业及民用领域。目前生物识别技术正趋 向于向高精度的专业化、简约化、普及化发展，在保证精度的前提下， 简化采样与算法的技术结构，达到设备小巧、价格低廉的普及化要 求。我国的生物识别产业，今后的发展主要表现在芯片的自主开发、 软件接口的标准化、产品的价格和可靠性等。比尔盖茨认为：“以 人类生物特征( 指纹、语音、脸像等) 进行身份验证的生物识别技术， 在今后数年内将成为i t 产业最为重要的技术革命。”人们常说：“只有 自己才是最可靠的”，生物特征，将是人类永远的身份证! 1 2 指纹识别 目前所有生物特征识别技术中，指纹识别无论在硬件设备还是软 件算法上都是最成熟、开发最早、应用最广泛的。据相关资料显示， 我国古代最早的指纹应用可追溯至秦朝。至唐朝，以“按指为书”为 代表的指纹捺印已经在文书、契约等民用场合被广泛采用。自宋朝起， 指纹则开始被用做刑事诉讼的物证。在欧洲，1 7 8 8 年，梅耶( j m a y e r ) 首次提出没有两个人的指纹会完全相同；1 8 8 9 年，亨利( e r h e n r y ) 在总结前人研究成果的基础上，提出了指纹细节特征识别理论，奠定 了现代指纹学的基础。指纹识别技术从被发现时起，就被广泛地应用 4 生物识别技术中的智能算法 于契约等民用领域。由于人体指纹具有终身稳定性和惟一性，很快就 被用于刑事侦查，并被尊为“物证之首”。但早期的指纹识别采用的 方法是人工比对，效率低、速度慢，不能满足现代社会的需要。2 0 世 纪6 0 年代末，在美国开始有人提出用计算机图像处理和模式识别方法 进行指纹分析以代替人工比对，这就是自动指纹识别系统( 简a f i s ) 。 因为成本及对运行环境的特殊要求，开始时其应用主要限于刑侦 也叫警用领域。随着计算机图像处理和模式识别理论以及大规模集成 电路技术的不断发展与成熟，指纹自动识别系统的体积不断缩小，其 价格也不断降低，因而被应用到民用领域。2 0 世纪8 0 年代，个人电脑、 光学扫描这两项技术的革新，使得它们作为指纹取像的工具成为现 实，从而使指纹识别可以在其他领域中得以应用，比如代替i c 卡。现 在( 9 0 年代后期) ，低价位取像设备的引入及其飞速发展，可靠的比 对算法的发现为个人身份识别应用的增长提供了舞台。指纹自动识别 技术已在警察司法活动和出入口控制、信息编码、银行信用卡、重要 证件防伪等许多领域广泛使用。 指纹是手指末端正面皮肤上的呈有规则定向排列的纹线。每个 人指纹纹路在图案、断点和交叉点上各不相同，是唯一的，并且终生不 变。人的指纹特征可大致分为两类：总体特征和局部特征 1 。总体特 征是用肉眼就可以直接观察到的纹路图案：环型( 1 0 0 p ) 、弓型( a r c h ) 、 螺旋型( w h o r l ) ，即我们俗称的斗、簸箕、双箕斗。但仅靠这些基本的 图案来进行分类识别还远远不够。在实际应用中，常提取某人指纹的 节点( 指纹纹路中经常出现的中断、分叉或转折) 这个局部特征信息， 硕士学位论文 进行身份认证。指纹节点的信息特征多达1 5 0 多种，但一些细节特征却 极为罕见，常见的节点类型有以下7 种：终结点( 一条纹路在此终结) 、 分叉点( 一条纹路在此分开成为两条或更多的纹路) 、分歧点( 两条平 行的纹路在此分开) 、孤立点( 一条特别短的纹路，以至于成为一点) 、 环点( 一条纹路分开成为两条之后，立即合并成为一条，这样形成的一 个小环) 、短纹( 一端较短但不至于成为一点的纹路) 。其中最典型和 最常用的是终结点和分叉结点，在自动指纹识别技术中，一般只检测 这两种类型的节点数量，并结合节点的位置、方向和所在区域纹路的 曲率，得到唯一的指纹特征。指纹识别的准确率与输入指纹图像的质 量有着非常重要的关系。由于噪声、不均匀接触等原因，可能导致指 纹图像获取时产生许多畸变、变形。在分析指纹特征时，就会产生大 量的可疑特征点，淹没真实特征点，所以采用平滑、滤波、二值化、细 化等图像处理方法来提高纹路的清晰度，同时删除被大量噪声破坏的 区域。 指纹识别主要包括指纹图像增强、特征提取、指纹分类和指纹匹 配几个部分。 ( 1 ) 指纹图像增强。目的在于提高可恢复区域的脊信息清晰度， 同时删除不可恢复区域，一般包括以下几个环节：规格化、方向图估 计、频率图估计、生成模板、滤波，其主要问题在于利用脊的平行性 设计合适的自适应方向滤波器和取得合适的阈值。h o n g 等 3 采用同 时具有频率选择和方向选择的g a b o r 滤波器来增强指纹图像，能在指 纹图像质量很差的情况下取得很好的效果，并减少了计算局部区域方 6 生物识别技术中的智能算法 向图的开销。 ( 2 ) 特征提取。美国国家标准局提出用于指纹匹配细节的四种特 征为脊终点、分叉点、复合特征( 三分叉或交叉点) 以及未定义。但目 前最常用细节特征的定义是美国联邦调查局f b i 提出的细节模型，它 指纹图像的最显著特征分为脊终点和分叉点，每个清晰指纹一般有 4 0 1 0 0 个这样的细节点。指纹特征的提取采用链码搜索法对指纹纹 线进行搜索，自动指纹识别系统( a f i s ) 依赖于这些局部脊特征及其关 系来确定身份。 另外，指纹图像的预处理和特征提取也可采用基于脊线跟踪的方 法 4 。其基本思想是沿纹线方向自适应地追踪指纹脊线，在追踪过程 中，局部增强指纹图像，最后得到一幅细化后的指纹脊线骨架图和附 加在其上的细节点信息。由于该算法只在占全图比例很少的点上估算 方向并滤波处理，计算量相对较少，在时间复杂度上具有一定的优势。 ，( 3 ) 指纹分类。常见的有基于神经网络的分类方法 5 、基于奇异 点的分类方法 6 、基于脊线几何形状的分类方法 7 、隐马尔可夫分 类器的方法 8 、基于指纹方向图分区和遗传算法的连续分类方法 9 。 一 ( 4 ) 指纹匹配。指纹匹配是指纹识别系统的核心步骤，匹配算法包 括图匹配、结构匹配等，但最常用的方法是用f b i 提出的细节模型来 做细节匹配，即点模式匹配。点模式匹配问题是模式识别中的经典难 题，研究者先后提出过很多的算法，如松弛算法、模拟退火算法、遗传 算法、基于h o u g h 变换的方法等，在实践中可以同时采用多种匹配方 碘七学位论文 法以提高指纹识别系统的可靠性及识别率。 1 3 虹膜识别 与指纹识别一样，虹膜( ir i s ) 识别也是以人的生物特征为 基础，而虹膜也同样具有高度不可重复性。虹膜是眼球中包围瞳孔的 部分，每一个虹膜都包含一个独一无二的基于像冠、水晶体、细丝、 斑点、结构、凹点、射线、皱纹和条纹等特征的结构，这些特征组合 起来形成一个极其复杂的锯齿状网络花纹。而与指纹一样，每个人的 虹膜特征都不相同，到目前为止，世界上还没有发现虹膜特征完全相 同的案例一即便是同卵双胞胎，虹膜特征也大不相同，而同一个人左 右两眼的虹膜特征也有很大的差别。此外，虹膜具有高度稳定性，其 细部结构在胎儿时期形成之后就终身不再发生改变，除了白内障等少 数病理因素会影响虹膜外，即便用户接受眼角膜手术，虹膜特征也与 手术前完全相同。高度不可重复性和结构稳定性让虹膜可以作为身份 识别的依据，事实上，它也许是最可靠、最不可伪造的身份识别技术。 基于虹膜的生物识别技术同指纹识别一样，主要由4 个部分构成： 虹膜图像获取、图像预处理、虹膜特征提取、匹配与识别。 虹膜图像获取时，人眼不与c c d 、c m o s 等光学传感器直接接触， 采用的是一种非侵犯式的采集技术。所以，作为身份鉴别系统中的一 项重要生物特征，虹膜识别凭借虹膜丰富的纹理信息，稳定性、唯一性 和非侵犯性，越来越受到学术界和工业界的重视。虹膜图像的获取， 看似非常简单的过程，却是非常困难的一步。一方面由于人眼本身就 生物识别技术中的智能算法 是一个镜头，许多无关的杂光会在人眼中成像，从而被摄入到虹膜图 像中：另一方面，由于虹膜直径只有十几毫米，不同人种的虹膜颜色有 着很大的差别。白种人的虹膜颜色浅，纹理显著，而黄种人的虹膜则多 为深褐色，纹理非常不明显。在普通状态下，很难拍到可用的图像。天 津大学光电学院 1 0 在采集虹膜活体样本时采取了这样的措施，在遮 蔽杂光的前提下，采用稳定的近红外光源，调整光源的入射角度，以获 得高质量的8 位灰度图像。 虹膜图像的预处理，包括对虹膜图像定位，归一化和增强3 大步 骤。虹膜图像定位是去除采集到的眼睑、睫毛、眼白等，找出虹膜的 圆心和半径。为了消除平移、旋转、缩放等几何变换对虹膜识别的影 响，必须把原始虹膜图像调整到相同的尺寸和对应位置：又由于虹膜 的环形图案特征，决定了虹膜图像可采用极坐标变换形式进行归一 化。虹膜图像在采集过程中的不均匀光照会影响纹理分析的效果。一 般采取直方图均衡化的方法进行图像增强，减少光照不均匀分布的影 响。 虹膜的特征提取和匹配识别方法最早由英国剑桥大学的 j o h n d a u g m a n 博士1 9 9 3 年提出 1 1 ，以后许多虹膜识别技术都是以此 为基础展开的。d a u g m a n 博士用g a b o r 滤波器对虹膜图像进行编码， 基于任意一个虹膜特征码都与其他的不同虹膜生成的特征码统计不 相关这一特性，比对两个虹膜特征码的h a mm i n g 距离实现虹膜识别。 中科院自动化所运用d a u b e c h i e s - 4 型小波 1 2 ，提取虹膜图像特征， 并采用方差倒数加权欧氏距离分类器来进行识别。随着虹膜识别技术 9 硕士学位论文 研究和应用的进一步发展，虹膜识别系统的自动化程度越来越高，神 经网络算法、模糊识别算法也逐步应用到虹膜识别之中。 进入21 世纪后，随着外围硬件技术的不断进步，虹膜采集设备 技术越来越成熟，虹膜识别算法所要求的计算能力也越来越不是问 题。虹膜识别技术，由于其在采集、精确度等方面独特的优势，必然 会成为未来社会的主流生物认证技术。未来的安全控制、海关进出口 检验、电子商务等多种领域的应用，也必然的会以虹膜识别技术为重 点。这种趋势，现在已经在全球各地的各种应用中逐渐开始显现。在 核心算法方面，现在世界主要的的公司基本上都采取的是john daugman 的核心算法。国内在2000 年以前在虹膜识别方面 一直没有自己的核心知识产权，中科院自动化所于2o o0 年初，在 国家模式识别重点实验室16 年的研究基础上，结合海外归国学者谭 铁牛，王阳生的研究成果开发出了虹膜识别的核心算法。北京中科模 识科技有限公司，作为国内生物认证领域的最权威研究机构中科 院自动化所的产业转信息网络安全化公司，于2003 年推出了中国 第一套虹膜识别应用系统，成为世界上仅有的掌握虹膜核心算法的公 司之一。同时，相对于国际上其它公司的核心算法，中科院自动化所 的核心算法速度更快，占用的内存空间更小，整体性能更加优异，检 测的准确率更高，达到了世界领先的技术水平，这标志着中国虹膜识 别技术的研究及产业化工作，从此走在了世界的前列。 1 0 生物识别技术中的智能算法 2 1 模拟退火算法 2 智能算法 在自然科学、计算机科学、管理科学、分子生物学、图像处理、 电子工程、电力工程等领域，存在许多组合优化问题( c o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m ) ，其中的n p 完全问题( n o n d e t e r m i n i s t i c p o l y n o m i a lc o m p l e t ep r o b l e m ) ，其求解时间呈指数级增长，当规 模稍大时就会因时间限制而失去可行性( f e a s i b i l i t y ) 1 3 1 6 。 如著名的货郎担问题( t r a v e l i n gs a l e s m a np r o b l e m ，简记为t s p ) ， 即在n 个顶点的完全图中找一条最小h a m i l t o n 回路，当图为对称图 时，要从( n - i ) ! 2 个可能解中找出最优者，需进行( n - 1 ) ! 2 1 次比较，若用每秒运算一亿次的计算机，n = l o 时只需0 0 0 1 8 秒，n = 2 0 时就需1 9 年，n = 3 0 时则猛增为1 4 x l o ”年。显然，如此求其精确解 是不可行的。 为解决这类问题，人们提出了许多近似算法 1 4 1 6 。但这些 算法或因过于注意个别问题的特征而缺乏通用性，或因所得解强烈地 依赖初始解的选取而缺乏实用性。模拟退火算法( s i m u l a t e d a n n e a l i n ga l g o r i t h m ) 就是对其中的局部搜索算法( l o c a ls e a r c h a l g o r i t h m ) 改进而提出的 1 7 1 9 。 模拟退火的核心思想与热力学的原理颇为相似，而且尤其类似 于液体流动和结晶以及金属冷却和退火的方式。在高温下，一种液体 的大量分子彼此之间进行着相对自由移动。如果该流体慢慢地冷却下 1 1 硕士学位论文 来，热能可动性便会消失。大量原子常常能够自行排列成行，形成一 个纯净的晶体，该晶体在各个方向上都被完全有序地排列在几百万 倍于单个原子大小的距离之内。对于这个系统来说，晶体状态是能量 最低状态：而所有缓慢冷却的系统都可以自然达到这个最低能量状 态，这可以说是一个令人惊奇的事实。实际上，如果某种液体金属被 迅速冷却或被“猝熄”，那么它不会达到这一状态，而只能达到一种 具有较高能量的结晶状态或非结晶状态。因此，这一过程的本质在于 缓缓地致冷，以争取充足的时间，让大量原子在丧失可动性之前进 行重新分布。这就是所谓退火在技术上的定义，同时也是确保达到低 能量状态所必需的条件。往往处理问题的方式都是：从初始点开始， 立即沿下降方向前进，走得越远越好，似乎这样才能迅速求得问题的 解。但是，这种方法往往只能求得局部极小点，却求不到整体小点。 自然界本身的极小化算法则基于一种截然不同的方式。所谓的玻尔兹 曼( b o l t z m a n n ) 概率分布 ， p ( f ) 一e x p ( 一点冶7 ) ( 2 1 ) ( 2 - 1 ) 式表达了这样一种思想，即：一个处于热平衡状态且具 有温度，的系统，其能量按照概率，分布于所有不同的能量状态互 之中。即使在很低的温度下，系统也有可能( 虽然这种可能性很小) 处于一个较高的能量状态。因此。相应地，系统也能够获得摆脱局部 能量极小点的机会。并找到一个更好的、更接近于整体的极小点。式 ( 2 1 ) 中的参数k ( 称为玻尔兹曼常数) 是一个自然常数，它的作用 是将温度与能量联系起来。换句话说。在有些情况下系统的能量可上 生物识别技术中的智能算法 升，也可下降，但是温度越低，显著上升的可能性就越小。 1 9 5 3 年，m e t r o p o l i s 及其合作者们首次将这种原理渗透到数值 计算中。1 9 8 3 年k i r k a t r i c k 等成功地将退火思想引入组合优化领域 2 0 。算法的基本思想是从一给定解开始，从邻域中随机产生另一 个解，接受准则( m e t r o p o l i s ) 允许目标函数在有限范围内变坏，它由 一控制参数t 决定，其作用类似于在物理过程中的温度下，对于控制 参数t 的每一取值，算法持续进行“产生新解一判断一接受或舍弃”的 迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。经过大 量的解交换后，可以求得给定控制参数t 值时优化问题的相对最优 解。然后减小控制参数t 的值，重复执行上述迭代过程。准则由下式 定义：。 f li ff ( j ) - f ( o 尉b 舻 州等玛o l h a w i j 根+ ， 具体步骤如下： ( 1 ) 给定冷却进度表参数及迭代初始解以及，( ) 其中冷却 进度表参数包括：控制参数t 的初值t 。，衰减函数，终值( 停止准则) 及m a p k o b 链长度t ( 2 ) 参数乒f i 时，按照如下过程作t 次试探搜索： 1 ) 根据当前解吒的性质产生一随机向量 2 1 z k ( 对于连续变量) 或随机偏移量m 。( 对于离散变量) ，从而得到一当前解邻域的新的试 探点t ： t ： + 以：对于登釜奎曼( 2 - 2 )1 1 x ( m + m ) ，对于离散变量 硕士学位论文 其中j 为离散变量的取值序列，7 为当前解的离散位置。 2 ) 产生一个在( 0 ，1 ) 上均匀分布的随机数i l ，计算出在给定当前 迭代点扎和温度下与m e t r o p o l i s 接受准则相对应的转移概率 2 2 p ， 一 尸书鞘：则 如果1 1 尸，则接受新解，坼= t 前解不变。 ( 2 3 ) ，( 也) = ，( t ) ，否则当 3 ) 试探搜索小于以次，返回步骤1 ) ，否则进入步骤( 3 ) ( 3 ) 如果迭代终止条件满足，则算法结束，当前解作为近似全 局最优解：否则继续步骤( 4 ) ( 4 ) 根据给定的温度衰减函数产生新的温度控制参数及 m a p k o b 链长度t 。转入步骤( 2 ) 进入下一温度点的平衡点寻优。 从上述步骤可以看出模拟退火算法依据( 2 2 ) 式描述的 m e t r o p o l i s 准则接受新解，因此除了接受优化解外，还在一定限度 内接受恶化解，这正是模拟退火算法与局部搜索算法的本质区别所 在。开始时t 值大，可能接受较差的恶化解：随着t 的减小，则只 能接受较好的恶化解：最后在t 值趋于零时，就不再接受恶化解了。 从而使模拟退火算法能从局部最优的“陷阱”中跳出，最后得到全局 最优解。实验已证明s a 能以概率1 找到最优解，但是s a 需要多次计 算目标函数适应值才能找到最优解，其收敛速度较慢。 2 2 粒子群算法 1 4 生物识别技术中的智能算法 自然界中有许多现象令人惊奇，鸟群优美而协调的运动便是其中 之一。鸟群的排列看起来似乎是随机的，其实它们有着惊人的同步性， 这种同步性使得鸟群的整体运动非常流畅，有着舞蹈的美感。有几位 科学家对鸟群的运动进行了计算机仿真 2 3 。他们让每个个体按照特 定的规则运动，形成鸟群整体的复杂行为。所提模型成功的关键在于 对个体间距离的操作，也就是说群体行为的同步性是因为个体努力维 持自身与邻居之间的距离为最优，为此每个个体必须知道自身位置和 邻居的信息。生物社会学家e 。q w i l s o n 也曾说过 2 4 ，“至少从理 论上，在搜索食物的过程中群体中的个体成员可以得益于所有其他成 员的发现和先前的经历。当食物源不可预测地零星分布时，这种协作 带来的优势是决定性的，远大于对食物的竞争带来的劣势。”以上两 例说明，群体中个体之间信息的社会共享有助于进化。这正是开发微 粒群优化算法( p s o ，p a r t i c l es w a r mo p t i m i z a t i o n ) 的核心思想。 基于上述思想，k e n n e d y 与e b e r h a r t 在1 9 9 5 年提出微粒群优化算 法( p s o ) 的最初形式 2 4 。p s o 是一种基于群体智能的优化技巧，它 用无质量无体积的粒子作为个体，并为每个粒子规定简单的行为规 则，从而使整个微粒群表现出复杂的特性，可用来求解复杂的优化问 题。 假设搜索空间是d 维的，p s o 描述群体中的每个粒子i 有如下属 性：在搜索空间中的当前位置：= ( h ，t ：，) ：当前的速度： h = ( v 1 ，_ ：，) ：在搜索空间中个体的最好位置：只= ( b 。，a ：，) 。对于最小化问题，个体最好值p i 就是微粒i 硕士学位论文 在其搜索空间中，使其目标函数达到最小的那个位置。由p i 可得群 体中的所有粒子经历过的最好位置以= ( 岛，p 。：，如) ，以由 下式定义： 舭叫c t + l 笼揣端珊 倍的 。 l 蜀 ；萎l l + 埘，；露 i ” 弓l 毫；忍玩露溉宅i 嘲 ， j ，弓 l i = 函n j ，昂j i ， 墨f f d ，乏l l ( 2 - 5 ) 在每次循环中，每个粒子通过下式来更新自己的速度和位置： 岣聃+ 1 ) = ”( t ) + q ，( i ) ( 岛( t ) 一毛忙) ) + 岛勺( i p j ( i ) 一而仕) ) ( 2 6 ) 而仕+ 1 ) = 吻( i ) + o + 1 ) ( 2 7 ) 其中：w 是惯性权重，一般介于【o 21 2 之间，c l 和c 2 为加 速度常数，代表每个粒子推向只和舔位置的统计加速项权重，r l 和 r 2 为两个在 01 范围内变化的随机函数 标准p s o 的算法流程如下： s t e p l ：初始化粒子群中每个粒子的位置及其速度： s t e p 2 ：评价每个微粒的适应度； s t e p 3 ：对每个微粒，将其适应值与其经历过的最好位置p 。作比 较，如果较好，则将其作为当前的最好位置以； s t e p 4 ：对每个微粒，将其适应值与全局所经历的最好位置作 比较，如果较好，则将其作为当前的最好位置以； s t e p 5 ：根据方程( 6 ) ( 7 ) 变化微粒的速度和位置； s t e p 6 ：如未达到结束条件( 通常为足够好的适应值或达到一个 预设最大代数) ，则返回s t e p 2 。 1 6 生物识别技术中的智能算法 对于p s o ，每个粒子通过个体最优值和群体最优值来改变自己的 速度和位置，最后收敛于一点。p s o 的优点在于其收敛速度快，但其 缺点是不能正确收敛到全局最优值或局部最优值。 2 3 模拟退火算法和粒子群算法相结合 粒子群优化算法( p s o ) 是一种进化计算技术，最早是由k e n n e d y 与e b e r h a r t 于1 9 9 5 年提出的 2 4 。在p s o 中，每个优化问题的解都 是搜索空间的一只鸟，我们称为粒子。所有粒子都有一个由被优化函 数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距 离，然后粒子们就追随当前最优粒子在解空间中搜索。p s o 描述群体 中的每个粒子i 有如下属性：在搜索空间中的当前位置：x i ：当前的 速度：v i ：在搜索空间中个体的最好位置：p i 。对于最小化问题，个 体最好值p i 就是微粒i 在其搜索空间中，使其目标函数达到最小的 那个位置。由p i 可得群体中的所有粒子经历过的最好位置p g ，p g 由 下式定义： 舭= 黔，箍 _ ：裟嬲0 咚 l i 毫；露l ，墨 l 霉 1 0 _ ，弓t l i s m i n 秒i 焉 l 歹i 忍l j ，i 霉秘i ( 2 - 4 ) ( 2 - 5 ) 在每次循环中，每个粒子通过下式来更新自己的速度和位置： ( 七+ 1 ) = 狮0 ( ”+ q ，往x 岛( 七) 一x o ( k ) ) + c = r 2 ，( 七x p 0 ( 七) 一而o ) ) ( 2 - 6 ) 而( t + 1 ) = 而( 1 ) + 屹( i + 1 ) ( 2 7 ) 其中：r 是惯性权重，一般介于 o 21 2 之间，c 1 和c 2 为加 1 7 硕士学位论文 速度常数，代表每个粒子推向p i 和p g 位置的统计加速项权重，r l 和r 2 为两个在 0 1 范围内变化的随机函数。 模拟退火算法最早思想是由m e t r o p o l i s 在1 9 5 3 年提出，1 9 8 3 年k i r k a t r i c k 等成功地将退火思想引入组合优化领域。算法的基本 思想是从一给定解开始，从邻域中随机产生另一个解，接受准则 ( m e t r o p o l i s ) 允许目标函数在有限范围内变坏，它由一控制参数t 决 定，其作用类似于在物理过程中的温度下，对于控制参数t 的每一取 值，算法持续进行“产生新解一判断一接受或舍弃”的迭代过程，对应 着固体在某一恒定温度下趋于热平衡的过程。经过