Determining a point correspondence between two points in two respective (fingerprint) images

• US 6,049,621 A
• Filed: 02/25/1998
• Issued: 04/11/2000
• Est. Priority Date: 08/22/1997
• Status: Expired due to Term

• Current Assignee: Lenovo PC International Limited (Lenovo Group Ltd.)
• Original Assignee: International Business Machines Corporation
• Inventors: Pankanti, Sharathchandra Umapathirao, Bolle, Rudolf Maarten, Hong, Lin, Jain, Anil K.
• Primary Examiner(s): Kelley, Christopher S.
• Application Number:
  US09/030,345
• Time in Patent Office: 776 Days
• Field of Search: 382/125, 382/115, 382/124, 382/173, 382/209
• US Class Current: 382/125
• CPC Class Codes: G06V 40/1365 Matching; Classification

Abstract

The invention is a system and method for determining a correspondence between a point selected from a set of points extracted from one image and an another point selected from the second set of points extracted from another image based on similarity of relationships of attributes associated with segments attached to the points.

Claims

1. A system for determining a point correspondence between two points in two respective image, comprising:

a computer having one or more central processing units (CPUs) and a memory;

a first image stored in the memory, the first image having one or more first points each of the first points located on a respective first curved line;

one or more second images stored in the memory, the second image having one or more second points each of the second points located on a respective second curved line;

a first reference point selector, executed by the CPU, that selects one of the first points as a first reference point, the first reference point selector also selecting a first reference segment the first curved line on which the first reference point is located;

a second reference point selector, executed by the CPU, that selects one of the second points as a second reference point, the second reference point selector also selecting a second reference segment the second curved line on which the second reference point is located;

a first segmentor, executed by the CPU, that segments the first reference segment into two or more first subsegments, each of the first subsegments ending at a respective first subsegment point, the first segmentor determining a first set of first segment relations between the first reference point and one or more of the first subsegment points;

a second segmentor, executed by the CPU, that segments the second reference segment into two or more second subsegments, each of the second subsegments ending at a respective second subsegment point, the second segmentor determining a second set of second segment relations between the second reference point and one or more of the second subsegment points; and

a reference point matcher, executed by the CPU, that determines a correspondence between the first reference point and one of the second reference points if the set of first segment relations have the same values as the respective values of the set of second segment relations.

2. A system, as in claim 1, where the reference point matcher determines a correspondence between the first reference point and one of the second reference points if the values of the set of first segment relations is similar to the values of the respective set of second segment relations.

3. A system, as in claim 2, where the similarity is determined by when a function of the values of the set of first segment relations and the values of the respective set of of second segment relations less than a threshold.

4. A system, as in claim 3, where the function is given by:

##EQU10## where d_i are the values of the set of first segment relations and where D_i are the values of the set of second segment relations.

5. A system, as in claim 1, where the relations include any one or more of the following:

distance, angle, curvatures, and tangent angles.

6. A system, as in claim 1, where the first and second images are fingerprint images, the curved lines are ridge lines, and the corresponding points are minutia.

7. A system, as in claim 1, where the first image is rotated and translated to register with the second image.

8. A system, as in claim 1, where the first and second images are matched because there is a correspondence determined between the first and second reference points in more than a threshold number of pairs of first and second reference points.