改进的指纹细节特征提取算法

第7卷(A 版) 　第12期2002年12月

中国图象图形学报

Jou

rnal of I m age and Grap h ics

V o l . 7(A ) ,N o. 12

D ec . 2002

改进的指纹细节特征提取算法

尹义龙　宁新宝　张晓梅

(南京大学银佳生物识别技术研究所, 南京大学电子科学与工程系, 南京　210093)

摘　要　指纹细节特征(m inutiae ) 提取是指纹自动识别的核心技术之一. 常规的指纹细节特征提取算法需要先采用纹线跟踪的方法对细化后的指纹图象进行纹线修复, 然后再实现细节特征提取. , 而且比较耗时. 针对这一问题, 提出了一种改进的指纹细节特征提取算法. 始细节特征点集; , 结合局部纹线方向信息, 针对不同的噪声, 采用针对性的算法, , 最终保留下来的特征点集即视为真正的特征点集. 为验证该算法的性能, . 实验结果表明, 改进算法有效地减少了计算时间, . 关键词　中图法分类号::A 　　文章编号:100628961(2002) 1221302205

An I m proved A lgor ithm for M i nuti ae Extraction i n F i ngerpr i n t I mages

Y I N Y i 2long , N I N G X in 2bao , ZHAN G X iao 2m ei

(N ju 2W inca Institu te of B io m etrics , D ep a rt m en t of E lectron ic S cience &E ng ineering , N anj ing U n iversity , N anj ing 210093)

Abstract 　M inutiae extracti on is one of the co re techniques of autom atic fingerp rint identificati on . Routine algo 2rithm fo r m inutiae extracti on needs to resto re ridges firstly by the w ay of ridge tracing on th inned fingerp rint i m 2ages and then m inutiae extracti on is realized . It is trivial and ti m e 2consum ing to resto re ridge structure . A i m ing at the p roblem , an i m p roved algo rithm fo r m inutiae extracti on is brough t out . F irst , the set of o riginal m inutiae is di 2. Second , vari ous no ises in fingerp rint i rectly extracted from th inned fingerp rint i m ages m ages and their p roperties are analyzed and distributing regulati on of p seudo m inutiae is generalized . L ast , com bining w ith the info r m ati on of local ridge directi on , special algo rithm s are designed w ith respect to vari ous no ises to delete p seudo m inutiae from o riginal m inutiae set . T he rem ainders of o riginal m inutiae are view ed as intrinsic m inutiae . To verify the perfo r 2m ance of the i m p roved algo rithm brough t out in th is paper , contrastive experi m ent w as conducted w ith routine al 2go rithm . Experi m ental results indicate that computati onal ti m e is reduced effectively w ith the i m p roved algo rithm and the accuracy of m inutiae extracti on can fill the dem and of app licati on .

Keywords 　F ingerp rints , M inutiae , M inutiae extracti on , R idge resto rati on , I m age th inning

0　引　言

指纹细节特征点(M inu tiae ) 主要指的是纹线端点(R idge Ending ) 和纹线分叉点(B ifu rcati on ) [1](定义如图1所示) . 纹线端点指的是纹线突然结束的位

图1　指纹细节特征点定义

基金项目:长春市科技发展计划重点项目(长科合字第99011号) ; 南京大学应用开发基金(2001203)

安徽省教育厅自然科学研究项目(2002KJ 234)

收稿日期:2001207230; 改回日期:2002205229

第12期尹义龙等:改进的指纹细节特征提取算法

1303

置, 纹线分叉点指的是纹线一分为二的位置. 大量的统计结果表明, 使用这两类特征点就足以描述指纹的唯一性. 诸如基本纹型、纹线频率等宏观特征, 主要用作指纹的分类和检索, 指纹唯一性最终要靠细节特征来判别. 细节特征提取是整个自动指纹识别系统中一个非常重要的环节, 它既是对图象预处理效果的检验, 又是后继指纹比对算法实现的基础.

