Fingerprint ID system and method

• US 5,493,621 A
• Filed: 04/15/1994
• Issued: 02/20/1996
• Est. Priority Date: 04/21/1993
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisya Matsumura Electronics
• Original Assignee: Kabushiki Kaisya Matsumura Electronics
• Inventors: Matsumura, Yoshihide
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Bella, Matthew C.
• Application Number:
  US08/228,293
• Time in Patent Office: 676 Days
• Field of Search: 382/4, 382/5, 382/26, 382/124, 382/125, 382/127, 382/209
• US Class Current: 382/125
• CPC Class Codes: G06V 40/1365 Matching; Classification

Abstract

A fingerprint ID system, which compares input fingerprint image data with registered data, with a digital signal processor exclusive for image processing use, indpendently of a central processing unit comprises: a device for scanning the input fingerprint image data for determining the thinning thereof and for extracting minutiae therefrom; a circuit for removing a pseudo minutia from the extracted minutiae; a circuit for registering the minutiae based on positions of branch points and their positional relationships; a circuit for scoring the mismatching degree between branch points in said fingerprint image data and the registered data on the basis of the norm and for judging the examinee to be the person of said registered data when the mean mismatching degree of the branch point of the minimum mimatching degee is under a predetermined value. When the recognition rate based on minutiae of a fingerprint is low, template matching data is registered and template matching of the input fingerprint image data against the registered data takes place.

Claims

1. A fingerprint ID system which compares input fingerprint image data with registered image data, comprising:

thinning processing means for thinning binary image data, said thinning processing means having thinning determination means which determines a deletable point in said binary image data by a table search in units of eight neighboring cells, and scan control means which reduces the number of times of scanning of said thinning determination means;

minutia extracting means for extracting minutiae from said image data, said minutia extracting means having means for extracting minutia candidates from said thinned image data by a table search in units of eight neighboring cells, and pseudo minutia removing means for excluding pseudo minutiae from said minutia candidates;

means for registering true minutiae of said image data;

minutia matching means for matching minutiae of said input fingerprint image data with registered minutiae;

means for registering template data for template matching;

template matching means for template matching said input fingerprint image data with registered data; and

means for;

comparing results of said minutia matching means and results of said template matching means in terms of recognition rate,

selecting the results of said minutia matching means for identifying said input fingerprint image data when the results of said minutia matching means have a higher recognition rate than the results of said template matching means, and

selecting the results of said template matching means for identifying said input fingerprint image data when the results of said template matching means have a higher recognition rate than the results of said minutia matching means.

2. The system of claim 1, wherein said thinning determination means comprises:

means for computing an adjoining cell pattern index value which is the sum total of products of predetermined weighting factors respectively assigned to eight adjoining cells surrounding a center one and pixel values of said eight adjoining cells;

means for making a table search in a memory for all combinations of cell patterns which allow changing the pixel value of said center cell from "1" to "0," said memory having stored therein said adjoining cell pattern index values of said eight adjoining cells; and

means for changing the pixel value of said center cell from "1" to "0."

3. The system of claim 1, wherein said scan control means comprises:

first image data scanning means for scanning said image data over an area of a predetermined size, said first image data scanning means including;

means for actuating said thinning determination means for each pixel on every scanning line; and

means for storing, in a memory, scan control data containing at least a flag representing whether the thinning has converged on each scanning line, positional information of that one of said adjoining cells for which the thinning has not converged on each said scannning line, and the number of contiguous cells for which the thinning has not converged on each said scanning line;

second and subsequent image data scanning means for scanning said image data only when the thinning has not converged in the preceding image data scanning, said second and subsequent image data scanning means including means for updating contents of said scan control data; and

means for determining whether the thinning of said image data has converged or not and for repeating said second and subsequent image data scanning until the thinning of said image data converges.

4. The system of claim 1, wherein said minutia extracting means comprises:

means for computing an adjoining cell pattern index value for each of eight adjoining cells surrounding a center one;

means for making a table search for said adjoining cell pattern index value from those stored in a memory; and

means whereby, when the same adjoining cell pattern index value as that of said input fingerprint data is found in said memory, the cell concerned is registered as a minutia candidate.

5. The system of claim 1, wherein said pseudo minutia removing means excludes said minutia candidate when the direction of said minutia candidate is the same as that of a counterpart of said registered fingerprint image data and a distance between them is smaller than a predetermined value.

6. The system of claim 1, wherein said minutia registering means comprises:

means for selecting, as a master branch point, a branch point closest to a center point of said image data;

means for selecting, as sub-branch points, branch points closest to said master branch point in first, second, third and fourth quadrants of an X-Y coordinate system with said master branch point at the origin thereof;

means for selecting a predetermined number of branch points in increasing order of distance to said sub-branch point in each of said first through fourth quadrants as sub-sub-branch points therein; and

