Fingerprint identification using Delaunay triangulations

Abstract

Although not scientifically proven, it is strongly believed that fingerprints are unique and so fingerprint recognition is one of the most popular and reliable biometric identification technique. Fingerprint identification systems are negatively affected by noise and image transformations which reduce the number of common characteristics of the matching fingerprints, making it more difficult to identify a matching pair. Our aim is to propose a new fingerprint representation and matching techniques resistant to noise and trans formations. The objective is to implement and test one of the proposed techniques to perform evaluation and draw conclusions. This dissertation includes a detailed analysis of the existing fingerprint techniques which helped to familiarise with conventional fingerprint systems, image enhancement practices and other existing technologies. We propose three new fingerprint matching techniques. The first one is a graph matching technique similar to graph isomorphism which can tolerate certain discrepancies. The second technique is based on building a common Delaunay triangulation set. Finally the third technique relies on topological representations including both minutiae and ridge structure and interprets fingerprints as graphs with the use of ridge counts as an alternative distance unit. The original idea was to apply Delaunay triangulations on fingerprint minutiae to obtain planar graph representations which allow the use of linear time graph isomorphism algorithms. However it was observed that this approach did not work out because the Delaunay triangulations matching fingerprints were not identical. The third alternative proposed techniques, based on Delaunay triangulations was developed and tested and the results obtained are very promising. This proofs that the adopted technique is capable to identify fingerprints. When tested on a sample of 200 fingerprints from the standard NIST Special Database 4 it classified 80% of the fingerprints in the best 30 identifications.