U.S. Department

of Commerce

National Bureau

of Standards

Computer Science

and Technology

, NBS

s PUBLICATIONS

NBS Special Publication 500-89

An Automated Fingerprint

Identification System
NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards' was established by an act ot Congress on March 3, 1901. The Bureau's overall goal is to strengthen and advance the Nation's science and technology

and facilitate their effective application for public benefit. To this end, the Bureau conducts

research and provides: (1) a basis for the Nation's physical measurement system, (2) scientific and technological services for industry and government, (3) a technical basis for equity in trade, and (4) technical services to promote public safety. The Bureau's technical work is per- formed by the National Measurement Laboratory, the National Engineering Laboratory, and

the Institute for Computer Sciences and Technology.

THE NATIONAL MEASUREMENT LABORATORY provides the national system of

physical and chemical and materials measurement; coordinates the system with measurement

systems of other nations and furnishes essential services leading to accurate and uniform

physical and chemical measurement throughout the Nation's scientific community, industry,

and commerce; conducts materials research leading to improved methods of measurement,

standards, and data on the properties of materials needed by industry, commerce, educational

institutions, and Government; provides advisory and research services to other Government

agencies; develops, produces, and distributes Standard Reference Materials; and provides

calibration services. The Laboratory consists of the following centers:

Absolute Physical Quantities' — Radiation Research — Thermodynamics and

Molecular Science — Analytical Chemistry — Materials Science. THE NATIONAL ENGINEERING LABORATORY provides technology and technical ser- vices to the public and private sectors to address national needs and to solve national problems; conducts research in engineering and applied science in support of these efforts; builds and maintains competence in the necessary disciplines required to carry out this research and technical service; develops engineering data and measurement capabilities;

provides engineering measurement traceability services; develops test methods and proposes

engineering standards and code changes; develops and proposes new engineering practices;

and develops and improves mechanisms to transfer results of its research to the ultimate user. The Laboratory consists of the following centers:

Applied Mathematics — Electronics and Electrical Engineering- — Mechanical

Engineering and Process Technology' — Building Technology — Fire Research —

Consumer Product Technology — Field Methods.

THE INSTITUTE FOR COMPUTER SCIENCES AND TECHNOLOGY conducts

research and provides scientific and technical services t^o aid Federal agencies in the selection, acquisition, application, and use of computer technology to improve effectiveness and

economy in Government operations in accordance with Public Law 89-306 (40 U.S.C. 759), relevant Executive Orders, and other directives; carries out this mission by managing the Federal Information Processing Standards Program, developing Federal ADP standards

guidelines, and managing Federal participation in ADP voluntary standardization activities; provides scientific and technological advisory services and assistance to Federal agencies; and

provides the technical foundation for computer-related policies of the Federal Government.

The Institute consists of the following centers:

Programming Science and Technology — Computer Systems Engineering.

'Headquarters and Laboratories at Gaithersburg, MD, unless otherwise noted; mailing address Washington, DC 20234. ^Some divisions within the center are located at Boulder, CO 80303.
National lureau Df Standards

library. E-^A Mmin. IW|.

FEB 2 4 1982

/aComputer Science

and Technology

NBS Special Publication 500-89

An Automated Fingerprint

