Belief propagation and affinity measures

• US 9,214,026 B2
• Filed: 12/20/2012
• Issued: 12/15/2015
• Est. Priority Date: 12/20/2012
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Price, Brian L., Cohen, Scott D., Zhang, Chenxi
• Primary Examiner(s): HEIDEMANN, JASON E
• Application Number:
  US13/722,825
• Publication Number:
  US 20140177903A1
• Time in Patent Office: 1,090 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/20076 Probabilistic image processing
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06T 7/593 from stereo images

Abstract

Belief propagation and affinity measure techniques are described. In one or more implementations, beliefs may be formed to solve a labeling problem for a node, such as to perform image processing. An affinity measure may be calculated that describes how similar the node is to another node. This affinity measure may then be used as a basis to determine whether the share the belief formed for the node with the other node to solve a labeling problem for the other node.

Claims

1. A method implemented by one or more computing devices, the method comprising:

arriving at one or more beliefs for a parent node that are to be used to solve a labeling problem for the parent node for image processing;

calculating an affinity measure of the parent node in comparison with a child node of the parent node, the affinity measure describing how similar the parent node and the child node are to each other, the parent node and child node being in different hierarchical levels; and

responsive to a determination that the affinity measure indicates that the parent node and the child node are different by at least a defined amount, using hierarchical belief propagation to solve a labeling problem for the child node for image processing that does not employ the one or more beliefs for the parent node.

2. A method as described in claim 1, further comprising responsive to a determination that the affinity measure indicates that the parent node and the child node are not different by at least the defined amount, using hierarchical belief propagation to solve the labeling problem for the child node for image processing that does employ the one or more beliefs for the parent node.

3. A method as described in claim 1, further comprising responsive to the determination that the affinity measure indicates that the parent node and the child node are different by at least the defined amount, calculating an affinity measure of the child node with another node, the affinity measure describing how similar the child node and the other node are to each other and the other node located at a level in a hierarchy that includes the parent node.

4. A method as described in claim 3, further comprising responsive to a determination that the affinity measure indicates that the other node and the child node are not different by at least the defined amount, using hierarchical belief propagation to solve the labeling problem for the child node for image processing that employs one or more beliefs arrived at for the other node that are to be used in hierarchical belief propagation to solve a labeling problem for the other node for image processing.

5. A method as described in claim 3, further comprising responsive to a determination that the affinity measure indicates that the other node and the child node are different by at least the defined amount, using hierarchical belief propagation to solve a labeling problem for the child node for image processing that does not employ one or more beliefs arrived at for the other node that are to be used in hierarchical belief propagation to solve a labeling problem for the other node for image processing.

6. A method as described in claim 5, further comprising responsive to the determination that the affinity measure indicates that the other node and the child node are different by at least the defined amount, using hierarchical belief propagation to solve the labeling problem for the child node for image processing that does not include use of beliefs calculated for any node located at a level of a hierarchy that includes the parent node.

7. A method as described in claim 1, wherein the image processing is performed to label pixels of the parent node, the parent node including one or more pixels of the child node.

8. A method as described in claim 1, wherein the image processing includes calculation of stereo correspondence.

9. One or more non-transitory computer-readable storage media comprising instructions that are stored thereon that, responsive to execution by a computing device, causes the computing device to perform operations comprising:

arriving at one or more beliefs for a node that are to be used as part of a labeling problem for the node;

calculating an affinity measure of the node in comparison with at least one or more other nodes in a different hierarchical level, the affinity measure describing a similarity of the node to the one or more other nodes; and

responsive to a determination that the affinity measure indicates that the similarity is within a pre-defined amount, using the one or more beliefs for the node as part of solving a labeling problem for the one or more other nodes.

10. One or more non-transitory computer-readable storage media as described in claim 9, further comprising responsive to a determination that the affinity measure indicates that the similarity is not within the pre-defined amount, solving the labeling problem for the one or more other nodes without using the one or more beliefs for the node.

11. One or more non-transitory computer-readable storage media as described in claim 10, further comprising responsive to the determination that the affinity measure indicates that the similarity is not within the pre-defined amount, calculating an affinity measure of the one or more other nodes with at least one other node, the affinity measure describing similarity of the one or more other nodes with the at least one other node.

12. One or more non-transitory computer-readable storage media as described in claim 11, wherein the at least one other node is a neighbor to the node in a hierarchical level that include the at least one other node and the node.

13. One or more non-transitory computer-readable storage media as described in claim 11, further comprising responsive to a determination that the affinity measure indicates that the similarity is within the pre-defined amount for the one or more other nodes and the at least one other node, solving the labeling problem for the one or more other nodes using one or more beliefs arrived at for the at least one node to solve a labeling problem for the at least one other node.

14. One or more non-transitory computer-readable storage media as described in claim 11, further comprising responsive to a determination that the affinity measure indicates that the similarity is not within the pre-defined amount for the one or more other nodes and the at least one other node, solving the labeling problem for the one or more other nodes without using one or more beliefs arrived at for the at least one node to solve a labeling problem for the at least one other node.

15. One or more non-transitory computer-readable storage media as described in claim 11, wherein the node and the one or more other nodes have a parent/child relationship.

16. One or more non-transitory computer-readable storage media as described in claim 11, wherein the solving of the labeling problem is performed using hierarchical belief propagation.

17. A system comprising:

one or more processors;

one or more computer-readable storage media;

at least one module implemented at least partially in hardware, the at least one module configured to arriving at one or more beliefs for a parent node that are to be used in hierarchical belief propagation to solve a labeling problem for pixels in the parent node; and

one or more modules implemented at least partially in hardware, the one or more modules configured to;

calculate an affinity measure of the parent node in comparison with a child node, the affinity measure describing how similar the parent node and the child node are to each other, the parent node and child node being in different hierarchical levels;

responsive to a determination that the affinity measure indicates that the similarity is within a pre-defined amount, using hierarchical belief propagation to solve the labeling problem for one or more pixels in the child node using the one or more beliefs that were arrived at for the parent node; and

responsive to a determination that the affinity measure indicates that the similarity is not within the pre-defined amount, using hierarchical belief propagation to solve the labeling problem for one or more pixels in the child node without using the one or more beliefs that were arrived at for the parent node.

18. A system as described in claim 17, wherein the labeling problem is used at least in part to determine stereo correspondence.

19. A system as described in claim 17, wherein the affinity measure is based on similarity of color of the pixels in relation to each other.

20. A system as described in claim 17, wherein the affinity measure is based at least in part on whether the pixels are likely included in a foreground or background of an image, respectively.