US6072895A — System and method using minutiae pruning for fing…

Claim 1

Independent Claim 182 words

A computer system for imaging fingerprints, comprising: a computer having a user interface, a central processing unit (CPU), a disk storage that contains a plurality of data records representing one or more fingerprint images and an image capturing subsystem that produces an image of a target fingerprint; a feature extractor that produces one or more features from the target image, the features being minutiae of the target fingerprint, feature extraction being based on an angle--distance metric defined as a function of both locations and orientations of a minutiae pair, in accordance with the relationships D'=D2 * (1.0+A), and A=K*(difference (t1, (t 2 +π))) exp (J) where D2 is the regular Euclidean distance between the minutiae; t1 is the orientation of a first minutiae in radians; t2 is the orientation of a second minutiae in radians; the difference function evaluates an absolute value of the difference in orientation of the minutiae; K is in the range of 0.8 to 1.2; J is in the range of 1.0 to 2.0; and wherein minutiae pairs are not extracted if D' is below a predetermined value.

Claim 2

Dependent Claim 182 words

A computer system for imaging fingerprints, comprising: a computer having a user interface, a central processing unit (CPU), a disk storage that contains a plurality of data records representing one or more fingerprint images and an image capturing subsystem that produces an image of a target fingerprint; a feature extractor that produces one or more features from the target image, the features being minutiae of the target fingerprint, feature extraction being based on an angle--distance metric defined as a function of both locations and orientations of a minutiae pair, in accordance with the relationships D'=D2 * (1.0+A), and A=K*(difference (t1, (t 2 +π))) exp (J) where D2 is the regular Euclidean distance between the minutiae; t1 is the orientation of a first minutiae in radians; t2 is the orientation of a second minutiae in radians; the difference function evaluates an absolute value of the difference in orientation of the minutiae; K is in the range of 0.8 to 1.2; J is in the range of 1.0 to 2.0; and wherein minutiae pairs are not extracted if D' is below a predetermined value.

Claim 3

Dependent Claim 50 words

A system, as in claim 1, further comprising: a minutiae pruner that determines if one or more of the minutiae produced by the feature extractor meet one of a set of pruning criteria, said minutiae pruner deleting minutiae that fail to meet any one of said set of pruning criteria.

Claim 4

Dependent Claim 35 words

A system, as in claim 2, where one of the pruning criterion is that the minutiae is deleted if the edge distance from the boundary of the fingerprint image is less than an edge threshold.

Claim 5

Dependent Claim 47 words

A system, as in claim 2, where first and second minutiae are each a ridge ending, where one of the pruning criterion used for deleting both the first and second minutiae is if the distance between the first and second minutiae is less than a threshold distance.

Claim 6

Dependent Claim 13 words

A system, as in claim 4, where the threshold distance is 4 pixels.

Claim 7

Dependent Claim 53 words

A system, as in claim 2, where a first minutiae is a ridge bifurcation and a second minutiae is a ridge ending, where one of the pruning criterion used for deleting both the first and second minutiae is if the distance between the first and second minutiae is less than a threshold distance.

Claim 8

Dependent Claim 13 words

A system, as in claim 6, where the threshold distance is 4 pixels.

Claim 9

Dependent Claim 45 words

A system, as in claim 2, where first and second minutiae are ridge bifurcations, where one of the pruning criterion used for deleting both the first and second minutiae is if the distance between the first and second minutiae is less than a threshold distance.

Claim 10

Dependent Claim 13 words

A system, as in claim 8, where the threshold distance is 4 pixels.

Claim 11

Dependent Claim 44 words

A system, as in claim 2, where first and second minutiae are parallel, where one of the pruning criterion used for deleting both the first and second minutiae is if a distance between the first and second minutiae is less than a threshold distance.

Claim 12

Dependent Claim 26 words

A system, as in claim 10, where the first and second minutiae are parallel if the orientation of each of the minutiae is within a tolerance.

Claim 13

Dependent Claim 13 words

A system, as in claim 11, where the tolerance is within 16 degrees.

Claim 14

Dependent Claim 45 words

A system, as in claim 2, where one of the pruning criterion used for deleting minutiae is if first and second minutiae are within a geometric distance that is less than a threshold distance, and the orientations of the first and second minutiae are anti-parallel.

Claim 15

Dependent Claim 26 words

A system, as in claim 13, where the first and second minutiae are anti-parallel if the orientation of each of the minutiae is within a tolerance.

Claim 16

Dependent Claim 13 words

A system, as in claim 14, where the tolerance is between 10-20 degrees.

Claim 17

Dependent Claim 26 words

A system, as in claim 13, where the first and second minutiae are also collinear and are deleted if they are within a second distance threshold.

Claim 18

Dependent Claim 52 words

