Finger Print Recognition: Technology and Application

Tri Caohuu, Dept. of EE
San Jose State University
One Washington Square
San Jose, CA 95192-0084

  Le Thuy, Super Computer Group
Fujitsu of America, Inc.
3055 Orchard Drive
San Jose, CA 95134-2022

 The fingerprints have been use as a mean for identifying individual for a long time because the fingerprints are unique and stay unchanged through out an individual life time. Currently there are about 200 million FBI cards (10 fingerprints per cards) stored in cabinets that would fill an area of one acre. The manual effort of identifying and maintaining such a system is very cumbersome , time consuming and expensive as the number of finger print records grow at a rate from 30 to 50 thousands cards per day [1]. With the advancement of computer technology the problem of automatic finger print identification has attracted wide attention among researchers sine 1969 that results in a few state-of the art automatic fingerprint identification system (AFIS) available today. Going in hands with the recognition problem is the problem of real-time matching system for large fingerprint data bases. Since the storage requirement for such a large amount of data can be thousands of terabytes system, data compression is another aspect of automatic identification using fingerprints. Currently the FBI data compression specification for finger is the de facto national standard which is based on wavelet transform scalar quatization (WSQ). In this paper we will briefly review the building blocks of the AFIS in section I, examine the WSQ in section II, and discuss about an application of fingerprint in driver licence currently proposed to the Federal Highway Administration ( FHWA).

  II. Automatic Fingerprint Identification System (AFIS)

 The four main components of an AFIS system is the scanner, the recognition algorithm, the search an query algorithm of the data base and the data compression algorithm.

 The live scanner captures the finger print at a minimum resolution of 500 pixels per inch in both row and column and each pixel shall be gray level quantized to 8 bits.[Data Format for the Interchange of Finger print Information, ANSI/NIST-CSL 1-1993]. Regardless of the method and media used by the scanner, the electronic image must be sufficient quality to provide conclusive finger print comparison, successful finger classification and feature detection, and can support a AFIS search reliably. The major consideration for the scanner is whether or not it meet a number test procedures that will warranty the image quality as stated in the Minimum Image Quality Requirement, Electronically Produced, Fingerprint Cards, Appendix F- IAFIS Image Quality Specifications, developed by NIST in conjunction with FBI and the Dept. of Justice[3 ].

a. Geometric Image Accuracy

b. Modulation Transfer Function (MTF).

MTF is the point response of the image capturing system. For each frequency the Image Modulation (IM) is computed. {IM = (Max- Min)/(Min-Max)}.The MTF is then computed by dividing the Image Modulation by the Target Modulation.

c. Signal to Noise Ratio (SNR).

For adequate image quality, the SNR must be less than 125 for both black and white noise.

The SNR is computed as the difference between the average white and the average black value, alternately divided by the white noise standard deviation and the black noise standard deviation.

d. Grey-Scale Range of Image Data

At least 80% of the captured images should have a dynamic range of at least 200 grey levels and at least 90% shall have a dynamic range of at least 128 grey levels.

e. Grey Scale Linearity and Grey Level Uniformity.

Linearity and uniformity of the grey level must meet a standard to assure a image quality suitable for AFIS. When scanning a uniform reference of white (and black), no two adjacent rows or columns of length 5 pixels or greater shall have an average grey scale different more than a threshold value (1. level for black to 2.5 level for white), pixel’s grey level must remain within a deviation from mean value of local area ("quarter inch area"), the mean grey level of adjacent quarter inch area shall not differ by certain value (9.0 for black, 12. for white).

The fingerprint matching process can be represented by the flowing block diagram

Fig. 1 : Matching Block Diagram

The pre-processing aim is to improve the quality of the image. The pre-processing has two tasks: ridge enhancement and restoration and segmentation of fingerprint image. The pre-processing step produces a binary segmented fingerprint ridge image from an input grey scale image. The ridges have a value of ‘1’ and the rest of the image has value of ‘0’. The pre-processing steps involve 1) computation of orientation field 2)foreground/background separation, 3)ridge segmentation , and 4) directional smoothing of ridge [5].

 Analysis of the fingerprints shows that the ridges (or the valleys) exhibit different anomalies refered to as ridge ending, ridge bifurcation, short ridge, ridge crossovers etc... There are some eighteen different types of features enumerated and called minutiaes. The most frequently used are the ridge ending and ridge bifurcations, they are as shown in Fig. 2(a) and (b).

