Our paper has two main contributions. Firstly, it presents a model for image sequences motivated by an image encoding perspective. It models accreted regions, where
objects appear, as well as motion and motion boundaries. We formulate the problem as probabilistic inference using
prior models of images and the motion field. Secondly, it introduces a new algorithm for motion estimation based on Swendsen-Wang Cuts, which performs inference on the image sequence model using bottom-up proposals to guide the search. The algorithm proceeds by first estimating the motion without the boundaries, and then by clustering in
the velocity space to obtain initial estimates of the motion boundaries. The algorithm performs MAP estimation by evolving the motion boundaries by a stochastic boundary diffusion algorithm, while improving the motion estimates. Our approach is illustrated on real images of city scenes and on simulated data and can deal with large motions (even 10 pixels or more per frame). We show a brief com- parison of Swendsen-Wang Cuts with Graph Cuts and Belief Propagation on the related stereo matching problem.