System and method for determining likely identity in a biometric database

• US 7,203,343 B2
• Filed: 09/21/2001
• Issued: 04/10/2007
• Est. Priority Date: 09/21/2001
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Broder, Andrei Z., Manasse, Mark S.
• Primary Examiner(s): Mehta; Bhavesh M.
• Assistant Examiner(s): Seth; Manav
• Application Number:
  US09/960,583
• Publication Number:
  US 20030061233A1
• Time in Patent Office: 2,027 Days
• Field of Search: 382115-118, 382124-127, 382/190, 382/195, 382/209, 382/217, 382/218, 382/173, 707/4, 707/103.R, 713/170
• US Class Current: 382/115
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/211 Selection of the most significant subset of features
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches
• CPC Class Codes: G06V 40/10 Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A system and method for finding one or more target biometric samples that are similar to or match a query biometric sample. A query feature vector is generated from a query biometric vector. The query biometric vector represents the query biometric sample as a set of characteristics. The characteristics are either invariable or variable. The query feature vector comprises a plurality of features which are derived from the query biometric vector using a process that includes canonicalization of the characters in the biometric vector. The query feature vector is compared to a plurality of similarly created target feature vectors, each target feature vector representing a respective target biometric sample. A target biometric sample is a potential match to the query biometric sample when a threshold number of features in the corresponding target feature vector are identical to features in the query biometric vector.

Claims

1. A method for finding one or more target biometric samples that are similar to or match a query biometric sample, comprising:

generating a query feature vector from a query biometric vector that represents said query biometric sample, said query feature vector comprising a plurality of features and said query biometric vector comprising a set of characteristics; and

comparing said query feature vector to a plurality of target feature vectors, each target feature vector representing a respective target biometric sample;

wherein,

a target biometric sample is a potential match to said query biometric sample when a threshold number of features in the target feature vector that corresponds to said target biometric sample are identical to features in said query feature vector, wherein the generating comprises;

extracting a set of tiles that represents said query biometric sample, each tile including a plurality of characteristics;

assigning an identification element to each said tile in said set of tiles;

selecting a predetermined number of the identification elements;

partitioning the selected identification elements into a plurality of partitioned groups; and

applying a fingerprint function to each partitioned group to generate a set of features, said set of features representing said query feature vector.

2. The method of claim 1, wherein said extracting step further comprises:

canonicalizing each characteristic associated with said query biometric sample to create a plurality of canonicalized characteristics; and

obtaining a pseudo randomly selected subset of said plurality of canonicalized characteristics to form each said plurality of characteristics included in said set of tiles.

3. The method of claim 2, wherein a characteristic associated with said query biometric sample is a variable characteristic and said canonicalizing step includes expansion of said variable characteristic using a predetermined function.

4. The method of claim 2, wherein said canonicalization of each said characteristic associated with said query biometric sample includes application of a respective weight to each said characteristic, the respective weight determining a number of copies of said characteristic that are present in said plurality of canonicalized characteristics.

5. The method of claim 1, wherein each target feature vector in said plurality of target feature vectors is generated by:

extracting a set of tiles that represent a respective target biometric sample, each tile including a plurality of characteristics;

assigning an identification element to each said tile in said set of tiles;

selecting a predetermined number of the identification elements;

partitioning the selected identification elements into a plurality of groups; and

applying a fingerprint function to each group to generate a set of features, said set of features representing said target feature vector.

6. The method of claim 5, wherein said extracting step further comprises:

canonicalizing the characteristics associated with said respective biometric sample to create a plurality of canonicalized characteristics; and

obtaining a pseudo randomly selected subset of said plurality of canonicalized characteristics to form each said plurality of characteristics included in said set of tiles.

7. The method of claim 6, wherein a characteristic associated with said respective biometric sample is a variable characteristic and said canonicalizing step includes expansion of said variable characteristic using a predetermined function.

8. The method of claim 6, wherein said canonicalization of each said characteristic associated with said respective biometric sample includes application of respective weight to each said characteristic, the respective weight determining a number of copies of said characteristic that are present in said plurality of canonicalized characteristics.

9. The method of claim 1, wherein the selecting includes selecting the identification elements using a selection function.

10. The method of claim 5, wherein the selecting includes selecting the identification elements using a selection function.

11. The method of claim 1, wherein each of the set of features is a one-way hash of a group.

12. The method of claim 5, wherein each of the set of features is a one-way hash of a group.

