3. PACKAGES

3.1 PCASYS - Fingerprint Pattern Classification

Automatic fingerprint classification is a subject of interest to developers of an Automated Fingerprint Identification System(AFIS). In an AFIS system, there is a database of file fingerprint cards, against which incoming search cards must be efficiently matched. Automatic matchers now exist that compare fingerprints based on their patterns of ridge endings and bifurcations(the minutiae). However, if the file is very large, then exhaustive matching of search fingerprints against file fingerprints may require so much computation as to be impractical. In such a case, the efficiency of the matching process may be greatly increased by partitioning the file based on classification of fingerprints. Once the class foreach fingerprint of the searchcard has been determined, these tof possible matching filecards can be restricted to those whose 10-tuple(one foreach finger) of classes matches that of the searchcard. This reduces the number of comparisons that must be performed by the minutiae-matcher. Some fingerprint identification systems use manual classification followed by automatic minutiae matching; the standard Henry classification system, or a modification or extension of it, is often used. The handbook[36] provides a complete description of a manual classification system. Automating the classification process would improve its speed and cost-effectiveness. However, producing an accurate automatic fingerprint classifier has proved to be a very difficult task. The object of there search leading to PCASYS is to build a prototype classifier that separates fingerprints into basic pattern-level classes known as arch, leftloop, rightloop, scar, tented arch, and whorl. Figure2 shows example fingerprints of the several classes. The system performs these steps: image segmentation and enhancement; feature extraction, registration,and dimensionality reduction; running of a main classifier, either a Probabilistic or Multi-Layer Perceptron NeuralNetwork and an auxiliary whorl-detector that traces and analyzes pseudo- ridges; and finally, creation of a hypothesized class and confidence level. PCASYS is a prototype/demonstration pattern-level fingerprint classification program. It is provided in the form of a sourcecode distribution and is intended to run on a desktop workstation. The program reads and classifies each of a set of fingerprint imagefiles, optionally displaying the results of several processing stages in graphical form. This distribution contains 2700 fingerprint images that may be used to demonstrate the classifier; it can also be run on user-provided images.

The basic method used by the PCASYS fingerprint classifier consists of, first, extracting from the fingerprint to be classified an array(a two-dimensional grid in this case) of the local orientations of the fingerprint's ridges and valleys. Second, comparing that orientation array with similar arrays made from prototype fingerprints ahead of time. The comparisons are actually performed between low-dimensional feature vectors made from the orientation arrays, rather than using the arrays directly, but that can be thought of as an implementation detail.

Figure 2. Example fingerprints of the six pattern-level classes. Going left-right, top-bottom, arch [A], left loop [L], right loop [R], scar [S], tented arch [T], and whorl [W]. These are NIST Special Database 14 images s0024501.wsq, s0024310.wsq, s0024304.wsq, s0026117.wsq, s0024372.wsq, and s002351.wsq, and they are among the fingerprint images included on the CD-ROM in test/pcasys/data/images.

Orientation arrays or matrices like the ones used in PCASYS were produced in early fingerprint work at Rockwell, CALSPAN, and Printrak. The detection of localridge slopes came about naturally as a side effect of binarization algorithms that were used to preprocess scanned fingerprint images in preparation for minutiae detection. Early experiments in automatic fingerprint classification using these orientation matrices were done by Rockwell, improved upon by Printrak, and work was done at NIST(formerly NBS). Wegstein, of NBS, produced the R92 registration algorithm that isused by PCASYS and did important early automatic classification experiments.[8] The algorithms used in PCASYS are described further in Section4.1 and in References[17] and [22]-[24].

3.2 MINDTCT - Minutiae Detection

Another software system provided in this distribution is a minutiae detection package called, MINDTCT. This section first describes what fingerprint minutiae are, and then some background is provided as to why this package was developed for the FBI.

3.2.1 Definition of Minutiae

Traditionally,two fingerprints have been compared using discrete features called minutiae. These features include points in a finger's frictionskin where ridges end(called a ridgeending) or split(called a ridge bifurcation). Typically, there are on the order of 100 to 200 minutiae on a tenprint. In order to search and match fingerprints, the coordinate location and the orientation of the ridge at each minutia point are recorded. Figure3 shows an example of the two types of minutiae. The minutiae are marked in the right image, and the tails on the markers point in the direction of the minutia's orientation.

Figure 3. Minutiae: bifurcation (square marker) and ridge ending (circle marker).

