Fast Piecewise-Affine Motion Estimation Without Segmentation

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

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 one-dimensional 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.

Introduction

In the field of optical flow and motion estimation, researchers typically rely on two primary types of prior models: dense smoothness constraints, such as Total Variation (TV), or piecewise-parametric models. While TV-based methods are common, they often introduce "staircasing" artifacts. Conversely, piecewise-parametric models assume the image consists of distinct regions, each following a specific motion model (e.g., affine transformation). These models produce highly accurate results with sharp motion boundaries but traditionally require a complex, alternating process of image segmentation and motion parameter estimation. This optimization is non-convex, sensitive to initialization, and computationally expensive, with runtimes that scale poorly with scene complexity.

This paper introduces a novel approach that achieves the benefits of piecewise-affine models—high accuracy and sharp boundaries—without the need for explicit, fragile segmentation steps.

Methodology

The proposed method bypasses explicit segmentation by reformulating the motion estimation problem.

Core Model and Optimization

Instead of alternating between a segmentation map and motion parameters, the motion field is expressed as a product of a parameter field and spatial coordinates. Piecewise-constant regularization is then applied directly to this parameter field. To handle the resulting non-convex and NP-hard optimization problem, the authors employ an Alternating Direction Method of Multipliers (ADMM) framework, which splits the 2D problem into more manageable subproblems.

1D Dynamic Programming Solver

A critical innovation in this framework is the reduction of the most computationally intensive subproblem into a series of independent 1D piecewise-affine denoising problems. By processing along directional scan lines (horizontal, vertical, and diagonal), these 1D problems can be solved exactly and optimally using dynamic programming. This approach ensures that the computational cost remains independent of the motion field's complexity.

Large Displacement Handling

To account for large and fast motions, the optimization framework integrates a sparse descriptor matching term (DeepMatching) and a standard coarse-to-fine pyramid scheme.

Experimental Results

The method was evaluated on the MPI Sintel (clean version) and KITTI 2012 benchmarks.

Quantitative Performance

The algorithm achieved an Average Endpoint Error (AEP) of 1.35 on the MPI Sintel test set and 1.5 on the KITTI test set. These results are highly competitive with state-of-the-art piecewise-parametric methods. Notably, the method is significantly faster; it processes full-resolution KITTI images in approximately 3 minutes on a 4-core CPU, whereas competing methods like PH-Flow can take up to 15 minutes on downsampled images.

Comparison of optical flow estimation and error maps on the MPI Sintel dataset.

Qualitative Analysis

The piecewise-affine model naturally avoids the blocky artifacts associated with Total Variation and the blurring artifacts seen in Total Generalized Variation (TGV). As shown in the comparison above, the proposed method delineates sharp motion boundaries with high precision. Further qualitative results on complex scenes demonstrate the method's ability to capture intricate structures and sharp transitions compared to standard approaches.

Qualitative results on a complex motion sequence.

Discussion and Conclusion

The primary insight of this work is that implicit segmentation via direct parameter field regularization is both more robust and faster than traditional explicit segmentation. By leveraging directional splitting and 1D dynamic programming, the authors provide a solution that is independent of scene complexity and avoids the need for fragile initialization.

While the method shows strong performance, it currently does not explicitly handle occlusions, which account for most errors at image borders. Future work could involve integrating more sophisticated data terms, such as the census transform, or dedicated occlusion detection techniques to further enhance robustness in challenging real-world 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 one-dimensional 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},
}
Figure