Method for classifying a fingerprint and the system device of the same

The invention relates to a method for automatically classifying fingerprint images. It mainly uses the number of core points in the fingerprint and the flow of fingerprint lines around the core points to classify fingerprints.

In access control systems, electronic transaction systems, or other systems that require personal identification, fingerprint identification is a feasible and reliable identification method. And fingerprint classification is usually used as a pre-processing step of fingerprint recognition. When performing fingerprint recognition, too high computational complexity is a problem usually encountered. If the fingerprint images can be classified in advance, the number of sample space searches and comparisons required during identification can be effectively reduced, so the time required for identification can be reduced, and the accuracy of identification can be increased at the same time.

There are some known fingerprint classification methods that use structural, comprehensive, and rule-based methods, or use neural networks for classification. These methods may use some different basic classification methods. For example, the method disclosed in US Patent 5,337,369 divides fingerprints into five categories, namely: right loop, left loop, Spiral (swirl), pointed arch (tented arch) and flat arch (plane arch). The present invention further divides fingerprints into right loop, left loop, tented arch, plane arch, left twin, There are eight categories: right twin, whorl, and others. Usually we must strike a balance between the number of fingerprint categories and the time required for classification processing and their correctness. The more fingerprint categories a classification method can distinguish, the higher the practical application value of this method; but on the other hand, the processing speed and the correct rate of classification will decrease as the number of fingerprint categories increases.

Before fingerprint classification, it is usually necessary to determine the special feature points in a fingerprint image (such as: core point, delta point, etc.). After the special feature points are found, different methods are applied to classify them according to these feature points. However, when a fingerprint is sampled, it does not necessarily have triangular points. In this case, the method of using core points and triangular points as the basis of classification at the same time will lose its effectiveness. The method disclosed in the present invention only classifies the core point and the fingerprint line flow around it. The method used in the aforementioned US Patent 5,337,369 also uses core points and analyzes the flow of fingerprint lines around them for classification. However, this method only uses the information of one core point in the fingerprint image. When there is more than one core point in the fingerprint image, this method cannot effectively use this information. In addition, this method can only classify fingerprint images into five categories, which may be too few in practical applications.

Figure 1 is a block diagram of the system structure of the present invention.

Figure 2 shows the seven types of fingerprint classification diagrams of the present invention.

Figures 3a and 3b are examples of convex cores in the present invention.

Figures 3c and 3d are examples of the concave core of the present invention.

Figure 4a shows that the fingerprint image in the present invention contains a convex core point.

Figure 4b shows that the fingerprint image in the present invention contains a convex core point and a concave core point.

Figure 5 is a flow chart of the entire classification work of the present invention.

Figure 6 shows that the fingerprint line is divided into 8 directions according to the present invention.

Figure 7 shows how to determine the direction of the fingerprint line based on the fingerprint data.

Figure 8a shows the left-tilt distribution in certain areas.

Figure 8b shows the right-leaning distribution in some areas.

Figure 8c shows the vertical distribution in certain areas.

Figure 8d shows the horizontal distribution pattern in some areas.

Figure 9 shows the use of a convex core point to determine the direction of the fingerprint line.

Figure 10 shows the fingerprint line orientation pattern of the 4 areas around the convex core point.

Figures 11a and 11b show that a convex core point and a concave core point are used to determine the direction of the fingerprint line.

Figure 12 shows the fingerprint line pattern of the four regions around the convex core point and the concave core point respectively.

In the present invention, the device of the entire fingerprint automatic classification system is as shown in Figure 1. First, there is a fingerprint image input unit 101 (fingerprint image input unit), which is a device composed of optical equipment. Contains some lenses, three beams, lighting equipment, and an image-electronic converter used to convert fingerprint images into electronic signals, such as a CCD camera. The converted electronic signal is sent to a signal conditioning unit 102 (signal conditioning unit) to perform adjustment work on the obtained signal. The adjusted signal will be sent to a digitizing unit 103 to convert the original analog signal into a digital signal. The digitized signal is a gray-scale digital image, which will be stored in an image memory unit 104 for further processing. The above entire fingerprint image acquisition process is controlled by an input control unit 110 (input control unit). When the system wants to acquire an input image, the micro-controller unit 105 (micro-controller unit) in the system inputs commands to the control unit Start the operation to perform a series of steps of the above-mentioned image acquisition.

