JPH05233782A - Image collation method and image collation device - Google Patents

Abstract

(57) [Summary] [Purpose] To identify images, two binary images are collated at high speed and the memory amount of registration information is reduced. In an image matching device 1 for matching a first image and a second image, which are binary images, a set of one or more black pixels is treated as a line, and the line width of the first image is set to the original line width. The individual black pixel addresses of the first converted image obtained by processing by the line width designation value narrowing processing means of less than are stored in the memory 6 as registration information, the second image is stored in the image memory 4, and the first image is stored. In the comparison between the second image and the second image, the registration information of the first image and the second changed image obtained by processing with the line width designation value narrowing processing means including the case where the line width of the second image remains unchanged. The processing device 5 determines the matching between the first image and the second image by the matching processing means with the individual black pixel addresses.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to pattern recognition of digitized images (fingerprints, imprints, figures, characters, etc.) to an image collation device (electronic computer, electronic exchange, communication control device, I
When using hardware and / or software such as a C card, an image processing device, or a recognition device),
The present invention relates to an image collating method and an image collating apparatus for collating two images and determining whether they are coincident or not based on the coincidence (degree of coincidence) of those images.

[0002]

2. Description of the Related Art As an example of an image targeted for pattern recognition, a case where the image is a fingerprint will be described. A fingerprint is a ridge pattern on a finger. Since the valley line (between ridges) is determined by the ridge line, the pattern drawn by the valley line may be used as the fingerprint instead of the ridge line. The line treated as a fingerprint is called a fingerprint line.

A fingerprint input device for identifying a person is a prism system (for example, Shimizu et al., “French information detection method using prism”) as a system for inputting from an image pickup device (for example, CCD (charge coupled device) camera). -Comparison of total internal reflection method and optical path separation method- ", IEICE Transactions, Vol.J68-D, No.
3, pp.414-415 (1985)), and hologram method (for example, Igaki et al. "Personal collation device using holographic fingerprint sensor", IEICE technical research report, PRU8
7-31, pp.27-33 (1987)).

A fingerprint image of analog information input from the image pickup device is converted into a digitized grayscale image of the fingerprint by an A / D (analog / digital) converter.
The grayscale image of the fingerprint is displayed by the coordinates (X, Y) which are the pixel addresses of the image memory and the brightness of the pixels which are the constituent elements of each pixel address of the image memory. In addition, the unevenness of the fingerprint may be directly converted into a binary image to be a fingerprint image.

The grayscale image of the fingerprint can be corrected by smoothing, ridge direction, and the like. There are end points, branch points, and intersections as the characteristic points that represent the characteristics of the fingerprint. For the feature points of the digitized fingerprint image of the fingerprint, the fingerprint image is binarized and further thinned, and the range of pixels representing the feature points (for example, a set of 3 × 3 pixels centering on the feature points) is used. Can be detected by the presence of the same pattern as the pattern in the thinned image
(For example, Sasakawa et al., "Fingerprint collation device for personal identification with enhanced ability to deal with low quality images", IEICE Transactions, Vol.J72-D-II, No.5, pp.707-714 ( 1990)).

In the collation of fingerprints, a fingerprint for which information for collation is registered in a memory in advance is referred to as a registered fingerprint, and a fingerprint for matching with the registered fingerprint is referred to as an inspection fingerprint. Known methods of collating the registered fingerprint and the inspection fingerprint include a method using a feature point, a method using the direction of a ridge, and a method using pattern matching between original images of the registered fingerprint and the inspection fingerprint. As a method of pattern matching between thinned images, Japanese Patent Application No. 63-132386 describes a matching method by superimposing a thinned image of a registered fingerprint and a thinned image of an inspection fingerprint.

Smoothing is a process for reducing the influence of noise on a fingerprint image. For example, there is a locally weighted average filter that uses the values of neighboring pixels of an arbitrary pixel. Takagi and Shimoda (supervised) "Image Analysis Handbook" , Pp.538-548, University of Tokyo Press (1991), etc.

The thinning of a binary image means that the line width of most of the pixels (the majority means more than half to all, and ideally all) of the pixels of the type of line object is one pixel. The pixel of the target type is either a black pixel or a white pixel, but will be described as a black pixel hereinafter.

As a method for binarizing a grayscale image and thinning the binary image, the black pixels on the outer side in the set of black pixels are connected to each other (4 connection or 8 connection). There is a Hilditch thinning method that holds and sequentially deletes (for example, Tamura (supervised) "Introduction to Computer Image Processing", Soken Publishing, pp.80-83 (1985), Tamura, " Research on multi-faceted image processing and its software system ", Research Report of Electrotechnical Laboratory, pp.25-64, 83
No. 5 (February 1984) and Mori et al., "Basics of Image Recognition [I]", pp.65-71, Ohmsha (1986)). Japanese Patent Application 2-24
No. 2473 (binarization and thinning of grayscale images), Japanese Patent Application No. 3-
No. 45136 (Image thinning method) also describes a thinning method for a grayscale image or a binary image.

When inputting a fingerprint, an inspection fingerprint and a registered fingerprint are used.
Since the positional deviation (rotation and / or parallel movement) occurs, the verification of the inspection fingerprint and the registered fingerprint requires alignment of both fingerprints. As the alignment method (rotation and parallel movement), the method that uses the ridge direction, the method that uses the representative feature points and the peripheral feature points, and the trial and error for the range in which only parallel movement is possible Positioning method and the like are known. The formulas of coordinate transformation and geometric transformation required for alignment are described in, for example, Plastock et al., Koriyama Translation "Computer Graphics", pp.84-
88, McGraw-Hill Book (1987).

It is useful to find an approximate center point of the fingerprint image in the alignment at the time of matching. Japanese Patent Sho 58
No. 55548 "Method of determining center position of figure" describes a method of sequentially searching in a direction in which the slope of a ridge is steep to obtain a center point. In Ito et al., "Classification Method of Fingerprint Images Focusing on Central Point", Technical Report, PRU89-79, pp.15-22 (1989), the number of intersections with parallel lines on each side of a rectangle is described. make use of,
A method of sequentially approaching the center position is described. "A Study on Extraction of Reference Points in Fingerprint Matching", 1987 IEICE National Conference on Information and Systems, No.12
In 5, the approximate center point is obtained from the information obtained by counting the number of ridges passing through each scanning line.

[0012]

DISCLOSURE OF THE INVENTION Problems to be Solved by the Invention
In the collation method based on branch points and intersections, it is difficult to perform collation when feature points are unclear or the number of feature points is small. In the ridge direction collation method, it is difficult to collate a fingerprint when the input fingerprint has a large inclination or a large variation in the ridge direction.

Further, in the method based on the feature points and the ridge direction,
It takes a lot of processing time to correct broken lines and adhesions in the image. In the matching method based on pattern matching between original images, the width of the ridge of the fingerprint at the time of imprinting varies depending on the pressure of the finger and the dry state, so that misidentification is likely to occur, and moreover, the registration information is stored. The amount of memory for this is increased.

Further, in the collation method based on the pattern matching between the thinned images, when one of the fingerprints has a low quality or the input has a rotational movement, the thinned image is deformed, and thus the collation is difficult. Is.

The present invention solves the above problems,
It is an object of the present invention to compare two binary images at high speed for image identification and to reduce the storage amount of registration information.