(^^-^r Identification System

Joseph H. Wegstein

Institute for Computer Sciences and Technology

National Bureau of Standards

Washington, DC 20234

Sponsored by the Federal Bureau of Investigation U S Department of Justice Wasfiington, DC 20535

*«''?CAO Of

U.S. DEPARTMENT OF COMMERCE

Malcolm Baldrige, Secretary

National Bureau of Standards

Ernest Ambler, Director

Issued February 1 982
Reports on Computer Science and Technology

The National Bureau of Standards has a special responsibility within the Federal

Government for connputer science and technology activities. The progranns of the

NBS Institute for Computer Sciences and Technology are designed to provide ADP

standards, guidelines, and technical advisory services to improve the effectiveness

of computer utilization in the Federal sector, and to perform appropriate research

and development efforts as foundation for such activities and programs. This

publication series will report these NBS efforts to the Federal computer community as

well as to interested specialists in the academic and private sectors. Those wishing

to receive notices of publications in this series should complete and return the form

at the end of this publication.

National Bureau of Standards Special Publication 500-89

Nat Bur. Stand (US), Spec. Publ. 500-89, 47 pages (Feb. 1982)

CODEN: XNBSAV

Library of Congress Catalog Card Number: 81-600193

The mention of trade names and/or company products is in no sense an endorsement or recommendation by the National Bureau of Standards.

u s. GOVERNMENT PRINTING OFFICE WASHINGTON: 1982
An Automated Fingerprint Identification System

J. H. Wegstein

ABSTRACT

Procedures are described for automatically identifying fingerprints.

Machine-read ridge-direction and minutiae data are utilized in registering and enhancing search or file minutiae data. The quality of the

data is measured. A procedure is then described for utilizing this

minutiae data in determining whether two fingerprint impressions were

made by the same finger.

Key Words: computerized-fingerprint-identification; identification;

pattern-recognition

.

1
1. INTRODUCTION

The unique identifying data in inked fingerprint impressions on standard

fingerprint cards can now be read automatically when the prints are of

good quality.-'-'^ The data from latent (scene of crime) fingerprints

and poor quality inked fingerprints can be read with semiautomatic

readers."^ The first part of this paper describes the automatic procedure for preparing this data so that it can be stored in a file or searched against data that has been previously placed in the file. The

second part of the paper describes the automatic procedure whereby a computer can compare search and file data and determine whether or not

the represented fingerprints came from the same person.

2. FINGERPRINT DATA

The automatic fingerprint readers at the Federal Bureau of Investigation can deliver both ridge-direction and minute-detail data from each of

the ten fingerprint boxes on a fingerprint card.'^'^ Ridge-direction

data consists of angles indicating the ridge directions at equally

spaced grid points superimposed over the entire print. The reader also

determines the X and Y coordinates and the direction, 9, for ridge

endings and bifurcations (minutiae) . A portion of a fingerprint along

with plots of ridge directions and minutiae are shown in Figure 1.*

Figure 2 shows how the X and Y coordinates, measured in units of one- tenth millimeter, and the direction 0, measured in degrees, are defined

for a minutia. If the areas marked A are ridges, then the minutia is

a ridge ending; but if the areas marked B are ridges, the pattern is

a bifurcation. Since a ridge ending in one print may appear as a bifurcation in another print from the same finger, no distinction is

made between ridge endings and bifurcations in recording data.

Part I: Preparation of Fingerprint Data

1. Registration

Ideally, the core of a fingerprint should be in the center of its

appropriate box and the finger should be parallel to the vertical lines

of the card when the impression is made. In practice, the print is

rarely centered and may be at an angle of more than 20 degrees with the

vertical. In order to relieve the matcher of the burden of aligning

fingerprint data at match time, registration or centering and aligning

is performed on the data before it is placed in the file or searched

against a file.

The R92 registration procedure is defined in Flow Charts 1 through 6

and various details will be referred to by the box numbers within

these charts. R92 uses the 29 X 29 array of ridge direction data,

ip-L^j, delivered by the fingerprint reader to find the core or center

point (XX, YY) . Figure 3 is a plot of the ridge direction array of an ulnar loop. The angles -90 ._<t|^^90 . are in degrees and missing

angles have the false value 100 for easy recognition by the computer.

-'-Raised figures refer to literature references appearing on page 16.

^Figures and flow charts appear on pages 17 through 44.

2
The parameters used by R92 are:

RK 1 RK 2 RK 3 RK 4 RK 5 RK 6 RK 7 RK 8 RK 9 RK 10 RK 11 RK 12

111. 45. 0. 8 73. 76. 176. 3 27 1 25 4

RK 13 RK 14 RK 15 RK 16 RK 17 RK 18 RK 19 RK 20 RK 21 RK 22 RK 23 RK 24

50. 100. 75. 3 9 3 465. 379. 379. 210. 90. 7.

RK 25 RK 26 RK 27 RK 28 RK 29 RK 30 RK 31 RK 32 RK 33 RK 34 RK 35

3 4 3 10 2 76. 45. 30. 180. 0. 2

1.1 Selection of Possible Center Points

Flow Chart 1 seeks all arch-like patterns within the print which might

house the core or center point. It begins at the top row, i=RK10=l, and

sweeps from left to right as j increases, seeking arch-like patterns

that do not include any blank spaces. Boxes 7-15 eliminate blank

areas where ridge-directions are missing. For each area being examined:

i,j-2 i,j-l i,j i,j+l iJ+2 i,j+3

/ / / \ \ \

AM AA AB AC AD AN

various tests are performed. Box 18 requires that | AB | + 1 AC[ <_ RKl (=111°) . Box 20 requires that SAD>^RK2 (=45°) . Boxes 21-42 accumulate a confidence score LCR which indicates if the arch is well formed. For

example, if box 22 finds that angle AA is greater than 0, box 23

increases the LCR score by 1. If box 42 finds that the total LCR score

is less than RK4=8, control returns to boxes 8 and 9 which moves one step to the right for the next set of ridge directions.

If box 42 finds LCR >_ 8, indicating a promising arch, control moves

through boxes 43 and 44 to point @ to Flow Chart 2. Boxes 45 to 58

perform additional tests on the ridge directions above and below

point (i,j). If a crossover { V^) is found above in row i-1 or beJov

in row i+1 near column j, then SW>0, and control goes to box 59

where the reference point (i,j) and other information are entered in

the K tables. For example:

*TI^ = i, TJ^ = j , and

TSAD =SAD=|v. . J + k. -l + k. .^il + k. .^ol K i,J-l 1,3 1,3+1 1,3+2'.

In Figure 4, showing a portion of the ridge direction data, SAD=246.

Control then passes to box 59.01 and on to box 78. During this phase

the sum of the absolute values of four consecutive ridge directions

from row i-f-l is obtained as sho\sm in Figure 4.

3
STX=|*i+,,j.3l + ln+i,j.2l + l*i«,j-il + ll'tW,j

Then j is increased by 1 and another STX is computed. This is repeated

until there are five different values for STX. The largest of these

values is called SXH and the lowest is called SXL. In Figure 4, the

largest STX = 335. Hence SXH = 335. The lowest STX gives SXL = 307.

SDY = SXH - SAD = 89. These will be entered in the K tables as TSXH^, TSXL^, and TSDY^.

With the above data, box 74 finds that SXL = 307 is greater than

RK6 = 76 and control goes to box 75. Here SDY = 89 is found to be

larger than RK5 =" 73 and box 76 finds SXH = 335 to be larger than

RK7 = 176. Thereupon box 77 sets TRY^ = 1 indicating that this area may embrace the core of the fingerprint and that the pattern may be a loop or a whorl.

Control then returns via point (^to Flow Chart 1 where i and j are advanced so that the entire print is explored for all possible core points which are then added to the K table. After the lowest row of

ridge directions, as designated by ILOW and lYLB, has been tested, KM

is set to K the total number of entries in the K table and Control

goes via point (a) to Flow Chart 3. At this time the K table correspond"

ing to the ridge directions shown in Figures 3 and 4 is shown in Figure

5.

1.2 Analysis of Area Around Center Point

In Flow Chart 3, boxes 84, 85, and 86 seek the last entry in the K

table where TRY =1. In the above example this occurs when K=8 at the

reference point (lYP , JXP) = (12 , 16) . Box 89 then defines two areas around this reference point shown as areas A and B in Figures 3 and 6.

Further tests are performed on the ridge-directions in these areas working upward from the bottom of box B. Boxes 94-131 and 144-145 lead

to RAS in box 102 which is ten times the mean of the absolute values of

the second differences of the angles in area B of Figure 6.

Boxes 132-143 deal with the ridge directions in area A. IC in box 133

is the total number of cases where the absolute values of the angles

are greater than RK30(=76?) . ITG in box 141 is the total number of

times that angles are too large for an arch form in area A. IIF in

box 143 counts the number of times that the absolute values of the

angles in any row of area A are less than RK24(7°). In other words,

this indicates excessive flatness in any row. Boxes 144-154 are again

used to accumulate second differences, this time in area A. Boxes

105.1 and 105.2 determine IF, the largest of the IIF values from the

three rows in area A. When box 105.21 finds that the analysis of the

top row in area A has been completed, control goes via point^to

Flow Chart 4.

4
In box 110, RAT is ten times the mean of absolute second differences

for area A. This is similar to RAS for area B in Figure 6. The various

quantities computed in Flow Chart 3 are renamed and stored in Table K

for possible later use. Boxes 114-124 perform various tests on these

quantities which may lead to setting SW3=1 in box 125 indicating that

this entry in the K table is unsatisfactory as a site for the core. For

example, RASK>RK21, where RK21=379, indicates a roughness in the ridge

directions like the area around (4,24) in Figure 3 which would be

unacceptable for a core area. TIF>_RK26 (4) would indicate that there

are too many flat ridge directions inarea A. If any of these tests

set SW3=1, control upon arriving at box 127 will pass via point @ to

box 86 in Flow Chart 3. Then control will back up in the K table and

try the next entry where TRY =1.

1.3 Center for a Loop, Whorl, or Tent (CLU=1)

In the example being followed with Figure 6, control arrives at box 127

with SW3=0 and passes through point© to box 197 in Flow Chart 5. Since

K=KM, box 205 sets CLU=1 indicating the pattern is probably a loop,

whorl, or tent and control passes via to Flow Chart 6 where the

precise center point (XX, YY) is computed as described in Section 1.6,

In box 197, K+2j<KM would indicate that there is some arch pattern

below the chosen core area and boxes 198-203 would set out to verify

that this is merely an arch pattern under a delta or other harmless

anomaly and return to box 205. Failing this, control would pass via

point to box 155 in Flow Chart 4 for examination as an arch pattern.

1.4 Center for an Arch (CLU=2)

Before concluding with the computation of (XX, YY) let us return to

box 85 in Flow Chart 3. If there were no TRY =1 in the K table,

control would loop through boxes 86 and 84 till K=0 and then pass via

point to box 155 in Flow Chart 4 to locate a center point for an arch pattern. Figure 7 shows the K table for the portion of arch

pattern shown in Figure 8. If box 155 finds at least two entries in

the K table, boxes 157-163 will start with the reference point

(TI2, TJ2)=(12,18) and determine that either the previous or following

entry in the K table will contain another reference point that is less

than two spaces away in the ridge direction matrix. This is true for

all of the (TI, TJ) in Figure 8. Consequently, for all entries except

K=7 and 8 which are rejected by box 162 for having TSXL less than 50 , control moves to boxes 167-170. Here ^ 1

| for each row in Figure 8 is

computed and stored as TSA in table K shown in Figure 7. For each

of these entries that passH^oxes 172.1 and 172.2 to point control

returns to Flow Chart 3 where the neighboring ridge directions are examined as described in Section 1.2. Note that now SW1=1 so that

when control successfully reaches box 126 in Flow Chart 4, control

passes through point (d) and on to boxes 174 and 175. Here TRF is set

to the largest TSA^(=392) in the K table and KT=5 notes the entry in

the K table of the promising center point for the arch pattern in

Figure 8. When the last entry in the K table has b^en examined.
box 176 sends control via point

^

to Flow Chart 5 for a further

examination of the ridge directions under the proposed center point

(15, 18) in Figure 8. Boxes 180-194 define an area bounded by the

points (16, 16), (16, 21), (24, 16), (24,21) and count the number of

times, JCwhen \^ . .|^75o. If JC£3 , box 195 sets CLU=2 and names the

center reference point (lYP, JXP) = (TI , TJ^^^) . In the example of

Figure 8, (lYP, JXP) = (15, 18). Control then goes via point © to Flow

Chart 6 where the precise center point (XX, YY) is computed as described

in Section 1.6»

1.5 No Definite Center Found (CLU=3)

If boxes 206 and 207 in Flow Chart 5 find CLU>2 and CLX>0 indicating

that there was at least one TRY^=1 in the K table even though none were

accepted, then box 209 sets KT=KTX and (JXP, lYP) becomes a "guess"

at the center point. (In box 116 in Flow Chart 4 KTX had noted the

last entry in the K table where TRYj^=l.) If CLX=0 indicating that there was no TRY^=1 in the K table, then boxes 208.1-208.5 make one last

desperate effort to name a center point by selecting the last entry in

the K table where TSDY>36°. If this fails, (XX, YY) is left at (200,

200) and control passes from point 0 to point (g), the end of the program.

A few numbers that might be useful for diagnostic purposes are identified.

1.6 Computation of the Center Point (XX, YY)

When control arrives at point (h) in Flow Chart 6, CLU, KT, lYP, JXP

been assigned values. The next task is to obtain a more precise

location for the center or core point in rectangular coordinates

(XX, YY) . This center point marked + for three ridge patterns is

shown in Figure 9. The rectangular coordinate system that is used

dealing with minutiae is related to the grid point system of ridge

directions as follows:

X(j) = .4849(49+24(j-l))

Y(j) = .4849(725-24(1-1))

Boxes 211 and 212 first find the abscissa,

XXI = X+X(j),

of a point between ii . and x. . ,i as shown in Figure 10. For noni»J i»J+l

arches, noted by box 213, box 219 uses the ratio'

PHI = DSPl

DS 90

to obtain a measure of the verticalness , DHl , of the ridge directions

at (i, j) and (i, j+1) . Similarly, boxes 223-226 computer XX2 and DH2

for the next lower row of ridge directions. (The crossover reference

point JL=TJL was obtained in box 59.01.) Using DH, the mean of DHl

and DH2 , box 227 uses the ratio shown in Figure 11 to obtain XX.

Box 228 follows, obtaining YY=Y (i) -DS+DH

.

6
For the loop pattern shown in Figures 3, 4, and 6 where (i, j)= (12,16):

DSP1=43+67=110

XXI = 11-6376x43 ^ 193.3=202.8

Since DSPl > 90, DH1=DS=11 . 6376 . Since there are no negative ridge

directions in row 13, JL=0, XX2=XX1, DH2=11.6376, DH=11.6376, and

XX=XX2=XX1=202 . 8 . YY=223 . 5-11 . 6376+11 . 6376=223 . 5

.

With an arch pattern , where CLU=2, control normally goes from box 212 to

boxes 215, 215.1, and 216.1. Using the data in Figure 7 which is

associated with the arch in Figure 8:

(i,j)=(15,18) DSP1=16+15=31.

XX=XX1 = ^^-^^^^^^^ + 221.6=227.6

YY is obtained by a "center of gravity" approach as illustrated in

Figure 12:

TNUM=177x346+189x392+200x366=208530.

TDNM=346+392+366=1104

The registration concludes in Flow Chart 5 by assembling some additional

data for possible future use.

2. (MANGA) Procedure for Improving Minutiae Angles

Due to flaws in the fingerprint image, minutiae direction angles are sometimes in error with respect to neighboring ridge direction

angles. For example, see Figure 13. Flow Charts 7 and 8 describe a procedure for correcting these angles by utilizing the angles of the

neighboring ridge directions. Box 2 in Flow Chart 7 defines a 2xDSP by 2xDSP square centered about each minutiae. Boxes 3-25

construct a table of the up to K=4 ridge directions (XK^, YK^,AK^) =

^'^jl2' ^j22' '^j32'^ that surround each minutiae as shown in Figure 14.

(Note that (A.-,-., A..,, A._,) = (X., Y , 0.) represents the coordinates

111 izl iJl 111

and angle of minutia i and (^^-^2^ ^^^22' '''^j32'^ represents the

coordinates and angle of ridge direction j.) The A _ angles are between -90° and +90°. The search for ridge directions surrounding a minutia seesaws back and forth across the ridge direction table from

j=l to j=IMX2.

7
Control now passes via point (b) to Flow Chart 8. In box 28 the distance

between the minutiae and each ridge direction, as shown by broken lines

in Figure 14, is subtracted from DAG, the diagonal distance of the DS

square, and set equal to ATj^. SN is the sum of these weighting factors

multiplied by the absolute value of their corresponding angles and AMN

is the mean of these products. If AMN is less than 45° as determined

by box 33, the neighboring ridge directions are predominately horizontal

as in Figure 15, and boxes 34-39 compute the weighted mean angle TP in

a straightforward manner. If AMN is greater than 45° indicating

predominately vertical ridge directions as in Figure 16, negative angles

indicated by box 40 must be converted to positive values before arriving

at the weighted mean in box 44. If the absolute value of DA, the

difference between TP and the minutia angle, is greater than DAK(=60°)

,

this minutia is deleted from the list of minutiae and control returns

via (a) to examine the next minutia. If |da| DAK the angle value TP

replaces the angle in the minutia table and control returns via^a)

to consider the next minutia.

3. (NU14) Computation of Rotation Angle

After the core or center point (XX, YY) of a fingerprint has been

determined, the minutiae data will be rotated about this point through

some angle V to a standard orientation for filing or searching. The

computation of A/ is described in Flow Chart 9 and uses the following

parameters :

NUMX KJC KJL KUP KDN KCT KNUl

20. 2 9 3 6 0 20.

Box 2 determines two areas about the reference point (lYP, JXP) shown

as area C and D in Figure 3 and as areas A and B in Figure 17 using

the parameters KJL, KUP, and KDN. Within this area boxes 9-13

systematically locate pairs of ridge directions iIi . . and iIi

. .. on the same row and equidistant from the center line as seen in Figure 17.

Box 14 computes RN which is half the difference of each of these pairs

of angles, and box 15 saves only those RN where |rn| <30°. Wnen all of

these pairs of angles in areas A and B of Figure 17 have been used, 'V the mean value of these RN, is computed in box 22 followed by the sine

and cosine in box 24.

4. (TRARO) Translation and Rotation of Minutiae Data

Flow Chart 10 describes the procedure for translating the minutiae data

centered at (XX, YY) to the standard center location (200, 200) and

at the same time rotating the minutiae pattern through the angle V.

5. (CLIP 3) Elimination of Excess Minutiae

Figure 19 shows the 162 raw minutiae as they came from the fingerprint

reader. These correspond to the ridge directions shown in Figure 3.

Procedure CLIP 3 retains only those minutiae within the area described

8
in box 1 of Flow Chart 11. The results of this clipping are shown in

Figures 19 and 20} normally PXA=80, PYU=70, PYD=110.

6. (YSORT) Ordering Minutiae Data

The high speed fingerprint matchers M40 and M82 require that both

search and file minutiae be arranged in descending order of the Y values.

This is accomplished before searching or filing the data by the procedure described in Flow Chart 12.

7. Function DA(TH1, TH2)

The FORTRAN expression DA(TH1, TH2) calls for the procedure described

in Flow Chart 13 which computes the difference, DA, between the ridge

direction angles THl and TH2 making sure that |da| <_ 90°. It is used

by the Q6 procedure.

8. (Q6) Measure of Fingerprint Data Quality

The procedure described in Flow Charts 14, 15, and 16 examines the

ridge direction data for poor quality in the fingerprint. In Flow

Chart 15 boxes 1-19 define a 154 point area in the ridge direction array

centered about the reference point (lYP, JXP) . Then for each point

(i, j) in this area, subroutine QUAL shown in Flow Chart 14 is called

upon. In box 7 the Qn differences between the angle at (i, j) and the

angle above, to the left and right and below are computed by function

DA described in Flow Chart 13. (Ridge direction 'B^^ is the same as

i|j . . used in earlier flow charts.) These Qn are first differences

comparable to first partial derivatives —^ and-rrr. Box 8 obtains QA, OA 0 1 the mean of the absolute values of these Qn. In box 9 the second

3 B 3 ^B

differences QX and QY, comparable to -^^7 ^'^^ 'y^I' obtained. The

mean of the absolutes of these, Q2A, along with QA are the outputs of

this subroutine. MQ=1 indicates that both values could be computed.

The results for two ridge configurations about (i, j) are shown in

Figure 18. A large value for Q2A indicates a disturbed ridge direction

area. Boxes 15 and 21 of Flow Chart 15 obtain the mean values QAM and

Q2AM for the entire area of ridge directions defined earlier.

The second part of Q6 in Flow Chart 16 uses the following parameters:

KQl QX2 QK3 QK4 QK5 KQ6 KQ7 KQ8 KQ9 KQIO KQll

120 17. 19. 20.5 72. 5 95 80 40 20 15

Working with the ridge directions of each fingerprint, it produces a number of demerits, ND, ranging from 0 to 3 . If either of a pair of

mating fingerprints that are being matched by computer has an ND > 0

,

the resulting matching score will tend to be low. The larger ND

becomes, the poorer will be the matching score. An ND=3 predicts

failure to identify the fingerprint and suggests that the minutia

9
should be reread with a semlautomated reader.

Boxes 24-26.4 accumulate a number of demerits depending on how many of

the ridge directions in the 154 areas being examined by QUAL are missing.

Boxes 27-32 begin accumulating demerits when Q2AM is greater than 16.

If both XX and YY are 200., ND is immediately set to 3 by box 35. Boxes

41-49 count the number of cases, IV, where the absolute values of the

ridge directions exceed 72° in the narrow area above the center point

defined by box 38. If box 50 finds IV to be five or more, box 51 sets

ND=3. Finally, boxes 52-57 give demerits if the total number of

minutiae, IMG, is low. In conclusion, boxes 58 and 59 limit the total

number of demerits for a fingerprint to three.

9. (PRO) Profusion of Minutia

Subroutine PRO described in Flow Chart 17 constructs a square box

centered at each minutia. The box measures 40x40 units when parameter

DK=20. The procedure then counts all of the MT minutia in this box.

After all of the minutiae in the fingerprint have been thus examined,

MD is set equal to the largest MT that was found. Thus, MD is a measure of the maximum minutiae density found in the print.

' . 10. (TIUP) Minutiae Tidy Up

When two minutiae are too close together, one or both minutiae are eliminated. First, boxes 1-3 in Flow Chart 18 clear an array L. Its

length is IMO which is equal to the number of minutiae being examined.

Boxes 5-22 describe the procedure for detecting two minutiae, i and K,

which are less than TK(=10)units apart in X and Y. If this occurs and

both minutiae are pointing within TA(~30*-') of each other, a note is

made in array L by setting Lj^=l in box 17. If the pair of minutiae are pointing in opposite directions, both L. and L are set equal to one in

1 K

box 20. Boxes 26-31 then eliminate all minutiae identified by a one in

array L.

11. (TIUP 1) Another Version of TIUP

TIUP 1 is the same as TIUP except that box 20 contains only L , . In

K=i

the case of opposing minutiae, only the second one is eliminated and

this appears to produce slightly better matching scores for mating

prints

.

A comparison of Figures 19 and 20 shows the results of all of the

preparation procedures concluding with TIUP 1. For example, minutiae

104 and 105 were too close together in Figure 19. Consequently,

minutia 105 was deleted and only 104 remains as minutia 51 in Figure 20.

The X, Y, e data corresponding to Figure 20 can now be placed in the

fingerprint file.

This concludes the preparation of minutiae for searching or filing

10
unless yet-to-be defined procedures are developed for classification

and compaction of the minutiae data.

Part II. The M82 Fingerprint Matcher

1. The MAO Matcher

The M82 fingerprint matcher is an extension of the MAO matcher reported

in an earlier publication^. This extension utilizes a tensor that

produces improved matcher scores particularly in cases where the mating

prints are distorted. Parts 1 and 2 of the M82 matcher shown in Flow

Charts 20 and 21 are essentially the same as the MAO matcher.

Figure 21 shows four search minutiae superimposed on five file minutiae

The file set is displaced, rotated, and stretched with respect to the

search set. The X, Y, 0 data for these minutiae are shown in Figure 22

As M82 sets out to compare these prints, boxes 1-3 in Flow Chart 20

examine the total number of search and file minutiae and assign the

subscript B to the set with the least minutiae (search set) and C to

the other set (file set). Boxes 5-18.1 proceed to put a box around

each search minutia i as shown in Figure 23. For each file minutia j

in this box with V9<LQ an entry S is made in the S table shown in

Figure 2A. The indices i, j for each pair of prints is also entered

as ISg AND JSg in this S Table. (These values were not saved in the

MAO matcher.) The parameters used in this illustration are as follows:

LG LS KG AKR KHG KHR KQL KMX XYK ANK BKR

15 25 0 26 16 26 -9 7 5 15. 5

KRR PS BB CC DD EE KMM

8500 7 20 .2 30 .36 15

2. Computation of R and TS Scores

After the last search minutiae i has been examined, control passes via

(B)to Flow Chart 21 where a score R is computed. Boxes 23-23.5 begin

by setting all values of table TS to zero. Each entry i in Figure 2A

is then compared with each other entry j and the differences TR and T0

defined in box 25 are computed. Those values of TR which pass the test

of boxes 26-28 are used to compute a score KR-TR in box 28.1 This is

added to the TS , and TS . at the locations corresponding to the minutiae

pairs IS and JS'^that contributed to this score. For example, using

entries i=l and j=2 as shown in box 25:

TR= 1 1+7 I + [6-8 I =8+2 = 10

KR-TR = 26-10 = 16

(Note that in box A in Flow Chart 20, KR=AKR=26.)

Then in box 26: TS^=0+16=16

TS2=0+16=16

11
Stated in another way, search minutia 1 in figure 21 sitting on file

minutia 1 coupled with search minutia 2 sitting on file minutia 2 produces a score of 16. This is credited to the TS score for each pair

in Figure 24.

The same accumulated score called R in box 29 is the R score used to

produce the final RS score in the M40 matcher.

3. Ordering and Clipping the S Table

When all combinations of the entries in the S table have been processed

control moves via point (g) to Flow Chart 22. Since KS¥ was set equal to zero in box 4 of Flow Chart 20, control passes to box 34.02 where the

switch KSW is set to 1. With mating cards the S table will usually

contain more than 100 entries. It is the task of boxes 40-57.1 to

arrange the TS values of the S table in descending order and retain the

associated IS and JS values. Thus IS, JS, TS become GI, GJ, GT in the

J table shown in Figure 25 with the GT now in descending order. This

is accomplished by comparing each TS value with each GT. When TS is

greater than GT , this GT and the remaining entries in the GT table are pushed down one notch. The TS value is then inserted in the vacated

GT space and the process is repeated till all TS values are treated.

In practice only KMM=15 entries are retained in the J table. These are normally mating minutiae and their TS contributions to the R score.

4. Computation of the Tensor

Control next moves via @ to Flow Chart 23 where table J is utilized in

computing the four element tensor: GOV, SIV, SIW, COW.

The following parameters are used in practical applications:

L9 IS KG AKR KH9 KHR KQL KMX XYK ANK BKR

15.47 25.00 .00 8.00 16.00 8.00 -9 7 5.00 15.47 5.

KRR PS AA BB CC DD EE BCMM FRC

8500.00 7. 0. 20. .130 40. .360 15 .0

For the following illustration, some of these will be changed as follows:

AKR KHR CC DD

26. 26. .20 30.

Box 58.002 assigns the coordinate labels (XXU, YYU) and (XXF, YYF) to

the search and file m.inutiae that produced the highest TS score by

using the first entry in the J table in Figure 25. Using the first GI

and GJ values and consulting Figure 22 one sees that the search

minutia number 2 coordinates are (XXU, YYU)= (181 , 219) and the file

minutia number 2 coordinates are (XXF , YYF) = (188 , 211) . Now, referring

to Figure 21, suppose that the search minutiae are superimposed on the

12
file minutiae so that search mlnutla 2 sits on top of file minutia 2.

This is illustrated in Figure 26. The next ranking pair of minutiae in

Figure 25 are search 4 on file 5. Figure 26 shows the X and Y

differences XI and YI as they are computed in box 58.006. The displacement of search and file minutiae are shown as XIJ and YIJ. Since

|xi|<|yi|, control goes to box 58.012 where the specific displacements

SYT=-.033 and WXT=.217 are computed. If the conditions of boxes 58.013

and 58.014 are satisfied, these are suiraned as SY and WX and a count is

kept by ISY. The difference between the angles of minutiae search 4

and file 5, TI, is summed as SA and counted as LA in boxes 58.018 and

58.019. (Subroutine ADA is shown in Flow Chart 19.)

Control then Increases Kl and moves to box 58.003 where the next pair

of minutiae in Figure 25, 3 on 3 is treated. See Figure 27. Since

XI|>|yi| control goes to box 58.008 where SXT=-.186 and WYT=-.100

and these are summed with similar values as SX and WY in box 58.011.

The last pass through box 58.003 where (i, j)=(l, 1) produces another

trip through box 58.012. The values of the various variables, as control makes three passes through point AA in Flow Chart 23, are shown

in Figure 28. When Kl reaches 4, box 58,007 sends control up the left

side of the flow chart where the tensor components GOV, SIW, COW, SIV

and the rotation angle NUU are computed. For example:

C0V=1 - = 1.186.

COV is the amount by which one print is stretched in the X direction

with respect to the other print per unit of length in the X direction . SIW is the amount by which one print is stretched in the Y direction

with respect to the other print per unit of length in the X direction.

In other words, COV and SIW deal with distortions in the predominately

horizontal area shown in Figure 29. In a similar way COW and SIV deal

with the predominately vertical area with respect to the search

minutia at (XXU, YYU)

The angle NUU is the mean of the differences between the various pairs

of minutiae angles that were used in computing the tensor. Control

then moves via

^to Flow Chart 24. The values of the tensor being

illustrated are shown in Figure 30.

5. Transformation of Search Minutiae

The search minutiae will now be moved to new locations as directed by

the tensor and some will be eliminated. The new X, Y, 0 values will

then be used to compute a new S table of DX, DY, D9 values and control

will return to Flow Chart 21 for computation of the final matching

score

Box 61 in Flow Chart 24 computes the XA and YA distance from the

reference search minutia at (XXU, YYU) to each of the other search

minutiae. If |xa|>_|ya| box 61.2 computes a new position (X, Y) for

this other search minutia, i, utilizing the tensor components COV and

SIW. If [xa|<|ya| box 61.3 does the job using COW and SIV. A new

angle TH is computed for this minutia by boxes 61.4 - 65. The location
(X, Y) is where the search minutia i would stand in the file minutiae

space. Box 66 then constructs a small box about this (X, Y) location

as shown in Figure 31. Boxes 67 - 68 then search the appropriate area

of the file minutiae table for any minutia j that falls within this

box. If the difference between the angles of these prospective mating

minutia is less than ANK in box 78, then box 79.1 enters their DX, DY,

D0 values in the new S table. In practical applications this table

tends to be limited to true mating minutiae.

To illustrate the above transformation, consider the first search

minutiae in Figure 22. Box 61 computes XA=181-168=13 and

YA=219-251=-32. Since |xa|<|ya|, box 61.3 computes the new location

for this search minutia as: X=188+(-32) ( . 233)-13=167 . 5 and

Y=211+32xl . 048=244 . 5 . This places the search minutia almost perfectly

on top of the file minutia. The relocated search minutiae coordinates

are shown in Figure 32 along with the resulting S table. The superimposed minutiae of Figure 21 after the tensor transofmation now appear

as shown in Figure 33. After resetting the parameter KR to a much

smaller BKR = 5, control returns via B to Flow Chart 21. — 6. Computation of Matcher Score RS

The computer proceeds through Flow Chart 21 obtaining the following

values for the DX and DY table shown in Figure 32.

i ,1 TR KR-TR R

2 1 1 4 4

3 1 1 4 8

2 0 5 13

4 1 1 4 17

2 2 3 20

3 2 3 23

Control then passes via C to Flow Chart 22, and, since KSW now equals

one, goes to box 34.03 where R is rounded to IIS for possible future

use. The final RS score is computed in box 34.04. S0LD=4 was the

value of S from the previous pass through Flow Chart 21 and was saved

in box 34.02. IMXB=4 and IMXC=5 are the numbers of minutiae in the

search and file sets. S=4 is the present number of entries in the S uT ^ Rq = 8500x23x4 _ qiis table. Therefore: . , ^ - y//3.

4x4x5

7 . Conclusion

In searching 50 cards against a file of 100 cards all of which are from

the ulnar loop section of file, the M82 made a significant improvement

in the hit rate when compared with the M40 matcher. The M40 software

matcher in the UNIVAC 1108 computer matches a pair of prints- in about

2 milliseconds compared with about 150 milliseconds required by the

M82 matcher. The M82, like its M40 predecessor, can be built in high14
speed integrated circuit hardware with a significant improvement in

speed of performance.

The computer programs used in this work were written and managed by J.

F. Rafferty of the National Bureau of Standards. The author is indebted

to R. M. Stock of the Federal Bureau of Investigation for advice and

assistance. The work was financially supported by the FBI.

15
References

Stock, R. M. , "Automatic Fingerprint Reading,"

Proceedings of the 1972 Carnahan Conference on - Electronic Crime Countermeasures , University

of Kentucky, Lexington, Kentucky, 1972, p. 16-28

Banner, C. S., and Stock, R. M. , "FINDER,

The FBI's Approach to Automatic Fingerprint

Identification, " Proceedings of a Conference

on the Science of Fingerprints , Home Office,

London, England, 1974.

Moore, R, T., and Park, J. R. , "The Graphic Pen, an Economical Semiautomatic Fingerprint Reader,"

Proceedings of the 1977 Carnahan Conference on Crime Countermeasures , University of Kentucky,

Lexington, Kentucky, 1977, p. 59-62.

Banner, C. S., and Stock, R. M. , "The FBI's

Approach to Automatic Fingerprint Identification

Part I," FBI Law Enforcement Bulletin , Vol. 44,

No. 1 (Jan. 1975).

Banner, C. S., and Stock, R. M. , "The FBI's

Approach to Automatic Fingerprint Identification

Part II," FBI Law Enforcement Bulletin , Vol. 44,

No. 2 (Feb. 1975).

Wegstein, J. H. , The M40 Fingerprint Matcher , National Bureau of Standards Technical Note 878,

U. S. Government Printing Office, Washington,

D. C, 1972.

16
y

/ n \ \\ \^'

/ n n\\

/ f f n \ \

Figure 1. Ridge Directions, Pattern, and

Minutiae for a Portion of a Fingerprint

X

Figure 2. Definition of Minutiae Data (X, Y, 9)

17
t/' / / / X

i

j/" X ^ ^ ^ jii^

«——e—

.

0^ ^ ^ ^ ^

^ ^

l"^^^^ ^ ^ ^ ^

j) X ^ ^

7 A

3,

\

^^^tsi^ ^^^^^

^^^^V,

^^^^^^

1 \^ \^ \^ I

Ns)^ \^ ^^^^

\^ \^ \^ ^

'^^^^

\ X

\

\

J> ^ ^ ^ ^ <^ <j> () I ^ \^ ^"^^ ^^^^ y^^^ ... . ^ ^

^ ^ ^ ^ ^ ^ ^ X ^ ^ \

^^^^

^^^^V

^

IpS^ ^ ^ ^ j) X I y^'^ X' X ^

—®

1%^ X X ^ ^ ^ j/^ j/' ^jgf^

^ jl{ ^jtf^^^jtf^—e-

-^—i^jB^ ^ ^ ^

—' —®'

j) XdJlS^ ^

j/ ^ X ^

J'^ X^'^^ <»—-^

Figure 3. Ridge Direction Data from

Automatic Fingerprint Reader

18
13 IH IS /G 17 It II ZD

J-3 J-% J-\ J J+\ J-^l J+3 J-t-HFigure 4.

Locating

Core Area

K TRY TI TJ TSBC TSAD TLCS TSDY TSXH TSXL TSW

1 0 5 18 17 67 9 57 123 48 2 2 0 6 17 12 48 10 62 110 50 2 3 0 7 17 10 50 10 107 157 70 2 4 0 8 16 22 70 10 98 168 88 2

5 1 9 17 18 88 10 108 197 132 2 6 1 10 16 47 132 10 98 230 177 2

7 1 11 16 65 192 8 78 270 243 2 8 1 12 16 110 246 8 89 335 307 1

Figure 5. Contents of Table K Upon Arrival

at Point a in Flow Chart 1

Figure 6. Analysis

of Core

Area

JKL n 15 lb n II m JKR

n.

/ / / y

/ T T / .

.

.

19
K TRY TI TJ TSXH TXSL TSA

1 0 1 1 xo1 p. 1 O 73 260

2 0 Xo X4Z O T 81 318

3 0 -L_) 1 Xo 96 337

4 n XO 109 366

_) U 15 18 150 110 392

6 0 16 18 125 66 346

7 0 17 18 87 47 0

8 0 18 18 50 34 0

Figure 7. Portion of K Table Associated with

Arch Pattern in Figure 8

Figure 8. Portion of an Arch Pattern Near Center Point "+"

20
J-l J J*' j-l-l

i l\ tf^ Z3 IH HI ZZ Z3 Zt ZZ. Z3 2V

A 3

Figure 9. Core Location (XX, YY) Marked "+"

for Three Ridge Patterns

9^'

>

\ XXI

V5 V5PI

DSPI

for Loops, Whorls,

and Arches

1

1 \\

vs\ \ \

1 ?^

^

1

1

1 1 XO'j XX/ XX y—

xx-xx^ ^ ^j±_

2)5

yy- y(i)-ds+i>H

Figure 11. Computation of XX

and YY for Loops

and Whorls

k y(KT-i)^zoo

/6 1im)^n7^

yy^/a?

Figure 12. Computation

of YY for

Arches

r5A

T5A

21
Figure 13. Flaw in Minutia

Direction Angle

Figure 15

AMN<450

y

/-A

Figure 16

AMN>A50

DSP

VSP

a>sp

\1

:dsp

Figure 14. Selection of

Neighboring Ridge

Directions

A \/ \ 3

IJ}\ i 1 I I JL JC JR.

Figure 17. Pairs Contributing

to >V

^5*

/ss

"10

il

'55 30.

Figure 18. Ridge Quality Measures Around (i,j)

22

24
/

/

Figure 21. Search Minutiae • Superimposed on File Finutiae ^

X Y 9 X Y e

i AilB Ai2B Ai3B i AjlC Aj2C Aj3C

1 168 251 45 1 167 245 47

2 181 219 60 2 188 211 64

3 251 196 320 3 271 195 327

4 232 159 335 4 182 172 30

Search Minutiae 5 252 149 343

Figure 22

File Minutiae

1

1

1

1 L5

d _ -LS

Figure 23- Definition of DX, DY, D©

25
Tn 1 "1 s DX DY D6 IS JS Contribution TS

1 1 6 -2 1 1 16 1 17

2 -7 8 -4 2 2 16 6 11 33

3 -20 1 -7 3 3 6 17 23

4 -20 10 -8 4 5 1 11 17 29

Figure 24. The S Table

Kl, .1 GI GJ GT

1 2 2 33

2 4 5 29

3 3 3 23

4 1 1 17

Figure 25. The J Table

2:2 n='7o

|XI|>|YI|

Figure 27

Figure 29. Tensor Areas

XXL/, yy(/

XIJ=XI-XJ

YIJ=YI-YJ

Figure 26 xrj=

i3_

Ki

2 3 4

i 4 3 1

j 5 3 1 XI -51 -70 13

YI 60 23 -32

XJ -64 -83 21

Y J 62 16 -34

XIJ 13 13 -8

YIJ -2 7 2 SYT - . 033 - . 063

WXT . 217 .250

SY - . 033 - . 096

wx .217 .467

ISY 1 2 SXT 186"~

WYT - . 100

SX 0 - . 186 - . 186

WY 0 - . ] C 0 - ,100

ISX 0 1 1 TI -8 -7 -2

SA -8 -15 -17

LA 1 2 3

Figure 28. Tensor Development

26
GOV SIW cow SIV

1.186 -0.100 1.048 0.233

Figure 30. The Values of the Tensor

Figure 31. File Space

i j XA YA X Y TH S DX DY DG

1 1 13 -32 168 245 51 1 1 0 4

2 2 0 0 188 211 66 2 0 0 2 3 3 -70 23 271 195 326 3 0 0 -1

4 5 -51 60 253 148 341 4 1 -1 -2

Figure 32. Relocated Search Minutia and S Table

Figure 33. Tensored Search Minutiae Superimposed on File Minutiae

27
K-0 i^PKIO

XX ^ zoo. vy^zoo. 1

7 \

I

i-i

V <

¥3

0

jlc = 0

LCHt

/5. ±

/a

/4

A3 PiJ

c

3?

LCH^LCli+l

*^ ~

37

LCK^LCK-^I

33-

H 3^

33

3^ AD'AN : ms LCK=La^l

3Z

29

LCK=LCKfl

30 :<!

31

LC-R=LCK-hl

zs.

It lEZ 2 3

m-AAmd LCK =LCR-^I

2e- f

^\AA^ 0

17. I

21.

5Bc = lA3l-^lAcl 3AV '53C+lA/[hlADl

Flow Charf I -RIZ Parfl

28
— w

1^

50.1

o

TRYk-O TlK=i TJk^J TS3Ck='^3C TSADk=5AD

TLC-Rk^LCH tsvYk^O. TSKHk=0, TSXLk^^O.

TSWk'^SW SXH=0. 5XL=0. TTCk=0 TTFk^O

TTGk^O TTk^O TTKk'=0 TTSk=0 TSAk=0

t

59,02

TJLk^JLC

TSh/3K = 0

SW 5<\.5

lYLd^jiK^'Rm

^ XlYL3:'RKll

-i-tl

ninz

n-ni

S7X-0.

7^ (v57X;5;ri^3///^577 —Y> r

-MZ

TSJ)YK-^5py TSXH.=SXH TSXU^SXL

77 TRYk^I

29

Flowchart Z
a

13

!u TSL^minv-pii.m +7^K3i

5lVk/^0 TRF^O

HI

IT&^ITG^I

111

/35|> —

%1

?5R^HK(jxPi-hj)^llm'-Ki{3l

SWI^O in ^ >

1

I TZTTTTT

IYF-TIk

I IIF^O i

IUL-iyP'3

JXL = JXP-¥

5^: 0

ISOUL-UT

1£L.

LSJL.

I

UT= P'SP'-%j

UT=UT-ISO,

JUJXL)

UV = IUT-ULl

UL=UT

'5 >|<

/02

—^"z:

J^JXR 10(0 llf-0

MA. 3"

Flowchart 3 K'^Z Tart

3

30
120

12 \ ('RASK:mi)

CrATK: mqj^,

TIFtUZi) i

TinmT)^,

;/7 l<

Jv

H3

'RASKK

mrx

riFx

riCKX ^TICK

KTX^K

(?) (.TStTRF^

172.2 TRVk'.O

f7S

rRF=T5

KT=K

>y

171 V<

170 I ^

j:J1^t)^T5=T5^I%I

TTCk^TICK

TTrs = TfF

TTk = -RAT

TTKk^KATK

TTdK^HASK

JLF=J-1^KIZ

J'RT^Ji-l+mz

112

mr^nAT-tHAs

TIF = IF

TICK = IC

SW3^0

JUL

/u

/56

TRF=0

K=2

< V J5XU\'Rm

TiK-TiH-r.i) \ "

1

^ ^

,^ ^

31
ISO I

CLU=3

KT=0

i$z'

^ \ im

m

im=iM

CLU-^Z

IYF-TIkt

JXL-I

Its'

J30_

?07