Fig. 2(a): Ridge ending Fig. 2(b): Ridge bifurcation Fig. 2(c): Ridge direction

  A typical good finger print has about 70 to 80 minutiae points. Other complex fingerprint features can be expressed as a combination of these two features. The features are normally recorded as a vector with three attributes: the x-co-ordinate, the y-co-ordinate, and the local ridge direction (q ). q is shown on Fig. 2 (c).

 The finger matching is the matching of the minutiae sets. This can done with number of techniques including point set matching , graph matching ,and sub-graph isomorphism [2].

 3. Fingerprint classification

 Given the database for the fingerprints is very large, the matching should be done only on a subset of the database. To this end, the fingerprints are classified in to five main categories as a high-level features that can be used in reducing the search source during a match. They are : arch, tented arch, left loop, right loop, and whorl.

 When ambiguous situation due to partial print or noisy fingerprint, other alternative method of classification are used including ridge density count and singular point detection [2].

The singular points commonly used are the core and the delta. The core is the highest point on the innermost ridge, the delta is the point at which three ridge radiated from it. Ratha et al. proposed a effective classification scheme that may be described by Fig. 3

Fig. 3: Block Diagram of Classification Algorithm [2 ]

 The US Federal Bureau of Investigation (FBI) has formulated a national standard for digitization and compression of grey-scale fingerprint image. At a 15:1 compression ration, the WSQ is a lossy compression but can produce archival-quality image. The compression and decompression is based on adaptive uniform scalar quatization of discrete wavelet transform subband decomposition. In this section we will examine the important aspects of the WSQ decoder and encoder. The overview of the encoder and decoder algorithm is as shown as follows:

WSQ Decoder

The encoding consists of three main processes: the discrete wavelet transform (DWT) decomposition, the scalar quantization, and the Huffman entropy coding [1 ].

 In the DWT step, the digital image is split into 64 spatial frequency subbands by a two-dimensional discrete wavelet transform which is a mutirate digital filter bank. The output DWT coefficients which is in floating point arithmetic format is truncated by the scalar quantization step ("quantized"). The integer indices output by the quantization encoder are entropy-encoded by run-length coding of zeros and Huffman coding. The compressed image data, a table of wavelet transform specifications, tables for the scalar quantizers and the Huffman codes are concatenated into a single bit stream of compressed data.

 In the WSQ, a two-dimensional symmetric wavelet transform is applied to the input image by transforming first the rows and then the column yielding a four-channel decomposition. The four subbands are then cascaded back through the two-dimensional analysis bank to produce a more refined sixteen-bank decomposition. This process is repeated until a 64-band decomposition is achieved.

 The WSQ decoder reverses the process above to reproduce the finger print image from compressed data. The Huffman decoder first recovers the quantized DWT coefficients. Through the dequantizer, approximation of the original floating point format of the DWT coefficients obtained and the coefficients are feed to an inverse DWT to reconstruct the finger print image.

 More details of the WSQ compression-decompression algorithms can be found in IAFIS-ISC-0110v2, the WSQ Grey-scale Finger Print Image Compression Specification (1993) and in references [1] and [6].

System for Commercial Driver Licence

