JP2005235041A - Retrieval image display method and retrieval image display program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To enable a user to efficiently find out a desired image in a short time when listing a number of retrieved images. <P>SOLUTION: An image group of retrieval results of the retrieval of an image database is acquired (S1), and an n-dimensional characteristic quantity is extracted from each retrieval result image (S2). The n-dimensional characteristic quantity is analyzed by multi-variable statistic analysis processing to calculate a new two-dimensional characteristic quantity (S3). Each retrieval result image is regarded as a point on a distance space with the two-dimensional characteristic quantity as two axes, and clustered to m-pieces of cluster groups (S4), and the display position and display the size of each retrieval result image are determined based on the clustering information (S5). Each retrieval result image is reduced and listed on a screen of a display device according to the determined display position and the display size (S6). <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

  The present invention relates to a search image display method and a search image display program for searching for an image having a specific feature from among a large number of candidate images and displaying it.

  Conventionally, a keyword is added to image data and stored in a database, and a keyword is specified at the time of search to search for an image to which the keyword is added, and a plurality of searched images are reduced to display devices in the search order. There are image search methods for displaying a list. In such a conventional technique, when there are a large number of search result images that match the keyword, the images are displayed in random order, so that there is a problem that it takes time to search for the target image. It was. In addition, in order to narrow down the number of search targets, there is a problem that a new keyword must be added and the search must be performed again.

  In order to solve these problems, when storing image data in a database, in addition to keywords, a system that pre-registers attribute values for classification to make it easier to view when displaying search results as a list. Exists. However, it is not realistic to manually add attribute values to all image data that is expected to increase explosively in the future.

