<**«" °' c

0i

^1*

Vau of *

\

Q

ISIBS TECHNICAL NOTE 878

U.S. DEPARTMENT OF COMMERCE/ National Bureau of Standards

QC

100

U5753

no ,878

1975

c.2
NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards' was established by an act of Congress 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: (I) 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 consists of the Institute for Basic Standards, the Institute for Materials Research, the Institute for Applied Technology,

the Institute for Computer Sciences and Technology, and the Office for Information Programs.

THE INSTITUTE FOR BASIC STANDARDS provides the central basis within the United

States of a complete and consistent system of physical measurement; coordinates that system

with measurement systems of other nations; and furnishes essential services leading to accurate and uniform physical measurements throughout the Nation's scientific community, industry, and commerce. The Institute consists of a Center for Radiation Research, an Office of Measurement Services and the following divisions: Applied Mathematics — Electricity — Mechanics — Heat — Optical Physics — Nuclear

Sciences- — Applied Radiation " — Quantum Electronics" — Electromagnetics 3 — Time

and Frequency n — Laboratory Astrophysics :l — Cryogenics r

'. THE INSTITUTE FOR MATERIALS RESEARCH conducts materials research leading to improved methods of measurement, standards, and data on the properties of well-characterized

materials needed by industry, commerce, educational institutions, and Government; provides

advisory and research services to other Government agencies; and develops, produces, and

distributes standard reference materials. The Institute consists of the Office of Standard

Reference Materials and the following divisions: Analytical Chemistry — Polymers — Metallurgy — Inorganic Materials — Reactor

Radiation — Physical Chemistry.

THE INSTITUTE FOR APPLIED TECHNOLOGY provides technical services to promote

the use of available technology and to facilitate technological innovation in industry and Government; cooperates with public and private organizations leading to the development of

technological standards (including mandatory safety standards), codes and methods of test; and provides technical advice and services to Government agencies upon request. The Institute consists of a Center for Building Technology and the following divisions and offices: Engineering and Product Standards — Weights and Measures — Invention and Innovation — Product Evaluation Technology — Electronic Technology —- Technical Analysis — Measurement Engineering — Structures, Materials, and Life Safety 4 — Building

Environment* — Technical Evaluation and Application* — Fire Technology.

THE INSTITUTE FOR COMPUTER SCIENCES AND TECHNOLOGY conducts research and provides technical services designed to aid Government agencies in improving cost effec- tiveness in the conduct of their programs through the selection, acquisition, and effective

utilization of automatic data processing equipment; and serves as the principal focus within

the executive branch for the development of Federal standards for automatic data processing

equipment, techniques, and computer languages. The Institute consists of the following

divisions: Computer Services — Systems and Software — Computer Systems Engineering — Information Technology.

THE OFFICE FOR INFORMATION PROGRAMS promotes optimum dissemination and

accessibility of scientific information generated within NBS and other agencies of the Federal Government; promotes the development of the National Standard Reference Data System and

a system of information analysis centers dealing' with the broader aspects of the National Measurement System; provides appropriate services to ensure that the NBS staff has optimum

accessibility to the scientific information of the world. The Office consists of the following

organizational units: Office of Standard Reference Data — Office of Information Activities — Office of Technical

Publications — Library — Office of International Relations.

1 Headquarters and Laboratories at Gaithersburg, Maryland, unless otherwise noted; mailing address Washington, D.C. 20234.

3 Part of the Center for Radiation Research.

3 Located at Boulder, Colorado 80302.

« Part of the Center for Building Technology.
a 1377 a,c c ^

The M40 Fingerprint Matcher

-t iecV^CaV ^oW) ^o.

"

J. H. Wegstein

Institute for Computer Sciences and Technology

National Bureau of Standards

Washington, D.C. 20234

Sponsored by

The Federal Bureau of Investigation

Washington, D.C. 20535

*< °r °°< 4

%

X

/

°*t:AU Of

U.S. DEPARTMENT OF COMMERCE, Rogers C. B. Morton, Secretary

V^.S NATIONAL BUREAU OF STANDARDS, Richard W. Roberts, Director

