JPH11312248A - Image retrieval apparatus and method - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To enable high-speed similar image retrieval in consideration of the arrangement of image feature amounts. An image feature amount extraction unit and a feature amount label matrixing unit divide image data into a plurality of blocks.
Labels are assigned according to the feature amounts obtained for each block, and the assigned labels are arranged in a predetermined block order to generate a label matrix, and a partial label matrix is extracted from the generated label matrix. The image management DB 18 stores the generated label matrix in association with the corresponding image data, and stores the label matrix index 19
Has a data structure capable of retrieving image data using a partial label matrix as a key. When a search is instructed, a partial label matrix is extracted from the search source image data, images are narrowed down using the label matrix index 19, and a similar image search is performed on the obtained image by the pattern matching unit 16.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to an image retrieval apparatus and method for retrieving an image.

[0002]

2. Description of the Related Art Conventionally, various techniques for searching for similar images have been proposed. Techniques that have been implemented to some extent to perform similar image searches on natural images include:
Many use color information as an image feature amount. In many cases, a histogram relating to color information is obtained, and a search is performed using a RGB ratio or a combination of colors that are frequently present in an image.

[0003] However, in the above method, the search accuracy is not always high because the position information of the color is lost. For example, Japanese Patent Application Laid-Open No. 8-249349 discloses a pattern matching method in which an image is divided into a plurality of blocks and each feature amount (representative color) is used. However, in this method, it is necessary to calculate the distance of the feature value between each block for two images to be matched, which requires a huge amount of calculation. In particular, when a representative color is used as a feature value, it is necessary to handle three pieces of RGB data, which further complicates the calculation. Further, since the comparison is performed using the feature amount itself, the accuracy of the comparison is improved, but there is a problem that a similar image search cannot be performed simply because the angle of the image changes or the position of the object changes. That is, the angle of the image changes, the position of the object changes, or absorbs a certain difference in the image feature amount depending on the shooting conditions, etc.
It has not been possible to perform a so-called robust similar image search in which an appropriate image search is performed while having some ambiguity.

When it is desired to perform a search by focusing on a certain object (a part) in an image, if the image (background image) other than the object is different, the search becomes impossible. was there.

[0005]

As a general image search system, it is known that a keyword is assigned to an image when searching for a natural image, and the image is searched using the keyword. However, this keyword assigning operation is a labor-intensive operation, and for images for which no keyword is assigned, an operation of presenting a reduced image and manually selecting the image occurs, making the search operation complicated. Was.

SUMMARY OF THE INVENTION The present invention has been made in view of the above problems, and has as its object to provide an image retrieval apparatus and method which enable high-speed retrieval of similar images in consideration of the arrangement of image feature amounts. I do.

Another object of the present invention is to search for a similar image in consideration of the arrangement of the feature amounts of the image, and to enable an image search apparatus capable of searching for a similar image by absorbing a difference due to a change in photographing conditions. And a method.

Another object of the present invention is to set a feature amount group to one.
An object of the present invention is to reduce the amount of calculation of the similarity by expressing the image by a label and calculating the similarity between the images by expressing the image by a label matrix, thereby enabling a quick similar image search.

It is another object of the present invention to appropriately manage a label matrix and remarkably improve the processing speed of an image search process using labels.

Another object of the present invention is to provide a method for comparing a label sequence or a label matrix to determine the similarity between an original image and a comparison target image, and to determine the degree of ambiguity before and after a label position such as DP matching or fuzzy non-deterministic automaton. It is another object of the present invention to apply a method that allows for similarity and to enable more effective similar image retrieval.

It is another object of the present invention to enable similar image retrieval focusing on a certain object (part) in an image.

[0012]

An image retrieval apparatus according to one aspect of the present invention for achieving the above object has, for example, the following configuration. That is, generating means for dividing the image data into a plurality of blocks, providing a label according to the feature amount obtained for each block, and arranging the provided labels in a predetermined block order to generate a label matrix, Storage means for storing the label matrix generated by the generating means in association with the image data; extracting a partial label matrix from the generated label matrix; searching for image data using the extracted partial label matrix as a key A storage unit that stores a possible table, and a first search unit that extracts a partial label matrix from image data of a search source and searches for a similar image using the table.

Preferably, each similar image retrieved by the first retrieval means is used as a comparison target image, and the label image is obtained from the label matrix of the comparison target image obtained from the storage means and the search source image data. A second search unit that obtains a similarity by performing a matching process based on an inter-label distance with a label matrix, and obtains a search result based on the obtained similarity;

Preferably, when a partial image forming a part of the image is designated as a search source image, a label corresponding to the characteristic amount is assigned to a block including the partial image data representing the partial image. A second generating means for generating a label matrix of the search source image by giving a don't care label having a distance of zero to any label with respect to other blocks, and image data of the partial image And a third generation unit that generates a partial label matrix based on a label assigned to a block including the first and second search units, wherein the first and second search units are generated by the second generation unit and the third generation unit. An image is searched using the label matrix and the partial label matrix thus obtained.

[0015]

Preferred embodiments of the present invention will be described below with reference to the accompanying drawings.

FIG. 1 is a block diagram showing a control configuration of the image retrieval apparatus according to the present embodiment. In FIG.
Denotes a CPU, which executes various controls in the image search device of the present embodiment. Reference numeral 102 denotes a ROM, which stores a boot program executed when the apparatus is started and various data. A RAM 103 stores a control program for processing by the CPU 101 and
101 provides a work area for executing various controls.
A keyboard 104 and a mouse 105 provide various input operation environments for the user.

Reference numeral 106 denotes an external storage device, which comprises a hard disk, a floppy disk, a CD-ROM, or the like. A network interface 107 enables communication with each device on the network. Reference numeral 109 denotes an interface, and 110 denotes a scanner for reading an image. A bus 111 connects the above components. Note that a control program for realizing the processing shown in each flowchart described below may be stored in the ROM 102 or may be stored in the RAM 10 from the external storage device 106.
3 may be loaded.

