JP2017188063A - Image search system, image search method, and image search program - Google Patents

Abstract

An image search system capable of searching for a partial image of an image in a database similar to a query image. A set of feature vectors is clustered into a predetermined number of classes, a representative feature vector of each class is calculated, and a representative feature vector nearest to the feature vector calculated at each point of a database image This is solved by creating a label image having a class name to which a representative feature vector belongs to each point of each image and calculating a cumulative histogram for calculating a cumulative histogram of the label image at each point of each image. . [Selection] Figure 1

Description

  The present invention relates to an image search system, an image search method, and an image search program. More specifically, the present invention relates to an image search system and an image search system that can widely search an image including a portion similar to an example image presented by a user from a database. The present invention relates to a search method and an image search program.

  Conventionally, various methods have been proposed as a similar image search for searching for an image using an image, such as Patent Document 1 and Patent Document 2.

JP 2010-113429 A JP 2014092909 A JP 2012-226429 A

The conventional method has a problem that an image similar to the image presented by the user as a whole can be searched from the database, but an image having the image presented by the user as a partial image cannot be searched. In order to solve this problem, Patent Document 3 tries to solve this problem by obtaining a partial area that can be searched and searched in advance by detecting a place with high saliency in each image in the database. It is said. However, there is a problem that the high saliency does not necessarily coincide with the possibility of being a search target.
Further, in the conventional method, the image presented by the user is included as a part in the image included in the database, but it cannot be properly searched when the orientation of the partial image is different.
The image search system, the image search method, and the image search program according to the present invention propose a technique capable of searching for an image having a partial image of a user presented image regardless of the presence or absence of the image. For the purpose. It is another object of the present invention to enable appropriate searching even when the orientation of partial images is different.

An image search system according to the present invention includes:
A database of many images,
A feature vector calculator that calculates a local feature vector at each point of the database image;
Clustering the set of feature vectors into a predetermined number of classes, calculating representative feature vectors of each class, and registering the representative feature vectors in the database;
Label image creation for detecting the representative feature vector nearest to the feature vector calculated at each point of the image in the database and creating a label image with the class name to which the representative feature vector belongs to each point of each image And
A cumulative histogram calculator for calculating a cumulative histogram of the label image at each point of each image;
A learning unit that associates an image in the database with a cumulative histogram of a label image calculated for the image and registers the image in the database,
The feature vector calculation unit calculates a local feature vector at each point of the query image;
The label image creating unit detects a representative feature vector registered in the nearest database with respect to a feature vector calculated at each point of the query image, and the representative feature vector belongs to each point of the query image. Create a label image with a class name,
A query image histogram calculation unit for calculating a histogram of the label image calculated by the query image;
A rectangular area histogram calculation unit that calculates a histogram for an arbitrary partial rectangular area of the image based on a cumulative histogram registered in the database in association with an image in the database;
The similarity between the rectangular area histogram calculated for the image in the database and the histogram of the query image is calculated, and the maximum similarity among the similarities between the rectangular area histogram and the query image histogram included in the image is calculated. And a ranking unit that calculates the similarity of each image included in the query image and the database, and presents a predetermined number in descending order of similarity.

  Preferably, the local feature vector in the image search system is rotation invariant.

Preferably, the feature vector calculation unit includes
A Gaussian filter for applying a Gaussian filter to the image;
A gradual differential filter unit that gradually applies a x-direction differential filter and a y-direction differential filter to the image after the Gaussian filter processing a predetermined number of times;
A rotation-invariant vector calculation unit that calculates a plurality of rotation-invariant local feature vectors by performing a predetermined calculation process for each output of the gradual differentiation filter;
It is composed of

