Bipartite graph reinforcement modeling to annotate web images

• US 8,321,424 B2
• Filed: 08/30/2007
• Issued: 11/27/2012
• Est. Priority Date: 08/30/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Mingjing, Ma, Wei-Ying, Li, Zhiwei, Rui, Xiaoguang
• Primary Examiner(s): LIN, SHEW FEN
• Application Number:
  US11/848,157
• Publication Number:
  US 20090063455A1
• Time in Patent Office: 1,916 Days
• Field of Search: 707/737, 707/748, 707/769, 706/45, 715/230
• US Class Current: 707/748
• 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: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

Systems and methods for bipartite graph reinforcement modeling to annotate web images are described. In one aspect the systems and methods implement bipartite graph reinforcement modeling operations to identify a set of annotations that are relevant to a Web image. The systems and methods annotate the Web image with the identified annotations. The systems and methods then index the annotated Web image. Responsive to receiving an image search query from a user, wherein the image search query comprises information relevant to at least a subset of the identified annotations, the image search engine service presents the annotated Web image to the user.

Claims

1. A method at least partially implemented by a computing device, the method comprising:

determining, using bipartite graph reinforcement modeling, a set of annotations relevant to a Web image, wherein determining the set of annotations comprises;

generating initial candidate annotations for the Web image;

ranking relevancy of the initial candidate annotations to the Web image using a first ranking algorithm, the first ranking algorithm comprising obtaining a first initial candidate annotation ranking and a second initial candidate annotation ranking for each initial candidate annotation and fusing the first initial candidate annotation ranking and the second initial candidate annotation ranking using a weighted linear combination scheme;

identifying, using the initial candidate annotations, extending candidate annotations by submitting each word and corresponding image associated with the initial candidate annotations as a respective query to an image search engine to receive search results and clustering the search results in view of the initial candidate annotations to obtain cluster names, the extending candidate annotations comprising the cluster names;

ranking relevancy of the extending candidate annotations using a second ranking algorithm that is different than the first ranking algorithm by determining an average similarity between images in a cluster and the Web image and weighting the average similarity with textual information associated with the cluster name, the cluster corresponding to the cluster name;

identifying, at least partially in view of relevancy rankings of the initial candidate annotations and the extending candidate annotations, relationships between two disjoint sets of vertices in a bipartite graph, a first set of the two disjoint sets of vertices representing the initial candidate annotations, a second set of the two disjoint sets of vertices representing the extending candidate annotations;

re-ranking the initial candidate annotations and the extending candidate annotations based on the relationships between the two disjoint sets of vertices in the bipartite graph;

annotating the Web image based on the re-ranked initial candidate annotations and the extending candidate annotations; and

providing the Web image to an indexing service for indexing and presentation of relevant search results to a user search query, the relevant search results being based on at least a subset of the annotations.

2. The method of claim 1, wherein determining the set of annotations relevant to the Web image further comprises:

generating a bipartite graph from a first and a second set of vertices, the first and the second set of vertices being disjoint from one another, the first set of vertices representing direct descriptions of the Web image, a second set of vertices representing indirect descriptions of the Web image; and

wherein the bipartite graph models relations between the first and the second sets of vertices.

3. A tangible computer-readable medium having encoded thereon computer-program instructions executable by a processor, the computer-program instructions when executed by the processor, for performing operations comprising:

submitting, for each word in a first set of annotations, a search query to an image search engine to generate a set of search results, the search query comprising the word and an image associated with the word;

clustering the search results in view of words in the first set of annotations to obtain cluster names, obtaining a second set of annotations comprising the cluster names;

modeling relationships between the first set and the second set of annotations in a bipartite graph, the bipartite graph comprising vertices representing the first set of annotations disjoint from the second set of annotations, the first set of annotations being direct descriptions of a target Web image, the second set of annotations being indirect descriptions of the target Web image;

