MTED STATES kRTMENT OF MMERCE

JLICATION O

*NrtsO» ^

V

NBS TECHNICAL NOTE 712

17510Z -Q*{ oct i4 1975 QC\00

U.S.

Um/IENT

OF

MMERCE

Natl -rt,

>tand

,L

/<90

.U5-75T7

Wo. nix

/?7^

Manual and

Computerized Footprint

Identification
NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards1 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: (1) a basis for the Nation's physical measure- ment 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 Center 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—Heat—Mechanics—Optical Physics—Linac

Radiation2—Nuclear Radiation2—Applied Radiation2—Quantum Electronics3—

Electromagnetics3—Time and Frequency3—Laboratory Astrophysics3—Cryogenics3

. THE INSTITUTE FOR MATERIALS RESEARCH conducts materials research lead- ing 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 pro- mote 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 also monitors NBS engineering standards activities and

provides liaison between NBS and national and international engineering standards

bodies. The Institute consists of the following divisions and offices: Engineering Standards Services—Weights and Measures—Invention and

Innovation—Product Evaluation Technology—Building Research—Electronic Technology—Technical Analysis—Measurement Engineering—Office of Fire Programs.

THE CENTER FOR COMPUTER SCIENCES AND TECHNOLOGY conducts re- search and provides technical services designed to aid Government agencies in improving cost effectiveness 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 Center

consists of the following offices and divisions: Information Processing Standards—Computer Information—Computer Services —Systems Development—Information Processing 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,

and directs the public information activities of the Bureau. The Office consists of the following organizational units: Office of Standard Reference Data—Office of Technical Information and

Publications—Library—Office of International Relations.

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

2 Part of the Center for Radiation Research.

3 Located at Boulder, Colorado 80302. mmimiiiiiuiii.iuijuii^^-^—^n.
«. BUREAU OF STANDARDS

MAR 2 1972

u±- ace- ify

Ms 7/S

14 73-

UNITED STATES DEPARTMENT OF COMMERCE

Maurice H. Stans, Secretary

S NATIONAL BUREAU OF STANDARDS • Lewis M. Branscomb, Director Iff

NBS TECHNICAL NOTE 712

ISSUED FEBRUARY 1972

Nat. Bur. Stand. (U.S.), Tech. Note 712, 13 pages (Feb. 1972)

CODEN: NBTNAE

Manual and Computerized Footprint Identification

J. H. Wegstein

Center for Computer Sciences and Technology

National Bureau of Standards

Washington, D.C. 20234

*** 0F *°*

%<TAU 0* "

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

listed or referred to in the open literature.

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

(Order by SD Catalog No. C 13.46:712). Price 25 cents.

Manual and Computerized Footprint Identification

by J. H. Wegstein

Part 1 describes a manual footprint classification system that utilizes the ridge patterns

adjacent to the toes on the sole of the right

foot. This system is an extension of the FBI

footprint classification system. Part 2 describes

a method of coding minute details of these prints

for storage in a computerized file. The computer

can then search a similarly coded unknown print

against this file and identify the most likely

matching prints from the file.

Key words: Computerized-footprint-identification; footprint; pattern

recognition.

Introduction

For personal identification, the use of fingerprints is the most

common and most developed technique. However, other dermatoglyphic

areas on palms, toes and soles of the feet can also serve to uniquely

identify an individual. This paper describes an identification system

utilizing the sole print of the right foot. The area of the sole starting at the base of the toes and running for about 70 mm toward the heel

is used Prints may be obtained by inking and pressing the sole on a flat surface or by internal reflection photography utilizing a light

source, prism, and camera. The latter resulting high-contrast image

resembles an inked print. This principle applies when one observes,

through a glass of water, the prints of the fingers holding the glass.

Figure 9 was made from an internal reflection photograph and shows the area of the sole that is used.

If a technician is given two dermatoglyphic prints of the same

area, such as the soles of the feet, he can immediately tell by

inspection of the prints whether they are from the same person. In

making this identification, he utilizes minute details in the prints,

particularly, ridge endings and bifurcations in the ridges that are hereafter referred to as minutiae.

When an unknown print is to be searched against a file of prints,

making a positive identification is a minor problem compared to the

task of finding the matching print in the file. To facilitate finding

a print in a file, it is classified using the gross patterns that occur

in the ridges. The resulting classification is then used to locate the

print in the file. The classification of a search print should agree

closely enough with the classification of a file print that only a few

prints from the file need to be compared with the search print.
The remainder of this paper is divided into two parts. Part 1 describes a system for manually classifying, filing, and searching

prints from the right foot. Part 2 describes a method of coding and

storing right-footprint information in a computer memory so that a computer can identify an unknown footprint by comparing its code with

other codes previously stored in its memory or mass store.

Part 1.

Manual Classification and Search

The manual classification system is a modification and extension

of the Federal Bureau of Identification footprint classification system

described in two issues of the FBI Law Enforcement Bulletin. 3 ' 4 It is

assumed that the reader who wishes to classify footprints will study

these references. The precise definition of cores, deltas, and major

pattern types requires further study of the basic FBI manual on fingerprints5

.

The complete classification for right-foot prints described here

consists of three parts labeled PS, DST, and FIN. The classification

for four typical prints appear as follows:

PS DST FIN

02 nu

La m 22

Ww m(JU 12

Wd u 8

PS, short for Primary-Secondary, refers to the eight different

patterns of ridges that occur on the ball of the foot Immediately below

the great toe. These are:

01 Ridges are plain arches that tend to flow from toe to heel.

02 Ridges are plain arches that tend to flow across the foot.

La Loops where staples point toward the toes.

Lb Loops whose staples point toward the great-toe side of the foot.

Ld Loops whose staples point toward the right and toward the heel

of the foot.

Ww Whorls

Wd Double loops.
Wx Patterns that do not conform to any of the above types —called

accidentals.

Schematic diagrams for these types of patterns are shown in Figures 1 and 2 These diagrams merely summarize the more elaborate FBI rules

for primary-secondary pattern definition.

The classification system described here is intended to handle a larger file than the FBI system was designed to handle and differs from

the FBI system as follows. The FBI classification includes only parts

labeled PS and FIN for the right foot along with similar parts for the

left foot. The system described here utilizes only the right footprint

but includes an extra part called DST that makes use of the patterns in

the remainder of the distal part of the sole. The ridge pattern on the

interdigital pads below the toes may include no loops or It may include

combinations of loops whose staples point up or down. A loop is considered to occur if at least one ridge recurves to form a staple. The

various possible patterns are shown schematically in Figure 3 along with

their DST designations. To elaborate on Figure 3, two or more downward

pointing staples are designated M. Two or more upward pointing staples

are designated UJ. When upward and downward pointing staples both occur,

it is immaterial whether they do or do not form a whorl.

The part of the classification called FIN is the distance in millimeters between a core and delta of the PS pattern (if a core occurs).

The line along which FIN Is measured is shown schematically as a fine

straight line in Figures 1 and 2. Note that types 01 and 02 have no FIN number. In Ld, Ww, and Wd type prints where there are two deltas,

the distance is measured from the upper delta to the core. The core

point used is defined as the point on the innermost curving ridge

where the curvature is greatest. In La type prints FIN is measured

from the core to the delta on the great-toe side of the sole of the

foot. In Wd type prints there are two cores and FIN is measured from the

upper delta to the nearest core. Some additional examples of type Wd

prints are shown in Figure 4 along with core-delta lines.

In the FBI system the FIN (or "final") part of the classification

is obtained by counting the number of ridges that occur between the core and the delta. An FBI classification of a print is entirely

topological in nature and is invariant to the size of the print,, It

does not change during the time an individual grows from a baby to a mature person. In contrast, the system described here is intended for use on prints from mature persons. The core-delta distance, in millimeters, is not expected to change significantly and, accordingly, it is

used in lieu of the more dif f icult-to-obtain ridge count. The complete

classification for the footprint shown in Figure 9 Is : Ww nw 21.
Prints are filed in the PS sequence shown in Figures 1 and 2.

Within each PS group the prints are filed in the DST sequence shown

in Figure 3. And, finally, within each DST group the prints are filed

in numerical order as indicated by FIN. Only those prints of good

enough quality to be classified should be filed.

When an unidentified print is to be searched against the file, it

is classified according to the above rules. It is then compared with

prints having the same classification from the file. It must also be

compared with neighboring prints from the file whose FIN values differ

from that of the search print by as much as two or three millimeters

plus or minus. If the search print is of such poor quality that there

is an uncertainty in the value of PS or DST, then other prints from

the file corresponding to possible PS and DST values of the search

print must also be examined. In comparing prints a technician notes

agreement in peculiarities of ridge patterns, but he makes final decisions

based on exact correspondences of minutiae patterns. Creases, scars,

and other marks that may be of a temporary nature are ignored.

Part 2

Codification and Computerized Search

Digitalized descriptive information suitable for use by a computer

is obtained from specific areas adjacent to cores in the PS region of

the footprint. Such an area might appear as shown in Figure 5. Ridges

are observed in a clockwise direction from left to right and minutiae

are given coded values, S, as follows. Ridge-endings such as minutiae

b, e, and g in Figure 5 have a value 0=0. Ridge-beginnings such as minutiae a and d have a value 0=1. Since a splitting of one ridge

into two ridges such as minutia j might appear as a ridge-beginning if

the print were less heavily inked, it too is given a value 0=1.

Similarly, merges in ridges such as c are given the value = as though they were ridge endings. Breaks in ridges like f that are shorter

than the distance between two ridges are ignored. Short ridges like

i that are shorter than the distance between two ridges are also ignored.

Incipient ridges like h are ignored. Ridges that "kiss" or touch

briefly as at k are not coded.

Each minutia that is given a e value is also given coordinate values

x and y by superimposing a rectangular grid over the area as shown in

Figure 6. The grid units are 0.5 mm and the grid covers an area of 15 mm

x 10 mm. The grid is oriented so that the x axis passes through a delta

and is tangent to the innermost recurving ridge of a core at the point

x = 15. One convenient way to read minutiae data is to project the print

with a ten power opaque projector. A suitably enlarged grid is then

placed on the projected image. The positioning of the grid for each

of the different PS pattern types is shown in Figure 7. Figure 8 shows

;
the grid position to use on the illustrated variant of type La. To

read minutiae data, one first locates each minutia as illustrated in

Figure 5 then records the nearest x, y coordinates along with 6. The

data corresponding to Figure 6 appears as follows:

y_£

15 01

13 01

13 02 1 16 02 1 18 02

14 03

16 03

14 04 1 16 04 1

The number of minutiae per footprint that are recordable in this manner

ranges from 5 to about 25. A set of data like this for each footprint

along with its identification and classification (PS, DST, FIN) is read

into a computerized file. The rather rare types 01 and 02 that have no

core are not handled by this system.

When an unknown footprint is to be identified, its minutiae data are recorded as above and read into the computer. The computer compares

this data from the unknown print with each set of data in its file

and computes a score indicating how well the two prints match. The

computer then prints the identification and classification of those

file prints having the highest matching scores, A technician then

compares the unknown print with each print from the file that the

computer has indicated to be a possible match.

The algorithm used by the computer in comparing footprints is

shown in flow diagram form in Figure 10. It is a slightly simplified

version of the M19 matcher described in National Bureau of Standards

Technical Note 538s . Here 3MX is the number of minutiae in a print;

Ident is the identification of the print including its classification;

and array A contains the values x, y, and 6 as shown at the bottom

of Figure 10. Corresponding minutiae are used in making the identification, but they need not coincide. The tolerated amount of displacement

is determined by the parameters LS and KR.

This work was performed at the NBS Center for Computer Sciences

and Technology and was encouraged by the Center's Director, Dr. Ruth

M. Davis. The author is also indebted to Mr. John Rafferty of NBS and

to Mr. Alan Meyrowitz of the Special Action Office for Drug Abuse

Prevention for testing this footprint identification system* He also

appreciates the advice received on footprint identification problems

from Mr. H. Caton of the Federal Bureau of Identification,,
References

1. Cummins, H. and Midlo, C, Fingerprints, Palms and Soles , Dover

Publications, Inc., New York 1961.

2. Harrick, N. J., Internal Reflection Spectroscopy , Interscience

Publishers, New York, 1967, pp. 3-6.

3. "Classification of Footprints, Part I", FBI Law Enforcement Bulletin

40, 9 (September 1971), pp. 18-22.

4. "Classification of Footprints, Part II", FBI Law Enforcement

Bulletin 40 . 10 (October 1971), pp. 23-27.

5. The Federal Bureau of Investigation, The Science of Fingerprints , U.S. Government Printing Office, Washington, D.C. 1963.

6. Wegstein, J. H.

,

Automated Fingerprint Identification , National

Bureau of Standards Technical Note 538, U.S. Government Printing

Office, Washington, D.C, 1970.
01

oz

L a

Lb

Figure 1. PS Pattern Designations
Ld

Ww

Wd

Wx

Figure 2. PS Pattern Designations (Continued)
/

m

m

u

UJ

rnu

muu

nu

nuu

Figure 3- DIST Pattern Designations
-< < -<

Wd

Figure 4. Core-Delta Lines on WD Prints

{ h>l c el 'e

1 o

Figure 5- Minutiae Identifications

10
Figure 6. Grid for Reading

Minutiae Data

^

Delta

wfmm

D—/2 13 If % !(, 17 It --30

Core

Figure 7. Placement of Grid on Various

Types of Prints

La

Lb

Ld

< SH Ww

-<

>Wd

-< y

ii
La

Figure 8. Grid Placement on Variant La Print

/o mm

Figure 9. Footprint with Classification:

Ww nw 21

12
1=1

Redd

Ueitt, Identt

Aw At*t

j 2.t

i

s=o

*3

3*\

I 23

3=Z

E_3

J*I

11

H,

TZ—

AX=Ai%3-Ajxc

J£.

j^J* 1 I li —h*1-*

^«0

2?

*7 gy

KS=f

30

3-S

70 y

./=/

(TD^Q

i

5D =

tax, * imz

^-3

10 7

p-(^v8?/i/>0

TK.x/Mj-VXjhfa-llI

tf " K*R + Kfc-T£

Parameters

L0 -0

sn -o

Conie.nts of Search Array

Aii i Aixi Ai*i A\'Y/

i Xi yi Si

I3\ f S = s+l

IX

I

I

ay* =ay

Figure 10. Footprint Matching Algorithm

* U. S. GOVERNMENT PRINTING OFFICE : 1 972--481 -330/1 65 13
f»©f*M-HfrS-H4A-ti»n > U.S. DEPT. OF COMM. BIBLIOGRAPHIC DATA

SHEET

1. PUBLICATION OR REPORT NO.

NBS-TN-712

2. Gov't Accession No.

4. TITLE AND SUBTITLE

Manual and Computerized Footprint Identification

7. A-UTHOR(S)

J. H, Wegstein

9. PERFORMING ORGANIZATION NAME AND ADDRESS

NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

12. Sponsoring Organization Name and Address

Same

3. Recipient's Accession No.

5. Publication Date January 1972

6. Performing Organization Code

8. Performing Organization

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

11. Contract/Grant No.

13. Type of Report & Period Covered

Final

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

Part 1 describes a manual footprint classification system that utilizes the

ridge patterns adjacent to the toes on the sole of the right foot. This system is an extension of the FBI footprint classification system. Part 2 describes a method

of coding minute details of these prints for storage in a computerized file. The

computer can then search a similarly coded unknown print against this file and

identify the most likely matching prints from the file.

17. KEY WORDS (Alphabetical order, separated by semicolons)

Computerized-footprint-identification, footprint, pattern recognition.

18. AVAILABILITY STATEMENT

UNLIMITED.

| | FOR OFFICIAL DISTRIBUTION. DO NOT RELEASE

TO NTIS.

19. SECURITY CLASS

(THIS REPORT)

UNCLASSIFIED

20. SECURITY CLASS

(THIS PAGE)

UNCLASSIFIED

21. NO. OF PAGES

13

22. Price

$.25

USCoUlH-DC 66244-P
NBS TECHNICAL PUBLICATIONS

PERIODICALS NONPERIODICALS

JOURNAL OF RESEARCH reports National

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

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

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

charts.

Published in three sections, available separately:

• Physics and Chemistry

Papers of interest primarily to scientists working in these fields. This section covers a broad range of physical and chemical research, with major emphasis

on standards of physical measurement, fundamental

constants, and properties of matter. Issued six times a year. Annual subscription: Domestic, $9.50; $2.25

additional for foreign mailing.

• 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 chemisty, logical design and programming of computers

and computer systems. Short numerical tables. Issued

quarterly. Annual subscription: Domestic, $5.00;

$1.25 additional for foreign mailing.

• Engineering and Instrumentation

Reporting results of interest chiefly to the engineer

j and the applied scientist. This section includes many

of the new developments in instrumentation resulting

from the Bureau's work in physical measurement,

j data processing, and development of test methods.

' It will also cover some of the work in acoustics,

applied mechanics, building research, and cryogenic

engineering. Issued quarterly. Annual subscription:

Domestic, $5.00; $1.25 additional for foreign mailing.

TECHNICAL NEWS BULLETIN

j The best single source of information concerning the

I Bureau's research, developmental, cooperative, and

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

daily work involves intimate contact with science and

technology

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

company executives. Annual subscription: Domestic,

$3.00; $1.00 additional for foreign mailing.

Applied Mathematics Series. Mathematical tables, manuals, and studies.

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) de- veloped in cooperation with interested industries,

professional organizations, and regulatory bodies.

Special Publications. Proceedings of NBS conferences, bibliographies, annual reports, wall charts,

pamphlets, etc.

Monographs. Major contributions to the technical

literature on various subjects related to the Bureau's

scientific and technical activities.

National Standard Reference Data Series.

NSRDS provides 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 co- operatively with interested Government and industry

groups and provide the basis for common understanding of product characteristics for both buyers and

sellers. Their use is voluntary.

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

NBS-sponsored work) of limited or transitory interest.

Federal Information Processing Standards

Publications. This series is the official publication

within the Federal Government for information on

standards adopted and promulgated under the Public

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

entitled, Standardization of Data Elements and Codes

in Data Systems.

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 Special Publication 305, Supplement 1, Publications of the NBS, 1968-1969. When ordering, include Catalog No. C13.10:305. Price $4.50;

$1.25 additional for foreign mailing.

1

Order NBS publications fromSuperintendent of Documents

Government Printing Office

Washington, D.C. 20402
U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

Washington, D.C. 20234

OFFICIAL BUSINESS

Penalty for Private Use. S300

POSTAGE AND FEES PAID

U.S. DEPARTMENT OF COMMERCE

I