System developers apply to fingerprint analysis

System developers apply to fingerprint analysis

By Richard Parker, Contributing Editor

umerous techniques have been deployed to positively identify people through biometric verification--fingerprint-matching, matching eyes` irises, and DNA analysis. Of these three methods, the last two have not been cost-effective. Even many fingerprinting techniques have fallen short because of the high cost associated with the stringent requirement for accuracy.

Neural-network software is now being developed to solve this problem. Many software packages that can be

operated on a personal computer (PC) are giving law-enforcement authorities, immigration agencies, and financial institutions secure, powerful, and cost-effective fingerprint solutions.

Fingerprint identification generally involves two main steps: pattern classification and matching. In the first step, known as the Henry step (Sir Edward Henry, a British scientist, introduced a system of fingerprint matching for identification back in 1901 at Scotland Yard), fingerprints are classified into groups based on the global structure of the fingerprint`s ridge patterns. They are first classified into categories such as loops, whorls, and arches. The final match of a fingerprint is made by comparing a fingerprint`s minutiae--quirks of individual lines in the fingerprint-like bifurcations, trifurcations, line endings, and islands.

According to data from the US Federal Bureau of Investigation (FBI), fingerprint loops (radial loops that open toward the thumb and ulnar loops that open toward the shortest finger) make up a class of about 65% of all fingerprints. Another 30% is made up of whorls, and arches, including "tented" ones, make up the remaining 5%.

Final fingerprint classification is made by initially counting the number of ridges that intersect a precisely defined line. The next step is to match a fingerprint`s minutiae against the database. These steps involve a large computing task to match all the required data.

The recognition task

The difficulty in positively identifying an individual through fingerprints depends on the additional information that is provided to a computer to match against its fingerprint database. For example, many bank-card-verification and security-access systems identify people through fingerprint matching coupled with photographs, personal identification numbers, or security codes.

On the other hand, checking only a person`s fingerprint against a database of fingerprints is a more demanding task and is where neural-network technology has been helpful. Unlike other techniques, it more accurately identifies fingerprint images even when they contain dirt, blurs, and smudges, or are of low quality.

Traditional fingerprinting methods used by law-enforcement and other government agencies are messy processes. They tend to impart ink smudges and other imperfections depending on how the person performing the fingerprinting applies the subject`s finger to the normally white pad, what angle is used, and how much force is applied. These variables make fingerprint matching with conventional techniques prone to errors. That is what Pierre Baldi, member of the technical staff at the Jet Propulsion Laboratory (JPL; Pasadena, CA), and Yves Chauvin, a visiting research associate at Stanford University`s psychology department (Stanford, CA), discovered in 1993 when they introduced the concept of using neural networks for fingerprint identification.

Baldi and Chauvin recognized that neural networks learn to match fingerprints by trial-and-error processes. That is, a neural network is first provided a pair of images (one to be identified and one from the computer`s database) and is then queried whether this pair is the same or not. After each neural-network decision, the network connections are adjusted until the right answer is selected every time (see "Learning About Artificial Neural Networks," p. 36).

Accomplishing this selection process requires many sets of fingerprints. At the time they developed their technique, Baldi and Chauvin were refused fingerprint data from the FBI. Consequently, they compiled a database by fingerprinting 20 colleagues many times.

From a pool of 4950 pairs of prints, Baldi and Chauvin used 300 pairs for training and the remaining 4650 pairs to verify that the network had mastered the task. A key element in the fingerprint system`s performance is that unlike other fingerprint databases, which contain fingerprint images taken only once, the system Baldi and Chauvin developed contains fingerprint images taken at different times and thus under different lighting and miscellaneous imprint conditions. This method is graded as being successful in improving the fingerprint system`s accuracy.

The matching algorithm they developed consists of two stages: preprocessing and decisioning. The former stage consists of aligning two fingerprint images (one to be identified and one in the database) and extracting from each one of them information from a central fingerprint region. Information from the two central regions is then fed to the decisioning stage, which is trained by using a probabilistic Bayesian neural-network technique.

