Abstract:
A method to extract automatic high level features of a gray level ridge flow image including the automatic determination of the location of the high level features including the core and delta points of a fingerprint image in the form of a gray level image, comprising the following five steps: 
     (1) determining a ridge flow direction of each gray level pixel of a fingerprint image and assign it with a direction code; 
     (2) finding out a block directional flow and assigning each with appropriate direction code thereof; 
     (3) correcting block flow directions in which a detection of the flow direction is affected image an input image quality in order to be immune from noises infiltrated during the acquiring process; 
     (4) locating the delta points which are based on a corrected block direction flow diagram to locate from zero to a few delta points; and 
     (5) locating the core points which are based on a corrected block direction flow diagram to locate one to two core points.

Description:
BACKGROUND OF THE INVENTION 
     In fingerprint recognition, there are two classes of characteristic points: (1) high-level features which include 0 to a few deltas and 1 to 2 cores; (2) low-level features which include the ending points and the bifurcation points. 
     Since the ridge-flow orientation of a fingerprint at a feature point will be different from the orientation of other part of the image, it can be relied on to determine the high-level features of the fingerprint. In fact, when an expert is identifying a fingerprint, the first characteristics being observed are these two characteristic points of the high-level features. As such, these features cannot be ignored in the development of an automatic fingerprint recognition system. 
     Each fingerprint may have a different number of core points and deltas. Therefore determining the high-level feature points will help make initial classifications for the fingerprints. However, as a major difficulty to the automatic fingerprint recognition, the fingerprint image acquired (for the same finger) may be different from each input of the image. This is because during each fingerprint acquisition, a person may either press his finger with different strength or in a different orientation that his fingerprint may be distorted. Therefore to re-orientate the fingerprint image and identify its location, such as using the cluster of core points and deltas as the basis, to simplify the recognition process and to improve the rate of recognition has become a principal object in automatic fingerprint recognition. 
     However, reviewing the conventional known technique, it can only determine one core point (a dual whole fingerprint has two core points), and cannot determine any delta point. Besides, it only divides the fingerprint ridge flow into four directions after the processing, which is not precise and can not determine the core point location so precisely. 
     U.S. Pat. No. 5,140,642 to Hsu et al. disclosed a method to automatically find out the actual position of the core point of a finger print by using the characteristics of the ridge flow of fingerprint. However, it also does not disclose a method to determine the delta points, thereby still being unsatisfactory for a precise recognition of fingerprints. 
     SUMMARY OF THE INVENTION 
     The object of this invention is to precisely determine the high-level feature points including 1 to 2 core points and 0 to a few delta points from any fingerprint. This method is able to determine the same high-level features including the core points and deltas, even if the fingerprint is acquired at different time, distorted due to different pressure, transformed or disoriented sensing. 
     From the distribution of core points and deltas, which are determined based on the ridge-flow direction, it is possible to extract the high-level feature points location, serving for a well classification of fingerprints. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows 8 codes for different flow directions in accordance with the present invention. 
     FIG. 2 shows a novel scheme to determine the direction of a pixel (using a 9×9 mask and direction code 3 as example here) in accordance with the present invention. 
     FIG. 3 shows a 5×5 region, R 5 ×5 (p, q), to decide whether to apply smoothing on the BDI. 
     FIG. 4a shows an application of smoothing method before smoothing BDI. 
     FIG. 4b shows the smoothing method after smoothing BDI. 
     FIG. 5 shows the direction-flow distribution in neighboring blocks of a delta point. 
     FIG. 6 shows the left-top and right-top corner block directions for the (p, q) block. 
     FIG. 7 shows region considered to have a vertical direction-flow. 
     FIG. 8a shows left-skew region. 
     FIG. 8b shows right-skew region. 
     FIG. 8c shows horizontal region. 
     FIG. 9 shows calculation of distance between core point and other points. 
     FIG. 10 shows first flow characteristics of a core point. 
     FIG. 11 shows second flow characteristics of a core point. 
     FIG. 12a shows first acquired image of fingerprint 1: original gray-level image. 
     FIG. 12b shows block direction-flow image obtained after applying Step 1 and 2 of this invention. 
     FIG. 12c shows block direction-flow image obtained after applying Step 3 of this invention, the core point and delta point positions obtained by Step 4 and 5 are indicated with inverse (color) block 
     FIG. 12d indicates the core point and delta point on the original gray-level image. 
     FIG. 13a shows second acquired image of fingerprint 1: original gray-level image. 
     FIG. 13b shows block direction-flow image obtained after applying Step 1 and 2 of this invention. 
     FIG. 13c shows block direction-flow image obtained after applying Step 3 of this invention, the core point and delta point positions obtained by Step 4 and 5 are indicated with inverse (color) block. 
     FIG. 13d indicates the core point and delta point on the original gray-level image. 
     FIG. 14a shows third acquired image of fingerprint 1: original gray-level image. 
     FIG. 14b shows block direction-flow image obtained after applying Step 1 and 2 of this invention. 
     FIG. 14c shows block direction-flow image obtained after applying Step 3 of this invention, the core point and delta point positions obtained by Step 4 and 5 are indicated with inverse (color) block. 
     FIG. 14d indicates the core point and delta point on the original gray-level image. 
    
    
     DETAILED DESCRIPTION 
     In the present invention, an algorithm can be divided into five steps to explain how the core points and delta feature points are determined: 
     1. Using new method to obtain the direction-flow image from the initial gray-level image; 
     2. Using new method to obtain the block direction-flow image; 
     3. Applying the new smoothing algorithm; 
     4. Determining the (0 to a few) deltas with new method; and 
     5. Determining the (1 to 2) core points with new method. 
     These steps are hereby described in detail as follows: 
     1. Obtaining the direction-flow image from initial gray-level image: 
     The initial image of the fingerprint is a gray-level image. To obtain the direction-flow image from the gray-level image, it is necessary to analyze the gray-levels surrounding each pixel to determine the flow direction of that pixel. The present invention labels the directions as 0, 1, . . . , N-1 , where N=8, i.e., there are altogether 8 directions. The flow directions and their corresponding labels are shown in FIG. 1. 
     Assuming that the size of the initial gray-level image is M×M, the direction of a pixel is determined based on a scheme as illustrated in FIG. 2. First of all, taking the pixel (i, j) as the center, we define a P×P region (mask) and calculate the change in gray-level along each direction. The direction, D(i, j), which has the minimum change in gray-level is taken as the direction of the pixel. FIG. 2 shows such calculation for a 9×9 mask (i.e., P=9) and assigned direction code 3 to the pixel at the center. Equation 1.a and 1.b gives the formula to determine the direction of each pixel. ##EQU1## where D(i,j) is the direction for the pixel (i,j). i,j=0, 1, . . . , M-1 V d  (i,j) is the change in gray-level, from pixel (i,j), along the direction d, and d=0, 1, . . . , N-1. 
     G(i,j) is the gray-level of pixel (i,j) in the initial fingerprint image. 
     G(i,j) is the gray-level of pixel (i,j) in the initial fingerprint image. 
     G d  (i t ,j t ) as the gray-level value of the t th  pixel from pixel (i,j) along the direction d. The value is filtered by the 9×9 mask. t=-m, . . . , m and t≢0. 
     m is extension (in terms of pixel number towards both sides) from (i,j) along direction d in determining the direction. 
     The method described above can calculate the direction of each pixel (i,j), thus obtaining the direction-flow image of the entire fingerprint gray-level image. 
     2. Obtaining the block direction-flow image (BDI): 
     After obtaining the direction-flow image using the method described above, it is necessary to gather the general flow of the fingerprint to facilitate the determination of the core points and deltas. From the curvature of the direction-flow, the procedures in the later stage of this invention can determine the number and the position of the core points and deltas. There may be 1 to 2 core points and 0 to a few deltas. 
     Referring to Eq. (1), since the direction-flow image is determined by the calculations for each pixel, it is easily disturbed by noises. As such we derive an averaged block direction-flow image (BDI) from the direction-flow image to reduce the effects of noise. The BDI is a better basis to determine the general flow of the fingerprint, thereby being advantageous to locate the core points and deltas. 
     This invention converts the original M×M direction-flow image to a M/b×M/b block direction-flow image (here we take b=8). That is to obtain the average value, BDI(.), of the direction code for the b 2  direction codes in the b×b subregion. The average value is calculated with following equation: 
     
         BDI(p,q)=k and h.sub.k =h.sub.max =MaxH.sub.pq =Max{h.sub.d |d=0, 1, . . . , N-1}                                           (2) 
    
     where h d  represents the number of pixels among the b 2  direction codes in region (p, q) having the same direction d. 
     Conceptually, the above is to determine the direction k(0≦k≦N-1) which has the highest frequency in the sub-region of the original direction-flow image. This direction BDI(p,q), is then assigned as the direction of the block. 
     3. Applying the smoothing algorithm: 
     Sometimes the block direction-flow image may be poor in quality or affected by stains on the finger. It is therefore necessary to perform automatic correction. We call this process smoothing. 
     From observations, the direction-flow of a fingerprint is rather smooth, except at the area around the core points and the deltas. This characteristic can be served as a reference whether to correct the direction of an area. On the other hand, the flow at areas around the core points and the deltas cannot be perturbed due to the smoothing process. This invention suggests a new method can consider this dilemma and is able to achieve a good result in smoothing the block direction-flow image. 
     For each block (p, q), our smoothing method applies a 5×5 block-region, R 5 ×5 (p,q), taking the block as the center (see FIG. 3), and calculate the ratio of the directions within the region. The smoothing is based on this ratio. The calculation is shown below: 
     We shall define 
     
         H(R.sub.5×5 (p,q))={h.sub.d |d=0, 1, . . . , N-1}(3) 
    
     where h d  is the number of blocks having the direction d, within the 5×5 area R 5 ×5 (p,q), where (p,q) is the center of the area. 
     Next, 
     
         H.sup.45&#39; (R.sub.5×5 (p,q))={h.sub.d.sup.45&#39; |d=0, 1, . . . , N-1}                                                    (4) 
    
     where h d   45&#39;   is the number of occupied blocks within the 45° sector, taking direction d as the reference axis. 
     Then whether BDI(p,q) is to be corrected depends on the following three considerations: 
     (1) the number of blocks with direction h k , where h k  =MaxH=Max{h d  |d=0, 1, . . . , N-1} 
     (2) the number of blocks with direction h d   45 °, where h d   45 ° =MaxH 45 ° =Max{h d   45 ° |d=1, 2, . . . , N-1} 
     (3) the angular difference between BDI(p,q) and k. 
     FIGS. 4(a) and 4(b) show the results of applying this method and it is obviously very effective. 
     4. Determining the deltas: 
     Analyzing the areas around the deltas, we discovered that they have a common flow characteristic as illustrated in FIG. 5. That is, the blocks surrounding a delta will have a flow distribution as shown in FIG. 5. In the R1 region, the flow directions observe a left skew (left down, right up) direction; in the R2 region, the flow directions observe a right skew (right down, left up) direction; whereas in the R3 region, the flow directions observe a horizontal direction. Based upon this observation, the present invention improvises a new method to locate the blocks where the deltas are. Details of this method are described in the following five steps: 
     Step 1: Taking (p, q) as the center of the current block (refer to FIG. 6), check whether the flow direction of the left-top corner block, BDI(p-1, q-1), is in the left skew direction. Also check whether the flow direction of the right-top corner block, BDI(p-1, q+1), is in the right skew direction. 
     Step 2: Taking (p, q) as the center, take a 5×5 block-region and count the number of blocks with vertical flow direction (all directions encompassed by the shaded area shown in FIG. 7 are considered as vertical flow direction). The analysis will continue only if this number exceeds a pre-determined threshold value. The purpose here is to filter off the areas further away from the delta point where the flow directions may be more or less similar to that in R1, R2 and R3 shown in FIG. 5. In those areas, the flow inclination (R1 or R2) are not large enough and can be discarded. 
     Step 3: As shown in FIGS. 8a, 8b and 8c, having defined the left skew, right skew and horizontal directional variations, the next three rules are considered to confirm whether the R1, R2 and R3 regions around block (p, q) have the same characteristic as shown in FIG. 5. 
     Rule 1: 
     Let the number of left skew in the R1 region be Left(R1), the number of right skew in region R1 be Right(R1), and the number of horizontal in region R1 be Horizon(R1). If the following condition is met, then R1 is assumed to be left skew: 
     (1) Left(R1)&gt;threshold 0  (a pre-assigned value) 
     (2) Left(R1)&gt;Right(R1) and Left(R1)&gt;Horizon(R1) 
     Rule 2: 
     Let the number of left skew in the R2 region be Left(R2), the number of right skew in region R2 be Right(R2), and the number of horizontal in region R2 be Horizon(R2). If the following condition is met, then R2 is assumed to be right skew: 
     (1) Right(R2)&gt;threshold, (a pre-assigned value) 
     (2) Right(R2)&gt;Left(R2) and Right(R2)&gt;Horizon(R2) 
     Rule 3: 
     Let the number of left skew in the R3 region be Left(R3), the number of right skew in region R3 be Right(R3), and the number of horizontal in region R3 be Horizon(R3). If the following condition is met, then R3 is assumed to be horizontal: 
     (1) Horizon(R3)&gt;threshold 2  (a pre-assigned value) 
     (2) Horizon(R3)&gt;Left(R3) and Horizon(R3)&gt;Right(R3) 
     If all Rules 1, 2 and 3 are satisfied, then the block (p, q) is a candidate delta location. 
     Step 4: After identifying the candidate delta locations in Step 3, we need to determine the number of clusters among them. The total number of clusters will be the number of delta points. 
     Here an improved K-means clustering algorithm is applied. In the original K-means clustering algorithm, it is required to fix and assume a number of clusters. However, it is impossible to predict the number of clusters, i.e. the number of delta points, at the beginning. Therefore we begin by assuming that there is one cluster, if the new point added to the cluster has a distance greater than Distance (Distance is a pre-determined value) from the cluster center, then this new point is assigned to a new cluster. The distance mentioned above is measured using the chess board measure as illustrated in FIG. 9 in which each of the 8 neighboring points around a given center point has the same distance from the center point. 
     Step 5: Similarly, for each cluster determined in previous step, a representative point has to be determined and to be regarded as the actual delta point. 
     Suppose the C th  cluster has altogether q points. For any point v corresponding to a vector (Left(R1)| v , Right(R2)| v , Horizon (R3)| v , where v=1, 2, . . . , q, which obeys the Rules 1, 2 and 3 in Step 3, there exists a point uε{1, 2, . . . , q} that satisfies the following: 
     Left(R1)| u  ≧Left(R1)| v ≢u 
     and Right(R2)| u  ≧Left(R2)| v ≢u 
     and Horizon(R3)| u  ≧Horizon(R3)| v ≢u 
     Under such condition, u is the actual location of the delta point within cluster C. 
     5. Determining the cores: 
     The nature of distribution of the core points is different from that of the delta points. However, the analysis to locate them is similar. That is to take a small area around the candidate core points for further dividing the small area in order to analyze the direction flow in each of the small area. 
     It is necessary to consider the two situations shown in FIG. 10 and FIG. 11 in analyzing the direction flow around the core points. In FIG. 10, the convex upward characteristics resembles the delta characteristics but the R3 region can be ignored. FIG. 11 shows a concave inward distribution characteristics which is symmetrical to that in FIG. 10. 
     The method to locate the core point in this invention is described in following six steps: 
     Step 1: From observation, the fingerprint direction flow has a greater variation, therefore the first step is to determine whether the two neighboring regions have sufficient variations. The consideration is illustrated below: 
     
         ______________________________________Left neighboring        Right neighboringregion                  region______________________________________BDI(p, q - 1)  BDI(p, q)                   BDI(p, q + 1)______________________________________ 
    
     
         Definition θ=|BDI(p,q-1)-BDI(p,q+1)|(5) 
    
     The candidate core points are restricted to the condition ##EQU2## Step 2: With block (p, q) as the center, take a 5×5 block-region as shown in FIG. 3. Since the angular variation as considerably large in regions around the cores, it will not be constrained in a small range. As such, use Eq. (4) to determine the distribution of H 45 ° (R 5 ×5 (p,q)) and calculate 
     
         A.tbd.h.sub.i.sup.45° =MAXH.sup.45° =Max{h.sub.d.sup.45 |d=0, 1, . . . , N-1}                            (6) 
    
     The rest of the steps will be carried only if A≦threshold 3  (a pre-defined value). 
     Step 3: Next, examine the 5×5 block-region which has (p, q) as the center forming the convex or concave shape as shown in FIGS. 10 and 11. That is, 
     find the number of left skew in region R1, Left(R1) 
     the number of right skew in region R2, Right(R2) 
     the number of right skew in region R4, Right(R4) 
     the number of left skew in region R5, Left(R5) 
     then make decision based on the following: 
     If (Left(R1)+Right(R2))&gt;(Right(R4)+Left(R5)) and Min(Left(R1), Right(R2))≧threshold 4  (a pre-defined value) then (p, q) is the center of the convex region. 
     If (Left(R1)+Right(R2))&lt;(Right(R4)+Left(R5)) and Min(Right(R4), Left(R5))≧threshold 4  then (p, q) is the center of the concave region. 
     Step 4: As the convex shape is similar to the delta shape, it is necessary to eliminate the information around the delta that may contribute to a candidate core point. This is to avoid repeated calculations and mistaking a delta point as a core point. 
     Step 5: According to the convex and concave shapes and the point to point distances, the clustering of the candidate core points as found in Step 4 is determined. The method to determine the clustering is again the modified K-means algorithm as developed in this invention. 
     Step 6: Step 5 has determined the clustering of the candidate core points. Each cluster has to find a representing point to be regarded as the core point location. That is to process the convex and concave situations with the followings: 
     take the lowest point in the convex region to be the core point 
     take the highest point in the concave region to be the core point 
     From the above six steps, one to two core point locations of the fingerprint can be determined. 
     As described above, this invention is applicable on any direction-flow of static or dynamic fluid (gas or liquid), or solids with grainy strips (e.g. grain of wood and fingerprint) to identify the locations of some characteristic points. For the case of fingerprint, the characteristic points are the core points and the delta points. Therefore, even if the fingerprint is distorted to a certain extend due to stain, cuts or exerting different pressure or placing one&#39;s finger in different orientation during the acquisition of the fingerprint, by using the methods in this invention the core points and the delta points can still be located since the features of the direction-flow are still available. 
     To summarize, this invention can accurately locate the same core points and delta points of a fingerprint acquired in different time or conditions (see FIGS. 12 to 14). This invention has made a considerable contribution to the automatic fingerprint recognition by providing highly accurate coordinates of the high-level feature points to be superior to any conventional methods of automatic fingerprint recognition.