The location of each minutia is represented by a coordinate location within the fingerprint's image. Different AFIS systems represent this location differently. The ANSI/NIST standard specifies units of distance in terms of 0.01mm from an origin in the bottomleft corner of the image. For example, a 500OE600 pixel image scanned at 19.69ppmm has dimensions 25.39OE30.47mm which in standard units of 0.01mm is 01.069.19 600 01.069.19 50030472539 ***=* Thus, the pixel coordinate(200,192) will be represented in standard units at ( ) \Delta \Theta \Lambda \Xi \Pi \Sigma *--*= 01.069.19 19213047,01.069.19 2002071,1016 where the Y-coordinate is measured from the bottom of the image upward. The orientation of the minutiae is represented in degrees, with zero degrees pointing horizontal and to the right, and increasing degrees proceeding counter-clockwise. The orientation of a ridge ending is determined by measuring the angle between the horizontal axis and the line starting at the minutiapoint and running through the middle of the ridge. The orientation of a bifurcation is determined by measuring the angle between the horizontal axis and the line starting at the minutia point and running through the middle of the intervening valley between the bifurcating ridges. The minutiae plotted in Figure4 illustrate the line to which the angle of orientation is measured. Each minutia symbol is comprised of a circle or square, marking the location of the minutia point, and the line or tail proceeding from the circle or square is projected along either the ridge ending's ridge, or the bifurcation's valley. The angle of orientation as specified by the ANSI/NIST standard is marked as angle X in the illustration.

Figure 4. Minutiae orientation. A. standard angle, B. FBI/IAFIS angle A B AB

3.2.2 Latent Fingerprints

In addition to tenprints, there is a smaller population of fingerprints also important to the FBI. These are fingerprints captured at crime scenes that can be used as evidence in solving criminal cases. Unlike tenprints, which have been captured in a relatively controlled environment for the expressed purpose of identification, crimescene fingerprints are by nature incidentally left behind. They are often invisible to the eye without some type of chemical processing or dusting. It is for this reason that they have been traditionally called latent fingerprints.

As one would expect, the composition and quality of latent fingerprints are significantly different from tenprints. Typically, only a portion of the finger is present in the latent, the surface on which the latent was imprinted is unpredictable, and the clarity of frictionskin details are often blurred or occluded. All this leads to fingerprints of significantly lesser quality than typical tenprints. While there are 100 to 200 minutiae on a tenprint, there maybe only a dozen on a latent. Figure5 shows a "good" quality latent on the left and its matching tenprint on the right.

Figure 5. Latent fingerprint (left) with matching tenprint (right).

Due to the poor conditions of latent fingerprints, today's AFIS technology operates poorly when presented a latent fingerprint image. It is extremely difficult for the automated system to accurately classify latent fingerprints and reliably locate the minutiae in the image. Consequently, human fingerprint experts, called latent examiners, must analyze and manually markup each latent fingerprint in preparation for matching. This is a tedious and labor intensive task.

To support the processing of latent fingerprints, the FBI and NIST collaboratively developed a specialized workstation called the Universal Latent Workstation(ULW). This workstation has been designed to aid the latent examiner in preparing a latent fingerprint for search. In addition, the workstation provides for interoperability between different AFIS systems by functioning as a vendor-independent front-end interface. These two aspects of the ULW contribute significantly to the advancement of the state-of-the-art in latent fingerprint identification and law enforcement in general. As such, the FBI has chosen to distribute the ULW freely upon request. To receive more in formation regarding ULW, please contact:

Tom Hopper(thopper@leo.com)
FBI,JEHBldg.
CJISDiv/Rm11192E935PAAve.,NW Washington,DC
20537-9700
202-324-3506

The successful application of the ULW is primarily facilitated by its use of the ANSI/NIST-ITL1-2000 standard. NIST also developed some its underlying core technology, including the minutiae detection package in this software distribution. MINDTCT takes a fingerprint image and locates all minutiae in the image, assigning to each minutia point its location, orientation, type, and quality. The command, mindtct, reads a fingerprint image from an ANSI/NIST file, detects the minutiae in the image, encodes the results into a Type-9 minutiae record[30], combines the record with the input data, and writes it all out to a new ANSI/NISTfile. An algorithmic description of MINDTCT is provided in Section4.2.

3.3 AN2K - Standard Reference Implementation

The AN2K package is a reference implementation of the ANSI/NIST-ITL 1-2000 standard. [30] This package contains utilities for reading, writing, and manipulating the contents of ANSI/NIST datafiles. These files are comprised of a sequence of data fields and image records. Sourcecode is provided to parse ANSI/NIST files into memory, manipulate designated fields, and write the sequence back to file. The utility an2ktool does this in batchmode. Logical dataunits are referenced on the commandline, and the specified contents may be printed, inserted, substituted, or deleted from the file. Alternatively, two other utilities are provided to support interactive editing of the contents of an ANSI/NIST file. The command an2k2txt converts the textual content of an ANSI/NIST file in to a formatted textreport, and any binarydata(including images) are stored to temporary files and externally referenced in the textreport. In this way, the textreport can then be loaded in to any common text editor and ASCII information can be added, deleted, or changed. When all edits are complete, the command txt2an2k is run on the edited version of the textreport, externally referenced binary data files are incorporated, and a new ANSI/NIST file is written.

