Image identification system

• US 20030118218A1
• Filed: 11/16/2001
• Published: 06/26/2003
• Est. Priority Date: 02/16/2001
• Status: Active Grant

• Current Assignee: SAC Technologies, Inc. (Bio-Key International Incorporated)
• Original Assignee: SAC Technologies, Inc. (Bio-Key International Incorporated)
• Inventors: Witting, Benedict, Wendt, Barry, LaCous, Mira Kristina, Brown, Jeffry R., Zarn, Gary Lawrence
• Granted Patent: US 6,895,104 B2
• Time in Patent Office: Days
• US Class Current: 382/124
• CPC Class Codes: G06V 10/993 Evaluation of the quality of the acquired pattern
• CPC Class Codes: G06V 40/1359 Extracting features related to ridge properties; Determining the fingerprint type, e.g. whorl or loop
• CPC Class Codes: G06V 40/1365 Matching; Classification

Abstract

Methods and procedures for improving the performance and reliability of image analysis within an image identification system include a series of image qualification functions designed to quickly process a fraction of available image data and to provide feedback to a system user pertaining to image quality and authenticity. Functions designed to produce image models based on original image data and to catalogue such image models into a searchable database are included in the present invention. The present invention also includes functions for comparing one image model to another. Finally, the present invention provides functions for making a quick determination as to which, if any, of a potential thousands (or more, i.e., millions) of image models within a searchable database exhibit a desired level of similarity, as compared to a target image model.

Claims

1. A method for comparing a first image to a second image, the method comprising:

deriving a first image data set based on the first image and a second image data set based on the second image, wherein the first and second image data sets include a plurality of data elements and are model representations of the first and second images; and

comparing at least one data element in the first image data set with at least one data element in the second image data set.

2. The method of claim 1, further comprising an initial step of:

narrowing the first and second image data sets by eliminating those data elements in one of the first and second image data sets that do not fit within a predetermined qualifying range of deviation from a data element of a same type in the other of the first and second image data sets.

3. The method of claim 1, wherein comparing at least one data element in the first image data set with at least one data element in the second image data set comprises:

comparing at least one data element of a first type from the first image data set to at least one data element of the first type from the second image data set, the first type being one of a plurality of data element types included in the plurality of data elements.

4. The method of claim 3, wherein the first and second images are fingerprint images and the first type of data element is selected from a group consisting of:

bifurcation representations, rod representations, vector segments associated with bifurcation representations, vector segments associated with rod representations, vector segments not associated with bifurcation representations, vector segments not associated with rod representations, microminutia points, and combinations thereof.

5. The method of claim 3, wherein each data element type has at least one defining characteristic and comparing at least one data element of a first type from the first image data set to at least one data element of the first type from the second image data set comprises:

comparing at least one defining characteristic of at least one data element of the first type from the first image data set to a corresponding at least one defining characteristic of at least one data element of the first type from the second image data set.

6. The method of claim 5, wherein comparing at least one defining characteristic of at least one data element of the first type from the first image data set to a corresponding at least one defining characteristic of at least one data element of the first type from the second image data set comprises:

determining an amount of deviation between said at least one defining characteristic of at least one data element of the first type from the first image data set and said corresponding at least one defining characteristic of at least one data element of the first type from the second image data set.

7. The method of claim 6, further comprising:

predetermining a qualifying range of deviation; and

generating a possible match list that indicates data elements from the first and second image data sets wherein the amount of deviation is within the qualifying range of deviation.

8. The method of claim 1, wherein comparing at least one data element in the first image data set with at least one data element in the second image data set comprises:

generating a first count of the plurality of data elements in the first image data set that approximately match the plurality of data elements in the second image data set.

9. The method of claim 8, further comprising:

re-positioning at least one of the first and second image data sets and the plurality of data elements associated therewith; and

generating a second count of the plurality of data elements in the first image data set that approximately match the plurality of data elements in the second image data set.

10. The method of claim 9, further comprising:

repeating the re-positioning step;

generating a plurality of additional counts of the plurality of data elements in the first image data set that approximately match the plurality of data elements in the second image data, wherein each additional count follows a repetition of the re-positioning step; and

identifying a maximum comparison point that corresponds to one of the first, second, and plurality of additional counts that approximates a maximum value.

11. The method of claim 10, further comprising:

predetermining a particular count value, based on a purpose for which the first image is being compared to the second image, that represents a selected level of similarity required for the first and second images to be considered matching; and

providing a positive match indication when the one of the first, second and plurality of additional counts that corresponds to the maximum comparison point is equal to or greater than said particular count value.

12. The method of claim 10, further comprising:

calculating a score that represents a percentage of the plurality of data elements in the first image data set that approximately match the plurality of data elements in the second image data set at the maximum comparison point.

13. The method of claim 12, further comprising:

predetermining a particular score, based on a purpose for which the first image is being compared to the second image, that represents a selected level of similarity required for the first and second images to be considered matching; and

providing a positive match indication when the score associated with the maximum comparison point is equal to or greater than said particular score.

14. The method of claim 10, further comprising:

calculating a probability of relationship value that represents a relationship of match between the plurality of data elements in the first image data set and the plurality of data elements in the second image data set at the maximum comparison point.

15. The method of claim 14, further comprising:

predetermining a particular probability of relationship value, based on a purpose for which the first image is being compared to the second image, that represents a selected level of similarity required for the first and second images to be considered matching; and

providing a positive match indication when the probability of relationship value associated with the maximum comparison point is equal to or greater than said particular probability of relationship value.

16. The method of claim 9, wherein re-positioning at least one of the first and second image data sets and the plurality of data elements associated therewith comprises:

shifting at least one of the first and second image data sets and the plurality of data elements associated therewith.

17. The method of claim 9, wherein re-positioning at least one of the first and second image data sets and the plurality of data elements associated therewith comprises:

rotating at least one of the first and second image data sets and the plurality of data elements associated therewith.

18. The method of claim 9, wherein re-positioning at least one of the first and second image data sets and the plurality of data elements associated therewith comprises:

shifting and rotating at least one of the first and second image data sets and the plurality of data elements associated therewith.

19. A method for comparing a first image data set to a second image data set, wherein the first and second image data sets are derived from fingerprint images and include a plurality of data elements comprising at least one of bifurcation representations, rod representations, vector segments associated with bifurcation representations, vector segments associated with rod representations, vector segments not associated with bifurcation representations, vector segments not associated with rod representations, microminutia points, and combinations thereof, the method comprising:

re-positioning at least one of the first and second image data sets, thereby re-positioning the set of data elements associated therewith;

generating a count of the data elements in the first image data set that approximately match the data elements in the second image data set; and

repeating said re-positioning and said generating a count until a maximum comparison point is identified, said maximum comparison point being a point at which said count approximates a maximum value.

20. The method of claim 19, further comprising:

predetermining a particular count value, based on a purpose for which the first image data set is being compared to the second image data set, that represents a selected level of similarity required for the first and second image data sets to be considered matching; and

providing a positive match indication when the count that corresponds to the maximum comparison point is equal to or greater than said particular count value.

21. The method claim 19 further comprising:

calculating a score that represents a percentage of the data elements in the first image data set that approximately match the data elements in the second image data set at the maximum comparison point.

22. The method of claim 21 further comprising:

predetermining a particular score, based on a purpose for which the first image data set is being compared to the second image data set, that represents a selected level of similarity required for the first and second image data sets to be considered matching; and

providing a positive match indication when the score associated with the maximum comparison point is equal to or greater than said particular score.

23. The method of claim 19, further comprising:

calculating a probability of relationship value that represents a relationship of match between the plurality of data elements in the first image data set and the plurality of data elements in the second image data set at the maximum comparison point.

24. The method of claim 23, further comprising:

predetermining a particular probability of relationship value, based on a purpose for which the first image is being compared to the second image, that represents a selected level of similarity required for the first and second images to be considered matching; and

providing a positive match indication when the probability of relationship value associated with the maximum comparison point is equal to or greater than said particular probability of relationship value.

25. The method of claim 19, further comprising an initial step of:

narrowing the first and second image data sets by eliminating those data elements in one of the first and second image data sets that do not fit within a predetermined qualifying range of deviation from data elements in the other of the first and second image data sets.

26. A method for efficiently and accurately comparing a first image to a plurality of other images, the method comprising:

deriving a first image data set based on the first image and a plurality of other image data sets based on the plurality of other images, wherein each image data set includes a plurality of data elements and is a model representation of a corresponding image; and

comparing at least one data element in the first image data set with data elements in at least one of the plurality of other image data sets.

27. The method of claim 26, wherein the first and second images are fingerprint images and the plurality of data elements are selected from a group consisting of:

bifurcation representations, rod representations, vector segments associated with bifurcation representations, vector segments associated with rod representations, vector segments not associated with bifurcation representations, vector segments not associated with rod representations, microminutia points, and combinations thereof.

28. The method of claim 26, further comprising:

generating a count for each of the plurality of other image data sets, wherein generating the count comprises calculating a quantity of data elements in each of the plurality of other image data sets that approximately match data elements taken from the first image data set.

29. The method of claim 28, further comprising:

selecting from the plurality of other image data sets a predetermined number of image data sets having the most data elements that approximately match data elements taken from the first image data set; and

performing a more thorough comparison of the predetermined number of image data sets to the first image data set.

30. The method of claim 29, wherein the first and second images are fingerprint images and the plurality of data elements are selected from a group consisting of:

bifurcation representations, rod representations, vector segments associated with bifurcation representations, vector segments associated with rod representations, vector segments not associated with bifurcation representations, vector segments not associated with rod representations, microminutia points, and combinations thereof.

31. The method of claim 26, wherein comparing at least one data element in the first image data set with data elements in at least one of the plurality of other image data sets comprises:

creating a B-tree data file for each of a plurality of data element types and categorizing and storing, based on a set of data normalization rules, substantially all of the data elements included in the plurality of other image data sets.

32. The method of claim 31, wherein creating a B-tree data file for each of a plurality of data element types and categorizing and storing, based on a set of data normalization rules, substantially all of the data elements included in the plurality of other image data sets, further comprises:

storing each data element in the B-tree data files with an identifier that represents association with a particular image data set within which the data element appears.

33. The method of claim 32, wherein creating a B-tree data file for each of a plurality of data element types and categorizing and storing, based on a set of data normalization rules, substantially all of the data elements included in the plurality of other image data sets, further comprises:

creating a B-tree data file, for each data element type, that reflects substantially all potential relative associations between data elements stored in the data file and the plurality of data element types.

34. The method of claim 32, wherein creating a B-tree data file for each of a plurality of data element types and categorizing and storing, based on a set of data normalization rules, substantially all of the data elements included in the plurality of other image data sets, further comprises:

creating a B-tree data file that reflects normalization rules for each data element type, including variations of relative position and rotation.

35. The method of claim 32, wherein the first and second images are fingerprint images and the plurality of data elements are selected from a group consisting of:

bifurcation representations, rod representations, vector segments associated with bifurcation representations, vector segments associated with rod representations, vector segments not associated with bifurcation representations, vector segments not associated with rod representations, microminutia points, and combinations thereof.

36. The method of claim 32, further comprising:

comparing at least one target data element from the first image data set to data elements in the B-tree data file having data elements of a same type as each target data element being compared.

37. The method of claim 36, further comprising:

utilizing the identifiers associated with the data elements listed in the B-tree data files to calculate and note a quantity of data elements in each of the plurality of other image data sets that approximately match data elements taken from the first image data set.

38. The method of claim 37, further comprising:

selecting from the plurality of other image data sets a predetermined number of image data sets having the most data elements that approximately match the target data elements taken from the first image data set; and

performing a more thorough comparison of the predetermined number of image data sets to the first image data set.

39. The method of claim 38, wherein the first and second images are fingerprint images and the plurality of data elements are selected from a group consisting of:

bifurcation representations, rod representations, vector segments associated with bifurcation representations, vector segments associated with rod representations, vector segments not associated with bifurcation representations, vector segments not associated with rod representations, microminutia points, and combinations thereof.

40. The method of claim 26, wherein comparing at least one data element in the first image data set with data elements in at least one of the plurality of other image data sets comprises:

creating a directory that progressively lists, based on at least one measured characteristic, a substantial number of a first type of data elements that appear in the plurality of other image data sets, wherein each data element in the directory is listed with an identifier that represents association with a particular image data set within which the data element appears; and

comparing data elements of the first type taken from the first image data set to the data elements that are progressively listed in the directory.

41. The method of claim 40, wherein comparing data elements of the first type taken from the first image data set to the data elements that are progressively listed in the directory comprises:

creating an array having a two-entry cell for each of a range of potential configurations for the first type of data element;

recording in a first entry of at least one two-entry cell, a quantity value representing a number of consecutive data elements in the directory that demonstrate characteristics that are approximately similar to characteristics of the one of the range of potential configurations for the first type of data element that is associated with the two-entry cell within which the first entry is being recorded; and

recording in a second entry of at least one two-entry cell, an index value corresponding to an initial data element that begins the number of consecutive data elements listed in the directory.

42. The method of claim 41, wherein comparing data elements of the first type taken from the first image data set to data elements that are progressively listed in the directory comprises:

identifying a two-entry cell in the array that is associated with a data element configuration having characteristics approximately identical to a target data element taken from the first image data set; and

comparing the target data element to a group of consecutive data elements listed in the directory, as indicated by the two-entry cell associated with the target data element; and

repeating the identifying and comparing steps for at least one additional target data element.

43. The method of claim 42, further comprising generating a count for each of the plurality of other image data sets, wherein generating the count comprises:

utilizing the identifiers associated with the data elements listed in the directory to calculate and note a quantity of data elements in each of the plurality of other image data sets that approximately match data elements taken from the first image data set.

44. The method of claim 43, further comprising:

selecting from the plurality of other image data sets a predetermined number of image data sets having the most data elements that approximately match data elements taken from the first image data set; and

performing a more thorough comparison of the predetermined number of image data sets to the first image data set.

45. The method of claim 43, further comprising:

repeating the previous steps substituting at least one other type of data elements in place of the first type of data elements;

selecting from the plurality of other image data sets a predetermined number of image data sets having the most data elements that approximately match data elements taken from the first image data set; and

performing a more thorough comparison of the predetermined number of image data sets to the first image data set.

46. A method for efficiently and accurately comparing a first image data set to a plurality of other image data sets, wherein the first and plurality of other image data sets are individually derived from fingerprint images and include a plurality of data elements of a plurality of types, the plurality of types comprising at least one of bifurcation representations, rod representations, vector segments associated with bifurcation representations, vector segments associated with rod representations, vector segments not associated with bifurcation representations, vector segments not associated with rod representations, microminutia points, and combinations thereof, the method comprising:

creating a directory that progressively lists, based on at least one measured characteristic, a substantial number of a first type of data elements that appear in the plurality of other image data sets, wherein each data element in the directory includes an identifier that represents association with a particular image data set within which the data element appears;

creating an array having a two-entry cell for each of a range of potential configurations for the first type of data element;

recording in a first entry of at lest one two-entry cell, a quantity value representing a number of consecutive data elements in the directory that demonstrate characteristics that are approximately similar to characteristics of the one of the range of potential configurations for the first type of data element that is associated with the two-entry cell within which the first entry is being recorded;

recording in a second entry of at least one two-entry cell, an index value corresponding to an initial data element that begins the number of consecutive data elements listed in the directory;

identifying a two-entry cell in the array that is associated with a data element configuration having characteristics approximately identical to a target data element of the first type taken from the first image data set; and

comparing the target data element to a group of consecutive data elements listed in the directory, as indicated by the two-entry cell associated with the target data element.

47. The method of claim 46, further comprising:

repeating the identifying and comparing steps for at least one additional target data element;

utilizing the identifiers associated with the data elements listed in the directory to calculate and note a quantity of data elements in each of the plurality of other image data sets that approximately match data elements taken from the first image data set;

selecting from the plurality of other image data sets a predetermined number of image data sets having the most data elements that approximately match data elements taken from the first image data set; and

performing a more thorough comparison of the predetermined number of image data sets to the first image data set.

48. The method of claim 46, further comprising:

repeating the identifying and comparing steps for at least one additional target data element;

utilizing the identifiers associated with the data elements listed in the directory to calculate and note a quantity of data elements in each of the plurality of other image data sets that approximately match data elements taken from the first image data set;

repeating the previous steps substituting at least one other type of data elements in place of the first type of data elements;

selecting from the plurality of other image data sets a predetermined number of image data sets having the most data elements that approximately match data elements taken from the first image data set; and

performing a more thorough comparison of the predetermined number of image data sets to the first image data set.

49. A method for efficiently and accurately comparing a first image data set to a plurality of other image data sets, wherein the first and plurality of other image data sets are individually derived from fingerprint images and include a plurality of data elements of a plurality of types, the plurality of types comprising at least one of bifurcation representations, rod representations, vector segments associated with bifurcation representations, vector segments associated with rod representations, vector segments not associated with bifurcation representations, vector segments not associated with rod representations, microminutia points, and combinations thereof, the method comprising:

creating a B-tree data file for at least one of the plurality of data element types and categorizing and storing, based on a set of data normalization rules, substantially all of the data elements included in the plurality of other image data sets;

storing each data element in the B-tree data files with an identifier that represents association with a particular image data set within which the data element appears; and

comparing at least one target data element from the first image data set to data elements in the B-tree data file having data elements of a same type as each target data element being compared.

50. The method of claim 49, further comprising:

utilizing the identifiers associated with the data elements listed in the B-tree data files to calculate and note a quantity of data elements in each of the plurality of other image data sets that approximately match data elements taken from the first image data set;

selecting from the plurality of other image data sets a predetermined number of image data sets having the most data elements that approximately match the target data elements taken from the first image data set; and

performing a more thorough comparison of the predetermined number of image data sets to the first image data set.