A Parallel Feature Tracker for Extended Image Sequences

Sing Bing Kang, Richard Szeliski, Heung-Yeung ShumCVIU 1997 · DOI

TL;DR

This paper introduces a novel parallel feature tracker designed for long image sequences. By modeling local patch deformations with splines and enabling patches to share information, the tracker achieves greater stability and robustness to non-translational motions and foreshortening effects compared to existing methods.

What Problem Does This Paper Address?

Tracking features across extended image sequences is crucial for many computer vision tasks, such as structure from motion, object tracking, and surveillance. A key challenge is maintaining accurate and stable tracks despite significant object or camera motion, which can lead to substantial image deformations, including foreshortening. Existing methods often struggle with these complex deformations, leading to track drift and loss. Furthermore, efficiently processing long sequences requires robust and computationally feasible algorithms.

Methods

The core of the proposed method is a spline-based image registration technique. Instead of treating each pixel's motion independently, the authors model the motion field using two-dimensional splines. This approach has several advantages:

  • Shared Information: Adjacent image patches share common spline control nodes, which allows them to exchange information. This sharing leads to more stable estimates, especially at the boundaries of patches.
  • Bilinear Deformations: The spline model allows for more complex, bilinear deformations of image patches, making it capable of handling significant non-translational motions and foreshortening effects that simpler affine models cannot.
  • Hierarchical Approach: To handle large displacements, the algorithm employs a coarse-to-fine strategy using a Gaussian image pyramid. This allows for efficient processing of large motions by starting with a low-resolution representation and progressively refining the estimates.
  • Confidence Measures: Feature tracks are assigned confidence values based on the local Hessian matrix and the summed squared error within each patch. This allows for the selection of reliable features and the termination of tracks that become occluded or exhibit significant errors.

Datasets

The paper evaluates the proposed tracker on several synthetic sequences:

  • Translating tree sequence
  • Diverging tree sequence
  • Diverging tree sequence with added Gaussian noise
  • Rotating tree sequence
  • Diverging Yosemite sequence
  • Rayshade generated sequence (a synthetic sequence created using ray-tracing)

Additionally, a real image sequence of a rotating cube is used to demonstrate the recovery of 3D structure.

Key Insights and Ideas

  • Stability through Shared Nodes: The key insight is that by making image patches share spline control nodes, the system gains a form of "regularization" that significantly improves tracking stability, preventing the kind of drift seen in independent patch trackers.
  • Bilinear Deformations are Crucial: For long sequences with significant motion, simple translational or even affine models are insufficient. The ability to model bilinear deformations is essential for accurately tracking features under foreshortening and complex perspective changes.
  • Hierarchical Processing is Efficient: The coarse-to-fine approach is vital for making the dense registration computationally tractable for large displacements, a common scenario in long image sequences.
  • Confidence-Based Feature Selection: Using Hessian eigenvalues and patch error as confidence measures provides a principled way to select good features and discard unreliable tracks, which is critical for long-term tracking.

Key Results

The proposed spline-based tracker consistently outperforms the Shi-Tomasi tracker (a well-regarded feature tracker) in terms of lower pixel error accumulation across various synthetic sequences.

  • Reduced Drift: Unlike the Shi-Tomasi tracker, which exhibits significant drift over time, the spline-based tracker maintains a more constant error, indicating better stability. This is attributed to the tracker matching to the first frame and avoiding cumulative errors.
  • Robustness to Noise: Both the proposed tracker and the Shi-Tomasi tracker show good robustness to additive Gaussian noise.
  • Improved 3D Structure Recovery: When applied to a real rotating cube sequence, the spline-based tracker produces less noisy 3D structure estimates compared to the Shi-Tomasi tracker.

Limitations and Future Work

  • Occlusions: The current algorithm does not explicitly handle occlusions. The authors suggest future work to incorporate occlusion detection and handling, possibly by detecting "foldovers" or using non-quadratic matching criteria.
  • Adaptive Patch Sizes: While the current spline model uses a fixed grid, the authors mention the potential benefit of adaptively sized patches for improved matching quality. This would require a more complex tessellation strategy, potentially using quadtree splines.
  • Local Minima: The gradient descent optimization can get trapped in local minima. The authors propose an optional exhaustive search component to mitigate this, but note that maintaining spline continuity complicates this process.

Summary updated

BibTeX
@article{kang1997parallel,
  author = {Sing Bing Kang and Richard Szeliski and Heung-Yeung Shum},
  title = {{A Parallel Feature Tracker for Extended Image Sequences}},
  journal = {Comput. Vis. Image Underst.},
  year = {1997},
  doi = {10.1006/cviu.1996.0519},
}
Figure