Projecting queries and images into a similarity space

• US 7,698,332 B2
• Filed: 03/13/2006
• Issued: 04/13/2010
• Est. Priority Date: 03/13/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Liu, Tie-Yan, Qin, Tao
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Lee; Rachel J
• Application Number:
  US11/375,528
• Publication Number:
  US 20070214114A1
• Time in Patent Office: 1,492 Days
• Field of Search: None
• US Class Current: 707/728
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and system for projecting queries and images into a similarity space where queries are close to their relevant images is provided. A similarity space projection (“SSP”) system learns a query projection function and an image projection function based on training data. The query projection function projects the relevance of the most relevant words of a query into a similarity space and the image projection function projects the relevance to an image of the most relevant words of a query into the same similarity space so that queries and their relevant images are close in the similarity space. The SSP system can then identify images that are relevant to a target query and queries that are relevant to a target image using the projection functions.

Claims

1. A computing system with a central processing unit and memory for projecting images and queries into a similarity space, comprising:

a data store that provides queries and images as training data and relevance of the images to the queries, the queries and images having associated words, the words being from a collection of words;

a relevance extraction component that,

for each image, identifies an image relevance for the most relevant words to the image, the image relevance represented by a most-relevant image feature having non-zero scores for each of the words of the collection that are most relevant to the image and having a score of zero for each of the other words of the collection; and

for each query,

identifies a query relevance for the most relevant words to the query, the query relevance represented by a most-relevant query feature having non-zero scores for each of the words of the collection that are most relevant to the query and a score of zero for each of the other words of the collection; and

for each image, identifies a query-specific image relevance that is specific to the query, the query-specific image relevance represented by a query-specific image feature having scores indicating relevance of the image to each of those most relevant words of the query and having scores of zero for each of the other words of the collection, the query-specific image feature being generated by;

for each of the most-relevant words to the query as indicated by a non-zero score in the most-relevant query feature,

 

extracting the score for that most-relevant word from the most-relevant image feature for the image; and

 

setting the score for that most-relevant word in the query-specific image feature to the extracted score; and

setting the score for the other words of the query-specific image feature to zero;

so that each combination of a query and an image has a query-specific image feature that includes, for each of the most relevant words of the query, the relevance score for that most relevant word from the image feature;

a learn projection component that learns a projection of the most-relevant query features to a similarity space and a projection of the query-specific image features to the similarity space so that in the similarity space distances between queries and their relevant images are smaller than distances between queries and their non-relevant images; and

a search component that identifies the most relevant words of a target query and their query relevance to the target query represented by a most-relevant query feature;

for each image, identifies image relevance to the image of the identified most-relevant words represented by a query-specific image feature;

projects the most-relevant query feature and the query-specific image feature; and

selects images with projected query-specific image features whose distances from the projected most-relevant query feature in the similarity space are smallest as being relevant to the query.

2. The system of claim 1 wherein the relevance extraction component includes:

a query feature extraction component that for each query identifies the most relevant words to the query and generates the most-relevant query feature that contains the relevance of the most relevant words to the query;

a feature selection component that for each query generates a feature selection operator for selecting the relevance of the most relevant words to the images; and

an image feature extraction component that for each image generates an image feature that contains the relevance of each word to the image and for each query and image combination uses the feature selection operator for the query to generate the query-specific image feature for the combination.

3. The system of claim 1 wherein the learn projection component uses a gradient descent optimization technique to minimize a distance in the similarity space between queries and their relevant images and to maximize a distance in similarity space between queries and their non-relevant images.

4. The system of claim 3 wherein the technique alternates between determination of gradient descent direction for a query projection and an image projection.

5. The system of claim 1 including an annotation component that

provides the image relevance of a target image to words;

for each query, identifies the image relevance of the most relevant words to the target image;

projects the image relevance of the target image into the similarity space; and

selects queries that are close to the image as being relevant to the target image.

6. The system of claim 5 wherein an annotation for the target image is generated from the selected queries.

7. The system of claim 1 wherein the image relevances represent textual features that are augmented with visual features for learning an image projection function that is based on textual and visual features.

8. The system of claim 1 including a data collection component that submits queries of the training data to a search engine and identifies images and words from the search results of the queries.

9. A method performed by computing system with a central processing unit and memory for projecting images and queries into a similarity space, comprising:

providing a data store that stores queries and images as training data and relevance of the images to the queries, the queries and images having associated words, the words being from a collection of words;

extracting by the processor relevance of images by;

for each image, identifying an image relevance for the most relevant words to the image, the image relevance represented by a most-relevant image feature having a score indicating relevance of a word to the image for each of the words of the collection that are most relevant to the image and having a score indicating that a word is not relevant to the image for each of the other words of the collection; and

for each query,

identifying a query relevance for the most relevant words to the query, the query relevance represented by a most-relevant query feature having a score indicating relevance of a word to the query for each of the words of the collection that are most relevant to the query and a score indicating that a word is not relevant to the query for each of the other words of the collection; and

for each image, identifying a query-specific image relevance that is specific to the query, the query-specific image relevance represented by a query-specific image feature having scores indicating relevance of the image to each of those most relevant words of the query and having scores indicating that a word is not relevant to the image for each of the other words of the collection, the query-specific image feature being generated by;

for each of the most-relevant words to the query as indicated by a score in the most-relevant query feature,

 

extracting the score for that most-relevant word from the most-relevant image feature for the image; and

 

setting the score for that most-relevant word in the query-specific image feature to the extracted score; and

setting the score for the other words of the query-specific image feature to indicate no relevance;

so that each combination of a query and an image has a query-specific image feature that includes, for each of the most relevant words of the query, the score for that most relevant word from the image feature;

learning by the processor a projection of the most-relevant query features to a similarity space and a projection of the query-specific image features to the similarity space so that in the similarity space distances between queries and their relevant images are smaller than distances between queries and their non-relevant images; and

searching by the processor by;

identifying the most relevant words of a target query and their query relevance to the target query represented by a most-relevant query feature;

for each image, identifying image relevance to the image of the identified most-relevant words represented by a query-specific image feature;

projecting the most-relevant query feature and the query-specific image feature; and

selecting images with projected query-specific image features whose distances from the projected most-relevant query feature in the similarity space are smallest as being relevant to the query.

10. The method of claim 9 wherein the learning of a projection uses a gradient descent optimization technique to minimize a distance in the similarity space between queries and their relevant images and to maximize a distance in similarity space between queries and their non-relevant images.

11. The method of claim 10 wherein the technique alternates between determination of gradient descent direction for a query projection and an image projection.

12. The method of claim 9 including:

providing the image relevance of a target image to words;

for each query, identifying the image relevance of the most relevant words to the target image;

projecting the image relevance of the target image into the similarity space; and

selecting queries that are close to the image as being relevant to the target image.

13. The method of claim 12 wherein an annotation for the target image is generated from the selected queries.

14. The method of claim 9 wherein the image relevances represent textual features that are augmented with visual features for learning an image projection function that is based on textual and visual features.

15. The method of claim 9 including submitting queries of the training data to a search engine and identifying images and words from the search results of the queries.