JP2013114597A - Information processing device, control method thereof, and program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To enable, upon receipt of a change, made by a user's manipulation, in position of an image displayed on a map, proper changing of weight on each feature value to be used for a search, thereby enabling searching of a similar image.SOLUTION: Arrangement information indicating a position displayed on a map is generated according to: an approximate degree between multiple feature values of a search image and multiple feature values of a search target image; and weight information indicating weight on the multiple feature values. Then, the search target image is displayed at a position indicated by the arrangement information generated. Further, in response to a user's operation, when a change in position of the search target image displayed on the map is accepted, weight information is generated according to the arrangement information of the search target image to which the change acceptance is made and the approximate degree calculated. Then, according to the approximate degree and the weight information generated, arrangement information of the search target image is generated again.

Description

  The present invention relates to an information processing apparatus, a control method thereof, and a program, and more particularly to an approximate image search technique.

  Search systems (called full-text search systems) based on keywords (character information) for searching document information on the Internet are already widely used, and the basic technology has been established and matured. It can be said that. On the other hand, for image information that is not character string information, the search method is not established as much as the full-text search system, and various methods are being studied.

  A currently popular technique is to perform a search using the same technique as a full-text search system based on character string information (called keywords or tags) attached to an image. In recent years, a mechanism for presenting an image (referred to as a query image) that is a source of an image to be searched for and searching for an image close to the query image has been provided. In this system, an image having a feature amount similar to the feature amount of the query image is searched.

  In general, in a search system using keywords, whether or not a document simply includes a search character string (query keyword) itself, a synonym, or a synonym can be used as an index of validity of a search result. On the other hand, in the case of a similar image search system that searches for similar images based on images, it is possible to determine that the query image and the image to be searched are similar based on what index (which feature amount of the image), Is difficult to determine uniquely.

  For example, when a user searches based on a photo A, the user may expect a photo showing a landscape similar to the landscape of A as a result. Another user may expect a photo that shows an object similar to an object (for example, a chair) in the photo based on the photo A. As described above, it is difficult to uniquely determine a result expected by the user from a certain query image, that is, to determine which feature of the query image should be used to determine similarity.

  In the image search system of Patent Document 1, a plurality of types can be used in combination as feature quantities used for search. When searching using a plurality of feature amounts, the user can specify the weights. Furthermore, in order to make it easy for the user to grasp the search result, the image that is the search result can be arranged and displayed in a three-dimensional manner. Each dimension is associated with the feature value used for the search.

JP-A-11-175556

However, in Patent Document 1, the user must explicitly specify the type of feature amount used for the search.
Therefore, the user not only has to recognize and specify the type of the feature quantity of the feature he or she pays attention to the query image, but also distributes (weights) each feature quantity used for the search. Also, the confirmation work and the designation were complicated. In addition, it is difficult to search for a similar image unless the type and weight of the feature amount are appropriately specified, and it is difficult for the user to search the image intuitively at a glance.

  Furthermore, in Patent Document 1, the number of feature quantities that can be used on the search result display screen is limited to three. Since this can be displayed only with a maximum of three axes of X, Y, and Z, the coordinate axes of feature amounts are limited to three.

  For this reason, the fourth or more feature quantities cannot be displayed on the display screen, and an image similar to the query image may be overlooked.

  Therefore, an object of the present invention is to accept a change in the position of an image displayed on a map by a user's operation, thereby appropriately changing the weight of each feature amount used for the search and searching for a similar image. It is to provide a mechanism to do.

  The present invention is an information processing apparatus that displays the search target image on a map indicating a relationship between a plurality of search target images that are target images to be searched based on the search image, and stores the plurality of search target images. Storage means, receiving means for receiving a search image input by a user, a plurality of feature amounts of the search image received by the receiving means, and a plurality of feature amounts of the search target image stored in the storage means According to the calculation means for calculating the degree of approximation, the degree of approximation calculated by the calculation means, and weight information indicating the weights for the plurality of feature amounts, the search target image whose degree of approximation is calculated by the calculation means Generating means for generating arrangement information indicating a position to be displayed on the map; and the search target image at a position on the map indicated by the arrangement information generated by the generating means. Display means for outputting to display, a change accepting means for accepting a change in the position of the search target image displayed on the map by the display means by a user operation, and a search accepting the change by the change accepting means Weight information generating means for generating weight information according to the arrangement information indicating the position of the target image and the degree of approximation calculated by the calculating means, and the generating means is further calculated by the calculating means According to the degree of approximation and the weight information generated by the weight information generating unit, the arrangement information of the search target image in which the degree of approximation is calculated by the calculating unit is generated.

  In addition, the present invention includes storage means for storing a plurality of search target images that are images to be searched based on the search image, and displays the search target images on a map indicating a relationship between the plurality of search target images. The information processing apparatus has a control method in which the reception unit of the information processing apparatus receives a search image input by a user, and the calculation unit of the information processing apparatus receives the search image received in the reception process. The calculation step of calculating the degree of approximation between each of the plurality of feature amounts and the plurality of feature amounts of the search target image stored in the storage unit, and the generation unit of the information processing apparatus are calculated by the calculation step. In accordance with the degree of approximation and the weight information indicating the weights for the plurality of feature quantities, the search target image whose degree of approximation is calculated by the calculation step is displayed on the map. And a display step in which the display unit of the information processing apparatus outputs the search target image to be displayed at a position on the map indicated by the arrangement information generated by the generation step. A change accepting unit for accepting a change in the position of the search target image displayed on the map in the display step by a user operation; and generating weight information for the information processing device. A weight information generating step for generating weight information according to arrangement information indicating the position of the search target image whose change has been received by the change receiving step and the degree of approximation calculated by the calculating step; The generation step further includes the calculation step according to the approximation degree calculated in the calculation step and the weight information generated in the weight information generation step. Similarity score, characterized in that to generate the arrangement information of the search target image calculated.

  In addition, the present invention includes storage means for storing a plurality of search target images that are images to be searched based on the search image, and displays the search target images on a map indicating a relationship between the plurality of search target images. An information processing apparatus that can be read and executed by the information processing apparatus, wherein the information processing apparatus receives a search image input by a user, a plurality of feature amounts of the search image received by the reception unit, and the storage unit According to the calculation means for calculating the degree of approximation with each of the plurality of feature amounts of the search target image stored in the image, the degree of approximation calculated by the calculation means, and weight information indicating a weight for the plurality of feature quantities, Generating means for generating arrangement information indicating a position at which the search target image whose degree of approximation has been calculated by the calculating means is displayed on the map; and Display means for outputting the search target image to be displayed at a position on the map indicated by the generated arrangement information, and the position of the search target image displayed on the map by the display means by a user operation. As a weight information generation unit that generates weight information according to a change reception unit that receives a change, arrangement information that indicates a position of a search target image that has received a change by the change reception unit, and the degree of approximation calculated by the calculation unit The generating means is further configured to search for the search target image whose degree of approximation has been calculated by the calculating means according to the degree of approximation calculated by the calculating means and the weight information generated by the weight information generating means. Arrangement information is generated.

  According to the present invention, by accepting a change in the position of an image displayed on a map by a user's operation, appropriately changing the weight of each feature amount used for the search, and searching for a similar image Is possible.

