A Robust Fingerprint Indexing Scheme Using Minutia Neighborhood Structure and Low-Order Delaunay Triangles

Fingerprint indexing is a key technique in automatic fingerprint identification systems (AFIS). However, handling fingerprint distortion is still a problem. This paper concentrates on a more accurate fingerprint indexing algorithm that efficiently retrieves the top N possible matching candidates from a huge database. To this end, we design a novel feature based on minutia neighborhood structure (we call this minutia detail and it contains richer minutia information) and a more stable triangulation algorithm (low-order Delaunay triangles, consisting of order 0 and 1 Delaunay triangles), which are both insensitive to fingerprint distortion. The indexing features include minutia detail and attributes of low-order Delaunay triangle (its handedness, angles, maximum edge, and related angles between orientation field and edges). Experiments on databases FVC2002 and FVC2004 show that the proposed algorithm considerably narrows down the search space in fingerprint databases and is stable for various fingerprints. We also compared it with other indexing approaches, and the results show our algorithm has better performance, especially on fingerprints with distortion.