STATES

I MENT OF ERCE

NATION

National Bureau of Standards

Library, E-01 Admin. Bldg.

DEC 3 1970

NBS TECHNICAL NOTE 538

ro» c.K

\f

Automated

Fingerprint

Identification

U.S.

ARTMENT

OF

|»MMERCE

National

Bureau

of

Standards

B
NBS TECHNICAL PUBLICATIONS

PERIODICALS NONPERIODICALS

JOURNAL OF RESEARCH reports National

Bureau of Standards research and development in physics, mathematics, chemistry, and engineering.

Comprehensive scientific papers give complete details of the work, including laboratory data, experimental

procedures, and theoretical and mathematical analyses. Illustrated with photographs, drawings, and

charts.

Published in three sections, available separately: • Physics and Chemistry

Papers of interest primarily to scientists working in these fields. This section covers a broad range of

physical and chemical research, with major emphasis on standards of physical measurement, fundamental

constants, and properties of matter. Issued six times a year. Annual subscription: Domestic, $9.50; for- eign, $11.75*. • Mathematical Sciences

Studies and compilations designed mainly for the mathematician and theoretical physicist. Topics in mathematical statistics, theory of experiment design,

numerical analysis, theoretical physics and chemistry, logical design and programming of computers

and computer systems. Short numerical tables. Issued quarterly. Annual subscription: Domestic,

$5.00; foreign, $6.25*. • Engineering and Instrumentation

Reporting results of interest chiefly to the engineer

and the applied scientist. This section includes many

of the new developments in instrumentation resulting

from the Bureau's work in physical measurement,

data processing, and development of test methods.

It will also cover some of the work in acoustics,

applied mechanics, building research, and cryogenic

engineering. Issued quarterly. Annual subscription:

Domestic, $5.00; foreign, $6.25*.

TECHNICAL NEWS BULLETIN

The best single source of information concerning the Bureau's research, developmental, cooperative and

publication activities, this monthly publication is designed for the industry-oriented individual whose

daily work involves intimate contact with science and

technology

for engineers, chemists, physicists, re- search managers, product-development managers, and

company executives. Annual subscription: Domestic,

$3.00; foreign, $4.00*.

* Difference in price is due to extra coat of foreign mailing. Order NBS publications from: Superintendent of Documents

Government Printing Office

Washington, D.C. 20402

Applied Mathematics Series. Mathematical tables, manuals, and studies. Building Science Series. Research results, test methods, and performance criteria of building ma- i terials, components, systems, and structures. Handbooks. Recommended codes of engineering

and industrial practice (including safety codes) de- veloped in cooperation with interested industries,

professional organizations, and regulatory bodies. Special Publications. Proceedings of NBS conferences, bibliographies, annual reports, wall charts,

pamphlets, etc. Monographs. Major contributions to the technical

literature on various subjects related to the Bureau's

scientific and technical activities. National Standard Reference Data Series.

NSRDS provides quantitive data on the physical

and chemical properties of materials, compiled from

the world's literature and critically evaluated.

Product Standards. Provide requirements for sizes, types, quality and methods for testing various industrial products. These standards are developed cooperatively with interested Government and industry groups

and provide the basis for common understanding of product characteristics for both buyers and sellers. Their use is voluntary.

Technical Notes. This series consists of communications and reports (covering both other agency and

NBS-sponsored work) of limited or transitory interest. Federal Information Processing Standards Publications. This series is the official publication within

the Federal Government for information on standards

adopted and promulgated under the Public Law

89-306, and Bureau of the Budget Circular A-86

entitled, Standardization of Data Elements and Codes

in Data Systems.

CLEARINGHOUSE

The Clearinghouse for Federal Scientific and

Technical Information, operated by NBS, supplies

unclassified information related to Government-generated science and technology in defense, space, atomic energy, and other national programs. For

further information on Clearinghouse services, write: Clearinghouse

U.S. Department of Commerce

Springfield, Virginia 22151
11 BURFAU OF STANMKS

UNITED STATES DEPARTMENT OF COMMERCE

Maurice H. Stans, Secretary

NATIONAL BUREAU OF STANDARDS • Lewis M. Branscomb, Director

NBS TECHNICAL NOTE 538

ISSUED AUGUST 1970

Nat. Bur. Stand. (U.S.), Tech. Note 538, 33 pages (Aug. 1970)

CODEN: NBTNA

Automated Fingerprint Identification

J. H. Wegstein

Center for Computer Sciences and Technology

National Bureau of Standards

Washington, D.C. 20234

^°'c ,

NBS Technical Notes are designed to supplement the Bureau's regular publications program. They provide a means for making available scientific data that are of transient or limited interest. Technical Notes may be

listed or referred to in the open literature.

For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C, 20402

(Order by SD Catalog No. CI 3.46:538). Price 40 cents

Contents

Page

1. Introduction 1

2. Tools for Performance Analysis 2

3. Experimental Results with

Constellation Matcher 4

4. A Statistical Matching Procedure 5

5. Experimental Results with

Statistical Matchers 8

6. Discussion of Results 10

7. References 12

III

Automated Fingerprint Identification

by J.H. Wegstein

A procedure is described for determining

whether two fingerprint impressions were made by

the same finger. The procedure uses the x and y

coordinates and the individual directions of the

minutiae (ridge endings and bifurcations). The

identity of two impressions is established by

computing the density of clusters of points in

Ax - Ay space where Ax and Ay are the differences

in coordinates that are found in going from one

of the fingerprint impression to the other.,

Experimental results using machine-read minutiae

data are given along with results from a previously reported procedure that utilized

constellations of minutiae in its matching process.

Key words: Computerized-fingerprint- identification,

fingerprint, pattern recognition.

1. Introduction

This paper follows a previous paper * that describes a procedure

for matching fingerprint impressions by computer using two types of

minutiae: ridge endings and bifurcations. With a fingerprint impression

in the first quadrant, data is obtained by reading the X coordinate,

Y coordinate, and the angle 8 which the minutia direction makes with

the X axis for each minutia in the print. When the data is taken

manually, 9 is measured in degrees and X and Y are measured in units

