Abstract:
An image collating apparatus includes a storage device and a processor. The storage device stores data representing a sensing image, data representing a template image, and a program. The processor detects exclusion areas in the sensing image to be excluded from the image collation operation based on classification of image patterns. The processor determines whether or not the sensing image and the template image are derived from the identical object by performing template-matching operations to evaluate similarity between the template image and partial images of the sensing image in different levels with increasing the size of area covered by the partial image to be matched with the template image level by level. At least in one level the processor performs the template-matching operation with respect to the partial image where the exclusion areas are excluded.

Description:
[0001]     This nonprovisional application is based on Japanese Patent Application No. 2005-282314 filed with the Japan Patent Office on Sep. 28, 2005, the entire contents of which are hereby incorporated by reference.  
       FIELD OF THE INVENTION  
       [0002]     The present invention relates to an image collating apparatus, an image collating method, an image collating program product, and a computer readable recording medium recording the image collating program. More specifically, the present invention relates to an image collating apparatus, an image collating method, an image collating program product, and a computer readable recording medium recording the image collating program, for collating a plurality of images.  
       DESCRIPTION OF THE BACKGROUND ART  
       [0003]     Japanese Patent Laying-Open No. 2003-323618 discloses a method including the steps of: dividing a sensing image into partial areas; searching in all sensing partial areas so as to find out a position in a template image at which each partial area attains the best match with the template image; and determining whether a fingerprint is the same based on distribution of movement vectors between the sensing image and the template image that attained best match in searching.  
         [0004]     According to the method disclosed in Japanese Patent Laying-Open No. 2003-323618, high collation accuracy can be attained.  
         [0005]     On the other hand, the invention disclosed in Japanese Patent Laying-Open No. 2003-323618 is disadvantageous in excessive time period for processing and excessive power consumption, which results from a large amount of information processing. A large amount of information processing results from such processes that one entire image is initially divided into a plurality of partial areas and search in all partial areas for clarifying positional relation between the partial areas is carried out.  
       SUMMARY OF THE INVENTION  
       [0006]     The present invention was made to solve the above-described problems, and an object of the present invention is to provide an image collating apparatus, an image collating method, an image collating program product, and a computer readable recording medium recording the image collating program, capable of attaining high collation accuracy with a small amount of search.  
         [0007]     In order to attain the above-described objects, according to one aspect of the present invention, an image collating apparatus for performing an image collation operation includes a storage device, and a processor. The storage device stores image data representing a sensing image of an object sensed by a sensor, template data representing a template image, and a program. The processor receiving commands from the program for (a) detecting exclusion areas in the sensing image to be excluded from the image collation operation based on classification of image patterns, (b) determining whether or not the sensing image and the template image are derived from the identical object by performing template-matching operations to evaluate similarity between the template image and partial images of the sensing image in different levels, in the different levels the processor increasing the size of area covered by the partial image to be matched with the template image level by level, and at least in one level the processor performing the template-matching operation with respect to the partial image where the exclusion areas are excluded.  
         [0008]     Preferably, each of the partial images includes a plurality of partial areas of the sensing image, and the processor, in the process for detemining, (b-1) determines whether a first partial image among the partial images includes the exclusion area, the first partial image including the partial areas at predetermined positions in the first level, and (b-2) when the first partial image includes the exclusion area, skips the first level and then determines in the second level whether or not the sensing image and the template image are derived from the identical object based on the template-matching operation between the template image and a second partial image among the partial images which is larger than the first partial image and other than the exclusion areas.  
         [0009]     Prefereably, the processor, in the process for detemining, (b-1) determines that the sensing image and the template image are derived from the identical object when a first partial image among the partial images matches with any portion of the template image, the exclusion areas being excluded from the first partial image and (b-2) when the first partial image does not match with the template image, determines whether or not the sensing image and the template image are derived from the identical object based on the template-matching operation between the template image and a second partial image among the partial images which is larger than the first partial image and other than the exclusion areas.  
         [0010]     Preferably, the processor specifies, in the process for detecting, characteristic information which corresponds to classification of the image patterns in arrangements of pixels of an identical color in the partial image, and detects the excluded areas based on the characteristic information.  
         [0011]     Preferably, each of the partial images includes a plurality of partial areas of the sensing image, and the exclusion area includes a first partial area and second partial areas adjacent to the first partial area, wherein the first and second partial areas correspond to the same classification category.  
         [0012]     Preferably, each of the partial images includes a plurality of partial areas of the sensing image, the processor searches for a most similar portion in the template image for each the partial area, and the processor calculates similarity score between at least a part of the sensing image and at least a part of the template image based on positional relation between each the partial area and the seached portion.  
         [0013]     Preferably, the processor, in the first level of the different levels, determines that the partial image matches with any portion of the template image if the similarity score is equal to or greater than a first threshold value, and determines that the partial image is different from any portion of the template image if the similarity score is smaller than a second threshold value.  
         [0014]     Preferably, the processor, in the process for calculating, calculates the number of partial areas which satisfies a prescribed requirement of positional relation between a plurality of the partial areas and the searched portion.  
         [0015]     Preferably, the partial image in the first level includes a partial area located in a center of the sensing image.  
         [0016]     Preferably, the processor determines whether or not the sensing image and the template image are derived from the identical object based on different threathold values in the different levels.  
         [0017]     Preferably, the storage device includes a device storing in advance the data representing the template image.  
         [0018]     Preferably, the image collating apparatus further includes an input unit receiving data of an image of fingerprint as the image data representing the sensing image.  
         [0019]     According to another aspect of the present invention, a method of collating an image for performing an image collation operation, includes the steps of: storing image data representing a sensing image of an object sensed by a sensor, template data representing a template image, and a program; detecting exclusion areas in the sensing image to be excluded from the image collation operation based on classification of image patterns; and determining whether or not the sensing image and the template image are derived from the identical object by performing template-matching operations to evaluate similarity between the template image and partial images of the sensing image in different levels, in the different levels the processor increasing the size of area covered by the partial image to be matched with the template image level by level, wherein the step of determining includes the step performing the template-matching operation of at least in one level with respect to the partial image where the exclusion areas are excluded.  
         [0020]     According to another aspect of the present invention, an image collating program product for performing an image collation operation and causing a computer to execute the steps of: storing image data representing a sensing image of an object sensed by a sensor, template data representing a template image, and a program; detecting exclusion areas in the sensing image to be excluded from the image collation operation based on classification of image patterns; and determining whether or not the sensing image and the template image are derived from the identical object by performing template-matching operations to evaluate similarity between the template image and partial images of the sensing image in different levels, in the different levels the processor increasing the size of area covered by the partial image to be matched with the template image level by level, wherein the step of determining includes the step performing the template-matching operation of at least in one level with respect to the partial image where the exclusion areas are excluded.  
         [0021]     According to another aspect of the present invention, a computer readable recording medium recording an image collating program for performing an image collation operation causing a computer to execute the steps of: storing image data representing a sensing image of an object sensed by a sensor, template data representing a template image, and a program; detecting exclusion areas in the sensing image to be excluded from the image collation operation based on classification of image patterns; and determining whether or not the sensing image and the template image are derived from the identical object by performing template-matching operations to evaluate similarity between the template image and partial images of the sensing image in different levels, in the different levels the processor increasing the size of area covered by the partial image to be matched with the template image level by level, wherein the step of determining includes the step performing the template-matching operation of at least in one level with respect to the partial image where the exclusion areas are excluded.  
         [0022]     The foregoing and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0023]      FIG. 1  is a block diagram representing a functional configuration of an image collating apparatus according to a first embodiment of the present invention.  
         [0024]      FIG. 2  illustrates arrangement of partial areas in an image according to the first embodiment of the present invention.  
         [0025]      FIG. 3  illustrates relation of arrangement and denotation of the partial areas according to the first embodiment of the present invention.  
         [0026]      FIG. 4  is a block diagram showing a computer hardware configuration implementing the image collating apparatus according to the first embodiment of the present invention.  
         [0027]      FIG. 5  is a flowchart representing a procedure for controlling fingerprint collation processing according to the first embodiment of the present invention.  
         [0028]      FIG. 6  illustrates a state of each pixel in the partial area according to the first embodiment of the present invention.  
         [0029]      FIG. 7  is a flowchart showing a procedure for controlling characteristic information specifying processing according to the first embodiment of the present invention.  
         [0030]      FIG. 8  is a flowchart showing a procedure for controlling maximum value MAXHLEN calculation processing according to the first embodiment of the present invention.  
         [0031]      FIG. 9  is a flowchart showing a procedure for controlling maximum value MAXVLEN calculation processing according to the first embodiment of the present invention.  
         [0032]      FIG. 10  is a flowchart showing a procedure for controlling characteristic information rewrite processing according to the first embodiment of the present invention.  
         [0033]      FIG. 11  is a flowchart showing a procedure for controlling similarity score calculation processing and collation determination processing according to the first embodiment of the present invention.  
         [0034]      FIG. 12  is a flowchart showing a procedure for controlling matching and similarity score calculation processing according to the first embodiment of the present invention.  
         [0035]      FIG. 13  is a flowchart showing a procedure for controlling similarity score calculation processing when a partial area determined as non eligible for collation is present, according to the first embodiment of the present invention.  
         [0036]      FIG. 14  is a flowchart showing a procedure for controlling matching score calculation processing according to the first embodiment of the present invention.  
         [0037]      FIG. 15  illustrates a sensing image according to the first embodiment of the present invention.  
         [0038]      FIG. 16  illustrates an exemplary template image according to the first embodiment of the present invention.  
         [0039]      FIG. 17  illustrates exemplary characteristic information according to the first embodiment of the present invention, in association with arrangement of the partial areas.  
         [0040]      FIG. 18  illustrates exemplary characteristic information of which value has been rewritten according to the first embodiment of the present invention, in association with arrangement of the partial areas.  
         [0041]      FIG. 19  is a conceptual view of an input image from which the partial area determined as non eligible for collation has been removed, according to the first embodiment of the present invention.  
         [0042]      FIG. 20  is a flowchart showing a procedure for controlling similarity score calculation processing and collation determination processing according to a second embodiment of the present invention.  
         [0043]      FIG. 21  is a flowchart showing a procedure for controlling matching and similarity score calculation processing according to the second embodiment of the present invention. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0044]     An embodiment of the present invention will be described hereinafter with reference to the drawings. In the description below, the same elements have the same reference characters allotted, and their label and function are also identical. Therefore, detailed description thereof will not be repeated.  
       First Embodiment  
       [0045]     In the following, an image collating apparatus according to a first embodiment of the present invention will be described.  
         [0046]     Referring to  FIG. 1 , an image collating apparatus  100  according to the present embodiment includes an input unit  101 , a storage unit  102 , a processing unit  103 , an output unit  104  (corresponding to a display  610  and a printer  690  which will be described later), and a bus  105 . Input unit  101  includes a fingerprint sensor. Input unit  101  serves as an apparatus accepting data representing a sensing image (image A) and data representing a template image (image B) sensed by the fingerprint sensor. Here, the sensing image and the template image are both fingerprint images. Input unit  101  also serves as the apparatus outputting the read fingerprint image data to storage unit  102  and processing unit  103 . The fingerprint sensor is of an optical type, a pressure type, or a static capacitance type, and the type thereof is designated by a user. In the present embodiment, it is assumed that an optical fingerprint sensor is included. Storage unit  102  serves as an apparatus storing data representing the sensing image, data representing the template image, and various calculation results. Processing unit  103  controls input unit  101  and storage unit  102 . In addition, processing unit  103  also serves as a circuit performing information processing (including operation) necessary for collating the fingerprint. Output unit  104  serves as an apparatus outputting information stored in storage unit  102  and information created by processing unit  103 . Bus  105  is used for transferring control signals and data signals between input unit  101 , storage unit  102 , and processing unit  103 .  
         [0047]     Storage unit  102  corresponds to a memory  624  or a fixed disk  626  which will be described later. Storage unit  102  includes a reference block  1021 , a calculation block  1022 , an image block  1023 , a first area  1024 , and a second area  1025 . Reference block  1021  is a block temporarily storing data for reference. Calculation block  1022  is a block temporarily storing data during operation. Image block  1023  is a block storing image data of the sensing image and the template image. First area  1024  and second area  1025  are both areas storing positional information (in the present embodiment, information representing the coordinate at the upper left vertex among the vertices of a partial area is referred to as “positional information”) and a movement vector which will be described later.  
         [0048]     Arrangement of the partial areas of which positional information is stored in first area  1024  and second area  1025  will be described with reference to  FIGS. 2 and 3 .  
         [0049]     In the present embodiment, the entire area of the sensing image is divided into 25 partial areas. The entire fingerprint image is covered with these partial areas. These partial areas are provided with identification numbers R( 1 ) to R( 25 ) respectively.  FIG. 2  illustrates arrangement of these partial areas of the sensing image. First area  1024  stores positional information of partial areas R( 1 ) to R( 9 ). Partial areas R( 1 ) to R( 9 ) are partial areas located in the center of the sensing image. Partial areas R( 1 ) to R( 9 ) constitute a first portion representing collective of adjacent partial areas. Second area  1025  stores positional information of peripheral partial areas consisting of partial areas R( 10 ) to R( 25 ). Partial areas R( 10 ) to R( 25 ) constitute a second portion different from the first portion, representing collective of adjacent partial areas. It is noted that a portion of the sensing image containing the first portion is referred to as “containing portion”.  
         [0050]     In the present embodiment, the entire area of the template image is divided into 64 partial areas. The entire fingerprint image is covered with these partial areas. Each partial area has a size as large as that of each partial area in the sensing image. These partial areas are provided with identification numbers G( 1 ) to G( 64 ) respectively.  FIG. 3  illustrates arrangement of these partial areas in image B. First area  1024  stores positional relation of partial areas G( 1 ) to G( 64 ).  
         [0051]     Processing unit  103  includes a correction unit  1031 , a search unit  1032 , a calculation unit  1033 , a determination unit  1034 , and a control unit  1035 . Correction unit  1031  performs density correction of image data input from input unit  101 . Search unit  1032  searches for a position in the template image that attains the highest matching score, for a plurality of partial areas of the sensing image. Calculation unit  1033  calculates similarity score based on a movement vector which will be described later, using information representing a result of search by search unit  1032 . Here, the “information representing a result of search” refers to information stored in reference block  1021 . Calculation unit  1033  also serves as a circuit calculating a value or the like for determining characteristic information which will be described later. Determination unit  1034  determines whether the result of collation of the fingerprint indicates “match”, “unmatch”, or “none of the former” based on the similarity score calculated by calculation unit  1033 . Control unit  1035  controls processing performed in each unit in processing unit  103 .  
         [0052]     Image collating apparatus  100  is implemented by computer hardware shown in  FIG. 4  and software executed by a CPU (Central Processing Unit)  622 . Referring to  FIG. 4 , the computer hardware described above includes input unit  101 , display  610  implemented by a liquid crystal display (or may be implemented by a CRT (Cathode-Ray Tube), however, in the present embodiment, it is assumed that display  610  is implemented by the liquid crystal display), CPU  622  for central management and control of the computer hardware itself, memory  624  including an ROM (Read Only Memory) or an RAM (Random Access Memory), fixed disk  626 , an FD drive  630  on which an FD (Flexible Disk)  632  is detachably mounted and which accesses to FD  632  mounted thereon, a CD-ROM drive  640  on which a CD-ROM (Compact Disk Read Only Memory) is detachably mounted and which accesses to the mounted CD-ROM  642 , a communication interface  680  for connecting the computer hardware to a communication network for establishing communication, a keyboard  650  accepting an input through keys, and a mouse  660  accepting an input through what is called a click-and-drag operation. These components are connected through a bus for communication. The computer hardware may be provided with a magnetic tape apparatus accessing to a cassette type magnetic tape that is detachably mounted thereto. In the present embodiment, however, it is assumed that such an apparatus is not provided. In general, such software is distributed with being stored in a recording medium such as FD  632  or CD-ROM  642 , read from the recording medium by FD drive  630 , CD-ROM drive  640  or the like, and once stored in fixed disk  626 . In addition, the software is read out to memory  624  and executed by CPU  622  described above. The computer hardware itself described above is common. Therefore, the most essential part of the present invention resides in the software recorded in a recording medium such as FD  632  or CD-ROM  642 .  
         [0053]     Referring to  FIG. 5 , the program executed in image collating apparatus  100  carries out control for collation of fingerprints as follows.  
         [0054]     In step  200  (hereinafter, step is abbreviated as S), control unit  1035  sends an image input start signal to input unit  101 , and thereafter waits until an image input end signal is received. Input unit  101  accepts input of the sensing image, and outputs the sensing image to image block  1023  in storage unit  102  through bus  105 . Reference block  1021  stores the image data of the sensing image. After the input of the sensing image is completed, input unit  101  sends the image input end signal to control unit  1035 . When the image input end signal is transmitted, control unit  1035  again sends the image input start signal to input unit  101 , and thereafter waits again until the image input end signal is received. Input unit  101  accepts input of the template image, and outputs the template image to image block  1023  in storage unit  102  through bus  105 . Image block  1023  stores the image data of the template image. After the input of the template image is completed, input unit  101  sends the image input end signal to control unit  1035 .  
         [0055]     In S 202 , control unit  1035  sends an image correction start signal to correction unit  1031 , and thereafter, waits until an image correction end signal is received. In most cases, the image accepted by input unit  101  is affected, in terms of tones of pixels and overall density distribution, by characteristics of input unit  101 , dryness of fingerprint itself, and pressure with which fingers are pressed. Therefore, the quality of the image accepted by input unit  101  is uneven. As the image quality is uneven, it is not appropriate to use the accepted image data directly for collation. Correction unit  1031  corrects the image quality of input image to suppress variations of conditions when the image is input. Specifically, the entire or partial area of the input image is subjected to histogram planarization or image binarization processing. Correction unit  1031  performs such processing onto both of the sensing image and the template image. After the processing for the sensing image and the template image ends, correction unit  1031  sends the image correction end signal to control unit  1035 . It is noted that histogram planarization refers to the processing executed as in the following steps. Specifically, in the first step, each pixel in the image is categorized based on a value representing density (density value). In the second step, the number of pixels having the same density value is counted. In the third step, the density value of each pixel is modified such that the number of pixels having the same density value is equal. A method of setting at which coordinate the density value of a pixel should be modified includes a method of extracting an arbitrary pixel and a method of referring to the density value of an adjacent pixel. In the present embodiment, the method of extracting an arbitrary pixel is employed for setting at which coordinate the density value of a pixel should be modified, because it is easy to create an algorithm. Alternatively, the image binarization processing refers to processing for modifying the density value to a maximum value or a minimum value depending on whether the density value of the pixel is equal to or greater than the threshold value determined in accordance with a method described later. The method of determining the threshold value includes what is called a p-tile method, a mode method, a differential histogram method, a discriminant analysis method, a variable threshold value method, and the like. In the present embodiment, the threshold value is determined using the mode method. The mode method refers to a method of determining the threshold value as in the following steps. Specifically, in the first step, the number of pixels for each density value is represented in a histogram. In the second step, the density value at which transition of the number of pixels for each density value turns from decrease to increase, that is, the bottom of the histogram, is detected, and this value is employed as the threshold value.  
         [0056]     In S 203 , control unit  1035  specifies characteristic information. Here, the “characteristic information” refers to information corresponding to classification of patterns in arrangement of pixels having the same color in the partial area. The processing for specifying the characteristic information refers to processing repeating the processing in S 210  to S 226  shown in  FIG. 7  for partial areas R( 1 ) to R( 25 ). The characteristic information will be described with reference to  FIG. 6 .  FIG. 6  illustrates a state of each pixel in a partial area. The partial area in the present embodiment is constituted of 16×16 pixels. Here, “16×16” means that the number of pixels in the horizontal direction and the number of pixels in the vertical direction are both set to “16”. In the present embodiment, the characteristic information is specified in the following procedure. The first procedure refers to a procedure for calculating a maximum value MAXHLEN of the number of black-filled pixels continuous in the horizontal direction. Here, maximum value MAXHLEN is the value representing how approximate to horizontal the pattern is (for example, lateral stripe). The second procedure is a procedure for calculating a maximum value MAXVLEN of the number of black-filled pixels continuous in the vertical direction. Here, maximum value MAXVLEN is the value representing how approximate to vertical the pattern is (for example, vertical stripe). The third procedure is a procedure for determining which of maximum value MAXHLEN and maximum value MAXVLEN is greater. If maximum value MAXHLEN is greater, the characteristic information is determined as a value “H” indicating horizontal (lateral stripe). If maximum value MAXVLEN is greater, the characteristic information is determined as a value “V” indicating vertical (vertical stripe). In the present embodiment, actually, if maximum value MAXVLEN is greater, the characteristic information is determined as either a value “R” indicating the vertical stripe extending toward upper right direction or a value “L” indicating the vertical stripe extending toward upper left direction, in accordance with the processing described later. Otherwise, the characteristic information is determined as “X”. If maximum value MAXHLEN and maximum value MAXVLEN are both smaller than the lower limit, the characteristic information is determined as “X”. In the present embodiment, the lower limit in the horizontal direction is represented as “HLEN(0)”, and the lower limit in the vertical direction is represented as “VLEN(0)”. The lower limit is set in advance, and the following equation expresses such definition: 
        if relation of MAXHLEN&gt;MAXVLEN and MAXHLEN≧HLEN (0) is satisfied, determination as “H” is made;     if relation of MAXVLEN&gt;MAXHLEN and MAXVLEN≧VLEN (0) is satisfied, determination as “V” is made; and     otherwise, determination as “X” is made.        
 
         [0060]     In S 204 , control unit  1035  rewrites the characteristic information. This processing corresponds to the processing in S 300  to S 304  shown in  FIG. 10 .  
         [0061]     In S 205 , processing unit  103  performs similarity score calculation and collation determination with regard to the sensing image and the template image. This processing corresponds to the processing in S 310  to S 334  shown in  FIG. 11 .  
         [0062]     In S 206 , control unit  1035  outputs information indicating the collation result to output unit  104 . The information indicating the collation result is stored in reference block  1021 . Output unit  104  outputs information output by control unit  1035 .  
         [0063]     Referring to  FIG. 7 , the program executed in image collating apparatus  100  carries out control for specifying the characteristic information as follows.  
         [0064]     In S 210 , control unit  1035  transmits a signal instructing start of determination to calculation unit  1033 . When the signal is transmitted, control unit  1035  waits until a signal indicating the end of determination is received. Calculation unit  1033  reads partial area R(I) to be subjected to determination from image block  1023 , and once stores the same in calculation block  1022 . Storage of partial area R(I) is carried out by substituting a value representing a color into a variable PIXEL (X,Y). Here, the “value representing a color” substituted into variable PIXEL (X,Y) refers to a value representing a color of each pixel constituting partial area R(I). In the present embodiment, if the color of the pixel is white, “0” is substituted into variable PIXEL (X,Y). If the color of the pixel is black, “1” is substituted into variable PIXEL (X,Y). Substitution of a value into variable PIXEL (X,Y) is carried out by storing the value in a prescribed area in calculation block  1022 .  
         [0065]     In S 212 , calculation unit  1033  reads partial area R(I) stored in calculation block  1022 . When partial area R(I) is read, calculation unit  1033  calculates maximum value MAXHLEN described above. This processing corresponds to the processing in S 230  to S 260  shown in  FIG. 8 .  
         [0066]     In S 214 , calculation unit  1033  reads partial area R(I) stored in calculation block  1022 . When partial area R(I) is read, calculation unit  1033  calculates maximum value MAXVLEN described above. This processing corresponds to the processing in S 270  to S 288  shown in  FIG. 9 .  
         [0067]     In S 216 , calculation unit  1033  determines whether relation of MAXHLEN&gt;MAXVLEN and MAXHLEN≧HLEN(0) is satisfied. If it is determined that relation of MAXHLEN&gt;MAXVLEN and MAXHLEN≧HLEN(0) is satisfied (YES in S 216 ), the process proceeds to S 218 . Otherwise (NO in S 216 ), the process proceeds to S 220 .  
         [0068]     In S 218 , calculation unit  1033  stores “H” in an area for storing the characteristic information of partial area R(I), included in first area  1024  or second area  1025 . When the characteristic information is stored, calculation unit  1033  transmits a signal indicating the end of determination to control unit  1035 .  
         [0069]     In S 220 , calculation unit  1033  determines whether relation of MAXVLEN&gt;MAXHLEN and MAXVLEN≧VLEN(0) is satisfied. If it is determined that relation of MAXHLEN&gt;MAXHLEN and MAXVLEN≧VLEN(0) is satisfied (YES in S 220 ), the process proceeds to S 221 . Otherwise (NO in S 220 ), the process proceeds to S 226 .  
         [0070]     In S 221 , calculation unit  1033  calculates total sum AS of logical products. Total sum AS of logical products is a value obtained by adding all the logical products of PIXEL (K,K) through PIXEL (LIM-K,LIM-K) from a case of K=0 to a case of K=LIM. Here, LIM represents the maximum value of a variable K. In the present embodiment, LIM is set to 15 (LIM=15).  
         [0071]     In S 222 , determination unit  1034  determines whether total sum AS of logical products is equal to or greater than a threshold value TF. If it is determined that total sum AS of logical products is equal to or greater than threshold value TF (YES in S 222 ), the process proceeds to S 223 . Otherwise (NO in S 222 ), the process proceeds to S 224 .  
         [0072]     In S 223 , calculation unit  1033  stores “L” in an area for storing the characteristic information of partial area R(I), included in first area  1024  or second area  1025 . When the characteristic information is stored, calculation unit  1033  transmits a signal indicating the end of determination to control unit  1035 .  
         [0073]     In S 224 , calculation unit  1033  stores “R” in an area for storing the characteristic information of partial area R(I), included in first area  1024  or second area  1025 . When the characteristic information is stored, calculation unit  1033  transmits a signal indicating the end of determination to control unit  1035 .  
         [0074]     In S 226 , calculation unit  1033  stores “X” in an area for storing the characteristic information of partial area R(I), included in first area  1024  or second area  1025 . When the characteristic information is stored, calculation unit  1033  transmits a signal indicating the end of determination to control unit  1035 .  
         [0075]     Referring to  FIG. 8 , the program executed in image collating apparatus  100  carries out control for calculating maximum value MAXHLEN as follows.  
         [0076]     In S 230 , calculation unit  1033  initializes maximum value MAXHLEN and a counter variable J. Thus, MAXHLEN and J are set to 0 (MAXHLEN=0, J=0).  
         [0077]     In S 232 , calculation unit  1033  determines whether relation of J&gt;M is satisfied. Here, a constant M refers to the maximum value of the number of pixels constituting the partial area that are arranged in the horizontal direction or the maximum value of the number of pixels constituting the partial area that are arranged in the vertical direction. In the present embodiment, as the maximum value of the number of pixels arranged in the horizontal direction is equal to the maximum value of the number of pixels arranged in the vertical direction, the same variable represents the maximum value of the number of pixels arranged in the horizontal direction and the maximum value of the number of pixels arranged in the vertical direction. If it is determined that relation of J&gt;M is satisfied (YES in S 232 ), the process proceeds to S 234 . Otherwise (NO in S 232 ), the process proceeds to S 236 .  
         [0078]     In S 234 , calculation unit  1033  outputs the value represented by maximum value MAXHLEN to calculation block  1022 .  
         [0079]     In S 236 , calculation unit  1033  initializes a counter variable I, a variable C representing a color of the pixel, the number LEN of pixels adjacent to each other having the same color, and a maximum value MAX of the number of pixels adjacent to each other in a row or in a column and having the same color. Thus, I, C, LEN, and MAX are set to 0 (I=0, C=0, LEN=0, and MAX=0).  
         [0080]     In S 238 , calculation unit  1033  determines whether relation of I&gt;M is satisfied. If it is determined that relation of I&gt;M is satisfied (YES in S 238 ), the process proceeds to S 240 . Otherwise (NO in S 238 ), the process proceeds to S 250 .  
         [0081]     In S 240 , calculation unit  1033  determines whether relation of MAX&lt;LEN is satisfied. If it is determined that relation of MAX&lt;LEN is satisfied (YES in S 240 ), the process proceeds to S 242 . Otherwise (NO in S 240 ), the process proceeds to S 244 . In S 242 , calculation unit  1033  substitutes the number LEN of pixels into maximum value MAX.  
         [0082]     In S 244 , calculation unit  1033  determines whether relation of MAXHLEN&lt;MAX is satisfied. If it is determined that relation of MAXLEN&lt;MAX is satisfied (YES in S 244 ), the process proceeds to S 246 . Otherwise (NO in S 244 ), the process proceeds to S 248 . In S 246 , calculation unit  1033  substitutes the value of maximum value MAX into maximum value MAXHLEN. In S 248 , calculation unit  1033  increases the value of counter variable J by “1”.  
         [0083]     In S 250 , calculation unit  1033  determines whether relation of C=1 and C=PIXEL (I,J) is satisfied. Here, variable C represents the color of the pixel, and variable PIXEL (I,J) represents the color of the pixel at a coordinate (I,J). If it is determined that relation of C=1 and C=PIXEL (I,J) is satisfied (YES in S 250 ), the process proceeds to S 252 . Otherwise (NO in S 250 ), the process proceeds to S 254 . In S 252 , calculation unit  1033  increases the value of the number LEN of the pixels by “1”.  
         [0084]     In S 254 , calculation unit  1033  determines whether relation of C=1 and MAX&lt;LEN is satisfied. If it is determined that relation of C=1 and MAX&lt;LEN is satisfied (YES in S 254 ), the process proceeds to S 256 . Otherwise (NO in S 254 ), the process proceeds to S 258 . In S 256 , calculation unit  1033  substitutes the value of the number LEN of pixels into maximum value MAX. In S 258 , calculation unit  1033  substitutes the value of variable PIXEL (I,J) into the number LEN of pixels. In addition, calculation unit  1033  substitutes the value of variable PIXEL (I,J) into variable C. In S 260 , calculation unit  1033  increases the value of counter variable I by “1”.  
         [0085]     Referring to  FIG. 9 , the program executed in image collating apparatus  100  carries out control for calculating maximum value MAXVLEN as follows. It is noted that the processing in the flowchart in  FIG. 9  that has been shown in  FIG. 8  described previously is given the same step number, and the processing is also the same. Therefore, detailed description thereof will not be repeated.  
         [0086]     In S 270 , calculation unit  1033  initializes maximum value MAXVLEN and counter variable I. Thus, MAXVLEN and I are set to 0 (MAXVLEN=0, I=0).  
         [0087]     In S 272 , calculation unit  1033  determines whether relation of I&gt;M is satisfied. If it is determined that relation of I&gt;M is satisfied (YES in S 272 ), the process proceeds to S 274 . Otherwise (NO in S 272 ), the process proceeds to S 276 . In S 274 , calculation unit  1033  outputs the value represented by maximum value MAXVLEN to calculation block  1022 .  
         [0088]     In S 276 , calculation unit  1033  initializes counter variable J, variable C representing a color of the pixel, the number LEN of pixels adjacent to each other having the same color, and maximum value MAX of the number of pixels adjacent to each other in a row or in a column and having the same color. Thus, J, C, LEN, and MAX are set to 0 (J=0, C=0, LEN=0, and MAX=0).  
         [0089]     In S 278 , calculation unit  1033  determines whether relation of J&gt;M is satisfied. If it is determined that relation of J&gt;M is satisfied (YES in S 278 ), the process proceeds to S 280 . Otherwise (NO in S 278 ), the process proceeds to S 250 .  
         [0090]     In S 280 , calculation unit  1033  determines whether relation of MAX&lt;LEN is satisfied. If it is determined that relation of MAX&lt;LEN is satisfied (YES in S 280 ), the process proceeds to S 242 . Otherwise (NO in S 280 ), the process proceeds to S 282 .  
         [0091]     In S 282 , calculation unit  1033  determines whether relation of MAXVLEN&lt;MAX is satisfied. If it is determined that relation of MAXVLEN&lt;MAX is satisfied (YES in S 282 ), the process proceeds to S 284 . Otherwise (NO in S 282 ), the process proceeds to S 286 . In S 284 , calculation unit  1033  substitutes the value of maximum value MAX into maximum value MAXVLEN. In S 286 , calculation unit  1033  increases the value of counter variable I by “1”. In S 288 , calculation unit  1033  increases the value of counter variable J by “1”.  
         [0092]     Referring to  FIG. 10 , the program executed in image collating apparatus  100  carries out control for rewriting the characteristic information as follows.  
         [0093]     In S 300 , control unit  1035  reads the characteristic information of partial area R(I) from the area storing the characteristic information of partial area R(I). The area storing the characteristic information of partial area R(I) is a part of first area  1024  or a part of second area  1025 .  
         [0094]     In S 302 , control unit  1035  determines whether partial area R(I) is non eligible for collation. In the present embodiment, “collation” refers to determination as to a possibility that the partial area matches with any portion of the template image. In the present embodiment, control unit  1035  determines as non eligible for collation, partial area R(I) having the characteristic information “X” or “E” (meaning of “E” will be described later), of which adjacent partial area also has the characteristic information “X” or “E”. Control unit  1035  thus detects as the excluded area, an area having the predetermined information as the characteristic information. In the present embodiment, the area non eligible for collation among the partial areas that are portions of the sensing image is referred to as the “excluded area”. In order to determine whether an area is non eligible for collation, control unit  1035  refers to the characteristic information of partial area R(I), sequentially from R( 1 ), R( 2 ), R( 3 ), and so on. If the characteristic information is determined as “X” or “E” (the partial area having the characteristic information “X” or “E” is referred to as the “partial area to be subjected to determination” in S 300  to S 304 ), control unit  1035  refers to the characteristic information of the partial areas that are arranged above, under, to the left of, to the right of, in the upper right of, in the lower right of, in the upper left of, and in the lower left of, the partial area to be subjected to determination (such a partial area is referred to as the “adjacent partial area” in S 300  to S 304 ), respectively. If the adjacent partial area has the characteristic information “X” or “E”, control unit  1035  determines the partial area to be subjected to determination as the excluded area.  
         [0095]     In S 304 , control unit  1035  rewrites characteristic information “X” of partial area R(I) to be subjected to determination with “E”. In order to rewrite the characteristic information, control unit  1035  overwrites the area storing the characteristic information of partial area R(I) with “E” and stores the same. As can clearly be seen from the processing in S 304 , the partial area having the characteristic information “E” refers to the partial area determined to have the characteristic information “X” as a result of processing in S 226  as well as to the partial area adjacent thereto.  
         [0096]     Referring to  FIG. 11 , the program executed in image collating apparatus  100  carries out control for similarity score calculation and collation determination as follows.  
         [0097]     In S 310 , control unit  1035  sends a collation determination start signal to determination unit  1034 . When the signal is transmitted, control unit  1035  waits until a collation determination end signal is received. Determination unit  1034  sets the central area in  FIG. 2 , that is, partial areas R( 1 ) to R( 9 ), as the partial area to be subjected to matching (similarity score calculation and collation determination). More specifically, determination unit  1034  sets an index minimum value IMIN of the partial area to “1”. In the present embodiment, the “index” refers to suffix I of partial area R(I). When minimum value IMIN is set, determination unit  1034  sets an index maximum value IMAX of the partial area to “9”. In setting the partial area to be subjected to matching in this step, the area should include a portion of a finger close to the distal interphalangeal joint rather than the tip end. Particularly, it is important to set the partial area such that the center of the arc of the fingerprint is included. This is because, if such a portion is set as the partial area, whether or not the fingerprints match with each other can readily be determined. The reason why matching can readily be determined is that difference between individuals in this portion is empirically significant. In the present embodiment, the total area of partial areas R( 1 ) to R( 9 ) occupies approximately 30% of the projection area of the finger in the sensing image. The reason why the area is determined as such is that it is empirically desirable for the total area of partial areas R( 1 ) to R( 9 ) to occupy 25 to 40% of the projection area of the finger in the sensing image.  
         [0098]     In S 312 , determination unit  1034  reads the characteristic information from the area storing the characteristic information of partial area R(I). Here, the characteristic information of partial areas R( 1 ) to R( 9 ) is read.  
         [0099]     In S 314 , determination unit  1034  determines whether characteristic information “E” is present among the characteristic information read in S 312 . In the present embodiment, the partial area having the characteristic information “E” is the excluded area. If it is determined that “E” is present (YES in S 314 ), the process proceeds to S 316 . Otherwise (NO in S 314 ), the process proceeds to S 324 .  
         [0100]     In S 316 , search unit  1032  or the like skips the process for partial areas R( 1 ) to R( 9 ) and carries out matching and similarity score calculation with regard to the partial area reset by determination unit  1034 . This processing corresponds to the processing in S 340  to S 380  shown in  FIG. 12 .  
         [0101]     In S 318 , determination unit  1034  determines whether a maximum value P(A,B) of the similarity score stored at a prescribed address in storage unit  102  is equal to or greater than a predetermined threshold value T(0). If it is determined that maximum value P(A,B) is equal to or greater than threshold value T(0) (YES in S 318 ), the process proceeds to S 320 . Otherwise (NO in S 318 ), the process proceeds to S 322 . If the partial area in the first portion includes the excluded area, determination unit  1034  determines whether there is a probability that the partial area other than the excluded area matches with the template image, based on the similarity score.  
         [0102]     In S 320 , determination unit  1034  outputs information indicating “match” (for example, a value of “1”) to reference block  1021 . In S 322 , determination unit  1034  outputs information indicating “unmatch” (for example, a value of “0”) to reference block  1021 .  
         [0103]     In S 324 , search unit  1032  or the like carries out matching and similarity score calculation with regard to the partial area set by determination unit  1034 . This processing corresponds to the processing in S 342  to S 380  and the processing in S 400  to S 410  shown in  FIG. 13 .  
         [0104]     In S 326 , calculation unit  1033  stores the value of maximum value P(A,B) of the similarity score at a prescribed address in memory  102 . When the value is stored, calculation unit  1033  transmits a similarity score calculation end signal to control unit  1035 . Determination unit  1034  determines whether maximum value P(A,B) of the similarity score is smaller than a threshold value T(2). If it is determined that maximum value P(A,B) is smaller than threshold value T(2) (YES in S 326 ), the process proceeds to S 322 . Otherwise (NO in S 326 ), the process proceeds to S 328 . As a result of this processing, if all the partial areas in the first portion are the considered areas, determination unit  1034  determines whether there is a probability that the first portion matches with any portion of the template image.  
         [0105]     In S 328 , determination unit  1034  determines whether maximum value P(A,B) of the similarity score is equal to or greater than a threshold value T(1), which is greater than threshold value T(2). If it is determined that maximum value P(A,B) is equal to or greater than threshold value T(1) (YES in S 328 ), the process proceeds to S 320 . Otherwise (NO in S 328 ), the process proceeds to S 330 . Thus, determination unit  1034  determines whether there is a probability that the considered area matches with any portion of the template image, based on the similarity score.  
         [0106]     In S 330 , determination unit  1034  sets the peripheral area in  FIG. 2 , that is, partial areas R( 10 ) to R( 25 ), as the partial area to be subjected to matching. More specifically, determination unit  1034  sets index minimum value IMIN of the partial area to “10”. In addition, determination unit  1034  sets index maximum value IMAX of the partial area to “25”.  
         [0107]     In S 332 , search unit  1032  or the like carries out matching and similarity score calculation with regard to the partial area set by determination unit  1034 . The processing corresponds to the processing in S 342  to S 380  and the processing in S 400  to S 410  shown in  FIG. 13 .  
         [0108]     In S 334 , determination unit  1034  determines whether maximum value P(A,B) of the similarity score is equal to or greater than threshold value T(1). If it is determined that maximum value P(A,B) is equal to or greater than threshold value T(1) (YES in S 334 ), the process proceeds to S 320 . Otherwise (NO in S 334 ), the process proceeds to S 332 . Thus, determination unit  1034  determines whether the partial area other than the excluded area in the sensing image matches with any portion of the template image, when there is a probability that the first portion matches with any portion of the template image. This is because whether the first portion matches with any portion of the template image has been determined in the processing in S 324  to S 328 .  
         [0109]     Referring to  FIG. 12 , the program executed in image collating apparatus  100  carries out control for matching and similarity score calculation as follows.  
         [0110]     In S 340 , control unit  1035  sends a matching start signal to search unit  1032 . Thereafter, control unit  1035  waits until a matching end signal is received. Search unit  1032  sets the value of counter variable I to “1”.  
         [0111]     In S 342 , search unit  1032  copies the image of partial area R(I) in the sensing image to reference block  1021 . The shape of partial area R(I) is not particularly specified. In the present embodiment, it is assumed that partial area R(I) has a rectangular shape, because calculation is facilitated. In addition, partial area R(I) in the present embodiment refers to such an area that a line traversing partial area R(I) and extending orthogonal to the ridge (line forming the pattern of the fingerprint) is at least twice and at most three times as long as the sum of the width of the ridge and the width of a ridge recess (recess between the ridges). The reason why the shape of the partial area is set as such is that it is empirically clear that the fingerprint can be collated with high accuracy. If the shape of the partial area is set in this manner, the average value of the width of the ridge or the width of the recess between the ridges, that has been measured in advance, serves as the basis for the size of the partial area.  
         [0112]     In S 344 , search unit  1032  reads characteristic information CR(I) of partial area R(I) from storage unit  102 . When variable I has a value in a range from “1” to “9”, characteristic information CR(I) is read from first area  1024 . If variable I has a value other than these, characteristic information CR(I) is read from second area  1025 .  
         [0113]     In S 346 , search unit  1032  searches for a location attaining the highest matching score within the image, in the image copied in S 342 , because the location attaining the highest matching score within the image is also the location at which data within the image attains the best match. Here, searching is carried out in a portion not having characteristic information CR(I) determined as “E”, among the partial areas. Search unit  1032  calculates a matching score C(I,S,T). Here, the “matching score” refers to a value representing a probability that the partial area other than the excluded area in the sensing image matches with any portion of the template image. When matching score C(I,S,T) is calculated, search unit  1032  stores the value of matching score C(I,S,T) in reference block  1021 , in association with counter variable I and a coordinate (S,T) of the template image. In calculating matching score C(I,S,T), the following equation is used.  
               C   ⁡     (     I   ,   S   ,   T     )       =       ∑     Y   =   1     H     ⁢       ∑     X   =   1     W     ⁢     (       V   ⁡     (   0   )       -            R   ⁡     (     I   ,   X   ,   Y     )       -     B   ⁡     (       S   +   X     ,     T   +   Y       )                )                 (   1   )             
 
         [0114]     Here, R(I,X,Y) represents the value of density of the pixel at coordinate (X,Y) in partial area R(I). B(S+X,T+Y) represents the value of density of the pixel at coordinate (S+X,T+Y) in the template image. If coordinate (S+X,T+Y) exceeds the maximum value of the coordinate of the template image, the value of B(S+X,T+Y) is set to “0”. W and H represent a width and a height of partial area R(I) respectively. V(0) represents the maximum density value of each pixel in the sensing image and the template image. As described above, matching score C(I,S,T) represents the probability of matching between the area having width W and height H in the template image with coordinate (S,T) being as origin and partial area R(I). In partial area R(I), partial area M(I) has the highest matching score C(I,S,T). In the present embodiment, the coordinate of partial area R(I) and the coordinate of the template image are both represented with the upper left vertex being the origin.  
         [0115]     In S 348 , search unit  1032  causes storage unit  102  to store a maximum value CIMAX of matching score C(I,S,T) calculated in S 346 . In S 346 , matching score C(I,S,T) is calculated for each coordinate (S,T) of image B, in the same partial area R(I). As matching score C(I,S,T) is calculated for each coordinate (S,T) of image B, search unit  1032  can specify maximum value CIMAX from among all calculated matching scores C(I,S,T). If variable I has a value in a range from “1” to “9”, maximum value CIMAX is stored in first area  1024 . Otherwise, maximum value CIMAX is stored in second area  1025 .  
         [0116]     In S 350 , search unit  1032  calculates a movement vector V(I). When movement vector V(I) is calculated, search unit  1032  causes storage unit  102  to store movement vector V(I). If the value “I” is in a range from “1” to “9”, movement vector V(I) is stored in first area  1024 . Otherwise, movement vector V(I) is stored in second area  1025 . As can clearly be seen from equation (2), the “movement vector” refers to a directional vector from the upper left vertex of partial area R(I) to the upper left vertex of the area attaining the best match in the template image (partial area M(I)) when the upper left vertex of the sensing image is superimposed on the upper left vertex of the template image. In general, magnitude of movement vector V(I) is not “0”, because the position of the fingerprint in the image is different between the sensing image and the template image. The reason why the position of the fingerprint is different is that the finger is placed in various manners on input unit  101 . In calculating movement vector V(I), the following equation is used. 
 
 V ( I )=( VIX, VIY )=( MIX−RIX,MIY−RIY )   (2) 
 
         [0117]     Variables RIX and RIY represent x and y coordinates at the reference position of partial area R(I). In the present embodiment, (RIX,RIY) represents the coordinate in the upper left corner of partial area R(I) in the sensing image. Variables MIX and MIY represent x and y coordinates of partial area M(I). In the present embodiment, (MIX,MIY) represents the coordinate in the upper left corner of partial area M(I).  
         [0118]     In S 352 , search unit  1032  determines whether the value of counter variable I is equal to or smaller than the total number N of the partial areas. If it is determined that the value of counter variable I is equal to or smaller than the total number N (YES in S 352 ), the process proceeds to S 354 . Otherwise (NO in S 352 ), the process proceeds to S 356 . In S 354 , search unit  1032  increases the value of counter variable I by “1”.  
         [0119]     In S 356 , search unit  1032  transmits a matching end signal to control unit  1035 . Control unit  108  transmits a signal instructing start of similarity score calculation to calculation unit  1033 . When the signal is transmitted, control unit  1035  waits until the similarity score calculation end signal is received. When the signal instructing start of similarity score calculation is received, calculation unit  1033  initializes maximum value P(A,B) of the similarity score to “0”. In the present embodiment, maximum value P(A,B) of the similarity score is a variable storing the maximum value of the similarity score between the sensing image and the template image.  
         [0120]     In S 358 , calculation unit  1033  initializes the value of counter variable I to “1”. In S 360 , calculation unit  1033  initializes a similarity score P(I) as to reference movement vector V(I) to “0”. In S 362 , calculation unit  1033  initializes the value of counter variable J to “1”.  
         [0121]     In S 364 , calculation unit  1033  calculates a vector difference dVIJ between reference movement vector V(I) and a movement vector V(J) to be compared, in accordance with the following equation.  
                   dVIJ   =            V   ⁡     (   I   )       -     V   ⁡     (   J   )                          =     SQRT   ⁡     (   F   )                   =     SQRT   ⁡     (         (     VIX   -   VJX     )     2     +       (     VIY   -   VJY     )     2       )                     (   3   )             
 
         [0122]     Variables VIX and VIY represent x direction and y direction components of movement vector V(I) respectively. Variables VJX and VJY represent x direction and y direction components of movement vector V(J) respectively. Function SQRT(F) represents square root of value F.  
         [0123]     In step S 366 , calculation unit  1033  determines whether movement vectors V(I) and V(J) are substantially the same. Specifically, calculation unit  1033  determines whether vector difference dVIJ is smaller than a constant ε. If it is determined that the movement vectors are substantially the same (YES in S 366 ), the process proceeds to step S 368 . Otherwise (NO in S 366 ), the process proceeds to step S 370 .  
         [0124]     In S 368 , calculation unit  1033  increases the value of similarity score P(I) in accordance with the following equation. Thus, calculation unit  1033  calculates the similarity score between at least a part of the sensing image and at least a part of the template image, based on positional relation between each considered area and each portion searched for by search unit  1032 . 
 
 P ( I )= P ( I )+α  (4) 
 
         [0125]     A variable α represents a value for increasing similarity score P(I). In the present embodiment, variable α can be set to any value at the time of design, such that it corresponds to magnitude of vector difference dVIJ. For example, if α is set to 1 (α=1), the value of similarity score P(I) represents the number of partial areas having the movement vector the same as reference movement vector V(I). As the number of partial areas having the movement vector the same as reference movement vector V(I) is represented, when a is set to 1 (α=1), calculation unit  1033  calculates the number of partial areas as the similarity score, the partial area satisfying a prescribed requirement of positional relation between a plurality of partial areas and the portion searched for by search unit  1032 . If α is set to CIMAX (α=CIMAX), similarity score P(I) represents the total sum of maximum matching score CIMAX.  
         [0126]     In S 370 , calculation unit  1033  determines whether counter variable J is smaller than the total number N of partial areas. If it is determined that counter variable J is smaller than the total number N of partial areas (YES in S 370 ), the process proceeds to S 372 . Otherwise (NO in S 370 ), the process proceeds to S 374 .  
         [0127]     In S 372 , calculation unit  1033  increases the value of counter variable J by “1”.  
         [0128]     In S 374 , calculation unit  1033  determines whether similarity score P(I) as to movement vector V(I) is greater than maximum value P(A,B) of the similarity score. If it is determined that similarity score P(I) is greater than maximum value P(A,B) of the similarity score (YES in S 374 ), the process proceeds to S 376 . Otherwise (NO in S 374 ), the process proceeds to S 378 .  
         [0129]     In S 376 , calculation unit  1033  substitutes the value of similarity score P(I) as to movement vector V(I) into maximum value P(A,B) of the similarity score.  
         [0130]     In S 378 , calculation unit  1033  determines whether the value of counter variable I is smaller than the total number N of partial areas. If it is determined that the value of counter variable I is smaller than the total number N of partial areas (YES in S 378 ), the process proceeds to S 380 . Otherwise (NO in S 378 ), the process ends. In S 380 , calculation unit  1033  increases the value of counter variable I by “1”.  
         [0131]     Referring to  FIG. 13 , the program executed in image collating apparatus  100  carries out control for similarity score calculation as follows. It is noted that the processing in the flowchart in  FIG. 13  that has been shown in  FIG. 12  described previously is given the same step number, and the processing is also the same. Therefore, detailed description thereof will not be repeated.  
         [0132]     In S 400 , control unit  1035  sends a matching start signal to search unit  1032 . Thereafter, control unit  1035  waits until a matching end signal is received. Search unit  1032  substitutes above-described index minimum value IMIN into counter variable I.  
         [0133]     In S 402 , search unit  1032  searches for an area attaining the highest matching score within the template image, that is, an area where data within the image attains the best match, in partial area R(I) of which image was copied in S 342 . Maximum matching score CIMAX for partial area R(I) copied in S 342  is thus calculated. This processing corresponds to the processing in S 420  to S 426  shown in  FIG. 14 .  
         [0134]     In S 404 , search unit  1032  determines whether the value of counter variable I is smaller than index maximum value IMAX of the considered partial area. If it is determined that the value of counter variable I is smaller than maximum value IMAX (YES in S 404 ), the process proceeds to S 354 . Otherwise (NO in S 404 ), the process proceeds to S 356 .  
         [0135]     In S 406 , calculation unit  1033  determines whether counter variable J is smaller than index maximum value IMAX of the partial area. If it is determined that counter variable J is smaller than maximum value IMAX (YES in S 406 ), the process proceeds to S 372 . Otherwise (NO in S 406 ), the process proceeds to S 408 .  
         [0136]     In S 408 , calculation unit  1033  determines whether similarity score P(I) as to movement vector V(I) is greater than maximum value P(A,B) of the similarity score. If it is determined that similarity score P(I) is greater than maximum value P(A,B) of the similarity score (YES in S 408 ), the process proceeds to S 376 . Otherwise (NO in S 408 ), the process proceeds to S 410 .  
         [0137]     In S 410 , calculation unit  1033  determines whether the value of counter variable I is smaller than index maximum value IMAX of the partial area. If it is determined that the value of counter variable I is smaller than index maximum value IMAX (YES in S 410 ), the process proceeds to S 380 . Otherwise (NO in S 410 ), the process ends.  
         [0138]     Referring to  FIG. 14 , the program executed in image collating apparatus  100  carries out control for searching for area M(I), that is, for calculating the matching score, as follows.  
         [0139]     In S 420 , search unit  1032  calculates matching score C(I,S,T), using the equation the same as in S 346 . When matching score C(I,S,T) is calculated, search unit  1032  stores the value of matching score C(I,S,T) in reference block  1021 , in association with counter variable I and coordinate (S,T) of image B.  
         [0140]     In S 422 , search unit  1032  determines whether there is a coordinate for which matching score C(I,S,T) has not yet been calculated, among the coordinates of the template image. If it is determined that there is a coordinate for which matching score C(I,S,T) has not yet been calculated (YES in S 422 ), the process proceeds to S 424 . Otherwise (NO in S 422 ), the process proceeds to S 426 .  
         [0141]     In S 424 , search unit  1032  updates coordinate (S,T) of the template image to a coordinate adjacent to the coordinate for which matching score C(I,S,T) has been calculated in S 422 . In the present embodiment, if there is not an adjacent coordinate, search unit  1032  updates coordinate (S,T) of the template image to a coordinate directly under the coordinate for which matching score C(I,S,T) has been calculated in S 422 . In the present embodiment, the initial value for coordinate (S,T) is set to (0,0). The coordinate (0,0) represents the coordinate in the upper left of the template image.  
         [0142]     In S 426 , search unit  1032  searches for the maximum value among matching scores C(I,S,T) stored in reference block  1021 . When maximum variable CIMAX of matching score C(I,S,T) is searched for, search unit  1032  assumes the following area as the area attaining the highest matching score with partial area R(I). Specifically, the area is an area having width W and height H, with the coordinate for which maximum variable CIMAX has been calculated as origin, among coordinates (S,T) of the template image. It is noted that the area assumed to attain the highest matching score with partial area R(I) is referred to as partial area M(I).  
         [0143]     An operation of image collating apparatus  100  based on the configuration and the flowchart as above will now be described.  
         [0144]     [Example in Which the Partial Area Having the Characteristic Information “E” is Present and the Value of HLEN(0) is Set to “2”] 
         [0145]     An operation of image collating apparatus  100  when the value of HLEN(0) is set to “2” will now be described.  
         [0146]     Control unit  1035  sends the image input start signal to input unit  101 . Input unit  101  accepts input of the sensing image, and outputs the sensing image to image block  1023  in storage unit  102  through bus  105 . Reference block  1021  stores the image data of the sensing image.  FIG. 15  illustrates an exemplary sensing image input at this time. There is a blur seen in the lower right portion of the image. Input unit  101  accepts the input of the template image, and outputs the same to image block  1023  in storage unit  102  through bus  105 . Image block  1023  stores the image data of the template image.  FIG. 16  illustrates an exemplary template image input at this time. After acceptance of the template image is completed, input unit  101  sends an image acceptance end signal to control unit  1035  (S 200 ).  
         [0147]     When the signal is sent, control unit  1035  sends the image correction start signal to correction unit  1031 . Correction unit  1031  corrects the image quality of input image to suppress variations of conditions when the image is input. After correction ends, correction unit  1031  sends the image correction end signal to control unit  1035  (S 202 ).  
         [0148]     When the signal is sent, control unit  1035  sends a signal instructing start of determination to calculation unit  1033 . Calculation unit  1033  reads partial area R( 1 ) to be subjected to determination from image block  1023 , and once stores the same in calculation block  1022  (S 210 ).  
         [0149]     When partial area R(I) is stored, calculation unit  1033  initializes maximum value MAXHLEN and counter variable J (S 230 ).  
         [0150]     When maximum value MAXHLEN and counter variable J are initialized, calculation unit  1033  determines whether relation of J&gt;M is satisfied (S 232 ). Here, as the value of constant M is set to “15” and the value of counter variable J is set to “0” (NO in S 232 ), calculation unit  1033  initializes counter variable I, variable C, the number LEN of pixels, and maximum value MAX (S 236 ). Thus, I, C, LEN, and MAX are set to 0 (I=0, C=0, LEN=0, and MAX=0).  
         [0151]     When counter variable I and the like are initialized, calculation unit  1033  determines whether relation of I&gt;M is satisfied (S 238 ). Here, as the value of constant M is set to “15” and the value of counter variable I is set to “0” (NO in S 238 ), calculation unit  1033  determines whether relation of C=1 and C=PIXEL (I,J) is satisfied (S 250 ). Here, as C is set to 0 (C=0) in S 236  (NO in S 250 ), calculation unit  1033  determines whether relation of C=1 and MAX&lt;LEN is satisfied (S 254 ). Here, as C, LEN and MAX are set to 0 (C=0, LEN=0 and MAX=0) (NO in S 254 ), calculation unit  1033  substitutes the value of variable PIXEL (I,J) into the number LEN of pixels. In addition, calculation unit  1033  substitutes the value of variable PIXEL (I,J) into variable C (S 258 ). Here, when relation of PIXEL (0,0)=0 is satisfied, both the value of the number LEN of pixels and the value of variable C remain at “0”.  
         [0152]     When the value of variable PIXEL (I,J) is substituted into variable C, calculation unit  1033  increases the value of counter variable I by “1” (S 260 ). Thus, the value of counter variable I is set to “1”. If it is assumed that the color of all pixels in the first line is white (that is, the values of PIXEL (I,0) are all set to “0”), the processing in S 238  to S 260  is repeated until the value of counter variable I is set to “16”. It is assumed that the values of PIXEL (16,J) and PIXEL (I,16) are defined in advance as “0”. As to the value of counter variable I and the like at the time point when the value of counter variable I is set to “16”, I is set to 15 and C and LEN are set to 0 (I=15, C=0, and LEN=0).  
         [0153]     After the processing in S 238  to S 260  is repeated, calculation unit  1033  determines whether relation of I&gt;M is satisfied (S 238 ). Here, as the value of constant M is set to “15” and the value of counter variable I is set to “16” (YES in S 238 ), calculation unit  1033  determines whether relation of MAX&lt;LEN is satisfied (S 240 ). Here, as C, LEN and MAX are set to 0 (C=0, LEN=0 and MAX=0) (NO in S 240 ), calculation unit  1033  determines whether relation of MAXHLEN&lt;MAX is satisfied (S 244 ). Here, as MAXHLEN and MAX are set to 0 (MAXHLEN=0, MAX=0) (NO in S 244 ), calculation unit  1033  increases the value of counter variable J by “1” (S 248 ). Thus, the value of counter variable J is set to “1”. Thereafter, while the value of counter variable J is in a range from “1” to “15”, the processing in S 232  to S 248  is repeated.  
         [0154]     Thereafter, at the time point when the value of counter variable J is set to “16”, calculation unit  1033  determines whether relation of J&gt;M is satisfied (S 232 ). Here, as the value of counter variable J is set to “16” and the value of constant M is set to “15” (YES in S 232 ), calculation unit  1033  outputs the value represented by maximum value MAXHLEN to calculation block  1022  (S 234 ). Here, it is assumed that “15” is output as the value of maximum value MAXHLEN.  
         [0155]     When the value represented by maximum value MAXHLEN is output, calculation unit  1033  initializes maximum value MAXVLEN and counter variable I (S 270 ). Thus, MAXVLEN and I are set to 0 (MAXVLEN=0, I=0).  
         [0156]     When maximum value MAXVLEN and counter variable I are initialized, calculation unit  1033  determines whether relation of I&gt;M is satisfied (S 272 ). Here, as the value of counter variable I is set to “0” and the value of constant M is set to “15” (YES in S 272 ), calculation unit  1033  initializes counter variable J, variable C representing a color of the pixel, the number LEN of pixels adjacent to each other having the same color, and maximum value MAX of the number of pixels adjacent to each other in a row or in a column and having the same color (S 276 ). Thus, J, C, LEN, and MAX are set to 0 (J=0, C=0, LEN=0, and MAX=0).  
         [0157]     When counter variable J and the like are initialized, calculation unit  1033  determines whether relation of J&gt;M is satisfied (S 278 ). Here, as the value of counter variable J is set to “0” and the value of constant M is set to “15” (NO in S 278 ), calculation unit  1033  determines whether relation of C=1 and C=PIXEL (I,J) is satisfied (S 250 ). Here, as C is set to 0 (C=0) (NO in S 250 ), calculation unit  1033  determines whether relation of C=1 and MAX&lt;LEN is satisfied (S 254 ). Here, as C, LEN and MAX are set to 0 (C=0, LEN=0 and MAX=0) (NO in S 254 ), calculation unit  1033  substitutes the value of variable PIXEL (I,J) into the number LEN of pixels. In addition, calculation unit  1033  substitutes the value of variable PIXEL (I,J) into variable C (S 258 ).  
         [0158]     When the value of the number LEN of pixels is increased by “1”, calculation unit  1033  increases the value of counter variable J by “1” (S 288 ). Thus, the value of counter variable J is set to “1”. When the value of counter variable J is increased by “1”, the processing in S 278  to S 288  is repeated until the value of counter variable J is set to “3”. It is assumed here that, as to the value of counter variable J and the like at the time point when the value of counter variable J is set to “3”, J is set to 3 and C and LEN are set to 0 (J=3, C=0, and LEN=0).  
         [0159]     Thereafter, calculation unit  1033  determines whether relation of J&gt;M is satisfied (S 278 ). Here, as the value of constant M is set to “15” and the value of counter variable J is set to “3” (NO in S 278 ), calculation unit  1033  determines whether relation of C=1 and C=PIXEL (I,J) is satisfied (S 250 ). Here, as C is set to 0 (C=0) (NO in S 250 ), calculation unit  1033  determines whether relation of C=1 and MAX&lt;LEN is satisfied (S 254 ). Here, as C and LEN are set to 0 (C=0, LEN=0) (NO in S 254 ), calculation unit  1033  substitutes the value of variable PIXEL (I,J) into the number LEN of pixels. In addition, calculation unit  1033  substitutes the value of variable PIXEL (I,J) into variable C (S 258 ). Thus, LEN and C are set to 1 (LEN=1, C=1).  
         [0160]     When the value is substituted into the number LEN of pixels and the like, the processing in S 278  to S 288  is repeated until the value of counter variable J is set to “16”. It is assumed here that, as to the value of counter variable J and the like at the time point when the value of counter variable J is set to “16”, J is set to 16 and C and LEN are set to 1 (J=16, C=1, and LEN=1).  
         [0161]     Thereafter, calculation unit  1033  determines whether relation of J&gt;M is satisfied (S 278 ). Here, as the value of constant M is set to “15” and the value of counter variable J is set to “16” (YES in S 278 ), calculation unit  1033  determines whether relation of MAX&lt;LEN is satisfied (S 280 ). Here, if C and LEN are set to 1 and MAX is set to 3 (C=1, LEN=1, and MAX=3) (NO in S 280 ), calculation unit  1033  determines whether relation of MAXVLEN&lt;MAX is satisfied (S 282 ). Here, if MAXVLEN is set to 0 and MAX is set to 3 (MAXVLEN=0, MAX=3) (YES in S 282 ), calculation unit  1033  substitutes the value of maximum value MAX into maximum value MAXVLEN (S 284 ). When the value is substituted, calculation unit  1033  increases the value of counter variable I by “1” (S 286 ). The value of counter variable I is set to “1”. Thereafter, while the value of counter variable I is in a range from “1” to “15”, the processing in S 272  to S 288  is repeated.  
         [0162]     Thereafter, at the time point when the value of counter variable I is set to “16”, calculation unit  1033  determines whether relation of I&gt;M is satisfied (S 272 ). At this time point, as the value of counter variable I is set to “16” and the value of constant M is set to “15” (YES in S 272 ), calculation unit  1033  outputs the value represented by maximum value MAXVLEN to calculation block  1022  (S 274 ). Here, it is assumed that “4” is output as the value of maximum value MAXVLEN.  
         [0163]     When the value represented by maximum value MAXVLEN is output, calculation unit  1033  determines whether relation of MAXHLEN&gt;MAXVLEN and MAXHLEN≧HLEN(0) is satisfied (S 216 ). Here, as MAXHLEN is set to 15, MAXVLEN is set to 4, and HLEN(0) is set to 2 (MAXHLEN=15, MAXVLEN=4, and HLEN(0)=2) (YES in S 216 ), calculation unit  1033  stores “H” in an area for storing the characteristic information of partial area R(I), included in first area  1024  or second area  1025 . When the characteristic information is stored, calculation unit  1033  transmits a signal indicating end of determination to control unit  1035  (S 218 ).  
         [0164]     The processing in S 210  to S 226  is repeated for each partial area.  FIG. 17  illustrates exemplary characteristic information read from first area  1024  or second area  1025  of storage unit  102 , in association with arrangement of each partial area. Thus, calculation unit  1033  extracts (specifies) each pixel column in the horizontal direction and vertical direction for each partial area, and determines tendency based on the number of black pixels in each extracted pixel column. The term “tendency” herein refers to any one of tendency that the pattern of the partial areas extends along the horizontal direction (for example, the tendency toward lateral stripe), tendency that the pattern of the partial areas extends along the vertical direction (for example, the tendency toward vertical stripe), and tendency corresponding to none of the former. Calculation unit  1033  outputs information in accordance with the result of determination of the tendency (any one of “R”, “L”, “V”, and “X”). This value indicates the characteristic information of the partial area.  
         [0165]     When the characteristic information of each partial area is stored, control unit  1035  reads the characteristic information of partial area R(I) from the area storing the characteristic information of partial area R(I) (S 300 ).  
         [0166]     When the characteristic information is read, control unit  1035  determines whether the partial area is non eligible for collation (S 302 ). In the case of  FIG. 17 , the characteristic information of R( 9 ) has been determined as “X”. Control unit  1035  refers to the characteristic information of the partial area adjacent to R( 9 ). Here, partial areas R( 20 ), R( 24 ) and R( 25 ) are the partial areas having the characteristic information “X” or “E”. When determination as to whether the partial area is non eligible for collation ends, control unit  1035  rewrites characteristic information “X” of the partial area to be subjected to determination with “E” (S 304 ). Thus, the characteristic information of partial areas R( 20 ), R( 24 ) and R( 25 ) is rewritten with “E”.  FIG. 18  illustrates exemplary characteristic information after the characteristic information of partial areas R( 20 ), R( 24 ) and R( 25 ) is rewritten with “E”, in association with arrangement of each partial area.  
         [0167]     In the present embodiment, if the fingerprint is handled as an image, the characteristic information of each partial area is represented by “H”, “R”, “L”, or “X”. Therefore, if there is a blur or an area to which no input is made on the sensor of input unit  101 , the characteristic information of that partial area is determined as “X”. Utilizing this characteristic, control unit  1035  detects an excluded area such as an image showing blur or an area to which the fingerprint image has not been input.  
         [0168]     If the characteristic information “X” is rewritten with “E”, control unit  1035  sends a collation determination start signal to determination unit  1034 . Determination unit  1034  sets the central area in  FIG. 2 , that is, partial areas R( 1 ) to R( 9 ), as the partial area to be subjected to matching (similarity score calculation and collation determination) (S 310 ).  
         [0169]     When the partial area is set, determination unit  1034  reads the characteristic information from the area storing the characteristic information of partial areas R( 1 ) to R( 9 ) (S 312 ). When the characteristic information is read, determination unit  1034  determines whether “E” indicating the partial area non eligible for collation is present among the read characteristic information (S 314 ). Here, as “E” is present (YES in S 314 ), control unit  1035  sends the matching start signal to search unit  1032 . Search unit  1032  sets the value of counter variable I to “1” (S 340 ).  
         [0170]     When the value of counter variable I is set to “1 ”, search unit  1032  copies the image of partial area R(I) to reference block  1021  (S 342 ). When the image is copied, search unit  1032  reads characteristic information CR(1) corresponding to partial area R( 1 ) from storage unit  102  (S 344 ). When characteristic information CR(I) is read, search unit  1032  searches for a location attaining the highest matching score within the image, in the image copied in S 342  (S 346 ). Here, searching is carried out in the portion not having characteristic information CR(I) determined as “E”, among the partial areas.  FIG. 19  is a conceptual view showing an input image from which the partial area determined as non eligible for collation has been removed. When the best matching location is searched for, search unit  1032  causes storage unit  102  to store maximum value CIMAX of matching score C(I,S,T) calculated in S 346  (S 348 ).  
         [0171]     When maximum matching score CIMAX is stored, search unit  1032  calculates movement vector V(I). When movement vector V(I) is calculated, search unit  1032  causes storage unit  102  to store movement vector V(I) (S 350 ).  
         [0172]     When movement vector V(I) is stored, search unit  1032  determines whether the value of counter variable I is equal to or smaller than the total number N of the partial areas (S 352 ). Here, as the value of counter variable I is equal to or smaller than the total number N (YES in S 352 ), search unit  1032  increases the value of counter variable I by “1” (S 354 ). Thereafter, the processing in S 342  to S 354  is repeated while the value of variable I is equal to or smaller than the total number N of the partial area. Maximum matching score CIMAX of each partial area R(I) and movement vector V(I) are thus calculated. As a result of calculation of maximum matching score CIMAX, search unit  1032  searches for the most similar portion in the template image, for each partial area R(I) which is the considered area.  
         [0173]     Thereafter, as the value of counter variable I exceeds the total number N of the partial areas (NO in S 352 ), search unit  1032  transmits the matching end signal to control unit  1035 . Control unit  1035  transmits the signal instructing start of similarity score calculation to calculation unit  1033 . Calculation unit  1033  calculates the similarity score, by using movement vector V(I) of each partial area R(I), maximum matching score CIMAX and the like, that are obtained in matching and stored in storage unit  102 . In order to do so, when the similarity score calculation start signal is received, calculation unit  1033  initializes maximum value P(A,B) of the similarity score to “0” (S 356 ). When maximum value P(A,B) of the similarity score is initialized, calculation unit  1033  initializes the value of counter variable I to “1” (S 358 ). When the value of counter variable I is initialized, calculation unit  1033  initializes similarity score P(I) as to reference movement vector V(I) to “0” (S 360 ). When similarity score P(I) is initialized, calculation unit  1033  initializes the value of counter variable J to “1” (S 362 ). When the value of counter variable J is initialized, calculation unit  1033  calculates vector difference dVIJ between reference movement vector V(I) and movement vector V(J) to be compared (S 364 ).  
         [0174]     When vector difference dVIJ is calculated, calculation unit  1033  determines whether movement vectors V(I) and V(J) are substantially the same (S 366 ). If it is determined that the movement vectors are substantially the same (YES in S 366 ), calculation unit  1033  increases the value of similarity score P(I) (S 368 ).  
         [0175]     When the value of similarity score P(I) is increased, calculation unit  1033  determines whether counter variable J is smaller than the total number N of partial areas (S 370 ). If it is determined that counter variable J is smaller than the total number N of partial areas (YES in S 370 ), calculation unit  1033  increases the value of counter variable J by “1” (S 372 ). As a result of the processing in S 360  to S 372 , similarity score P(I) using the information of the partial area determined to have the movement vector the same as reference movement vector V(I) is calculated.  
         [0176]     Thereafter, when counter variable J is equal to or greater than the total number N of partial areas (NO in S 370 ), calculation unit  1033  determines whether similarity score P(I) as to movement vector V(I) is greater than maximum value P(A,B) of the similarity score (S 374 ). Here, if it is assumed that similarity score P(I) is greater than maximum value P(A,B) of the similarity score (YES in S 374 ), calculation unit  1033  substitutes the value of similarity score P(I) as to movement vector V(I) into maximum value P(A,B) of the similarity score (S 376 ). In S 374  or S 376 , calculation unit  1033  assumes similarity score P(I) based on reference movement vector V(I) as most proper as the reference.  
         [0177]     When the value is substituted into maximum value P(A,B) of the similarity score, calculation unit  1033  determines whether the value of counter variable I of reference movement vector V(I) is smaller than the total number N of partial areas (S 378 ). As the value of counter variable I is initially smaller than the total number N of partial areas (YES in S 378 ), calculation unit  1033  increases the value of counter variable I by “1” (S 380 ). When the value of counter variable I is increased by “1”, the processing in S 360  to S 380  is repeated. As a result of the processing in S 356  to S 380 , the similarity score between the sensing image and the template image is calculated as the value of variable P(A,B). Calculation unit  1033  stores the calculated value of variable P(A,B) at the prescribed address of storage unit  102 , and transmits the similarity score calculation end signal to control unit  1035 .  
         [0178]     Thereafter, when the value of counter variable I is equal to or greater than the total number N of partial areas (NO in S 378 ), determination unit  1034  determines whether similarity score P(A,B) stored at the prescribed address in storage unit  102  is equal to or greater than predetermined threshold value T(0) (S 318 ). Determination unit  1034  thus determines whether there is a probability that the considered area which is the area other than the excluded area in the first portion matches with any portion of the template image. In addition, determination unit  1034  determines whether the partial area other than the excluded area of the sensing image matches with any portion of the template image, when there is a probability that any partial area of the first portion matches with any portion of the template image. If it is determined that similarity score P(A,B) is equal to or greater than threshold value T(0) (YES in S 318 ), determination unit  1034  outputs information indicating “match” to reference block  1021  (S 320 ).  
         [0179]     When the value is output, control unit  1035  outputs information indicating the result of collation stored in reference block  1021  to output unit  104 . Output unit  104  outputs the information output by control unit  1035  (S 206 ).  
         [0180]     [Example in Which the Partial Area Having the Characteristic Information “E” is Present, the Value of HLEN(0) is Set to “2”, and the Value of VLEN(0) is Set to “5”] 
         [0181]     An operation of image collating apparatus  100  when the partial area having the characteristic information “E” is present and the value of HLEN(0) is set to “5” will now be described.  
         [0182]     As a result of processing until S 274 , it is provisionally assumed that MAXHLEN is set to 3, MAXVLEN is set to 4, HLEN(0) is set to 2, and VLEN(0) is set to 5 (MAXHLEN=3, MAXVLEN=4, HLEN(0)=2, and VLEN(0)=5). Calculation unit  1033  determines whether relation of MAXHLEN&gt;MAXVLEN and MAXHLEN≧HLEN(0) is satisfied (S 216 ). Here, as MAXHLEN is set to 3, MAXVLEN is set to 4, and HLEN(0) is set to 2 (MAXHLEN=3, MAXVLEN=4, and HLEN(0)=2) (NO in S 216 ), calculation unit  1033  determines whether relation of MAXVLEN&gt;MAXHLEN and MAXVLEN≧VLEN(0) is satisfied (S 220 ). Here, as MAXHLEN is set to 3, MAXVLEN is set to 4, and VLEN(0) is set to 5 (MAXHLEN=3, MAXVLEN=4, and VLEN(0)=5) (NO in S 220 ), calculation unit  1033  stores “X” in an area for storing the characteristic information of partial area R(I), included in first area  1024  or second area  1025 . When the characteristic information is stored, calculation unit  1033  transmits the determination end indicating signal to control unit  1035  (S 226 ).  
         [0183]     [Example in Which the Partial Area Having the Characteristic Information “E” is Present, MAXHLEN is Set to 4 and MAXVLEN is Set to 15 (MAXHLEN=4, MAXVLEN=15), and the Value of VLEN(0) is Set to “2”] 
         [0184]     An operation of image collating apparatus  100  when MAXHLEN is set to 4 and MAXVLEN is set to 15 (MAXHLEN=4, MAXVLEN=15), and the value of VLEN(0) is set to “2” will now be described.  
         [0185]     As a result of processing until S 274 , it is provisionally assumed that MAXHLEN is set to 4, MAXVLEN is set to 15, and VLEN(0) is set to “2” (MAXHLEN=4, MAXVLEN=15, and VLEN(0)=2). When the value represented by maximum value MAXVLEN is output, calculation unit  1033  determines whether relation of MAXHLEN&gt;MAXVLEN and MAXHLEN≧HLEN(0) is satisfied (S 216 ). Here, as MAXHLEN is set to 4, MAXVLEN is set to 15, and VLEN(0) is set to “2” (MAXHLEN=4, MAXVLEN=15, and VLEN(0)=2) (NO in S 216 ), calculation unit  1033  determines whether relation of MAXVLEN&gt;MAXHLEN and MAXVLEN≧VLEN(0) is satisfied (S 220 ). Here, as MAXHLEN is set to 4, MAXVLEN is set to 15, and VLEN(0) is set to “2” (MAXHLEN=4, MAXVLEN=15, and VLEN(0)=2) (YES in S 220 ), calculation unit  1033  calculates total sum AS of logical products (S 221 ). When total sum AS of logical products is calculated, determination unit  1034  determines whether total sum AS of logical products is equal to or greater than threshold value TF (S 222 ). Here, if total sum AS of logical products is set to 3 and threshold value TF is set to 5 (total sum AS of logical products=3, threshold value TF=5) (NO in S 222 ), calculation unit  1033  stores “R” in an area storing the characteristic information of partial area R(I), included in first area  1024  or second area  1025 . When the characteristic information is stored, calculation unit  1033  transmits the signal indicating the end of determination to control unit  1035  (S 223 ).  
         [0186]     [Example in Which the Partial Area Having the Characteristic Information “E” is Not Present] 
         [0187]     When the characteristic information is read as a result of processing until S 312 , determination unit  1034  determines whether “E” indicating the partial area non eligible for collation is present among the read characteristic information (S 314 ). Here, as there is no “E” among the characteristic information (NO in S 314 ), control unit  1035  sends the matching start signal to search unit  1032 . Search unit  1032  sets index minimum value IMIN described above as the value of counter variable I (S 400 ).  
         [0188]     When index minimum value IMIN is set, after the processing in S 342 , search unit  1032  calculates matching score C(I,S,T). When matching score C(I,S,T) is calculated, search unit  1032  stores the value of matching score C(I,S,T) in reference block  1021 , in association with counter variable I and coordinate (S,T) of the template image (S 420 ).  
         [0189]     When the value of matching score C(I,S,T) is stored, search unit  1032  determines whether there is a coordinate for which matching score C(I,S,T) has not yet been calculated, among the coordinates of the template image (S 422 ). As there is initially a coordinate for which matching score C(I,S,T) has not yet been calculated (YES in S 422 ), search unit  1032  updates coordinate (S,T) of the template image to a coordinate adjacent to the coordinate for which matching score C(I,S,T) has been calculated in S 422  (S 424 ). When the coordinate is updated, the processing in S 422  to S 424  is repeated.  
         [0190]     When there is no longer a coordinate for which matching score C(I,S,T) has not yet been calculated (NO in S 422 ), search unit  1032  searches for the maximum value among matching scores C(I,S,T) stored in reference block  1021 . When maximum variable CIMAX of matching score C(I,S,T) is searched for, search unit  1032  assumes the area having width W and height H, with the coordinate at which maximum variable CIMAX has been calculated as origin, as the area attaining the highest matching score with partial area R(I), among coordinates (S,T) of the template image (S 426 ).  
         [0191]     When maximum variable CIMAX is searched for, after the processing in S 348  to S 350 , search unit  1032  determines whether the value of counter variable I is smaller than index maximum value IMAX of the considered partial area (S 404 ). If it is determined that the value of counter variable I is smaller than maximum value IMAX (YES in S 404 ), the processing in S 342  to S 354  is repeated after the processing in S 354 .  
         [0192]     Thereafter, if it is determined that the value of counter variable I is equal to or greater than maximum value IMAX (NO in S 404 ), after the processing in S 356  to S 368 , calculation unit  1033  determines whether counter variable J is smaller than index maximum value IMAX of the partial area (S 406 ). If it is determined that counter variable J is initially smaller than maximum value IMAX (YES in S 406 ), the processing in S 364  to S 372  is repeated after the processing in S 372 .  
         [0193]     Thereafter, if it is determined that counter variable J is equal to or greater than maximum value IMAX (NO in S 406 ), calculation unit  1033  determines whether similarity score P(I) as to movement vector V(I) is greater than maximum value P(A,B) of the similarity score (S 408 ). If it is determined that similarity score P(I) is greater than maximum value P(A,B) of the similarity score (YES in S 408 ), after the processing in S 376 , calculation unit  1033  determines whether the value of counter variable I is smaller than index maximum value IMAX of the partial area (S 410 ). Here, if it is assumed that the value of counter variable I is smaller than index maximum value IMAX (YES in S 410 ), the processing in S 360  to S 380  is repeated, after the processing in S 380 . As a result of the processing in S 356  to S 380  shown in  FIG. 13 , the similarity score between the sensing image and the template image is calculated as the value of variable P(A,B).  
         [0194]     Thereafter, if the value of counter variable I is equal to or greater than index maximum value IMAX (YES in S 410 ), calculation unit  1033  stores the value of variable P(A,B) at the prescribed address in memory  102 . When the value is stored, calculation unit  1033  transmits the similarity score calculation end signal to control unit  1035 . Determination unit  1034  determines whether maximum value P(A,B) of the similarity score is smaller than threshold value T(2) (S 326 ). Here, if it is determined that maximum value P(A,B) is equal to or greater than threshold value T(2) (NO in S 326 ), determination unit  1034  determines whether maximum value P(A,B) of the similarity score is equal to or greater than threshold value T(1), which is greater than threshold value T(2) (S 328 ). Here, if it is determined that maximum value P(A,B) of the similarity score is equal to or greater than threshold value T(1) (YES in S 328 ), determination unit  1034  outputs information indicating “match” (for example, a value of “1”) to reference block  1021  (S 320 ). It is thus determined that the sensing image and the template image were taken from the same fingerprint.  
         [0195]     As described above, the image collating apparatus according to the present embodiment is capable of processing for including all the central areas and the peripheral areas as the areas to be subjected to collation, at the time point when the image non eligible for collation is detected in the central area.  
         [0196]     For instance, an example in which R( 6 ), R( 8 ) and R( 9 ) shown in  FIG. 2  are non eligible for collation (having the characteristic information “E”) and the threshold value (T(0), T(1)) is set to “0.7” will be described. Here, if a collation method using solely the central portion of the image is employed and if collation with regard to the partial areas other than R( 6 ), R( 8 ) and R( 9 ) among the central areas is successful, the similarity score is expressed as in the equation below. As this value is smaller than the threshold value, collation eventually fails. 
 