迄今为止, 人们已经对指纹细节特征提取算法进行了很多的研究工作[2～4]. 文献[5]、[6]还对直接在灰度指纹图象上提取细节特征点的问题进行了深入的研究, 但总体来讲, 这类算法对低质量指纹图象的适应性不是太理想. 常规的细节特征提取算法大多是在经过细化和纹线修复的指纹图象上进行的. 经过完全细化、细化图象, 素宽, . 情. 而事实上, 象预处理技术的局限, 对图象进行比较理想的细化是有一定技术难度的[7, 8]. 对纹线进行有效的修复, 如连接纹线间断、分离纹线叉连和去除毛刺等操作, 则需要对纹线进行跟踪和遍历, 步骤非常繁琐, 时间消耗也比较大[9]. 所以, 在实际应用中, 常规细节特征提取算法的效果并不总能令人满意. 基于这样一种情况, 提出了一种改进的指纹细节特征提取算法, 即在不对纹线做任何修复处理的情况下, 在细化指纹图象上直接提取原始细节特征点集, 得到初步的特征提取结果; 然后分析图象中存在的各类噪声及其特点, 结合指纹细节特征点固有的分布规律和局部纹线方向信息, 针对不同的噪声采用针对性的算法, 将各类噪声引起的伪特征点分别予以删除, 而将最终保留的特征点集作为真正特征点的集合.

P 1P 8P 7

P 2P P 6

P 3P 4P 5

图2　象素的8邻点定义

其中, P 9=P 1.

常规的细节特征提取算法是先将图象细化, 然后进行纹线修复, 最后采用式(1) 或者式(2) 提取细节特征点. P , 如果T Sum (P ) 的值等于1, ; 如果T Sum (P ) 的值等; 如果T Sub (P ) 的值等于; 如果T Sub (P ) 的值等于6, 则.

其中, 式(1) 必须在指纹纹线被严格地细化成单像素宽的条件下才可以正确工作, 而式(2) 即使对于未完全细化的指纹图象也可以正确地提取细节特征信息. 虽然对指纹纹线进行比较理想的修复后, 常规算法也可以很好地完成细节特征的提取工作, 但当指纹图象质量不好、噪声干扰比较严重时, 对指纹纹线进行很好的修复是一件很困难的事情, 常规算法的特征效果也会受到严重的影响.

2　改进算法

在对细化指纹图象进行纹线修复前, 其中存在着大量的毛刺、纹线间断和纹线叉连等噪声. 采用式(1) 或式(2) 直接在这种图象上提取到的细节特征中, 往往包含大量的伪特征信息. 但如果深入分析指纹图象中各类噪声的特点, 总结出伪特征点的形成原因和分布规律, 就可以设计相应的算法, 去伪存真, 筛选出真正的特征点集.

2. 1　细化指纹图象中存在的噪声分类及其特点分析

未经修复处理的细化指纹图象中, 主要存在以下几类噪声(如图3所示) :

(1

) 纹线间断　在指头比较干时, 采集到的指纹图象往往存在大量的纹线间断. 在纹线有间断的地方, 细节特征提取算法就会检测到两个纹线端点, 属于伪特征点. 这种伪特征点的特点是两点之间距离很小, 沿局部纹线方向两点之间的区域没有纹线存在.

(2) 纹线叉连　当指头比较湿或者比较脏时, 采集到的指纹图象往往会出现较多纹线叉连的现象,

1　常规细节特征提取算法

如图2所示, 设P 点为一目标像素点(待处理的图象点) , 则其周围相邻的8点P 1, P 2, …, P 8被称为P 点的8邻点. 指纹细节特征点提取算法是建立在对8邻点的统计分析基础之上的. 定义

8

T Sum (P ) =

8

∑P

i =1

i

(1)

P i

T Sub (P ) =

∑

i =1

P i +1-(2)

1304

中国图象图形学报第7卷(A 版)

结构, 都不是指纹所固有的结构, 应该可以直接予以删除.

2. 3　算法描述

定义　D (i , j ) 为两特征点i , j 之间的距离, 单位为像素; A (i , j ) 为两特征点i , j 连线与横坐标轴方向的夹角, 单位为弧度; 如有纹线连接特征点i , j , 则C (i , j ) =1; 否则, C (i , j ) =0; Η(i , j ) 为两特征点

i , j 所在的局部邻域的纹线方向, 单位为弧度; ∃Η为

