JP2734245B2 - Image feature extraction method and apparatus - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and an apparatus for extracting image features used for collating or classifying skin patterns such as fingerprints.

[0002]

2. Description of the Related Art A fingerprint collation device used for entry control, criminal investigation, and the like performs collation and classification of fingerprint patterns. At this time, it is important how to extract features of the fingerprint patterns. When fingerprints are collated, a minutia composed of the end points and branch points of fingerprint ridges is used for this feature extraction. When classifying fingerprints, singular points such as the center of a fingerprint pattern and a delta are used. Feature extraction for skin ridge systems such as finger prints and palm prints can be handled in the same manner as fingerprints. Here, how to extract the fingerprint minutiae,
Two points of a method of extracting a singular point which is a portion where the flow of the pattern changes rapidly will be described.

Conventionally, when a fingerprint collation device extracts a fingerprint minutiae, it first binarizes an input fingerprint pattern image and further thins it. Next, the end points and branch points of the thin line image thus obtained are extracted as fingerprint minutiae. As a method of extracting this minutia from a striped pattern such as a skin pattern, an image in which the ridge side of a fingerprint is thinned (a ridge thin line image) and an image in which a valley appearing between ridges is thinned (a valley) (A thin line image) (Japanese Patent Laid-Open No. 59-144982). In this method, first, a mask is set according to the direction for each of the ridge and the end point of the valley. In the mask, there is a branch point of the valley if it is a ridge, and a branch point of the ridge if it is a valley. If so, the ridge end point is selected, and if it is a valley, those without valley end points are selected as feature points. Although the end point and the branch point of the ridge should be selected as the feature point, the branch point of the ridge is regarded as corresponding to the end point of the valley, and the end point of the ridge and the valley is selected as the feature point. The ridge direction is obtained by tracing the ridge from the end points of the ridge and the valley. That is, this method uses a skin pattern characteristic such that the branch point of the ridge corresponds to the end point of the valley and the branch point of the valley corresponds to the end point of the ridge as seen in the skin pattern of FIG. I have. However, this property does not always hold for the minutia of the center and delta in fingerprints where the flow of ridges changes rapidly. That As shown in FIG. 8, although there are minutia in the valley image, and if not appear minutiae in the ridge image corresponding to the minutiae, as in FIG. 9, although there are minutiae in the ridge image, the valley image <br The corresponding minutia may not appear in the image. Therefore, if this method is used, it may be impossible to extract a feature point in a portion where the flow of the ridge changes abruptly.
The method of extracting a minutia from a skeleton image has been described above. However, in order to extract a minutia, a thin line is not necessarily required, and there is also a method of extracting a minutia from a grayscale image (Koichiro Morita et al. Communication Association, AL85-56, "Fingerprint collation terminal for personal identification").

[0004] As for a method of detecting the center of a fingerprint pattern or a delta, a method using a ridge direction pattern is generally used. As one of the methods, there is a method of detecting by checking a directional distribution (Transactions of the Institute of Electronics, Information and Communication Engineers, '8
2, vol. J65-D. No. 10. pp1286-
1293, Nori Nakamura et al., "Fingerprint Image Classification by Direction Distribution Pattern"). In this method, first, a fingerprint image is divided into small areas, and ridge directions in each of the small areas are obtained, thereby extracting a ridge direction pattern of the entire fingerprint. Next, a singular point such as a center or a delta is detected by passing a circular window through the ridge direction pattern and obtaining a direction distribution in this region. However, when a singular point such as a center or a delta is detected using the ridge direction pattern, it is not possible to indicate on which ridge the singular point exists because the ridge image is not referred to.

[0005]