Therefore, there is a need for a technology that automatically classifies image data based on basic features such as saturation and brightness that all image data has and whose numerical values can be automatically calculated by an electronic computer. . As such a technique, with respect to an image set having n-dimensional attribute information, attention is paid to specific two-dimensional attribute information of n dimensions, and a two-dimensional metric space is selected according to the feature amount of the attribute information. There is an image search technique that enables efficient search by generating a subspace and specifying the subspace as a search condition (see, for example, Patent Document 1).
JP-A-5-282375

  However, the technique disclosed in Patent Document 1 has a problem that the list display of the search result image greatly depends on the selection of the dimension axes of the two feature amounts to be employed.

  There are many image features that affect vision and sensation, such as saturation, hue, luminance, and their spatial differential values (Laplacian). For example, take one saturation. There are also options such as the average value and maximum value of the saturation of each pixel. There is also a selection of whether the pixel range when calculating the average value or the maximum value covers the entire screen or only one-nineth of the central portion. Which two of these dimension axes are adopted generally depends on the search purpose, but the fact that all searchers must select the “appropriate axis” is inconvenient for practical use. Is not always practical.

  Further, in the technique disclosed in Patent Document 1, when a searcher specifies a subspace from a two-dimensional metric space, efficient browsing cannot be performed unless the subspace size is appropriately specified. Since the “appropriate size” varies greatly depending on the search target, there is a problem that finding the “appropriate size” requires troublesome work for the searcher.

  In view of the above-described problems, the present invention can be performed even if the searcher does not select the “appropriate axis” of the two-dimensional metric space, or the searcher does not find the “appropriate size” of the subspace. It is an object to realize a list display of images so that a desired image can be efficiently found in a short time from images as search results.

  In order to solve the above-described problem, the present invention reflects all attribute information instead of selecting two attribute information from them when three-dimensional or more digitized attribute information is obtained. Two new attribute axes are dynamically generated, and a search image is arranged and displayed in a two-dimensional metric space based on the two attribute axes.

  The present invention also divides a two-dimensional metric space generated from a group of image data into a plurality of clusters by a known clustering method, assigns a partial area of the screen to each cluster, and assigns image data belonging to the cluster to the partial area. Is filled in as much as possible and displayed in a reduced size.

  FIG. 1 is a flowchart for explaining the principle of the present invention. The flowchart of FIG. 1 shows the flow of processing when an image satisfying an arbitrarily given condition such as a keyword is searched from an image database, and a plurality of images acquired by the search are reduced and displayed on a display device. Show.

  First, in search result image set acquisition processing step S1, a plurality of images (search result image sets) are acquired by searching an image database. Next, in image feature amount extraction processing step S2, n-dimensional feature amounts represented by numerical values such as saturation, hue, and luminance are extracted from each search result image acquired in step S1, and image feature amount analysis processing step In S3, the n-dimensional feature value is analyzed by a multivariate statistical analysis process such as principal component analysis to calculate a new two-dimensional feature value. In the image space clustering processing step S4, each search result image is regarded as a point on the distance space having two-dimensional feature amounts as two axes, and is clustered into m (m ≧ 2) cluster groups, and an image arrangement determining processing step In S5, the display position and display size of the search result image are determined based on the clustering information.

  In image display processing step S6, each search result image is displayed in a list on the screen of the display device in accordance with the display position and display size of each search result image determined by the search result information generation processing in steps S2 to S5.

  FIG. 2 is a diagram showing an example of the principle configuration of the present invention. The example of FIG. 2 is an example of an image search system that searches an image database for an image satisfying an arbitrarily given condition such as a keyword, and reduces a plurality of searched images and displays them on a display device.

  The image search system includes a search result image set acquisition unit 10 that acquires a plurality of images (search result image set) by searching an image database, and search result information (search result image) used for display from the acquired search result image set. , Display position, display size, etc.) and a display device 30 for displaying each search result image based on the generated search result information.

  The search result information generation unit 20 includes an image feature amount extraction unit 21 that extracts n-dimensional feature amounts represented by numerical values such as saturation, hue, and luminance from each image data belonging to the search result image set, and an n-dimensional feature amount extraction unit 21. An image feature quantity analysis unit 22 that calculates a two-dimensional new feature quantity by analyzing the feature quantity by multivariate statistical analysis processing such as principal component analysis, and each search result image has two-dimensional feature quantities as two axes. An image space clustering unit 23 that performs clustering into m cluster groups that are regarded as points on the metric space, and an image arrangement determination unit 24 that determines the display position and display size of each search result image based on the cluster information. .

  The processing functions of the above means can be realized by a computer and a software program, and the program can be recorded on a computer-readable recording medium or provided through a network.

  According to the present invention, when two or more dimensionalized attribute information is obtained from image data, two new attribute axes that reflect all the attribute information are dynamically generated. No need to select the “appropriate axis”. In addition, a two-dimensional metric space generated from the image data group is divided into a plurality of clusters by a known clustering method, a partial area of the screen is assigned to each cluster, and image data belonging to the cluster is assigned to the partial area as much as possible. Since a large amount is displayed in a reduced size, the searcher does not need to find the “appropriate size” of the subspace. Therefore, the searcher can find out a desired image from the search result images in a short time, and can efficiently search for a necessary image.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings. FIG. 3 is a diagram illustrating a configuration example of the image search system according to the embodiment of the present invention. The image search system includes a search condition input device 40, a search condition collation unit 11, a search result information generation unit 20, a display device 30, and an image database 50.

  The search condition input device 40 is a means for inputting a condition for searching for an image from a user of the image system, for example, a keyword for collation, and the search condition input by the user is used as a search condition. The data is transferred to the verification unit 11. The search condition matching unit 11 extracts an image set that matches the input search condition as a subset of the image database 50, and passes it to the search result information generation unit 20. The search result information generation unit 20 calculates the display position and display size of each image data when displayed on the display device 30, and delivers them to the display device 30 together with the image data. The display device 30 displays each image data according to the calculated display position and display size.

  The search result information generation unit 20 includes an image feature amount extraction unit 21, an image feature amount analysis unit 22, an image space clustering unit 23, and an image arrangement determination unit 24. The image feature quantity extraction unit 21 extracts the numerical value of the attribute group of the image data from each image data delivered from the search condition matching unit 11 and delivers it to the image feature quantity analysis unit 22.

  The image feature amount analysis unit 22 performs principal component analysis on the numerical value group of the attribute group of each image data, calculates two new attributes (respectively attribute X and attribute Y, respectively), and The numerical value of attribute X and the numerical value of attribute Y are calculated and transferred to the image space clustering unit 23.

  The image space clustering unit 23 generates a two-dimensional metric space with attributes X and Y, and regards each image data by regarding the numerical values of the attribute X and attribute Y of each image data as the X coordinate value and Y coordinate value of the metric space. Are clustered into u × v clusters by, for example, the K-means clustering method so that a set of these points is evenly allocated to each cluster, and the coordinate value of the centroid of each cluster and Information on points (images) belonging to each cluster is transferred to the image arrangement determination unit 24.

  The image layout determining unit 24 divides the entire screen into u × v screen areas by dividing the screen by u and v vertically, and coordinates the center of gravity of the cluster in the u × v screen areas. By assigning each cluster using the value, the display position and display size of each image data on the display device 30 are calculated, and the calculated display position and display size are transferred to the display device 30 together with the image data.

  Hereinafter, the present embodiment will be described more specifically. In the following, it is assumed that there are four feature quantities extracted from the image data and analyzed: attribute 1, attribute 2, attribute 3, and attribute 4, and the number of clusters divided by the image space clustering unit 23 is 2 × 2. It is assumed that the number of screen areas divided by the image arrangement determination unit 24 is 2 × 2.

  The searcher inputs a search condition by an input method (for example, keyword input) prepared in the search condition input device 40. The search condition matching unit 11 extracts an image set that matches the input search condition as a subset of the image database 50, and delivers the extracted image set to the search result information generation unit 20.

  FIG. 4 is a diagram for explaining the processing of the image feature amount analysis unit 22 in the present embodiment. Here, it is assumed that the number of image data extracted by the search condition matching unit 11 is 15, and the names of the image data are image 1, image 2,.

