JP3720538B2 - Image search apparatus and method - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an image search apparatus and method for searching for an image.
[0002]
[Prior art]
Conventionally, various techniques for searching for similar images have been proposed. Many techniques that have been put to practical use for performing similar image search on natural images often use color information as image feature amounts. And most of them search by using a combination of colors that are present in the ratio of RGB and many colors by taking a histogram relating to color information.
[0003]
[Problems to be solved by the invention]
However, in the above method, color position information is lost, so that the search accuracy is not necessarily high. For example, Japanese Patent Laid-Open No. 8-249349 discloses pattern matching using an image divided into a plurality of blocks and using respective feature amounts (representative colors). However, in this method, the distance of the feature amount between each block must be calculated for two images to be matched, which requires a huge amount of calculation. In particular, when a representative color is used as a feature quantity, three RGB data must be handled, and the calculation is further complicated. In addition, since the comparison is performed using the feature amount itself, the accuracy of the comparison is increased, but there is a problem that a similar image cannot be searched just by changing the angle of the image or the position of the object. In other words, the image angle is changed, the position of the object is changed, or the image search is appropriately performed while having a certain degree of ambiguity, such as absorbing a certain amount of difference in the image feature amount depending on the shooting conditions. So-called robust similar image search could not be performed.
[0004]
Therefore, when searching for a natural image in the prior art, it is common to assign a keyword to the image and perform an image search using this keyword. However, this keyword attaching operation is a labor-intensive operation. Further, for an image that has not been assigned a keyword, an operation of presenting a reduced image and selecting it manually is required, and the search operation is complicated. It was.
[0005]
The present invention has been made in view of the above-described problems, and an object of the present invention is to provide an image search apparatus and method capable of searching for similar images at high speed in consideration of the arrangement of image feature amounts.
[0006]
Another object of the present invention is to provide an image search apparatus and method that enable a similar image search that effectively absorbs a change in an image due to a change in shooting conditions such as a shooting angle and a shooting magnification. .
[0007]
[Means for Solving the Problems]
In order to achieve the above object, an image search apparatus according to the present invention comprises the following arrangement. That is,
An assigning unit that divides the image into a plurality of blocks and assigns a label according to the feature amount acquired for each block;
Generating means for generating a label matrix from the labels given by the giving means;
Storage means for storing the label matrix generated by the generation means in association with the image;
Search means for performing an image search based on a label matrix stored in the storage means,
A first matching unit that associates, by DP matching, a label unit in a row unit extracted from a label matrix of a search source image with a label unit in a unit of row extracted from a label matrix of a comparison destination image;
A second matching unit that obtains a similarity between the row sequence of the search source image and the row sequence obtained by the first matching unit by DP matching;
[0008]
  Moreover, the image search method of the present invention that achieves the above object includes the following steps. That is,
  To an image search device for searching for an image similar to a specified search source image from images stored in a storage meansCanAn image search method,
  Image feature extraction meansThe image stored in the memory is divided into a plurality of blocks, and the image data belonging to each block is used.A calculation step of calculating a feature amount;
The label attaching means is the calculating stepCalculationWasAn assigning step of assigning a label to each block according to a feature amount;
  The label matrix generation meansLabels given to each block in the giving processUsingA generation process for generating a label matrix;
  A storage step of storing the label matrix generated in the generation step in the storage unit in association with the image;
  Search meansA search step of performing an image search based on the label matrix stored in the storage means,
  The search processThe search meansThe image specified as the search source image according to the specification of the search source imageGenerated from the calculation step, the applying step and the generating stepLabel matrixWhenCorresponding to the image as the comparison destination imageIn the storage meansExtract from stored label matrixdidA first matching step for associating a row-by-line label column with DP matching;
  A second matching step of obtaining a similarity between the row sequence of the search source image and the row sequence obtained in the first matching step by DP matching.