The classification of this method is performed by a classifier unit 109 (classifier unit). This classification unit obtains the stored grayscale fingerprint image from the image memory unit 104, and after processing, outputs the classification result to the VDU/LCD output unit 107 (VDU/LCD output unit) and uses the Keyboard/keypad input unit 108 (keyboard/keypad input unit) as the user input interface. The work of the classification unit 109 is performed according to an algorithm stored in a program and work memory unit 106 (program and work memory unit). The purpose of the present invention is to design an algorithm for this classification, which will be described later.

As shown in Figure 2, the present invention divides all fingerprints into eight categories, namely: right loop, left loop, tented arch, and flat arch. plane arch), left twin, right twin, spiral (whorl), and if a fingerprint image does not meet the above categories, it will be classified into the last category and other categories (others). Here, the core point in the fingerprint image and the block pattern formed by the fingerprint image are used as the basis for classification. Because the obtained fingerprint image often has orientation deviation, distortion or even serious defacement, we must first determine the position of the core point in a fingerprint image to relocate the fingerprint image to improve the accuracy of classification and make The following classification steps are repeatable. The fingerprint core points obtained in the present invention can be divided into two types: 1. Convex core points: for example, the core points shown in Figure 3a and Figure 3b.

2. Concave core points: such as the core points shown in Figure 3c and Figure 3d.

Each fingerprint image contains one or two core points. The fingerprint image in Figure 4a includes a convex core point 401; the fingerprint image in Figure 4b includes a convex core point 402 and a concave core point 403. From the classification table in Figure 2, we can see that the fingerprint images of the first to fourth types have only one core point, while the fifth to seventh types of fingerprint images have both a convex core point and a concave point. Core point.

Figure 5 is a flow chart of the entire classification work of the present invention. First obtain a grayscale fingerprint image. Then, the block direction image (BDI) is generated based on the original grayscale image. The purpose of the block direction image is to store the direction of the fingerprint line in a fingerprint block. In the present invention, we divide the fingerprint line into eight directions as shown in Figure 6. To obtain a block direction map of a fingerprint image, we first divide the entire M×N grayscale fingerprint image into blocks of m×n size as shown in Figure 7, so a total of<img file="TW354397B_D0001.tif" />A block, which contains two kinds of blocks: background block and fingerprint block. For example, the fingerprint image in Figure 7 is a 400×400 grayscale fingerprint image. We divide it into 50×50 blocks with a size of 8×8 (that is, here M=N=400 and m=n=50), where the block marked 701 represents a background block in the fingerprint image, and the block marked 704 is a fingerprint block in the fingerprint image. For each small block, we calculate the average fingerprint line direction in this block, and then according to Figure 6, find a value from 0 to 7 that represents this direction, and set this value to represent this area The block direction of the block.

After finding the core points in the fingerprint and calculating the entire block direction map, the present invention will start the classification work. The steps are as shown in the flowchart in Figure 5. First, according to the number of core points, fingerprint images can be divided into two categories: (1). Fingerprints with only one convex core point, and (2). There is one convex core point and one The fingerprint of the concave core point. Figures 4a and 4b are examples of the two types of fingerprints.

If the input fingerprint has only one core point as shown in Figure 9, we use the core point as the origin and analyze the direction of the blocks in the four regions (901,902,903,904) to determine that the fingerprint image belongs to the right circle shape and the left circle shape. Pointed arch or flat arch. Otherwise, if the input fingerprint has two core points as shown in Figure 11a and Figure 11b, we analyze the directions of the blocks in the four areas of 1101, 1102, 1103, and 1104 to determine whether the fingerprint belongs to the left double circle shape , Right double circle or spiral.

