×

Using a bipartite graph to model and derive image and text associations

  • US 8,001,139 B2
  • Filed: 12/20/2007
  • Issued: 08/16/2011
  • Est. Priority Date: 12/20/2007
  • Status: Active Grant
First Claim
Patent Images

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;

    wherein the association score is derived, at least in part, on a random walk through the bipartite graph, wherein the random walk is performed based, at least in part, 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 probability associated with a directed edge from one node to another node is based, at least in part, on the probability that one word represented by the one node is associated with any image in a set of images with which another word represented by the other node is associated;

    wherein the method is performed by one or more computing devices.

View all claims
  • 9 Assignments
Timeline View
Assignment View
    ×
    ×