Issued July 1975
National Bureau of Standards Technical Note 878

Nat. Bur. Stand. (U.S.), Tech. Note 878, 14 pages (July 1975) CODEN: NBTNAE

U.S. GOVERNMENT PRINTING OFFICE

WASHINGTON: 1975

For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C. 20402 (Order by SD Catalog No. C13.46:878). Price cents (Add 25 percent additional for other than U.S. mailing).
The M40 Fingerprint Matcher

J.H. Wegstein

A procedure is described for automatically

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 the 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 impressions to the other.

Key words: Computerized - fingerprint -

i denti f i cati on , f i ngerpri nt

,

pattern recognition.

1 . Introduction

An average rolled fingerprint impression exhibits about eighty ridge

endinqs and forks or bifurcations in its ridge pattern. By comparing the

data representing these minutiae, a computer can determine whether or not

two fingerprint impressions came from the same finger. Figure 1 shows

how the x and y coordinates and the direction 8 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.

A Dortion of a fingerprint along with a plot of the corresponding

minutiae are shown in Figure 2. The minutia data are read automatically

from the rolled impressions on fingerprint cards 1 ,2,3,4 ancj

-j n addition,

the reader also produces ridge direction data at equally spaced

grid-points over the entire print. In a fully automated identification

system, this ridge-direction data is utilized in finding the core or "center" of a print as well as the angle through which the print should

be rotated. 5»6 This registration information is used to translate and

rotate the minutia data into a standard position. The ridge-direction

data in the neighborhood of each minutia is also used to make slight

corrections to the angle e of that minutia. Those registered minutiae

within a certain distance of the center are then sorted into a descending

order on y and this data may then be placed in a file or used to search

against minutia data in a previously established file.

The matcher, M40, described here differs from the previously

reported Ml 9 matcher?- only in that M40 utilizes ordering in the y direction to achieve a great increase in SDeed, and the final matching

score is computed in a slightly different manner.

1
2. Selecting Minutiae

Complete details for the M40 procedure are given in Flow Chart 1 The values of x,y, and e are handled as elements in an array, A, as follows:

x y e Search Minutiae Ail! Ai 21 Ai 31

File Minutiae Aj 1 2 Aj22 Aj32

The number of search minutiae IMX"| , is first compared with the number of

file minutiae IMX2- Whichever is smaller is identified as IMXB.

Each value of y-j ( A i 2 1

) in the control set 1 is then used to determine

the range of values of yj ( A -j 2 2 ) ln se t 2 W1'^

n which comparisons are to

be made. Thus YBL < Aj 2 2 1 YAB, where YAB (above) and YUL vuelow) are determined by A-,-?]- While index i runs from 1 to IMX] , index j is

determined by this "window".

3. Difference Tables

The M40 matcher can deal with a certain amount of distortion and

lack of registration between two fingerprints that are being compared.

To illustrate this, the superimposed plots of minutiae from two different

prints A and B, made by the same finger, are shown in Figure 3. This is

typical of the appearance of superimposed minutiae from two prints that

have been read by machine. There may be missing or false minutiae. Here

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. X and Y are measured in units of one-tenth millimeter and 6 is

measured in degrees. The minutia data for prints A and B is shown in

Figure 4.

Since print A has 5 minutiae and print B has 6 minutiae, IMXB = 5. The procedure begins by comparing:

DX = Xi - Xj

DY = Y

i - Yj

De = e-i - e-i
where i runs from 1 to IMX] and j is determined by the previously

described window. Only those pairs of minutiae that satisfy the

following conditions simultaneously are used.

| DX | < LS

| DY | < LS

| De I £Le

If the matcher parameters have the values

LS = 60

Le = 25

then the resulting differences can be plotted as points in a ax, Ay

coordinate system as shown in Figure 5. If the prints are from the same finger then many points will tend to be in a cluster, but if the prints

are from different fingers the points tend to be randomly located over

the entire area. Figure 6 is an enlargement of the cluster area from

Figure 5 and Figure 7 gives the difference table for prints A and B. For

