Fast Piecewise-Affine Motion Estimation Without Segmentation

Denis Fortun, Martin Storath, Dennis Rickert, Andreas Weinmann, Michael Unser

TL;DR

This paper introduces a novel method for estimating piecewise-affine motion fields (optical flow) that completely bypasses the computationally heavy step of explicit image segmentation. By reformulating the problem to enforce piecewise constancy directly on the affine parameter field and using a highly efficient 1D dynamic programming solver, the approach achieves competitive accuracy without requiring initialization, runs significantly faster than existing piecewise-parametric methods, and avoids the artifacts common in standard Total Variation models.

What Problem Does This Paper Address?

In optical flow and motion estimation, researchers generally rely on two types of prior models: dense smoothness constraints (like Total Variation, which often creates blocky "staircasing" artifacts) or piecewise-parametric models (which assume the image is made of distinct regions, each moving according to a parametric model like an affine transformation).

Piecewise-parametric models yield highly accurate results with sharp motion boundaries. However, they traditionally require jointly segmenting the image and estimating the motion parameters for each segment. This alternating optimization is a massive headache: it is highly non-convex, extremely sensitive to initialization, and computationally prohibitive. The runtime of these traditional methods scales poorly because it depends on the number of regions in the image. The authors tackle this exact gap: how can we get the high-accuracy, sharp-boundary benefits of piecewise-affine models without the fragile, slow, and complex explicit segmentation step?

Methods

The authors propose a direct estimation approach that eschews explicit segmentation.

  • The Core Model: Instead of alternating between a segmentation map and motion parameters, they express the motion field as a product of a parameter field and spatial coordinates. They then impose a piecewise-constant regularization directly on this parameter field.
  • Directional Splitting (ADMM): Because the resulting optimization problem is still non-convex and NP-hard, they use an Alternating Direction Method of Multipliers (ADMM) framework. This splits the complex 2D problem into a series of tractable subproblems.
  • The 1D Dynamic Programming Solver: This is the paper's secret sauce. The most computationally expensive subproblem is reduced to a series of independent 1D piecewise-affine denoising problems along different directional scan lines (vertical, horizontal, diagonal). These 1D problems are solved exactly and efficiently using dynamic programming.
  • Large Displacements: To handle large, fast motions, the authors integrate a sparse descriptor matching term (DeepMatching) and a standard coarse-to-fine pyramid scheme into their optimization framework.

Datasets

The authors evaluated their method on two standard optical flow benchmarks:

  • MPI Sintel: A dataset extracted from a realistic animated movie. The authors specifically used the clean version (which lacks atmospheric fog and motion blur) to isolate and evaluate the performance of their regularization scheme.
  • KITTI (2012): A real-world dataset of outdoor driving sequences captured from a moving car, characterized by rigid motions and large illumination changes.

Key Insights and Ideas

  • Implicit Segmentation is Faster and More Robust: You don't need to explicitly segment an image to apply piecewise-parametric regularization. Constraining the parameter field directly yields the same structural benefits but removes the need for fragile initialization steps.
  • Dimensionality Reduction Unlocks Exact Solvers: By using directional splitting, a notoriously difficult 2D non-convex problem can be broken down into 1D problems. While 2D segmentation is NP-hard, 1D piecewise-affine partitioning can be solved exactly and optimally via dynamic programming.
  • Complexity Independence: Unlike traditional segmentation-based methods where runtime explodes as the scene becomes more complex (more moving objects = more regions to compute), this 1D dynamic programming approach has a computational cost that is entirely independent of the motion field's complexity.

Key Results

  • Quantitative Accuracy: The method achieved an Average Endpoint Error (AEP) of 1.35 on the MPI Sintel test set and 1.5 on the KITTI test set, making it highly competitive with the best-performing piecewise-parametric methods.
  • Speed: The algorithm runs in about 3 minutes on full-resolution KITTI images using a 4-core CPU. For context, a leading competing method (PH-Flow) takes 15 minutes even on downsampled images.
  • Qualitative Superiority over TV/TGV: The piecewise-affine model naturally avoids the "staircasing" (blocky) artifacts of Total Variation (TV) and the blurring artifacts of Total Generalized Variation (TGV). It delineates sharp motion boundaries much more accurately than these standard regularizers.

Limitations and Future Work

  • Occlusions: The authors explicitly note that occlusion handling is a separate problem not addressed in this paper. Errors at the image borders in their results are primarily due to occlusions, which require dedicated detection and handling techniques.
  • Data Term Flexibility: The current implementation relies on a linearized brightness constancy assumption (with an $L_1$ penalty). While robust, it can struggle with severe illumination changes.
  • Future Work: Because the proximal splitting strategy is highly modular, the authors suggest that their approach can serve as a general regularization framework. Future work could easily swap in more sophisticated data terms (like the census transform or normalized cross-correlation) to further improve robustness in challenging lighting conditions.

Summary updated

Abstract

Current algorithmic approaches for piecewise affine motion estimation are based on alternating motion segmentation and estimation. We propose a new method to estimate piecewise affine motion fields directly without intermediate segmentation. To this end, we reformulate the problem by imposing piecewise constancy of the parameter field, and derive a specific proximal splitting optimization scheme. A key component of our framework is an efficient 1D piecewise-affine estimator for vector-valued signals. The first advantage of our approach over segmentation-based methods is its absence of initialization. The second advantage is its lower computational cost, which is independent of the complexity of the motion field. In addition to these features, we demonstrate competitive accuracy with other piecewise-parametric methods on standard evaluation benchmarks. Our new regularization scheme also outperforms the more standard use of total variation and total generalized variation.
BibTeX
@article{fortun2018fast,
  author = {Denis Fortun and Martin Storath and Dennis Rickert and Andreas Weinmann and Michael Unser},
  title = {{Fast Piecewise-Affine Motion Estimation Without Segmentation}},
  journal = {IEEE Trans. Image Process.},
  year = {2018},
  doi = {10.1109/tip.2018.2856399},
}

Loading related content...

Figure