of one tenth millimeter on an actual fingerprint or a millimeter on a ten-fold enlargement of the print. There are about 80 minutiae in an average rolled fingerprint.

To test the performance of a matching procedure, the minutiae data

for a set of fingerprints is entered into a computer file. Next,

working with minutiae data for a second set of prints (the search prints),

the computer compares each of the search prints with each of the prints

in the file. Thus, if there are N prints in the file and n search

prints, the computer will make n x N comparisons in a given matching run. Each comparison yields a score and the higher the score the more likely

it is that both of the prints being compared came from the same finger.

In the course of adjusting parameters and improving matching procedures

many thousands of pairs of prints have been compared. These experiments

have used data that was read manually at the National Bureau of Standards

as well as data that was read by machine at the Autonetics Division of

North American Rockwell Corporation and Cornell Aeronautical Laboratory,

Inc.
2. Tools for Performance Analysis

In the development of pattern recognition techniques it is

essential to have ways of measuring performance. New results, after

a change in the recognition technique, must be compared with previous

results and ultimately it should be possible to compare the achievements

of one research effort with the achievements of others in the same field of endeavor.

One tool for displaying the results of fingerprint recognition as well as voice signature recognition is a score matrix . For example if

a set of five fingerprints identified as XIII-I, XIII-2, , XIII-5 is

compared with a file of twenty prints identified as XIV-1, XIV-2, , XIV-20, the results can be displayed as shown in Figure 1. Each of the

100 pairs of prints are compared and the resulting score is entered

in the matrix. In Figure 1 prints XHI-n and XlV-n came from the same finger where n=l, 2, 5. Therefore the leftmost diagonal should

contain the highest scores in the matrix.

In voiceprint file searches, Tosi has defined a closed task

as a file search in which the search print is known to be in the file.

The searcher must simply find the best match. Analogously, if print

XIII-2 is known to be in the file, then one need only look for the

highest score, 80, in the XIII-2 row. Tosi has defined an open task

as a file search in which the searcher does not know if the print being

sought is in the file. This is a difficult task because the searcher

must judge if the degree of match exceeds some threshold value . By

analogy, if a score of 70 is set as a threshold for a match in this

fingerprint file search, then XIII-1, XIII-2, and XIII-3 would be

correctly identified. However, the search would conclude that XIII-4

and XIII-5 were not in the file. The discrimination matrix can be

reduced to a binary matrix by recording only scores that exceed the

threshold as X and leaving all other spaces blank.

If a computer is comparing an unknown print with prints in a file

as a closed task , the computer will always indicate that some print

from the file has the highest matching score and a fingerprint expert

must compare the unknown print with the file print to determine if

they are from the same finger. In a practical system where some of

the unknown prints are not in the file, the expert must still look at some file print for each of the unknown prints. On the other hand, if

the computer is operating in the open task mode, it will indicate only

those prints from the file that exceed some matching score threshold.

The obvious objective in the design of a matching procedure is to

achieve such a level of discrimination that only those pairs of prints

that came from the same finger will exceed the matching score threshold

and require verification by the fingerprint expert.

In order to compare the performance of one matching run with

another, one might reduce the data in a discrimination matrix to two

numbers: M the percentage of misses, and F the percentage of false
matches. Let

TM = total number of matches that should have occurred

TF = total number of failures to match that should have occurred

MS = number of misses

FM = number of false matches

100 MS then M =

F =

TM

100 FM

TF

In Figure 1, TM = 5, TF = 95 and if a threshold score has been set

at 50, MS = 1 and FM = 3 Therefore F = 3.2% and M = 20%.

The values of F and M can be plotted against their corresponding

threshold scores as shown in Figure 2„ As the threshold value decreases,

the percentage of misses decreases as is shown by the solid line.

Unfortunately, this is accompanied by an increase in the number of

false matcheso When a . large number of prints are compared, the curves appear to be exponential curves as shown in Figure 3. The point P

where the curves cross is of considerable interest in perfecting

a matching procedure. P should be as low as possible when a very

large number of fingerprints are compared,,

The F and M scores are actually impractical for tuning and

improving matcher performance with the available general purpose

computer because more than 26 pairs of prints in a given matching

run exceeds the storage capacity of the high speed memory. When a promising level of performance is achieved, there will be a significant

portion of the curves where F and M are zero as seen in Figure 4.

Accordingly, three other scores are used: OS, CS, and AA. OS is used

to measure performance as an open task and is the highest score for a pair of prints that should not match divided by the lowest score for a pair of prints that should match multiplied by 100 (rounded to the

nearest integer). Using the data from Figure 1,

OS = || x 100 = 149.

CS is used to measure performance as a closed task. In Figure 1, the

highest off-diagonal score in each row is divided by the diagonal score

for that row (where there should be a match) and this is multiplied by

100. Thus, there is a score for each row. The highest (or worst) of

these is taken as the score CS. In Figure 1, CS = 124, corresponding to

the highest row score, occurring in row 5, where

46 ^ x 100 = 124.
A print is correctly identified if CS < 100, and the objective in this

developmental work is to obtain as low a value as possible for CS and OS.

One bad print in the set can cause CS and OS to be very high, but

the matcher may be doing a relatively good job with the rest of the

prints. Accordingly, still another score, AA, is defined as the mean

off-diagonal score divided by the mean diagonal score times 100. In

Figure 1,

19 95

AA = Z*/l

D x 100 = 26

76. 6

It is desirable to have as low a value as possible for AA.

3. Experimental Results with Constellation Matcher

The fingerprint matcher reported in NBS Technical Note 466 1 " as well as several subsequent variations of this matcher compared two fingerprint impressions by finding several minutiae (a constellation) in one print that approximately coincide with a similar constellation from

another print. Relative positions of the minutiae as well as direction

angles of the minutiae were utilized in computing whether or not there was a coincidence„ To minimize the amount of computer time and data

storage required, only a portion of the available minutiae from a fingerprint was used. Only those minutiae in a circle of 6mm radius

centered at the core of the print were used, and there was an average

of about 24 minutiae in the circle on the prints used. Using minutiae

