JP2007323432A - Image collation device, image collation method, image collation program, and computer-readable recording medium recording image collation program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To increase processing efficiency of an image collating device, an image collating method, an image collating program, and a computer-readable recording medium with the image collating program recorded thereon. <P>SOLUTION: A section 1047 detects elements not to be collated in an image. The image from which the detected elements are excluded is used to perform collation processing. A partial image feature value calculating unit 1045 calculates feature values corresponding to patterns of a plurality of partial images in the image corresponding to the respective partial images. The section 1047 detects an area specified by a combination of partial images having predetermined calculated feature values as an element not to be collated. <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

  The present invention relates to an image collation apparatus, an image collation method, an image collation program, and a computer-readable recording medium on which an image collation program is recorded, and in particular, image collation for detecting an element to be excluded from collation from an image for collation. The present invention relates to an apparatus, an image collation method, an image collation program, and a computer-readable recording medium on which the image collation program is recorded.

  Conventionally, personal authentication techniques tend to be applied in various situations, such as when giving permission to use a device to a user. In personal authentication, authentication using fingerprints is often adopted because of physical characteristics unique to each person, for example, ease of collection. At the time of authentication using a fingerprint, image verification is performed using a fingerprint image read from a user's finger placed on a fingerprint reading surface of a fingerprint sensor.

  In such fingerprint authentication, if the fingerprint reading surface is contaminated, the fingerprint image contains a noise component due to the contamination, so that accurate image matching cannot be performed. A method for solving such a problem is proposed in Patent Document 1.

In Patent Document 1, in a fingerprint collation device, an image of a finger placement unit is captured before a finger is placed on the finger placement unit, the contrast of the entire captured image is detected, and the detected contrast value is equal to or greater than a predetermined value. Whether or not the finger placement portion is dirty is detected based on whether or not the finger placement portion is dirty. When it is detected that the contrast value is greater than or equal to a predetermined value, an alarm is issued. When a warning is issued, the user needs to clean the finger placement unit and place the finger again to capture the image, which is not excellent in operability.
Japanese Patent Laid-Open No. 62-197878

  According to the above-mentioned Patent Document 1, prior to the fingerprint collation process, the presence or absence of dirt on the finger placement unit is detected, and if there is dirt, the user is required to be uniformly cleaned. Not excellent in properties. In addition, since dirt is detected based on the image information of the entire finger placement unit, the user is required to clean it even though the position or size of the dirt does not hinder the practical use of fingerprint verification. In addition, since a fingerprint image capture operation is requested again, the verification process takes time, and the convenience for the user is not excellent.

  SUMMARY OF THE INVENTION Therefore, an object of the present invention is to provide an image collation apparatus, an image collation method, an image collation program, and a computer-readable recording medium on which an image collation program is recorded that can efficiently perform image collation.

  An image matching device according to an aspect of the present invention includes an element detection unit that detects an element to be excluded from a target to be matched in an image, and a matching process that performs a matching process using an image from which the element detected by the element detection unit is excluded And a feature value detection unit that detects and outputs a feature value corresponding to the pattern of the partial image corresponding to each of the plurality of partial images in the image. The element is detected as a region indicated by a combination of partial images having predetermined feature values output by the unit.

  Preferably, the image indicates a fingerprint image, and the feature value output by the feature value detection unit is a value indicating that the pattern of the partial image follows the vertical direction of the fingerprint, a value indicating that the pattern of the fingerprint follows the horizontal direction, and It is classified as a value indicating other.

  Preferably, the image represents a fingerprint image, and the feature value output by the feature value detection unit is a value indicating that the pattern of the partial image follows the right diagonal direction of the fingerprint, and a value indicating that the partial image pattern follows the left diagonal direction of the fingerprint. , And values indicating other.

Preferably, the predetermined feature value indicates another value.
Preferably, the combination indicates a set of partial images located adjacent to each other in a predetermined direction in which the feature value indicates another value.

  Preferably, the collation processing unit detects the position of the region having the highest degree of coincidence with the partial region in the first image among the first image and the second image to be collated, and detects the element in the second image. A position search unit for searching in a partial region excluding the region of the element detected by the unit, a reference position for measuring the position of the region in the first image, and a maximum matching score position searched by the position search unit A similarity calculation unit that calculates and outputs the similarity between the first image and the second image based on the positional relationship amount indicating the positional relationship, and the first image matches the second image based on the given similarity. And a determination unit for determining whether or not.

  Preferably, the position search unit searches for the maximum matching position corresponding to each of the partial images in the partial region excluding the region of the element detected by the element detection unit in the second image, and the similarity calculation unit Outputs the number of partial images indicating that the positional relation amount between the corresponding maximum matching position searched by the position search unit and the reference position among the partial images in the second image is smaller than a predetermined amount as the similarity To do.

Preferably, the positional relationship amount indicates the direction and distance of the maximum matching position with respect to the reference position.
Preferably, the sum of the maximum matching degrees for the partial images having a positional relation amount smaller than a predetermined amount is output as the similarity.

  Preferably, an image input unit that inputs an image and a registered image storage unit that stores images of a plurality of partial areas that are registered in advance, and the partial image of the first image is read from the registered image storage unit, The other image is input by the image input unit.

  Preferably, the image input unit has a reading surface on which an object is placed and an image is read from the placed object.

  According to another aspect of the present invention, an image collation method for collating an image using a computer includes an element detection step for detecting an element to be excluded from a collation target in the image and an element detected by the element detection step. A collation processing step for performing collation processing using an image, and a feature value detection step for detecting and outputting a feature value corresponding to the pattern of the partial image corresponding to each of the plurality of partial images in the image, In the element detection step, an element is detected as an area indicated by a combination of partial images having a predetermined feature value output by the feature value calculation step.

  When the further another situation of this invention is followed, the image collation program for making a computer perform the above-mentioned image collation method is provided.

  According to still another aspect of the present invention, a computer-readable recording medium recording an image collation program for causing a computer to execute the above-described image collation method is provided.

  According to the invention, when a feature value corresponding to the pattern of each partial image is detected corresponding to each of the plurality of partial images in the image to be collated, a combination of the partial images having a predetermined feature value is used. An element that is a region to be shown is detected, and collation processing is performed using an image from which the detected element is excluded.

  Therefore, since elements that should not be verified are detected and the detected elements are excluded, image verification is performed, so even if there are elements that cannot be verified due to noise components such as dirt, image verification Can continue without interruption. Therefore, many images per unit time can be collated, and high collation processing efficiency can be obtained.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
(Embodiment 1)
FIG. 1 is a block diagram of an image matching apparatus 1 according to the first embodiment. FIG. 2 is a configuration diagram of a computer on which the image collating apparatus according to each embodiment is mounted. Referring to FIG. 2, the computer includes an image input unit 101, a display 610 made up of a CRT (cathode ray tube) or liquid crystal, a CPU (Central Processing Unit) 622 for centrally managing and controlling the computer itself, ROM ( A memory 624 including a read only memory (RAM) or a random access memory (RAM), a fixed disk 626, and an FD (flexible disk) 632 are detachably mounted, and an FD drive device 630 that accesses the mounted FD 632; A CD-ROM (Compact Disc Read Only Memory) 642 is detachably mounted, and a CD-ROM drive device 640 that accesses the mounted CD-ROM 642, the communication network 300, and communication for communication connection between the computer and the computer. Interface 680, printer 690, and keyboard 650 and mouse An input unit 700 having a 60. These units are connected for communication via a bus.

  The computer may be provided with a magnetic tape device in which a cassette type magnetic tape is detachably mounted to access the magnetic tape.

  Referring to FIG. 1, the image collation apparatus includes an image input unit 101, a memory 102 corresponding to the memory 624 or fixed disk 626 in FIG. The memory 102 includes a reference memory 1021, a calculation memory 1022, a captured image memory 1023, a reference partial image feature value calculation result memory 1024, and a captured image partial image feature value calculation result memory 1025. The matching processing unit 11 includes an image correcting unit 104, a partial image feature value calculating unit (hereinafter referred to as a feature value calculating unit) 1045, a non-matching target image element determining unit (hereinafter referred to as an element determining unit) 1047, and a maximum matching position searching unit 105. , A similarity calculation unit (hereinafter referred to as a similarity calculation unit) 106 based on a movement vector, a matching determination unit 107, and a control unit 108. The functions of each unit of the verification processing unit 11 are realized by executing a corresponding program.

  The image input unit 101 includes a fingerprint sensor 100 and outputs fingerprint image data corresponding to the fingerprint read by the fingerprint sensor 100. Any one of an optical type, a pressure type, a capacitance type, and the like may be applied to the fingerprint sensor 100.

  The memory 102 stores image data and various calculation results, the reference memory 1021 stores a plurality of partial areas of the template fingerprint image, and the calculation memory 1022 stores various calculation results. Fingerprint image data output from the image input unit 101 is stored in the captured image memory 1023. The reference partial image feature value calculation result memory 1024 and the captured image partial image feature value calculation result memory 1025 are described later. The calculation result of the feature value calculation unit 1045 is stored. The bus 103 is used to transfer control signals and data signals between the units.

  The image correction unit 104 performs density correction on the fingerprint image data input from the image input unit 101.

  A feature value calculation unit 1045 detects a value corresponding to a pattern exhibited by the partial image for each of a plurality of partial region images set in the image, and calculates a result corresponding to the reference memory as a partial image feature value Are output to the reference partial image feature value calculation result memory 1024, and the calculation results corresponding to the captured image memory are output to the captured image partial image feature value calculation result memory 1025, respectively.

  The element determination unit 1047 refers to the captured image partial image feature value memory 1025 when determining the non-matching target image element, and performs matching by combining the partial image feature values of the partial images at a specific portion of the image. A non-target image element is determined.

  The maximum matching position search unit 105 is a so-called template matching unit. That is, with reference to the determination information calculated by the element determination unit 1047, the verification target partial image is limited, and the search range is further reduced according to the partial image feature value calculated by the feature value calculation unit 1045. Thus, using a plurality of partial regions of one fingerprint image as a template, a position with the highest degree of matching is searched for in the template and the other fingerprint image.

  The similarity calculation unit 106 uses the result information of the maximum matching position search unit 105 stored in the memory 102 to calculate a similarity based on a movement vector described later. The collation determination unit 107 determines match / mismatch based on the similarity calculated by the similarity calculation unit 106. The control unit 108 controls processing of each unit of the verification processing unit 11.

  FIG. 3 shows an example in which the configuration of the fingerprint sensor 100 is assumed to be a capacitance type sensor. As shown, the fingerprint sensor 100 includes a sensor circuit 203, a fingerprint reading surface 201, and a plurality of electrodes 202. As shown in the figure, when a user's finger 301 having a fingerprint to be collated is placed on the fingerprint reading surface 201 of the fingerprint sensor 100, a capacitor 302 is formed between each sensor electrode 202 and the finger 301. The At this time, since the distance between the finger 301 and each sensor electrode 202 is different due to the unevenness of the fingerprint placed on the reading surface 201 of the finger 301, the capacitance of each capacitor 302 formed is different. The sensor circuit 203 detects the difference in capacitance of each capacitor 302 based on the output voltage level of the electrode 202, converts it into a voltage signal indicating the difference, amplifies it, and outputs it. As described above, the voltage signal output from the sensor circuit 203 indicates a signal corresponding to an image showing the uneven state of the fingerprint placed on the fingerprint reading surface 201.

  In the image collating apparatus 1 in FIG. 1, a procedure for collating an image (image data) A and an image (image data) B corresponding to two fingerprint images input from the image input unit 101 in order to collate two fingerprint images. Will be described with reference to the flowchart of FIG.

  First, the control unit 108 sends an image input start signal to the image input unit 101, and then waits until an image input end signal is received. The image input unit 101 inputs an image A to be collated, and stores the input image A at a predetermined address in the memory 102 through the bus 103 (step T1). In this embodiment, it is assumed that data is stored at a predetermined address in the reference memory 1021. The image input unit 101 sends an image input end signal to the control unit 108 after the input of the image A is completed.

  When receiving the image input end signal, the control unit 108 sends an image input start signal to the image input unit 101 again, and then waits until an image input end signal is received. The image input unit 101 inputs an image B to be collated, and stores the input image B through the bus 103 at a predetermined address in the memory 102 (step T1). In this embodiment, it is assumed that data is stored at a predetermined address in the captured image memory 1023. The image input unit 101 sends an image input end signal to the control unit 108 after the input of the image B is completed.

  Next, the control unit 108 sends an image correction start signal to the image correction unit 104, and then waits until an image correction end signal is received. In many cases, the image quality of the input image is not uniform because the density value of each pixel and the overall density distribution change with respect to the characteristics of the image input unit 101, the degree of dryness of the finger skin, and the pressure with which the finger is pressed. It is not appropriate to use input image data as it is for collation. The image correction unit 104 corrects the image quality of the input image so as to suppress fluctuations in conditions during image input (step T2). Specifically, for the entire image corresponding to the input image data or for each small area obtained by dividing the image, histogram flattening (“Introduction to computer image processing”, Soken publication P98) and image binarization processing (“computer image processing”). The “Introduction” Soken publication P66-69) is applied to the images A and B stored in the memory 102, that is, stored in the reference memory 1021 and the captured image memory 1023.

  The image correction unit 104 sends an image correction processing end signal to the control unit 108 after the image correction processing for the images A and B is completed.

  Thereafter, the partial image feature value calculation process (step T25a) is performed by the feature value calculation unit 1045 on the image subjected to the image correction process by the image correction unit 104. Thereafter, the non-collation target image element determination process is performed by the element determination unit 1047 (step T25b), the similarity calculation by the similarity calculation unit 106 and the collation determination by the collation determination unit 107 are performed (step T3). The result is output from the printer 690 or the display 610 (step T4). Details of the processes of steps T25a, T25b, and T3 will be described later.

