Fingerprint matching using virtual minutiae

1. A method for matching fingerprints using virtual minutiae, the method comprising:

obtaining data indicating (i) a list of search minutiae from a search fingerprint and (ii) a list of reference minutiae from a reference fingerprint;

determining a matched area shared between the search fingerprint image and the reference fingerprint based on the list of search minutiae and the list of reference minutiae;

generating a list of virtual search minutiae for the list of search minutiae based on the matched area of the search fingerprint image;

generating a list of virtual reference minutiae for the list of reference minutiae based on the matched area of the reference fingerprint image; and

computing a similarity score between the search fingerprint and the reference fingerprint based at least on comparing the list of virtual search minutiae and the list of virtual search minutiae.

2. The method of claim 1 , further comprising:

generating (i) a set of search octant feature vectors for each search minutia from the list of search minutiae, and (ii) a set of reference octant feature vectors for each reference minutia from the list of reference minutiae;

generating a plurality of possible mated minutiae based at least on pairing an octant neighborhood of each of the list of search minutiae with the octant neighborhood of each of the list of reference minutiae, wherein:

the octant neighborhood includes a combination of (i) a neighborhood formed between the list of virtual search minutiae and the list of search minutiae, and (ii) a neighborhood formed between the list of virtual reference minutiae and the list reference minutiae, and

each of the plurality of possible mated minutiae includes (i) a search minutia from the list of search minutiae, and (ii) a reference minutia from the list of reference minutiae; and

wherein the similarity score between the search fingerprint image and the reference fingerprint image is based on comparing minutiae pairs of the plurality of possible mated minutiae.

3. The method of claim 1 , further comprising:

identifying an overlapping region containing a portion of the search fingerprint and a portion of the reference fingerprint;

applying a coordinate grid including a plurality of cross points to the overlapping region;

placing a virtual search minutia for the list of search minutiae on each of the plurality of cross points of the applied regular grid over the overlapping region;

placing a virtual reference minutia for the list of reference minutiae on each of the plurality of cross points of the applied regular grid over the overlapping region; and

generating a set of virtual search octant feature vectors for each virtual search minutia from the list of virtual search minutiae;

generating a set of virtual reference octant feature vectors for each virtual reference minutia from the list of virtual reference minutiae.

4. The method of claim 3 , wherein generating the list of virtual minutiae for each of the list of search minutiae and the list of file minutiae is based at least on a density of the plurality of cross points within the overlapping region.

5. The method of claim 1 , wherein computing the similarity score between the search fingerprint and the reference fingerprint comprises:

computing a first score between the list of search minutiae and the list of reference minutiae, the first score representing a similarity between the list of search minutiae and the list of reference minutiae;

computing a second score based at least on comparing the list of virtual search minutiae and the list of virtual reference minutiae, the second score representing a similarity between the list of virtual search minutiae and the list of virtual reference minutiae; and

combining the first score and the second score to compute the similarity score.

6. The method of claim 1 , wherein combining the first score and the second score comprises assigning respective weights to each the first score and the second score.

7. The method of claim 6 , wherein assigning the respective weights to each of the first and second scores comprises assigning a respective linear weights to each of the first and second scores.

8. A system comprising:

one or more computers; and

one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:

obtaining data indicating (i) a list of search minutiae from a search fingerprint and (ii) a list of reference minutiae from a reference fingerprint;

determining a matched area shared between the search fingerprint image and the reference fingerprint based on the list of search minutiae and the list of reference minutiae;

generating a list of virtual search minutiae for the list of search minutiae based on the matched area of the search fingerprint image;

generating a list of virtual reference minutiae for the list of reference minutiae based on the matched area of the reference fingerprint image; and

computing a similarity score between the search fingerprint and the reference fingerprint based at least on comparing the list of virtual search minutiae and the list of virtual search minutiae.

9. The system of claim 8 , wherein the operations further comprise:

generating (i) a set of search octant feature vectors for each search minutia from the list of search minutiae, and (ii) a set of reference octant feature vectors for each reference minutia from the list of reference minutiae;

generating a plurality of possible mated minutiae based at least on pairing an octant neighborhood of each of the list of search minutiae with the octant neighborhood of each of the list of reference minutiae, wherein:

the octant neighborhood includes a combination of (i) a neighborhood formed between the list of virtual search minutiae and the list of search minutiae, and (ii) a neighborhood formed between the list of virtual reference minutiae and the list reference minutiae, and

each of the plurality of possible mated minutiae includes (i) a search minutia from the list of search minutiae, and (ii) a reference minutia from the list of reference minutiae; and

wherein the similarity score between the search fingerprint image and the reference fingerprint image is based on comparing minutiae pairs of the plurality of possible mated minutiae.