that were carefully read manually, matching twenty pairs of average

fingerprint impressions after extensive parameter tuning and matcher

modifications led to the results shown in Figure 4. Here, the number

of minutiae in the constellation being matched is used as the score and

hence as the discrimination factor. The point P has been lowered to

zero, but the range in the number of minutiae in the matching constellation

is discouraging. The maximum number of nine matching minutiae found

here fall short of the 12 or more predicted by Caudra * as necessary

to get adequate odds in favor of recognizing two prints from the same finger when working with a large file If other parameters in the

matcher are "loosened up" such as increasing the allowable difference

in position of matching minutiae, then the number of false matches

invariably rises.

The reason for a false match can be seen by referring to Figure 5 Minutiae tracings from fingerprint impression XIII-11 (enlarged 10 times) are superimposed on tracings from impression XIV-2 which came from a different finger. Minutiae XIII- 11-48 is positiqned to coincide with

minutia XIV-2- 13. If the maximum allowed difference in coordinate

values for the other minutiae are:

AX = 6 units

AY = 6 units

A0 =15 degrees.

4
then the two constellations of seven minutiae produce a false match.

If parameter AX or AY is reduced to 5 units then this false match is

eliminated.

On the other hand, these same parameters may fail to produce matches

of two impressions from the same finger because of ever-present

distortions,. All rolled fingerprint impressions tend to be stretched or twisted in varying amounts „ To illustrate a worse- than usual case,

minutiae from impression IIP2 are superimposed on minutiae from impression

IIP8 in Figure 6. Both impressions are from the same finger and

minutia 79 is positioned to coincide with minutia 79'. While minutiae

79, 33, and others to the left tend to coincide, minutiae to the right

move further and further apart. Furthermore, distortions may be

strangely localized,, In Figure 7 two different impression IIP5 and IIP6

from the same finger are superimposed with minutiae 28 and 28' coinciding.

While the degree of coincidence is good in the upper left, lower left,

and lower right, there is X-distortion in the upper right portion of

the print.

The method of matching pre-defined portions of fingerprints by

starting with some minutia as a nucleus and developing a constellation of

coinciding minutiae has been unsatisfactory. The main reason for this

is that only five minutiae were tried as the nucleus for a constellation.

This number was limited to five in order to hold down the amount of

computing time needed on a general purpose computer to make extensive

matching tests. It may be that trying more minutiae as a nucleus would

result in satisfactory matching. To adequately test this method of

matching prints, it will either be necessary to use more generalpurpose computer time or use a special- purpose device designed for

minutiae matching such as that described by Thiebault " ' which can utilize parallel operations for very fast matching,,

4. A Statistical Matching Procedure

In spite of the distortion shown in Figure 7, it is desirable to

take advantage of those pairs of minutiae such as 28, 27, 34, 35, 52,

53, 70, 74, and 75 and others not shown that do coincide. To illustrate

how this can be done, some minutiae data from four prints will be used.

In Figure 8, the print A and B data are from two different prints made

by the same finger and the print C and D data are from prints from two

different fingers. Minutiae i in print A is the same as minutiae j in

print B if i = j. Minutia 6 (labeled B6 in Figure 9) is not found in

print A. The minutiae of both prints are plotted in Figure 9. This is

typical of the appearance of superimposed minutiae from two prints that

have been read by machine. One print is rotated about six degrees and

is shifted about 35 units in the x direction with respect to the other

print, but, of course, this information is unknown to the computer when

it attempts to match these prints. Figure 10 shows the superimposed

minutiae from prints C and d.
The M19 Matcher

The simplest version of the statistical matcher, known as M19,

begins by computing

Ax = x . - x

.

i J Ay = y±

- y

A0 = 0. - 9.

1 J for all possible combinations of pairs of minutiae. Only those pairs

of minutiae that satisfy the following conditions simultaneously are retained.

| Ax | ^ LS

| Ay | ^ LS

Ia8| £ L9

If the matcher parameters have the values

LS = 60

L0 = 25

then the resulting difference table for prints A and B is shown in

Figure 11 and the difference table for prints C and D is shown in

Figure 12. These points can be plotted in a Ax, Ay coordinate system

as shown in Figure 13 for prints A and B and in Figure 14 for prints C

and D. If the prints are from the same finger, then many points will

tend to be in a cluster as seen in Figure 13» If the prints are from different fingers, then the points tend to be randomly located over the entire area. It will be noted that there is no pronounced clustering

in Figure 14.

The task of the matcher is to compute a matching score that

increases as the density of the cluster increases. The M19 matcher

accomplishes this by starting from each point in the graph and counting

the number of steps in the Ax and Ay directions to each of the other

points o If this number of steps, TR, is less than a matcher parameter

KR, then the quantity KR-TR is added to an accumulating sum R. To see how this works, let KR = 10 and refer to Figure 15 which is an enlargement

of the area around the cluster in Figure 13 ° Point 1,1 in Figure 15

indicates the distance from minutia Bl to Al in Figure 9„ The number of

steps from point 1,1 in Figure 15 to any other point exceeds 10 so that nothing is added to R. However, the number of steps from 2,2 to

4,4 is TR=8. Therefore, the score R is increased by KR-TR=10-8=2.

Similarly, there are 8 steps between points 2,2 and 5,5 and this increases

the value of R to 4. The contributions from all points are shown in
Figure 16 giving a total R=24<, The score actually used is RS=R/S where

S is the total number of points found in Figure 13. Therefore in this

example S=7 and comparing print A with print B yields a score

RS = ^ = 3.42

The comparison of print C with print D yields a score

14

RS = -^ = 2.00

In actual practice, prints that match tend to produce very dense

clusters of points in their difference graphs with correspondingly

high RS scores. The complete details for the M19 matcher are shown

in Flow Chart 1.

The M27 Matcher

The M27 matcher is an expansion of the M19 matcher. It can handle data from prints that are not as accurately positioned in the

reader as prints whose data is used by the M19 matcher. As in M19,

M27 computes different tables for Ax, Ay, and A0 where

|Ax| ^ LSI

|Ay| ^ LSI

|a9| ^ L91