(Calculation of partial image feature values)
Next, the procedure for calculating the feature value of the partial image in step T25a will be described.

<Three feature values>
First, a case where three types of feature values are taken will be described. FIG. 5 is a diagram in which the maximum value of the number of pixels in the horizontal and vertical directions is described for each partial image for each of the images A and B to be verified. Here, the images A and B and the partial image are assumed to be rectangular planar images corresponding to the two-dimensional coordinate space defined by the orthogonal X axis and Y axis. The partial image in FIG. 5 is composed of 16 pixels × 16 pixels having 16 pixels in both the horizontal direction according to the X axis and the vertical direction according to the Y axis.

  In the partial image feature value calculation according to the first embodiment, a value corresponding to the pattern of a calculation target partial image is calculated as a partial image feature value. That is, the maximum continuous black pixel number maxhlen in the horizontal direction and the maximum continuous black pixel number maxvlen in the vertical direction are detected, and the detected maximum continuous black pixel number maxhlen in the horizontal direction (the tendency that the pattern follows the horizontal direction (for example, horizontal stripes) )) And the maximum number of continuous black pixels maxvlen in the vertical direction (value indicating the tendency of the pattern to follow the vertical direction (for example, the tendency to be vertical stripes)) As a result of comparison, when a relatively large direction is determined to be a horizontal direction, a value “H” indicating horizontal (horizontal stripes) is used. When a vertical direction is determined, a value indicating vertical (vertical stripes) is determined. If it is determined that “V” is other, “X” is output.

  Referring to FIG. 5, the maximum number of continuous black pixels maxhlen is the maximum black among the numbers of continuous black (hatched lines in the figure) detected for each of 16 rows of n = 0 to 15 in the horizontal direction. Refers to the number of pixels. The number of continuous black pixels detected for a row refers to the maximum number of continuous black pixels detected from a portion where one or more black pixels included in the row are continuous. The maximum number of continuous black pixels maxvlen indicates the maximum number of black pixels among the number of continuous black (hatched lines in the figure) detected for each of 16 columns of m = 0 to 15 in the vertical direction. . The number of continuous black pixels detected for a column refers to the maximum number of continuous black pixels detected from a portion where one or more black pixels included in the column are continuous.

  However, even if it is determined as “H” or “V” in the above, the maximum continuous black pixel numbers maxhlen and maxvlen respectively indicate the lower limit values hlen0 and vlen0 set in advance for each direction. If it is determined that it is not, “X” is output. If these conditions are expressed as an expression, “H” is output if maxhlen> maxvlen and maxhlen ≧ hlen0, “V” is output if maxvlen> maxhlen and maxvlen ≧ vlen0, and “X” is output otherwise. .

  FIG. 6 shows a flowchart of the partial image feature value calculation process according to the first embodiment of the present invention. This flowchart is repeated for each partial image Ri, which is an image of N partial areas of the reference image in the reference memory 1021 to be calculated, and the calculation result value is associated with each partial image Ri and the reference partial image. It is stored in the feature value calculation result memory 1024. Similarly, the n partial images Ri of the captured image B in the captured image memory 1024 are repeated, and the calculation result value is associated with each partial image Ri and the captured image partial image feature value calculation result memory 1025. Stored in

  First, the control unit 108 sends a partial image feature value calculation start signal to the feature value calculation unit 1045, and then waits until a partial image feature value calculation end signal is received. The feature value calculation unit 1045 reads the partial image Ri of the calculation target image from the reference memory 1021 or the captured image memory 1023, and temporarily stores it in the calculation memory 1022 (step S1). The feature value calculation unit 1045 reads the stored partial image Ri, and obtains the maximum continuous black pixel number maxhlen in the horizontal direction and the maximum continuous black pixel number maxvlen in the vertical direction (step S2). Here, a process for obtaining the maximum continuous black pixel number maxhlen in the horizontal direction and the maximum continuous black pixel number maxvlen in the vertical direction will be described with reference to FIGS.

  FIG. 7 is a flowchart of the process (step S2) for obtaining the maximum horizontal continuous black pixel number maxhlen in the partial image feature value calculation process (step T2a) according to the first embodiment of the present invention. The feature value calculation unit 1045 reads the partial image Ri from the calculation memory 1022 and initializes the maximum continuous black pixel number maxhlen in the horizontal direction and the pixel counter j in the vertical direction, that is, maxhlen = 0, j = 0. (Step SH001).

  Next, the value of the pixel counter j in the vertical direction is compared with the value of the variable n indicating the maximum number of pixels in the vertical direction (step SH002). If j ≧ n, then step SH016 is executed, otherwise Next, step SH003 is executed. In the first embodiment, n = 16, and j = 0 at the start of processing, so the process proceeds to step SH003.

  In step SH003, initialization of the horizontal pixel counter i, the previous pixel value c, the current pixel continuation number len, and the maximum black pixel continuation number max in the current row, i.e., i = 0, c = 0, len = 0 and max = 0 (step SH003). Next, the horizontal pixel counter i is compared with the horizontal maximum pixel number m (step SH004). If i ≧ m, step SH011 is executed next, and otherwise, step SH005 is executed next. In the first embodiment, since m = 16 and i = 0 at the start of processing, the process proceeds to step SH005.

  In step SH005, the previous pixel value c is compared with the pixel value pixel (i, j) of the coordinate (i, j) currently being compared. If c = pixel (i, j), step SH006 is executed. Otherwise, execute step SH007. In the first embodiment, since c is initialized and 0 (white pixel) and pixel (0,0) is 0 (white pixel) with reference to FIG. 5, c = pixel (i, When it is determined that j) is satisfied (Y in step SH005), the process proceeds to step SH006.

  In step SH006, len = len + 1 is executed. In the first embodiment, len = 0 is set by initialization, so 1 is added and len = 1. Next, the process proceeds to step SH010.

  In step SH010, i = i + 1, that is, the value of the pixel counter i in the horizontal direction is incremented by one. Here, i = 0 is set by initialization, and 1 is added to i = 1. Next, the process returns to step SH004. Thereafter, the pixel values in the 0th row, that is, pixel (i, 0) are all white pixels with reference to FIG. 5, and therefore, steps SH004 to SH010 are repeated until i = 15. The respective values when i = 16 after the processing of step SH010 are i = 16, c = 0, and len = 15. Next, the process proceeds to step SH004 in this state. Since m = 16 and i = 16, the process further proceeds to step SH011.

  In step SH011, if c = 1 and max <len, step SH012 is executed, otherwise, step SH013 is executed. At this time, since c = 0, len = 15, and max = 0, the process proceeds to step SH013.

  In step SH013, the horizontal maximum continuous black pixel number maxhlen in the previous row is compared with the maximum continuous black pixel number max in the current row. If maxhlen <max, step SH014 is executed, otherwise Step SH015 is executed. Since maxhlen = 0 and max = 0 at the present time, the process proceeds to step SH015.

  In step SH015, j = j + 1, that is, the value of the pixel counter j in the vertical direction is incremented by one. Since j = 0 at the present time, j = 1 and the process returns to SH002.

  Thereafter, the processing of steps SH002 to SH015 is repeated in the same manner for j = 1 to 15, and when j = 16 after the processing of step SH015, the value of the vertical pixel counter j and the vertical direction are then reached in step SH002. Is compared with the value of the maximum number of pixels n. As a result of the comparison, if j ≧ n, step SH016 is executed next. If not, step SH003 is executed next. Since j = 16 and n = 16 at the present time, the process proceeds to step SH016.

  In step SH016, maxhlen is output. With reference to the above description and FIG. 5, maxhlen is the maximum number of continuous black pixels in the horizontal direction. 15 is stored, and maxhlen = 15 is output.

  Next, the flowchart of the process (step S2) for obtaining the maximum continuous black pixel number maxvlen in the vertical direction in the partial image feature value calculation process (step T2a) according to the first embodiment of the present invention will be described. Since it is clear that the processing of steps SV001 to SV016 in FIG. 8 is basically the same as the flowchart in FIG. 7 described above, the processing content can be easily understood from the description in FIG. Therefore, the detailed description of FIG. 8 is omitted. As a result of executing the processing according to the flowchart of FIG. 8, the maximum number of continuous black pixels maxvlen output in the vertical direction indicates 4 which is the maximum value in the x direction, as shown in FIG.

  Processing subsequent to referring to maxhlen and maxvlen output in the above procedure will be described with reference to step S3 and subsequent steps in FIG.

  In step S3, maxhlen and maxvlen are compared with a predetermined maximum continuous black pixel number lower limit hlen0, and if it is determined that the conditions of maxhlen> maxvlen and maxhlen ≧ hlen0 are satisfied (Y in step S3), the next Step S7 is executed, and if it is determined that it does not hold (N in Step S3), then Step S4 is executed. At this time, assuming that maxhlen = 14 and maxvlen = 4, and further assuming that the lower limit value hlen0 is 2, the condition is satisfied, and the process proceeds to step S7. In step S7, “H” is stored in the feature value storage area of the partial image Ri for the original image in the reference partial image feature value calculation result memory 1024 or the captured image partial image feature value calculation result memory 1025; A partial image feature value calculation end signal is sent to the control unit 108.

  If the lower limit value hlen0 is assumed to be 15, it is determined that the condition of step S3 is not satisfied, and the process then proceeds to step S4. In step S4, it is determined whether or not the conditions of maxvlen> maxhlen and maxvlen ≧ vlen0 are satisfied. If it is determined that the condition is established (Y in step S4), the process of step S5 is executed next. If it is determined that the condition is not established, the process of step S6 is executed next.

  In this case, assuming that maxhlen = 15, maxvlen = 4, and vlen0 = 5, the condition is not satisfied, and the process proceeds to step S6. In step S6, “X” is stored in the feature value storage area of the partial image Ri for the original image in the reference partial image feature value calculation result memory 1024 or the captured image partial image feature value calculation result memory 1025; A partial image feature value calculation end signal is sent to the control unit 108.

  Assuming that the output values of step S2 are maxhlen = 4 and maxvlen = 10 and hlen0 = 2 and vlen0 = 12, the condition of step S3 is not satisfied, and further, the condition of step S4 is not satisfied. The process of step S5 is executed. In step S5, “V” is stored in the feature value storage area of the partial image Ri for the original image in the reference partial image feature value calculation result memory 1024 or the captured image partial image feature value calculation result memory 1025, and control is performed. A partial image feature value calculation end signal is sent to the unit 108.

  As described above, the feature value calculation unit 1045 according to the first embodiment extracts (specifies) each pixel column in the horizontal direction and the vertical direction from the partial image Ri (see FIG. 5) of the calculation target image. Based on the number of black pixels in each pixel row, the pattern of the partial image has a tendency to follow a horizontal direction (for example, a tendency to be a horizontal stripe), or a tendency to follow a vertical direction (for example, a tendency to be a vertical stripe), or It is determined that it is neither of them, and a value (any one of “H”, “V”, and “X”) corresponding to the determination result is output. This output value indicates the feature value of the partial image Ri. Here, the feature value is obtained based on the number of continuous black pixels, but the feature value can be obtained similarly based on the number of continuous white pixels.

