A framework for efficient fingerprint identification using a minutiae tree
MetadataShow full item record
Automated Fingerprint Identification Systems (AFIS) match a query fingerprint image with potentially large number of enrolled templates. Techniques such as pyramid indexing have been used to improve search efficiency by pruning templates using a varying range of feature values at each level. Other indexing methods pre-order the templates based on similarities in local regions. For example, a recently published method using correspondences of feature triplets and geometric constraints shows that reducing the search space improves the speed of matching and retrieval at the expense of accuracy. The challenge in practical AFIS operating on large datasets (millions of records) is to keep error rates low, while providing a match in real-time. We have developed an efficient indexing and matching methodology for AFIS using a novel tree-based algorithm. Fingerprint templates of the enrolled users have been registered in a tree structure using minutiae features (contour ridge singularities) extracted from different local regions of a fingerprint image. We have developed the notion of 'minutiae bins', so that fingerprint images with similar minutiae patterns are stored at the same node of the tree. During traversal, branch selection is performed using minutiae the properties (e.g. distances to neighboring minutiae) corresponding to the current node of the tree. Variations in the minutiae extracted at different instances or due to distortions and noise can lead to binning errors. We overcome this problem by placing the same template at multiple locations in the tree, which reduces the effect of missing and spurious minutiae. Multiple paths, corresponding to adjoining bins, may also be searched, if extracted feature values are close to bin boundaries. Experiments performed on the FVC 2002 and FVC 2004 public datasets have shown that searching deep in the tree eliminates virtually all incorrect matches. We have also tested the system on very large synthetically generated datasets, and shown that the accuracy and response time of our approach scale well with the size of the index. We conclude with a detailed study on how different features used for matching affect the system accuracy and efficiency.