The image search method according to the present invention includes:
It has a database that stores a large number of images,
A feature vector calculating step of calculating a local feature vector at each point of the database image;
Clustering the set of feature vectors into a predetermined number of classes and calculating a representative feature vector of each class; and
Label image creation for detecting the representative feature vector nearest to the feature vector calculated at each point of the image in the database and creating a label image with the class name to which the representative feature vector belongs to each point of each image Steps,
A cumulative histogram calculation step of calculating a cumulative histogram of the label image at each point of each image;
A learning step of registering the image in the database and the cumulative histogram of the label image calculated for the image in association with the database;
A local feature vector is calculated at each point of the query image, the representative feature vector nearest to the feature vector is detected, and a class name to which the representative feature vector belongs is assigned to each point of the query image A query image histogram calculation step of creating a label image and calculating a histogram of the label image;
A rectangular area histogram calculation step of calculating a histogram for an arbitrary partial rectangular area of the image based on a cumulative histogram registered in the database in association with an image in the database;
The similarity between the rectangular area histogram calculated for the image in the database and the histogram of the query image is calculated, and the maximum similarity among the similarities between the rectangular area histogram and the query image histogram included in the image is calculated. And a ranking step of calculating a similarity between the query image and each image included in the database and presenting a predetermined number in descending order of similarity.

Preferably, the local feature vector in the image search method is rotation invariant.

Preferably, the feature vector calculation step includes:
A Gaussian filter step for applying a Gaussian filter to the image;
A gradual differential filter step of gradually applying a x-direction differential filter and a y-direction differential filter to the image after the Gaussian filter processing a predetermined number of times;
A rotation-invariant vector calculating step of calculating a plurality of rotation-invariant local feature vectors by a predetermined calculation process for each output of the gradual differentiation filter for each pixel;
Is composed of

And the image search program according to the present invention is:
The image search apparatus described above is realized by a computer.

  The image search system, the image search method, and the image search program according to the present invention calculate a histogram for an arbitrary rectangular area of an image in a database and calculate the similarity of the histogram of the query image. The partial image of the image in the database can be searched.

  Furthermore, if the local feature vector is rotation invariant, when the query image and a partial image in the database are rotated and similar, the degree of similarity is high, and a similar image closer to intuition can be searched.

  Specifically, if the above-described gradual differentiation filter is processed, a rotation-invariant local feature vector can be calculated, so that it is possible to search appropriately even when the orientation of partial images is different.

1 is a block diagram of a first embodiment of an image search system according to the present invention. It is a figure which shows rectangular area histogram calculation. It is a block diagram of 2nd embodiment of the image search system which concerns on this invention. It is explanatory drawing of a Vienna figure classification table. It is explanatory drawing of a classification code instruction | indication part. It is a block diagram showing the example of a structure of the feature vector calculation part.

  The configuration of the image search system according to the present invention will be described below.

  FIG. 1 shows a block diagram of an embodiment of an image search system according to the present invention.

  The image search system 1 is constituted by, for example, a personal computer (personal computer), and mainly stores a central processing unit (CPU) that controls the operation of each component and a control program for the device, and works when the program is executed. Main memory that is an area, a graphic board that controls the display of a monitor device such as a liquid crystal display or a liquid crystal display, a communication interface (communication I / F) connected to a network, a PC operating system (OS), a PC As an instruction input by detecting key operations on a keyboard device device, a hard disk device storing various application software including the image search system 1 according to the present invention, a CD-ROM drive, and a keyboard operation Keyboard keyboard output to CPU And controller, and a mouse controller which detects and outputs the mouse state of the position input signals, such as a state position and a mouse the mouse pointer on the monitor device to the CPU.

  The personal computer having the above-described configuration is well-known except for the image search system 1 according to the present invention, which is stored in the hard disk device, and a detailed description of each component will be omitted.

  The image search system 1 according to the present invention includes a learning unit 20 in which a cumulative histogram (definition will be described later) that characterizes each image 11 in the database 10 is associated in advance. In addition, a set of representative features necessary for creating a histogram that characterizes the query image 40 at the time of search is created. Details are as follows.

First, the learning unit 20 includes a feature vector calculation unit 21 that calculates a feature vector representing a feature of a k × k local region centered on each pixel of each image 11 in the database 10. There are various methods for calculating feature vectors. Here, an example is shown.
A predetermined number (for example, N) of feature patterns having a size of k × k is prepared in advance. Let it be f ₁ (u, v), f ₂ (u, v),…, f _N (u, v). Here, k is an odd number, and u and v are integers that move from-(k-1) / 2 to (k-1) / 2.
These feature patterns are obtained by, for example, performing principal component analysis on a large number of k × k dimensional vectors consisting of pixel values of a large number of k × k local regions in a large number of images 11 in the database 10 in advance. It is obtained by extracting N eigenvectors from the largest.
As another example, assuming H _p (u) is a Hermitian polynomial,