<Other examples of three types of feature values>
Next, another example of the three types of partial image feature values will be described. An outline of the partial image feature value calculation for this purpose will be described with reference to FIGS. 9A to 9F are diagrams showing the total number of black pixels (shaded portions in the drawing) and white pixels (white background portion in the drawing) with respect to the partial image Ri of the image. The partial image Ri in these drawings is composed of a partial region of 16 pixels × 16 pixels having 16 pixels in both the horizontal direction and the vertical direction. 9A to 9F, each partial image indicates a planar image corresponding to a two-dimensional coordinate space defined by the orthogonal i-axis and j-axis.

  Here, for the calculation target partial image Ri in FIG. 9A, the increase amount hcnt of the number of black pixels when the calculation target partial images are shifted one pixel to the left and right as shown in FIG. The amount of increase vcnt of the number of black pixels when the calculation target partial images are shifted one pixel up and down as in 9 (C) is obtained, and the obtained amount of increase hcnt is compared with the amount of increase vcnt. If hcnt is larger than twice the increase amount vcnt, a value “H” meaning horizontal is output, and if the increase amount hcnt is larger than twice the increase amount vcnt, a value “V” meaning vertical is output. Other examples are similarly shown in FIGS. 9D to 9F.

  Here, the “increase amount of black pixels when the image is shifted one pixel to the left and right and overlapped” shown in FIGS. 9A to 9C is “each pixel of the original image (16 × 16 pixels)”. If the coordinates of (i, j) are (i, j), the original image is moved by +1 pixel parallel to the i-axis so that the coordinates (i, j) are (i + 1, j) for all pixels. And an image obtained by moving the original image by −1 pixel parallel to the i axis so that the coordinates (i, j) are (i−1, j) for all the pixels. The total number of black pixels of the image (16 × 16 pixels) obtained by superimposing the image and the original image so that the pixels with the same coordinates (i, j) match, and the total number of black pixels of the original image Point of difference ”.

  Here, the “increase amount of black pixels when the image is shifted one pixel up and down and overlapped” shown in FIGS. 9D to 9F is “each pixel of the original image (16 × 16 pixels)”. If the coordinates of (i, j) are (i, j), the original image is moved +1 pixel parallel to the j-axis so that the coordinates (i, j) are (i, j + 1) for all pixels And an image obtained by moving the original image by −1 pixel parallel to the j axis so that the coordinates (i, j) become (i, j−1) for all the pixels. The total number of black pixels of the image (16 × 16 pixels) obtained by superimposing the image and the original image so that the pixels with the same coordinates (i, j) match, and the total number of black pixels of the original image Point of difference ”.

  In these cases, when a black pixel overlaps in a certain pixel, the certain pixel becomes a black pixel, and when a white pixel and a black pixel overlap each other, the certain pixel becomes a black pixel. When these overlap, the certain pixel becomes a white pixel.

  Next, details of the partial image feature value calculation processing will be described with reference to the flowchart of FIG. This flowchart is repeated for each of the N partial images Ri of the reference image A in the reference memory 1021 to be calculated, and the calculation result value is associated with each partial image Ri and the reference partial image feature value calculation result memory. Stored in 1024. Similarly, the N partial images Ri of the captured image B in the captured image memory 1024 are respectively repeated, and the calculation result value is associated with each partial image Ri and the captured image partial image feature value calculation result memory. 1025.

  First, the control unit 108 sends a partial image feature value calculation start signal to the feature value calculation unit 1045, and then waits until a partial image feature value calculation end signal is received.

  The feature value calculation unit 1045 reads the partial image Ri (see FIG. 9A) of the calculation target image from the reference memory 1021 or the captured image memory 1023, and temporarily stores it in the calculation memory 1022 (step ST1). The partial image feature value calculation unit 1045 reads the stored partial image Ri, and increases when hcnt is shifted left and right as shown in FIG. 9B and increased when it is shifted up and down as shown in FIG. 9C. The amount vcnt is obtained (step ST2).

  Processing for obtaining the increase amount hcnt and the increase amount vcnt will be described with reference to FIGS. 11 and 12. FIG. 11 is a flowchart of a process (step ST2) for obtaining the increase amount hcnt. FIG. 12 is a flowchart of the process for obtaining the increase amount vcnt (step ST2).

  Referring to FIG. 11, feature value calculation unit 1045 reads partial image Ri from calculation memory 1022 and initializes pixel counter j in the vertical direction, that is, sets j = 0 (step SHT01). Next, the pixel counter j in the vertical direction is compared with the maximum number n of pixels in the vertical direction (step SHT02). If j> n, next step SHT10 is executed, and otherwise, step SHT03 is executed. Here, n = 16, and at the start of processing, since j = 0, the process proceeds to step SHT03.

  In step SHT03, the horizontal pixel counter i is initialized, i.e., i = 0. Next, the value of the pixel counter i in the horizontal direction is compared with the maximum number of pixels m in the horizontal direction (step SHT04). If i> m, next step SHT05 is executed, otherwise, step SHT06 is executed next. To do. Here, since m = 16 and i = 0 at the start of processing, the process proceeds to step SHT06.

  In step SHT06, the partial image Ri is read and the pixel value pixel (i, j) of the coordinate (i, j) currently being compared is 1 (black pixel) or the coordinate (i, j) The pixel value pixel (i-1, j) of the left coordinate (i-1, j) in the horizontal direction is 1 or the right one in the horizontal direction from the coordinate (i, j) It is determined whether or not the pixel value pixel (i + 1, j) of the coordinates (i + 1, j) is 1. If pixel (i, j) = 1 or pixel (i-1, j) = 1 or pixel (i + 1, j) = 1, then execute step SHT08, otherwise execute next step SHT07 To do.

  Here, the range of one pixel in the upper, lower, left, and right sides of the partial image Ri, that is, Ri (-1 to m + 1, -1), Ri (-1, -1 to n + 1), Ri (m + 1, The pixel values in the range of −1 to n + 1) and Ri (−1 to m + 1, n + 1) are set to 0 (white pixel) as shown in FIG. Here, referring to FIG. 9A, since pixel (0,0) = 0, pixel (-1,0) = 0, and pixel (1,0) = 0, the process proceeds to step SHT07.

  In step SHT07, 0 is stored in the pixel value work (i, j) (see FIG. 10C) of the coordinates (i, j) of the image WHi that is stored in the calculation memory 1022 and shifted one pixel to the left and right. To do. That is, work (0, 0) = 0. Next, the process proceeds to step SHT09.

  In step SHT09, i = i + 1, that is, the horizontal pixel counter i is incremented by one. Here, i = 0 is obtained by initialization, and 1 is added to i = 1. Next, the process returns to step SHT04. Thereafter, since the pixel values of the 0th row, that is, pixel (i, 0) are all white pixels with reference to FIG. 9A, steps SHT04 to SHT09 are performed until i = 15. Repeatedly, i = 16 after the processing of step SHT09. In this state, the process proceeds to SHT04. Since m = 16 and i = 16, the process proceeds to step SHT05.

