基于灰度指纹图像的指纹特征提取算法研究

第 18卷第 2期 系 统 仿 真 学 报© Vol. 18 No. 2 2006年 2月 Journal of System Simulation Feb., 2006 • 319 • 基于灰度指纹图像的指纹特征提取算法研究 赵应丁 1,2,3,4, 戴仕明 4 刘金刚 1,2,3 1.中国科学院计算技术研究所, 北京 100080; 2.中国科学院研究生院, 北京 100039; 3.首都师范大学计算机科学联合研究院, 北京 100037 4.江西农业大学, 江西 330045 摘 要 一种全新的直接从灰度指纹图像中提取指纹特征点的算法 该算法不需要像常见的特征点 提取算法那样需要非常耗时的滤波和细化过程 而是首先对指纹图像进行规格化操作 其次定位到 离指纹图像中心最近且未处理过的脊线上 再沿该条脊线搜索到候选特征点为止 然后再根据判 断条件判定候选特征点的真伪 最后对该条脊线的所有像素点进行标记 依此方法 逐条处理其他 脊线 经算法实现验证 该算法明显比传统算法运算速度快 关键词 指纹图像 提取特征点 脊线搜索 标记 中图分类号 TP391.41 文献标识码 A 文章编号 1004-731X (2006) 02-0319-04 Research on Grey-Scale Image Based Extraction Fingerprint Minutiae Algorithm ZHAO Ying-ding1,2,3,4, DAI Shi-ming4 LIU Jin-gang1,2,3 (1.Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China; 2.Graduate School of Chinese Academy of Sciences, Beijing 100039, China; 3.Join Faculty of Computer Scientific Research, Capital Normal University, Beijing 100080, China; 4.Jiangxi Agricultural University, Jiangxi 330045, China) Abstract: A new algorithm for direct extract fingerprint minutiae from grey-scale image was proposed. Different from traditional fingerprint minutiae extraction algorithm, this algorithm does not need thinning and filtering which demands complicated calculations. First, fingerprint images underwent normalization operation, then an unprocessed ridge closest to the center of the fingerprint image was located, next, candidate minutia was found along the ridge, after that, true and false minutiae were judged according to the given judgment conditions. Finally, all the pixels were marked along the ridge. Other ridges will be processed with the same method. It is confirmed through algorithm implement that this algorithm is apparently faster than traditional ones. Key words: fingerprint image; extract minutiae; ridge search; mark 引 言1 指纹作为人体的重要特征 因为其所具有的长期不变性 和唯一性 已经成为生物识别领域的重要手段 通过对人的 指纹特征来鉴别一个人身份的技术 越来越得到广泛的应 用 随着指纹检测技术和指纹识别算法的不断改进 指纹识 别技术在越来越多的部门得到应用 在指纹识别中 已经有几种指纹特征提取方案被提出 尽管它们之间各不相同 但主要步骤均相差不大 主要是包 括两大部分 即指纹图像预处理和指纹特征处理, 如 Lin Hong等在[1] [2]和[3]中所提出的指纹图像增强算法就包括 归一化 方向图计算 频率图计算 掩码区域计算和 Gabor 函数滤波操作 在指纹图像预处理算法中 首先是进行指纹 图像滤波 被采用过的滤波算法有 均值滤波 中值滤波 直方图均衡化滤波 N×N 频值滤波 十字型中值滤波 方 向图滤波和 Gabor函数滤波等 图像滤波主要目的是去除指 纹图像中的叉连 断点及模糊不清的部分 其次是将滤波后 收稿日期 2004-12-13 修回日期 2005-03-21 作者简介 赵应丁(1965-), 男, 江西余干人, 副教授, 博士生, 研究方向 为数字图像处理, 网络与信息安全等 戴仕明(1965-), 男, 江西宜丰人, 副教授, 硕士生, 研究方向为数字图像处理等 刘金刚(1962-1), 男, 辽 宁铁岭人, 教授, 博导, 研究方向为计算机智能接口技术等 的灰度指纹图像转化为二值化图像 一般情况下 灰度指纹 图像均为 256 级灰度图像 通过二值化方法变成 0 1取值 的二值化图像 对一幅图像进行二值化, 首先必须选取相应阈 值, 把高于阈值灰度的像素点转换为 1, 低于阈值的象素点 转换为 0 但由于不同图像的灰度基值不同, 以及同一幅图 像中各部分的明暗不同 , 所以阈值的设定是很困难的 , Oivind Due Trier和 Anil.K.Jain在文[4]中对用于指纹图像的 常见二值化方法进行比较和性能评估 最后 就是对二值化 图像进行细化操作 该过程使得脊线的宽度缩小到一个像素 第二部分的步骤 就是通过对细化后的指纹图像进行图 像扫描提取相对应的特征点 即从经预处理后的指纹图像中 提取相关端点和分叉点的相对位置 方向以及附近其它特征 点的相关信息 美国国家标准局(NIST)提出四种类型的特征 分类标准 即端点 分叉点 三叉点和未确定点 在本文中 我们采用了美国联邦调查局(FBI)在文[5]中所提出的指纹分 类方法 该方法也是目前绝大部分自动指纹识别系统所采纳 的 基于 2类的分类方法 即端点和分叉点 如图 1所示 图 1 指纹特征点 纹线端点和分叉点 第 18卷第 2期 Vol. 18 No. 2 2006年2月 系 统 仿 真 学 报 Feb., 2006 • 320 • 由于在上面所提到的传统算法中 指纹图像滤波 二 值化和细化处理都非常耗时 占据了整个指纹特征提取算法 的全部时间的 90%以上 本文提出了一个全新指纹特征点提 取算法 该算法没有采用图像滤波 细化处理等过程 二值 化过程也非常简单 耗时很少 在算法图像预处理过程中只 是经过了一个简单的规格化过程 对图像进行二值化和修补 操作 然后就直接在灰度图像中采用脊线跟随算法搜索该条 脊线上所有像素点 提取候选特征点 由于图像中存在着大 量的伪特征点 所以我们在算法中有一个判断特征点真伪的 过程 为防止脊线重复搜索 对每一条被处理过的像素点进 行标记 在本文所介绍的指纹特征提取算法中 共分为 2大 步骤 第一步为指纹图像规格化 第二步为脊线跟随算法 1 指纹图像规格化 算法中通过指纹图像规格化过程 主要是对采集到的指 纹图像进行简单的处理 这里主要是做三部分的操作 第一 对指纹图像进行二值化处理 第二是对指纹图像进行修补 剔除其中的孤立像素点等 第三估计脊线的平均宽度 1.1 矩形二值化法 我们通过对大量的指纹图像分析 在指纹图像的像素灰 度平均值在指纹图像的边缘处与图像坐标中心附近处相差 很大 中心坐标附近像素点的灰度平均值通常只有边缘处的 像素灰度平均值的 80%左右 因此整幅指纹图像采用统一的 阈值或采用分块的自适应阈值对指纹图像进行二值化显然 是不准确的 本文中采用了以图像中心点为矩形中心的框 架 以该矩形四条边上的所有像素的灰度平均值作为矩形四 边上的所有像素进行二值化操作的阈值 如图 2所示 利用 位于矩形四边上的像素点计算二值化的阈值 图 2 指纹图像以及计算阈值的矩形框 设该指纹图像的高度及宽度分别为 h, w 位于坐标(i, j) 的像素灰度值为 gray(i, j) k=k>w?w:k for(i=0;iaverage_gray) gray(i, j)=255; else gray(i, j)=0; if(gray(h-i,j)>average_gray) gray(h-i, j)=255; else gray(h-i, j)=0; } //对左右两边进行二值化 for(j=i+1;javerage_gray) gray(i, j)=255; else gray(i, j)=0; if(gray(i, w-j)>average_gray) gray(i, j)=255; else gray(i, j)=0; } } 1.2 指纹图像修补 指纹图像修补是对图像进行简单的去噪处理 消除原始 图像中的孤立像素点 即在一系列白像素点中所包围的部分 黑像素点 如图 3(a),(b),(c)所示 对于在一系列的黑像素点 之中所包围的基本的部分白像素点 将这些白象素点进行灰 度取反 即改为黑象素点如图 3(d), (e), (f) (a) (b) (c) (d) (e) (f) 图 3 孤立像素点和空洞 1.3 估计指纹原始图像脊线平均宽度 由于不同的采集指纹图像方法以及指纹图像的大小不 一 使得在指纹脊线的宽度 毛刺长度等就不一致 我们在 判断特征点的真伪时需要这些参数 由于篇幅限制 并且这 部分算法比较简单 这里就不对算法进行描述 2 脊线跟随算法 脊线跟随算法为整个算法的关键所在 它所要完成的 功能就是在指纹图像预处理的基础之上 首先定位到一条新 的 未处理过的脊线上 从该脊线的当前像素点开始 沿着 脊线搜索完该脊线上的所有像素点 并且对已处理过的像素 第18卷第2期 Vol. 18 No. 2 2006年 2月 赵应丁, 等 基于灰度指纹图像的指纹特征提取算法研究 Feb., 2006 • 321 • 点进行标记 以避免像素点被重复处理 对于所读取到的候 选端点或分叉点进行判断 最后得到该条脊线上的特征点 算法流程图见图 4 图 4 脊线跟随算法流程图 2.1 定位未处理的脊线 脊线跟随算法为整个算法的关键所在 它所要完成的功 能就是在指纹图像预处理的基础之上 首先定位到一条新 的 未处理过的脊线上 从该脊线的当前像素点开始 沿着 脊线搜索完该脊线上的所有像素点 并且对已处理过的像素 点进行标记 以避免像素点被重复处理 对于所读取到的可 能端点或分叉点进行判断 最后得到该条脊线上的特征点 这里我们所采用的方法是 以该像素为中心 将 360度 的空间平均分成 8个方向 分别沿该 8个方向进行搜索未处 理过的像素点 使用以最短距离搜索到的未处理点作为新的 一条脊线的起始点 2.2 定义集合W 像素点跟随算法就是在当前跟随的脊线上 通过当前像 素点求出下一个像素点所在位置 我们所采用的算法就是利 用 8方向图 求出该像素的点在原始图的点方向 通过点方 向计算该脊线上跟随像素点的位置 我们首先定义一个包含 P0像素点的集合W 该集合所 包含的范围为沿通过 P0像素点且与该 P0像素点的点方向平 行的两条直线为矩形的两条边 与法线方向一致且通过 P0 的一条直线以及与该直线平行的另一条直线组成矩形区域 的另外两边 该矩形区域内的所有像素点组成集合W 矩形 区域如图 5所示 图 5 矩形区域定义 该矩形区域的长度为 d1 矩形的宽度为 d2 由于像素点 P0的方向可能与 X 轴或 Y轴不平行 所以在计算该矩形区 域的像素点坐标就比较困难 并且由于倾斜角度的原因 区 域内像素点的数量也可能不一致 我们通过建立如图所示的 虚线所描述的坐标系 X1Y1 其中 X1坐标轴与 X坐标轴平 行 Y1坐标轴与 Y坐标轴平行 X1Y1坐标系的原点位于在 P0像素点上 通过对 X1Y1坐标系沿逆时针旋转 á角 得到 X2Y2坐标系 其中 X2坐标轴与像素点 P0的点方向一致 Y2坐标轴与像素点 P0的点方向垂直 设 P0像素点在 XY坐 标系中的坐标为(x0,y0) 对于矩形框内任一点 P 其在 XY 坐标系中的坐标为(x, y) 在 X2Y2坐标系中的坐标为(x2,y2) 坐标系 X1Y1中的 X1轴与 X1Y1中的 X2轴交角为 á 则他们 之间的关系如下 ( ) ( ) ï ï î ï ï í ì ÷÷ ø ö çç è æ +÷÷ ø ö çç è æ ÷÷ ø ö çç è æ - -- ÷÷ ø ö çç è æ +÷÷ ø ö çç è æ ÷÷ ø ö çç è æ - =÷÷ ø ö çç è æ 位于第四象限像素点 位于第一象限像素点 P y x y x cossin sincos P y x y x cossin sincos y x 0 0 2 2 0 0 2 2 aa aa aa aa 或 ( ) ( ) ï ï î ï ï í ì ÷÷ ø ö çç è æ - - ÷÷ ø ö çç è æ -- - ÷÷ ø ö çç è æ - - ÷÷ ø ö çç è æ - =÷÷ ø ö çç è æ 位于第四象限像素点 位于第一象限像素点 P yy xx P yy xx y x 0 0 0 0 2 2 cossin sincos cossin sincos aa aa aa aa 这样我们就可以得到像素点集合W 并且所有像素点的 坐标均采用 XY坐标系标注 2.3 连通标记算法 接下来就是对集合W中所有像素点进行标记操作 算法 思路 首先对标记 P0 把像素点 P0的 8-邻域范围内并且包 含在集合W中的所有未处理过的像素点进行预标记并在标 记的像素点中记录标记距离为 1 其次是采用同样的方法 对刚才被预标记的所有像素点的 8-邻域范围内并且也包含 在集合W中的所有未处理过的像素点进行预标记并在标记 的像素点中记录标记距离为 2 通过以上方法把集合W中所 有与 P0 像素点连通的像素点进行预标记 对于集合中所有 未标记的像素点的标记距离设为-1 像素点结构定义如下 struct PixelPoint { int x,y; //像素点坐标 int distance; //标记距离 int type; //像素点类型 struct PixelPoint * next; //指针 } 算法描述如下 PixelPoint head,p,q; head =p1; q=p1; while(head!=NULL) { for(i=-1;i<=1;i++) { for(j=-1;j<=1;j++) { if(i!=0&&j!=0) { 第 18卷第 2期 Vol. 18 No. 2 2006年2月 系 统 仿 真 学 报 Feb., 2006 • 322 • p.x=head.x+i; p.y=head.y+j; if( WÎp && p.distance==-1) { p.distance=head.distance+1; q->next=p; q=q->next; }}} } head=head->next; } 2.4 特征点检测算法 就检测在 3.3 所标记的像素点中脊线跟随过程的跟随 像素点 它可能是可能的分叉点 端点或普通像素点 我们 所采用的方法就是首先提取集合W中的位于矩形区域边界 上所存在的已被标记过的像素点 组成集合 E 计算集合W 中的标记距离最大值 设为 k 即 k= max {p.distance | " p�Ù} 在已标记过的像素点中 标记距离分别为 0,1, … ,k-1和 k 的像素点集合分别为 0M M1 M2 … Mk-1 和 Mk Check_Link(Mi)是检测集合 Mi 中的像素是否互相连通 如 果连通则返回 True 否则返回 False 脊线跟随算法中确定跟随像素点的算法描述如下 { for(i=k,i>=0;i--) { if(Check_Link(Mi)) break; } if( iM E f==I and i= =k) { p=Mi中某一个非边缘点 p.type =0; //候选端点 } else if( !iM E f=I and i= =k) { p=Mi中某一个非边缘点 p.type=2; //普通像素点 } else { Mi+1=>Mi+1,1�Mi+1,2 满足 1,1 1,2i iM M f+ + =I && Check_Link(Mi+1,1)=True && Check_Link(Mi+1,2)=True while(1) { iq M" Î ; if(Check_Link(Mi+1,1{q}) && Check_Link(Mi+1,2+{q})) { p=q; p.type=1;//候选分叉点 break; } else Mi=Mi-{q}; } } return p; } 这时 p就是在脊线跟随过程中的跟随像素点 2.5 真伪特征点判定算法 在一条脊线跟随完成后 会产生大量的候选特征点 我们在 2.4中对所产生的所有候选特征点都记录下来了 在 本部分 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 中我们就是根据前面所保存的候选特征点中剔 出伪特征点 提取真正的特征点 我们这里主要是根据两特 征点之间的跟随距离进行判别 如果它们之间的跟随距离小 于 d3 则为伪特征点 定义 head为指向保存候选特征点的链表中的第一个候 选特征点 我们这里主要是要完成两方面的工作 (1) 检测所有的分叉点 判断其两个分叉的跟随距离是 否大于 d3 如果其中有两个分叉点的跟随距离大于 d3 则该 分叉点为真的特征点 如果两个分叉的跟随距离有一个小于 d3 则该分叉点为伪特征点并且删除该分支 如果两个该分 叉点的两个特征点均小于 d3 则该分叉点为伪特征点 并删 除跟随距离较少的那个分支 (2) 如果最后该脊线只剩下两个端点 并且它们之间的 距离小于 d3 则该条脊线不是真正的脊线 可能是由毛刺引 起的 删除所记录的全部特征点 在一条脊线的所有特征点检测完毕 再定位到下一条 脊线上 就这样从内向外循环每一条脊线上的所有特征点 直至所检测到的特征点数量符合要求为止 3 结论 以上是本文所提出的直接从灰度图像中提取指纹特征 算法 该算法主要采用指纹图像规格化和脊线跟踪两大步 骤 在指纹图像规格化操作中 主要包含了矩形二值化处理 指纹图像修补和脊线平均宽度估算 在脊线跟踪算法中主要 是逐条沿象素点脊线方向提取相关候选细节特征点 对于每 条已处理过的脊线进行标记 避免重复检测 最后删除伪特 征点 该算法避免了传统算法中的指纹图像滤波 指纹图像 细化等非常耗时的步骤 算法运行速度较快 我们从 FVC2000 指纹数据库 DB2_B 中随机提取了 50 枚指纹样本 和通过本实验室研制的指纹采集装置采集了 50 枚指纹 共 选用 100枚指纹进行测试 测试环境为 PIII600计算机 运 行的操作系统为Windows 2000 Professional 内存为 128MB 所采集的图像大小为 256*288 分辨率为 256级灰度 DB2_B指纹数据库中的指纹图像大小为 256*384 分辨率为 256级灰度 以此比较 我们对 A. Jain等在文[1]和[2]中所 提出的算法进行了比较 对所采集的指纹图像细节特征提取算法平均耗时约为 0.55 秒 对 DB2_B指纹数据库中的指纹图像细节特征提取 算法平均耗时约为 0.70秒 耗时受指纹图像大小影响 A.Jain 在文[1]所提到的实验结果为 2.49秒 运行环境为 P200的计 算机 文中没有说明指纹图像的大小 作者对该算法进行实 现 对于 256*288大小的指纹图像 平均耗时为 1.2秒 通过以上数据可以看出 该算法效果较好 能够满足 (下转第 326页) 第 18卷第 2期 Vol. 18 No. 2 2006年2月 系 统 仿 真 学 报 Feb., 2006 • 326 • 表 3 JPEG压缩及水印图像 PSNR对比 JPEG压缩质量系数 PSNR dB 40% 46.9731 50% 47.6205 60% 48.2396 70% 49.0726 80% 50.1946 90% 51.3970 100% 52.2854 5 结论 本文利用图像小波变换系数的树结构关系和各层小波 系数的特点 将低频重要系数分为两类 一类对应强纹理区 域 另一类对应于弱纹理区域 根据人眼视觉特性 在强纹 理区域嵌入较强水印 在弱纹理区域嵌入较弱的水印 使水 印具有不可见性和较好的鲁棒性 是一种基于图像内容的自 适应小波域水印算法 而且在水印提取过程中 不需要原始 图像 是一种盲水印算法 增强了算法的安全性 有着广泛 地应用价值 参考文献 [1] Shapiro J M. Embedded image coding using zerotrees of wavelet coefficients [J]. IEEE trans. On Signal Processing (S0018-9380), 1993, 41(12): 3445-3462. [2] Cox I J, Killian J, Leighton t. A secure, robust watermark for multimedia [J]. IEEE Trans. Image Processing (S0018-9480), 1997, 6(12): 1673-1687. [3] Daubechies I. Ten Lectures on Wavelets [C]//CBMS-NSF conference series in applied mathematics, SIAMED. [4] Kundur D, Hatzinakos D. A robust digital image watermarking method using wavelet based fusion [C]//Proc of ICIP’97, Washington DC, 1997, 1: 544-547. [5] Fabien A P Petitcolas, Ross J Anderson, Markus G. Kohn. Information Hiding A Survey [J]. Proceedings of the IEEE (S0018-9219), 1999, 87(7): 1062-1078. [6] 黄继武, Shi Y Q, 程卫东. DCT域图象水印: 嵌入对策和算法[J]. 电子学报, 2000, 28(4): 57-60. (上接第 318页) 表 4 某型鱼雷自航发射仿真计算结果表 后段管及 长度(mm) 中段管及 长度(mm) 前段管 (mm) 鱼雷出管 速度(m/s) 鱼雷运动 时间(s) 590/3700 740/4300 0 6.729 2.880 570/3700 740/4300 0 6.529 3.520 570/3700 740/4300 650 4.844 3.960 将表 4与表 3进行比对可以看出 鱼雷出管速度基本上 与试验数据相吻合 鱼雷运动时间也在试验数据的估计范围 之内 从而验证了本仿真模型的正确性 4 结论 本文通过对鱼雷自航发射过程中受力情况的具体分析 建立了自航发射鱼雷的内弹道数学模型 并以某型自航管及 对应的鱼雷参数为例进行了仿真计算 仿真结果与试验结果 基本吻合 证明了本模型和仿真程序的可信性 从而可为自 航式发射管的设计提供验证手段 参考文献 [1] 孙柱国. 自航式鱼雷发射装置[C]//发射技术论文集. 昆明: 七零 五所昆明分部, 2000, 184-193. [2] 解洪举. 自航式发射鱼雷的内弹道研究[C]//发射技术论文集. 昆 明: 七零五所昆明分部, 2000, 194-203. [3] 周广林, 王云. 自航鱼雷发射装置内弹道计算与管体参数选择 [C]//鱼雷发射装置学术研讨会论文集. 昆明: 七零五所昆明分部, 2002, 69-78. [4] 黄震中. 鱼雷总体设计[M]. 西安: 西北工业大学出版社, 1987, 27-30. [5] 张兆顺, 崔桂香. 流体力学[M]. 北京: 清华大学出版社, 1999, 325-326. [6] 景思睿 , 张鸣远 . 流体力学[M]. 西安: 西安交通大学出版社, 2001, 181-189. (上接第 322页) 在线指纹识别要求 该算法存在的主要问题是如果指 纹图像质量较差 特别是毛刺和断连较多时 则效果较一般 我们正在针对此问题进行改进 文中所使用的参数 d1,d2,d3 其中 d1可选择 12~20之间 效果较好 d2选择主要是矩形区域能基本包含 3条脊线 d3 主要是指定脊线的最短跟随长度 该两个参数与所采集的图 像大小有关 笔者所采用的是 d2=12,d3=10~12 参考文献: [1] Lin Hong, Yifei Wan, Anil Jain. Fingerprint image enhancement: algorithm and performance evaluation [J]. IEEE Trans on Pattern Analysis and Machine intelligence. 1997, 19(4): 302-305. [2] Anil Jain, Lin Hong, and Rund Bolle, On-Line Fingerprint Verification [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(4): 302-314. [3] Lin Hong. Fingerprint Enhancement 3rd [J]. IEEE Workshop on Applications of Computer Vision (WACV '96), 1996, 202-207. [4] Oivind Due, Anil K Jain. Goal-Directional Evaluational of Binarization Methods [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(12): 1191-1201. [5] J H Wegstein. An Automated Fingerprint Identification System [R]. US Government Publication, Washington, 1982. [6] Dario Maic, Davide Malteni Maltoni. Direct Gray-Scale Minutiae Detection In FingerPrints [J]. IEEE Transaction on pattern analysis and Machine intelligence, 1997, 19(4): 2941-2994.