1 is a system configuration diagram showing an example of a configuration of an image search system of the present invention. It is a block diagram which shows the hardware constitutions of the information processing apparatus applicable to the user terminal 101 and the image search apparatus 102 shown in FIG. It is a figure showing the structure of the functional block of the user terminal 101 and the image search apparatus 102 which were shown in FIG. It is a figure showing the function block inside the feature-value extraction part 503 shown in FIG. It is a figure which shows an example of the feature-value table in the feature-value database 505 shown in FIG. It is a flowchart which shows an example of the registration procedure of the search object image in the image search system in this invention. It is a flowchart which shows the procedure of the search process in the image search system in this invention. It is a flowchart which shows the procedure of the update process of the search result in the image search system in this invention. It is a figure which shows an example of the display screen in the map display part 302 of the user terminal 101 of the search result in the image search system in this invention. It is a figure which shows an example of the display screen in the map display part 302 of the user terminal 101 of the search result in the image search system in this invention. It is a figure which shows an example of the display screen in the map display part 302 of the user terminal 101 of the search result in the image search system in this invention. It is a figure which shows an example of the type | formula which converts the approximation vector of the similar image in the image search system in this invention into a coordinate vector. It is a figure which shows an example of the type | formula for calculating | requiring a conversion matrix based on the coordinate vector of the similar image in the image search system in this invention. It is a figure which shows an example of the type | formula for calculating | requiring a conversion matrix based on the coordinate vector of the similar image in the image search system in this invention. 1 is a system configuration diagram showing an example of a configuration of an image search system of the present invention.

<First Embodiment>
FIG. 1 is a system configuration diagram showing an example of the configuration of the image search system of the present invention.

  FIG. 1 shows a configuration in which one or a plurality of user terminals 101 and an image search apparatus 102 are connected to each other via a local area network (LAN) 103 so that they can communicate with each other.

  The user terminal 101 is an information processing apparatus used by a user who searches for an image, and has a function of transmitting a search request and a function of receiving and displaying a search result.

  The image search apparatus 102 stores a plurality of images to be searched, and has a function of receiving a search request from the user terminal 101, performing an image search process, and responding to a search result. In addition, a means for inputting an image to be searched from outside is provided. The image search apparatus 102 is an application example of the information processing apparatus of the present invention.

  Hereinafter, the hardware configuration of the information processing apparatus applicable to the user terminal 101 and the image search apparatus 102 illustrated in FIG. 1 will be described with reference to FIG.

  FIG. 2 is a block diagram illustrating a hardware configuration of an information processing apparatus applicable to the user terminal 101 and the image search apparatus 102 illustrated in FIG.

  In FIG. 2, reference numeral 201 denotes a CPU that controls the entire information processing apparatus using programs and data stored in a RAM 202 and a ROM 203, and executes each process described later performed by the information processing apparatus.

  A RAM 202 includes an area for temporarily storing programs and data loaded from the HDD 204 and the recording medium drive 206, and data received via the network I / F (interface) 205, and the CPU 201 has various types of data. It is provided with a word query used for executing the process.

  A ROM 203 stores setting data, a boot program, and the like of the information processing apparatus.

  Reference numeral 204 denotes an HDD, which stores an OS (operating system) and programs and data for causing the CPU 201 to execute each process described later performed by the information processing apparatus. Some or all of these programs and data are loaded into the RAM 202 in accordance with the control of the CPU 201, and the CPU 201 performs processing using this, whereby the information processing apparatus executes each processing described below.

  Reference numeral 205 denotes a network I / F for connecting the information processing apparatus to the network 103, and the information processing apparatus can perform data communication with an external device via the network I / F 205.

  Reference numeral 206 denotes a recording medium drive, which reads out programs and data recorded on a storage medium such as a CD-ROM, CD-R / RW, DVD-ROM, DVD-R / RW, and DVD-RAM and outputs them to the RAM 202. This reading operation is controlled by the CPU 201.

  A keyboard 207 can input various instructions to the CPU 201. A pointing device 208 such as a mouse can input various instructions to the CPU 201.

  Reference numeral 209 denotes a video I / F (interface) which functions as an I / F for supplying an image to be displayed on the display device 210 to the display device 210 as a signal.

  A display device 210 includes a CRT, a liquid crystal screen, and the like, and can display a processing result by the CPU 201 using an image, characters, or the like.

  Reference numeral 211 denotes a peripheral device I / F, which includes a USB port, an IEEE1394 port, and the like, and can be connected to the peripheral device via the peripheral device I / F 211. The connection form with the peripheral device may be wired or wireless. A bus 212 connects the above-described units.

  Next, the functional block configuration of the image search system of the present invention will be described with reference to FIG.

  The image search system includes a user terminal 101, an image search device 102, and an image source 600. The user terminal 101, the image search device 102, and the image source 600 are connected to each other via a network so that they can communicate with each other.

  The user terminal 101 is an information processing device for sending an image search request to the image search device 102 and receiving and displaying the search result. The user terminal 101 includes a search query unit 301, a map display unit 302, and an arrangement instruction unit 303.

  The search query unit 301 includes an input unit that receives a query image as a search request from a user. The search query unit 301 is a function processing unit that includes a unit that transmits the query image to the search processing unit 503 of the image search apparatus 102 via the network. is there.

  The map display unit 302 is a function processing unit having means for receiving a search result returned from the image search apparatus 102 and means for displaying the search result. Examples of display screens are shown in FIGS.

  The arrangement instructing unit 303 collects the change information when the user changes the arrangement of similar images on the coordinate plane displayed as a search result on the map display unit 302 by using a device such as a mouse. , A function processing unit having means for transmitting the change information to the transformation matrix calculation unit 507 of the image search apparatus 102.

  The image search apparatus 102 receives an image search request from the user terminal 101, executes the requested search process on the stored image, and transmits search result information to the user terminal 101. It is. The image search device 102 includes an image registration unit 501, a feature amount extraction unit 502, a search processing unit 503, a feature amount approximation degree calculation unit 504, a dimension compression unit 505, a map generation unit 506, and a transformation matrix calculation unit. 507, an image database 508, and a feature amount database 509.

  The image registration unit 501 is a function processing unit that registers an image to be searched into the system. Image data to be searched is received or acquired from an actor outside the system specified by the image source 600, the feature amount of the image data is stored in the feature amount database 509, and the image data itself is stored in the image database 508. Has the function of saving.

  The feature amount extraction unit 502 is a function processing unit that receives image data as input and extracts various feature amounts of the image data. FIG. 4 is a diagram illustrating an example of functional blocks inside the feature amount extraction unit 502. As shown in FIG. 4, the feature quantity extraction unit 502 includes a plurality of feature quantity extraction units. The feature amount extraction units indicated by 5021 to 5024 in FIG. 4 are function processing units that extract different types of image feature amounts. For example, scalable color feature quantities (feature quantities representing the color distribution state in the entire image), color layout feature quantities (feature quantities representing the color distribution state for each area of the image), edge histogram feature quantities (boundary lines in the image) For example, it is possible to apply an implementation for extracting feature amounts such as a feature amount (SIFT) and a scale inverse feature transform (SIFT) feature amount (a feature amount representing a density change feature of a local region). The number of individual feature amount extraction units is four in FIG. 4, but is not particularly limited, and may be implemented by the number of image feature amounts to be used.

  That is, as the feature amount of the image, for example, a statistic regarding a color (consisting of hue, saturation, brightness, etc.), a pattern (texture), a local area density change feature, a shape of an imaged object, Since there are various types such as the shooting date and time, the shooting location, etc., the feature amount extraction unit 502 can also be implemented so as to extract such various feature amounts.

  The search processing unit 503 accepts a query image as a search request, instructs the feature amount extraction unit 502 to perform feature amount extraction processing of the image data, and passes the feature amount information received as a result to the feature amount approximation degree calculation unit 504. The function processing unit instructs the calculation of the approximation vector with the accumulated image, passes the approximation vector data to the dimension compression unit 505, and instructs the generation of the position vector group.

  The feature amount approximation degree calculation unit 504 receives a plurality of types of image feature amounts related to an image from the search processing unit 503, compares the image feature amounts with the feature amounts stored in the feature amount database 509, and compares them. Is a function processing unit that calculates the degree of approximation and generates an approximation vector.

  The dimension compression unit 505 can receive the approximation vector data of the image group as a search result from the search processing unit 503, apply principal component analysis to the data, and can express the data (approximation vector) by the map generation unit 506 This is a function processing unit that generates a position vector (placement information) that has been reduced in dimension to a smaller number of dimensions.

  The map generation unit 506 receives the arrangement information of the image group as the search result, generates image information (search result map information) that is arranged on the two-dimensional coordinate plane and visualized, and displays the map on the user terminal 101. This is a function processing unit that transmits to the unit 302.

  That is, the image search apparatus 102 maps the query image (search image) and the approximate relationship of a plurality of search target images, which are target images searched based on the query image (search image) (FIGS. 9 and 10). FIG. 11) The search target image is displayed on (search result map information).

  The transformation matrix calculation unit 507 receives change information (location change information) of image arrangement information from the arrangement instruction unit 303 of the user terminal 101, and converts a transformation matrix (position vector from the approximation vector) that reflects the arrangement change information. It is a function processing unit that calculates a function to be calculated.

  The image database 508 is a storage area for storing a group of image data (search target images) to be searched. The stored image data has means that can be directly accessed by an ID (identifier). The image database 508 is an application example of a storage unit that stores a plurality of search target images.

  The feature amount database 509 is a storage area for storing various feature amount data (FIG. 5) of image data to be searched. The feature amount data is managed in the table illustrated in FIG.

  In the table of FIG. 5, one row represents one image data stored in the image database 508, and is indicated by a column name from feature amount A to feature amount D together with an image data ID (identifier) (also referred to as image NO). In this column, each feature amount data of the image is stored.

  The image source 600 is an external actor that represents the source (input source) of the search target image in the image search system. For example, a site having a photo sharing function such as Flickr and Facebook on the Internet, a user who directly provides photo data, and video input devices such as various cameras and scanners are also conceivable.

  Next, processing for registering image data to be searched for in the image search system will be described with reference to FIG.

  Each step shown in FIG. 6 is executed by the CPU 201 of the image search apparatus 102.

  The image source 600 (external device) described below can be of various types as described above. Here, an example in which an administrator terminal operated by a system administrator is used will be described.

  In step S601, the image registration unit 501 receives image data to be searched from an administrator terminal operated by a system administrator represented by the image source 600.

  In step S <b> 602, the image registration unit 501 inputs the received image data to the feature amount extraction unit 502. The feature quantity extraction unit 502 analyzes the image data, and calculates the feature quantities A to D of the image data through the individual feature quantity extraction units exemplified by 5021 to 5024 in FIG. Usually, these feature quantities are expressed as a one-dimensional numerical vector. The feature amount extraction unit 502 inputs the extracted feature amount data (four from A to D) to the image registration unit 501.

  In step S603, the image registration unit 501 registers the feature amount data acquired in step S602 in the feature amount database 509. The feature amount data is stored in a table structure as illustrated in FIG.

  A table structure (feature amount database 509) for storing feature amount data will be described with reference to FIG.

  As already described, a plurality of types of feature amounts are extracted for a certain image. Various feature quantities are expressed as numerical (integer or floating point) multidimensional vectors. For example, a SIFT feature value, which is one of the local feature values, is expressed as a floating-point 128-dimensional vector. In the image search system described in this embodiment, four types of image feature amounts from feature amount A to feature amount D are acquired as shown in FIG. In the table of FIG. 5, one row stores feature amount data related to one search target image. Each feature amount data is stored in each column whose column names are feature amount A to feature amount D. Each feature quantity is basically stored as numeric multidimensional vector data, although the number of dimensions and the type of numeric value differ depending on the type of feature quantity.

  In step S <b> 604, the image registration unit 501 stores the received image data in the image database 508.

  This completes the image registration process.

  Next, a processing flow in image search will be described with reference to FIG.

  In step S <b> 701, the search processing unit 503 receives a query image transmitted from the search query unit 301 of the user terminal 101.

  That is, in step S701, an input of a query image (search image) is received by an operation by a user (user) who operates the user terminal 101 (accepting means). Here, the query image itself may be received from the user terminal 101 and input may be received, or input of a query image selected by the user as a query image from an image stored in the image database 508 may be received. Good.

  In step S702, the search processing unit 503 analyzes the query image data, inputs the query image data to the feature amount extraction unit 502, and acquires feature amount data (four feature amount vectors in this embodiment) of the image.

  In step S <b> 703, the search processing unit 503 inputs the feature amount data acquired in step S <b> 702 to the feature amount approximation degree calculation unit 504. The feature amount approximation degree calculation unit 504 compares the received feature amount data with all the feature amount data groups stored in the feature amount database 509, and calculates the degree of approximation of each. The degree of approximation related to one feature amount is expressed by, for example, a Eugrid distance between numerical vectors. The degree of approximation of the query image with respect to one search target image is expressed as an array of Eugrid distances for each feature quantity type (A to D in this embodiment), that is, a multidimensional numerical vector. The feature amount approximation degree calculation unit 504 generates a multidimensional numerical vector (hereinafter referred to as an approximation degree vector) representing the degree of approximation with the query image for all the search target images, and the search processing unit 503 uses the approximation degree vector group. To respond.

  That is, in step S703, the degree of approximation between the plurality of feature amounts of the query image received in step S701 and the plurality of feature amounts of each image stored in the image database 508 is calculated (calculation means).

  In step S704, the search processing unit 503 inputs the approximation vector group acquired in step S703 to the dimension compression unit 505. The dimension compression unit 505 performs principal component analysis processing on the approximation vector group, and compresses each dimension of the approximation vector group into two dimensions. Hereinafter, the two-dimensional approximation vector is referred to as arrangement information.

  That is, in step S704, each degree of approximation calculated in step S703 is substituted for 1203 in FIG. 12, and is calculated with the transformation matrix 1202 (initial value) in FIG. 12, thereby calculating and generating arrangement information 1201. Here, the transformation matrix 1202 in FIG. 12 is an application example of the weight information in the present invention, and is information that combines the approximations of the plurality of types of feature values and indicates the weights for the plurality of types of feature values. Further, the arrangement information generated here is information indicating a position at which the search target image in which each calculated degree of approximation is calculated is displayed on the map.

  As described above, in step S704, arrangement information indicating positions to be displayed on a map having a smaller number of dimensions than the plurality of types of feature quantities is synthesized by combining the degrees of approximation of the calculated types of feature quantities. Generate.

(Dimensional compression means)
FIG. 12 shows a vector conversion formula for performing the dimensional compression. A vector indicated by 1203 represents an approximation vector between the query image and the search target image. The values of F0, F1, F2, and F3 represent the distance (difference) between the query image and the search target image regarding the feature amount A to the feature amount D, respectively. The matrix indicated by 1202 is calculated in the above principal component analysis process, and represents a transformation matrix (dimensional compression function). The value of the first row (T00, T01, T02, T03) of this transformation matrix represents the first principal component, and the value of the second row (T10, T11, T12, T13) represents the second principal component. A vector indicated by 1201 represents arrangement information (position vector) obtained by two-dimensionalizing the approximation vector. Both X and Y values of 1201 are a linear combination of the distances of a plurality of image feature amounts (F0 to F3 in this embodiment).

  A set of search target images with high similarity (images close to the origin in the approximation vector space) by two-dimensionalizing multidimensional numerical vector data (approximation vector) consisting of approximations of a plurality of feature quantities by principal component analysis The set) can be visualized in an arrangement in which those features are efficiently expressed (in an expression reduced in dimension so that the amount of information is not reduced as much as possible). Each component of the two-dimensional data represents a value obtained by combining the approximations of various feature amounts, but each component is a scale representing a similarity expression independent of each other.

  In step S <b> 705, the dimension compression unit 505 inputs the arrangement information group calculated in step S <b> 704 to the map generation unit 506. The map generation unit 506 targets the arrangement information within a certain range from the origin in the arrangement information group, and displays a thumbnail image of the image corresponding to the arrangement information (similar image thumbnail) on the two-dimensional coordinate plane. Create arranged visualization information (also called map). This visualization information is illustrated in the area indicated by 900 in FIG. Hereinafter, this visualization information is called a similar image map, and an image displayed on a two-dimensional coordinate plane is called a similar image.

  In step S705, only the arrangement information search target image indicating the position within the predetermined range on the map is arranged on the map. Therefore, in step S706, the arrangement information search target indicating the position within the predetermined range on the map. Output only the image to be displayed on the map.

  In step S <b> 706, the map generation unit 506 transmits the generated similar image map to the map display unit 302 of the user terminal 101.

  That is, in step S706, the search target image is output to be displayed at a position on a similar image map (also simply referred to as a map) indicated by the generated arrangement information.

  The processing from when the user sends a search request to when the search result is responded has been described above.

  Next, a flow of processing for improving a search result according to a user instruction will be described with reference to FIG.

  In step S801, the map display unit 302 of the user terminal 101 receives the similar image map transmitted from the map generation unit 506 in S706.

  In step S <b> 802, the similar image map is displayed on the map display unit 302.

(Explanation of FIG. 9)
FIG. 9 is a screen example of the map display unit 302 displaying a similar image map. A similar image map is displayed in the area indicated by 900. The similar image map is obtained by arranging thumbnails of images (similar images) calculated to be similar to the query image on a two-dimensional coordinate plane. The object indicated by 901 represents a thumbnail of the query image, and is arranged at the origin of the coordinate plane. The objects designated in steps 904 to 909 represent thumbnails of similar images, and are displayed at the coordinates of the arrangement information calculated in step S704.

  Since the similar image is arranged at a distance (difference) between various feature amounts of the query image and each similar image into a two-dimensional coordinate, a similar image having a higher similarity to the query image is arranged closer to the origin. The

  Reference numeral 902 denotes a button for sending update information including the update contents to the image search apparatus 102 when the user changes the position of the similar image by dragging or the like. Reference numeral 903 denotes a button for notifying the image search apparatus 102 that there is no room for further change regarding the arrangement of similar images.

(About changing the arrangement of similar images)
After step S802, the user visually recognizes the similar image map displayed on the map display unit 302 of the user terminal 101, and compares the thumbnail as indicated by 904 to 909 with the thumbnail of the query image 901. The thumbnail placement location is changed by dragging with the mouse.

  That is, a search that is determined to be similar by performing an operation such as the user dragging the location of the thumbnail of the search target image that the user has determined to be similar to the thumbnail of the query image 901 with the mouse. Change the location of thumbnails for the target image. Specifically, the location of the thumbnails of the search target images that are determined to be similar is approximated so as to be close to the center of the map (the origin of the two coordinate axes where the thumbnails of the query image are arranged). Move the distance according to the degree of judgment. On the other hand, the degree of determination that the location of the thumbnail of the search target image that is determined not to be similar is not approximated so as to be away from the center of the map (the origin of the two coordinate axes where the thumbnail of the query image is positioned). Move according to the distance.

  Thus, the user terminal 101 receives a change in the position of the search target image displayed on the map by a user operation (change receiving unit).

  As described above, each axis of the thumbnail arrangement represents a linearly synthesized value of the distance component related to each feature amount. The initial values of the linear synthesis parameters (conversion matrix 1202 in FIG. 12) are derived by principal component analysis, and are determined so as not to reduce the amount of information as much as possible during dimension compression. That is, the approximation vectors calculated in step S703 (in this embodiment, the feature quantity A, feature quantity B, feature quantity C, and feature quantity D extracted in the respective units 5021, 5022, 5023, and 5024) Principal component analysis is performed on the approximation vectors), and each approximation vector (four approximation vectors in the present embodiment) is combined into two components (dimensions) to form a transformation matrix 1202 (initial value) in FIG. Is calculated and generated. Here, in dimension compression to two dimensions by principal component analysis, two components (dimensions) are selected so as not to reduce the information amount of the approximation vector group as much as possible.

  For similar image groups on the coordinate system determined in this way, the user adjusts the position in consideration of their relative positional relationship and the distance from the origin. As a result, it is considered that the parameters of the linear synthesis approach the weights of various feature amounts that the user expects from the similarity of images.

  With regard to the arrangement changing means, in order to make it easier for the user to check each similar image, there may be a device such that when a thumbnail from 904 to 909 is clicked, a larger size image is displayed on the spot.

  An example of the map display unit 302 in which the thumbnail arrangement position is updated is shown in FIG.

  In FIG. 10, the user moves the image B from the location (arrangement position) indicated by 905 to the location (arrangement position) indicated by 910, and the image C from the location (arrangement position) indicated by 906. Move to the location (arrangement position) indicated by 911, move the image E from the location (arrangement position) indicated by 908 to the location (arrangement position) indicated by 912, and instruct the image F by 909. This indicates that the user has moved from the place (arrangement position) to the place (arrangement position) indicated by 913.

  In step S803, if the map display unit 302 detects that the no-update button 903 designated by the user in 903 has been pressed, the process ends. If the map display unit 302 detects that the update button 902 indicated by 902 is pressed, the process proceeds to step S804.

  In step S804, the arrangement instruction unit 303 stores change information (arrangement change information) indicating the position of the thumbnail image changed in the map display unit 302 in the RAM instructed in 203. In the above example, new position information of the image B, the image C, the image E, and the image F is stored in the RAM 202 as position vector data.

  In step S805, the arrangement instruction unit 303 transmits the plurality of position vector data (arrangement change information) stored in step S804 to the transformation matrix calculation unit 507 of the image search apparatus 102.

  In step S806, the transformation matrix calculation unit 507 of the image search apparatus 102 receives the position vector data (arrangement change information) transmitted in step S805.

  In other words, the image search device 102 receives the arrangement change information as the content in which the position of the search target image displayed on the map has been changed by a user operation. The arrangement change information is arrangement information indicating the position of the changed search target image.

(Calculation of transformation matrix from location update information)
In step S807, the transformation matrix calculation unit 507 inputs position vector data (placement change information) and calculates a dimensional compression matrix. This is a process for obtaining the transformation matrix indicated by 1202 in FIG. 12 that came out when the process of step S704 was described, based on the position vector 1201 and the approximation vector 1203. For example, when there are four position vector data, the relationship between them and the new transformation matrix T ′ is expressed by the equation of FIG. This is an expression in which four conversion information of the arrangement information are combined into one.

  In FIG. 13, portions 1301 to 1304 represent arrangement information (position vector data) of similar images each moved by the user. Further, portions 1305 to 1308 represent approximation vectors (values generated in step S703) of the images corresponding to 1301 to 1304 with the query image. For example, the part indicated by 1301 represents data (placement information (position vector)) of the new position (910) of the image B moved by the user in FIG. 10, and the part indicated by 1305 at that time is 1301. The approximation vector of the corresponding image B is represented. Similarly, reference numerals 1302 to 1304 and 1305 to 1308 respectively represent new position vector data and image approximation vector data corresponding to the new position vector data.

  By transforming this equation and solving for T ′, the transformation matrix T ′ can be calculated. 13 is multiplied from the right of both sides of the equation of FIG. 13 by the inverse matrix of the matrix indicated by 1310 to be transformed into the equation represented in FIG. 14, and T ′ is calculated. In this case, the position vector data 1301 to 1304 do not necessarily have to be the images whose positions have been changed by the user. In addition to the image whose position has been changed, the position vector data of an image indicating that the user attaches importance to the position of the image whose position has not been changed may be used in this expression.

  T ′ calculated as described above is expressed as a feature amount weighting matrix in which the feature amount is weighted in calculating the similarity between the query image and the search target image group. It has become.

  As described above, in step S807, a transformation matrix (weight information) is generated according to the arrangement information indicating the changed position of the search target image and the degree of approximation calculated in step S703 (weight information generation unit).

  In step S808, the transformation matrix generation unit 507 applies the transformation matrix generated in step S807 to each of the approximation vector groups generated in step S703 using the equation shown in FIG. Each position vector group (placement information) is generated.

  That is, in step S808, according to the degree of approximation calculated in step S703 and the transformation matrix generated in step S807, arrangement information of the search target image whose degree of approximation is calculated is generated.

  Specifically, the approximation vector calculated in step S703 is calculated by comparing the feature amount data of the query image with all the feature amount data groups stored in the feature amount database 509, respectively. Each of these approximation vectors is assigned to 1203, and the transformation matrix generated in step S807 is assigned to 1202, and new arrangement information (positions) for all the images stored in the image database 508 is obtained. Vector) 1201 is calculated.

  This new position vector represents the degree of similarity of each search target image expected by the user more accurately in the two-dimensional coordinate space.

  That is, here, arrangement information including a value indicating how much weight is assigned to which feature amount is generated by the user's operation (instruction to change the arrangement position of the image).

  In step S809, the transformation matrix generation unit 507 inputs the arrangement information of each search target image calculated in step S808 to the map generation unit 506. The map generation unit 506 creates a new similar image map in which thumbnail images of these images are arranged on a two-dimensional coordinate plane for images within a certain distance from the origin.

(Description of updated similar image map)
The updated search result will be described using the similar image map illustrated in FIG. As shown in FIG. 10, the images with changed locations are B, C, E, and F. Regarding these four images, they are arranged at positions close to the places almost changed in FIG. However, the image E has been moved out of the region. Further, an image that is not taken into account when calculating the transformation matrix, for example, the image A, is not displayed in the area in FIG. This means that the position after applying the new transformation matrix to the approximation vector of the image A does not appear within a certain distance from the origin. Further, the image D is closer to the origin than the position at the time of FIG. Furthermore, on the coordinate plane of FIG. 11, new images G and H appear in the region. In both cases, the result of having been determined to be closer to the query image as a result of changing the weight to the degree of approximation for each feature amount by the new transformation matrix is shown.

  When the transformation matrix is calculated using the inverse matrix as described in S807 above, the new position used for the calculation is calculated so as to exactly match the changed position, but it is not always necessary to do so. Different methods may be used, such as trialing a new parameter a plurality of times using a random number or the like, and selecting a parameter in which a plurality of position changes are realized in the most balanced manner. FIG. 11 shows the result when calculated by such a calculation.

  In step S810, the map generation unit 506 transmits the similar image map to the map display unit 302 of the user terminal 101.

  After step S810, the user terminal 101 continues to the process of step S801.

  As described above with reference to FIG. 8, the characteristics expected by the user by repeatedly changing the position of the similar image displayed on the two-dimensional coordinate plane so that the user reflects his intention. It is possible to acquire an image similar to the query image provided with

  In this way, once the arrangement position of the image displayed on the map is changed, it is possible to search for similar images by narrowing down the images stored in the image database 508.

  As described above, according to the procedure described with reference to FIG. 8, the parameters (when the similarities of various feature amounts are combined by updating the similarity of each search target image visually represented by a user instruction ( Conversion matrix), and the user can generate an approximation expression that the user expects more.

  That is, as described above, the location of the thumbnails of the search target images that are determined to be similar is approximated so as to be close to the center of the map (the origin of the two coordinate axes where the thumbnails of the query image are arranged). The position of the thumbnail of the search target image that is determined not to be similar is moved to the center of the map (the two coordinate axes where the query image thumbnail is placed). Move away from the origin) by a distance corresponding to the degree of judgment that is not approximate, and perform the search again, so that the query is changed according to the arrangement location (arrangement position) of the thumbnail of the moved search target image. Automatically determine which feature of the image should be used to determine similarity, and automatically weight each feature value (transformation matrix) to reflect the determination result Optimized, to search for similar images, it is possible to reduce a complicated operation.

<Second Embodiment>
A second embodiment of the present invention will be described.

  FIG. 15 is a functional block diagram of the image search system according to the second embodiment. FIG. 15 is obtained by adding a transformation matrix accumulating unit designated by 510 to the configuration of the first embodiment shown in FIG.

  The transformation matrix accumulation unit 510 is a storage unit that stores various feature amount data of the query image and the transformation matrix value in pairs.

  The transformation matrix accumulation unit 510 is an application example of the information storage means of the present invention. That is, the transformation matrix accumulation unit 510 is a storage unit that stores the transformation matrix (weight information) generated in step S807 and the plurality of feature amounts of the search image received in step S701 in association with each other.

  In the second embodiment, only processing different from the first embodiment will be described below. That is, in the second embodiment, the description of the same configuration as in the first embodiment is omitted.

(Query image feature data and transformation matrix storage processing)
In step S803 in the flowchart of FIG. 8, when there is an instruction not to be updated from the user, the arrangement instruction unit 303 notifies the conversion matrix calculation unit 507 of the image search apparatus 102 that the conversion matrix has been determined, and the conversion matrix. The calculation unit 507 stores the various feature amount data of the query image and the data of the transformation matrix finally calculated in step S807 in the transformation matrix storage unit 510.

(Calculation of initial value of transformation matrix)
In the second embodiment, in step S704 of the flowchart of FIG. 7, the process of obtaining the transformation matrix by the principal component analysis in the first embodiment is performed using the transformation matrix stored in the transformation matrix accumulation unit 510 described above. Change to use the value.

  Specifically, the dimension compression unit 505 searches the transformation matrix storage unit 510 for an entry having a feature amount data set that is closest to the various feature amount data sets (each feature amount) of the query image. The arrangement information is generated using the data.

  That is, in step S704, the transformation matrix stored in the transformation matrix accumulating unit 510 in association with a plurality of feature amounts most similar (approximate) to the plurality of feature amounts acquired from the search image newly received in step S701. (Weight information) is identified (identifying means). The transformation matrix accumulation unit 510 finally calculates various feature amount data of the previous (past) query image used in the previous (past) search and the previous (past) step S807. Therefore, when a new query image (search image) is received in step S701, it is most similar (approximate to the plurality of feature amounts acquired from the search image). ) To identify the transformation matrix (weight information) stored in the transformation matrix storage unit 510 in association with a plurality of feature quantities.

  Then, by substituting the degree of approximation calculated in step S703 and the specified weight information into 1203 and 1202 in FIG. 12, respectively, arrangement information indicating the position where the search target image is displayed on the map is generated. (Step S704).

However, if there is no entry within a certain distance with respect to the various feature data sets of the query image, the transformation matrix is calculated by principal component analysis as in the first embodiment.
That is, according to the arrangement information generated in step S704, it is determined whether there is a predetermined number of search target images within a predetermined range on the map (image number determination means). By substituting the degree of approximation calculated in step S703 and the transformation matrix specified in step S704 into 1203 and 1202 in FIG. 12, respectively, arrangement information indicating the position where the search target image is displayed on the map is generated. .

  On the other hand, if it is determined that there is no predetermined number of search target images within a predetermined range on the map, the degree of approximation calculated in step S703 and the conversion of the initial value are converted as described in the first embodiment. Arrangement information is generated by substituting the matrix (weight information) into 1203 and 1202 in FIG.

  Here, as described above, the initial value conversion matrix (weight information) is a conversion matrix obtained by performing principal component analysis, and according to the degree of approximation of the plurality of feature amounts calculated in step S703, A transformation matrix (weight information) indicating weights for a plurality of feature quantities is determined (decision means).

  By making the above changes, if a query image having a similar feature amount has been searched in the past, the transformation matrix created at that time can be reused to burden the user to change the layout. Can be omitted, and a similar image can be found efficiently.

  That is, it is possible to find a similar image efficiently and quickly by learning the feature amount of the query image and a transformation matrix suitable for searching for an image similar to the query image.

<Third Embodiment>
In the first embodiment and the second embodiment, the user terminal 101 and the image search device 102 are described in separate housings, but they are combined to form a single information processing device. It is possible. That is, a search query unit 301, an arrangement instruction unit 303, and a map display unit 302 included in a user terminal 101 to be described later are included in the image search device 102, and the image search device 102 is configured as one information processing device. can do.

  As described above, according to the present invention, by accepting a change in the position of an image displayed on a map by a user's operation, the weight of each feature amount used for the search is appropriately changed to search for a similar image. It becomes possible to do.

  Further, according to the present invention, the user can confirm the searched image without explicitly specifying the feature amount used for the search, and intuitively move the position of the image. Since the weight of the feature amount is automatically optimized and a similar image is searched, it is possible to reduce complicated operations.

  In addition, according to the present invention, the feature quantity used for the result display is not limited to three, and coordinate axes (including a plurality of feature quantity weights) that take into consideration the fourth or more feature quantities are also included. Since the image obtained as a result of the search is displayed on the map including the two-dimensional coordinate axis), the possibility of overlooking an image similar to the query image can be reduced.

  Further, according to the present invention, the weight of each index is automatically set through the interaction with the user without the user explicitly specifying the similarity index, and even when a plurality of indices are used. It is to provide an image search mechanism that can be optimized.

  Further, according to the present invention, it is possible to quickly and efficiently search for and find an image having features desired by a user from a large number of images.

  The embodiment of the present invention has been described in detail above. However, the present invention can take an embodiment as a system, an apparatus, a method, a program that can be read and executed by the apparatus, a storage medium, or the like. In addition, the present invention may be applied to a system composed of a plurality of devices, or may be applied to an apparatus composed of a single device. In the above-described embodiments, the user terminal 101 and the image search device 102 have been described as separate cases. However, the user terminal 101 and the image search device 102 may be combined into one information processing device. it can. That is, it goes without saying that even when the information processing apparatus is combined with the user terminal 101 and the image search apparatus 102 as described above, it is within the scope of the present invention.

  Another object of the present invention is to supply a storage medium storing software program codes for realizing the functions of the above-described embodiments to a system or apparatus, and the computer (or CPU or MPU) of the system or apparatus stores the storage medium. Needless to say, this can also be achieved by reading and executing the program code stored in.

  In this case, the program code itself read from the storage medium realizes the functions of the above-described embodiments, and the program code itself and the storage medium storing the program code constitute the present invention.

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

  Further, by executing the program code read by the computer, not only the functions of the above-described embodiments are realized, but also an OS (basic system or operating system) running on the computer based on the instruction of the program code. Needless to say, a case where the function of the above-described embodiment is realized by performing part or all of the actual processing and the processing is included.

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

101 User terminal 102 Image search device 103 LAN
301 Search Query Unit 302 Map Display Unit 303 Arrangement Instruction Unit 501 Image Registration Unit 502 Feature Amount Extraction Unit 503 Search Processing Unit 504 Feature Amount Approximation Calculation Unit 505 Dimensional Compression Unit 506 Map Generation Unit 507 Transformation Matrix Calculation Unit 508 Image Database 509 Feature Quantity database 510 Transformation matrix storage 600 Image source