13. The method of claim 1, wherein the comparing includes:

extracting from a database a set of target feature vectors, each extracted target feature vector including at least one feature that is in common with a feature in said query feature vector;

locating each target feature vector in the set of target feature vectors in a count hash table, that count hash table including target feature vector identifications corresponding to target feature vectors that share at least one feature in common with the target feature vector, the count hash table including a count of matching features for each target feature vector represented by the table; and

incrementing the count of matching features for each located target feature identification.

14. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a data structure including a plurality of target feature vectors, each target feature vector representing a respective target biometric sample;

a module for finding one or more said respective target biometric samples that are similar to or match a query biometric sample, said module including instruction for;

generating a query feature vector from a query biometric vector that represents said query biometric sample, said query feature vector comprising a plurality of features and said query biometric vector comprising a set of characteristics; and

comparing said query feature vector to said plurality of target feature vectors;

wherein,

a target biometric sample is a potential match to said query biometric sample when a threshold number of features in the target feature vector that corresponds to said target biometric sample are identical to features in said query feature vector, wherein the instructions for generating comprise;

instructions for extracting a set of tiles that represents said query biometric sample, each tile including a plurality of characteristics;

instructions for assigning an identification element to each said tile in said set of tiles;

instructions for partitioning the selected identification elements into a plurality of partitioned groups; and

instruction for applying a fingerprint function to each partitioned group to generate a set of features, said set of features representing said query feature vector.

15. The computer program product of claim 14, wherein said instructions for extracting further comprise:

instructions for canonicalizing each characteristic associated with said query biometric sample to create a plurality of canonicalized characteristics; and

instructions for obtaining a pseudo randomly selected subset of said plurality of canonicalized characteristics to form each said plurality of characteristics included in said set of tiles.

16. The computer program product of claim 15, wherein a characteristic associated with said query biometric sample is a variable characteristic and said instructions for canonicalizing includes expansion of said variable characteristic using a predetermined function.

17. The computer program product of claim 15, wherein said instructions for canonicalization for each said characteristic associated with said respective biometric sample includes application of a respective weight to each said characteristic, the respective weight determining a number of copies of said characteristic that are present in said plurality of canonicalized characteristics.

18. The computer program product of claim 14, wherein said module further includes instructions for creating each target feature vector in said plurality of target feature vectors, said instructions for creating including:

instructions for extracting a set of tiles that represent a respective target biometric sample, each tile including a plurality of characteristics;

instructions for assigning an identification element to each said tile in said set of tiles;

instructions for selecting a predetermined number of the identification elements;

instructions for partitioning the selected identification elements into a plurality of groups; and

instructions for applying a fingerprint function to each group to generate a set of features, said set of features representing said target feature vector.

19. The computer program product of claim 18, wherein said instructions for extracting further comprise:

instructions for canonicalizing the characteristics associated with said respective biometric sample to create a plurality of canonicalized characteristics; and

instructions for obtaining a pseudo randomly selected subset of said plurality of canonicalized characteristics to form each said plurality of characteristics included in said set of tiles.

20. The computer program product of claim 19, wherein a characteristic associated with said respective biometric sample is a variable characteristic and said instructions for canonicalizing include expansion of said variable characteristic using a predetermined function.

21. The computer program product of claim 19, wherein said instructions for canonicalization of each said characteristic associated with said respective biometric sample includes application of a respective weight to each said characteristic, the respective weight determining a number of copies of said characteristic that are present in said plurality of canonicalized characteristics.

22. The computer program product of claim 14, wherein said instructions for selecting include instructions for selecting the identification elements using a selection function.

23. The computer program product of claim 18, wherein said instructions for selecting include instructions for selecting the identification elements using a selection function.

24. The computer program product of claim 14, wherein each of the set of features is a one-way hash of a group.

25. The computer program product of claim 18, wherein each of the set of features is a one-way hash of a group.

26. The computer program product of claim 14, wherein the instructions for comparing include:

instructions for extracting from said data structure a set of target feature vectors, each extracted target feature vector including at least one feature that is in common with a feature in said query feature vector;

instructions for locating each target feature vector in the set of target feature vectors in a count hash table, the count hash table including target feature vector identifications corresponding to target feature vectors that share at least one feature in common with the target feature vector, the count hash table including a count of matching features for each target feature vector represented by the table; and

instructions for incrementing the count of matching features for each located target feature identification.