Image analysis – Applications – Personnel identification
Reexamination Certificate
1998-04-16
2001-10-09
Au, Amelia M. (Department: 2722)
Image analysis
Applications
Personnel identification
C382S209000
Reexamination Certificate
active
06301376
ABSTRACT:
BACKGROUND OF THE INVENTION
The most popular method used by fingerprint verification device vendors is the minutia based verification. This is also the oldest method used by the FBI and other government agencies and in other countries around the world. It is well established understood and standardized. There is an ANSI (American National Standards Institute) standard for “Data Format for the Interchange of Fingerprint Information”, describing a common format for interchange of minutia based fingerprint data. Minutia data represents four categories of fingerprint characteristic points: ridge ending, bifurcation, compound (trifurcation or crossover) and type undetermined. A ridge ending occurs when a friction ridge begins or ends within the fingerprint and without splitting into two or more continuing and the ridge must be longer than it is wide. A bifurcation occurs when a ridge divides or splits to form two ridges that continue past the point of division for a distance that is at least equal to the spacing between adjacent ridges at the point of bifurcation. A compound type occurs either when there is trifurcation, which is when a single ridge splits into three ridges, or there is a crossover, i.e. when two ridges intersect each other. Finally, when the minutia cannot be clearly categorized as one of the above three types, it is designated as undetermined. Minutia based systems, however, are pretty slow, and any defects in the input fingerprint image could generate false minutia. They are used predominantly in large fingerprint identification databases where input fingerprint data could be manually quality controlled and because minutia fingerprint data could be transferred between systems due to format standardization. They are also pretty expensive, which further limits their areas of application.
There are other systems, based on full image analysis. They perform complex two dimensional FFT's on the fingerprint data. Then in the frequency domain a two dimensional cross correlation is done between 2D-FFT of the fingerprint to be verified and the conjugate of the template image (or vice versa) and the cross correlation result is thresholded to determine if the images are similar. In some devices cross correlation is performed optically.
Those systems are usually much faster than the minutia based ones. However, the size of their templates is usually much larger and they are not very suitable for large fingerprint data bases due to the nature of the verification process.
Both described systems are also very sensitive to the finger placement on the fingerprint image scanner devices. Relatively small displacements or rotations of the finger could lead to false results.
The present invention is directed to a system and algorithm to avoid shortcomings of the existing fingerprint enrollment and verification systems and algorithms.
According to various aspects of the present invention, digitized fingerprint image data is obtained. From it, sets of data called “yardsticks” are extracted. The yardsticks are preferably linear sections from the enrollment fingerprint representation. Preferably, each yardstick comprises data for a set of co-linear pixels which extend in a predetermined direction, e.g. row-wise or column-wise. In a basic enrollment, the yardsticks do not seek to find features or subfeatures, but simply represent the data for the fingerprint to be enrolled. Preferably, these yardsticks are divided into segments, which are subsets of the yardstick data. Preferably, each segment represents data for a group of adjacent pixels in the yardstick, and there preferably will be a first segment, then a second segment, and so forth, depending on how many segments are desired per yardstick. Preferably, the yardsticks and segments thereof are stored in a predetermined order in a data structure, which may be called a template. In one variation, each yardstick may be composed of parts of two adjacent rows (when yardsticks are aligned row-wise).
For fingerprint verification, the disclosed apparatus and method seek a statistical similarity between an enrolled fingerprint and the fingerprint to be verified. It first seeks to match a first yardstick to a corresponding amount of data representing the fingerprint image to be verified. Yardstick data or segment data is moved throughout the image, preferably in a predetermined order, and comparisons are made to find a sufficient match. This match is a statistical match which may be calculated using, for example, the Hamming distance.
With reference to embodiments using the segmented yardsticks, preferably a provision is made so that a yardstick may be found to match even if not every segment is matched. That is, if enough other segments of that yardstick sufficiently match the data, the method and apparatus are allowed to conclude that a match has been found for the yardstick.
Once the first yardstick has been matched, the location of the match is known, and because the location of the other yardsticks to be tested is known relative to the position of the first yardstick, the method and apparatus checks other yardsticks in only limited numbers of locations.
Preferably the apparatus and method employ an optimization routine during some of the matching tests. In such a procedure, if a match is found, the threshold for declaring a match is lowered, and testing repeats with repeated lowerings of the threshold until the relevant segment is found not to match. This indicates that the immediately prior test was the best match, and the procedure continues.
Provision is made in the preferred method and apparatus according to other features to permit verification despite entire yardsticks not matching the image. After matching a first yardstick, or illustratively the first two yardsticks, subsequent yardsticks are permitted not to match, and for each non-matching yardstick, a mismatch counter or count is incremented. The yardsticks may be grouped by position or otherwise so that if, illustratively, the non-matching yardstick is located below the first yardstick, then a first mismatch count is incremented, but if a non-matching yardstick is located above the first matching yardstick, then a second mismatch count is incremented. Various decision rules are permitted with this arrangement where, for example, rejection ratios and tolerances are to be controlled. Illustratively, if the number of failed yardsticks passes a preselected threshold number, that threshold number may be increased. It alternatively may be ignored, with the possibility of maintaining or tightening the tolerance for the other mismatch count. Of course, the decision algorithm may require all yardsticks that are presented for match to find a match. Not all yardsticks need to be presented, however, and in one version described herein, only six yardsticks are employed, and even that embodiment may use a mismatch count to permit some yardsticks to remain unmatched.
SUMMARY OF THE INVENTION
The size of the template produced during enrollment is very compact, smaller than that of full image analysis systems, and comparable to that of minutia based systems. Due to the hierarchical way of organization this algorithm is much faster than existing ones and also allows easy implementation in both, verification and identification systems—one to one, and one to many.
The template is comprised of a number of line patterns called for convenience “yardsticks”. Those yardsticks represent parts of video lines from the acquired during enrollment process fingerprint image and are organized in a special order inside the template.
The consequential “sliding yardstick” comparison process with the fingerprint image acquired for verification, during verification part of the algorithm allows for very wide tolerances in regard to positioning and skew of the finger to be verified on the finger image input scanner device.
The code implementing the algorithm is very efficient and allows the use of low cost digital signal processor (DSP) engines. Memory requirements are very reduced.
This approach permits adjustm
Au Amelia M.
Miller Martin
LandOfFree
Segmented sliding yardsticks error tolerant fingerprint... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Segmented sliding yardsticks error tolerant fingerprint..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Segmented sliding yardsticks error tolerant fingerprint... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2567371