In the above configuration, the scanner 110
Alternatively, the external storage device 106 may be replaced with a device arranged on a network.

FIG. 2 is a block diagram showing a functional configuration of the image retrieval apparatus according to the present embodiment. In the figure, reference numeral 11 denotes a user interface unit, which detects various operation inputs from a user using a display 107, a keyboard 104, and a 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 according to a procedure described later. Reference numeral 15 denotes a feature label matrixing unit, which generates a label matrix based on the feature obtained by the image feature extracting unit 14.
A pattern matching unit 16 calculates the similarity between the label matrix of the designated image and the label matrix of the image stored in the image storage unit 17, and searches for a similar image. Reference numeral 17 denotes an image storage unit, which stores image data obtained by the image input unit 12 or the like.

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 a data form shown in FIG. Also, 1
Reference numeral 9 denotes a label component index, which stores the label component index file shown in FIG. The use of the label component index will be described later with reference to the flowchart of FIG.

An example of the operation of the image retrieval apparatus according to 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 values focusing on color, and the processing is performed using a three-dimensional color space.

[Image Registration Processing] First, processing performed at the time of image registration will be described. FIG. 5 is a flowchart illustrating the procedure of the image registration process according to the present embodiment. First, in step S11, an image is read using the image input unit 12 in accordance with a user's instruction via the user interface unit 11, and stored in the image memory 13. Next, in step S12, this image is divided into a plurality of blocks. In the present embodiment, an image is divided into a plurality of vertical and horizontal blocks. FIG. 6 is a diagram illustrating an example of image block division according to the present embodiment. As shown in the figure, in the present embodiment, it is assumed that an image is divided into a total of nine (3 × 3) blocks for explanation. Next, in step S13, the feature amount of each divided block is calculated, and the obtained feature amount is labeled by the following procedure.

It should be noted that the division into 3 × 3 used in the present embodiment is merely for explanation. In practice, it is preferable to set the number of divisions to 10 × 10 or more for a natural image.
In addition, when a product is shown on a white plain background, the number of divisions is preferably 13 × 13 or more.

FIG. 7 is a diagram for explaining a multidimensional feature quantity space according to the present embodiment. As shown in FIG. 6, the multidimensional feature amount space (RGB color space) is divided into a plurality of blocks (color blocks), that is, cells (color cells), and each cell (color cell) is unique by a serial number. Give a label.
The reason why the multidimensional feature space (RGB color space) is divided into a plurality of blocks is to absorb subtle differences in feature amounts (colors).

In the multidimensional feature space, the image features are not used as they are, but the averages and variances of the respective parameters are experimentally obtained and normalized (normalized).
For example, it is conceivable to perform orthogonal transformation such as principal component analysis and use a significant dimension. In addition, the “significant dimension” is a dimension configured by a principal component axis having a large contribution rate in the principal component analysis.

In step S13, a predetermined image feature amount calculation process is performed on each of the divided blocks obtained in step S12 to determine which cell in the multidimensional feature amount space belongs, and a corresponding label is determined. Ask for. This process is performed for all blocks. That is, for each divided image block, a calculation process is performed to determine which color cell all the pixels belong to, and the label of the most frequent color cell is determined as the parameter label (color label) of the divided image block. Processing is performed on all blocks.

When the 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 forming a parameter label matrix (hereinafter referred to as a label label matrix). ) Is generated.

FIG. 8 is a diagram for explaining an example of a block order when a label string is generated. The above-mentioned parameter labels are arranged according to the numbers in the cells of the divided image block in FIG. When the label matrix is stored in the image management database 18 or the label component index 19, a two-dimensional label matrix arranged one-dimensionally in a predetermined order as described above is stored. Such a one-dimensional form is also referred to as a label matrix.

Here, in FIG. 8A, the divided blocks are horizontally scanned from left to right, and the horizontal scanning is performed from top to bottom. The scanning method applicable to the present embodiment is as follows. In the horizontal direction (as shown in FIG. 8A, in addition to the order of scanning from left to right from top to bottom, 8 (b) to (d), there are four scanning methods such as scanning from left to right from bottom to top), and vertical direction (scanning from top to bottom from left) There are four possible scanning methods, such as scanning to the right.) As shown in FIG. 8E, the scanning is divided into even lines and odd lines.

In this embodiment, the scanning method shown in FIG. 8A is employed, but it is apparent that the other scanning methods described above can be applied.

Subsequently, in step S15, the label string and the image data obtained as described above are stored in the image storage unit 17,
This is reflected in the image management DB 18. That is, step S1
Acquire an image ID for the image data read in step 1,
These are paired and stored in the image storage unit 17. Also,
The image management DB record shown in FIG. 3 is generated in association with the image ID, and registered in the image management DB 18.

Then, in step S16, a partial label matrix is obtained from the label matrix of the image, and a label component index file as shown in FIG. 4 is updated.
The label component index file stores a record that stores an image ID group and the number of partial label matrices included in each image using a partial label matrix (including a single label) as a search key. According to the label component index, by providing a partial label matrix (including a single label), the image ID group having the partial label matrix and the inclusion of the partial label matrix (including the single label) of each image are included. Numbers are obtained fast. At the stage of image registration, information is stored at an unprocessed level. Also, all the labels constituting the label matrix are registered in the label component index. For example, histogram information of labels is obtained, and all of the appearing labels are reflected in the label component index. For example, when a label component index in which a single label is registered is used, a data record using all labels appearing in the histogram information as keys is updated.

In the image registration process, a don't care label described later is not used. That is, don't care labels are not registered in the label component index. The above is the processing performed at the time of image registration.

[Image Retrieval Processing] Next, FIG. 9 and FIG.
The similar image search process according to the present embodiment will be described with reference to the flowchart of FIG. The search processing differs depending on whether the search is a similar image search of the entire image or a search focusing on an object. Hereinafter, description will be made in order.

FIG. 9 is a flowchart illustrating the procedure of an image search according to the present embodiment. First, step S2
In 1, the user specifies whether the search is a similar image search of the entire image or a search focusing on a desired object (or partial area). When the search method is specified, step S2
In step 2, a label matrix and a feature portion label matrix suitable for the specified search method are acquired. This step S2
In 2, the processing differs depending on the specified search method. Hereinafter, step S22 will be described with reference to the flowchart of FIG.
Will be described in detail.

FIG. 10 is a flowchart for explaining a procedure for extracting a characteristic portion label matrix according to the present embodiment.

First, in step S41, the designated search method is determined. If the specified search method is “similar search of entire image”, the process proceeds to step S42. In step S42, the searcher selects an image for which a similar search of the entire image is to be performed. That is, a similar search source image is specified. In step S43, a label matrix corresponding to the specified similar search source image is obtained from the image DB 18. Then, in step S44, a characteristic part label matrix is obtained.

As to the method of obtaining the characteristic portion label matrix, there are various means for realizing such as learning by experience / experiment and statistical methods, and there is no particular limitation here. For example, a characteristic partial label matrix (including a single label) is obtained by performing, for example, histogram analysis on the label matrix.

On the other hand, if it is determined in step S41 that the similarity search for the object of interest has been designated, the flow advances to step S45 to determine an image of the object of interest as a search source. As a method of determining the target object, for example, the following method can be used.

(1) The object of interest in the image is designated by a pointing device, the object of interest is separated from the background image by image processing, and the object image of interest is created by removing the background image. As an example, an existing image processing technique for extracting an object of interest from coordinates designated by a user in consideration of how edges and colors change is used. In this case, if there is an error in the extracted content of the target object, correct extraction of the target object can be performed by correcting the extracted outline with a pointing device.

(2) Select an object image of interest from the object image library. One example of an object image library is to install an object image that allows keyword search in its own system in advance, or to search for an object image using a keyword on a server via a network such as the Internet to retrieve the object image. There is a way to get it.

(3) An image of the object of interest is drawn using drawing software, or the color of the object image of interest obtained in (1) or (2) is changed and used as the object image of interest.

Next, the process proceeds to step S46, in which the extracted object image of interest is pasted on an image frame in consideration of its size, position, and direction to create a similar search source image.
Then, in step S47, the similar search source image is divided into blocks, and only the part of the divided block including the object image of interest obtained by any of the above methods (1) to (3) is the same as that at the time of registration. An image feature extraction process (for example, representative color extraction) is performed for labeling. Further, in step S48, a don't care label having a penalty of 0 is given to each of the divided blocks not including the object image of interest, and a label matrix of the similar search source image is generated. I do.

In the images obtained by the above-mentioned methods (1) to (3), the image dividing method may be changed according to the ratio of the area occupied by the object image of interest to the area of the background area. . For example, when the area of the object image of interest is equal to or smaller than a predetermined ratio, a predetermined number of divided blocks are obtained for a rectangular region circumscribing the object image of interest and label allocation is performed. If the area of the object image of interest exceeds a predetermined ratio, a divided block is obtained for the above-described image frame.

Then, in step S49, step S
The histogram processing as described above is performed on each label except for the don't care label from the label matrix of the similar search source image obtained in 48 to obtain a feature portion label matrix. For example, a characteristic partial label sequence is obtained by performing histogram analysis on a label matrix obtained only from the image division block group including the target object. In the histogram analysis, weighted histogram processing may be performed in consideration of a prior existence probability of a color, saturation in a color space, and the like. Also, in the similarity search using the target object, a plurality of characteristic partial label matrices can be present.

As described above, when the label matrix and the characteristic portion label matrix of the similar search source image suitable for the search method are obtained, the process proceeds to step S23 in FIG. In step S23, label component index 19
The upper limit value and the lower limit value of the number of contents of the characteristic portion label matrix obtained in 22 are determined. The range of the number of contents determined by the upper limit value and the lower limit value is used for narrowing down (pre-search) the image to be subjected to the matching process using the label component index 19.

There are various means for determining the upper and lower limits of the number of contents of the characteristic partial label matrix, such as learning based on experience and experiments, statistical methods, and the like. As an example, the designation is performed by the ratio to the number n0 of the search source images that include the acquired characteristic part label matrix. For example, an ambiguity degree fuzziness with a value of 1 or more (the greater the degree of ambiguity is performed) is introduced, the upper limit is n0 × fuzziness proportional to the ambiguity, and the lower limit is n0 ÷ f inversely proportional.
uzziness.

As described above, it is possible to adjust the ambiguity of the pre-search by giving the ambiguity fuzziness according to the degree of ambiguity when searching for an image that has been enlarged or reduced, or when searching for a slightly different image. It becomes possible.

Next, in step S24, referring to the label component index file, an image ID group including the number of characteristic part label matrices within the range of the upper limit value and the lower limit value determined in step S23 is obtained. As shown in FIG. 4, the label component index uses the partial label matrix as a key, and registers the image ID of the image including the partial label matrix and the number of contents. Therefore, a search can be performed using the feature portion label matrix obtained in step S44 or step S49, and an image ID including the feature portion label matrix in a desired content range can be obtained easily and at high speed.

Narrowing down is performed until the number of image IDs obtained using the partial feature label matrix becomes equal to or less than a predetermined target number. For example, the image ID groups are sequentially acquired by the above-described method using the characteristic part label sequence selected in order from the top of the histogram, and the logical ID of the sequentially acquired image ID groups is obtained to narrow down to the target number of image IDs. Go out. In the histogram analysis, a weighted histogram process may be performed in consideration of a prior existence probability of a color, saturation in a color space, and the like. Further, a plurality of characteristic partial label matrices may exist.