[0016]

According to the present invention, two images of a binary image having black pixels and white pixels as constituent elements of the pixels of the image are defined as a first image and a second image, and one or more black pixels. Is treated as a line, and each black pixel of the first modified image obtained by performing the process of thinning the line width of most of the first image to a line width smaller than the original line width and the second image For each black pixel of the second modified image obtained by performing the process of thinning most of the line width to a specified value or less, including the case where the line width remains unchanged, at least one of the modified images It is characterized in that the matching between the first image and the second image is judged by the matching process for checking the matching after the positioning for converting the pixel address of the black pixel to zero or more times.

[0017]

According to the present invention, the line width designation value of the thinning processing means applied to the first image (for example, the binary image of the registered image) is
Since the line width can be made smaller than the line width specification value of the thinning processing means applied to the second image (for example, the binary image of the inspection image), if the original object of the registered image and the inspection image are the same, each corresponding place In, the line width of the first modified image can be made smaller than the line width of the second modified image.

Therefore, the second image which is the information obtained by performing the thinning process (including the case where the image is the original image) on each black pixel of the first modified image which is the registration information of the first image is performed on the second image. Matching with the individual black pixels of the modified image has the following effects.

A complicated image correction process (for example, correction using the direction of a line) for extracting a feature point is unnecessary.

Since the line width of the first image can be set smaller than the line width of the second image, when the first image and the second image are images obtained from the same object, the influence of the positional deviation between the two images is affected. Few.

The number of black pixels of the image subjected to the thinning processing is
Since the total number of black pixels of the original image is smaller than that of the original image, the amount of memory required for the registration information is smaller than when the original image is used as the registration information as it is.

[0022]

EXAMPLE As an example, a case where an image is a fingerprint (which may be referred to as a fingerprint image) will be described. FIG. 1 is a configuration example of a fingerprint identification system according to an embodiment of the present invention. The fingerprint input from the image input device 2 is processed in the image matching device 1. The image matching apparatus 1 includes an image memory 4 for storing a digitized grayscale image of a fingerprint, a binary image, and an image subjected to various kinds of processing (thinning processing, etc.) when necessary, a processor (one or more processors). It has a processing unit 5 which is a CPU) and a memory 6 for storing information such as programs, data and files (collection of data). When storage devices having different characteristics (for example, a semiconductor memory and a magnetic disk) coexist in the memory 6, information transfer between them is performed by hardware or software as needed. Here, the image memory 4 and the memory 6 are divisions based on stored information, and can be realized by the same storage device.

The image input device 2 includes an image pickup device 7,
The / D converter 3 converts analog information from the image pickup device 7 into digital information. Here, when an image input device of a type that can directly obtain a digital image is used, the A / D
No converter is needed.

Further, the pixel address in the image memory 4 for storing the fingerprint image which is the grayscale image of the digitized fingerprint is represented as (X, Y) by the X coordinate and the Y coordinate. Pixel address (X, Y) is the pixel (X, Y), or simply
Sometimes expressed as (X, Y). The portion of the image memory 4 that stores one image is called a screen, and the image memory 4 can have one or more screens.

Each screen of the image memory 4 is composed of pixels, and the range of all pixel addresses is _0≤X≤Xh , 0.
If ≦ Y ≦ Y _h , the processing range further specified within this pixel address range is to be processed. If a number after the decimal point is generated in the pixel address or the number of pixels due to the calculation including the pixel address or the number of pixels, the process is performed by rounding down, rounding down or rounding up. Pixel values are represented by brightness. Which part of the luminance becomes the ridge depends on the processing method of the image input device 2 and the image processing in the image processing device 1. In any case, the characteristic of the luminance corresponding to the ridge is determined by the image matching device 1. It is possible to process by setting in advance.

Next, in fingerprint identification, a fingerprint input from the image input device 2 for registration in the memory 6 of the image matching device 1 is a registered fingerprint, and a fingerprint input from the image input device 2 for inspection is selected. Called inspection fingerprint. In the image binarized into black pixels and white pixels, either black pixels or white pixels can be selected as the fingerprint line (if either of them corresponds to a ridge line or a valley line, respectively). Good luck).

In this embodiment, black pixels are treated as fingerprint lines. The thinning is a process in which most of the line width is set to one pixel, but in the present embodiment, the line width of the black pixel set is included in the image of black pixels of the original binary image. Is called a thinning process, and an image obtained as a result of the thinning process is called a thinning image. Therefore,
Thinning is one form of thinning processing in this embodiment. In addition, line width, when the point of the edge of an arbitrary line is determined,
It is defined as the minimum distance (number of pixels) to reach another edge through the line (determined by the position of the edge of the line).

FIG. 2A shows the status of the image data stored in the image memory 4. The screen of the image 10 stores a digitized image (binary image or grayscale image) obtained from the image input from the image input device 2. image
For example, a past image is stored in the screen 11 and can be used for processing the image 10. Image by selecting the processing method
In some cases, 11 is unnecessary, in which case the image memory 4
Requires only image 10.

FIG. 2B shows the status of data and the like stored in the memory 6, and the program and data 12 include
The program and data for realizing the present embodiment are stored, and the registration information 13 stores the registration information of the registered fingerprint image in a file.

When the image is a grayscale image, a code value corresponding to the brightness is set. The binary image may be obtained by binarizing the grayscale image set in the image memory 4 or may be directly set in the image memory 4 depending on the image input method.

The binary image is represented by only black pixels and white pixels, but code values (for example, 1 for black pixels and 0 for white pixels) corresponding to the respective luminance values of the black and white pixels are determined. I will keep it. Whether the black pixel has a high brightness part or a low brightness part depends on the target image and the input method thereof, and may correspond to either case. The binary image may be stored in the image memory with a smaller memory amount than the grayscale image.

The logical origin and coordinate axes of the image stored in the image memory 4 can be determined independently of the physical pixel position of the image memory 4. The X and Y axes can be set freely, but for convenience of explanation, the X direction is from left to right (that is,
The X direction is the horizontal direction, and the Y direction is the vertical direction from top to bottom (that is, the Y increasing direction).

The notations and definitions are described below, but some of these notations may not appear in the following description.

[M]: represents truncation after the decimal point of an arbitrary number m. f (X, Y): The luminance at the pixel address (X, Y). FA: Fingerprint area. Since this fingerprint area can be expressed only by the fingerprint boundary, it is stored in the memory 6 as fingerprint boundary information. The fingerprint boundary is treated as within the fingerprint area. (X _C , Y _C ): Address of the approximate center point of the fingerprint. (X _RC , Y _RC ): The address of the approximate center point of the registered fingerprint. (X _TC , Y _TC ): Address of the approximate center point of the test fingerprint. R _th : Registered fingerprint change image (that is, first change) obtained by at least thinning the registered fingerprint binary image (first image) obtained from the registered fingerprint image (grayscale image or binary image) Image). T _th : An inspection fingerprint change image (at least obtained by subjecting a registered fingerprint binary image obtained from the inspection fingerprint image (grayscale image or binary image) to thinning processing (including the case of leaving it as it is) That is, the second modified image). RA: A set of addresses (X, Y) of all black pixels in the fingerprint area in the registered fingerprint change image R _th . RA
Is called a template. RT (0): X _RC −a ≦ X ≦, which is a small area in the center of RA
It is a set of addresses (X, Y) of black pixels in X _RC + a and Y _RC −b ≦ Y ≦ Y _RC + b. That is, RT (0)
Is a subset of RA, and this RT (0) is called a sub-template. RB (0): This is a set of addresses of black pixels in a portion of RA excluding RT (0). RB (0) is a subset of RA. RB (0) is called a non-subtemplate. RT (S): Sub-template R when the coordinate axis of the registered fingerprint change image is rotated S degrees about an arbitrarily determined point
It is a set of addresses (X, Y) of black pixels of T (0). RT (S, H, V): After the coordinate axis of the registered fingerprint change image is rotated S degrees about an arbitrary point (for example, the approximate center point of the registered fingerprint), horizontal movement H and vertical movement V are performed. Is a set of addresses of the sub-template RT (0) on the coordinate axis of. RT (0,0,0) = RT (0), RT (S, 0,0) =
It is RT (S). RB (S, H, V): After the coordinate axis of the registered fingerprint change image is rotated S degrees about an arbitrary point (for example, the approximate center point of the registered fingerprint), horizontal movement H and vertical movement V are performed. Is a set of addresses of the non-sub-template RB (0) on the coordinate axis of. RB (0,0,0) = RB (0), RB (S, 0,0)
= RB (S). N1 _m : The number of sub-template matching black pixels, which represents the number of matching black pixels between the sub-template black pixels of the registered fingerprint and the inspection fingerprint black pixel. N1 _c : The total number of black pixels of the sub-template, which represents the total number of black pixels of the sub-template of the registered fingerprint. N2 _m : The number of non-subtemplate matching black pixels, which represents the number of matching black pixels of the registered fingerprint non-subtemplate black pixels and the inspection fingerprint black pixels. N2 _c : The total number of black pixels of the non-sub-template, which represents the total number of black pixels of the non-sub-template of the registered fingerprint.

FIG. 3 shows an example of the relationship between the fingerprint area defined by the fingerprint boundary 14 in the image 10 in the image memory 4 and the part extracting the sub-template RT (0) and the part extracting the non-sub-template RB (0). Is represented.

The means for processing the fingerprint image will be described below. If there is no description of the next process in the steps of the procedure of each means, the process immediately follows. The constant used in each means is set to an appropriate value statically or dynamically in consideration of various conditions in the image matching device 1 and the image input device 2. The implementation of each step can be modified as long as the content of the process is the same.

(1) Smoothing processing means Smoothing is processing for reducing the influence of noise on the fingerprint image. A known method can be used for the smoothing process. For example, a local weighted average filter that uses the values of neighboring pixels of an arbitrary pixel can be used.

When the binary image can be directly input to the image memory 4, the smoothing is omitted.

(2) Binarization and Background Separation Processing Means Binarization is a process of converting a grayscale image into a binary image.
Background separation is a process of clarifying the effective range of the fingerprint image of the image 10 in the image memory 4. An example of a procedure for performing binarization and background separation is described in procedure B below. The input information of the procedure B is input image information. The output information of the procedure B is the binary image of the output image and the fingerprint boundary information. When using an image input device of the type capable of directly inputting a binary image to the image memory 4, the binarization (step B2) is omitted,
Performs only background separation.

(Procedure B) K is the length of the partial region in the X direction
It is a constant representing (= the length of the partial area in the Y direction).

[0041]

## EQU1 ## Let L = (X _h +1) / K. Here, K is selected so that L becomes an integer.
(Generally, the length of the partial area can be changed for each partial area).

[0042]

## EQU2 ## Let K _max = ((X _h +1) / K) -1. In the image 10, the partial area address for uniquely identifying the partial area is set as the leading pixel address of each partial area. An arbitrary pixel address (X, Y) is M = [X / Y] at the partial area address J (M, N), and N =
[Y / K]. Therefore, the partial area address J
The pixel address (X, Y) corresponding to (M, N) is

[0043]

## EQU00003 ## X = K.M, (M = 0,1,2, ..., _Kmax ) Y = K.N, (N = 0,1,2, ..., _Kmax ) ..

[0044] Step B1 (determination of the effective partial region): M = 0,1,2, ···, K max N = 0,1,2, ···, the K _max, the following process is performed. Each partial area address J
For each (M, N), the brightness average value B _av (M, N) of all pixels in each partial area is expressed as B _av (M, N) = (sum of brightness of pixels in partial area) / ( The number of pixels in the partial area). _BL and _BH are constants for distinguishing the effective partial area and the invalid partial area. For each partial area, when _BL ≤ B _av (M, N) ≤ B _H , it is determined that the partial area is an effective partial area, and the effective partial area table G (the element is G (M ，
N)) is set to a valid display (display value is 1), and when B _av (M, N) <B _L or B _av (M, N)> B _H , G (M, N) Sets invalid display (display value is 0). FIG. 4 shows an example of the effective partial area table G of the partial area of the fingerprint, where K = 16.

For the sake of convenience, the pixel (X, Y) in the invalid partial area is
All are set to the code value of white pixels.

The effective partial area and the invalid partial area may be divided not only by using the average value of the brightness of the partial areas but also by the distribution status of the brightness (variance value etc.).

[0047] Step B2 (binarization): M = 0,1,2, ···, K max N = 0,1,2, ···, the K _max, the following process is performed. About the effective partial area,
The brightness f of the pixel (X, Y) in the partial area for which B _av (M, N) is obtained
For (X, Y), the threshold value T _B for binarization is

[0048]

[Formula 4] T _B = B _av (M, N) + D _B (where D _B is an integer for adjusting the threshold value for binarization)
(Constant of positive, negative, or zero)), for the pixel (X, Y) at the partial area address J (M, N) at this time, if the one with lower luminance is a black pixel, K · M ≦ X ≦ K · (M + 1) -1 K · N ≦ Y ≦ K · (N + 1) -1 range of (X, Y) for, f (X, Y) when ≧ T _B, the pixel (X, Y) of sets a code value of the white pixels in luminance, when f (X, Y) <T B, still sets a code value of black pixels to the luminance of the pixel (X, Y), and black pixels the higher luminance If so, in this step, the white pixel and the black pixel are set in the opposite manner to the above.

Step B3 (inspection of the number of effective partial areas): The number of effective partial areas G _E is counted by the effective partial area table G, and if G _E ≧ G _C , go to step B4 (G _C is If G _E <G _C , a constant for determining that there are sufficient valid partial areas), this procedure ends abnormally due to insufficient number of valid partial areas.

Step B4 (left end of fingerprint boundary in units of partial area): The partial area fingerprint boundary information is set to {(N _T , M _L , M _R ),
N _T = 0 to K _max }, and for each N = N _T value, M _L
≦ M ≦ M _R is the fingerprint area of each partial area.

Here, the left end M _{L of the} fingerprint boundary is obtained for each partial area. Starting from N = 0, N = N _T , (N _T =
The following processing is performed for 0 to K _max ). In the increasing direction of M from the left end (M = 0), 1 (effective partial area display) of the element G (M, N) of the effective partial area table G is sequentially searched,
1 is K _C or more (K _C is a constant of 1 or more for determining the fingerprint boundary 14 of the partial area) The first M value M _L of the continuous part is the left end of the fingerprint area for N at that time. And
When 1 (effective area display) is not continuously found by K _C or more at M = 0 to K _max , the value of N is a non-fingerprint area for all M, and N _{T of the} non-fingerprint area is _Let M _L = M _R = −1.

