USING A BIPARTITE GRAPH TO MODEL AND DERIVE IMAGE AND TEXT ASSOCIATIONS

• US 20090160860A1
• Filed: 12/20/2007
• Published: 06/25/2009
• Est. Priority Date: 12/20/2007
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Slaney, Malcolm, Sengamedu, Srinivasan H.
• Granted Patent: US 8,001,139 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• CPC Class Codes: G06F 16/5866 using information manually generated, e.g. tags, keywords, comments, manually generated location and time information

Abstract

A method for deriving probabilistic association scores based on image content is provided. A bipartite graph is constructed based on a database of image content and associated textual content. One partition of the bipartite graph contains image content and the other partition of the bipartite graph contains textual content. Weighted edges between nodes in the two partitions represent associations between the image content and textual content in the database. Random walks on the bipartite graph are performed to derive probabilistic association scores between image content and textual content. Association scores are used to automatically annotate images and detect spurious image tags.

Claims

1. A method comprising:

constructing, based on a set of data, a bipartite graph;

wherein the set of data comprises a set of visual words, a set of linguistic words, and a set of associations between the set of visual words and the set of linguistic words;

wherein each association in the set of associations is an association between a visual word in the set of visual words and a linguistic word in the set of linguistic words;

wherein constructing the bipartite graph includes constructing a first partition and a second partition;

wherein the first partition comprises a first set of nodes;

wherein each node in the first set of nodes represents a linguistic word in the set of linguistic words;

wherein the second partition comprises a second set of nodes;

wherein each node in the second set of nodes represents a visual word in the set of visual words;

deriving and storing in volatile or non-volatile memory, based on the bipartite graph, an association score between a first node of said bipartite graph and a second node of said bipartite graph.

2. The method of claim 1 wherein the step of deriving the association score includes:

generating a first set of scores based on a random walk through the bipartite graph;

generating a second set of scores based on a random walk, with restart from the first node, through the bipartite graph; and

deriving the association score based on the first set of scores and the second set of scores.

3. The method of claim 1, further comprising:

constructing a set of connections between the first set of nodes and the second set of nodes;

wherein each connection in the set of connections connects a node in the first set of nodes and a node in the second set of nodes if there is an association between the linguistic word represented by the node in the first set of nodes and the visual word represented by the node in the second set of nodes;

wherein each connection in the set of connections comprises a first directed edge and a second directed edge;

wherein the first directed edge is directed from the node in the first set of nodes to the node in the second set of nodes;

wherein the second directed edge is directed from the node in the second set of nodes to the node in the first set of nodes;

wherein the first directed edge is labeled with a first probability;

wherein the first probability indicates a probability that the visual word represented by the node in the second set of nodes occurs in an image in the set of images described by the linguistic word represented by the node in the first set of nodes;

wherein the second directed edge is labeled with a second probability;

wherein the second probability indicates a probability that the linguistic word represented by the node in the first set of nodes describes an image in the set of images in which the visual word represented by the node in the second set of nodes occurs;

wherein the random walk through the bipartite graph is performed based on probabilities labeled on directed edges in connections between nodes in the first set of nodes and nodes in the second set of nodes; and

wherein the random walk, with restart from the first node, through the bipartite graph is performed based on probabilities labeled on directed edges in connections between nodes in the first set of nodes and nodes in the second set of nodes, with restarts at the first node based on a restart probability.

4. The method of claim 1 wherein the first node represents a linguistic word, the second node represents a visual word, and the association score indicates a degree of association between the linguistic word and the visual word.

5. The method of claim 4 wherein the association score indicates how strongly the linguistic word is associated with the visual word.

6. The method of claim 4 wherein the association score indicates how strongly the visual word is associated with the linguistic word.

7. The method of claim 1 wherein the first node represents a first linguistic word, the second node represents a second linguistic word, and the association score indicates a degree of association between the first linguistic word and the second linguistic word.

8. The method of claim 1 wherein the first node represents a first visual word, the second node represents a second visual word, and the association score indicates a degree of association between the first visual word and the second visual word.

9. The method of claim 3, wherein:

the set of data further comprises a set of images; and

wherein a visual in the set of visual words is associated with a linguistic word in the set of linguistic words if the visual word occurs in an image described by the linguistic word.

10. The method of claim 5, further comprising:

receiving a new image;

generating a new set of visual words;

wherein each visual word in the new set of visual words represents a characteristic of the new image;

for each visual word in the set of new visual words and each linguistic word associated with the each visual word, performing the step of deriving an association score;

wherein the first node represents the each visual word;

wherein the second node represents the each linguistic word that is associated with the each visual word;

wherein the step of deriving an association score further comprises storing the association score in a set of association scores;

determining, based on the set of association scores, a new set of linguistic words;

wherein each linguistic word in the new set of linguistic words is represented by a node which has an association score with the each visual word that is above a preset threshold; and

wherein the new set of linguistic words are used to describe the new image.

11. The method of claim 5, further comprising:

receiving a new image;

generating a new set of visual words;

wherein each visual word in the new set of visual words represents a characteristic of the new image;

receiving a first set of linguistic words;

wherein the first set of linguistic words is associated with the new image;

for each visual word in the set of new visual words and each linguistic word in the first set of linguistic words, performing the step of deriving an association score;

wherein the first node represents the each visual word;

wherein the second node represents the each linguistic word;

wherein the step of deriving an association score further comprises storing the association score in a set of association scores;

eliminating, from the first set of linguistic words, all linguistic words represented by nodes whose association scores with visual words in the new set of visual words is below a preset-threshold.

12. A computer-readable storage medium storing instructions, the instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of:

constructing, based on a set of data, a bipartite graph;

wherein the set of data comprises a set of visual words, a set of linguistic words, and a set of associations between the set of visual words and the set of linguistic words;

wherein each association in the set of associations is an association between a visual word in the set of visual words and a linguistic word in the set of linguistic words;

wherein constructing the bipartite graph includes constructing a first partition and a second partition;

wherein the first partition comprises a first set of nodes;

wherein each node in the first set of nodes represents a linguistic word in the set of linguistic words;

wherein the second partition comprises a second set of nodes;

wherein each node in the second set of nodes represents a visual word in the set of visual words;

deriving and storing in volatile or non-volatile memory, based on the bipartite graph, an association score between a first node of said bipartite graph and a second node of said bipartite graph.

13. The computer-readable storage medium of claim 12 wherein the instructions for deriving the association score includes instructions for:

generating a first set of scores based on a random walk through the bipartite graph;

generating a second set of scores based on a random walk, with restart from the first node, through the bipartite graph; and

deriving the association score based on the first set of scores and the second set of scores.

14. The computer-readable storage medium of claim 12, further comprising instructions for:

constructing a set of connections between the first set of nodes and the second set of nodes;

wherein each connection in the set of connections connects a node in the first set of nodes and a node in the second set of nodes if there is an association between the linguistic word represented by the node in the first set of nodes and the visual word represented by the node in the second set of nodes;

wherein each connection in the set of connections comprises a first directed edge and a second directed edge;

wherein the first directed edge is directed from the node in the first set of nodes to the node in the second set of nodes;

wherein the second directed edge is directed from the node in the second set of nodes to the node in the first set of nodes;

wherein the first directed edge is labeled with a first probability;

wherein the first probability indicates a probability that the visual word represented by the node in the second set of nodes occurs in an image in the set of images described by the linguistic word represented by the node in the first set of nodes;

wherein the second directed edge is labeled with a second probability;

wherein the second probability indicates a probability that the linguistic word represented by the node in the first set of nodes describes an image in the set of images in which the visual word represented by the node in the second set of nodes occurs;

wherein the random walk through the bipartite graph is performed based on probabilities labeled on directed edges in connections between nodes in the first set of nodes and nodes in the second set of nodes; and

wherein the random walk, with restart from the first node, through the bipartite graph is performed based on probabilities labeled on directed edges in connections between nodes in the first set of nodes and nodes in the second set of nodes, with restarts at the first node based on a restart probability.

15. The computer-readable storage medium of claim 12 wherein the first node represents a linguistic word, the second node represents a visual word, and the association score indicates a degree of association between the linguistic word and the visual word.

16. The computer-readable storage medium of claim 13 wherein the association score indicates how strongly the linguistic word is associated with the visual word.

17. The computer-readable storage medium of claim 13 wherein the association score indicates how strongly the visual word is associated with the linguistic word.

18. The computer-readable storage medium of claim 12 wherein the first node represents a first linguistic word, the second node represents a second linguistic word, and the association score indicates a degree of association between the first linguistic word and the second linguistic word.

19. The computer-readable storage medium of claim 12 wherein the first node represents a first visual word, the second node represents a second visual word, and the association score indicates a degree of association between the first visual word and the second visual word.

20. The computer-readable storage medium of claim 12, wherein:

the set of data further comprises a set of images; and

wherein a visual in the set of visual words is associated with a linguistic word in the set of linguistic words if the visual word occurs in an image described by the linguistic word.

21. The computer-readable storage medium of claim 16, further comprising instructions for:

receiving a new image;

generating a new set of visual words;

wherein each visual word in the new set of visual words represents a characteristic of the new image;

for each visual word in the set of new visual words and each linguistic word associated with the each visual word, performing the step of deriving an association score;

wherein the first node represents the each visual word;

wherein the second node represents the each linguistic word that is associated with the each visual word;

wherein the step of deriving an association score further comprises storing the association score in a set of association scores;

determining, based on the set of association scores, a new set of linguistic words;

wherein each linguistic word in the new set of linguistic words is represented by a node which has an association score with the each visual word that is above a preset threshold; and

wherein the new set of linguistic words are used to describe the new image.

22. The computer-readable storage medium of claim 16, further comprising instructions for:

receiving a new image;

generating a new set of visual words;

wherein each visual word in the new set of visual words represents a characteristic of the new image;

receiving a first set of linguistic words;

wherein the first set of linguistic words is associated with the new image;

for each visual word in the set of new visual words and each linguistic word in the first set of linguistic words, performing the step of deriving an association score;

wherein the first node represents the each visual word;

wherein the second node represents the each linguistic word;

wherein the step of deriving an association score further comprises storing the association score in a set of association scores;

eliminating, from the first set of linguistic words, all linguistic words represented by nodes whose association scores with visual words in the new set of visual words is below a preset-threshold.