In the conventional method described above, when comparing the minutiae at the ridge line and the minutiae at the valley line, even if the image is ideally beautiful, the center of the fingerprint or the ridge-like skin ridge is obtained. In the portion where the flow of the changes rapidly, the correspondence between the end point and the branch point is not always established by the minutiae extracted from the ridge line and the minutiae extracted from the valley line. That is, even if the minutiae can be extracted from the ridge line, the minutiae corresponding to the minutiae of the ridge line is not extracted at the valley line, or the minutiae extracted at the valley line is not extracted at the ridge line. In addition, it is impossible to detect a singular point in the center of the fingerprint or in a delta-like portion. Furthermore, even in the method of extracting minutiae using the ridge image and the valley image, the ridge direction and position are extracted from one extracted minutiae, and the direction and position of the corresponding minutiae are ignored. Will be done.

An object of the present invention is to obtain the correspondence of minutiae to more stably extract the features of the minutiae, and at the same time, the flow of the ridge pattern, which cannot be extracted by the conventional method, rapidly. It is also to extract feature points in a changing part. Further, a singular point in the center of the fingerprint or in a delta-shaped portion is extracted, and the minutiae information is made available for use in fingerprints, palmprint classification, fingerprint collation devices or personal identification devices.

[0007]

According to a first aspect of the present invention, there is provided an image feature extracting method for extracting a feature from a skin pattern image, wherein the minutiae group of the ridge line corresponding to the ridge of the skin pattern is provided. The minutiae group of the valley line corresponding to the valley portion between the ridge lines is extracted, and the minutiae group of the ridge line and the minutiae group of the valley line are paired.
Ridge line or valley line does not exist between two points
And a corresponding minutia that is a pair of a corresponding ridge line end point and a valley line branch point or a corresponding ridge line branch point and a valley line end point is paired. extracts feature points, said extracted
Based on the set of minutia pairs
The method is characterized in that features associated with the user are extracted .

According to a second aspect of the present invention, there is provided an image feature extracting method for extracting a feature from a skin pattern image.
Ridge minutiae groups corresponding to skin pattern ridges,
The minutiae group of the valley line corresponding to the valley portion between the ridges is extracted, and the end point of the corresponding ridge line and the branch point of the valley line among the minutiae group of the ridge line and the minutiae group of the valley line are extracted. Or a combination of corresponding minutiae that forms a pair of a branch point of a corresponding ridge line and an end point of a valley line, and extracting an isolated peculiar minutiae without a corresponding minutiae as a feature point of an image. I do.

A third aspect of the present invention is an image feature extracting method for extracting a feature from a skin pattern image.
Ridge minutiae groups corresponding to skin pattern ridges,
The minutiae group of the valley line corresponding to the valley portion between the ridges is extracted, and the end point of the corresponding ridge line and the branch point of the valley line among the minutiae group of the ridge line and the minutiae group of the valley line are extracted. Or a pair of corresponding minutiae that form a pair of a corresponding ridge line branch point and a valley line end point, and extracting feature points of the image by the pair of minutiae, and an isolated singularity without a corresponding minutiae. An image feature extraction method for extracting various minutiae as image feature points.

According to a fourth aspect of the present invention, there is provided an image feature extracting apparatus for extracting a ridge minutiae group corresponding to a ridge of a skin pattern image, and a valley corresponding to a valley between the ridges. A valley minutia extracting means for extracting a line minutiae group, and two pairs of pairs of the extracted ridge line minutiae group and valley line minutiae group
In such a way that the ridge line or the valley line does not exist , a pair of a corresponding ridge line end point and a valley line branch point, or a corresponding ridge line branch point and a valley line end point pair. a corresponding minutia extracting means for extracting a corresponding minutiae, Manyu from the corresponding minutiae the extracted
Minutesha feature extraction method for extracting features associated with sha
And a step .

According to a fifth aspect of the present invention, there is provided an image feature extracting apparatus for extracting a ridge minutiae group corresponding to a ridge of a skin pattern image, and a valley corresponding to a valley between the ridges. A valley minutia extracting means for extracting a line minutiae group, a pair of an end point of the corresponding ridge line and a branch point of the valley line, or a corresponding ridge line among the minutiae group of the ridge line and the minutiae group of the valley line. An isolated minutiae extracting means for combining corresponding minutiaes that form a pair of a branch point and an end point of a valley line and extracting an isolated minutiae without a corresponding minutiae is provided.