In the search result information generation unit 20, the image feature amount extraction unit 21 extracts the values of attribute 1, attribute 2, attribute 3, and attribute 4 of each image data. By this processing, a numerical value group of feature values as shown in FIG. 4A is obtained. In FIG. 4A, the numerical value of the attribute b of the image a is represented as C _ab .

The image feature amount analysis unit 22 performs principal component analysis on the numerical group in FIG. 4A to generate new attributes X and Y. Further, the value of attribute X and attribute Y of each image data is calculated, and a numerical value group as shown in FIG. 4B is obtained. In FIG. 4B, the numerical value of the attribute X of the image a is represented as C _aX, and the numerical value of the attribute Y of the image a is represented as C _aY .

  Assume that attribute X and attribute Y are two orthogonal axes in the two-dimensional metric space, and that the values of attribute X and attribute Y of each image data (image 1 to image 15) are the X coordinate and Y coordinate, respectively, 4B, the set of image data and attribute values shown in FIG. 4B can be identified with an XY graph as shown in FIG. 4C, for example. In FIG. 4C, the plotted points represent the coordinate positions of the respective image data (image 1 to image 15).

  FIG. 5 is a diagram for explaining the processing of the image space clustering unit 23 in the present embodiment. FIG. 6 is a flowchart of the image space clustering process in the present embodiment. Note that the graph shown in FIG. 5A is the same XY graph as that shown in FIG.

First, the image space clustering unit 23 uses the K-means clustering method for the two-dimensional metric space as shown in FIG. The metric space is divided into four regions (clusters K ₁ , K ₂ , K ₃ , K ₄ ) (step S40).

In this example, 15 points are divided into four. FIG. 5B is an example of the result of clustering FIG. 5A by the K-means clustering method. Here, K ₁ {Image 1, Image 2, Image 3, Image 7}, K ₂ {Image 4, Image 5, Image 6, Image 8}, K ₃ {Image 9, Image 11, Image 13, Image 15} , K ₄ {image 10, image 12, image 14}.

