Image analysis – Applications – Personnel identification
Reexamination Certificate
1998-02-25
2002-11-26
Chang, Jon (Department: 2623)
Image analysis
Applications
Personnel identification
C382S201000
Reexamination Certificate
active
06487306
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of image processing. More specifically, the invention relates to a system and method for processing and matching fingerprint images.
BACKGROUND OF THE INVENTION
There exist systems for accomplishing automatic authentication or identification of a person using his/her fingerprint. A fingerprint of a person comprises a distinctive and unique ridge pattern structure. For authentication or identification purposes, this ridge pattern structure can be characterized by endings and bifurcations of the individual ridges. These features are popularly known as minutiae.
An example of portion of a fingerprint is shown in FIG.
1
A. The minutiae for the fingerprint shown in
FIG. 1A
are shown in
FIG. 1B
as being enclosed by “boxes.” For example, box
101
B shows a bifurcation minutiae of a bifurcated ridge
101
A and box
103
B shows a ridge ending minutiae of ridge
103
A. Note that minutiae on the ridges in fingerprints have directions (also called orientations)
105
associated with them. The direction
113
B of a minutiae at a ridge end
103
B is the direction in which the end of the ridge points. The direction
111
B of a bifurcation minutiae
101
B is the direction in which the bifurcated ridge points. Minutiae also have locations which are the positions, with respect to some coordinate system, of the minutiae on the fingerprint.
FIG. 2
is a flow chart showing the steps generally performed by a typical prior art system
200
.
In step
210
, the image is acquired. This acquisition of the image could either be through a CCD camera and framegrabber interface or through a document scanner communicating with the primary computing equipment.
Once the image is acquired into the computer memory or onto disk, relevant minutia features are extracted (
220
). Not all of the features thus extracted are reliable; some of the unreliable features are optionally edited or pruned (step
230
), e.g., manually. The resultant reliable features are used for matching the fingers (step
240
).
The fingerprint feature extraction
220
, pruning
230
, and matching system
240
constitute the primary backbone
250
of a typical minutiae-based automatic fingerprint identification systems (AFIS). The matching results are typically verified by a human expert (step
260
). The verification may also be performed automatically. The following reference describes examples of the state of the prior art for feature extraction:
Nalini K. Ratha and Shaoyun Chen and Anil K. Jain,
Adaptive flow orientation based feature extraction in fingerprint images, Journal of Pattern Recognition, vol. 28, no. 11, pp. 1657-1672, November, 1995.
This reference is herein incorporated by reference in its entirety.
FIG. 3A
is a flow chart showing the prior art steps performed by a feature extraction process
220
that are similar to some of the feature extraction methods proposed by Ratha, Jain, and Chen in the article incorporated above.
It is often not desirable to directly use the input fingerprint image for feature extraction. The fingerprint image might need an enhancement or preprocessing before one could further extract minutiae. Typically, a smoothing process is employed to reduce the pixel-wise noise (step
305
).
After the preprocessing stages, prior art systems find the directions of the ridge flow (step
310
). The next important step in the processing is finding the exact location of the finger in the image. To accomplish this, a process referred to as the foreground/background segmentation (step
315
) separates the finger part of the image from the background part of the image. Once the finger part is localized, i.e., segmented to define its location, the next step is to extract the ridges from the finger image (step
320
). The ridges thus extracted are thick and might contain some noisy artifacts which do not correspond to any meaningful structures on the finger. These small structures, i.e., the noisy artifacts, can be safely removed and the longer structures are smoothed (step
325
). The longer structures are thinned to one-pixel width and then processed to remove any other artifacts using morphological operators (step
330
). The locations and orientations of ridge endings and bifurcations are then extracted from the thinned structures (step
335
) to obtain the minutiae. In some systems, a “cleanup” or postprocessing
340
is performed. Here undesirable minutiae are removed based on certain criteria.
One of the prevalent methods of fingerprint authentication and identification methods is based on minutiae features. These systems need to process the fingerprint images to obtain accurate and reliable minutiae features to effectively determine the identity of a person.
The following reference describes examples of the state of the prior art fingerprint matcher:
N. Ratha, K. Karu, S. Chen and A. K. Jain, A Real-time Matching System for Large Fingerprint Database, IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 18, Number 8, pages 799-813, 1996.
This reference is herein incorporated by reference in its entirety.
Given two (input and template) sets of features originating from two fingerprints, the objective of the feature matching system is to determine whether or not the prints represent the same finger.
FIG. 3B
is a flow chart showing the prior art steps performed by a typical feature matching system
240
that is similar to the feature matching system proposed by Ratha, Karu, Chen, and Jain in the article incorporated above.
A minutiae in the input fingerprint and a minutiae in the template fingerprint are said to be corresponding if they represent the identical minutiae scanned from the same finger. An alignment estimation method based on Generalized Hough Transform (as in above cited Ratha et al. reference) estimates the parameters of the overall rotation, scaling and translation between the features of the input and template fingerprint (
350
). In step
360
the input fingerprint features are aligned with the template fingerprint using the rotation, translation, and scaling parameters estimated in step
350
. In step
370
, the aligned features of the input fingerprint features are matched with the features of the template fingerprint features. The matching consists of counting the number of features in the aligned input fingerprint representation for which there exists a corresponding consistent feature in the template fingerprint representation. The verification of a corresponding feature is performed as follows: for each feature in the aligned input fingerprint feature, the matcher determines whether there is a consistent template fingerprint feature in its rectangular neighborhood whose size is predetermined. Normalizer
380
takes the matching score generated by the matcher and computes a normalized matching score. The higher the normalized score, the higher the likelihood that the test and template fingerprints are the scans of the same finger.
STATEMENT OF PROBLEMS WITH THE PRIOR ART
Determining whether two representations of a finger extracted from its two impressions, scanned at times possibly separated by a long duration of time, are indeed representing the same finger, is an extremely difficult problem. This difficulty can be attributed to two primary reasons. First, if the test and template representations are indeed matched (also referred to as mated) pairs, the feature correspondence between the test and template minutiae in the two representations is not known. Secondly, the imaging system presents a number of peculiar and challenging situations some of which are unique to the fingerprint image capture scenario:
(i) Inconsistent contact: The act of sensing distorts the finger. Determined by the pressure and contact of the finger on the glass platen, the three-dimensional surface of the finger gets mapped onto the two-dimensional surface of the glass platen. Typically, this mapping function is uncontrolled and results in different inconsistently mapped fingerprint images across the impressions.
(ii) Non-uniform co
Bolle Rudolf Maarten
Hong Lin
Jain Anil K.
Pankanti Sharathchandra Umapathirao
Chang Jon
International Business Machines - Corporation
Ohlandt Greeley Ruggiero & Perle LLP
Percello, Esq. Louis J.
LandOfFree
System and method for deriving a string-based representation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for deriving a string-based representation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for deriving a string-based representation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2992189