Next, a group of label matrices containing the same label to some extent and the label matrix of the image of the similar retrieval source are compared, and a group of label matrices close to the label matrix of the image to be subjected to similar retrieval are output as a retrieval result together with the similarity. I do.

When the searcher selects an image for which a similar search is to be performed, a color label matrix corresponding to the image is obtained from the image management DB, and a color label matrix group of already registered images is obtained from the index file. By comparison,
A color label matrix group close to the color label matrix of the image to be searched for similarity is output as a search result together with the similarity.

In the processing in step S24, if matching (comparison) between label matrices is performed for all registered images, the processing becomes slow. This is for comparison with the label matrix of the similar search source image. Of course, if the processing may be delayed, a comparison with all the label matrices of the registered image may be performed to perform a highly accurate search.

Next, in step S25, pattern matching is performed between the label matrix of the search source image and the label matrix of the image obtained in step S24. That is, a label matrix of an image having a common label to some extent or more and a label matrix of the similar search source image are compared by performing a matching process in consideration of a penalty matrix between labels. Figure 11 for the penalty matrix
Will be described later. The similarity is determined based on a penalty value (distance between labels) obtained as a result of this comparison. In the present embodiment, two-dimensional DP matching in consideration of the two-dimensional arrangement of labels in the label matrix is used. In addition, 2
The dimension DP matching will be described later.

In step S26, it is determined whether or not the similarity obtained as a result of the matching processing in step S25 is equal to or greater than a predetermined threshold. If the similarity is equal to or larger than the predetermined threshold, the process proceeds to step S27, where the image ID is registered in the search result, and the images are sorted in descending order of the similarity. On the other hand, if it is determined in step S26 that the similarity has not reached the predetermined threshold value, step S27 is skipped and excluded from the search results. In step S28, it is determined whether or not the processing of steps S25 to S27 has been completed for all the images acquired in step S24. If there is an unprocessed image, the process returns to step S25. Proceed to step S29.

In step S29, referring to the image management database 18, a file name of a full path corresponding to the image IDs registered in descending order of similarity is obtained as a search result, and is presented to the user.

[Two-Dimensional DP Matching] Next, two-dimensional DP matching for performing similarity comparison between label matrices will be described.

FIG. 11 is a diagram showing an example of a penalty matrix between labels used for comparing label strings and calculating similarity. The smaller the value in the matrix, the more similar. That is, in pattern matching between color labels, a penalty (distance) is reduced between adjacent color cells, and a large penalty is given to a distant color cell. For example, the penalty for label 2 and label 6 is “7”. The penalty between the same labels is “0” as a matter of course. The purpose of using this matrix is to make a distance determination according to the similarity of labels. That is, in the present embodiment, since the RGB color space is used as the feature amount space, it is possible to determine the distance according to the similarity of the color. However, don't
For the care labels, penalty is defined as 0 for all labels.

For example, in the example shown in FIG. 12, the label sequence of the search source image is "112313441" and the label sequence of the search target image is "113224452". Such one-dimensional DP matching of a label sequence, that is, one-dimensional DP matching, is generally well known. That is, when DP matching is performed on the label string of FIG. 12 using the penalty matrix of FIG.
As shown in FIG. 13, the distance between both label rows (final solution)
Is found. In this example, the following condition is used as the inclination limit. That is, in FIG. 14, the grid point (i-
1, j), (i-1, j-1) and (i, j-1) are represented by g (i-1,
j), g (i-1, j-1), g (i, j-1) and the penalty on the grid point (i, j) is d (i, j), the grid point (i , j), the cost g (i, j) is obtained by the following recurrence formula.

[0060]

(Equation 1)

In the comparison between label strings, matching may be performed so that label sequences such as automata can be compared ambiguously. By using such an ambiguity technique, a low penalty is given to the addition of an extra label, a missing label, or a repetition of the same label, and a penalty between labels is given in FIG.
By calculating the distance between the label rows using the penalty matrix between the two color labels, ambiguous pattern matching can be performed. As the automaton, a "fuzzy non-deterministic finite automaton" described in "A fuzzy non-deterministic finite automaton using a fuzzy non-deterministic finite automaton" of Japanese Patent Application Laid-Open No. 8-241335 can be applied.

In the present embodiment, similarity comparison (calculation of similarity) between label matrices is performed using two-dimensional DP matching obtained by extending the one-dimensional DP matching into two dimensions. Hereinafter, two-dimensional DP matching will be described.

FIG. 15 is a view for explaining the similarity calculation processing according to this embodiment. The label matrices of the similar search source images acquired in step S22 (steps S43 and S48) can be arranged as shown in FIG. 15B according to the scanning method. Step S
If one of the label matrices of the image IDs extracted in 24 is a similar comparison destination image, the label matrices can be arranged as shown in FIG.

First, the label string "abc" on the first line of the similar comparison destination image and the label strings on the first to third lines of the similar search source image ("123", "456", "789") Is obtained by DP matching, and the row number of the label sequence having the shortest distance in the similar search source image is stored in the corresponding position of the similar line matrix ((c) in FIG. 15). Also, if the obtained minimum distance is greater than a predetermined threshold, it is determined that there is no similarity to any row,
"!" Is stored in the corresponding position of the similar line matrix. D
Due to the nature of the P matching, for example, even if the angle of the image slightly changes in the horizontal direction, a similar line can be detected by the above processing. The above processing is performed on all the rows (“def”, “gh”) of the similar comparison destination image.
i)), a similar line matrix in the column direction as shown in FIG. 15C is obtained. In this process, the process is not performed on a column (Don't care label sequence) consisting only of the don't care label in the similar search source image. This is because a column consisting only of the don't care labels has a distance of zero to all the columns of the similar comparison destination image.

In FIG. 15C, a line similar to “abc” does not exist in the similar search source image, and a line similar to “def” is included in the first line “ghi” of the similar search source image. This indicates that the similar line was 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 arrangement of the rows of the similar search source image, which is “123” in this example) is calculated using DP matching. Is output as the degree of similarity between the similar search source image and the similar comparison destination image. In the DP matching, as is well known, the label sequence to be compared is expanded or contracted so that the similarity distance between the label sequences to be compared becomes the smallest (the patient to be compared does not proceed to the next step, but must be patient).
Then, a comparison process is performed. It is also possible to give the extent to which expansion / contraction (patience) is possible by a constraint condition (width of the matching window).

