基于结构特征匹配的指纹识别算法研究
|
摘要
指纹识别作为一种方便有效的生物识别技术,受到了人们广泛的关注和重视,是目前个人身份认证的重要组成部分。尽管在此技术上已有多种成型产品问世,但因为许多核心技术因商业利益而未经公开,以及社会的发展对系统的性能提出了更高的要求,所以进行指纹识别技术方面的研究,具有较高的现实意义和理论意义。
本文在查阅大量国内外指纹识别方面的参考文献的基础上,对指纹识别中的预处理算法、特征提取算法和匹配算法进行了深入和系统的研究。完成了如下工作:
1.在求取指纹方向图部分,通过分析领域方向模板法和最小均方差估计块方向方法,针对点方向求取时精确度不高的问题,提出一种改进的方法,将最小均方差法应用到每个像素点的点方向的计算,使点方向图的准确性有了提高。
2.在特征提取方面,研究了两种指纹特征的提取方法:基于预处理的特征提取和基于灰度指纹图像的直接特征提取,并通过实验进行比较。
3.在指纹匹配部分,提出一种基于细节点和中心点的连线所穿越的脊线数与角度差相结合的方法构造指纹的结构特征进行匹配。实验结果表明,该方法对指纹图像的旋转、偏移、扭曲和压缩等具有很好的鲁棒性。
4.采用一种改进的Bresenham画线算法来计算两点连线穿越的脊线数。该算法可以避免遗漏或误判脊线,准确地计算出两点之间间隔的脊线数。
作者在计算机上用Visual C++实现了上述全套算法,实验结果比较令人满意。
Fingerprint identification is one of the most important and effective biometric technology which has been paid amount of attention. It is the significant part of individual authentication. Nowadays many fingerprint products have been offered, however, most of the key methods wouldn't be publicized because of commercial benefits. Besides, more requirements on the fingerprint identification system are made because of the society's development. So studies on the theory and application of fingerprint recognition have significant meanings both in theory and application.
Base on plenty of papers, this dissertation makes some research on common fingerprint recognition,which including algorithms on fingerprint preprocessing, especiaolly on feature extraction and feature matching.The main points of the dissertation are as follows:
1.In the process of computing fingerprint direction image,analyze neighbor direction mask method and min average covariation block direction estimation method.Focusing on the problem of point direction with low accuracy,propose a improved scheme in which applicate the min average covariation algorithm to compute the direction of every point.This scheme improves the accuracy of direction image.
2.In the process of fingerprint feature extraction,study two methods on extracting fingerprint feature:preprocessing-based extraction and Gray fingerprint image-based direct feature extraction. The experimental results have been compared.
3. In the process of fingerprint matching, a new fingerprint matching method is presented. This algorithm constructs the structure features based on the number of ridge lines and D-value of angles between minutiae and core point. The experimental results demonstrate that it is robust to rotation, excursion, distortion and condensation.
4. Use an improved Bresenham draw line algorithm to compute the ridge number between two points. It can calculate the number of ridges between two points exactly because it could avoid missing or tell wrong ridges.
All algorithms mentioned in this thesis are carried out with Visual C++ on the computer.The experiment results is satisfied.
本文在查阅大量国内外指纹识别方面的参考文献的基础上,对指纹识别中的预处理算法、特征提取算法和匹配算法进行了深入和系统的研究。完成了如下工作:
1.在求取指纹方向图部分,通过分析领域方向模板法和最小均方差估计块方向方法,针对点方向求取时精确度不高的问题,提出一种改进的方法,将最小均方差法应用到每个像素点的点方向的计算,使点方向图的准确性有了提高。
2.在特征提取方面,研究了两种指纹特征的提取方法:基于预处理的特征提取和基于灰度指纹图像的直接特征提取,并通过实验进行比较。
3.在指纹匹配部分,提出一种基于细节点和中心点的连线所穿越的脊线数与角度差相结合的方法构造指纹的结构特征进行匹配。实验结果表明,该方法对指纹图像的旋转、偏移、扭曲和压缩等具有很好的鲁棒性。
4.采用一种改进的Bresenham画线算法来计算两点连线穿越的脊线数。该算法可以避免遗漏或误判脊线,准确地计算出两点之间间隔的脊线数。
作者在计算机上用Visual C++实现了上述全套算法,实验结果比较令人满意。
Fingerprint identification is one of the most important and effective biometric technology which has been paid amount of attention. It is the significant part of individual authentication. Nowadays many fingerprint products have been offered, however, most of the key methods wouldn't be publicized because of commercial benefits. Besides, more requirements on the fingerprint identification system are made because of the society's development. So studies on the theory and application of fingerprint recognition have significant meanings both in theory and application.
Base on plenty of papers, this dissertation makes some research on common fingerprint recognition,which including algorithms on fingerprint preprocessing, especiaolly on feature extraction and feature matching.The main points of the dissertation are as follows:
1.In the process of computing fingerprint direction image,analyze neighbor direction mask method and min average covariation block direction estimation method.Focusing on the problem of point direction with low accuracy,propose a improved scheme in which applicate the min average covariation algorithm to compute the direction of every point.This scheme improves the accuracy of direction image.
2.In the process of fingerprint feature extraction,study two methods on extracting fingerprint feature:preprocessing-based extraction and Gray fingerprint image-based direct feature extraction. The experimental results have been compared.
3. In the process of fingerprint matching, a new fingerprint matching method is presented. This algorithm constructs the structure features based on the number of ridge lines and D-value of angles between minutiae and core point. The experimental results demonstrate that it is robust to rotation, excursion, distortion and condensation.
4. Use an improved Bresenham draw line algorithm to compute the ridge number between two points. It can calculate the number of ridges between two points exactly because it could avoid missing or tell wrong ridges.
All algorithms mentioned in this thesis are carried out with Visual C++ on the computer.The experiment results is satisfied.
引文
[1] O’Gorman.L. Comparing passwords, tokens, and biometrics for user authentication. In:Proceedings of the IEEE, 2003, 91(11):2019-2040
[2] 孙冬梅,裘正定.生物特征识别技术综述.电子学报, 2001, 29(12):1744-1748
[3] G. Lassmann. Some results on robustness, security and usability of biometric systems.IEEE International Conference on Multimedia and Expo,2002, 2(8):577-579
[4] P.J.Phillips,A.Martin,C.L.Wilson, et al.An introduction evaluating biometric systems. Computer, 2000, 33 (2):56-63
[5] R.R.Sanchez, C.A.Sanchez. Fingerprint verification using smart cards for access control systems.IEEE Aerospace and Electronics Systems Magazine, 2002, 17(9):12-15
[6] Anil K.Jain, Lin Hong, Ruud Bolle. An identity-authentication system using fingerprints. Proceeding of the IEEE, 1997, 85 (9):1365-1387
[7] B.C.Seow,S.K.Yeoh,S.L.Lai et al.Image Based Fingerprint Verification.In: SCOReD of Student Conference on Research and Development. Bukit Beruang,2002:58 - 61
[8] Ling Hong, Wan Yfei, Anil K Jain. Fingerprint Image enhancement:Algorithm and Performance Evaluation. IEEE Transaction on PatternAnalysis and Machine Intelligence, 1998,20(8):777-789
[9] 罗希平,田捷.自动指纹识别中的图像增强和细节匹配算法.软件学报, 2002, 13(5):946-955
[10] 尹义龙,詹小四,谭台哲等.基于加博函数的指纹增强算法及其应用,软件学报,2003,14(3):484-489
[11] 蒙丽彬,赵进创,傅文利.一种改进的基于 Gabor 滤波的指纹增强算法.微计算机信息,2006,22(11-3):297-299
[12] BM Mehtreand B, Chatterjee. Segmentation of fingerprint image-a composite method Pattern Recognition .1989,22(4):381-385
[13] Rao A R.A taxonomy for texture description and identification. New York: Springer Verlag .1990,372-381
[14] Rafael C. Gonazalez,Richard E. Woods.数字图像处理.第二版.阮秋琦,阮宇智译.北京:电子工业出版社,2003:59-170
[15] Park.S,Smith.M.J.T,Jun Jae Lee.Fingerprint enhancement based on the directional filter bank.In: Proceeding of International Conference on Image Processing. Atlanta,2000(3):793-796
[16] B. M.Mehtre. Fingerprint Image Analysis for Automatic Identification.Machine Visionand Applications, 1993, 6:124–139
[17] 孙以雷,陈红卫,指纹图像的二值化方法研究.舰船电子工程,2006,26 (1):110-112
[18] 楚亚蕴,詹小四,孙兆才等.一种结合方向信息的指纹图像二值化算法.中国图象图形学报,2006,11(6):855-860
[19] Chin R T, WanH K, StoverD L,et al.A one-pass thinning algo-rithm and its parallel implementation. ComputerVision Graphics Image Processing, 1987,40(1):30-40
[20] Datta A, Parui S K. A robust parallel thinning algorithm for binary images. Pattern Recognition, 1994, 27(9):1181-1192
[21] 冯星奎,李林艳,颜祖泉.一种新的指纹图象细化算法,中国图象图形学报,1999, 4(10): 297-301
[22] 王家隆,郭成安,一种改进的图像模板细化算法.中国图象图形学报,2004.3, 9(3):297-301
[23] 梅园,孙怀江,夏德深.一种基于改进后模板的图像快速细化算法.中国图象图形学报, 2006,11(9):1306-1311
[24] N.K.Ratha,S.Chen,A.K.Jainl. Adaptive flow direction based feature extraction in fingerprit image. Pattern Recognition,1995,28(11):1657-1672
[25] 姜红超,张高伟.基于脊线跟踪的指纹细节特征提取.计算机工程,2007,33(8):185-186
[26] Miao D,Maltoni D.Direct gray-scale minutiae detection in fingerprint.IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(1):27-39
[27] Lin Hong. Automatic personal identification using fingerprints:[dissertation]. East Lansing, Michigan State University, 1998,80-81
[28] Jiang Xudong, Yau We Yun, SerWee. Minutiae extraction by adaptive tracing the gray level ridge of the fingerprint image. In: IEEE Sixth International Conference on Image Processing( IC IP’99) . Kobe, Japan, 1999, 2: 852-856
[29] Liu Jinxiang, Huang Zhongyang, Chan Kap Luk. Direct minutiae extraction from gray-level fingerprint image by relationship examination. In: IEEE Proceedings International Conference on Image Processing. V arcourer, British Columbia, Canada, 2000, 2: 427-430
[30] 杨小冬,宁新宝,谭台哲.基于纹线跟踪的指纹细节提取算法.计算机应用,2004, 24(3):75-78
[31] 王芙蓉,程鹏,邹璇.直接提取指纹特征算法的优化研究.中国图象图形学报,2004, 9(5):557-564.
[32] 赵应丁,戴仕明,刘金刚.基于灰度指纹图像的指纹特征提取算法研究.系统仿真学报,2006.2,18(2): 319-322
[33] Qinzhi Zhang, Kai Huang, Hong Yan. Fingerprint Classification Based on Extractionand Analysis of Singularities and Pseudoridges.In: ProceedingProceedings of the Pan-Sydney area workshop on Visual information processing, Sydney,2001, 83-87
[34] Xuejun Tan, Bir Bhanu, Yingqiang Lin.Fingerprint Classification Based on Learned Features,IEEE transctions on Systems, Man, and Cybernetics, Part C: Applications and Reviews 2005, 35(3):287-300
[35] Huvanandana S,Kim C,Hwang J.N.Reliable and Fast Fingerprint Identification for Security Applications.Image Processing,2000 (2):503?506
[36] A.Jain,A.Ross,Sali.Prabhakar.Fingerprint matching using minutiae and texture features.In:Proceedings of International Conference on Image Processing.East Lansing,2001 (10):282-285
[37] Bazen A.M,Verwaaijen G.T.B,Gerez S.H,et al.A Correlation-Based Fingerprint Verification System.Circuits Systems and Signal Processing,2000 (5):205?213
[38] 沈清,汤霖.模式识别导论.第二版.长沙:国防科技大学出版社,1991.1-290
[39] 王玮,李见为,张腾.指纹图像的预处理算法.计算机应用, 2004,24(5):72-75
[40] 刘灵丽.指纹图像预处理与特征提取:[湖南大学硕士学位论文].长沙:湖南大学计算机与通信学院,2005,18-33
[41] Ranade, Rosenfeld A.Point pattern matching by relation. Pattern Recognition, 1980, 12(4) :269-274
[42] Jiang, Xu-dong, Yau, Wei-Yun. Fingerprint minutiae matching based on the local and global structures. In: Proceedings of the 15th International Conference on Pattern Recognition. Los Alamitos, 2000,1042-1045
[43] 江杰,胡晓莉,李杰.一种新的指纹细节点匹配算法的研究.计算机应用, 2005, 25:114-115
[44] 侯少峰,彭少奇,王一丁.一种基于参考点方向的指纹极坐标匹配算法.计算机应用, 2006,25(10):20-22
[45] 孙家广.计算机图形学.第三版.北京:清华大学出版社,1998.169-170
[2] 孙冬梅,裘正定.生物特征识别技术综述.电子学报, 2001, 29(12):1744-1748
[3] G. Lassmann. Some results on robustness, security and usability of biometric systems.IEEE International Conference on Multimedia and Expo,2002, 2(8):577-579
[4] P.J.Phillips,A.Martin,C.L.Wilson, et al.An introduction evaluating biometric systems. Computer, 2000, 33 (2):56-63
[5] R.R.Sanchez, C.A.Sanchez. Fingerprint verification using smart cards for access control systems.IEEE Aerospace and Electronics Systems Magazine, 2002, 17(9):12-15
[6] Anil K.Jain, Lin Hong, Ruud Bolle. An identity-authentication system using fingerprints. Proceeding of the IEEE, 1997, 85 (9):1365-1387
[7] B.C.Seow,S.K.Yeoh,S.L.Lai et al.Image Based Fingerprint Verification.In: SCOReD of Student Conference on Research and Development. Bukit Beruang,2002:58 - 61
[8] Ling Hong, Wan Yfei, Anil K Jain. Fingerprint Image enhancement:Algorithm and Performance Evaluation. IEEE Transaction on PatternAnalysis and Machine Intelligence, 1998,20(8):777-789
[9] 罗希平,田捷.自动指纹识别中的图像增强和细节匹配算法.软件学报, 2002, 13(5):946-955
[10] 尹义龙,詹小四,谭台哲等.基于加博函数的指纹增强算法及其应用,软件学报,2003,14(3):484-489
[11] 蒙丽彬,赵进创,傅文利.一种改进的基于 Gabor 滤波的指纹增强算法.微计算机信息,2006,22(11-3):297-299
[12] BM Mehtreand B, Chatterjee. Segmentation of fingerprint image-a composite method Pattern Recognition .1989,22(4):381-385
[13] Rao A R.A taxonomy for texture description and identification. New York: Springer Verlag .1990,372-381
[14] Rafael C. Gonazalez,Richard E. Woods.数字图像处理.第二版.阮秋琦,阮宇智译.北京:电子工业出版社,2003:59-170
[15] Park.S,Smith.M.J.T,Jun Jae Lee.Fingerprint enhancement based on the directional filter bank.In: Proceeding of International Conference on Image Processing. Atlanta,2000(3):793-796
[16] B. M.Mehtre. Fingerprint Image Analysis for Automatic Identification.Machine Visionand Applications, 1993, 6:124–139
[17] 孙以雷,陈红卫,指纹图像的二值化方法研究.舰船电子工程,2006,26 (1):110-112
[18] 楚亚蕴,詹小四,孙兆才等.一种结合方向信息的指纹图像二值化算法.中国图象图形学报,2006,11(6):855-860
[19] Chin R T, WanH K, StoverD L,et al.A one-pass thinning algo-rithm and its parallel implementation. ComputerVision Graphics Image Processing, 1987,40(1):30-40
[20] Datta A, Parui S K. A robust parallel thinning algorithm for binary images. Pattern Recognition, 1994, 27(9):1181-1192
[21] 冯星奎,李林艳,颜祖泉.一种新的指纹图象细化算法,中国图象图形学报,1999, 4(10): 297-301
[22] 王家隆,郭成安,一种改进的图像模板细化算法.中国图象图形学报,2004.3, 9(3):297-301
[23] 梅园,孙怀江,夏德深.一种基于改进后模板的图像快速细化算法.中国图象图形学报, 2006,11(9):1306-1311
[24] N.K.Ratha,S.Chen,A.K.Jainl. Adaptive flow direction based feature extraction in fingerprit image. Pattern Recognition,1995,28(11):1657-1672
[25] 姜红超,张高伟.基于脊线跟踪的指纹细节特征提取.计算机工程,2007,33(8):185-186
[26] Miao D,Maltoni D.Direct gray-scale minutiae detection in fingerprint.IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(1):27-39
[27] Lin Hong. Automatic personal identification using fingerprints:[dissertation]. East Lansing, Michigan State University, 1998,80-81
[28] Jiang Xudong, Yau We Yun, SerWee. Minutiae extraction by adaptive tracing the gray level ridge of the fingerprint image. In: IEEE Sixth International Conference on Image Processing( IC IP’99) . Kobe, Japan, 1999, 2: 852-856
[29] Liu Jinxiang, Huang Zhongyang, Chan Kap Luk. Direct minutiae extraction from gray-level fingerprint image by relationship examination. In: IEEE Proceedings International Conference on Image Processing. V arcourer, British Columbia, Canada, 2000, 2: 427-430
[30] 杨小冬,宁新宝,谭台哲.基于纹线跟踪的指纹细节提取算法.计算机应用,2004, 24(3):75-78
[31] 王芙蓉,程鹏,邹璇.直接提取指纹特征算法的优化研究.中国图象图形学报,2004, 9(5):557-564.
[32] 赵应丁,戴仕明,刘金刚.基于灰度指纹图像的指纹特征提取算法研究.系统仿真学报,2006.2,18(2): 319-322
[33] Qinzhi Zhang, Kai Huang, Hong Yan. Fingerprint Classification Based on Extractionand Analysis of Singularities and Pseudoridges.In: ProceedingProceedings of the Pan-Sydney area workshop on Visual information processing, Sydney,2001, 83-87
[34] Xuejun Tan, Bir Bhanu, Yingqiang Lin.Fingerprint Classification Based on Learned Features,IEEE transctions on Systems, Man, and Cybernetics, Part C: Applications and Reviews 2005, 35(3):287-300
[35] Huvanandana S,Kim C,Hwang J.N.Reliable and Fast Fingerprint Identification for Security Applications.Image Processing,2000 (2):503?506
[36] A.Jain,A.Ross,Sali.Prabhakar.Fingerprint matching using minutiae and texture features.In:Proceedings of International Conference on Image Processing.East Lansing,2001 (10):282-285
[37] Bazen A.M,Verwaaijen G.T.B,Gerez S.H,et al.A Correlation-Based Fingerprint Verification System.Circuits Systems and Signal Processing,2000 (5):205?213
[38] 沈清,汤霖.模式识别导论.第二版.长沙:国防科技大学出版社,1991.1-290
[39] 王玮,李见为,张腾.指纹图像的预处理算法.计算机应用, 2004,24(5):72-75
[40] 刘灵丽.指纹图像预处理与特征提取:[湖南大学硕士学位论文].长沙:湖南大学计算机与通信学院,2005,18-33
[41] Ranade, Rosenfeld A.Point pattern matching by relation. Pattern Recognition, 1980, 12(4) :269-274
[42] Jiang, Xu-dong, Yau, Wei-Yun. Fingerprint minutiae matching based on the local and global structures. In: Proceedings of the 15th International Conference on Pattern Recognition. Los Alamitos, 2000,1042-1045
[43] 江杰,胡晓莉,李杰.一种新的指纹细节点匹配算法的研究.计算机应用, 2005, 25:114-115
[44] 侯少峰,彭少奇,王一丁.一种基于参考点方向的指纹极坐标匹配算法.计算机应用, 2006,25(10):20-22
[45] 孙家广.计算机图形学.第三版.北京:清华大学出版社,1998.169-170