JP4692377B2 - Image collation device, image collation method and program - Google Patents

Description

  The present invention relates to an image collation apparatus, an image collation method, and a program for collating image data.

  In recent years, with the increase in capacity of storage devices and the like, data management systems that accumulate a large amount of document data and image data and provide them to users are becoming widespread. In order to efficiently use such a data management system, it is necessary to enhance the search function so that the user can easily find the necessary data from the large amount of accumulated data. However, searching for image data is generally more difficult than searching for document data consisting of character code information or the like. That is, for example, even when image data representing almost the same image is printed on a recording medium such as paper and then read again by a scanner, misalignment, color change, etc. occur, and the data Will be completely different. As a result, it is not possible to determine that the images are similar by simply comparing the image data. In view of this, for example, an image matching technique has been proposed in which data representing image characteristics is extracted from image data and verified to determine whether the images are similar.

  As one of such image collation techniques, image feature information based on each of two image data to be collated is acquired, and is a conversion parameter of affine transformation for one image data based on the image feature information. There is a technique for estimating values of an enlargement / reduction ratio and a parallel movement amount, and performing image matching using an estimated conversion parameter (Patent Document 1). In this technique, for example, a pixel value projection waveform obtained by accumulating pixel values of each pixel included in image data in a predetermined direction is acquired, and a position where the waveform change is characteristic in the pixel value projection waveform is obtained. The represented position information is used as image feature information. According to this technology, for example, in an image representing a document including a horizontally written or vertically written character string, information regarding the arrangement of rows and columns where pixels are concentrated is extracted as a pixel value projection waveform and collated, whereby the image Can be determined.

  FIGS. 7A and 7B are explanatory diagrams illustrating examples of directions in which pixel values included in image data are accumulated when a pixel value projection waveform is generated. FIG. 7A shows an example in which pixel values are accumulated in the horizontal direction of image data. FIG. 7B shows an example in which pixel values are accumulated in the vertical direction of image data. By accumulating the pixel values along the direction shown in this figure, the accumulated values obtained by accumulating the pixel values of the pixels in each row or each column are arranged in an order corresponding to the position on the image data. An arithmetic value series is obtained. A waveform represented by this accumulated value series is a pixel value projection waveform. FIG. 8 is an explanatory diagram schematically showing an example of the pixel value projection waveform thus obtained.