. A (i , j ) 与Η(i , j ) 之差的绝对值

改进算法描述如下:

(1图3　细化指纹图象中存在的各种噪声

, 直接使用, 得到原始的细节特征点. (2) 顺序减差的特点, 即使对未完全细化的图象仍可以正确地提取到细节特征点. 当然, 由于大量噪声的存在, 原始细节特征点集中, 可能会包含大量的伪特征点.

(2) 短线与纹线间断形成的伪特征点的删除原始细节特征点集中, 对任意两个纹线端点i ,

≈0, 则该两点为伪特征j , 如果D (i , j )

点, 予以删除.

(3) 小孔状结构形成的伪特征点的删除原始细节特征点集中, 对任意两个纹线分叉点i , j , 如果D (i , j )

删除.

(4) 小毛刺形成的伪特征点的删除原始细节特征点集中, 对任一纹线端点和任一纹线分叉点j , 如果D (i , j )

(5) 较长毛刺形成的伪特征点的删除

原始细节特征点集中, 对任一纹线端点和任一纹线分叉点j , 如果D (i , j )

即本不应该相连的纹线粘连在一起. , 特征点. 点, , 而方向.

(3) 短线　当指纹比较脏时, 采集到的指纹图象容易出现较多的短线, 短线的出现主要是由随机噪声引起的. 在这种位置, 会提取到两个纹线端点, 属于伪特征点. 这种伪特征点的特点是两点之间距离很小, 两点之间由一条纹线相连.

(4) 很小的孔状结构　很小的孔状结构的出现主要是由于随机噪声的影响而形成的. 这种位置可以检测到两个纹线分叉点, 属于伪特征点. 这种伪特征点的特点是两点之间的距离非常地小, 且两点之间连线与其局部邻域纹线的方向近似平行.

(5) 毛刺　毛刺的出现也是由于随机噪声的影响而形成的. 这种位置可以检测到一个纹线端点和一个纹线分叉点, 属于伪特征点. 这种伪特征点的特点是一对端点与分叉点之间有纹线相连, 且两点之间距离比较近.

2. 2　指纹细节特征点的固有分布规律分析

椐有关资料和实验观察, 指纹纹线和细节特征点存在以下特点:(1) 除去模式区等个别区域以外, 指纹纹线的变化趋势是平缓的, 两条相邻纹线之间的宽度大致是相等的. (2) 在500dp i 的分辨率下, 一般指纹图象中不存在距离小于8个像素点的细节特征点. (3) 指纹中基本不存在毛刺、纹线叉连这种带有突变性质的结构. 所以, 诸如距离很近的两个纹线端点、两个纹线分叉点的结构或者毛刺、纹线叉连等

, 则该两点为伪特征点, 予以删除. 4

(6) 纹线叉连形成的伪特征点的删除

原始细节特征点集中, 对任意两个纹线分叉点

, 则2

≈i , j , 如果D (i , j ) ≈D 5且C (i , j ) =1, 且∃Η该两点为伪特征点, 予以删除.

其中, D 1, D 2, D 3, D 4, D 5为距离门槛值, 在指纹图象为500dp i 的采集分辨率下, 经实验确定, D 1,

D 2, D 3, D 4分别取7, 3, 4, 8; D 5为指纹图象平均纹

线宽, 可通过计算求得.

第12期尹义龙等:改进的指纹细节特征提取算法

A =1-

1305

3　实验结果

为验证改进算法的性能, 选取30幅典型指纹图象, 在主频为P 733、内存为128M 的台式微机上, 用改进算法和常规算法进行了性能对比实验. 常规算法是在经完全细化、纹线修复的指纹图象上进行的特征提取, 而改进算法则是在未完全细化、未对纹线做任何修复的图象上进行的. 定义特征提取的准确率为

用时

(秒 幅)

0. 470. 18

　(3) 检测到的特征点数-伪特征点数+丢失的特征点数

实验结果如表1所示. 图4是用常规算法和改

进算法分别对一幅指纹图象进行细化处理和特征提取的结果, 其中方框代表纹线端点, 圆圈代表纹线分叉点. 就细节特征提取而言, 迄今为止, 指纹自动识别技术中还没有一个既定的标准来规定准确率达到多少算是合格的. 实际应用证明, 87%的准确率基本可以满足指纹匹配算法的需要.

表1

　常规算法和改进算法的细节特征提取统计结果

算法常规算法改进算法

检测到的特征点

(个 幅)

66. 053. 4

出现伪特征点

(个)

8. 6

)