A system, as in claim 13, where the first and second minutiae are deleted if the first and second minutiae are also collinear, within a third distance threshold, and an average brightness of all of the pixels on a line between the first and second minutiae is greater than a brightness threshold.

Claim 19

Dependent Claim 53 words

A system, as in claim 2, where an end distance of a ridge ending minutiae is less than a threshold distance from the ridge, and where one of the pruning criterion results in the ridge ending minutiae being deleted and a new bifurcation introduced at a linearly extrapolated ridge ending intersecting the ridge.

Claim 20

Dependent Claim 13 words

A system, as in claim 18, where the threshold distance is 8 pixels.

Claim 21

Dependent Claim 43 words

A system, as in claim 2, where for a pair of minutiae comprised of first and second minutiae, one of the pruning criterion used for deleting both the first and second minutiae is if they are mutual nearest neighbors within a threshold distance.

Claim 22

Dependent Claim 16 words

A system, as in claim 20, where the threshold distance is between 8 and 12 pixels.

Claim 23

Dependent Claim 43 words

A system, as in claim 2, where for a pair of minutiae comprised of first and second minutiae, one of the pruning criterion used for deleting both the first and second minutiae is if they are mutual closest neighbors within a threshold distance.

Claim 24

Dependent Claim 14 words

A system, as in claim 22, where the threshold distance is between 12-18 pixels.

Claim 25

Dependent Claim 46 words

A system, as in claim 2, where one of the pruning criterion is based on a distribution density in a region of the target image, and the minutiae in the region are deleted if the minutiae density in the region is larger than a threshold density.

Claim 26

Dependent Claim 15 words

A system, as in claim 24, where the threshold density is between two and four.

Claim 27

Dependent Claim 63 words

A system, as in claim 2, where one of the pruning criterion is based on a ridge function, the ridge function being a length of a selected ridge, and where the selected ridge, and all of zero or more of the minutiae attached to the selected ridge, are deleted if the selected ridge has a length that is smaller that a threshold length.

Claim 28

Dependent Claim 16 words

A system, as in claim 26, where the threshold length is between eight to sixteen pixels.

Claim 29

Dependent Claim 56 words

A system, as in claim 2, where one of the pruning criterion is based on a ridge function, and the ridge function is a density of all of the ridges in a region, and the minutiae in the region are deleted if the density of ridges in the region is larger than a threshold ridge density.

Claim 30

Dependent Claim 16 words

A system, as in claim 28, where the threshold ridge density is between two and four.

Claim 31

Dependent Claim 89 words

A system, as in claim 2, where the pruning criteria are comprised of at least one of: a location of the minutiae being within an edge distance of a foreground boundary, a contrast difference between an orthogonal contrast and a parallel contrast of one or more of the minutiae, a distance between a first and second minutiae, an orientation difference between the first and second minutiae, a distribution density of two or more minutiae, a ridge ending being within a ending distance of a ridge, and a ridge function.

Claim 32

Dependent Claim 53 words

A system, as in claim 1, further comprising: a minutiae pruner that determines if one or more of the minutiae produced by the feature extractor meet one of a set of pruning criteria, said minutiae pruner marking for subsequent deletion, minutiae that fail to meet any one of said set of pruning criteria.

Claim 33

Dependent Claim 8 words

A system, as in claim 1, wherein K=1.0.

Claim 34

Dependent Claim 8 words

A system, as in claim 1, wherein J=1.0.

Claim 35

Independent Claim 145 words

A system for imaging fingerprints, comprising: a computer having a user interface, a central processing unit (CPU), a disk storage that contains a plurality of data records representing one or more fingerprint images and an image capturing subsystem that produces an image of a target fingerprint; a feature extractor that produces one or more features from the target image, the features being minutiae of the target fingerprint; and a minutiae pruner that determines if one or more of the minutiae produced by the feature extractor meet one of a set of pruning criteria, and that deletes the minutiae if the pruning criteria is met, where the pruning criteria is that the contrast difference between the orthogonal contrast and the parallel contrast of one or more of the minutiae, normalized by an average brightness over an area of the fingerprint, is less than a contrast threshold.

Claim 36

Independent Claim 145 words

A system for imaging fingerprints, comprising: a computer having a user interface, a central processing unit (CPU), a disk storage that contains a plurality of data records representing one or more fingerprint images and an image capturing subsystem that produces an image of a target fingerprint; a feature extractor that produces one or more features from the target image, the features being minutiae of the target fingerprint; and a minutiae pruner that determines if one or more of the minutiae produced by the feature extractor meet one of a set of pruning criteria, and that deletes the minutiae if the pruning criteria is met, where the pruning criteria is that the contrast difference between the orthogonal contrast and the parallel contrast of one or more of the minutiae, normalized by an average brightness over an area of the fingerprint, is less than a contrast threshold.

Claim 37

Dependent Claim 46 words

