Vector based topological fingerprint matching

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.

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.

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.

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.

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.