f _i (u, v) = 1 / √ (2 ^{p + q} p! q! π) H _p (u) H _q (v) exp (-(u ² + v ² ) / 2)

It is obtained as follows. Here, p and q are integers determined according to i.
Using these feature patterns, the i-th component of the feature vector is the image I (x, y)
v _i (x, y) = Σ _{u, v} I (x + u, y + v) f _i (u, v)
Obtained by.

Further, the feature vector calculation unit 21 can also be configured as shown in FIG. In other words, a Gaussian filter is applied to the image input by the Gaussian filter unit 21a, and an x-direction differential filter and a y-direction differential filter are gradually applied to the image after the Gaussian filter processing by the progressive differential filter unit 21b. Apply several times. Thereafter, the rotation-invariant vector calculation unit 21c can calculate a plurality of rotation-invariant local feature vectors by performing predetermined calculation processing for each output of the gradual differentiation filter for each pixel.
This configuration can be applied to both the feature vector calculation unit 21 for the input from the query image 40 and the feature vector calculation unit 21 in the learning unit 20.

A specific method for calculating a rotation-invariant feature vector is shown below.
First, the image is smoothed with a Gaussian filter of the form exp (-(x ² + y ² ) / 2σ ² ). The result is J (x, y).
An image T ₀₀ (x, y) representing the first feature is obtained by T ₀₀ (x, y) = J (x, y).
The second feature T ₁₀ (x, y) is obtained by T ₁₀ (x, y) = ∂T ₀₀ (x, y) / ら れ る x = ∂J (x, y) / ∂x.
T ₀₁ (x, y) = ∂T ₀₀ (x, y) / ∂y = ∂J (x, y) / ∂y gives the third feature T ₀₁ (x, y).
Next, if you repeat the differentiation further
T ₂₀ (x, y) = ∂T ₁₀ (x, y) / ∂x = ∂ ² J (x, y) / ∂x ²
T ₁₁ (x, y) = ∂T ₁₀ (x, y) / ∂y = ∂ ² J (x, y) / ∂x∂y
T ₀₂ (x, y) = ∂T ₀₂ (x, y) / ∂y = ∂ ² J (x, y) / ∂y ²
These are efficient because they can be obtained by differentiating the above result once again without performing second order differentiation.

Furthermore, if differentiation is repeated,
T ₃₀ (x, y) = ∂T ₂₀ (x, y) / ∂x = ∂ ³ J (x, y) / ∂x ³
T ₂₁ (x, y) = ∂T ₂₀ (x, y) / ∂y = ∂ ³ J (x, y) / ∂x ² ∂y
T ₁₂ (x, y) = ∂T ₁₁ (x, y) / ∂y = ∂ ³ J (x, y) / ∂x∂y ²
T ₀₃ (x, y) = ∂T ₀₂ (x, y) / ∂y = ∂ ³ J (x, y) / ∂y ³
In this way, by gradually differentiating one after another, as many T _pq (x, y) as necessary can be constructed.
These characteristics are not rotation invariant as they are. However, a little transformation of the formula,
In this way, the visibility of the behavior with respect to rotation is improved, and from these, rotation invariant features can be configured as follows (not shown).
The above formula is a complex number including an imaginary unit. However, on the computer, it may be divided into a real part and an imaginary part.
Note the following properties.
At this time, it can be proved that the following Equation 3 is rotation invariant.