The distribution of the values of Ax is then determined among eleven

equal intervals between -LSI and +LS1., A similar computation is

performed for Ay and A9 except with A9 the range is from -L01 to L01.

The parameter values

LSI = 60

L01 = 25

used in matching print A with print B produce the same difference

table shown in Figure 11. The distributions of these values of Ax and

Ay are shown in Figure 17. Prints from the same finger produce peaks

in the distribution table, but prints from different fingers produce

random distributions. The M27 matcher computes the matching score

as did M19 except that it uses only those points in an area 2 x LS2 by

2 x LS2 centered at the peak of the Ax distribution, -36, and the peak

of the Ay distribution, 12. These points must simultaneously satisfy

the condition that AS lies within the range of + L02 from the peak of

the A0 distribution which is in this example.

The parameters
LS2 = 10

L92 = 20

KR = 10

cause M27 to compute a matching score using only the points found in

the area enclosed by the broken line in Figure 15. As before, R = 24

but there are only S = 5 points to consider. Therefore, in comparing

print A with print B, the M27 matcher produces a score

RS =|=^ = 4.80

The comparison of print C with print D yields a score of RS = 0.

Here there are two peaks in the Ak distribution and in choosing the

first or leftmost, the matcher locates the reduced scoring area in a place where no points are close enough together to score. The complete

procedure for the M27 matcher is given in Flow Chart 2.

The M32 Matcher

When a fingerprint impression is placed in a reader, whatever

may be defined as the center of the print may be displaced from the

center of the reader window. The M27 matcher can cope with this

situation. However, the direction line of the finger may also be

rotated with respect to the y-axis of the reader, and the M27 matcher

may then fail to make a correct match. The M32 matcher is designed

to overcome this difficulty. It begins by performing the same comparison procedure as the M27 matcher. The computer then re-computes

the data for one of the prints being compared to represent the rotation

of this print through V degrees from its original position, and another

M27 comparison is made. Altogether, the M32 matcher compares the pair

of prints seven times with one print being set at each of the following

angles with respect to its original position.

V = -15°, -10°, -5°, 0°, 5°, 10°, 15°

When prints from the same finger are compared, there is always a sharp

peak in the graph of RS vs V and the highest of the seven RS scores

is taken as the M32 matching score. A typical graph is shown in Figure

18.

5. Experimental Results with Statistical Matchers

Numerous matching runs have been made with these statistical matchers

using the NBS UNIVAC 1108 computer. Each run is identified by number and

the RS scores from each run are entered in a score matrix as described

earlier. Each fingerprint is identified by an Arabic number. The set

of search prints is identified by a Roman number and the set of file

prints is identified by the next larger Roman number. Each pair of

sets is identified by a capital letter.

8
The score matrix resulting from computer run number 280 is shown

in Figure 19. Set XXVI consisting of 14 search prints was compared with

set XXVII consisting of 14 file prints. The prints are always ordered

such that the scores for prints that should match occur on the diagonal.

For example, print 272 and print 1122 are two different impressions from

the same finger but print 272 and print 1132 are from different fingers.

For this particular run, the minutiae data was read by machine from

standard fingerprint cards. The prints were selected as "good looking"

rolled prints. Each print was manually positioned in the reader so that

the estimated center of the inked impression was at the center of the reader

window and the estimated direction of the finger was parallel to the yaxis of the reader c The open task score OS = 60 is found by dividing

the highest off-diagonal score, 45 (times 100), by the lowest diagonal

score, 75o The closed task score CS = 51 is caused by the second row

where 40 is divided by 78. Since both OS and CS are less than 100,

the search was a success either as an open or closed search. The

score AA = 15 is found by dividing the mean off-diagonal score by

the mean diagonal score. It may be feasible to use the score AA from

matching runs on small samples of fingerprints to predict the performance

in searching large files.

The results of all of the computer runs that have been made using

the statistical matchers are summarized in Figure 20. The previous

example may be found by referring to computer run number 280 in Figure

20 Part 2. The 28 prints used in this and 7 other runs are identified

as Pair F. The smallest number of minutiae read from any of the prints

in set XXVI was 81 and the largest number of minutiae was 238. Since

the average number of minutiae on a rolled print is about 80, the

reader obviously produced many false minutiae, but these false minutiae

did not prevent successful identifications in all of the tests with

this pair of sets of data.

The same 28 prints were also read by a different reader and the

data is identified as pair E consisting of sets XXX and XXXI. See

Figure 20 Part 1. Here the prints were not positioned in the reader

but instead, the finger-boxes on the fingerprint card were positioned

manually in the reader. In some cases the fingerprint was at an angle

with the y-axis of the finger-box or the print was not centered in the

box. The OS and CS scores in runs 282 and 283 are accordingly high.

Runs 286, 287, 289, 290, and 291 were made to determine the best

possible scores attainable with this data To do this, the minutiae of

all 28 prints were plotted using the machine-read data. The plots for

each pair of prints from sets XXX and XXXI that should match were

manually superimposed and positioned by eye to give the best looking

match. The amounts by which each print from set XXX needed to be

shifted in the x and y directions and also rotated were measured. These

data xx, yy, and v were supplied to the computer and at match time it

computed new data representing the corrected position for each print from

set XXX prior to computing the match score. The resulting scores show

a considerable improvement. The AA scores for runs 289-291 may identify
the lower limit for what can be achieved in practical matching runs. All other matching runs that were made with this type of pre-positioning

are identified by the words "See text" in the Notes Column of Figure 20.

60 Discussion of Results

The amount of time required for the computer to compare a pair of

prints varys considerably depending on the parameters used and the

number of minutiae in each print. Run 282 using the M27 matcher took an average time of 0.1667 seconds to compare a pair of prints. Run

286 using the M19 matcher on the same data took an average time of

0.0845 seconds to compare a pair of prints,, This is obviously too slow

for the practical search of a large file but it is hoped that these

matching techniques can be utilized in a specially built device that can compare a pair of prints in a few microseconds.

Aside from the problems with the matcher itself, the sources of

difficulty with minutiae matching can be broken into the following

categories, and a discussion of each one follows

„