Step B5 (right edge of fingerprint boundary for each partial area): Here, the right edge M of the fingerprint boundary is set for each partial area.
_{Find R.} Starting from N = 0, N = N _T , (N _T = 0 to
K _max ), N for which the left end is not set in step B4 (that is, N when _ML = -1) is skipped, and the effective part is sequentially increased from the right end (M = K _max ) in the decreasing direction. Search for 1 (effective partial area display) of the element G (M, N) of the area table G, and find the value M _R of the first M of a continuous section where 1 is K _C or more (K _C is a constant) at that time. Let N be the right edge of the fingerprint finger area. From the above, partial area fingerprint boundary information {(N _T , M _L , M _R ), N _T = 0 to K _max } is obtained.

Step B6 (fingerprint boundary information for each pixel): partial area fingerprint boundary information {(N _T , M _L , M _R ), N _T =
The fingerprint boundary information for each pixel is obtained from 0 to K _max }.
The fingerprint boundary information for each pixel is represented by {(Y _T , _XL , X _R ), Y _T = 0.
Expressed in to Y _h -1)}, which, for each value of Y _T, X _L
≦ X ≦ X _R means the fingerprint area.

Depending on the partial area fingerprint boundary information, N = 0 to K
_{At max} , for Y = Y _T of K · N ≦ Y ≦ K · N + K _max ,

[0055]

Equation 5] as _{X L = K · M L X} R = K · M R + K max, fingerprint boundary information of each pixel {(Y _T, X _L,
X _R ), Y _T = 0 to Y _h -1)}.
(End of procedure B).

Note that, hereinafter, when simply referred to as fingerprint boundary information, the fingerprint boundary information for each pixel {(Y _T , _XL , X _R ),
Y _T = 0 to Y _h -1)}.

(3) Image Correction Processing Means The degree of image correction needs to be determined depending on the image quality, and may be omitted or enhanced as necessary. The purpose of the image correction in this embodiment is to allow the thinning processing to be sufficiently executed. Here, for the image 10, the removal of the isolated black pixel set is performed by the pixel pattern around each pixel in the fingerprint area of the binary image.
An example of a procedure for performing simple image correction such as (changing to white pixels) or filling in a set of isolated white pixels (changing to black pixels) is shown in the following procedure T.

This procedure T shows the case where each processing is applied to a set of 5 × 5 pixels, and in general, n × n
Similar processing can be performed on a pixel set of (n = 2k + 1, k = 1, 2, ...). The size of the pixel set for image correction needs to be appropriately determined according to the number of pixels in the image memory 4, the image quality, and the like. An example of the positions of the individual names P _{0 to} P ₂₄ of the 5 × 5 pixel group centered on an arbitrary pixel P ₀ and the change of the black pixel and the white pixel when the procedure T is applied is shown in FIG. ) And FIG. 5 (b). The input information of the procedure T is input pixel information and fingerprint boundary information. The output information is output image information.

(Procedure T) The pixel of interest in the fingerprint area (including the boundary) in the image 10 is set to P ₀ = (X, Y),

[0060]

## EQU6 ## The processing of steps T1 to T4 is repeated for X = 2, 3, ..., X _h -2 Y = 2, 3, ..., Y _h -2. Note that the pixels outside the fingerprint area are set to white pixels by binarization, so that the pixels of the 5 × 5 pixel set are all white pixels or black pixels, and P ₀ after selecting P ₀ in the fingerprint area At the time of processing a set of 5 × 5 pixels, it is not necessary to be aware of the fingerprint area.

Step T1 (selection of P ₀ ): Pixel P ₀ =
Whether or not (X ₀ , Y ₀ ) is within the fingerprint boundary is checked by the fingerprint boundary information (Y _T , _XL , X _R ). That is, Y ₀ = Y _T
For X _L and X _R of Y _T , if P _L ≦ X ₀ ≦ X _R , then P ₀ is within the fingerprint boundary, and otherwise P ₀ is outside the fingerprint boundary. Then, when P ₀ is within the fingerprint boundary, go to step T2.

When P ₀ is outside the fingerprint boundary, the process goes to the next P ₀ and the processes are performed from step T 1.

Step T2 (Removal of Isolated Black Pixel Set): Here, an isolated black pixel set is removed.

When P _{9 to} P ₂₄ are all white pixels, the pixels P _{0 to} P ₈ are all white pixels, and step T3
Go to If not, go to.

When P _{1 to} P ₈ are all white pixels, P
_{Set 0} to a white pixel and go to step T3. If not, go to step T3 without doing anything.

Step T3 (Removal of Isolated White Pixel Set): Here, the process of filling the isolated white pixel set (so-called hole) is performed.

When P _{9 to} P ₂₄ are all black pixels, all the pixels of P _{0 to} P ₈ are black pixels, and step T4
Go to If not, go to.

When P _{1 to} P ₈ are all black pixels, P
_{Set 0} to a black pixel and go to step T4. If not, go to step T4 without doing anything.

Step T4 : This procedure is ended.
(End of procedure T).

At step T2 and step T3 in the procedure T, when the pixel to be updated has the value to be updated, it is not necessary to update, but in order to avoid the value confirmation processing, the update is performed. You may.

(4) Processing means for obtaining approximate center point The procedure for obtaining the approximate center point (X _C , Y _C ) of the fingerprint area from the binary image of the fingerprint in the image 10 is shown in the following procedure Q. Show. The input information of the procedure Q is input image information and fingerprint boundary information. The output information of the procedure Q is the approximate center point (X _C ,
Y _C ). FIG. 6 shows an example of the relationship between each constant, the fingerprint area, and the approximate center point.

(Procedure Q) Step Q1 (Process for Obtaining Y _C ): V _L ≦ X ≦ V
_For the range of _R , the horizontal line Y = KA _i , (i = 1,2, ..., n;
H _D ≤ Y ≤ H _U ) and the number of intersections K of the black pixel lines which are fingerprint lines
Find H _i , (i = 1, 2, ..., N). Here, the partial width of the black pixel in each intersecting portion is set to a certain value (for example, one pixel) or more. _{H D, H U, V L} , V R _{is, V L ≦ X ≦ V R} , and H _D ≦
The section of Y ≦ H _U is a constant selected so as to be within the fingerprint area and within a settable range of the approximate center point. KA _i , (i = 1, 2, ..., N) is a constant that determines the scanning position.

Next, the number of intersecting lines K with respect to the horizontal line Y = KA _i
For H _i , (i = 1, 2, ..., N), i = i _m that maximizes KH _i , (i = 1, 2, ..., N) is obtained. Generally i _m is (the T _y pieces) are one or more. Y which is the Y coordinate of the approximate center point
_c

[0074]

[Equation 7]

[0075]

[Outer 1]

Step Q2 (Process for obtaining X _C ): Vertical line X = K in the range of H _D ≦ Y ≦ H _U
B _i , (i = 1,2, ..., n; V _L ≦ X ≦ V _R ) and the number of intersections KV _i of the black pixel line, which is a fingerprint line, (i = 1,2, ...・, N) is calculated. Here, the line segment width of the black pixel in the intersecting portion is set to a certain value (for example, one pixel) or more. KB _i , (i = 1, 2, ..., N) is a constant.

Next, the number of intersecting lines K with respect to the vertical line X = KB _i
For V _i , (i = 1,2, ..., N), i = i _s that maximizes KV _i , (i = 1, 2, ..., N) is obtained. Generally, there is one or more i _s (T _x ). X which is the X coordinate of the approximate center point
_c

[0078]

[Equation 8]

[0079]

[Outside 2]

Step Q3 : Let (X _C , Y _C ) be the approximate center point of the fingerprint area. (End of procedure Q).

As an alternative to the procedure Q, the image 10
The center ([X _h / 2], [Y _h / 2]) of
There is a means to regard it as (X _C , Y _C ).

(5) Thinning processing means A set of one or more black pixels is treated as an image line. The method of holding the line width designation value is arbitrary, and it is possible to use it as the input information of the thinning processing means or to hold it in the thinning processing means. One or more line width designation values may be held in one thinning process. In the present embodiment, the thinning processing means can be selectively used according to the line width designation value. However,
The image matching device 1 includes only the thinning processing means for the line width designation value applied to the first image and the thinning processing means applied to the second image.
Be prepared. An example of the thinning processing means depending on the specified line width value is shown below.

Thinning processing for setting most line widths to 1 pixel (line width specified value is 1 pixel) Means for thinning the line width of a binary image (or means for binarizing a grayscale image and narrowing the line width) It is possible to use a known method (for example, a thinning method capable of making most of the line width one pixel). There is also a method of directly binarizing and thinning a grayscale image.

It is self-evident that the thinning process in which the line width is not changed (the line width designation value is used to designate the display with no change designation) is the case where the original binary image is not processed (as it is). is there.

A thinning process for thinning most of the lines to the line width specified value or less (the line width specified value is an arbitrary value) can be realized based on a known method. For example, the following means.

(A) Most of the line width is obtained by performing the processing for one screen in which the elements of the line are erased pixel by pixel from the outside of the line (corresponding to the black pixel which is the fingerprint line in the present embodiment) forming the image. In the case of a thinning method that repeats until one pixel is reached,

[0087]

[Equation 9]

The number of repetitions may be set so that

(B) In the case of a thinning method in which a black pixel is left from the center of an element of a line forming an image, an arbitrary straight line is set to the center of the black pixel on the line segment where the lines of the image intersect. Pixels less than or equal to the specified line width are left (if the line segment width is greater than or equal to the line width specified value, the black pixels for the line width specified value are left around the midpoint of the line segment and the line segment width is specified This can be achieved by leaving all black pixels on the line segment below An example of a specific procedure is shown in the following procedure F.

As one straight line L _x and its parallel line, X
When the Y axis and its parallel line are used as the parallel lines of the straight lines L _y and L _{y obtained} by rotating the straight line L _x by a constant angle of 0 ° or more using the axis and its parallel line (that is, the rotation angle is 90 degrees).
The following examples will be given. Note that, here, the parallel lines are limited to those that pass on each coordinate. The input information in the following procedure F is input image information. The output information is an output image.

(Procedure F) Step F1 (thinning process in the X direction): Here, the black pixels on the X axis and the parallel lines thereof are redone into black pixels and white pixels. For image 10, Y = Y ₀ , (Y ₀ = 0,1,2, ..., Y _h ).
And the continuous range of black pixels at that time is X _Li ≦ X ≦
Let X _{Hi be} (i = 1,2, ...). Next, with respect to all X directions, a black pixel continuous portion having a line width specified value w _x or more (that is,
The coordinates (X, Y) for i satisfying X _Hi −X _Li + 1 ≧ w _x
0 ) which is a segment of X _Li ≤X ≤X _Hi ),
When the length (number of pixels) of the line segment is w _x or more, w _x black pixels are left around the midpoint of the line segment, and black pixels on the line segment whose line segment length is less than w _x are Leave all.

The above result is set in the image 10. The process of this step is executed for all Y ₀ by increasing Y ₀ by 1.

Step F2 (thinning process in Y direction): Here, the black pixels on the Y axis and the parallel lines thereof are redone into black pixels and white pixels. For image 10, X = X ₀ , (X ₀ = 0,
1,2, ..., X _h ), and the continuous range of black pixels at that time is Y
_Li ≦ Y ≦ Y _Hi , (i = 1,2, ...). Then all Y
Consecutive black pixels with line width specified value w _y or more in the direction
(I.e., Y _Hi -Y _Li + 1 is ≧ w satisfying _y coordinates for _{i (X 0, Y),} Y Li ≦ Y ≦ Y Hi, line section of)
, If the length of the line segment is greater than or equal to w _y , then w _y black pixels are left around the midpoint of the line segment, and all black pixels on the line segment whose length is less than w _y are left. ..

The above result is set in the image 10. The processing of this step is performed for all X ₀ by increasing X ₀ by 1. (End of procedure F).

In the present embodiment, the line width designation value when performing the thinning process on the registered fingerprint image and the inspection fingerprint image can be arbitrarily designated, but the quality and characteristics of the line of the input image and the line width of the thinning process It is necessary to determine it from the performance with respect to the designated value, the performance required for the image matching device 1, and the like.

If the difference between the line width designation values in the respective thinning processing of the registered fingerprint image and the inspection fingerprint image is increased, the positional deviation between the two images becomes stronger, but if the difference is too large,
The collation accuracy may be deteriorated. The smaller the line width of the registered fingerprint change image is, the smaller the number of black pixels is, so that the memory amount required for the registration information can be reduced. Considering these matters, for example, one of the following specifications may be valid.

In the thinning process of the registered fingerprint image, the designated line width value is set to 1 pixel, and in the thinning process of the inspection fingerprint image, the designated line width value is unchanged.

In the thinning process of the registered fingerprint image, the designated line width value is set to 1 pixel, and in the thinning process of the inspection fingerprint image, the designated line width value is set to an appropriate value of 2 pixels or more.

The line width designation value for the thinning process of the registered fingerprint image is appropriately selected under the condition that it is smaller than the line width designation value for the thinning process of the inspection fingerprint image.

The procedure F is effective when the line width designation value can be made relatively large because it is difficult to maintain the connectivity of the black pixels when the line width designation value is small. Further, the extension of applying the procedure F to the grayscale image can be easily realized. That is, for the brightness of each pixel, a range of brightness considered as a black pixel and a range considered as a white pixel is set dynamically or statically, and the same process as in step F is performed.

(6) Registration processing means for registration information of registered image In the registration processing of fingerprint information, an image 10 which is the result of the processing up to the narrowing processing is input to the image 10 of the image memory 4 as a registered fingerprint. A sub template RT (0) is created from a certain registered fingerprint change image R _th, and the sub template RT (0) is created.
This is the process of storing in the file (0). The procedure for registering fingerprint information is shown in procedure R below. The input information of the procedure R is the file name of the registered fingerprint, the registered fingerprint change image R _th , the fingerprint boundary information of the registered fingerprint, and the approximate center point (X _RC , Y _RC ) of the registered fingerprint. The output information of the procedure R is the file of the sub template RT (0) and the file of the non-sub template RB (0).

