Abstract
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 comparison of Swendsen-Wang Cuts with Graph Cuts and Belief Propagation on the related stereo matching problem.
Introduction
Traditional motion estimation often relies on the "optical flow constraint," which assumes that pixel intensities remain constant and motions are small enough to be captured by spatiotemporal gradients. However, real-world video is complex: objects move quickly, and their movement reveals "accreted" regions—parts of the background or object that were previously occluded. Standard models struggle with these regions because there is no corresponding pixel in the previous frame to match against. Furthermore, traditional methods often fail to provide a clean segmentation of moving objects.
This paper presents a three-stage framework for joint motion estimation and segmentation using Swendsen-Wang Cuts. By framing motion as an image encoding problem, the authors successfully model accreted regions and handle large displacements that traditional gradient-based optical flow methods typically fail to capture.
Methodology
The authors propose a Bayesian framework for Maximum a Posteriori (MAP) estimation, solved in three distinct stages:
- Initial Motion Estimation: Using the Swendsen-Wang (SW) Cuts algorithm, the system estimates a raw motion field and an "accretion map." SW Cuts is a cluster-sampling Markov Chain Monte Carlo (MCMC) method that uses "bottom-up" cues (local intensity and motion similarity) to propose moves. This allows the algorithm to jump through the solution space much faster than traditional pixel-by-pixel MCMC.
- Velocity Clustering: The results from the first stage are clustered in velocity space (similar to K-means) to generate an initial coarse segmentation of the moving regions.
- Full MAP Refinement: The algorithm simultaneously refines the motion estimates, the segmentation boundaries, and the accretion maps. This stage uses a "stochastic boundary diffusion" process to evolve the shapes of moving objects while maintaining smooth motion within those shapes.
A key technical novelty is the explicit modeling of accreted pixels using histogram-based intensity models. This allows the system to "give up" on finding a match in the previous frame if the pixel is clearly new to the scene, preventing the motion field from "leaking" or blurring at object edges.
Experiments and Results
The paper evaluates the approach on a mix of synthetic and real-world data, including city scenes with pedestrians and cars, and the "Woman" sequence involving a moving person and a moving camera. In a head-to-head comparison on a stereo matching task using the Tsukuba dataset, the SW Cuts variant reached within 1% of the energy level achieved by Graph Cuts and matched the performance of Belief Propagation within 15 minutes.
Key Findings
- The Encoding Perspective: By viewing motion as a way to "predict" the next frame, the authors justify why some pixels should be labeled as "accreted." If it is more efficient to describe a pixel using a static intensity model than a motion vector, it is likely a newly revealed region.
- Bottom-Up Proposals: Purely top-down optimization is too slow for high-dimensional image labels. By using local image edges to weight the graph in SW Cuts, the algorithm identifies pixels likely to move together, drastically speeding up convergence.
- Large Motion Handling: Because the method does not rely on local gradients, it can accurately estimate displacements of 10 pixels or more per frame, which would typically require complex multi-resolution image pyramids in standard optical flow.
Conclusion and Future Work
The Swendsen-Wang Cuts approach successfully segments moving objects even under camera motion, producing sharp boundaries that follow object contours closely. While robust, the current implementation uses simple histogram models for image intensities. Future work could incorporate more sophisticated texture models (like the FRAME model) and extend the label space to include sub-pixel accuracy, affine transformations, and 3D motion models to further improve performance in complex environments.
Summary updated