Method and apparatus for improving the speed of belief propagation

• US 7,606,420 B1
• Filed: 10/31/2005
• Issued: 10/20/2009
• Est. Priority Date: 10/31/2005
• Status: Expired due to Fees

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Ruzon, Mark A.
• Primary Examiner(s): Mariam; Daniel G
• Assistant Examiner(s): Allison; Andrae S
• Application Number:
  US11/264,537
• Time in Patent Office: 1,450 Days
• Field of Search: 382/100, 382/103, 382/106, 382/107, 382/140, 382/154, 382/155, 382/168, 382/174, 382/181, 382/184, 382/193, 382/194, 382199-203, 382/232, 382/255, 382/260, 382/264, 382/274, 382/276, 382286-288, 382/291, 382/305, 382317-321, 348/584, 375/240.16, 345/475, 345/530, 345/166
• US Class Current: 382/180
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06T 7/277 involving stochastic approaches, e.g. using Kalman filters

Abstract

One embodiment of the present invention provides a system that efficiently performs a belief-propagation (BP) operation. During this process, for each node i in a BP graph, the system iteratively performs the following operations. First, the system receives incoming messages m_ji at node i for all adjacent nodes j. Next, the system calculates the full product P_i of all incoming messages m_ji. The system then produces an outgoing message m_ij from node i to node j by, computing a partial product P_ij of all incoming messages to node i except for the message from node j by dividing the P_i by the incoming message from node j. The system then combines P_ij with a data function for node i and a smoothness function between node i and node j to produce outgoing message m_ij. Finally the system communicates outgoing message m_ij to node j. This system improves computational efficiency over existing BP techniques because computing the full product P_i first and then dividing by individual incoming messages to produce each partial product is faster than computing each partial product separately.

Claims

1. 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 m_ji at node i for all adjacent nodes j;

calculating the full product P_i of all incoming messages m_ji; and

producing an outgoing message m_ij from node i to a node j by,

calculating a partial product P_ij of all incoming messages to node i except for the message from node j by dividing P_i by the incoming message from node j, and

composing P_ij with a data function for node i and a smoothness function between node i and node j to produce outgoing message m_ij; and

communicating outgoing message m_ij to node j.

2. The method of claim 1, wherein computing the full product P_i involves:

multiplying all incoming messages to node i except for the message from node k to compute the partial product P_ik; and

multiplying P_ik by the message from node k to produce the full product P_i;

whereby the partial product P_ik can be computed while the full product P_i is being computed.

3. The method of claim 1, wherein after each iteration of the belief-propagation process over all nodes of the belief-propagation graph, the method further comprises:

computing differences between old and new messages over the entire belief-propagation graph to compute an amount of change for the entire belief-propagation graph; and

if the amount of change falls below a threshold, terminating the belief-propagation process.

4. The method of claim 1, wherein after each iteration of the belief-propagation process, the method further comprises:

determining whether a node has converged by computing differences between old and new messages for the node; and

if the node has converged, subsequently resending previously sent outgoing messages from the node instead of recomputing the outgoing messages.

5. The method of claim 4, wherein if a node has converged, the method further comprises setting a flag to indicate that the node has converged.

6. The method of claim 1, wherein the belief-propagation process is used to compute an optical flow for an image, wherein each node in the belief-propagation graph holds a local velocity estimate for a corresponding point in the image, and wherein each node is adjacent to nodes that are associated with neighboring points in the image;

and

wherein the method further comprises using the computed optical flow to compute an apparent motion for one or more objects in the image.

7. 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 m_ij at node i for all adjacent nodes j;

calculating the full product P_i of all incoming messages m_i; and

producing an outgoing message m_ji from node i to a node j by,

calculating a partial product P_ij of all incoming messages to node i except for the message from node j by dividing the P_i by the incoming message m_ji from node j, and

composing P_ij with a data function for node i and a smoothness function between node i and node j to produce outgoing message m_ij; and

communicating outgoing message m_ij to node j.

