Gray scale matcher

• US 7,450,741 B2
• Filed: 06/22/2004
• Issued: 11/11/2008
• Est. Priority Date: 06/23/2003
• Status: Active Grant

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Lo, Peter Z., Daniel, Sam M., Wabgaonkar, Harshawardhan M.
• Primary Examiner(s): Ahmed; Samir A
• Assistant Examiner(s): Koziol; Stephen R
• Application Number:
  US10/873,790
• Publication Number:
  US 20040258284A1
• Time in Patent Office: 1,603 Days
• Field of Search: 382/115, 382/116, 382/124, 382/125, 382/168, 382/169, 382/170
• US Class Current: 382/124
• CPC Class Codes: G06V 40/1365 Matching; Classification

Abstract

A method for comparing a first print image having a first set of minutiae to a second print image having a second set of minutiae, wherein at least a second subset of minutiae from the second set is mated to a first subset of minutiae from the first set, the method that includes the steps of: selecting (350) a first pair of minutiae from the first subset and a second pair of corresponding mated minutiae from the second subset; generating (350) a first segment based on the first pair of minutiae and a second segment based on the second pair of minutiae; generating (360) a first cross-section profile based on the first segment and a second cross-section profile based on the second segment; and computing (365) at least one similarity measure that is indicative of the similarity between the first cross-section profile and the second cross-section profile.

Claims

1. A method for comparing a first print image having a first set of minutiae to a second print image having a second set of minutiae, wherein at least a second subset of minutiae from the second set is mated to a first subset of minutiae from the first set, the method comprising the steps of:

selecting a first pair of minutiae from the first subset and a second pair of corresponding mated minutiae from the second subset;

generating a first segment by connecting the first pair of minutiae, wherein the first pair of minutiae are endpoints to the first segment and a second segment by connecting the second pair of minutiae, wherein the second pair of minutiae are endpoints to the second segment;

extending the first segment or the second segment so that one segment is longer than the other segment;

generating a first cross-section waveform profile based on the first segment and a second cross-section waveform profile based on the second segment, wherein the extended segment is used to generate a corresponding extended cross-section waveform profile that is longer that the other cross-section waveform profile by a predetermined number of samples;

computing at least one similarity measure that is indicative of the similarity between the first cross-section waveform profile and the second cross-section waveform profile by correlating the shorter cross-section waveform profile against the extended cross-section waveform profile; and

calculating a metric based on the at least one computed similarity measure which indicates similarity between the first print image and the second print image.

2. The method of claim 1, wherein the minutiae in the first pair correspond to a first pair of pixel locations on the first print image and the minutiae in the second pair correspond to a second pair of pixel locations on the second print image, the method further comprising the steps of:

sampling the first print image based on at least the first pair of pixel locations for generating the first segment comprising a first number of samples; and

sampling the second print image based on at least the second pair of pixel locations for generating the second segment comprising a second number of samples.

3. The method of claim 2, wherein the first and second segments each comprise at least one of:

a linear segment;

a dithered segment;

a piecewise linear segment;

or an orthogonal segment.

4. The method of claim 3, wherein:

the first print image is sampled based upon the first pair of pixel locations and based on at least one intermediate pixel location closest to a straight line connecting the first pair of pixel locations to generate a first linear segment; and

the second print image is sampled based upon the second pair of pixel locations and based on at least one intermediate pixel location closest to a straight line connecting the second pair of pixel locations to generate a second linear segment.

5. The method of claim 2, wherein the first print image is a first grayscale image, and the second print image is a second grayscale image, the method further comprising the steps of:

obtaining a first set of gray scale values corresponding to the first number of samples and generating the first cross-section waveform profile from the first set of gray scale values; and

obtaining a second set of gray scale values corresponding to the second number of samples and generating the second cross-section waveform profile from the second set of gray scale values.

6. The method of claim 5, wherein the grayscale image is band-limited using at least one band-pass filtering technique.

7. The method of claim 1, wherein the first and the second segments each have a first end and a second end, and the extended segment is extended equally on both ends.

8. The method of claim 1, wherein the extended cross-section waveform profile and the shorter cross-section waveform profile each have a first end and a second end, the step of correlating the shorter cross-section waveform profile against the extended cross-section waveform profile comprising the steps of:

