 |
Description  |
|
|
FIELD OF THE INVENTION
This invention relates to identification of fingerprints, and possibly to
other personal characteristic matching, and more particularly to the
matching of a set of fingerprints with a reference file containing many
fingerprints, and verification of whether two or more fingerprint
impressions are from the same finger or from different fingers.
BACKGROUND OF THE INVENTION
Pattern matching or comparison schemes have many applications, such as
identifying machine parts in a manufacturing context, and the reading of
addresses in a mail-sorting context. The above-mentioned applications are
among the simpler uses of such comparisons, because, in the case of
machine parts, the number of different parts is finite, and their shapes
are, in general, relatively simple; the text reading context has only 26
letters and ten digits to identify, although the number of permutations of
machine printing is large.
More complex types of comparisons are those involving differentiation among
items which are similar, but not identical, especially when the conditions
under which the images are formed is not uniform. When the images are of
biological specimens, the variability of the images may be very large. One
such aspect of image matching is that of matching the retinal patterns of
subjects for identification. Another use is that of identification of
fingerprints by comparison with file fingerprints.
Fingerprints are very rich in information content. There are two major
types of information in a fingerprint. First is the ridge flow
information, and second is the specific features or minutiae (minutia) of
the fingerprint. As used herein, the term "minutia" is used to denote both
the singular and plural. Fingerprints uniquely identify an individual
based on their information content. Information is represented in a
fingerprint by the minutia and their relative topological relationships.
The number of minutia in a fingerprint varies from one finger to another,
but, on average, there are about eighty (80) to one hundred and fifty
(150) minutia per fingerprint. In the fingerprint context, a large store
of fingerprints exists in law enforcement offices around the country.
These fingerprints include files of fingerprints of known individuals,
made in conjunction with their apprehension or for some other reason such
as security clearance investigation or of obtaining immigration papers,
often by rolling the inked fingers on cards, and also includes copies of
latent fingerprints extracted from crime scenes by various methods. These
reference fingerprints are subject to imperfections such as overinking,
which tends to fill in valleys in fingerprints, and underinking, which
tends to create false ridge endings, and possibly both overinking and
underinking in different regions of the same fingerprint image. Smudging
and smears occur at different places in the fingerprint due to unwanted
movement of the finger, or uneven pressure placed on the finger, during
the rolling process. The stored fingerprints are also subject to
deterioration while in storage, which may occur, for instance, due to
fading of the older images, or due to stains. Furthermore, the wide
variation in the level of experience among fingerprint operators, and the
conditions under which the fingerprint is obtained, produces wide
variation in quality in the fingerprint images. Similar effects occur due
to the variation of the scanning devices in cases of live scanning of
fingerprints.
Matching of fingerprints in most existing systems relies for the most part
on comparison of cores and deltas as global registration points, which
tends to make the comparisons susceptible to errors due to the many
sources of distortion and variations listed above, which almost always
occur due to the various different inking, storage and preprocessing
conditions which may be encountered.
As described at pages 164-191 of the text Advances in Fingerprint
Technology, by Henry C. Lee and R. E. Guenssten, published by Elsevier in
1991, efforts have been underway for a long time to automate fingerprint
identification, because manual search is no longer feasible due to the
large number of reference files. The effort to automate fingerprint
identification involves two distinct areas, namely (a) that of fingerprint
scanning and minutia identification, and (b) comparison of lists of
minutia relating to different fingerprints in order to identify those
which match. Large files of reference fingerprints have been scanned, and
minutia lists in digital form obtained therefrom, either by wholly
automated equipment, or with semiautomated equipment requiring human aid.
While not all problems in scanning of fingerprints and detection of
minutia have been solved, it appears that the matching problem is the more
pressing at this time.
The matching or search subsystem constitutes the most critical component of
any Automated Fingerprint Identification System (AFIS). Its performance
establishes the overall system matching reliability (the probability of
declaring the correct mate, if one exists in the database), match
selectivity (the average number of false candidates declared in each
search attempt), and throughput, which is particularly important in large
database systems. The unique identification of fingerprints is usually
performed using the set of minutia contained in each fingerprint. For each
fingerprint, these minutia form a minutia map.
FIG. 1a illustrates a particular skeletonized fingerprint impression,
number F0048.sub.-- 04, from the National Institute of Standards and
Technology (NIST) database 4, resulting from a proper inking procedure,
while FIG. 1b illustrates the same skeletonized fingerprint, resulting
from underinking and some smudges in the underlying impression. As a
result of the different conditions under which the impressions of FIGS. 1a
and 1b were made, at least some of the minutia, represented by dots in
FIGS. 1a and 1b, are different, and differently located. These differences
make it clear that a matching scheme must be particularly robust if it is
to reliably identify an unknown or search fingerprint with a reference
fingerprint without generating an excessive number of false positives.
An improved search or matching system is desired, which provides high match
reliability, low match selectivity, and high system throughput in a large
database context.
SUMMARY OF THE INVENTION
Images, such as fingerprints, are compared with reference fingerprints by,
in the first instance, generating a file of reference fingerprints,
digitizing the reference fingerprints to generate digital representations
of the reference fingerprints, and storing the information in a digital
memory, which may be read-only memory, magnetic tape, or the like. Such
files already exist, and are maintained and updated by institutions such
as the FBI.
The digitized reference fingerprint data is converted, by an electronic
computing apparatus, to attributed relational graph (ARG) form, which
includes (a) nodes and node attributes and (b) branches between the nodes,
and branch attributes, derived from extracted digital minutia maps of the
sets of reference fingerprints. The attributed relational graph includes
various node and branch attributes, including topological information such
as minutia location and direction. To identify a set of unidentified
fingerprints (which set may contain as few as one fingerprint), that set
of unidentified fingerprints must be compared with the stored set of
reference fingerprints. In this context, the term "unidentified" as
applied to a set of fingerprints does not necessarily mean that the
fingerprints are from an unidentified person, but rather that they have
not been matched against the reference fingerprints. The comparison of the
set of unidentified fingerprints is made by, first, generating an
attributed relational graph of each fingerprint of the unidentified
fingerprint set, each of which attributed relational graphs includes (a)
nodes and node attributes and (b) branches between the nodes, and branch
attributes, all derived from an extracted digital minutia map of the set
of unidentified fingerprints, much as was initially done for the reference
fingerprint files. The generation of the attributed relational graphs
implicitly generates stars centered at each of the nodes; a star includes
a central node, its branches, which are the branches immediately connected
to the central node, and the nodes at the ends of its branches. The second
step in identification or comparison of an unidentified fingerprint set
uses an electronic computing apparatus to generate a distance matrix
between (a) the stars in the ARG of one of the fingerprints of the set of
unknown fingerprints and (b) the stars of the ARG of one of the
fingerprints in one of the sets of reference fingerprints. The distance
matrix includes a matrix element associated with each pair of stars being
compared. In a preferred embodiment of the invention, the elements of the
distance matrix are sorted for each fingerprint pair, according to the
value of the elements, to establish an order of star pair matches. A match
core of consistent star pairs is generated using the distance matrix and
the ARG for each fingerprint being compared. In the preferred embodiment,
the generation of the match core is performed in an order established by
the sorted distance matrix. The match core for each fingerprint pair being
compared is expanded by adding star pairs consistent with the star pairs
included within the match core, until no more such star pairs consistent
with the match core are available to be added. This may occur because
there is a lack of a match between the fingerprints being compared,
because all available star pairs of the fingerprint pair have been
matched, or because a predetermined limiting number of matched star pairs
has been reached. The procedure is repeated, comparing the unidentified
fingerprint successively with each fingerprint of the reference file. If
the search can be reduced by extrinsic knowledge, such as the
identification of the particular digit (for example, the index finger) or
the hand (left or right), the search or comparison may be limited to
corresponding fingerprints of the reference fingerprint file. That match
core(s) which has the highest score identifies the closest pair match
between the unidentified fingerprint and a fingerprint of the reference
fingerprint files.
According to another aspect of the method according to the invention, the
step of generating an attributed relational graph includes the steps of
(a) assigning a particular node of the ARG to each minutia of the
extracted digital minutia map, (b) assigning to the particular node of the
ARG the location of its corresponding minutia, (c) assigning to the
particular node of the ARG the direction of its corresponding minutia, (d)
constructing a branch between the particular node and the nearest other
node in each of four quadrants around the particular node, as established
by the direction of the particular node, where the "nearest" is determined
by the Euclidean distance between the nodes, and (e) assigning to the
branch at least the attributes of (i) the Euclidean distance, and (ii) the
quadrant within which the other node lies.
According to an aspect of the invention, the step of performing distance
matrix calculations includes the steps of determining the Euclidean
distance between pairs of the minutia, and dividing the Euclidean distance
between the pairs of minutia by the average of the local ridge width
between the minutia of the pairs, to generate normalized ridge width
distances for each of the pairs, whereby the list of topological
relationships includes the normalized ridge width distances.
According to a further aspect of the invention, either or both of the
attributes of minutia type and local ridge width is/are assigned to the
nodes of the attributed relational graph. The branches of the attributed
relational graph are assigned the attributes of ridge count, normalized
ridge width distance, andor "same ridge" attribute.
According to the invention, the generation of the distance matrix is
performed by two steps, the first of which is comparing the values of the
attributes of the stars of the ARG representations of the unknown and
reference fingerprints. This includes a comparison between each branch of
a star of the unknown fingerprint and each branch of a star of the
reference fingerprint. A score is generated for each such pair of branches
The second step in generation of an element of the distance matrix is by
calculating the maximum consistent sum of scores of branch pairs for each
star pair.
A match core is formed by the steps of selecting a star pair associated
with, or corresponding to, a highest-value distance matrix element, which
defines a first element of a match core; adding such a first element to
the match core; deleting from the distance matrix that element associated
with the first element of the match core, to thereby generate a reduced
distance matrix; selecting, from among candidate pairs of stars centered
on neighbor nodes of the central nodes of the star pair in the first
element of the match core, that candidate star pair which both (a) is
consistent with the match core, and (b) among all such candidate star
pairs which are consistent with the match core, is associated with a
highest distance matrix element in the reduced distance matrix, to thereby
generate a second element for the match core; adding the second element to
the match core as a further element; deleting from the reduced distance
matrix that one of the elements of the distance matrix associated with the
candidate star pair added as a second element to the match core, to form a
further reduced distance matrix; and repeating the steps of selecting that
further star pair, adding, and deleting from the reduced distance matrix,
at least until no more candidate star pairs consistent with the match core
remain. As mentioned above, a predetermined number of elements in the
match core may be deemed to be sufficient to halt the further generation
of match cores, which is termed and additional elements than this number
are termed "inconsistent".
If the number of elements in the match core is less than a particular
number, and no star pair consistent with the match core remains, the
search strategy may "back up" and try another search path, by deleting the
most recently added element from the match core, whereby the penultimate
element, or another element, becomes the last element added to the match
core. Another candidate pair of stars is then selected, from among
candidate pairs of stars centered on neighbor nodes of the center nodes of
any star which is associated with an element of the match core. That pair
of stars is selected which both (a) is consistent with the match core, and
(b) among all the candidate star pairs which are consistent with the match
core, is associated with a highest distance matrix element in the reduced
distance matrix. This generates a next candidate element for the match
core, which is then added to the match core. That one of the elements of
the distance matrix associated with the candidate star pair is deleted, to
form a yet further reduced distance matrix. The steps of selecting that
further star pair, adding, and deleting from the reduced distance matrix
are repeated, at least until no more candidate star pairs consistent with
the match core remain.
DESCRIPTION OF THE DRAWING
FIGS. 1a and 1b are representations of skeletonized print images of a
single finger, illustrating the effects of different inking conditions of
the impression on the resulting minutia;
FIG. 2 is an overall diagram of a fingerprint matching apparatus or system
according to the invention, illustrating the image scanning, feature
extraction, storage of reference information in memory, and an overview of
the matching process performed in a computing apparatus, either
general-purpose programmed, or special-purpose;
FIG. 3a is an attributed relational graph (ARG) representation of the
minutia of a fingerprint, FIG. 3b is a representation of a possible bit
structure of a node attribute vector, and FIG. 3c is a possible
representation of the bit structure of a branch attribute vector;
FIG. 4a illustrates a pair of stars from a attributed relational graphs of
two fingerprints being compared, each star being made up of a central
node, branches from the central node, and neighbor nodes, and FIG. 4b
illustrates a portion of a fingerprint showing minutia at the ends of a
ridge and at a bifurcation of a ridge, and also showing the measurement of
ridge count between adjacent minutia;
FIGS. 5a, 5b, 5c, and 5d represent the local coordinate system about a
particular minutia, the coordinate system definition applied to one
minutia from among the minutia of a particular fingerprint, fuzzy quadrant
definition similar to that of FIG. 5b with the coordinate system rotated
in the clockwise direction, and fuzzy quadrant definition similar to that
of FIG. 5b rotated in the counterclockwise direction;
FIGS. 6a and 6b together are a simplified flow chart which represents a
distance matrix generation portion of a method for matching a particular
fingerprint with another in accordance with the invention;
FIG. 7 is a simplified flow chart which represents the match core
generation portion of the determination of similarity of two fingerprints
in accordance with the invention; and
FIGS. 8a and 8b1 and 8b2 together constitute a simplified flow chart
illustrating details of a candidate node selection step of FIG. 7.
DESCRIPTION OF THE INVENTION
In FIG. 2, a fingerprint card 10, made by inking and rolling the fingers of
an individual, is scanned by an optical scanner 12, to generate digital
signals representing the image at a sufficient level of detail to allow
minutia to be identified. As mentioned above, an alternative to the use of
the illustrated scanner is to use a live scanning device which generates
digital signals directly from scanning of a finger placed on a plate. As
used herein, unless the context indicates otherwise, the term
"fingerprint" or "fingerprint image" is used to denote a digital image
obtained from the automatic or manual scanning of an inked rolling of a
finger, or the capturing of a fingerprint through live scanning devices.
The digital signals are applied to a conventional feature extractor 14,
which extracts at least a list of minutia locations and directions, and
which may produce a skeleton of the image. It may be desirable to extract
other information, such as minutia type and local ridge width. A skeleton
is an image of an impression of a fingerprint in which the contrast has
been increased so that only binary information (ones and zeroes) remain;
the skeletonizing may be performed optically, followed by scanning and
digitization, or the scanning of the image may result in digital
information which represents a gray scale, following which the digital
information may be processed to compress the gray scale to two values. The
skeleton may be used within the feature extractor to extract another
desirable attribute, namely ridge count, as described below. Feature
extractor 14 couples the minutia list of the search print to a processor
16. Processor 16 performs conversion of the digital minutia list to an
attributed relation graph (ARG), described below in relation to FIG. 3a.
In general, the ARG is a symbolic representation of the fingerprint
impression, including relevant information, such as minutia location on
the card, minutia direction, and other attributes which may be available.
The minutia locations on the image will vary each time an inked impression
is made or a live scan is taken, even of the same finger, because of
variations in the setting of the finger on the card window, and even if
the location were by chance the same, the rolling of the finger, and the
variations in pressure thereon, would move the locations of some of the
minutia relative to other minutia. The ARG of the unknown or search
fingerprint is coupled by a path 18 to a processor 20. In the present
context, processors 16 and 20 may be the same general-purpose processor,
using ARG generation software part of the time, and search software during
other times, or they may be distinct hardware devices, each programmed for
a specific function.
A memory 22, which may be an electronic memory such as a tape archive,
optical disk memory, or the like, is preloaded with attributed relational
graph representations of sets of reference fingerprint information, made
as described above in relation to the unidentified fingerprint ARG. Since
the memory must be loaded in some fashion, a further data path 24,
illustrated by dash lines, represents the loading, before the time at
which the search is to be made, of memory 22 with ARG representations of
the reference fingerprint information from processor 16. A reading
arrangement, designated 23, reads information relating to reference
fingerprints under command of a control signal coupled thereto.
The minutia which are used in matching according to the invention are
generally of two basic types, namely (a) joining points of ridges
(bifurcations), and (b) the ends of ridges without branching or joining
(ridge endings), but are not limited to these two types. The minimum
information which must be available in relation to each minutia is the
location, which is generally provided in X-Y Cartesian coordinates, but
which might be provided in circular or other coordinates, and the
direction. The direction of a minutia is defined in the abovementioned Lee
and Guenssten text, but in general, may be said to be the direction of the
ridge in a ridge ending situation, and a direction opposite to the
direction of the common portion of a furcation in the bifurcation context.
When the memory 22 of FIG. 2 is loaded with reference fingerprint
attributed relational graph information, and processor 16 has generated
the ARG of an unknown fingerprint, both are made available to processor 20
to allow a search to be made. The identification is accomplished by
comparing the fingerprint to be identified sequentially with each relevant
fingerprint in the reference fingerprint memory. Thus, two fingerprints,
constituting a set, are always being compared; one unknown or search
fingerprint, and one of the fingerprints from the reference memory. In
general, the comparison of each fingerprint pair is started by generating
a distance matrix by calculations on both the unknown fingerprint ARG and
on the ARG of one of the reference fingerprints. In FIG. 2, the distance
matrix calculations are performed in a module 26 of processor 20.
Processor 20 may be a programmed general-purpose computer, in which case
it itself produces the control signals which control the memory reader 23
for reading from memory 22, and which controls the various modules 26, 28,
and 30 therein; if processor 20 is a special-purpose processor, it may
require a time controller or sequencer 39 for synchronizing the activities
of the various portions. The distance matrix calculation is performed by
comparing stars of one fingerprint ARG with stars of another fingerprint
ARG, or more particularly between stars of the unknown fingerprint and the
stars of the current one of the reference fingerprints. A star is defined
below. The distance matrix calculation performed in module 26 of FIG. 2
results in a matrix with an element for each pair of stars of the
attributed relational graphs of the unknown fingerprint and the reference
fingerprint. In a preferred embodiment of the invention, the distance
matrix is coupled from module 26 to a block 28, which represents a sorting
of the elements of the distance matrix in accordance with their magnitude
or value. The sorting can be performed in any manner. Block 30 of
processor 20 represents a graph matching module, which attempts all
possible combinations of matches of the star pairs, in order to build up,
star pair by star pair, the largest consistent set of matching star pairs.
In order to reduce the amount of processing which is unlikely to produce a
substantial match, the processing is preferably performed in graph
matching module 30 in an order established by the sorting performed in
sorting module 28, starting with the star pairs which are most alike. Once
the graph matching is performed in module 30, the result of the matching
is transferred, in the form of a value, by way of a path 32 to a temporary
store or memory 34, in which the value of at least that graph which
contained the largest number of matched star pairs is stored, together
with the identity of the reference fingerprint associated with that
matching. When the unknown fingerprint has been compared with a reference
fingerprint, and its match value recorded, information relating to the
next reference fingerprint is read from memory 22 to distance matrix
generator 26, and the matching procedure starts again. This sequence
continues, at least until a match is found as established by some
threshold criterion, or until the supply of relevant reference
fingerprints is exhausted. The information stored in store 34 represents
the best match, or if more than one match is stored, the values or
comparative qualities of the matches, together with the identification of
the reference fingerprints with which the match is associated. Block 36
represents the selection of the best match from among those stored, and
block 40 represents a display, on which the identification of at least
that reference fingerprint set which was the best match to the unknown
fingerprint is presented.
FIG. 3a represents a simplified attributed relational graph of a
fingerprint. In FIG. 3a, circles or ovals represent nodes, each of which
is associated with one minutia of the extracted fingerprint information.
One such node is designated 310, and an adjacent node is designated 312.
Each node, as described below, is the central node of a star. A line or
"branch" 314 extends between nodes 310 and 312, and is attributed with or
"represents" the topological relationship of the two nodes. Each node of
FIG. 3a has a plurality of branches extending therefrom, but the minimum
number of branches associated with a single node is one. A "star" consists
of a selected center node, together with the branches which terminate
thereon, and the "neighbor" nodes at the other ends of those branches.
Thus, if node 310 is selected as the central node of the star, then the
entire star consists of central node 310, branches 314, 324, 326, 328, and
330, together with nodes 312, 316, 318, 320, and 322. The term "neighbors"
is assigned to nodes 312, 316, 318, 320, and 322, as they relate to
central node 310. In FIG. 3a, each node is associated with a graphic
representation of the minutia type. For example, node 310 is associated
with a graphic designated 340, which is in the form of a bifurcation,
whereas node 312 is associated with a graphic 342, which represents a
ridge ending. The orientations of the graphics also indicates the minutia
direction. The minutia type and minutia direction information represented
by the graphics in FIG. 3a is encoded in the digital words associated with
the node.
FIG. 3b represents the format of a digital word which defines a node of
FIG. 3a. In FIG. 3b, eighteen bits of the word are associated with the X,
Y location of the minutia represented by the node, the next set of eight
bits represents the direction of the minutia, a further eight bits define
the ridge width local to the minutia (if available), and one or two
further bits are assigned to indicate the minutia type (if available).
While only one bit is actually needed to specify the two above-defined
minutia types, an extra bit is available to encode information relating to
additional information should such detail be available.
FIG. 3c represents the bit assignments for the branch attributes or
definitions. In FIG. 3c, eight bits identify each of the two nodes (NODE
IDs) upon which the branch ends, for a total of sixteen bits. Four
additional bits define the ridge count between the two minutia represented
by the nodes. Eight additional bits are used for "fuzzy quadrant
assignment"; four bits define the location of a first one of the end nodes
in a quadrant which is based upon the direction of the minutia of the
second node, and an additional four bits define the location of the second
one of the end nodes in a quadrant which is based upon the direction of
the minutia of the first node. The reason that four bits are required to
identify a quadrant is that the quadrants are "fuzzy", in that the basic
quadrant is specified, and the location in the basic quadrant, subdivided
into three regions, is also specified; there are, as a consequence, twelve
possible fuzzy quadrant assignments. Ridge assignment requires two bits in
the word of FIG. 3a. The ridge assignment establishes, for two adjacent
nodes (associated with the same branch) representing adjacent minutia,
whether or not they lie on the same ridge, or are on different ridges; the
same-ridge attribute is described below in relation to FIG. 4b. As FIG. 3c
has been so far described, the branch vector bits are those which are
expected to be stored as part of the ARG in memory 22 of FIG. 2.
Two further sets of bits are calculated in distance matrix module 26 of
FIG. 2, but are not necessarily stored in memory 22. These are the
Euclidean distance between the two minutia represented by the adjacent
nodes, and the normalized ridge width distance between those same minutia.
The Euclidean distance is a block of 32 bits in the bit assignment of the
word of FIG. 3c, while the normalized ridge width is a block of 32 bits.
Normalized ridge width distance is the Euclidean distance divided by half
the sum of the two local ridge widths of the adjacent nodes. The ridges in
fingers are not necessarily equally spaced; the normalized ridge width
distance corrects for the different ridge widths in the finger itself,
andor in the inked impression, due to the elasticity of the finger.
FIG. 4a represents a star 410 from the attributed relational graph of the
unknown fingerprint, and another star 430 from the ARG of the reference
fingerprint with which it is currently being compared. Star 410 may be
considered to be a star among those of the ARG of an unknown fingerprint
currently being coupled to distance matrix calculation module 26 of FIG. 2
from ARG extractor 16, while star 430 may be considered to be a star among
those of the ARG of a reference fingerprint currently being coupled to
distance matrix calculation module 26 from memory 22 for comparison. The
central node of star 410 of FIG. 4a is designated 412, and the central
node of star 430 is designated 432. For the first star of the particular
set of fingerprints being compared, it is assumed that the node direction
can be in any orientation, that is, a 360.degree. rotation. As a practical
matter, fingers are oriented in roughly the same direction on the card
when the inked finger is rolled, and even latent fingerprints have a
preferred orientation, so that it is possible to restrict the range of
angular positions which must be searched. More particularly, it is
believed to be sufficient to restrict the matching of minutia directions
to within 120.degree., corresponding to a 60.degree. clockwise and
counterclockwise rotation of the image. If the restriction of matching is
changed to 361.degree., the test is essentially eliminated from the
processing, which results in processing for all possible rotations,
thereby preserving rotational invariance in the matching process, which
allows matching to occur notwithstanding any amount of relative rotation
of the impressions.
The first step in generating the distance matrix in processor 26 of FIG. 2
for this particular pair of stars of this set of fingerprints (one unknown
fingerprint and one reference fingerprint) is to start the processing, as
suggested by START block 610 of the flow chart of FIG. 6, load the ARG of
the unknown fingerprint into local memory (block 612), and load the ARG of
the first of the reference fingerprints (block 614). From block 614, the
logic of FIG. 6 flows to a block 616, which represents setting of the set
of all stars in the ARG of the unknown fingerprint equal to SU. The logic
of FIGS. 6a and 6b ultimately iterates over all elements of SU for this
fingerprint. From block 616, the logic flows to a decision block 618,
which examines the set SU to determine if it contains elements or if it is
empty. If the set SU is empty, the distance matrix calculations are
finished for this fingerprint pair, and the logic leaves the flow chart of
FIGS. 6a and 6b by a path 620, and flows to sorting module 28 of FIG. 2.
If the distance matrix calculations have not been completed, however, the
logic leaves decision block 618 by the NO path, and reaches a block 622.
Block 622 represents removal of a star u from set SU, so that it may be
compared with all stars of the reference fingerprint. Block 624 assigns to
another set SV all stars of the ARG of the reference fingerprint, much as
block 616 did for the stars of the unknown fingerprint. From block 624,
the logic flows to a decision block 626, which examines set SV. If set SV
is empty, the current u has been compared with all stars of the reference
fingerprint, and the logic flows by a logic path 628 back to decision
block 618. Assuming that SV is not empty, the logic leaves decision block
626 by the NO path, and flows to a block 630, which represents removal of
one of the stars v from set SV for comparison with u. The remainder of the
flow chart of FIGS. 6a and 6b represents the comparison of star u with
star v.
Block 632 represents the identification of the central nodes of u and v as
u.sub.c and v.sub.c. The logic flows in sequence through decision blocks
634, 636, and 638, which compare three of the possible attributed factors
(factors which are appended to the node descriptive word) of the central
nodes. The first of these factors is similarity of node direction (block
634), the second is similarity of minutia type (block 636), and the third
is similarity of the position of the minutia relative to the fingerprint
in the image (638). The determination of the first of the factors, namely
the factor of node direction, in evaluating the distance matrix element
value for this star pair is to compare, with a threshold value, the
absolute value of the difference between the directions of the nodes. This
is performed in block 634, according to
.vertline.(dir 312)-(dir 332).vertline..ltoreq.T.sub..theta.(1)
where the threshold T.sub..theta. may be the abovementioned 120.degree..
This admits of a yes-no result. As mentioned above, the threshold may be
set to 361.degree. to preserve rotational invariance.
The determination of the second of the factors in evaluating the distance
matrix element value for this star pair, namely the factor of similarity
of minutia type, is to evaluate the equality of the minutia types. Is
minutia type 412 equal to type 432 | | |
