Method and apparatus for improving the speed of belief propagation

A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for efficiently performing a belief-propagation operation, wherein for each node i in a belief-propagation graph, the method comprises iteratively:

• receiving incoming messages mij at node i for all adjacent nodes j;
• calculating the full product Pi of all incoming messages mi;
• and
• producing an outgoing message mji from node i to a node j by,
• calculating a partial product Pij of all incoming messages to node i except for the message from node j by dividing the Pi by the incoming message mji from node j, and
• composing Pij with a data function for node i and a smoothness function between node i and node j to produce outgoing message mij;
• and
• communicating outgoing message mij to node j.

An apparatus that efficiently performs a belief-propagation operation, comprising:

• a computation mechanism within a computer system, wherein for each node i in a belief-propagation graph, the computation mechanism is configured to iteratively,
• receive incoming messages mji at node i for all adjacent nodes i,
• calculate the full product Pi of all incoming messages mji,
• produce an outgoing message mij from node i to a node j, and in doing so to,
• calculate a partial product Pij of all incoming messages to node i except for the message from node j by dividing the Pi by the incoming message from node j, and to
• compose Pij with a data function for node i and a smoothness function between node i and node j to produce outgoing message mij;
• and
• a communication mechanism within the computer system configured to communicate outgoing message mij to node j.

A computer-implemented method for efficiently performing a belief-propagation operation, the method comprising:

• using a computer to perform the following:
• for each node i in a belief-propagation graph, iteratively:
• receiving incoming messages mji at node i for all adjacent nodes j;
• producing an outgoing message mij from node i to node j by,
• calculating a partial product Pij of all incoming messages to node i except for the message from node j, and
• composing Pij with a data function for node i and a smoothness function between node i and node j to produce outgoing message mij;
• communicating outgoing message mij to node j;
• after each iteration of the belief-propagation process, determining whether a given node has converged by computing differences between old and new messages for the given node;
• and
• if the given node has converged, subsequently resending previously sent outgoing messages from the given node instead of recomputing the outgoing messages.