TECHNICAL NOTE

KSSSKiSsSBSSSSSsa 443

A Computer Oriented

Single-Fingerprint

Identification System

til

J*

CUT OF

Q

^\

%

Q

^CAU <* ^

U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

It
THE NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards1 provides measurement and technical information services

essential to the efficiency and effectiveness of the work of the Nation's scientists and engineers. The

Bureau serves also as a focal point in the Federal Government for assuring maximum application of

the physical and engineering sciences to the advancement of technology in industry and commerce. To

accomplish this mission, the Bureau is organized into three institutes covering broad program areas of

research and services: THE INSTITUTE FOR BASIC STANDARDS . . . provides the central basis within the United

States for a complete and consistent system of physical measurements, coordinates that system with the 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. This

Institute comprises a series of divisions, each serving a classical subject matter area: —Applied Mathematics—Electricity—Metrology—Mechanics—Heat—Atomic Physics—Physical

Chemistry—Radiation Physics—Laboratory Astrophysics2—Radio Standards Laboratory,2 which

includes Radio Standards Physics and Radio Standards Engineering—Office of Standard Refer- ence Data. THE INSTITUTE FOR MATERIALS RESEARCH . . . conducts materials research and provides

associated materials services including mainly reference materials and data on the properties of materials. Beyond its direct interest to the Nation's scientists and engineers, this Institute yields services which are essential to the advancement of technology in industry and commerce. This Institute is or- ganized primarily by technical fields: —Analytical Chemistry—Metallurgy—Reactor Radiations—Polymers—Inorganic Materials—Cryogenics2—Office of Standard Reference Materials.

THE INSTITUTE FOR APPLIED TECHNOLOGY . . . provides technical services to promote the use of available technology and to facilitate technological innovation in industry and government. The

principal elements of this Institute are: —Building Research—Electronic Instrumentation—Technical Analysis—Center for Computer Sci- ences and Technology—Textile and Apparel Technology Center—Office of Weights and Measures —Office of Engineering Standards Services—Office of Invention and Innovation—Office of Vehicle

Systems Research—Clearinghouse for Federal Scientific and Technical Information3—Materials

Evaluation Laboratory—NBS/GSA Testing Laboratory.

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

20234.

2 Located at Boulder, Colorado, 80302.

3 Located at 5285 Port Royal Road, Springfield, Virginia 22151.
UNITED STATES DEPARTMENT OF COMMERCE

Alexander B. Trowbridge, Secretary

NATIONAL BUREAU OF STANDARDS • A. V. Astin, Director

NBS TECHNICAL NOTE 443

ISSUED MARCH 1968

A Computer Oriented

Single-Fingerprint

Identification System

J. H. Wegstein

Center for Computer Sciences and Technology

Institute for Applied Technolgy

National Bureau of Standards

Washington, D.C. 20234

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, Government Printing Office

Washington, D.C, 20402 - Price 25 cents

A Computer Oriented Single-Fingerprint

Identification System

by J.H. Wegstein

A procedure is described for computing a set

of numerical descriptors that identify a single

fingerprint. The procedure starts with the X and

Y coordinates and the individual directions of the

minutiae (ridge endings and bifurcations) of a fingerprint impression. Sets of descriptors are computed corresponding to groups or constellations

of these minutiae. Descriptors corresponding to

various fingerprint impressions are stored on magnetic tape A fragment of a fingerprint impression

such as occurs in a latent fingerprint may also be

used.

A second computer program reads the descriptors corresponding to two different fingerprint

impressions from magnetic tape. A score is computed

that indicates how well the two impressions match.

Preliminary experimental results suggest that this

procedure might be suitable as a basis for a singlefingerprint classification system.

Key words: Classification, computer, descriptor,

file, fingerprint, identification,

pat tern- recognition.

lo Introduction

In all of the fingerprints ever studied, no two impressions from

different fingers have ever been found to be identical in minute detail.

Furthermore, the minute details or minutiae of a fingerprint never change

throughout the normal life of a finger. Accordingly, the single fingerprint invites increased attention as a means for human identification

where tools such as the electronic digital computer are available to