During the preprocessing stage, a prism is used against which a person presses a fingerprint for data acquisition. The prism reflects a beam of light into a CCD camera. Wherever the fingerprint`s ridges touch the glass, however, no reflection is obtained. The resulting pattern of bright and dark lines seen by the CCD camera is converted to a digital still image by a PC-based frame grabber.

These fingerprint images contain nearly 2 Mbits of data, which is excessive for the time needed to train the computer. In fact, when Baldi and Chauvin developed the system on a Unix workstation, they needed approximately eight hours to train the computer. This time frame meant that selective bits of data had to be used.

As a result, the computer was programmed to locate only the center of a fingerprint (where most of a fingerprint`s important details can be found) and discard everything else except a patch of about 10 ridgewidths square, just below the center of the image. With this approach, training time was reduced to about two hours. Today, with more powerful PCs available, the fingerprint system can be trained in about one hour.

The PC matches the square patch over a smaller square area of the reference image until both images line up. The computer then discards the part of the test image beyond the reference square and compresses the two overlaid squares into squares one-fourth the size. The compressed squares are scanned by a set of filters that look for specific features. The neural network "learns" what kinds of filters it needs to use as it goes through the training.

Based on this fingerprinting method, Baldi and Chauvin founded Net-ID (San Francisco, CA), with Baldi serving as the chief executive officer. The company makes available NetPrint (formerly VeriPrint)--software that runs on a PC under Windows 95/NT or UNIX. According to the company, its system is able to match two fingerprints in about 1 s, with an error rate of about 0.5%.