means for registering at least the total number of branch points, their positional information, the positional relationships between said master branch point and said sub-branch points, and the positional relationships between said sub-branch point and said sub-sub-branch points in each quadrant.

7. A fingerprint ID system which compares input fingerprint image data with registered image data, comprising:

thinning processing means for thinning binary image data, said thinning processing means having thinning determination means which determines a deletable point in said binary image data by a table search in units of eight neighboring cells, and scan control means which reduces the number of times of scanning of said thinning determination means;

minutia extracting means for extracting minutiae from said image data, said minutia extracting means having means for extracting minutia candidates from said thinned image data by a table search in units of eight neighboring cells, and pseudo minutia removing means for excluding pseudo minutiae from said minutia candidates;

means for registering true minutiae of said image data, said image data including a plurality of quadrants;

minutia matching means for matching minutiae of said input fingerprint image data with registered minutiae, said minutia matching means including;

means for comparing the total number of branch points in said input fingerprint image data and the total number of branch points in said registered fingerprint image data;

means for selecting a predetermined number of sub-branch points in increasing order of distance to a center point of said input fingerprint image data as master branch point candidates;

means for determining if one said sub-branch point in each said quadrant in said input fingerprint image data lies in the vicinity of a corresponding sub-branch point in said registered fingerprint image data;

means for determining if sub-sub-branch points in each said quadrant in said input fingerprint image data each lie in the vicinity of a corresponding one of sub-sub-branch points in said registered fingerprint image data;

means for scoring a degree of mismatching between said sub-branch points in said input and registered fingerprint image data on the basis of a norm when said sub-branch point in said input fingerprint image data lies in the vicinity of said corresponding sub-branch point in said registered fingerprint image data;

means for scoring the degree of mismatching between said sub-sub-branch points in said input and registered fingerprint image data on the basis of a norm when said sub-sub-branch points lie in the vicinities of said corresponding sub-sub-branch points in said registered fingerprint image data;

means for computing a mean mismatching degree of said master branch point candidates;

means for selecting, as a master branch point in said input fingerprint image data, that one of said master branch point candidates which has a minimum means mismatching degree; and

means for judging an examinee to be a person of said registered fingerprint image data when the mean mismatching degree of said master branch point in said input fingerprint image data is smaller than a predetermined value;

means for registering template data for template matching; and

template matching means for template matching said input fingerprint image data with registered data.

8. A fingerprint ID method which compares input fingerprint image data with registered image data, comprising the steps of:

processing binary image data for thinning, said thinning step including a thinning determination step which determines a deletable point in said binary image data by a table search in units of eight neighboring cells and a scan control step which reduces the number of times of scanning of said thinning determination step;

extracting minutiae from said image data, said minutia extracting step including a step which extracts minutia candidates from said thinned image data by a table search in units of eight neighboring cells and a step which excludes pseudo minutiae from said minutia candidates;

registering true minutiae of said image data;

matching minutiae of said input fingerprint image data with registered minutiae;

registering template data for template matching;

template matching said input fingerprint image data with said registered data;

comparing results of said minutia matching step and results of said template matching steps in terms of recognition rate;

selecting the results of said minutia matching step for identifying said input fingerprint image data when the results of said minutia matching step have a higher recognition rate than the results of said template matching step; and

selecting the results of said template matching step for identifying said input fingerprint image data when the results of said template matching step have a higher recognition rate than the results of said minutia matching step.

9. A fingerprint ID method which compares registered fingerprint data and input fingerprint data obtained by automatic contrast control by software, characterized by:

first matching wherein a bulge-line direction pattern and a bulge-line curvature pattern of said registered fingerprint data are compared with those of said input fingerprint data and aligned with each other;

the matching degree of said bulge-line direction and curvature patterns in overlapping areas thereof is computed;

when said matching degree is above an upper threshold value, an examinee is judged to be the person of said registered fingerprint data; and

when said matching degree is under a lower threshold value, said examinee is judged to be an outsider; and

at least one second matching step wherein when said matching degree is above said lower threshold value and under said upper threshold value, only those areas of said input fingerprint data which match minutia high-density and medium-density areas of said registered fingerprint data are subjected to thinning to extract minutiae;

the matching degree of said extracted minutiae is computed in terms of their position, kind and direction;

when said matching degree in said high-density area is above said upper threshold value, said examinee is judged to be the person of said registered fingerprint data, and when said matching degree is under said lower threshold value, said examinee is judged to be an outsider, and when said matching degree is above said lower threshold value and under said upper threshold value, said examinee is judged to be an outsider; and

when said matching degree in said medium-density area is above said upper threshold value, said examinee is judged to be the person of said registered fingerprint data, and when said matching degree is under said lower threshold value, said examinee is judged to be an outsider, and when said matching degree is above said lower threshold value and under said upper threshold value, said examinee is judged to be an outsider.