一個新的基于細(xì)節(jié)特征的指紋匹配方法

1、大 連 理 工 大 學(xué) 學(xué) 報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一個新的基于細(xì)節(jié)特征的指紋匹配方法浩1, 2 ,歐 宗 瑛3 1 ,洋1郭何( 1. 大連理工大學(xué) 機(jī)械工程學(xué)院 ca d &c g 研究所,遼寧 大連 116024;2. 大連海事大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院, 遼寧 大連 116026 )摘要: 自動指紋識別系統(tǒng) (au tom a t ic f in

2、ge rp r in t iden t if ica t io n sy stem s, a f is) 的精度和效率主要依賴于指紋的匹配算法. 指紋匹配涉及的兩個關(guān)鍵問題是指紋的對齊和匹配方式. 根 據(jù)同一個指紋的不同采樣, 其脊線形狀保持高度的相似性的特點, 利用兩條脊線對應(yīng)點的距離構(gòu)造了一個判據(jù), 用來評價兩條脊線形狀的相似性, 以實現(xiàn)指紋的最優(yōu)對齊; 針對傳統(tǒng)指紋 匹配算法中偽細(xì)節(jié)點的混入和真實細(xì)節(jié)點的遺漏影響指紋匹配精度的問題, 提出了一種基于 編輯距離原理的指紋細(xì)節(jié)特征匹配方法, 對指紋庫 f ingdb 和 f inge r du t 進(jìn)行了測試, 等錯誤率分別為 0. 62%

3、和 2. 75% , 證明該方法具有較高的可靠性和有效性.關(guān)鍵詞: 指紋識別; 指紋匹配; 編輯距離中圖分類號:文獻(xiàn)標(biāo)識碼: at p 3910引言果的評估標(biāo)準(zhǔn)選擇. 常用的匹配評估方法是計算其相關(guān)度6 或向量的歐氏距離3 . 還有一些方法基于人類個體生理或行為特征的生物安全技術(shù)1 、2 , 為人們提供了可靠的身份確認(rèn)解決方案.指紋識別是應(yīng)用比較廣泛的一種生物安全技術(shù),它包括指紋提取、指紋分類和指紋匹配三部分內(nèi) 容, 其中指紋的匹配技術(shù)是核心, 直接決定了識別的精度和效率.所有指紋匹配技術(shù)都必須解決的兩個核心問 題是: (1) 指紋特征的表達(dá); (2) 匹配策略.特 征表達(dá)就是如何構(gòu)造特征向量

4、, 對指紋進(jìn) 行數(shù)學(xué)描述. 目前這方面的研究大致可分為兩大類: (1) 基于宏觀特征的表達(dá); (2) 基于細(xì)節(jié)的表 達(dá). 基于指紋宏觀特征的表達(dá)方法是對指紋圖像以“分割 2變換 2編碼”的方式來描述指紋, 如文獻(xiàn)采用了特殊的數(shù)學(xué)方法, 文獻(xiàn) 7網(wǎng)絡(luò) (fn n ) 進(jìn)行強(qiáng)映射匹配.采用模糊神經(jīng)本 文針對同一指紋的不同次采樣, 其脊線形狀仍然保持高度相似性的特點, 提出一個新的對 齊判據(jù), 并利用這一判據(jù)對齊兩個待匹配指紋, 然后利用改進(jìn)的編輯距離算法進(jìn)行匹配.1指紋細(xì)節(jié)的提取指紋的細(xì)節(jié)提取包括以下 4 個步驟 (見圖 1). (1) 圖像的增強(qiáng)處理. 當(dāng)圖像質(zhì)量不好、指紋脊線結(jié)構(gòu)被破壞時, 會

5、產(chǎn)生大量的偽細(xì)節(jié), 同時原有的真實細(xì)節(jié)被忽略, 這時需要進(jìn)行指紋的增強(qiáng) 處理. 采用 gabo r 函數(shù)對指紋圖像進(jìn)行濾波, 可以有效地增強(qiáng)指紋的脊線結(jié)構(gòu).(2) 圖像的二值化. 通過二值化, 分割出指紋 的山脊和山谷特征.(3) 脊線的細(xì)化. 通過細(xì)化處理, 將指紋的脊 線用八鄰域單連通的骨架圖表達(dá).(4) 細(xì)節(jié)的提取. 根據(jù)指紋細(xì)節(jié)像素結(jié)構(gòu)特 點, 在指紋骨架圖中標(biāo)記細(xì)節(jié)特征點. 每個細(xì)節(jié)特征點表示為 (x , y , ) , 其中 x 和 y 為細(xì)節(jié)點的坐 標(biāo)位置, 為細(xì)節(jié)點處對應(yīng)的指紋方向場仰角.3通 過 對 一 組 gabo r 函 數(shù) 的 濾 波 結(jié) 果 進(jìn) 行 編碼, 構(gòu)造特征向

