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

1、大 連 理 工 大 學(xué) 學(xué) 報(bào)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文章編號(hào):100028608 (2005) 0120064204一個(gè)新的基于細(xì)節(jié)特征的指紋匹配方法浩1, 2 ,歐 宗 瑛3 1 ,洋1郭何( 1. 大連理工大學(xué) 機(jī)械工程學(xué)院 ca d &c g 研究所,遼寧 大連 116024;2. 大連海事大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 遼寧 大連 116026 )摘要: 自動(dòng)指紋識(shí)別系統(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) 的精度和效率主要依賴于指紋的匹配算法. 指紋匹配涉及的兩個(gè)關(guān)鍵問(wèn)題是指紋的對(duì)齊和匹配方式. 根 據(jù)同一個(gè)指紋的不同采樣, 其脊線形狀保持高度的相似性的特點(diǎn), 利用兩條脊線對(duì)應(yīng)點(diǎn)的距離構(gòu)造了一個(gè)判據(jù), 用來(lái)評(píng)價(jià)兩條脊線形狀的相似性, 以實(shí)現(xiàn)指紋的最優(yōu)對(duì)齊; 針對(duì)傳統(tǒng)指紋 匹配算法中偽細(xì)節(jié)點(diǎn)的混入和真實(shí)細(xì)節(jié)點(diǎn)的遺漏影響指紋匹配精度的問(wèn)題, 提出了一種基于 編輯距離原理的指紋細(xì)節(jié)特征匹配方法, 對(duì)指紋庫(kù) f ingdb 和 f inge r du t 進(jìn)行了測(cè)試, 等錯(cuò)誤率分別為 0. 62%

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

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

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

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

7、; (d x 0 , d y 0 ) 和 (d x 0 , d y 0 ) 是脊線 d 和d 的起始點(diǎn) 坐標(biāo); l 是脊線 d 和 d 的選取長(zhǎng)度內(nèi)包含的采樣點(diǎn)數(shù); s d 為描述脊線 d 和 d 的近似程度的系數(shù) (0 s d 1) , 當(dāng)系數(shù)為 1 時(shí), 表明兩條脊線形狀完 全相同.圖 1指紋的細(xì)節(jié)提取過(guò)程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)行指紋對(duì)齊指 紋對(duì)齊的實(shí)質(zhì)就是通過(guò)坐標(biāo)變換, 將待匹 配的指紋由輸入指紋坐標(biāo)系變換到模板指紋對(duì)應(yīng) 的坐標(biāo)系下, 進(jìn)而和模板指紋匹配 (見(jiàn)圖 2).

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

9、 d (r d 是輸入指紋的脊 線集合) , 根據(jù)下面的對(duì)齊判據(jù)判定兩條曲線形狀的近似程度:l2圖 2指紋脊線的對(duì)齊過(guò)程f ig12 t he a lignm en t o f r idge s o f f inge rp r in t s(2) 由下式算得由輸入指紋對(duì)應(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 是指紋的脊線起始點(diǎn)在模板指紋坐dd標(biāo)系中的坐標(biāo); x 和 y 是指紋的脊線起始點(diǎn)在輸入指紋坐標(biāo)系中的坐標(biāo); i 和 i 分別是指紋脊線上的各點(diǎn)相

10、對(duì)于脊線起始點(diǎn)與模板指紋坐標(biāo)系和 輸入指紋坐標(biāo)系 x 軸的仰角.d d(3) 為了增強(qiáng)算法的魯棒性, 根據(jù)步驟 (1)、(2) , 順序遍歷輸入指紋中的所有長(zhǎng)度大于設(shè)定門 檻值的脊線, 選擇最近似的幾個(gè)配對(duì)脊線, 得到相應(yīng)的幾組 x 、y 和 , 然后利用最小二乘法計(jì)算 最佳匹配的平移量以及旋轉(zhuǎn)角.(4) 下二式將指紋的細(xì)節(jié)點(diǎn)由輸入指紋坐標(biāo) 系轉(zhuǎn)換到模板指紋坐標(biāo)系, 最終對(duì)齊待匹配的輸 入指紋和模板指紋: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 上各點(diǎn)在各自對(duì)應(yīng)的坐標(biāo)系下的 x 軸坐標(biāo); d y 和d y 分別表示脊i式中: t r 是旋轉(zhuǎn)變換矩陣; t t 是平移變換矩陣; x di大 連 理 工 大 學(xué) 學(xué) 報(bào)第 45 卷66和 y d 是輸入指紋坐標(biāo)系下的坐標(biāo); d 是輸入指紋d (m , n ) , 下式中的 t r、t e

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

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

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

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

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

17、把兩組特征點(diǎn)集排成兩個(gè)特征點(diǎn)序列:是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, ) 表示特征點(diǎn)的極徑、極角和特征點(diǎn) 方向場(chǎng)仰角; m 和 n 為特征點(diǎn)序列 a 和 b 的長(zhǎng) 度.(2) 計(jì) 算 特 征 點(diǎn) 序 列 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 指紋識(shí)別 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 指紋識(shí)別 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é)論指紋匹配是整個(gè) a f is 實(shí)施的關(guān)鍵.本文針對(duì)指紋對(duì)齊和匹配方式兩個(gè)技術(shù)關(guān)鍵難點(diǎn), 提出的新的指紋對(duì)齊判據(jù)和改進(jìn)的編輯距離算法, 經(jīng) 驗(yàn)證對(duì)齊方式合理可靠, 在一定程度上有效地補(bǔ) 償了采樣變形而造成的細(xì)節(jié)變化, 可以快速有效 地實(shí)現(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