For detailed fingerprint acquisition and fingerprint classification steps, the following will refer to Figure 5 and describe the process in detail. In step 500, the microcontroller unit 105 causes the system to start a working loop of image capture, and stores the digitized image in the image memory unit 104. In step 501, the gray-scale fingerprint image obtained in step 500 will be processed and divided into two parts: a background block and a fingerprint block. The two types of blocks are distinguished according to the mean value of the block and its variance value. The calculation method is as follows:<maths><img file="TW354397B_D0002.tif" /></maths>Among them, F(x, y) represents the grayscale value of the point with coordinates (x, y) in the fingerprint image. The average gray level of the above if one block<i>Mean</i>(<i>p,q</i>)&lt;<i>threshold</i>₁And its grayscale difference value<i>Variance</i>(<i>p,q</i>)&gt;<i>threshold</i>₂, Then this block (p, q) will be recognized as a fingerprint block, otherwise it will be recognized as a background block. Among the above<i>threshold</i>₁and<i>threshold</i>₂It is a set of predetermined thresholds.

In step 502, we analyze the fingerprint line direction of each fingerprint block to generate a block direction map (BDI). Next, in step 503, the block direction map generated in step 502 is used to find the core point and the triangle point in the fingerprint. After the feature points are found, the classification work will start in step 504. Step 504 calculates the number of core points in the fingerprint image. If there is only one core point, step 505 will be executed next; if it has two core points, step 511 will be executed next; otherwise, this fingerprint will be classified It is the last category "others".

In step 505, it is checked whether the single core point obtained above is a convex core point, and if it is, step 506 is executed, if otherwise, the same fingerprint will be classified as "others". Step 506 is to determine the frequency of occurrence of blocks in the left-tilt direction and blocks in the right-tilt direction in the two areas 901 and 902 in FIG. 9. With reference to the direction line labeling in Figure 6, we specify that the directions labelled 1, 2, and 3 are left skew angles, as shown in Figure 8a, and calculate the following formula (3); label 5, 6, and The direction of 7 is the right skew angles, as shown in Figure 8b, and the following formula (4) is calculated: The directions marked 3, 4, and 5 are vertical, as shown in Figure 8c, and calculate The following formula (5); and the directions marked 1,0,7 are horizontal (horizontal), as shown in Figure 8d, and the following formula (6) is calculated.

<i>L=(a</i>_<i>-1</i><i>×H[1]+a</i>_<i>0</i><i>×H[2]+a</i>_<i>1</i><i>×H[3])/(a</i>_<i>-1</i><i>+a</i>_<i>0</i><i>+a</i>_<i>1</i><i>)</i>………(3)

<i>R=(a</i>_<i>-1</i><i>×H[5]+a</i>_<i>0</i><i>×H[6]+a</i>_<i>1</i><i>×H[7])/(a</i>_<i>-1</i><i>+a</i>_<i>0</i><i>+a</i>_<i>1</i><i>)</i>………(4)

<i>Ver=(a</i>_<i>-1</i><i>×H[3]+a</i>_<i>0</i><i>×H[4]+a</i>_<i>1</i><i>×H[5])/(a</i>_<i>-1</i><i>+a</i>_<i>0</i><i>+a</i>_<i>1</i><i>)</i>………(5)

<i>Hor=(a</i>_<i>-1</i><i>×H[7]+a</i>_<i>0</i><i>×H[0]+a</i>_<i>1</i><i>×H[1])/(a</i>_<i>-1</i><i>+a</i>_<i>0</i><i>+a</i>_<i>1</i><i>)</i>.........(6) Among them<i>H[d]</i>The direction of the block in this area is<i>d</i>The frequency of the block,<i>d=0,1,..,7</i>It is the direction as shown in Figure 6. and<i>a</i>_<i>-1</i>, <i>a</i>_<i>0</i>, <i>a</i>_<i>1</i>It is the specific gravity constant set in advance.