[0012]

[Function] At the part where the flow of the ridge changes rapidly from the skin pattern (the center or delta in the case of fingerprints), it can be detected by the ridge line, but can not be detected by the valley line. There may be minutiae that are extracted but not extracted by the ridge line. The present invention can extract the minutia as a feature point. Also, normally, for minutiae that can be extracted, the minutiae of the corresponding ridge and valley can be extracted, so that the direction and position of the minutiae can be more accurately extracted.

This will be described below.

A minutia appearing in a portion where the flow of the skin pattern is gentle appears as a branch point in the valley image if it is an end point in the ridge image as shown in FIG. Since the branch point of the valley appears near the end point that appears in the ridge image, the combination of minutiae is extracted as a feature point. Conversely, a minutia appearing as an end point in the valley image appears as a branch point in the ridge image.
In this case, the minutia can be extracted similarly. But,
This is not the case where the flow of the ridge changes abruptly. First, as an example, a portion where the flow of the skin ridge changes abruptly in the center of the fingerprint will be described with reference to the images of FIGS. In FIG. 8, first, nothing is detected as the ridge line minutiae. An end point is detected as a valley line minutiae. Since there is no minutia near this end point, it is determined that there is no corresponding minutia,
This point is extracted as a singular point. Conversely, in FIG. 9, even if there is an end point at the ridge, there is no branch point at the valley.

The portion where the flow of the ridge changes in a triangular shape of the fingerprint will be described with reference to, for example, the image shown in FIG.
In this image, first, as the ridge line minutiae,
No minutiae are detected. In the valley image, a branch point can be detected. Since no minutiae of the corresponding ridge is detected near this branch point, this branch point is extracted as a singular point.

As described above, according to the present invention, feature points that cannot be detected by examining only the ridge line image or only the valley line image can be extracted, and the flow of ridges can be sharply increased. The singular point in the portion that changes to can also be extracted. As a result, it becomes possible to extract a singular point in a core or a delta conventionally used for classification of a fingerprint image.

Further, since the correspondence between the minutiae of the ridge and the minutiae of the valley is determined, the minutiae information can be further obtained by averaging information such as the position and direction extracted from the corresponding end points and branch points. Can be obtained stably. Particularly, the direction information can be obtained more accurately in a portion where the flow of the ridge changes relatively sharply.

[0018]

FIG. 1 is a block diagram showing an embodiment of an image feature extracting apparatus according to the present invention.

This image feature extracting apparatus includes an image storage means 11 for recording an image of a skin pattern such as a fingerprint input from a CCD camera or the like, and a ridge image corresponding to a ridge portion of the stored skin pattern image. Ridge minutiae extracting means 12 for extracting minutiae which are end points or branch points of a ridge line
Valley minutiae extracting means 13 for extracting minutiae corresponding to valleys between ridges, which are end points and branch points of valley lines in the valley image; and between the extracted ridge minutiae and valley minutiae, Corresponding minutiae extracting means 14 for extracting minutiae having a corresponding relationship such as a valley branch point for an end point and a valley end point for a ridge branch point.
And a minutia feature extracting unit 15 for extracting minutia features such as the direction of the minutia from the extracted minutia.

A description will be given of a case where a feature point of a skin pattern is extracted by the image feature extracting apparatus having the above configuration. FIG.
Will be described in more detail with reference to a case where processing is performed according to a processing flow as shown in FIG. The image input by the CCD camera or the like is stored by the image storage unit 200. The image storage means is realized by a memory.

The ridge minutiae extracting means 210 for extracting the ridge minutiae from the image stored by the image storage means 200 binarizes the image, converts the image into a center line, and scans the image with a minutiae detection mask as shown in FIG. To detect minutiae. The minutiae detected by the minutiae detection mask shown in FIG. 4A is an end point, and the minutiae detected by the mask shown in FIG. 4B is a branch point. In this way, the ridge minutiae extracting means 210 extracts the end point of the ridge image and the branch point of the ridge image, respectively, and creates a list thereof (steps 211 and 212).

