Matcher

• US 4,696,046 A
• Filed: 03/27/1986
• Issued: 09/22/1987
• Est. Priority Date: 08/02/1985
• Status: Expired due to Fees

• Current Assignee: Secure Technologies Group, Inc.
• Original Assignee: Secure Technologies Group, Inc.
• Inventors: Schiller, Michael
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Mancuso, Joseph
• Application Number:
  US06/845,154
• Time in Patent Office: 544 Days
• Field of Search: 382/4, 382/5, 382/30, 382/34, 382/36, 356/71
• US Class Current: 382/125
• 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 set of Search identification points derived from an optical scan of a finger are compared against File identification points for the same finger. A multiple comparator divides the finger image into multiple segments. The Search and File points from each segment are compared separately. A difference table (D.T.) provides a proximity value Q for each search point. The D.T. is purged of all entries representing multiple Search points. The purge keeps those entries having the highest Q value. The purged D.T. with recalculated Q values is the basis for correcting the position of each Search point on the image plane to compensate for shift in finger position and for the variable distortion and changes that come about in a finger over time and upon successive applications of the finger to input scan. The corrected Search points are compared against the File points to establish a new D.T. A proximity value Q for each entry on this D.T. is calculated and a proximity value Q for the entire table is calculated. These proximity values in view of the number of entries on the difference table are used to verify identification in a scoring routine.

Claims

1. A matcher improvement for matching a set of Search identification points against a set of File identification points employing a difference table, comprising:

first memory means for storing a set of Search identification points as a set of binary value signals,

second memory means for storing a set of File identification points as a set of binary value signals,

multiple comparator means, each of said comparator means being coupled to a predetermined subset of said Search identification points and to a corresponding predetermined subset of said File identification points, each of said multiple comparative means having;

(i) differencing means to provide a first difference table and a first proximity value for each entry on said difference table,

(ii) constant adjustament means to provide a difference plane translation of that entry in said difference table which has the highest proximity value to the origin of the difference plane represented by said difference table, all of the entries in said difference table being translated by the same amount,

(iii) differential adjustment means to differentially adjust each entry in said difference table as a function of the distance between the Search point of the entry being adjusted and the Search point of the entry having the highest proximity value,

(iv) means to provide a final set of proximity values based on the difference table provided by said constant and said differential adjustment means, and

(v) means to provide at least one figure of merit based on said final set of proximity values for the Search subset involved, and

means to combine said figures of merit from each of said subsets to provide at least one overall figure of merit indicating the degree of match between said set of Search points and said set of File points.

2. The matcher of claim 1 wherein:

said File point and Search point signals represent minutia identification points on the image plane of a fingerprint and said subsets of File points are overlapping subsets on the image plane.

3. The matcher of claim 2 further comprising:

limiting means to provide a final difference table that is limited to a predetermined number of entries based on those entries having the highest proximity values in the difference table provided by said constant and said differential adjustment means.

4. The matcher of claim 2 wherein:

each of said multiple differencing means includes,

means to provide an intial difference table based on the associated ones of said subsets of Search and File identification point signals and to provide an initial proximity value for each entry on said initial difference table, and

means to extract from said initial difference table a set of entries representing no duplicate Search point entries, said extracted set of entries being based on those entries in said initial difference table having the higher proximity values, and to provide a purged difference table based on said extracted entries, said purged difference table being said first difference table for which said constant and differential adjustment means provides said translation and differential adjustment.

5. The matcher of claim 4 further comprising:

limiting means to provide a final difference table that is limited to a predetermined number of entries based on those entries having the highest proximity values in the difference table provided by said constant and said differential adjustment means.

6. The matcher of claim 5 further comprising:

first window means to limit the entries of said initial difference table to Search and File points within a predetermined distance on the image plane from each other.

7. The matcher of claim 6 further comprising:

second window means to limit the entries of said final difference table to difference table entry comparisons within a predetermined distance on the difference plane from each other.

8. The matcher of claim 4 further comprising:

first window means to limit the entries of said inital difference table to Search and File points within a predetermined distance on the image plane from each other.

9. The matcher of claim 8 further comprising:

second window means to limit the entries of said final difference table to difference table entry comparisons within a predetermined distance on the difference plane from each other.

10. The matcher of claim 1 wherein:

each of said multiple differencing means includes,

means to provide an initial difference table based on the associated ones of said subsets of Search and File identification point signals and to provide an initial proximity value for each entry on said initial difference table, and

means to extract from said initial difference table a set of entries representing no duplicate Search point entries, said extracted set of entries being based on those entries in said initial difference table having the higher proximity values, and to provide a purged difference table based on said extracted entries, said purged difference table being said first difference table for which said constant and differential adjustment means provides said translation and differential adjustment.

11. The matcher of claim 10 further comprising:

limiting means to provide a final difference table that is limited to a predetermined number of entries based on those entries having the highest proximity values in the difference table provided by said constant and said differential adjustment means.

12. The matcher of any of claims 1 or 2 through 7 wherein the number of said comparator means is at least four, said comparator means dividing said image into at least four subsets along a first axis.

13. The matcher of any of claim 1 or 2 through 7 therein the number of said computer means is sixteen, said sixteen comparator means dividing said image into a two dimensional matrix of four by four subsets.

14. The machine method of automatically matching a set of File identification points against a set of Search identification points employing a difference table, comprising:

storing a set of Search identification points, as a set of binary value signals, in a first memory means,

storing a set of File identification points, as a set of binary value signals, in a second memory means,

segmenting said set of Search points and said set of File points into predetermined corresponding subsets,

for each of said corresponding Search and File subsets, comparing the individual Search and File points, said step of comparing, including;

(i) providing a first difference table for the corresponding set of Search and File points, said difference table having a first proximity value for each entry therein,

(ii) shifting the entry on said difference table having the highest proximity value to the origin of the difference plane represented by said difference table, and shifting all of the other entries on said difference table by the same amount, and

(iii) then differentially adjusting each of said entries on said difference table as a function of the distance between the Search point of the entry being adjusted and the Search point of the entry having the highest proximity value,

(iv) providing a final set of proximity values for the difference table provided by said steps of shifting and differentially adjusting, and

(v) providing at least one figure of merit based on said final set of proximity values for the Search subset involved, and

combining said figures of merit from each of said Search subsets to provide at least one overall figure of merit indicating the degree of match between said set of Search points and said set of File points.

15. The method of claim 14 wherein:

said File point and Search point signals represent minutia identification points on the image plane of a fingerprint and said subsets of File points are overlapping subsets on the image plane.

16. The method of claim 15 wherein said step of comparing further comprises the steps of:

providing an initial difference table for the corresponding subset of Search and File points,

providing an initial proximity value for each entry on said initial difference table,

extracting a purged difference table from said initial difference table, said purged difference table being limited to a set of entries having no duplicate Search point entries, the entries in said purged difference table being based on those entries in said initial difference table having the higher proximity values, said purged difference table being the difference table for said steps of shifting and differentially adjusting.

17. The method of claim 16 further comprising the step of providing a final difference table that is limited to a predetermined number of entries based on those entries having the highest proximity values in the table provided by said constant and said differential adjustment means.

18. The method of any of claim 14 or 15 through 74 wherein the number of said subsets in said step of segmenting is at least four to divide said image into at least four subsets along a first axis.

19. The method of any of claims 14 or 15 through 74 wherein the number of said subsets in said step of segmenting is sixteen, to divide said image into a two dimensional matrix of four by four subsets.