As described above, if p is gradually increased while increasing q by one, the following is obtained.
Q ₀₀ = T ₀₀
Q ₁₀ = T ₁₀ + iT ₀₁
Q ₂₀ = T ₂₀ − T ₀₂ + 2iT ₁₁
Q ₁₁ = T ₂₀ + T ₀₂
Q ₃₀ = T ₃₀ − 3T ₁₂ + i (3T ₂₁ − T ₀₃ )
Q ₂₁ = T ₃₀ + T ₁₂ + i (T ₂₁ + T ₀₃ )
Q ₄₀ = T ₄₀ − 6T ₂₂ + T ₀₄ + i (4T ₃₁ − 4T ₁₃ )
Q ₃₁ = T ₄₀ − T ₀₄ + i (2T ₃₁ + 2T ₁₃ )
Q ₂₂ = T ₄₀ + 2T ₂₂ + T ₀₄
Q ₅₀ = T ₅₀ −10T ₃₂ + 5T ₁₄ + i (5T ₄₁ −10T ₂₃ + T ₀₅ )
Q ₄₁ = T ₅₀ − 2T ₃₂ − 3T ₁₄ + i (3T ₄₁ + 2T ₂₃ − T ₀₅ )
Q ₃₂ = T ₅₀ + 2T ₃₂ + T ₁₄ + i (T ₄₁ + 2T ₂₃ + T ₀₅ )
Q ₆₀ = T ₆₀ − 15T ₄₂ + 15T ₂₄ − T ₀₆ + i (6T ₅₁ − 20T ₃₃ + 6T ₁₅₎
Q ₅₁ = T ₆₀ − 5T ₄₂ − 5T ₂₄ + T ₀₆ + i (4T ₅₁ − 4T ₁₅ )
Q ₄₂ = T ₆₀ + T ₄₂ − T ₂₄ − T ₀₆ + i (2T ₅₁ + 4T ₃₃ + 2T ₁₅ )
Q ₃₃ = T ₆₀ + 3T ₄₂ + 3T ₂₄ + T ₀₆
These images are complex numbers consisting of real and imaginary parts, but n = p + q, l = pq
Then R _nl is invariant to rotation.

In this way, feature vectors are calculated for each pixel of each image 11 in the database 10, and the representative feature vector calculation unit 22 clusters a set of these feature vectors into M classes.
Here, clustering is performed by the k-means method, which is a typical clustering method. However, the present invention is not limited to this clustering method. As a result, one representative feature is determined for each class, and a set of M representative feature vectors is obtained. This is stored in the database 10.

Next, the label image creation unit 23 calculates a feature vector from each pixel of each image 11 in the database 10, calculates a distance between each of the M representative feature vectors and the nearest representative feature vector. To detect. Then, the class name of the class to which the representative feature vector belongs is written in the pixel.
In this way, a label image creation unit 23 is provided that creates a label image in which a class name is assigned to each pixel. Here, an integer from 0 to M-1 is simply written to each pixel as the class name. Each pixel of the label image is given a label (an integer from 0 to M-1) indicating the characteristics of a k × k local region centered on that pixel. A label image is represented by L (x, y).

  FIG. 2 is a diagram illustrating rectangular area histogram calculation.

Next, the cumulative histogram calculation unit calculates a cumulative histogram F (x, y; l) determined as follows.
F (x, y; l) = 0 when x = -1 or y = -1
Otherwise, F (x, y; l) = “0 <= x '<= x, 0 <= y'<= y in the rectangular region where L (x ', y') = l number.
For example, F (x2, y2; l) is the number of pixels whose label value is l in the shaded area in FIG.
For all images in the database 10, F (x, y; l) is calculated for all x, y, and registered in the database 10. This is called a cumulative histogram. When the size of the image is X × Y, F (X−1, Y−1; l) represents a histogram in the entire image.
This is the content of processing in the learning unit 20.

Next, when presented as a query image 40 that the user wants to search, first, the feature vector calculation unit 21 performs the feature of the k × k local region centered on the pixel in each pixel as in the processing in the learning unit 20. Is calculated.
In the label image creation unit 23, as in the processing in the learning unit 20, the distance between the feature vector in each pixel and each of the M representative feature vectors held in the database is calculated, and the nearest representative feature vector is calculated. Is detected. Then, the class name of the class to which the representative feature vector belongs is written in the pixel.

  The query image histogram calculation unit 30 calculates a query image histogram Hq (l) representing the number of pixels whose label value is 1 in the query image 40.

Next, in the rectangular area histogram calculation unit 31, the histogram H (x1, y1; x2, y2; in the rectangular area where the start point is (x1, y1) and the end point is (x2, y2) in each image in the database 10. l) is calculated by the following equation (see FIG. 2).

H (x1, y1; x2, y2; l)
= F (x2, y2; l)-F (x2, y1 -1; l)-F (x1 -1, y2) + F (x1-1, y1-1; l)

The similarity calculation unit 32 calculates the similarity R between the query image histogram Hq (l) and the rectangular area histogram H (x1, y1; x2, y2; l) as follows.
First, the normalized histogram of the query image 40 is set with the size of the query image 40 being P × Q.
q _l = Hq (l) / (P × Q)
Is calculated.

Next, the normalized histogram of the rectangular area of the image in the database 10 in the same manner
p _l = H (x1, y1; x2, y2; l) / ((x2-x1 + 1) x (y2-y1 + 1))
Is calculated.

q _l and p _l can be considered to represent probabilities because each l takes the sum of 1 and becomes 1. q _l represents the probability that the label of a pixel in the query image is l. Similarly, p _l represents the probability that the label of a pixel is l in a rectangular area where the start point of the image in the database is (x1, y1) and the end point is (x2, y2).
The closer the probabilities of both q _l and p _l are, the closer the images in the rectangular area with the start point (x1, y1) and the end point (x2, y2) of the query image and the image in the database are more similar .
In general, the degree of difference between two probability distributions is evaluated by the information amount of the Cullback library.

D = Σ _l q _l log (q _l / p _l )

By changing the rectangular area in various ways, it is determined that the rectangular area closest to the distance is most similar to the query image, and the reciprocal of D at that time is calculated as the similarity. The method for evaluating the similarity between two histograms is not limited to this.

  The ranking unit 33 calculates the similarity between the query image 40 and each image included in the database 10, and presents a predetermined number in descending order of similarity.

  FIG. 3 shows a block diagram of a second embodiment of the image search system according to the present invention. FIG. 4 is an explanatory diagram of the Vienna figure classification table. FIG. 5 is an explanatory diagram of the classification code instruction unit.

  The second embodiment is an example applied to graphic trademark retrieval. The graphic trademark search is a search for a similar graphic trademark to be presented by the user from a database of graphic trademarks registered so far.

Generally, since a graphic trademark is created by a combination of a plurality of graphics, the user cuts out a partial graphic to be searched in advance and presents it as a query image to the system. Therefore, although the basic configuration of the first embodiment is used, an area instruction is added thereto.
In the graphic trademark database, codes of the Vienna graphic classification table are given to each graphic as shown in FIG.

In general, a plurality of codes are attached to each figure. For example, if both men and women are included in the figure, the code for “male” and the code for “female” are attached. If there is a star in the circle, the "circle" code and the "star" code are attached. One graphic element may have multiple codes. For example, the figure representing the sun is both "sun" and "circle". When a certain code is attached to a certain figure, it means that the figure includes an element figure (partial figure) indicated by the code.
If the classification code is known at the time of the search, it is not necessary to search for similar images for all the images 11 in the database 10, and only the image to which the classification code is assigned may be targeted.
Therefore, in this embodiment, a new classification code instruction is also added, and only an image having the specified classification code is targeted.
In FIG. 3, an area instruction unit 51 instructs an area of a partial graphic to be searched from the query image 40 as shown in FIG.
Further, the classification code instruction unit 52 instructs a classification code (3.9.1 “fish, fish-like animal” in the example of FIG. 5) corresponding to the partial figure.

  As described above, the image retrieval system of the present invention can retrieve a partial image of an image in a database similar to a query image, as compared with the conventional method.

DESCRIPTION OF SYMBOLS 1 Image search system 10 Database 11 Image 12 Set of representative feature vector 13 Cumulative histogram 20 Learning part 21 Feature vector calculation part 22 Representative feature vector calculation part 23 Label image creation part 24 Cumulative histogram calculation part 30 Query image histogram calculation part 31 Rectangular area Histogram calculation unit 32 Similarity calculation unit 33 Ranking unit

Claims (7)

A database of many images,
A feature vector calculator that calculates a local feature vector at each point of the database image;
Clustering the set of feature vectors into a predetermined number of classes, calculating representative feature vectors of each class, and registering the representative feature vectors in the database;
Label image creation for detecting the representative feature vector nearest to the feature vector calculated at each point of the image in the database and creating a label image with the class name to which the representative feature vector belongs to each point of each image And
A cumulative histogram calculator for calculating a cumulative histogram of the label image at each point of each image;
A learning unit that associates an image in the database with a cumulative histogram of a label image calculated for the image and registers the image in the database,
The feature vector calculation unit calculates a local feature vector at each point of the query image;
The label image creating unit detects a representative feature vector registered in the nearest database with respect to a feature vector calculated at each point of the query image, and the representative feature vector belongs to each point of the query image. Create a label image with a class name,
A query image histogram calculation unit for calculating a histogram of the label image calculated by the query image;
A rectangular area histogram calculation unit that calculates a histogram for an arbitrary partial rectangular area of the image based on a cumulative histogram registered in the database in association with an image in the database;
The similarity between the rectangular area histogram calculated for the image in the database and the histogram of the query image is calculated, and the maximum similarity among the similarities between the rectangular area histogram and the query image histogram included in the image is calculated. A similarity calculation unit that outputs a query image, a ranking unit that calculates the similarity of each image included in the database, and presents a predetermined number in descending order of similarity;
An image search apparatus comprising:   The image search apparatus according to claim 1, wherein the local feature vector is a rotation-invariant feature vector. The feature vector calculation unit includes:
A Gaussian filter for applying a Gaussian filter to the image;
A gradual differential filter unit that gradually applies a x-direction differential filter and a y-direction differential filter to the image after the Gaussian filter processing a predetermined number of times;
A rotation-invariant vector calculation unit that calculates a plurality of rotation-invariant local feature vectors by performing a predetermined calculation process for each output of the gradual differentiation filter;
The image search device according to claim 1, wherein the image search device comprises: It has a database that stores many images,
A feature vector calculating step of calculating a local feature vector at each point of the database image;
Clustering the set of feature vectors into a predetermined number of classes, calculating representative feature vectors for each class, and registering the representative feature vectors in the database; and
Label image creation for detecting the representative feature vector nearest to the feature vector calculated at each point of the image in the database and creating a label image with the class name to which the representative feature vector belongs to each point of each image Steps,
A cumulative histogram calculation step of calculating a cumulative histogram of the label image at each point of each image;
A learning step of registering the image in the database and the cumulative histogram of the label image calculated for the image in association with the database;
A query image feature vector calculating step for calculating a local feature vector at each point of the query image;
A label image in which a representative feature vector registered in the database nearest to the feature vector calculated at each point of the query image is detected, and a class name to which the representative feature vector belongs is assigned to each point of the query image A query image label image creation step to create a
A query image histogram calculation step of calculating a histogram of the label image calculated by the query image;
A rectangular area histogram calculation step of calculating a histogram for an arbitrary partial rectangular area of the image based on a cumulative histogram registered in the database in association with an image in the database;
The similarity between the rectangular area histogram calculated for the image in the database and the histogram of the query image is calculated, and the maximum similarity among the similarities between the rectangular area histogram and the query image histogram included in the image is calculated. A similarity calculation step for outputting a query image and a ranking step for calculating a similarity between each image included in the database and presenting a predetermined number in descending order of the similarity;
Image search method including   The image search method according to claim 4, wherein the local feature vector is a rotation-invariant feature vector. The feature vector calculation step includes:
A Gaussian filter step for applying a Gaussian filter to the image;
A gradual differential filter step of gradually applying a x-direction differential filter and a y-direction differential filter to the image after the Gaussian filter processing a predetermined number of times;
A rotation-invariant vector calculating step of calculating a plurality of rotation-invariant local feature vectors by a predetermined calculation process for each output of the gradual differentiation filter for each pixel;
The image search method according to claim 4, wherein the image search method comprises:
The image search program which implement | achieves the image search device of any one of Claims 1-3 with a computer.