1. Poor quality prints.

2. Only a partial print available.

3. A stretched or twisted print.

4. Print displaced in reader in x and y directions.

5. Print rotated in reader.

6. Reader falsely reports minutiae.

7. Reader misses minutiae.

1. Prints accepted for classification in the Henry system need

to be only clear enough so that a fingerprint expert can identify the

pattern type and count the ridges between core and delta,, Light inking,

heavy inking, smudges, and missing portions of the print can often

be tolerated in the Henry system. The pairs of prints sets A, B, C, and

D were randomly selected from such system files. Set pair C was further

limited to those prints where the reader produced more than 50 minutiae

per print. The matching runs made with set pairs C and D, using machineread minutiae from these prints, gave unsatisfactory scores. The runs

199, 218, and 306 with set pairs A and B where the minutiae data was read manually gave better results. Runs 236 and 237 were made on the same minutiae data that produced the results with the constellation

matcher reported in Figure 4 C Future improvements in minutiae readers

may produce some improvement in matching scores. However, it will

probably be more effective to change the rules and require higher

quality prints for an automated identification system than are required

for the Henry system.

10
The determination of the quality of fingerprints is a verysubjective procedure. In the future it may be feasible for the

minutiae reader itself to determine the acceptability of fingerprints

based on the character and number of minutiae read. The prints for

set pairs E, F, and H were selected prior to machine reading on the

basis that they looked as though they would read well. The resulting

matching scores are very encouraging and produce an optimistic outlook

for automating fingerprint identification.

2. Minutiae data from partial prints and particularly latent

fingerprints have not been tested with the statistical matchers.

However, the outlook is optimistic. The advantage of manually read

minutiae data as indicated by the low AA scores with set-pairs A and B

may also apply to latent prints where the minutiae data must also be

read manually.

3. The low scores with set-pairs E and F suggest that the problem

due to flexing and twisting in rolled prints has been solved. Since

plain prints tend to be devoid of the flexing and twisting that plagues

rolled prints, the nearly equivalent scores with set-pairs F (rolled)

and set-pairs H (plain) supports this suggestion.

4. The problem that results from x-y displacement of the print

in the reader can be handled by the matchers with suitable parameter

adjustments. In particular, the parameter LS in M19 and LSI in M27

must be set large enough to accomodate any displacement that can occur. Unfortunately, increases in these parameters are accompanied by increase

in both computer time and memory capacity requirements.

5. As was seen in Figure 18, the RS scores are very sensitive

to the angular orientation of the print in the reader. The print must

be oriented within plus or minus 5 degrees for best results. Further

experiments should demonstrate that the M32 matcher can handle this

problem if the print is not carefully positioned in the reader. However,

this too requires additional computer time and would require many more

circuit elements in some future specially-built device. Accordingly,

it may be more economical to handle both the x-y positioning and angular

orientation problem at the reader. The low scores with set-pairs E, F,

and H indicate that manual positioning is satisfactory and it may be

feasible for this to be accomplished automatically by the reader.

6,7. The number of minutiae missed as well as the number of false

minutiae reported by an automatic reader tend to increase as the quality

of prints goes down. Accordingly, the remarks under 1 above also

apply here. The degree to which these phenomena degrade matcher

performance is under study and future improvements in minutiae readers

are expected to decrease the number of missed and falsely read minutiae.

11
The computer programs used in this work were written and managed

by J.F. Rafferty and D. Zimmerman of the National Bureau of Standards

and W.J. Pencak, a Guest Worker at NBS from the Federal Bureau of

Investigation. The author is also indebted for advice and assistance

to R.T. Moore of NBS, and Agents C.S. Voelker and R. Payne of the FBI.

The work was financially supported by the FBI.

7 . References

1. Wegstein, J. Ho and Rafferty, J.F., Matching Fingerprints

by Computer , National Bureau of Standards Technical Note

466, U.S. Government Printing Office, Washington, D.C.,

1968.

2. Tosi, 0. and Nash, E., "Operational/Technical Analysis of

Voiceprint Technology", Proceedings of the Third National

Symposium on Law Enforcement and Technology, 1970 , (in

publication)

.

3. Caudra, C.A., A Feasibility Study for Automated Fingerprint

Identification , System Development Corporation, Santa

Monica, California, 1966, p. 60.

4. Thiebault, R. , "Automatic Process for the Identification

of Fingerprints," Proceedings , International Symposium

on Automation of Population Register Systems , Vol. 1,

Jerusalem, Israel, 1967, 207-226.

12
XIV

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

XIII

1 128 46 8 11 23 8 32 30 13 18 22 42 22 6 53 54 22 19 32 12

2 55 80 8 12 11 12 28 29 6 12 17 25 18 27 40 34 10 8 8 10

3 9 11 75 35 16 20 19 9 19 30 23 9 14 13 16 18 36 25 14 17

4 6 1 19 63 14 16 2 4 11 21 22 23 15 13 17 7 22 18 9 26

5 11 13 13 27 37 28 14 22 20 40 25 13 16 14 24 20 46 36 29 22

Mr

F

0%

Figure 1, Score Matrix

Percent

\ False.

* -iwr

"

30 35 to f5 50 55 ^0

Threshold Score

(Discrimination Factor)

65 70

10%

Z0%

-10%

0%

Figure 2. Discrimination Graph

Corresponding to Figure 1. 13
A\

Discrimination Factor

Figure 3. Idealized Discrimination Graph

3g

2%

F

False

i%-

o%

\

\

\

\

_ »-

6 7 d 7 i°

Number of Minutiae, in Consre liarion

(Discrimination Factor)

Figure 4. Discrimination Graph Showing

Experimental Results with Constellation

Matching.

Set XIII vs Set XIV Using Minutiae

from 6 mm Radius Circle at Center

of Print.

14

y>%

/A

/H/5S

0%
Scale

H 1 \~

10 ZO 30

Units

to

3ZF-1-/3 \

33

3U^

I

Minutiae from Print XIII 11/

Minutiae from Print XIV 2 /

Figure 5. Superimposed Minutiae Tracings

from Prints of Different Fingers

15
Scale

i—i—i