In step SHT05, j = j + 1, that is, the pixel counter j in the vertical direction is incremented by one. At this time, since j = 0, j = 1 and the process returns to SHT02. Here, since it is the start of a new line, the process proceeds to step SHT03 and step SHT04 as in the case of the 0th line. Thereafter, steps SHT04 to SHT09 are repeated until the pixel in the 14th column of the first row where pixel (i + 1, j) = 1, that is, i = 14, j = 1. After step SHT09, i = 14. Since m = 16 and i = 14, the process proceeds to SHT06.

  In step SHT06, since pixel (i + 1, j) = 1, that is, pixel (14 + 1,1) = 1, the process proceeds to step SHT08.

  In step SHT08, 1 is stored in the pixel value work (i, j) of the coordinates (i, j) of the image WHi (see FIG. 9B) which is stored in the calculation memory 1022 and shifted one pixel to the left and right. To do. That is, work (14, 1) = 1.

  When the process proceeds to step SHT09, i = 16 and the process proceeds to step SHT04, m = 16 and i = 16, so the process proceeds to step SHT05, j = 2, and the process proceeds to step SHT02. Thereafter, the processing of steps SHT02 to SHT09 is repeated in the same manner for j = 2 to 15. When j = 16 is obtained after the processing of step SHT09, the vertical value of the pixel counter j in the vertical direction is next vertical in step SHT02. The maximum number of pixels n in the direction is compared. If j ≧ n, next step SHT10 is executed, and otherwise, step SHT03 is executed next. Since j = 16 and n = 16 at the present time, the process proceeds to step SHT10. At this time, the calculation memory 1022 stores an image WHi that is shifted by one pixel to the left and right as shown in FIG. 9B based on the partial image Ri that is currently being compared.

  In step SHT10, the pixel value work (i, j) of the image WHi, which is stored in the calculation memory 1022 and shifted one pixel to the left and right, and the pixel value pixel (i, j) of the partial image Ri currently being compared and compared. ) Difference cnt. The process for calculating the difference cnt between work and pixel will be described with reference to FIG.

  FIG. 13 shows the pixel value pixel (i, j) of the partial image Ri currently being compared and the pixel value work (i, j) of the image WHi obtained by shifting the partial image Ri one pixel at a time from left to right or up and down. It is a flowchart which calculates difference cnt with j). The feature value calculation unit 1045 reads the image WHi superimposed on the partial image Ri one pixel at a time from the calculation memory 1022, and initializes the difference counter cnt and the vertical pixel counter j, that is, cnt = 0, j = 0 is set (step SC001). Next, the value of the pixel counter j in the vertical direction is compared with the maximum number n of pixels in the vertical direction (step SC002). If j ≧ n, the process returns to the flowchart of FIG. 11 and cnt is substituted for hcnt in step SHT11. Otherwise, step SC003 is executed next.

  Here, since n = 16 and j = 0 at the start of processing, the process proceeds to step SC003. In step SC003, the horizontal pixel counter i is initialized, i.e., i = 0. Next, the value of the pixel counter i in the horizontal direction is compared with the maximum number of pixels m in the horizontal direction (step SC004). If i ≧ m, next step SC005 is executed, otherwise, step SC006 is executed next. To do. Here, since m = 16 and i = 0 at the start of processing, the process proceeds to step SC006.

  In step SC006, the pixel value pixel (i, j) of the partial image Ri of the coordinates (i, j) that is currently the comparison target is 0 (white pixel), and the image WHi is overlaid by shifting one pixel at a time. Whether pixel value work (i, j) is 1 (black pixel), and if pixel (i, j) = 0 and work (i, j) = 1, then step SC007 is executed and the others Then, step SC008 is executed. Here, referring to FIG. 9A and FIG. 9B, pixel (0,0) = 0 and work (0,0) = 0, so the process proceeds to step SC008.

  In step SC008, i = i + 1, that is, the horizontal pixel counter i is incremented by one. Here, i = 0 is set by initialization, and 1 is added by adding 1. Next, the process returns to step SC004. Thereafter, since the pixel values of the 0th row, that is, pixel (i, 0) and work (i, 0) are all white pixels with reference to FIG. 9 (A) and FIG. 9 (B), Steps SC004 to SC008 are repeated until i = 15, and the respective values when i = 16 after the processing of step SC008 are cnt = 0 and i = 16. In this state, the process proceeds to SC004. Since m = 16 and i = 16, the process proceeds to step SC005.

  In step SC005, j = j + 1, that is, the vertical pixel counter j is incremented by one. At this time, since j = 0, j = 1 and the process returns to SC002. Here, since it is the start of a new line, the process proceeds to step SC003 and step SC004 as in the 0th line. Thereafter, the pixels in the 14th column of the first row where pixel (i, j) = 0 and work (i, j) = 1, that is, steps SC004 to SC008 are performed until i = 15 and j = 1. Repeatedly, i = 15 after the process of step SC008. Since m = 16 and i = 15, the process proceeds to SC006.

  In step SC006, since pixel (i, j) = 0 and work (i, j) = 1, that is, pixel (14, 1) = 0 and work (14, 1) = 1, the process proceeds to step SC007.

  In step SC007, cnt = cnt + 1, that is, the value of the difference counter cnt is incremented by one. Here, cnt = 0 is set by initialization, and 1 is added to set cnt = 1. Next, the process proceeds to step SC008, i = 16, and the process proceeds to step SC004. Since m = 16 and i = 16, the process proceeds to step SC005, j = 2, and the process proceeds to step SC002.

  Thereafter, the processing of steps SC002 to SC009 is repeated in the same manner for j = 2 to 15. When j = 15 after the processing of step SC008, the value of the vertical pixel counter j and the vertical direction are next determined in step SC002. The maximum number of pixels n is compared. If j ≧ n, the process returns to the flowchart of FIG. 11 to execute step SHT11. Otherwise, step SC003 is executed. At this time, since j = 16 and n = 16, the flowchart of FIG. 12 is terminated, and then the process returns to the flowchart of FIG. 11 and proceeds to step SHT11. At present, the difference counter cnt = 21.

  In step SHT11, hcnt = cnt, that is, the value of the difference cnt calculated in the flowchart of FIG. Next, the process proceeds to step SHT12. In step SHT12, an increase amount hcnt = 21 when shifted left and right is output.

  Next, the processing of steps SVT01 to SVT12 of FIG. 12 of the processing (step ST2) for obtaining the increase amount vcnt when shifted up and down in the feature value calculation processing (step T2a) of FIG. 10 is described above with reference to FIG. It is clear that basically the same processing is performed, and detailed description is omitted.

  As the amount of increase vcnt when shifted up and down, 96 is output which is the difference between the image WVi and the partial image Ri of FIG. The

  The subsequent processing for the output hcnt and vcnt will be described by returning to step ST3 and subsequent steps in FIG.

  In step ST3, hcnt and vcnt are compared with the maximum black pixel number increase lower limit value vcnt0 in the vertical direction. If the condition of vcnt> 2 × hcnt and vcnt ≧ vcnt0 is satisfied, then step ST7 is executed. If not, step ST4 is executed next. At this time, assuming that vcnt = 96, hcnt = 21, and vcnt0 = 4, the process proceeds to step ST7. In step ST7, “H” is stored in the feature value storage area of the partial image Ri for the original image in the reference partial image feature value calculation result memory 1024 or the captured image partial image feature value calculation result memory 1025. Then, a partial image feature value calculation end signal is sent to the control unit 108.

  If it is assumed that the output values of step ST2 are vcnt = 30, hcnt = 20 and vcnt0 = 4, the condition of step ST3 is not satisfied, so the process proceeds to step ST4. In step ST4, if it is determined that the conditions of hcnt> 2 × vcnt and hcnt ≧ hcnt0 are satisfied, step ST5 is executed next. If it is determined that the conditions are not satisfied, step ST6 is then executed.

  In step ST6, the reference partial image feature value calculation result memory 1024 or the captured image partial image feature value calculation result memory 1025 stores “X” in the feature value storage area of the partial image Ri for the original image. ”And a partial image feature value calculation end signal is sent to the control unit 108.

  Further, assuming that the output values of step ST2 are vcnt = 30, hcnt = 70 and hcnt0 = 4, it is determined in step ST3 that vcnt> 2 × hcnt and vcnt ≧ vcnt0 is not satisfied. Next, step ST4 is executed. In step ST4, it is determined whether or not the conditions of hcnt> 2 × vcnt and hcnt ≧ hcnt0 are satisfied. If it is determined that it is satisfied, next step ST5 is executed, and if it is determined that it is not satisfied, next step ST6 is executed.

  Here, since it is determined to be established, the process proceeds to step ST5, where the partial image Ri of the reference partial image feature value calculation result memory 1024 or the original image in the captured image partial image feature value calculation result memory 1025 is displayed. “V” is stored in the feature value storage area, and a partial image feature value calculation end signal is sent to the control unit 108.

  In the partial image feature value calculation calculated in this way, when there is noise in the reference image A or the captured image B, for example, a part of the fingerprint image is missing due to finger wrinkles or the like. As shown in FIGS. 9E and 9F, even if the image has a vertical wrinkle at the center of the partial image Ri as shown in FIG. 9D, hcnt = 29 and vcnt = If vcnt0 = 4 and vcnt0 = 4 is set, in step ST3 of FIG. 10, if vcnt> 2 × hcnt and vcnt ≧ vcnt0, then step ST7 is executed and a value “H” meaning horizontal is output. . As described above, the partial image feature value calculation has a feature that the calculation accuracy can be maintained for the noise component included in the image.

  As described above, the feature value calculation unit 1045 obtains, for the partial image Ri, an image WHi that is shifted from the left and right by a predetermined pixel and an image WVi that is shifted from the upper and lower by a predetermined pixel, and further, The increase hcnt of the number of black pixels, which is the difference between the image WHi and the partial image Ri that are shifted one pixel to the left and right, and the black that is the difference between the image WVi and the partial image Ri that are shifted one pixel vertically. An increase amount vcnt of the number of pixels is obtained, and based on the increase amounts, the pattern of the partial image Ri tends to be a pattern that follows the horizontal direction (for example, a tendency to be a horizontal stripe) or a pattern that follows the vertical direction (for example, It is discriminated that it is a vertical stripe) or neither, and a value corresponding to the discrimination result (any one of “H”, “V” and “X”) is output. This output value indicates the feature value of the partial image Ri.