Here, if the two image data completely match, the pixel value projection waveforms in the predetermined direction generated from the image data should also match. However, when one of the image data to be collated is image data that has been enlarged or reduced with respect to the other image data, or a positional shift has occurred, the pixel value projection waveform of the image data Misalignment occurs. Therefore, according to the technology, the image collation apparatus performs affine transformation on one image data based on position information obtained from each pixel value projection waveform so that the degree of coincidence of the image data to be collated is high. The conversion parameters (enlargement / reduction ratio and parallel movement amount) are calculated. Then, image conversion processing such as enlargement, reduction, and parallel movement is performed on one image data according to the determined conversion parameter, and the images are collated using the converted image data. As a result, a similar image can be searched even from an image that has been enlarged, reduced, or misaligned.
JP 2003-91730 A

  However, in the above-described conventional technique, for example, when collating images in which a large number of peak positions are included in the pixel value projection waveform generated based on the characteristics of the image data, the images cannot be collated with sufficiently high accuracy. There is. That is, when a large number of image feature information (for example, position information of peak positions) is obtained from image data, the conversion parameter is calculated by comparing image feature information acquired based on the respective image data to be collated In addition, noise may occur, and the accuracy of the calculated conversion parameter may deteriorate.

  The present invention has been made in view of the above circumstances, and one of its purposes is to provide an image collation apparatus, an image collation method, and a program capable of improving the accuracy of image collation.

  An image collation apparatus according to the present invention for solving the above-described problems is an image collation apparatus that collates first image data and second image data, based on each of the first and second image data. Based on the acquired image feature information, an enlargement / reduction ratio and a parallel movement amount are affine transformation conversion parameters for matching the image feature information based on the first image data with the image feature information based on the second image data. A linear formula determining means for determining a plurality of linear formulas representing the relationship between possible values as a straight line on a two-dimensional space having coordinate axes corresponding to the scaling ratio and the amount of parallel movement, and an intersection of the determined linear formulas An intersection group determining means for performing a clustering process for classifying each intersection and determining at least one intersection group including a plurality of intersections as a candidate intersection group; Based on the position of each intersection belonging to the determined candidate intersection group, a conversion parameter calculation that calculates the scaling ratio and the amount of parallel movement that increase the degree of coincidence between the first image data and the second image data And the calculated enlargement / reduction ratio and parallel movement amount are provided for collation processing between the first image data and the second image data.

  According to the above configuration, a plurality of linear expressions representing a relationship between values that can be taken by the scaling factor and the amount of translation that are the conversion parameters of the affine transformation for one of the image data to be collated are determined, and each conversion parameter is defined as a coordinate axis. By executing the clustering process for classifying the intersections of the linear equations in the two-dimensional space to be performed, the intersections in the two-dimensional space that have been generated as noise can be removed. As a result, a conversion parameter that increases the degree of coincidence between two image data to be collated can be obtained with high accuracy, and the accuracy of image collation can be improved.

  In addition, the image collating device obtains a pixel value projection waveform obtained by accumulating pixel values of pixels included in the image data in a predetermined direction for each of the first and second image data. Projection waveform acquisition means may be further included, and the image feature information may be position information representing a position where a change in waveform within each acquired pixel value projection waveform is characteristic. Furthermore, the position where the change in the waveform is characteristic may be a position representing a peak of the waveform in the pixel value projection waveform.

  In the image collation apparatus, the intersection group determination unit may perform a clustering process on intersections included in a candidate region that satisfies a predetermined condition in the two-dimensional space.

  An image collating method according to the present invention is an image collating method for collating first image data and second image data using a computer, and is based on each of the first and second image data. Based on the acquired image feature information, an enlargement / reduction ratio and a parallel movement amount are affine transformation conversion parameters for matching the image feature information based on the first image data with the image feature information based on the second image data. A step of determining a plurality of linear expressions representing a relationship of values that can be taken as a straight line in a two-dimensional space having coordinate axes corresponding to the scaling ratio and the amount of parallel movement, and the intersection of the determined plurality of linear expressions Performing a clustering process for classifying each intersection and determining at least one intersection group including a plurality of intersections as a candidate intersection group; and Calculating values of the enlargement / reduction ratio and the amount of translation that increase the degree of coincidence between the first image data and the second image data based on the positions of the respective intersections belonging to the candidate intersection group. The calculated enlargement / reduction ratio and parallel movement amount are used for collation processing between the first image data and the second image data.

  In addition, the program according to the present invention can convert image feature information based on the first image data based on image feature information acquired based on each of the first and second image data to image feature based on the second image data. The relationship between values that can be taken by the scaling factor and the translation amount, which is a transformation parameter of the affine transformation that matches the information, is expressed as a straight line in a two-dimensional space having coordinate axes respectively corresponding to the scaling factor and the translation amount. A straight line determining means for determining a plurality of straight lines, and performing a clustering process for classifying each cross point on the determined cross points of the plurality of straight lines, and selecting at least one cross point group including a plurality of cross points as candidate cross points The first image data and the second image based on the intersection group determination means determined as a group, and the position of each intersection belonging to the determined candidate intersection group A computer that functions as a conversion parameter calculation unit that calculates values of the enlargement / reduction ratio and parallel movement amount that increase the degree of coincidence with the data, and the calculated enlargement / reduction ratio and parallel movement amount correspond to the first image data and the translation amount It is used for collation processing with the second image data.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings. As shown in FIG. 1, the image collation apparatus according to an embodiment of the present invention includes a control unit 11, a storage unit 12, an image reading unit 13, and a display unit 14.

  The control unit 11 is a CPU or the like, and operates according to a program stored in the storage unit 12. In the present embodiment, the degree of coincidence between the two image data is increased by using image feature information based on the key image data serving as a search key and the accumulated image data stored in the storage unit 12. Calculate the conversion parameters. Further, two image data are collated using the calculated conversion parameter, and an image collation process for determining whether or not the two images are similar is executed. Thereby, the image collation apparatus according to the present embodiment can search stored image data similar to the key image data and output the result. An example of processing executed by the control unit 11 in the present embodiment will be described in detail later.

  The storage unit 12 is a computer-readable storage medium that holds a program executed by the control unit 11, and includes at least one of a memory element such as a RAM or a ROM, a disk device, or the like. The storage unit 12 also operates as a work memory for the control unit 11. Further, in the present embodiment, the storage unit 12 stores a plurality of pieces of image data to be collated as accumulated image data.

  The image reading unit 13 optically reads an image formed on a recording medium such as paper, converts the image into image data, and outputs the image data to the control unit 11. Thereby, the control part 11 can acquire key image data. The display unit 14 is a display or the like, and displays various information such as search results in accordance with instructions input from the control unit 11.

  Next, functions realized by the image collating apparatus according to the present embodiment will be described. As shown in FIG. 2, the image matching device according to the present embodiment functionally has a projection waveform acquisition unit 21, a position information acquisition unit 22, a linear equation determination unit 23, an intersection group determination unit 24, A conversion parameter calculation unit 25 and an image collation unit 26 are included. These functions can be realized, for example, when the control unit 11 executes a program stored in the storage unit 12.

  The projection waveform acquisition unit 21 sets the pixel value of each pixel included in the image data in a predetermined direction for each of key image data and accumulated image data (hereinafter referred to as “matching target image data”) to be collated. A pixel value projection waveform obtained by accumulation is acquired.

  Here, the predetermined direction is, for example, a horizontal direction or a vertical direction. As a specific example, if the key image data is data representing a document image and it is known in advance whether the document is vertical writing or horizontal writing, the direction in which the characters are arranged is selected as a predetermined direction. It is good. By using such a direction, it is possible to obtain a pixel value projection waveform that particularly reflects the characteristics of the image. For example, when the characteristics of the image data are unclear, pixel value projection waveforms in a plurality of directions such as both the horizontal direction and the vertical direction may be acquired. In this case, the image collating apparatus according to the present embodiment can perform collation of images with higher accuracy by comparing pixel value projection waveforms in a plurality of predetermined directions. Further, for example, the pixel value projection waveform in one of the horizontal direction and the vertical direction with respect to the key image data may be compared with the pixel value projection waveforms in the horizontal direction and the vertical direction with respect to the accumulated image data. Thus, even when the key image data is an image rotated 90 degrees with respect to the stored image data, it can be determined that the images are similar by collating the images.

  The projection waveform acquisition unit 21 acquires a pixel value projection waveform obtained by accumulating pixel values of each pixel included in the image data along the predetermined direction. The pixel value projection waveform represents a distribution when the pixel values of the image data are projected in the predetermined direction. On the computer, this pixel value projection waveform is a pixel group in which a plurality of accumulated values obtained by accumulating pixel values of each pixel along a predetermined direction are targets for calculating each accumulated value. Are expressed as a numerical array (accumulated value series) arranged according to the arrangement order on the image data.

  In calculating the accumulated value, if the image data to be collated is monochrome image data, the pixel value of the white point may be accumulated as “0”, and the pixel value of the black point may be accumulated as “1”. In the case of multi-value image data including a halftone, for example, white may be “0”, black may be “255”, and the like. Further, in the case of color image data, for example, the density value obtained by separating the density components is regarded as the multi-value image, and the accumulated value is calculated. The separation of density components can be performed by a conversion process for known color values.

  The projection waveform acquisition unit 21 may acquire the pixel value projection waveform by calculating each accumulated value based on the verification target image data, for example, when performing the image verification process. Alternatively, particularly for the accumulated image data, a pixel value projection waveform calculated in advance in a predetermined direction of the accumulated image data may be stored in the storage unit 12 in association with the accumulated image data. In this case, the projection waveform acquisition unit 21 can acquire the pixel value projection waveform simply by reading it from the storage unit 12, and can reduce the amount of calculation when collating images.

  When generating a pixel value projection waveform for key image data acquired by reading by the image reading unit 13, a known tilt correction technique is used before the pixel value projection waveform generation process to make a slight reading. The inclination may be corrected. In addition, the pixel value projection waveform temporarily generated from the key image data is scaled to a predetermined scale (default scale) according to the resolution setting of the image reading unit 13 when the key image data is read. The converted pixel value projection waveform may be acquired. Thereby, the pixel value projection waveforms can be compared using the pixel value projection waveforms that have been standardized in advance to a size close to the pixel value projection waveform of the stored image data.

  In the description so far, the waveform itself represented by the accumulation value series obtained by accumulating the pixel values is the pixel value projection waveform to be acquired, but the differentiation is obtained by differentiating the waveform. You may acquire as a pixel value projection waveform used as the object which compares a waveform. For example, when a copy document is used as key image data, if the image data includes a halftone area such as a photograph or drawing, the density value often changes greatly. The peak value of the waveform is often not stable. This is because, even in such a case, the state of the unevenness of the waveform composed of the accumulated value series is maintained in many cases, so it is often preferable to use the differential waveform as the pixel value projection waveform to be compared.

  The position information acquisition unit 22 acquires, based on each pixel value projection waveform acquired by the projection waveform acquisition unit 21, a plurality of position information representing positions where the change in waveform within the pixel value projection waveform is characteristic. . This position information is an example of image feature information in the present invention, and is used for calculation of a conversion parameter that increases the degree of matching of collation target image data.

  As the position where the change in waveform is characteristic, for example, the peak position of the accumulated value can be used. The peak position of the accumulated value can be calculated as the extreme value of the pixel value projection waveform. In addition, the position information acquisition unit 22 is a position where the change of the waveform is characteristic, such as the maximum or minimum value of the accumulated value, the position of the inflection point of the waveform, the position of the center of gravity, or the position where the accumulated value takes a predetermined value. Etc. may be used.

  Here, for example, when the peak position of the accumulated value is used as a position where the waveform change is characteristic, the position information of all the peak positions may not be acquired. For example, the number and position of peaks generated by high-frequency components of the pixel value projection waveform can be easily fluctuated due to noise or the like included in the image data, and the characteristics of the image may not be reflected. Therefore, the position information acquisition unit 22 may acquire position information representing the peak position after excluding such a peak by the method described in Patent Document 1 described above.

  Similar to the projection waveform acquisition unit 21, the position information acquisition unit 22 may perform operation on the acquired pixel value projection waveform to acquire position information, or may store the storage unit 12 in association with image data in advance. You may acquire by reading the positional information memorize | stored in. As an example, when acquiring position information representing a peak position with respect to a pixel value projection waveform as illustrated in FIG. 8, the position information acquisition unit 22 acquires values of α, β, and γ as position information.

  The linear formula determination unit 23 is configured to match the image feature information based on one image data with the image feature information based on the other image data based on the image feature information acquired based on each of the collation target image data. A relational expression representing a relation between values that can be taken by the enlargement / reduction ratio and the amount of translation, which is a conversion parameter of the conversion, is determined. Here, the relational expression is a linear expression representing a straight line on a two-dimensional space (conversion parameter plane) having coordinate axes respectively corresponding to the scaling ratio and the parallel movement amount.

  Here, the enlargement / reduction ratio corrects such a change when the scale changes between image data to be collated, or when the image size changes due to reading at a different resolution when reading. This parameter is used for scaling processing. The parallel movement amount is used for a parallel movement process for correcting such a positional shift when the entire position of each pixel included in the image data is shifted due to a shift in the position of the document at the time of reading. Parameter. Using this conversion parameter, comparing the pixel value projection waveform obtained from two image data or image data after performing affine transformation processing including scaling processing and translation processing on one pixel value projection waveform Thus, the image collating apparatus according to the present embodiment can search for similar image data from image data that has been enlarged, reduced, or translated with respect to the original image data. Here, the image data to be subjected to the affine transformation process may be key image data or accumulated image data.

  As a specific example, the linear equation determination unit 23 selects one piece of position information from each of the plurality of pieces of position information for the key image data and the plurality of pieces of position information for the stored image data acquired by the position information acquisition unit 22. A plurality of position information pairs are generated. Then, a linear expression that represents a set of values that can be taken by a conversion parameter that matches the two pieces of position information constituting each position information pair is determined.

  Specifically, an example of processing in which the linear equation determination unit 23 determines a linear equation will be described below. Here, the enlargement / reduction ratio is represented by a variable k, the parallel movement amount is represented by a variable s, and the position information of the peak position of the pixel value projection waveform obtained from the key image data is represented by p1, p2, and p3. Further, the position information of the peak position of the pixel value projection waveform obtained from the accumulated image data is assumed to be q1, q2, q3.

  First, the linear equation determination unit 23 generates a plurality of position information pairs. The linear equation determination unit 23 generates a position information pair by selecting position information one by one from position information obtained from key image data to be collated and position information obtained from accumulated image data. it can. Here, the linear equation determination unit 23 may generate position information pairs for all possible combinations, or may select only position information pairs that satisfy a predetermined condition. For example, when the difference between two pieces of position information is greater than or equal to a predetermined value, the position information pair may not be selected. In the above-described example, the linear equation determination unit 23 uses, for example, (p1, q1), (p1, q2), (p1, q3), (p2, q1), (p2, q2), (p2) as position information pairs. , Q3), (p3, q1), (p3, q2) and (p3, q3). The linear equation determination unit 23 needs to generate a position information pair by combining position information representing characteristic positions of the same type. That is, for example, when the position information acquisition unit 22 acquires position information about each of the convex peak and the concave peak, the linear equation determination unit 23 determines the position information of the convex peak as the position information of the convex peak and the concave peak. Generates a position information pair in combination with the position information of the concave peak.