. 7. 3

特征提取准确率

(%) 8187

(a ) 常规算法(b ) 改进算法

图4　用常规算法和改进算法进行细化和特征提取的结果

4　结　论

在常规细节特征提取方法的基础上, 对指纹细

节特征提取算法进行了一定的改进, 即未对纹线进行修复而是直接在细化指纹图象上提取所有的细节特征点, 然后利用伪特征点在数学形态学上的分布规律, 对伪特征点进行了删除. 初步的实验结果表明, 与常规方法相比, 该算法较大幅度地提高了特征提取的速度, 特征提取的准确率也基本可以满足实际应用的需要.

实验过程中还发现, 在指纹图象质量比较差时, 改进算法能有效删除大多数伪特征点, 特征提取的准确率比常规方法有大幅度提高; 而在指纹图象质量比较好时, 改进算法的固有缺陷总会导致误删除少量真正的特征点, 特征提取的准确率要比常规算法低.

由于改进算法造成真正特征点丢失的情况多集

中在指纹模式区, 而这部分特征点对指纹识别而言比周边特征点具有更大的权重, 这是今后需要进一步完善之处.

参考文献

1　L in Hong . A utom atic personal identificati on using fingerp rints

[D]. U S:Mich igan State U niversity, 1998:5～46.

2　R atha N , Chen S , Jain A K . A dap tive flow o rientati on based

feature extracti on in fingerp rint i m ages [J ]. Pattern R ecogniti on , 1995, 28(11) :1657～1672.

3　M eh tre B . F ingerp rint i m age analysis fo r autom atic identificati on

[J ]. M ach ine V isi on and A pp licati on , 1993, 6(223) :124～139. 4　Hong L , Jain A K , Bo lle R et a l . Pankanti . Identity authentica 2

ti on using fingerp rints [A ]. In

:P roc . of F irst Int’lConference on A udi o and V ideo 2Based B i om etric Person A uthenticati on [C ],

～110. Geneva, Sw itzerland, 1997:103

5　M ai o D , M altoni D . D irect gray 2scale m inutiae detecti on in fin 2gerp rints [J ].

IEEE T ransacti ons on Pattern A nalysis and M a 2

～40. ch ine Intelligence , 1997, 19(1) :27

6　Fang Xu 2dong , Yau W ei 2Yun , Ser W ee . D etecting the finger 2

1306

中国图象图形学报第7卷(A 版

)

p rint m inutiae by adap tive tracing the gray 2level ridge [J ]. Pat 2

～1013. tern R ecogniti on , 2001, 34(5) :999

7　Yu Sh iaw 2Sh ian , T sai W en 2H siang . A new th inning algo rithm

fo r gray 2level i m ages by the relaxati on technique [J ]. Pattern

　　　宁新宝　1941年生, 南京大学电子科学与工程系教授、博士生导师、南大银佳生物识别技术研究所所长. 主要研究方向为生物信息采集与处理. 发表论文80余篇

.

～1076. R ecogniti on, 1990, 23(10) :1067

8　D atta A , Parui S K . A robust parallel th inning algo rithm fo r bi 2

～1192. nary i m ages [J ]. Pattern R ecogniti on , 1994, 27(9) :1181

9　X iao Q , R aafat H . F ingerp rint i m age p rocessing :A com bined

statistical and structural app roach [J ]. 1991, 24(10) :985～992

.

Pattern R ecogniti on ,

　　　张晓梅　1971年生, 1994年获莱阳农学院工学学士学位, 现为南京大学电子科. 主要研究方向为数字图象处理.

　　　尹义龙　1972年生, 2000年获吉林工业大学工学博士学位, 现为南京大学电子科学与工程系博士后、南大银佳生物识别技术研究所副所长. 主要研究方向为图象处理与模式识别、征识别

.