<Further another example of three types of feature values>
The three types of partial image feature values are not limited to those described above, and may be the following three types. An outline of partial image feature value calculation for that purpose will be described with reference to FIGS. FIGS. 14A to 14F are diagrams showing the total number of black pixels and white pixels and the like for the partial image Ri of the image. The partial image Ri in these drawings is composed of a partial region of 16 pixels × 16 pixels having 16 pixels in both the horizontal direction and the vertical direction. In the partial image feature value calculation, the increase amount rcnt of the black pixel when the calculation target partial image Ri is shifted by one pixel in the diagonally rightward direction and overlapped with respect to the calculation target partial image Ri in FIG. (B) hatched portion of the image WHi) and the increase amount lcnt of the number of black pixels when the calculation target partial image is shifted by one pixel in the left diagonal direction (that is, the shaded portion of the image WVi in FIG. 14C) And the obtained increase amount rcnt is compared with the increase amount lcnt. If the increase amount lcnt is larger than twice the increase amount rcnt, the value “R” means the diagonally right, and the increase amount rcnt is the increase amount lcnt. If the value is larger than 2 times, a value “L” meaning left oblique is output, and “X” is output in other cases.

  'The amount of increase in black pixels when the image is shifted one pixel at a time in the diagonally right direction' means "if the coordinates of each pixel in the original image (16 x 16 pixels) are (i, j) The original image is moved so that the coordinates (i, j) are (i + 1, j-1) for all pixels, and the coordinates (i, j) are (i-1) for all pixels. , j + 1), and an image obtained by moving the original image so as to be overlapped, and the generated two images and the original image are overlapped so that the pixels having the same coordinates (i, j) coincide with each other It refers to the difference between the total number of black pixels of the image (16 × 16 pixels) obtained together and the total number of black pixels of the original image ”.

  'The amount of increase in black pixels when the image is shifted one pixel at a time in the left diagonal direction' means "if the coordinates of each pixel in the original image (16 x 16 pixels) are (i, j) The original image is moved so that the coordinates (i, j) are (i-1, j-1) for all the pixels, and the coordinates (i, j) are (i + 1) for all the pixels. , j-1), and an image obtained by moving the original image so that the two images and the original image are overlapped so that the pixels with the same coordinates (i, j) match. It refers to the difference between the total number of black pixels of the image (16 × 16 pixels) obtained together and the total number of black pixels of the original image ”.

  In this case, when a black pixel overlaps a certain pixel, the certain pixel becomes a black pixel. When a white pixel and a black pixel overlap each other, the certain pixel becomes a black pixel. Also, a certain pixel overlaps a white pixel. Then, the certain pixel becomes a white pixel.

  However, even when “R” or “L” is determined as described above, “X” is output if the amount of increase in the number of black pixels is not equal to or lower than the lower limit values lcnt0 to rcnt0 set in advance in both directions. If these conditions are expressed as an expression, “R” is output if (1) lcnt> 2 × rcnt and (2) lcnt ≧ lcnt0 is satisfied, (3) rcnt> 2 × lcnt and (4) rcnt ≧ rcnt0 If the above holds, “L” is output, otherwise “X” is output.

  Here, if the increase amount lcnt is larger than twice the increase amount rcnt, the value “R” that is diagonally right is output. However, the value that is twice the threshold value may be changed to another value. . The same applies to the right diagonal direction. Further, it is known in advance that the image is suitable for collation processing because it is within a certain range (for example, 30% or more and 70% or less of the total number of pixels of the partial image Ri) in the partial image. In such a case, the conditional expressions (2) and (4) may be deleted.

  FIG. 15A is a flowchart of still another partial image feature value calculation process. This flowchart is repeated for each of the N partial images Ri of the reference image A in the reference memory 1021 to be calculated, and the calculation result value is associated with each partial image Ri and the reference partial image feature value calculation result memory. Stored in 1024. Similarly, the N partial images Ri of the captured image B in the captured image memory 1024 are respectively repeated, and the calculation result value is associated with each partial image Ri and the captured image partial image feature value calculation result memory. 1025. Next, details of the partial image feature value calculation processing will be described with reference to FIG.

  The control unit 108 sends a partial image feature value calculation start signal to the feature value calculation unit 1045, and then waits until a partial image feature value calculation end signal is received.

  The feature value calculation unit 1045 reads the partial image Ri (see FIG. 14A) of the calculation target image from the reference memory 1021 or the captured image memory 1023, and temporarily stores it in the calculation memory 1022 (step SM1). The feature value calculation unit 1045 reads the stored partial image Ri, and when it is shifted in the diagonally left direction as shown in FIG. 14C and the increment rcnt when shifted in the diagonally right direction as shown in FIG. The increase amount lcnt is obtained (step SM2).

  A process for obtaining the increase amount rcnt and the increase amount lcnt will be described with reference to FIGS. FIG. 16 is a flowchart of the process (step SM2) for obtaining the increase amount rcnt when shifted in the diagonally right direction in the partial image feature value calculation process (step T2a).

  Referring to FIG. 16, feature value calculation unit 1045 reads partial image Ri from calculation memory 1022, and initializes the value of pixel counter j in the vertical direction, that is, sets j = 0 (step SR01). . Next, the value of the pixel counter j in the vertical direction is compared with the maximum number n of pixels in the vertical direction (step SR02). If the comparison result indicates j ≧ n, then step SR10 is executed, and if not, Next, step SR03 is executed. Here, n = 16, and at the start of processing, since j = 0, the process proceeds to step SR03.

  In step SR03, the value of the pixel counter i in the horizontal direction is initialized, i.e., i = 0. Next, the value of the pixel counter i in the horizontal direction is compared with the maximum number m of pixels in the horizontal direction (step SR04). If the comparison result indicates i ≧ m, then step SR05 is executed, otherwise it is not indicated. Next, step SR06 is executed. In the present embodiment, m = 16, and i = 0 at the start of processing, so the process proceeds to step SR06.

  In step SR06, the partial image Ri is read and the pixel value pixel (i, j) of the coordinate (i, j) currently being compared is 1 (black pixel) or the coordinate (i, j). The pixel value pixel (i + 1, j + 1) of the upper right coordinate (i + 1, j + 1) is 1 or one lower right of the coordinate (i, j) It is determined whether or not the pixel value pixel (i + 1, j-1) at the coordinates (i + 1, j-1) is 1. If it is determined that pixel (i, j) = 1 or pixel (i + 1, j + 1) = 1 or pixel (i + 1, j-1) = 1, then step SR08 is executed, Otherwise, step SR07 is executed next.

  Here, the range of one pixel in the upper, lower, left, and right sides of the partial image Ri, that is, Ri (-1 to m + 1, -1), Ri (-1, -1 to n + 1), Ri (m + 1, The pixel values in the range of −1 to n + 1) and Ri (−1 to m + 1, n + 1) are set to 0 (white pixel) as shown in FIG. Here, referring to FIG. 14A, since pixel (0, 0) = 0, pixel (1, 1) = 0, and pixel (1, −1) = 0, the process proceeds to step SR07.

  In step SR07, the pixel value work (i, j) of the coordinates (i, j) of the image WHi, which is stored in the calculation memory 1022 and shifted one pixel at a time in the diagonally right direction, is set to 0 (see FIG. 15C). Is stored. That is, work (0, 0) = 0. Next, the process proceeds to step SR09.

  In step SR09, i = i + 1, that is, the value of the pixel counter i in the horizontal direction is incremented by one. Here, i = 0 is set by initialization, and 1 is added to i = 1. Next, the process returns to step SR04.

  In step SR05, j = j + 1, that is, the value of the pixel counter j in the vertical direction is incremented by one. At this time, since j = 0, j = 1 and the process returns to SR02. Here, since it is the start of a new line, the process proceeds to step SR03 and step SR04 as in the case of the 0th line. Thereafter, steps SR04 to SR09 are repeated until the pixel of the first column in the first row where pixel (i, j) = 1, i.e., i = 5, j = 1, and i = 5 after the processing of step SR09. It becomes. Since m = 16 and i = 5, the process proceeds to SR06.

  In step SR06, since pixel (i, j) = 1, that is, pixel (5, 1) = 1, the process proceeds to step SR08.

  In step SR08, the pixel value work (i, j) of the coordinates (i, j) of the image WLi (see FIG. 14B) that is stored in the calculation memory 1022 and is shifted one pixel at a time in the diagonally right direction is overlapped. Is stored. That is, work (5, 1) = 1.

  Proceeding to step SR09, i = 16, and proceeding to step SR04. Since m = 16 and i = 16, the process proceeds to step SR05, j = 2, and the process proceeds to step SR02. Thereafter, the processing of steps SR02 to SR09 is repeated in the same manner for j = 2 to 15, and after j = 16 after the processing of step SR09, next, in step SR02, the value of the vertical pixel counter j is The maximum number of pixels n in the direction is compared. If the comparison result indicates j ≧ n, step SR10 is executed next. If not, step SR03 is executed next. Since j = 16 and n = 16 at the present time, the process proceeds to step SR10. At this time, the calculation memory 1022 stores an image WRI that is shifted by one pixel in the diagonally rightward direction as shown in FIG. 14B based on the partial image Ri currently being compared and stored. Yes.

  In step SR10, the pixel value work (i, j) of the image WLi that is stored in the calculation memory 1022 and is shifted by one pixel in the diagonally rightward direction and the pixel value pixel (i) of the partial image Ri that is currently being compared. , J) The difference cnt is calculated. Processing for calculating the difference cnt between work and pixel will be described with reference to FIG.

  FIG. 18 shows the pixel value pixel (i, j) of the partial image Ri that is currently being compared and the pixel value of the image Wri in which the partial image Ri is shifted one pixel at a time in the right diagonal direction or left diagonal direction. It is a flowchart which calculates difference cnt with work (i, j). The feature value calculation unit 1045 reads the image Wri superimposed on the partial image Ri by shifting by one pixel from the calculation memory 1022 and initializes the values of the difference counter cnt and the vertical pixel counter j, that is, cnt = 0. , J = 0 (step SN001). Next, the value of the pixel counter j in the vertical direction is compared with the maximum number of pixels n in the vertical direction (step SN002). If the comparison result indicates j ≧ n, the process returns to the flowchart of FIG. If cnt is substituted for rcnt and if not indicated, then step SN003 is executed.

  Here, n = 16, and at the start of processing, j = 0, so the process proceeds to step SN003. In step SN003, the horizontal pixel counter i is initialized, i.e., i = 0. Next, the value of the pixel counter i in the horizontal direction is compared with the maximum number of pixels m in the horizontal direction (step SN004). If the comparison result indicates i ≧ m, then step SN005 is executed. Next, step SN006 is executed. Here, since m = 16 and i = 0 at the start of processing, the process proceeds to step SN006.

  In step SN006, the pixel value pixel (i, j) of the partial image Ri of the coordinates (i, j) currently being compared is 0 (white pixel), and the image WRI is superimposed by shifting by one pixel. Whether pixel value work (i, j) is 1 (black pixel), and if pixel (i, j) = 0 and work (i, j) = 1, then step SN007 is executed and the others Then, step SN008 is executed next. Here, referring to FIG. 14A and FIG. 14B, since pixel (0,0) = 0 and work (0,0) = 0, the process proceeds to step SN008.

  In step SN008, i = i + 1, that is, the horizontal pixel counter i is incremented by one. Here, i = 0 is set by initialization, and 1 is added by adding 1. Next, the process returns to step SN004. Thereafter, steps SN004 to SN008 are repeated until i = 15, and the process proceeds to SN004 when i = 16 after the processing of step SN008. Since m = 16 and i = 16, the process proceeds to step SN005.

  In step SN005, j = j + 1, that is, the value of the pixel counter j in the vertical direction is incremented by one. At this time, since j = 0, j = 1 and the process returns to SN002. Here, since it is the start of a new line, the process proceeds to step SN003 and step SN004 as in the 0th line. Thereafter, steps SN004 to SN008 are performed until pixel (i, j) = 0 and pixel in the 11th column of the first row where work (i, j) = 1, that is, i = 10 and j = 1. Repeatedly, i = 10 after the processing of step SN008. Since m = 16 and i = 10, the process proceeds to SN006.

  In step SN006, pixel (i, j) = 0 and work (i, j) = 1, that is, pixel (10, 1) = 0 and work (10, 1) = 1, so the process proceeds to step SN007.

  In step SN007, cnt = cnt + 1, that is, the value of the difference counter cnt is incremented by one. Here, cnt = 0 is set by initialization, and 1 is added to set cnt = 1. Thereafter, the process proceeds and proceeds to step SN008, i = 16, and the process proceeds to step SN004. Since m = 16 and i = 16, the process proceeds to step SN005, j = 2, and the process proceeds to step SN002.

  Thereafter, the processing of steps SN002 to SN008 is repeated in the same manner for j = 2 to 15. When j = 16 after the processing of step SN008, the value of the vertical pixel counter j and the vertical direction are next set to step SN002. If the comparison result indicates j ≧ n, the process returns to the flowchart of FIG. 12 and executes step SR11. If not, step SN003 is executed. , J = 16, and n = 16, the flowchart of FIG. 18 is terminated, and then the process returns to the flowchart of FIG. 16 and proceeds to step SR11. At present, the difference counter cnt = 45.

  In step SR11, rcnt = cnt, that is, the value of the difference cnt calculated in the flowchart of FIG. 18 is substituted into the increase amount rcnt when shifted to the right diagonal direction. Next, the process proceeds to step SR12. In step SR12, an increase amount rcnt = 45 when shifted to the right diagonal direction is output.

  Next, the processing of steps SL01 to SL12 in FIG. 17 of the processing (step SM2) for obtaining the increase amount lcnt when shifted in the diagonally leftward direction in the feature value calculation processing (step T2a) in FIG. 18 is described above. It is clear that basically the same processing as that of FIG. 16 is performed, and detailed description thereof is omitted.

  The increase amount lcnt when shifted in the diagonally left direction is the difference between the image WLi shifted by one pixel in the diagonally left direction in FIG. 14C and the partial image Ri in FIG. lcnt = 115 is output.

  The subsequent processing for the output rcnt and lcnt will be described by returning to step SM3 and subsequent steps in FIG.

  In step SM3, rcnt and lcnt are compared with the maximum black pixel number increase lower limit value lcnt0 in the diagonally left direction. If lcnt> 2 × rcnt and lcnt ≧ lcnt0, then step SM7 is executed. Next, step SM4 is executed. At this time, assuming that lcnt = 115 and rcnt = 45 and lcnt0 = 4, the process proceeds to step SM7. In step SM7, “R” is stored in the feature value storage area of the partial image Ri for the original image in the reference partial image feature value calculation result memory 1024 or the captured image partial image feature value calculation result memory 1025. Then, a partial image feature value calculation end signal is sent to the control unit 108.

  If it is assumed that the output value of step SM2 is lcnt = 30, rcnt = 20 and lcnt0 = 4, the process proceeds to step SM4, and if rcnt> 2 × lcnt and rcnt ≧ rcnt0 holds, Step SM5 is executed. If not established, Step SM6 is executed next.

  In step SM6, the reference partial image feature value calculation result memory 1024 or the captured image partial image feature value calculation result memory 1025 stores “X” in the feature value storage area of the partial image Ri for the original image. ”And a partial image feature value calculation end signal is sent to the control unit 108.

  Further, assuming that the output value of step SM2 is lcnt = 30, rcnt = 70, lcnt0 = 4, rcnt0 = 4, the condition of lcnt> 2 × rcnt and lcnt ≧ lcnt0 is satisfied in step SM3. Therefore, the process proceeds to step SM4. If rcnt> 2 × lcnt and rcnt ≧ rcnt0, which are the conditional expressions of step SM4, are satisfied, then step SM5 is executed, and if not, step SM6 is executed next.

  In step SM5, the reference partial image feature value calculation result memory 1024 or the captured image partial image feature value calculation result memory 1025 stores “L” in the feature value storage area of the partial image Ri for the original image. ”And a partial image feature value calculation end signal is sent to the control unit 108.

  In the above-described feature value calculation, when there is noise in the reference image A or the captured image B, for example, because a part of the fingerprint is missing due to a wrinkle of a finger or the like, as shown in FIG. Even if the image has a vertical wrinkle at the center of the partial image Ri, as shown in FIGS. 14E and 14F, rcnt = 57 and lcnt = 124, and lcnt0 = 4 Assuming that the conditional expression of lcnt> 2 × rcnt and lcnt ≧ lcnt0 is satisfied in step SM3 in FIG. 15A, step SM7 is executed next, and “R” is stored as the feature value. Thus, the feature value calculation has a feature that the calculation accuracy can be maintained for the noise component included in the image.

  As described above, the feature value calculation unit 1045 obtains, for the partial image Ri, an image WRI that is shifted by a predetermined pixel in the diagonally right direction and an image WLi that is shifted and superimposed by a predetermined pixel in the diagonally left direction. Further, an increase amount rcnt of the number of black pixels, which is a difference between the image WRi and the partial image Ri that are shifted by one pixel in the right diagonal direction, and an image WLi and a portion that are overlapped by shifting by one pixel in the left diagonal direction The amount of increase lcnt of the number of black pixels, which is the difference from the image Ri, is obtained, and the pattern of the partial image Ri tends to follow the right diagonal direction based on the increase (for example, the right diagonal stripe) Or a tendency that is a pattern that follows the left diagonal direction (for example, a tendency that is a left diagonal stripe) or neither of them, and values ("R", "L", and "X") corresponding to the determination result either To store.

