This page contains a summary of the Federal Bureau of Investigation's image coding standard for digitized fingerprints, developed and maintained by the FBI, Los Alamos National Lab, and the National Institute for Standards and Technology. The standard is a discrete wavelet transform-based algorithm referred to as Wavelet/Scalar Quantization (WSQ).
The goal of this project is to design and implement a national standard for coding and compression of digitized fingerprint images. The FBI is digitizing the nation's fingerprint database at 500 dots per inch with 8 bits of grayscale resolution. At this rate, a single fingerprint card turns into about 10 MB of data!
Here's a sample fingerprint image measuring 768 x 768 pixels
(= 589,824 bytes):
``Big deal,'' I hear you saying, ``I've got a gigabyte disk on my computer!''
Yes, but the FBI has been collecting fingerprint cards since 1924, and because (like most of us) they find it hard to throw things out, over the past 70 years their collection has grown to over 200 million cards occupying an acre of filing cabinets in the J. Edgar Hoover building back in Washington. (No; they don't have the entire U.S. population in their files, just lots of ``repeat customers.'') This includes some 29 million records they examine each time they're asked to ``round up the usual suspects.''
Your gigabyte drive starts to look pretty puny when faced with 2,000 terabytes' worth of images. And to make matters worse, fingerprint data continues to accumulate at a rate of 30,000-50,000 new cards PER DAY, which makes for a serious traffic jam on the Information Superhighway. (Go ahead; compute the time required to send a 10 MB card over the 9600 baud modem they're still using in Mayberry RFD. Hint: with a 20% communications overhead reducing the data rate to 7680 bits/second, it'll take just under 3 hours!)
``Okay,'' you say, ``so they need to use data compression. Better use a lossless method to preserve every pixel perfectly.''
Unfortunately, in practice lossless methods haven't done better than 2:1 on fingerprints. The FBI needs more than an order of magnitude reduction in bits to make a serious dent in this database. That implies lossy compression, which means we're going to have to tolerate some distortion in the compressed images.
``No problem! They can use the new ISO JPEG standard, which will work on ANY type of image.''
Well, maybe; let's see how well it performs on this type of data, though. Here's a 4x zoom of the ``core'' (or center) of the fingerprint image we saw above. The graininess you see represents the individual pixels in the 500 dpi scan. The white spots in the middle of the black ridges are sweat pores, and they're admissible points of identification in court, as are the little black flesh ``islands'' in the grooves between the ridges. Since these details are just a couple pixels wide, our compression method needs to preserve features right at the resolution of the scan, a VERY tough problem since most lossy algorithms work by throwing out the smallest (or highest frequency) details in the image.
Original image; file size 589824 bytes.
(Click on the picture to get a non-embedded copy.)
Now see what's left after JPEG compression with a compression ratio of 12.9. Not very attractive for what's supposed to be an archival quality image. The fine details are pretty much history, and the whole image has this artificial ``blocky'' pattern superimposed on it. These blocking artifacts annoy the bejeesus out of human end-users like the FBI's fingerprint experts, who do NOT like seeing computers munch their precious data and are pretty leery of this whole ``data compression'' thing in the first place. What's more, the blocking artifacts also affect the performance of automated systems that attempt to trace out ridges to help classify the fingerprint.
JPEG image; file size 45853 bytes, compression ratio 12.9.
Next take a look at the same image compressed 12.9:1 by the WSQ method (the algorithm chosen over JPEG for this project). The fine details are preserved better than they are with JPEG, and there are NO blocking artifacts!
WSQ image; file size 45621 bytes, compression ratio 12.9.
For this particular application, where image quality is the preeminent concern, wavelet transform coding is superior.
Or, skip to end.
Last updated 25 June 2002.