JPH05165945A - Fingerprint line direction calculation apparatus and method - Google Patents

Abstract

(57) [Summary] [Object] The present invention relates to a fingerprint line direction calculation device and method for detecting the direction of a ridge line or a valley line of a fingerprint for use in a fingerprint collation device or the like. The purpose is to prevent erroneous detection of the direction caused by doing so and to speed up the process by efficient scanning. [Structure] Binary image storage device 13 by N direction scanning circuit 14
The binary image of the fingerprint inside is scanned in the N direction, and the scanning line length measuring circuit 15 measures the length of the scanning line in which the same pixel value continues. Therefore, except for the line segments having a length equal to or shorter than a predetermined threshold, the directions and lengths of the other line segments are recorded in the halftone dot information storage device 16 for each halftone dot. The halftone dot line direction detection circuit 17 calculates a local direction at the halftone dot from the directions and lengths of a plurality of line segments that intersect each halftone dot.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a fingerprint line direction calculation device and method for detecting the direction of a ridge or valley of a fingerprint for use in a fingerprint collation device or the like.

With the spread of computers throughout society in recent years, public attention has been focused on how to secure safety. Many questions have been raised regarding the security of ID cards and personal identification numbers that have been used up to now as a means of confirming the identity when entering a computer room or using a terminal.

On the other hand, fingerprints are considered to be the most effective means for personal identification because they have the two major characteristics of "universality" and "lifetime invariance", and many simple personal verification systems using fingerprints are considered. Is being researched and developed. Such fingerprint collation requires a technique for recognizing the direction of the ridge or valley of the fingerprint for alignment and noise removal.

[0004]

2. Description of the Related Art In a fingerprint, ridges and valleys are alternately arranged to form a smooth pattern. Therefore, with a noise-free fingerprint, the local direction of the line can be calculated at each point. However, normal images have noise such as cracks in ridges, adhesion between adjacent ridges, and sweat glands. For this reason, research has been conducted on a method of automatically calculating the correct local direction visually by eliminating the influence of these noises.

FIG. 8 is an explanatory view of the prior art. In the conventional technology, in calculating the local direction of the local area of the fingerprint image,
Only the pixels around the same area were investigated. For example, after the fingerprint image is binarized, the binarized image is smoothed by a 3 × 3 logical filter, and the mask patterns <1> to <4> in four directions as shown in FIG. > Is used to count the number of matching pixel values. Then, an average directional angle of the ridge flow is calculated by a weighted average using the four count values as weights.

However, since this method lacks reliability with respect to noise, the directional angle is calculated after updating the initial probability obtained from the four count values by the stochastic relaxation method. Since this method investigates only a narrow area, it has many drawbacks in that direction detection is erroneous and correction is required. References of the prior art include, for example, the following.

References: Sasakawa, Isogai, and Ikebata: "Fingerprint collation device for personal identification with enhanced ability to cope with low-quality images," IEEJ (D-II) Vol.J72-D-II No.5 pp.707. -714 May 1989 Moreover, each pixel is scanned using, for example, an 8-direction quantum mask as shown in (b) of FIG. 8 or a 16-direction quantum mask as shown in (c) of FIG. The detection of the direction in which pixels with pixel values of "1" or "0" are arranged has been performed. However, since this method is performed sequentially for adjacent pixels or their representative points, the same scanning lines are substantially overlapped and scanned, which is inefficient and it takes time to detect the direction. ..

[0008]

SUMMARY OF THE INVENTION The present invention solves the above problems by preventing the detection error of the direction resulting from the examination of only a narrow area and by not scanning the same line many times. It is intended to provide a technique that enables high-speed processing.

[0009]

FIG. 1 is a diagram showing a configuration example of the present invention. In FIG. 1A, 10 is a fingerprint sensor for reading a fingerprint image, 11 is a grayscale image storage device for storing a grayscale image of the fingerprint image, 12 is a binarization circuit for binarizing the fingerprint image, and 13 is a binary. A binarized image storage device for storing the digitized fingerprint image, 14 is an N-direction scanning circuit for scanning the binarized image in N (for example, 4, 8 or 16) directions, and 15 is for measuring the length of a scanning line. A scanning line length measuring circuit, 16 is a halftone dot information storage device for storing information on the direction and length of a scanning line passing through each halftone dot, and 17 is a halftone dot line direction detecting circuit for detecting the halftone dot line direction. , 18 are halftone dot moving circuits for moving the halftone dots when the line direction of the halftone dots cannot be obtained.