<Five feature values>
The feature value calculation unit 1045 may output all the feature values described above. In that case, the feature value calculation unit 1045 obtains an increase amount hcnt, an increase amount vcnt, an increase amount rcnt, and an increase amount lcnt of the number of black pixels for the partial image Ri according to the above-described procedure. Based on the amount of increase, the pattern of the partial image Ri tends to be a pattern that follows a horizontal (horizontal) direction (for example, a tendency to be a horizontal stripe), or a pattern that follows a vertical (vertical) direction (for example, a tendency to be a vertical stripe), Or a trend that follows a diagonally right direction (e.g. a trend that is a diagonal right stripe), a trend that follows a diagonally left direction (e.g. a trend that is a diagonal left stripe), or none of them, A value (any one of “H”, “V”, “R”, “L”, and “X”) corresponding to the determination result is output. This output value indicates the feature value of the partial image Ri.

  Here, since “H” and “V” are used as the feature values of the partial image Ri in addition to “R”, “L”, and “X”, the feature values of the partial images of the target image to be collated are more strictly determined. Even if it is a partial image that can be classified by three types of feature values and becomes “X”, if it is classified into five types of feature values, any one other than “X” Since it can be classified into values, the partial image Ri to be classified as “X” can be detected more precisely.

  FIG. 19 shows a flowchart of five types of feature value calculation. In the partial image feature value calculation of FIG. 19, first, steps ST1 to ST4 of the partial image feature value calculation process (T2a) shown in FIG. 10 are similarly executed, and the determination results “V” and “H”. Is determined (ST5, ST7). In this case, if it is determined that it is neither “V” nor “H” (N in ST4), then steps SM1 to SM7 of the image feature value calculation process (T2a) shown in FIG. As a result of determination, “L”, “X”, and “R” are output. As a result, partial image feature values of “V”, “H”, “L”, “R”, and “X” are output as partial image feature values by partial image feature value calculation (T25a). Can do.

  Here, in view of the fact that many fingerprints to be judged tend to follow the pattern in the vertical or horizontal direction, the processing of FIG. 10 is executed first, but the execution order is not limited to this. If the process of FIG. 15 is executed first and it is determined that it is neither “L” nor “R”, the procedure of FIG. 10 may be executed next.