Next, the image space clustering unit 23 calculates the barycentric coordinates p _i (i = 1 to 4) of each cluster K _i (i = 1 to 4) (steps S41 to S44). FIG. 5C shows the barycentric coordinates p _i calculated for each cluster K _i in FIG. 5B. Information on points (images) belonging to the respective clusters K _{1 to} K ₄ and barycentric coordinates (p _{1 to} p ₄ ) are transferred to the image arrangement determining unit 24 (step S45).

  FIG. 7 is a diagram for explaining the processing of the image arrangement determining unit 24 in the present embodiment. FIG. 8 is a flowchart of image arrangement determination processing in the present embodiment.

  First, the image arrangement determining unit 24 limits the two-dimensional metric space to a rectangular finite region as shown in FIG. 7A within a range in which all the points corresponding to each image data and all the centroids are accommodated ( Step S50). A finite rectangular area as shown in FIG. 7A can be associated with the display area of the display device 30 by obvious coordinate conversion.

Next, the finite rectangular area as shown in FIG. 7A is divided into 2 × 2 (generally u × v) equal-area rectangular areas as shown in FIG. 7B (step S51). ). In FIG. 7B, a rectangular region at the upper left corner is L _1, and from there, L ₂ , L ₃ , and L ₄ are sequentially turned toward the center. Here, there is no special meaning in selecting clockwise as the numbering method for each L _j (j = 1 to 4). If one number is added to one rectangular area without excess or deficiency, You can use another numbering.

Clusters K _i (i = 1 to 4) are assigned to each region L _{j in} order from the smallest number j, so that all images belonging to K _i can be displayed in the display region of the display device 30. The display position and display size of the image are calculated, and the calculated display position and display size are transferred to the display device 30 together with the image data (steps S52 to S510). When the cluster K _i is allocated to each region L _j , the allocation is performed so that the relative positional relationship between the rectangular regions and the relative positional relationship between the cluster centroids correspond as much as possible.

An example of the allocation procedure is described below. The procedure described below, already region _{L 1, L 2, ...,} L j-1 respectively K _i1, K _i2, ..., when K _ij-1 is assigned, K _i for L _j This is a procedure for determining (K _ij ). Here, K _ij means K _i assigned to L _j .

When the center of gravity p _i of the cluster K _i not assigned to the regions L ₁ , L ₂ ,..., L _j-1 exists on the region L _j (step S53), the regions L ₁ , L _{2 ,.} of centroid p _i of the cluster K _i that is not assigned to _-1, i on regions L _j is probing the smallest center of gravity p _i (step S54).

When the center of gravity p _i of the cluster K _i not assigned to the regions L ₁ , L ₂ ,..., L _j-1 does not exist on the region L _j (step S53), L ₁ , L _{2 ,.} of centroid p _i of the cluster K _i that have not been assigned to _1, the distance between the center of L _j is probing the smallest center of gravity p _i (step S55).

When j = 1 for the first time, it is checked whether or not the center of gravity p _i exists on the region L ₁ (step S53). If it exists, the center of gravity p _i on the region L ₁ where i is smallest is searched ( In step S54), if it does not exist, the center of gravity p _i having the smallest distance from the center of L ₁ is searched (step S55).

The cluster K _i having the center of gravity p _i obtained by the search is assigned to the region L _j (step S56).

In the example of FIG. 7B, first, since the center of gravity p ₁ exists in the region L ₁ , the cluster K ₁ is assigned. In the region L _2, the center of gravity does not exist, the cluster K ₂ the distance between the center of the area L ₂ is the centroid of the smallest center of gravity p ₂ is assigned. In the region L ₃ , the center of gravity p ₂ and the center of gravity p ₄ exist, but since the cluster K ₂ has already been assigned to the region L ₂ , the cluster K ₄ is assigned. Since the center of gravity p ₃ exists in the region L ₄ , the cluster K ₃ is assigned.

Although an example of the allocation procedure has been described above, another procedure may be used as long as allocation is performed so that the relative positional relationship between the rectangular areas and the relative positional relationship between the cluster centroids correspond as much as possible. . For example, for all bijective functions (ie, allocation patterns) f from {L ₁ , L ₂ , L ₃ , L ₄ } to {K ₁ , K ₂ , K ₃ , K ₄ },
D _f = Σ _{(j = 1,2,3,4)} {Distance between L _j and f (L _j )}
May be used, and _f that minimizes D _f may be adopted as an assignment.