the number of partial areas for which collation is successful/total number of areas=6/9=0.667 
 
         [0197]     If it is assumed that collation with regard to all peripheral areas is successful, the similarity score is expressed as in the equation below. This value means that collation is successful. 
 
the number of partial areas for which collation is successful/total number of areas=22/25=0.88 
 
         [0198]     Consequently, an image collating apparatus, an image collating method, and an image collating program product can be provided, in which collation ends when determination as to whether one image is the same as the other image can be made using only a part of one image and collation of a remaining portion of the image is not necessary, and even though a part of one image is non eligible for collation due to blur or the like, collation can still be carried out using the image that can originally be subjected to collation.  
         [0199]     As a variation, a program for implementing image collating apparatus  100  described above may be implemented as a data file used for spreadsheet software.  
         [0200]     In addition, as a variation, if there are a plurality of reference images, it is likely that most reference images do not match with the image to be collated. As unmatch with the image to be collated is likely, S 328  may not be performed, thus effectively saving time.  
         [0201]     Moreover, as a variation, the image data to be collated may be image data of characteristics of a living body except for fingerprint, such as those similar among individuals but not matching with each other.  
         [0202]     Further, as a variation, the image data to be collated may be image data of a linear pattern or other image data.  
         [0203]     In addition, as a variation, in the processing in S 210  to S 226 , instead of finding the characteristic information based on the number of continuous black pixels, the characteristic information may be found also based on the number of continuous white pixels.  
         [0204]     Moreover, as a variation, in S 302 , the criterion on which determination as to whether the partial area is non eligible for collation is made is not limited to that in the description above (at least two partial areas having the characteristic information “X” continue in at least one of the vertical direction, the lateral direction, and the oblique direction). For example, all partial areas having the characteristic information “X” may be determined as non eligible for collation. Control unit  1035  thus detects as the excluded area, any of the areas having the predetermined information as the characteristic information.,  
         [0205]     Further, as a variation, between S 328  and S 330 , search unit  1032  or the like may set a criterion value which is a value representing a probability that a portion of the sensing image including the first portion matches with any portion of the template image. Here, determination unit  1034  may determine whether the criterion value exceeds the threshold value. The threshold value used for determination is desirably a value corresponding to a size of the portion of the sensing image including the first portion.  
         [0206]     In addition, as a variation, the data of the template image may be data stored in advance.  
         [0207]     Moreover, as a variation, the processing in S 328  may not be performed. If the processing in S 328  is not performed, determination unit  1034  determines through the processing in S 334  whether the partial area other than the excluded area of the sensing image matches with any portion of the template image, when the first portion matches with any portion of the template image.  
       Second Embodiment  
       [0208]     An image collating apparatus according to a second embodiment of the present invention will be described hereinafter.  
         [0209]     The hardware configuration of the image collating apparatus according to the present embodiment is the same as that in the first embodiment described above, and the function thereof is also the same. Therefore, detailed description thereof will not be repeated.  
         [0210]     Referring to  FIG. 20 , the program executed in image collating apparatus  100  carries out control for similarity score calculation and collation determination as follows. It is noted that the processing in the flowchart in  FIG. 20  that has been shown in  FIG. 11  described previously is given the same step number, and the processing is also the same. Therefore, detailed description thereof will not be repeated.  
         [0211]     In S 430 , search unit  1032  or the like carries out matching and similarity score calculation with regard to the partial area to be subjected to matching, that is set by determination unit  1034 . The processing corresponds to the processing in S 342  to S 380  and the processing in S 440  to S 450  shown in  FIG. 21 .  
         [0212]     In S 432 , search unit  1032  or the like carries out matching and similarity score calculation with regard to the partial area to be subjected to matching, that is set by determination unit  1034 . The processing corresponds to the processing in S 342  to S 380  and the processing in S 440  to S 450  shown in  FIG. 21 .  
         [0213]     Referring to  FIG. 21 , the program executed in image collating apparatus  100  carries out control for matching and similarity score calculation as follows. It is noted that the processing in the flowchart in  FIG. 21  that has been shown in  FIG. 12  described previously is given the same step number, and the processing is also the same. Therefore, detailed description thereof will not be repeated.  
         [0214]     In S 440 , control unit  1035  sends the matching start signal to search unit  1032 . Thereafter, control unit  1035  waits until the matching end signal is received. Search unit  1032  substitutes the value of IMIN into counter variable I.  
         [0215]     In S 442 , search unit  1032  determines whether the value of counter variable I is equal to or smaller than IMAX. If it is determined that the value of counter variable I is equal to or smaller than IMAX (YES in S 442 ), the process proceeds to S 354 . Otherwise (NO in S 352 ), the process proceeds to S 356 .  
         [0216]     In S 444 , calculation unit  1033  substitutes the value of IMIN into counter variable I. In S 446 , calculation unit  1033  substitutes the value of IMIN into counter variable J.  
         [0217]     In S 448 , calculation unit  1033  determines whether counter variable J is smaller than IMAX. If it is determined that counter variable J is smaller than IMAX (YES in S 448 ), the process proceeds to S 372 . Otherwise (NO in S 448 ), the process proceeds to S 374 .  
         [0218]     In S 450 , calculation unit  1033  determines whether the value of counter variable I is smaller than IMAX. If it is determined that the value of counter variable I is smaller than IMAX (YES in S 450 ), the process proceeds to S 380 . Otherwise (NO in S 378 ), the process ends.  
         [0219]     It is noted that other process flows are the same as those in the first embodiment described previously, and the function thereof is also the same. Therefore, detailed description thereof will not be repeated.  
         [0220]     An operation of image collating apparatus  100  based on the configuration and the flowchart as above will now be described.  
         [0221]     After the processing until S 310  ends, control unit  1035  sends the matching start signal to search unit  1032 . Thereafter, control unit  1035  waits until the matching end signal is received. Search unit  1032  substitutes the value of IMIN into counter variable I (S 440 ). When the value of IMIN is substituted into counter variable I, after the processing in S 342  to S 350 , search unit  1032  determines whether the value of counter variable I is equal to or smaller than IMAX (S 442 ). As it is determined that the value of counter variable I is initially equal to or smaller than IMAX (YES in S 442 ), the processing in S 342  to S 354  is repeated.  
         [0222]     Thereafter, when it is determined that the value of counter variable I exceeds IMAX (NO in S 442 ), after the processing in S 356 , calculation unit  1033  substitutes the value of IMIN into counter variable I (S 444 ). When the value of IMIN is substituted, after the processing in S 360 , calculation unit  1033  substitutes the value of IMIN into counter variable J (S 446 ). When the value of IMIN is substituted, after the processing in S 364  to S 368 , calculation unit  1033  determines whether counter variable J is smaller than IMAX (S 448 ). As it is determined that counter variable J is initially smaller than IMAX (YES in S 448 ), the processing in S 360  to S 372  is repeated.  
         [0223]     Thereafter, when it is determined that the value of counter variable J is equal to or greater than IMAX (NO in S 448 ), after the processing in S 374  to S 376 , calculation unit  1033  determines whether the value of counter variable I is smaller than IMAX (S 450 ). While the value of counter variable I is smaller than IMAX (YES in S 450 ), the processing in S 360  to S 380  is repeated.  
         [0224]     Thereafter, when it is determined that the value of counter variable I is equal to or greater than IMAX (NO in S 450 ), after the processing in S 326  to S 330 , search unit  1032  or the like carries out matching and similarity score calculation with regard to the partial area to be subjected to matching, that is set by determination unit  1034  (S 432 ). When matching and similarity score calculation are performed, determination unit  1034  determines whether maximum value P(A,B) of the similarity score is equal to or greater than threshold value T(1) (S 334 ). Determination unit  1034  thus determines whether the partial area other than the excluded area in the sensing image matches with any portion of the template image, when there is a probability that the first portion matches with any portion of the template image.  
         [0225]     As described above, when an image non eligible for collation is detected in the central area, the image collating apparatus according to the present embodiment handles such an area as the area non eligible for collation, thus permitting collation of peripheral areas,  
         [0226]     Consequently, an image collating apparatus, an image collating method, and an image collating program product can be provided, in which collation ends when determination as to whether one image is the same as the other image can be made using only a part of one image and collation of a remaining portion of the image is not necessary, and even though a part of one image is non eligible for collation due to blur or the like, collation can still be carried out using the image that can originally be subjected to collation.  
         [0227]     Although the present invention has been described and illustrated in detail, it is clearly understood that the same is by way of illustration and example only and is not to be taken by way of limitation, the spirit and scope of the present invention being limited only by the terms of the appended claims.