reinforcing, using respective ones of the relationships, initial rankings associated with the first set of annotations and the second sets of annotations by a reinforcement learning algorithm, the first set of annotations ranked according to a ranking algorithm comprising;

obtaining a first initial candidate annotation ranking and a second initial candidate annotation ranking for each annotation in the first set of annotations, and

fusing the first initial candidate annotation ranking and the second initial candidate annotation ranking using a weighted linear combination scheme;

selecting a subset of the first and the second sets of annotations based on results of reinforcing the initial rankings, wherein the subset represents annotations determined with a modified threshold strategy;

annotating the Web image with the subset to generate an annotated Web image; and

providing indexing and search engine applications with access to the annotated Web image to present a user with relevant results to a search query.

4. The tangible computer-readable medium of claim 3, wherein the initial rankings are determined with first and second ranking algorithms, the first ranking algorithm being different than the second ranking algorithm, the first ranking algorithm being used to determine initial rankings of the first set of annotations, the second ranking algorithm being used to determine initial rankings of the second set of annotations.

5. The tangible computer-readable medium of claim 3, wherein operations for reinforcing the initial rankings converge through iteration.

6. The tangible computer-readable medium of claim 3, wherein the operations further comprise removing duplicate names from the cluster names after clustering the search results.

7. The tangible computer-readable medium of claim 3, wherein the operations further comprise operations for mining a large-scale image database for the first set of annotations and the second sets of annotations.

8. A computing device comprising:

a processor; and

a memory coupled to the processor, the memory having encoded thereon a set of computer-program instructions executable by the processor, the computer-program instructions when executed by the processor for performing operations comprising;

generating and ranking initial candidate annotations for a Web image, the ranking initial candidate annotations comprising utilizing a first ranking algorithm that obtains a first initial candidate annotation ranking and a second initial candidate annotation ranking for each initial candidate annotation and fuses the first initial candidate annotation ranking and the second initial candidate annotation ranking using a weighted linear combination scheme;

searching a large-scale image database for search results, the search results comprising text and images related to the initial candidate annotations and corresponding image(s);

clustering the search results based on the initial candidate annotations to create a set of clusters;

selecting a set of extending candidate annotations based on names of the set of clusters;

determining ranking values for each extending candidate annotation in the set of extending candidate annotations using a calculated average similarity between the Web image and images in a corresponding cluster;

generating a bipartite graph using the initial candidate annotations as a first set of vertices disjoint from a second set of vertices representing the extending candidate annotations;

reinforcing initial relevancy rankings of the initial candidate annotations and the extending candidate annotations by a reinforcement learning algorithm in view of relationships modeled by the bipartite graph between the two disjoint sets of vertices, the initial relevancy rankings indicating respective relevancy of each annotation of the initial candidate annotations and the extending candidate annotations to the Web image;

re-ranking, by the reinforcement learning algorithm, the initial relevant rankings of initial candidate annotations, and the extending annotations based on the propagated relations between the vertices with weighted parameters to create re-ranked results;

based on the re-ranked results annotating the Web image with a subset of the initial candidate annotations and the extending candidate annotations;

generating an index from the subset;

evaluating the index to present a search result to a search query from a user; and

selecting the subset by evaluating re-ranked relevancy values generated by reinforcing the initial relevancy rankings, the evaluating comprising selecting a set of final annotations using a threshold algorithm that assigns higher weight to relevancy rankings associated with words in the initial candidate annotations.

9. The computing device of claim 8, wherein:

the initial candidate annotations represent direct descriptions of the Web image, and the extending candidate annotations represent indirect descriptions of the Web image.

10. The computing device of claim 8, wherein searching the large-scale image database further comprises submitting a text-based image search query to the image search engine.

11. The computing device of claim 8, wherein the operations further comprise operations for ranking the initial candidate annotations with a first relevancy ranking algorithm that is different from a second relevancy ranking algorithm used to rank the extending candidate annotations.