When the assignment of each K _i to each region L _j is determined, each L _j is associated with a partial region of the display region of the display device 30 by obvious coordinate transformation. For example, L ₁ in FIG. 7B corresponds to the upper left region in FIG.

Now, among the regions L _j of the cluster K _i is allocated in the display area of the display device 30, the start point coordinates (x _0, y _0), and Vertical H, correspond to the region of the oblong W, also, K _i the number of points representing the image data is c-number belongs to (the respective image data, Img _1, Img _2, ..., and Img _c) When it is, the image data Img _k corresponding to points belonging to K _i ( The display position (x coordinate and y coordinate) and display size (vertical and horizontal) of k = 1, 2,..., c) are calculated, for example, by the following formula (step S57), and the calculated display position and display size are calculated. Are transferred to the display device 30 together with the image data (step S58).

(X coordinate of the display position of Img _k )
= X ₀ + ((W / √s) * rnd (k−1, √s))
(Y coordinate of the display position of Img _k )
= Y ₀ + ((H / √s) * qt (k−1, √s))
(Display length of Img _k ) = H / √s
(Img _k display landscape) = W / √s
Here, s represents “the smallest integer that is a square of a certain integer and not less than c”, qt (a, b) represents “a quotient obtained by dividing a by b”, rnd (a, b) represents “the remainder when a is divided by b”. If the calculation result is not an integer, the decimal part is rounded down.

  Through such a series of processes, arrangement information as shown in FIG. 7C is delivered to the display device 30. However, in FIG. 7C, a margin that should not exist between the images is provided in order to emphasize the arrangement state of the images.

  The display device 30 performs enlargement / reduction processing of each image according to the designation of the image data delivered from the image arrangement determination unit 24, its display position, and display size, and each image is displayed at a corresponding position in the display area. To display.

  As described above, the embodiment of the present invention has been described. However, the image space clustering process is not performed on the two-dimensional metric space of FIG. 4C, and the two-dimensional metric space is limited to a finite rectangular area as it is. The display position and the display size of the image may be determined according to the position of each point (image) in the two-dimensional distance space, and the image may be displayed on the display device 30. Thereby, an image can be displayed at a position corresponding to a point on the two-dimensional distance space of the display device 30.

  The above image retrieval system was actually constructed and evaluated. In order to eliminate the arbitraryness in the selection of experimental images, image search using six types of keywords is performed using the image search service of goo (http://www.goo.ne.jp/). A group of 500 images was used as an experimental image. The six types of keywords were “goldfish”, “penguin”, “kitty”, “Mickey Mouse”, “Natsumi Abe”, and “Thai food”, and the subjects were previously listed as “what they want to search”.

  In each image group, the number of clusters is 3 × 3, the number of points belonging to each cluster is 25, the above-described image search process is performed, and a list display result according to the present invention is prepared. In addition, as a comparison target, an image in which 25 × 9 = 225 pieces are arranged in a grid from the upper left to the lower right in order from the image with the highest search hit rate (simple arrangement) is prepared. Randomly selected images were given to each subject, and the same images were retrieved from each display result, and the time until discovery was measured and compared.

  FIG. 9 is a diagram showing the results of an evaluation experiment in this example. In FIG. 9, each numerical value is an average value of time (unit: second) required to search for one image. Of 5 persons (subjects A to E), 4 persons (subjects A and C to E) were able to search faster by the list display according to the present invention. It can be considered that the effectiveness of the list display according to the present invention has appeared because the difference in one second (subject B) who is faster in simple placement is also less than 1 second.

It is a flowchart for demonstrating the principle of this invention. It is a figure which shows the principle structural example of this invention. It is a figure which shows the structural example of the image search system in embodiment of this invention. It is a figure for demonstrating the process of the image feature-value analysis part in this Embodiment. It is a figure for demonstrating the process of the image space clustering part in this Embodiment. It is an image space clustering process flowchart in this Embodiment. It is a figure for demonstrating the process of the image arrangement | positioning determination part in this Embodiment. It is an image arrangement | positioning determination flowchart in this Embodiment. It is a figure which shows the result of the evaluation experiment in a present Example.

Explanation of symbols

DESCRIPTION OF SYMBOLS 10 Search result image set acquisition part 11 Search condition collation part 20 Search result information generation part 21 Image feature-value extraction part 22 Image feature-value analysis part 23 Image space clustering part 24 Image arrangement | positioning determination part 30 Display apparatus 40 Search condition input device 50 Image The database

Claims (4)

Search an image database that stores images with n-dimensional (n ≧ 3) attribute information expressed numerically, satisfying any given condition, and reduce the searched images A search image display method for displaying on a display device, comprising:
Extracting n-dimensional attribute information from each of a plurality of searched images;
A process of calculating a new two-dimensional attribute from the extracted n-dimensional attribute information by multivariate statistical analysis;
Generating a two-dimensional metric space with the two-dimensional new attributes as x-axis and y-axis, respectively;
A step of displaying each retrieved image on a display device by reducing and arranging the searched image at a position in the two-dimensional distance space corresponding to the attribute value of the new attribute of the image. Search image display method. Search an image database that stores images with n-dimensional (n ≧ 3) attribute information expressed numerically, satisfying any given condition, and reduce the searched images A search image display method for displaying on a display device, comprising:
Extracting n-dimensional attribute information from each of a plurality of searched images;
A process of calculating a new two-dimensional attribute by multivariate statistical analysis from the extracted n-dimensional attribute information of a plurality of images,
Generating a two-dimensional metric space with the two-dimensional new attributes as x-axis and y-axis, respectively;
Based on the attribute value of the new attribute of each image, each image is regarded as a point on the two-dimensional metric space, and clustering is performed using multivariate statistical analysis. Dividing a set of images into m (m ≧ 2) subsets;
Dividing the two-dimensional metric space into m partial regions;
Based on the centroid coordinates of each of the subsets and the relative positional relationship between the centroids, the process of associating the partial areas with the subsets on a one-to-one basis;
A method for displaying a search image, comprising: displaying, on a display device, a reduced number of images included in a corresponding subset of the partial areas, and displaying a reduced number of the images. Search an image database that stores images with n-dimensional (n ≧ 3) attribute information expressed numerically, satisfying any given condition, and reduce the searched images A search image display program for causing a computer to execute a search image display method to be displayed on a display device,
A process of extracting n-dimensional attribute information from each of a plurality of retrieved images;
A process of calculating a new two-dimensional attribute by multivariate statistical analysis from the extracted n-dimensional attribute information;
A process of generating a two-dimensional metric space with the two-dimensional new attributes as x-axis and y-axis,
Processing for displaying each searched image on the display device by reducing and arranging the searched image at a position in the two-dimensional distance space corresponding to the attribute value of the new attribute of the image;
A search image display program to be executed by a computer. Search an image database that stores images with n-dimensional (n ≧ 3) attribute information expressed numerically, satisfying any given condition, and reduce the searched images A search image display program for causing a computer to execute a search image display method to be displayed on a display device,
A process of extracting n-dimensional attribute information from each of a plurality of retrieved images;
A process of calculating a new two-dimensional attribute by multivariate statistical analysis from the extracted n-dimensional attribute information of a plurality of images;
Processing for generating a two-dimensional metric space with the two-dimensional new attributes as x-axis and y-axis, respectively;
Based on the attribute value of the new attribute of each image, each image is regarded as a point on the two-dimensional metric space, and clustering is performed using multivariate statistical analysis. Dividing the image set into m subsets (m ≧ 2);
A process of dividing the two-dimensional metric space into m partial areas;
A process of associating each of the partial areas with each of the subsets on a one-to-one basis based on the centroid coordinates of each of the subsets and the relative positional relationship between the centroids;
For each of the partial areas, processing for displaying on the display device a reduced number of images included in the corresponding subset.
A search image display program to be executed by a computer.

Images