System and method for automatically verifying identity of a subject

• US 5,917,928 A
• Filed: 07/14/1997
• Issued: 06/29/1999
• Est. Priority Date: 07/14/1997
• Status: Expired due to Term

• Current Assignee: BES Systems Incorporated
• Original Assignee: BES Systems Incorporated
• Inventors: Berestetskiy, Mikhail, Shpuntov, Mikhail, Pletnev, Alexandre
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US08/891,958
• Time in Patent Office: 715 Days
• Field of Search: 382/124, 382/125, 382/209, 382/216, 382/217, 382/218, 356/71
• US Class Current: 382/124
• CPC Class Codes: A61B 5/1172 using fingerprinting
• CPC Class Codes: G06V 40/12 Fingerprints or palmprints
• CPC Class Codes: G07C 9/37 using biometric data, e.g. fingerprints, iris scans or voice recognition

Abstract

A system and method for verifying identity of a user seeking access to a secured area or object is provided. The system employs a novel global image comparison approach by first acquiring a reference fingerprint image from a user during an enrollment stage, obtaining a set of multiple reference segments from the reference image representative of unique portions thereof, and later during a verification stage obtaining a verification fingerprint image from a user seeking access to the secured area or object, determining the most likely positions for the multiple reference segments over the verify image, and then comparing all pixels of the reference image enclosed by the multiple reference segments to all pixels in a portion of the verify image overlaid by the multiple reference segments in their current positions over the verify image in accordance with a dynamically determined threshold that is individually tailored for the user providing the reference image during the enrollment stage. When the threshold is exceeded, the user seeking access is granted access to the secured object or area; otherwise the user is rejected. The system of the present invention includes the capability of determining multiple most likely positions for the multiple reference segments over the verify image and then sequentially matching the reference segments to the verify image portion overlaid by them in their current position against the dynamic threshold until a match is found or until it is determined that the verify and reference images are not matched. To speed up the verification process, the verify image and one of the multiple reference segments may be temporarily coarsened during the process of determining multiple possible most likely positions for the multiple reference segments.

Claims

1. A method for comparing a first image of a predefined image resolution comprising a first plurality of pixels and a second image of the predefined image resolution comprising a second plurality of pixels to determine if the images are substantially similar, said method being implemented in a data processing system having a memory, comprising the steps of:

(a) acquiring the first image;

(b) defining a plurality of adjacent reference templates positioned over a substantial portion of the first image, wherein each of said reference templates encloses a different portion of the first image;

(c) designating one reference template of said plurality of reference templates as a primary reference template, and all other reference templates as secondary reference templates;

(d) defining around each of said reference templates, a corresponding individual first selection area centered on each reference template, each of said first selection areas being larger than its respective reference template;

(e) determining a best position for each reference template within said corresponding first selection area, wherein said best position of each reference template is representative of a most unique portion of the first image within the respective first selection

(g) storing, in the memory as a reference file, the most unique portion of each respective first selection area, wherein the most unique portion corresponding to said primary reference template is designated as a primary reference segment and wherein each most unique portion corresponding to a particular one of said plurality of said secondary reference templates is designated as a plurality of said secondary reference segments;

(h) storing a set of coordinate positions of each of secondary reference segments relative to said primary reference segment in said reference file in the memory;

(i) defining a reference area comprising the pixels of the first image within said primary reference segment and said plurality of secondary reference segments;

(j) acquiring the second image;

(k) defining a first search area over a substantial portion of the second image;

(l) retrieving, from said reference file in the memory, said primary reference segment and said plurality of secondary reference segments;

(m) comparing said primary reference segment with all primary reference segment-sized portions of the second image within said first search area to determine a location of a closest match between said primary reference segment and a like-sized portion of the second image, wherein said like-sized portion is designated as a closest match portion;

(n) positioning the primary reference segment at said at least one closest match location and said plurality of secondary reference segments over said second image in accordance with said set of coordinate positions of each said secondary reference segment relative to said primary reference segment;

(o) defining a plurality of second search area templates, each second search area template corresponding to each of said secondary reference segments, each second search area template being centered on of each said corresponding secondary reference segments;

(p) comparing each secondary reference segment with all secondary reference segment-sized portions of the second image within its corresponding second search area to determine a best match position for each secondary reference segment within its corresponding second search area to obtain a plurality of best match portions of the second image corresponding to said plurality of secondary reference segments;

(q) defining a verification area comprising pixels of the second image within said closest match portion and said plurality of best-match portions; and

(r) comparing said reference area to said verification area to determine a total response value, said total response value being indicative of the degree of similarity between said reference area and said verification area.

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

(s) after said step (r) comparing said total response value to a predetermined total threshold, and when said total response value exceeds said predetermined total threshold, accepting the second image as substantially similar to the first image, and otherwise rejecting the second image as being not substantially similar to the first image.

3. The method of claim 2, wherein said step (m) comprises the steps of:

(gg) comparing said primary reference segment with each primary reference segment-sized area having a set of associated coordinates in said first search area to determine a predetermined amount of highest verification response values and said associated coordinates of corresponding particular reference segment-sized areas, each verification response value being representative of, and having a magnitude proportional to, the degree of similarity between said primary reference segment and a corresponding particular primary reference segment-sized area;

(hh) storing, in a best match queue in the memory, said predetermined amount of highest verification response values in a descending order of magnitude and storing said sets of associated coordinates of said particular primary reference segment-sized areas that each correspond to a particular verification response value of said predetermined amount of highest verification response values;

wherein said step (n) comprises the steps of;

(ii) retrieving from said best match queue a set of associated coordinates of a first primary reference segment-sized area corresponding to a highest verification response value of said predetermined amount of highest verification response values;

(jj) positioning said primary reference segment at said retrieved set of associated coordinates over said second image;

(kk) positioning said plurality of secondary reference segments over said second image in accordance with said set of coordinate positions of each said secondary reference segment; and

wherein said step (s) comprises the step of;

(ll) comparing said total response value to a predetermined total threshold, and when said total response value exceeds said predetermined total threshold, accepting the second image as substantially similar to the first image, and otherwise when at least one unretrieved set of associated coordinates of a primary reference segment-sized area remains in said best match queue, retrieving from said best match queue a set of associated coordinates of a first primary reference segment-sized area corresponding to a next highest verification response value of said predetermined amount of highest verification response values and returning to said step (jj), and otherwise rejecting the second image as being not substantially similar to the first image and terminating the comparing process.

4. The method of claim 2, wherein said step (m) comprises the steps of:

(mm) comparing said primary reference segment with each primary reference segment-sized area having a set of associated coordinates in said first search area to determine a plurality of verification response values and said associated coordinates of corresponding particular reference segment-sized areas, each verification response value being representative of, and having a magnitude proportional to, the degree of similarity between said primary reference segment and a corresponding particular primary reference segment-sized area;

(nn) comparing each verification response value of said plurality of verification response values to a predetermined verification response threshold, and storing, in a best match queue in the memory, all verification response values that have exceeded said predetermined verification response threshold in a descending order of magnitude and storing said sets of associated coordinates of said particular primary reference segment-sized areas that each correspond to a particular verification response exceeding said predetermined verification response threshold, wherein when none of said plurality of verification response values exceed said predetermined verification response threshold, storing, in said best match queue in the memory, a highest verification response value and a set of associated coordinates of a particular primary reference segment-sized areas corresponding to said highest verification response value;

wherein said step (n) comprises the steps of;

(oo) retrieving from said best match queue a set of associated coordinates of a first primary reference segment-sized area corresponding to a highest verification response value stored in said best match queue;

(pp) positioning said primary reference segment at said retrieved set of associated coordinates over said second image;

(qq) positioning said plurality of secondary reference segments over said second image in accordance with said set of coordinate positions of each said secondary reference segment; and

wherein said step (s) comprises the step of;

(rr) comparing said total response value to a predetermined total threshold, and when said total response value exceeds said predetermined total threshold accepting the second image as substantially similar to the first image, and otherwise when at least one unretrieved set of associated coordinates of a primary reference segment-sized area remains in said best match queue, retrieving from said best match queue a set of associated coordinates of a first primary reference segment-sized area corresponding to a next highest verification response value stored in said best match queue, and returning to said step (pp), and otherwise rejecting the second image as being not substantially similar to the first image and terminating the comparing process.

5. The method of claim 1, further comprising the step of:

(t) after said step (a) but before said step (b), filtering the first image to remove at least signal noise and brightness variations therefrom.

6. The method of claim 1, further comprising the step of:

(u) after said step (a) but before said step (b), binarizing the second image in accordance with a predefined binarization threshold.

7. The method of claim 1, further comprising the step of:

(v) after said step (j) but before said step (k), filtering the second image to remove at least signal noise and brightness variations therefrom.

8. The method of claim 7, further comprising the step of:

(w) after said step (v) but before said step (k), binarizing the second image in accordance with a predefined binarization threshold.

9. The method of claim 1, wherein said step (e) further comprises the steps of:

(x) for each of said reference templates;

(1) for each reference template-sized area in said corresponding first search area;

(A) defining a corresponding second selection area centered on a reference template-sized area, said second selection area being larger than said reference template-sized area;

(B) comparing a set of pixels of said first plurality of pixels that are enclosed by said reference template-size area to other sets of pixels of said first plurality of pixels that are enclosed by each of a plurality of other reference template-sized areas within said second search area to determine a plurality of response function values for said reference template-sized area, each response function value of said plurality of response function values being representative of, and proportional to, a degree of similarity between said reference template-sized area and a different one of said plurality of other reference template-sized areas, wherein a lower response function value is representative of a low degree of similarity, and a higher response function value is representative of a high degree of similarity, and wherein a maximum value of a response function is unity;

(C) determining a uniqueness factor of said reference template-sized area in accordance with a following expression;