The valley minutiae extracting means 220 for extracting the valley minutiae is provided by the ridge minutiae extracting means 2.
The same processing as that for the ridge image is performed by inputting an image obtained by inverting the shade of the ridge image as the input image 10. In addition, ridge and valley minutiae extracting means 210 and 220
Is a method of raster matching that does not necessarily require centering and extracts minutiae directly from a grayscale image (Koichiro Morita et al., IEICE Technical Report AL85-
56, “Fingerprint collation terminal for personal identification”).

Next, the corresponding minutiae extracting means 230 for associating the minutiae group of the ridge and the valley thus extracted will be described. Ridge minutiae and valley minutiae usually have the following one-to-one correspondence.
The end points of the ridge appear corresponding to the branch points of the valley, and the branch points of the ridge appear corresponding to the end points of the valley. The correspondence is obtained by utilizing this property. Steps 231, 232, 23
In step 3, the correspondence between the end point of the ridge and the branch point of the valley is examined using the minutialist obtained in steps 211 and 222. By this process, the correspondence between the end point of the ridge and the branch point of the valley is associated, and a unique minutiae isolated in each process is extracted. Similarly, in steps 234, 235, and 236, the correspondence between the end point of the valley and the branch point of the ridge is also examined. Based on the corresponding minutialist obtained by the corresponding minutiae extracting means, in step 240, the average value of the minutiae position and the minutiae direction is used as the minutiae feature amount, so that a conventional feature extraction method such as a minutiae network feature (electronic Information and Communication Engineers Transactions D-II, vol.J72-D-II, No.
5, pp. 724-732 (1989), Hiroshi Asai et al.,
"Automatic Fingerprint Verification Using Minute Sharp Network Features-
The feature is extracted by a feature extraction process-)).

Hereinafter, steps 231, 232, and 233 will be described.
Will be described in detail. Step 231 is realized by an algorithm as shown in FIG.

First, in step 301, a valley branch point appearing within a distance L near the ridge end point i registered in the ridge end point list obtained by the process 211 is selected from the valley branch point list. look for. In this method, the distance is obtained from the coordinates of the end point and the coordinates of the branch point, and it is determined whether or not there is a neighborhood based on the distance. It may be determined whether or not a branch point exists. If there is no valley branch point near the ridge end point i, it is determined that there is no corresponding valley branch point at this ridge end point i. Then, the end point i is set as an isolated point, and registered in an isolated point list in step 311. If there is a valley branch point near the end point i of the ridge, the branch point of the valley is registered in a list of branch points near the end point i in step 302. Next, with respect to the branch points in the registered neighboring branch point list, in step 303, the end point i
It is checked whether a ridge line or a valley line exists between and the branch point. If the ridge line or the valley line exists between the end point i and the branch point, it is determined that this branch point is not the branch point of the valley corresponding to the end point i, and the branch on the remaining neighboring branch point list is determined. Find out about points. If the ridge line or the valley line does not exist between the end point i and the branch point, in step 304, the branch point of the valley is set as a candidate of the branch point of the valley corresponding to the end point of the ridge. Register on the list. Step 305
After checking the existence of the ridge line and the valley line for all the neighboring branch points on the neighboring branch point list, in step 306, the number of the corresponding branch point candidates on the corresponding branch point candidate list is examined. If a ridge line or a valley line exists between all the branch points on the nearby branch point list and the end point i and no corresponding branch point candidate exists, it is determined that the end point i of the ridge is an isolated point. When there are a plurality of corresponding branch point candidates, the corresponding branch point list is stored as a corresponding branch point list for the end point i of the ridge. If there is only one corresponding branch point, the end point i and the only valley branch point j on the list of corresponding branch points are determined to be the branch points corresponding to the end points of the ridge, and the corresponding minutialist is determined in step 314. register. Since there is no need to check the correspondence between the registered ridge end point i and the valley branch point j thereafter, it is excluded from the valley branch point list when searching for nearby branch points. If the branch point j exists on the corresponding branch point candidate list of the end point m of another ridge, the branch point j is also excluded from this list. As a result, if the candidate in the corresponding branch point candidate list of the ridge end point m is only the valley branch point n, it is determined that the ridge end point m and the valley branch point n are in a correspondence relationship. . Thereafter, the process returns to step 313 in the same manner, and the end point m of the ridge and the branch point n of the valley are registered in the corresponding minutialist, and the list is updated. After the registration of the corresponding minutiae and the updating of the list, the flow returns to step 309. If the processing has not been performed for all the ridge end points, the flow returns to step 302 to repeat the processing. When the processing has been completed for all the ridge end points, the processing proceeds to the next processing step. Thus, step 231 in FIG. 2 is completed.