aligning the first end of the shorter cross-section waveform profile with the first end of the extended cross-section waveform profile;

aligning the shorter cross-section waveform profile with the extended cross-section waveform profile at least one predetermined interval between the first and second ends of the extended cross-section waveform profile;

aligning the second end of the shorter cross-section waveform profile with the second end of the extended cross-section profile; and

computing a corresponding correlation coefficient at each alignment, whereby the correlation coefficient is the similarity measure at its corresponding alignment.

9. The method of claim 8 further comprising the step of selecting at least one maximum correlation coefficient from the computed correlation coefficients that is indicative of at least one maximum point of similarity between the first cross-section waveform profile and the second cross-section waveform profile.

10. The method of claim 9, wherein a maximum normal correlation coefficient is selected that is indicative of a maximum point of positive similarity between the first cross-section waveform profile and the second cross-section waveform profile and a maximum absolute correlation coefficient is selected that is indicative of a maximum point of absolute similarity between the first cross-section waveform profile and the second cross-section waveform profile.

11. The method of claim 10, further comprising the step of computing a transformed maximum normal correlation coefficient and a transformed maximum absolute correlation coefficient.

12. The method of claim 11, wherein the transformed maximum normal and absolute correlation coefficients are computed based on at least one of image quality along the first and the second segments and Luclidean length of one of the first segment and the second segment.

13. The method of claim 10 further comprising the steps of:

computing a maximum normal correlation coefficient for each possible combination of mated minutiae pairs in the first and second subsets to generate a set of maximum normal correlation coefficients; and

computing a maximum absolute correlation coefficient for each possible combination of mated minutiae pairs in the first and second subsets to generate a set of maximum absolute correlation coefficients.

14. The method of claim 13 further comprising the steps of computing a first metric as a function of the correlation coefficients in the set of maximum normal correlation coefficients and a second metric as a fUnction of the correlation coefficients in the set of maximum absolute correlation coefficients.

15. The method of claim 14 further comprising the step of computing a first combined metric based on the fusion of the first metric with the second metric.

16. The method of claim 15, wherein the fusion is performed based on at least one of:

addition and multiplication.

17. The method of claim 15, wherein in the first combined metric is generated in a first fingerprint matcher system and a third metric is generated in a second fingerprint matcher system, the method further comprising the step of computing a second combined metric based on the fusion of the first combined metric with the third metric.

18. The method of claim 17, wherein the fusion is performed based on at least one of:

addition, multiplication, and an eigenspace method.

19. The method of claim 10 further comprising the steps of selecting at least one non-mated minutiae from one of the first and the second sets of minutiae that is within a predetermined distance from at least one minutiae in one of the first and the second selected pairs of minutiae and regenerating the corresponding segment and cross-section profile, and re-computing the corresponding maximum normal correlation coefficient and maximum absolute correlation coefficient.

20. The method of claim 10 further comprising the steps of:

generating a segment and corresponding cross-section waveform profile for each possible combination of mated minutiae pairs in the first subset;

generating a segment and corresponding cross-section waveform profile for each possible combination of mated minutiae pairs in the second subset;

combining at least a portion of the cross-section waveform profiles generated based on the minutiae pair combinations of the first subset to generate a first composite cross-section waveform profile;

combining at least a portion of the cross-section waveform profiles generated based on the minutiae pair combinations of the second subset to generate a second composite cross-section waveform profile;

over-sampling one of the first composite cross-section waveform profile and the second composite cross-section waveform profile; and

computing the maximum normal correlation coefficient and the maximum absolute correlation coefficient based on the correlation of the shorter composite cross-section waveform profile against the longer composite cross-section waveform profile.

21. The method of claim 20, wherein the first number of samples is different from the second number of samples, the method further comprising the step of over-sampling one of the first and the second cross-section waveform profiles for causing the first and the second cross-section waveform profiles to have the same number of samples prior to the step of extending one of the first and the second segments.

22. The method of claim 21 further comprising the step of over-sampling the extended cross-section waveform profile for causing it to be longer than the shorter cross-section waveform profile by the predetermined number of samples.

23. The method of claim 21 wherein the over-sampling is done using interpolation.

24. The method of claim 23, wherein the interpolation is one of a linear, a quadratic, and a cubic spline interpolation technique.