Segmented sliding yardsticks error tolerant fingerprint enrollment and verification system and method

• US 6,301,376 B1
• Filed: 04/16/1998
• Issued: 10/09/2001
• Est. Priority Date: 05/07/1997
• Status: Expired due to Fees

• Current Assignee: Georgi H. Draganoff
• Original Assignee: Georgi H. Draganoff
• Inventors: Draganoff, Georgi H.
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): MILLER, MARTIN E
• Application Number:
  US09/061,406
• Time in Patent Office: 1,272 Days
• Field of Search: 382/115, 382/124, 382/125, 382/126, 382/127, 382/209, 382/218, 382/275, 382/283
• US Class Current: 382/124
• CPC Class Codes: G06V 40/1347 Preprocessing; Feature extraction

Abstract

A fast position tolerant and economical fingerprint verification algorithm and software implementation is disclosed. The algorithm has very important advantages in comparison to existing fingerprint verification algorithms like minutia extraction or full image analysis based on a series of two dimensional fast Fourier transforms ( FFT'"'"'s) and two dimensional cross correlation in speed, compactness of the template and finger positioning for verification. It is based on a small “yardstick” pattern being moved inside the image to be verified, and when a match is found the rest of the verification process is started. The yardstick is divided into segments in order to fit different DSP and microcontroller register lengths and structures. The software code implements the algorithm in the most efficient way for utilization on a digital signal processor architecture. A main area of application is in fingerprint identification and verification, but it could be implemented with same success in other image verification systems like iris, eye, face etc., where two images should be compared. The algorithm is adaptive, so various false acceptance and false rejection coefficients could be utilized very easily. It also produces a very compact template, which leads to better memory utilization in fingerprint databases.

Claims

1. A biometric enrollment and verification method comprising the steps of:

obtaining biometric image signals for an image to be verified;

obtaining a data structure for an enrolled image, said data structure having a plurality of yardsticks in a predetermined order, each said yardstick comprising a one dimensional pixel array having a predetermined number of either horizontal or vertically oriented, consecutive, co-linear pixels corresponding to a predetermined portion of a row or column of pixels within said enrollment image, each yardstick having a predetermined spatial relationship within said enrollment image relative to each of said other yardsticks, the maximum number of said yardsticks being substantially smaller than the maximum number extractable from the enrollment image and organized into a plurality of adjacent segments, comparing said yardsticks to an image to be verified by comparing segments of each yardstick to corresponding linear patterns in the image to be verified, wherein the result of the comparison of segments in a particular yardstick determines if said yardstick has found a match.

2. A biometric image verification method according to claim 1 wherein even if a predetermined number of segments fail to match corresponding linear patterns in the image to be verified, the result of matching the yardstick which includes said segments will be positive if other segments from said yardstick do match.

3. A biometric image verification method according to claim 1:

wherein the first segment of the first yardstick is compared for a match to a line pattern of the same size inside the image to be verified,

wherein if there is no match the first segment of the first yardstick shifts relative to the linear pattern from the image to be verified and again is tested for a match,

wherein if the current line has been tested and no match found, the segment moves to the next line, and the process repeats until a match is found, then the second segment of the first yardstick is compared to a line pattern from the image to be verified corresponding to its position relative to the first segment of the first yardstick for a match, and continuing until the last segment from the first yardstick has been matched.

4. A biometric image verification method as claimed in claim 3, wherein if a predetermined number of segments from the first yardstick fail to match corresponding line patterns from the image to be verified, further matching of the remaining segments of the first yardstick is discontinued and the match considered unsuccessful.

5. A biometric verification system as claimed in claim 3, wherein the central processor unit is programmed so that if it fails to find a match for the first yardstick in the acquired image to be verified, the next image to be verified is acquired, stored into memory and the first yardstick starts tests for a match from the same position it started the said tests with the previous image sought to be verified.

6. A biometric image verification method according to claim 1 wherein if a segment finds a match, the threshold for matching is made more stringent, new testing for a match is performed, and this process is repeated until no match is detected, and wherein the position of the last successful match in the image to be verified is the position of the match for said segment.

7. A biometric image verification method according to claim 1 wherein the test for matching the yardsticks to linear patterns of the same size from the image to be verified is performed by calculating the Hamming distance between them and comparing it to a predetermined threshold.

8. A biometric image verification method according to claim 1 wherein step of said obtaining and storing biometric image signals for the image to be verified includes:

converting the image to be verified into a line art image with one bit pixel depth, and

saving said line art image into memory for verification purposes.

9. A biometric verification method according to claim 1:

wherein the first segment of any selected yardstick from said data structure, except for the first yardstick, is compared for a match to line patterns of the same size inside the image to be verified, for a limited number of positions surrounding and including the position corresponding to the position of this segment of said selected yardstick in regard to the positions of the yardsticks tested for a match prior to said selected yardstick within the current verification process,

and if there is a match, the second segment of said selected yardstick is tested for a match at a fixed position corresponding to its relative position to the first segment of said selected yardstick,

then the next segment is tested for a match, the same way as the second segment, and this process repeats, until the last segment of said selected yardstick has been tested for a match;

if no successful match is found for the first segment of said selected yardstick, the next segment is then tested for a match, for a limited number of positions surrounding and including the position corresponding to the position of said next segment of said selected yardstick in regard to the positions of the yardsticks tested for a match prior to selected yardstick within the current verification process.

10. A biometric verification method as claimed in claim 9, wherein if a match is found for a segment, the threshold for matching is made more stringent, new testing for a match is performed, and this process is repeated until no match is detected, and wherein the position of the last successful match in the image to be verified is the position of the match for said segment.

11. A biometric verification method as claimed in claim 9, wherein the number of said next segments to be tested as said first segment, after the test for a match of the previous segment failed, is limited to a predetermined number of segments from said given yardstick.

12. A biometric verification method as claimed in claim 9, wherein if all segments of a yardstick tested for a match as said first segment fail to find a successful match, the test for a match of said yardstick to the line pattern in the verification image is not successful, even if the preset threshold for the number of failed segments has not been exceeded.

13. A biometric verification method as claimed in claim 9, wherein if a predetermined number of segments from said given yardstick fail to match corresponding line patterns from the image to be verified, further matching of the remaining segments of the given yardstick is discontinued and the match considered unsuccessful.

14. A biometric verification method as claimed in claim 1, wherein said comparing step includes deciding whether said data structure has found a match inside said image to be verified is made by a decision making step.

15. A biometric verification method as claimed in claim 14, wherein the matching process is considered successful by said decision making step if each of a predetermined number of yardsticks from the data structure finds a successful match.

16. A biometric verification method as claimed in claim 14, wherein the verification process is considered unsuccessful by said decision making step if any one of predetermined ones of said yardsticks is not found to match said fingerprint image to be verified.

17. A biometric verification system as claimed in claim 14, wherein the decision making step compares mismatch counts to corresponding threshold values.

18. A biometric verification method as claimed in claim 17, wherein if the contents of one of said mismatch counts exceeds its threshold value, said threshold value is modified.

19. A biometric verification method as claimed in claim 18, wherein said decision making step modifies the threshold values for other mismatch counters.

20. A biometric verification method as claimed in claim 19, including relaxing the threshold value for said one mismatch counter, and making the threshold values for said other mismatch counters more stringent.

21. A biometric verification method as claimed in claim 17, wherein if a predetermined number of mismatch counts exceed their corresponding threshold values the current verification process is considered unsuccessful.

22. The method of claim 1 wherein said image to be verified can be verified even if a yardstick from the enrolled image fails to find a match.

23. The method of claim 22 wherein said image to be verified is not verified if a predetermined number of yardsticks sought to be matched cannot be matched.

24. The verification method of claim 1 wherein said step of obtaining a data structure for an enrolled biometric image includes deriving a plurality of yardsticks from data representing an image to be enrolled, each said yardstick being based on pixel data from co-linear pixels of said image.

25. The method of claim 1 wherein said comparing step includes first and second tolerances;

wherein said first tolerance permits one of said yardsticks to be found to correspond sufficiently to acquired data for the image to be verified even if the verification process has not been able to match a first limited number of segments of said yardstick to said acquired data;

wherein said second tolerance permits said image to be verified to be found to correspond sufficiently to an enrolled image even if the verification process has not been able to match a second limited number of said yardsticks to said acquired data.

26. The method of claim 25 wherein said comparing step includes applying said first tolerance applies for each of said yardsticks sought to be matched.

27. The method of claim 25 wherein said comparing step includes applying said second tolerance to a plurality of said yardsticks.

28. The method of claim 25 wherein said comparing step includes applying said first tolerance but not said second tolerance to at least one of said yardsticks.

29. The method of claim 25 wherein said comparing step compares said yardsticks in a predetermined order.

30. The method of claim 1 wherein said comparing step, after finding a first match for a said yardstick, compares all other ones of said yardsticks which are sought to be matched to limited numbers of locations within the data for the image to be verified.

31. The method of claim 1 wherein said comparing step further includes a match optimization step to at least one yardstick segment.

32. The method of claim 1 wherein said comparing step requires a sufficient match, within a first tolerance, of at least one of said yardsticks;

wherein after said first sufficient match has been found, a plurality of further matches is sought in said comparing step;

wherein each said further matches is sought at limited numbers of respective locations relative to a location where a prior match had been determined; and

wherein a second tolerance is applied in the comparing step for at least one of said further matches.

33. The method of claim 32 wherein said second tolerance includes maintaining a mismatch count;

and incrementing said mismatch count if said comparing step does not find a match for selected ones of said yardsticks in the image data to be verified.

34. The method of claim 33 wherein said comparing step includes adjusting said second tolerance.

35. The method of claim 33 wherein said comparing step includes a decision making step and wherein said adjusting occurs in said decision making step.

36. The method of claim 1 wherein said comparing step includes maintaining first and second mismatch counts;

and incrementing a selected one of said mismatch counts for each of selected ones of said yardsticks if said comparing step does not find a match therefor in the image data to be verified.

39. The enrollment system of claim 1 wherein said central processor is arranged to store said yardsticks in a predetermined data structure.

37. An enrollment system for biometric identification device, having

an input device to provide signals representing an enrollment image,

a memory, and

a control system coupled to said memory,

wherein said control system includes a processing unit to extract yardsticks from said enrollment image, each said yardstick comprising a one dimensional pixel array having a predetermined number of either horizontal or vertically oriented, consecutive, co-linear pixels corresponding to a predetermined portion of a row or column of pixels within said enrollment image, each yardstick having a predetermined spatial relationship within said enrollment image relative to each of said other yardsticks, the maximum number of said yardsticks being substantially smaller than the maximum number extractable from the enrollment image and each yardstick being divided into a predetermined number of adjacent, multiple pixel segments, and

wherein said control system causes said yardsticks to be stored in said memory.

38. An enrollment system for biometric identification device as claimed in claim 37, wherein the acquired enrollment image is converted into line art image with one bit pixel depth and saved into memory for further processing.

40. A biometric enrollment and verification system, comprising:

an input device to acquire biometric images,

a memory to store the acquired images from said input device,

a central processor unit to control and synchronize the operation of said biometric enrollment and verification system, and

a data structure including a plurality of yardsticks in a predetermined order, each said yardstick comprising a one dimensional pixel array having a predetermined number of either horizontal or vertically oriented, consecutive, co-linear pixels corresponding to a predetermined portion of a row or column of pixels within said enrollment image, each yardstick having a predetermined spatial relationship within said enrollment image relative to each of said other yardsticks, the maximum number of said yardsticks being substantially smaller than the maximum number extractable from the enrollment image and organized into a plurality of adjacent segments,

wherein said central processor unit compares said yardsticks for a match to a biometric image to be verified by comparing sequentially segments of each yardstick to corresponding linear patterns in the image to be verified, wherein the result of the comparison of all segments in a particular yardstick determines if said yardstick has found a match.

41. A biometric verification system as claimed in claim 40, wherein yardsticks comprising the enrollment data structure are divided into groups, each group having assigned a corresponding mismatch counter, to count yardsticks in said group, failing to find a match.

42. In a biometric enrollment and verification system stored on a computer-readable medium, comprising the steps of:

acquiring data representing an image to be verified;

obtaining a plurality of sets of data each representing a set of co-linear pixels from an enrolled image said set being called yardstick and each said yardstick comprising a one dimensional pixel array having a predetermined number of either horizontal or vertically oriented,

consecutive, co-linear pixels corresponding to a predetermined portion-of a row or column of pixels within said enrollment image, each yardstick having a predetermined spatial relationship within said enrollment image relative to each of said other yardsticks, the maximum number of said yardsticks being substantially smaller than the maximum number extractable from the enrollment image, each set of data including a plurality of subsets, each subset representing a segment of said yardstick;

accessing said subsets of data; and

comparing said subsets with data for said image to be verified, outputting a verification result after comparing.

43. The data structure of claim 42 wherein each said yardstick has uniform length.

44. The data structure of claim 43 wherein each said yardstick is selected from the group consisting of a line of pixels in a row of said enrollment image and a line of pixels in a column of said enrollment image.

45. A biometric image enrollment method comprising the steps of:

providing an enrollment image representation and obtaining digitized enrollment image data;

obtaining a plurality of sets of pixel data from said enrollment representation called yardsticks, each said yardstick comprising a one dimensional pixel array having a predetermined number of either horizontal or vertically oriented, consecutive, co-linear pixels corresponding to a predetermined portion of a row or column of pixels within said enrollment image, each yardstick having a predetermined spatial relationship within said enrollment image relative to each of said other yardsticks, the maximum number of said yardsticks being substantially smaller than the maximum number extractable from the enrollment image,

dividing said sets of pixel data into a plurality of subsets corresponding to adjacent segments of said co-linear pixels; and

storing said subsets of pixel data in a memory.

46. The method of claim 45 further including storing said sets of data and subsets thereof in a data structure.

47. A method of biometric enrollment and verification comprising the steps of:

acquiring data representing an image to be verified;

obtaining a plurality of sets of data each representing a set of co-linear pixels from an enrolled image said set being called yardstick and each said yardstick comprising a one dimensional pixel array having a predetermined number of either horizontal or vertically oriented, consecutive, co-linear pixels corresponding to a predetermined portion of a row or column of pixels within said enrollment image, each yardstick having a predetermined spatial relationship within said enrollment image relative to each of said other yardsticks, the maximum number of said yardsticks being substantially smaller than the maximum number extractable from the enrollment image, each set of data including a plurality of subsets, each subset representing a segment of said yardstick;

accessing said subsets of data; and

comparing said subsets with data for said image to be verified, outputting a verification result after comparing.

48. The method of claim 47 wherein said comparing step further includes a match optimization step.

49. The method of claim 47 wherein said comparing step requires a sufficient match, within a tolerance, of at least one of said yardsticks;

wherein after a first sufficient match has been found for a said yardstick;

a plurality of further matches is sought in said comparing step;

wherein each said further match is sought at only limited numbers of respective locations relative to a location where a prior match had been determined.

50. The method of claim 47 wherein said step of obtaining a plurality of sets of data includes accessing a stored data structure which contains said sets of data in a predetermined order.

51. The method of claim 47 wherein said comparing step, after finding a first match for a said yardstick, compares at least one other one said yardsticks to limited numbers of locations within the data for the image to be verified.

52. A biometric image verification method according to claim 47 wherein said comparing step verifies the acquired data as corresponding to an enrolled image, even if a limited number of said subsets of said enrolled sets of data are not found to be sufficiently matched to said acquired data.

53. The method of claim 47 wherein said accessing and comparing steps comprise:

accessing a first one of said sets of data;

accessing a first subset from said first set;

then comparing said first subset with said data for said image to be verified in a plurality of locations until a match has been found;

then sequentially comparing one or more further subsets from said first set and comparing each said further subset to said data for said image to be verified at locations corresponding to the position of the pixels represented by said further subset relative to the positions of the pixels represented by said first subset, until a sufficient number of subsets have been matched to data for said image to be verified;

then accessing one or more further sets of data and comparing the subsets of each at only limited numbers of locations relative to the location at which a match was found for a previously matched set of data; and

determining whether the image to be verified corresponds to the enrolled image as a function of the matches located in said sets and subsets of data.

54. The method of claim 53 wherein a set of data is determined to have been matched after a predetermined number of subsets thereof have been found to match the data for said image to be verified.