JPWO2002009034A1 - Fingerprint matching device, fingerprint matching method, and fingerprint matching program - Google Patents

Abstract

(57) [Abstract] A plurality of partial images of a fingerprint input from a fingerprint input device (7) are reconstructed by correcting overlapping portions of the partial images in a reconstruction processing unit (106), and features are extracted in a fingerprint feature extraction unit (110) and stored in an input feature memory. A matching processing unit performs a DP comparison (dynamic programming) between the features stored in the input feature memory and the features stored in the registered feature memory, and compares the obtained distance value with a preset threshold value. If the distance value is smaller than the threshold value, it is determined to be a match, and if the distance value is greater than the threshold value, it is determined to be a mismatch.

Description

Detailed Description of the Invention

TECHNICAL FIELD The present invention relates to a fingerprint matching device, a fingerprint matching method, and a computer-based program for fingerprint matching for identity verification. Background Art In recent years, the rapid advancement of electronic information and networking has led to growing interest in security technologies for controlling access to information. As one such security technology, various products for identity authentication through fingerprint matching have emerged. Fingerprint authentication requires first inputting a fingerprint image into a fingerprint sensor and then matching the input fingerprint image with a registered fingerprint image. Typical fingerprint matching methods include the minutiae extraction and image matching (pattern matching). The minutiae extraction and image matching method identifies the end points and bifurcation points of fingerprint ridges as minutiae and compares them to perform fingerprint matching. Minutiae are extracted after noise removal from the input fingerprint image and image processing such as contrast enhancement and thinning. Various rules are introduced to avoid false minutiae due to the state of the finger at the time of input or image processing, resulting in a complex algorithm and variations in matching processing time. The image matching method directly compares the similarity of fingerprint images themselves. Since the similarity is measured while shifting the registered fingerprint image and the input fingerprint image, relatively high-speed processing is possible. However, since the fingerprint image itself is stored, security issues such as electronic duplication of the fingerprint image must be overcome. However, these conventional methods extract feature points from the entire fingerprint image or use the entire image itself for matching, requiring a large amount of memory and computational complexity to store the entire image. This hinders the miniaturization and cost reduction of devices. The present invention has been made to solve the above-mentioned problems, and its object is to provide a fingerprint matching device, fingerprint matching method, and fingerprint matching program that can perform fingerprint matching without storing the entire fingerprint image by extracting feature amounts from partial fingerprint images. Disclosure of the Invention The fingerprint matching device of the present invention, which matches fingerprints based on an input fingerprint image, is characterized by comprising: a feature extraction means for calculating and extracting feature amounts from the partial fingerprint images; and an identification means for identifying fingerprints based on the feature amounts extracted by the feature extraction means. In a fingerprint matching device with this configuration, the feature values extracted from the partial images are used to identify fingerprints, so there is no need to store the entire fingerprint image, which eliminates the need for a large-capacity memory, and there is no risk of the entire fingerprint image being electronically duplicated. Also, by defining the partial images to be small, the amount of calculation required to obtain the feature values can be reduced,
If the feature extraction process and the identification process are made independent, the processes can be performed in parallel, thereby making it possible to increase the speed. In addition to the above-mentioned configuration of the invention, the fingerprint collation device of the present invention may also have a fingerprint input means for sequentially inputting partial fingerprint images, and an image processing means for comparing and processing the partial fingerprint images sequentially input by the fingerprint input means to remove overlapping portions, and the feature extraction means may extract the feature from the partial fingerprint images obtained from the image processing means from which overlapping portions have been removed. In the fingerprint collation device of this configuration, the multiple partial fingerprint images sequentially input are combined,
The fingerprint matching device of the present invention includes a storage means for storing one or more features, and the storage means stores the features of the fingerprint matching device, and the fingerprint matching device stores the features of the fingerprint matching device, and the fingerprint matching device stores the features of the fingerprint matching device.
The identification means may identify fingerprints by comparing one or more feature quantities stored in the storage means with one or more feature quantities extracted by the feature quantity extraction means. In a fingerprint matching device with this configuration, fingerprints can be identified by comparing the feature quantities of stored partial images with the feature quantities of input partial images. This eliminates the need to store the feature quantities of the entire fingerprint in the storage means, thereby reducing the storage capacity. Furthermore, in the fingerprint matching device of the present invention, the feature quantity extraction means may perform frequency analysis processing on partial fingerprint images to extract frequency spectrum information of the partial fingerprint images as the feature quantities. In a fingerprint matching device with this configuration, instead of extracting minutiae from a fingerprint, ridge information itself is used to generate feature quantities through frequency analysis processing. This shortens the image preprocessing time, enabling faster processing. Furthermore, since there is no problem with variations in the difficulty of minutiae extraction depending on the state of the finger at the time of image input, processing time can be kept constant. In the fingerprint matching device of the present invention, the frequency analysis calculation process performed by the feature extraction means may be at least one of linear predictive computation (LPC) calculation process, group delay spectrum (GDS) calculation process, and fast Fourier transform (FFT) calculation process. In a fingerprint matching device of this configuration, by using a frequency analysis calculation process well known in voice analysis etc. for feature extraction, it is possible to extract features easily and quickly and perform fingerprint matching processing. In addition, in the fingerprint matching device of the present invention, the fingerprint input means may sequentially input image line images consisting of one or more image lines as partial fingerprint images, and the image processing means may detect overlapping image lines in two partial fingerprint images input consecutively by the fingerprint input means and remove them from one of the partial fingerprint images. In a fingerprint matching device of this configuration, the image processing means may extract the input partial images in two steps,
Since the partial input images are sequentially processed and reconstructed, the memory capacity required to store the input partial images is minimized, and parallel processing of input and image processing enables high-speed processing. In addition, in the fingerprint matching device of the present invention, the image processing means may further apply image reduction processing in at least one of the raster direction and the line direction to the partial fingerprint images from which overlapping portions have been removed. In a fingerprint matching device with this configuration, for example, when an LPC calculation process is used to extract features, performing image reduction processing in the raster direction reduces the number of orders required for calculation, thereby reducing the amount of memory required to store the features. Furthermore, performing image reduction processing in the line direction reduces the number of times the features are calculated, thereby reducing the amount of memory required to store the features. In addition, in the fingerprint matching device of the present invention, the identification means may use a DP matching method (dynamic programming). In a fingerprint matching device with this configuration, even if the detection accuracy of the amount of movement is low and the overall length of the features at the time of registration and at the time of matching differs, fingerprint matching can be performed while absorbing the difference in length between the fingerprints being matched. Furthermore, the fingerprint matching method of the present invention is characterized in that it is a fingerprint matching method for matching fingerprints based on an input fingerprint image, and comprises a feature extraction step for calculating and extracting feature amounts for a partial image of the fingerprint, and an identification step for identifying the fingerprint based on the feature amounts extracted by carrying out the feature extraction step. In the fingerprint matching method of this configuration, the feature amounts extracted from the partial image are used for fingerprint identification, so there is no need to store the entire fingerprint image, eliminating the need for a large-capacity memory and eliminating the risk of electronic duplication of the entire fingerprint image. Furthermore, by setting the partial image to be small, the amount of calculation required to obtain feature amounts can be reduced,
If the feature extraction process and the identification process are separated, the processes can be performed in parallel, thereby increasing the speed. In addition to the configuration of the above invention, the fingerprint matching method may have a fingerprint input step of sequentially inputting partial fingerprint images, and an image processing step of comparing and processing the multiple partial fingerprint images sequentially input in the fingerprint input step to remove overlapping portions, and in the feature extraction step, the feature may be extracted from the partial fingerprint images obtained in the image processing step from which overlapping portions have been removed. In a fingerprint matching method of this configuration, the multiple partial fingerprint images sequentially input are combined,
Since the overlapping portions are removed and the image is reconstructed, feature extraction for overlapping input portions is not duplicated, thereby reducing the load on feature extraction. The fingerprint matching method of the present invention may also include a storage step for storing one or more feature values, and the identification step may identify the identity of fingerprints by comparing one or more feature values stored in the storage step with one or more feature values extracted in the feature extraction step. In this fingerprint matching method, the identity of fingerprints can be identified by comparing the feature values of the stored partial image with the feature values of the input partial image, eliminating the need to store the feature values of the entire fingerprint. In the fingerprint matching method of the present invention, the feature extraction step may also perform frequency analysis on the partial fingerprint image, extracting frequency spectrum information of the partial fingerprint image as the feature value. In this fingerprint matching method, instead of extracting minutiae from the fingerprint, ridge information itself is used to generate feature values through frequency analysis. This shortens the image preprocessing time, thereby enabling faster processing. Furthermore, since there is no problem of variations in the difficulty of extracting feature points depending on the state of the finger when the image is input, the processing time can be made constant. Also, in the fingerprint verification method of the present invention, the frequency analysis processing performed in the feature extraction step includes linear prediction (LPC) processing, group delay spectrum (GDS) processing, and the like.
) arithmetic processing or fast Fourier transform (FFT) arithmetic processing may be used. In the fingerprint verification method of this configuration, by using frequency analysis arithmetic processing well known in voice analysis, etc., to extract features, fingerprint verification processing can be performed easily and quickly. In the fingerprint verification method of the present invention, the fingerprint input step may sequentially input image line images consisting of one or more image lines as partial fingerprint images, and the image processing step may detect overlapping image lines in two partial fingerprint images input consecutively in the fingerprint input step and remove them from one of the partial fingerprint images. In the fingerprint verification method of this configuration, the input partial images are sequentially processed two at a time to reconstruct them, minimizing the memory capacity required to hold the input partial images. Furthermore, parallel processing of input and image processing enables high-speed processing. In the fingerprint verification method of the present invention, the image processing step may further apply image reduction processing in at least one of the raster direction and the line direction to the partial fingerprint images from which overlapping portions have been removed. In the fingerprint matching method of this configuration, for example, when LPC calculation processing is used to extract features, performing image reduction processing in the raster direction reduces the order of calculation required, thereby reducing the amount of memory required to store the features. Also, performing image reduction processing in the line direction reduces the number of times the features are calculated, thereby reducing the amount of memory required to store the features. Furthermore, in the fingerprint matching method of the present invention, the identification step may use DP matching (dynamic programming). In the fingerprint matching method of this configuration, even if the detection accuracy of the amount of movement is low and the overall length of the features at the time of registration and at the time of matching is different, fingerprint matching can be performed while absorbing the difference in length between the fingerprints to be matched. Furthermore, the fingerprint matching program of the present invention performs the following based on the input fingerprint image:
a fingerprint matching program for causing a computer to perform fingerprint matching, comprising: a feature extraction step for calculating and extracting feature amounts for partial fingerprint images; and performing the feature extraction step for one or more partial fingerprint images to extract partial fingerprint feature amounts;
and an identification step for identifying a fingerprint based on these partial features. In a fingerprint matching program of this configuration, features extracted from partial images are used for fingerprint identification, eliminating the need to store the entire fingerprint image, eliminating the need for a large-capacity memory and eliminating the risk of electronic duplication of the entire fingerprint image. Furthermore, by defining small partial images, the amount of calculation required to obtain features can be reduced. Separating the feature extraction process from the identification process enables parallel processing, thereby enabling faster processing. In addition to the above configuration, the fingerprint matching program may also cause a computer to execute a fingerprint input step for sequentially inputting partial fingerprint images, and an image processing step for comparing and processing multiple partial fingerprint images sequentially input in the fingerprint input step to remove overlapping portions, and the feature extraction step may extract the features from the partial fingerprint images obtained in the image processing step from which the overlapping portions have been removed. In a fingerprint matching program of this configuration, multiple partial images sequentially input are combined and reconstructed by removing the overlapping portions, eliminating the need for redundant feature extraction for overlapping input portions, thereby reducing the load on feature extraction. Furthermore, the fingerprint matching program of the present invention may have a computer execute a storage step for storing one or more feature quantities, and the identification step may identify the identity of a fingerprint by comparing the one or more feature quantities stored in the storage step with the one or more feature quantities extracted in the feature quantity extraction step. A fingerprint matching program having this configuration can identify the identity of a fingerprint by comparing the feature quantities of the stored partial image with the feature quantities of the input partial image, eliminating the need to store the feature quantities of the entire fingerprint. Furthermore, the fingerprint matching program of the present invention may have the feature quantity extraction step perform frequency analysis processing on the partial image of the fingerprint, extracting frequency spectrum information of the partial image of the fingerprint as the feature quantities. A fingerprint matching program having this configuration does not extract minutiae from a fingerprint, but instead uses ridge information itself to generate feature quantities through frequency analysis processing. This shortens the image preprocessing time, enabling faster processing. Furthermore, since there is no problem of variations in the difficulty of minutiae extraction depending on the state of the finger at the time of image input,
The processing time can be kept constant. In addition, in the fingerprint matching program of the present invention, the frequency analysis calculation process performed in the feature extraction step includes linear prediction (LPC) calculation process, group delay spectrum (
The fingerprint matching program of the present invention may use at least one of a GDS (Geometrical Transform) calculation process and a Fast Fourier Transform (FFT) calculation process. By using a frequency analysis calculation process well known in speech analysis, etc., to extract features, the fingerprint matching program of the present invention can easily and quickly extract features and perform fingerprint matching. Furthermore, in the fingerprint matching program of the present invention, the fingerprint input step may sequentially input image line images consisting of one or more image lines as partial fingerprint images, and the image processing step may detect overlapping image lines in two partial fingerprint images input consecutively in the fingerprint input step and remove the overlapping image lines from one of the partial fingerprint images. The fingerprint matching program of the present invention may reconstruct the input partial images by sequentially processing two partial fingerprint images at a time, thereby minimizing the memory capacity required to hold the input partial images and further enabling faster processing by parallel processing of input and image processing. Furthermore, in the fingerprint matching program of the present invention, the image processing step may further apply image reduction processing in at least one of the raster direction and the line direction to the partial fingerprint images from which overlapping portions have been removed. In the fingerprint matching program of this configuration, for example, when LPC calculation processing is used to extract features, if image reduction processing is performed in the raster direction, the number of orders required for calculation is reduced, and therefore the amount of memory for storing features can be reduced. Also, if image reduction processing is performed in the line direction, the number of times features are calculated is reduced, and therefore the amount of memory for storing features can be reduced. Also, in the fingerprint matching program of the present invention, the identification step is performed using the DP matching method (
A fingerprint matching program having this configuration can perform fingerprint matching by absorbing the difference in length between the fingerprints being matched, even if the detection accuracy of the amount of movement is low and the feature values at the time of registration and at the time of matching are different in overall length. BEST MODE FOR CARRYING OUT THE INVENTION Hereinafter, an embodiment in which the present invention is applied to an electronic lock equipped with a fingerprint matching device will be described with reference to the drawings. As shown in FIG. 1, the electronic lock 100 of this embodiment has:
A fingerprint input device 7 and a switch 8 (fingerprint registration switch 8a and fingerprint deletion switch 8b)
) and a liquid crystal display 10, and is attached to a door or the like, and is connected to an electromagnetic solenoid 9 (FIG. 2
2, the electronic lock 100 of this embodiment is composed of an electronic circuit centered around a CPU 1, a RAM 2, a ROM 3, an EEPROM 4, a fingerprint input device 7, a switch 8, and a
The electronic lock 100 is comprised of an input/output (I/O) port 5 connecting the electromagnetic solenoid 9 to the CPU 1, a liquid crystal display controller (LCDC) 6 controlling the liquid crystal display 10, and a power supply such as a battery (not shown). As shown in FIG. 4, the RAM 2 includes a partial image buffer memory 20 for storing a slice image of a fingerprint input from the fingerprint input device 7, an input feature memory 21 for storing the feature values of the input fingerprint, a joint determination memory 22 for storing the calculation results for determining the joint portion, and a work area 23 for temporarily storing various data. The ROM 3 stores various programs in addition to a fingerprint matching program, and the CPU 1 executes these programs to control the electronic lock 100. As shown in FIG. 5, the EEP-ROM 4 includes a registered feature memory 40 for storing the feature values of registered fingerprints. The EEP-ROM 4 is a nonvolatile memory, so it can retain its contents even when the power supply is interrupted. In addition, the EEP-ROM 4 may be a non-volatile memory such as a flash memory in addition to a normal EEP-ROM. In detail, as shown in Fig. 3, the fingerprint matching device built into the electronic lock 100 is composed of a fingerprint input device 7, an image processing unit 102, a fingerprint feature extraction unit 110, a matching processing unit 114, a determination unit 115, a determination result output unit 116, a partial image buffer memory 20 provided in the RAM 2, an input feature memory 21, a joint determination holding memory 22, and a registered feature memory 40 of the EEP-ROM 4. The fingerprint input device 7 is composed of a sensor 7a and an A/D converter (not shown),
The temperature change of the finger moving on the sensor 7a is output in the form of an input partial image, and stored in RAM2.
The input partial image is stored in the partial image buffer memory 20 within the fingerprint input device 7. In this embodiment, the input partial image is formed in a line shape of 280 pixels wide by 8 pixels high, and is output at least 200 times per second. An example of an input partial image is shown in FIG. 6. The image processing unit 102 performs preprocessing on the input partial image to prepare it for feature extraction, and is composed of a start determination unit 103, a movement amount detection unit 104, an overlapping processing unit 105, a reconstruction processing unit 106, a joint determination preprocessing unit 107, a joint determination holding memory 22, and an image reduction processing unit 109. The start determination unit 103 extracts the center portion (64 pixels wide by 4 pixels high in this embodiment) from two temporally consecutive input partial images obtained from the fingerprint input device 7, and sums the absolute values of the differences in pixel values at the same location. If the number of times this value exceeds a threshold reaches a certain number or more, it is determined that the finger is moving on the fingerprint input device 7, and recording to the joint determination holding memory 22 and the input feature memory 21 is started. Similarly, when the number of times below the threshold reaches a certain number or more, it is determined that the finger has been removed from the input device, and recording to each memory is stopped. After that, matching is performed using the matching processing unit 114. The movement amount detection unit 104 uses two temporally consecutive input partial images obtained from the fingerprint input device 7, and detects the center of one of the input partial images (64 horizontal lines in this embodiment).
The overlapping processing unit 105 extracts an input partial image (8 pixels wide x 8 pixels high) from the fingerprint input device 7. Next, a location shifted by the estimated movement amount is extracted from the other input partial image in the same size. The absolute values of the differences in pixel values at the same locations in these extracted partial images are summed up and used as the image difference. This is repeated for each estimated movement amount, and the movement amount that results in the smallest image difference is output as the detection result of the movement amount of the finger moving on the sensor 7a. The overlapping processing unit 105 overlaps the input partial image obtained from the fingerprint input device 7 by adding the value in the memory and the value of the input image to a buffer memory at a position shifted by the movement amount obtained from the movement amount detection unit 104 and storing the results in the same location. At this time, the number of overlapping times is also recorded in the buffer memory. The reconstruction processing unit 106 reconstructs the image obtained from the fingerprint input device 7 based on the movement amount obtained from the movement amount detection unit 104, and extracts a partial image (280 wide x 8 pixels high in this embodiment) from the image.
The image is output in units of 256 pixels horizontally by 1 pixel vertically. FIG. 7 shows an example of an entire image obtained by the reconstruction processing unit 106. FIG. 8 shows an example of nine consecutive partial images output from the reconstruction processing unit 106. The joint determination preprocessing unit 107 also performs some of the calculations required to determine the joint parts of the finger moving on the sensor 7a, outputs the calculation results, and stores them in the joint determination storage memory 22. First, a Sobel transform is performed on the input image to emphasize the fingerprint features. Next, a Gaussian transform is performed to reduce noise-like pixels. Next, one line (in this embodiment, 256 pixels horizontally by 1 pixel vertically) is extracted, and the number of pixels whose pixel values exceed a threshold is counted and used as the processing result for that line. This value is approximately proportional to the area of the finger contacting the sensor 7a. Portions where this value is small are determined to be joints, and only portions containing valid information are used as data for matching. The determination unit 115 stores the data in the joint determination storage memory 22.
2, the position of the joint is determined after the finger is released from the sensor 7a, and the end point of the matching is determined.
The image is reduced to 1/2 and vertically to 1/3. The horizontal reduction makes it possible to reduce the order required for feature extraction using LPC analysis, which will be described later. Furthermore, the vertical reduction makes it possible to reduce the capacity of the input feature memory 21 without impairing the matching results. The fingerprint feature extraction unit 110 extracts features from one input reduced line (128 pixels horizontally by 1 pixel vertically in this embodiment) and outputs feature data. In this embodiment, LPC analysis is performed using the pixel values of the line as signal changes. The input feature memory 21 continuously records the feature data output from the fingerprint feature extraction unit 110 in memory. Furthermore, when fingerprint matching processing is performed, the matching processing unit 1
14. When instructed to register a fingerprint, the registered feature memory 40 of the EEP-ROM 4 stores and holds the contents of the input feature memory 21. When performing fingerprint matching processing, the registered feature memory 40 of the EEP-ROM 4 outputs feature data in accordance with a request from the matching processing unit 114. The matching processing unit 114 performs DP matching between the feature data stored in the input feature memory 21 and the registered feature memory 40 of the EEP-ROM 4, represents the smallest distance as the distance between the features, and outputs it as the similarity. The determination unit 115 makes a determination by comparing the similarity output from the matching processing unit 114 with a preset threshold, and outputs the result to the determination result output unit 116. The determination result output unit 116 inputs the determination result output from the determination unit 115 and outputs it to the outside of the device. Next, the operation of the electronic lock 100 of this embodiment will be explained based on the flowcharts of Figures 9 to 13. Each step of the flowchart will be referred to as S
In the electronic lock 100 of this embodiment, a fingerprint is registered by pressing the fingerprint registration switch 8a, placing a finger on the fingerprint input device 7, and moving the finger in a slidable manner in the longitudinal direction of the finger, and the plunger 9a is extended to lock the lock. If a finger is placed on the fingerprint input device 7 without pressing the fingerprint registration switch 8a and moved in a slidable manner in the longitudinal direction of the finger, a fingerprint is collated, and if the fingerprint matches the registered fingerprint, the plunger 9a is retracted and the electronic lock 100 is unlocked. Also, if a fingerprint is input by pressing the fingerprint deletion switch 8b, placing a finger on the fingerprint input device 7, and moving the finger in a slidable manner in the longitudinal direction of the finger, a confirmation message is displayed on the liquid crystal display 10, and then the fingerprint deletion switch 8b is pressed again.
Pressing the key erases the registered fingerprint. Figure 9 is a flowchart showing the overall main control process of the electronic lock 100. First, when the power is turned on, the electronic lock is reset and the memory in RAM 2 is initialized (
S40). If any of the switches 8 is pressed, this is detected (S41). If the fingerprint registration switch 8a is pressed (S42: YES), fingerprint registration processing is performed (S43). If the fingerprint deletion switch 8b is pressed (S44: YES) instead of the fingerprint registration switch 8a (S42: NO), fingerprint deletion processing is performed (S45). Details of the fingerprint registration processing and fingerprint deletion processing will be described later. If there is no switch input (S44: NO), fingerprint input is detected (S46). Details of the fingerprint input detection processing will be described later. If there is no fingerprint input (S47: NO), the process returns to S41 and switch input detection is performed. If a fingerprint is input (S47: YES) and it is determined that the input fingerprint matches the registered fingerprint (S48: YES), the plunger 9a is pulled to unlock (S49). Figure 10 is a flowchart showing details of the fingerprint registration processing performed in S43 of Figure 9. When a finger is placed on the fingerprint input device 7 and slid along the length of the finger, a partial image as shown in FIG. 6 is input from the sensor 7a (S50).
Since input is detected at regular time intervals (in this embodiment, 200 times or more per second), one or more partial images are input depending on the speed at which the finger is moved. The input partial images are stored in the partial image buffer memory 20 of the RAM 2 (S51). If only one partial image is detected as an input and only one partial image is stored in the partial image buffer memory 20, an error occurs, the process ends, and the process returns to the main routine (S52: NO). If multiple partial images are detected as input in the partial image buffer memory 20, the process ends and returns to the main routine (S52: NO).
If the value is set to 0 (S52: YES), the movement amount detection unit 104 detects the movement amount, and the reconstruction processing unit 106 corrects the overlapping portions of the partial images based on the detected movement amount and performs reconstruction (S53).
The amount of movement that does not overlap with the above is expelled and stored in the work area 23 of RAM 2.
Next, the overlapping portion of the old frame and the current frame is overlapped by an overlapping processing unit and stored in the work area 23 of the RAM 2, and further the portion of the current frame that does not overlap with the old frame is stored in the work area 23 of the RAM 2.
Then, the fingerprint feature extraction unit 110 extracts features from the reconstructed partial image (S54), stores the extracted features in the input feature memory 21, and then stores the extracted features in the EEP-RO
The fingerprint is stored in the registered feature memory 40 of M4 (S55). Details of the feature extraction process will be described later. Fig. 11 is a flowchart showing details of the fingerprint erasure process performed in S45 of Fig. 9. When a finger is placed on the fingerprint input device 7 and moved in the longitudinal direction of the finger as if sliding, a partial image as shown in Fig. 6 is input from the sensor (S60). The sensor detects input at regular time intervals (in this embodiment, 200 times or more per second),
Depending on the speed of the finger movement, one or more partial images are input. The input partial images are stored in the partial image buffer memory 20 (S61). If only one partial image is detected as being input and only one partial image is stored in the partial image buffer memory 20, an error occurs, the process ends, and the process returns to the main routine (S62: NO). If multiple partial images are stored in the partial image buffer memory 20, an error occurs.
If the partial image is stored in the area (S62: YES), the movement amount detection unit 104 detects the movement amount, and the reconstruction processing unit 106 corrects the overlapping portions of the partial images based on the detected movement amount and performs reconstruction (S63). The reconstruction is performed by moving the movement amount that does not overlap with the partial image (current frame) input later from the partial image (old frame) input earlier and storing it in the work area 23 of RAM 2, then the overlapping portions of the old frame and the current frame are superimposed by the superimposition processing unit and stored in the work area 23 of RAM 2, and further the portion of the current frame that does not overlap with the old frame is superimposed in the work area 23 of RAM 2.
3. Then, the fingerprint feature extraction unit 110 extracts features from the reconstructed partial image (S64) and stores them in the input feature memory 21 (S65). Details of the feature extraction process will be described later. It is determined whether the features stored in the input feature memory 21 are equal to or longer than a predetermined length (for example, 500 lines) (S66). If the length is less than the predetermined length, an error occurs because comparison and matching are difficult, and the process is terminated and the process returns to the main routine (S66: NO). If the length is equal to or longer than the predetermined length (S66: YES),
), the feature stored in the input feature memory 21 in the matching processing unit 114 and E
A DP comparison (dynamic programming) is performed between the features stored in the registered feature memory 40 of the EP-ROM 4 (S67). DP comparison (dynamic programming) is also called DP matching or rubber matching, and is widely used because it has the characteristic of being able to smoothly match even slightly fluctuating data strings. This DP comparison is an algorithm that draws two series of reference data and test data on an x-y plane, and selects the time progression that will result in the shortest cumulative distance, taking into account the distance difference between the actual data. In this embodiment, S
The LPC cepstrum (described later in detail) obtained by the feature extraction process (described later) of 64 is regarded as the spectral data for each fingerprint line, and the LPC cepstrum obtained from the input fingerprint image is arranged vertically on the fingerprint image as test data, and the LPC cepstrum stored in the registered feature memory 40 of the EEP-ROM 4 is arranged vertically on the fingerprint image as reference data to obtain the degree of matching between them. Although the reference data and the test data differ in input speed change and degree of change, these are taken into account by DP comparison, and a search is made for a vertical correspondence that ultimately brings the reference data and the test data closest, and the degree of matching based on the closest vertical correspondence is output as a distance value. A smaller distance value indicates a smaller difference between the two LPC cepstra, and a larger distance value indicates a larger difference between the two LPC cepstra. Next, the determination unit 115 compares the distance value obtained by the DP comparison with a preset threshold value, and determines that there is a match if the distance value is smaller than the threshold value, and determines that there is a mismatch if the distance value is larger than the threshold value (S68). If there is no match, the registered fingerprint is not erased from the registered feature memory 40 of the EEP-ROM 4, and the process ends and returns to the main routine (S69: NO). If there is a match, the feature value of the matching registered fingerprint is erased from the registered feature memory 40 of the EEP-ROM 4 (
9. When a finger is placed on the fingerprint input device 7 and moved in the longitudinal direction of the finger in a sliding motion, a partial image as shown in FIG. 6 is input from the sensor (S80). The sensor detects input at regular intervals (in this embodiment, 200 times or more per second), so one or more partial images are input depending on the speed at which the finger is moved. The input partial images are stored in the partial image buffer memory 20 (S81).
If only one partial image is detected as an input and only one partial image is stored in the partial image buffer memory 20, an error occurs, the process ends, and the process returns to the main routine (S82: NO).
If the value is set to 0 (S82: YES), the movement amount detection unit 104 detects the movement amount, and the reconstruction processing unit 106 corrects the overlapping portions of the partial images based on the detected movement amount and performs reconstruction (S83).
The amount of movement that does not overlap with the above is expelled and stored in the work area 23 of RAM 2.
Next, the overlapping portions of the old and current frames are overlapped by an overlapping processing unit and stored in work area 23 of RAM 2, and further, the portions of the current frame that do not overlap with the old frame are stored in work area 23 of RAM 2. Then, feature extraction is performed on the reconstructed partial images by fingerprint feature extraction unit 110 (S84), and the extracted features are stored in input feature memory 21 of RAM 2 (S85).
The details of the feature extraction process will be described later. It is determined whether the feature stored in the input feature memory 21 is equal to or longer than a predetermined length (for example, 500 lines) (S86).
If the length does not reach the predetermined length, it is difficult to perform comparison and verification, so an error occurs, the process ends, and the process returns to the main routine (S86: NO).
(S86: YES), the matching processing unit 114 performs a DP (dynamic programming) comparison between the feature stored in the input feature memory 21 and the feature stored in the registered feature memory 40 of the EEP-ROM 4 (S87).
The distance value obtained by the P comparison is compared with a preset threshold value. If the distance value is smaller than the threshold value, it is determined to be a match. If the distance value is larger than the threshold value, it is determined to be a mismatch (S88), and the process ends and returns to the main routine. FIG. 13 is a flowchart showing the details of the feature extraction process performed in S54 of FIG. 10, S64 of FIG. 11, and S84 of FIG. 12. In this embodiment, minutiae are not extracted from the fingerprint, but rather, ridge information itself is used for analysis and processing to obtain feature quantities. That is, if a fingerprint image is cut out horizontally and the fingerprint position is taken horizontally and the fingerprint unevenness (shade) is taken vertically, one cut-out line of the fingerprint can be viewed as a waveform signal. Then, by performing an analysis of this waveform signal as is commonly performed in voice data processing, a power spectrum can be obtained. Specifically, each line of the reconstructed input partial image is considered as one frame, and extraction processing is performed for each frame. First, as preprocessing, Hamming windowing is performed (S9
0), and the influence of the edges due to frame segmentation is alleviated. Next, the frame data that has been corrected by Hamming windowing is received, and its autocorrelation function is calculated (S91). Furthermore, based on the obtained autocorrelation function, a linear prediction method (LPC:
LPC coefficients are calculated using Linear Predictive Coding (LPC) (S92). Linear prediction is a well-known technique used for voice compression in mobile phones and the like. Using this technique, voices such as vowels can be estimated using a full-spectrum transfer function, and peak frequencies and the like can be estimated from the spectrum. The LPC coefficients obtained in S92 are then linearly combined to obtain an LPC cepstrum (S93). In this embodiment, the LPC cepstrum thus obtained in the feature extraction process is stored as a feature in the input feature memory 21 of the RAM 2 (S55, S65, S85). Note that in this embodiment, linear prediction (LPC) is used as the frequency analysis calculation process used for feature extraction, and the LPC cepstrum is extracted as a feature, but the frequency analysis calculation process used for feature extraction is not limited to this. For example, the well-known Fast Fourier Transform (FFT)
m) may be used. Fast Fourier transform is a type of algorithm that quickly performs computational processing to calculate the frequency components (spectrum) of a digitized signal, known as discrete Fourier transform. Specifically, the weighted LPC coefficients obtained in S92 are subjected to fast Fourier transform to obtain a power spectrum, which is then used as a feature. Furthermore, the well-known group delay spectrum (GDS) may be used as the frequency analysis computational processing used to extract features. The group delay spectrum (GDS) is defined as the frequency derivative of the phase spectrum in a power transfer function. The number of elements in this array is the number of elements in the phase spectrum minus one. Specifically, the group delay spectrum (GDS) is obtained by taking the phase derivative of the power spectrum obtained by fast Fourier transforming the weighted LPC coefficients, and this is used as a feature. As described above, the fingerprint matching device of this embodiment does not extract minutiae from a fingerprint, but rather extracts features by frequency analysis computational processing, regarding the ridge information itself as a waveform signal. As a result, the processing time required for feature extraction is constant regardless of the state of the fingerprint, and furthermore, feature values can be extracted from partial images without storing the entire fingerprint image. Therefore, compared to conventional fingerprint matching methods that extracted feature data from the entire fingerprint image, matching can be performed with a smaller memory capacity, making it possible to reduce the size of the fingerprint matching device and speed up processing. Furthermore, since it is not necessary to store the entire fingerprint image, security issues due to electronic duplication can be avoided. Note that, since feature values are extracted from partial images, there is a risk of duplication of extraction processing due to overlapping of input images, but this is prevented by performing image reconstruction processing. Furthermore, since feature values are extracted from partial images, there is a possibility of variation from registered feature values for each fingerprint input, but this is absorbed and matched using DP comparison (DP matching). Note that it goes without saying that the present invention can be modified in various ways. For example, in the above embodiment, the present invention was described as being applied to an electronic lock, but the present invention can also be applied to
It goes without saying that the present invention can be applied not only to electronic locks but also to various devices that perform fingerprint matching. In the above embodiment, the fingerprint matching program is stored in ROM 3, but is not limited to being stored in ROM. It may also be stored in a computer-readable storage medium such as a floppy disk or CD-ROM, or may even be distributed via a network such as the Internet. INDUSTRIAL APPLICABILITY As described above, the fingerprint matching device, fingerprint matching method, and fingerprint matching program of the present invention are suitable for use in various devices that perform fingerprint matching. They are particularly suitable for use in electronic locks that are unlocked by fingerprint matching, electronic devices that are activated by fingerprint matching, and information terminals such as mobile phones that perform fingerprint matching.

[Brief explanation of the drawings]

Fig. 1 is an external view of the electronic lock of this embodiment, Fig. 2 is a block diagram showing the electrical configuration of the electronic lock of this embodiment, Fig. 3 is a block diagram showing the electrical configuration of the fingerprint matching device, Fig. 4 is a schematic diagram showing the memory area of RAM 2, Fig. 5 is a schematic diagram showing the memory area of EEP-ROM 4, Fig. 6 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 7 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 8 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 9 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 10 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 11 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 12 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 13 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 14 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 15 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 16 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 17 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 18 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 19 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 20 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 21 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 22 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 23 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 24 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 25 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 26 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 27 is a schematic diagram showing the memory area of the fingerprint matching device, Fig. 28 is
7 is an example of an input partial image, and FIG. 7 is an example of an image obtained by the reconstruction processing unit 106.
8 shows an example in which nine consecutive partial images are arranged and output from the reconstruction processing unit 106. FIG. 9 is a flowchart showing an outline of the processing flow of the electronic lock, FIG. 10 is a flowchart showing the details of the fingerprint registration processing, and FIG. 11 is a flowchart showing the details of the fingerprint registration processing.
Fig. 12 is a flowchart showing the fingerprint input detection process in detail, and Fig. 13 is a flowchart showing the feature extraction process in detail.

[Procedure Amendment] Submission of a copy of amendments under Article 34 of the Patent Cooperation Treaty (Official)

[Submission date] July 22, 2002 (2002.7.22)

[Procedural Correction 1]

[Name of document to be corrected] Statement

[Item to be amended] Claims

[Correction method] Change

[Contents of the amendment]

[Claims]

[Procedural Correction 2]

[Name of document to be corrected] Drawing

[Item name to be corrected] Figure 4

[Correction method] Change

[Contents of the amendment]

[Figure 4]

───────────────────────────────────────────────────── Continued from the front page (81) Designated Countries EP(AT,BE,CH,CY, DE, DK, ES, FI, FR, GB, GR, IE, I T, LU, MC, NL, PT, SE, TR), OA(BF , BJ, CF, CG, CI, CM, GA, GN, GW, ML, MR, NE, SN, TD, TG), AP(GH, G M, KE, LS, MW, MZ, SD, SL, SZ, TZ , UG, ZW), UA(AM, AZ, BY, KG, KZ, MD, RU, TJ, TM), AE, AG, AL, AM, AT, AU, AZ, BA, BB, BG, BR, BY, B Z, CA, CH, CN, CR, CU, CZ, DE, DK ,DM,DZ,EE,ES,FI,GB,GD,GE, GH, GM, HR, HU, ID, IL, IN, IS, J P, KE, KG, KP, KR, KZ, LC, LK, LR , LS, LT, LU, LV, MA, MD, MG, MK, MN, MW, MX, MZ, NO, NZ, PL, PT, R O, RU, SD, SE, SG, SI, SK, SL, TJ , TM, TR, TT, TZ, UA, UG, US, UZ, VN, YU, ZA, ZW (72) Inventor Tatsuhiko Sugimoto 2-4-7 Kifune, Ichinomiya City, Aichi Prefecture Tsubasa 102 (72) Inventor: Toshiro Ishizaka 2-62 Aoike-cho, Atsuta-ku, Nagoya 203 (Note) This publication is based on the publication published internationally by the International Bureau of Patents (WIPO). The effect of the international publication of the Japanese patent application (Japanese utility model registration application) related to this publication arises pursuant to Article 184-10, Paragraph 1 of the Patent Act (Article 48-13, Paragraph 2 of the Utility Model Act) and is unrelated to this publication.

Claims (24)

[Claims] 1. A fingerprint matching device for matching fingerprints based on an input fingerprint image, comprising: a feature extraction means for calculating and extracting feature values for a partial fingerprint image;
a fingerprint matching device comprising: a fingerprint identifying means for identifying a fingerprint based on the feature extracted by the feature extracting means; [Claim 2] A fingerprint matching device as described in claim 1, characterized in that it has a fingerprint input means for sequentially inputting partial fingerprint images, and an image processing means for comparing and processing the partial fingerprint images sequentially input by the fingerprint input means to remove overlapping portions, and the feature extraction means extracts the feature from the partial fingerprint images from which overlapping portions have been removed and which are obtained from the image processing means. [Claim 3] A fingerprint matching device as described in claim 1 or 2, characterized in that it has a memory means for storing one or more features, and the identification means identifies the identity of fingerprints by comparing and matching the one or more features stored in the memory means with the one or more features extracted by the feature extraction means. [Claim 4] A fingerprint matching device as described in any one of claims 1 to 3, characterized in that the feature extraction means performs frequency analysis calculation processing on a partial image of the fingerprint and extracts frequency spectrum information of the partial image of the fingerprint as the feature. [Claim 5] A fingerprint matching device as described in claim 4, characterized in that the frequency analysis calculation processing performed by the feature extraction means uses at least one of linear prediction (LPC) calculation processing, group delay spectrum (GDS) calculation processing, and fast Fourier transform (FFT) calculation processing. [Claim 6] A fingerprint matching device as described in any one of claims 2 to 5, characterized in that the fingerprint input means sequentially inputs image line images consisting of one or more image lines as partial images of a fingerprint, and the image processing means detects overlapping image lines in two partial images of fingerprints input consecutively by the fingerprint input means and removes them from the partial image of one of the fingerprints. [Claim 7] A fingerprint matching device as described in any one of claims 2 to 6, characterized in that the image processing means further applies image reduction processing in at least either the raster direction or the line direction to the partial fingerprint image from which overlapping portions have been removed. 8. The fingerprint matching device according to claim 1, wherein said identifying means uses a DP matching method (dynamic programming). [Claim 9] A fingerprint matching method for matching fingerprints based on an input fingerprint image, characterized in that it comprises a feature extraction step for calculating and extracting features from a partial image of the fingerprint, and an identification step for identifying the fingerprint based on the features extracted by carrying out the feature extraction step. [Claim 10] A fingerprint matching method as described in claim 9, comprising a fingerprint input step of sequentially inputting partial fingerprint images, and an image processing step of comparing and processing the partial fingerprint images sequentially input in the fingerprint input step to remove overlapping portions, wherein in the feature extraction step, the feature is extracted from the partial fingerprint images obtained in the image processing step from which overlapping portions have been removed. [Claim 11] A fingerprint matching method as described in claim 9 or 10, characterized in that it has a storage step for storing one or more features, and in the identification step, the identity of the fingerprints is identified by comparing and matching the one or more features stored in the storage step with the one or more features extracted in the feature extraction step. [Claim 12] A fingerprint matching method as described in any one of claims 9 to 11, characterized in that in the feature extraction step, frequency analysis calculation processing is performed on a partial image of the fingerprint, and frequency spectrum information of the partial image of the fingerprint is extracted as the feature. 13. The frequency analysis calculation process performed in the feature extraction step includes:
13. The fingerprint verification method according to claim 12, wherein at least one of linear predictive coding (LPC) calculation processing, group delay spectrum (GDS) calculation processing, and fast Fourier transform (FFT) calculation processing is used. [Claim 14] A fingerprint matching method as described in any one of claims 9 to 13, characterized in that in the fingerprint input step, image line images consisting of one or more image lines are input sequentially as partial images of the fingerprint, and in the image processing step, overlapping image lines are detected in the partial images of two fingerprints input consecutively in the fingerprint input step, and are removed from the partial image of one of the fingerprints. [Claim 15] A fingerprint matching method described in any one of claims 10 to 14, characterized in that in the image processing step, image reduction processing is further applied to the partial fingerprint image from which overlapping portions have been removed in at least one of the raster direction or line direction. 16. A fingerprint matching method according to claim 9, wherein the identification step uses a DP matching method (dynamic programming). [Claim 17] A fingerprint matching program that causes a computer to perform fingerprint matching based on an input fingerprint image, the fingerprint matching program causing a computer to execute a feature extraction step of calculating and extracting features for partial fingerprint images, and an identification step of performing the feature extraction step for one or more partial fingerprint images to extract partial fingerprint features and identify the fingerprint based on those partial features. [Claim 18] A fingerprint matching program as described in claim 17, which causes a computer to execute a fingerprint input step of sequentially inputting partial fingerprint images, and an image processing step of comparing and processing the partial fingerprint images sequentially input in the fingerprint input step to remove overlapping portions, and wherein in the feature extraction step, the feature is extracted from the partial fingerprint images obtained in the image processing step from which overlapping portions have been removed. [Claim 19] A fingerprint matching program as described in claim 17 or 18, characterized in that a computer is caused to execute a storage step for storing one or more features, and in the identification step, the identity of the fingerprint is identified by comparing and matching the one or more features stored in the storage step with the one or more features extracted in the feature extraction step. [Claim 20] A fingerprint matching program as described in any one of claims 17 to 19, characterized in that in the feature extraction step, frequency analysis calculation processing is performed on a partial image of the fingerprint, and frequency spectrum information of the partial image of the fingerprint is extracted as the feature. 21. The frequency analysis calculation process performed in the feature extraction step includes:
21. The fingerprint matching program according to claim 20, wherein at least one of linear predictive coding (LPC) calculation processing, group delay spectrum (GDS) calculation processing, and fast Fourier transform (FFT) calculation processing is used. [Claim 22] A fingerprint matching program as described in any of claims 17 to 21, characterized in that in the fingerprint input step, image line images consisting of one or more image lines are input sequentially as partial images of a fingerprint, and in the image processing step, overlapping image lines are detected in the partial images of two fingerprints input consecutively in the fingerprint input step, and are removed from the partial image of one of the fingerprints. [Claim 23] A fingerprint matching program as described in any of claims 18 to 22, characterized in that in the image processing step, image reduction processing is further applied to the partial fingerprint image from which overlapping portions have been removed in at least one of the raster direction or line direction. 24. The fingerprint matching program according to claim 17, wherein the identification step uses a DP matching method (dynamic programming).