<Limited search target>
The search target by the maximum matching score position searching unit 105 can be limited according to the feature value calculated above.

  20B and 20C schematically illustrate images A and B in which partial image feature values are calculated after image input (T1) and image correction (T2), respectively. To do.

  First, how to specify a partial image position in an image will be described with reference to FIG. The shape (shape, size) of the image shown in FIG. 20A matches the images A and B shown in FIGS. 20B and 20C. In the image of FIG. 20A, partial images Ri having the same shape (rectangular shape) divided into 64 and equally divided into mesh shapes are prepared. By assigning numerical values 1 to 64 to the 64 partial images Ri in order from the upper right to the lower left of the image in FIG. 20A, the positions of the partial images Ri in the image A or B can be assigned. It shows using the numerical value. Here, each of the 64 partial images Ri in the image is designated as a partial image g1, a partial image g2,..., A partial image g64 using a numerical value indicating a corresponding position. Since the images in FIGS. 20A, 20B, and 20C have the same shape, the images A and B in FIGS. 20B and 20C are also shown in FIG. 64 partial images Ri are provided, and the position of each partial image Ri can be specified as a partial image g1, a partial image g2,..., A partial image g64. The maximum matching position search unit 105 searches for the partial images Ri corresponding to the maximum matching positions for the images A and B. The search order follows the partial image g1, the partial image g2,. Each partial image of the images in FIG. 20B and FIG. 20C has one of feature values “H”, “V”, and “X” calculated by the feature value calculation unit 1045 as a feature value. Assume that.

  FIGS. 21A to 21C are diagrams illustrating a procedure for searching for the maximum matching position between images A and B in which the feature values of the partial images in FIGS. 20B and 20C are calculated. FIG. 22 is a processing flowchart for maximum matching position search and similarity calculation.

  Maximum matching position search section 105 searches image A in FIG. 20B and searches for a partial image having the same feature value in image B for a partial image having a feature value of “H” or “V”. . Therefore, when the search for a partial image in the image A is started and a partial image having a feature value of “H” or “V” is first detected, the detected partial image is the first partial image to be searched. It becomes. An image (A) -S1 in FIG. 21A shows a partial image feature value for a partial image of the image A, and a partial image g27 having a feature value of “H” or “V” first, that is, “ V1 ″ is a hatched image.

  As this image (A) -S1, the partial image feature value detected first indicates “V”. For this reason, the partial image whose feature value is “V” in the image B is a search target. In image B, the first partial image g11 having the characteristic value “V” after the search is started, that is, the image obtained by hatching “V1” is the image (B) -S1-1 in FIG. . The processing shown in steps S002 to S007 in FIG. 22 is performed on this partial image.

  Next, in the image B, processing is performed for the partial image g14 having the feature value “V” next to the partial image g11, that is, “V1” (image (B) -S1-2 in FIG. 21A). Thereafter, the processing is performed for the partial images g19, g22, g26, g27, g30, g31 (image (B) -S1-8 in FIG. 20A). When the search process is completed in the image B for the partial image g27 having the feature value of “H” or “V” at the beginning of the image A, the partial image having the feature value of “H” or “V” next. For g28 (image (A) -S2 in FIG. 21B), the processing shown in steps S002 to S007 in FIG. 22 is similarly performed, and the partial image feature value of the partial image g28 is “H”. Partial image g12 (image (B) -S2-1 in FIG. 21B), image g13 (image (B) -S2-2 in FIG. 21B) having “H” as the feature value of image B, A search process is performed for g33, g34, g39, g40, g42 to g46, and g47 (image (B) -S2-12 in FIG. 21B).

  Thereafter, the partial images g29, g30, g35, g38, g42, g43, g46, g47, g49, g50, g55, g56, g58 to 62, g63 (with the characteristic value of “H” or “V” in the image A ( The search process in the image B is similarly performed for the images (A) to S20) in FIG.

  Therefore, the number of partial images searched in the images A and B by the maximum matching position search unit 105 is (the number of partial images of the image A having the partial image feature value “V” × the partial image feature value “V”. The number of partial images of an image B + the number of partial images of an image A having a partial image feature value “H” × the number of partial images of an image B having a partial image feature value “H”). In the case of FIGS. 21A to 21C, the number of partial images to be searched is search partial image number = 8 × 8 + 12 × 12 = 208.

  Note that the partial image feature value depends on the pattern presented by the image, and therefore, here, a case where the image has a pattern different from the patterns shown in FIGS. 20A and 20B is shown. FIGS. 23A and 23B show images A and B, and images A and B shown in FIGS. 20B and 20C show different patterns. FIG. These show the image C which shows a different pattern from the image B of FIG.20 (C).

  FIG. 23D, FIG. 23E, and FIG. 24F are respectively partial images of the images A, B, and C in FIG. 23A, FIG. 23B, and FIG. Is a feature value calculated by the feature value calculation unit 1045.

  Similarly to the above, the number of partial images searched by the maximum matching position search unit 105 for the image A in FIG. 23A and the image C in FIG. The number of partial images of the image A being V ”× the number of partial images of the image C being the partial image feature value“ V ”+ the number of partial images of the image A being the partial image feature value“ H ”× the partial image feature value“ H ”. (The number of partial images of the image C). Referring to FIG. 23D and FIG. 23F, the number of search partial images = 8 × 12 + 12 × 16 = 288.

  In this description, partial images having the same feature value are targeted for search. However, this is not always necessary, and the reference partial image feature value is “H” for the purpose of improving collation accuracy. The partial image feature value for the captured image is not only “H” but also the partial region of “X”, or the partial image feature value for the captured image is only “V” when the reference partial image feature value is “V”. Needless to say, the partial region of “X” may be the search target.

  Further, when the feature value is “X”, it can be said that the corresponding partial image has a pattern in which neither vertical stripes nor horizontal stripes can be specified. When the collation speed is to be improved, the search range by the maximum matching position search unit 105 May be excluded from the partial region indicating “X”.

  In order to improve accuracy, not only “H” and “V”, but also “L” and “R” values may be applied.

<Determination of non-collation target image elements>
Next, a non-collation target image element determination calculation process (step T25b) is performed on the image that has been subjected to the correction process by the image correction unit 104 and the feature value of the partial image calculated by the feature value calculation unit 1045. . This process is shown in the flowchart of FIG.

  Here, it is assumed that each partial image in the verification target image adopts “H”, “V”, “L”, and “R” (in the case of four values) as a feature value by the processing of the element determination unit 1047. To do. That is, if there is an area where dirt is attached on the fingerprint reading surface 201 of the fingerprint sensor 100 or an area in which an image cannot be input because no fingerprint is placed (no finger is placed), the area corresponds to that area. This partial image basically takes “X” as a feature value. Using this characteristic, the element determination unit 1047 detects (determines) a partial area where dirt is attached in the input image or a partial area where a fingerprint image cannot be input as a non-collation target image element. Then, processing is performed so as to assign the feature value “E” to the detected area. Here, assigning “E” as a feature value to a partial region (partial image) of the image means that the partial region (partial image) is subjected to image matching performed by collation determination unit 107 for maximum matching position search unit 105. It is excluded from the search range, and excluded from the similarity calculation target of the similarity calculation unit 106.

  25A to 25F schematically show determination of image elements that are not to be collated and collation. FIG. 25B and FIG. 25F schematically show the input image B and the reference image A. As shown in FIG. 25A, the reference image A has 64 partial images having the same size and shape by being equally divided into 8 pieces in the vertical and horizontal directions. In FIG. 25A, numerical values indicating image positions from g1 to g64 are assigned and instructed for each partial image.

  The input image B shown in FIG. 25B has 25 partial images having the same size and shape that are equally divided into 5 in each of the vertical and horizontal directions. With respect to the 25 partial images, assignments are instructed to the positions indicated by positions g1 to g5, g9 to g13, g17 to g21, g25 to g29, and g33 to g37 in FIG. For the sake of simplicity, the reference image A is obtained by calculating values ('H', 'V', 'L', 'R') excluding X and E as feature values for each partial image. Assuming that

  The element determination unit 1047 calculates the feature value calculated by the feature value calculation unit 1045 of each partial image corresponding to the input image B in FIG. 25B from the captured image partial image feature value calculation result memory 1025. Read to memory 1022. The read state is schematically shown in FIG. 25C (step SS001 in FIG. 24).

  Next, the element determination unit 1047 detects image elements that are not to be collated by searching the feature values of the partial images in FIG. 25C in the calculation memory 1022 in ascending order of numerical values indicating the partial image positions. (Step SS002 in FIG. 24). Here, when a partial image having “X” as the feature value is detected in the search process, the feature value of the partial image adjacent to the partial image is searched. As a result of the search, at least one of the vertical direction (direction according to the Y axis), the horizontal direction (direction according to the X axis), and the oblique direction (direction according to an axis having an inclination of 45 degrees with respect to the X axis or the Y axis) of the partial image. When a partial image having a feature value indicating “X” is detected adjacent to one direction, a set of the partial image and the detected adjacent partial image is detected as an image element that is not to be matched ( judge.

  Specifically, the characteristic values such as g2, g3, g4, g5, g9,... G13, g17... Are sequentially displayed from the partial image g1 of the input image B in FIG. Search for. In the search process, when a partial image whose feature value indicates “X” or “E” is detected, all of the partial images adjacent to the upper, lower, left, right, upper right, lower right, upper left, and lower left of the partial image are detected. A feature value is searched for a partial image. As a result of the search, if a feature value indicating “X” can be searched in the adjacent partial images, “X” searched in the calculation memory 1022 is rewritten to “E” (step SS003 in FIG. 24). When the search for all partial images of the input image B is thus completed, the feature values of the partial images of the image B are updated as shown in FIG. 25C to FIG. 25D. The value of each updated partial image is stored in the captured image feature value memory 1025.

  An example of this rewriting will be described. Referring to FIG. 25C, when the feature values are searched in order from the partial image g1, the partial image having the feature value “X” is detected for the first time when the partial image g28 is searched. When the feature values of all partial images adjacent to the g28 partial image are searched, it is detected that the feature values of the adjacent partial images of g29, g36, and g37 are 'X'. The feature value “X” of the partial images g28, g29, g36, and g37 in the memory 1022 is updated (rewritten) to “E” as shown in FIG.

  Here, in the input image B, a partial region in which two or more partial images having “X” as a feature value are continuously formed in at least one of the vertical direction, the horizontal direction, and the diagonal direction is a collation. Although the image element is determined to be a non-target image element, the determination criterion is not limited to this. For example, the partial image itself having “X” as the feature value may be determined as a non-collation target image element, or other combinations may be taken.

<Similarity calculation and matching judgment>
Next, the maximum matching position search in consideration of the result of the non-matching target image element determination by the element determination unit 1047 and the similarity calculation process based on the search result (step T3 in FIG. 4) will be described with reference to the flowchart in FIG. To do. Here, the total number of partial images (partial regions) in the image A is indicated by a variable n. The maximum matching position search and similarity calculation are performed on each partial image of the reference image A in FIG. 25A and the image B from which the determined non-matching elements in FIG. 25E are removed. .

  When the determination by the element determination unit 1047 is completed, the control unit 108 transmits a template matching start signal to the maximum matching position search unit 105 and waits until a template matching end signal is received.

  When the maximum matching position search unit 105 receives the template matching start signal, the template matching process as shown in steps S001 to S007 is started. In step S001, the value of the variable i of the counter is initialized to 1. In step S002, an image of a partial area defined as the partial image Ri of the reference image A is set as a template used for template matching.

  In step S0025, the maximum matching position search unit 105 searches the reference image feature value memory 1024 and reads the feature value CRi of the partial image Ri of the template.

  In step S003, a search is made for a place having the highest degree of matching in the image B with respect to the template set in step S002, that is, where the data in the image B most matches. In this search, the following calculation is performed only for the partial images of the image B whose feature value is not “E”.

  The pixel density of coordinates (x, y) based on the upper left corner of the rectangular partial image Ri used as a template is Ri (x, y), and the coordinates (s, t) are based on the upper left corner of the image B. ) Is B (s, t), the width of the partial image Ri is w, the height is h, and the maximum density that each pixel of the images A and B can take is V0. The degree of coincidence Ci (s, t) at the coordinates (s, t) is calculated based on the density difference of each pixel, for example, according to (Equation 1) below.

  The coordinates (s, t) are sequentially updated in the image B, and the degree of coincidence C (s, t) at the updated coordinates (s, t) is calculated each time the coordinates are updated. It is assumed that the position in the image B corresponding to the largest value in the calculated matching degree C (s, t) has the highest matching degree with the partial image Ri, and the image of the partial region at that position in the image B. Is a partial region Mi. Then, the matching degree C (s, t) corresponding to the position is set to the maximum matching degree Cimax.

  In step S004, the maximum matching degree Cimax is stored at a predetermined address in the memory 102. In step S005, the movement vector Vi is calculated according to the following (Equation 2), and the calculated movement vector Vi is stored at a predetermined address in the memory 102.

  Here, as described above, the image B is scanned (searched) based on the partial image Ri corresponding to the position P in the image A, and as a result, the position M having the highest degree of coincidence with the partial image Ri. When the partial area Mi is detected, the direction vector from the position P to the position M is called a movement vector Vi. Since the manner in which the finger is placed on the fingerprint reading surface 201 of the fingerprint sensor 100 is not uniform, the movement vector Vi indicates that when one image, for example, the image A is used as a reference, the other image B appears to have moved. ing. Since the movement vector Vi indicates the direction and the distance, the positional relationship between the partial image Ri of the image A and the partial area Mi of the image B is quantified and shown by the movement vector Vi.

Vi = (Vix, Viy) = (Mix-Rix, Miy-Ry) (Formula 2)
In (Expression 2), variables Rix and Riy indicate the values of the x coordinate and the y coordinate of the reference position of the partial image Ri, and correspond to, for example, the coordinates of the upper left corner of the partial image Ri in the image A. Variables Mix and Miy indicate an x-coordinate and a y-coordinate indicating a position corresponding to the maximum matching degree Cimax calculated by searching the partial region Mi. For example, this corresponds to the coordinates of the upper left corner of the partial area Mi at the matched position in the image B.

  In step 006, the value of the counter variable i is compared with the value of the variable n, and based on the comparison result, it is determined whether or not the value of the counter variable i is less than the value indicated by the variable n. Is determined to be less than the value of the number of variables n, the process proceeds to S007, and if not, the process proceeds to S008.

  In step S007, 1 is added to the value of the variable i. Thereafter, while it is determined that the value of the variable i is less than the value of the variable n, steps S002 to S007 are repeated, and for all the partial images Ri of the image A, the reference image feature value memory 1024 for the partial image Ri. Template matching is performed by limiting to the partial region of the image B having the same value as the characteristic value CM and the corresponding feature value CRi retrieved by searching for the maximum matching score Cimax of each partial image Ri and the movement vector Vi. And calculate.

  The maximum matching position search unit 105 stores the maximum matching degree Cimax and the movement vector Vi for all the partial images Ri sequentially calculated as described above at a predetermined address in the memory 102, and then sends a template matching end signal to the control unit 108. Send and finish the process.

  Subsequently, the control unit 108 sends a similarity calculation start signal to the similarity calculation unit 106 and waits until a similarity calculation end signal is received. The similarity calculation unit 106 uses the information such as the movement vector Vi and the maximum matching degree Cimax of each partial image Ri obtained by template matching stored in the memory 102 to show the steps S008 to S020 in FIG. The similarity is calculated by performing the above process.

  In step S008, the value of similarity P (A, B) is initialized to zero. Here, the similarity P (A, B) indicates a variable for storing the similarity between the image A and the image B. In step S009, the value of the index i of the reference movement vector Vi is initialized to 1. In step S010, the value of similarity score Pi relating to reference movement vector Vi is initialized to zero. In step S011, the index j of the movement vector Vj is initialized to 1. In step S012, a vector difference dVij between the reference movement vector Vi and the movement vector Vj is calculated according to (Equation 3) below.

dVij = | Vi−Vj | = sqrt ((Vix−Vjx) ^ 2 + (Viy−Vjy) ^ 2) (Expression 3)
Here, the variables Vix and Viy indicate the x-direction component and the y-direction component of the movement vector Vi, the variables Vjx and Vji indicate the x-direction component and the y-direction component of the movement vector Vj, and the variable sqrt (X) is the square root of X. , X ^ 2 is a calculation formula for calculating the square of X.

  In step S013, the value of the vector difference dVij between the movement vectors Vi and Vj is compared with the threshold value indicated by the constant ε. Based on the comparison result, the movement vector Vi and the movement vector Vj can be regarded as substantially the same movement vector. Determine if possible. If the determination result indicates that the value of the vector difference dVij is smaller than the threshold value (vector difference) indicated by the constant ε, it is determined that the movement vector Vi and the movement vector Vj are substantially the same, and the process is performed. The process proceeds to step S014, but conversely, if it indicates that the value is equal to or greater than the value of the constant ε, it is determined that both vectors are not regarded as substantially the same, and the process proceeds to step S015. In step S014, the value of similarity score Pi is increased according to (Expression 4) to (Expression 6) below.

Pi = Pi + α (Formula 4)
α = 1 (Formula 5)
α = Cjmax (Expression 6)
The variable α in (Expression 4) is a value that increases the similarity score Pi. When α = 1 as shown in (Expression 5), the similarity Pi is the number of partial areas having the same movement vector as the reference movement vector Vi. Further, when α = Cjmax as in (Equation 6), the similarity score Pi is the sum of the maximum matching degrees at the time of template matching for a partial region having the same movement vector as the reference movement vector Vi. Further, the value of the variable α may be decreased according to the magnitude of the vector difference dVij.

  In step S015, it is determined whether the value of the index j is smaller than the value of the variable n. As a result of the determination, if the value of the index j is smaller than the total number of partial areas indicated by the variable n, the process proceeds to step S016, and if it is greater than the total number, the process proceeds to step S017. In step S016, the value of index j is incremented by one. Through the processing from step S010 to step S016, the similarity score Pi is calculated using the information on the partial areas determined to have the same movement vector with respect to the reference movement vector Vi. In step S017, the value of the similarity score Pi and the variable P (A, B) with the movement vector Vi as a reference is compared, and the comparison result shows that the value of the similarity score Pi is the maximum similarity (variable P). If it is greater than (A, B)), the process proceeds to S018, and if it is less, the process proceeds to S019.

  In step S018, the value of similarity score Pi with movement vector Vi as a reference is set in variable P (A, B). In steps S017 and S018, the similarity Pi when the movement vector Vi is used as a reference is the maximum value of the similarity when other movement vectors calculated up to this point are used as a reference (variables P (A, B)). If the value is larger than the value i), the movement vector Vi used as a reference is the most legitimate reference in the index i up to the present.

  In step S019, the value of index i of reference movement vector Vi is compared with the number of partial areas (value of variable n). If the value of index i is smaller than the number of partial areas, the process proceeds to step S020. In step S020, the index i is incremented by one.

  From step S008 to step S020, the similarity between images A and B is calculated as the value of variable P (A, B). The similarity calculation unit 106 stores the value of the variable P (A, B) calculated as described above at a predetermined address in the memory 102, sends a similarity calculation end signal to the control unit 108, and ends the process.

  Subsequently, the control unit 108 transmits a verification determination start signal to the verification determination unit 107 and waits until a verification determination end signal is received. The collation determination unit 107 collates and determines (step T4). Specifically, the similarity indicated by the value of the variable P (A, B) stored in the memory 102 is compared with a predetermined matching threshold T. As a result of comparison, if the variable P (A, B) ≧ T, it is determined that the image A and the image B are taken from the same fingerprint, and a value indicating “match” as a comparison result to a predetermined address in the memory 102, for example, “1” Otherwise, it is determined that the data is collected from a different fingerprint, and a value indicating “non-match”, for example, “0”, for example, is written as a collation result to a predetermined address in the memory 102, that is, the calculation memory 1022. Thereafter, a collation determination end signal is sent to the control unit 108, and the process ends.

  Finally, the control unit 108 outputs the collation result stored in the memory 102 via the display 610 or the printer 690 (step T4), and ends the image collation.

  In the present embodiment, images A and B are both input by image input unit 101, but may be as follows. In other words, the collation processing unit 11 reads the partial image Ri of the image A from the registered image storage unit so that the memory 102 includes a registered image storage unit that registers a plurality of partial images Ri of the image A in advance. In this way, the image B may be input by the image input unit 101.

  In the present embodiment, all or a part of the image correction unit 104, the feature value calculation unit 1045, the element determination unit 1047, the maximum matching position search unit 105, the similarity calculation unit 106, the collation determination unit 107, and the control unit 108 are processed. You may comprise using ROM, such as memory 624 which memorize | stored the procedure as a program, and arithmetic processing units, such as CPU622 for performing it.

