Sliding yardsticks fingerprint enrollment and verification system and method

• US 6,075,876 A
• Filed: 05/07/1997
• Issued: 06/13/2000
• Est. Priority Date: 05/07/1997
• Status: Expired due to Fees

• Current Assignee: Georgi Hristoff Draganoff
• Original Assignee: Georgi Hristoff Draganoff
• Inventors: Draganoff, Georgi Hristoff
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Miller, Martin E.
• Application Number:
  US08/852,382
• Time in Patent Office: 1,133 Days
• Field of Search: 382/124, 382/125, 382/126, 382/127, 382/192, 382/201, 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 biocript 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 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 biocript, which leads to better memory utilization in fingerprint databases.

Claims

1. An enrollment system for biometric identification device comprising:

an input device to provide signals representing an enrollment image wherein said enrollment system includes a processing unit to extract a plurality of 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

wherein said processing unit stores said yardsticks in said memory based upon their relative spatial relationship to each other.

2. An enrollment system as claimed in claim 1, wherein said predetermined locations for a said array are located within a selected one of a single column and a single row from said enrollment image.

3. An enrollment system as claimed in claim 1, wherein said enrollment image is saved into said memory as a binary image with one bit pixel size.

4. A fingerprint enrollment system as claimed in claim 1, wherein said yardsticks correspond to lines of pixels having uniform length.

5. An enrollment system as claimed in claim 1, wherein said yardsticks are composed into a data structure constituting an enrollment template in a predetermined order.

6. An enrollment system according to claim 1 further including a data structure, including said yardsticks in a predetermined order, stored in said memory.

7. An enrollment and verification system for biometric identification device comprising:

an input device to provide signals representing an enrollment image wherein said enrollment system includes a processing unit to extract a plurality of 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

wherein said processing unit stores said yardsticks in said memory as a data structure based upon their relative spatial relationship to each other;

wherein for verification, a current line is obtained from an image to be verified, a first one of said plurality of yardsticks from said data structure is compared for a match to a line of pixels of the same size in said current line, wherein if there is no match, the first yardstick shifts relative to the line of pixels from the current line and is tested for a match thereto, wherein said shifting and then comparing iterates through said current line from the image to be verified until a match is found, wherein if the current line has been tested with said first yardstick and no match found a next line from the image to be verified is obtained and said first yardstick comparison process repeats, and wherein said shifting and then if necessary moving, to a next line iterates until a match is found, wherein after a match is found for said first yardstick,

a next one of said plurality of yardsticks from said data structure is compared to a predetermined set of lines of pixels from the image to be verified and spaced from the location of said previously matched yardsticks based upon the spatial relationship of the said predetermined yardstick locations;

the verification process continues to attempt to find the best match of all of the yardsticks in the data structure until the final yardstick is matched and the best match within said predetermined set is selected;

wherein said verification process exits after the last yardstick from the data structure has been matched;

said processing unit outputs a match indication signal.

8. A biometric verification system, comprising:

an input device to provide signals representing images acquired from a predetermined part of a body;

a memory;

a control system including a central processor unit, wherein said control system is coupled to control the operation of said verification system, and a data structure stored in said memory;

said data structure including a plurality of yardsticks having a predetermined spatial relationship to one another in an enrolled image;

each said yardstick is a one-dimensional array having a predetermined number of either horizontal or vertically oriented, consecutive, co-linear pixels and the maximum number of yardsticks being substantially less than the maximum number extractable from said enrolled image, said enrolled image is smaller, in pixel dimensions, than the input image;

each yardstick representing a predetermined location within an enrollment window;

wherein said yardsticks are compared in a predetermined fashion for a match to co-linear pixels of an image to be verified; and

wherein for verification, a current line is obtained from an image to be verified, a first one of said plurality of yardsticks from said data structure is compared for a match to a line of pixels of the same size in said current line, wherein if there is no match, the first yardstick shifts relative to the line of pixels from the current line and is tested for a match thereto, wherein said shifting and then comparing iterates through said current line from the image to be verified until a match is found, wherein if the current line has been tested with said first yardstick and no match found a next line from the image to be verified is obtained and said first yardstick comparison process repeats, and wherein said shifting and then if necessary moving, to a next line iterates until a match is found, wherein after a match is found for said first yardstick;