handle the information that can be related to the fingerprint impression.

Numerous schemes exist whereby a classification or set of descriptive symbols is developed which describe the fingerprints of a particular

individual. The classification is usually kept on the same standard

eight inch square card with the ten fingerprints of an individual, and a collection of these cards can be ordered and filed according to the

classification. Then, starting with the fingerprints of an unknown

person, a classification can be made and the file can be searched for a matching classification. Several identical classifications may be found

in the file and a comparison of the fingerprints is then required to

uniquely identify the individual.
The Henry Classification System ' with modern extensions is widely

used for large fingerprint collections. It takes account of the

different patterns (arch, loop, whorl) and also depends on ridge counts

between the core and delta of loops and whorls. The Henry system

utilizes information from all ten fingers and consequently, a file cannot

be searched for a single fingerprint. The Henry system also requires

the classifier to recognize readily the basic patterns as well as cores and deltas. These recognition problems are serious obstacles in any

effort to automate the Henry system.

The search for a suitable method for automatically scanning and

classifying fingerprints has led to another aspect of fingerprint work:

identification. Two fingerprints can be shown to belong to the same finger by comparing a few minutiae such as ridge endings, bifurcations

or forks in ridges, incipient ridges, islands, and enclosures. Authorities generally regard the demonstration of 12 correspondences of

minutiae (and of course no discordances) as proof that two prints

originate from the same finger,, • While the minutiae are distributed

throughout the fingerprint, an identification can be made using the

minutiae from any portion of the print. Thus a classification system

using minutiae might even be used in searching for fingerprints corre- sponding to chance prints or latent prints where only a portion of the

fingerprint is available. This paper describes a fingerprint identification system based on only two types of minutiae: ridge endings and

bifurcations . There are about 93 such minutiae in the fingerprint

shown in Figure 1. Four of these are labeled,,

In the work reported in this paper the minutiae data are read

manually. A set of descriptors is then computed and stored along with

a label identifying the fingerprint on magnetic tape as shown in

Figure 2. (A magnetic disc, drum, or other mass storage device could of course be substituted for the magnetic tape.)

After several sets of descriptors have been stored in the file, the

file may be searched for a particular set of descriptors. The crux of

the searching procedure is a matching program and Figure 2 illustrates

the set-up used for experimenting with the matching program which is

also described in this paper. An operator types in the identifying

labels of two fingerprints that are known to be in the file. The matcher

then reads the corresponding sets of descriptors from the file and

computes a score, ST, which indicates how well the two sets match. The

descriptors of a fingerprint can thus be compared with the descriptors

of another fingerprint from the same or from a different finger. This

paper does not deal with the problem of classifying and ordering the

descriptors in the file for the purpose of minimizing search time
2. Taking Minutia Data

Since a ridge ending in one fingerprint may appear as a bifurcation

in another fingerprint from the same finger, no distinction is made

between ridge endings and bifurcations in recording data. For each of

these minutiae both a location and direction are defined as shown in

Figure 3. If the areas marked B are considered as ridges, then point P

is the location of a ridge ending and the line GP defines the direction

of this minutia. If the areas marked A are considered as ridges, then

point P is the location of a bifurcation, and the line GP defines the

direction associated with this minutia. Hopefully, an automatic scanning

device will soon be available which can scan a fingerprint and record the

coordinates and directions of all of its minutiae.

In the work reported here, each fingerprint impression is photographed and enlarged by a factor of 10. The minutiae on each of these

enlargements are then marked with a pencil on a piece of transparent

plastic laid over the enlargement. Figure 4 shows the minutiae from an impression hereafter identified as II-W-1. Figure 5 shows minutiae from

impression II-W-2 shown in Figure 1. Both impressions are from the same finger but were taken about two months apart. Each minutia is numbered

for convenience in studying the identification system, but in an operating system the numbering is unnecessary.

Each transparency is next taped to a drawing board so that all

minutiae markings fall in the first quadrant of an X-Y coordinate system

as shown in Figure 6. The exact position is not critical. The X and Y

coordinates of each minutia are then read in millimeters and recorded.