(cL){:oyg03_

JXF= TJkt

UP'^TIkt

KT^m

20S.H

cJXP=TJkt

lYP^Thr

ill

c

m.

>/

ZDS CLU=! KT^K

Z03

22?

TLCF^TLCRkt

230 V 23/

233 V

7ir

(tIk*2-T1k*i:i)

^

^

a3 V 235- .

g3V >t - t

Z37 1-

(/TjKK-Vu-<i''i)Hri.rTL.-r'ip

'

Flo IV Chart S 'R'iZ ?arf S

32
223

219 ( jL w y

Z20

2ii

I

JL=TJLkt

:DHI+DHZ

rr —5 T-m

222

a/3 1?^

( CLUtZ }

2/¥

2/2

( KT:my

2/6.

TDNM -a

DSPI ^

211 I

^

2/5"

I? -TlKJ + i m=TlKr-,

TNU/A-^(7^SrZi.(IP'i|^nil^JS^Kr^

TNUfA

TDN/A

Flowchart 6 Fart 6

33
St

2 = i-^l a

J =j+ /

J

(jjmh)

5.4

K = 0

AlL = Aii,-DSP

(Ajzz :AZH)^Am 'AZL)^ ( Aj.z:AZl)

1

SI

r<:—*^

IS

^ 7

17

AKx=Aj3i-m

A 2V

Aizz'.hZH)

(mil)

XKk - Ajiz

^

13 ^ 1Kk =Aj^z \^Aj,z ; )

p i> 4:

/I.

/5-

Flo^Charf 7 AIAN&A I

34
A// -Ail, ~ Ahi

Al.31 = TP

5^

S7

TP-TP-f-3G0,

s/

^^^^^^^^

TP^lP'iW.

30

K= /<+/

jj^ SN^SN+ATk'^ AKk

JiL

TP=TP-^/SO,

3$

3^

57

3£_ 33

5N-=5N-i-ATK-AKK

SD =5d + ATk

Flowchart ? M/\N6A TL
3.

JL^JXP-KJL

JC=JXP~KJC

IV^IYP^KDN

i : 0

s.

7.

JL=dL+l

JR = JR-I

j=JL Jj = JK

<

JJ^JJ-I

ID ^ ID1

J

<

20-1 /i it n

/7 J I , , V-r

- -7./

II.

/a. 1 =-| ;3,

I

'—

i/=a

/6.

Flowcharts NU I'i

a. > I >

"A,3,/;g!)

^

//I = X/-/1i,;,/

-=zoo-x^^5I\l-i^''Coy

Ai,3,t = 1/ + Ai,3.l

Flow Chart 10 TRARO

36
/. UXL = m-TXA

Uyu =Zoo.+ ?YU

(JYD^ZOo.-TYXi

2 = 1 J-0

10.

s

(^Ai,z,Ki UYB)^/\i,z,K: UYUy^AiM[ UXJ^y^Ai.K' UXL

<I_ -Jf^ ~J>^ ^t<-

7

J-J-f-l Aj,f,K-Al,l,K Aj,2,K =A2,Z>K Ap,H=Az,3,K

Flow Chart /I CLIP 3

_7 fc. 1 =

2 :mo)^J=i^i

<

Aj,z. ,-TZ

T3 ~/lz,3,/ ^Aj,3,l Air ,^T3

rioh/ Chart 12 YSOKT

2

rHT= THl -THZ KtOT^^^

rHT=THT-/SO.

s. THT =THTi-ISO.

Flowchart /3 m(rHi,TH2)

37
3.

. tf I'f

7.

QZ=m(3i,j, 3i,j-i)

Flowchart /¥ QUAL

3i,j

ryp, JXP

lUP

JL

m

QA5 = QA5 -i-QA

QZAS-QZAS-^QZA

~ J~

u

is:

1 3. ( AIQ:0

Qzm=

QAS

Km

QZAS

QUAL

~~r~ IL

JR)

M

(jmjzl

10.

1

IJ)N=IVDI-I

/I V

>

KQN

zz GAM-a

//. QAS^O.

QZA5 = 0.

KQN^O

i ^ruF

11. y<

2=1+1

FloNChari IS QG'I

38
l\IJ)=-0

Z5 ' ~~J—

>

l32,jl:QK5)

31 1^

JL^JXP-f

LDN=IYP^I

3S

5v

ND^3 f-n

3i

94

33

5^.

31.

J

J

so \'

ND=3

>i

^2. ^

<

J-7 1±-

Flow Chart !G Q(o-JL

39
1=1 MD^O J=l 2 = 2+/

V 2. /2 z - mo

II.

>-:i:

Flowchart 17

T'RO

A s.

1 = 1+1

3 < Ji

(//l/./-4,/=7-/()

- 2=/

Z2.

JL

^

I_ /Z. I 17.

Zl. f

I z'?^ — 2^. V

>

lf QJm) . 3/.

^y.

—3

Z

^ ^ 27.

nOh/ Chart TIUP

D/l - DA ^ DA

Flowchart /? AmfALA2,DA)

40
2.

3. \ c

IMXC =mx,

K5h/^0

KR^m

>/

V.3

6.2

1

6,^

< ^,3

^.2

9.1 J^ : /AlXc)

2/. <

A

Ay Zl X = /4 2,3,5 ""/!/, 3, C

< T> /5.

IG,

Flow Chart ZO mz Tarf i

41

17. {g, fS.I

5 = 5-^1

Ms - AX

Ws^AB

ISs ^ z
2=1 + /

31

30 ^ TO - iDBi -Wjl

\rs„=o.

23

72 =a

^ '

i I C F>: ??l2 ^ r—. ^ ^7

2? -TR.

-TR

3Hr/oh/Char-f- 21 mz Ta^fz

39,03

> 3fM

(£)

tOU N

»

( K5W:0 )

SOLD niAys mxc

90

SO

GJjfi

GTjti

Hi)

¥6^

I 1

^1

QJj — JS/n

GTj -TS/n

I1^

51

Flow Chart ZZ 7krf3 ^^'^ K=KMM

42
LA

si US I

5A = 3/4 +71

U

NUU^ 0.

^{.02%

L

31V ^ 0,

<

ssJW

3y

ISY

5IV^

ISY

sy - sy+SYT

isy=isY+i

>

sx = SX+SXT

m+i

( I5Y:0

COV^I.

5X

m

ISX

(jlsyjli cc}

WXT-^

ClXll:lYliy

COV^I.

SJVi-0.

3^

XIJ

XI

yij — XI

KliK)

XJ=XXF -AjAc

YJ =/YF-Aj,z,c

XIJ= XI -xo

YIJ' Yl-YJ

T

<

LA^O 3A=0,

lSX-^0 5X=0.

sy=a

Flow Chart Z3 Ai^z Tart ^

43
(,0.01

2 = 1 5^0

i ^1

t3 7?

/-^^'\ ~

1

ri- ll

6/.

X/4 =xx(;-/f^/,3 7f./

, Y 77 f

61-z y

X^XXF-i-YA'SIV-XA

L Y^YYF-yA'COl^/

76

AVAfTHjj.3,c,Dw) —

iZ

I

'

<

(,3 V

s

-^i(Aj,,,c'.XL )

_Z2

us

7/ 1^

7^ i ^

&7

YH = Y^XYK XR^X^XYK

YL =- Y-XYK XL^X-XYH

0^

IF

J = J-I

Flow Chart Zf Tarf S

A4
NBS-n4A (REV. 2-8C) U.S. DEPT. OF COMM. BIBLIObKArnlL UAIA

SHEET (See instructions)

1. PUBLICATION OR

REPORT NO. NBS SP 500-89

2. Performing Organ. Report No. 3. Publication Date

February 1982

4. TITLE AND SUBTITLE

An Automated Fingerprint Identification System

5. AUTHOR(S)

Joseph H. Wegstein

6. PERFORMING ORGANIZATION (If joint or other than NBS, see in struct/on s)

NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

7. Contract/Grant No.

8. Type of Report & Period Covered

Final

9. SPONSORING ORGANIZATION NAME AND COMPLETE ADDRESS (Street. City. State. ZIP)

Federal Bureau of Investigation

U.S. Department of Justice

Washington, DC 20535

10. SUPPLEMENTARY NOTES

Library of Congress Catalog Card Number: 81-600193

Document describes a computer program; SF-185, FIPS Software Summary, is attached.

11. ABSTRACT (A 200-word or less factual summary of most si gnificant information. If document includes a si gnificant

bibliography or I iterature survey, mention it here) Procedures are described for automatically identifying fingerprints.

Machine-read ridge-direction and minutiae data are utilized in

registering and enhancing search or file minutiae data. The quality

of the data is measured. A procedure is then described for utilizing

this minutiae data in determining whether two fingerprint impressions

were made by the same finger.

12. KEY WORDS (Six to twelve entries; alph abeti cal order; capital i ze only proper names; and separate key words by semicolon s)

Computerized-fingerprint-identification; identification; pattern recognition.

13. AVAILABILITY

X! Unlimited

I I For Official Distribution. Do Not Release to NTIS

Order From Superintendent of Documents, U.S. Government Printing Office, Washington, D C

20402.

Order From National Technical Information Service (NTIS), Springfield, VA 22161

14. NO. OF

PRINTED PAGES

47

15. Price

USCOMM-DC 6043-P80
ANNOUNCEMENT OF NEW PUBLICATIONS ON

COMPUTER SCIENCE & TECHNOLOGY

Superintendent of Documents,

Government Printing Office,

Washington, D. C. 20402

Please add my name to the announcement list of new publications to be issued in the series: National Bureau of Standards Special Publication 500-.

Name

Company , Address

Ciiy State Zip Code

(Nolification key N-503)
NBS-n4A (REV. 2-8C) U.S. DEPT. OF COMM. BIBLIOGRAPHIC DATA

SHEET (See instructions)

1. PUBLICATION OR

REPORT NO.

iNDo or puu oy

2. Performing Organ. Report No. 3. Publication Date

February 1982

4. TITLE AND SUBTITLE

An Automated Fingerprint Identification System

5. AUTHOR(S)

Joseph H. Wegstein

6. PERFORMING ORGANIZATION (If joint or other than NBS, see in struct/on s) 7. Contract/Grant No. NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE 8. Type of Report & Period Covered

WASHINGTON, D.C. 20234 Final

9. SPONSORING ORGANIZATION NAME AND COMPLETE ADDRESS (Street. City. State. ZIP)

Federal Bureau of Investigation

U.S. Department of Justice

Washington, DC 20535

10. SUPPLEMENTARY NOTES

Library of Congress Catalog Card Number: 81-500193

[^J Document describes a computer program; SF-185, FIPS Software Summary, is attached.

11. ABSTRACT (A 200-word or less factual summary of most significant information. If document includes a significant

bibliography or literature survey, mention it here) Procedures are described for automatically identifying fingerprints.

Machine-read ridge-direction and minutiae data are utilized in

registering and enhancing search or file minutiae data. The quality

of the data is measured. A procedure is then described for utilizing

this minutiae data in determining whether two fingerprint impressions were made by the same finger.

12. KEY WORDS (Six to twelve entries; alphabetical order; capitalize only proper names; and separate key words by semicolons)

Computerized-fingerprint-identification; identification; pattern recognition.

13. AVAILABILITY

X! Unlimited

I I For Official Distribution. Do Not Release to NTIS

[~\ Order From Superintendent of Documents, U.S. Government Printing Office, Washington, D C

20402.

[X^Order F rom National Technical Information Service (NTIS), Springfield, VA 22161

14. NO. OF

PRINTED PAGES

47

15. Price

USCOMM-DC 6043-P80


\
NBS TECHNICAL PUBLICATIONS

PERIODICALS

JOURNAL OF RESEARCH—The Journal of Research of the National Bureau of Standards reports NBS research and develop- ment in those disciplines of the physical and engineering sciences in which the Bureau is active. These include physics, chemistry,

engineering, mathematics, and computer sciences. Papers cover a broad range of subjects, with major emphasis on measurement

methodology and the basic technology underlying standardization. Also included from time to lime are survey articles on topics

closely related to the Bureau's technical and scientific programs. As a special service to subscribers each issue contains complete

citations to all recent Bureau publications in both NBS and non- NBS media. Issued limes a year. Annual subserlption: domcslie $ I S; lureign S22.5U. Single copy 5>4.25 domestic; S5.35 loreign. NOTE: The Journal was formerly published in two sections: Section A "Physics and Chemistry" and Section B "Mathematical

Sciences." DIMENSIONS/NBS—This monthly magazine is published to in- form scientists, engineers, business and industry leaders, teachers, students, and consumers of the latest advances in science and

technology, with primary emphasis on work at NBS. The magazine

highlights and reviews such issues as energy research, fire protection, building technology, metric conversion, pollution abatement,

health and safety, and consumer product performance. In addition, it reports the results of Bureau programs in measurement

standards and techniques, properties of matter and materials, engineering standards and services, instrumentation, and

automatic data processing. Annual subscription: domestic $11;

foreign $13.75. NONPERIODICALS

Monographs—Major contributions to the technical literature on

various subjects related to the Bureau's scientific and technical activities. Handbooks—Recommended codes of engineering and industrial practice (including safety codes) developed in cooperation with in- terested industries, professional organizations, and regulatory

bodies. Special Publications—Include proceedings of conferences sponsored by NBS, NBS annual reports, and other special publications

appropriate to this grouping such as wall charts, pocket cards, and

bibliographies. Applied Mathematics Series—Mathematical tables, manuals, and

studies of special interest to physicists, engineers, chemists,

biologists, mathematicians, computer programmers, and others engaged in scientific and technical work.

National Standard Reference Data Series—Provides quantitative data on the physical and chemical properties of materials, compiled from the world's literature and critically evaluated. Developed under a worldwide program coordinated by NBS under

the authority of the National Standard Data Act (Public Law

90-396).

NOTE: The principal publication outlet for the foregoing data is the Journal of Physical and Chemical Reference Data (JPCRD)

published quarterly for NBS by the American Chemical Society

(ACS) and the American Institute of Physics (AlP). Subscriptions,

reprints, and supplements available from ACS, 1 155 Sixteenth St., NW, Washington, DC 20056.

Building Science Series—Disseminates technical information developed at the Bureau on building materials, components,

systems, and whole structures. The series presents research results,

test methods, and performance criteria related to the structural and

environmental functions and the durability and safety characteristics of building elements and systems.

Technical Notes—Studies or reports which are complete in themselves but restrictive in their treatment of a subject. Analogous to monographs but not so comprehensive in scope or definitive in treatment of the subject area. Often serve as a vehicle for final reports of work performed at NBS under the sponsorship of other government agencies.

Voluntary Product Standards—Developed under procedures

published by the Department of Commerce in Part 10, Title 15, of

the Code of Federal Regulations. The standards establish nationally recognized requirements for products, and provide all concerned interests with a basis for common understanding of the

characteristics of the products. NBS administers this program as a supplement to the activities of the private sector standardizing

organizations. Consumer Information Series—Practical information, based on NBS research and experience, covering areas of interest to the con- sumer. Easily understandable language and illustrations provide

useful background knowledge for shopping in today's technological marketplace. Order the above NBS publications from: Superintendent of Documents, Government Printing Office. Washington. DC 20402. Order the following NBS publications—FIPS and NBSIRs—from

the National Technical Information Services. Springfield. VA 22161

.

Federal Information Processing Standards Publications (FIPS

PUB)—Publications in this series collectively constitute the Federal Information Processing Standards Register. The Register

serves as the official source of information in the Federal Govern- ment regarding standards issued by NBS pursuant to the Federal Property and Administrative Services Act of 1949 as amended.

Public Law 89-306 (79 Stat. 1127), and as implemented by Executive Order 11717(38 FR 12315, dated May II, 1973) and Part 6 of Title 15 CFR (Code of Federal Regulations).

NBS Interagency Reports (NBSIR)—A special series of interim or

final reports on work performed by NBS for outside sponsors

(both government and non-government). In general, initial dis- tribution is handled by the sponsor; public distribution is by the National Technical Information Services, Springfield, VA 22161,

in paper copy or microfiche form.
U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

Washington, DC 20234

OFFICIAL BUSINESS

Penalty for Private Use. $300

POSTAGE AND FEES PAID

U.S. DEPARTMENT OF COMMERCE

COM-215

THIRD CLASS