The Problem
Fingerprints have been used for personal
identification for centuries. For many
applications such as bank Automatic Teller Machine (ATM) access, credit card
transaction authorization, user identification on computer systems and building
access, fingerprints have been the primary method. For a means of automatic identification, it has been not only
been the oldest, but the most reliable method because of the invariance of the
fingerprint features over the age of a person.
Recent advances in inkless image capturing devices for
fingerprint image attainment, has generated significant interest in using
fingerprints for several other civil applications. One of the newest and most interesting involves the FBI. Between 1924 and today, the FBI has
collected over 30 million sets of fingerprints. Their archive consists of mainly inked impressions on paper
cards. Facsimile scans of the
impressions are taken for storage. Over
the past 70 years, their collection has grown to over 200 million cards of
prints, occupying over an acre of filing cabinets in the J. Edgar Hoover
building in Washington. This collection
includes over some 29 million records that need to be examined every time a
criminals’ print needs to be checked.
In the U.S. some 40,000 fingerprints must be treated, classified and
compared every day. Besides the FBI,
all of the police force in the United States must manage multiple fingerprint
collections.
Recently, in 1993, the FBI had set out to design and
implement a national standard for coding and compression of digitized
fingerprint images. This was done
because a number of jurisdictions had been experimenting with digital storage
of fingerprints, and incompatibilities between data formats had been starting
to become a problem. In image
acquisition, a digital image of a fingerprint is captured either from the live
person’s fingers, or from an existing inked paper record. Methods that are more recent involve using
inkless methods. Currently, there are
four different technologies available.
Among them include optical, ultrasonic, electrical field, and
thermal. After the image is acquired,
the feature extraction stage involves representing the fingerprint for
matching. In matching, a decision is
made about the confirmation of the fingerprints closeness the fingerprints in
the database.
One problem that the FBI ran into when going digital is
that they had an enormous amount of data to store. Their images were to be digitized at a resolution of 500 dots per
inch (dpi), with 256 levels of grey-scale per dot. With a single fingerprint, like the one shown in Figure 2,
containing almost 700,000 dpi, it would need about 0.6 megabytes of electronic
storage space.
Figure 2. Sample
Inked Fingerprint.
Put that together with the
fact that the FBI takes prints of both hands of suspects, and this results in
approximately 10 megabytes per 8 inch by 8 inch card. A sample of what one of these cards looks like can be shown here
in Figure 3.
Figure 3. Sample
Fingerprint Card.
Sometimes repeat offenders
can have more than one card. Looking at
the big picture, the FBI would now require nearly 200 terabytes of electronic
storage space. With today’s rate of
crime coupled with the price of hard-disk space, the cost of storing all these
uncompressed images would be about 200 million dollars. In addition, if one of these cards was to be
transmitted over a modem it could take up to 3 hours alone. To make matter worse, fingerprint data
continues to accumulate at a rate of 30,000 – 50,000 new cards per day. It was obvious that the FBI look into some
sort of data compression to reduce wasted time and money.
It was originally considered that the FBI would use a
method known as Joint Photographic Experts Group (JPEG). JPEG, a new compression algorithm, was based
on a Discrete Cosine Transform on blocks of 8 by 8 pixels or dots. In the case with the FBI, the images of the
fingerprints were in monochrome, 256 grey-scale, and always the same size and
looked very similar. While JPEG did a
very good job lowering the compression ratio, from 5:1 to 10:1, the results
were often unacceptable, as shown here in Figure 4.
(a)
(b)
Figure 4. (a) Original Fingerprint
(b) JPEG Compressed Fingerprint.
These results were
unacceptable and appeared grainy because of the 500 dpi scan. They needed to be more detailed because tiny
white spots in the black ridges of fingerprints contain sweat pores, shown here
in Figure 5. These sweat pores are
admissible points in court criminal cases.
Likewise were the little black flesh islands in the grooves between the
ridges, shown in Figure 5.
Figure 5. Fingerprint
Details.
These ridge endings and
bifurcation’s form permanently in childhood.
There are about 150 of them per finger, and these details are just a
couple of pixels wide. Often times in court, the presence of 12 or more can be
the difference in the jury’s decision.
The compression methods needed to be better to preserve the features
right at the resolution of the scan, whether it is a good print or a bad
one. Some examples of good and bad
fingerprints are shown in Figure 6.
Figure 6. Fingerprint
Qualities. (a) Good, (b) Fair, (c) Poor
The
problem was that most lossy algorithms work by throwing out the smallest,
highest frequency, details. In short,
they must provide an alternative to JPEG which must be clearly better in some
cases, in particular when compressing aggressively large images. The FBI decided to use wavelets for their
great compression ratios, along with their filtering techniques, which do not
discard minor details because they can be preserved.