i—

i

10 20 30 10

Units

7

0'

io

%'

' in

'23'

23

>ZX'

IZZ

\

Minutiae from Print IIP 2 J

Minutiae from Print IIP 8 /

Figure 6. Superimposed Minutiae Tracings

from Prints of the Same Finger

16
5ca.le

I 1 1 1 j

10 20 30 *0

Uni is

n

S3

f

\ V

7<7

\vt'

w

Minutiae from Print IIP 5

Minutiae from Print IIP 6 r

Figure 7. Superimposed Minutiae Tracings

from Prints of the Same Finger

17
Print A

i x y e

1 48 252 67

2 27 190 226

3 68 174 205

4 136 233 111

5 142 181 327

Print C

i X y

e

1 38 217 56

2 27 154 223

3 89 244 15

4 143 210 115

5 117 175 300

6 153 128 334

Figure 8

Print B

J x y e

1 75 241 65

2 62 181 225

3 109 161 222

4 174 229 128

5 182 175 346

6 157 226 111

Print D

J x y

1 55 227 54

2 41 164 227

3 120 226 305

4 173 180 276

5 77 132 320

6 65 121 325

7 172 142 285

Minutiae Data

18
1

f

fa

3%.

A3

Scale

+

10 ZO 30 tjQ Units

AH

AS

:B£> m

BS

33

Minutiae from Print A

Minutiae from Print B r

Figure 9. Superimposed Machine Read Minutiae

from Prints of the Same Finger

19
C3

,33

Scale

H 1 1 1 10 20 3D HO

Units

CY

>/>>

'CI

cs

VH2>7

2>S

J)£

CG

Minutiae from Print C f

Minutiae from Print D /

Figure 10. Superimposed Machine Read Minutiae

from Prints of Different Fingers.

20
i j Ak Ay A9 Ax Ay A9

1 1 -27 11 2

2 2 -35 9 1 3 2 6 -7 -20

3 3 -41 13 -17

4 4 -38 4 -17

4 6 -21 7 5 5 -40 6 -19

1 1 -17 -10 2 2 2 -14 -10 -4

5 3 -3 -51 -5

5 4 -56 -5 24

5 5 40 43 -20

5 6 52 54 -25

5 7 -55 33 15

Figure 11. Difference Table

for Prints A and B

Figure 12. Difference Table

for Prints C and D

Ay

j_ j

i -T-r i -Ob SO -HO -36 -lb -fa

50 —HO

30

20

-10 AX

-lo

—10

-30

--V0 —-so

^0-

10 16 3o t/i> SO

Figure 13. Difference Graph for

Prints A and B of the

Same Finger

21
ay

66-

-56

-HO

-30

-20

-to

4X

Cf> # SO -HO -30 -20 -10

% •

io 20 30 Ho So

--70

20

-

30

—SO

=U>

6)

Figure 14. Difference Graph for

Prints C and D of

Different Fingers
A/

-25

i _ ^

20

im f f~ u

3} 5

hi

r _ /n 2,2 /0

u

s,s