example, point 1, 1 in Figure 6 indicates the distance from minutia Bl

to Al in Figure 3.

4. The Matching Score

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

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

accomplishes this by starting from each point in the graph in Figure 6

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

the other points. (See boxes 23 through 36 in the Flow Chart.) 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. De can also be

made to contribute to the R score by selecting a suitable value for a parameter Ke. To see how this works, let KR = 10 and refer to Figure 6

and the difference table in Figure 7. The column S in Figure 7 determines the order in which steps are counted. One goes from S = 2 to

S = l, S = 3 to S = 1 , S = 3toS = 2, S = 4 to S = 1 , etc. The number

of steps from point 2,2 to point 1,1 exceeds 10 so that nothing is added

to R. The distance from 2,3 to 1,1 is just 10 so again, nothing is added

to R. In fact nothing is added to R until one goes from S = 4 to S = 2.

Here, in going from point 3,4 to point 2,2 one steps down 5 steps and to

the left 3 steps, or a total of 8 steps. Thus TR = 8, and the score R

is increased by KR - TR = 10 - 8 = 2. Referring to Box 25 in the Flow

Chart, the computer computes

TR = |DX4

- DX 2 | + |DY 4- DY 2 | or TR = |-35 + 38 | + | 9 - 4 | = 3 + 5 - 8

In Box 29, R which was previously set to is increased to 2.
The next contribution to the score R occurs when one steps from

point 4,5 to 2,2. Two steps to the right and two steps down gives

TR = 4. Then R = 2 + (10 - 4) = 8. The history of the development of

the R score is shown in Figure 8 where the final value of R is found to

be 12. The matching score actually used is

dc KRR x R Kb

IMXB

where KRR is a scaling parameter. In this illustration let KRR = 2.

Then

RS =

2 * 12

= 4.8

5

5. Conclusion

Matching runs have been made with a Univac 1108 computer on data

read by the FBI's prototype fingerprint reader from somewhat better than

average quality fingerprint cards. The parameter values most frequently

used were:

LB LS K6 KR KH9 KHR KRR

10. 10. 0. 8. 8. 8. 2.

The average matching time per pair of prints was about 20 milliseconds.

Einht prints from each card were used (little fingers excluded). For the

most frequently used reference data set, the average matching score for

nrints from the same finger was 26.04. The highest mating print score observed was 165. The average score for non-mating prints (false

matches) was 0.97. The highest false matching score observed was 17. It

appears that a threshold score can be establ ished- such that when a pair

of prints exceeds this threshold, a positive identification is achieved.

The computer programs used in this work were written by J.F. Rafferty

of the National Bureau of Standards. The author is also indebted for

advice and assistance to R.T. Moore of NBS, and R.M. Stock of the FBI.

The work was financially supported by the FBI.
6. References

1. 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

2. 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.

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

Automatic Finqerprint Identification, Part I," FBI Law

Enforcement Bulletin , Vol. 44, No. 1 (Jan. 1975).

4. 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).

5. Wegstein, J.H., Manual and Automated Fingerprint

Registration , National Bureau of Standards Technical Note

730, U.S. Government Printing Office, Washington, D.C., 1972

6. Wegstein, J.H., "The Automated Classification and

Identification of Fingerprints," Proceedings of a Conference on the Science of Fingerprints , Home Office,

London, England, 1974.

7. Wegstein, J.H., Automated Fingerprint Identification , National Bureau of Standards Technical Note 538, U.S.

Government Printing Office, Washington, D.C., 1970.
Figure 1. Definition of Minutia Data

S W

/

NX

:7

/V;. ^

L \.

^ x

\

V

_i

Fiqure 2. A Portion of a Fingerprint with

a Plot of Corresponding Minutiae
31

Scale

+

10 20 30 HO

Units

A3

At

BS

BG

Figure 3. Superimposed Machine-Read

Minutiae from Prints of the

Same Finger

Minutiae from Print A

Minutiae from Print B r

Print A

1 48 252 67

2 136 233 111

3 27 190 226

4 142 181 327

5 68 174 205

Print B

J X y e