The angle Q which the minutia direction makes with the X axis is recorded

in degrees. Figure 7 shows a portion of this minutia data which is used

for demonstrating this identification system.. This is similar to the

situation that would exist if only a part of the pattern were available

in a latent fingerprint for searching against a fingerprint file. Note

that the core and delta data are not needed in this system.

3. Computation of Descriptors

The complete logical details of the computer program for computing

the descriptors that describe the impression are given in Flow Charts 1 through 5. A block diagram of the various steps is given in Figure 8.

The computer first reads in the identification and minutiae data for an impression such as that for impression II-W-1 shown in the left half

of Figure 7»
3.1 Constellation Generator

As detailed in Flow Chart 1, each minutia point is taken as a focal

point for a constellation of neighboring points. All points which are within a distance d of the focal point are considered for inclusion in

the constellation. Each of those points is actually included in the

constellation provided that its non-directed minutia angle (0 or 9- 180)

differs by less than OL degrees from the non-directed minutia angle

(9 or 0-180) of the focal point . Next, each point that is now in the

constellation is in turn considered as a focal point and all data points

are examined according to the above criteria to see if they too should

be added to the constellation. However, all angles are compared to the

minutia angle of the original focal point. As a result of the above

procedure, minutia point 2 serves as a focal point for a constellation

that includes points 2, 4, 5, and 8 as shown in Column E, in the left

half of Figure 9. This constellation will hereafter be referred to as "constellation 2" in impression II-W- 1 because it was formed about

minutia 2 as a focal point. Constellations which do not include at

least W minutiae points are rejected. Currently, W=4, d=20mm, and

a=12°

3.2 Constellation Selector

Since each minutia point takes its turn as a focal point trying to

form a constellation, there will be some duplication of constellations.

Accordingly, Flow Chart 2 details a procedure whereby any constellation

that is equal to or included in another constellation is rejected. At

the conclusion of the constellation generation and selection (Connector

IV in Flow Chart 2), the data for impression II-W-1 in Figure 7 yields

the four constellations shown at the left of Figure 9. Figure 9 also

shows the two constellations that are generated from the data in Figure 7 for impression II-W- 2.

3.3' Coordinate Transformer

Each constellation next undergoes a coordinate transformation. The

center of gravity of the constellation is determined by computing the

average value of the X and the average value of the Y coordinates. The

coordinates X' and Y' of each point relative to this center of gravity

are then computed as detailed in Flow Chart 3. The new coordinates for

constellation 2 consisting of points 2, 4, 5, and 8 in impression II-W-1

are shown in Figure 10. Figure 10 also gives values for Z which is the

direction of a minutia relative to the X axis, Z=l means that the

minutia points upward and Z=0 means that the minutia points downward.

Z is readily determined from as shown in boxes 53 and 54 of Flow