( r

t~r w ~i"

-yj -w -35 -30 -25"

AX

-20

Figure 15. EnlargedPortion of Difference

Graph for Prints A and B

Shown in Figure 13.

23
Contribution

From Steps to Score

point to point TR KR-TR

1,1 >10

2,2 4,4 8 2 2,2 5,5 8 2 3,3 5,5 8 2 4,4 2,2 8 2 4,4 5,5 4 6

5,5 2,2 8 2 5,5 3,3 8 2 5,5 4,4 4 6

R = 24

Figure 16. Computation of Score for Figure 15.

Distribu tion Center of

Interva 1 Ax Ay Interval

-60 to -55 -60

-54 to -43 -48

-42 to -31 4 -36 Peak Ax

-30 to -19 2 -24

-18 to - 7 1 -12

- 6 to 5 1 6 to 17 1 5 12 Peak Ay

18 to 29 24

30 to 41 36

42 to 53 48

54 to 60 60

F igure 17. Distr ibut ion of Ax and Ay for Print A vs Print B

24
50

Score RS

75

1»m \

Figure 18. Results from M32

Comparison of Prints

XVII 71 and XVIII 921

from the Same Finger

-15 -!0 -5 S to IS

Anyle V

25
Set XXVII (Computer Run # 280)

Print 1122 1132 1157 1167 1182 1187 1188 1212 1217 1242 1257 1332 1337 1492

Set

XXVI

272

282

307

317

332

337

338

362

367

392

407

482

487

642

119 30 13

34 78. 12

10 12 104.

29 20 21

13 19 30

12 29 39

24 26 15

20 19 25

14 17 24

28 32 10

40 23

7

27

10

14

3

15

24 20

21 19

20 26

75 36

15 266_

8 31

22 24

15 22

24 10

19 19

34 30

10 18

29 17

28

7

31

31 14 15 20 23 22 20

12 10 15 40 18 14 10 12

30 16 20 22 15 16 19

17 34 16 18 32 31 32 21 25

10 24 30 16 8 13

86_ 22 15 11 17 28

25 105_ 6

5 14 158. 5 12 3

26 21 13 115_ 13 32

11 10 19 6 109 18 20

17 45 28 22 22 132

14 19 12 11 10 8

17 23

20 30

17 42 17

8 22 15

1 16 18

7 20

9 15 28

145 19 15

10 31 21 19 19 16 143 19

20 18 10 28 30 29 19 21 15 22 22 14 27 116

Figure 19 Score Matrix for

M27 Matching of

Good-Quality Machine-Read Prints

OS = 60

CS = 51

AA = 15

26
aj OO IN- co co no H CA HMD no H TA. On co c^-_=r

CO

CD

«aj H H H CM M (A CA CA CA fA (A H H

_cT On NO MD O O H ON NO TAlfN O fA O CM 30 O O fA INSh CO CM CM o- o- TA On CM TA CM TA CA O TA CO O TATA-Cr fATA o

o

CO o H H C*- H H H H H CM H H

ON fA H "LA V} CO TA CD OnD CMsvO On (A NO CO J- O _Zf CO _=r "LA J" _ct 5 • O H O U\OJHO -H-TA ON CO ON O H o H H H H m j- H CM CM CM fA CM H H H H

g

rri O O O O o o o O CO CO O O O O O o o o o o 53 H H H H H H H H H H H H H H H H H H

OJ co co O co co co co o TA O TATA O TACO O TATATA O

CO

Sh

<D

g

CO a H H H H r-1 r-i r-\ CM H H H H H H H CM H H H

CM TA lA TA TA TA TA o o o o o O TA COO

I

-P CO H H H r-\ r-\ rl H H H H H H H r-i r-\ rt H LA TA CO "UN TA O TA CO TATA TATA O TA TA TA TA TA TA "O o

CTi 9 a

CM fA H CM CM fA CM H H H H H H H CM r-\ H r-i r-\ r-\ Ph H O O TA O O O O T_Tn TA TA TA O TA o o 0OTATA O O CO 3

o o H MD O CM O H fA fA fA fA fA NO no rH H CM CM CM J H H H t-1 r-{

Sho on c— ^- (S1 On o- >- C— CM On r— !>- I>- O- C— 0- IS- On On o- r— in- +3 a

CXI g

CO CM g g

i—I CM g gCM CM CA g g g ^

CM CM CM CM CM g g g s g g'g' d^g^g

Sh -P Sh D ON CO NO o- H -J- TA l>- -H-TAMD D-CO CM fA NO O- ON O H

& - rg ON H fA CA O CM CO O- TA TATA TATA co CO CO CO CO On On S fl fi H CM CM CM CM C\J CM H CM CM CM CM CM CM CM CM CM CM CM CM o s o ccj 3

£3 \ h * TD X ^s.

L ^ -P Xi O JU rCj

L si o «T t^P1 H co p g co P,a T3 P P1 ^TZ! P1 P^ T3 p>

CQ H >H 0) 05 x co S hh tM 1 T3 13 X" «H H Sh v4 1 T3 T3 X' H 3 co H •H MD O <3j CQ S ^ Sh Sh Sh CD Sh !s H Sh CO f^ ig Sh Sh Sh CD -P ct3 -H H Sh -p ^ rf H +2 •H CD -P H CD «H -P •rl CD p>

P^ o D 13 X 03 O D g O U fl & T3 M o -P Sh in TD H5 -P Sh £ & T3 txO O P> Sh Pm Js; d cxj co ?h

CO 1 CO O S O ^ Sh .J .H O CD Sh fl O CD d £ O -H

CD CO Sh O CD C fl Q TJ ^ 'ri O CO ?H S'H O O Ph ft

cd . M B C CD -H Si fi

PS g Jh M ft-P CO g Sh hh O O -H CO gsi eu«a ft S Sh hh O O .H co

CO T3 H 1A On -cf C— _cr CO O _=J- CO W •H co 9

H O <A (A H CM TA TA CM On

<d -p H H H H CM CM H HEn s* e

1=5 td -P g £

C— NO O ON NO CM H NO r>- H

|—

|

•H "O > TA On -3 CM d CM ON CD d _cf g HH Sh O Ph

co ct3 [•— NO CM CM CO CO 1A TA co IN- Ph H H

• Sh fl O £

•H CM NO <A -d- o- <A TA On On O S Ph E _=f CA H H TA TA ON fA r^ -^

HH CO -p O -Pc CO CO • -rl O O O O H H H H -cr -cr s o u fl CM CM CM CM CM CM CM CM H H O S Ph M

H

CO O H

H •P > >

> H

H

hHO

•H

co H H E w

4h M O

| 6-1 o H M H cd & -p H

MM

H

u H

CO co K

M

B

H

HH |>s f >3 "DTI:

O Sad w O bO-P T3 CO CO &J343 T3 CO CO p o s 'o co O co -H -P -P CD TH -P p> O M -H -P S CO -P Sh r-j H £ 2 G < Jh rH H C Sh O (D: i!H C

E

Sh £ CO co H -H i

•*

CO Sh CO

C D H -H g -H i—1 OH-ri H -H -p > 3 OJh

•=3 CpS Ph > :3 O Sh CD Sh CO CO O O Sh Ph£ CO CO H Ph Ph co

CO Ph Cti <tl cy CS Ph CO Ph CO

<t! pq o O H

27
4 ^— -LAOsOs[^-r— COI/s H OCOCAfAOOOOt— OsHOO.

0)

a)

«j -\t-\r-^Hr-ir-{<-\H CM WrIWWHWrlWHHCvlWrl

^- nr^vflvOvOco H o CO OOf— sOrHCOiHCOvOONCOOlA

Sh CO O OwOvOJlA'UMrN o \A OsO OssOOOIAO-r—O-sOTAsOsO

o

fj o C\J H

4^\00 r— Os r- O c H O r~- t^- CA sO V!A r-\ _rt -1 Os \A H O

CO ^-CNOOOOUAIAO-SO sC H O O CMs-cOvO o- Os OS sO vO CO IS- o 1A H H H

re o

J 3000000000 c o COCOOOOCOOOCOOOOO E E r-\ r-{ r~\ r-1 r-\ r-i H H H H H i-l H H H H H

o LA O "LOTA O OT-OO CC> o IA01A1A01A0 O O Ol^lO.O

CD

to. ^

fl HHHHHr-IHrH H H HHr-lHH.-lr-lr-IHi-IHHH

CM oooooooo 1A o o O O O 'O o o o o o o o

+3 S HHHHHHHH H HrHHHHHHiHHrHHHH

w g H lAIATAlA O O 1A O o co tATAT-OlAO lAOlAIAOlAIAO

o

EH

PL,

CD a

Hi-HHrHHrHHH CA H HHHHHHHHHHHHH

i- "Lfs TA1A O "LA O "LA O o •LO 1ATA1A O 1A O O O O 1A1A O O

a 3 n nnnnnw c\i CMH

H CAfAfAfAr^r^\<AfAr^oJOJOJC\J

<-

o o o- r— c— c— c— r— c— r— c^

D- Os c— c— r— c-— r— i>— c— t:— c— c-— c— c~— c

p f —

CV CM OJ OJ OJ OJ OJ CVJ OJ 1—

CXlCVJfXJCSJCSJCVJCVJCXJCSJCSJCSJCNJCSJ assays ^sg^gsg 1 a £ :s! s g sdsss s a

-p u

3 CNO H CM CACO Os O O : J-TASO O-CO OSO H CM fA_^r-Lf>vO

& rg TAsO sO so sO l>- [>-co OJ CO sOsOsOsOsOsO o- t-- D— [>- C^- [^ IS— s a e OJOJOJOJOJOJOJOJ (M Ih CMCMCMCMOJOJOJOJOJCs'OJOJCM

o n D

o ct; s

T3 \ 'O

CO Xi L £ T3 0) p p> j>8 'a -p

CD .H H 0. S [s Jh co tI • -n 'H OrlrllBS

-p C g CO ^ J-4 CTJ a ^ h ?h co o •H «J -H P» •H P> O rP •H nj .H P>

rvj s JZl 73 3 -P ^ fl ^ TJ S !h -P !h ^T3 3-P !j fl PH O ctJ C fl O -H o aj .h a c o ni pj p

1 O -rl O c3 nj sl, CTJ f Du a t^ nj ?-i

c3 gfnS OtSft a u a ... , CO ^ U £ o & p.,

CO" TJ CO 1A _n CO r— so

•H ctJ g

CA I

s- 1A o- i>- H H -p OJ H

M ti

Cti e

En £

-P ?H l>- OS 1A OJ CO rA g

£ • • • • •H T3 > _zr co CO o- CO CO a

<+H Jh cd CT? rA OvJ rA rA 1A sO O Ph H H

. *H cd s o & ^ H o CA OJ SO H

s Oh CO CO CM OJ CA 1A

CH CO p> o p

CO

• •H _=f _=J C— C-- O O

EC o U £ H H H H H H S S3 p H

o

CO M

CMo H -P

03 w H M o M

EH

S2S

a] & p

1

(k! M M H r*S Ph

to. to txl T3 TD =

<H £>s O bO O CO M +3 CO -P O £ CO O pi ctj -rh a p> O bjO-H ti +> S CO p a w U r-h -h n = ^ -H C M Sn £ CO e -h cJ ct3 «H H odd Pn •H •H -p 3 t, co CO Ph nJ > :3 H Sh CO O H Jh CO nJ H Cm Ph £ & to

<u cS^Ph P-. Pn o W

OJ

+3

5-. aJ PmO

OJ

28
Flow Chart / /n /<? Mafcher

s

Read

IA\X. IMXg

/ix)ti Axxz

2=/

5^0

V z.i (jmjjnx)

J = i n

i=i + i J

A*~Ai:iB -Aj. B

~~ njzc

IS

J =j + I ~%

< If i_±

( I ; Tm3 )^-=^ j sIMX^qj^JMi LS )

i~ i\ ©^C 5

:

5ai )^

Contents o-f Arrays

nxix Axix Ax3x Axvx

p x y e

rarame'fers

LS L9 SM KR

^y =

^/3s -Aj3c

V to &B -Aif-B -~Ajfc

y a CmTTT)^

>

Y iz

t ^C M ; mo - LB )

77? ^IWi-DxJ+lw-jyjl

23 '' -^( T&: /Cr)

Z£

~R. = R+KH-TR.

c

I /2./ £0:0

v=.v

/2.2 St

40 -A6-3&0

12.3

<

40 =3«;<7 +45

*-**!* >'

/3

3=5+/

/3x£I

i»5 - ^y

29
Flow Chart 2 Part I AIE7 Matcher

2.

'Read Uent 1 lAentZ

mx, ZMXa A**> /ixxz

'< 2.1

2.? L5=L5/

id --L6I

2.2

2.2. w JL 2.:

5W-0

VX*0

A

3=/

C=2

5=2

2.7 3>-T>+\

^r> 3^o

JL s

i*t

5b

5*1/ = I L5- 152

LB ~ LdZ

II

JM.

J)*l

)

2.5

V3

3 = /

JJL

i_^ 4C5"

J> = 25 */

^<iT7)

I// = L5 (& -J)/*!)/?

Fa ram e hre rs

LSI LBI LS2 L62 KR

a

j~i *r <d)

/5

2 - l t I

JL

J ~J + I r

5<9 = S

31 V

£M~0

25 = /

35

3%

33

D-D+\

Q £»:£Af)-»'

2>/f =J)

< V J"

M = Ld(&-J?A1)/S

^ 37

J>=/

-^' 3? 39 • n> J)Af=D

v/ (^£j^j£^/n

^

£fo

J) = 2) + / T