[0102] (Formation of sub-template RT (0)) (Step R) Step R1: from modified image of the registered fingerprint R _th, located in the fingerprint region FA, and the modified image of the registered fingerprint R _th center small region (X _RC −a ≦ X ≦
The range of X _RC + a and Y _RC −b ≦ Y ≦ Y _RC + b. a, b
Is a constant. The black pixel address in () is extracted, a sub-template RT (0) is created, and a file of this RT (0) is created. Further, the registered file approximate center point (X _RC , Y _RC ) is also stored in this RT (0) storage file.

Step R2 (Non-sub-template RB
(0) Creation): Black pixel addresses outside the sub-teleplate RT (0) and within the fingerprint area FA are extracted from the registered fingerprint change image R _th to create a non-sub-template RB (0), Create a file for this RB (0).
(End of procedure R).

The storage format of the data of each file of the sub-template and the non-sub-template is arbitrary.
For example, the data may be compressed and stored, and the data may be expanded at the time of use.

(7) Collation processing means of registered image and inspection image The collation processing is a result obtained by inputting the inspection fingerprint into the image 10 of the image memory 4 and performing the processing up to the narrowing processing (including the case of no change). Is a process of checking the consistency between each black pixel of the black pixel set of the inspection fingerprint changed image and each black pixel of the black pixel set stored in the memory 6 as the registration information regarding the registered fingerprint.

The coordinate conversion by rotating and translating the coordinate axes for aligning the registered fingerprint and the inspection fingerprint may be performed on either one of the images, but in this embodiment, the registered fingerprint is more However, the registered fingerprint is moved to match the inspection fingerprint on the assumption that the number of black pixels is reduced because the line width designation value of the thinning process is small.

The outline of the matching process will be described below.

Sub Template Matching (Primary Matching) The sub template matching is performed at the position where the black pixel of the registered fingerprint changed image and the black pixel of the inspection fingerprint changed image are the best match in the registered fingerprint sub template RT (0). Is a process for obtaining. That is, first, the registered fingerprint change image R _th
For the sub-template RT (0) of, the sub-template RT (0, H, V) when the approximate center of the registered fingerprint is matched with the approximate center of the inspection fingerprint is obtained by parallel movement of the coordinate axes of the registered fingerprint.

Next, in the vicinity of the center, the sub template RT
When the coordinate axes of (0, H, V) are rotated and translated in the vertical and horizontal directions, the registered fingerprint sub-template RT (S, S,
The conversion angle S of (H, V) and the parallel movement amount (horizontal movement amount H, vertical movement amount V) are obtained (S, H, V are integers).

Non-sub-template verification (secondary verification) Non-sub-template verification is performed by using the registered fingerprint's RT (S, H, V) S, H, V obtained by the sub-template verification. Coordinate conversion of the black pixel address of the non-sub-template RB (0) is performed to obtain the black pixel address, and the match with the black pixel address of the inspection fingerprint change image is checked to obtain information on the match between the registered fingerprint and the inspection fingerprint. This is the process of outputting.

That is, first, by using the angular rotation amount S, the horizontal movement amount H, and the vertical movement amount V of the coordinate axis of the sub-template of the registered fingerprint obtained by the sub-template matching, the non-sub-template RB (0 ), The coordinate conversion of the black pixel is performed to obtain RB (S, H, V). Next, the match between the black pixel of RB (S, H, V) of the registered fingerprint change image and the black pixel of the inspection fingerprint change image is checked.

Based on the outline of the collation processing described above, the procedure for performing the collation processing is shown in the following procedure C. The input information of this procedure C is the file name of the registered fingerprint, the inspection fingerprint change image, and the approximate center point (X _TC , Y _TC ) of the inspection fingerprint. The output information of procedure C is collation information.

(Procedure C) Step C1 (Verification of Sub Template): Sub template RT (0), S = S _min stored in the memory 6.
To S _max, (incremental value K _s of _{S), H = H min ~H} max,
An image consistency check auxiliary procedure (procedure W) described below is executed using (H increment step width K _h ), V = V _{min to} V _max , and (V increment step width K _v ). As a result, the optimum values of S, H, and V at which the sub-sample rate matching rate T1 is maximum and T1 at this time are

[0114]

[Equation 10]

(N1 _m , N1 _c is calculated by the procedure T
See). Next, regarding the constant TK1, if T1 ≧ TK1, it is determined that the registered fingerprint and the inspection fingerprint match, and the process proceeds to step C2. If T1 <TK1, it is determined that the registered fingerprint and the inspection fingerprint do not match, and the procedure C To finish.

Step C2 (collation of non-sub-template): Non-sub-template RB (0) in the memory 6 and the optimum S, H, V obtained in step C1 as input information, the image consistency check auxiliary procedure ( Perform step W). As a result, as the non-subtemplate matching rate T2,

[0117]

[Equation 11]

Is obtained (for the calculation method of N2 _m and N2 _c , see the procedure W described later). Next, regarding the constant TK2, if T2 ≧ TK2, it is determined that the registered fingerprint and the inspection fingerprint match, and the process proceeds to step C3. If T2 <TK2, it is determined that the registered fingerprint and the inspection fingerprint do not match, and the procedure C To finish. (End of procedure C).

An example of items of collation information (progress and result) which is output information of the procedure C is shown below.

Sub Template Matching (Primary Matching) Coordinate axis optimum rotation angle S of registered fingerprint, coordinate axis optimum horizontal movement amount H of registered fingerprint, coordinate axis optimum vertical movement amount V of registered fingerprint,
Number of sub-template matching black pixels N1 _m , total number of sub-template black pixels N1 _c , sub-template matching rate T1 =
N1 _m / N1 _c , and the primary matching result (match or mismatch).

Non-sub-template matching (secondary matching) Non-sub-template matching black pixel count N2 _m , non-sub-template total black pixel count N2 _c , non-sub-template matching rate T
2 = N2 _m / N2 _c , and the secondary matching result (match or mismatch).

(8) Image Consistency Check Auxiliary Procedure The processing outline of the image consistency check auxiliary procedure (procedure W) is as follows. For each pixel address (X _R , Y _R ) of the sub-template RT (0) or non-sub-template RB (0) for the registered fingerprint, the approximate center point (X _RC , Y _R ) of the registered fingerprint (X _R , Y _R ). _(RC ) is moved in parallel so as to match the approximate center point (X _TC , Y _TC ) of the inspection fingerprint (X _T , Y _T ), and the coordinate axis of the registered fingerprint is further rotated to convert the black pixel address (X _R
@, Y _R @) is a black pixel in the fingerprint area of the inspection fingerprint change image, and if RT (S, H, V), S, H,
S, H, V and T1, N1 _m , N1 _c when the matching rate T1 = N1 _m / N1 _c at each value of V becomes maximum are obtained. Here, N1 _m is the number of matching black pixels of the sub template, and N1 _c is the total number of black pixels of the sub template.

For RB (S, H, V), S, H, V
, Respectively, and the value at that time gives the maximum T2 (N2 _m is the number of matching black pixels in the non-subtemplate, and N2 _c is the total number of black pixels in the non-subtemplate). In addition, T1, T2, N1 _m , N2 _m , N1 _c , N
In the present procedure, 2 _c is called T, N _m , and N _c because it is common to the coincidence collation and the secondary collation.

The input information of the procedure W is the set of black pixel addresses of the designated portion (either RT (0) or RB (0)) of the registered fingerprint change image, the angle conversion amount S of the coordinate axis (storage format: minimum value). S _min , maximum value S _max , increased step size K _s ), horizontal movement amount H of coordinate axis of registered fingerprint (storage format: minimum value H _min , maximum value H _max , increased step size K _h ), coordinate axis of registered fingerprint A vertical movement amount V (storage format: minimum value V _min , maximum value V _max , increment step width K _v ) and inspection fingerprint change image. The output information of the procedure W is any of the optimum coordinate axis rotation angle S of the registered fingerprint, the optimum coordinate axis horizontal movement amount H of the registered fingerprint, the optimum coordinate axis vertical movement amount V of the registered fingerprint, and the designated area (RT (0) or PB (0)). One side)
Of the registered fingerprint changed image and the inspection fingerprint changed image, N _m , the total number of black pixels N _c of the registered fingerprint changed image of the designated area, and the matching rate T. The processing procedure of procedure W is shown below. Figure 7
A schematic flow chart of the procedure W is shown in FIG.