FIG. 16 is a flowchart for explaining the procedure of calculating the similarity using the two-dimensional DP matching according to the present embodiment. The processing described with reference to FIG.
This will be further described with reference to the flowchart of FIG.

First, in step S101, a variable i representing the line number of the similar comparison destination image and a variable j representing the line number of the similar retrieval source image are initialized to 1, and both are set to indicate the first line. . Next, in step S102,
The label column in the i-th row of the similar comparison destination image is obtained. For example, in the case of FIG. 15, if i = 1, “abc” is acquired. Then, in step S103, a label string on the j-th line of the similar search source image is obtained. For example, in FIG. 15, if j = 1, “123” is acquired. In step S103a, it is determined whether or not the label string acquired in step S103 is a don't care label string. If the label string is a don't care label string, the flow advances to step S106; otherwise, the flow advances to step S104.

Next, in step S104, the distance between the two label strings obtained in steps S102 and S103 is obtained by DP matching using the color cell penalty matrix described in FIG. Then, in step S105, if the distance obtained in step S104 is the minimum value of the distance obtained so far for the i-th row, the row number (j) is set to the line matrix element LINE.
Stored in [i].

The above steps S103 to S1
The process of step S05 is performed for all rows of the similarity search source image (steps S106 and S107). As described above,
With respect to the i-th label column of the similar comparison destination image, the number of the closest line among the lines included in the similar search source image is stored in LINE [i].

Then, in step S108, the LINE [i] processed in the above process and a predetermined threshold value (Thres
h). And LINE [i] is Thr
If the value is equal to or greater than sh, the process proceeds to step S108, and “!” indicating that the line is not similar to any line is set to LINE [i]
To be stored.

The above-described steps S102 to S10
By executing the processing of No. 8 on all the rows of the similar comparison destination image (steps S110 and S111), LINE is obtained.
Since [1] to LINE [imax] are obtained, these are output as a similar line matrix LINE [].

Next, in step S113, the standard line matrix "12... Imax" and the similar line matrix LINE
DP matching with [] is performed to calculate the distance between the two. Here, the standard line matrix is a matrix starting from 1 and increasing by 1 in the column direction.

Here, a penalty used in DP matching between a standard line matrix and a similar line matrix will be described. There are two methods for setting a penalty for DP matching between a similar line matrix in the column direction and a standard line matrix. That is, there are a dynamic penalty and a fixed penalty.

The dynamic penalty dynamically sets a penalty between line numbers, and the penalty between line numbers changes depending on an image. In the present embodiment, the distance of the label matrix in the horizontal (row) direction of the similar search source image in itself is obtained, and the penalty between each row is obtained based on the distance.

FIG. 17 is a flowchart showing a procedure for dynamically setting a penalty value according to the present embodiment. In step S121, the variable i is set to 1 and the variable j is set to 2 respectively. Next, in step S122, the label sequence on the i-th row of the similar search source image is obtained, and in step S123, the label sequence on the j-th row of the similar search source image is obtained. Then, in step S124,
Using the color penalty matrix, the label column of the i-th row and the label column of the j-th row of the similar search source image
Perform P matching and obtain distance. Step S12
In step 5, the distance of the DP matching obtained in step S124 is stored in LINE [i] [j] as a penalty between the label column of the i-th row and the label column of the j-th row of the similar search source image. The penalty between the label row on the j-th row and the label row on the i-th row of the search source image is stored in LINE [j] [i].

Steps S123 to S125 are repeated until the value of variable j becomes jmax in step S126. As a result, a penalty value is determined for the label column in the i-th row and each label column in the i + 1 to jmax rows. Then, steps S128 and S
129 and S130, steps S123 to S126
Is repeated until the value of the variable i becomes imax-1. As a result, the penalty values determined in the above processing are stored in LINE [i] “j” except for the diagonal components of i = j.

Next, in step S131, the penalty of the diagonal component of LINE [i] [j] not determined in the above processing is determined. Since this portion is i = j and is the same label sequence, the distance is 0, and thus a penalty of 0 is stored. In step S132,
Determine penalty 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 the penalty value is extremely large, the characteristic of hitting vaguely is impaired.

Using the penalty between the label strings calculated for the similar search source image as described above, DP matching in step S113 is performed to obtain the similarity between the similarity search source image and the similar comparison target image. .

On the other hand, in the case of a fixed penalty, as a penalty for DP matching, a penalty of “0” if the labels match, a penalty of not matching, or “!”
If this is the case, a certain amount of penalty is given. In this case, the penalty is always the same regardless of the similar search source image. The processing of step S113 is executed using such a fixed penalty to determine the similarity between the similarity search source image and the similarity comparison destination image.

The matching process described above has the following features. If (a) and (b) in FIG. 15 are very similar, the similar line matrix is “123”,
The distance is 0. In addition, the similar line matrix is "! 1
If it is “2” or “212”, the similar comparison destination image may be shifted downward with respect to the similar search source image, and the similar line matrix may be “23!” Or “233”. For example, there is a possibility that the similar comparison destination image is shifted upward from 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 from the similar search source image. Similarly, it is possible to detect a case where the similar comparison destination image is an image obtained by enlarging the similar search source image.

As described in the above step S113, by performing the DP matching between the similar line matrix and the standard line matrix, the deviation in the vertical direction is effectively absorbed. For this reason, the difference between the similar search source image and the similar comparison target image due to the upward or downward displacement, enlargement, reduction, and the like as described above is effectively absorbed, and a good similarity search is performed. Becomes possible.

