.. .I , .. . i .3 . :4 ._ . . . . . . . . .h£w.§;fi.cum. 3. .1 3...? .. . . .. .. , . . . 4. 1.. . 5... .._ mi: LIBRARY Michigan State University 3 I: This is to certify that the dissertation entitled MULTIBIOMETRIC SYSTEMS: FUSION STRATEGIES AND TEMPLATE SECURITY presented by KARTHIK NANDAKUMAR has been accepted towards fulfillment of the requirements for the Ph. D. degree in COMPUTER SCIENCE AND ENGINEERING “My Major Professor’s Signature Feb LI, 4003 Date MSU is an affirmative-action, equal-opportunity employer PLACE IN RETURN BOX to remove this checkout from your record. To AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 5/08 K /Pro;lAcc&Pres/ClRC/DateDue indd MULTIBIOMETRIC SYSTEMS: FUSION STRATEGIES AND TEMPLATE SECURITY By Karthik Nandakumar A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Computer Science and Engineering 2008 ABSTRACT MULTIBIOMETRIC SYSTEMS: FUSION STRATEGIES AND TEMPLATE SECURITY By Karthik Nandakumar Multibiometric systems, which consolidate information from multiple biometric sources, are gaining popularity because they are able to overcome limitations such as non-universality, noisy sensor data, large intra—user variations and susceptibility to Spoof attacks that are commonly encountered in unibiometric systems. In this thesis, we address two critical issues in the design of a multibiometric system, namely, fusion methodology and template security. First, we propose a fusion methodology based on the Neyman-Pear‘son theorem for combination of match scores provided by multiple biometric matchers. The likeli- hood mtz'o (LR) test used in the Neyman—Pearson theorem directly maximizes the genuine accept rate (GAR) at any desired false accept rate (FAR). The densities of genuine and impostor match scores needed for the LR test are estimated using finite Gaussian mixture models. We also extend the likelihood ratio based fusion scheme to incorporate the quality of the biometric samples. Further, we also Show that the LR framework can be used for designing sequential multibiometric systems by con- structing a binary decision tree classifier based on the marginal likelihood ratios of the individual matchers. The LR framework achieves consistently high recognition rates across three different multibiometric databases without the need for any parameter tuning. For instance, on the WVU-l\Iultimodal database, the GAR of the LR fusion rule is 85.3% at a FAR of 0.001%, which is significantly higher than the corresponding GAR of 66.7% provided by the best single modality (iris). The use of image quality information further improves the GAR to 90% at a FAR of 0.001%. Next, we Show that the proposed likelihood ratio based fusion framework is also applicable to a multibiometric system operating in the identification mode. We further investigate rank level fusion strategies and propose a hybrid scheme that utilizes both ranks and scores to perform fusion in the identification scenario. While fusion of multiple biometric sources significantly improves the recognition accuracy, it requires storage of multiple templates for the same user corresponding to the individual biometric sources. Template security is an important issue in biomet- ric systems because unlike passwords, stolen biometric templates cannot be revoked. Hence, we propose a scheme for securing multibiometric templates as a single entity using the fuzzy vault framework. We have developed fully automatic implementa- tions of a fingerprint-based fuzzy vault that secures minutiae templates and an iris cryptosystem that secures iriscode templates. We also demonstrate that a multibio- metric vault achieves better recognition performance and higher security compared to a unibiometric vault. For example, our multibiometric vault implementation based on fingerprint and iris achieves a GAR of 98.2% at a FAR of less than 0.01% and provides approximately 49 bits of security. The corresponding GAR values of the individual iris and fingerprint vaults are 88% and 78.8%, respectively. When the iris and fingerprint vaults are stored separately, the security of the system is only 41 bits. © Copyright by KARTHIK NANDAKUMAR 2008 To My Grandfather and Grandmother ACKNOWLEDGMENTS First and foremost, I would like to thank my grandfather Shri. P.S. Venkatachari and my grandmother Smt. P.S. Vanaja for their prayers and blessings. Without their support and encouragement at crucial periods of my life, it would not have been possible for me to pursue graduate studies and aim for a career in research. Their hard work and positive attitude even at the age of 80, is my main source of inspiration. I am proud to dedicate this thesis and all the good things in my life to them. I would like to express my Sincere gratitude to my advisor Dr. Anil K. Jain for providing me the opportunity to work in the exciting and challenging areas of pattern recognition and biometrics. His constant motivation, support and infectious enthusiasm have guided me towards the successful completion of my graduate studies. My interactions with him have been of immense help in defining my research goals and in identifying ways to achieve them. His encouraging words have often pushed me to put in my best possible efforts. I would also like to thank him for his guidance and help in identifying a suitable career path for me. Above all, the complete belief that he has entrusted upon me has instilled a great sense of confidence and purpose in my mind, which I am sure will stand me in good stead throughout my career. I also thank my guidance committee members Dr. George Stockman, Dr. Bill Punch, Dr. Sarat Dass and Dr. Arun ROSS for their valuable comments and sugges- tions that have greatly enhanced and shaped this thesis. In particular, I appreciate vi Dr. Stockman for the time and effort that he has spent in guiding my research, assist- ing me in administrative tasks and moulding me professionally. Special thanks also goes to Dr. Arun Ross and Dr. Sarat Dass for the enlightening research discussions that have shown me the right path on many occasions. I would also like to thank Dr. Sharath Pankanti and Dr. Salil Prabhakar for their assistance in the template security project. The research in this thesis was supported by grants from the National Science Foundation (NSF-ITR grant number CNS-0325640), the Army Research Office (ARO grant number W911NF-06—1—0418) and the Center for Identification Technology Re- search at West Virginia University. I would like to thank the NSF, ARC and CITeR for their generous financial support. I would like to thank all the faculty members in the Department of Computer Science and Engineering and the Department of Statistics and Probability at Michigan State University. In particular, I would like to express my thanks to Dr. Abdol Esfahanian and Dr. Eric Torng for their help as CSE graduate directors, Dr. Li Xiao for her encouragement and support, Dr. Jon Sticklen for his support during my tenure as a teaching assistant and his special interest in my research work and career, Dr. Herman Hughes and Dr. Matt Mutka for their guidance during my first year at MSU and Dr. James Stapleton for his encouragement and help as the graduate director of the Statistics department. I would also like to express my appreciation and gratitude to Linda Moore, Debbie Kruch, Cathy Davison, Starr Portice, Norma Teague, Kim Thompson, Cathy Sparks, Sue Watson and Adam Pitcher for their administrative assistance and support. I would also like to express my thanks to vii Mr. Dale Setlak, Dr. Kuntal Sengupta, Mr. Dick Jones and Dr. Mike Boshra at Authentec, Inc. and Dr. Srimat T. Chakradhar, Dr. Anand Raghunathan and Dr. Srivaths Ravi at NBC Labs America, Inc. for the internship opportunities. A Special word of appreciation for Dr. Chandrasekara Rao Komma for providing me with accommodation and transportation during my internship at Authentec. The PRIP lab is an excellent place to work in and it is one place where you can always find good company, no matter what time of the day it is. My interactions with members of this lab has certainly made me a better professional. Special thanks goes to Dr. Umut Uludag for helping me acclimatize to the lab during the initial months. I would also like to thank Dr. Xiaoguang Lu and Unsang Park for their assistance in the soft biometrics project, Yi Chen for sharing the joys and frustrations in research, Dr. Hong Chen for all his help during the NEC internship and Dr. Martin Law who was always ready to help in case of any technical problems. Finally, I would like to express my gratitUde to other contemporary Prippies Dr. Anoop Namboodiri, Dr. Dirk Colbry, Yongfang Zhu, Meltem Demirkus, Steve Krawczyk, Jung-Bun Lee, Pavan Kumar Mallapragada, Abhishek Nagar, Leonardo Max Batista Claudino, and Miguel Figueroa-Villanue for creating and sustaining a lively and enjoyable research environment during my five years of stay in the windowless PRIP lab. As a person who had never left the comforts of my home and family until I landed at Michigan State University, 2, 000 days of pleasant and unforgettable life in Michigan would not have been possible without the company of many great friends. First of all, I would like to sincerely thank my roommates Arun Prabakaran, Mahesh Arumugam, Srikanth Sridhar and Sriram Raghunath for their deep camaraderie, emo- viii tional support and logistical help. In particular, the idea of doing a PhD with Dr. Jain would have never crossed by mind but for Mahesh, who had constantly extolled the virtues of this path and convinced me to follow it. I owe this thesis to him for all his guidance and help. I am also grateful to Sunil Unikkat, Shankarshna Mad- havan, Narasimhan Swaminathan, Aravindhan Ravisekar, Prasanna Balasundaram, Loganathan Anjaneyulu, Raja Ganjikunta, Bruhadeswar Bezawada, Madhusudhan Srinivasan, Sudharson Sundararajan, Senthil Kumar Venkatesan and Amit Gore for all the fun-time we had together in Michigan. I am also very grateful to my friends Mahadevan Balakrishnan, Jayaram Venkatesan, Hariharan Rajasekaran, Balasubra— manian Rathakrishnan and Balaji Arcot Srinivasan for their long conversations over phone that helped me feel at home. Finally, I would like to thank my parents who have been the pillars of strength in all my endeavors. I am always deeply indebted to them for all that they have given me. I also thank all the other members of my family including my brother and two sisters for their love, affection and timely help. ix TABLE OF CONTENTS LIST OF TABLES xiii LIST OF FIGURES xv 1 Introduction 1 1.1 Biometric Systems .............................. 2 1.2 Biometric Functionalities ........................... 6 1.3 Performance of a Biometric System ..................... 9 1.4 Challenges in Biometrics ........................... 16 1.4.1 Accuracy .................................. 16 1.4.2 Scalability .................................. 21 1.4.3 Security and Privacy ............................ 22 1.5 Summary ................................... 24 1.6 Thesis contributions ............................. 26 2 Multibiometric Systems 28 2.1 Design Issues in Multibiometrics ....................... 32 2.2 Sources of Multiple Evidence ........................ 33 2.3 Acquisition and Processing Sequence .................... 35 2.4 Levels of Fusion ................................ 38 2.4.1 Pbsion Prior to Matching ......................... 39 2.4.2 Fusion After Matching ........................... 43 2.5 Challenges in Multibiometric System Design ................ 46 2.6 Summary .................................. 49 3 Multibiometric Verification 55 3.1 Likelihood Ratio Test ............................. 58 3.2 Estimation of Match Score Densities .................... 60 3.2.1 Kernel Density Estimation ......................... 63 3.2.2 GMM-based Density Estimation ..................... 73 3.3 Incorporating Image Quality in Fusion ................... 75 3.3.1 Pairwise Fingerprint Quality ........................ 80 3.3.2 Pairwise Iris Quality ............................ 82 3.4 Likelihood Ratio Based Fusion Rules .................... 83 3.5 Sequential Fusion Using Likelihood Ratio Framework ........... 85 3.6 Experimental Results ............................. 87 3.6.1 Evaluation Procedure ........................... 88 3.6.2 Performance of Likelihood Ratio Based Parallel Fusion ......... 89 3.6.3 Comparison With Other Score Fusion Techniques ............ 90 3.6.4 Comparison of Product and Complete Likelihood Ratio Fusion ..... 97 3.6.5 Performance of Quality-based Fusion ................... 102 3.6.6 Performance of Likelihood Ratio Based Sequential Fusion ....... 102 3.7 Summary ................................... 106 4 Multibiometric Identification 110 4.1 Score Level Fusion .............................. 111 4.2 Rank Level Fusion .............................. 115 4.3 Experimental Results ............................. 118 4.4 Summary ................................... 123 5 Multibiometric Template Security 124 5.1 Review of Template Protection Schemes .................. 126 5.1.1 Feature Transformation .......................... 127 5.1.2 Biometric Cryptosystems ......................... 129 5.2 Fuzzy Vault .................................. 134 5.2.1 Fuzzy Vault Implementation ........................ 137 5.3 Proposed Fingerprint-based Fuzzy Vault .................. 139 5.3.1 Vault Encoding ............................... 141 5.3.2 Vault Decoding ............................... 144 5.3.3 Alignment based on High Curvature Points ............... 148 5.4 Proposed Iris Cryptosystem ......................... 156 5.4.1 Helper Data Extraction .......................... 158 5.4.2 Authentication ............................... 161 5.5 Multibiometric Fuzzy Vault ......................... 163 5.6 Experimental Results ............................. 166 5.6.1 Fingerprint-based Vault .......................... 166 5.6.2 Iris Cryptosystem .............................. 176 5.6.3 Multibiometric Vault ............................ 179 5.7 Security Analysis ............................... 181 5.7.1 Fingerprint-based Vault .......................... 182 5.7.2 Iris Cryptosystem .............................. 187 5.7.3 Multimodal Vault .............................. 188 5.8 Summary ................................... 191 6 Conclusions and thure Research 193 6.1 Conclusions .................................. 193 6.2 Future Research Directions .......................... 195 APPENDICES 198 A Databases ................................... 199 A1 Multibiometric Databases ......................... 199 A2 Fingerprint Databases ........................... 201 A3 CASIA Iris Database ............................ 202 xi B Algorithms .................................. 203 B.1 Determining Discrete Components in a Score Distribution ....... 203 B2 Juels-Sudan Vault Encoding ........................ 206 B3 Juels-Sudan Vault Decoding ........................ 207 B4 Alignment using ICP ............................ 208 BIBLIOGRAPHY 209 xii 1.1 2.1 2.2 2.3 2.4 3.1 5.1 5.2 5.3 5.4 LIST OF TABLES False reject and false accept rates associated with state-of-the-art finger- print, face, voice and iris verification systems. Note that the accuracy estimate of a biometric system depends on a number of test conditions. Examples of multi-sensor systems ....................... Examples of multi-algorithm systems ..................... Examples of multi-sample and multi—instance systems. .......... Examples of multimodal systems. ...................... Performance improvement achieved due to likelihood ratio based fusion. The GAR values in the table correspond to 0.01% FAR. ....... Summary of different template protection schemes. Here, T represents the biometric template, Q represents the query and K is the key used to protect the template. In salting and non-invertible feature trans— form, T represents the transformation function and M represents the matcher that operates in the transformed domain. In biometric cryp— tosystems, .7: is the helper data extraction scheme and M is the error correction scheme that allows reconstruction of the key K. ...... Parameters used for fuzzy vault implementation ............... Performance of the proposed fingerprint-based fuzzy vault implementation on FVC2002-DB2 database. Here, n denotes the degree of the encoding polynomial. The maximum key size that can be secured is 16n bits. The Failure to Capture Rate (FTCR), Genuine Accept Rate (GAR) and False Accept Rate (FAR) are expressed as percentages ....... Performance of the proposed fingerprint-based fuzzy vault implementation on MSU-DBI database. The Failure to Capture Rate (F TCR), Genuine Accept Rate (GAR) and False Accept Rate (FAR) are expressed as percentages. ................................ xiii 21 51 52 53 54 90 133 167 171 171 5.5 5.6 5.7 Performance of the multifinger (right and left index fingers) fuzzy vault on the MSU-DBI fingerprint database. The Failure to Capture Rate (FTCR), Genuine Accept Rate (GAR) and False Accept Rate (FAR) are expressed as percentages and the key size is expressed in bits. Performance of the multimodal (right index finger and iris) fuzzy vault on the virtual multimodal database derived from the MSU-DB1 fingerprint and CASIA iris databases. The Failure to Capture Rate (FTCR), Gen- uine Accept Rate (GAR) and False Accept Rate (FAR) are expressed as percentage and the key Size is expressed in bits ............ Security of the proposed fuzzy vault implementations. Here, the security is measured in terms of HOO(T IV), which represents the average min- entropy of the biometric template T given the vault V. The parameters t, r and n represent the total number of points in the vault (genuine and chaff), number of genuine points in the vault and the degree of the polynomial used in the vault, respectively. ............... Summary of multibiometric databases. Note that the NIST-Multimodal, NIST-Fingerprint and NIST-Face databases are different partitions of the NIST Biometric Score Set Release-1. ................ Summary of fingerprint databases used in the evaluation of fuzzy vault. . xiv 180 181 189 203 LIST OF FIGURES 1.1 Examples of body traits that can be used for biometric recognition. Anatomical traits include face, fingerprint, iris, palmprint, hand ge- ometry and ear shape, while gait, signature and keystroke dynamics are some of the behavioral characteristics. Voice can be considered either as an anatomical or as a behavioral characteristic. ....... 5 1.2 Enrollment and recognition stages in a biometric system. Here, T repre- sents the biometric sample obtained during enrollment, Q is the query biometric sample obtained during recognition, X I and X Q are the tem- plate and query feature sets, respectively, S represents the match score and N is the number of users enrolled in the database. ........ 8 1.3 Illustration of biometric intra—class variability. Two different impressions of the same finger obtained on different days are shown with minu- tia points marked on them. Due to differences in finger placement and distortion introduced by finger pressure variations, the number and location of minutiae in the two images are different (33 and 26 in the left and right images, respectively). The number of correspond- ing/ matching minutiae in the two images is only 16 and some of these correspondences have been indicated in the figure ............ 11 1.4 Performance of a biometric system operating in the verification mode. (a) The genuine and impostor match score densities corresponding to the Face-G matcher in the NIST BSSRl database. The threshold, 77, determines the FAR and GAR of the system. (b) Receiver operating characteristic (ROC) curve for the Face-G matcher which plots the GAR against FAR on a semi-logarithmic scale .............. 15 1.5 Cumulative match characteristic (CMC) curve for the Face-G matcher in the NIST BSSRl database which plots the rank-m identification rate for various values of m. In this example, the rank-1 identification rate is a: 78% which means that for z 78% of the queries, the true identity of the query user is selected as the best matching identity. ...... 17 1.6 Examples of noisy biometric data; (a) A noisy fingerprint image due to smearing, residual deposits, etc.; (b) A blurred iris image due to loss of focus. .................................. 18 XV 1.7 2.1 2.2 2.3 2.4 2.5 2.6 3.1 Non-universality of a biometric trait. This figure shows three impressions of a user’s finger in which the ridge details are worn-out. ....... A hypothetical mobile banking application where the user has the flexi- bility to choose all or a subset of available biometric traits (e.g., face, voice and fingerprint) for authentication depending on his convenience. Research is under way to perform iris recognition based on images cap- tured using the camera on the mobile phone [100] ............ Various sources of information that can be fused in a multibiometric sys- tem. In four of the five scenarios (multiple sensors, representations, instances and samples), multiple sources of information are derived from the same biometric trait. In the fifth scenario, information is derived from different biometric traits and such systems are known as multimodal biometric systems ....................... Acquisition and processing architecture of a multibiometric system; (a) Serial (Cascade or Sequential) and (b) Parallel. ............ The amount of information available for fusion decreases progressively after each layer of processing in a biometric system. The raw data represents the richest source of information, while the final decision (in a verification scenario) contains just a single bit of information. However, the raw data is corrupted by noise and may have large intra- class variability, which is expected to be reduced in the subsequent modules of the system. (Reproduced from [169]) ............ Fusion can be accomplished at various levels in a biometric system. Most multibiometric systems fuse information at the match score level or the decision level. FE: feature extraction module; MM: matching module; DM: decision-making module; FM: fusion module ............ Flow of information in a match score level fusion scheme. In this example, the match scores have been combined using the sum of scores fusion rule after min-max normalization of each matcher’s output. Note that the match scores generated by the face and fingerprint matchers are simi- larity measures. The range of match scores is assumed to be [-—I, +1] and [0, 100] for the face and fingerprint matchers, respectively. Non-homogeneity in the match scores provided by the two face matchers in the NIST-Face database. Note that about 0.2% of the scores output by matcher 1 are discrete scores with value -1, which are not shown in this plot. ................................. xvi 18 31 34 36 40 41 45 3.2 3.3 3.4 3.5 3.6 3.7 3.8 Histograms of match scores and the corresponding Gaussian density es- timates for the Face-G matcher in the NIST BSSRl database. (a) Genuine and (b) Impostor. Note that the Gaussian density does not account well for the tail in the genuine score distribution and the mul- tiple modes in the impostor score distribution .............. Histograms of match scores and the corresponding generalized density esti- mates for MSU-Multimodal database. (a) and (b) Genuine and impos- tor match scores for face modality. (c) and (d) Genuine and impostor match scores for fingerprint modality. (e) and (f) Genuine and impos- tor match scores for hand geometry modality. The solid line above the histogram bins is the density estimated using the kernel density 62 estimator, and the Spikes in (d) correspond to the discrete components. 66 Comparison of continuous and generalized density estimates for impos- tor match scores provided by the first face matcher in the NIST-Face database. (a) Continuous density estimates in the entire score range [—1, 1] and only in the range [0.4, 0.7]. (b) Generalized density esti- mates (T = 0.002) in the entire score range {—1, 1] and only in the range [0.4, 0.7]. .............................. Joint density of the genuine match scores output by the two matchers in the NIST-Face database estimated using (a) product of marginal densities and (b) copula functions. The density estimate in (b) captures the correlation between the matchers ................... Density estimation based on Gaussian mixture models for the genuine scores in the NIST-Face database. (a) Scatter plot of the genuine scores along with the fitted mixture components and (b) density estimates of the genuine scores. In this case, 12 mixture components were found. . Density estimation based on Gaussian mixture models for the impostor scores in the NIST-Face database. (a) Scatter plot of the impostor scores along with the fitted mixture components and (b) density esti- mates of the impostor scores. In this example, 19 mixture components were found. ................................ Minutiae extraction results for fingerprint images of varying quality. (a) A good quality fingerprint image. (b) A noisy fingerprint image. (c) Minutia points detected in the good quality fingerprint image by an au- tomatic minutiae extraction algorithm. (d) Minutia points detected in the noisy fingerprint image. The circles represent true minutia points while the squares represent false (spurious) minutiae. While no spuri- ous minutia is detected in the good quality fingerprint image, several false minutia points are detected when the fingerprint image quality is poor ..................................... xvii 68 72 76 77 79 3.9 3.10 3.11 3.12 3.13 3.15 3.16 3.17 3.18 3.19 Variation of match score with quality for fingerprint modality in the WVU- Multimodal database. W . observe that the genuine and impostor match scores are well-separated only for good quality (with quality index > 0.5) samples. . ......................... Performance of complete likelihood ratio based fusion rule and linear S\/ M- based fusion on the NIST-Multimodal database ............. Performance of complete likelihood ratio based fusion rule and SVM—based fusion on the NIST-Fingerprint database. A radial basis function ker— nel with 7 = 0.005 was used for SV M fusion ................ Performance of complete likelihood ratio based fusion rule and SVM-based fusion on the NIST-Face database. A radial basis function kernel with ”y = 0.1 was used for SVM fusion. .......... Performance of complete likelihood ratio based fusion rule and linear SV M- based fusion on the XM2VTS—Benchmark database Although there are 8 different matchers in the XM2VTS-Benchmark database, only the ROC curves of the best face matcher (DCTb-GMM) and the best. speech matcher (LFCG-GMM) are Shown for clarity. ......... Performance of complete likelihood ratio based fusion rule and sum of scores fusion rule with min-max normalization on (a) NIST- Multimodal database and (b) XM2V'1'S-Benchmark database. In (b), IT-MM denotes that an inverse tangent function is applied only to the match scores of the MLP classifiers prior to normalizmg all the match scores using min-max normalization. ................. Distribution of genuine and impostor match scores in the XMQVTS- Benchmark database for (a) MLP classifier and (b) GMM classifier. .. Performance of product and complete likelihood ratio based fusion rules for the two face matchers in the NIST-Face database ......... Performance of product and complete likelihood ratio based fusion rules for the LFCC~GMM and SSC-GMM speech matchers in the XMQVTS database. .............................. _ . Performance of product fusion and quality-based product fusion rules on the WVU-Multimodal database ...................... A typical sequential fusion rule (decision tree) obtained using the NIST— Fingerprint database. Here, L1 and L2 represent the marginal log- likelihood ratios for the left index finger and right index finger. respec- tively. ................................... A 81 91 92 93 94 103 104 3.20 A typical sequential fusion rule obtained using the NIST-Multimodal 4.1 4.2 4.3 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 database. Here, L1, L2 and L3 represent the marginal log-likelihood ratios for the left index finger, right index finger and face modalities, respectively. ............. g .................. Cumulative Match Characteristic (CMC) curve of highest rank fusion and the hybrid score-rank fusion rules on the NIST-Multimodal database (K = 4, N = 517) .............................. Cumulative Match Characteristic (CMC) curve of highest rank fusion and the hybrid score-rank fusion rules on the NIST-Fingerprint. database (K = 2,N = 6,000). ........................... Cumulative Match Characteristic (CMC) curve of highest rank fusion and the hybrid score-rank fusion rules on the NIST—Face database (K 2 2, N = 3, 000) ............................ Categorization of template. protection schemes. Authentication mechanism when the biometric template is protected using a feature transformation approach. ................... Authentication mechanism when the biometric template is secured using a key generation biometric cryptosystem. Authentication in a key- binding biometric cryptosystem is similar except that the helper data is a function of both the template and the key K, i.e., H = .F(T; K). Schematic diagram of the fuzzy vault scheme proposed by J uels and Sudan [102] based on fingerprint minutiae. (a) Vault encoding and (b) vault decoding. ................................. Proposed implementation of vault encoding. ............... Proposed implementation of vault decoding. (a) Block diagram of the complete decoding process and (b) details of the filter used to eliminate the chaff points ............................... Algorithm for extraction of high curvature points .......... Determination of maximum curvature points. (a) Curvature estimation at point 6 j and (b) trace of curvature for a sample flow curve along with the local maximum ........................... xix 107 119 120 122 127 128 130 136 142 14 151 1 0 3 5.9 An example of successful minutiae alignment based on high curvature points and ICP algorithm. (a) Template image with minutiae and high curvature points, (b) query image with minutiae and high curva- ture points (c) template and overlaid query minutiae prior to alignment and ((1) template and overlaid query minutiae after alignment. In this figure, the template minutiae are represented as squares (tails indicate the minutia direction) and the query minutiae are represented as cir- cles. The template and query high curvature points are represented as asterisks and diamonds, respectively. .................. 157 5.10 Schematic diagram of the iris cryptosystem based on iriscode features. (a) Enrollment or helper data extraction and (b) authentication or key recovery ................................... 159 5.11 Schematic diagram of a multimodal (fingerprint and iris) fuzzy vault. . . 165 5.12 An example of successful operation of the fuzzy vault. (a) Template fin- gerprint image with minutiae, (b) selected template minutiae and high curvature points, (c) vault in which the selected template minutiae are hidden among chaff points (for clarity, minutiae directions are not shown), (d) query fingerprint image with minutiae, (e) selected query minutiae and high curvature points, (f) ICP alignment of template and query high curvature points and coarse filtering of chaff points, and (g) unlocking set obtained by applying a minutiae matcher that eliminates almost all the chaff points. The two points shown in filled squares in (g) are the only chaff points that remain in the unlocking set. Here, figures (a)-(c) represent vault encoding and (d)-(g) represent vault decoding. .............................. 169 5.13 Failure due to incorrect extraction of high curvature points. (a) Tem- plate fingerprint image with minutiae and high curvature points, (b) query fingerprint image with minutiae and high curvature points, and (c) ICP alignment of template and query high curvature points along with aligned template and query minutiae. High curvature points were incorrectly detected in the template because the high curvature region is near the boundary ............................ 174 5.14 Failure due to partial overlap. (a) Template fingerprint image with minu- tiae and high curvature points, (b) query fingerprint image with minu- tiae and high curvature points, and (c) ICP alignment of template and query high curvature points along with aligned template and query minutiae. Though the alignment is accurate, there are only few match- ing minutiae in these two images. .................... 175 XX 5.15 An example of false accept when n = 8. (a) Template fingerprint image with minutiae and high curvature points, (b) query fingerprint image with minutiae and high curvature points, and (c) ICP alignment of template and query high curvature points along with aligned template and query minutiae. In (c), we observe that there are 9 matching minutiae between the query and the template (represented as dotted ellipses). .................................. 177 Images in this dissertation are presented in color. Chapter 1 Introduction Personal identity refers to a set of attributes (e.g., name, social security number, etc.) that are associated with a person. Identity management is the process of creating, maintaining and destroying identities of individuals in a population. A reliable iden- tity management system is urgently needed in order to combat the epidemic growth in identity theft and to meet the increased security requirements in a variety of appli- cations ranging from international border crossing to accessing personal information. Establishing (determining or verifying) the identity of a person is called person recog- nition or authentication and it is a critical task in any identity management system. The three basic ways to establish the identity of a person are “something you know” (e.g., password, personal identification number), “something you carry” (e.g., physical key, ID card) and “something you are” (e.g., face, voice) [44]. Surrogate representations of identity such as passwords and ID cards can be eas- ily misplaced, Shared or stolen. Passwords can also be easily guessed using social engineering [136] and dictionary attacks [110]. Hence, the effective security provided 1 by passwords is significantly less than the expected security. Studies by the National Institute of Standards and Technology (N IST) [18] have estimated that on average, an 8-character ASCII (7 bits/ character) password effectively provides only 18 bits of entropy, which is much less than the expected 56 bits of security. Moreover, passwords and ID cards cannot provide vital authentication functions like non-repudiation and detecting multiple enrollments. For example, users can easily deny using a service by claiming that their password has been stolen or guessed. Individuals can also conceal their true identity by presenting forged or duplicate identification documents. Therefore, it is becoming increasingly apparent that knowledge—based and token-based mechanisms alone are not sufficient for reliable identity determination and stronger authentication schemes based on “something you are” , namely biometrics, are needed. 1. 1 Biometric Systems Biometric authentication, or simply biometrics, offers a natural and reliable solution to the problem of identity determination by establishing the identity of a person based on “who he is”, rather than “what he knows” or “what he carries” [84]. Biometric systems automatically determine or verify a person’s identity based on his anatomical and behavioral characteristics such as fingerprint, face, iris, voice and gait. Biometric traits constitute a strong and permanent “link” between a person and his identity and these traits cannot be easily lost or forgotten or shared or forged. Since biometric systems require the user to be present at the time of authentication, it can also deter users from making false repudiation claims. Moreover, only biometrics can provide 2 negative identification functionality where the goal is to establish whether a certain individual is indeed enrolled in the system although the individual might deny it. Due to these reasons, biometric systems are being increasingly adopted in a number of government and civilian applications either as a replacement for or to complement existing knowledge and token-based mechanisms. Some of the large scale biometric systems include the Integrated Automated Fingerprint Identification System (IAF IS) of the FBI [150], the US-VISIT IDENT program [149], the Schiphol Privium scheme at Amsterdam’s Schiphol airport [176] and the finger scanning system at Disney World, Orlando [77]. A number of anatomical and behavioral body traits can be used for biometric recognition (see Figure 1.1). Examples of anatomical traits include face, fingerprint, iris, palmprint, hand geometry and ear shape. Gait, signature and keystroke dynamics are some of the behavioral characteristics that can be used for person authentication. Voice can be considered either as an anatomical or as a behavioral trait because certain characteristics of a person’s voice such as pitch, bass/ tenor and nasality are due to physical factors like vocal tract shape, and other characteristics such as word or phoneme pronunciation (e.g., dialect), use of characteristic words or phrases and conversational styles are mostly learned. Ancillary characteristics such as gender, ethnicity, age, eye color, skin color, scars and tatoos also provide some information about the identity of a person. However, since these ancillary attributes do not pro- vide sufficient evidence to precisely determine the identity, they are usually referred to as soft biometric traits [89]. Each biometric trait has its advantages and limita- tions, and no single trait is expected to effectively meet all the requirements such as 3 accuracy, practicality and cost imposed by all applications [99]. Therefore, there is no universally best biometric trait and the choice of biometric depends on the nature and requirements of the application. A typical biometric system consists of four main components, namely, sensor, feature extractor, matcher and decision modules. A sensor is used to acquire the biometric data from an individual. A quality estimation algorithm is sometimes used to ascertain whether the acquired biometric data is good enough to be processed by the subsequent components. When the data is not of sufficiently high quality, it is usually re—acquired from the user. The feature extractor gleans only the salient information from the acquired biometric sample to form a new representation of the biometric trait, called the feature set. Ideally, the feature set should be unique for each person (extremely small inter-user similarity) and also invariant with respect to changes in the different samples of the same biometric trait collected from the same person (extremely small intra-user variability). The feature set obtained during enrollment is stored in the system database as a template. During authentication, the feature set extracted from the biometric sample (known as query or input or probe) is compared to the template by the matcher, which determines the degree of similarity (dissimilarity) between the two feature sets. The decision module decides on the identity of the user based on the degree of Similarity between the template and the query. Face Voice Signature Gait Palmprint Figure 1.1: Examples of body traits that can be used for biometric recognition. Anatomical traits include face. fingerprint, iris, palmprint, hand geometry and ear shape, While gait, signature and keystroke dynamics are some of the behavioral char- acteristics. Voice can be considered either as an anatomical or as a. behavioral char- acteristic. 1.2 Biometric Functionalities The functionalities provided by a biometric system can be categorized1 as verification and identification. Figure 1.2 Shows the enrollment and authentication stages of a bio- metric system operating in the verification and identification modes. In verification, the user claims an identity and the system verifies whether the claim is genuine, i.e., the system answers the question “Are you who you say you are?”. In this scenario, the query is compared only to the template corresponding to the claimed identity. If the user’s input and the template of the claimed identity have a high degree of similarity, then the claim is accepted as “genuine”. Otherwise, the claim is rejected and the user is considered an “impostor”. Formally, verification can be posed as the following two-category classification problem: given a claimed identity I and a query feature set XQ, we need to decide if (I,XQ) belongs to “genuine” or “impostor” class. Let XI be the stored template corresponding to identity I. Typically, XQ is compared with X I and a match score S, which measures the similarity between XQ and X I, is computed. The decision rule is given by genuine, if S 2 77, (I, XQ) E (1.1) impostor, if S < 17, where 77 is a pre—defined threshold. In this formulation, the match score S is assumed to measure the similarity between XQ and X I, i.e., a large score indicates a good match. It is also possible for the match score to be a dissimilarity or distance measure 1Throughout this dissertation, the terms recognition or authentication will be used interchange- ably when we do not wish to make a distinction between the verification and identification functionalities. (i.e., a large score indicates a poor match) and in this case, the inequalities in the decision rule shown in equation (1.1) should be reversed. Identification functionality can be classified into positive and negative identifica- tion. In positive identification, the user attempts to positively identify himself to the system without explicitly claiming an identity. A positive identification system answers the question “Are you someone who is known to the system?” by determin- ing the identity of the user from a known set of identities. In contrast, the user in a negative identification application is considered to be concealing his true identity from the system. Negative identification is also known as screening and the objec- tive of such systems is to find out “Are you who you say you are not?”. Screening is often used at airports to verify whether a passenger’s identity matches with any person on a “watch-list”. Screening can also be used to prevent the issue of multi- ple credential records (e.g., driver’s licence, passport) to the same person. Negative identification is also critical in applications such as welfare disbursement to prevent a person from claiming multiple benefits (i.e., double dipping) under different names. In both positive and negative identification, the user’s biometric input is compared with the templates of all the persons enrolled in the database and the system outputs either the identity of the person whose template has the highest degree of similarity with the user’s input or a decision indicating that the user presenting the input is not an enrolled user. Formally, the problem of identification can be stated as follows: given a query feature set XQ, we need to decide‘the identity I of the user, where I E {11,12, - -- ,IN,IN+1}. Here, [1,12, . -- ,IN correspond to the identities of the N 7 Enrollment ( User Identity, I . -iomein'c . Feature L System 86;:[- Sensor 'T' 7" EMCIOF Database Verification { Claimed Identity. I Genuine/lmpostor Identification User Identity Figure 1.2: Enrollment and recognition stages in a biometric system. Here, T rep- resents the biometric sample obtained during enrollment, Q is the query biometric sample obtained during recognition, X I and XQ are the template and query feature sets, respectively, S represents the match score and N is the number of users enrolled in the database. users enrolled in the system and I N +1 indicates the case where no suitable identity can be determined for the given query. If X1" is the stored template correspond- ing to identity In and Sn is the match (similarity) score between XQ and X [71’ for n = 1, 2, - - - ,N, the decision rule for identification is, Ino, if no = argm1ax Sn and S710 2 r7, XQ E (1.2) I N +1, otherwise, where 17 is a pre-defined threshold. In some practical biometric identification systems such as FBI-IAFIS, identification is semi-automated, i.e., the biometric system out- puts the identities of the top m matches (1 < m < N) and a human expert manually determines the identity (among the m selected identities) that best matches the given query. Note that the number of enrolled users in the database can be quite large. For example, there are more than 80 million subjects in the FBI-IAFIS system [150]. The presence of large number of identities in the database makes the identification task significantly more challenging than verification. 1.3 Performance of a Biometric System Samples of the same biometric trait of a user obtained over a period of time can differ dramatically. The variability observed in the biometric feature set of an individual is known as intra-user variations. For example, in the case of fingerprints, factors such as placement of finger on the sensor, applied finger pressure, skin condition and feature extraction errors lead to large intra-user variations [129]. Figure 1.3 shows 9 two impressions of the same finger obtained on different days. Note how these im- pressions differ with respect to translation, rotation and non-linear distortion. On the other hand, features extracted from biometric traits of different individuals can be quite similar. For example, some pairs of individuals can have nearly identical facial appearance due to genetic factors (e.g., father and son, identical twins, etc.). Appearance-based facial features will exhibit a large similarity for these pairs of in- dividuals and such a similarity is usually referred to as inter-user similarity. A biometric system can make two types of errors, namely, false non-match and false match. When the intra—user variation is large, two samples of the same biometric trait of an individual (mate samples) may not be recognized as a match and this leads to a false non-match error. A false match occurs when two samples from different individuals (non-mate samples) are incorrectly recognized as a match due to large inter-user Similarity. Therefore, the basic measures of the accuracy of a biometric system are False Non-Match Rate (FNMR) and False Match Rate (FMR). FNMR refers to the fraction of matches between two mate samples that are not recognized as a match and FMR is the proportion of matches between two non-mate samples that are incorrectly recognized as a match. A False Non-Match Rate of 5% indicates that on average, 5 in 100 genuine at- tempts do not succeed. A majority of the false non-match errors are usually due to incorrect interaction of the user with the biometric sensor and can be easily rectified by allowing the user to present his/ her biometric trait again. This is similar to the case where the user in a password—based authentication system makes a mistake while entering a password and is allowed to reenter the password. 10 ", fl; ’7be v“ ‘I \ . ' I“ . 9/” :1 , ,v Q tape“. at... I ”5‘ \\\\\\\ ? V0 3‘“); ‘/)\‘.‘§, 3 “ . ’ ' a: k‘ i - "9,,er \ «2.. ‘L ,1 at“ g. Figure 1.3: Illustration of biometric intra—class variability. Two different impres- sions of the same finger obtained on different days are shown with minutia points marked on them. Due to differences in finger placement and distortion introduced by finger pressure variations, the number and location of minutiae in the two images are different (33 and 26 in the left and right images, respectively). The number of corresponding/matching minutiae in the two images is only 16 and some of these correspondences have been indicated in the figure. 11 A False Match Rate of 001% indicates that on average, 1 in 10,000 impostor attempts are likely to succeed. However, it must be emphasized that the security of a biometric system operating at 0.01% FMR is not equivalent to the security provided by a 4—digit PIN due to three reasons. Firstly, the adversary has to guess input values in the biometric feature space, which is requires significantly more effort and domain knowledge (e.g., knowledge about the features used in a particular biometric system, the statistical distribution of the features, the format of the stored templates, etc.) than what is required for guessing a PIN. Secondly, even if the adversary guesses the feature values, he must circumvent a physical component in the biometric system (sensor, feature extractor, or communication channels) in order to input the guessed features. This circumvention can be made very difficult by securing the physical infrastructure of the biometric system through appropriate techniques such as liveness detection, secure code execution and cryptographic protocols. Finally, it should be noted that the effective security provided by a 4—digit PIN is typically much less than 1 success in 10, 000 impostor attempts, because most users tend to use numbers that are easy to remember (e.g., 1234, year of birth, etc.) and such PINS can be easily guessed by the adversary in a few attempts. Apart from false non-match and false match, two other types of failures are also possible in a practical biometric system. If an individual cannot interact correctly with the biometric user interface or if the biometric samples of the individual are of very poor quality, the sensor or feature extractor may not be able to process these individuals. Hence, they cannot be enrolled in the biometric system and the propor- tion of individuals who cannot be enrolled is referred to as Failure to Enroll Rate 12 (FTER). In some cases, a particular sample provided by the user during authentica- tion cannot be acquired or processed reliably. This error is called failure to capture and the fraction of authentication attempts in which the biometric sample cannot be captured is known as Failure to Capture Rate (FTCR). In the context of biometric verification, FNMR and FMR are also known as False Reject Rate (FRR) and False Accept Rate (FAR), respectively. A match score is termed as genuine or authentic score if it indicates the similarity between two mate samples. An impostor score measures the similarity between two non-mate samples. As discussed in section 1.2, a verification system makes a decision by comparing the match score 3 to a threshold 17. Therefore, FRR can be defined as the proportion of genuine scores that are less than the threshold 17 and FAR can be defined as the fraction of impostor scores that are greater than or equal to 17. Let fgen(s) = p(S = 3| genuine) and fimp(5) 2 p(5' = slimpostor) be the probability density functions of the genuine and impostor scores, respectively. The FAR and FRR of the biometric system are given by FARO?) = as 2 nli'mpostor) = f" fimpaws, (1.3) 17 FRR(17) = p(S < nlgenuine) = [00 fgen(s)ds. (1.4) Both FRR and FAR are functions of the system threshold 77. If the threshold is increased, FAR will decrease but the FRR will increase and vice versa. Hence, for a given biometric system, it is not possible to decrease both these errors simultane- 13 ously by varying the threshold. The Genuine Accept Rate (GAR) can be used as an alternative to FRR while reporting the performance of a biometric verification system. GAR is defined as the fraction of genuine scores that exceed the threshold 77. Therefore, GARM) 2 p(5 2 nlge‘nuine) = 1 — FRR('r]). (1.5) The FAR and F RR of a biometric verification system at different values of thresh- old 71 can be summarized in the form of a Detection Error Tradeoff (DET) or Receiver Operating Characteristic (ROC) curve. While the DET plot uses the normal devi- ate scale, ROC curves are plotted in a linear, semi—logarithmic or logarithmic scale. Equal Error Rate (EER) is the point in a DET or ROC curve where the FAR equals the F RR. A lower EER value indicates better performance. In this dissertation, we plot the ROC curve (GAR against FAR) on the semi-logarithmic scale to summarize the verification performance. Figure 1.4(a) shows the genuine and impostor score densities of the Face-G matcher in the NIST-BSSRl database [151] and figure 1.4(b) shows the corresponding ROC curve. The performance of a biometric identification system is measured in terms of the identification rate. Identification rate is the proportion of times the identity determined by the system is the true identity of the user providing the query biometric sample. If the biometric system outputs the identities of the top m matches, the rank-m identification rate, Rm, is defined as the proportion of times the true identity of the user is contained in the top m matching identities. The identification rate at 14 0.14 . . , f 0.12- Impostor :: *ThreSho'dm) , density—>- . A o_1 p(s|impostor),' : Genuine . ‘21 ' . density £0.08- .' i p(s|genuine). E ,' : g 0.06 . , 2 l' : O. 0.04? .5 I ,\ 0.02» :U_ "£5 :53" 65 70 {5 so 35 Match score (8) (8) 100 D a", 90- .9 g ‘5. 80- § Threshold (11) = 74 < 70- FAR = 0.6% E GAR = 85.5% 3 C 8 60- 50 _ ‘_ ._ . 10 3 10 2 1o 1 10° 101 False Accept Rate (%) (b) Figure 1.4: Performance of a biometric system operating in the verification mode. (a) The genuine and impostor match score densities corresponding to the Face-G matcher in the NIST BSSRl database. The threshold, 7), determines the FAR and GAR of the system. (b) Receiver operating characteristic (ROC) curve for the Face-G matcher which plots the GAR against FAR on a semi-logarithmic scale. 15 different ranks can be summarized using the Cumulative Match Characteristic (CMC) curve [139] (see Figure 1.5), which plots Rm against 777. for m = 1, 2, - - - ,N, where N is the number of enrolled users. When the same matcher is used for both verification and identification, then the corresponding ROC and CMC curves are related and the CMC curve can be estimated from the genuine and impostor score densities fgen(s) and fimp(s) [12,75]. 1.4 Challenges in Biometrics Though biometric systems have been successfully deployed in a number of real-world applications, biometrics is not yet a fully solved problem. The three main factors that contribute to the complexity of biometric system design are accuracy (FAR, GAR and rank-1 identification rate), scalability (size of the database) and usability (ease of use, security and privacy). Jain et al. [92] state that the grand challenge in biometrics is to design a system that operates in the extremes of all these three factors. In other words, the challenge is to deve10p a biometric system that is highly accurate and secure, convenient to use and easily scalable to a large population. We now discuss the major obstacles that hinder the design of such an “ideal” biometric system. 1.4. 1 Accuracy An ideal biometric system should always provide the correct identity decision when a biometric sample is presented. However, a biometric system seldom encounters a 16 (O 01 (O O 85- Rank—m Identification Rate (%) 1 10 20 30 40 50 Rank (m) Figure 1.5: Cumulative match characteristic (CMC) curve for the Face-G matcher in the NIST BSSRl database which plots the rank—m identification rate for various values of m. In this example, the rank-1 identification rate is a: 78% which means that for z 78% of the queries, the true identity of the query user is selected as the best matching identity. 17 sample of a user’s biometric trait that is exactly the same as the template. This results in a number of errors as discussed in section 1.3 and thereby limits the system accuracy. The main factors affecting the accuracy of a biometric system [97] are: (a) (b) Figure 1.6: Examples of noisy biometric data; (a) A noisy fingerprint image due to smearing, residual deposits, etc.; (b) A blurred iris image due to loss of focus. Figure 1.7: Non-universality of a biometric trait. This figure shows three impressions of a user’s finger in which the ridge details are worn-out. e Noisy sensor data: Noise can be present in the acquired biometric data mainly due to defective or improperly maintained sensors. For example, accumulation 18 of dirt or the residual remains on a fingerprint sensor can result in a noisy fingerprint image as shown in Figure 1.6(a). Failure to focus the camera appro- priately can lead to blurring in face and iris images (see Figure 1.6(b)). The recognition accuracy of a biometric system is highly sensitive to the quality of the biometric input and noisy data can result in a significant reduction in the GAR of a biometric system [72,204]. Non-universality: If every individual in the target pOpulation is able to present the biometric trait for recognition, then the trait is said to be universal. Uni- versality is one of the basic requirements for a biometric identifier. However, not all biometric traits are truly universal. The National Institute of Standards and Technology (NIST) has reported that it is not possible to obtain a good quality fingerprint from approximately two percent of the population (people with hand-related disabilities, manual workers with many cuts and bruises on their fingertips, and people with very oily or dry fingers) [189] (see Figure 1.7). Hence, such people cannot be enrolled in a fingerprint verification system. Simi- larly, persons having long eye-lashes and those suffering from eye abnormalities or diseases like glaucoma, cataract, aniridia, and nystagmus cannot provide good quality iris images for automatic recognition [147]. Non-universality leads to high FTER and FTCR in a biometric system. Inter-user similarity: Inter-user similarity refers to the overlap of the biomet- ric samples from two different individuals in the feature Space. The lack of uniqueness in the biometric feature set restricts the discriminative ability of the 19 biometric system and leads to an increase in the FMR. In the case of a bio- metric identification system, the inherent information constraint in the feature set results in an upper bound on the number of unique individuals that can be accommodated. 0 Lack of invariant representation: Biometric samples of an individual usually exhibit large intra-user variations (see Figure 1.3). The variations may be due to improper interaction of the user with the sensor (e.g., changes due to ro- tation, translation and applied pressure when the user places his finger on a fingerprint sensor, changes in pose and expression when the user stands in front of a camera, etc.), use of different sensors during enrollment and verification, changes in the ambient environmental conditions (e.g., illumination changes in a face recognition system) and inherent changes in the biometric trait (e.g., appearance of wrinkles due to aging or presence of facial hair in face images, presence of scars in a fingerprint, etc.). Ideally, the features extracted from the biometric data must be relatively invariant to these changes. However, in most practical biometric systems the features are not invariant and therefore complex matching algorithms are required to take these variations into account. Large intra—user variations usually decrease the GAR of a biometric system. Due to the above factors, the error rates associated with biometric systems are higher than what is required in many applications. Table 1.1 summarizes the error rates of fingerprint, face, iris and voice biometric systems obtained through various technology evaluation tests. Although the error rates presented in Table 1.1 are 20 dependent on a number of test conditions such as the sensor used, the acquisition protocol, the number and demographic profile of the subjects involved and the time lapse between successive biometric acquisitions, they provide a good estimate of the accuracy of state-of—the-art unibiometric systems because these results are obtained by independent third-party testing of competing algorithms on common databases. The results of these evaluations clearly indicate that biometric systems have non-zero error rates and there is scope for improving the accuracy of biometric systems. Table 1.1: False reject and false accept rates associated with state-of—the—art finger- print, face, voice and iris verification systems. Note that the accuracy estimate of a biometric system depends on a number of test conditions. Biometric Test Test Conditions False False Trait Reject Accept Rate Rate Fingerprint FVC 2006 [148] Heterogeneous 2.2% 2.2% population including _ manual workers and elderly people F pVTE 2003 [204] US. government 0.1% 1% operational data Face FRVT 2006 [153] Controlled illumination, 0.8—1.6% 0.1% high resolution Voice N IST 2004 [156] Text independent, 5-10% 2-5% multi-lingual Iris ICE 2006 [153] Controlled illumination, 1.1-1.4% 0.1% broad quality range 1.4.2 Scalability In the case of a biometric verification system, the size of the database (number of enrolled users in the system) is not an issue because each authentication attempt 21 basically involves matching the query with a single template. In the case of large scale identification systems where N identities are enrolled in the system, sequentially comparing the query with all the N templates is not an effective solution due to two reasons. Firstly, the throughput.2 of the system would be greatly reduced if the value of N is quite large. For example, if the size of the database is 1 million and if each match requires an average of 100 microseconds, then the throughput of the system will be less than 1 per minute. Furthermore, the large number of identities also affects the false match rate of the system adversely. Hence, there is a need for efficiently scaling the system. This is usually achieved by a process known as filtering or indexing where the database is pruned based on extrinsic (e.g., gender, ethnicity, age, etc.) or intrinsic (e.g., fingerprint pattern class) factors and the search is restricted to a smaller fraction of the database that is likely to contain the true identity of the user. There are very few published studies on efficiently indexing biometric databases [9, 52, 73] and this is still an active area of research in the biometrics community. 1.4.3 Security and Privacy Although it is difficult to steal someone’s biometric traits, it is still possible for an impostor to circumvent a biometric system in a number of ways [160]. For example, it is possible to construct fake or spoof fingers using lifted fingerprint impressions (e.g., from the sensor surface) and utilize them to circumvent a fingerprint recogni- tion system [133,134]. Behavioral traits like signature [78] and voice [58] are more 2Throughput of a biometric system is defined as the number of queries (authentication attempts) that can be processed per unit time. 22 susceptible to such attacks than anatomical traits. The most straightforward way to secure a biometric system is to put all the system modules and the interfaces between them on a smart card (or more generally a secure processor). In such systems, known as match-on-card or system-on—card technology, sensor, feature extractor, matcher and template reside on the card [91]. The advantage of this technology is that the user’s biometric data never leaves the card which is in the user’s possession. However, system-on-card solutions are not appropriate for most large-scale verification applications because they are still expensive and users must carry the card with them at all times. Moreover, system-on—card solutions cannot be used in identification applications. One of the critical issues in biometric systems is protecting the template of a user which is typically stored in a database or a smart card. Stolen biometric templates can be used to compromise the security of the system in the following two ways. (i) The stolen template can be replayed to the matcher to gain unauthorized access, and (ii) a physical spoof can be created from the template (see [2,21,171]) to gain unauthorized access to the system (as well as other systems which use the same biometric trait). Note that an adversary can covertly acquire the biometric information of a genuine user (e.g., lift the fingerprint from a surface touched by the user). Hence, spoof attacks are possible even when the adversary does not have access to the biometric template. However, the adversary needs to be in the physical proximity of the person he is attempting to impersonate in order to covertly acquire his biometric trait. On the other hand, even a remote adversary can create a physical spoof if he gets access to the biometric template information. 23 Unlike passwords, when biometric templates are compromised, it is not possible for a legitimate user to revoke his biometric identifiers and switch to another set of uncompromised identifiers. Due to this irrevocable nature of biometric data, an attack against the stored templates constitutes a major security and privacy threat in a biometric system. Since a biometric trait is a permanent link between a person and his identity, it can be easily prone to abuse in such a way that a person’s right to privacy and anonymity is compromised. A common type of abuse of biometric identifiers is function creep [84] where the acquired biometric identifiers are later used for purposes other than the intended purpose. For example, Disney World in Orlando collects fingerprints from park visitors in order to prevent customers from sharing the tickets with others [77]. However, it is possible that the same fingerprints may be used later for searching against a criminal fingerprint database or cross-link it to a person’s health records. Hence, strategies to prevent function creep and to ensure an individual’s privacy are urgently needed. 1.5 Summary Biometric recognition is the process of establishing the identity of a person based on his anatomical or behavioral characteristics. Since biometric traits provide irrefutable evidence linking a person to his identity, biometric authentication is a natural and reliable solution to the problem of establishing the identity of an individual in any identity management system. While biometric systems offer a number of functional- 24 ities such as verification, positive identification and screening, these systems are not perfect. Due to factors like intra—user variations and inter-user similarity, the error rates associated with biometric systems is non-zero. Besides the accuracy, the high failure rates (F TER and FTCR), scalability and various vulnerabilities also limit the deployment of biometric systems in many applications. While rapid progress has been made in the development and deployment of biometric systems in the past few decades, a number of core research issues in biometrics have not yet been fully addressed. Solutions to advance the state of the art in biometrics include the design of new sensors that can acquire the biometric traits of an individual in a more reliable, con- venient and secure manner, the development of invariant representation schemes and robust and efficient matching algorithms, combining evidence from multiple biometric sources to compensate for the limitations of the individual sources and the develop- ment of techniques for liveness detection, template security and privacy enhancement of biometric systems. In this thesis, we focus on biometric systems that integrate cues obtained from multiple biometric sources and these systems are commonly referred to as multibiometric systems. Multibiometric systems offer a number of advantages that can alleviate the problems associated with traditional (uni)biometric systems. This thesis addresses two critical issues in the design of a multibiometric system, namely, fusion methodology and template security. 25 1.6 Thesis contributions The first part of this dissertation addresses the problem of fusion in a multibiomet- ric system and the second part deals with the problem of multibiometric template security. The major contributions of this dissertation are as follows. 0 We propose a principled approach based on the likelihood ratio test for fusion of match scores from multiple biometric matchers in the verification scenario. The proposed fusion framework is based on the Neyman-Pearson theorem, which guarantees that at any specified FAR, the likelihood ratio test maximizes the GAR, provided the genuine and impostor match score densities are known. We use a semi-parametric density estimation approach, namely, finite Gaussian mixture models (GMM) to estimate the joint densities of match scores. We demonstrate that fusion based on these density estimates achieves consistently high performance on different multibiometric databases involving face, finger- print, iris, and speech modalities. We also extend the likelihood ratio based fusion scheme to incorporate the quality of the biometric samples and define new quality metrics known as pairwise quality indices for fingerprint and iris images. We also propose a technique based on decision trees to design cascade multibiometric systems within the likelihood ratio framework. 0 We investigate rank and score level fusion schemes in a multibiometric identi- fication system and show that the genuine and impostor likelihood ratios used in the verification scenario can also be applied in the case of identification if we assume that the match scores of the individual users are independent and 26 identically distributed. We propose a feature level fusion scheme for securing multibiometric templates using the fuzzy vault framework. The proposed framework can handle multiple samples (e.g., two impressions from the same finger), multiple instances (e.g., impressions from left and right index fingers of a person) and multiple biomet- ric traits (e.g., fingerprint and iris). Towards this end, we have developed a fully automatic implementation of a fingerprint-based fuzzy vault where helper data derived from the fingerprint orientation field is used to align the template and query minutiae. We have also developed an iris-based fuzzy vault for se- curing iriscode templates. Finally, we show that a multibiometric vault that utilizes multiple fingerprint impressions or multiple fingers or fingerprint and iris achieves better accuracy and security compared to a unibiometric vault. 27 Chapter 2 Multibiometric Systems Systems that consolidate evidence from multiple sources of biometric information in order to reliably determine the identity of an individual are known as multibiomet- ric systems [169]. Multibiometric systems can alleviate many of the limitations of unibiometric systems because the different biometric sources usually compensate for the inherent limitations of the other sources [81]. Multibiometric systems offer the following advantages over unibiometric systems. 1. Combining the evidence obtained from different sources using an effective fusion scheme can significantly improve the overall accuracy of the biometric system. The presence of multiple sources also effectively increases the dimensionality of the feature space and reduces the overlap between the feature spaces of different individuals. 2. Multibiometric systems can address the non-universality problem and reduce the FTER and FTCR. For example, if a person cannot be enrolled in a finger- 28 print system due to worn-out ridge details, he can still be identified using other biometric traits like face or iris. . Multibiometric systems can also provide a certain degree of flexibility in user authentication. Suppose a user enrolls into the system using several different traits. Later, at the time of authentication, only a subset of these traits may be acquired based on the nature of the application under consideration and the convenience of the user. For example, consider a banking application where the user enrolls into the system using face, voice and fingerprint. During authenti- cation, the user can select which trait to present depending on his convenience. While the user can choose face or voice modality when he is attempting to ac- cess the application from his mobile phone equipped with a digital camera (see Figure 2.1), he can choose the fingerprint modality when accessing the same application from a public ATM or a network computer. . The availability of multiple sources of information considerably reduces the effect of noisy data. If the biometric sample obtained from one of the sources is not of sufficient quality during a particular acquisition, the samples from other sources may still provide sufficient discriminatory information to enable reliable decision-making. . Multibiometric systems can provide the capability to search a large database in a computationally efficient manner. This can be achieved by first using a relatively simple but less accurate modality to prune the database before using the more complex and accurate modality on the remaining data to perform 29 the final identification task. This will improve the throughput of a biometric identification system. 6. Multibiometric systems are more resistant to spoof attacks because it is difficult to simultaneously spoof multiple biometric sources. Further, a multibiometric system can easily incorporate a challenge-response mechanism during biometric acquisition by acquiring a subset of the traits in some random order (e.g, left index finger followed by face and then right index finger). Such a mechanism will ensure that the system is interacting with a live user. Further, it is also possible to improve the template security by combining the feature sets from different biometric sources using an appropriate fusion scheme. Multibiometric systems also have a few disadvantages when compared to unibio- metric systems. They are more expensive and require more resources for computation and storage than unibiometric systems. Multibiometric systems generally require ad— ditional time for user enrollment, causing some inconvenience to the user. Finally, the accuracy of a multibiometric system can actually be lower than that of the unibio— metric system if an appropriate technique is not followed for combining the evidence provided by the different sources. Still, multibiometric systems offer features that are attractive and as a result, such systems are being increasingly deployed in security- critical applications (e.g., FBI-IAFIS [150], US-VISIT IDENT program [149], etc). 30 Camera Van ily mama, A “th0 to cuum H flu/HI SQCUHW Microphone Fingerprint Sensor Figure 2.1: A hypothetical mobile banking application where the user has the flex- ibility to choose all or a subset of available biometric traits (e.g., face, voice and fingerprint) for authentication depending on his convenience. Research is under way to perform iris recognition based on images captured using the camera on the mobile phone [100]. 31 2.1 Design Issues in Multibiometrics The design of a multibiometric system is dependent on the requirements of the appli- cation. The major issues that need to be considered in the design of a multibiometric system are described below. 1. Sources of biometric information include multiple sensors, multiple representa- tions and matching algorithms, multiple samples of the same biometric trait, multiple instances of a biometric trait and multiple biometric traits. For a given application, the system designer needs to decide which of these sources should be used in designing the multibiometric system. 2. The sequence in which the multiple sources of information are acquired and processed could be serial (cascade or sequential), parallel or hierarchical (tree- like). Depending on the application scenario, an appropriate acquisition and processing architecture must be selected. 3. The process of integrating evidence provided by different biometric sources is known as biometric fusion. Four types of information can be obtained from the biometric sources, namely, raw biometric samples, feature sets, match scores and decision labels. Depending on the type of information that is fused, the fusion scheme can be classified as sensor level, feature level, score level and decision level fusion. The choice of the fusion level is the most important design issue in a multibiometric system and it has a substantial impact on the performance of the system. 32 4. Given the type of information to be fused, a number of techniques are available for fusion of information provided by the multiple sources. Many of these fusion schemes may be admissible in an application and the challenge is to find the Optimal one. It must be mentioned that a majority of the design decisions are based on a cost- benefit analysis. Typically, there is a tradeoff between the additional cost and the improvement in performance of a multibiometric system. The cost could be a function of the number of sensors deployed, the time required for acquisition and processing (throughput), performance gain (reduction in FAR/FRR), storage and computational requirements and perceived (in)convenience to the user. 2.2 Sources of Multiple Evidence Sources of information in a multibiometric system (see Figure 2.2) may include (i) multiple sensors to capture the same biometric trait (e.g., face captured using optical and range sensors), (ii) multiple representations or multiple algorithms for the same biometric trait (e.g., texture and minutiae-based fingerprint matchers), (iii) multiple instances of the same biometric trait (e.g., left and right iris), (iv) multiple samples of the same biometric trait (e.g., two impressions of a person’s right index finger), and (v) multiple biometric traits (e.g., face and iris). In the first four scenarios, multiple sources of information are derived from the same biometric trait. In the fifth scenario, information is derived from different bio- metric traits and these systems are known as multimodal biometric systems. In fact, 33 biometric fusion can also be carried out on any arbitrary combination of the above five sources and such systems can be referred to as hybrid multibiometric systems [26]. An example of a hybrid multibiometric system is the system proposed by Brunelli et a1. [15] where the results of two speaker recognition algorithms are combined with three face recognition algorithms at the match score and rank levels using a HyperBF network. Hence, this system is multi-algorithmic as well as multimodal in its design. i\. v , Minutiae )" ‘ "‘ Right Eye Left Eye Figure 2.2: Various sources of information that can be fused in a multibiometric system. In four of the five scenarios (multiple sensors, representations, instances and samples), multiple sources of information are derived from the same biometric trait. In the fifth scenario, information is derived from different biometric traits and such systems are known as multimodal biometric systems. 34 2.3 Acquisition and Processing Sequence The order or sequence in which biometric samples are acquired and processed can have a significant impact on the time required for enrollment and authentication, failure to enroll rate (FTER) and user convenience. Typically, the acquisition and processing architecture of a multibiometric system is either serial or parallel (see Figure 2.3). In the serial or cascade or sequential architecture, the acquisition and processing of the different sources take place sequentially and the outcome of one matcher may affect the processing of the subsequent sources. In the parallel design, different sources are processed independently and their results are combined using an appropriate fusion scheme. Both these architectures have their own advantages and limitations. In the case of biometric acquisition, both serial and parallel architectures are quite common. It is usually convenient and cost-effective to acquire physically related biometric traits simultaneously. For example, face, voice and lip movement can be simultaneously acquired using a video camera [69]. Similarly, palmprint and hand- geometry information can be acquired in parallel using a single camera [112]. On the other hand, when multiple instances of the same trait (e. g., iris images from both the eyes) or physically unrelated biometric traits (e.g., fingerprint and face) need to be acquired, the acquisition is usually done sequentially. Most of the multibiometric systems proposed in the literature follow a parallel architecture for processing the biometric information. This is because the primary goal of system designers has been a reduction in the error rate of biometric systems and the parallel mode of processing generally has a higher accuracy because it utilizes 35 Additional __No—_, _ ' Biometric? DeCISIon Additional Biometric? Decision Decision s #1! Fusion ‘ FTP + Decision [ Matching T (b) Figure 2.3: Acquisition and processing architecture of a multibiometric system; (a) Serial (Cascade or Sequential) and (b) Parallel. 36 more evidence about the user for recognition [167,180]. However, a cascading archi- tecture may have other advantages such as increased user convenience and higher throughput, which may be useful in large scale identification tasks. For example, when a cascaded multibiometric system has sufficient confidence on the identity of the user after processing the first biometric source, the user may not be required to provide the other sources of information. The system can also allow the user to decide which information source he/she would present first. Finally, if the system is faced with the task of identifying the user from a large database, it can utilize the outcome of each matcher to successively prune the database, thereby making the search faster and more efficient. Thus, a cascaded system can be more convenient to the user and generally requires less recognition time when compared to its parallel counterpart. An example of a cascaded multibiometric system is the one proposed by Hong and Jain [80]. In this system, face recognition is used to retrieve the top m matching identities and fingerprint recognition is used to verify these identities and make a final identification decision. The choice of the system architecture depends on the application requirements. User-friendly and low security applications like bank ATMs can use a cascaded multi- biometric system. On the other hand, parallel multibiometric systems are more suited for applications where security is of paramount importance (e.g., access to military installations). It is also possible to design a hierarchical (tree-like) architecture to combine the advantages of both cascade and parallel architectures. This hierarchical architecture can be made dynamic so that it is robust and can handle problems like missing and noisy biometric samples that often arise in biometric systems [129]. How- 37 ever, the design of a hierarchical multibiometric system has not yet received adequate attention from researchers. 2.4 Levels of Fusion One of the fundamental issues in the design of a multibiometric system is to determine the type of information that should be fused. Depending on the type of information that is fused, the fusion scheme can be classified as sensor level, feature level, score level and decision level fusion. Typically, the amount of information available to the system decreases as one proceeds from the sensor module to the decision module (see Figure 2.4). The raw biometric data (e.g., face image in the case of face biometric) has the highest information content, which gets reduced by subsequent processing (e.g., after extraction of PCA features). In the verification mode, the final decision label contains only a single bit of information (match or non-match). However, the different stages of biometric data processing are expected to decrease the intra—user variability I and the amount of noise that is contained in the available information. Further, in many practical multibiometric systems, higher levels of information such as the raw images or feature sets are either not available (e.g., proprietary feature sets used in commercial-off—the—shelf systems) or the information available from different sources is not compatible (e.g., fingerprint minutiae and eigenface coefficients). On the other hand, in most of the multibiometric systems, it is relatively easy to access and combine the match scores generated by different biometric matchers. Therefore, information fusion at the match score level offers the best tradeoff in terms of information content 38 and ease in fusion. Consequently, score level fusion is the most commonly used approach in multibiometric systems. Figure 2.5 shows examples of fusion at the various levels in a multibiometric system. The four levels of fusion can be broadly categorized as (i) fusion prior to matching and (ii) fusion after matching [173]. This distinction is made because once the biometric matcher is applied, the amount of information available to the system drastically decreases. 2.4.1 Fusion Prior to Matching Prior to matching, integration of information from multiple biometric sources can take place either at the sensor level or at the feature level. Sensor Level Fusion The raw data from the sensor(s) are combined in sensor level fusion [83]. Sensor level fusion can be performed only if the sources are either samples of the same biometric trait obtained from multiple compatible sensors or multiple instances of the same biometric trait obtained using a single sensor. For example, multiple 2D face images obtained from different viewpoints can be stitched together to form a 3D model of the face [123] or a panaromic face mosaic [207]. Another example of sensor level fusion is the mosaicing of multiple fingerprint impressions to form a more complete fingerprint image [40,95,140, 159,212]. In sensor level fusion, the multiple cues must be compatible and the correspondences between points in the raw data must be either known in advance (e.g., calibrated camera systems) or reliably estimated. 39 Raw Data Extracted Features Match Score Final decision 94 6,) Genuine/lmpostor L / \ J 1.2 MB 22 Bytes 1 Byte 1 Bit Figure 2.4: The amount of information available for fusion decreases progressively af- ter each layer of processing in a biometric system. The raw data represents the richest source of information, while the final decision (in a verification scenario) contains just a single bit of information. However, the raw data is corrupted by noise and may have large intra-class variability, which is expected to be reduced in the subsequent modules of the system. (Reproduced from [169]) Feature Level Fusion Feature level fusion refers to combining different feature sets that are extracted from multiple biometric sources. When the feature sets are homogeneous (e.g., multiple fingerprint impressions of a user’s finger), a single resultant feature set can be calcu- lated as a weighted average of the individual feature sets (e. g., mosaicing of fingerprint minutiae [170]). When the feature sets are non-homogeneous (e. g., feature sets of dif- ferent biometric modalities like face and hand geometry), we can concatenate them to form a single feature set. Feature selection schemes can then be applied to reduce the dimensionality of the resultant feature set [166]. Concatenation is not possible when the feature sets are incompatible (e. g., fingerprint minutiae and eigenface coefficients). When the multiple feature sets correspond to different samples of the same biometric trait that are processed using the same feature extraction algorithm, then feature level fusion can be considered as template update or template improvement [101]. 40 Sensor Level Fuflon Decision Level Fusion Right Eye Feature Level Fuflon Score Level Fuflon Figure 2.5: Fusion can be accomplished at various levels in a biometric system. Most multibiometric systems fuse information at the match score level or the decision level. FE: feature extraction module; MM: matching module; DM: decision-making module; FM: fusion module. 41 Integration at the feature level is difficult to achieve in practice due to the following reasons: 0 The relationship between the feature spaces of different biometric sources may not be known. In the case where the relationship is known in advance, care needs to be taken to discard those features that are highly correlated. This requires the application of feature selection algorithms prior to classification. 0 The feature sets may be incompatible. For example, the minutiae set of finger- prints and eigenface coefficients cannot be directly combined because the former is a variable length feature set whose individual values represent the attributes of a minutia point while the latter is a fixed length feature set whose individual values are scalar entities. o Concatenating two feature vectors results in a feature vector with larger dimen- sionality which may lead to the ‘curse of dimensionality’ problem [85] where the classification accuracy actually degrades with the addition of new features due to the limited number of training samples. Although this is a well-known problem in most pattern recognition applications, it is more severe in biomet- ric applications because of the time, effort and cost involved in collecting large amounts of biometric (training) data. 0 Most commercial biometric systems do not provide access to the feature sets used in their products due to proprietary reasons. Examples of feature level fusion schemes proposed in the literature can be found in 42 Chibelushi et a1. [37] (voice and lip shape), Son and Lee [182] (face and iris), Kumar et al. [113] (hand geometry and palmprint) and Ross and Govindarajan [166] (face and hand geometry). Due to the constraints mentioned above, most of the attempts at feature level fusion have met with only limited success. Hence, very few researchers have studied integration at the feature level in a multibiometric system and fusion schemes at the match score and decision levels are generally preferred. 2.4.2 Fusion After Matching Schemes for integration of information after the classification/matcher stage can be divided into four categories: dynamic classifier selection, fusion at the decision level, fusion at the rank level and fusion at the match score level. A dynamic classifier selection scheme chooses the biometric source that is most likely to give the correct decision for the specific input pattern [205]. This is also known as the winner-take- all approach and the module that performs this selection is known as an associative switch [30]. Score Level Fusion Match score is a measure of the similarity between the input and template biometric feature vectors. When match scores output by different biometric matchers are con- solidated in order to arrive at a final recognition decision, fusion is said to be done at the match score level. This is also known as fusion at the measurement level or confidence level. The general flow of information in a match score level fusion scheme is shown in Figure 2.6. It must be noted that the match scores generated by the indi- 43 vidual matchers may not be homogeneous. For example, one matcher may output a distance or dissimilarity measure (a smaller distance indicates a better match) while another may output a similarity measure (a larger similarity value indicates a better match). Furthermore, the outputs of the individual matchers need not be on the same numerical scale (range). Finally, the match scores may follow different probability distributions and may be correlated. These factors make match score level fusion a challenging problem. Rank Level Fusion When the output of each biometric system is a subset of possible matches (i.e., iden- tities) sorted in decreasing order of confidence, the fusion can be done at the rank level. This is relevant in an identification system where a rank may be assigned to the top matching identities. Ho et a1. [79] describe three methods to combine the ranks assigned by different matchers. In the highest rank method, each possible identity is assigned the best (minimum) of all ranks computed by different systems. Ties are broken randomly to arrive at a strict ranking order and the final decision is made based on the consolidated ranks. The Borda count method uses the sum of the ranks assigned by the individual systems to a particular identity in order to calculate the fused rank. The logistic regression method is a generalization of the Borda count method where a weighted sum of the individual ranks is used. The weights are deter- mined using logistic regression. Another technique for rank level fusion is the mixed group ranks approach [135], which attempts to find a tradeoff between the general 44 Face Matcher Fingerprint Matcher User ; Match User [Match Identity [ Score Identity 1 Score screws Bob -O.4 Score Fusion Module Fused Alice Bob Chariie 1.47 1.80 0.92 1.00 Figure 2.6: Flow of information in a match score level fusion scheme. In this example, the match scores have been combined using the sum of scores fusion rule after min— max normalization of each matcher’s output. Note that the match scores generated by the face and fingerprint matchers are similarity measures. The range of match scores is assumed to be [—1, +1] and [0,100] for the face and fingerprint matchers, respectively. 45 preference for specific matchers and the confidence in specific results (as indicated by the ranks). Decision Level Fusion In a multibiometric system, fusion is carried out at the abstract or decision level when only the decisions output by the individual biometric matchers are available. Many commercial off-the—shelf (COTS) biometric matchers provide access only to the final recognition decision. When such COTS matchers are used to build a multibiometric system, only decision level fusion is feasible. Methods proposed in the literature for decision level fusion include “AND” and “OR” rules [49], majority voting [116], weighted majority voting [114], Bayesian decision fusion [206], the Dempster-Shafer theory of evidence [206] and behavior knowledge space [82]. 2.5 Challenges in Multibiometric System Design While multibiometric systems offer several advantages such as better recognition ac- curacy, increased population coverage, greater security and flexibility, the design of a multibiometric system is not an easy task. Multibiometric system design is a chal- lenging problem because it is very difficult to predict the optimal sources of biometric information and the optimal fusion strategy for a particular application. This diffi- culty arises due to the following factors. 1. Heterogeneity of information sources: Integration at an early stage of processing is believed to be more effective because the amount of information 46 available to the fusion module decreases as we move from the sensor level to the decision level. However, fusion at the sensor or feature level is not always possible due to the heterogeneity or incompatibility of the information content. For example, in a multibiometric system that uses face and fingerprint, it may not be possible to fuse either the raw images or the features extracted from them (e.g., fingerprint minutiae and eigenface coefficients). . Fusion complexity: Even when the sources of information are compatible (e.g., two impressions of the same finger, minutiae sets from two different fin- gers of an individual, etc.), the complexity of the fusion algorithm may nullify the advantages of fusion. For instance, fusion at the sensor or feature levels in- volves additional processing complexities such as registration and design of new algorithms to match the fused data. Further, the raw data from the sensor and the extracted feature sets are usually corrupted by various types of noise (e.g., background clutter in a face image, spurious minutiae in a fingerprint minutiae set, etc.) Hence, fusion at the sensor and feature level may not lead to any performance improvement. . Varied discriminative ability: The amount of discriminatory information provided by each biometric source can be quite different. Consider a multi- biometric system with two matchers A and B, where the matcher A has very high accuracy compared to matcher B. If a simple fusion rule that assigns equal weights to the information from the two matchers is employed, the accuracy of the multibiometric system is likely to be lower than the accuracy of the individ- 47 ual matcher A. Furthermore, some multibiometric systems utilize soft biometric traits like gender, ethnicity, height, etc., which have significantly lower discrim- inatory information content compared to traditional biometric identifiers such as fingerprint, face and iris. Hence, it is essential to estimate the amount of dis- criminatory information in each source and assign appropriate weights to the different sources based on their information content. . Correlation between sources: In many multibiometric systems, the different biometric sources may not be statistically independent. Examples of multibio- metric systems in which different information sources are correlated include (i) systems using physically related traits (e.g., speech and lip movement of a user), (ii) multiple matchers operating on the same biometric data or feature representation (e.g., two different face matchers that operate on the same raw face image) and (iii) multiple samples of the same biometric trait (e.g., two impressions of a person’s right index finger). In general, fusion of independent evidences can be expected to provide a larger improvement in accuracy com- pared to fusion of correlated sources. But the impact of correlation among the biometric sources on the fusion performance is not completely known. Apart from the above four factors, the conflicting performance requirements of an application also contribute to the difficulty of the fusion problem. A typical example is an identification system where both the accuracy and throughput requirements need to be satisfied. While utilizing more sources of evidence increases the accuracy, it may reduce the throughput of the system and it is hard to find the optimal tradeoff 48 between the two. Due to these reasons, information fusion in biometrics is still an active area of research despite the fact that information fusion has been well studied in the wider pattern recognition context. 2.6 Summary Multibiometric system design depends on various factors such as sources of informa- tion, acquisition and processing architecture, level of information fusion and fusion methodology. There has been a proliferation of work exploring the fusion of a variety of biometric sources and discussing different fusion techniques. Tables 2.1, 2.2, 2.3, and 2.4 summarize some of the representative work in the multibiometrics literature and these tables have been categorized based on the sources of information used. From these tables, it is quite apparent that fusion at the match score level has received the maximum attention from the biometrics community. However, most of the proposed score level fusion schemes involve ad-hoc techniques for normaliz- ing the match scores and assigning optimal weights to different matchers. Hence, one of the goals of this dissertation is to develop a principled statistical framework for match score fusion in multibiometric systems. Score fusion in a multibiometric verification system can be formulated as a two-class classification problem and a sig- nificant number of training samples are usually available for both the genuine and impostor classes. On the other hand, fusion in multibiometric identification systems is typically characterized by (i) a large number of classes (identities), (ii) frequent change in the number of classes during system operation due to addition/deletion 49 of users and (iii) insufficient number of training samples for the individual classes (often, only one score per matcher is available available for each user). Due to these reasons, we consider the fusion strategies for verification and identification systems separately in this dissertation. In chapter 3, we present a likelihood ratio based fu- sion framework for multibiometric verification systems. The fusion framework for multibiometric identification is presented in chapter 4. Furthermore, while template security has been receiving substantial attention, the issue of multibiometric template security has not been adequately addressed in the literature. Therefore, in chapter 5 we develop techniques that can protect multibiometric templates as a single entity. 50 Table 2.1: Examples of multi-sensor systems. Sensors Fused Authors Level of Fusion Methodology Fusion Optical and [130] Match Sum and product rules; logistic capacitive score regression fingerprint sensors 2D camera and [26] Match Weighted sum and product rules range scanner for score face [124] Match Weighted sum rule; hierarchical score matching 2D camera and IR [181] Match Weighted sum rule camera for face score [31] Match Sum rule; logistic regression score; rank 2D camera, range [27] Match Weighted sum rule scanner and IR score camera for face Red, Green, Blue [109] Match Sum and min rules channels for face score [166] Feature; Feature selection and match concatenation; sum rule score 51 Table 2.2: Examples of multi-algorithm systems. texture, fuzzy “interest” line) Representations Authors Level of Fusion Methodology and/ or Matchers Fusion Fused Fingerprint [132, Match Likelihood ratio, weighted sum (minutiae and 155,168] score rule, sum and product rules, texture features) perceptron Face (PCA, LDA, [125, Feature, Sum and max rules, nearest ICA) 131,166] match neighbor, RBF network, feature score selection and concatenation Face (LDA, PM, [45] Match Sum, product, min, max and HST) score median rules; quadratic Bayes; Parzen; weighted sum rule Face (global and [5m Feature ANFIS (Adaptive Neuro—Fuzzy local features) Inference System); SVM Face (two different [208] Feature Feature concatenation; two sets of sets of PCA-based features form the real and features) imaginary parts of the concatenated feature vector in the complex plane _Signature (global and [64,71] Match Sum and max rules, SVM local features) score Hand (geometry and [112] Feature; Feature concatenation; sum rule texture features) match score Voice (SVM and [20] Match Weighted sum rule; perceptron GMM) score Voice (multi-level [162] Match Perceptron features) score Voice (spectral [165] Match Sum, product, min, max and features, utterance score median rules; neural network verification) Voice (LPCC, [107] Feature; Feature concatenation; sum rule; MFCC, ARCSIN, match majority voting FMT features) score; decision Voice (MFCC, CMS, [172] Feature; Feature concatenation; weighted MACV features) match sum rule score Palmprint (Gabor, [113] Match Sum rule (for Gabor and line line, score; features) followed by product rule; appearance-based) decision SVM; neural network; AND rule Palmprint (geometry, [211] Decision Hierarchical (serial) matching 52 Table 2.3: Examples of multi-sample and multi-instance systems. Modality Authors Level of Fusion Methodology Fusion Fingerprint (10 [204] Match No details are available fingers) score Fingerprint (2 [72] Match Sum rule fingers) score Fingerprint (2 [155] Match Likelihood ratio computed from impressions, 2 score non-parametric joint density fingers) estimates Fingerprint (2 [95] Sensor; Mosaicing of templates at the impressions) feature image level; mosaicing of minutiae sets .140, Feature Mosaicing of minutiae sets Face (sequence of 213 Match Temporal integration images from video) score [121] Match Temporal integration through score construction of identity surfaces Voice (multiple [36] Match Zero sum fusion after sorting of utterances) score scores 53 Table 2.4: Examples of multimodal systems. Modalities Fused Authors Level of Fusion Methodology Fusion Face and voice [15] Match Geometric weighted average; score; HyperBF rank [108] Match Sum, product, min, max and score median rules [6] Match SVM; multilayer perceptron; C4.5 score decision tree; Fisher’s linear discriminant; Bayesian classifier [10] Match Statistical model based on score Bayesian theory Face, voice and lip [69] Match Weighted sum rule; majority movement score; voting decision Face and fingerprint [80] Match Product rule score [180] Match - Sum rule, Weighted sum rule score Face, fingerprint and [167] Match Sum rule; decision trees; linear hand geometry score discriminant function Face, fingerprint and [88] Match Likelihood ratio voice score Face and iris [203] Match Sum rule; weighted sum rule; score Fisher’s linear discriminant; neural network Face and gait [178] Match Sum rule score [104] Match Sum and product rules score Face and ear 25‘ Sensor Concatenation of raw images Face and palmprint _60. Feature Feature concatenation Fingerprint, hand [190] Match Weighted sum rule geometry and voice score Fingerprint and [191] Match Reduced multivariate polynomial hand geometry score model Fingerprint and 7192] Match Functional link network voice score Fingerprint and [65] Match SVM in which quality measures signature score are incorporated Voice and signature [111] Match Weighted sum rule score 54 Chapter 3 Multibiometric Verification While fusion in a multibiometric verification system can be performed at the sensor, feature, match score and decision levels, score level fusion is generally preferred be— cause it offers the best trade-off in terms of the information content and the ease in fusion. One of the challenges in combining match scores is that scores from differ- ent matchers are typically not homogeneous. Consider the scores provided by the two face matchers in the NIST-Face database [151]. The scores from the first face matcher are in the range [—1, 1], whereas scores from the second face matcher are in the range [0, 100] (see Figure 3.1). The match scores of different matchers (i) can be either distance or similarity measures, (ii) may follow different probability distribu- tions and (iii) matcher accuracies may be quite different. For example, in the case of the MSU-Multimodal database [90], the fingerprint matcher outputs similarity scores whereas the face matcher outputs distance scores; the score distributions for these two modalities are quite different (see Figure 3.3) and the fingerprint matcher is more accurate than the face matcher. Biometric matchers may also be correlated as shown 55 in Figure 3.1; the correlation coefficient1 for the genuine and impostor scores of the two face matchers in Figure 3.1 are 0.7 and 0.3, respectively. % 280 0 § m :70 J 8 a u. E60‘ 2 cf) 50 ,g', e O lmpostor Scores 6' O O 1* Genuine Scores ”b4 a5 a6 07 as as 1 Score from Face Matcher 1 Figure 3.1: N on-homogeneity in the match scores provided by the two face matchers in the NIST-Face database. Note that about 0.2% of the scores output by matcher 1 are discrete scores with value -1, which are not shown in this plot. Score fusion techniques can be divided into the following three categories. 0 Dunsformation-based score fusion: The match scores are first normalized (transformed) to a common domain and then combined using product, sum, max or min rules [108]. Choice of the normalization scheme and combination weights is data-dependent and requires extensive empirical evaluation [90,167,180,190]. o Classifier—based score fusion: Scores from multiple matchers are treated as a fea- ture vector and a classifier is constructed to discriminate genuine and impostor 1In this dissertation, we estimate correlation using the Pearson’s product-moment correlation coefficient, which measures the strength and direction of linear relationship between two random variables [164]. The correlation between two matchers is defined as the correlation between the scores of the two matchers. 56 scores [15,66,127]. When biometric score fusion is considered as a classification problem, the following issues pose challenges. (i) Unbalanced training set: The number of genuine match scores available for training is 0(N), but the number of impostor scores is 0(N2), where N is the number of users in the database. (ii) Cost of misclassification: Depending on the biometric application, the cost of accepting an impostor may be very different from the cost of rejecting a genuine user. For example, a biometric system deployed in a security applica- tion typically is required to have a false accept rate (FAR) of less than 0.1%. Therefore, the fusion strategy needs to minimize the false reject rate (FRR) at the specified FAR values rather than minimizing the total error rate (sum of FAR and FRR) [155]. (iii) Choice of classifier: Given a variety of admissible classifiers, selecting and training a classifier that gives the optimal performance (minimum FRR at a specified FAR) on a given data set is not easy. Density-based score fusion: This approach is based on the likelihood ratio test and it requires explicit estimation of genuine and impostor match score densities [74,155]. The density based approach has the advantage that it directly achieves optimal performance at any desired operating point (FAR), provided the score densities can be estimated accurately. In fact, a comparison of eight biometric fusion techniques conducted by NIST [195] with data from 187,000 subjects concluded that “Product of Likelihood Ratios was consistently most accurate, but most complex to implement” and “complexity in this implementation is in the modeling of distributions, rather than fusion per se”. The statement 57 in [195] about the complexity of density estimation was based on the use of kernel density estimator (KDE). The selection of kernel bandwidth and density estimation at the tails proved to be the most complex steps in estimating the score densities using KDE in [195]. Among the three approaches, density based fusion is a more principled approach because it achieves optimal fusion performance if the score densities are estimated accurately. Hence, we follow the density-based score fusion approach in this thesis. We investigate two different techniques for accurately estimating the genuine and im- postor match score densities, namely, the Gaussian mixture model (GMM) and the non-parametric kernel density estimator (KDE). We show that (i) GMM is quite effec- tive in modeling the genuine and impostor score densities and is simpler to implement than KDE, (ii) fusion based on the resulting density estimates achieves consistently high performance on three multibiometric databases involving face, fingerprint, iris, and speech modalities and (iii) biometric sample quality can be easily incorporated in the likelihood ratio based fusion framework. 3.1 Likelihood Ratio Test Let S be a random variable denoting the match score provided by a matcher. Let the distribution function for the genuine scores be denoted as Fgen(s) (i.e., P(S S SIS is genuine) = Fgen(s)) with the corresponding density function fgen(s). Similarly, let the distribution function for the impostor scores be denoted as Fimp(3) with the corresponding density function fimp(3)- Suppose we need to decide between 58 the genuine and impostor classes (to verify a claimed identity) based on the observed match score 3. Let \I' be a statistical test for testing the null hypothesis H0: score S corresponds to an impostor against the alternative hypothesis H1: score S corre- sponds to a genuine user. Let \Il(s) = i imply that we decide in favor of Hi, where i = 0, 1. The probability of rejecting H0 when H0 is true is known as the false accept rate (also referred to as the size or level of the test). The probability of correctly rejecting H0 when H1 is true is known as the genuine accept rate (also referred to as the power of the test). The Neyman-Pearson theorem [118] states that 1. For testing H0 against H1, there exists a test ‘1! and a constant T) such that POI/(S) = 1|H0) = a (3.1) and f 811(3) 1, when j—T > 1), NS) = f‘m” S) (3.2) 0, when %37:—7;((:—)) < 77. When fgen(s)/fimp(s) is equal to n, \Il(s) is zero with probability 7 and one with probability 1— '7. Here, 7 is chosen such that the level of the test is exactly equal to a. 2. If a test satisfies equations (3.1) and (3.2) for some 77, then it is the most powerful test for testing H0 against H1 at level a. 59 According to the N eyman—Pearson theorem, given the false accept rate (FAR) a, the optimal test for deciding whether a match score S corresponds to a genuine user or an impostor is the likelihood ratio test given by equation (3.2). For a fixed FAR, we can select a threshold 17 such that the likelihood ratio test maximizes the genuine accept rate (GAR) and there does not exist any other decision rule with a higher GAR. However, this optimality of the likelihood ratio test is guaranteed only when the underlying densities are known. In practice, we only have a finite set of genuine and impostor match scores, so we need to reliably estimate the densities fgen(s) and fimp(s) before applying the likelihood ratio test. 3.2 Estimation of Match Score Densities Density estimation techniques can be classified as parametric or non-parametric [179]. In parametric density estimation, the form of the density function (e.g., Gaussian) is assumed to be known and only the parameters of this density function (e.g., mean and standard deviation) are estimated from the training data. Non-parametric techniques (e.g., density histogram and kernel density estimator) do not assume any standard form for the density function and are essentially data-driven. A mixture of densities whose functional forms are known (e.g., mixture of Gaussians) can also be used for density estimation. This mixture method can be categorized as either parametric or semi-parametric depending on whether the number of mixture components is fixed a priori or is allowed to vary based on the observed data [67]. In the context of biometric systems, it is very difficult to choose a specific para- 60 metric form for the density of genuine and impostor match scores. It is well known that the Gaussian density is usually not appropriate for genuine and impostor match scores because the score distributions generally have a large tail and may have more than one mode (see Figure 3.2). The simplest non-parametric density estimator is the histogram method, which has the following limitations [202]: (i) it is sensitive to the placement of the bin-edges, (ii) it estimates the density by a step function and (iii) the asymptotic rate of convergence2 of the histogram is lower than that of other density estimators. Due to the above reasons, we do not use histograms for estimating the score densities. Griffin [74] used the following non-parametric approach to estimate the match score densities. The distribution functions Fgen(s) and Fimp(s) are approximated using polynomials whose coefficients are obtained empirically from the receiver oper- ating characteristic (ROC) curve of the biometric matcher. The marginal densities fgen(s) and fimp(s) are then obtained by differentiating the corresponding distri- bution functions. Although this method is relatively simple, the main limitation is that the choice of polynomial degree to be used for approximating the distribution functions is arbitrary. Further, there is no guarantee that the estimated densities will converge to the true underlying densities. To overcome these limitations, Prab- hakar and Jain [155] used kernel density estimators (also known as the Parzen window method [57]) for estimating the score densities. 2The asymptotic rate of convergence of a density estimator is defined as the rate at which the integrated mean squared error between the true and estimated densities approaches zero as the number of samples available for density estimation tends to infinity. 61 Frequency 0.08 * 0.07 > 65 70 i so 75 Match Score (a) 0.16- 0.14- 0.12- n "iii-‘1 .;.-=. ‘ 55 60 65 70 I 75 Match Score (b) Figure 3.2: Histograms of match scores and the corresponding Gaussian density es— timates for the Face-G matcher in the NIST BSSRI database. (a) Genuine and (b) Impostor. Note that the Gaussian density does not account well for the tail in the genuine score distribution and the multiple modes in the impostor score distribution. 62 3.2.1 Kernel Density Estimation In practice, many biometric matchers apply thresholds at various stages in the match- ing process. When the required threshold conditions are not met, pre—specified match scores are output by the matcher. For example, a fingerprint matcher may output a specific score value (say 31) if the orientation field of the input fingerprint does not match well with the template; the same matcher may provide a different score value (say 32) if the number of minutia points in the input fingerprint is less than a threshold. This leads to discrete components in the match score distribution that cannot be modeled accurately using a continuous density function. Hence, we propose a modified kernel density estimator [48] in which the marginal density is modeled as a mixture of continuous and discrete components (referred to as generalized density) and the joint density is estimated using copula functions. Generalized Marginal Density A generic score value so is said to be discrete if P(S = so) > 0. In such a situation, F cannot be represented by a density function in the neighborhood of so (since this would imply that P(S = so) = 0). Hence, our approach consists of first detect- ing discrete components in the genuine and impostor match score distributions, and then modeling the observed distribution of match scores as a mixture of discrete and continuous components. Given a set of match scores, 8, we first identity if there are any discrete compo— nents in it, namely, score values so with P(S = so) 2 T, where T is a threshold; 63 0 S T _<_ 1. The value of T can be determined using the algorithm described in the Appendix 8.1. We estimate the probability P(S = so) by #91, where N (so) is the number of observations in S that equal so and N is the total number of observations. The collection of all discrete components for a match score distribution is denoted by D: {so : IVES“) 2 T}. (3.3) The discrete components constitute a proportion PD E 23063 £35,9-) of the complete set of match scores, 8. We obtain the subset C, C Q S, by removing all the discrete components from S, C = S — ’D. The scores in C constitute a proportion p0 _=_- (1 — p D) of 8, and they are used to estimate the continuous component of the density (fC(s)). The continuous component of match score density is estimated using a kernel density estimate of fC(s), which is given by foe) = @- : 1c ( g “3). (3.4) mEC where [C is a function satisfying ffooo IC(s)ds = 1, called the kernel, h is a positive number, called the bandwidth of the kernel and NC E N pC. Usually IC is chosen to be a unimodal probability density function symmetric about zero. We use the Gaussian kernel (lC(s) = (NS), where (15(5) is the standard normal density) for density estimation. The choice of kernel bandwidth is a critical factor in kernel density estimation. In [155], a simple heuristic was used to estimate the bandwidth of the kernel (set to 0.0167, where (“7 is the standard deviation of the observed match scores). However, the 64 above heuristic is not always optimal and does not provide accurate density estimates on a variety of multibiometric databases. Hence, we use an automatic bandwidth es- timator known as “solve-the—equation” bandwidth selector [202] to obtain the optimal bandwidth. The “solve-the—equation” bandwidth estimator has been shown to give very good density estimates for a large class of underlying functions. This band- width estimator minimizes a mean square error criterion asymptotically. In other words, the density estimate obtained from the “solve-the-equation” bandwidth esti- mator preserves most of the characteristics (e.g., peaks and tails) of the distribution of match scores without over-smoothing, thus, achieving a good compromise between the bias and the variance of the density estimate (see Figure 3.3). The generalized density (a mixture of discrete and continuous components) is defined as - . N s f(s) =PC fc(s) + Z —]V—°) - I{s = so}. (36) 806D where I {.L‘ = so} = 1 if s = so, and 0, otherwise. The distribution function corre- sponding to the generalized density estimate is defined as P(s) =pc [_Soofcww Z ”[30]. (3.6) 306113033 The above approach for estimating the generalized density can be applied to the genuine and impostor match scores from different matchers. For a multibiometric system with K matchers, we denote the kth generalized marginal density estimated from the genuine scores as fgen,k(3)v k = 1,2, . . . , K. The corresponding estimates 65 0.04» °-°35 0.008 0.03 « § 0.025 . I: 0.006- 0.02 J g 0.004 0.015 ] 0'01 0.002 0.005 0 0 20 40 60 00 100 Match Score _3 (a) ‘ X 10 a: q r w r .‘u r ‘ 3.5 0.2 3 2.5 1 . E 0. 5 2 2 8 o 1 1.5 - 1 0.05 0.5 ‘ J ”0 200 400 600 000 0 1o 20 30 40 50 Match Scone Match Score _3 (d) c x 10 5 . 4 . E 1 g 3- 2 g ' . sj': ; 1 . "0 50 100 150 200 250 " 200 400 500 000 Match Scone Match Score (6) (f ) Figure 3.3: Histograms of match scores and the corresponding generalized density estimates for MSU-Multimodal database. (a) and (b) Genuine and impostor match scores for face modality. (c) and (d) Genuine and impostor match scores for fingerprint modality. (e) and (f) Genuine and impostor match scores for hand geometry modality. The solid line above the histogram bins is the density estimated using the kernel density estimator, and the spikes in ((1) correspond to the discrete components. 66 based on the impostor scores are denoted by fimp,k(8)v k = 1,2,...,K. Figure 3.3 gives the plots of fgen,k(5) and fimp,k(5)v k. = 1,2,3 for the distribution of observed genuine and impostor match scores in the lVISU-lV’IllltlIIlOClal database (see Appendix for a description of this database). Figure 3.3 also gives the histograms of the genuine and impostor match scores for the three modalities, namely, face, fingerprint and hand-geometry. Discrete components were detected only in the case of impostor match scores of the fingerprint modality; see the “spikes” in Figure 3.3(d) that represent the detected discrete components for T = 0.008 in equation (3.3). A comparison between the continuous and generalized density estimates for im- postor match scores provided by the first face matcher in the NIST-Face database is shown in Figure 3.4. This matcher can output a discrete match score with value —1. Figure 3.4(a) shows the continuous density estimate over the entire range of scores ([—1,1]) and the same estimate only in the range [04,07] that covers a majority of the scores. The scores with value —1 affect the kernel bandwidth significantly (h = 0.00001 when the scores with value —1 are present, while h = 0.0027 when they are removed). As a result, the continuous density estimates of the impostor scores are not accurate in the range [0.4, 0.7]. On the other hand, the generalized density estimates shown in Figure 3.4(b) are very accurate in modeling the match scores. Generalized Multivariate Density Using Copula Models The methodology described in section 3.2.1 provides only the marginal genuine and impostor score densities for each of the K matchers. When the matchers are assumed to be mutually independent, the joint (multivariate) density of the K match scores can 67 a} ‘ l 8] ] i g 6* l '5 ] S S 5‘. o i o 4, . i i l 4: ] 1 2l 2‘ l 0‘ . 0 ”mm”, “a, d", _m-“ ,. .. -1 5 0 0.5 0.45 0.5 0.55 0.6 0.65 0.7 MatchScore ‘ , MatchScore k J (a) _17 _i .7 ,v _. , W , 1 1 10 ‘ l i ‘ 1o~ ] 8 i l i a] 3 a? s ’5 . s C o 6* o , o 4 . i i 4’ 0.15 ”0.5"I0.55A‘0Emo.65 0T7 0 ' . ' i Web Score \_T_J \ Match Score J Figure 3.4: Comparison of continuous and generalized density estimates for impostor match scores provided by the first face matcher in the NIST-Face database. (a) Continuous density estimates in the entire score. range [—1, 1] and only in the range [04,07]. (b) Generalized density estimates (T = 0.002) in the entire score range [—1,1] and only in the range [0.4,0.7]. 68 be estimated as the product of the marginal densities. However, if the matchers are correlated, it may be important to model the dependence between them. When the marginal distributions are continuous, the joint density can be directly estimated us- ing multidimensional kernels. Since the marginal distribution of match scores contains discrete components, we use copula functions [146] to estimate the multivariate dis- tribution. The copula-based joint density estimation is semi-parametric because the marginals are non-parametric and the copula function that combines the marginals to get the joint density is parametric. Let H1,H2,...,H K be K continuous distribution functions and H be a K- dimensional distribution function with the kth marginal given by H k, k = 1,2, . . . , K. According to Sklar’s theorem [146], there exists a unique function C(u1,u2, . . . ,uK) from [0, 1]K to [0,1] satisfying H(81,82, - - - aSK) = C(H1(81),H2(82), - - -,HK(SK)), (3-7) where 31,...,s K are K real numbers. The function C is known as a K -copu1a function that “couples” the univariate distributions H1,H2 . . .,H K to obtain the K -variate distribution H. We use the family of Gaussian copula functions [34] to model the joint distributions of match scores3. These functions incorporate the second—order dependence among the K matchers using a K x K correlation matrix R. The K -dimensional Gaussian copula function is given by 3The Gaussian copula function does not assume that the joint or marginal match score distribu- tions are Gaussian. 69 C§(u1,u2, . . . ,uK) = <1>§(<1>-1(u1),0-1(u2),. .. ,—1(uK)), (3.8) where each uk 6 [0,1] for k = 1,2, . . . , K, R is the correlation matrix, (-) is the distribution function of the standard normal, _1(-) is its inverse, and (Pg is the K - dimensional distribution function of a random vector Z = (21, Z2, . . . , ZK)T with component means and variances given by 0 and 1, respectively. The density of 0%, denoted by 0%, is defined as oc§(u1,u2,...,uK) : ¢II§(¢-1(U1),‘I’—1(U2),---,‘I’_1(UK)) 01116112 . . . 311K 115:1 ¢((I>-1(uk)) Ill K cR(u1,u2,...,uK) ‘) (3.9) where (pg (81, 32, . . . , 3K) is the density function of the K -variate normal distribution with mean 0 and covariance matrix R (since the variance of each component of Z is 1, the covariance matrix is the same as the correlation matrix R), and 05(33) is the standard normal density. The (m,n)-th entry of R, pmn, measures the degree of correlation between the th and nth matchers for m, n = 1, 2, . . . , K. Since the K x K correlation matrix R m is unknown, we estimate it using the Pearson’s product-moment correlation of normal quantiles [164] corresponding to the given match scores from the K matchers. This method assumes that the K match scores come from the multivariate distribution H with continuous marginals, H1, H2, . . . , H K- However, the marginals associated with the genuine and impostor distributions of the K matchers may have discrete compo- 70 nents. Therefore, the generalized distributions are first “converted” into continuous distributions. This is achieved by perturbing each discrete component of figen,k(3) and pimp/0(3) through the addition of a Gaussian noise process with mean 0 and stan- dard deviation 0 = 0.0001. Note that the discrete scores are perturbed only when estimating R, and not during the estimation of the marginal distributions Fgen,k(3) and Fimp,k(5)° Hence, the multivariate density obtained by using the copula function is still a generalized (mixture of discrete and continuous) density. We model the joint distribution function of genuine match scores for K matchers, F913,, as shown in equations (3.7) and (3.8) for some correlation matrix Rgen. For the genuine case, the kth marginal will be estimated by Fgen,k(3) for k = 1, 2, . . . , K. The joint distribution function of the impostor match scores, Filfnp’ is of the same form as Fggn, but with a correlation matrix Rimp' In the impostor case, the kth marginal is estimated by Fimp,k(s) for k = 1,2, . . . , K. Figure 3.5 shows the joint density estimates of the genuine match scores output by the two matchers in the NIST-Face database when they are estimated using (i) product of the marginals (under the assumption of statistical independence) and (ii) copula functions. We can observe that the joint density estimated using copula functions is able to capture the correlation between the two face matchers (see Figure 3.5(b)) and hence, is a better estimate of the underlying genuine match score density. 71 0.7 ' 85 Match Score 1 0.6 75 0.5 65 70 Match Score2 (a) 0.7 Match Score 1 0.6 80 75 0'5 65 70 Match Score 2 (b) Figure 3.5: Joint density of the genuine match scores output by the two matchers in the NIST-Face database estimated using (a) product of marginal densities and (b) copula functions. The density estimate in (b) captures the correlation between the matchers. 72 3.2.2 GMM-based Density Estimation Although the modified kernel density estimation approach resulted in good fusion performance [48], it is not clear whether our heuristic used for detecting the discrete components and the use of a parametric copula function to estimate the joint density are optimal. To avoid these issues, we employ a well-known technique based on Gaussian mixture models (GMM) for density estimation [142]. Note that Gaussian mixture models can be used to estimate arbitrary densities and the theoretical results in [119,157] show that the density estimates obtained using finite mixture models indeed converge to the true density. Let S = [S 1, $2, - - - , S Kl be the random vector corresponding to the match scores of K different biometric matchers, where S k is the random variable representing the match score provided by the kth matcher, k = 1, 2, - - - ,K. Let fgen(s) and fimp(s) be the conditional joint density of the K match scores given the genuine and impostor classes, respectively, where s = [31,32, - -- ,sK]. Let ¢K (s; “,2) be the K-variate Gaussian density with mean vector p and covariance E, i.e., ¢K(8;M,E) =(2w1—K/2121—1/2 exp (gt — “FE-Rs —— m). (3.10) The estimates of fgen(s) and fimp(s) are obtained as a mixture of Gaussians as follows. 73 Algcn fgenfS) :2 pgenaj¢ [{(8; ”9671.,j’ 2987173.) , (311) M imp fimpfs 2; pi'mrj‘lb K(3i“imp.jv 2mm) , (3'12) where .Mgen (Mimp) is the number of mixture components used to model the density of the genuine (impostor) scores, ngng‘ (#imp,j) and Egen’j (Zimpj) are the mean vector and covariance matrix corresponding to the jth mixture component in fgen(s) (fimp(s)) and Pgen,j (pimpg') is the weight assigned to the jth mixture component in fgen(s) (fimp(s)l' In equations (3.11) and (3.12), the sum of the component weights Afgen isl, i..e ’3': _1 Pgenj =1 ande-wz _1 ppimp,j= 1. We use the algorithm proposed by Figueiredo and Jain [67] to estimate the param- eters of the mixture densities in equations (3.11) and (3.12). Selecting the appropriate number of components is one of the most challenging issues in mixture density estima- tion; while a mixture with too many components may result in over-fitting, a mixture with too few components may not approximate the true density well. The GMM fit- ting algorithm proposed in [67] 4 automatically estimates the number of components and the component parameters using an EM algorithm and the minimum message length (MML) criterion. This algorithm is also robust to initialization of parameter values (mean vectors and covariance matrices) and can handle discrete components in the match score distribution by modeling the discrete scores as a mixture component 4The MATLAB code for this algorithm is available at http://www.1x.it.pt/~mtf/ mixturecode.zip 74 with very small variance. This is achieved by adding a small value (regularization factor) to the diagonal of the covariance matrices. The actual value of this variance does not affect the performance as long as it is insignificant compared to the vari- ance of the continuous components in the match score distribution. For example, the lowest value of variance in the match score data used in our experiments is of the order of 10’3. Hence, we used the value of 10‘5 as the lower bound for the variance. Our experiments indicate that a value smaller than 10-5 (say, 10‘7 or 10‘9) does not change the performance of GMM. Since we do not place any restrictions on the component covariance matrices Egenj and Simp’j, the estimates of the joint densi- ties fgen(:1:) and fimp(a:) also take into account the correlation between the match scores. Figures 3.6 and 3.7 show that Gaussian mixture model reliably estimates the 2-D genuine and impostor densities of the two face matchers in the NIST-Face database. 3.3 Incorporating Image Quality in Fusion The quality of acquired biometric data directly affects the ability of a biometric matcher to perform the matching process effectively. Noise can be present in the biometric data due to defective or improperly maintained sensors, incorrect user in~ teraction or adverse ambient conditions. For example, when noisy fingerprint images are processed by a minutiae based fingerprint recognition algorithm, a number of false (spurious) minutia points will be detected. Figures 3.8(c) and 3.8(d) show the minutiae extracted from good quality (Figure 3.8(a)) and noisy fingerprint (Figure 75 O O ‘l O Match Score 2 0 9’ 0| 0 & O l = -1 0:5 0:6 0:7 0:8 0:9 1 0.7 Match Score 1 0.6 85 80 70 75 0-5 60 65 Match $50152 (b) Figure 3.6: Density estimation based on Gaussian mixture models for the genuine scores in the NIST—Face database. (a) Scatter plot of the genuine scores along with the fitted mixture components and (b) density estimates of the genuine scores. In this case, 12 mixture components were found. 76 75- 70- N : fies] a) L £60 2 55] i 50* o/#—— -.\ o 4 5‘ ‘~ __ ,, 45— It 045 0.5 0.55 08 065 07 MuchScore1 (a) 4 75 Match Score 1 0-5 65 70 0.4 55 6° Match ScoreZ (b) Figure 3.7: Density estimation based on Gaussian mixture models for the impostor scores in the NIST—Face database. (a) Scatter plot of the impostor scores along with the fitted mixture components and (b) density estimates of the impostor scores. In this example, 19 mixture components were found. 77 3.8(b)) images, respectively, using the minutiae extraction algorithm proposed in [86]. We observe that no false minutia is detected in the good quality fingerprint image shown in Figure 3.8(0). On the other hand, Figure 3.8(d) shows that several spurious minutiae are detected in the noisy image. In practice, some true minutiae may not be detected in poor quality images. These spurious and missing minutiae will eventually lead to errors in fingerprint matching [32]. Estimating the quality of a biometric sample and predicting the performance of a biometric matcher based on the estimated quality can be very useful in building robust multibiometric systems. This will allow us to dynamically assign weights to the individual biometric matchers based on the quality of the input sample to be verified. For example, consider a bimodal biometric system with iris and fingerprint as the two modalities. Let us assume that during a particular access attempt by the user, the iris image is of poor quality but the fingerprint image quality is sufficiently good. In this case, we can assign a higher weight to the fingerprint match score and a lower weight to the iris match score. With this motivation in mind, we now describe methods for automatically determining the quality of iris and fingerprint images and incorporating them into the fusion process. To incorporate sample quality in the likelihood ratio framework, we first make the following observation. Since a poor quality sample will be difficult to classify as genuine or impostor (see Figure 3.9), the likelihood ratio for such a sample will be close to 1. On the other hand, for good quality samples, the likelihood ratio will be greater than 1 for genuine users and less than 1 for impostors. Hence, if we estimate the joint density of the match score and the associated quality, the resulting likelihood 78 (C) ((0 Figure 3.8: Minutiae extraction results for fingerprint images of varying quality. (a) A good quality fingerprint image. (b) A noisy fingerprint image. (c) Minutia points detected in the good quality fingerprint image by an automatic minutiae extraction algorithm. (d) Minutia points detected in the noisy fingerprint image. The circles represent true minutia points while the squares represent false (spurious) minutiae. While no spurious minutia is detected in the good quality fingerprint image, several false minutia points are detected when the fingerprint image quality is poor. 79 ratios will be irnplicity weighted by the respective sample quality. We can still use the Gaussian mixture based density estimation technique described in section 3.2.2. To perform quality-based fusion, we need to automatically extract quality in- formation from the input biometric samples. Since biometric quality estimation is a challenging task in itself, we demonstrate the advantages of our scheme using only fin- gerprint and iris modalities for which quality estimators are readily available [32,33]. However, the proposed quality-based fusion scheme is generic and can be applied to any biometric modality or matcher. Note that the match score depends on the quality of both the template and query samples, so we need to define a single quality index, known as pairwise quality [143], that takes into account the quality of both template and query images. We now describe techniques to compute the pairwise quality index for fingerprint and iris modalities. 3.3.1 Pairwise Fingerprint Quality We estimate the local quality in a fingerprint image using the coherence measure described in [32]. Let Tf and Q f represent the template and the query fingerprint images, respectively. We partition Tf and Q f into blocks of size 12 x 12 pixels and estimate the coherence '7 and ’y’ for each block in Tf and Q f, respectively. Let M1,...,Mm be the m minutiae in Tf, where M,- =f$ivlli10ilai= 1,...,m. Let M’,...,M[, be the n minutiae in Qf, where M; = {2:9,y3,03}, j = 1,...,n. Let 7(23, y) and 7’ (:13, y) be the quality (coherence) of the block which contains the location (at, y) in Tf and Q f, respectively. Let t(;1:, y, A) be the rigid transformation function 80 Match Score 20 ‘ 1 L' 0 lmpostor g (B * Genuine 0 0“" m 0'" V 0.8 1 .4 0.6 Quality Index Figure 3.9: Variation of match score with quality for fingerprint modality in the WVU-Multimodal database. We observe that the genuine and impostor match scores are well-separated only for good quality (with quality index > 0.5) samples. that transforms a point (1:, y) in Tf to a point (x’, y’) in Q f. Here, A = [Azt, Ay, A0] represents the translation and rotation parameters which are estimated using the 2—D dynamic programming based minutiae matcher described in [93]. Let A and A] be the area of the fingerprint regions in the template and the query. The area of overlap, A0, between the fingerprint regions of Tf and Q f can be computed using A. The overall quality of the match between the template and query fingerprint images, q f(Tf, Q f), is then defined as follows. 2A0 qfin’Qf) = (3.3;?) (m), (3-13) where 81 .3 II M3 7(I27yi)7 “(xiayiwAll and i=1 fl to II II Ms” I,/' I. (Ij’yj’— A))’f (‘Ejayjh Here, 0 5 q f (Tf, Q f) S 1. Note that if a minutia point in the template (query) falls outside the fingerprint region of the query (template) image, then the quality of that minutia is set to zero. Given good quality template and query fingerprint images with large overlap, qf(Tf, Qf) a: 1. 3.3.2 Pairwise Iris Quality We estimate the quality of match between the template and query iris images using a modified version of the wavelet-based iris quality assessment scheme proposed in [33]. The template (Ti) and query (Qt) iris images are segmented into iris and non-iris regions [33]. A 2-D isotropic Mexican hat wavelet filter is applied to the iris regions of T, and Q; at three different scales (0.5, 1.0, 2.0) and the product of the responses at the three scales is obtained. In order to account for the variations in the pupil dilation, iris size and rotation, the rubber sheet model proposed by Daugman [50] is used to normalize the wavelet responses. Let wns be the product of the wavelet responses at the rth radius (r = 1,...,R) and sth angle (3 = 1,. ..,S) in T,- and let 11.14., 3 be the corresponding wavelet response in Qi- The average wavelet response at each radius r is computed as wr (= S'ngzl wns) and 111,. :3 128 ___1w,. 3) 82 in T,- and in respectively. The quality of match between the template and query iris images, ql(Ti1Qi)’ is defined as the correlation coefficient between the vectors w = [u11,...,wR] and w’ = ['w’1,...,w;2]. Here, —1 g q,,-(T2',Q,;) S 1. 3.4 Likelihood Ratio Based Fusion Rules Based on the likelihood ratio test described in section 3.1, we consider three fusion rules: (i) complete likelihood ratio based fusion, (ii) product fusion and (iii) quality- based product fusion. The complete likelihood ratio based fusion rule does not involve any assumptions about the match score densities. I11 this case, the joint density is directly estimated by fitting the Gaussian mixture model as outlined in section 3.2. Given a vector of match scores 3 = (31,...,sK) generated by K matchers, the complete likelihood ratio fusion rule can be stated as, Assign s to the genuine class if CLR(s) = 1.162(3)— > r, (3.14) fimp(3) — where 7' is the decision threshold that is determined based on the specified FAR. The product fusion rule can be used when the matchers are assumed to be inde— pendent. Here, the joint density of the match scores is estimated as the product of the marginal densities. For a vector of match scores 3 = (.91, . . . ,sK) generated by K matchers, the product fusion rule is given by Assign s to the genuine class if 83 K f s. -——-—-——.98”’k( k) 2 T, (3.15) k=1 fimp,k(3k) PLR(s) = where fgen,k(') and fimp,k(') are the marginal densities of the genuine and impostor scores of the kth matcher. The quality-based product fusion rule assumes independence between the K bio- metric matchers. However, within each biometric matcher the match score and the quality measure can be correlated. Let ‘Ik be the quality of the match provided by the kth matcher, for k = 1,. . .,K. Let fgen,k(3k1qk) ((fimp,k(5k:qkll be the joint density of the match score and the quality estimated from the genuine (impostor) template-query pairs of the kth matcher. The quality-based product fusion rule is given by Assign s to the genuine class if K A 3 a QPLR(s,q) = H {9672,14 ’1: (1k) 2 7'. k=1 fimp,k(3k1Qk) (3.16) It is also possible to compute the joint density of the K match scores and K quality values without assuming the independence of the matchers. However, we do not consider this rule because it requires estimating the joint density of a rather large number of variables (K x 2), which may not be reliable with limited training data that is often encountered in practice. The likelihood ratio based fusion framework can also be used for fusion of soft biometric information (e.g., gender, ethnicity and height) with the primary biometric identifiers (e.g., fingerprint and face). For instance, Jain et a1. [89] used the product 84 fusion rule proposed here for fusion of soft and primary biometric traits. This requires computation of soft biometric likelihoods as described in [169]. 3.5 Sequential Fusion Using Likelihood Ratio Framework The likelihood ratio based fusion rules proposed in section 3.4 can be applied only in a multibiometric verification system operating in the parallel mode where the scores from all the matchers are available prior to fusion. However, in some applications a multibiometric system operating in the cascade or sequential mode (see section 2.3) may be more appropriate because a sequential system has higher throughput and is more convenient for the user. For example, when a cascaded multibiometric system has sufficient confidence on the identity of the user after processing the first biometric source, the user may not be required to provide the other sources of information. One method to extend the likelihood ratio based fusion framework for a sequential multibiometric system is to employ the sequential probability ratio test (SPRT) [201]. At stage k in a SPRT, the score (311:) output by the kth matcher is used to compute the marginal likelihood ratio, Lk, where __ fgen,k(3kl . . (3.17) fimp,k(3k) Here, fgen,k() and fimp,k() are the marginal densities of the genuine and impostor scores of the kth matcher and k = 1, 2, . -- ,K. The marginal likelihood ratio (Lk, 85 k = 1, 2, - - - K — 1) is compared to two different thresholds Ak and Bk, where Ak > Bk- When Lk > Ak, we decide in favor of the genuine class. On the other hand, if Lk < Bk, we decide in favor of the impostor class. Only when Bk 3 Lk g Ak, the test proceeds to the next stage (k + 1). At stage K, if no decision has been made, the process can be truncated by setting A K = B K- While the SPRT is a principled approach to handle fusion in a cascade multibiometric system, it has the following limitations. Firstly, determining the optimal values of the thresholds Ak’s and Bk’s is not an easy task, particularly when the score densities do not have a simple parametric form. Secondly, the SPRT assumes that the sequence in which the matchers are to be invoked is fixed a priori. Finally, while Devijver and Kittler [53] have shown that it is possible to incorporate the cost of invoking a matcher when determining the thresholds in a SPRT, such an approach adds further complexity in the threshold determination process. Due to these reasons, we use a simple binary decision tree classifier [57] based on the marginal score densities of the individual matchers to extend the likelihood ratio framework for the sequential fusion scenario. During the training phase, the marginal genuine and impostor score densities are estimated as described in section 3.2 and the marginal likelihood ratios of the training samples are obtained. The marginal likelihood ratios are treated as features and are used to train a binary decision tree classifier using the C45 decision tree learning algorithm [57]. During the authentication phase, the biometric modalities are acquired and the marginal likelihood ratios are computed in the order in which the different modalities appear in the decision tree starting from the root node. The main advantage of the decision tree based approach for sequential fusion is its simplicity in 86 terms of learning and implementation. However, the major limitation of this approach is that it is not straightforward to control the tree complexity (number of levels in the tree and positions of the leaf nodes). Since the goal of a cascade multibiometric system is to increase the throughput and user convenience, the number of levels in the tree should be small and the leaf nodes should be as close as possible to the top of the tree (especially for the genuine class), thereby favoring early decisions. Heuristic pruning approaches are needed to obtain a decision tree that satisfies the above two requirements. 3.6 Experimental Results The performances of likelihood ratio based fusion rules were evaluated on two public- domain databases, namely, NIST-BSSRl and XM2VTS-Benchmark databases. The performance of the quality-based product fusion rule was evaluated only on the WVU- Multimodal database since the other databases do not contain raw fingerprint and iris images to enable us to estimate the biometric sample quality. A description of these multibiometric databases can be found in the Appendix. Density estimates based on both the modified kernel density estimator and Gaussian mixture model-based estimator lead to almost identical fusion results on all the databases. Therefore, we report only the performance of GMM-based density estimation in the subsequent sections. 87 3.6.1 Evaluation Procedure For each experiment, half of the genuine and impostor match scores were randomly selected to be in the training set for estimating the marginal densities and the corre— lation matrices5. The remaining genuine and impostor scores were used for analyzing the effectiveness of the fusion rules. The above training—test partitioning was repeated m times (m = 20) and the reported ROC curves correspond to the mean GAR values over the m trials at different FAR values. The following procedure is used to test if the difference in performances of two different fusion algorithms is significant. Let GA,- and GB,- be the GAR of two different fusion rules A and B, respectively, at a specific value of FAR for the ith trial, i = 1, . -- ,m. Let D,- = (GA,- — GBi) be the difference between the GAR values of the two rules for the ith trial and let [u D be the expected difference. If we assume that Di’s are independent and normally distributed with variance 02D, then hypotheses about a D can be tested using a paired t test [164]. To determine if the performance of rule A is better than that of rule B, we test the null hypothesis Ho: a D S 0 against the alternative hypothesis H1: ,u D > 0. Here, rejecting the null hypothesis indicates that the performance of rule A is better than that of rule B. The test statistic is given by D t: —, SD/x/TTL (3.18) 5 For experiments on the XM2VTS—Benchmark database, we do not randomly partition the score data into training and test sets because this partitioning is already defined by the Lausanne Protocol- 1 [154]. Hence, confidence intervals are not estimated for experiments with the XM2VTS-Benchmark database. 88 where B and s D are the sample mean and standard deviation, respectively, of the Di’s, i = 1,--- ,m. For an a level test, the null hypothesis must be rejected if t Z t( where t( ) is the value such that a fraction 0 of the area under ohm—1)? a,m—1 the t distribution with m — 1 degrees of freedom lies to the right of ta,m—1- The 100(1 — a)% confidence interval for #D is given by B :l: t(a/2,m-1)SD/\/T7i’ Here, a 100(1 - a)% confidence interval denotes that if the database is randomly partitioned into training and test sets a large number of times and if the confidence interval is estimated for these trials, then 95% of these confidence intervals would contain the true value of #D- The value of a is set to 0.05 in our experiments. 3.6.2 Performance of Likelihood Ratio Based Parallel Fusion The performance of complete likelihood ratio based fusion rule was evaluated on the three partitions of the N IST -BSSR1 database and the XM2VTS—Benchmark database. The receiver operating characteristic (ROC) curves of the individual matchers and the likelihood ratio based fusion rule for these databases are shown in Figures 3.10, 3.11, 3.12 and 3.13. As expected, likelihood ratio based fusion leads to significant improvement in the performance compared to the best single modality on all the four databases. At a false accept rate (FAR) of 0.01%, the improvement in the genuine accept rate (GAR) achieved due to likelihood ratio based fusion is presented in Table 3.1. We observe that the 95% confidence intervals estimated in Table 3.1 are fairly tight, which indicates that the performance improvement is consistent across different cross-validation trials. 89 Table 3.1: Performance improvement achieved due to likelihood ratio based fusion. The GAR values in the table correspond to 0.01% FAR. Database Best Single Mean GAR 95% Confidence Matcher Interval on Best Likelihood increase in GAR Single Ratio Matcher based Fusion NIST- Right Index Finger 85.3% 99.1% [13.5%, 14%] Multimodal NIST- Right Index Finger 83.5% 91.4% [7.6%, 8.2%] Fingerprint NIST-Face Matcher 1 71.2% 77.2% [4.7%, 7.3%] XM2VTS- DCTb—GMM Face 89.5% 98.7% N/ A Benchmark Matcher 3.6.3 Comparison With Other Score Fusion Techniques The performance of the LR fusion rule is first compared to fusion based on Support Vector Machine (SVM) classifier. While the performance of SVM based fusion is com- parable to LR fusion on the NIST-Fingerprint and XM2VTS—Benchmark databases (see Figures 3.11 and 3.13), it is inferior to LR fusion on the NIST-Multimodal and NIST-Face databases (see Figures 3.10 and 3.12). Moreover, the kernel function and the associated parameters for SVM must be carefully chosen in order to achieve this performance. For example, while linear SVM gave good performance on the NIST- Multimodal and XM2VTS-Benchmark databases, a radial basis function (RBF) kernel with different parameter values for the NIST-Fingerprint (”y = 0.005) and NIST-Face (7 = 0.1) databases was used to obtain the results reported here. In our experiments, 90 100 - we --- ...... —---------- ........................ 0" 95 _ Likelihood Ratio Fusion Rule Right Index ‘ .0 ‘0 l e 0 .I e A 90 _ _ .. , ’ - s , . , r ‘ l *3 Left Index Finger 0: 35 ’. _ _ , — ‘61 Face ”.3“, — — " o c 8 Matcher 2 , :- < - — ’f a, 80 L ’ , c ‘I _ C I ‘I '5 , v .’ c I- ’ I O ‘l‘ o ,m 75 ~ ‘ ' Face Matcher 1 — -"I [I I 70 0‘ - 65 . A . . . . . . l A L 4 1 . A . . 1 m A 1 10'2 10 ‘ 10° 101 False Accept Rate (%) Figure 3.10: Performance of complete likelihood ratio based fusion rule and linear SVM-based fusion on the N IST -Multimodal database. 91 100 . . ..s-s., SVM Likelihood Ratio Fusion Rule 95 is" .03 (U i— a: 90 Right Index E. Finger , I s , . ' < ’ s .“s’ 85 4 ' _ 3 C a) I (D , , ’ l r 80 “ ’ I I ‘ 755‘-’ . . ...1..1 . A .JLJLAI r 1 txlrg 10‘2 10’1 10° 101 False Accept Rate (%) Figure 3.11: Performance of complete likelihood ratio based fusion rule and SVM- based fusion on the NIST-Fingerprint database. A radial basis function kernel with 7 = 0.005 was used for SVM fusion. 92 100 e rsmm I 95 90 “ Likelihood Ratio Fusion Rule 85 80 Genuine Accept Rate (%) 75 . ' ' [xi ‘,.-"‘Face Matcher 1 70,! Fa ‘ Matcher 2 L l e n s e I e c — s e n c 0 I I 60 t t . . 1 . . . l r r . m ML Lil t 1 ML 1 4 t . 10 10‘1 10° 101 False Accept Rate (%) Figure 3.12: Performance of complete likelihood ratio based fusion rule and SVM- based fusion on the NIST-Face database. A radial basis function kernel with 'y = 0.1 was used for SVM fusion. 93 100 . . . - . -"'..'7.77. 71735:. M h . — . ; . ¢ - o ------- Likelihood Ratio SVM ,~ ‘ “ 95 - Fusion Rule _____ ,...~" . v‘IlI gs ,,.—. —-' ---- F 90 [- , p ‘ ' l ’3 ¢ “ .4 iii ‘ est Face 1' tr Matcher 3 ‘6. (Dch-GMM); Best Speech 8 85 - Matcher - 2 (LFCC-GMM) O .5 3:3, 80 - - (D 75 - - 70 1 r . .....i- .1 . j . .12. 10-2 10 1 10° 101 False Accept Rate (%) Figure 3.13: Performance of complete likelihood ratio based fusion rule and linear SVM-based fusion on the XM2VTS-Benchmark database. Although there are 8 dif- ferent matchers in the XM2VTS-Benchmark database, only the ROC curves of the best face matcher (DCTb—GMM) and the best speech matcher (LFCC—GMM) are shown for clarity. 94 the model selection for SVM (kernel type and kernel parameters) was performed by trial and error. We manually tried the linear SVM and RBF kernel with different parameter choices (approximately 5 different values) on each database and report the best results. It is also possible to set the values of the kernel parameters automatically using techniques proposed in the literature [29,70]. Next, we compare the performance of complete likelihood ratio based fusion rule with commonly used transformation-based score fusion techniques, where the scores are first transformed using a normalization scheme and then the normalized scores are combined using a fusion rule. Among the various possible combinations of nor- malization schemes and fusion rules [90,180], we selected the min-max normalization scheme and sum of scores fusion method because our empirical results showed that this combination gave the best results. The ROC curves for the likelihood ratio based and sum of scores fusion rules on N IST—Multimodal and XM2VTS-Benchmark databases are shown in Figure 3.14. In the case of NIST-Multimodal database, we observe that the complete likelihood ratio based fusion rule does not provide any sig- nificant improvement over the sum rule (see Figure 3.14(a)). The paired t test rejects the hypothesis that the performances of the likelihood and sum rules are different. This is not surprising, because it has been shown in the literature that the sum rule works quite well in practice due to its robustness to noisy data and errors in density estimation [108]. However, the performance of the sum rule is inferior to the likeli- hood ratio based approach in the case of XM2VTS-Benchmark database (see Figure 3.14(b)). The reason for the sub-optimal performance of sum rule in the case of XM2VTS- 95 :\°‘ 0) ‘tii (I 96 . ‘5. o O 2 g 94 ' ------ Minmax-Sum Rule is Complete Likelihood 0 Ratio Fusion Rule (D 92 . 90 ‘ ‘ 10-2 -1 0 101 1 False Accept Rate (%) (a) Genuine Accept Rate (%) ; --'-- Minmax—Sum Rule _i ------- IT-MM—Sum Rule 92 “.t’ __ Complete Likelihood Ratio Fusion Rule 90 ‘ ' ' 10'3 10'2 10'1 10° 101 False Accept Rate (%) (b) Figure 3.14: Performance of complete likelihood ratio based fusion rule and sum of scores fusion rule with min-max normalization on (a) NIST-Multimodal database and (b) XM2VTS—Benchmark database. In (b), IT-MM denotes that an inverse tangent function is applied only to the match scores of the MLP classifiers prior to normalizing all the match scores using min-max normalization. 96 Benchmark database is that the match scores are computed based on two types of classifiers. One of them is a multi-layer perceptron (MLP) while the other is a Bayes classifier using the Gaussian Mixture Model (GMM). While the distribution of match scores output by the GMM classifier can be approximated by a Gaussian distribution (see Figure 3.15(b)), the match score distribution of the MLP classifier is peaked around 1 and —1 due to the tanh function at the output layer of the perceptron (see Figure 3.15(a)). Hence, the sum rule does not provide a good approximation to the likelihood ratio based fusion rule because the nature of match score distributions is very different. However, if we change the distribution of scores at the output of the MLP classifier by applying an inverse tangent function to these scores, then the performance of the sum rule improves and becomes comparable to likelihood ratio based fusion as observed in Figure 3.14(b). These results demonstrate that while it is possible to achieve good fusion performance for a specific database using the simple sum rule by carefully choosing the normalization scheme, the proposed likelihood- ratio based fusion framework is a general approach that provides good performance consistently on all the databases considered in this thesis. 3.6.4 Comparison of Product and Complete Likelihood Ratio Fusion The complete likelihood ratio based fusion rule is based on the joint density of the genuine and impostor match scores and hence, takes into account the correlation be- tween the matchers. On the other hand, the product fusion rule, which is simpler 97 .O \l 1 — Genuine Scores - - -lmpostor Scores . Frequency .0 .0 .0 .0 .0 N on A 01 a) .0 _L O Match Score (a) 0.35 r . — Genuine Scores 0.3 ~ - - -|mpostor Scores . 0.25 ~ .0 N P _L 01 Frequency .0 A 0.05 * Match Score (b) Figure 3.15: Distribution of genuine and impostor match scores in the XM2VTS- Benchmark database for (a) MLP classifier and (b) GMM classifier. 98 to implement, ignores the correlation between matchers and approximates the joint density by the product of the marginal densities. To study the performance differ- ence between these two rules, we consider two databases for which the correlation between the various matchers is high. As an example, in the NIST-Face database, the correlation between the scores of the two matchers is 0.7 for the genuine class and 0.3 for the impostor class. In the XM2VTS—Benchmark database, we choose the two speech matchers LFCC—GMM and SSC-GMM because this matcher pair had the highest correlation value among the different matcher pairs (0.8 for the genuine class and 0.7 for the impostor class). The performance of the product and complete likelihood ratio based fusion rules on the NIST—Face database is shown in Figure 3.16, which indicates that there is no difference in the performance of the two rules. This is because the difference between genuine and impostor correlations is not high and the two matchers in this database are reasonably accurate (the d, value6 is 3.2 for both the matchers). Now, we apply a linear transformation of the form 3; = (3k — a)/b to the genuine match scores I kth matcher and 3k is from the two matchers, where 8k is the original score of the the modified score. The values of the constants a and b are chosen such that the d, metric of the transformed scores is approximately 2. This linear transformation does not affect the correlation between the genuine scores of the two matchers. We also remove the correlation between impostor scores by randomly permuting the impostor scores from one of the two matchers. Note that this permutation does not change the 6The d-prime value ((1) measures the separation between the means of the genuine and impostor distributions in standard deviation units. A higher (1 value indicates better performance. 99 I'narginal distribution of the impostor scores. As a result of these transformations, the (I, value for the modified match scores is approximately 2 and the correlation between the scores is 0.7 for the genuine class and O for the impostor class. The performance of the complete likelihood ratio based fusion and the product fusion rules on the modified scores is shown in Figure 3.16. Since the separation between the genuine and impostor distributions was reduced by applying a linear transformation to the genuine scores, the accuracy of the individual matchers and hence the fusion performance is reduced substantially. However, in this case we observe that the complete likelihood ratio based fusion rule clearly outperforms the product fusion rule. For example, at a FAR of 0.1%, the average improvement in the GAR is 2.7% and the 95% confidence interval for the difference in the GAR between the two rules is [2.5%,2.9%]. This result indicates that modeling the correlation between the match scores, and hence the use of complete likelihood ratio fusion rule is justified only if the matchers are of low accuracy and the difference between genuine and impostor correlation is large. Similar results were also obtained in the case of correlated matcher pairs in the XMZVTS—Benchmark database. Figure 3.17 shows the ROC curves for the fusion of LFCC-GMM and SSC—GMM speech matchers in the XM2VTS database. The d, values for the LFCC-GMM and SSC-GMM matchers are approximately 4 and 3, respectively. From Figure 3.17, we observe that the complete likelihood ratio based fu- sion and product fusion rules perform equally well on this pair of matchers. However, if the d, values of the two matchers are reduced by applying a linear transformation to the genuine scores and if the impostor correlation is removed, we observe that the complete likelihood ratio based fusion rule provides better fusion performance than 100 100 90 §§ 80 0) iii a: ‘5. g 70 < 0 .E 3 C {3 60 50 _ - - -Complete LR Fusion Rule - Modified Match Scores j ------- Product Fusion Rule - Modified Match Scores ’ e --0- - Product Fusion Rule - Original Match Scores .- — Complete LR Fusion Rule - Original Match Scores 40 J . l i A r . l l 1 i l a L 10'1 10° False Accept Rate (%) 10 1 Figure 3.16: Performance of product and complete likelihood ratio based fusion rules for the two face matchers in the N IST-Face database. 101 the product fusion rule (see Figure 3.17). 3.6.5 Performance of Quality-based Fusion We investigate the performance of the quality-based product fusion rule on the WVU- Multimodal database. Recall that for the other two databases, raw images are not available precluding the use of quality-based fusion. Figure 3.18 shows the perfor- mance of the product7 and the quality—based product fusion rules. Fusion of finger- print and iris modalities using the product rule gives a large improvement in the GAR compared to the best single modality (iris, in this experiment). The quality-based product fusion rule further improves the GAR. For example, at a FAR of 0.001%, the mean GAR of the iris modality is 66.7%, while the GAR values of the product and quality-based product fusion rules are 85.3% and 90%, respectively. The 95% confi- dence interval for the improvement in GAR obtained by using quality-based product fusion instead of product fusion is [4.1%, 5.3%]. 3.6.6 Performance of Likelihood Ratio Based Sequential Fu- sion The performance of the decision tree based approach for likelihood ratio based sequen- tial fusion was studied using the NIST-BSSR1 database. Since the structure of the decision tree depends on the set of match scores selected for training, the sequential fusion rule is not the same across all the cross-validation trials. A typical sequential 7Since the correlation between fingerprint and iris modalities is zero, complete likelihood ratio based fusion and product fusion rules have the same performance on the WVU-Multimodal database. 102 100 90 80 § 9 70 (U C! a 8 60 0 < 0 .E 2 50 d) O 40 , I ’ - - - ' Product Fusion Rule - Original Match Scores 30 _ I ’ -——Comp|ete LR Fusion Rule - Modified Match Scores r' ---------- ‘ ------- Product Fusion Rule - Modified Match Scores .......... - - -Complete LR Fusion Rule - Modified Match Scores 20 a A kin—LLL; . 4 1.14444 . . 111.11 10‘3 10'2 10“ 10° False Accept Rate (%) Figure 3.17: Performance of product and complete likelihood ratio based fusion rules for the LFCC-GMM and SSC-GMM speech matchers in the XM2VTS database. 103 100 Quality-based ' ' ' ' ' ’ _ _ ‘_ _ _ _ .__.,=f._., 35:53.14. u. Likelihood Ratio Fusion _ _ __ _ .. .. .. — -:|:.'_'_.". — ------- 90" ’.’,—".' ........... ; ."v‘: "‘ .l ............ ’.’ ‘ ‘‘‘‘ ’ ‘ v A Likelihood Ratio-based "', e r ’ E 80 ~ Score Fusion as; e — a, v ’0'". E I ' ’ ' ' ns ’ a 0 fl ' ‘\ g- o ’ ' ' C.“ o 70 L , - ,. 1 - O r ’ . . ‘0‘) r ' Flngerpnnt .E 3 C 8 60 r _ 50 L _ 40 m ...1 . . .LL...l .1 -3 -2 -1 1O 10 1O 10 False Accept Rate (%) Figure 3.18: Performance of product fusion and quality-based product fusion rules on the WVU-Multimodal database. 104 fusion rule (decision tree) obtained using the NIST-Fingerprint database is shown in Figure 3.19. For this database, marginal likelihood ratio corresponding to the right index finger was usually selected as the root node because it is more accurate than the left index finger. On average, 92.6% of the genuine attempts required only a single modality (right index finger). The operating point of the system was modified by varying the ratio of genuine and impostor samples in the training phase. The average GAR of the system was observed to be 94.2% at a FAR of 0.2% and 95.9% at a FAR of 1.3%. The corresponding GAR values obtained in the parallel fusion scenario are 94.6% and 96.1%. These results show that while there is a marginal degradation in the GAR when sequential fusion is used instead of parallel fusion, the sequential system can lead to a significant increase in the user convenience and throughput be- cause 3 92% of the genuine authentication attempts can be processed using just one modality. Similar results were also observed in the case of the NIST-Multimodal database. Since both the face matchers in this database have roughly the same performance, we consider the scores from a single face matcher and the two fingers in this experiment. Figure 3.20 shows a typical sequential fusion rule (decision tree) obtained using the NIST-Multimodal database. Again in this database, the most accurate modality, namely, the right index finger was usually selected as the root node and on average, 91.1% of the genuine attempts required only a single modality (right index finger). The average GAR of the system was observed to be 96.9% at a FAR of 0.01% and 97.9% at a FAR of 0.2%. The corresponding GAR values obtained in the parallel fusion scenario are 97.8% and 98.6%. Thus, sequential fusion significantly reduces 105 Genuine Impostor Genuine Figure 3.19: A typical sequential fusion rule (decision tree) obtained using the NIST- Fingerprint database. Here, L1 and L2 represent the marginal log-likelihood ratios for the left index finger and right index finger, respectively. the number of modalities to be acquired during authentication without adversely affecting the GAR. 3.7 Summary We have proposed a statistical framework for the fusion of match scores in a multibio- metric verification system based on the likelihood ratio test. This approach is optimal provided the underlying genuine and impostor match score densities are known. In practice, one needs to estimate these densities from the available training set of match scores. We have modeled the genuine and impostor match scores using a mixture of Gaussian densities and used the EM algorithm with the minimum message length cri- terion for estimating the parameters of the mixture density and the number of mixture components. We have also developed a quality-based fusion scheme within the likeli- 106 Impostor ® No Yes Impostor Genuine Figure 3.20: A typical sequential fusion rule obtained using the NIST-Multimodal database. Here, L1, L2 and L3 represent the marginal log-likelihood ratios for the left index finger, right index finger and face modalities, respectively. 107 hood ratio framework to fuse multiple biometric sources based on the input biometric sample quality. Finally, we have shown that sequential fusion rules for a cascade multibiometric system can be generated by constructing a binary decision tree clas- sifier based on the marginal likelihood ratio of the individual matchers. Experiments on three different multibiometric databases lead us to the following conclusions. 0 Both the modified kernel density estimator and Gaussian mixture models pro- vide reliable density estimates. However, The GMM-based density estimation is simpler to implement than KDE. The likelihood ratio based fusion rule based on the density estimates provided by GMM achieves consistently high recognition rates without any tuning of parameters by the system designer. o The performance of a simple fusion rule such as the sum rule with min-max normalization is often comparable to that of the likelihood ratio based fusion rule. However, the sum rule requires careful selection of normalization scheme and fusion weights to achieve good performance. Further, this selection of normalization scheme and fusion weights is data dependent. o In practice, the assumption of independence between matchers to be used does not adversely affect the performance of the fusion scheme, especially when the individuals matchers are quite accurate (equal error rate is less than 5%). In other words, the complete likelihood ratio fusion rule and the product likelihood ratio fusion rule give comparable performance. 0 Utilizing biometric sample quality information, when available, in the likeli- hood ratio based fusion framework leads to a significant improvement in the 108 performance of multibiometric systems. 0 The sequential fusion rules significantly reduce the number of modalities re- quired for authentication and hence, increase the throughput and user conve- nience without degrading the recognition performance significantly. 109 Chapter 4 Multibiometric Identification The likelihood ratio based score fusion framework proposed in Chapter 3 was devel- oped specifically for the verification scenario where the goal is to decide whether an input sample belongs to the genuine or impostor class. In verification, the biometric query is compared only to the template of the claimed identity, resulting in a single match score for each matcher. However, in an identification system, the biometric query is compared with all the templates in the database resulting in N match scores for each matcher, where N is the number of persons enrolled in the database. The goal is to determine the true identity I of the user based on these N match scores, where I E {11,12,--- ,IN,IN+1}. Here, 11,12, - -- ,IN correspond to the identities of the N persons enrolled in the system and I N +1 indicates the “reject” option, which is output when no suitable identity can be determined for the given query. When the reject option is available to the system, the problem is known as open set identifica- tion. On the other hand, if the biometric system is forced to make a decision in favor of one of the N identities, then the problem is referred to as closed set identification. 110 In this chapter, we show that likelihood ratio based score fusion framework developed for the verification scenario is also applicable to multibiometric identification under certain assumptions. We also demonstrate that likelihood ratio based score fusion achieves good identification performance compared to other score level and rank level fusion approaches. 4.1 Score Level Fusion Let K denote the number of matchers in the multibiometric system and N be the number of persons enrolled in the system. Let Sf, denote the random variable corre— sponding to the match score output by the kth matcher after comparing the query to the template of the nth person in the database, k = 1, 2, - -- ,K: n = 1, 2, - u ,N. Let 8 be a N x K matrix defined as 1 k K 51 51 51 8= S}, Si: 55 =l51’52"”’SKl=[51»52,“',5NIT’ 1 k K _SN SN 3N_ T where Sk = [Sk,S§,--- ,Sfi/v] , for k =1,2,---,K and Sn =[S,1,,S,2,,---,S£{], forn=1,2,~- ,N. Suppose for a given query, we observe the N x K score matrix 3 = [9,13] Note 111 that 35, represents the match score output by the kth matcher for the nth template in the database, k = l,2,--- ,K; n = 1,2, ,N. Our goal is to determine the true identity I of the given query based on 3. According to the Bayesian decision theory [57], the query should be assigned to the identity [no that maximizes the posteriori probability, i.e., Assign I “I720 if P(InOIS) Z P(InlS),V n =1,2,"' ,N. (4.1) The above decision rule applies only to closed set identification. For Open set iden- tification, the query is assigned to identity [no only when equation (4.1) holds and P(Inols) Z 7', where T is a threshold. We can estimate the posteriori probabilities P(Inls) in the following manner. According to the Bayes theorem, P(slIn)P(In) Pan's) 2 12(8) , (4-2) where p(s|In) is the likelihood of observing the score matrix 3 given that the true identity is In and P(In) is the prior probability of observing the identity In. If we assume equal prior for all the identities (i.e., P(In) = 1/N,V n = 1,2, - -- ,N), the posteriori probability P(Inls) is proportional to the likelihood p(s|In). Hence, we can rewrite the decision rule in equation (4.1) as 112 Assign I——>In0 if Ideally, we would like to estimate the conditional density of s individually for each user because it captures the complete information about dependencies between the scores assigned to the different users and the user-specific characteristics of the match scores. However, directly estimating the conditional density of s is not practical due to the following two reasons. 1. Since 3 is a N x K dimensional matrix and N is usually quite large (can be of the order of millions), estimating the density of 3 requires a significant number of training samples for each user, which is not generally available in multibiometric databases. Often, only a single template and query is available for each user. 2. The density of 8 needs to be re—estimated whenever there is a change in the list of persons enrolled in the biometric system, which may occur frequently. Two simplifying assumptions are generally used [12,75] to make the density esti- mation feasible. Firstly, we assume that the match scores for different persons are independent of one another. In other words, 3,; and sj are assumed to be independent for allz' 75 j,i = 1,2, - -- ;N,j = 1, 2, - -- ,N. Based on this assumption, the likelihood p(s|In) can be simplified as 113 N p()=s|In fip(sj|1n)=p(snIIn) H p(sj|In). (4.4) j=1aj7én Here, p(sn|In) represents the density of genuine match scores corresponding to user In and p(stIn), j 75 n represents the densities of the impostor scores. The second assumption made is that the genuine match scores of all users are identically distributed, i.e., p(sn|In) = p(sn|genuine) = fgen(sn),V n = 1,2, - n ,N and the impostor match scores of all users are identically distributed, i.e., p(sj|In) = p(sj|impost0r) = fimp(3j)aV j, n = 1, 2, - -- ,N,n 7é j. Therefore, equation (4.4) can be further rewritten as N P(Slln)=fgen(3n) H fimp(3j)- (4-5) 1:10?” Multiplying and dividing equation (4.5) by fimp(3n)a we get p(sl1n)= ff——T::((:")) H fimplsjl. (4.6) Under the above two simplifying assumptions, the likelihood of observing the score matrix 3 given that the true identity is In is proportional to the likelihood ratio that was used in the verification scenario. Thus, the decision rule in equation (4.3) can be restated as Assign I ——’InO if 114 fgen(3n0) > fgen(3n) _ ,Vn=l,2,-~,N. 4.7) fimp(3n0) fimp(3n) ( 4.2 Rank Level Fusion When a biometric system operates in the identification mode, for a given query, the output of the system can be viewed as a ranking of the enrolled identities. In other words, the output indicates the set of possible matching identities sorted in a decreasing order of match scores. Although the ranks are derived from the match scores, the rank information captures the relative ordering of the scores corresponding to different users. The goal of rank level fusion schemes is to consolidate the ranks output by the individual biometric subsystems in order to derive a consensus rank for each identity. Let K denote the number of matchers in the multibiometric system and N be the number of persons enrolled in the system. Suppose for a given query, we observe the N x K rank matrix 1‘ = [r5], where r5, represents the rank output by the kth matcher for the nth template in the database, k = 1, 2, - -- ,K; n = 1, 2, - -- ,N. The goal in rank level fusion is to determine the true identity I of the given query based on 1'. Let 7‘; be a statistic computed for user n such that the user with the lowest value of r, is assigned the highest consensus (or reordered) rank. For example, in the highest rank method [79], each user is assigned the highest rank (minimum 7‘ value) as computed by different matchers, i.e., the statistic for user n is I K k Tn = mm 'rn. (4.8) 115 Ties are broken randomly to arrive at a strict ranking order based on the new statistic 7". Ho et al. [79] prOposed other methods such as Borda Count and logistic regression which compute the statistic r, as a linear combination of ranks provided by the individual matchers. Melnik et al. [135] proposed the use of non-linear functions to combine the ranks of the individual matchers. We now propose a new rank combination statistic based on Bayesian decision theory. Let Pk(r) be the probability that the identity that is assigned rank 1" by the kth matcher is the true identity, 7‘ = 1,2,--- ,N; k = 1,2, ,N. Note that the cumulative distribution function of the discrete rank distribution Pk(r) is nothing but the Cumulative Match Characteristic (CMC) defined in section 1.3. Grother and Phillips [75] and Bolle et a1. [12] show that the rank distribution Pk('r) can be estimated provided the marginal genuine and impostor match score densities fgen,k(') and fimp,k(') are known. This estimation again requires the same two assumptions used in section 4.1, namely, (i) scores of the individual users are independent and (ii) genuine score distributions of different users are identical and the impostor score distributions of different users are identical. For a given query, suppose that the identity In is assigned the rank r5 by the kth matcher. From the definition of the rank distribution Pk(r), Pk(r[“,) is the posteriori probability that In is the true identity given r5. Further, if we assume that the matchers are independent, we can compute the new rank combination statistic as the product of the posterior probabilities of the individual matchers. 116 K I Tn = H Pk('I‘£),forn = 1,2, - -- ,N. (4.9) k=1 Note that for the rank statistic computed using equation (4.9), the user with the I largest value of 1‘ should be assigned the highest consensus rank. The rank posterior based fusion rule can then be defined as follows. Assign I ——+In0 if I I T710 _>_rn,Vn=1,2,--- ,N. (4.10) Note that likelihood ratio based score fusion rule shown in equation (4.7) uti- lizes only the match scores corresponding to a particular user, when computing the likelihood ratio for that user. In other words, the relative information between the scores of different users is ignored when computing the score likelihood ratio. On the other hand, the rank posterior based fusion rule in equation (4.10) considers only the relative order information between the scores of different users and the actual score values are ignored. Therefore, we can treat the score and rank information as two different pieces of evidence and define a hybrid fusion scheme that utilizes both the match scores and the ranks. Let R the combined score and rank statistic, defined as Rn(s, r) = P(Inlsirg, (4.11) where the posterior probability based on the match score matrix 8, P(Inls), is com- puted by substituting equation (4.6) in equation (4.2) and the posterior probability 117 based on the rank matrix 1' is obtained using equation (4.9). The hybrid score-rank fusion rule can then be defined as ASSIgn I _* [no if RnOZRn,Vn=1,2,--- ,N. (4.12) 4.3 Experimental Results The identification performance of various score and rank level fusion strategies was evaluated on the three partitions of the NIST—BSSRl database. The cumulative match characteristic (CMC) curves of the individual matchers and the highest rank and hybrid score-rank fusion rules on the NIST-BSSRI database are shown in Figures 4.1, 4.2 and 4.3. Similar to the verification scenario, in each experiment, half the users were randomly selected to be in the training set for estimating the marginal densities and the rank distribution. The remaining half of the database was used for evaluating the fusion performance. The above training-test partitioning was repeated 20 times and the reported CMC curves correspond to the mean identification rates over the 20 trials. Among the various rank level fusion schemes such as highest rank, Borda count and logistic regression, we observed that the highest rank method achieves the best rank-m recognition rate when m 2 K, where K is the number of matchers. Hence, only the recognition rates of the highest rank method are reported here. It is well- 118 r l I I 1001l+—~- 'e- <.>~-:> ~<>~ s3 as)--(,2——~£.;-«era-~94.)—awn---<,->~---:.:>--:.)~-~Q--c:-~<')-us.> d: (0 01 A § 9.2 (U D: C e 90 L3 9.: .l‘ g 85 _,- —— Face Matcher 2 _ E ------ Face Matcher 1 ,2 ------- Left Index Finger g 8 - *- Right Index Finger _ —0— Highest Rank Fusion —-9—- Hybrid Score-Rank Fusion 75 J 1 L l 1 5 10 15 20 25 Rank (m) Figure 4.1: Cumulative Match Characteristic (CMC) curve of highest rank fusion and the hybrid score-rank fusion rules on the NIST-Multimodal database (K = 4, N = 517) 119 25 $94 i n-o-o--o--o~o'st-‘>'4|>‘°‘°""""b 9 ' oic‘o‘o'o'o‘ g 92—' o--°“ ‘ I o“ C l ‘0" .g _10‘ 8 90 l: - E. “I .,.._..r-0‘*"' cc: 88: ,o—O"°".’._'. _ 2 l (*I...' IE 86: ,r‘“ ~ g l I" '-o-' Left lndex Finger g 84- i" ---0v--Right Index Finger I! - + - Highest Rank Fusion 8207 —o—Hybrid Score-Rank Fusion“ 80 ‘ ‘ ' l 1 5 10 15 20 Rank (m) Figure 4.2: Cumulative Match Characteristic (CMC) curve of highest rank fusion and the hybrid score-rank fusion rules on the NIST-Fingerprint database (K = 2, N = 6, 000). 120 known that the highest rank method works well when the number of users is large compared to the number of matchers [79], which is usually the case in biometric identification systems. This is because the highest rank method utilizes the strength of each matcher effectively. Even if only one matcher assigns a high rank to the correct user, it is still very likely that the correct user will receive a high rank after reordering. However, there can be up to K ties at rank 1 due to conflicting decisions output by the K matchers. Since the ties are broken randomly without considering the relative accuracies of the matchers, the identification rate of the highest rank method at ranks 1 to K -— 1 is not very high. In fact, the rank-1 accuracy of the highest rank method is usually less than the rank-1 accuracy of the best individual matcher. The recognition rates of the likelihood ratio based score fusion rule, the rank posterior fusion rule and the hybrid score-rank fusion rule were observed to be quite similar on all the three partitions of N IST-BSSRl. While the hybrid score-rank fusion rule achieves a marginal improvement in the recognition rates over the other two fusion rules, the differences in the recognition rates of the three fusion rules is less than 1% at all ranks. Therefore, only the performance of the hybrid score-rank fusion rule is reported in Figures 4.1, 4.2 and 4.3. In the case of the NIST-Multimodal database, the hybrid score-rank fusion rule provides 100% rank-1 accuracy, while the rank-1 accuracy of the best single matcher (right index finger) was only 93.7%. The hybrid score-rank fusion rule improves the rank-1 accuracy from 88.9% for the best single matcher (right index finger) to 94% on the NIST-Fingerprint database. Finally, on the NIST-Face database the improvement is comparatively lower (81.2% for the best 121 (O O) i 94» I ’? 92 " , . —u i: .9....o-o--o--o-—0‘°". .I‘ ‘5 90* of? a: 0 0.0.0 5 88 .. o--o~° ° “=- 0..o~°“° o g 86 .. _ 5 < ' o J 2 841-? o :4 _E 82 a". _.~° --°--- Face Matcher 2 _ {5, if 9’ ~0~ Face Matcher1 a: 804: ---+-- Highest Rank Fusion 1 78 —9— Hybrid Score—Rank Fusion 0 761 5 10 20 25 15 Rank (m) Figure 4.3: Cumulative Match Characteristic (CMC) curve of highest rank fusion and the hybrid score-rank fusion rules on the NIST-Face database (K = 2, N = 3, 000). 122 face matcher and 84.1% for the score-rank fusion rule) due to the strong correlation between the two face matchers. The results also indicate that the performance of the simplest rank level fusion scheme, namely, the highest rank method, is quite comparable to performance of the more complex score and rank fusion strategies for ranks greater than or equal to K, where K is the number of matchers. Therefore, in practical multibiometric identification systems with a large number of users, it may be sufficient to use the highest rank method if the goal is to retrieve the top few matches. However, if the best rank-1 accuracy is desired and if the match score information is available, then the hybrid score-rank fusion rule can be employed. 4.4 Summary While fusion in a multibiometric identification system is a more challenging problem due to the presence of large number of classes, we have shown that the likelihood ratio based fusion framework developed for a verification system can also be used for identification, provided the match scores of different users are assumed to be independent and identically distributed. We also proposed a scheme for rank level fusion in multibiometric identification that is based on converting the ranks into posterior probabilities. Furthermore, the rank posteriors can be directly combined with the posteriors obtained from the match score distributions to obtain a hybrid score-rank fusion rule. Finally, we have demonstrated that the proposed hybrid fusion rule consistently achieves high recognition rates at all ranks. 123 Chapter 5 Multibiometric Template Security One of the most potentially damaging attacks on a biometric system is against the biometric templates. Attacks on the template can lead to the following four vulnera- bilities: (i) A template can be replaced by an impostors’s template to gain unautho- rized access, (ii) a physical spoof can be created from the template (see [3,21, 171]) to gain unauthorized access to the system (as well as other systems that use the same biometric trait), (iii) the stolen template can be replayed to the matcher to gain unau- thorized access, and (iv) the templates can be used for cross-matching across different databases to covertly track a person without his/ her consent. Due to these reasons, biometric templates (or the raw biometric images) should not be stored in plaintext form and fool-proof techniques are required to securely store the templates such that both the security of the application and the users’ privacy are not compromised by adversary attacks. As shown in Chapters 3 and 4, multibiometric systems that fuse evidence from multiple biometric sources can provide significant improvement in the recognition accuracy. However, a multibiometric system requires storage of multiple 124 templates for the same user corresponding to the different biometric sources. Hence, template security is even more critical in multibiometric systems where it is essential to secure multiple templates of a user. Although a number of approaches such as feature transformation and biometric cryptosystems have been proposed to secure templates [199], these approaches have been proposed primarily to secure a single template. While it is possible to apply these template protection schemes to each individual template separately, such an approach is not optimal in terms of security. The following simple analogy illustrates why securing the individual templates separately is not the best approach. Consider an application that requires the user to enter two separate 4-digit personal identifica- tion numbers (PIN) that are verified independently to provide access. An adversary attempting to break such a system would require at most 104 attempts to guess each PIN. Since the PINs are verified independently, the maximum number of attempts needed to circumvent the system is only 2 x 104. On the other hand, if the applica- tion employs a single 8-digit PIN, the attacker would now need a maximum of 108 attempts to circumvent the system, which would require more effort than cracking two 4-digit PINS. Protecting the individual templates separately is equivalent to hav- ing a scheme requiring multiple smaller PINS, which is less secure than a scheme that stores the multiple templates as a single entity (analogous to single large PIN). In this chapter, we propose a unified scheme to secure multiple templates of a user in a multibiometric system by (i) transforming features from different biometric sources (e.g., fingerprint minutiae and iriscodes) into a common representation, (ii) performing feature-level fusion to derive a single multibiometric template, and (iii) 125 securing the multibiometric template using a single fuzzy vault construct [102]. We show that the proposed multibiometric template protection scheme has higher secu- rity and better recognition performance compared to the case where the individual templates are secured separately. We have developed a fully automatic implemen- tation of a multibiometric fuzzy vault that can handle the following scenarios (i) multiple samples (e.g., two impressions from the same finger), (ii) multiple instances (e.g., left and right index fingers) and (iii) multiple traits (e.g., fingerprint and iris). 5.1 Review of Template Protection Schemes Almost all the commercial biometric systems secure the stored templates by encrypt- ing them using standard cryptographic techniques. Either a public key cryptosystem like RSA [115] or a symmetric key cipher like ABS [1] is commonly used for template encryption. Since the above cryptosystems are generic, they can be directly applied to any biometric template and the encrypted templates are secure as long as the decryption key is secure. However, encryption is not a good solution for biometric template protection due to two main reasons. Firstly, encryption is not a smooth function and a small difference in the values of the feature sets extracted from the raw biometric data would lead to a very large difference in the resulting encrypted features. Recall that multiple acquisitions of the same biometric trait do not result in the same feature set (see Figure 1.3). Due to this reason, one cannot store a biometric template in an encrypted form and then perform matching in the encrypted domain. Hence, for every authentication attempt, (i) the template is decrypted, (ii) matching 126 is performed between the query and decrypted template and (iii) the decrypted tem- plate is then removed from memory. Thus, the template gets exposed during every authentication attempt. Secondly, the security of the encryption scheme depends on the decryption key. Hence, the decryption key needs to be securely stored in the system and if the key is compromised, the template is no longer secure. Because of these two reasons, standard encryption algorithms alone are not adequate for securing biometric templates and techniques that are designed to specifically account for the intra-user variability in the biometric data are needed. The template protection schemes proposed in the literature can be broadly clas- sified into two categories (see Figure 5.1), namely, feature transformation approach and biometric cryptosystem. Template Protection / (1/ Feature . . . Biometric Cryptosystem (Helper Data Methods) / // Salting Non-invertible Key Binding Key Generation (e.g., Biohashing) Transform , (e.g., Fuzzy Vault. (e.g., Secure Sketch- (9'9-- R°b“5t Hashing) Fuzzy Commitment) Fuzzy Extractor) Figure 5.1: Categorization of template protection schemes. 5.1.1 Feature Transformation In the feature transform approach, a. transformation function (f) is applied to the biometric template (T) and only the transformed template (7‘ (T; K )) is stored in 127 the database (see Figure 5.2). The parameters of the transformation function are typically derived from a random key (K) or a password. The same transformation function is applied to query features (Q) and the transformed query (f (Q; K )) is directly matched against the transformed template (.7 (T; K )) Depending on the characteristics of the transformation function f, the feature transform schemes can be further categorized as salting or non-invertible transfonns. In salting, .7: is invertible, i.e., if an adversary gains access to the key and the transformed template, she can recover the original biometric template (or a close approximation of it). Hence, the security of the salting scheme is based on the secrecy of the key or password. On the other hand, non—invertible transformation schemes typically apply a one-way function on the template and it is computationally hard to invert a transformed template even if the key is known. Enrollment Authentication ‘ RQ'K) Transform F Matching . . . Key (K) Transformed l Biometric Biometnc Template Key (K) Query (Q) Template (T) RT.K) Match! Non-match Figure 5.2: Authentication mechanism when the biometric template is protected using a feature transformation approach. An example of salting approach is the random multi—space quantization technique proposed by Teoh et al. [187]. In this technique, the authors first extract the most dis— 128 criminative projections of the face template using the Fisher discriminant analysis [5] and then project the obtained vectors on a randomly selected set of orthogonal direc- tions. This random projection defines the salting mechanism for the scheme. Similar biohashing schemes have been proposed for iris [38] and palmprint [43] modalities. An- other example of salting is the cancelable face filter approach proposed in [174] where user-specific random kernels are convolved with the face images during enrollment and authentication. Non-invertible transformation functions have been proposed for fingerprint [158] and face [188] modalities in the literature. 5.1.2 Biometric Cryptosystems Biometric cryptosystems [22,198] were originally developed for the purpose of either securing a cryptographic key using biometric features or directly generating a cryp— tographic key from biometric features. However, they can also be used as a template protection mechanism. In a biometric cryptosystem, some public information about the biometric template is stored. This public information is usually referred to as helper data and hence, biometric cryptosystems are also known as helper data-based methods [199]. While the helper data does not (is not supposed to) reveal any signifi- cant information about the original biometric template, it is needed during matching to extract a cryptographic key from the query biometric features. Matching is per- formed indirectly by verifying the validity of the extracted key (see Figure 5.3). Error correction coding techniques are typically used to handle intra-user variations. Biometric cryptosystems can be further classified as key binding or key generation 129 systems depending on how the helper data is obtained. When the helper data is obtained by binding a key (that is independent of the biometric features) with the biometric template, we refer to it as a key-binding biometric cryptosystem. Note that given only the helper data, it is computationally hard to recover either the key or the original template. Matching in a key binding system involves recovery of the key from the helper data using the query biometric features. If the helper data is derived only from the biometric template and the cryptographic key is directly generated from the helper data and the query biometric features, it leads to a key generation biometric cryptosystem. Extracted fl Validity Match/ Key (K) Check Non-match Helper Data Extraction - Recovery Helper Data Blometrlc H = F (T) B' tri Template (T) Qlomemc) uery Enrollment Authentication Figure 5.3: Authentication mechanism when the biometric template is secured using a key generation biometric cryptosystem. Authentication in a key—binding biometric cryptosystem is similar except that the helper data is a function of both the template and the key K, i.e., H = J:(T; K). A number of template protection techniques like fuzzy commitment [103], fuzzy vault [102], shielding functions [194] and distributed source coding [56] can be consid- ered as key binding biometric cryptosystems. Other schemes for securing biometric 130 templates such as the ones proposed in [51,76,105, 137,138] also fall under this cat- egory. The fuzzy vault scheme proposed by Juels and Sudan [102] has become one of the most pOpular approaches for biometric template protection and its implemen- tations for fingerprint [41,42, 141, 196,209], face [62], iris [117] and signature [68] modalities have been proposed. Recently, multibiometric fuzzy vaults based on mul- tiple fingers [210] and fingerprint and voice [19] have also been proposed. Direct cryptographic key generation from biometrics is an attractive proposition, but it is a difficult problem because of the intra-user variability. Early biometric key generation schemes such as those by Chang et a1. [28] and Veilhauer et al. [200] em- ployed user-specific quantization schemes. Information on quantization boundaries is stored as helper data, which is used during authentication to account for intra- user variations. Dodis et a1. [55] introduced the concepts of secure sketch and fuzzy extractor in the context of key generation from biometrics. The secure sketch can be considered as helper data that leaks only limited information about the template (measured in terms of entropy loss), but facilitates exact reconstruction of the tem- plate when presented with a query that is close to the template. The fuzzy extractor is a cryptographic primitive that generates a cryptographic key from the biometric features. Dodis et a1. [55] proposed secure sketches for three different distance metrics, namely, Hamming distance, set difference and edit distance. Li and Chang [120] introduced a two-level quantization based approach for obtaining secure sketches. Sutcu et al. [185] discussed the practical issues in secure sketch construction and proposed a secure sketch based on quantization for face biometric. The problem of 131 generating fuzzy extractors from continuous distributions was addressed by Buhan et al. in [16]. Secure sketch construction for other modalities such as fingerprints [4,23], 3D face [214] and multimodal systems (face and fingerprint) [186] have also been proposed. Protocols for secure authentication in remote applications [14,17] have also been proposed based on the fuzzy extractor scheme. Some template protection techniques make use of more than one basic approach (e.g., salting followed by key—binding). We refer to such techniques as hybrid schemes. Template protection schemes proposed in [13,145,183,184] are examples of the hy- brid approach. A brief summary of the various template protection approaches is presented in Table 5.1. Apart from salting, none of the other template protection schemes require any secret information (such as a key) that must be securely stored or presented during matching. The template protection schemes described in Table 5.1 have their own advantages and limitations in terms of template security, computational cost, storage require- ments, applicability to different kinds of biometric representations and ability to han- dle intra-class variations in biometric data [198]. In this thesis, we focus on a specific biometric cryptosystem known as fuzzy vault and present (i) a fully automatic im- plementation of a minutiae-based fingerprint fuzzy vault where high curvature points derived from the orientation field are used to align the template and query minutiae, (ii) an iris cryptosystem based on the fuzzy vault framework to secure iriscode tern- plates, and (iii) a multibiometric vault framework to secure multiple templates of a user in a multibiometric system as a single entity. 132 Table 5.1: Summary of different template protection schemes. Here, T represents the biometric template, Q represents the query and K is the key used to protect the template. In salting and non-invertible feature transform, .7: represents the trans- formation function and M represents the matcher that operates in the transformed domain. In biometric cryptosystems, .7: is the helper data extraction scheme and M is the error correction scheme that allows reconstruction of the key K. Approach What imparts se- What entities are How are intra-user curity to the tem- stored? variations handled? plate? Salting Secrecy of key K Public domain: Quantization and Transformed tem— matching in trans- plate .7: (T; K ) formed domain Secret: Key K M(.7-'(T; K), .7-"(Q; K)) Non- N on—invertibility of Public domain: Matching in trans- invertible the transformation Transformed tem- formed domain transform function .7: plate .’F (T; K ), key M(f (T; K ), .7: (Q; K )) K Key-binding Level of security Public domain: Error correction and biometric depends on the Helper Data user specific quantiza- cryptosystem amount of infor- H = .7: (T; K ) tion mation revealed by l K = M(.7:(T; K), Q) the helper data H Key- Level of security Public domain: Error correction and generating depends on the Helper Data user specific quantiza- biometric amount of infor— H = .7: (T) tion cryptosystem mation revealed by K = M(}' (T), Q) the helper data H 133 5.2 Fuzzy Vault Fuzzy vault is a cryptographic construct that is designed to work with biometric features represented as an unordered set (e.g., minutiae in fingerprints). The security of the fuzzy vault scheme is based on the infeasibility of the polynomial reconstruction problem, which is a special case of the Reed-Solomon list decoding problem [11]. The fuzzy vault scheme works as follows (see Figure 5.4). Suppose that a user wishes to protect his biometric template, which is represented as an unordered set X, using a secret K (e.g., a cryptographic key). Here, unordered set implies that all the elements in the set are unique and the order in which the elements of the set are listed is irrelevant. Note that this is true for minutiae representation of fingerprints. The user selects a polynomial P that encodes the secret K in some way and evaluates the polynomial on all the elements in X. The user then chooses a large number of random chaff points that do not: lie on the polynomial P. The entire collection of points consisting of both points lying on P and those that do not lie on P constitute the vault V. The purpose of adding the chaff points is to conceal the points lying on P from an attacker. Since the points lying on P encode the complete information about the template X and the secret K, concealing these points secures both the template and the secret simultaneously. The user authentication based on the vault V proceeds as follows. Let the query be represented as another unordered set X I. If X I overlaps substantially with X, then the user can identify many points in V that lie on the polynomial P. If a sufficient number of points on P can be identified, an error correction scheme can be applied to 134 exactly reconstruct P and thereby decode the secret K. If a valid secret is decoded, the authentication is deemed to be successful. If X I does not overlap substantially with X, then it is infeasible to reconstruct P and the authentication is unsuccessful. Since the authentication can be successful even when X and X I are not exactly the same, this scheme is referred to as a fuzzy vault. The steps involved in creating the vault from the user’s biometric template and the secret (vault encoding) are presented in Algorithm B.1 (see Appendix). All op- erations in this algorithm are carried out over a field 1:. The algorithm has three parameters, namely, n, r and 3. Here, r depends on the number of features that can be extracted from a user’s biometric template (e.g., number of minutia points in the user’s fingerprint). The parameter 3 represents the number of chaff points that are added to the vault and this parameter influences the security of the fuzzy vault construction. If no chaff points are added, the vault leaks the information about the template and the secret. As more chaff points are added, the security of the vault increases. The degree of the polynomial, n, controls the tolerance of the system to errors in the biometric data during decoding. For example, n determines the mini- mum number of matching minutiae required for successful vault decoding. A larger 77. requires more number of minutiae matches. The function ENCODESECRET(K) constructs a polynomial P of degree n in variable x such that P encodes the secret K uniquely, i.e., given P, we should be able to get back the secret K. A simple method to construct such a polynomial is to embed the secret in the coefficients of P. The function PERMUTEU/I) randomly reorders the elements in V, to obtain the vault V. 135 Polynomial ' Key Evaluation ‘ Vault [5234] .° . o o o °°o P(X)= ‘ 000° 0 0 0° 5x3+2x2+ 3x+ 4 0° ' r 9, f I E Fingerprint 1‘“ ‘ a - . Sensor Template Template Generation of Image Minutiae Charr Points (8) Polynomial Reconstruction 0 0 P(X)= 5x3+ 2x2+ 3x+ 4 ~ I Recovered Key '1 y 5234 9, r 1 2" i \ Fingerprint ' - .- - - ' ‘ . ,- Sensor Query Query Image Minutiae (b) Figure 5.4: Schematic diagram of the fuzzy vault scheme proposed by Juels and Sudan [102] based on fingerprint minutiae. (a) Vault encoding and (b) vault decoding. 136 Algorithm 8.3 (see Appendix) presents the steps involved in retrieving the secret from the vault based on the user’s biometric query (vault decoding). The output of this algorithm is either the secret K or a value null indicating that the authentication is unsuccessful. The function RSDECODE(L’) is a (r, n) Reed-Solomon decoding algorithm [7], which searches for a polynomial P of degree n such that P (a2) = b; for more than 1321’ values of (a2, b1) 6 L’. The RSDECODE function either outputs a polynomial P that satisfies the above conditions or a value null indicating that no such polynomial exists. The function DECODESECRET(p) is the inverse of the ENCODESECRET function and it reconstructs the secret K from the polynomial P. The vault decoding algorithm successfully retrieves the secret K if the number of errors (e.g., non-matching minutiae) in the biometric data (IX — X I]) 1 is less than (153). This ability to deal with intra—class variations in the biometric data, along with its ability to work with unordered sets, makes the fuzzy vault scheme a promising solution for biometric cryptosystems, particularly for fingerprints. 5.2.1 Fuzzy Vault Implementation Since the introduction of the fuzzy vault scheme by Juels and Sudan, several re- searchers have attempted to implement it in practice for securing biometric tem- plates. Clancy et a1. [42] proposed a fuzzy vault scheme based on the location of minutia points (row and column indices in the image) in a fingerprint. They assumed that the template and query minutiae sets are pre—aligned, which is not a realistic 1The notation [A] denotes the number of elements in a set A. 137 assumption in practical fingerprint authentication systems. Further, multiple (four) fingerprint impressions of a user were used during enrollment for identifying the reli- able minutia points. The error correction step was simulated without being actually implemented. The False Reject Rate of their system was approximately 20-30% and they claimed that retrieving the secret was 269 times more difficult for an attacker than for a genuine user. The fingerprint-based fuzzy vault proposed by Yang et al. [209] also used only the location information about the minutia points. Four impressions were used during enrollment to identify a reference minutia, and the relative position of the remaining minutia points with respect to the reference minutia was represented in the polar coordinate system. This scheme was evaluated on a small database of 10 fingers and a FRR of 17% was reported. Chung et al. [41] proposed a geometric hashing technique to perform alignment in a minutiae-based fingerprint fuzzy vault. A modified fuzzy vault scheme was used for designing an asymmetric cryptosystem in [141]. Fuzzy vault implementations based on other biometric modalities such as face [62] and handwritten signature [68] have also been proposed. Uludag et al. [197] introduced a modification to the fuzzy vault scheme, which eliminated the need for error correction coding. Uludag and Jain [196] also prOposed the use of high curvature points derived from the fingerprint orientation field to automatically align the template and query minutiae sets. Our fingerprint-based fuzzy vault implementation [144] extends the ideas presented in [197] and [196] in order to achieve better performance on public-domain fingerprint databases. 138 5.3 Proposed Fingerprint-based Fuzzy Vault We first propose a fuzzy vault implementation based on fingerprint minutiae. We use both the location and orientation attributes of a minutia point in our fuzzy vault implementation. These attributes are represented as a 3-tuple (u,v,0), where u indicates the row index in the image (1 S u S U), 1) indicates the column index (1 S u S V) and 6 represents the orientation of the minutia with respect to the horizontal axis (1 S 0 S 360). The algorithm presented in [87] is used for minutiae extraction. We have implemented a modified version of the fuzzy vault construction that was proposed by Uludag et al. [197]. This modified fuzzy vault scheme does not require error correction coding. Instead, several candidate sets of size (n + 1) (where n is the degree of the polynomial which encodes the secret) are generated from the unlocking set L, and polynomials are reconstructed using Lagrange interpolation. This method gives rise to several candidate secrets and Cyclic Redundancy Check (CRC) based error detection technique is used to identify the correct polynomial and hence decode the correct secret. The main advantage of this scheme is its increased tolerance to errors. Since only (n + 1) points are required to uniquely determine a polynomial of degree n, this scheme can retrieve the secret K when the number of errors (IX — X I] = [L - LII) is less than (r—n), i.e., it can tolerate twice the number of errors as the original fuzzy vault scheme. However, this method has a higher computational cost because it requires a large number of polynomial interpolations. Our fingerprint-based fuzzy vault implementation differs from the implementation 139 in [197] and [196] in the following aspects. 1. In our implementation, we apply a minutiae matcher [87] during decoding to account for non-linear distortion in fingerprints whereas in [196], the minutia location information is coarsely quantized to compensate for distortion. Since deformation of the fingerprint ridges increases as we move away from the center of the fingerprint area towards the periphery, uniform quantization alone, as used in [196], is not sufficient to handle distortion. The minutiae matcher used in our implementation [87] employs an adaptive bounding box that accounts for distortion more effectively. This is one of the main reasons the proposed approach leads to a significant improvement in the genuine accept rate (CAR). 2. Only the location of minutia points was used for vault encoding in [196]. We use both minutia location and orientation attributes, which increases the number of chaff points that can be added because we can now add a chaff point whose location is close to a true minutia but with a different direction. Chang et a1. [24] have shown that the number of possible chaff points affects the security of the vault. Hence, using both minutia location and orientation makes it more difficult for an attacker to decode the vault. At the same time, when a genuine user attempts to decode the vault, it is easier to filter out chaff points from the vault because it is less probable that a chaff point will match with a query minutia in both location and direction. This reduces the decoding complexity by eliminating most of the chaff points from the unlocking set. 3. We use local image quality index estimated from the fingerprint in order to select 140 the most reliable minutiae for vault encoding and decoding. In [197], minutiae selection was based on the value that is assigned to the minutiae in the field .7, which does not have any relation to the minutiae reliability. Our minutiae selection method is also more efficient than the one used in [42] where multi- ple fingerprint impressions were needed to determine reliable minutiae during encoding. 4. Although our alignment technique is similar to the one proposed in [196], we have made significant changes to the curvature estimation and alignment steps compared to [196], which results in a more accurate alignment between the template and query. 5.3. 1 Vault Encoding Figure 5.5 shows the block diagram of the proposed J S fuzzy vault encoding scheme. The field used for constructing the vault is .77 = GF(216). We use the Galois field, .7: = GF(216), for constructing the vault. The specific field GF(216) was chosen because it offers a sufficiently large universe (number of elements in the field) to ensure vault security [55] and is computationally convenient for the fuzzy vault application. The vault encoding process consists of the following eight steps. 1. Given the template fingerprint image T, we first obtain the template minutiae set MT = [min]: 1], where NT is the number of minutiae in T. The local quality index proposed in [32] is used to estimate the quality of each minutia in T. Let q (mgr) be the quality of the ith minutia and qT = {q (Th?) )1]: 7; 141 , Fingerprint . CM Chaff Pomt 7 , W) , L M-nutiae X, Y _olynomial V = (X P(X)) U ( Y 2) Minutiae .ncoding _rojection Extraction & M cl Mi-utiae 7 List Quali .election Estimattibn Scrambling # CRC K' Polynomial Secret K Codin j ’[P Encoding Vault V= (A.B) Helper Data Template Extraction Helper Data H T Figure 5.5: Proposed implementation of vault encoding. be the quality set corresponding to minutiae set M T. We also extract the high curvature points H T from the template image to be used for alignment during decoding. The details of extraction of high curvature points are presented in Section 5.3.3. 2. Since only r genuine minutiae points are required to construct the vault, we apply a minutiae selection algorithm to the template minutiae set M T. This selection algorithm first sorts the minutiae based on their quality and then se- quentially selects the minutiae starting with the highest quality minutia. More— over, the algorithm selects only welI-separated minutiae, i.e., the minimum dis- tance between any two selected minutia points is greater than a threshold 61. The distance, D M, between two minutia points m,- and mj is defined as DMfmi'flnj) = (Ur r "302 + (W — Uj)2 + fiMszflj) (5-1) 142 where A(6.,-,6j) = min ([6,- — 63-],360 — [6,- — 6J-I) and 5M is the weight as- signed to the orientation attribute (set to 0.2 in our experiments2). Selection of well-separated minutiae ensures that they are assigned unique values when they are encoded into the field .77. Let SM T = {minim denote the selected minutiae set. Note that if the number of minutia points in T is less than r, or if the selection algorithm fails to find r well-separated minutiae, we consider it as a failure to capture (FTC) error and no further processing takes place. . The chaff point set CM = {mghsml is generated iteratively as follows. A chaff point m = (u,v,6) is randomly chosen such that u E {1, 2, . -- ,U}, u 6 {1,2, - -- ,V} and 6 6 {1,2, - -- ,360}. The new chaff point is added to CM if its minimum distance (as defined in equation (5.1)) to all the points in the set SMT U CM is greater than 61. . The minutia attributes u, u, and 6 are quantized and represented as bit strings of length Bu, EU and By, respectively. If Bu, BU and 139 are chosen such that they add up to 16, we can obtain a 16—bit number by concatenating the bit strings corresponding to u, v, and 6. Using this method, minutia points are encoded as elements in the field .7: = CF(216). Let X = {xj};=1 and Y = {yk}z=1 be the encoded values of selected template minutiae and chaff points, respectively, in the field .7. 2Since the variation in the orientation attribute of a minutia point is usually much larger compared to the variation in its location attribute, the orientation difference is assigned a smaller weight than the Euclidean distance between the minutiae locations. The specific value of 0.2 for [3M was determined empirically as a tradeoff between eliminating as many chaff points as possible from the unlocking set while retaining as many genuine points as possible. The above tradeoff also determines the value of the threshold 62 used in decoding. 143 5. Our scheme is designed to work with a secret key K of length 16n bits, where n is the degree of the encoding polynomial. We append a 16—bit CRC code to secret K to obtain a new secret K I containing 16(n + 1) bits. The generator polynomial C(w) = w16 + 1015 + w2 + 1, which is commonly known as IBM CRC-16, is used for generating the CRC bits. I 6. The secret K is encoded into a polynomial P of degree n in .7 by partitioning it into (n + 1) 16—bit values c0, c1, . -- , on and considering them as coefficients of P, i.e., P(x) = our" + - - - + CO- 7. The polynomial P is evaluated at all the points in the selected minutiae set X to obtain the set P(X) = {P(zj)};:1. The corresponding elements of the sets X and ’P(X) form the locking set L = {(3.-Trap) §=,. A set 2 = {2k};=, is obtained by randomly selecting values zk E .77 such that the points (yk, zk) do not lie on the polynomial P, i.e, Zk 75 P(yk), V ,k = 1,2, - u ,s. The chaff set is defined as C = {(yk,zk)}i=1. The union of locking and chaff sets is denoted as V’. 8. The elements of V, are randomly reordered to obtain the vault V, which is represented as V = {(ai, b,)}§=1, where t = r + 3. Only the vault V and the high curvature points HT are stored in the system. 5.3.2 Vault Decoding The process of decoding the vault consists of the following steps (see Figure 5.6). 144 Fingerprint query (0) Vault v= (A,B) i q° Minutiae *i 7 T7" Quality Alignment ’ Interpolation Decoding Estimation Helper Data H T Helper Data _>Query Helper Extractlon Data H° [ Template (a) Vault V= (A,B) ‘v A Minutiae MV Coarse SMV Remove Minutiae . Decoding Filter C Without we» L A Correspondences Selected Query Minutiae SM 0 (b) Figure 5.6: Proposed implementation of vault decoding. (a) Block diagram of the complete decoding process and (b) details of the filter used to eliminate the chaff points. 145 . Given the query fingerprint image Q, we obtain the query minutiae set M Q = {rn-Q}NQ1 and the high curvature points H Q The quality of each minutia in Q is estimated and the quality set qQ — {q (m? )}NQ1 corresponding to M Q is obtained. . The alignment algorithm described in Section 5.3.3 is applied and the aligned query minutiae set M AQ = {m ZAQHEQ _1 is obtained. . A minutiae selection algorithm is applied to select r minutiae from the set M AQ based on their quality. The selected minutiae SM Q —{miQ}; ___1 are well-separated in the sense that the minimum distance (as defined in equation (5.1)) between any two selected minutiae is greater than 61. If N Q < r or if the number of well-separated query minutiae is less than r, it is considered as failure to capture (FTC) and no further processing takes place. . The selected query minutiae are used to filter the chaff points in the vault as follows (see Figure 5.6(b)). The abscissa values of the points in the vault, i.e., A = {Gilt-:1: are first represented as 16—bit strings. The 16—bit strings are partitioned into three strings of lengths Bu, By and 80 which are then converted into quantized minutia attribute values u, u and 6. Thus, we obtain the set MV = {Trill-f = (ui,vi,6,-)}‘z?=l. . The ith element of the set M V is marked as a chaff point if the minimum distance between the point my 9 m J E S M Q is greater than a threshold 62. We refer to this process as a coarse E M V and all the selected minutiae in the query 146 filter and it filters out a significant proportion of the chaff points (approximately 80%). Let S A! V = {mg} 113/:1 be a subset of M V containing only those elements that are not marked as chaff. Here, N V is the number of points in M V that are not marked as chaff and N V << 8. At this stage, a minutiae matcher [87] is applied to determine the corresponding pairs of minutiae in the sets S M V and S M Q. Let VIQ denote the set of correspondences and let r, be the number of correspondences. Since the size of the selected query minutiae set is r, we have 0 g r, S r because each query minutiae can have no more than one corresponding minutia in Shiv. Note that it is also possible to directly apply the minutiae matcher to find correspondences between M V and SM Q without any coarse filtering. However, such a method is not effective because the presence of a large number of chaff points in the vault leads to a number of false correspondences. Hence, the coarse filter step is essential before the minutiae matcher is applied. . Only those elements of V that are contained in SM V and which have a corre- I sponding minutia in SM Q are added to the unlocking set L . The unlocking I I set is represented as L, = {(a;,bi)}:___1, where (al- bl.) = (aj,bj) if aj has a i’i corresponding minutia in S M Q. . To find the coefficients of a polynomial of degree n, (n + 1) unique projections are necessary. If r, < (n + 1), it results in authentication failure. Otherwise, we consider all possible subsets L” of size (n + 1) of the unlocking set L, and, for each subset, we construct a polynomial P* by Lagrange interpolation. If 147 II I I L = {(ai’ bi) ”1:11 is a specific candidate set, P*(:r) is obtained as I I P*(a:) = (Ix—a;)(a:—a )---(;r—a,n+1) I I I I I (“1 ’ “2)(“1 — “3) ’ ' ‘ (“1 ‘ “n+1) I b1+... (x-a’1) I I I I I I bn+1 (5'2) (“n+1 — “1)(an+1 — “2) ' ' ' (“n+1 ‘ an) The above operations result in a polynomial P* (:13) = Caz" + c;_1xn_1 + - - - + c6. 8. The coefficients c3, ci‘, - . - ,c; of the polynomial P* are 16-bit values which are concatenated to obtain a 16(n + 1)-bit string K * and CRC error detection is applied to K *. If an error is detected, it indicates that an incorrect secret has been decoded and we repeat the same procedure for the next candidate set L”. If no error is detected, it indicates that K * = K I with very high probability. In this case, the 16—bit CRC code is removed from K * and the system outputs the secret K, which indicates a successful match. 5.3.3 Alignment based on High Curvature Points The first step in matching two fingerprint images is to apply an alignment (regis— tration) algorithm that can remove translation, rotation and possibly any non-linear distortion between the two images and determine the area of overlap. Although align- ing two fingerprints is a difficult problem in any fingerprint authentication system, it is particularly more difficult in a biometric cryptosystem like fuzzy vault. This is 148 because the original fingerprint template is not available during authentication and only a transformed version of template is available in the vault. Previous implementations of fingerprint-based fuzzy vault either assumed that the template and query fingerprint images are pre-aligned [42] or used a reference point (e.g., core point [161] or a reference minutia point [209]) for alignment. Though alignment based on a reference point is simple and computationally efficient, it is difficult to determine the reference point reliably. Even a small error in locating the reference point could lead to a false reject. To avoid this problem, Uludag and Jain [196] proposed the use of additional information derived from the fingerprint image to assist in alignment. While this additional data should carry sufficient information to accurately align the template and query images, it should not reveal any information about the template minutiae used for constructing the vault because any such leakage would compromise the security of the vault. Uludag and Jain derived the alignment data from the fingerprint orientation field. In particular, points of high curvature were used as the alignment data in [196] and an Iterative Closest Point (ICP) algorithm was used to determine the alignment between the template and the query based on this alignment data. Our proposed alignment scheme is similar to the one presented in [196] with some modifications. Extraction of High Curvature Points An orientation field flow curve [47] is a set of piecewise linear segments whose tan- gent direction at each point is parallel to the orientation field direction at that point. Although flow curves are similar to fingerprint ridges, extraction of flow curves is 149 not affected by breaks and discontinuities, which are commonly encountered in ridge extraction. Points of maximum curvature in the flow curves along with their cor- responding curvature values constitute the alignment data in our implementation. Therefore, the algorithm for extraction of high curvature points (see Figure 5.7) con- sists of four steps: (i) orientation field estimation, (ii) extraction of flow curves, (iii) determination of maximum curvature points and (iv) clustering of high curvature points. Let I be a fingerprint image with U rows and V columns. A robust estimate of the orientation field for the given fingerprint image is obtained using the algorithm described in [46]. Let 6 = (A,u) be a point in I, where 1 S /\ S U and 1 S a S V. Let 453 be the orientation of the ridge flow with respect to the horizontal axis in the neighborhood of 6. Let 03 = (cos (basin (by) be the unit orientation vector at 6. A flow curve with starting point [0 E I can be defined iteratively as é’j =(j-1 +P'7‘0€j_1: (5-3) for j = 1,2, - -- ,J. Here, ,0 = {—1,+1} defines the flow direction from €j_1 to 63-, 7 is the length of the line segment from [j—l to £3- and Ogj._1 is the unit orientation vector at the point €j_1. The process of tracing a flow curve is terminated when (i) the boundaries of the image are reached or (ii) J exceeds a certain pre—defined threshold Jmax- The parameter 7 determines the sampling interval of the flow curve and is set to 5 pixels in our experiments. Each starting point 60 generates two curve + J segments {63‘ } i=1 J— and {67—} 1 in opposite directions corresponding to p = +1 J: 150 228 155 1.57 228 157 1.55 226 159 1.46 318 40 0.77 316 37 0.76 317 43 0.75 Orientation Field Flow Curves High Curvature Points Helper Data Figure 5.7: Algorithm for extraction of high curvature points. and p = —1, respectively. The maximum number of samples in each curve segment, Jmam, is set to 150. The two curve segments are then merged to get the complete flow curve, which is represented as a set of points {63- }:,:1, where J, = J+ + J _. By repeating this procedure with different starting points (0 E I , we obtain a set of flow curves. Midpoints of the ridges in the thinned fingerprint image and points in whose neighborhood the orientation field changes significantly are chosen as the starting points. The curvature (w) of a point €3- in a flow curve is defined as we], = 1 — cos agj, where are]. is the angle between the vectors that are tangent to the flow curve at the points €j_T and €j+T, for all r S j S J, — r. The parameter r is related to the sampling interval of the flow curve ('7) and is set to 5. The value of cos agj can be easily computed from the orientation field as cos (13]. = (pj_TOgj_T) =0: (pj+TOgj+T), where pj_.,. is the flow direction from €j_7. to (j, Pj+r is the flow direction from 151 l’ j to 63-.” and * indicates dot product. The value of tag]. is minimum (zero) when there is no change in direction as we go from gj—r to €j+r through E]- and it attains its maximum value of 2 when the change in direction is It. For each flow curve, the curvature values for the points in the curve are estimated and local maxima in the curvature are detected. If the value of the local maximum is greater than a threshold 0 (set to 0.3), then the point is marked as a high curvature point and the 3—tuple h = (A, raw), where (A, u) is the location and w is the curvature value, is added to the alignment data set H. Figure 5.8 shows the procedure for curvature estimation at a point and a trace of the curvature values for a sample flow curve. The process of determining the maximum curvature points is repeated for all the flow curves, and the final alignment data set for the image 1' is obtained as HI = {hfiff 1, where R1 is the number of high curvature points in I. High curvature points usually tend to occur near the singular points (core and delta) in a fingerprint image. If the image has more than one singular point, the points in the alignment data set may have many clusters. Hence, a single-link clustering algorithm is applied to cluster the elements of the alignment data set based on the location of the points. The proposed alignment data extraction scheme differs from the one proposed in [196] mainly in the definitions of curvature and local maxima in the curvature. The proposed definition of curvature leads to a smooth estimate of curvature with distinct local maxima. Further, unlike [196] where a single point having the maximum curvature is selected as the high curvature point, we apply a robust local maxima detection algorithm and utilize all the locally maximum points. This leads to better alignment data extraction for some types of fingerprint images such as whorls because 152 (a) 1.6 1.4 ' 1.2 ' 0.8 - 0.6 0.4 . 0.2 . Curvature 0 1o 20 so 40 so so 70 Point Index A Sample Flow Curve Curvature Trace along the Flow Curve (b) Figure 5.8: Determination of maximum curvature points. (a) Curvature estimation at point 6]- and (b) trace of curvature for a sample flow curve along with the local maximum. 153 the flow curves near the core region of whorls generally tend to have more than one high curvature point (one above the core and one below the core). Alignment using ICP Let T and Q be the template and query fingerprint images, respectively. Let H T = {hi-Thfiq; and H Q = {hgf2}f__c_21 be the alignment data sets obtained from T and Q, respectively. Let M Q = {m§?}§V=Ql be the query minutiae set, where N Q is the number of minutia points in Q. The goal of the alignment scheme is to find a rigid transformation F that closely aligns M Q with the template minutiae set M T based on the alignment data sets H T and H Q. Note that the template minutiae set M T is not available during alignment and only H T is known. We use the Iterative Closest Point (ICP) algorithm proposed by Besl and McKay [8] to align H T and H Q and estimate the rigid transformation F. The ICP algorithm to align the template and query alignment data sets is shown in the appendix as Algorithm B1 In this algorithm, the function INITTRANS (HT,HQ) estimates an initial transformation between H T and H Q by aligning the center of mass of the points in H T and H Q. The weighted distance, D H, between two high curvature points h,- and hj is defined as DHUI’i’ hj) = \/()‘i — A392 + (M — #j)2 + filez‘ — wt (54) where [3 H weights the relative contribution of the Euclidean distance between the points (first term) and the difference in curvature (second term). The parameter 154 6 H is set to 100 in our experiments. The function TRANS (H TlQ, H Q) computes the transformation F I that minimizes the mean squared Euclidean distance between the locations of the corresponding points in H TlQ and H Q. Algorithm B1 is run until convergence or until a maximum number of iterations (kmax) is reached. The algorithm is said to converge if the change in the mean weighted distance (M WD) between the paired points is less than a threshold (Dstop)- The values of kmam and Dstop are set to 200 and 0.01, respectively. When the template and query images overlap only partially, it is possible that the overlap between the template and query alignment data sets is also partial. In such cases, all the high curvature points in the query may not have a corresponding point in the template. Algorithm B.1 strictly assigns a correspondence between every high curvature point in the query and the template, and this may lead to alignment errors when the overlap between the two sets is partial. To overcome this problem, we use the trimmed ICP algorithm [35], which basically ignores a proportion of the points in the query alignment data set whose distance to the corresponding points in the template alignment data set is large, i.e., we ignore the query points with large values of DH (hle, h?) The proportion of points to be ignored is found by minimizing an objective function (see [35] for details). The trimmed ICP algorithm is also robust to outliers in the alignment data sets. Based on the rigid transformation F output by the ICP algorithm, we align the query minutiae set M Q with the template. Let 1% AQ = F (ll/IQ) = {meg-Vle represent the query minutiae set after alignment. Figure 5.9 shows an example of 155 successful minutiae alignment based on high curvature points and trimmed ICP al- gorithm. In Algorithm 8.1, it is assumed that both the alignment data sets HT and H Q have only a single cluster. If the number of clusters in HT and/or H Q is more than one, then the algorithm is repeated for all possible cluster pairs. In this scenario, there will be multiple aligned query minutiae sets. We select the aligned I query minutiae set that gives the largest unlocking set L . 5.4 Proposed Iris Cryptosystem The most common representation scheme used for matching iris images is the iriscode representation developed by Daugman [50]. The iriscode features are obtained by dernodulating the iris pattern using quadrature 2D Gabor wavelets. In order to account for the variations in the pupil dilation, iris size and rotation, the rubber sheet model [50] is used to normalize the Gabor responses. The phase information in the resulting Gabor responses is then quantized into one of the four quadrants to produce a two—bit code for each local region. When the iris pattern is sampled at R different radii and 3 different angles, a N-bit iriscode sequence is generated, where N = (2 x R x S) We use the algorithms described in [177] for pre-processing, segmentation and extraction of iriscodes from the iris images. We now propose an iris cryptosystem to secure iriscode templates. Since the iriscode is a fixed length binary vector in which the relative order information between the bits is essential for matching, we cannot secure the iriscode directly using the fuzzy vault framework. To overcome this problem, we construct the iris cryptosystem in 156 Figure 5.9: An example of successful minutiae alignment based on high curvature points and ICP algorithm. (a) Template image with minutiae and high curvature points, (b) query image with minutiae and high curvature points (c) template and overlaid query minutiae prior to alignment and ((1) template and overlaid query minu- tiae after alignment. In this figure, the template minutiae are represented as squares (tails indicate the minutia direction) and the query minutiae are represented as cir— cles. The template and query high curvature points are represented as asterisks and diamonds, respectively. 157 two steps (see Figure 5.10). In the first step, we apply a salting (invertible) transform to the iriscode template based on a randomly generated transformation key. Since the transformation is invertible, the security of the transformed iriscode template relies on the security of the transformation key. Hence, in the second step, we represent the transformation key as an unordered set and secure it using the fuzzy vault construct. Both the transformed iriscode template and the vault that embeds the transformation key constitute the helper data in this iris cryptosystem. The proposed iris cryptosystem has two main advantages. Firstly, the salting step can be considered as a feature transformation function that converts a fixed length binary vector into an unordered set. This enables us to secure diverse biometric tem- plates such as fingerprint minutiae and iriscode as a single multibiometric fuzzy vault. Moreover, both the salting and fuzzy vault steps can account for intra-user variations in the iriscode template. Due to the presence of two layers of error correction, the proposed iris cryptosystem allows larger intra—user variations in the iriscode template and hence, provides a high genuine accept rate. 5.4.1 Helper Data Extraction The schematic diagram of helper data extraction scheme in the proposed iris cryp- tosystem is shown in Figure 5.10(a). The salting transform consists of two operations, namely, BCH encoding [122] and an exclusive-or operation. Let H be a (M I, M K) BCH encoding function, which takes a message K of length Ill/I K (1M K < llfl) and appends (ll/I I — ll/IK) error correcting symbols to it in order to generate a codeword 158 Template Image Helper Data Extraction [ TransformatIon Unordered Fuzzy Vault ] Key (K,) t Encoder (F) i I I I Va It I I I Transformation key : BCH 50606” (H) Key (K2) ] embedded In vault l ] V-F2(K11K2) fl“‘.‘1‘.7‘?f"~ .1“ a"; "I -'-' .‘~-' [ w [4 Template Irlsoode (tr) I l Transformed : Salting (Invertlble) ] Irlsoode Template \_T'_"1"_°'_"‘_'E°fl {F9 ______________ I (1' =Ft(1r:'