(Procedure W) Step W1 (Selection of Angle S): Incremental step width K from S = S _{min to} S _{max in the} order in which the angle S is set in the storage area.
_s (that is, S = S _min , S _min + K _s , S _min + 2K _s ,
..., change to maximum S _max ), and when S = 0 is selected, go to step W4 and S ≠
If 0 is selected, go to step W2.

Step W2 (coordinate conversion by angle S):
The approximate center of the registered fingerprint with respect to all the black pixel addresses (X _R , Y _R ) for the black pixel set (either RT (0) or RB (0)) of the input registered fingerprint modified image point
After (X _RC , Y _RC ) is moved in parallel to the approximate center point (X _TC , Y _TC ) of the inspection fingerprint, the coordinate axis is rotated about the angle (X _TC , Y _TC ) by the angle S. This is

[0127]

[Expression 12] X _R @ = (X _R −X _RC ) · cos (S) + (Y _R −Y _RC ) · sin (S) + X _TC Y _R @ = − (X _R −X _RC ) · sin ( This can be done by S) + (Y _R −Y _RC ) · con (S) + Y _TC (see Procedure W). Thus, when H = V = 0, all black pixel addresses (X _R @,
Seek a set of Y _R @).

Step W3 (calculation of matching rate T): Step W3a : Matching black pixel number N _m and total black pixel number N
Initialize each _c to 0.

Step W3b : For each black pixel address of the set (X _R @, Y _R @), check the inspection fingerprint change image,
If it is a black pixel in the inspection fingerprint area, 1 is added to the matching black pixel number N _m, and 1 is also added to the total black pixel number N _c .

In other cases (that is, white pixels within the inspection fingerprint area or outside the fingerprint area (treated as neither black pixels nor white pixels)), 1 is added to the total number of black pixels N _c .

Step W3c : For all addresses in the set of (X _R @, Y _R @), when step W3b is completed, T = N _m / N _c is calculated. Then, for (S, H, V) at this time, N _m , N _c , and T are output to the collation work area.

Step W4 (translation by H and V):
Newly registered fingerprint black pixel address set (X = H = 0)
(@, Y @), sequentially select H and V set in the H and V storage areas (here, when H = V = 0, calculation is already performed in step W3, so calculation is unnecessary. ).

When H = H _{min to} H _max and V = V _{min to} V _max are successively changed with each increment (the increment increment of H is K _h , and the increment increment of V is K _v ). That is, H is H =
Maximum H due to H _min , H _min + K _h , H _min +2 K _h , ...
Change to _max . V is V = V _min , V _min + K _v , V
_The maximum V _{max is} changed by _min + 2K _v , .... ), For each (S, H, V), (X @ -H, Y @
-V) is a set of newly registered fingerprint black pixel addresses after translation, so for each combination of (S, H, V),
The same processing as step W3 is performed and the matching rate is output to the collation work area.

Step W5 (check unprocessed S):
If there is an unprocessed S value, go to step W1. When there is no unprocessed S value, the process goes to step W6.

Step W6 (determination of maximum matching rate): S
For each value (S, H, V) due to changes in H = H _{min to} H _max and V = V _{min to} V _max , S, H when T = N _m / N _c is maximum, V, and T, N _m , and N _c are obtained and used as output information. When only one S, H, and V is input, the matching rate at that time is output information.
(End of procedure W).

The information stored in the collation work area in the procedure W is
Each value is set for each (S, H, V), and the items include the coordinate fingerprint rotation angle S of the registered fingerprint, the coordinate axis horizontal movement amount H of the registered fingerprint, the coordinate axis vertical movement amount V of the registered fingerprint, and the sub template.
(Or non-sub-template) number of matching black pixels N _m , total number of sub-template (or non-sub-template) black pixels N _c , and matching rate T = N _m / N _c .

