Fingerprint Indexing using Extended Set Delaunay Triangulation

With the increasing need of security systems for personal authentication, the use of biometrics has gained importance in recent times. Biometric Recognition is the use of physiological (fingerprint, faces, iris, palm etc) and behavioral (gait, voice, etc) characteristics for recognizing the identity of individual. Biometric Recognition is of two types, verification and Identification. Verification refers to the process in which a person verifies his identity with the identity of the person whom he claims to be i.e., it is one to one match, whereas in Identification the system must determine the identity of the person by searching all templates in the database. Identification refers to an one to N match in the database. To put in simpler words, verification answers the question “Am I Whom I claim I am?” and Identification answers the question “Who am I?”. In either of the cases, the goal of recognition is to quickly determine if an object or template is in the database and to retrieve those objects or templates which are most similar with the unknown object or query template. Accuracy and Efficiency are the defining factors for any Biometric recognition system because everything in the end boils down to how much we are using and how fast we are producing results.

Fingerprint recognition is one of the most widely accepted biometric technique because of its uniqueness, immutability, ease of extraction and its numerous availability (ten fingers) and are extensively used in forensic and civilian applications[Source : www.biometrics.gov]. A naive approach for fingerprint identification would be to compare the given template with all the templates in the database. However, with modern databases, which contain millions of templates, the required processing would have a very large response time and a very low performance which is not acceptable in most of the real time systems. To overcome these difficulties, several researchers have proposed different methods to narrow down the search space.These approaches can be broadly categorized into two types, Classification and Indexing. The goal of these approaches is to reduce the potential candidates that have to be matched with the query image when performing matching. Because fingerprint matching algorithms are generally computationally very expensive, the candidate list produced by the these approaches should be as small as possible with high probability of containing the templates that are most similar the query image. These type of approaches can be considered to be a front end recognition systems which is to be followed by a back end verification system.

CLASSIFICATION:

Classification based approaches split the database into fixed number of classes. During Identification , first the class of the template is determined and the matching is done only with the fingerprints of the same class. Henry [3] has classified fingerprint images into 5 major classes, plain arch, tented arch, left-loop, right-loop and whorl based on the patterns formed by ridges. Jain[8] has used a novel representation (FingerCode) and a two stage classifier to classify the images into five classes.Classification based approaches can be broadly classified into five categories[4]: syntactic-based [5,6], structural-based[7], statistical-based[25], rulebased and neural network-based[24] methods.

This type of approaches have a serious disadvantage mainly because the number of classes into which fingerprints can be divided is small and it is fixed.Also the distribution of fingeprints among these classes is also very uneven because of small interclass variations. Fingerprint classification in most of the cases does not account for translations or rotations and noises of fingerprint images. This led the researchers build systems that are not based on classification but represent each fingerprint template in a very stable robust and effective manner so that in the identification phase , the number of candidates to be selected is reduced.

BACKGROUND

Fingerprints are the impressions produced by the friction ridges on the human finger. Minutia which represent the singularities present on the fingerprint are of two types bifurcations and endings. Bifurcation is a point where a ridge splits into two ridges while an ending is an end point of the ridge. In our approach we use these two types of minutia to classify the triangles. Triangulation: Let P = {p1,....,pn} be a point set. A triangulation of P is a maximal planar subdivision whose vertex set is P. A maximal planar subdivision is a subdivision S such that no edge connecting two vertices can be added to S without destroying its planarity.

DELAUNAY TRIANGULATION

Delaunay Triangulations: Let P = {p1, p2,....,pn} be a set of points in the plane. A triangulation P is said to be a Delaunay Triangulation if and only if for every triangle in T, it satisfies a property that its circumcircle contains no other point of P. A Delaunay graph is represented by G = {P,E} where P is the points in the Delaunay graph and E are the edges in its Delaunay triangulation.

Properties of Delaunay Triangulations:

1. Insertion of Spurious minutia in the fingerprint template only effects the triangles whose circumcircle contain that point. Hence, it effects only the local structure keeping the global structure intact. 2. The Delaunay Triangulation of a set of points is unique if there is no circumcircle with more than three points on its border. 3. The Delaunay triangulation maximizes the minimum angle. Compared to any other triangulation of the points, the smallest angle in the Delaunay triangulation is at least as large as the smallest angle in any other. 4. The union of all triangles of a Delaunay triangulation of a set of points P forms the convex hull of P. The Delaunay triangulation of a set of points P has 2N-2-kriangles and 3N-3-kedges, where N is the number of points in P and k is the number of points of P forming the convex hull.

EXTENDED SET TRAINGULATION

Let P ={p1 ,p2,....,pN} be a set of points in the plane, where G={P, E},is its Delaunay graph and T is its Delaunay triangulation.To be able to formally define the expanded triangle set ofP, we first define thetriangular hull of any point pi∈ P. Triangular hull: Let p i be a point of P. The set Ni ={pj | {pj,pi } ∈ E} denoted the point setformed by all the adjacent vertices of pi in the Delaunay graph G. The triangular hull of pi is defined as the Delaunay triangulation of the planar point set Ni, and it is denoted by Hi . As we can see, the number of points in each set Ni is the degree of pi in the graph G, and it is denoted by di.

Expanded triangle set : The expanded triangle set of P is defined as R = {H1 ∪ H2 ∪ H3 ∪ H4 ∪ .... ∪ HN. The set R includes the triangles in the Delaunay triangulation of P and any triangle in the triangular hulls of the points in P. Therefore,|R|≥|T|. The number of triangles in R is lesser than 13N-25, where N is the number of minutua point

PROPOSED APRROACH

3.1 PREPROCESSING STAGE Feature selectivity is one of the most important steps of any indexing approach. Features with lower discrimination power tend to give very similar indices which further increases the searching time and reduces the efficiency of the approach [11]. Using Extended set execution times of the algorithm are similar to Delaunay Triangulation since both of them produce O(N) triangles.The advantage Extended set has is that it contains all Delaunay Triangles that are formed when each minutia is removed individually[20]. Because most of the minutia features change under elastic distortion, it is very essential to choose features that are invariant to distortion for indexing. Even if the distortion is applied to the fingerprint image, the neighborhood structure of minutia and its shape remains intact. Extended set triangulations store the local structure of the minutia, hence using such a method under distortions would produce better results.Fig(2.2) shows Delaunay triangulation and Extended set for a fingerprint. Extended Set contains all Delaunay Triangles that are formed when each minutia is eliminated individually. This property ensures that in cases of missing or spurious minutia, some matching are definitely found between the distorted and the original

image.

The proposed approach represents fingerprints in terms of their minutia. Each minutia can be represented uniquely by using its co-ordinates m(x, y). Let the graph S{P, E} denote the extended set triangulation for these minutia, where P represents co-ordinates of the minutia points and E represents the edges between them in the triangulation.Fig(3.3) represents a mintuia triplet with vertices V1,V2 and V3.

The above work was done as part of Indian Academy of Sciences fellowship at Institute of Development and Research in Banking Technology, Hyderabad. The findings of the projects were presented in the 8th International IEEE Asia Modeling Symposium held in Kuala Lumpur, Malaysia.

The code for the project can be found at : https://github.com/chennavamshi/fingerprintindexing

For more information about the implementation of the project and dataset used for testing, feel free to contact me through email.