8. The computer-readable storage medium of claim 7, wherein computing the full product P_i involves:

multiplying all incoming messages to node i except for the message from node k to compute the partial product P_ik; and

multiplying P_ik by the message from node k to produce the full product P_i;

whereby the partial product P_ik can be computed while the full product P_i is being computed.

9. The computer-readable storage medium of claim 7, wherein after each iteration of the belief-propagation process over all nodes of the belief-propagation graph, the method further comprises:

computing differences between old and new messages over the entire belief-propagation graph to compute an amount of change for the entire belief-propagation graph; and

if the amount of change falls below a threshold, terminating the belief-propagation process.

10. The computer-readable storage medium of claim 7, wherein after each iteration of the belief-propagation process, the method further comprises:

determining whether a node has converged by computing differences between old and new messages for the node; and

if the node has converged, subsequently resending previously sent outgoing messages from the node instead of recomputing the outgoing messages.

11. The computer-readable storage medium of claim 10, wherein if a node has converged, the method further comprises setting a flag to indicate that the node has converged.

12. The computer-readable storage medium of claim 7, wherein the belief-propagation process is used to compute an optical flow for an image, wherein each node in the belief-propagation graph holds a local velocity estimate for a corresponding point in the image, and wherein each node is adjacent to nodes that are associated with neighboring points in the image;

and

wherein the method further comprises using the computed optical flow to compute an apparent motion for one or more objects in the image.

13. 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 m_ji at node i for all adjacent nodes i,

calculate the full product P_i of all incoming messages m_ji,

produce an outgoing message m_ij from node i to a node j, and in doing so to,

calculate a partial product P_ij of all incoming messages to node i except for the message from node j by dividing the P_i by the incoming message from node j, and to

compose P_ij with a data function for node i and a smoothness function between node i and node j to produce outgoing message m_ij; and

a communication mechanism within the computer system configured to communicate outgoing message m_ij to node j.

14. The apparatus of claim 13, wherein while computing the full product P_i, the computation mechanism is configured to:

multiply all incoming messages to node i except for the message from node k to compute the partial product P_ik; and

to

multiply P_ik by the message from node k to produce the full product P_i;

whereby the partial product P_ik can be computed while the full product P_i is being computed.

15. The apparatus of claim 13, wherein after each iteration of the belief-propagation process over all nodes of the belief-propagation graph, the computation mechanism is configured to:

compute differences between old and new messages over the entire belief-propagation graph to compute an amount of change for the entire belief-propagation graph; and

if the amount of change falls below a threshold, to terminate the belief-propagation process.

16. The apparatus of claim 13, further comprising a resending mechanism, wherein after each iteration of the belief-propagation process, the resending mechanism is configured to:

determine whether a node has converged by computing differences between old and new messages for the node; and

if the node has converged, to subsequently resend previously sent outgoing messages from the node instead of recomputing the outgoing messages.

17. The apparatus of claim 16, wherein if a node has converged, the computation mechanism is configured to set a flag to indicate that the node has converged.

18. The apparatus of claim 13, wherein the computation mechanism is used to compute an optical flow for an image, wherein each node in the belief-propagation graph holds a local velocity estimate for a corresponding point in the image, and wherein each node is adjacent to nodes that are associated with neighboring points in the image;

and

wherein the computation mechanism is further configured to use the computed optical flow to compute an apparent motion for one or more objects in the image.

19. 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 m_ji at node i for all adjacent nodes j;

producing an outgoing message m_ij from node i to node j by,

calculating a partial product P_ij of all incoming messages to node i except for the message from node j, and

composing P_ij with a data function for node i and a smoothness function between node i and node j to produce outgoing message m_ij;

communicating outgoing message m_ij 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.

20. The method of claim 19, wherein after each iteration of the belief-propagation process over all nodes of the belief-propagation graph, the computation mechanism is configured to:

compute differences between old and new messages over the entire belief-propagation graph to compute an amount of change for the entire belief-propagation graph; and

if the amount of change falls below a threshold, to terminate the belief-propagation process.