6、量來描述指紋; 基于細(xì)節(jié)的表達(dá)就是利用細(xì)節(jié)點的特征和細(xì)節(jié)點之間的位置關(guān)系來 描述指紋4 、5 , 通常指紋的細(xì)節(jié)特征包括指紋脊線的 終點和分叉點兩種. 一般來說, 基于宏觀特征 的表達(dá)通常對指紋的變形非常敏感, 但對噪聲影響 因素不敏感. 當(dāng)指紋圖像的脊線結(jié)構(gòu)清晰、偽 細(xì)節(jié)點少時, 基于細(xì)節(jié)表達(dá)的方法則更為可靠.匹配策略就是特征向量的匹配機(jī)制和匹配結(jié)收稿日期: 2003207220; 修回日期: 2004210216.作者簡介: 郭 浩 ( 19722) , 男, 博士, 副教授; 歐宗瑛3 ( 19362) , 男, 教授, 博士生導(dǎo)師.線 d 和d 上各點在各自對應(yīng)的坐標(biāo)系下的 y 軸坐標(biāo)

7、; (d x 0 , d y 0 ) 和 (d x 0 , d y 0 ) 是脊線 d 和d 的起始點 坐標(biāo); l 是脊線 d 和 d 的選取長度內(nèi)包含的采樣點數(shù); s d 為描述脊線 d 和 d 的近似程度的系數(shù) (0 s d 1) , 當(dāng)系數(shù)為 1 時, 表明兩條脊線形狀完 全相同.圖 1指紋的細(xì)節(jié)提取過程f ig11 t h e acqu irem en t o f m inu t iae o f f inge rp r in t s利用脊線進(jìn)行指紋對齊指 紋對齊的實質(zhì)就是通過坐標(biāo)變換, 將待匹 配的指紋由輸入指紋坐標(biāo)系變換到模板指紋對應(yīng) 的坐標(biāo)系下, 進(jìn)而和模板指紋匹配 (見圖 2).

8、 對齊 的 關(guān)鍵是尋找最佳基準(zhǔn)點. 理論上講, 只要找到 兩 個相應(yīng)的點對, 就可以對齊兩個指紋. 但是由 于同一個指紋的采樣不可避免地存在變形, 輸入 指 紋 不 可 能 正 好 和 模 板 指 紋 的 紋 理 相 重 合. 為 此, 本文提出了一種基于脊線形狀的指紋對齊判 據(jù), 其核心思想就是利用指紋脊線在不同坐標(biāo)系 下投影的曲線外形仍保持高度相似性的特點, 通 過對齊判據(jù)尋求最佳的脊線匹配, 進(jìn)而把脊線的 起始點作為坐標(biāo)變換的基準(zhǔn)點. 具體的對齊算法 如下.(1) 隨機(jī)地選取模板指紋中的一條脊線 d r d (r d 是模板指紋的脊線集合) , 在待匹配的輸入 指紋中選取一條脊線 d r

9、 d (r d 是輸入指紋的脊 線集合) , 根據(jù)下面的對齊判據(jù)判定兩條曲線形狀的近似程度: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) 由下式算得由輸入指紋對應(yīng)的坐標(biāo)系轉(zhuǎn) 換到模板指紋坐標(biāo)系的 x 、y 方向的平移量 x 和y , 以及旋轉(zhuǎn)角 :ddx - xxy ddy - y(4)=l1 (dd-i )ili= 0dd式中: x 和 y 是指紋的脊線起始點在模板指紋坐dd標(biāo)系中的坐標(biāo); x 和 y 是指紋的脊線起始點在輸入指紋坐標(biāo)系中的坐標(biāo); i 和 i 分別是指紋脊線上的各點相

10、對于脊線起始點與模板指紋坐標(biāo)系和 輸入指紋坐標(biāo)系 x 軸的仰角.d d(3) 為了增強(qiáng)算法的魯棒性, 根據(jù)步驟 (1)、(2) , 順序遍歷輸入指紋中的所有長度大于設(shè)定門 檻值的脊線, 選擇最近似的幾個配對脊線, 得到相應(yīng)的幾組 x 、y 和 , 然后利用最小二乘法計算 最佳匹配的平移量以及旋轉(zhuǎn)角.(4) 下二式將指紋的細(xì)節(jié)點由輸入指紋坐標(biāo) 系轉(zhuǎn)換到模板指紋坐標(biāo)系, 最終對齊待匹配的輸 入指紋和模板指紋: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 ) +

