COMPUTATIONAL ALGORITHMS FOR FINGERPRINT RECOGNITION Kluwer International Series on Biometrics Professor David D. Zhang Consulting editor Department of Computer Science Hong Kong Polytechnic University Hung Hom, Kowloon, Hong Kong email: [email protected] Additional information about this series can be obtained from our website: httpllwww.wkap.nl COMPUTATIONAL ALGORITHMS FOR FINGERPRINT RECOGNITION by Bir Bhanu Xuejun Tan University 0/ Calijornia at Riverside U.S.A. SPRINGER SCIENCE+BUSINESS MEDIA, LLC Library of Congress Cataloging-in-Publication COMPUTAT IONAL ALGORITHMS FOR FINGERPRINT RECOGNITION bv Bir Bhanu. Xueiun Tan ISBN 978-1-4613-5103-0 ISBN 978-1-4615-0491-7 (eBook) DOI 10.1007/978-1-4615-0491-7 Copyright © 2004 Springer Science+Business Media New York Originally published by Kluwer Academic Publishers in 2004 Softcover reprint of the hardcover 1 st edition 2004 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photo-copying, or microfilming, recording, otherwise, without the prior written permission of the publisher, with the exception of any material supplied specifically for the pUrPQse of being entered and executed on a computer system, for exclusi ve use by the purchaser of the work. Permissions for books published in the USA: [email protected] Permissions for books published in Europe: [email protected] Printed on acid-free paper. Contents LIST OF FIGURES IX LIST OF TABLES XV PREFACE XVII 1. INTRODUCTION 1 1.1 RESEARCH HISTORY 1 1.2 FINGERPRINT COLLECTION 6 1.3 FINGERPRINT FORMATION 6 1.4 FUNDAMENTAL CONCLUSIONS 8 1.5 FUNDAMENTAL RECOGNITION SYSTEMS 8 1.6 OUTLINE OF THE BOOK 11 2. LEARNED TEMPLATES FOR MINUTIAE EXTRACTION 13 2.1 INTRODUCTION 13 2.2 RELATED RESEARCH AND CONTRIBUTIONS 14 2.2.1 Related Research 14 2.2.2 Contributions 18 2.3 TECHNICAL ApPROACH 18 2.3.1 Offline Learning of Templates 19 2.3.2 Run Time Feature Extraction 24 vi Contents 2.4 EXPERIMENTS 26 2.4.1 Database 26 2.4.2 Learned Templates 27 2.4.3 Results 29 2.5 CONCLUSIONS 32 3. FINGERPRINT INDEXING 33 3.1 INTRODUCTION 33 3.2 RELATED RESEARCH AND CONTRIBUTIONS 35 3.2.1 Related Research 35 3.2.2 Contributions 37 3.3 TECHNICAL APPROACH 38 3.3.1 Indexing Components 39 3.3.2 Geometric Constraints 43 3.3.3 Indexing Score 44 3.3.4 Algorithms 44 3.3.5 Probability of False Indexing 46 3.4 EXPERIMENTS 47 3.4.1 Database 47 3.4.2 Performance Evaluation Measures for Indexing 48 3.4.3 Indexing Results 49 3.4.4 Effect of Geometric Constraints 52 3.4.5 Extrapolation of Indexing Performance 52 3.4.6 Comparison of Approaches 55 3.5 CONCLUSIONS 56 4. FINGERPRINT MATCHING BY GENETIC ALGORITHMS 59 4.1 INTRODUCTION 59 4.2 RELATED RESEARCH AND CONTRIBUTIONS 60 4.2.1 Related Research 60 4.2.2 Contributions 61 4.3 TECHNICAL APPROACH 62 4.3.1 Fingerprint Matching Problem 62 4.3.2 Selection of an Optimization Technique 62 4.3.3 Optimization Based on GA 63 4.3.4 GA Based Fingerprint Representation 66 4.4 EXPERIMENTS 71 4.4.1 Database 71 4.4.2 Estimation of Parameters for GA 72 4.4.3 Results 78 Contents Vll 4.4.4 Effectiveness of Selection and Crossover Operators 80 4.4.5 Computation Time 81 4.5 CONCLUSIONS 82 5. GENETIC PROGRAMMING FOR FINGERPRINT CLASSIFICATION 83 5.1 INTRODUCTION 83 5.2 RELATED RESEARCH AND CONTROBUTIONS 84 5.2.1 Related Research 84 5.2.2 Contributions 89 5.3 TECHNICAL APPROACH 90 5.3.1 Design Considerations 92 5.3.2 Reproduction, Crossover and Mutation 97 5.3.3 Steady-State and Generational Genetic Programming 100 5.4 EXPERIMENTS 103 5.4.1 Database 103 5.4.2 Results 104 5.5 CONCLUSIONS 116 6. CLASSIFICATION AND INDEXING APPROACHES FOR IDENTIFICATION 117 6.1 INTRODUCTION 117 6.2 RELATED RESEARCH AND CONTRIBUTIONS 118 6.2.1 Related Research 118 6.2.2 Contributions 123 6.3 TECHNICAL APPROACH 123 6.3.1 Indexing 123 6.3.2 Verification 125 6.4 EXPERIMENTS 127 6.4.1 Classification results 128 6.4.2 Indexing Results 130 6.4.3 Identification Results 130 6.5 CONCLUSIONS 133 7. FUNDAMENTAL PERFORMANCE ANALYSIS - PREDICTION AND VALIDATION 135 7.1 INTRODUCTION 135 7.2 RELATED RESEARCH AND CONTRIBUTIONS 138 7.2.1 Related Research 138 7.2.2 Contributions 142 viii Contents 7.3 TECHNICAL APPROACH 142 7.3.1 Two-Point Model 147 7.3.2 Three-Point Model 148 7.4 EXPERIMENTS 155 7.4.1 Database 155 7.4.2 Parameters 156 7.4.3 Estimation ofP3•M{M3= s I M = i} 158 7.4.4 Results 160 7.4.5 Real Data 166 7.4.6 Error Rates between Fingerprint and Iris 167 7.5 CONCLUSIONS 168 8. SUMMARY AND FUTURE WORK 169 8.1 SUMMARY 169 8.2 FUTURE WORK 172 REFERENCES 175 INDEX 189 List of Figures Chapter 1 Figure 1.1. A piece of ancient Chinese document which used fingerprint as identity (courtesy of [131]). 2 Figure 1.2. Fingerprint science pioneers: (a) Sir Francis Galton and (b) Sir Edward Henry (courtesy of[131]). 3 Figure 1.3. Examples of fingerprints from each class of Henry System for fingerprint classification: (a) Right Loop (R); (b) Left Loop (L); (c) Whorl (W); (d) Arch (A) and (e) Tented Arch (T). 5 Figure 1.4. AFS8500 fingerprint sensor manufactured by AuthenTec Inc. (courtesy of [126]). 7 Figure 1.5. Examples of minutiae: endpoint and bifurcation. Singular points, core and delta, are also shown in this figure. 7 Figure 1.6. (a) Fingerprint authentication system (AFAS) and (b) Fingerprint identification system (AFIS). 9 Figure 1.7. General block diagram of a fingerprint recognition system. 11 Chapter 2 Figure 2.1. Block diagram for minutiae-based feature extraction. 14 Figure 2.2. Block diagram of our approach for minutiae extraction. 19 Figure 2.3. Illustration of an ideal endpoint template T. 20 Figure 2.4. Sample fingerprints in NIST-4. 27