The fingerprint image input from the fingerprint sensor 10 is
After the analog / digital conversion, it is stored in the grayscale image storage device 11. The binarization circuit 12 reads it out and binarizes it, and stores the resulting binarized image in the binarized image storage device 1.
Store in 3. In the present invention, the direction of the ridges or valleys of the fingerprint is detected from the binarized image of the fingerprint as follows.

The N direction scanning circuit 14 scans the binarized image in the binarized image storage device 13 in the N direction, and the scanning line length measuring circuit 15 determines the length of the scanning line in which the same pixel value continues. measure. Therefore, except for line segments having a length equal to or shorter than a predetermined threshold value, the directions and lengths of other line segments are recorded in the halftone dot information storage device 16 for each halftone dot.

The halftone dot line direction detection circuit 17 calculates a local direction at each halftone dot from the directions and lengths of a plurality of line segments that intersect each halftone dot. For a halftone dot whose direction cannot be calculated, the halftone dot moving circuit 18 moves the position of the halftone dot and the N direction scanning circuit 14 rescans to determine the local direction of the halftone dot.

Further, for the halftone dots for which the line direction of the fingerprint could not be detected, the threshold used for extracting the line segment in the scanning line length measuring circuit 15 is set low, and the binary image is scanned again. The line direction may be detected by repeating the above.

[0014]

In the present invention, the binarized image of the fingerprint is scanned so that the scanning lines in the N direction are parallel to each other and the intersections thereof form a mesh.
In other words, for example, as shown in (b) of FIG.
Halftone dots are selected every several pixels in the binarized image, and the fingerprint image is scanned in the N direction passing through the halftone dots. FIG. 1C shows an example of the scanning line. As can be seen from the figure, for example, when scanning in 8 directions,
A scan corresponding to the directional quantum will be performed.

The present invention utilizes the fact that pixels having the same value are continuous in the line direction in the smooth ridges or valleys of the fingerprint image, and pixels having the same value are continuous in the scanning line passing through each halftone dot. The number is counted and the direction of the line (ridge / valley) passing through each halftone dot is calculated. By searching for pixels having the same value in a substantially wide area, the accuracy of direction detection is improved.

The scanning line shown in FIG. 1C appears to be scanned along the directional quantum mask shown in FIG. 8C when viewed from each halftone dot. However, in the conventional mask, since the counting process using the mask is performed for each pixel or its representative point, the same scanning line is overlapped and scanned many times. Since the same scanning line is not repeatedly scanned as many times as when using a quantum mask, the processing speed is high.

[0017]

FIG. 2 is an explanatory diagram of scanning line length measurement according to an embodiment of the present invention, FIG. 3 is an explanatory diagram of halftone dot information according to an embodiment of the present invention,
FIG. 4 is an explanatory view of judgment of a line direction according to an embodiment of the present invention, FIG.
Is an explanatory view of detecting a halftone dot line direction according to the embodiment of the present invention, FIG. 6 is an explanatory view of movement of a halftone dot according to the embodiment of the present invention, and FIG. 7 is a flowchart of the embodiment of the present invention.

In FIG. 2A, L is a scanning line, N1
-N3 represents a halftone dot. One square on the scanning line L represents one pixel. Further, the hatched portion represents the ridge of the fingerprint having a value of "1" in the binarized image, and the other portion represents the valley line having a value of "0" in the binarized image.

In the present invention, for example, in the scanning line L as shown in FIG. 2A, the number of consecutive pixels having the same value is counted. Then, the line segment whose count value is equal to or less than the predetermined threshold Th is removed. For example, if the threshold Th is 5, the length of AB is 2, which is smaller than the threshold Th and is therefore removed. Similarly, BC is also removed. The CD has nine pixel values of "0", so the threshold value is larger than Th = 5,
Line segment information is saved. This information is stored for halftone dots N2 and N3 included in the line segment.

As described above, in the binarized image of a fingerprint, the fact that a certain number of pixels having the same value are continuous means that there is a high possibility that the direction indicates the correct direction of the ridge line or the valley line. means. That is, the process shown in FIG. 2A leaves candidates for the correct line direction.

As shown in FIG. 2B, the remaining line segments pass through the above-mentioned halftone dots. That is, in the present invention, instead of scanning the same line only once, each line segment (scan line) is associated with several halftone dots.
In the halftone dot information storage device 16, the direction and length of the same line segment are written for each halftone dot passing through each line segment.

In FIG. 3 (a), the crosses indicate halftone dots and (0
0) to (22) represent halftone dot numbers attached to each halftone dot. For example, for dot (00), direction 1 to direction 5
However, in the scanning in the direction 1, the processing for the halftone dots (01) and (02) is also performed at the same time. When the scanning of the row of halftone dots (00), (01), (02), ...
Scanning is performed on the columns of 0), (11), and (12).
When all the scanning in the direction 1 is completed, the scanning in the direction 2 is performed next.