<Effects of the embodiment>
Here, a specific example of the collation processing according to the present embodiment and the effect thereof will be shown.

  When a fingerprint image with dirt as shown in FIG. 20B is used as the input image B, if the reference image A shown in FIG. 20F is collated as it is, FIG. 20B is configured. The ratio of the 25 partial images that matches the reference image A shown in FIG. 20F is (25−4) /25=0.84. Here, “4” corresponds to the four partial images in FIG. 20C which are derived from dirt and determined as “X” as the partial image feature value.

  Here, assuming that the partial image of the input image B has a matching ratio with the reference image A of 90% (0.9) or more, the image B having the characteristic value of FIG. When used for collation, the collation result is “mismatch”.

  On the other hand, since the partial region corresponding to the stain is designated as an image element to be excluded from the matching target in advance by the element determination unit 1047 according to the present embodiment, the matching between the image B and the image A is performed by the image element that is not the matching target. The collation processing of the collated image of FIG. 20E and the reference image A shown in FIG. Therefore, the matching ratio is (25-4) / (25-4) = 1, and the collation result indicates “match”.

  As described above, in this embodiment, it is possible to omit the process of checking the fingerprint reading surface of the fingerprint sensor for the presence of the fingerprint before the fingerprint collation process required in the prior art. Also, instead of directly detecting dirt from the image read from the entire fingerprint reading surface 202, dirt is detected according to information acquired for the partial image (partial image determined to have a feature value of 'X'). is doing. Therefore, by changing the reference for calculating “X” as the feature value by the feature value calculation unit 1045 variably according to the required matching ratio, cleaning can be performed if the position / size of dirt has no practical problem. It is possible to continue the verification process without requesting. As a result, many images per unit time can be processed. In addition, it is possible to prevent a situation in which the convenience of the user is impaired due to the need for re-input of the fingerprint due to the adhesion of dirt or the demand for cleaning to remove the dirt.

(Embodiment 2)
The processing function for image collation described above is realized by a program. In the second embodiment, this program is stored in a computer-readable recording medium.

  In the second embodiment, as the recording medium, a memory necessary for processing by the computer shown in FIG. 2, for example, the memory 624 itself may be a program medium. The recording medium may be a recording medium that is detachably attached to an external storage device of a computer, and a program recorded therein can be read via the external storage device. Examples of such external storage devices include a magnetic tape device (not shown), an FD driving device 630, and a CD-ROM driving device 640. As the recording medium, magnetic tape (not shown), FD 632, and CD- ROM 642 or the like. In any case, the program recorded on each recording medium may be configured to be accessed and executed by the CPU 622, or in any case, the program is once read from the recording medium and the program shown in FIG. The program may be loaded into the program storage area, for example, the program storage area of the memory 624, and read and executed by the CPU 622. This loading program is assumed to be stored in advance in the computer.

Here, the above-described recording medium is configured to be separable from the computer main body. As such a recording medium, a medium that carries a program in a fixed manner can be applied. Specifically, tape systems such as magnetic tape and cassette tape, magnetic disks such as FD632 and fixed disk 626, CD-ROM 642 / MO (Magnetic Optical Disc) / MD (Mini Disc) / DVD (Digital Versatile Disc), etc. A semiconductor memory such as a disk system of an optical disk, a card system such as an IC card (including a memory card) / optical card, a mask ROM, an EPROM (Erasable and Programmable ROM), an EEPROM (Electrically EPROM), a flash ROM, or the like is applicable.

  In addition, since the computer of FIG. 2 employs a configuration capable of communication connection with the communication network 300 including the Internet, the computer may be a recording medium in which the program is downloaded from the communication network 300 and fluidly carries the program. When the program is downloaded from the communication network 300, the download program may be stored in the computer main body in advance, or may be installed in the computer main body from another recording medium in advance.

Note that the content stored in the recording medium is not limited to a program, and may be data.

  The embodiment disclosed this time should be considered as illustrative in all points and not restrictive. The scope of the present invention is defined by the terms of the claims, rather than the description above, and is intended to include any modifications within the scope and meaning equivalent to the terms of the claims.

It is a block diagram of the image collation device of an embodiment of the invention. 1 is a configuration diagram of a computer on which an image collation apparatus according to an embodiment of the present invention is mounted. It is a block diagram of the fingerprint sensor by embodiment of this invention. It is a flowchart of the collation process by embodiment of this invention. It is a figure explaining the pixel of the image for calculating three types of feature values by an embodiment of the invention. It is a flowchart which calculates three types of feature values by embodiment of this invention. It is a flowchart of the process which calculates | requires the maximum continuous black pixel number of the horizontal direction by embodiment of this invention. It is a flowchart of the process which calculates | requires the maximum continuous black pixel number of the orthogonal | vertical direction by embodiment of this invention. (A)-(F) is a figure which shows the outline | summary of the image feature value calculation process by embodiment of this invention. It is a figure which shows the partial image and the flowchart of the partial image feature value calculation process by embodiment of this invention, and (A)-(C). It is a processing flowchart which calculates | requires the increase amount when shifting to the right and left of the partial image by embodiment of this invention. It is a flowchart of the process which calculates | requires the increase amount when shifting to the upper and lower sides of the partial image by embodiment of this invention. It is a flowchart of the process which calculates | requires the difference of the pixel value of the image shifted from the upper and lower sides and the right and left based on the partial image by the embodiment of this invention, and the original partial image. (A)-(F) is a figure which shows the outline | summary of the image feature value calculation process by embodiment of this invention. (A)-(C) are the figures which show the partial image and the flowchart of the partial image feature value calculation process by embodiment of this invention, and are referred. It is a processing flowchart which calculates | requires the increase amount when shifting to the right diagonal direction of the partial image by embodiment of this invention. It is a flowchart of the process which calculates | requires the increase amount when it shifts to the left diagonal direction of the partial image by embodiment of this invention. It is a processing flowchart which calculates | requires the difference of the pixel value of the image shifted from the diagonally left direction and the diagonally right direction, and the original partial image based on the partial image by embodiment of this invention. It is a flowchart of the partial image feature value calculation process by embodiment of this invention. (A)-(C) are the figures for demonstrating the specific example of the collation process by embodiment of this invention. (A)-(C) are the figures for demonstrating the specific example of the collation process by embodiment of this invention. It is a processing flowchart of the maximum matching position search and similarity calculation by embodiment of this invention. (A)-(F) are the figures for demonstrating the specific example of the collation process by embodiment of this invention. It is a processing flowchart of the determination of the element not to be collated according to the embodiment of the present invention. (A)-(F) is a figure which shows roughly the procedure of the collation in consideration of the non-collation target element by embodiment of this invention.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 1 Image collation apparatus, 11 Collation process part, 101 Image input part, 102 Memory, 104 Image correction | amendment part, 1045 Partial image feature value calculation part, 1047 Non-collation target image element determination part, 105 Maximum matching position search part, 106 Movement vector Similarity calculation unit based on 107, 107 collation determination unit, 108 control unit, A reference image, B input image, Ri partial image.

Claims (14)

An element detection unit for detecting an element to be excluded from the target of matching in the image;
A collation processing unit that performs collation processing using the image from which the element detected by the element detection unit is excluded;
A feature value detector that detects and outputs a feature value corresponding to the pattern of the partial image corresponding to each of the plurality of partial images in the image,
The element detection unit detects the element as an area indicated by a combination of the partial images having a predetermined feature value output from the feature value calculation unit. The image shows a fingerprint image,
The feature value output by the feature value detection unit is a value indicating that the pattern of the partial image follows the vertical direction of the fingerprint, a value indicating that the pattern follows the horizontal direction of the fingerprint, and the like. The image collating apparatus according to claim 1, wherein the image collating apparatus is classified into values to be indicated. The image shows a fingerprint image,
The feature value output by the feature value detection unit is a value indicating that the pattern of the partial image follows the diagonal right direction of the fingerprint, a value indicating that the fingerprint image follows the diagonal left direction of the fingerprint, and others. The image collating apparatus according to claim 1, wherein the image collating apparatus is classified into a value indicating the above.   The image collating apparatus according to claim 2, wherein the predetermined feature value indicates the other value.   The image matching device according to claim 4, wherein the combination includes a plurality of partial images indicating the other values located adjacent to each other in a predetermined direction. The collation processing unit
Of the first image and the second image to be collated, the position of the region having the highest degree of coincidence with the partial region in the first image is detected by the element detection unit in the second image. A position search unit for searching in a partial area excluding the area of the element;
The first image and the second image are based on a positional relationship amount indicating a positional relationship between a reference position for measuring the position of the region in the first image and a maximum coincidence position searched by the position search unit. A similarity calculator that calculates and outputs the similarity of
The image collating apparatus according to claim 1, further comprising: a determination unit that determines whether the first image and the second image match based on the given degree of similarity. The position search unit includes:
Searching for the maximum matching position corresponding to each of the partial images in the partial area excluding the area of the element detected by the element detection unit in the second image,
The similarity calculation unit
Of the partial images in the second image, the number of partial images indicating that the positional relation amount between the corresponding maximum matching position searched by the position search unit and the reference position is smaller than a predetermined amount The image collation apparatus according to claim 6, wherein the image collation is output as the similarity.   The image collating apparatus according to claim 7, wherein the positional relation amount indicates a direction and a distance of the maximum matching position with respect to the reference position.   The image collating apparatus according to claim 6, wherein the sum of the maximum matching degrees for the partial images having the positional relationship amount smaller than the predetermined amount is output as the similarity. An image input unit for inputting an image;
A registration image storage unit that stores images of the plurality of partial areas that are registered in advance;
The image collating apparatus according to claim 1, wherein the partial image of the first image is read from the registered image storage unit, and the other image is input by the image input unit.   The image collating apparatus according to claim 10, wherein the image input unit has a reading surface on which an object is placed and an image is read from the placed object. An image matching method for matching images using a computer,
An element detection step for detecting elements to be excluded from matching in the image;
A collation processing step for performing collation processing using the image from which the element detected by the element inspection step is excluded;
A feature value detecting step for detecting and outputting a feature value corresponding to the pattern of the partial image corresponding to each of the plurality of partial images in the image,
In the element detecting step, the element is detected as an area indicated by a combination of the partial images having the predetermined feature value output by the feature value calculating step.   An image collation program for causing a computer to execute the image collation method according to claim 12.   A computer-readable recording medium on which an image collation program for causing a computer to execute the image collation method according to claim 12 is recorded.

Images