Thursday, 21 February 2019

Fingerprint recognition


Jump to: navigation, search



Alexandre ACKERMANS - Nadine WARZEE

Project description

In a modern AFIS (Automated Fingerprint Identification System), you can have up to several millions prints to compare against each other for a total of more than 10^12 comparisons.

This project, made in collaboration with a belgian company Zetes, aims to develop a fingerprint matching process that runs on off-the-shelf GPU's (Graphical Processing units). This will allow to compare many more fingerprints than is actually possible and lower the cost-performance ratio. It is also an excellent test case for complex scientific computations on parallel hardware. Current leading methods allow a comparison rate of 3-5000 prints per second, but by harnessing the power found in modern GPU's this number could increase dramatically.


Modern GPU's like Nvidia's latest mass market offering the Geforce 8800 contain as many as 128 distinct processors that can work in parallel and process much more data than the fastest CPU's as long as the algorithms used allow to process the data independently and that the various bottlenecks of the system do not prevent data coming into the GPU. It is very difficult to adapt current, serialized methods for parallel processing. Usually graphic cards were reserved for processing images where pixels or sections of the images are often independant of one another and can be processed independantly. Now it is possible with modern API's to harness the power of GPU's for other uses.

Each "shader" on the GPU runs the same code on different data. Data has to be sent from the CPU to the GPU and back, which is an important bottleneck, as well as the various memory access the GPU must make to access data and load it in its shaders. Conflicting and concurrent accesses are also to avoid.

Algorithmically, we need to adapt or devise new methods that are suitalbe for testing on GPU's; current algorithms in the litterature are made to run on CPU's and do not pay attention to data locality, branching avoidance(same instructions on different data means avoiding conditional tests on the data) and other problems inherent to parallel cmoputing.


When comparing fingerprints we usually extract various caracteristic poitns called "minutiae" and then compare different features recognizable with each minutiae such as
- orientation
- position
- type

Figure 1: Minutiae extracted from fingerprint

Comparing minutiae can be made via numerous methods that will yield a "matching score" that aims to give the best result of whether or not the two fingerprints analysed are the same.

Other work

Many other aspects of fingerprint analysis have to be considered to tackle this problem. among them - improving the quality of the initial dataset in order to increase the quality of the results obtained by these algorithm. This allows to compare less points and thus increases speed.
Fp imh enhancement.jpg
Figure 3: Fingerprint image enhancement

- classification of the fingerprints to reduce the size of the groups of individuals that need to be compared. - singular points detection for alignment and registration that allows to reduce errors introduced by variations in translation and rotation.
Figure 2: Classification of fingerprint using singular points (core and delta)

- image quality assesment for dynamic selection of algorithms and parameters

Recommended reading

If you are interested in the subject, the following documents are a good start.

[1] A. Crouzil, L. Massip-Pailhes,S. Castan "A New Correlation Criterion Based on Gradient Fields Similarity", Proceedings of the 1996 International Conference on Pattern Recognition (ICPR '96) Volume I - Volume 7270 table of contents

[2] Takahiro Hatano,Takuya Adachi, Satoshi Shigematsu,Hiroki Morimura, Shigehiko Onishi,Yukio Okazaki,Hakaru Kyuragi "A Fingerprint Verification Algorithm Using the Differential Matching Rate " 16th International Conference on Pattern Recognition (ICPR'02) - Volume 3 p. 30799

[3] Asker M. Bazen, Gerben T.B. Verwaaijen, Sabih H. Gerez, "A Correlation-Based Fingerprint Verification System ", Leo P.J. Veelenturf and Berend Jan van der Zwaag

[4] Umeyama S., "Least-Square Estimation of transformation parameters between two point patterns", IEEE transactions on attern analysis and machine intelligence, vol 13 no 4 pp 376-380, 1991

[5] Chang S.H, Cheng F.H, Hsu W.H, and Wu G.Z., "Fast Algorithm for Point Pattern-Matching: Invariant to Translations, Rotations and Scale Changes" Pattern Recognition, vol. 30, no 2, pp. 311-320, 1997

[6] Ratha N.K., Karu K., Chen S. and Jain A.K. "A real time Matching system for large fingerprint databases" IEEE Trans. on Pattern Analysis and Machine Intelligence, vol 18 no 8 pp 799-813, 1996

[7] Bozorth, A.S. D. Garris, C. I. Watson, R. M. McCabe, and C. L. Wilson, "Sect 4.5 Bozorth3" Users guide to nist fingerprint image software (nfis2). Technical Report NISTIR 6813, National Institute of Standards and Technology, 2002. Sect 4.5 pp 80-86

[8] Ratha N.K, Rover D., Jain A.K., "Fingerprint Matching on Splash 2" in Splash 2: FPGA's in a custom Computing Machine, pp 117-140, IEEE Computer society Press, Los Alamitos, CA 1996

[9] Prabhakar R.V.S.N A parallel Algorithm for fingerprint Matching IEEE 1989