The information on the line segment extracted by such scanning is stored as halftone dot information, as shown in FIG. That is, for each halftone dot, the number of consecutive pixels having the same value (hereinafter, referred to as scanning line length or line segment length) is stored together with the direction information. For the scanning line length equal to or less than the predetermined threshold value, the value in that direction is set to 0.
The storage format is not limited to the table format as shown in FIG. 3B, but may be stored as a list in which the direction information and the scanning line length are paired.

For example, as shown in FIG. 4, many line segments having a certain threshold value or more overlap each dot. These are candidates for the correct direction at that halftone dot. When the directions are similar to each other, such as the line segments L1 and L2 shown in (a) of FIG. 4, it is possible to select the direction in which the length of the line segment is maximum, or to combine these directions. You can also create new directions.

On the other hand, line segments L1 and L2 shown in FIG.
If there is a combination of directions that are significantly different from each other, it may be a combination of a crack and a valley line or a bridge and a ridge. Detect again.

FIG. 5 shows an example in which, when a plurality of line segments overlap in a similar direction at a certain halftone dot, these vectors are combined to create a new direction. In FIG. 5B, the halftone dot N
2 of direction quantum vector a and direction quantum vector b at
If the line segments of the book overlap, combine their vectors,
The direction of vector a + vector b is the line direction at the halftone dot N.

In FIG. 5B, when two line segments of the direction quantum vector a and the direction quantum vector b overlap at the halftone dot N, first, the lengths of these vectors are made equal,
Then combine the vectors. For example, | a | <| b |
In this case, a vector b ′ having the same direction as the vector b and the same length as the vector a is calculated, and then the vector a and the vector b ′ are combined to obtain the line direction at the halftone dot N.

For example, as shown in (b) of FIG. 4 described above, the line segments may be combinations in which the directions are greatly different from each other, or, as shown in (a) of FIG. If there are halftone dots for which the local direction could not be calculated because there are no line segments to have, the following processing is performed.

As shown in FIG. 6B, the halftone dot N1 for which the local direction cannot be calculated is moved to the position N2 by shifting the halftone dot N1 in an arbitrary direction by a distance of about half the interval between the scanning lines. For the scanning line in the N direction passing through this new halftone dot N2, the line direction detection processing is similarly performed. As shown in (a) of FIG. 6, even if the direction may not be detected because the halftone dot N1 is on the ridge with many cracks, the scanning line is slightly shifted as shown in (b), and the adjacent valley is detected. By scanning the line, the line direction can be detected.

For a halftone dot whose direction cannot be detected, the halftone dot is not moved as shown in (b) of FIG. It is also possible to make it possible to detect the line direction even in the part where the change is drastic by resetting the setting low. Further, for a halftone dot whose direction cannot be detected, the direction calculated in the surrounding halftone dots can be borrowed and set as the direction of the halftone dot.

Next, the flow of processing according to the embodiment of the present invention will be described with reference to (a) to (m) shown in FIG. (a) The fingerprint sensor 10 reads the fingerprint and stores the grayscale image in the grayscale image storage device 11.

(B) The fingerprint image stored in the grayscale image storage device 11 is binarized by the binarization circuit 12 and stored in the binarized image storage device 13. (c) Binarized image storage device 13 by N-direction scanning circuit 14
The binary image of is scanned for each parallel scanning line in each direction.

(D) The scanning line length measuring circuit 15 measures the length of a scanning line in which the same pixel value continues. (e) It is determined whether the length of the scanning line is greater than or equal to a predetermined threshold. If it is less than or equal to the predetermined threshold value, the line segment information is discarded and the process (g) is performed.

(F) If the length of the scanning line is equal to or larger than a predetermined threshold value, the direction and length of the line segment are recorded in the halftone dot information storage device 16 for each halftone dot. (g) It is judged whether or not the scanning of all the scanning lines in one direction is completed. If not completed, the process returns to the processing (c), and the same scanning is performed for the next scanning line.

(H) When scanning of all scanning lines in one direction is completed, it is determined whether scanning in all directions is completed. If not finished, the process returns to the process (c), and scanning of the scanning line in the next direction is continued. When finished, process
Move to (i).

(I) Referring to the halftone dot information storage device 16, the line direction is detected for each halftone dot. At this time, if necessary, vector composition as shown in (a) or (b) of FIG. 5 is performed.

(J) The local line direction for each halftone dot is determined based on the result of combining. (k) Determine whether there is a halftone dot whose direction cannot be detected. If there is no halftone dot whose direction is unknown, the process ends.