[0009]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, a preferred embodiment of the present invention will be described with reference to the accompanying drawings.
[0010]
FIG. 1 is a block diagram showing a control configuration of the image search apparatus of the present embodiment. In the figure, reference numeral 101 denotes a CPU which executes various controls in the image search apparatus of this embodiment. Reference numeral 102 denotes a ROM which stores a boot program executed when the apparatus is started up and various data. Reference numeral 103 denotes a RAM which stores a control program for processing by the CPU 101 and provides a work area when the CPU 101 executes various controls. A keyboard 104 and a mouse 105 provide various input operation environments for the user.
[0011]
An external storage device 106 includes a hard disk, a floppy disk, a CD-ROM, and the like. Reference numeral 107 denotes a network interface, which enables communication with each device on the network. Reference numeral 109 denotes an interface, and 110 denotes a scanner for reading an image. Reference numeral 111 denotes a bus connecting the above-described components.
[0012]
In the above configuration, the scanner 110 and the external storage device 106 may be replaced with those arranged on the network.
[0013]
FIG. 2 is a block diagram showing a functional configuration of the image search apparatus according to the present embodiment. In the figure, reference numeral 11 denotes a user interface unit, which detects various operation inputs from the user using the display 107, the keyboard 104, and the mouse 105. An image input unit 12 reads an image by the scanner 110. An image memory 13 stores image data obtained by the image input unit 12 in a predetermined area of the RAM 103. Reference numeral 14 denotes an image feature amount extraction unit, which extracts a feature amount of an image stored in the image memory 13 by a procedure described later. Reference numeral 15 denotes a feature amount label matrix forming unit, which generates a label matrix based on the feature amount obtained by the image feature amount extracting unit 14. Reference numeral 16 denotes a pattern matching unit, which calculates the degree of similarity using the later-described two-dimensional DP matching for the label matrix of the designated image and the label matrix of the image stored in the image storage unit 17.
[0014]
An image storage unit 17 stores image data obtained by the image input unit 12 or the like. FIG. 3 is a diagram for explaining a storage state of image data in the image storage unit 17. An image ID 111 is assigned to each image data 112, and these are stored in the image storage unit 17 in pairs. Reference numeral 18 denotes an image management database (hereinafter referred to as an image management DB), which manages image data stored in the image storage unit 17 in the data format shown in FIG. Reference numeral 19 denotes a label matrix index, which stores the label series index shown in FIG. 9 and the label component index file shown in FIG.
[0015]
An operation example of the image search apparatus of the present embodiment having the above configuration will be described below. In the following example, three colors of red (R), green (G), and blue (B) are adopted as image feature amounts focused on color, and description will be made using processing in a three-dimensional color space.
[0016]
[Image registration process]
First, processing performed at the time of image registration will be described. FIG. 4 is a flowchart showing the procedure of the image registration process according to this embodiment. First, in step S <b> 11, an image is read using the image input unit 12 in accordance with an instruction via the user interface unit 11 and held in the image memory 13. Next, in step S12, this image is divided into a plurality of blocks. In this embodiment, an image is divided into a plurality of vertical and horizontal blocks. FIG. 5 is a diagram showing an example of block division of an image according to the present embodiment. As shown in the figure, in this embodiment, it is assumed that the image is divided into a total of nine 3 × 3 images. Next, in step S13, the feature amount of each divided block is calculated, and the obtained feature amount is labeled according to the following procedure. Note that the 3 × 3３ division used in the present embodiment is for illustrative purposes only. Actually, if natural, it is preferable to set the number of divisions to 10 × 10 or more. In addition, if the product is shown on a white plain background, the number of divisions is preferably 13 × 13 or more.
[0017]
FIG. 6 is a diagram for explaining a multidimensional feature amount space according to the present embodiment. As shown in FIG. 6, the multi-dimensional feature space (RGB color space) is divided into a plurality of blocks (color blocks), that is, cells (color cells), and each cell (color cell) is uniquely identified by a serial number. Give a label. Here, the reason why the multi-dimensional feature space (RGB color space) is divided into a plurality of blocks is to absorb subtle differences in feature quantities (colors).
[0018]
For the multi-dimensional feature space, the image feature is not used as it is, and after obtaining and normalizing (normalizing) the average and variance of each parameter by experiment, for example, orthogonal transformation such as principal component analysis is performed, It is conceivable to use a meaningful dimension. The “significant dimension” is a dimension composed of principal component axes having a large contribution rate in the principal component analysis.
[0019]
In step S13, a predetermined image feature amount calculation process is performed on each divided block obtained in step S12 to determine which cell in the multi-dimensional feature amount space belongs to and a corresponding label. This process is performed for all blocks. That is, for each divided image block, calculation processing is performed to determine which color cell all pixels belong to, and the label of the most frequently used color cell is determined as the parameter label (color label) of the divided image block. Processing is performed for all blocks.
[0020]
When parameter labels are assigned to the respective blocks as described above, in step S14, the parameter labels assigned to the respective blocks are arranged in a predetermined block order, thereby obtaining a parameter label matrix (hereinafter referred to as a label matrix). ) Is generated. FIG. 7 is a diagram for explaining an example of a block order when generating a label matrix. The above parameter labels are arranged according to the numbers at the bottom of the divided image block shown in FIG. When storing the label matrix in the image management database 18 or the label matrix index 19, a two-dimensional label matrix arranged in a predetermined order as described above is stored as described above. Such a one-dimensional form is also referred to as a label matrix.
[0021]
Here, in FIG. 7A, the divided blocks are scanned in the horizontal direction from left to right, and this horizontal scanning is performed from top to bottom. As a scanning method applicable to this embodiment,
-Horizontal direction (as shown in FIG. 7A, in addition to the order of scanning from left to right from top to bottom, as shown in FIGS. 7B to 7D, left There are four scanning methods, such as scanning from right to right, from bottom to top)
Vertical direction (4 scanning methods are possible, such as scanning from top to bottom from left to right).
[0022]
In this embodiment, the scanning method shown in FIG. 7A is adopted, but the other scanning methods described above can also be applied.
[0023]
Subsequently, in step S15, the label matrix and image data obtained as described above are stored in the image storage unit 17, the image management DB 18, and the label matrix index 19. That is, an image ID is acquired for the image data read in step S11, and these are paired and stored in the image storage unit 17. Then, an image management DB record shown in FIG. 8 is generated in association with the image ID, and this is registered in the image management DB 18. Further, in step S16, a record (label series index in FIG. 9) in which the image ID group is stored in a variable-length record using the label matrix as a search key is created and registered in the label matrix index 19. Here, if the label matrix is not registered, a new record is generated, a label matrix ID is assigned, and the label matrix and the image ID are registered. On the other hand, if the label matrix is already registered, the image ID is additionally registered in the image ID group. By using such a label sequence index, when a label matrix is given, an image ID corresponding to the label matrix can be obtained at high speed.
[0024]
The above is the process performed at the time of image registration.
[0025]
[Similar image search processing]
Next, similar image search processing will be described with reference to the flowchart of FIG. FIG. 10 is a flowchart for explaining the processing procedure of the similar image search. In the present embodiment, at the time of initialization, a label matrix group of an already registered image is obtained from the label sequence index in advance, and a label component index file is generated with each label component as a key. 19 is stored. Here, the initialization time may be either when the system is started up or when an application is started. Also, when there is a new image registration and this is registered in the image DB, this label component index is generated. FIG. 11 is a diagram illustrating a data configuration example of a label component index. As shown in FIG. 11, the label component index has, for each label component, an address group (column ID group) to a label matrix having the label therein. This label component index file does not need to be recreated until it is necessary to reflect image registration, deletion, and change.
[0026]
First, when a similar search source image is designated from the user interface unit 11 in step S21, the image ID of the designated similar search source image is acquired in step S22, and the label matrix of the original image is further obtained from the image management DB 18. (In this example, a color label matrix) is acquired.
[0027]
Next, in step S23, the label component index file is referred to, and a label matrix group (label matrix in the label series index) including labels that are the same as the label matrix of the similar search source image to some extent is acquired. This is because the processing is slowed down if all the label matrices of the registered image are compared, so it is similar in advance (a label matrix group including a label matrix of a similar search source image and a predetermined number or more of the same labels). This is to improve the processing speed by making a one-to-one comparison with the label matrix of the similar search source image after narrowing down. Of course, if it is acceptable to slow down the processing, it is possible to perform a high-accuracy search by comparing with all the label matrices of the registered image (in this case, step S23 is omitted).
[0028]
Next, in step S24, each label matrix acquired in step S23 is compared with the label matrix of the similar search source image, and the similarity is calculated. And it outputs as a search result with the similarity in order from the label matrix nearest to the label matrix of the similar search source image.
[0029]
Here, a method for performing similarity comparison (similarity calculation) between label matrices will be described. Hereinafter, the label matrix acquired in step S23 is referred to as a similar comparison target image.
[0030]
FIG. 12 is a diagram showing an example of a penalty matrix between labels used when comparing label matrices and obtaining similarity. The smaller the value in the matrix, the more similar. For example, the penalty of label 2 and label 6 is “7”. Moreover, the penalty between the same labels is “0” as a matter of course. The purpose of using this matrix is to perform distance determination according to the similarity of labels. That is, in this embodiment, since the RGB color space is used as the feature amount space, the distance determination according to the similarity of colors can be performed.
[0031]
For example, a penalty matrix between labels as shown in FIG. 12 is introduced in order to reduce the penalty (distance) between adjacent cells during pattern matching between labels and to give a large penalty to distant cells. In step S24, the penalty matrices are considered and the label matrices are compared with each other. In this embodiment, two-dimensional DP matching described below (hereinafter referred to as two-dimensional DP matching) is used.
[0032]
FIG. 13 is a diagram for explaining similarity calculation processing according to this embodiment. The label matrix of the similar search source images acquired in step S22 described above can be arranged as shown in FIG. 13A according to the scanning method. If one of the label matrix groups extracted in step S23 is a similar comparison target image, the label matrix can be arranged as shown in FIG.
[0033]
First, the label column “abc” in the first row of the similar comparison destination image and the label columns (“123”, “456”, “789”) in the first to third rows of the similar search source image, respectively Is obtained by DP matching, and the row number in the similar search source image of the label column having the smallest distance is stored in the corresponding position of the similar line matrix ((c) of FIG. 13). If the obtained minimum distance is larger than a predetermined threshold, it is determined that no row is similar, and “!” Is stored at the corresponding position in the similar line matrix. Due to the nature of DP matching, for example, even if the angle of the image is slightly changed in the horizontal direction, a similar line (line) can be detected by the above processing. By performing the above processing for all rows (“def” and “ghi”) of the similar comparison target image, a similar line matrix in the column direction as shown in FIG. 13C is obtained.
[0034]
In FIG. 13C, a row similar to “abc” does not exist in the similar search source image, and a row similar to “def” is the first row of the similar search source image, a row similar to “ghi”. Is the second line of the similar search source image. The similarity between the similar line matrix obtained as described above and the standard line matrix (the row sequence of similar search source images, which is “123” in this example) is calculated using DP matching, Is output as the similarity between the similarity search source image and the similarity comparison target image. In DP matching, as is well known, the comparison is performed by expanding / contracting the label sequence to be compared (withstanding the partner to be compared without proceeding) so that the label sequence to be compared has the smallest similarity distance. I do. It is also possible to give a constraint condition (the width of the matching window) to what extent the expansion / contraction (withstand) can be made.
[0035]
FIG. 14 is a flowchart for explaining the similarity calculation procedure employing DP matching in this embodiment. The process described with reference to FIG. 13 will be further described with reference to the flowchart of FIG.
[0036]
First, in step S101, a variable i representing the row number of the similar comparison target image and a variable j representing the row number of the similar search source image are initialized to 1, and are set to indicate the first row. In step S102, the i-th label column of the similar comparison target image is acquired. For example, in the case of FIG. 13, if i = 1, “abc” is acquired. In step S103, the label column in the j-th row of the similar search source image is acquired. For example, in FIG. 13, if j = 1, “123” is acquired.
[0037]
In step S104, the distance between the two label columns obtained in steps S102 and S103 is obtained by DP matching using the color cell penalty matrix described in FIG. In step S105, if the distance obtained in step S104 is the minimum distance obtained so far with respect to the i-th row, the row number (j) is stored in the line matrix element LINE [i]. .
[0038]
The processing from step S103 to step S105 is performed for all rows of the similar search source image (steps S106 and S107). As described above, for the i-th label column of the similar comparison target image, the number of the closest row among the rows included in the similar search source image is stored in LINE [i]. Become.
[0039]
In step S108, LINE [i] obtained by the above processing is compared with a predetermined threshold (Thresh). If LINE [i] is equal to or greater than Thresh, the process proceeds to step S108, and “!” Indicating that no line is similar is stored in LINE [i].
[0040]
LINE [1] to LINE [imax] are obtained by executing the processing of steps S102 to S108 described above for all the rows of the similar comparison target image (steps S110 and S111). Output as [].
[0041]
Next, in step S113, DP matching between the standard line matrix “12... Imax” and the similar line matrix LINE [] is performed, and the distance between the two is calculated. Here, the standard line matrix is a matrix starting from 1 and increasing by 1 in the column direction.
Here, the penalty used in DP matching between the standard line matrix and the similar line matrix will be described. Two methods are conceivable for setting the DP matching penalty between the similar line matrix in the column direction and the standard line matrix. That is, there are two dynamic penalties and fixed penalties.
The dynamic penalty dynamically sets a penalty between line numbers, and the penalty between line numbers varies depending on the image. In the present embodiment, the distance of the label matrix in the horizontal (row) direction of the similar search source image is obtained, and a penalty between the rows is obtained based on the distance.
FIG. 15 is a flowchart showing a procedure for setting a dynamic penalty value according to this embodiment. In step S121, variable i is set to 1 and variable j is set to 2. Next, in step S122, the label column of the i-th row of the similar search source image is acquired, and in step S123, the label column of the j-th row of the similar search source image is acquired. In step S124, DP matching is performed on the i-th label column and the j-th label column of the similar search source image using a color penalty matrix to obtain a distance. In step S125, the DP matching distance obtained in step S124 is stored in LINE [i] [j] as a penalty between the i-th label column and the j-th label column of the similar search source image, It is stored in LINE [j] [i] as a penalty between the j-th label column and the i-th label column of the similar search source image.
Steps S123 to S125 are repeated until the value of variable j reaches jmax in step S126. As a result, for the i-th label column, a penalty value between the i + 1-th and jmax-th label columns is determined. Then, in steps S128, S129, and S130, the processes in steps S123 to S126 are repeated until the value of the variable i becomes imax-1. As a result, the penalty value determined in the above process is stored in LINE [i] “j” except for the diagonal component of i = j.
Next, in step S131, the penalty of the diagonal component of LINE [i] [j] that has not been determined in the above process is determined. Since this portion is i = j and is the same label string, the distance is 0, and thus penalty 0 is stored. In step S132, a penalty is determined for “!”. That is, the penalty for “!” Is set to a value that is somewhat larger than the maximum penalty value among all the penalty values of LINE [i] [j]. However, if this penalty value is extremely increased, the ambiguous hit property is lost.
DP matching in step S113 is performed using the penalty between the label strings calculated for the similar search source image as described above, and the similarity between the similarity search source image and the similar comparison target image is acquired.
Another fixed penalty is a DP matching penalty of “0” if the labels match, or a certain size if it does not match or is compared to “!”. Give a penalty. In this case, the penalty is always the same regardless of the similar search source image. The process of step S113 is executed using such a fixed penalty, and the similarity between the similarity search source image and the similar comparison destination image is determined.
[0042]
The matching process described above has the following characteristics. If (a) and (b) in FIG. 13 are very similar, the similar line matrix is “123” and the distance is zero. If the similar line matrix is “! 12” or “212”, the similar comparison destination image may be shifted downward with respect to the similar search source image, and the similar line matrix is “23”. ! "Or" 233 ", there is a possibility that the similar comparison target image is shifted upward with respect to the similar search source image. If the similar line matrix is “13!” Or “! 13”, there is a possibility that the similar comparison target image is reduced with respect to the similar search source image. Similarly, it is possible to detect a case where the similar comparison target image is an enlargement of the similar search source image.
[0043]
As described in step S113 above, by performing DP matching between the similar line matrix and the standard line matrix, the shift in the vertical direction is effectively absorbed. Therefore, as described above, the difference between the similar search source image and the similar comparison target image due to the upward or downward shift, enlargement, reduction, or the like is effectively absorbed, and a good similarity search is performed. Is possible.
[0044]
That is, the two-dimensional DP matching of the present embodiment is a matching that allows ambiguity before and after each label column of the label matrix, and has a property of absorbing the influence of the image positional deviation. Also, it is expected that the color of the block will be slightly different by changing the position of the object due to the difference in angle and the position of the object cut by the block, but this difference is absorbed by the above penalty matrix. Will be. As described above, the synergistic effect of the matching that allows ambiguity by the two-dimensional DP matching of the present embodiment and the allowance of ambiguity of the feature amount by the penalty matrix has no influence on the vertical / horizontal enlargement / reduction shift. Less matching is possible.
However, it is preferable to use a dynamic penalty between the dynamic penalty and the fixed penalty. For example, if there is a similar source search image of the whole wheat field, it is conceivable that every line has a similar label sequence. On the other hand, if there is an image of the whole wheat field in the similar comparison destination image, all the similar line matrices of this image may have the first line number 1 and become “111”. In this case, every line of the similar search source image is a similar image, and a hit at a low distance is not made unless the penalty between the line numbers is extremely small. However, when a dynamic penalty is used, the penalty between line numbers is low, and a result with a high degree of similarity can be obtained.
On the other hand, if a fixed penalty is used, the penalty value increases for “123” and “111”, and the similarity decreases.
[0045]
The similarity calculation process described above is performed for all the label matrices acquired in step S23, and the obtained similarities are sorted in descending order, and the process proceeds to step S25. In step S25, a search is performed using a label matrix having a high similarity from the label series index as a key, and a corresponding image ID is acquired. Thereafter, this process is repeated for each label matrix output in descending order of similarity, and as a result, image ID groups of similar images are obtained. In step S26, the image management DB 18 is referred to, a full path file name is acquired for each image ID of the image ID group, and this is presented to the user.
[0046]
By performing DP matching in the horizontal and vertical directions, that is, two-dimensionally as described above, it is possible to perform a search even if the image angle changes in the horizontal and vertical directions and further in the oblique direction, or the object moves. It is. Also, it is possible to search for a zoomed-up photographed image and a macro photographed image by the DP matching time-series expansion / contraction characteristics.
[0047]
In the above embodiment, the similar line matrix is obtained using the horizontal block and the corresponding label column. However, the similar line matrix may be obtained using the vertical block and the corresponding label column. It can be realized by the same method as described above.
[0048]
In the above embodiment, an example of performing natural image search has been described. However, it is obvious to those skilled in the art that the present invention is a technique that can also be applied to search for artificial images such as CG and CAD. .
[0049]
In the above embodiment, color information is selected as the image feature amount. However, the present invention is not limited to this, and the present invention can be implemented by obtaining other image parameters for each image division block.
[0050]
In this embodiment, an example of recognition with one feature quantity is given. However, a high-speed search from a plurality of feature quantities may be performed by performing a logical operation with a search result with another feature quantity. Is possible.
[0051]
When a search using a plurality of image feature amounts is performed on one image, the similarity obtained in the present invention is regarded as one new image feature amount, and a multivariate analysis using a plurality of parameters is performed. It is also possible to perform a search using a statistical distance measure. In the above-described embodiment, similar images having a degree of similarity exceeding a predetermined value are obtained as search results. However, a predetermined number of images may be output as search results in order from images with high similarity. Needless to say.
[0052]
Note that the present invention can be applied to an apparatus (for example, a copier, a facsimile machine, etc.) composed of a single device even if it is applied to a system composed of a plurality of devices such as a host computer, an interface device, a reader, and a printer. You may apply.
[0053]
Another object of the present invention is to supply a storage medium storing software program codes for implementing the functions of the above-described embodiments to a system or apparatus, and the computer (or CPU or MPU) of the system or apparatus stores the storage medium. Needless to say, this can also be achieved by reading and executing the program code stored in the.
[0054]
In this case, the program code itself read from the storage medium realizes the functions of the above-described embodiments, and the storage medium storing the program code constitutes the present invention.
[0055]
As a storage medium for supplying the program code, for example, a floppy disk, a hard disk, an optical disk, a magneto-optical disk, a CD-ROM, a CD-R, a magnetic tape, a nonvolatile memory card, a ROM, or the like can be used.
[0056]
Further, by executing the program code read by the computer, not only the functions of the above-described embodiments are realized, but also an OS (operating system) running on the computer based on the instruction of the program code. It goes without saying that a case where the function of the above-described embodiment is realized by performing part or all of the actual processing and the processing is included.
[0057]
Further, after the program code read from the storage medium is written into a memory provided in a function expansion board inserted into the computer or a function expansion unit connected to the computer, the function expansion is performed based on the instruction of the program code. It goes without saying that the CPU or the like provided in the board or the function expansion unit performs part or all of the actual processing, and the functions of the above-described embodiments are realized by the processing.
[0058]
As described above, according to the present embodiment, a feature amount group (a group of feature amounts obtained by dividing a feature amount space) is expressed by one symbol (ie, labeled), and the similarity between labels is expressed. The base distance is given by the above-described two-dimensional DP matching and penalty matrix. For this reason, the amount of calculation of the distance between the blocks of two images can be greatly reduced, and similar feature amounts are represented by the same label, so that similar images can be searched well. it can.
[0059]
In addition, (1) The concept of distance between labels using a penalty matrix is introduced, and (2) the label position to be compared can be moved ambiguously back and forth so that the total distance is minimum (similarity is maximum). By introducing the above-described two-dimensional DP matching that realizes matrix comparison, it is possible to search even if the angle of the image changes slightly, and it is possible to search for images having similar atmospheres.
[0060]
Furthermore, according to the above-described embodiment, the image search is further speeded up by using the index database (label series index or label component index).
[0061]
That is, according to the above-described embodiment, it is possible to perform a high-speed search for similar images in consideration of the arrangement of image feature amounts, and to search for similar images that absorb differences due to changes in shooting conditions, which has been difficult in the past. It is possible to perform robust similar image search such as absorbing a certain amount of image feature amount due to image angle change, object position change, or other shooting conditions fluctuation etc. Become.
[0062]
【The invention's effect】
As described above, according to the present invention, it is possible to search for a similar image at high speed in consideration of the arrangement of the feature amount of the image. Further, according to the present invention, it is possible to perform a similar image search that effectively absorbs a change in an image due to a change in shooting conditions such as a shooting angle and a shooting magnification.
[0063]
[Brief description of the drawings]
FIG. 1 is a block diagram illustrating a control configuration of an image search apparatus according to an embodiment.
FIG. 2 is a block diagram illustrating a functional configuration of the image search apparatus according to the present embodiment.
FIG. 3 is a diagram for explaining a storage state of image data in an image storage unit 17;
FIG. 4 is a flowchart illustrating a procedure of image registration processing according to the present embodiment.
FIG. 5 is a diagram illustrating an example of block division of an image according to the present embodiment.
FIG. 6 is a diagram illustrating a multidimensional feature amount space according to the present embodiment.
FIG. 7 is a diagram illustrating an example of a block order when generating a label matrix.
FIG. 8 is a diagram illustrating a data configuration example of an image management DB record.
FIG. 9 is a diagram showing a data order for a label series index.
FIG. 10 is a flowchart illustrating a similar image search processing procedure.
FIG. 11 is a diagram illustrating a data configuration example of a label component index.
FIG. 12 is a diagram illustrating an example of a penalty matrix between labels used when comparing a sequence of labels to obtain a similarity.
FIG. 13 is a diagram illustrating similarity calculation processing according to the present embodiment.
FIG. 14 is a flowchart for explaining a similarity calculation procedure employing DP matching in the present embodiment.
FIG. 15 is a flowchart showing a procedure for setting a dynamic penalty value according to the present embodiment.

Claims (16)

An assigning unit that divides the image into a plurality of blocks and assigns a label according to the feature amount acquired for each block;
Generating means for generating a label matrix from the labels given by the giving means;
Storage means for storing the label matrix generated by the generation means in association with the image;
Search means for performing an image search based on the label matrix stored in the storage means,
A first matching unit that associates, by DP matching, a label unit in a row unit extracted from a label matrix of a search source image with a label unit in a unit of row extracted from a label matrix of a comparison destination image;
An image search apparatus comprising: second matching means for obtaining a similarity between the line arrangement of the search source images and the line arrangement obtained by the first matching means by DP matching. The image search apparatus according to claim 1, wherein the label column in row units of the label matrix is an array corresponding to a horizontal direction of the image. The image search apparatus according to claim 1, wherein the label columns in row units of the label matrix are arranged corresponding to a vertical direction of the image. The label is a unique label given to each of the cells obtained by dividing the multidimensional feature space into a plurality of cells.
The image search apparatus according to claim 1, wherein the assigning unit calculates a feature amount for each of the blocks, and assigns a label attached to a cell to which the calculated feature amount belongs to the block. . 2. The image search apparatus according to claim 1, further comprising an output unit that outputs an image having a similarity degree obtained by the second matching unit exceeding a predetermined value as a search result. The first matching means has a table that holds a penalty value based on the distance between cells for each pair of label values, and performs DP matching on the distance between the label sequence of the search source image and the label sequence of the comparison destination image The image search apparatus according to claim 1, wherein the table is referred to when calculating using a technique. The second matching means has a table that holds a penalty value for each pair of row numbers in a row sequence, and uses the DP matching method to calculate the similarity between the row sequence of the search source image and the row sequence of the comparison destination image. The image search apparatus according to claim 1, wherein the table is referred to when calculating. Based on the distance between each label matrix of the search source image, the penalty value for each pair of row numbers in the row sequence is determined, further comprising holding means for holding this,
The second matching means refers to the penalty value held by the holding means when calculating the similarity between the row arrangement of the search source image and the row arrangement of the comparison target image using a DP matching technique. The image search apparatus according to claim 1, wherein: The first matching unit, when calculating the similarity between the label sequence of the image of the search source and the label sequence stored in the storage unit, further gives a penalty and a constraint due to the series expansion / contraction of the label comparison. The image search device according to claim 6. The image search apparatus according to claim 9, wherein the penalty and the constraint associated with the series expansion / contraction of the label comparison are acquired based on a theory of DP matching. A first table for registering an image ID group using the label matrix generated by the generating means as a key;
The output means acquires a label matrix whose similarity calculated by the search means exceeds a predetermined value, extracts an image corresponding to the label matrix acquired with reference to the first table, and uses this as a search result The image search apparatus according to claim 5, wherein the image search apparatus outputs the image as 12. The image search apparatus according to claim 11, wherein a label matrix that is a target of similarity calculation in the search means is a label matrix that is a key of the first table. The label matrix that is the target of similarity calculation in the search means includes a label that includes a predetermined number or more of the same label components as the label components included in the label matrix of the search source image among the label matrices stored in the storage means. The image search device according to claim 11, wherein the image search device is a matrix. The label matrix stored in the storage means further includes a second table in which each label component is used as a key and a label matrix group including the label component is registered.
Obtaining a label matrix including a predetermined number or more of the same label components as those included in the original image with reference to the second table, and using the obtained label matrix as a target of similarity calculation in the computing means. The image search apparatus according to claim 13, wherein Than the stored image in the storage unit, an image retrieval method definitive the image search apparatus for searching an image similar to the specified search source image,
An image feature amount extraction unit divides the image stored in the memory into a plurality of blocks, and calculates a feature amount using image data belonging to each block ; and
A labeling unit, a labeling process for labeling each block according to the feature amount calculated in the calculation process ;
A generation process in which a label matrix generation unit generates a label matrix using the label given to each block in the giving process;
A storage step of storing the label matrix generated in the generation step in the storage unit in association with the image;
A search means comprising a search step for performing an image search based on a label matrix stored in the storage means,
In the search step , the search means , according to the specification of the search source image, the label matrix generated by the calculation step, the adding step and the generation step from the image specified as the search source image, and the comparison destination A first matching step for associating a label unit in a row unit extracted from a label matrix stored in the storage unit corresponding to an image as an image by DP matching;
An image search method comprising: a second matching step of obtaining a similarity between the row sequence of the search source image and the row sequence obtained in the first matching step by DP matching. In order to cause the computer to execute an image search process for searching for an image similar to the designated search source image from the image stored in the storage means ,
An assigning unit that divides an image stored in a memory into a plurality of blocks and assigns a label to each block according to a feature amount calculated using image data belonging to each block;
Generating means for generating a label matrix from the labels given to each block by the giving means ;
And means for storing in the storage means in association with the label matrix generated by said generating means to said image,
Search means for performing an image search based on a label matrix stored in the storage means,
In response to the specification of the search source image, the search means extracts a row-unit label column extracted from a label matrix stored corresponding to the image specified as the search source image, and an image as a comparison destination image First matching means for associating the row-by-row label column extracted from the label matrix stored in correspondence with DP by DP matching;
A control program is stored that functions as an image search device including a second matching unit that obtains a similarity between the row sequence of the search source image and the row sequence obtained in the first matching step by DP matching. A storage medium.

Images