11、(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 上各點在各自對應(yīng)的坐標(biāo)系下的 x 軸坐標(biāo); d y 和d y 分別表示脊i式中: t r 是旋轉(zhuǎn)變換矩陣; t t 是平移變換矩陣; x di大 連 理 工 大 學(xué) 學(xué) 報第 45 卷66和 y d 是輸入指紋坐標(biāo)系下的坐標(biāo); d 是輸入指紋d (m , n ) , 下式中的 t r、t e

12、 和 t 為設(shè)定的極徑、極角和方向場仰角的門檻值:ii坐標(biāo)系下的細(xì)節(jié)點方向場仰角; x d 、y d 和 d 是指ii i0; m =m ; n =n; m =1 且 n =1 且 1 1 且 1 1m mn n紋細(xì)節(jié)點轉(zhuǎn)換為模板指紋坐標(biāo)系下對應(yīng)的值, 其中 i = 1, 2, n , 為輸入指紋的細(xì)節(jié)點總數(shù).3利用編輯距離算法進(jìn)行指紋匹配指 紋匹配就是評估兩個指紋的相似程度, 當(dāng)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;相似程度超過設(shè)定的門檻值時, 可

13、以認(rèn)為兩個指紋采樣于同一個指紋. 由于指紋采樣都會存在一 些偽細(xì)節(jié)點或遺漏細(xì)節(jié)點, 細(xì)節(jié)點的加入和約去 次數(shù)也應(yīng)當(dāng)記錄在最終的判定結(jié)果中. 采用編輯距離算法不僅記錄了細(xì)節(jié)點的匹配數(shù), 而且記錄 了細(xì)節(jié)點加入和約去的次數(shù).3. 1 編輯距離編輯距離8 算法最早應(yīng)用于單詞的拼寫檢 查, 目前在語音識別和基因序列的相似性匹配等領(lǐng)域有廣泛的應(yīng)用. 其基本思想是通過比較兩個 字符串 a 和 b , 尋求由字符串 a 變?yōu)樽址?b 的最 小點變換次數(shù). 變換的類型有 3 種: (1) 改變 1個字符; (2) 插入 1 個字符; (3) 刪除 1 個字符. 每 一次點變換均為 3 種類型中的一種. 圖

14、3 是編輯 距離算法的 1 個應(yīng)用實例.(9)其中a ba b0; | rm -rn | t r , | em - en | (m , n ) =t e , | abm - n | t 1; 其他(10) (3) 計算待匹配指紋與模板指紋的匹配分?jǐn)?shù) 當(dāng) s 超過設(shè)定的門檻值 s t 時, 可以認(rèn)為這兩個s.指紋源自同一個指紋:s = m ax (m , n ) - d (m , n )(11)4指紋匹配試驗本 文 描 述 的 指 紋 匹 配 方 法 是 自 行 開 發(fā) 的a f is 的一部分, 用于測試的兩個指紋庫, 一個是意大利伯羅尼亞大學(xué)的 f in gdb 指紋庫, 包含 168個實時

15、掃描指紋 (21 種指紋, 每種采樣 8 次) ; 另一 個 是 大 連 理 工 大 學(xué) ca d &c g 研 究 所 采 集 的f inge r du t 指紋庫, 包含 928 個印記指紋 (116種 指 紋, 每 種 采 樣 8 次 ). 試 驗 方 案 是: 對 于f ingdb , 取每種指紋的前 4 次采樣 (共計 84 個) 作 為 輸入指紋; 剩下的 84 個指紋作為模板, 共進(jìn)行7 056 (84 84) 次匹配; 對于 f inge r du t , 方案圖 3編輯距離算法的一個應(yīng)用示例f ig13 a n app lica t io n o f ed it d ista

16、nce相同, 輸入和模板均為 464 (116 4) 個指紋, 共進(jìn)行 215 296 (464 464) 次匹配. 表 1 是不同匹 配門檻分?jǐn)?shù) s t 下的錯誤接受率 r fa 和錯誤拒絕率r f r 的對應(yīng)結(jié)果. 圖 4 和 5 是兩個指紋庫匹配結(jié)果的 ro c 曲線, r ga 表示正確接受率. 通過分析可 以得到, f in gdb 和 f inge r du t 的等錯誤率分別3. 2基于改進(jìn)的編輯距離算法的指紋匹配基于編輯距離的指紋匹配算法的步驟如下.(1) 將待匹配的輸入指紋的特征點集和指紋 庫中模板指紋的特征點集, 統(tǒng)一在模板坐標(biāo)下以極坐標(biāo)表示, 然后將極角按照由小到大的順序

17、把兩組特征點集排成兩個特征點序列:是0. 62% 和 2. 75%.a = ( ra , ea , a ) , ( ra , ea , a ) ,1 1 1 2 2 2 , ( ra , ea , a ) 表 1t ab 11不同匹配門檻分?jǐn)?shù) s t 下的匹配結(jié)果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) 式 中

18、: ( 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 參考文獻(xiàn):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 tworked

19、soc 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

20、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 2li

21、ang, 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

22、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 tw

23、orks, 2001,14 (3) : 3052323.8 s el l er s p h. a n a lgo r ithm fo r th e d istance5結(jié)論指紋匹配是整個 a f is 實施的關(guān)鍵.本文針對指紋對齊和匹配方式兩個技術(shù)關(guān)鍵難點, 提出的新的指紋對齊判據(jù)和改進(jìn)的編輯距離算法, 經(jīng) 驗證對齊方式合理可靠, 在一定程度上有效地補(bǔ) 償了采樣變形而造成的細(xì)節(jié)變化, 可以快速有效 地實現(xiàn)指紋匹配, 從而提高了 a f is 的性能.be tw eentw of in itesequence sj .j ofcom b ina tor ia l theory, 1974, 16

24、: 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

25、 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

26、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 in