1 75 241 65

2 174 229 128

3 157 226 in

4 62 181 225

5 182 175 346

6 109 161 222

Figure 4. Minutia Data for Prints A and B
Ay

--50 —Ho —3C

lo

i L f-rJi i A

10—It

I—3oI—i/oI—SOH,&>

AX

-60 SO -HO -30 -10 ~/0

-lo

20

30

¥0

so

=40-

Fiqure 5. Difference Graph for Prints A and B
A/

1 —— i — -25

— on20

._. f IT u

5

i 6~

|

/,/

it

_> //I 3,¥ /0

2,3

%s < F

1 t

2,2

*5

"

i -yj -w -35 -30

AX

-25- _20

Figure 6. Enlarged Portion of Difference Graph for Prints A and B

J DX DY D8

1 1 1 -27 11 2 2 2 2 -38 4 -17

3 2 3 -21 7 4 3 4 -35 9 1 5 4 5 -40 6 -19

6 5 4 6 -7 -20

7 5 6 -41 13 -17

Figure 7. Difference Table for Prints A
TR T9

4 2 8 18 2

5 2 4 2 8

5 4 8 20 10

7 5 8 2 12

Figure 8. Matching Score Computation Using

Data from Fiqure 7.

10
In Core : IMXi IK**

(Search Prmt) (File Print)

Mmuiiae Arrays Ordered on y

FLOW CHART I M HO (Matcher)

Key io Arrays : Aim Aim Aidn

x y e

mxd-iMx,

23. 2=2

33

Parameters: LG LS K9 KR KH9 KHR KRZ

2 -I

3

S = 1

YAB=Ai2l +LS

X5L zMl - LS

I- 2 + 1 nr j^JMKJAIK-SA1K+ I I 6.1- \

mxB-wxz

J 2i t< ^.3 i< 6.z y

>-,!/ J-

^*-/ ?-2- J7ZP <r V

2V. > ;=/ ;=

?=f +/

25: ^- I

->

31.

TR^IvXi -DXjl-r iDyj -3>yjl

re =lv&i -i>ej\

j=j + /

^M

<: Z±

^~

J

j ijm)

i\

32. 1< 1< jo. 36. I

3V. t

35:

c si y^

36. y

/?5--KRR*R

JMKb

/es=o

jf\Te: KHe

2i. y

g& I

D

77?: /C/?

27. Z-K-rKR-TR

29J I

i

K 73j*D

29.2 V

Ay =Ah, -Ajzz

AX-Aiu -Ay/2

^r LS

JL ¥

AQ=Ai3 i -Ajsz

12. y

(lAOh LP)

13.

46> -A6+3&0

15. A6 = A6 -3GO

^

1?=R1-K0-TO

ii- S-S-hl

It. \f DXS = AX

Vys =Ay

D0S = A6

ll


U.S. DEPT. OF COMM. BIBLIOGRAPHIC DATA

SHEET

1. PUBLICATION OR REPORT NO.

NfiS TN-878

2. Gov't Accession

No.

4. TITLE AND SUBTITLE

The M40 Fingerprint Matcher

3. Recipient's Accession No.

5. Publication Date July 1975

6. Performing Organization Code

7. AUTHOR(S)

J. H. Weqstein

8. Performing Organ. Report No.

9. PERFORMING ORGANIZATION NAME AND ADDRESS

NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

10. Project/Task/Work Unit No. 600 4400

11. Contract/Grant No.

12. Sponsoring Organization Name and Complete Address (Street, City, State, ZIP)

Federal Bureau of Investigation

Washington, D. C. 20535

13. Type of Report & Period Covered

14. Sponsoring Agency Code

15. SUPPLEMENTARY NOTES

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

bibliography or literature survey, mention it here.)

A procedure is described for automatically 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 the 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 impressions to the other.

17. KEY WORDS (six to twelve entries; alphabetical order; capitalize only the first letter of the first key word unless a proper name; separated by semicolons)

Computerized fingerprint identification, fingerprint, pattern recognition