<:>' J

<; <T77T)fO

¥2

|/X= Z-5 U-J)M)/s

30
Flow Chart 2 Part 2

AI27 Matcher Cent

A3.

3

®—H Ax^/>itB -/i/»c + Vx

r<r % 7

-^( l/ixl: jJj

©

M=Ai3B -Aj3c +VY

3)/ = 40 +Z.0

J>2 = fa/'S)/L8

J) ~ 3>Z + / £j> = £j> + / Dl = AX H-LS

£Xj,=£XJ + /

13.V Dl * AY + LS

DX - (di*s)/l$

D -J>x + i EYx^EYx + 1

I 7

*-( \ay\-. 15 )

13

jo

Ae^Aiu, -Ai9c + V&

5=5 + 1 1

t (V

Z3.-2-

Jt >

12.1. A6-AB -3CP

-c

/2.3

4(9 -Ad +360

> < ~*

>

r i3_

i -2

zo XX

V^ y-/

2?

1=1+/

1

*

J = j+'

<| 27 < I 2.5" ( *

; * )^( Li \zi )<—

K

•( 7%: K\ )

_ZX" if

X " R+ KR -TR

1127./ *? 7?=2«R.

i?S =

= £

27.3

£.5=<?

ft U.S. GOVERNMENT PRINTING OFFICE : 1970 431-989/18


U.S. DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20230

OFFICIAL BUSINESS POSTAGE AND FEES PAID

U.S. DEPARTMENT OF COMMERCE