一个新的基于细节特征的指纹匹配方法.doc

大 连 理 工 大 学 学 报Journa l of D a l ian Un iver s ity of Techn o logy第4 5 卷第1 期2 0 0 5 年 1 月Vo l. 45, No. 1Jan. 2 0 0 5文章编号:100028608 (2005) 0120064204一个新的基于细节特征的指纹匹配方法浩1, 2 ,欧 宗 瑛3 1 ,洋1郭何( 1. 大连理工大学 机械工程学院 CA D &C G 研究所,辽宁 大连 116024;2. 大连海事大学 计算机科学与技术学院, 辽宁 大连 116026 )摘要: 自动指纹识别系统 (au tom a t ic f inge rp r in t iden t if ica t io n sy stem s, A F IS) 的精度和效率主要依赖于指纹的匹配算法. 指纹匹配涉及的两个关键问题是指纹的对齐和匹配方式. 根 据同一个指纹的不同采样, 其脊线形状保持高度的相似性的特点, 利用两条脊线对应点的距离构造了一个判据, 用来评价两条脊线形状的相似性, 以实现指纹的最优对齐; 针对传统指纹 匹配算法中伪细节点的混入和真实细节点的遗漏影响指纹匹配精度的问题, 提出了一种基于 编辑距离原理的指纹细节特征匹配方法, 对指纹库 F ingdb 和 F inge r DU T 进行了测试, 等错误率分别为 0. 62% 和 2. 75% , 证明该方法具有较高的可靠性和有效性.关键词: 指纹识别; 指纹匹配; 编辑距离中图分类号:文献标识码: AT P 3910引言果的评估标准选择. 常用的匹配评估方法是计算其相关度6 或向量的欧氏距离3 . 还有一些方法基于人类个体生理或行为特征的生物安全技术1 、2 , 为人们提供了可靠的身份确认解决方案.指纹识别是应用比较广泛的一种生物安全技术,它包括指纹提取、指纹分类和指纹匹配三部分内 容, 其中指纹的匹配技术是核心, 直接决定了识别的精度和效率.所有指纹匹配技术都必须解决的两个核心问 题是: (1) 指纹特征的表达; (2) 匹配策略.特 征表达就是如何构造特征向量, 对指纹进 行数学描述. 目前这方面的研究大致可分为两大类: (1) 基于宏观特征的表达; (2) 基于细节的表 达. 基于指纹宏观特征的表达方法是对指纹图像以“分割 2变换 2编码”的方式来描述指纹, 如文献采用了特殊的数学方法, 文献 7网络 (FN N ) 进行强映射匹配.采用模糊神经本 文针对同一指纹的不同次采样, 其脊线形状仍然保持高度相似性的特点, 提出一个新的对 齐判据, 并利用这一判据对齐两个待匹配指纹, 然后利用改进的编辑距离算法进行匹配.1指纹细节的提取指纹的细节提取包括以下 4 个步骤 (见图 1). (1) 图像的增强处理. 当图像质量不好、指纹脊线结构被破坏时, 会产生大量的伪细节, 同时原有的真实细节被忽略, 这时需要进行指纹的增强 处理. 采用 Gabo r 函数对指纹图像进行滤波, 可以有效地增强指纹的脊线结构.(2) 图像的二值化. 通过二值化, 分割出指纹 的山脊和山谷特征.(3) 脊线的细化. 通过细化处理, 将指纹的脊 线用八邻域单连通的骨架图表达.(4) 细节的提取. 根据指纹细节像素结构特 点, 在指纹骨架图中标记细节特征点. 每个细节特征点表示为 (x , y , ) , 其中 x 和 y 为细节点的坐 标位置, 为细节点处对应的指纹方向场仰角.3通 过 对 一 组 Gabo r 函 数 的 滤 波 结 果 进 行 编码, 构造特征向量来描述指纹; 基于细节的表达就是利用细节点的特征和细节点之间的位置关系来 描述指纹4 、5 , 通常指纹的细节特征包括指纹脊线的 终点和分叉点两种. 一般来说, 基于宏观特征 的表达通常对指纹的变形非常敏感, 但对噪声影响 因素不敏感. 当指纹图像的脊线结构清晰、伪 细节点少时, 基于细节表达的方法则更为可靠.匹配策略就是特征向量的匹配机制和匹配结收稿日期: 2003207220; 修回日期: 2004210216.作者简介: 郭 浩 ( 19722) , 男, 博士, 副教授; 欧宗瑛3 ( 19362) , 男, 教授, 博士生导师.线 d 和D 上各点在各自对应的坐标系下的 y 轴坐标; (d x 0 , d y 0 ) 和 (D x 0 , D y 0 ) 是脊线 d 和D 的起始点 坐标; L 是脊线 d 和 D 的选取长度内包含的采样点数; S d 为描述脊线 d 和 D 的近似程度的系数 (0 S d 1) , 当系数为 1 时, 表明两条脊线形状完 全相同.图 1指纹的细节提取过程F ig11 T h e acqu irem en t o f m inu t iae o f f inge rp r in t s利用脊线进行指纹对齐指 纹对齐的实质就是通过坐标变换, 将待匹 配的指纹由输入指纹坐标系变换到模板指纹对应 的坐标系下, 进而和模板指纹匹配 (见图 2). 对齐 的 关键是寻找最佳基准点. 理论上讲, 只要找到 两 个相应的点对, 就可以对齐两个指纹. 但是由 于同一个指纹的采样不可避免地存在变形, 输入 指 纹 不 可 能 正 好 和 模 板 指 纹 的 纹 理 相 重 合. 为 此, 本文提出了一种基于脊线形状的指纹对齐判 据, 其核心思想就是利用指纹脊线在不同坐标系 下投影的曲线外形仍保持高度相似性的特点, 通 过对齐判据寻求最佳的脊线匹配, 进而把脊线的 起始点作为坐标变换的基准点. 具体的对齐算法 如下.(1) 随机地选取模板指纹中的一条脊线 D R D (R D 是模板指纹的脊线集合) , 在待匹配的输入 指纹中选取一条脊线 d R d (R d 是输入指纹的脊 线集合) , 根据下面的对齐判据判定两条曲线形状的近似程度:L2图 2指纹脊线的对齐过程F ig12 T he a lignm en t o f r idge s o f f inge rp r in t s(2) 由下式算得由输入指纹对应的坐标系转 换到模板指纹坐标系的 x 、y 方向的平移量 x 和y , 以及旋转角 :Ddx - xxy Ddy - y(4)=L1 (Dd-i )iLi= 0DD式中: x 和 y 是指纹的脊线起始点在模板指纹坐dd标系中的坐标; x 和 y 是指纹的脊线起始点在输入指纹坐标系中的坐标; i 和 i 分别是指纹脊线上的各点相对于脊线起始点与模板指纹坐标系和 输入指纹坐标系 x 轴的仰角.D d(3) 为了增强算法的鲁棒性, 根据步骤 (1)、(2) , 顺序遍历输入指纹中的所有长度大于设定门 槛值的脊线, 选择最近似的几个配对脊线, 得到相应的几组 x 、y 和 , 然后利用最小二乘法计算 最佳匹配的平移量以及旋转角.(4) 下二式将指纹的细节点由输入指纹坐标 系转换到模板指纹坐标系, 最终对齐待匹配的输 入指纹和模板指纹:2 ld lDi ii= 1(1)S d =L ( ld ) 2 +( lD ) 2 iii= 1Ddx ix i式中y dd=T r T ty i1i22ld(d x -d x 0 ) + (d y - d y 0 ) ; 0 < i Li =1(2)x dco s -sin 0sin 0co s 0100010xy1ilD22d=(D x -D x 0 )+(D y - D y 0 ); 0 < i L(3)( )5y i1i01D =id + (6)其中 d x 和D x 分别表示脊线 d 和D 上各点在各自对应的坐标系下的 x 轴坐标; d y 和D y 分别表示脊i式中: T r 是旋转变换矩阵; T t 是平移变换矩阵; x di大 连 理 工 大 学 学 报第 45 卷66和 y d 是输入指纹坐标系下的坐标; d 是输入指纹d (M , N ) , 下式中的 T r、T e 和 T 为设定的极径、极角和方向场仰角的门槛值:ii坐标系下的细节点方向场仰角; x D 、y D 和 D 是指ii i0; m =m ; n =n; m =1 且 n =1 且 1 <1 且 1 <1m Mn N纹细节点转换为模板指纹坐标系下对应的值, 其中 i = 1, 2, N , 为输入指纹的细节点总数.3利用编辑距离算法进行指纹匹配指 纹匹配就是评估两个指纹的相似程度, 当d (m , n ) =d (m - 1, n ) + 1m in d (m , n - 1) + 1d (m - 1, n - 1) + (m , n )1 < m M 且 1 < n N;相似程度超过设定的门槛值时, 可以认为两个指纹采样于同一个指纹. 由于指纹采样都会存在一 些伪细节点或遗漏细节点, 细节点的加入和约去 次数也应当记录在最终的判定结果中. 采用编辑距离算法不仅记录了细节点的匹配数, 而且记录 了细节点加入和约去的次数.3. 1 编辑距离编辑距离8 算法最早应用于单词的拼写检 查, 目前在语音识别和基因序列的相似性匹配等领域有广泛的应用. 其基本思想是通过比较两个 字符串 A 和 B , 寻求由字符串 A 变为字符串 B 的最 小点变换次数. 变换的类型有 3 种: (1) 改变 1个字符; (2) 插入 1 个字符; (3) 删除 1 个字符. 每 一次点变换均为 3 种类型中的一种. 图 3 是编辑 距离算法的 1 个应用实例.(9)其中A BA B0; | rm -rn | < T r , | em - en | <(m , n ) =T e , | ABm - n | < T 1; 其他(10) (3) 计算待匹配指纹与模板指纹的匹配分数 当 S 超过设定的门槛值 S t 时, 可以认为这两个S.指纹源自同一个指纹:S = m ax (M , N ) - d (M , N )(11)4指纹匹配试验本 文 描 述 的 指 纹 匹 配 方 法 是 自 行 开 发 的A F IS 的一部分, 用于测试的两个指纹库, 一个是意大利伯罗尼亚大学的 F in gdb 指纹库, 包含 168个实时扫描指纹 (21 种指纹, 每种采样 8 次) ; 另一 个 是 大 连 理 工 大 学 CA D &C G 研 究 所 采 集 的F inge r DU T 指纹库, 包含 928 个印记指纹 (116种 指 纹, 每 种 采 样 8 次 ). 试 验 方 案 是: 对 于F ingdb , 取每种指纹的前 4 次采样 (共计 84 个) 作 为 输入指纹; 剩下的 84 个指纹作为模板, 共进行7 056 (84 × 84) 次匹配; 对于 F inge r DU T , 方案图 3编辑距离算法的一个应用示例F ig13 A n app lica t io n o f ed it d istance相同, 输入和模板均为 464 (116 × 4) 个指纹, 共进行 215 296 (464 × 464) 次匹配. 表 1 是不同匹 配门槛分数 S t 下的错误接受率 R fa 和错误拒绝率R f r 的对应结果. 图 4 和 5 是两个指纹库匹配结果的 RO C 曲线, R ga 表示正确接受率. 通过分析可 以得到, F in gdb 和 F inge r DU T 的等错误率分别3. 2基于改进的编辑距离算法的指纹匹配基于编辑距离的指纹匹配算法的步骤如下.(1) 将待匹配的输入指纹的特征点集和指纹 库中模板指纹的特征点集, 统一在模板坐标下以极坐标表示, 然后将极角按照由小到大的顺序把两组特征点集排成两个特征点序列:是0. 62% 和 2. 75%.A = ( rA , eA , A ) , ( rA , eA , A ) ,1 1 1 2 2 2 , ( rA , eA , A ) 表 1T ab 11不同匹配门槛分数 S t 下的匹配结果R e su lt s unde r d iffe ren t m a tch ing th re sho ld s S tMMM(7) ( rB , eB , B ) , ( rB , eB , B ) , ( rB , eB , B ) B =F ingdb1 1 1 2 2 2F inge r DU TNNNS t(8) 式 中: ( r, e, ) 表示特征点的极径、极角和特征点 方向场仰角; M 和 N 为特征点序列 A 和 B 的长 度.(2) 计 算 特 征 点 序 列 A 和 B 的 编 辑 距 离 R fa % R f r % R fa % R f r % 9700. 067. 144. 410. 020. 079. 237. 01 5 0. 21 1. 73 0. 44 3. 97 参考文献:1 JA IN A K , BOL L E R M , PA N KA N T I S.B iom e tr ic s: Per sona l Iden t if ica t ion in a Ne tworkedSoc ie ty M . L o ndo n: K luw e r A cadem ic P ub lish e r s,1999.图 4F ingdb 指纹识别 RO C 曲线RO C cu rve s: f inge rp r in t s m a tch ing fo rF ingdb2 M IL L ER B. V ita l sign s o f iden t ity J .Spec trum , 1994, 31 (2) : 22233.IEEEF ig143 P RA BHA KA R S. F inge rp r in t c la ssif ica t io n andm a tch ing u sing a f ilte rbank D . M ich igan: M ich igan S ta te U n ive r sity, 2001.4 R A T HA N , KA RU K , CH EN S, e t a l. A rea l2t im em a tch ing sy stem fo r la rge f inge rp r in t da taba se s J .IEEE Tran s on Pa ttern Ana l an d M ach in e In te ll,1996, 18 (8) : 7992813.5 H E Yu 2liang, T IA N J ie, L U O X i2p ing, e t a l. Im age enhancem en t and m inu t iae m a tch ing in f inge rp r in t图 5F ig15F inge r DU T 指纹识别 RO C 曲线RO C cu rve s:F inge r DU Tf inge rp r in t sm a tch ingfo rve r if ica t io nJ .Pa ttern Recogn it ion L e tter sVo lum e, 2003, 24 (9) : 135921370.6 C O E T ZE E L , BO T HA E C. F inge rp r in t reco gn it io n in low qua lity im age s J . Pa ttern Recogn it ion ,1993, 26 (11) : 114121460.7 Q U E K C , TA N K B , SA GA R V K. P seudo 2o u te r p ro duct ba sed fuzzy neu ra l ne tw o rk f inge rp r in t ve r if ica t io n sy stem J . Neura l Ne tworks, 2001,14 (3) : 3052323.8 S EL L ER S P H. A n a lgo r ithm fo r th e d istance5结论指纹匹配是整个 A F IS 实施的关键.本文针对指纹对齐和匹配方式两个技术关键难点, 提出的新的指纹对齐判据和改进的编辑距离算法, 经 验证对齐方式合理可靠, 在一定程度上有效地补 偿了采样变形而造成的细节变化, 可以快速有效 地实现指纹匹配, 从而提高了 A F IS 的性能.be tw eentw of in itesequence sJ .J ofCom b ina tor ia l Theory, 1974, 16: 2532258.A n ew f in gerpr in t m a tch in g m e thod ba sed on m in ut ia e of f in gerpr in tsHa o 1, 2 ,O UZo ng 2y ing 3 1 ,HEYa ng 1GUO( 1. CAD & C G L a b. , S c ho o l o f M e c h. Eng. , D a lia n U n iv. o f Te c hno l. , D a lia n 116024, C h ina ;2. S c ho o l o f C om p u t. S c i. a nd Te c hno l. , D a lia n M a rit im e U n iv. , D a lia n 116026, C h ina )A bstrac t:T h e accu racy and eff ic iency o f au tom a t ic f inge rp r in t iden t if ica t io n sy stem s (A F IS) m a in lydep end o n th e f inge rp r in t m a tch ing p ro ce ssing. T h e a lignm en t o f f in ge rp r in t s and th e m a tch ingm e tho d a re th e tw o k ey p ro b lem s to m a tch ing w o rk ing p e rfo rm an ce. B ecau se th e sh ap e s o f r idge s f rom th e sam e f inge rp r in t k eep sim ila r ity in d iffe ren t acqu isit io n im age s, a no ve l c r ite r io n fo r eva lua t in g th e sim ila r ity o f tw o r idge sh ap e s is p ropo sed, w h ich is co n st ru c ted ba sed o n th e d istance s o f co r re spo nd in g po in t p a ir s o n r idge s. A n op t im a l a lignm en t o f tw o f inge rp r in t s can be im p lem en ted by a lign ing th e m o st sim ila r r idge s o n tw o f in ge rp r in t s. In th e co nven t io na l f inge rp r in t m a tch ing app ro ach , th e de ta iled po sit io n ch an ge becau se o f r idge d isto r t in g and th e fa ilu re m a tch ing b ecau se o f th e ex t ra p seu do m inu t iae in te rfu sin g and o r th e rea l m inu t iae m issin g, can affec t th e p rec isio n o f m a tch ing. So a new m e tho d ba sed o n ed it ing d istance fo r ca lcu la t in g th e sim ila r ity sco re be tw een tw of inge rp r in t s is p re sen ted. E xp e r im en t s h ave b een do ne o n tw o f in ge rp r in t da taba se s, F ingdb and F ingDU T , and th e equa l e r ro r ra te s (E ER ) a re 0. 62% an d 2. 75% re sp ec t ive ly. T h e re su lt s show th a tth e new app ro ach is ro b u st and effec t ive.Key word s: f inge rp r in t iden t if ica t io n; f inge rp r in t m a tch ing; ed it d istance