A system, as in claim 34, where the normalized contrast difference, called a feature confidence, G, is: G=(Var.sub.o -Var.sub.p)/log(B), where Var o and Var p are orthogonal and parallel contrasts at a pixel, respectively and B is the average brightness of a neighborhood of the pixel.

Claim 38

Independent Claim 154 words

A system for imaging fingerprints, comprising: a computer having a user interface, a central processing unit (CPU), a disk storage that contains a plurality of data records representing one or more fingerprint images and an image capturing subsystem that produces an image of a target fingerprint; a feature extractor that produces one or more features from the target image, the features being minutiae of the target fingerprint; and a minutiae pruner that determines if one or more of the minutiae produced by the feature extractor meet one of a set of pruning criteria, and that deletes the minutiae if the pruning criteria is met, where the pruning criteria is based on a ridge function and the ridge function is: WF=(sum of a pixel-wise change in a direction of a selected ridge)/(k*length)), and the minutiae in the region are deleted if the WF is larger than a threshold wiggle factor, and k is preferably 1.

Claim 39

Independent Claim 154 words

A system for imaging fingerprints, comprising: a computer having a user interface, a central processing unit (CPU), a disk storage that contains a plurality of data records representing one or more fingerprint images and an image capturing subsystem that produces an image of a target fingerprint; a feature extractor that produces one or more features from the target image, the features being minutiae of the target fingerprint; and a minutiae pruner that determines if one or more of the minutiae produced by the feature extractor meet one of a set of pruning criteria, and that deletes the minutiae if the pruning criteria is met, where the pruning criteria is based on a ridge function and the ridge function is: WF=(sum of a pixel-wise change in a direction of a selected ridge)/(k*length)), and the minutiae in the region are deleted if the WF is larger than a threshold wiggle factor, and k is preferably 1.

Claim 40

Dependent Claim 16 words

A system, as in claim 36, where the threshold wiggle factor is between 0.3 to 0.6.

Claim 41

Dependent Claim 150 words

A computer implemented method for processing a fingerprint image, comprising steps of: inputting an image of a target fingerprint; processing the image with a feature extractor to generate a set of minutiae of the target fingerprint, feature extraction being based on an angle--distance metric defined as a function of both locations and orientations of a minutiae pair, in accordance with the relationships D'=D2 * (1.0+A), and A=K*(difference (t1, (t 2 +π))) exp (J) where D2 is the regular Euclidean distance between the minutiae; t1 is the orientation of a first minutiae in radians; t2 is the orientation of a second minutiae in radians; the difference function evaluates an absolute value of the difference in orientations of the minutiae; K is in the range of 0.8 to 1.2; J is in the range of 1.0 to 2.0; and wherein minutiae pairs are not extracted if D' is below a predetermined value.

Claim 42

Dependent Claim 150 words

A computer implemented method for processing a fingerprint image, comprising steps of: inputting an image of a target fingerprint; processing the image with a feature extractor to generate a set of minutiae of the target fingerprint, feature extraction being based on an angle--distance metric defined as a function of both locations and orientations of a minutiae pair, in accordance with the relationships D'=D2 * (1.0+A), and A=K*(difference (t1, (t 2 +π))) exp (J) where D2 is the regular Euclidean distance between the minutiae; t1 is the orientation of a first minutiae in radians; t2 is the orientation of a second minutiae in radians; the difference function evaluates an absolute value of the difference in orientations of the minutiae; K is in the range of 0.8 to 1.2; J is in the range of 1.0 to 2.0; and wherein minutiae pairs are not extracted if D' is below a predetermined value.

Claim 43

Dependent Claim 73 words

A method, as claimed in claim 34, further comprising: pruning the set of minutiae to obtain a subset of the minutiae that are determined to be the most reliable for matching the target fingerprint image to one of a plurality of prestored fingerprint images, the step of pruning using a set of pruning criteria comprised of a location and contrast-based criterion, a distance and angle-based criterion, a distribution-based criterion, and a ridge-based criterion.

Claim 44

Dependent Claim 77 words

A method, as claimed in claim 34, further comprising: marking for pruning the set of minutiae to obtain a subset of the minutiae that are determined to be the most reliable for matching the target fingerprint image to one of a plurality of prestored fingerprint images, the step of marking for pruning using a set of pruning criteria comprised of a location and contrast-based criterion, a distance and angle-based criterion, a distribution-based criterion, and a ridge-based criterion.

Claim 45

Dependent Claim 9 words

A method, as claimed in claim 34, wherein K=1.0.

Claim 46

Dependent Claim 9 words

A method, as claimed in claim 34, wherein J=1.0.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2003-06-06	2003-12-06	2004-06-06	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2007-06-06	2007-12-06	2008-06-06	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2011-06-06	2011-12-06	2012-06-06	$7700.00	Window Closed / Lapsed

System and method using minutiae pruning for fingerprint image processing

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag