Bipartite Graph Reinforcement Modeling to Annotate Web Images

• US 20090063455A1
• Filed: 08/30/2007
• Published: 03/05/2009
• Est. Priority Date: 08/30/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rui, Xiaoguang, Ma, Wei-Ying, Li, Mingjing, Li, Zhiwei
• Granted Patent: US 8,321,424 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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;

annotating the Web image with the 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 further 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;

identifying, using the initial candidate annotations, extending candidate annotations;

ranking relevancy of the extending candidate annotations using a second ranking algorithm that is different than the first ranking algorithm;

identifying, at least partially in view of relevancy rankings of the initial and 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 of the initial and additional annotations in view of the relationships; and

wherein the annotations used to annotate the Web image are selected based on results of the re-ranking operations.

3. The method of claim 2, wherein the results are determined with a top N strategy, a threshold strategy, or a modified threshold strategy.

4. The method of claim 2, wherein identifying the extending candidate annotations further comprises:

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 candidates being the cluster names.

5. The method of claim 4, wherein ranking relevancy of the extending candidate annotations further comprises, for each cluster name of the cluster names:

determining average similarity between images in a cluster and the Web image, the cluster corresponding to the cluster name; and

weighting the average similarity with textual information associated with the cluster name.

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

generating a bipartite graph from first and second sets of vertices, the first and second sets 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 second sets of vertices.

7. The method of claim 1, wherein determining the set of annotations relevant to the Web image further comprises re-ranking initial rankings associated with first and second sets of annotations of the annotations, the re-ranking using relationships between the first and second sets of annotations, the relationships being modeled in a bipartite graph where the first and second sets of annotations represent two disjoint sets of vertices.

8. 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:

modeling relationships between first and second sets 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 and second sets of annotations;

selecting a subset of the first and second sets of annotations based on results of reinforcing the initial rankings;

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

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

9. The tangible computer-readable medium of claim 8, 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.

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

11. The tangible computer-readable medium of claim 8, wherein the subset is a configurable number of annotations with highest ranking values.

12. The tangible computer-readable medium of claim 8, wherein the subset represents annotations with respective ranking values greater than a dynamic threshold, the dynamic threshold being based on numbers of annotations in the first or second sets of annotations.

13. The tangible computer-readable medium of claim 8, wherein the operations further comprise operations for:

selecting candidate final annotations of the first and second sets of annotations with a ranking of value greater than a dynamic threshold; and

appending extending words selected from a subset of the second set of annotations to the candidate final annotations.

14. The tangible computer-readable medium of claim 8, wherein the operations further comprise operations for generating the second set of annotations by:

generating search results by submitting, for each word in the first set of annotations, a search query to an image search engine to receive a respective 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;

removing duplicate names from the cluster names to create the second set of annotations.

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

16. 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 given Web image;

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 search results in view of the initial candidate annotations to generate and rank a set of extending candidate annotations;

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 and extending candidate annotations 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 and extending annotations to the given Web image;

in view of ranking results from reinforcing the initial relevancy rankings, annotating the given Web image with a subset of the initial and extending annotations;

generating an index from the subset; and

evaluating the index to present a search result to a search query from a user.

17. The computing device of claim 16, wherein the initial candidate annotations represent direct descriptions of the given Web image, and wherein the extending candidate annotations represent indirect descriptions of the given Web image.

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

19. The computing device of claim 16, 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.

20. The computing device of claim 16, wherein the subset is selected by evaluating re-ranked relevancy values generated by reinforcing the initial relevancy rankings, the evaluating comprising selecting a set of final annotations using a top N ranking algorithm, a dynamic threshold, or a threshold algorithm that assigns higher weight to relevancy rankings associated with words in the initial candidate annotations.