18. AVAILABILITY [Xj Unlimited

|H For Official Distribution. Do Not Release to NTIS

|x ^ Order From Sup. of Doc, U.S. Government Printing Office Washington, D.C. 20402, SD Cat. No. C13. 46:878

_] Order From National Technical Information Service (NTIS)

Springfield, Virginia 22151

19. SECURITY CLASS

(THIS REPORT)

UNCLASSIFIED

20. SECURITY CLASS

(THIS PAGE)

UNCLASSIFIED

21. NO. OF PAGES

14

22. Price 65 cents

USCOMM-DC 29042-P"
NBS TECHNICAL PUBLICATIONS

PERIODICALS JOURNAL OF RESEARCH reports National Bureau

of Standards research and development in physics,

mathematics, and chemistry. It is published in two sections, available separately:

• Physics and Chemistry (Section A)

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, $17.00; Foreign,

$21.25.

• Mathematical Sciences (Section B)

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, $9.00; Foreign, $11.25. DIMENSIONS/NBS (formerly Technical News Bulletin) —This monthly magazine is published to inform

scientists, engineers, businessmen, industry, teachers,

students, and consumers of the latest advances in science and technology, with primary emphasis on the work at NBS. The magazine highlights and reviews such

issues as energy research, fire protection, building tech- nology, 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, $9.45; Foreign, $11.85.

NONPERIODICALS

Monographs—Major contributions to the technical liter- ature 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 interested industries, professional

organizations, and regulatory bodies.

Special Publications—Include proceedings of confer- ences 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 world-wide

program coordinated by NBS. Program under authority

of National Standard Data Act (Public Law 90-396). NOTE: At present the principal publication outlet for these 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 (AIP). Subscriptions, reprints, and supplements available from ACS, 1155 Sixteenth

St. N. W., Wash. D. C. 20056.

Building Science Series—Disseminates technical infor- mation 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 pro- cedures published by the Department of Commerce in Part 10, Title 15, of the Code of Federal Regulations.

The purpose of the standards is to establish nationally

recognized requirements for products, and to provide

all concerned interests with a basis for common under- standing of the characteristics of the products. NBS

administers this program as a supplement to the activities of the private sector standardizing organizations.

Federal Information Processing Standards Publications (FIPS PUBS) —Publications in this series collectively constitute the Federal Information Processing Standards Register. Register serves as the official source of information in the Federal Government regarding stand- ards 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 11, 1973) and Part 6 of Title 15 CFR (Code of Federal

Regulations). Consumer Information Series—Practical information, based on NBS research and experience, covering areas

of interest to the consumer. Easily understandable language and illustrations provide useful background

knowledge for shopping in today's technological

marketplace.

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 distribution is handled by the sponsor; public distribution is by the National Technical Information Service (Springfield, Va. 22161) in paper

copy or microfiche form.

Order NBS publications (except NBSIR's and Biblio- graphic Subscription Services) from: Superintendent of Documents, Government Printing Office, Washington,

D.C. 20402. BIBLIOGRAPHIC SUBSCRIPTION SERVICES

The following current-awareness and literature-survey

bibliographies are issued periodically by the Bureau:

Cryogenic Data Center Current Awareness Service A literature survey issued biweekly. Annual subscription: Domestic, $20.00; foreign, $25.00.

Liquefied Natural Gas. A literature survey issued quarterly. Annual subscription: $20.00. Superconducting Devices and Materials. A literature

survey issued quarterly. Annual subscription: $20.00. Send subscription orders and remittances for the pre- ceding bibliographic services to National Technical Information Service, Springfield, Va. 22161.

Electromagnetic Metrology Current Awareness Service Issued monthly. Annual subscription: $100.00 (Special rates for multi-subscriptions). Send subscription order and remittance to Electromagnetics Division, National Bureau of Standards, Boulder, Colo. 80302.
U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

Washington. D.C. 20234

OFFICIAL BUSINESS

Penalty for Private Use. $300

POSTAGE AND FEES PAID

U.S. DEPARTMENT OF COMMERCE COM-21 5

SPECIAL FOURTH-CLASS RATE BOOK

U.S.I

^e-igi6