That is, the two-dimensional DP matching according to the present embodiment is a matching that allows ambiguity before and after in each label column of the label matrix, and has a property of absorbing the influence of image displacement. In addition, it is expected that the position of the object changes due to a difference in angle and the position of the object cut by the block changes, so that the hue of the block may be slightly different, but this difference is absorbed by the above penalty matrix. Will be. As described above, the synergistic effect of the matching that allows the ambiguity by the two-dimensional DP matching of the present embodiment and the allowance of the ambiguity of the feature amount by the penalty matrix has an effect on the displacement of the vertical and horizontal enlargement and reduction. It enables less matching.

However, it is preferable to use a dynamic penalty between the dynamic penalty and the fixed penalty. For example, assuming that there is a similar original search image of a whole wheat field, it is conceivable that all lines will have similar label strings. On the other hand, if it is assumed that the image of the wheat field is also present in the similar comparison destination image, the first line number 1 is entered in all the similar line matrices of this image, which may be “111”. In this case, all the lines of the similar search source image are similar images, and unless the penalty between the line numbers is extremely small, no hit occurs at a low distance. However, when a dynamic penalty is used, the penalty between line numbers is low, and a result with high similarity can be obtained.

On the other hand, if a fixed penalty is used,
For “123” and “111”, the penalty value increases and the similarity decreases.

As described above, by performing the DP matching in the horizontal and vertical directions, that is, in two dimensions, the image angle changes in the horizontal and vertical directions, and further in the oblique direction.
The search can be performed even when the object is moving. In addition, the time-series expansion / contraction characteristics of the DP matching make it possible to retrieve a zoom-up photographed image and a macro photographed image.

In the above embodiment, the similar line matrix is obtained by using the horizontal blocks and the corresponding label columns. However, the similar line matrix is obtained by using the vertical blocks and the corresponding label columns. This can also be realized by a method similar to the above.

As described above, according to the present embodiment, a feature amount group (a group of feature amounts obtained by dividing the feature amount space) is represented by one symbol (ie, labeling), and the labels The distance based on the similarity is given by the two-dimensional DP matching and the penalty matrix. For this reason, the amount of calculation of the distance between the blocks of the two images can be significantly reduced, and similar feature amounts are represented by the same label, so that a similar image can be searched well. it can.

Further, (1) the concept of distance between labels by a penalty matrix is introduced, and (2) the position of the label to be compared can be moved ambiguously back and forth, so that the total distance is minimized (similarity is maximized). By introducing the two-dimensional DP matching for realizing such a label matrix comparison, it is possible to search even if the angle of the image slightly changes, and it becomes possible to search for an image having a similar atmosphere.

Further, according to the above embodiment, the use of the index database (label component index) further speeds up image retrieval.

That is, according to the above-described embodiment, a high-speed search for similar images in consideration of the arrangement of the feature amounts of images can be performed, and a search for similar images that absorbs differences due to fluctuations in photographing conditions and the like can be performed. Perform robust similar image search, such as absorbing some differences in image features due to changes in the angle of the image, changes in the position of the object, or changes in other shooting conditions, which were difficult in the past. Becomes possible.

In the above embodiments, an example in which a natural image search is performed has been described. However, it is known to those skilled in the art that the present invention is a technology that can be applied to search for artificial images such as CG and CAD. Is clear.

In each of the above embodiments, color information is selected as an image feature value. However, the present invention is not limited to this, and can be implemented by obtaining other image parameters for each image division block. is there.

In the above embodiment, an example of recognition with one feature has been described. However, a high-speed search from a plurality of features can be performed by performing a logical operation on a search result with other features. It is also possible to do.

When performing a search using a plurality of image feature amounts for one image, the similarity obtained by the present invention is set to 1
It is also possible to perform a multivariate analysis using a plurality of parameters and perform a search using a statistical distance scale, assuming two new image features. Further, in the above embodiment, similar images having similarities exceeding a predetermined value are obtained as search results. However, it is also possible to output a predetermined number of images in order from images having high similarity as search results. Needless to say.

By specifying the degree of ambiguity, the DP
By changing the width of the so-called matching window in the matching, the ambiguity of the search can be set as desired. FIG. 18 illustrates a matching window in DP matching. In FIG. 18, the straight line A is represented by J = I + r, and the straight line B is represented by J = I−r. The width of the matching window can be changed by changing the value of r. Therefore, keyboard 1
If the value of r is changed by designating the degree of ambiguity from 04, the similarity search can be performed with the degree of ambiguity (width of the matching window) desired by the user.

In the two-dimensional DP matching as in the above embodiment, the width of the matching window in horizontal DP matching and the width of the matching window in vertical DP matching can be set separately. Good. Alternatively, both matching windows may be configured to change at different rates. In this way, the user can set finer ambiguity at the time of similar image search. For example, in a case where the block order as shown in FIG. 8 is used, a case where it is desired to allow the target object in the search source image to move in the horizontal direction, or a case where the search source image is a horizontally long image. In such a case, the width of the matching window in the horizontal DP matching may be increased to increase the ambiguity in the horizontal direction.

In the case of a similarity search in which one parameter is added to one image that cannot be blocked,
It is also possible to perform a search based on a statistical distance scale, using the similarity obtained by the present invention (created using the sum of penalties) as one new feature amount. Further, in the above embodiment, similar images having similarities exceeding a predetermined value are obtained as search results. However, it is also possible to output a predetermined number of images in order from images having high similarity as search results. Needless to say.

Further, instead of the DP matching processing, the position of the label to be compared, such as a fuzzy non-deterministic automaton, can be moved ambiguously back and forth, and the label sequence in which the total distance is minimized (the similarity is maximized) is reduced. It is also possible to introduce a method for realizing comparison, whereby it is possible to search even if the angle of the image is slightly changed, and it is possible to search for an image having a similar atmosphere.

Further, according to the above embodiment, the use of the index database (label component index (FIG. 4)) further speeds up image retrieval.