space="preserve" listing-type="equation">uniqueness factor=(1-RF.sub.-- HIGH)

wherein RF_-- HIGH is a highest response function value of said plurality of response function values; and

(2) storing the position of a reference template-sized area having a highest uniqueness factor as a best-match position for said reference template.

10. The method of claim 9, wherein said step (x) further comprises the steps of:

(3) determining a reference threshold value in accordance with a following expression;

space="preserve" listing-type="equation">reference threshold value=RF.sub.-- HIGH+A(uniqueness factor),

wherein A is a predefined threshold constant.

11. The method of claim 10, further comprising the steps of:

(y) after said step (e) and before said step (f), determining a total threshold value by one of;

determining a weighted average of said reference threshold values obtained at said step (x)(3), and determining a mean of said reference threshold values obtained at said step (x)(3); and

(z) after said step (h) and before said step (j), storing said total threshold value in said reference file in the memory.

12. The method of claim 1, further comprising the steps of:

(aa) after said step (a) and before said step (j) acquiring from a user additional identifying data comprising said user'"'"'s personal identification code; and

(bb) storing said additional identifying data in, and associating said additional identifying data with said reference file in the memory.

13. The method of claim 12, wherein said step (aa) comprises the step of randomly selecting additional identifying data comprising said user'"'"'s personal identification code.

14. The method of claim 12, further comprising the steps of:

(cc) after said step (k) and before said step (l), acquiring a personal identification code from a user seeking verification of the second image being substantially similar to the first image; and

(dd) determining whether a match exists between said acquired personal identification code and said personal identification code stored in said reference file in the memory, and when a match exists proceeding to said step (l), and otherwise rejecting the second image as being not substantially similar to the first image and terminating the comparing process.

15. The method of claim 12, wherein said additional identifying data further comprises at least one of:

said user'"'"'s personal information and an image of said user.

16. The method of claim 1, wherein said primary reference segment is of a predefined segment resolution, further comprising the steps of:

(ee) after said step (l) and before said step (m), reducing the image resolution of the second image and said segment resolution of said primary reference segment by a predefined resolution factor; and

(ff) after said step (m) and before said step (n) increasing the image resolution of the second image and said segment resolution of said primary reference segment by said predefined resolution factor.

17. A data processing system for comparing a first image comprising a first plurality of pixels and a second image comprising a second plurality of pixels to determine if the images are substantially similar, said system comprising:

scanning means for acquiring the first and the second images;

memory means for storing data; and

control means, connected to said scanning means and said memory means, operable for;

causing said scanning means to acquire the first image;

defining a plurality of adjacent reference templates positioned over a substantial portion of the first image, wherein each of said reference templates encloses a different portion of the first image;

designating one reference template of said plurality of reference templates as a primary reference template, and all other reference templates as secondary reference templates;

defining around each of said reference templates, a corresponding individual first selection area centered on each reference template, each of said first selection areas being larger than its respective reference template;

determining a best position for each reference template within said corresponding first selection area, wherein said best position of each reference template is representative of a most unique portion of the first image within the respective first selection area, said most unique portions being of the same size as the respective reference templates;

moving each reference template to its corresponding best position;

storing, in said memory means as a reference file, the most unique portion of each respective first selection area, wherein the most unique portion corresponding to said primary reference template is designated as a primary reference segment and wherein each most unique portion corresponding to a particular one of said plurality of said secondary reference templates is designated as a plurality of said secondary reference segments;

storing, in reference file in said memory means, a set of coordinate positions of each of secondary reference segments relative to said primary reference segment;

defining a reference area comprising the pixels of the first image within said primary reference segment and said plurality of secondary reference segments;

causing said scanning means to acquire the second image;

defining a first search area over a substantial portion of the second image;

retrieving, from said reference file in said memory means, said primary reference segment and said plurality of secondary reference segments;

comparing said primary reference segment with all primary reference segment-sized portions of the second image within said first search area to determine a location of a closest match between said primary reference segment and a like-sized portion of the second image, wherein said like-sized portion is designated as a closest match portion;

positioning the primary reference segment at said at least one closest match location and said plurality of secondary reference segments over said second image in accordance with said set of coordinate positions of each said secondary reference segment relative to said primary reference segment;

defining a plurality of second search area templates, each second search area template corresponding to each of said secondary reference segments, each second search area template being centered on of each said corresponding secondary reference segments;

comparing each secondary reference segment with all secondary reference segment-sized portions of the second image within its corresponding second search area to determine a best match position for each secondary reference segment within its corresponding second search area to obtain a plurality of best match portions of the second image corresponding to said plurality of secondary reference segments;

defining a verification area comprising pixels of the second image within said closest match portion and said plurality of best-match portions;

comparing said reference area to said verification area to determine a total response value, said total response value being indicative of the degree of similarity between said reference area and said verification area; and

comparing said total response value to a predetermined total threshold, and when said total response value exceeds said predetermined total threshold, accepting the second image as substantially similar to the first image, and otherwise rejecting the second image as being not substantially similar to the first image.