Based on the plurality of position information pairs, linear expressions representing sets of values that can be taken by conversion parameters that match two position information belonging to each position information pair can be determined. Here, it is assumed that the position information of the key image data included in the position information pair is pi and the position information of the stored image data is qi. As a result of performing scaling processing and translation processing using the scaling factor k and the translation amount s on the pixel value projection waveform of the key image data, the peak position pi in the pixel value projection waveform of the key image data and the accumulated image data It is assumed that the peak position qi in the pixel value projection waveform of coincides. In this case, the expansion / contraction rate k and the parallel movement amount s satisfy the following relational expression.
qi = k · pi + s
By transforming this relational expression, the following linear expression on the conversion parameter plane is obtained.
s = −pi · k + qi
The linear equation determination unit 23 determines such a linear equation for each generated position information pair.

  When a plurality of linear expressions determined in this way are drawn on the conversion parameter plane, ideally, coordinates at which many straight lines intersect are obtained. If affine transformation is performed on one pixel value projection waveform using this coordinate value (k, s), the peak positions should match in two pixel value projection waveforms generated from two similar images. It is. However, k and s obtained from each linear equation do not necessarily match due to factors such as calculation errors. Therefore, it is necessary to estimate a conversion parameter that increases the degree of coincidence between the two image data based on a plurality of linear expressions.

  What is characteristic in the present embodiment is that the intersection point group determined by the clustering process is used when calculating the conversion parameter. That is, in the present embodiment, the intersection group determination unit 24 performs clustering processing on the intersections of a plurality of straight lines determined by the linear equation determination unit 23 to classify the intersections. Then, at least one candidate intersection group that is considered to correspond to the position coordinates of the conversion parameter to be obtained is determined from the intersection group (intersection cluster) obtained as a result of the classification. The intersection group determined by the intersection group determination unit 24 is used for calculation of the conversion parameter by the conversion parameter calculation unit 25. Thereby, the image collation device according to the present embodiment excludes the intersection that has been generated as noise on the conversion parameter plane from the candidate intersection group, so that the conversion parameter that increases the degree of coincidence of the two image data is obtained. It can be obtained with high accuracy.

  Here, the intersection group determination unit 24 may first determine an area that satisfies a predetermined condition on the conversion parameter plane as a candidate area that is estimated to have a conversion parameter to be obtained. As a specific example, as shown in Patent Document 1, for example, the intersection group determination unit 24 determines a candidate region based on information on the width and the center of gravity of the pixel value projection waveform acquired by the projection waveform acquisition unit 21. By executing the clustering process using only the intersections included in this candidate area, the image matching apparatus according to the present embodiment can reduce the amount of calculation when calculating the conversion parameter, and the conversion parameter for which an incorrect conversion parameter should be obtained. Can be avoided as determined.

  Further, the intersection group determination unit 24 may determine a candidate region from among the plurality of unit regions by dividing the transformation parameter plane into a plurality of unit regions (cells) and quantizing them. In this case, for example, the intersection group determination unit 24 divides the conversion parameter plane into predetermined unit lengths along the coordinate axis direction of the enlargement / reduction ratio and the parallel movement amount, so that a unit region composed of a rectangular region having a predetermined size is obtained. Divide the transformation parameter plane into. FIG. 3 is an explanatory diagram showing an example of the conversion parameter plane divided into such unit areas. In the example of FIG. 3, a straight line represented by a solid line on the plane indicates an example of a straight line represented by the linear formula determined by the linear formula determining unit 23, and a two-dot chain line in the diagram represents each unit region. Represents a boundary line.

  Then, the intersection group determination unit 24 selects, as a candidate area (candidate unit area), at least one unit area selected based on a straight line passing through the unit area among the plurality of unit areas. For example, the intersection group determination unit 24 selects a unit region having the largest number of straight lines passing as a candidate unit region. Alternatively, a predetermined number of unit areas may be selected as candidate unit areas in order of increasing number of straight lines. As an example, in the example of FIG. 3, a unit region that is the unit region through which the most straight lines pass and is represented by hatching in the drawing is selected as a candidate unit region.

  Next, the intersection group determination unit 24 classifies the intersections for all the intersections obtained from the plurality of linear equations determined by the linear equation determination unit 23 or the intersections included in the candidate area described above. Execute. Here, as a clustering processing method, for example, a known method such as hierarchical clustering or a K-average method can be used.

  FIG. 4 is an explanatory diagram illustrating an example of an intersection group (cluster) obtained as a result of classifying intersections by clustering processing in the candidate unit region on the conversion parameter plane. In this example, there are six intersections in the candidate unit area. Then, these six intersections are classified into three intersection groups for each intersection having a relatively close distance by the clustering process. A two-point difference line in the figure represents three intersection groups G1, G2, and G3 obtained by the clustering process.

  Further, the intersection group determination unit 24 determines, as candidate intersection groups, at least one intersection group considered to correspond to the position coordinates of the conversion parameter to be obtained from the intersection groups obtained as a result of the classification. As an example, the intersection group determination unit 24 determines an intersection group including the largest number of intersections as a candidate intersection group. For example, in the example of FIG. 4, an intersection group G1, which is an intersection group including the largest number of intersections, is determined as a candidate intersection group. Alternatively, the intersection group determination unit 24 may determine a predetermined number of intersection groups as candidate intersection groups in descending order of the number of intersections. Furthermore, when the range occupied by the intersection group on the conversion parameter plane is a predetermined size or more, it may be excluded from the candidate intersection group. For example, when the maximum value of the distance between the intersections included in the intersection group exceeds a predetermined value, the candidate intersection group is not selected.

  When performing clustering processing on intersections included in a plurality of candidate unit regions, the intersection group determination unit 24 separately performs clustering processing on intersections included in each candidate unit region, An intersection group may be determined. Alternatively, the clustering process may be performed on all the intersection points included in the adjacent candidate unit regions for the adjacent candidate unit regions among the plurality of candidate unit regions.

  As an example, an example of two adjacent candidate unit areas A1 and A2 shown in FIG. 5 will be described. Here, when the clustering process is separately performed for the intersections included in each of the candidate unit areas A1 and A2, for example, the intersection groups G4 and G5 are obtained based on the respective intersections included in the candidate unit area A1. To do. Further, it is assumed that intersection groups G6, G7, and G8 are obtained based on each intersection included in the candidate unit region A2. Here, the barycentric position of each intersection group is calculated, and the distance between the calculated barycentric positions is calculated. An intersection group in which the distance between the center of gravity positions is equal to or less than a predetermined value is regarded as one intersection group. In the example of FIG. 5, for example, G5 and G6 are integrated as one intersection group G9. Thereby, the intersection group which has been divided by the unit area can also be made into one intersection group. On the other hand, when the clustering process is executed for all the intersections included in the adjacent candidate unit areas, for example, the intersection groups G4, G7, G8, and G9 are obtained by the clustering process. In this case, the candidate intersection group may be determined using the obtained intersection group as it is.

  Based on the position of each intersection belonging to the candidate intersection group determined by the intersection group determination unit 24, the conversion parameter calculation unit 25 converts the conversion parameter value (scaling rate) that increases the degree of coincidence between the key image data and the accumulated image data. k and the value of the translation amount s). Specifically, for example, the value of the conversion parameter is determined by calculating the gravity center position of each intersection belonging to the candidate intersection group. In addition, when the intersection group determination part 24 determines a some intersection group as a candidate intersection group, the value of a some conversion parameter is calculated based on each candidate intersection group.

  The image matching unit 26 uses the conversion parameter calculated by the conversion parameter calculation unit 25 to perform image matching processing between the key image data and the stored image data. For example, when there are a plurality of conversion parameters calculated by the conversion parameter calculation unit 25, the image collation unit 26 performs an affine conversion process on the pixel value projection waveform of the key image data based on each conversion parameter. Next, a correlation value between the pixel value projection waveform of the key image data subjected to the affine transformation and the pixel value projection waveform of the accumulated image data is calculated as a parameter representing the degree of matching of the collation target image data. Then, the image collation unit 26 determines the conversion parameter with the highest degree of coincidence calculated as the conversion parameter to be obtained.

  Furthermore, affine transformation may be performed on the key image data itself using the determined transformation parameter, and it may be determined in more detail whether or not the affine-transformed key image data and the stored image data are similar. Here, the image matching unit 26 performs affine transformation using the transformation parameters for the respective directions obtained by comparing the pixel value projection waveforms in the vertical direction and the horizontal direction of the respective pieces of matching target image data. It is good. Alternatively, the image collating unit 26 immediately determines whether the correlation value between the pixel value projection waveform of the key image data subjected to affine transformation and the pixel value projection waveform of the accumulated image data satisfies a predetermined condition or not. It may be determined whether two pieces of image data are similar. Specifically, the image matching process performed by the image matching unit 26 can be realized by a method described in Patent Document 1, for example.

  Here, an example of processing executed by the image collating apparatus according to the present embodiment will be described based on the flowchart of FIG. In this flow example, it is assumed that pixel value projection waveforms in the horizontal direction and vertical direction of accumulated image data are stored in the storage unit 12 in advance.

  First, the projection waveform acquisition unit 21 acquires image data of an image read by the image reading unit 13 as key image data (S1). Then, based on the key image data acquired in S1, either the horizontal direction or the vertical direction is determined as a predetermined direction for projection when generating a pixel value projection waveform (S2). Furthermore, the projection waveform acquisition unit 21 acquires the pixel value projection waveform of the key image data for the direction determined in S2 (S3).

  Next, the position information acquisition unit 22 is based on the pixel value projection waveform of the accumulated image data to be collated stored in the storage unit 12 and the pixel value projection waveform of the key image data acquired in S3, respectively. The position information representing the peak position is calculated and acquired (S4). Next, the linear equation determination unit 23 determines a linear equation by generating a plurality of position information pairs based on the position information acquired in S4 (S5).

  Subsequently, the intersection group determination unit 24 calculates the position coordinates of the intersection of each straight line represented by the straight line expression based on each straight line expression determined in S5 (S6). Further, a candidate area on the conversion parameter plane is determined based on a predetermined condition, and the position coordinates of the intersection included in the determined candidate area are selected from the position coordinates calculated in S6 (S7). Then, the intersections selected in S7 are classified by clustering processing, and candidate intersection groups are determined from the intersection groups obtained by classification (S8).

  Next, the conversion parameter calculation unit 25 calculates a conversion parameter based on the candidate intersection group determined in S8 (S9). Further, the image collation unit 26 calculates the degree of coincidence between the key image data that has been subjected to the conversion process based on the conversion parameter calculated in S9 and the stored image data (S10). The processes of S9 and S10 are repeated for all candidate intersection groups when there are a plurality of candidate intersection groups determined in S8.

  Then, the image matching unit 26 selects the highest matching score by comparing the matching scores calculated in S10 for all candidate intersection groups determined in S8, and determines whether the images are similar based on the matching score. And the result is output (S11). For example, if the degree of coincidence is equal to or less than a predetermined value, it is determined that the image data is not similar, and the matching process between the key image data and the stored image data is terminated. On the other hand, if it is determined that they are similar, the stored image data is included as a collation target in the search result candidate, and the collation process is terminated. By performing this processing for all the image data stored in the storage unit 12, the image collation apparatus according to the present embodiment extracts image data similar to the key image data as search result candidates and causes the display unit 14 to display the extracted image data. Etc., and can be presented to the user as a search result.

  According to the present embodiment described above, a plurality of linear expressions representing the relationship between values that can be taken by the conversion parameter on the conversion parameter plane are determined, and the clustering process for classifying the intersections of the linear expressions is performed as noise. By excluding intersections that have occurred, it is possible to accurately obtain a conversion parameter that increases the degree of coincidence between two image data to be collated. Thereby, the image collation apparatus according to the present embodiment can improve the accuracy of image collation.

  The present invention is not limited to the above embodiment. For example, the image collation apparatus according to the embodiment of the present invention includes not only image data stored in advance in the storage unit 12 or image data read by the image reading unit 13 as image data to be collated, but also a communication network, for example. Various image data such as image data acquired via the network can be used.

  In the above description, an example in which position information obtained based on a pixel value projection waveform is used as image feature information has been described. However, image feature information that can be used in the embodiment of the present invention is limited to this. Absent. For example, it is possible to use information relating to positions that can be matched between matching target image data, such as position coordinates of feature points selected based on predetermined conditions from image data.

