Fingerprint minutiae matcher

Claim 1

A method employing a programmed computer for comparing the minutiae of a search fingerprint (the "search minutiae") with the minutiae of a file fingerprint (the "file minutiae") to determine if the search fingerprint closely resembles the file fingerprint, including the steps of pairing mating search (S1,S2 ...) and file (F1,F2 ...) minutiae, computing scores (S M ) or individual pairs of mating search and file minutiae (S4,F2; S9,F14 ...), and summing the computed scores (S M ) to obtain a final match score indicative of the overall resemblance of the search fingerprint to the file fingerprint, the method being characterised by: a) prior to the pairing step, rotating and translating the search and file fingerprints relatively to one another (N R ) to determine a selected rotation (a) and translation (△X, ΔY) which most nearly brings the search minutiae (S1,S2...) into registration with the file (F1,F2...) minutiae (Figure 5, MM*); b) carrying out the step of pairing mating search and file minutiae (S4, F2; S9, F14...) based upon the selected rotation and translation; and c) computing the individual minutia score (S M ) for each search minutia (S1 ,S2 ...) that has a mating file minutia based on the spatial and angular relationship between the other mating file and search minutiae (Tables 7(c), 7(a)) located within a neighbourhood of each such search minutia (S1,S2...), the step of computing an individual score comprising the steps of (c1) computing a variance (σ 2 ) of the spatial and angular relationships between file and search minutiae of the neighbouring pairs of file and search minutiae (Tables 7(b), 7(d) and (c2) comprising an individual minutiae score (S M ) based upon the number of neighbouring pairs (N M ) and the variances (σ 2 ) of such pairs.

Claim 2

A method employing a programmed computer for comparing the minutiae of a search fingerprint (the "search minutiae") with the minutiae of a file fingerprint (the "file minutiae") to determine if the search fingerprint closely resembles the file fingerprint, including the steps of pairing mating search (S1,S2 ...) and file (F1,F2 ...) minutiae, computing scores (S M ) or individual pairs of mating search and file minutiae (S4,F2; S9,F14 ...), and summing the computed scores (S M ) to obtain a final match score indicative of the overall resemblance of the search fingerprint to the file fingerprint, the method being characterised by: a) prior to the pairing step, rotating and translating the search and file fingerprints relatively to one another (N R ) to determine a selected rotation (a) and translation (△X, ΔY) which most nearly brings the search minutiae (S1,S2...) into registration with the file (F1,F2...) minutiae (Figure 5, MM*); b) carrying out the step of pairing mating search and file minutiae (S4, F2; S9, F14...) based upon the selected rotation and translation; and c) computing the individual minutia score (S M ) for each search minutia (S1 ,S2 ...) that has a mating file minutia based on the spatial and angular relationship between the other mating file and search minutiae (Tables 7(c), 7(a)) located within a neighbourhood of each such search minutia (S1,S2...), the step of computing an individual score comprising the steps of (c1) computing a variance (σ 2 ) of the spatial and angular relationships between file and search minutiae of the neighbouring pairs of file and search minutiae (Tables 7(b), 7(d) and (c2) comprising an individual minutiae score (S M ) based upon the number of neighbouring pairs (N M ) and the variances (σ 2 ) of such pairs.

Claim 6

A method according to any of the preceding claims, wherein the variances are computed as the average of the sum of the squares of translational and angular differences between file and search minutiae of the respective pairs.

Claim 7

A method according to any of the preceding claims, further comprising: (a) sorting the search minutiae into angle order; (b) finding the closest neighbours for each search minutia; (c) sorting the file minutiae into angle order; and (d) computing maximum and minimum coordinates for the file minutiae.

Claim 8

A method according to any of claims 1 to 3, wherein step a) comprises terminating the comparison between the minutiae of a search fingerprint and the minutiae of a file fingerprint whenever the degree of registration of the search minutiae with the file minutiae fails to exceed an operator selected threshold.

Claim 9