After calculating the above four equations for areas 901 and 902, step 507 makes the following judgments:<i>L</i>_<i>901</i><i>&gt;R</i>_<i>901</i>and<i>L</i>_<i>901</i><i>&gt;threshold</i>,………(7)

<i>R</i>_<i>902</i><i>&gt;L</i>_<i>902</i>and<i>R</i>_<i>902</i><i>&gt;threshold</i>,.........(8) Go to step 508, otherwise classify this fingerprint as "others". in<i>L</i>_<i>901</i>and<i>L</i>_<i>902</i>Respectively represent the frequency of occurrence of the blocks with the block direction leaning to the left in the area 901 and the area 902 in Figure 9, the same<i>R</i>_<i>901</i>and<i>R</i>_<i>902</i>Represents the frequency of occurrence of blocks whose block direction is tilted to the right.

The purpose of step 508 is to determine the ridge direction mode (ridge direction mode) of the four areas of 901, 902, 903, and 904.<i>D</i>_<i>901</i><i>, D</i>_<i>902</i><i>, D</i>_<i>903</i><i>, D</i>_<i>904</i>(As shown in Figure 10). The fingerprint line direction patterns of these four areas are defined as follows:<i>D</i>_<i>901</i><i>=</i>{<i>d</i>∣<i>H</i>_<i>901</i><i>(d)=Max(H</i>_<i>901</i><i>(i)),i=0,1,..,7</i>}………(9)

<i>D</i>_<i>902</i><i>=</i>{<i>d</i>∣<i>H</i>_<i>902</i><i>(d)=Max(H</i>_<i>902</i><i>(i)),i=0,1,..,7</i>}………(10)

<i>D</i>_<i>903</i><i>=</i>{<i>d</i>∣<i>H</i>_<i>903</i><i>(d)=Max(H</i>_<i>903</i><i>(i)),i=0,1,..,7</i>}………(11)

<i>D</i>_<i>904</i><i>=</i>{<i>d</i>∣<i>H</i>_<i>904</i><i>(d)=Max(H</i>_<i>904</i><i>(i)),i=0,1,..,7</i>}.........(12) where<i>H</i>_<i>901</i><i>(i), H</i>_<i>902</i><i>(i), H</i>_<i>903</i><i>(i), H</i>_<i>904</i><i>(i)</i>The directions of the fingerprint lines in the regions 901, 902, 903, and 904 are<i>i</i>The frequency of occurrence of the block. After determining the fingerprint line direction pattern of each of the above areas, in steps 509 and 510, referring to Figure 10 and according to the classification rules in the following table, they are classified into four types: right circle, left circle, pointed arch or flat arch do not.

<tables><img file="TW354397B_D0003.tif" /></tables>

For example, if<i>D</i>_<i>901</i><img file="TW354397B_D0004.tif" />Right leaning (i.e.<i>D</i>_<i>901</i><img file="TW354397B_D0005.tif" />{1,2,3})，<i>D</i>_<i>902</i><img file="TW354397B_D0006.tif" />Left-leaning (i.e.<i>D</i>_<i>901</i><img file="TW354397B_D0007.tif" />{5,6,7})，<i>D</i>_<i>903</i><img file="TW354397B_D0008.tif" />Right leaning (i.e.<i>D</i>_<i>903</i><img file="TW354397B_D0009.tif" />{1,2,3})，<i>D</i>_<i>904</i><img file="TW354397B_D0010.tif" />Right leaning (i.e.<i>D</i>_<i>904</i><img file="TW354397B_D0011.tif" />{1,2,3}), the fingerprint will be classified as a right circle. If the input fingerprint does not meet any of the classification rules in the table above, the fingerprint will be classified as the last type of other types "others".

