Index Structure And Retrieval Approach Of Very Large Scale Fingerprint Database

Fingerprint is the most widely used feature in the biometrics field. Due to its uniqueness and invariability, with the developing of researches in the fingerprint identification technology in the last decades, Automated Fingerprint Identification Systems (AFIS) are extensively utilized in the identification fields, such as police, border controls, customs inspection, bank, insurance, hospital, network and so on.Along with the application expanding, the scale of fingerprint databases is getting larger and larger, so the challenging retrieval problem is emerged from the very large scale fingerprint database identification system. Very large scale means the capacity of the database is achieved or exceeded tens of millions of fingerprint images.The very large scale fingerprint database retrieval problem belongs to massive information retrieval problem, and the massive information retrieval problem is a typical Non-deterministic Polynomial (NP) problem. For the NP problem, the time it consumes to find an uncertain solution is much more than to verify a specified solution. Because the NP problem is inextricable by using the Exhaustive Search Method, a common approach to deal with the massive data retrieval problem is using Heuristic Search approach. The Heuristic Search approach can guide the retrieval process towards a relatively small range by adding heuristic information to the retrieval strategy thus can accelerate the whole retrieval process, reduce the retrieval time.The basic idea of fingerprint retrieval is:extract and select reliable features as heuristic information firstly, then build the indexing structure on the basis of characteristics of features, and finally get Candidate Sequence by retrieving procedure according to Similarity Retrieval Rules, so extracting and selecting reliable features, and building pertinence indexing structure and retrieval strategies, are all important issues in the fingerprint retrieval sysytem. The information content of features in the fingerprint retrieval sysytem is closely related to the quality of fingerprint images, the veracity and accuracy of identification results will be remarkably decreased if the fingerprint images have poor quality. So, adding Automated Fingerprint Image Quality Assessment into AFIS is significant. In this thesis, our researches are focused on aforementioned important issues, and some effective solutions are proposed.The main work of this dissertation is as follows:(a)Automated Fingerprint Image Quality Assessment (AFIQA)In the fingerprint retrieval system, AFIQA can be used for chosing retrieval algorithm according to the quality of probe image, and also can be used for predicting the dynamic threshold of the retrieval system.Because it is a combined action of many factors, AFIQA usually integrates global features with local features to create a syncretic algorithm. The first factor must be considered is how to choose the quality evaluation indexes. Unfortunately, the related researches did not propose any assessment criteria for choosing the evaluation indexes, but only chose them empirically.An evaluation indexes classification method using Mechanism of Visual Attention is proposed in this dissertation, it can classify quality evaluation indexes into many clusters. After clustering, quality evaluation indexes are selected by considering the whole efficiency of AFIS and the reliability of those evaluation indexes themselves. Finally, five quality evaluation indexes are chosen, among those selected evaluation indexes, a minutiae reliability assessment method based on Polar Coordinates Centrum Sensitivity (PCCS) and a gray level image contrast assessment method based on Otsu algorithm are proposed. The experimental results on Error Back Propagation (BP) Neural Network and Support Vector Machine (SVM) show that the selected evaluation indexes have good evaluating performance.The main drawback of the state of art fingerprint image quality classification methods based on Machine Learning is the insufficiency of quality ranks, and the main drawback of Linear Weighted Methods is the weak ability of approximating the nonlinear mapping relation from evaluation indexes to fingerprint image quality assessment score.Fingerprint Subjective Assessment experiments and Influence Estimate Matrix experiments are introduced into this dissertation in order to propose the fingerprint image quality assessment approach based on Multi Parameters Non-linear Integrated (MPNLI). The proposed MPNLI approach can effectively approximate the nonlinear mapping relation from evaluation indexes to fingerprint image quality assessment score. Furthermore, the proposed MPNLI approach has more quality ranks than BP Neural Network and SVM based approaches. More available quality ranks can result in the predicted thresholds more precisely, which will conduce to promotion of the retrieval efficiency.(b)Fingerprint retrieval algorithmIn the state of art fingerprint retrieval approaches, because they only regard the indexing and retrieval modules as simple subsidiary fuctions of retrieval procedure, they tend to ignore pondering over the indexing and retrieval strategies. However, in this dissertation, we name the index building module as Indexer, and name the retrieval module as Retriever, for going deep into the problems in the indexing and retrieval strategies.The state of art Minutiae Polygon Based Fingerprint Retrieval Approaches are effective according to the literature, but they are faced with the conflict of polygon identification ability and polygon number: More sides in polygon can enhance the identification ability, but thus will make retrieval procedure slow down because of the enlarged polygon number. The proposed Fingerprint Retrieval Approach Based on Minutiae Triplets One Side Multiple Matching (MTOSMM) can solve this conflict by obtaining matched polygon (more than4sides) number via matched triplets.For the building of Indexer, the match method of triplets, quantization of features, analysis and solving match errors caused by quantization, MTOSMM, feature selection, Mid Point of Quantized Interval and index structure are all be considered in this dissertation. Finally, a polygon selection method based on MTOSMM is proposed and a two-layer index structure is built, experimental results show that the proposed Indexer can speed up the retrieval procedure effectively.For the building of Retriever, two aspects must be thought highly of: the first one is Similarity Criterion, the other one is Retrieval Threshold. A Similarity Criterion Based on MTOSMM score method is proposed, which use weighted sum of matched number of multi topological structures to format the score equation, and the weights are obtained by proposed Midpoint Flag Weight (MFW) method.The generally used retrieval strategy in the state of art literature is Top N Strategy. The main drawback of Top N strategy is the one-to-one matching procedure must wait for the end of the retrieval and sorting procedure, and can not execute simultaneously. Because Threshold Strategy can execute retrieval and one-to-one matching procedure simultaneously, and Threshold Strategy does not need sorting procedure either, we tend to think that the Threshold Strategy must be more efficient than Top N Strategy. The key issue of the Threshold Strategy is that good threshold predicting method must be proposed. Therefore, a Threshold Predicting Approach Based on Fingerprint Image Quality Ranks is proposed to solve this problem.(c)Poor fingerprint image retrieval algorithmThe fingerprints left in the crime scenes are named as Latent Fingerprint Images. Because they are left unconsciously, perhaps they are taped by non-uniform pressure, have small area, are partial, or have complex background, thus they usually have large deformation or noise, therefore, the retrieval problem of Latent Fingerprint is particularly difficult. To our knowledge, no approach was proposed specially for poor quality Latent Fingerprint Images retrieval problem in the literature till now.Because the Latent Fingerprint Images usualy have poor quality, the proposed retrieval approach based on MTOSMM needs to be improved, thus a novel retrieval approach based on Latent Triplet Multicast (LTM) is proposed. According to researches in this dissertation, the main reason of poor retrieval effect is that the number of minutiae in the Latent Fingerprint Image is very few, so some things must be done for the effective utilization of the scanty information. The retrieval approach based on LTM can reduce the errors caused by quantization, and increase triplets number of Latent Fingerprint Images, thus it can promote the retrieval efficiency.(d)The very large scale fingerprint database retrieval systemIn this dissertation, we proposed an Automated Fingerprint Image Quality Assessment approach based on MPNLI, a fingerprint retrieval approach based on MTOSMM and a fingerprint retrieval approach based on LTM, thus the problem of how to combination all those approaches efficiently into AFIS is put on the agenda.The proposed fingerprint retrieval approach based on MTOSMM has the trait of being fast and relatively precise, but is not so good for retrieving poor fingerprint images, so it can be used for retrieval tasks for good quality probe images.The fingerprint retrieval approach based on LTM is specially proposed for poor quality probe images, and can promote the retrieval effect remarkably, so it is suitable for poor quality probe image retrieval.The fingerprint image quality assessment approach can be utilized in the very large scale fingerprint image retrieval system in two ways: algorithm selection module and threshold predicting module.The algorithm selection function can be achieved by the image quality classification approach based on BP neural network. Because the BP neural network based approach is more accurate than the MPNLI based approach in two class classification problems, BP neural network is selected as a classifier. The BP neural network classifies the probe images into2clusters:good quality images and bad quality images. In the retrieval procedure, fingerprint retrieval approach based on MTOSMM is utilized to retrieve good quality images, and fingerprint retrieval approach based on LTM is utilized to retrieve bad quality images.Both MTOSMM based and LTM based retrieval approach need threshold in retrieval procedure. Because the MPNLI based quality assessment approach can provide more quality ranks, more available quality ranks can let the predicted dynamic thresholds more precise, which will conduce to promotion of the retrieval efficiency. So the MPNLI based quality assessment approach is chosen for predicting threshold.In conclusion, fingerprint images quality assessment approaches, fingerprint retrieval approaches and building methods of very large fingerprint database structure are discussed in this dissertation, and some research achievements have been proposed. Experimental results show that the proposed approaches can promote the efficiency of very large fingerprint database remarkably.