After the step 231 is completed, the process proceeds to a step 232. This is because even if the processing for all the end points is completed in step 231, for example, in the case of a disconnected minutia as shown in FIG. 5, a plurality of corresponding branch point candidates for the two end points remain forever. Would. In order to cope with such a case, when there are a plurality of processing corresponding branch point candidates, among the branch points on the corresponding branch point candidate list, the corresponding branch point candidate closest to the end point of the ridge is determined as the corresponding branch point, Register with the corresponding minutialist. Updating of the list after registration is performed in the same manner as in step 313 and subsequent steps in FIG. In this way, the end points of all the ridges are registered in the corresponding minutialist or isolated point list. In step 233, all the branch points of the remaining valleys that are not registered in the corresponding minutialist are determined as isolated points.

FIG. 6 is a block diagram showing another embodiment of the image feature extracting apparatus of the present invention.

The image feature extracting apparatus includes an image storage means 61 for storing an image of a skin pattern such as a fingerprint input from a CCD camera or the like, and a ridge of a ridge image corresponding to a ridge portion of the stored skin pattern image. Ridge minutiae extracting means 62 for extracting minutiae which are end points and branch points of the line;
A valley minutiae extracting means 63 for extracting a minutia which is an end point or a branch point of a valley line of a valley image corresponding to a valley portion between ridges, and a valley if the ridge end point is between the extracted ridge minutiae and the valley minutiae. An isolated minutiae extracting means 64 for extracting minutiae having no correspondence, such as a branch point and an end point of a valley if a branch point of a ridge, and an isolated minutiae utilization means for utilizing an isolated point extracted by the isolated minutiae extracting means. Prepare.

Each of the means 61, 62 and 63 in FIG.
11, 12, and 13. The isolated minutiae extracting means 65 outputs an isolated point obtained by the intermediate processing of the corresponding minutiae extracting means 14 in FIG. The isolated minutiae utilization means 65 is means for utilizing the singular minutiae on the isolated point list output by the isolated minutiae extraction means 64.
It is realized by displaying on T. The extracted singular minutiae is a singular point related to the center of the fingerprint or the delta that serves as a reference when classifying the fingerprint. For example, by superimposing and displaying the unique minutia on the original image or the skeleton image by the isolated minutia utilization means 65, it is possible to easily perform the classification of the fingerprint by hand.

[0030]

According to the present invention, in addition to the minutia extracted from only the ridge image or the valley image, the minutia that could not be obtained by itself can be extracted. As a result, many feature points can be extracted, and the accuracy of fingerprint collation can be improved.

Further, by obtaining the correspondence between minutiae at the ridge and the valley, it becomes possible to more stably obtain minutiae information such as the position and direction of the corresponding minutiae. The accuracy of fingerprint collation can be improved.

Further, according to the present invention, a singular point appearing in a rapidly changing portion of a skin pattern can be extracted independently of a normal minutiae. Thereby, when classifying fingerprints, it is possible to extract a singular point appearing at an important fingerprint center or a delta, and the use of the extracted singular points has an effect that fingerprint classification is facilitated. It goes without saying that fingerprint classification is performed at the time of registration and collation in a fingerprint collation device used in criminal investigation .

[Brief description of the drawings]

FIG. 1 is a block diagram showing an embodiment of an image feature extraction device according to the present invention.

