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; 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.