As described above, according to the present embodiment, an image retrieval apparatus and method suitable for retrieving an image without a keyword are provided.

At present, the barriers to image recognition technology are thick. By providing a means for finding a reduced image close to the image desired by the user and searching for an image similar to the image, it is possible to repeat the reduced image presentation and similar image search. As a result, a means for obtaining an image desired by a searcher with high probability can be considered.

At this time, in this method, robust similar image retrieval can be performed at high speed, for example, by changing the angle of an image, changing the position of an object, or absorbing a certain difference in image feature amount due to shooting conditions. Can be performed. In addition, it is possible to perform a search that is not affected by the background search, which is a weak point of the conventional similar image search, and focuses on the target object.

The present invention can be applied to a system composed of a plurality of devices (for example, a host computer, an interface device, a reader, a printer, etc.), and can be applied to a single device (for example, a copier, a facsimile). Device).

An object of the present invention is to supply a storage medium storing a program code of software for realizing the functions of the above-described embodiments to a system or an apparatus, and to provide a computer (or CPU) of the system or apparatus.
And MPU) read and execute the program code stored in the storage medium.

In this case, the program code itself read from the storage medium implements the functions of the above-described embodiment, and the storage medium storing the program code constitutes the present invention.

As a storage medium for supplying the program code, for example, a floppy disk, hard disk, optical disk, magneto-optical disk, CD-ROM, CD
-R, a magnetic tape, a nonvolatile memory card, a ROM, or the like can be used.

When the computer executes the readout program code, not only the functions of the above-described embodiment are realized, but also the OS (Operating System) running on the computer based on the instruction of the program code. ) May perform some or all of the actual processing, and the processing may realize the functions of the above-described embodiments.

Further, after the program code read from the storage medium is written into a memory provided on a function expansion board inserted into the computer or a function expansion unit connected to the computer, based on the instruction of the program code, It goes without saying that the CPU included in the function expansion board or the function expansion unit performs part or all of the actual processing, and the processing realizes the functions of the above-described embodiments.

[0109]

As described above, according to the present invention,
It is possible to search for similar images at high speed in consideration of the arrangement of image feature amounts.

Further, according to the present invention, it is possible to search for similar images in consideration of the arrangement of the feature amounts of images, and to search for similar images in which differences due to fluctuations in photographing conditions are absorbed.

Further, according to the present invention, the feature amount group is represented by one label, the image is represented by a label matrix, and the similarity between the images is calculated to reduce the amount of calculation of the similarity. It is possible to search for similar images.

Further, according to the present invention, the label matrix is appropriately managed, and the processing speed of the image search processing using the label is remarkably improved.

Further, according to the present invention, when the similarity between the original image and the comparison target image is determined by comparing the label sequence or the label matrix, the ambiguity before and after the label position such as DP matching or fuzzy non-deterministic automaton is removed. By applying the forgiving method, more effective similar image retrieval can be performed.

Further, according to the present invention, it is possible to perform a similar image search focusing on a certain object (part) in an image.

[0115]

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a control configuration of an image search device according to an embodiment.

FIG. 2 is a block diagram illustrating a functional configuration of the image search device according to the embodiment;

FIG. 3 is a diagram illustrating a data configuration example of an image management database.

FIG. 4 is a diagram illustrating a data configuration example of a label component index.

FIG. 5 is a flowchart illustrating a procedure of an image registration process according to the embodiment.

FIG. 6 is a diagram illustrating an example of block division of an image according to the present embodiment.

FIG. 7 is a diagram illustrating a multidimensional feature amount space according to the present embodiment.

FIG. 8 is a diagram illustrating an example of a block order when a label string is generated.

FIG. 9 is a flowchart illustrating a procedure of an image search according to the embodiment.

FIG. 10 is a flowchart illustrating a procedure for extracting a characteristic portion label matrix according to the present embodiment.

FIG. 11 is a diagram illustrating an example of a penalty matrix between labels used when comparing label strings and calculating similarity.

FIG. 12 is a diagram illustrating an example of a label string of a similar search source image and a label string of a similar search destination image.

FIG. 13 is a diagram illustrating one-dimensional DP matching.

FIG. 14 is a diagram for explaining the inclination limitation of DP matching.

FIG. 15 is a diagram illustrating a similarity calculation process according to the embodiment.

FIG. 16 is a flowchart illustrating a procedure of similarity calculation using two-dimensional DP matching according to the present embodiment.

FIG. 17 is a flowchart illustrating a procedure for dynamically setting a penalty value according to the embodiment;

FIG. 18 is a diagram illustrating a matching window in DP matching.

Claims (23)