A method according to any of the preceding claims, wherein the step of rotating and translating comprises: (a) rotating the search minutiae through a preselected set of rotations; (b) for each rotated set of search minutia constructing a histogram showing the number of coincident search and file minutiae for various translations of the search minutiae relative to the file minutiae; and (c) determining the rotation and translation which most nearly brings the search minutia into registration with the file minutiae by comparing the magnitudes of the largest adjacent blocks of entries in each of the histograms.

Claim 10

A method of comparing minutiae of a search fingerprint (search minutiae) with minutiae of a file fingerprint (file minutiae) to determine if the two fingerprints match one another, including the steps of pairing mating search (S1,S2...) and file (F1,F2...) minutiae, computing scores (S M ) for individual pairs of mating search and file minutiae (S4,F2; S9,F14...), and summing the computed scores (S M ) to obtain a final match score indicative of the overall resemblance of the search fingerprint to the file fingerprint, the method being characterised by: (a) prior to the pairing step, relatively rotating the search and file fingerprints through a plurality of discrete rotations (N R ); (b) determining for each rotation (a) a translation (ΔX, ΔY) of the search fingerprint that produces a maximum number (Figure 5) of mating pairs of file and search minutiae; (c) selecting that rotation (a) and translation (ΔX, ΔY) which produces the largest (MM) of the maximum numbers of mating pairs; (d) carrying out the step of pairing mating search and file minutiae (S4,F2; S9,F14 ...) based upon the selected rotation and translation; and (e) for the selected rotation and translation, computing the individual minutiae score (S M , Table 7(e)) for each search minutiae (S4,S9 ...) that has a mating file minutiae (F2,F14 ...) based upon comparisons ( 0 2 , N M , Tables 7(b), 7(d)) of angular and spatial relations of other mating file and search minutiae (Tables 7(a), 7(c)) located in a neighbourhood of each such search minutiae.

Claim 11

A method of comparing minutiae of a search fingerprint (search minutiae) with minutiae of a file fingerprint (file minutiae) to determine if the two fingerprints match one another, including the steps of pairing mating search (S1,S2...) and file (F1,F2...) minutiae, computing scores (S M ) for individual pairs of mating search and file minutiae (S4,F2; S9,F14...), and summing the computed scores (S M ) to obtain a final match score indicative of the overall resemblance of the search fingerprint to the file fingerprint, the method being characterised by: (a) prior to the pairing step, relatively rotating the search and file fingerprints through a plurality of discrete rotations (N R ); (b) determining for each rotation (a) a translation (ΔX, ΔY) of the search fingerprint that produces a maximum number (Figure 5) of mating pairs of file and search minutiae; (c) selecting that rotation (a) and translation (ΔX, ΔY) which produces the largest (MM) of the maximum numbers of mating pairs; (d) carrying out the step of pairing mating search and file minutiae (S4,F2; S9,F14 ...) based upon the selected rotation and translation; and (e) for the selected rotation and translation, computing the individual minutiae score (S M , Table 7(e)) for each search minutiae (S4,S9 ...) that has a mating file minutiae (F2,F14 ...) based upon comparisons ( 0 2 , N M , Tables 7(b), 7(d)) of angular and spatial relations of other mating file and search minutiae (Tables 7(a), 7(c)) located in a neighbourhood of each such search minutiae.

Claim 14

A method according to any of claims 9 to 11, wherein steps a to c comprise selecting pairs of file and search minutiae for which the direction values thereof differ by less than a selected matching threshold; and for each discrete rotation, relatively translating the search and file fingerprints through a number of translations at each of which the file and search minutiae of one of the selected pairs coincide with one another.

Claim 15

A method according to any of claims 9 to 12, wherein the step of computing an individual score comprises the steps of computing a variance of the spatial and angular relationships between file and search minutiae of neighbouring pairs of file and search minutiae; and computing an individual minutiae score based upon the number of neighbouring pairs and the variances of such pairs.