Controlling Model Complexity in Flow Estimation

Zoran Duric, Fayin Li, Harry Wechsler, Vladimir CherkasskyICCV 2003 · DOI

Introduction

Optical flow estimation—the process of determining how objects move between consecutive video frames—is a fundamental task in computer vision. Despite its importance, it remains a significant challenge due to two primary issues: the aperture problem and the difficulty of model selection. The aperture problem occurs when motion is viewed through a limited window, making it impossible to determine the full velocity of an edge. Model selection, or the "Goldilocks" problem, involves choosing a motion model that is neither too simple to capture the movement nor too complex to overfit the image noise.

Traditional approaches to model selection often rely on asymptotic statistics, which require large datasets to be effective. However, in many real-world video applications, data is sparse and noisy. This paper proposes a robust solution by applying Statistical Learning Theory (SLT) and Vapnik-Chervonenkis (VC) generalization bounds to flow estimation.

Methodology

VC-Generalization Bounds

Rather than simply minimizing empirical risk (how well a model fits the current data), the authors utilize VC-dimension to penalize excessive model complexity. By calculating a "prediction risk," the approach estimates how well a model will generalize to future, unseen frames. This provides a mathematical framework to select the optimal model even when working with small samples.

Model Hierarchy

The researchers tested five nested models of increasing complexity to represent motion:

  • M1: Pure translation (2 degrees of freedom).
  • M2/M3: Translation combined with rotation, shear, or scaling (4 degrees of freedom).
  • M4: 6-parameter affine flow.
  • M5: Full affine and quadratic flow (8 degrees of freedom).

Addressing the Aperture Problem

To stabilize the mathematical estimation in cases where data is ambiguous (the aperture problem), the authors employed ridge regression. By adding a penalty term to the optimization process, they could prevent the model from producing erratic results when the "condition number" of the motion matrix indicated high uncertainty.

Experimental Validation

The methodology was validated using both synthetic and real-world datasets. The synthetic tests involved a moving square with added Gaussian noise, allowing for a precise comparison against "ground truth" motion. In these tests, the Vapnik measure (vm) correctly identified the true motion model with 96% to 100% accuracy, significantly outperforming classical criteria like Akaike’s Information Criterion (AIC).

The real-world test sequence involved a moving human arm to evaluate non-rigid motion.

For real-world testing, the authors used a 13-frame sequence of a moving human arm. This provided a complex, non-rigid motion scenario. The SLT approach identified the M2 model (translation, shear, and rotation) as the most effective for predicting motion in frames not used during the initial estimation phase.

Estimated flow vectors for the moving arm sequence, demonstrating the algorithm's ability to capture complex motion.

Conclusion

The application of Statistical Learning Theory to flow estimation offers a powerful alternative to traditional statistical methods. By leveraging VC-dimension and prediction risk, the proposed method achieves superior accuracy and robustness, particularly in small-data and high-noise environments. While the method currently assumes a closed set of motion models, its ability to handle the aperture problem and prevent overfitting makes it a significant advancement for real-time video processing and low-level vision tasks.

Summary updated

BibTeX
@inproceedings{duric2003controlling,
  author = {Zoran Duric and Fayin Li and Harry Wechsler and Vladimir Cherkassky},
  title = {{Controlling Model Complexity in Flow Estimation}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2003},
  doi = {10.1109/iccv.2003.1238445},
}
Figure