The goal of the system design is to meet the following motto cherished by the DMV which is "One man, one driver license, one set of biometric identifier". To meet this goal the system design must have the following functions: (a) Verify that the driver is the authorized holder of the licence (assure that the driver is indeed the legal holder of the licence) (b) Verify that the driver licence is valid (assure that the driver licence is not falsified) and (c) Prevent issuance of multiple licences and multiple-driver-licence detection.

 The criteria for the technology used must support both co-operative and non-co-operative user, is proven technology and has multiple sourcing available.

 The overview system is visualised to be composed of three main tasks and five system components. The main tasks are described in the system functions above. The major subsystem components are the card, the scanner, the network/server, the data base, and the search algorithm.

 Verifying the matching between driver fingerprint and the fingerprint features stored on the licence assures that the driver is indeed the person that the licence is issued for. This task can be done on-site where the fingerprint features obtained from the driver by live_scanning is compared with the features magnetically stored on the driver licence. Current "smart card" technology allows abundant memory capacity to store the features on card.

 A driver/ licence match means that the licence indeed belongs to the driver, this, however does no warranty that the driver license is not falsified. To check for validity of the driver licence the police officer has the option to make additional inquiry against the database. In this case a licence validity check will result. See Flow Chart 1.

 A match in driver/licence only means that the driver’s fingerprint has the same features as stored on the driver licence, a driver licence validity check will verify the authenticity of the licence itself. The associative search with key being the features will be made at the data base. A successful search will verify the licence validity.

 A failure of the on-site driver/licence match means that the driver uses someone else’s or a falsified licence. In this case, the driver will be taken off the road and a on-line system search for the fingerprint features from the card is initiated (the licence might be a stolen one). A successful search means that the driver is using a valid licence but not one issued to himself. This will result in the driver licence being "flagged" and proper procedures for notification of stolen licence will follow. A multiple successful search detects the issuance of multiple driver licence that somehow resulted from prevention system failure. The search is a non-trivial task whose algorithm need to be developed. Flow Chart 2 shows system function (b).

 The prevention of the issuance of multiple driver’s licences is essentially implemented at the licence application stage (enrolment) while the detection of multiple driver’s licences is incorporated by the license validity check described in part (b). The prevention subtask is done by live scanning of the fingerprint(s) of the applicant. Similar to part (a), this subtask is implemented in two steps: verification of acceptability (VA) which is done in real-time mode and verification of uniqueness (VU) which may be done in batch mode (during the review and approval of the application). Failure in the VA process results in a retry while failure in the VU process results in access of the fingerprint archive (WSQ standard) to retrieve and reconstruct the finger set to confirm the detection prior to rectification of the error and/or prosecution procedures pending violations. Flow Chart 3 shows this system function.

There are a number of key issues associated with this system function:

 1. Data bases that support content search and query techniques and procedures.

Since the fingerprint images, even after compressed, is of much higher dimensionality than textual information, the storage management and query techniques are very crucial for a real-time matching system.

 2. During the process of obtaining the live scan image of the fingerprint(s) a set of features (if feature extraction is utilised) or signatures must be generated and check for its acceptability on-site and on-line. In case of poor or partial image or defective finger, the applicant will ask to retry or reconfigure data. (Verification of acceptability)

Flow Chart 1: Driver-Licence Matching

Flow Chart 2: Licence Validity Check

Flow Chart 3: Prevention and Detection of Multiple Driver Licence

3. The verification of uniqueness (VU) involves a global search for fingerprints with the same set of features. This process may take a long time (system latency) and perhaps could be done in batch mode.

 4. The VU search characteristics as a content search with feature(s) for key . To be more effective the search is organized on data bases clustering by region. Associated fingerprint records are

placed in WSQ standard archives

 We have presented and overview of the finger print technology which include primarily the scanner, the classification of fingerprint image in the database, the matching algorithms and the compression\decompression algorithm standardized by the FBI. While the approach to AFIS is common for most manufactures of AFIS systems ( feature_based) the details of the matching schemes are not identical. Certain standard perhaps might be needed for this area before major commercial system applications can be implemented. We also presented the conceptual design of an fingerprint_based biometric systems for commercial driver licence which a part of a current study for the FHWA.

 Once the standards and compliance procedures are in place, we predict a explosion in the number of applications of the fingerprint technology to important industries including network security and protection, smart money, ATM transaction, and biometric identifier systems and to many major government sectors such as FBI, NIST, and DMV.

 [1] C. M. Brislawn, J. N. Bradley, R. J. Onyshczak, T. Hopper, " The FBI compression standard for digitized finger print images", Proc. SPIE, Vol. 2847, Denver, Aug. 1996

[2] N. K. Ratha, K. Karu, S. Chen , and A. K. Jain, " a Real-time Matching System for Large Finger Print Data Base"., IEEE Trans. on PAMI. Vol. 18, N. 8, Aug. 1996

[3] IAFIS Image quality Specification, Appendix G, CJIS-RS-0010 (V4), FBI, Aug. 24, 1995

[4] Harold H. Szu, "Image wavelet transform implemented by discrete wavelet chips", Optical Engineering, Vol 33, N. 7, 1994.

[5] B. M. Mehtre, "Finger Image Analysis for Automatic Identification", Machine Vision and Application, Vol. 6, p. 124-139, 1993.

[6] J.N. Bradley, C. M. Brislawn, and T. Hopper, "The FBI wavelet\scalar quantization standard for grey-scale fingerprint image compression", in Proc. SPIE, Vol. 1961, pp. 293-304, Orlando, Apr. 1993