FIG. 2 is a diagram for explaining FIG. 1;

FIG. 3 is a diagram for explaining a corresponding minutiae extracting unit in FIG. 1;

FIG. 4 is a diagram for explaining minutiae detection in FIG. 1;

FIG. 5 is a diagram for explaining a corresponding minutia in FIG. 1;

FIG. 6 is a block diagram showing an embodiment of an image feature extraction device according to the present invention.

FIG. 7 is a diagram for explaining the operation of the present invention.

FIG. 8 is a diagram for explaining the operation of the present invention.

FIG. 9 is a diagram for explaining the operation of the present invention.

FIG. 10 is a diagram for explaining the operation of the present invention.

[Explanation of symbols]

 Reference Signs List 11 image storage means 12 ridge minutiae extraction means 13 valley minutiae extraction means 14 corresponding minutiae extraction means 15 minutiae feature extraction means 61 image storage means 62 ridge minutiae extraction means 63 valley minutiae extraction means 64 isolated minutiae extraction means 65 display means

Claims (5)

(57) [Claims] An image feature extracting method for extracting a feature from a skin pattern image, wherein the minutiae of a ridge line corresponding to a ridge of the skin pattern and the minutiae of a valley line corresponding to a valley portion between the ridges. And a pair is selected from the minutiae group of the ridge line and the minutiae group of the valley line.
There is no ridge line or valley line between two points
Thus, a pair of corresponding ridge line end points and valley line branch points, or a corresponding ridge line branch point and valley line end point pair, is combined with a corresponding minutiae, and the minutia pair group is used to generate an image. extracts feature points, the extraction of
Based on the minutiae pair group
An image feature extraction method characterized by extracting features associated with a pusher . 2. An image feature extracting method for extracting a feature from a skin pattern image, wherein the minutiae of a ridge line corresponding to a ridge of the skin pattern and the minutiae of a valley line corresponding to a valley portion between the ridges. A group of minutiae of the ridge line and a pair of minutiae of the valley line, a pair of a corresponding ridge line end point and a valley line branch point, or a corresponding ridge line branch point and a valley line end point. An image feature extraction method characterized by combining corresponding minutiaes that form a pair with each other and extracting an isolated unique minutiae without a corresponding minutiae as a feature point of the image. 3. A minutiae group of ridge lines corresponding to ridges of a skin pattern and a minutiae of valley lines corresponding to valleys between the ridges, in the image feature extraction method for extracting a feature from a skin pattern image. A group of minutiae of the ridge line and a pair of minutiae of the valley line, a pair of a corresponding ridge line end point and a valley line branch point, or a corresponding ridge line branch point and a valley line end point. An image feature extraction method that combines corresponding minutiae that forms a pair, extracts feature points of an image using the pair of minutiae, and extracts isolated unique minutiae without a corresponding minutiae as feature points of the image. 4. A ridge minutiae extracting means for extracting ridge line minutiae groups corresponding to ridges of a skin pattern image,
Valley minutiae extraction means for extracting a valley minutiae group corresponding to the valley portion between the ridges, and a ridge line minutiae group extracted and a valley line minutiae group,
The ridge line or the valley line exists between two pairs of points.
Corresponding minutiae extraction means for extracting a corresponding minutiae that is a pair of a corresponding ridge line end point and a valley line branch point, or a corresponding ridge line branch point and a valley line end point pair so as not to be present. , The extracted corresponding manual
Manifold that extracts features associated with minutiae from
Image feature extraction apparatus characterized by comprising a Yusha feature extraction means. 5. A ridge minutiae extracting means for extracting ridge line minutiae groups corresponding to ridges of a skin pattern image, and a valley minutiae for extracting valley line minutiae groups corresponding to valleys between the ridges. Extraction means, of the minutiae group of the ridge line and the minutiae group of the valley line, a pair of a corresponding ridge line end point and a valley line branch point or a corresponding ridge line branch point and a valley line end point pair. An isolated minutiae extracting means for extracting an isolated minutiae without a corresponding minutiae by combining the corresponding minutiae with each other.