10. The system of claim 8 , wherein the operations further comprise:

identifying an overlapping region containing a portion of the search fingerprint and a portion of the reference fingerprint;

applying a coordinate grid including a plurality of cross points to the overlapping region;

placing a virtual search minutia for the list of search minutiae on each of the plurality of cross points of the applied regular grid over the overlapping region;

placing a virtual reference minutia for the list of reference minutiae on each of the plurality of cross points of the applied regular grid over the overlapping region; and

generating a set of virtual search octant feature vectors for each virtual search minutia from the list of virtual search minutiae;

generating a set of virtual reference octant feature vectors for each virtual reference minutia from the list of virtual reference minutiae.

11. The system of claim 10 , wherein generating the list of virtual minutiae for each of the list of search minutiae and the list of file minutiae is based at least on a density of the plurality of cross points within the overlapping region.

12. The system of claim 8 , wherein computing the similarity score between the search fingerprint and the reference fingerprint comprises:

computing a first score between the list of search minutiae and the list of reference minutiae, the first score representing a similarity between the list of search minutiae and the list of reference minutiae;

computing a second score based at least on comparing the list of virtual search minutiae and the list of virtual reference minutiae, the second score representing a similarity between the list of virtual search minutiae and the list of virtual reference minutiae; and

combining the first score and the second score to compute the similarity score.

13. The system of claim 8 , wherein combining the first score and the second score comprises assigning respective weights to each the first score and the second score.

14. The system of claim 13 , wherein assigning the respective weights to each of the first and second scores comprises assigning a respective linear weights to each of the first and second scores.

15. A non-transitory computer-readable storage device encoded with computer program instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

obtaining data indicating (i) a list of search minutiae from a search fingerprint and (ii) a list of reference minutiae from a reference fingerprint;

determining a matched area shared between the search fingerprint image and the reference fingerprint based on the list of search minutiae and the list of reference minutiae;

generating a list of virtual search minutiae for the list of search minutiae based on the matched area of the search fingerprint image;

generating a list of virtual reference minutiae for the list of reference minutiae based on the matched area of the reference fingerprint image; and

computing a similarity score between the search fingerprint and the reference fingerprint based at least on comparing the list of virtual search minutiae and the list of virtual search minutiae.

16. The device of claim 15 , wherein the operations further comprise:

generating (i) a set of search octant feature vectors for each search minutia from the list of search minutiae, and (ii) a set of reference octant feature vectors for each reference minutia from the list of reference minutiae;

generating a plurality of possible mated minutiae based at least on pairing an octant neighborhood of each of the list of search minutiae with the octant neighborhood of each of the list of reference minutiae, wherein:

the octant neighborhood includes a combination of (i) a neighborhood formed between the list of virtual search minutiae and the list of search minutiae, and (ii) a neighborhood formed between the list of virtual reference minutiae and the list reference minutiae, and

each of the plurality of possible mated minutiae includes (i) a search minutia from the list of search minutiae, and (ii) a reference minutia from the list of reference minutiae; and

wherein the similarity score between the search fingerprint image and the reference fingerprint image is based on comparing minutiae pairs of the plurality of possible mated minutiae.

17. The device of claim 16 , wherein the operations further comprise:

identifying an overlapping region containing a portion of the search fingerprint and a portion of the reference fingerprint;

applying a coordinate grid including a plurality of cross points to the overlapping region;

placing a virtual search minutia for the list of search minutiae on each of the plurality of cross points of the applied regular grid over the overlapping region;

placing a virtual reference minutia for the list of reference minutiae on each of the plurality of cross points of the applied regular grid over the overlapping region; and

generating a set of virtual search octant feature vectors for each virtual search minutia from the list of virtual search minutiae;

generating a set of virtual reference octant feature vectors for each virtual reference minutia from the list of virtual reference minutiae.

18. The device of claim 17 , wherein generating the list of virtual minutiae for each of the list of search minutiae and the list of file minutiae is based at least on a density of the plurality of cross points within the overlapping region.

19. The device of claim 15 , wherein computing the similarity score between the search fingerprint and the reference fingerprint comprises:

computing a first score between the list of search minutiae and the list of reference minutiae, the first score representing a similarity between the list of search minutiae and the list of reference minutiae;

computing a second score based at least on comparing the list of virtual search minutiae and the list of virtual reference minutiae, the second score representing a similarity between the list of virtual search minutiae and the list of virtual reference minutiae; and

combining the first score and the second score to compute the similarity score.

20. The device of claim 15 , wherein combining the first score and the second score comprises assigning respective weights to each the first score and the second score.