(L) When there is a halftone dot of which the direction is unknown, the halftone dot moving circuit 18 moves the halftone dot by a distance of about half the scanning line interval. Alternatively, the threshold value for the number of consecutive pixels having the same value is changed to a smaller value.

(M) The processes similar to the processes (c) to (j) are repeated to detect the line direction of the halftone dots. The hardware for realizing the above processing can be easily realized by applying well-known image processing circuit technology. It can also be realized by firmware or software such as a microprocessor.

The information on the line direction of the fingerprint obtained as described above can be used to efficiently perform the alignment when the input fingerprint is compared with the fingerprint stored in advance. Further, it can be used in the case where the value of the fingerprint image is integrated in the detected line direction and reset, thereby removing noise.

[0041]

As described above, according to the present invention,
It has the following effects. (1) Since the number of consecutive pixels of the same value is checked on the binarized image, there is less error in judgment due to noise compared to the conventional method that uses only information in a narrow area.

(2) When the directional quantum mask is scanned, the same line is scanned many times, but in this method, the same portion is scanned only once, so the processing is fast. (3) The directional quantum mask has a length of about 16 to 32 pixels, whereas the present method has no such limitation. Therefore, it is possible to detect a line that continues smoothly for longer than 32 pixels.

(4) Since the bit processing is performed on the binarized image instead of the byte processing on the grayscale image, the hardware or the like can be reduced.

[Brief description of drawings]

FIG. 1 is a diagram showing a configuration example of the present invention.

FIG. 2 is an explanatory diagram of scanning line length measurement according to an embodiment of the present invention.

FIG. 3 is an explanatory diagram of halftone dot information according to the embodiment of the present invention.

FIG. 4 is an explanatory diagram of determination of a line direction according to an embodiment of the present invention.

FIG. 5 is an explanatory diagram of detection of a halftone dot line direction according to an embodiment of the present invention.

FIG. 6 is a diagram illustrating movement of halftone dots according to an embodiment of the present invention.

FIG. 7 is a flowchart of an embodiment of the present invention.

FIG. 8 is an explanatory diagram of a conventional technique.

[Explanation of symbols]

 10 Fingerprint Sensor 11 Grayscale Image Storage Device 12 Binarization Circuit 13 Binary Image Storage Device 14 N Direction Scanning Circuit 15 Scanning Line Length Measuring Circuit 16 Halftone Information Storage 17 Halftone Direction Detection Circuit 18 Halftone Moving Circuit

Claims (4)

[Claims] 1. A binary line image storage device (13) for storing a binarized fingerprint image in a fingerprint line direction calculation device for detecting the direction of a ridge line or a valley line of a fingerprint, and the binarization. An N-direction scanning means (14) for scanning a binarized image stored in the image storage device at predetermined intervals in a plurality of predetermined directions and a length of a scanning line in which pixels having the same value in each scan are continuous. Measure
Scanning line length measuring means (15) for extracting line segments above a predetermined threshold
And a halftone dot information storage device (1) for storing, for each halftone dot formed by intersections of the scanning lines in the plurality of directions, line segment information extracted by the scanning line length measuring means and having a predetermined threshold value or more.
6) and halftone dot line direction detecting means (17) for detecting the direction of the ridge or valley line of the fingerprint for each halftone dot by referring to the line segment information stored in the halftone dot information storage device. A device for calculating the line direction of a fingerprint. 2. The fingerprint line direction calculation device according to claim 1, wherein a position of a halftone dot is moved within a range smaller than an interval between adjacent halftone dots with respect to a halftone dot whose fingerprint line direction cannot be detected. A fingerprint line direction calculation device comprising a halftone dot moving means (18) for detecting the line direction of a fingerprint for a moved halftone dot. 3. A fingerprint line direction calculation method for detecting the direction of a ridge line or a valley line of a fingerprint, wherein the scanning lines in a plurality of directions are parallel to each other and the intersections of the scanning lines form a mesh pattern. The process of scanning the binarized image, the process of counting the number of consecutive pixels with the same value during scanning, and measuring the length of the line segment where the same value continues, and the length of the line segment exceeds the threshold Based on the process of recording only the line segment and recording the direction and length of the line segment that passes through the same point for each halftone dot, and the record of the line segment for each halftone dot, the ridge or valley of the fingerprint for each halftone dot A method for calculating the line direction of a fingerprint, comprising the step of calculating the line direction. 4. The fingerprint line direction calculation method according to claim 3, wherein the number of consecutive pixels having the same value when extracting the line segment is compared with the halftone dot for which the line direction of the fingerprint cannot be detected. A method for calculating a line direction of a fingerprint, wherein the threshold value to be set is set lower than in the previous process to detect the line direction.