Claims (8)

An information processing apparatus that displays the search target image on a map indicating a relationship between a plurality of search target images that are target images to be searched based on the search image,
Storage means for storing the plurality of search target images;
Accepting means for accepting input of a search image by a user;
Calculating means for calculating a degree of approximation between a plurality of feature amounts of the search image received by the receiving means and a plurality of feature amounts of the search target image stored in the storage unit;
Arrangement indicating a position at which the search target image whose degree of approximation is calculated by the calculating unit is displayed on the map according to the degree of approximation calculated by the calculating unit and weight information indicating weights for the plurality of feature amounts Generating means for generating information;
Display means for outputting the search target image to be displayed at a position on the map indicated by the arrangement information generated by the generation means;
Change accepting means for accepting a change in the position of the search target image displayed on the map by the display means by a user operation;
Weight information generating means for generating weight information according to the arrangement information indicating the position of the search target image whose change has been received by the change receiving means and the degree of approximation calculated by the calculating means;
With
The generation means further includes, based on the approximation degree calculated by the calculation means and the weight information generated by the weight information generation means, the arrangement information of the search target image whose approximation degree is calculated by the calculation means. An information processing apparatus that generates the information processing apparatus. The calculating means calculates the approximate degree of the plurality of types of feature quantities of the search image received by the receiving means and the plurality of types of feature quantities of the search target image stored in the storage means,
The generating unit synthesizes each degree of approximation in the plurality of types of feature quantities and, according to weight information indicating weights for the plurality of types of feature quantities, each degree of approximation in the plurality of types of feature quantities calculated by the calculation unit. The information processing apparatus according to claim 1, wherein arrangement information indicating positions to be displayed on the map having a smaller number of dimensions than the plurality of feature amount types is generated. Information storage means for storing the weight information generated by the weight information generation means in association with a plurality of feature amounts of the search image received by the reception means;
A specifying unit that specifies weight information stored in the information storage unit in association with a plurality of feature amounts similar to the plurality of feature amounts of the newly received search image received by the receiving unit;
Further comprising
The generation means is a position for displaying, on the map, a search target image whose approximation degree is calculated by the calculation means according to the approximation degree calculated by the calculation means and the weight information specified by the specifying means. The information processing apparatus according to claim 1, wherein arrangement information indicating the information is generated.   4. The display device according to claim 1, wherein the display unit outputs only a search target image of arrangement information indicating a position within a predetermined range on the map so as to be displayed on the map. 5. The information processing apparatus described. According to the arrangement information generated by the generation means, further comprising an image number determination means for determining whether or not there is a predetermined number of search target images within a predetermined range on the map,
When the image number determination unit determines that there are a predetermined number of search target images within a predetermined range on the map, the generation unit determines the degree of approximation calculated by the calculation unit and the identification 4. The arrangement information according to claim 3, wherein arrangement information indicating a position at which the search target image whose degree of approximation is calculated by the calculation unit is displayed on the map is generated according to the weight information specified by the unit. Information processing device. A determination unit configured to determine weight information indicating a weight for the plurality of feature amounts according to the degree of approximation of the plurality of feature amounts calculated by the calculation unit;
When the image number determination unit determines that there is no predetermined number of search target images within a predetermined range on the map, the generation unit determines the degree of approximation calculated by the calculation unit and the determination 6. The arrangement information according to claim 5, wherein, according to the weight information determined by the means, arrangement information indicating a position where the search target image whose degree of approximation is calculated is displayed on the map is generated. Information processing device. Control in an information processing apparatus that includes a storage unit that stores a plurality of search target images that are images to be searched based on the search image, and displays the search target images on a map that indicates a relationship between the plurality of search target images. A method,
A receiving step in which a receiving unit of the information processing apparatus receives an input of a search image by a user;
A calculation step in which the calculation unit of the information processing apparatus calculates the degree of approximation between the plurality of feature amounts of the search image received in the reception step and the plurality of feature amounts of the search target image stored in the storage unit, respectively. When,
The generation unit of the information processing apparatus uses the approximation degree calculated in the calculation step and the weight information indicating the weights for the plurality of feature amounts to obtain the search target image in which the approximation degree is calculated in the calculation step. A generation step for generating arrangement information indicating a position to be displayed on the map;
A display step in which display means of the information processing apparatus outputs to display the search target image at a position on the map indicated by the arrangement information generated by the generation step;
A change accepting step in which the change accepting means of the information processing device accepts a change in the position of the search target image displayed on the map in the display step by a user operation;
Weight information in which the weight information generating means of the information processing device generates weight information according to the arrangement information indicating the position of the search target image whose change has been received by the change receiving step and the approximation calculated by the calculating step Generation process;
With
The generation step further includes the placement information of the search target image whose approximation degree is calculated by the calculation step according to the approximation degree calculated by the calculation step and the weight information generated by the weight information generation step. A control method characterized by generating. An information processing device that includes a storage unit that stores a plurality of search target images that are images to be searched based on the search image, and that displays the search target images on a map indicating a relationship between the plurality of search target images is read An executable program,
The information processing apparatus;
Accepting means for accepting input of a search image by a user;
Calculating means for calculating a degree of approximation between a plurality of feature amounts of the search image received by the receiving means and a plurality of feature amounts of the search target image stored in the storage unit;
Arrangement indicating a position at which the search target image whose degree of approximation is calculated by the calculating unit is displayed on the map according to the degree of approximation calculated by the calculating unit and weight information indicating weights for the plurality of feature amounts Generating means for generating information;
Display means for outputting the search target image to be displayed at a position on the map indicated by the arrangement information generated by the generation means;
Change accepting means for accepting a change in the position of the search target image displayed on the map by the display means by a user operation;
According to the arrangement information indicating the position of the search target image whose change has been received by the change receiving means, and the approximation calculated by the calculating means, function as weight information generating means for generating weight information,
The generation means further includes, based on the approximation degree calculated by the calculation means and the weight information generated by the weight information generation means, the arrangement information of the search target image whose approximation degree is calculated by the calculation means. A program characterized by generating.

Images