Chart 3, Figure 10 also gives the non-directed angle (3 of each minutia.

If < 180 then 3=0. If 9 > 180 then £=0-180.
In the final step of the transformation, the coordinate axes are rotated so that the angle between the^axis and the initial X axis is

equal to the average value of the angle p. In effect the ^axis of the new coordinate system is aligned with the constellation. The coordinates

of the minutiae in constellation 2 relative to this ^-^ coordinate system

are shown in Figure 11.

3.4 Descriptor Generator

If the minutiae in constellation 2 are arranged in order according

to the values of *X a ^d *4 in Figure 11, they can be exhibited on a grid

as shown in Figure 12. The value of Z determines whether a minutia

points up or down. The constellation is now in a measure- independent

form. By comparing Figure 12 with the same minutiae in Figure 4 it will

be seen that the minutiae have retained their positions and up-or-down

directions relative to each other but distances between points and

variations in the angles between minutiae have become irrelevant.

The descriptor d. u. -d^u -d-u^-d^u.. for constellation 2 is

4- 4- j 3 Z Z 11 10-01-12-03. This can be determined by inspecting Figure 12 as follows:

d is the direction of the corresponding minutia and is equal to Z for

this minutia. The value of u for each minutia is read from the scale

along the Y axis. For example d=l for minutia point 4 because 4 point

upward and u=2 as read from the Y scale. The detailed procedure for

this computation of descriptors is given in Flow Chart 4.

3.5 Descriptor Compression

It may be desirable to compress the information in a descriptor

into a binary integer for the purpose of minimizing the amount of storage

space that will be required in the file. One method for compressing a descriptor is illustrated in Figure 13. The right-most five bits contain

the integer N, where N is the number of minutiae in the constellation.

The next N bits to the left give the values of d>7 , d„ n

, , d. . The

N N-J- rest of the bits to the left represent the integer A whose derivation is

described below.

Since the integers u , u , , w are a string of permuted

numbers, there are N.1 permutations of these numbers. Accordingly, each

permutation can be identified with an integer A between and N.'-l

inclusive. For example, if N=4, each string of u's can be related to a value of A as follows:
U

4

U

3

U

2 U

1 12 3

13 2 1 2 13 2

3 2 1 22

3 2 10 23

Flow Chart 5 gives a detailed procedure for computing the value of A

corresponding to any given string of u's. This procedure, from the art

of orderly listing permutations , is based on the lexicographical method

of D.H. Lehmer„3 # The total number of bits in the compressed descriptor

is a function of N and this information may be utilized in packing the

descriptors into the file. In the design of an automated fingerprint

system the time needed for computing the compression and expansion of a descriptor must be weighed against the amount of file space that will be

saved.

The four descriptors for impression II-W- 1 and the two descriptors

for impression II-W-2, shown in Figure 14, result from the data shown in

Figure 7. The compressed forms of these descriptors are shown as octal

integers for convenience. The impression identification name (Ident)

II-W-1 and its set of four descriptors are now written in the electronic

file as shown in Figure 2. A similar procedure is carried out for

impression II-W-2 and, of course, the descriptors for other fingerprint

impressions may also be placed in the file. In a practical application

of this system it would be undesirable to store the identifying name

(Ident) in the file. Instead the filing computer might supply a number

to the fingerprint reader which is a unique function of the location in

the file where the fingerprint descriptor is stored. This number would

be written on the fingerprint card and would become the serial number

which determines where the fingerprint card is filed.

4. Matching Fingerprint Descriptors

The matcher shown at the right in Figure 2 is used for studying the

effectiveness of the descriptor design. Descriptor sets for two different fingerprint impressions in the file, named IdentA and IdentB, are read from the file and compared. A score ST is printed by the computer

indicating how well the descriptors match. The impressions being

compared may be from the same or different fingers and, of course, the score ST should be high if the impressions are from the same finger and

low if the impressions are from different fingers. Various parameters

in the descriptor generator such as d=distance between minutiae, a=angle

between minutiae directions, and W=minimum number of minutiae required

to form a constellation can be varied while the resulting score ST is

observed. The next section describes one of several experimental methods

for matching descriptors.
4.1 Descriptor Expansion and Elaboration

An operator typing in two identifying impression names such as II-W-1 and II-W-2 will cause the computer to retrieve the set of com- pressed descriptors corresponding to each of these impressions. Each

compressed descriptor is then expanded into its original form by the

inverse of the procedure illustrated in Figure 13. The permuted numbers

are generated from the integer A by the procedure detailed in Flow

Chart 6.

Assume now that the computer contains the two sets of descriptors

shown in Figure 14. The computer will next proceed to compare each

descriptor of impression II-W-1 with each descriptor of impression II-W-2

and accumulate a score ST as it proceeds. The comparison of the descriptor for constellation 41 in impression II-W-1 with constellation 41 in

impression II-W-2 will be used in explaining the procedure. The pictographs for these constellations are shown in Figure 15. The minutiae

are compared from right- to- left . They are also compared from top-tobottom, and to facilitate the latter comparison, a second descriptor is

computed for each constellation. If a pictograph in Figure 15 is rotated

90° clockwise, the new descriptor e. v. e^v^e_v„e n v., is derived in the same way that was described earlier in this paper in the section labeled

Descriptor Generator. However, now each direction bit e=l if the

minutiae points to the right and e=0 if the minutia points to the left.

The resulting descriptors are shown at the right of each pictograph in

Figure 15 and the details of their computation are given in Boxes 6, 7,

and 8 in Flow Chart 7.

The minutiae in each pair of constellations such as those shown in

Figure 15 are next compared three at-a-time working from right- to- left

and also from top- to-bottom. The method for accomplishing this is

illustrated by grouping the minutiae in 3x3 pictographs working from

left- to-right . This is illustrated in Figure 16 for constellation 41 of

impression II-W-1. The direction bits are converted to octal equivalents

(reading backward) and the permutations are converted- to their orderedlist equivalents as described earlier in the section on Descriptor

Compression., For convenience in hand calculation, the following conver- sion table can be used.

Permutation a 210

120 1 201 2 021 3 102 4

012 5
The details for computing the horizontal triads a„ _ b T _ a n b, from N-2 N-2 11

the descriptor d u ^i u i anc^ *-he vertical triads f _ g f g , from the rotated descriptor e „v e.v n are given in Boxes 9-23 in

N N 11 Flow Chart 7. The results for the illustrative example are given in

Figure 17.

4o2 Triad Matching

For each pair of constellations being matched, each ab triad in the

first constellation is compared with each ab triad in the second constellation. When two of these triads are found to be equal, a score S is

set equal to 1 and the next successive triads from the constellations are compared. If these are found to be equal the score is increased by 1. This procedure is repeated until either string of triads is exhausted.

The score S resulting from this run of matches is compared with the score resulting from any other run of matches that may occur for the same pair

of ab strings. The largest of these scores is designated Si. Matching

the two ab strings in Figure 17 results in only one run and the final score is Sl=3. The details for this computation are given in Flow

Chart 8.

The two fg strings from the same pair of constellations are next

matched as described above. The score for the example in Figure 17 is

S2=2. The total score for the constellation match is SS=Sl+S2, and

SS=5 in the example. Any score SS that is equal to or greater than a threshold score SL is retained and all others are rejected. In a practical application of this identification system the parameter SL

might be set low when searching for latent fingerprints and be set

higher when searching for regular fingerprints.

The total score ST resulting from matching two impressions is equal

to the sum of all SS scores resulting from matching the various pairs of

constellations from the two impressions „ The scores resulting from

matching the two impression fragments whose minutiae data is given in

Figure 7 are shown in Figure 18. The total score, ST=8, includes two

legitimate constellation matches (41-41 and 40-41) producing a total

score of 6 and a false match (40-2) producing a score of 2. False

matches produce a certain amount of "noise" in the score and it may be

desirable to reduce this noise by filtering.
5. Conclusions

Complete sets of descriptors have been computed for a few fingerprint impressions from the same and different fingers. The parameters

used were d=20mm, a=12°, and W=4„ When the descriptors for two impressions from different fingers were compared, the score SS resulting from

comparing pairs of constellations was found to occasionally have values

of 1, 2, or 3 but seldom more than 3. Most of these scores, indicating

false matches or noise, were therefore eliminated from the accumulated

score ST by setting the parameter SL=4 in the matcher program. Then a further improvement in scoring was found by defining a new score SK equal

to the score ST with SL=4 divided by the score ST with SL=1. The SK scores resulting from comparing various pairs of impressions from the same finger were found to be generally higher than SK scores resulting

from comparing the impressions from different fingers.

Based on the limited amount of fingerprint data processed to date,

the procedure described in this paper offers promise as a basis for a single- fingerprint classification system,, Many more fingerprint impressions must be processed, and optimum values must be found for the various

parameters corresponding to the characteristics of the minutia reader

used, Also, a method of ordering the descriptor sets is needed so that

fingerprints can be classified and filed in a manner that will minimize

search time. It may be possible to further reduce the amount of information filed in the descriptors and further improvement may be possible

in the matcher. For example, matching quads instead of triads may offer some advantage. Finally, the computer time required for matching must

be reduced to the lowest possible value.

References

lo The Science of Fingerprints , U.S. Government

Printing Office, 1963

2. Cummins, H. and Midlo, C. , Finger Prints, Palms

and Soles , Dover Publications, Inc., New York,

1961, p. 155

3o Beckenbach, E.F. (ed) , Applied Combinatorial

Mathematics , John Wiley and Sons, New York,

1964, p. 20

The author is indebted to the Identification Division of the

Federal Bureau of Investigation for its assistance in the preparation

of this paper. The author is particularly indebted to Mr» J.F. Rafferty

of the National Bureau of Standards who wrote the computer programs

specified by the Flow Charts in this paper and who computed the results

given here using the NBS Research Computer Facility.

9
Figure 1 -- Fingerprint Impression II-W-2

10
Read

Minutiae

Data

for

Single

Fingerprint

Impression

Read

IdentA

IdentB

Match

Descriptors

for

IdentA and IdentB

Fingerprint

Impressions

h

Print

IdentA

IdentB

Score ST

Electronic File

for

Descriptors

Figure 2 — Computerized system for experimentally identifying

fingerprints

11
-- Location and

direction of a minutia.

12
Figure k -- Minutiae from impression II-W-1

13
Figure 5 -- Minutiae from impression II-W-2

14
Data Recorded

Point

Number

X

in

ram.

Y

in

mm.

e

in

degrees

Figure 6 — Method used for

recording minutiae

data

Area included

in impression

Fingerprint

Impression

II-W-1

Fingerprint

Impression

II-W-2

Y 6

2 203 221 293

3 221 200 101

h 200 210 110

5 185 201 291; 6 216 188 290

7 203 186 111

8 183 195 112

9 161 191* 301

22 183 11*8 101* 23 17k 127 287

1*0 11*2 117 87

1*1 157 125 95

1*2 163 111 101*

1*3 215 115 298

1*1* 151* 103 91

61 155 088 89

63 152 080 75

S3 051 01*1* 213

88 078 01*3 202

89 066 01*1 209

90 01*2 033 211* 92 01*3 022 30

P_ X Y ©

2 199 208 290

3 216 190 110

1* 200 197 111

5 185 196 287

6 213 179 291

7 197 181 109

8 182 192 107

23 173 129 293

1*0 11*3 118 9h

1*1 156 128 102

1*2 161* 116 110

1*1* 156 106 102

61 156 091 98

Figure 7 — A portion of minutiae

data used for demonstrating

descriptor generation and

matching

15
Read

Ident and

Fingerprint data

I

Generate Constellations

See Flow Chart 1

Select Constellations

See Flow Chart 2

Transform Coordinates

See Flow Chart 3

i

Generate Descriptors

See Flow Chart h

Compress Descriptors

See Flow Chart 5

Write Descriptors in File

Figure 8 —

Computation of

Descriptors

Fingerprint Fingerprint

Impression Impression

II-W-1 II-W-2

K,12El IL E, e! e*„ 3 li 1 2 2 hi UO ^3 2 23

h 23 Ul 89 it 111 $ ho hh 90 $ U2

8 U2 61 88 3 IiO Ui 63 92 7 Ui

61 8 61

6

Figure 9 — Constellations Selected

16
Impression II-W-1

Constellation 2

p I' Y' Z /3

2 10.25 111. 25 113

h 7.25 3-25 1 110

$ -7.75 -5-75 111* 8 -9.75 -11.75 1 112

Figure 10 — Minutiae, coordinates, and directions relative

to coordinate axes at constellation's center of

gravity

Impression II-W-1

Constellation 2

P 2> ¥ *

2 1U. 88 930 ~

it 7.9k .26 1

5 -9.36 -2.38

8 -13. kl -1.11 1

Figure 11 — Minutiae coordinates

relative to rotated axes

17
Impression II-W-1

Constellation 2

I

2

T<

1*

I

8 10-01-12-03

Vu~ d

3 u3

- d

2

u

2

- d

iu

i

Figure 12 — Measure-independent constellation and

resultant descriptor

Impression II-W-1

Constellation 2

10-01-12-03 Descriptor

Permutted

numbers

u.uuu =0123

h 3 2 1

convert to

integer A =

N = h Number of minutiae

in constellation.

Binary number as stored in file bycomputer.

Octal equivalent.

Figure 13 -- Compression of descriptor for

storage in electronic file

18
Impression II-W-1

Constellation

Minutiae in

Constellation

2 8,5^,2

ill l|0,6l,IUi,la,ii2,23

Ho hO, 63,kh,6l,hl

S3 53,88,89,90,92

Descripto r

10-01-12-03

13-10-11-1U-12-05

13-10-12-11-Ui

02-01-03-0ii-10

Octal Form of

Compressed

Descriptor

5ol4

2653706

22S1US

1620J45

2

ill

Impression II-W-2

&>5,7,k,2,6,3 114-05-11-13-06-00-12

li0,6l,liU,J4l,ii2,23 13-10-11-15 -12 -Oli

65105^7

2663706

Figure H4. — Descriptors corresponding to fingerprint

shown in Figure 7

Impression II-W-1

Constellation Ul

[23

Tta

Juo

Tte

fuu

1 6!

o

o

I CVJ H

I H

I >

I QJ H

H

I on

13—10—11—1U—12—05

du

Impression H-W-2

Constellation Ul

lu

1,3

|uo

!-*

!u

T&

13—10—11—15—12—0^

du

OJH

O

H

H

I m

Figure 15 — Pictographs of the same constellation

from two different fingerprint impressions

19
UO 6l kh 6l hk kl kk kl 1)2 Ul k2 23

T T r

a

b

T

T

T

T

T

T

2 7

%\

1 T

T

a

3

b

3 o o

Minutiae

Directions

Permutations

Triads

Figure 16 — Derivation of horizontal triads for constellation kl

in fingerprint impression II-W-1

Impression II-W-1

Constellation kl

Impression II-W-2

Constellation kl

Horizontal Vertical Horizontal Vertical

Descriptors

du

13-10-11-1U-12-05

ev lU-13-11-15-12-00

du

13 -10 -11 -15 -12 -Ok ev lU-13-11-15-00-12

Triads

at

27-57-37-^3 07-^7-37-03

ab

27-57-37-23

fg

07-^7-13-25

Figure 17 — Descriptor and triad data for illustrative example

Impression ii--W-l Impression II-W-2

Score for

Constellations

Constellation Con:stellation SI S2 SS

Ui ill 3 2 5

ao 2 2 2

uo ill

Total Score

1 1

ST = 8

Figure 18 — Score resulting from matching Impression II-W-1

with Impression II-W-2

20
101

lead.

Tdenf hM

Table fi Xi yt et

A V

Jikra meters

d, o<

) <£ ; k/