[Claims] 1. Dividing image data into a plurality of blocks,
Generating means for generating a label matrix by assigning a label according to the feature amount obtained for each block and arranging the assigned labels in a predetermined block order; Storage means for storing data in association with data; storage means for extracting a partial label matrix from the generated label matrix; and storing a table capable of searching for image data using the extracted partial label matrix as a key; And a first search unit that extracts a partial label matrix from the image data and searches for a similar image using the table. 2. A label matrix of a comparison target image obtained from the storage unit and a label matrix obtained from the search source image data, using each similar image searched by the first search unit as a comparison destination image. 2. The image search method according to claim 1, further comprising a second search unit that obtains a similarity by performing a matching process based on an inter-label distance between and obtains a search result based on the obtained similarity. apparatus. 3. The table is registered with an identifier of image data including the partial label matrix and a content number of the partial label matrix by each image data, using each partial label matrix as a key. Item 2. The image search device according to Item 1. 4. The label is a unique label given to each of cells obtained by dividing a multi-dimensional feature amount space into a plurality of cells, and the generation unit assigns a feature amount to each of the blocks. 2. The image search device according to claim 1, wherein a label assigned to a cell to which the calculated feature amount belongs is assigned to the block. 5. When a partial image forming a part of an image is designated as a search source image, a label corresponding to the feature amount is given to a block including partial image data representing the partial image, and A second generation unit that generates a label matrix of an image of a search source by assigning a don't care label having a distance between all the labels of zero with respect to the block, and image data of the partial image. A third generation unit configured to generate a partial label matrix based on a label assigned to the block, wherein the first and second search units include a label generated by the second generation unit and the third generation unit. The image search device according to claim 2, wherein the image search is performed using the matrix and the partial label matrix. 6. A designating means for designating a desired partial image in an image, and an extracting means for extracting partial image data corresponding to the partial image designated by the designating means and providing the extracted partial image data to the second generating means. The image search device according to claim 5, further comprising: 7. A designating means for designating image data representing a desired object of interest, and combining the image data designated by the designating means with an image having a predetermined background to generate a search source image. The image search apparatus according to claim 5, further comprising: a combining unit provided to the second generation unit. 8. The second search means has a penalty table for holding a penalty value for each label value pair, and refers to each penalty table to each label of the image data searched by the first search means. 8. The image search device according to claim 2, wherein a distance between a matrix and a label matrix obtained from the search source image data is calculated. 9. The label matrix represents a two-dimensional label matrix, wherein the second search means includes: a row-based label string extracted from a label matrix of the search-source image data; First matching means for associating, by DP matching, a row-by-row label string extracted from a label matrix of the obtained comparison destination image data to obtain a row arrangement of the comparison destination image data; and a label of the original image data 3. The image retrieval apparatus according to claim 2, further comprising a second matching unit that obtains, by DP matching, a similarity between the row arrangement of the matrix and the row arrangement obtained by the first matching unit. 10. The first matching means has a penalty table for holding a penalty value for each label pair, and uses a DP matching method to determine the distance between the label sequence of the search source image and the label sequence of the comparison destination image. 10. The image search apparatus according to claim 9, wherein the penalty table is referred to when performing the calculation by using. 11. The second matching means has a line-to-line penalty table that holds a penalty value for each pair of line numbers in a line list, and a similarity between the line list of the search source image and the line list of the comparison target image. 10. The image search device according to claim 9, wherein when calculating using the DP matching method, the line spacing penalty table is referred to. 12. A storage unit for determining a penalty value for each pair of rows based on the similarity of each label column in the row direction of the original image data, and storing the determined penalty value as the inter-row penalty table. The image search device according to claim 11, wherein: 13. The D used in the first matching means.
The image search device according to claim 9, further comprising a first setting unit that sets a width of a matching window of P matching. 14. The D used in said second matching means.
The image search device according to claim 9, further comprising a second setting unit that sets a width of a matching window of P matching. 15. The first search means extracts a partial label matrix from the search source image data using the same technique as the holding means, and extracts an image including the partial label matrix within a predetermined content number range. 15. The image search device according to claim 1, wherein the search is performed using the table. 16. The apparatus further comprising: setting means for setting the range of the content number based on the number of partial label matrices extracted from the image data of the search source included in the image data of the search source. The image search device according to claim 15, wherein the search is performed. 17. The image search apparatus according to claim 16, wherein the setting unit determines the range of the content number based on the number included in the image data of the search source and a designated degree of ambiguity. . 18. A method for generating a label matrix by dividing image data into a plurality of blocks, assigning labels according to the feature amounts acquired for each block, and arranging the assigned labels in a predetermined block order. And a storing step of storing the label matrix generated in the generating step in a storage device in association with the image data, extracting a partial label matrix from the generated label matrix, and extracting the extracted partial label matrix. A holding step of holding a table from which image data can be searched as a key; and a first search step of extracting a partial label matrix from the search source image data and searching for a similar image using the table. How to search for images. 19. A label matrix of the comparison target image obtained from the storage device and a label matrix obtained from the image data of the search source, using each similar image searched in the first search step as a comparison destination image. 19. The image search according to claim 18, further comprising a second search step of obtaining a similarity by performing a matching process based on an inter-label distance between and obtaining a search result based on the obtained similarity. Method. 20. When a partial image forming a part of an image is designated as a search source image, a label corresponding to the feature amount is given to a block including partial image data representing the partial image, and A second generation step of generating a label matrix of an image of a search source by giving a don't care label having a distance of zero to any label with respect to the block of the image, and image data of the partial image. A third generation step of generating a partial label matrix based on the label given to the block, wherein the first and second search steps are performed by the second generation step and the label generated by the third generation step. 20. The image search method according to claim 19, wherein an image search is performed using a matrix and a partial label matrix. 21. A storage medium for storing a control program for causing a computer to perform an image search, wherein the control program divides image data into a plurality of blocks, and according to a feature amount acquired for each block. A label for generating a label matrix by arranging the assigned labels in a predetermined block order, and a label matrix generated in the generating step is associated with the image data in the storage device. A code of a storage step of storing, a code of a holding step of extracting a partial label matrix from the generated label matrix, and a code of a holding step of holding a table capable of searching for image data using the extracted partial label matrix as a key, A code for a first search step of extracting a partial label matrix from the image data and searching for a similar image using the table. Storage medium characterized Rukoto. 22. A label matrix of a comparison target image obtained from the storage device, and a label matrix obtained from the search source image data, wherein each similar image searched in the first search step is used as a comparison destination image. 22. The method according to claim 21, further comprising a code of a second search step of obtaining a similarity by performing a matching process based on an inter-label distance between and obtaining a search result based on the obtained similarity. Storage medium. 23. When a partial image forming a part of an image is designated as a search source image, a label corresponding to the feature amount is given to a block including partial image data representing the partial image, and The code of the second generation step of generating a label matrix of the search source image by giving a don't care label having a distance between all labels of zero for the block of A code of a third generation step of generating a partial label matrix based on the label given to the included block, wherein the first and second search steps are performed by the second generation step and the third generation step. 23. The storage medium according to claim 22, wherein an image search is performed using the generated label matrix and partial label matrix.