US 5,631,971 AGrant
Vector Based Topological Fingerprint Matching
Issue Date:1997-05-20
•20 Claims
•12 Drawing Sheets
Abstract
A fingerprint recognition and retrieval system in which the positions of fingerprint minutiae points and an index number for each minutiae point are recorded in a storage medium. The local ridge flow direction in the vicinity of each minutiae point defined by ridge endings and ridge bifurcations is determined and a generating line is projected at an angle to the local ridge flow direction. The generating line has a length sufficient to span a predetermined number of ridges to each side of each of the minutiae points. Each ridge is traced, in two directions, from the point of crossing of the projected generating line along any crossed ridge line. The first occurring topological event is assigned a type code (T) to the topological event. A topological event code vector is generated for each minutiae comprising an ordered sequence of topological type codes encountered during the tracing and any associated minutiae reference numbers and sets of the vectors are stored in a machine searchable database. The matching algorithm systematically develops connected cluster of minutiae points within an unknown one of the fingerprints for which there exists a matching cluster of minutiae points within the fingerprint under comparison and wherein the topological relationships among the set of minutiae within the matching clusters are substantially identical.
Metadata
Inventor
- Malcolm K. Sparrow
Application Information
Application Number:US 2761556
Filing Date:1994-07-15
Priority Date:1994-05-24
Art Unit:266
Classifications
IPC:
G06K 900
Field of Search:
382124;125;126;127;197;258;259;209;305
Patent Drawings (12 sheets)
Description
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
Background and Brief Description of the Invention
The invention relates to fingerprint coding and recognition and retrieval systems based on generally invarying topological irregularities, characteristics or minutiae (which terms are used interchangeably herein) of fingerprints. The term "fingerprint" or "print" is used in reference to the epidermal ridge lines of the ten fingers of the human hand, palm prints, toe and sole prints of humans wherein such epidermal ridge lines and characteristic features thereof are in patterns unique to a particular individual.
In my U.S. Pat. Nos. 4,747,147 and 4,817,183 and my papers entitled "Digital Coding of Single Fingerprints--A New Approach for the Computer Age", Journal of Police Science and Administration, Vol. X, No. 2, June 1982, (1) "A TOPOLOGICAL APPROACH TO THE MATCHING OF SINGLE FINGERPRINTS: DEVELOPMENT OF ALGORITHMS FOR USE ON ROLLED IMPRESSIONS", NBS Special Publication 500-124, May 1985, and (2) "A TOPOLOGICAL APPROACH TO THE MATCHING OF SINGLE FINGERPRINTS: DEVELOPMENT OF ALGORITHMS FOR USE ON LATENT FINGERMARKS", NBS Special Publication 500-126, October, 1985. I show that the soft elastic nature of human skin causes substantial variation of the spatial descriptions of successive impressions of the same fingerprints. Consequently, spatially based coding schemes used for forming machine searchable databases have inherent inaccuracies due to the fact that the spatial based coordinate system typically used for coding purposes could not take into account the wide variations in spatial distortions making the match or identification between two rolled prints on the same finger somewhat problematical particularly where the prints are taken at substantially different times or pressures.
Topological coding schemes provide concise digital codes that provide a more reliable basis for fingerprint identification systems. In my above referred to patents and paper, I disclose comparison methods based on topological coding of prints in which a topology base coding system for recording and comparing minutiae used a single vector array generated from topologically based coding of a fingerprint.
In the topological vector extraction part of the system disclosed in my above referred to patents, 1982 Paper and my NBS Special Publication 500-124, the core of the fingerprint is centrally located at a reference point and a horizontal line is projected through the core to intersect ridge lines to each side of the centrally located reference point. In the case of an arch a vertical line is drawn through successive ridge summits. From the points of crossing of the ridges with the projected horizontal or vertical line, the ridges are traced to the first significant irregularity and a type code (T) is assigned to the irregularity. In my patents, the distance (D) from the reference line is measured and these data are recorded in a predetermined order to constitute a topological vector for the print which then is recorded in a machine searchable database. Comparison of vectors takes the form of a sequence of array operations. Comparison of good quality rolled prints is performed extremely rapidly on this basis. In my NBS Special Publication 500-126 I disclose a system for topologically coding fingerprints wherein each topological code would be a vector generated by exploration from short straight lines orthogonal to ridge flow direction and drawn offset from a given characteristic (bifurcations suggested).
The Present Invention
An object of the present invention is to provide an improved fingerprint recognition and retrieval system.
A further object of the invention is to provide an improved topological matching system in which topological code vectors are generated from the fingerprint with one vector being generated for each minutiae revealed on the print.
Another object of the invention is to provide an improved topological event code incorporating the reference number of any other minutiae point encountered through ridge explorations or tracing from each vector generating line.
Another object of the invention is to provide a more versatile matching algorithm.
According to the present invention, topological code vectors are generated directly from the fingerprint (i.e. not via any topological coordinate representation as in my U.S. Pat. No. 4,747,147), one vector being generated for each minutiae revealed on the print.
As is common in the art, incoming fingerprint images are electronically processed to provide a skeleton image of ridge lines and minutiae points constituted by ridge endings and bifurcations with the spatial positions of the minutiae points and an reference or index number (N) for each minutiae point being recorded in a storage medium.
The local ridge flow directions in the vicinity of each minutiae point is determined and a generating line is projected at a predetermined angle transverse to the local ridge flow direction at each minutiae point (the predetermined angle being preferably orthogonal to a local ridge flow direction). The generating line has a length sufficient to span a predetermined number of ridges to each side of each minutiae point. For each minutiae point, from the point of crossing of the projected generating line with the ridges within the span, a tracing is made in two directions along each ridge line crossed by the generating line to the first occurring topological event.
A type code (T) is assigned to each topological event encountered by the ridge tracings. Then, from these data, a topological event code vector is generated for each minutiae with the topological event code vector being comprised of the topological type code for any minutiae encountered during the tracing and the reference or index number (N) for each associated minutiae. These data are stored as vectors in a machine searchable database. It is not necessary to make reference to any central core point or delta and all dependence on the presence of arbitrary selection of a central reference point within the print is therefore eliminated.
A matching algorithm is arranged in a sequence of graded stages with the computational intensity of each stage being controlled by the parameters. This enables the algorithm to be adapted easily for different purposes (from high resolution identification of poor quality latent images at one extreme, to rapid pass filtering of good quality scanned or rolled fingerprint images at the other) simply by changing the parameters set.
Moreover, the matching algorithm systematically develops "topologically connected clusters" within any two prints under comparison. It therefore seeks to develop a maximal topologically connected cluster within one print, for which there exists a matching cluster within the other print (and where the topological relationships between minutiae within the clusters are replicated). A final score is derived for this optimal cluster which reflects both the size of the cluster and the density of the topological connectivity data which is replicated within the other print.
Thus, an important feature of the invention is that the matching algorithm identifies the maximal topologically connected cluster of minutiae points within one print for which there exists a matching cluster of minutiae points within the print under comparison and where the topological relationships among the set of minutiae within the matching clusters are identical.
Brief Description of the Drawings
The above and other objects, advantages and features of the invention will become more apparent when considered with the following specification and accompanying drawings wherein:
FIG. 1A is a block diagram of a fingerprint recording and recognition system incorporating the invention,
FIG. 1B is a diagrammatic illustration showing how generating lines are off-set from minutiae points and oriented orthogonal to a local ridge flow direction (the selection of lines being shown only for purposes of illustration),
FIGS. 2A and 2B show the detail of how the generating line is oriented and, in a preferred embodiment, off-set in the two principle cases, namely, ridge endings and ridge bifurcations,
FIGS. 3A and 3B show how the vector entries correspond to the different ridge exploration events,
FIG. 4 is a table illustrating the ridge exploration event codes for use in the topological event code vector formations,
FIG. 5A shows a portion of a print around a minutiae point (minutiae reference No. 20) and spanning 6 ridge lines to each side of the minutiae point and, FIG. 5B illustrates the extracted vector centered on minutiae 20 of FIG. 5A,
FIG. 6 shows a sample part of a composite data record,
FIG. 7 shows a schematic of the stages of the matching algorithm,
FIG. 8 illustrates returning of a pairs list from the full vector matching (level 3) of FIG. 7,
FIG. 9 shows a detailed matcher output of two prints under comparison, and the final version of Table 3 is printed-out in full,
FIG. 10 shows a print-out of Table 4 revealing a number of different clusters with the cluster score in each case being calculated as the sum of the second order neighborhood scores for each search/file minutiae pairing within the cluster,
FIG. 11 shows the final combined cluster produced during the print comparison following through from FIGS. 9 and 10, and
FIG. 12 shows a full table of matcher parameters.
Detailed Description of the Invention
In a fully automated system, rolled prints are received as grey-scale images, and pass through binarization 10 and skeletonization 11 stages (image processing steps).
Latent images will normally be photographed, placed under a scanner, and the resulting image displayed on a screen. A fingerprint technician then traces the ridge pattern on the computer screen using either a mouse or a light pen of some kind. The resulting tracing (albeit there is no physical tracing) acts as the skeleton image.
Either process produces a skeleton image of the ridge pattern. The difference is only that, in the case of latents, technicians intervene in interpreting and editing the ridge pattern; and with good quality prints (rolled, or live-scan) no human intervention would be required.
From the skeleton image onwards, the encoding processes are the same.
(1) All minutiae points (ridge-endings and bifurcations) are detected and their spatial positions noted in block 12. This process is well understood in the art.
(2) Blurred areas (where the ridge structure is unclear) are established and their positions and boundaries recorded (in what is commonly called a "blur map") in 13.
(3) The local ridge flow direction is determined in the vicinity of each minutiae point in 14.
(4) In block 15, a vector "generating line" is placed orthogonal to the ridge flow direction, preferably slightly offset from the minutiae point, at each minutiae. The generating line is drawn long enough to cover a predetermined number of ridges either side of the central minutiae point. The number of ridges covered each side is a parameter of the encoding and matching process, which we will call "SPAN".
FIG. 1B shows a skeletal print with such generating lines superimposed transverse to the ridge flow direction, where SPAN is assumed to be 6. A selection of lines only is displayed, for purposes of illustration.
FIGS. 2A and 2B shows the detail of how the generating line 20 is positioned according to local ridge flow direction and preferably oriented and offset OS in the two cases--ridge ending (FIG. 2A) or bifurcation (FIG. 2B).
(5) A topological code vector is then generated in 16 through the process of ridge exploration.
FIGS. 3A and 3B diagrammatically show how the vector entries correspond to the different ridge exploration events. The arbitrary terms "up" and "down" are merely terms of reference for the directions shown in FIGS. 3A and 3B.
The final position (14 in FIG. 3B) is "padded" both up and down in the case of a bifurcation.
FIG. 4 shows the selection of hexadecimal event codes according to different possible ridge-traced events. These are only slightly different from the original set disclosed in my above-reference patents and papers.
(6) For any ridge traced event that corresponds to another identified minutiae point (i.e. where the ridge-traced event is 2, 3, 4, 6, 7 or 8) the reference number of that other minutiae point is stored along with the topological exploration event code, as an "associated minutiae reference number". Otherwise a "0" or blank entry is made for the associated minutiae reference number.
FIG. 5 shows an extracted vector EV (centered on minutiae 20), complete with associated minutiae reference numbers RN, for a selected minutiae point (minutiae No. 20 in this case).
(7) For each minutiae on the print, the topological code vectors are recorded in a storage medium 17 (e.g. optical or magnetic), together with the following additional pieces of data:
(a) a reference or index number (an arbitrary ordering of the minutiae points),
(b) spatial coordinates (according to some arbitrary global referencing scheme),
(c) the minutiae type code (`e` for ridge ending, or `b` for bifurcation),
(d) an angular orientation of the minutiae point (per se known in the art).
(8) These sets of information are then combined for each minutiae visible on the print, producing a composite data record for the whole print which is stored in 17.
FIG. 6 shows a sample part of such a composite data record.
FIG. 7 shows a schematic of the stages of the matching algorithm (Appendix A). They are in order:
(1) Read in search print data and file print data for comparison.
(2) Calculate "information content" for the search print and for the file print: This is essentially a count of the number of valid topological connections between minutiae which are represented within the topological code vectors. In practice it would be calculated once when a print was first introduced to the system, and the result stored as part of the data file. The "information content" measure is used only as part of the final score normalization procedure.
(3) Level 1: initial selection of search/file minutiae pairings: Level 1 provides a fast and efficient mechanism for generating search-file minutiae pairs. The large majority of these pairs will be false and are eliminated at subsequent stages of processing. All possible search/file minutiae pairings are evaluated against the following simple rules:
(a) do both the search and file minutiae vectors have sufficient non-trivial information content (i.e. the number of non-trivial topological connections represented exceeds a predetermined minimum threshold--"Filter 1"),
(b) are the search and file minutiae angular orientations the same, within some predetermined tolerance parameter--"minimum angular tolerance".
Further rules could be added to speed processing in certain applications. For instance, global coordinates could be used to require that the search and file minutiae pairings came from essentially similar regions of the print. Another possible filtration rule would require that they be of the same type (i.e. both ridge-endings or both bifurcations).
Search/file minutiae pairings that pass the level 1 rules are passed to level 2.
(4) Level 2: "FASTMATCH" on topological code vectors: For each minutiae pair passing level 1, the topological code vectors for the search and file minutiae are compared. This comparison is designed to operate fast and within minimal computational load, so no use is made at this stage of the accompanying "associated minutiae reference numbers". The hexadecimal code vectors are essentially overlaid, and a count made of the number of times matching event codes appear in similar positions. This count can be referred to as the "hex overlay count".
Search/file minutiae pairs pass level 2 if and only if their "hex overlay count", as returned from subroutine "FULLMATCH" exceeds a predetermined threshold--"Filter 2".
The combinations passing the level 2 tests are stored in a table for subsequent processing. The file print index and search print index are stored, together with a "shift condition indicator" which records the precise alignment under which the vectors were best matched.
The shift condition indicator assumes the values `O`, `f`, or `s`. Condition `O` shows that the score was obtained with the natural alignment of the search and file vectors. Condition `f` shows a shift of one position (i.e. one ridge), where the file minutiae is type `e` and the search minutiae is type `b`. The search vector is effectively shifted one place to the right by adjusting all the FILE print references. Condition `s` is the converse, that is, the file minutiae is `b` while the search minutiae is `e`. "Shifted" scores can arise only if the central minutiae are of different types. If they are, and both the aligned and shifted matches given sufficiently high totals, then there is no objection to BOTH matches, that is, with and without a shift, forming entries in the Level 2 score table, and being passed on for further processing. If no minutiae pairs pass the Level 2 threshold score, processing is terminated and a zero score returned.
(5) Level 3: Full vector matching: Level 3 examines each of the search/file minutiae pairings (call them "base pairings") that passed level 2 in turn. For each pair the corresponding pair of topological code vectors are passed to subroutine "FULLMATCH". FULLMATCH incorporates a more detailed and sophisticated topological vector matching process, including:
(a) the use of crude distance tests,
(b) score reduction for dependent pairings.
The FULLMATCH scoring procedure is very similar to that disclosed in my above-identified patents within the vector matching routines of MATCH 4 and LM6.
However, FULLMATCH performs one additional function here. For each vector match undertaken FULLMATCH returns a list of further search/file minutiae pairings, derived from the vector match through reference to the "associated minutiae reference numbers". These further pairings represent other minutiae on the search and file prints which are topologically connected to the base pairing in the same way, and through corresponding ridge explorations. These further search/file minutiae pairings are denoted "pairs connected to the base minutiae pair".
FIG. 8 illustrates the returning of a pairs list from FULLMATCH.
After the use of FULLMATCH the vector comparisons that score above a threshold--Filter 3--are stored in a temporary table (Temporary Table 3), and the associated lists of connected pairs are retained for further use.
For each minutiae pair appearing in Temporary Table 3, a "1st order neighborhood" score is calculated by adding to its own vector match score the vector match scores for all the connected pairs returned from FULLMATCH. The "1st order neighborhood" score thus reflects not only how well the base vectors matched up, but also reflects how similar the vectors corresponding to all connected pairs were.
Then "2nd order neighborhood" scores are calculated for each base pair, simply adding together the "1st order neighborhood" scores for all the connected minutiae pairs.
The final version of Table 3 is constructed by reordering this information in descending order of the 2nd order neighborhood scores. A high composite neighborhood score provides a strong indication not only that the underlying vector match was a good one, but also that the minutiae in this pair are in fact topologically connected, in a manner consistent on both file and search prints, with a dense cluster of other high scoring minutiae pairs.
FIG. 9 shows the detailed matcher output of two prints under comparison, and the final version of Table 3 is printed out in full.
(6) Level 4: Exhaustive cluster formation: Minutiae pairs from Table 3 are lifted in sequence and used to generate exhaustively connected topological clusters. These clusters are recorded in sequence in "Table 4". The conceptual approach is to establish, in clusters, search/file minutiae pairings which are all connected together topologically.
The rules under which this general procedure is carried out are:
(a) A new entry from Table 3 is first checked against existing entries in Table 4 (from previously generated clusters) and forms the basis for generation of a new cluster if, and only if, it has not already appeared. The object of this rule is to prevent duplication of effort that would result from starting a new cluster from a pairing already included within some previous cluster.
(b) Once a cluster has been opened, no file index or search index is allowed to be repeated within the cluster. That avoids going over ground already covered within that cluster, and also avoids any file or search minutiae being matched against two different minutiae in the other print.
(c) In order for the clusters to be topologically exhaustive, pairings can be added whether or not they appeared in Table 3 (i.e. had a vector match score above the Level 3 threshold). However, only pairings that appeared in level 3 will be used to start the generation of a new cluster.
(d) Once a cluster is exhausted, its length is checked against a run time parameter--Filter 4--which specifies the minimum number of minutiae pairs to form a reportable cluster. If it is not large enough the cluster is deleted.
FIG. 10 shows a printout of Table 4, revealing a number of different clusters. The cluster score in each case is calculated as the sum of the second order neighborhood scores for each search/file minutiae pairing within the cluster.
(7) Cluster combination routine: A cluster combination routine is included to boost match scores in cases where two or more portions of the prints may match up quite well, but where these regions are topologically disconnected (e.g. by scars running across the fingers).
Cluster combination follows the following rules. First the best cluster from Table 4 is copied (into "Final" Table). Then each other cluster (if there are any) is examined in turn. These subsequent clusters are deemed to be either:
(a) Disjoint: None of their file indices or search indices appear in the current (possibly already extended) version of "final".
(b) Overlapping and non-contradictory: Some of the search/file minutiae pairings already appear in "final" (overlapping); but no file or search pairings appear with different pairings (i.e. non-contradictory).
(c) Contradictory: At least one of the search or file minutiae appears in "final" with a different mate.
Depending on which of these cases arises, "final" may be extended. The rules are:
(a) Disjoint cluster: add the whole cluster into "final" if the root minutiae pairing is distance compatible with all the existing entries in "final".
(b) Overlapping and non-contradictory: add in all minutiae pairings not already in "final".
(c) Contradictory: discard whole cluster.
FIG. 11 shows the final combined cluster produced during the print comparison following through from FIGS. 9 and 10.
(8) Final score calculation: The "second order neighborhood" scores are then summed for the best cluster, which may have been extended through the cluster combination stage. This composite score is then normalized to take account of the information content of both the search and file prints.
The effect and purpose of normalization, of course, is to correct high raw scores which resulted from information rich mismatches and which might have beaten down mate scores from very poor quality prints.
FIG. 12 shows a full table of matcher parameters, with reasonable (but not necessarily optimal) values. Optimal parameter tuning will depend heavily on the operational context and performance criteria.
The matching algorithm described herein is attached hereto as Appendix A, which is proprietary and protected by copyright.
While preferred embodiments of the invention have been illustrates and described, it will be appreciated that various other embodiments, adaptations and modifications of the invention will be readily apparent to those skilled in the art. ##SPC1##
Claims
What is claimed is:
1. In a fingerprint recognition method in which images of fingerprints are electronically processed to provide an electronic image of ridge lines and minutiae points, said minutiae points including ridge endings and ridge bifurcations, with the positions of said minutiae points and a sequence of reference numbers being recordable in a storage medium, wherein each reference number (N) is arbitrarily assigned for each minutiae point, each of said ridge lines having a local ridge flow direction, respectively, the improvement comprising: at each respective minutiae point projecting a generating line at a predetermined angle which is transverse to said local ridge flow direction, said generating line having a length sufficient to span a predetermined number of ridge lines to each side of each said minutiae point, respectively, for each generating line, from the point of crossing of said projected generating line with ridge lines within said span for said each minutiae point, exploring, in two directions, along any crossed ridge line from said generating line to the first occurring topological event in each of said two directions, respectively, and assigning a type code (T) to each said first occurring topological event, respectively, and generating one topological event code vector for each respective minutiae point, each topological event code vector being comprised of an ordered sequence of topological type codes (T) and reference numbers (N) for the minutiae points encountered during exploration of each ridge, for all the ridges intersected by said generating line.
2. The method defined in claim 1 including the step of storing said topological event code vectors in a machine searchable database.
3. The method defined in claim 1 wherein said generating lines are offset from the respective minutiae points, and are orthogonal to said local ridge flow direction, respectively.
4. In a fingerprint recognition method in which images of fingerprints are electronically processed to provide an electronic image of ridge lines and minutiae points, said minutiae points including ridge endings and ridge bifurcations, with the positions of said minutiae points and a sequence of reference numbers being recordable in a storage medium, wherein each reference number (N) is arbitrarily assigned for each minutiae point, each of said ridge lines having a local ridge flow direction, respectively, the improvement comprising: at each respective minutiae point projecting a generating line at a predetermined angle which is transverse to said local ridge flow direction, said generating line having a length sufficient to span a predetermined number of ridge lines to each side of each said minutiae point, respectively, for each generating line, from the point of crossing of said projected generating line with ridge lines within said span for said each minutiae point, exploring, in two directions, along any crossed ridge line from said generating line to the first occurring topological event in each of said two directions, respectively, and assigning a type code (T) to each said first occurring topological event, respectively, and generating one topological event code vector for each respective minutiae point, each topological event code vector being comprised of an ordered sequence of topological type codes (T) and reference numbers (N) for the minutiae points encountered during exploration of each ridge, for all the ridges intersected by said generating line, storing said topological event code vectors in a machine searchable data base, producing, for each respective minutiae point in an unknown or latent fingerprint, a topological event code vector comprised of an ordered sequence topological type codes (T) and reference numbers (N), and identifying the maximal topologically connected cluster of minutiae points within one of the fingerprints in said machine searchable database for which there exists a matching cluster of minutiae points within the unknown or latent fingerprint and indicating when the topological relationships among the set of minutiae within said matching cluster are substantially identical.
5. The method defined in claim 4, including selecting an initial minutiae pairing, one from the file print and one from the unknown or latent fingerprint and making an initial comparison of the topological event code vector of the unknown or latent fingerprint with topological event code vectors stored in said machine searchable database to determine the number of times matching topological type codes (T) appear in similar positions in the topological event code vectors of the unknown or latent fingerprints stored in said machine searchable database, and determining if said number of times exceeds a predetermined threshold.
6. The method defined in claim 5, wherein during said initial comparison one of said topological event code vectors is shifted relative to the one with which it is being compared to determine the optimum alignment of the topological event code vectors stored in said machine searchable database with the topological event code vectors of said unknown or latent fingerprint.
7. The method defined in claim 6, wherein each set of topological event code vectors of fingerprints in said machine searchable database which have type code (T) in matching positions to the type codes in the topological code vectors for the unknown or latent fingerprints are further compared to locate other minutiae pairings which are connected to the initial minutiae pairing.
8. The method defined in claim 7, including further comparing of pairs of minutiae pairings to form clusters of minutiae pairings which are topologically connected together and in which no reference number (N) is repeated within the cluster.
9. The method defined in claim 8, including further comparing of numbers of minutiae pairings forming a cluster against a predetermined minimum number of minutiae pairs.
10. In a fingerprint recognition and retrieval system in which fingerprint images are electronically processed to provide a skeleton image of ridge lines and minutiae points constituted by ridge endings and bifurcations, with the spatial positions of said minutiae points and a sequence of reference numbers being recorded in a storage medium, wherein each reference number (N) is arbitrarily assigned for each minutiae point, each of said ridge lines having a local ridge flow direction, respectively, the improvement comprising: means for projecting a vector generating line at a predetermined angle transverse to said local ridge flow direction at each minutiae point, respectively, said generating line having a length sufficient to span a predetermined number of ridges to each side of each said minutiae points, respectively, means for tracing along each ridge crossed by said vector generating line in first and second directions along each ridge line from the point of crossing of said vector generating line with each crossed ridge within the span for said each minutiae point along any crossed ridge line from said vector generating line to the first occurring topological event and assigning a type code (T) to said topological event, means for generating a topological event code vector for each minutiae comprised of an ordered sequence of topological event type codes (T) and reference number (N) for each minutiae encountered during the ridge tracing, for all the ridges intersected by said vector generating line, and means for storing said topological event code vectors in a machine searchable database.
11. The system defined in claim 10 wherein said generating lines are offset from said minutiae points and orthogonal to said local ridge flow direction.
12. The system defined in claim 10 wherein one of said fingerprints is an unknown fingerprint and the topological event code vectors for said unknown fingerprint are generated for matching with topological event code vectors of fingerprints stored in said machine searchable database, further including: comparison means having means for identifying the maximal topologically connected cluster of minutiae points within one fingerprint for which there exists a matching cluster of minutiae points within the fingerprint under comparison and wherein the topological relationships among the set of minutiae within said matching cluster are substantially identical.
13. In a fingerprint recognition and retrieval method in which fingerprint images are processed to provide an image of ridge lines and minutiae points constituted by ridge endings and bifurcations, with a reference number (N) for each minutiae point being recorded in a storage medium, each of said ridge lines having a local ridge flow direction in the vicinity of each minutiae, respectively, the improvement comprising: projecting a vector generating line at an orthogonal angle to said local ridge flow direction at each minutiae point, respectively, said vector generating line being offset from said minutiae point and having a length sufficient to span a predetermined number of ridges to each side of each said minutiae point, respectively, for each said vector generating line, tracing along any crossed ridge line from said projected generating line to the first occurring topological event and assigning a type code (T) to said topological event, generating a topological event code vector for each vector generating line, each topological event code vector being comprised of a sequence of topological type event codes (T) for the minutiae encountered during the ridge tracing and the reference number (N) for that minutiae, for all the ridges intersected by said vector generating line, storing each said topological event code vector for each fingerprint in a machine searchable database, and identifying the maximal topologically connected cluster of minutiae points within an unknown one of said fingerprints for which there exists a matching cluster of minutiae points within the fingerprint under comparison and wherein the topological relationships among the set of minutiae within said matching clusters are substantially identical.
14. The method defined in claim 13, including selecting an initial minutiae pairing, one from the file print and one from the unknown or latent fingerprint and making an initial comparison of the topological event code vector of the unknown or latent fingerprint with topological event code vectors stored in said machine searchable database to determine the number of times matching topological type codes (T) appear in similar positions in the topological event code vectors, of the unknown or latent fingerprints stored in said machine searchable database, and determining if said number of times exceeds a predetermined threshold.
15. The method defined in claim 14, wherein during said initial comparison one of said topological event code vectors is shifted relative to the one with which it is being compared to determine the optimum alignment of the topological event code vectors stored in said machine searchable database with the topological event code vectors of said unknown or latent fingerprint.
16. The method defined in claim 10, wherein each set of topological event code vectors of fingerprints in said machine searchable database which have type code (T) in matching positions to the type codes in the topological code vectors for the unknown or latent fingerprints are further compared to locate other minutiae pairings which are connected to the initial minutiae pairing.
17. The method defined in claim 16, including further comparing of pairs of minutiae pairings to form clusters of minutiae pairings which are topologically connected together and in which no reference number (N) is repeated within the cluster.
18. The method defined in claim 17, including further comparing of numbers of minutiae pairings forming a cluster against a predetermined minimum number of minutiae pairs.
19. In a fingerprint recognition and retrieval method in which the spatial positions of fingerprint minutiae points and a reference number for each minutiae point are recorded in a storage medium, the improvement comprising: determining the local ridge flow direction in the vicinity of each minutiae point defined by ridge endings and ridge bifurcations, projecting a vector generating line at an angle orthogonal to said local ridge flow direction and offset at each minutiae point, said vector generating line having a length sufficient to span a predetermined number of ridges to each side of each said minutiae point, respectively, tracing in two directions along any crossed ridge line from each vector generating line, respectively, to the first occurring topological event along the ridge line being traced and assigning a type code (T) to said topological event, generating a topological event code vector for each minutiae comprised of an ordered sequence of the reference number (N) and topological type event codes (T) for each topologically occurring event encountered during the ridge tracing, for all of the ridges intersected by said vector generating line, storing each said topological event code vector in a machine searchable database, and identifying the maximal topologically connected cluster of minutiae points within an unknown one of said fingerprints for which there exists a matching cluster of minutiae points within the fingerprint under comparison and wherein the topological event code vectors among the set of minutiae within said matching cluster are substantially identical.
20. In a fingerprint recognition and retrieval system in which the positions of fingerprint minutiae points and a sequence of reference numbers are recorded in a storage medium, wherein each reference number (N) is arbitrarily assigned for each minutiae point, said fingerprint minutiae points including ridge endings and ridge bifurcations, the improvement comprising: means for determining the local ridge flow direction in the vicinity of each minutiae point defined by ridge endings and ridge bifurcations, means for projecting a vector generating line at an orthogonal angle to said local ridge flow direction and offset at each ridge ending and ridge bifurcation, respectively, each said generating line having a length sufficient to span a predetermined number of ridges to each side of each said minutiae point, respectively, means for tracing in first and second directions along each ridge from the point of crossing of said projected vector generating line with ridges in two directions along each side of any crossed ridge line to the first occurring topological event in each of said first and second directions and assigning a type code (T) to said topological event, respectively, means for generating a topological event code vector for each minutiae comprised of the reference number (N) for said each minutiae, the directions of said tracing, the number of each ridge traced within the span for said minutiae, and the topological type code (T) for the minutiae encountered during said tracing, means for storing each said topological event code vector for each fingerprint in a machine searchable database, and means for identifying the maximal topologically connected cluster of minutiae points within an unknown fingerprint with one of said fingerprints for which there exists a matching cluster of minutiae points within the fingerprint under comparison and wherein the topological event code vectors among the set of minutiae within said matching cluster are substantially identical.
Patent Citations (3)
Non-Patent Literature (2)
- A Topological Approach to the Matching of Single Fingerprints: Development of Algorithms for use on Rolled Impressions Sparrow et al National Bureau of Standards Publication NBS 500-124 May 1985.
- A Topological Approach to the Matching of Single Fingerprints: Development of Algorithms for use on Latent Fingermarks Sparrow et al National Bureau of Standards Publication NBS 500-126 Oct. 1985.