Method and device for allocating core points of finger prints

A method to automatically find out the actual position of the core point of a finger print by using the characteristic of the ridge flow of finger prints. This method comprises three parts: (1) ridge flow finding algorithm, (2) ridge flow correction algorithm and (3) core point allocation algorithm.

FIELD OF THE INVENTION 
The present invention relates generally to a method to be used in a 
computerized finger print processing system to allocate the core points of 
finger prints and in particular to a method for matching finger prints. 
BACKGROUND OF THE INVENTION 
Using a computer to do finger print processing is very efficient and 
convenient in matching finger prints as the computer has a great capacity 
to do a number of operations in a very short period. Owing to the rapid 
speed of processing in the studying of finger prints by means of the 
computer, the characteristics used to identify a finger print are much 
simpler than ever and, therefore, it is possible to process a great number 
of finger prints at the same time. Nevertheless, different images of the 
same finger print usually cannot be identified as the same. The magnitude 
and orientation of the force applied by a finger tip in producing the 
finger print thereof and the translation and rotation of the finger will 
more or less affect the configuration of the printed finger print. 
The finger prints of human beings are categorized into 8 groupings 
according to the ridges of finger prints. The ridge flows of some 
groupings are quite different from each other and a common characteristic 
is almost impossible to obtain. It is the major task for researchers to 
develop a finger print recognition system which is capable of recognizing 
all kinds of finger prints in spite of the great difference in the ridge 
flows. 
SUMMARY OF THE PRESENT INVENTION 
It is therefore an object of the present invention to provide a method 
which is capable of allocating the core point of a finger print, no matter 
what grouping the finger print belongs to. 
It is another object of the present invention to provide a method which is 
capable of allocating the core point of a finger print, no matter how 
badly the finger print is distorted. 
It is a further object of the present invention to provide a method which 
is capable of allocating the core point of a finger print, no matter how 
many times the same finger print is repeatedly and differently input. 
The present invention analyzes the ridge flow of a finger print according 
to the characteristics of its ridge flow and locates the core point 
thereof to the analysis of the ridge flow. No matter how the finger print 
is rotated, translated and/or scaled the core point can be allocated at 
the same point every time the same finger print is input. The core point 
of a finger print can always be located, no matter what grouping of finger 
print it belongs.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
The method in accordance with the present invention comprises at least the 
following three steps: 
(1) the step to find out the ridge flow of a finger print; 
(2) the step to correct the ridge flow; and 
(3) the step to allocate the core point of the finger print via the 
corrected ridge flow. 
All these steps will be described hereinafter. 
Finding Out the Ridge Flow 
The original image of a finger print is usually a gray level image, and a 
binary image can be obtained therefrom when the image is processed to be 
represented by binary codes. The present invention makes use of the binary 
image to do finger print processing. In the present invention, the 
orientations of the ridge flow of a finger print are categorized into four 
groupings, each represented by an individual direction code. In the 
direction codes, "0" represents the orientation of east-west, "1" the 
orientation of southeast-northwest, "2" the orientation of north-south and 
"3" the orientation of northeast-southwest. 
For a binary image constituted by a k (pixel).times.k (pixel) matrix, where 
k=m.times.n, the binary image is first divided into m.times.x m windows, 
each of which is an n (pixel).times.n (pixel) sub-matrix. The values of m 
and/or n should be adjusted in accordance with the ratio that a finger 
print is taken in the whole image. To specifically describe the step, k is 
taken, for example, as 256 and m is 32 and n is 8. In applying the method, 
each window is processed individually. That is, each of the n.times.n 
sub-matrix is individually processed to determine the direction thereof. 
The direction code of each n.times.n sub-matrix is obtained with a 
convolution operation. For a given two-dimensional data matrix (such as 
that shown in FIG. 1) and a 3.times.3 mask (such as that shown in FIG. 2), 
the convolution operation taken upon the (1, 1) element of the data matrix 
of FIG. 1 with the 3.times.3 mask of FIG. 2 gives the result. 
##EQU1## 
That is, to place the centered element of the c.times.3 mask at the (1, 1) 
location of each of the data matrix and then summing up the products of 
the eight elements of the 3.times.3 mask that are around the centered 
element thereof times its associated element of the data matrix. The 
convolution operation is taken upon all elements of the data matrix, 
except those elements located at the four edges of the data matrix. 
For determining the direction code of an n.times.n sub-matrix (n=8, as 
stated previously), the convolution operation is taken upon the inner 
element of the sub-matrix with the four masks shown on FIG. 3, and the 
results of the convolution operation with the four masks are denoted by 
c.sub.0, c.sub.1, c.sub.2 and c.sub.3 (An inner element of a sub-matrix is 
an element that is not located at any edge row or edge column of the 
sub-matrix.) 
Taking the matrix denoted by (a) in FIG. 4 as an example of an n.times.n 
sub-matrix of a finger print binary image to be processed. In the area of 
the finger print covered by the sub-matrix, the orientation of the ridge 
flow is north-south, therefore the centered four columns have the value 
"1" and the other columns are "0" (Recall that this is a binary image.) 
The results of the convolution operation with the four masks are also show 
in FIG. 4 and are respectively denoted by c.sub.0, c.sub.1, c.sub.2 and 
c.sub.3, as stated previously. 
The rule to determine the direction code from the convoluted results 
c.sub.0, c.sub.1, c.sub.2 and c.sub.3 is that the direction code thereof 
is the one associated with the convoluted result which has the most "0" 
among all other convoluted results. That is the convoluted result that has 
the largest number of "0" among all other convoluted results determines 
the direction code. The orientation of the ridge flow inside the area 
covered by the sub-matrix is determined from the direction code. It is 
clear from FIG. 4 that c.sub.2 has the most "0" and that the direction 
code is "2". This is to say that the orientation is north-south which is 
exactly what is given. 
FIG. 5 shows several finger prints and the results obtained with the above 
procedure, wherein a.sub.1 to a.sub.3 are binary images of the finger 
prints, and b.sub.1 to b.sub.3 are the distribution map of codes that 
display the orientation patterns of the ridge flows obtained with the 
above-mentioned convolution operation. As stated previously, each binary 
image is constituted by a 256.times.256 data matrix and is divided into 
32.times.32 windows, each of which comprises 8.times.8 image elements. 
Correcting the ridge Flow 
When the quality of the original copy of a finger print is bad, for example 
the print may contain many local distortions of the ridge pattern, the 
binary image thus has many noises (incorrect data due to the local 
distortions). This results in incorrect results in determining the 
orientation with the above method. Since the ridge flow changes smoothly 
and the orientations thereof in adjacent areas are the same, it is 
possible to correct the ridge flow and eliminate the incorrect results. 
This will be described hereinafter. 
Taking a 3.times.3 matrix which is constituted by an adjacent direction 
code taken from the resulting matrix of the convolution operation as 
follows: 
##EQU2## 
where i and j are numbers between o and m (m=32 here) and represent the 
location of a direction code in the matrix constituted by the m.times.m 
windows, q represents the corrected direction code and p is the direction 
code which has not been corrected yet. If among the nine codes, "d" is the 
direction code that appears the most times, then the direction code 
p.sub.ij should be substituted by "a", if it is not "d". 
In FIG. 5, c.sub.1 to c.sub.3 are the corrected orientation patterns 
obtained from the un-corrected distribution map of codes b.sub.1 to 
b.sub.3 with the rule stated above. It is clear that although there are 
noises input into the processing system, a correct ridge flow can also be 
obtained. 
Allocating the Core Point 
By analyzing a great number of finger printsafter having been processed 
with the above two procedures, it is found that there is always an 
inverted east-westward triangle formed on the upper part of the ridge 
flow. It is concluded that the core point is located at the lower vertex 
or narrowest part therearound. 
With a way to determine the core point, each time a finger print is 
analyzed, the core point can be obtained first as a reference in matching 
finger prints and thus making the matching more correct. 
EXAMPLE 1 
In FIGS. 6, (a) to (h) show a typical sample of the 8 groupings of finger 
print and the core points thereof identified with the method in accordance 
with the invention. It is seen from FIG. 6 that no matter which grouping a 
finger print belongs to, an inverted triangle as stated previously always 
exists and it is always possible to identify the core point thereof with 
the method of the present invention, without any exception. 
EXAMPLE 2 
In FIG. 7, the finger prints of three fingers, each of which is input three 
times, together with the core points thereof are shown. In the figure, 
(a.sub.1, a.sub.2, a.sub.3) represent the three inputs of the first finger 
print (b.sub.1, b.sub.2, b.sub.3) represent those of the second finger 
print and (c.sub.1, c.sub.2, c.sub.3) represent those of the third finger 
print. It is clear that although the finger prints may be translated 
and/or distorted and thus have differences from each other, the same core 
point for the same finger print is always identified and located with the 
present method. 
As described, the present invention provides a method which is capable of 
identifying and allocating the core point of a finger print, no matter how 
many times the finger print is input. Even though a finger print is 
translated and/or distorted, the core point there of can always be 
identified with the method of the present invention. 
A method for allocating the core points of finger prints is described above 
and various details of the invention may be changed without departing from 
its scope. The foregoing description is for the purpose of illustration 
only and not for limitation --the invention being defined by the appended 
claims.