a next one of said plurality of yardsticks from said data structure is compared to a predetermined set of lines of pixels from the image to be verified and spaced from the location of said previous yardstick based upon the spatial relationship of the said predetermined yardstick locations;

the verification process continues to attempt to find the best match of all of the yardsticks in the data structure until the final yardstick is matched and the best match within said predetermined set is selected;

wherein said verification process exits after the last yardstick from the data structure has been matched.

9. A verification system as claimed in claim 8, wherein if the best matches for a predetermined number of yardsticks fail to meet predetermined thresholds the verification process is interrupted before its end.

10. A verification system as claimed in claim 8, wherein the test for matching a yardstick to a line of pixels 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.

11. A verification system as claimed in claim 8, wherein the test for matching said yardsticks to said lines of pixels from the image to be verified is one by calculating the average Hamming distance, equal to the sum of all calculated Hamming distances for all already matched yardsticks, plus the Hamming distance calculated for the current test and dividing said sum by the number of matched yardsticks including the current one.

12. A verification system as claimed in claim 8, wherein the image to be verified is converted into a binary line art image with one bit pixel size and then saved into said memory.

13. A verification system as claimed in claim 8 wherein if the first yardstick fails to find a match in the acquired image to be verified, a next image to be verified is acquired stored into memory and said first yardstick is tested for a match from the same position it started said tests with previous image to be verified.

14. A verification system as claimed in claim 13, including selecting another one of said yardsticks as a first yardstick for testing against said next image to be verified.

15. A method for verification of two images where the first image is used for verification and the second image is to be verified and said first image is smaller in pixel number size in row and column directions than said second image, the method including;

deriving from said first image a plurality of yardsticks, the maximum number of said yardsticks being substantially smaller than the maximum number extractable from said first image, each yardstick comprising a one dimensional array of data representative of a plurality of successive co-linear pixels;

wherein each yardstick represents pixels from a single corresponding row or a single corresponding column of pixels from said first image, and wherein said plurality of yardsticks are organized in a predetermined order corresponding to their relative positions to each other;

wherein a first yardstick from said data structure is tested for a match by sliding it to multiple positions along the lines of the second image in a predetermined order and at each said position comparing the first yardstick to line portions of corresponding pixel number size, representing parts of the selected one of lines and columns from the second image;

wherein if a match is found for said first yardstick, then a next yardstick is tested for best match within only a predetermined number of possible positions relative to the location in the second image where the first yardstick was successfully matched; and

wherein successive yardsticks are tested for best match in the same manner as said second yardstick but at respectively different locations relative to the previous yardsticks matched within the second image.

16. A method of claim 15, wherein said first and second images are of binary type, wherein the pixel size in each is one bit deep and wherein the lines of successive pixels represented by said yardsticks are all parallel.

17. A method of claim 15, wherein the test for matching of said yardsticks to corresponding line portions from the second image is performed by calculating the average Hamming distance between said line portions and the yardsticks and comparing the resulting Hamming distance to at least one predetermined threshold.

18. A method of claim 17, wherein said average Hamming distance is equal to the sum of calculated Hamming distances for all already matched yardsticks, plus the Hamming distance calculated for the current yardstick matching to a linear portion from the second image, and wherein said sum is then divided by the total number of matched yardsticks including the current one.

19. A method of claim 17, wherein the magnitude of said threshold varies as the verification process progresses.

20. A method of claim 15, wherein if a measure of a best match for the yardsticks following the first yardstick fails to meet the at least one predetermined threshold, the value of a mismatch counter is changed.

21. A method of claim 20, wherein the value in said mismatch counter is tested for a predetermined value, and if a match is detected, the verification process is interrupted.

22. A method of claim 21, wherein when said verification process has been interrupted, the search for a match for said first yardstick proceeds further from the point of last match for the first yardstick, until a new match is found.

23. A method of claim 21, where said predetermined value is variable and is a function of the number of yardsticks already tested for a match.

24. A method of claim 15, wherein if no match is found for said first yardstick, the verification process for a next image to be verified starts from beginning test parameters.

25. A method of claim 24, wherein whenever the new search for a match begins, another yardstick is selected from said data structure and used as a first yardstick.