Another company that provides fingerprint-identification systems is Cambridge Neurodynamics (Cambridge, England). The company`s Fingerprint Verification System automatically analyzes the overall shape of a fingerprint pattern and provides false acceptance and recognition rates of less than 1%. The system consists of a fingerprint-reader module to capture images and image-enhancing and analysis software. It runs on a personal computer running under Windows software (see Fig. 1). Fingerprint template information can be stored in as little as 20 bytes, verification time is 2 s, and enrollment time is 30 s.

A more powerful solution is afforded by the company`s Integrated Automatic Fingerprint Recognition System. This system automates the needs of a fingerprint bureau, from management of print records to latent fingerprint search. "We developed the software for the South Yorkshire Police, and it is still being used," says Emma Barnes, Cambridge Neurodynamics`s marketing manager. "Our system is now being used by the Royal Jordanian government, and we are also in the final installation phase of a welfare verification and identification system," she adds.

Unsupervised learning

Many fingerprint-recognition systems treat fingerprint classification and identification as mutually exclusive events. This approach places a burden on computer-memory re quirements because a large database of fingerprint characteristics is needed for searches and matches. To solve this problem, Cihan H. Dagli along with A. Murat Ozbayoglu of the smart engineering laboratory of the University of Missouri at Rolla are proposing a hierarchical system with unsupervised learning. In their system, raw fingerprint images are acquired by the system computer (see Fig. 2). These images are enhanced and then thinned. This processing is followed by feature extraction, classification, and fingerprint identification.

After the image is enhanced, a fast Fourier transform is applied for subsequent image processing. The transformed data are next passed through a bidirectional bandpass filter using local-ridge-orientation information. This information is used as the source of features for the classification stage. After a thinning operation is performed on the images and features, known as singular points, the classification and identification processes are performed.

According to Dagli, the neural-network model shows an acceptable level of accuracy. In tests on 28 fingerprints from six different people, confidence levels of 0.97 to 0.99 were achieved (1.0 being a perfect match). He feels that his approach will be useful for security systems with small to medium-size databases of fingerprints.

No matter what type of fingerprint identification system is desired, supervised or unsupervised, enough hardware and software tools are now available for developing associated neural networks (see "Trying neural nets for free," p. 38).

Fingerprint-analysis systems from Cambridge Neuro dynamics are currently being used in security applications.

FIGURE 1. Fingerprint details (left) are matched against a known fingerprint in a database (right) using a neural-network-based fingerprint-management system, the Integrated Automatic Fingerprint Recognition System from Cambridge Neurodynamics.

FIGURE 2. In a neural-network system that uses unsupervised learning for fingerprint identification, a fingerprint (a) is passed through a bidirectional bandpass filter that provides local ridge-orientation information (b). This information is used as the source of the features for classification (c).

Learning about artificial neural networks

Artificial neural networks (ANNs) are mathematical algorithms inspired by studies of the human brain and nervous system. The ANNs encompass various techniques for modeling nonlinear processes and are firmly rooted in statistical methods. They use massively parallel distributed processors with a natural propensity for storing knowledge based on experience.

The most popular ANN is the multilayer perceptron network. Some authorities call it the back-propagation network, while others have named it the feed-forward network. In either case, the network consists of three layers--an input layer, a hidden layer, and an output layer (see figure). Each layer has a number of processing elements that are called neurons. These neurons are connected to each other, with each connection being given an assigned weighting factor, or weight.

Input-layer neurons receive input data, with the number of input neurons being equal to the number of input signals. Therefore, a 16-channel input layer has 16 input signals, a 10-channel layer has 10 input signals, and so on. Both the input and hidden layers contain bias neurons whose function it is to restrict neuron outputs in the input; the hidden layers also implement threshold limits set by the system developer.

Most ANNs incur some type of training rule whereby the weights of the neuron connections are adjusted on the basis of the input data. Because of this training, ANNs have the ability to learn based on the input data, the threshold limits, and the assigned connection weights.

R. P.

The artificial neural network (ANN) comprises an input layer, a hidden layer, and an output layer, all of which contain processing elements called neurons. These connected neurons are assigned a weighting factor, or weight. Both the input and hidden layers also contain bias neurons whose function is to restrict neuron outputs in the input and hidden layers to certain threshold limits set by the system developer. Based on the imposed training rules and adjustments, the ANN derives the ability to learn and produce the desired results.

Trying free neural networks

A starting point for system developers wanting to try neural networks for fingerprint identification is a free program available from the National Institute of Standards and Technology (NIST; Gaithersburg, MD). The program, called the Pattern-Level Classification Automation System for fingerprints, is neural network public-domain software.

Its primary component is a classifier demonstration program that separates fingerprint images into pattern-level classes known as left loop, right loop, scar, tented arch, and whorl. Available in the form of an ISO9660-format CD-ROM, the program contains source code in C for the classifier demon stration, optimization and utility commands, library subroutines, make-files for various workstations, data files, default parameter files used by the classifier, and about 2700 fingerprint images.

"The software uses a probabilistic neural network that does not require much training," says Gerald T. Candela, a member of the NIST technical staff. Like others involved in fingerprint verification and recognition, Candela believes neural networks can be useful for such tasks. "You can give a neural network a problem without having to know much about the problem itself and it will give you results. Of course, the more you know about the problem, the better and more accurate the results will be," he explains.

The software is designed to work on workstations from Digital Equipment Corp., Hewlett-Packard, IBM, Silicon Graphics, Challenge, and Sun Microsystems. It can also work on personal computers, but requires modifications.

For a copy of the free CD-ROM, write on company letterhead to Gerald T. Candela, NIST, Bldg. 225, Room A216, Gaithersburg, MD 20899, or call (301) 975-3388, Fax (301) 840-1357, or e-mail: [email protected].

R. P.

Company Information

Cambridge Neurodynamics

Cambridgeshire, CB4 4WS England

223-421107

Web: www.camneuro.stjohns.co.uk

Net-ID

San Francisco, CA 94107

(415) 647-9402

Web: www.netid.com

NIST

Gaithersburg, MD 20899

(301) 975-3388

Web: www.nist.gov

University of Missouri at Rolla

Rolla, MO 65401

(573) 341-4374

Web: www.umr.edu