Step 511 and subsequent steps deal with the situation where there are two core points in the fingerprint image. If the fingerprint image contains a convex core point and a concave core point, go to step 512, otherwise the fingerprint will be classified as "others". In step 512, the straight-line distance between the two core points is first calculated<i>Dis</i>,like<i>Dis</i>&lt;<i>threshold</i>₁Or <i>x</i>_<i>cx</i>-<i>x</i>_<i>cv</i>∣&lt;<i>threshold</i>₂, Then this fingerprint will be classified as a spiral in step 513, where the above<i>x</i>_<i>cx</i>and<i>x</i>_<i>cv</i>Respectively represent the X coordinate of the convex core point and the X coordinate of the concave core point in the fingerprint image; if otherwise, proceed to step 514.

Step 514 is similar to step 508, which will determine the fingerprint line direction pattern of this fingerprint. However, the four regions divided here are different from step 508, such as the four regions 1101, 1102, 1103, and 1104 in Figures 11a and 11b. We take their fingerprint line direction patterns respectively:<i>D</i>_<i>1101</i><i>=</i>{<i>d</i>∣<i>H</i>_<i>1101</i><i>(d)=Max(H</i>_<i>1101</i><i>(i)),i=0,1,..,7</i>}………(9)

<i>D</i>_<i>1102</i><i>=</i>{<i>d</i>∣<i>H</i>_<i>1102</i><i>(d)=Max(H</i>_<i>1102</i><i>(i)),i=0,1,..,7</i>}………(10)

<i>D</i>_<i>1103</i><i>=</i>{<i>d</i>∣<i>H</i>_<i>1103</i><i>(d)=Max(H</i>_<i>1103</i><i>(i)),i=0,1,..,7</i>}………(11)

<i>D</i>_<i>1104</i><i>=</i>{<i>d</i>∣<i>H</i>_<i>1104</i><i>(d)=Max(H</i>_<i>1104</i><i>(i)),i=0,1,..,7</i>}………(12)

After obtaining the fingerprint line orientation patterns of the above four regions, in step 509, referring to Figure 12 and according to the following table, the input fingerprints are classified into right double circle, left double circle and spiral.

<tables><img file="TW354397B_D0012.tif" /></tables>

In addition, in step 510, if the fingerprint image satisfies <i>D</i>₁₁₀₁<i>-D</i>₁₁₀₂∣&lt;<i>threshold</i>And <i>D</i>₁₁₀₃<i>-D</i>₁₁₀₄∣&lt;<i>threshold</i>At that time, this fingerprint image will also be classified as a spiral. Otherwise if <i>D</i>₁₁₀₁<i>-D</i>₁₁₀₂∣<img file="TW354397B_D0013.tif" /><i>threshold</i>Or <i>D</i>₁₁₀₃<i>-D</i>₁₁₀₄∣<img file="TW354397B_D0014.tif" /><i>threshold</i>and<i>x</i>_<i>cx</i>&gt;<i>x</i>_<i>cv</i>,<i>y</i>_<i>cx</i>&gt;y_<i>cv</i>When, the fingerprint image will be classified as the left double circle; if <i>D</i>₁₁₀₁-<i>D</i>₁₁₀₂∣<img file="TW354397B_D0015.tif" /><i>threshold</i>Or <i>D</i>₁₁₀₃-<i>D</i>₁₁₀₄∣<img file="TW354397B_D0016.tif" /><i>threshold</i>and<i>x</i>_cx&lt;<i>x</i>_<i>cv</i>, <i>y</i>_<i>cx</i>&gt;<i>y</i>_<i>cv</i>At the time, this fingerprint will be classified as a right double circle shape. in<i>x</i>_<i>cx</i>and<i>y</i>_<i>cx</i>Respectively represent the X and Y coordinates of the convex core point, and<i>x</i>_<i>cv</i>and<i>y</i>_<i>cv</i>Respectively represent the X and Y coordinates of the concave core point. If a fingerprint image does not meet the above-mentioned conditions, it will be classified as the last category "others".

Method and system device for automatically classifying fingerprint images