It is a block diagram showing the example of a structure of the image collation apparatus which concerns on embodiment of this invention. It is a functional block diagram showing the function of the image collation device concerning an embodiment of the invention. It is explanatory drawing showing the example of the conversion parameter plane divided | segmented into the unit area. It is explanatory drawing showing an example of the intersection classified into the intersection group on the conversion parameter plane. It is explanatory drawing showing an example of the intersection classified into the intersection group in two adjacent candidate unit area | regions on a conversion parameter plane. It is a flowchart which shows an example of the process performed by the image collation apparatus which concerns on embodiment of this invention. It is explanatory drawing showing an example of the predetermined direction at the time of calculating an accumulated value from image data. It is explanatory drawing showing an example of the pixel value projection waveform produced | generated from image data.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 11 Control part, 12 Memory | storage part, 13 Image reading part, 14 Display part, 21 Projection waveform acquisition part, 22 Position information acquisition part, 23 Linear formula determination part, 24 Intersection group determination part, 25 Conversion parameter calculation part, 26 Image collation Department.

Claims (4)

An image collation device that collates first image data and second image data,
Position information representing the position at which the change in the pixel value projection waveform obtained by accumulating the pixel value of each pixel included in the image data in a predetermined direction is characteristic for each of the first and second image data Obtaining means for obtaining
A scaling factor and a translation amount, which are transformation parameters of affine transformation that match each of a plurality of position information obtained from the first image data with each of a plurality of position information obtained from the second image data. a linear equation determining means that determine a plurality of linear equation expressed as a straight line on the two-dimensional space having the coordinate axes is the relationship between possible values, corresponding respectively to the scaling factor and the amount of parallel movement,
Based on the number of straight lines passing through each of the plurality of unit regions obtained by dividing the two-dimensional space among the plurality of straight lines represented by the determined plurality of linear equations, at least one from the plurality of unit regions. Candidate unit region selection means for selecting a candidate unit region;
A clustering process for classifying each intersection is performed on a plurality of intersections included in the selected candidate unit region among the plurality of determined intersections of the linear expressions, and at least one including a plurality of intersections Means for determining an intersection group as a candidate intersection group, and when the candidate unit region selection unit selects a plurality of adjacent candidate unit regions, all the intersection points included in the plurality of adjacent candidate unit regions Intersection point group determining means for performing clustering processing for
The coordinate values in the two-dimensional space of the center- of- gravity positions of a plurality of intersections belonging to the determined candidate intersection group are used as the enlargement / reduction ratio and translation that increase the degree of coincidence between the first image data and the second image data. Conversion parameter calculation means for calculating the value of the quantity;
Including
An image collation apparatus that performs collation processing between the first image data and the second image data that have been affine transformed using the calculated scaling ratio and parallel movement amount. The image collation apparatus according to claim 1 ,
The position where the change of the waveform is characteristic is a position representing the peak of the waveform in the pixel value projection waveform. An image collation method for collating first image data and second image data using a computer,
Position information representing the position at which the change in the pixel value projection waveform obtained by accumulating the pixel value of each pixel included in the image data in a predetermined direction is characteristic for each of the first and second image data An acquisition step to acquire,
A scaling factor and a translation amount, which are transformation parameters of affine transformation that match each of a plurality of position information obtained from the first image data with each of a plurality of position information obtained from the second image data. a step of determine a plurality of linear equation expressed as a straight line on the two-dimensional space having the coordinate axes is the relationship between possible values, corresponding respectively to the scaling factor and the amount of parallel movement,
Based on the number of straight lines passing through each of the plurality of unit regions obtained by dividing the two-dimensional space among the plurality of straight lines represented by the determined plurality of linear equations, at least one from the plurality of unit regions. A candidate unit region selection step for selecting a candidate unit region;
A clustering process for classifying each intersection is performed on a plurality of intersections included in the selected candidate unit region among the plurality of determined intersections of the linear expressions, and at least one including a plurality of intersections A step of determining an intersection group as a candidate intersection group, and when a plurality of candidate unit regions adjacent to each other are selected in the candidate unit region selection step, all of the candidate unit regions included in the adjacent plurality of candidate unit regions are selected. Performing a clustering process on the intersection ;
The coordinate values in the two-dimensional space of the center- of- gravity positions of a plurality of intersections belonging to the determined candidate intersection group are used as the enlargement / reduction ratio and translation that increase the degree of coincidence between the first image data and the second image data. Calculating as a quantity value;
Including
Image matching method and performing matching processing between the affine converted first image data and the second image data by using the scaling ratio and amount of translation and the calculated. For each of the first and second image data, position information representing a position where a change in the pixel value projection waveform obtained by accumulating the pixel value of each pixel included in the image data in a predetermined direction is characteristic. Acquisition means to acquire,
A scaling factor and a translation amount, which are transformation parameters of affine transformation that match each of a plurality of position information obtained from the first image data with each of a plurality of position information obtained from the second image data. linear equation determining means that determine a plurality of linear equation expressed as a straight line on the two-dimensional space having the respective axes of the relationship between the value which can take, in the scaling factor and the amount of parallel movement,
Based on the number of straight lines passing through each of the plurality of unit regions obtained by dividing the two-dimensional space among the plurality of straight lines represented by the determined plurality of linear equations, at least one from the plurality of unit regions. Candidate unit region selection means for selecting a candidate unit region;
A clustering process for classifying each intersection is performed on a plurality of intersections included in the selected candidate unit region among the plurality of determined intersections of the linear expressions, and at least one including a plurality of intersections Means for determining an intersection group as a candidate intersection group, and when the candidate unit region selection unit selects a plurality of adjacent candidate unit regions, all the intersection points included in the plurality of adjacent candidate unit regions intersection points determining means for performing a clustering process as target,
The coordinate values in the two-dimensional space of the center of gravity of the plurality of intersections pertaining to the candidate intersection points from pre Symbol determined, and the first image data, the scaling factor and the parallel degree of coincidence between the second image data is high Conversion parameter calculation means for calculating as a value of movement amount, and means for performing collation processing between the first image data and the second image data that have been affine transformed using the calculated scaling ratio and parallel movement amount ;
A program characterized by causing a computer to function.

Images