Procedure W: The expression of step W2 has the following meaning. In step W2, the address (X _R , Y _R )
For all of, the approximate center point of the enrolled fingerprint (X _RC , Y
The new address after parallel translation that makes ( _RC ) match the approximate center point (X _TC , Y _TC ) of the inspection fingerprint is

[0138]

X _R # = X _R − (X _RC −X _TC ) Y _R # = Y _R − (Y _RC −Y _TC ) and (X _R #, Y _R #) is the new address. next,
Rotate the coordinate axis at an angle S centered at (X _TC , Y _TC ).
This is

[0139]

[Formula 14] X _R @ = (X _R # -X _TC ) ・ cos (S) + (Y _R # -Y _TC ) ・ sin (S) + X _TC = (X _R −X _RC ) ・ cos (S) + (Y _R -Y _RC ) ・ sin (S) + X _TC Y _R @ =-(X _R # -X _TC ) ・ sin (S) + (Y _R # -Y _TC ) ・ con (S) + Y _TC = It can be _calculated by − (X _R −X _RC ) · sin (S) + (Y _R −Y _RC ) · con (S) + Y _TC . Where the trigonometric function sin
As the values of (•) and cos (•), values in the range of fluctuation of the angle S may be held in advance.

(9) Flow of registration process and collation process FIG. 8 shows an outline flow of the fingerprint registration process and collation process.
The registration process is a process of registering the registration information of the fingerprint in the memory 6 of the image matching device 1. The matching process is a process of determining the match between the inspection fingerprint and the registered fingerprint. An outline of the flow from fingerprint input to registration or verification is shown in Procedure Z below.

(Procedure Z) Step ZA1 to step ZA
5 is a process common to the registration process and the collation process. Step ZA1 : Input a fingerprint from the image input device 2 into the image memory 4. Step ZA2 : The grayscale image of the fingerprint in the image 10 of the image memory 4 is smoothed. Step ZA3 : The image 10 is binarized and the background is separated according to the procedure B. Step ZA4 : The image 10 is corrected by the procedure T. Step ZA5 : The approximate center point of the fingerprint image in the image 10 is obtained by the procedure Q. (Step ZA1 to Step Z
A5 end).

Subsequent processing is divided into registration processing and collation processing. Steps ZR1 and ZR2 are the case of the registration process, and the registration information of the registered fingerprint is registered in the memory 6.

Step ZR1 : The registered fingerprint binary image (first image) in the image 10 is thinned within the fingerprint area to obtain a registered fingerprint changed image (first changed image). Step ZR2 : The registration information of the registered fingerprint is processed (procedure R). (End of step ZR1 to step ZR2).

Steps ZC1 and ZC2 are the case of the collation processing, in which the inspection fingerprint of the registered fingerprint is collated. Step ZC1 : Binary image of the inspection fingerprint in image 10 (second
Thinning process in the fingerprint area of (image) (may not be converted)
And an inspection fingerprint change image (second change image) is obtained. Step ZC2 : The matching process (procedure C, procedure W) determines the coincidence between the registered fingerprint and the inspection fingerprint. (Step ZC
1 to the end of step ZC2).

The present invention is not limited to the above-described embodiments, but can be applied to the following expansions or modifications within the scope of the claims. .. For the image input method, smoothing processing, binarization processing, background separation processing, correction processing, processing for obtaining an approximate center point, thinning processing, and the matching rate calculation formula in matching processing, etc. Modifications, extensions, or partial omissions using methods (eg, known methods) are possible.

Further, when the positional deviation is so small as to be negligible, the positional alignment may be determined by the positional deviation of only a possible parallel movement, and may be judged by the matching rate when the matching rate is the best. In step W2 of procedure W, X _R
The equations for obtaining @ and Y _R @ can be used as long as they are transformations that can rotate and translate, and are not limited to the present embodiment. For example,

[0147]

X _R @ = X _R · cos (S) + Y _R · sin (S) Y _R @ = − X _R · sin (S) + Y _R · con (S) can also be used.

Also, the usage of coordinate transformation or geometric transformation is free. By adding the value obtained by rotating or translating the sub template as registration information, the processing amount for collation can be reduced (in this case, the memory amount increases).

In the present embodiment, the case where the image is a fingerprint has been described, but the present invention can be applied to an image other than the fingerprint when the image can be regarded as being composed of lines. In the embodiment, the collation of one inspection fingerprint and one registered fingerprint is described, but when searching for the best matching registered fingerprint from two or more registered fingerprints for one inspection fingerprint,
It can be applied by repeating the collation of this embodiment. The sub-template and the non-sub-template can be freely divided, and there is an extension such as not dividing them or providing more divisions.

[0150]

As described above, in the image collating method and apparatus of the present invention, the line width designation value of the thinning processing means applied to the first image is the line width of the thinning processing means applied to the second image. Since it can be smaller than the specified value, when the original objects of the registered image and the inspection image are the same, the line width of the first changed image is made smaller than the line width of the second changed image at each corresponding location. be able to.

Therefore, if the individual black pixels of the first modified image, which are the registration information of the first image, are compared with the individual black pixels of the second modified image, which is the information based on the second image, the following effects are obtained. is there.

A complicated image correction process (for example, correction using the direction of a line) for extracting a feature point is unnecessary.

Since the line width of the first image can be set smaller than the line width of the second image, when the first image and the second image are images acquired from the same object, the influence of the positional shift between the two images is affected. Less is.

The number of black pixels of the image subjected to the thinning processing is
Since the total number of black pixels of the original image is smaller than that of the original image, the amount of memory required for the registration information is smaller than when the original image is used as the registration information as it is.

[Brief description of drawings]

FIG. 1 is a diagram showing a configuration example of a fingerprint identification system according to an embodiment of the present invention.

2 is an illustration of the image memory of FIG. 1 and the use of the memory.

FIG. 3 is an explanatory diagram of a fingerprint area.

FIG. 4 is an example of an effective partial area table of a fingerprint.

FIG. 5 is a diagram illustrating an example of simple image correction.

FIG. 6 is an explanatory diagram of an example of means for obtaining an approximate center point of a fingerprint image.

FIG. 7 is a schematic flowchart of an image consistency check assisting procedure (procedure W).

FIG. 8 is an example of a schematic flowchart of fingerprint registration processing and collation processing.

[Explanation of symbols]

1 ... Image collation device, 2 ... Image input device, 3 ... A / D
Converter, 4 ... Image memory, 5 ... Processing device, 6 ... Memory, 7 ... Imaging device, 10, 11 ... Image, 12 ... Program and data, 13 ... Fingerprint registration information, 14 ... Fingerprint boundary.

Claims (5)

[Claims] 1. Two images of a binary image having black pixels and white pixels as constituent elements of image pixels are defined as a first image and a second image, and a set of one or more black pixels is treated as a line. , Individual black pixels of the first modified image obtained by performing a process of reducing the line width of most of the first image to a line width smaller than the original line width,
The second obtained by performing the process of thinning most of the line width to a specified value or less, including the case where the line width of the second image remains unchanged.
With respect to each black pixel of the modified image, a matching process for checking the consistency after the alignment for converting the pixel address of at least one of the individual black pixels of the modified image to zero times or more is performed. An image collation method characterized by determining coincidence. 2. A specified line including a case where the line width of most of the first image is narrowed to 1 pixel to create a first modified image and the line width of most of the second image is left unchanged. The image matching method according to claim 1, wherein the second modified image is created by narrowing the width to a width or less. 3. Two images of a binary image having black pixels and white pixels as constituent elements of image pixels are defined as a first image and a second image, and a set of one or more black pixels is treated as a line. , Including one or more thinning processing means for thinning the line width to a line width specified value or less for most of the lines including the case where the line width of the binary image is left unchanged by the designation, and The line widths of the second image and the individual black pixels of the first modified image obtained by processing the line width of the image with the line width designation value smaller than the original line width by the line narrowing processing unit are reduced. With respect to each black pixel of the second modified image obtained by processing by setting the line width designation value including the case of leaving the original as it is by the processing means, at least one pixel address of each black pixel of the modified image Matching processing means for checking the consistency after registration for converting the number of times to zero or more Comprising, by collating processing unit, an image collating apparatus characterized by determining a coincidence of the first and second images. 4. The line width specified value of the thinning processing means applied to the first image is one pixel, and the line width specified value of the thinning processing means applied to the second image is the line width of the second image. 4. The image matching apparatus according to claim 3, wherein the value is one of arbitrary line widths including the case of keeping the original size. 5. For an image having two or more luminance values, the line width designation value of the thinning processing means is set to w _x, and each line on the one straight line L _x and its parallel line intersects the line of the image. of the black pixel set on the line segment, the other black pixels, leaving w _x number of black pixels of the line segment if the number of pixels of the line segment is w _x more than the white pixel, the line segment All the pixels in the black pixel continuous portion where the number of pixels is less than w _x are left as black pixels as they are, and the line width designation value of the thinning processing means is set to w _y , and the straight line L _x is constant above zero degree. in the angular rotation to linear L _y and black pixel set segments on parallel lines and the portion line intersects the image each of the straight line L _y, if the number of pixels of the line segment is w _y or more line segments all pixels of the other black pixels and white pixels, leaving w _y number of black pixels, the number of pixels of the line segment is black pixel contiguous portion of less than w _y pieces As the second step to be left as black pixels, the image matching system according to claim 3, characterized in that it comprises as one of the narrowing process means a means for performing the narrowing process of the image.