One of the many types of records in an ANSI/NIST file is the Type-9 record designed to hold minutiae data for fingerprint matching. Currently there is no global consensus on how fingerprint minutiae should be numerically represented. Different fingerprint systems use different sets of attributes and representation schemes. To manage this, the fields of the Type-9 record have been divided into blocks, where each block is assigned to a registered vendor, and the vendor defines how he will represen this minutiae data. In the standard, the first 4 fields of the Type-9 record are mandatory and must always be filled. Fields 5 through 12 are fields in the standard defined by NIST to hold among other things, the fingerprint's core, delta, and minutiae locations, along with neighbors and intervening ridge counts. The FBI's IAFIS is assigned fields 13 through 23. The definition of these fields is specified in the FBI's Electronic Fingerprint Transmission Specification(EFTS), Reference[37]. Unfortunately, these two blocks of fields are different. Two utilities are provided in the AN2K package to facilitate the conversion between these blocks of fields in a Type-9 record. The command an2k2iaf translates the minutiae data stored in NIST fields 5-12 into the FBI/IAFIS fields 13-23. The command iaf2an2k reverses the process. An XWindows ANSI/NIST file image previewer is included in the package. The utility dpyan2k is designed to parse an ANSI/NIST file, locating and displaying each image in the file to a separate window. In addition, if any minutiae are included in a corresponding Type-9 record, then the minutia points are plotted on top of the fingerprint image.

3.4 IMGTOOLS - General Purpose Image Utilities

NIST has distributed several fingerprint databases [14], [18]-[20] over the past decade for use in evaluating fingerprint matching systems. The images in these databases are formatted as NIST IHead [14],[18] files using either Lossless JPEG or WSQ compression. The IHead format uses a 296 byte header to store basic information about the image(i.e. pixelwidth, height, depth, compressiontype, compressedlength, etc.). Displaying these images is problematic as common image viewing utilities do not support this format. Using utilities in the IMGTOOLS package, users are able to take NIST legacy database files and convert them into standard compliant formats, including Baseline JPEG which is widely supported. Another issue is that these legacy files are not standard compliant. The utility sd_rfmt takes a legacy database file and reformats it. For example, legacy IHead WSQ files are converted so that they can be decoded with an FBI compliant WSQ decoder. The command dwsq14 decompresses fingerprint images distributed with NIST Special Database14, while the command djpeglsd decompresses images distributed with NIST Special Database4,9,10,&18.[25] IMGTOOLS also contains a collection of standard compliant and certifiable image encoders and decoders. The utilities cjpegb and djpegb encode and decode Baseline JPEG files respectively. The utilities cjpegl and djpegl encode and decode Lossless JPEG files. This represents one of the only publicly available implementations of the standard LosslessJPEG algorithm. Finally, theutilities cwsq and dwsq encode and decode FBI WSQ files. An XWindow application, dpyimage, is provided to view these different file compression formats, including IHead images and rawpixmaps.

Users should exercise caution when using these encoders and decoders in succession. The decoders generate uncompressed, reconstructed imagepixmaps that can be subsequently re- encoded. Both Baseline JPEG and WSQ are lossy compression schemes, so taking their decoded pixmaps and re-encoding them may produce undesirable results. The amount of image degradation caused by lossy compression can be analyzed using the utility diffbyts to compare the pixels in an original image to those returned by one of the decoders.

All three compression algorithms in this distribution support internal comment blocks. Applications typically need easy access to various image attributes. These attributes include generic statistics such as pixel width, height, depth, and scan resolution, but often it is desirable to store and retrieve application-specific information such as fingerprint type, mugshot pose, or age/sex of the individual. To support applications, a structure called a NISTCOM has been defined, containing a text-based attribute list of(name,value)pairs. The encoders in IMGTOOLS accept an optional NISTCOM file, and if provided, embed its contents into a comment block within the encoded bytestream. The decoders on the other hand, search the encoded by testream for the presence of a NISTCOM, and if found, merge its contents with those attributes the decoder derives itself and writes the resulting attribute list to a separate text file with extension "ncm" For more information on the NISTCOM convention, please refer to the Reference Manual in AppendixB. A NISTCOM stored in a JPEG or WSQ file does not interfere with other standard compliant decoders because it is contained in a standard comment block.

Several commands are provided to support NISTCOM and comment blocks in general. The utilities rdjpgcom and wrjpgcom read and write comments blocks to and from both Baseline and Lossless JPEG files. Similarly, rdwsqcom and wrwsqcom read and write comment blocks to and from WSQ files. Two other capabilities are included in IMGTOOLS. The first handles the interleaving and non-interleaving of color components in an image. The command intr2not takes an interleaved color image and separates the components into individual planes, whereas the command not2intr reverses the process. These condcapability handles converting between RGB and YCbCr colorspaces. The command rgb2ycc converts from RGB to YCbCr, and ycc2rgb reverses the process.