i

100. Prmt

Jdeni

Cj = /i

zl

1=1

f-Ct

I. V

Is 7, Wj

C ggjg )^to-/tol:oty±(l6>J>-3iol:<K ^

/y. t g- „ ^g -SF K

ftp =/*f - 9n\ r\(yi ->J V fa -x^f ; j

/zx=/

36. f^

stL~s4L+l

11— ' ««sr

/T- I

2/. 23.

i

'. nM t'-J

L

MtV

I ~l+l

zz. y

** c°~j

it.

K Tjjl )^@

t=t-h/

>

<D

/ lOW L tlCirJ I. Constellation Generaior

21
YOJ>.

¥0F

L-m-/ *-m

Hue. ml

hfi -m+i

^£-i\^Cm7jT)

\f 93 A.

Hf. Q^\&K^'<& >

r~%.

u

ft.

i

ft*j?-hi

E^C

H3-

YoA.

<ED

Z7

25.

( ^£ )

Fl0WCfiarf Z. Constellation Selecto*

22
Si

so, r

5%

9t : no

i -cj

W

S3 I

SfL

Zj=o

f3j =&i-/tO

& 5S\I SC

co. *e j *J+I

li j^l 5X~~0

fSH=o Sy=o

t3L = l$0

5$.

(3L ~fy

5?. lh^7iD<a

A *Pl)

>

P» -ft

loi. ^

tor-H*:

HI

C=£j

H7^

LI. £3 V

r=2

T£ tv

r=/

fij =a+iio

1

i

ii

y-=/

7Z.

£7

A

£>6. -* Xy = ^ -/U '=V

(ft Id)=—

>

7<J>. " a f Sfi=Sp-r/3j

J -V +

1

1L

<=r

73. ^~

>

7V. r^-*

75, t

/3^/0 -vr*

76. ?~/3-fo

a. \f

71

j = l n

to.

Xy ~XJ Cs$ tyj Sin?

j^j + i

7t T

I lOW Chart J>. Coordinate. Transformer

23
y( J

•• c*

)

5^ = _ /^0

X>t=At& Ut

MJL

yyj - Ay

Vritt

lot. CJTy

f03.

jf*Jt+l

y /n.

[/[/rite Xdenf £__ <D

Floy Chart 4

2>escripfor G-enera.for

24
Given > /V, U„, U*.,,---,u,

\t) Computes : A

I. M

GET J~J"I

7- V I

l'-3

%

>

> l^i-i

'£-

to. J

I

K-K*j

II. \1 1%. j: N J^j-f-l

V

©

I.

Gxiven ; A{ A

Computes : U*, Un-,,-" Oi,

¥. h

<: ( z:/y)* 1=1 + /

5. f

£*0

z^

l-l-l

4i ? <;. y

» ( ft:/t JA Hi't

I

7 1'-

A^A-Ki

ii. f

= i + i i3±

V

2 = /

/v. V

6(f> : ut

1£_ Y

#i^= Ui-f-l

y

a

lt>.

It <

ft N

i :f

i-= i + v

Flow Chart 5.

Com pressor

Flow Charf G.

Expander

25
/. V

Read (Type)

Ide»tA IdentB

5L

Tdent = IdentB

3.Read

Tdenf £

& Ex -£*

* i

%%.Array F = Army E

Ue»i = UentA

J-l

* i

27.

1 = /

6- ]>_

JL*I+i

v=

^5;

Z = Ce ^=C

V Ji 7 V

4^ = 1

_^L

/I

£

<r

>

i- )—

f

E.I EX £M £JZ

&iX ~diUi Hi h{ elATt fj

<ft Ef^Ej&C

*

{oil} (*•

i

1=/ tf,te =C

/o.

a3.

i = i+-/

7%. Q =^«i ^iAjPi -6i &-dj+, t dj +

.

Di ^eiATL

11. )'

til T> 70. Qjtiju^jp*

a

III l Lli-i-i n- u

#i-l

U-i-hi * Ui+z

II.

/?.

Ui ' Uirt CLi=1

a )i 15. ^ *,- = ?

/^.#£ ^5"

FlowCharf 7. Triad General

26

or
njt

5T=0

30 \l £-1

3/ \'

SI.

53. f

5T-5T+SS

ttl=\

^

£T ^^

m i h J

Print

J?,M,S),S2 } SS

SI 3Z

55: 5L

w

SO.

FloivCharf I Matcher

~( Q:^ )

^

27

NBS TECHNICAL PUBLICATIONS

PERIODICALS

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, 35.00; foreign, 36.00*.

• 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,

32.25; foreign, 32.75*.

• 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, 32.75; foreign, 33.50*.

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,

research managers, product-development managers, and

company executives. Annual subscription: Domestic,

31.50; foreign, 32.25*.

•Difference in price is due to extra cost of foreign mailing.

N0NPERI0DICALS

Applied Mathematics Series.

tables, manuals, and studies. Mathematical

Building Science Series. Research results, test methods, and performance criteria of building materials, components, systems, and structures. Handbooks. Recommended codes of engineering

and industrial practice (including safety codes) developed 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 quantitative 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 in- dustry 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. CLEARINGHOUSE

The Clearinghouse for Federal Scientific and

Technical Information, operated by NBS, supplies

unclassified information related to Governmentgenerated 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

Order NBS publications from:

Superintendent of Documents

Government Printing Office Washington, D.C. 20402
U.S. DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20230

POSTAGE AND FEES PAID

U.S. DEPARTMENT OF COMMERCE

OFFICIAL BUSINESS