Filling in scenes by propagating probabilities through layers and into appearance models

Inferring the identities and positions of multiple occluding objects in a noisy image is a difficult problem, even when the shapes and appearances of the allowable objects are known. Methods that detect and analyze shape features, occlusion boundaries and optical flow break down when the image is noisy. In situations where we know the boundaries and appearances of the allowable objects, a brute force method can be used to perform MAP inference. If there are K possible objects (including translations, etc.) in up to L layers, the number of possible configurations of the scene is K/sup L/, so exact inference is intractable for large numbers of objects and reasonably large numbers of layers. We construct a Bayesian network that describes the occlusion process and we use iterative probability propagation to approximately recover the identities and positions of the objects in the scene in time that is linear in K and L. Although iterative probability propagation is an approximate inference technique, it was recently used to obtain the world record in error-correcting decoding. Experiments show that when one explanation of the scene is most probable, the algorithm finds the solution. For a small problem, we show that as the number of iterations increases, iterative probability propagation performs better than a greedy technique and becomes closer to the exact MAP algorithm. Quite surprisingly, we also find that when the order of occlusion is ambiguous, the output of the algorithm may oscillate between plausible interpretations of the scene.