Unifying Registration based Tracking: A Case Study with Structural Similarity

Abhineet Singh, Mennatullah Siam, Martin JagersandarXiv 2016 · arXiv

TL;DR

This paper introduces a unified framework that decomposes registration-based trackers (RBTs) into three independent sub-modules: appearance models, state space models, and search methods. By adapting the popular Structural Similarity (SSIM) index and a novel pixelwise variant (SPSS) into this framework, the authors conduct a massive benchmarking study that exposes critical gaps between theoretical tracking proofs and real-world performance.

What Problem Does This Paper Address?

In computer vision, visual tracking generally splits into two paradigms: Online Learning Trackers (OLTs) and Registration-Based Trackers (RBTs). While OLTs handle drastic appearance changes well, RBTs (or direct visual trackers) are preferred in robotics and augmented reality because they offer superior pose precision and run significantly faster.

However, RBT literature has historically been fragmented. When researchers propose a new tracking component—such as a novel optimization method or a new image similarity metric—they usually test it by arbitrarily pairing it with existing components. This makes it impossible to know if a tracker performs well because of the new innovation or simply because of a lucky combination of sub-modules. The authors address this lack of systematic analysis by creating a modular framework to cleanly isolate and evaluate each component of an RBT.

Methods

The authors formalize the RBT problem as a modular triad:

  1. Appearance Model (AM): The similarity metric used to compare image patches (e.g., SSD, NCC, Mutual Information).
  2. State Space Model (SSM): The warping function defining the allowed degrees of freedom (DOF) for motion (e.g., translation, affine, homography).
  3. Search Method (SM): The optimization procedure used to find the best match (e.g., Lucas-Kanade variants, particle filters).

Using this decomposition, they adapt the Structural Similarity (SSIM) index—traditionally an image quality metric robust to illumination changes—for high-DOF gradient descent tracking by deriving its analytical Jacobians and Hessians. To combat potential computational bottlenecks, they also introduce Sum of Pixelwise Structural Similarity (SPSS), a simplified variant that discards neighborhood covariance calculations to operate strictly on a pixel-by-pixel basis.

Datasets

The unified framework was evaluated across four diverse, publicly available datasets comprising over 100,000 unique frames:

  • Tracking for Manipulation Tasks (TMT): 109 sequences (70,592 frames) capturing manipulation tasks at various speeds and lighting conditions.
  • UCSB Dataset: 96 short sequences (6,889 frames) featuring artificial but specific tracking challenges.
  • LinTrack: 3 long, realistic, and highly challenging tracking sequences (12,477 frames).
  • PAMI Planar Dataset: 28 challenging planar tracking sequences (16,511 frames).

Key Insights and Ideas

  • The Lucas-Kanade Equivalence Myth: Textbook computer vision often treats the four classic variants of the Lucas-Kanade tracker (FALK, IALK, FCLK, ICLK) as mathematically equivalent first-order approximations. This paper reveals that this equivalence completely breaks down in practice. Forward-compositional (FCLK) methods consistently outperform inverse-compositional (ICLK) methods under real-world conditions.
  • ESM is Overhyped: Efficient Second-order Minimization (ESM) is theoretically celebrated for its second-order convergence rate. However, empirical testing shows it rarely outperforms the simpler FCLK method, except when paired with specific appearance models like SCV.
  • Stochastic-Gradient Hybrids Win: Purely stochastic search methods (like Particle Filters) suffer from high jitter. However, composite methods that use a stochastic search to initialize a gradient descent refiner (e.g., PFFC) yield the highest overall tracking success rates.

Key Results

  • Top-Tier Metrics: Normalized Cross-Correlation (NCC) and the newly adapted SSIM emerged as the most robust appearance models across almost all optimization methods, as seen in the success rate curves across different search methods.
Figure 1: Success rates for AMs using different SMs with Homography as well as for different SSMs using SSIM with ESM (bottom right). Plot legends indicate areas under the respective curves. Best viewed on a high resolution screen.
  • The SPSS Speed Paradox: Although SPSS has lower theoretical computational complexity than SSIM, it did not provide a significant real-world speedup. This is because SSIM's matrix operations are highly optimized by modern linear algebra libraries (like Eigen), and SSIM typically requires fewer iterations to converge.
Figure 2: Speeds of ESM and PF with homography. Solid and dotted lines show the means and standard deviations respectively.
  • RBT vs. OLT Speed: When comparing low-DOF RBTs against state-of-the-art OLTs (like DSST, KCF, and Struck), RBTs proved to be 10 to 30 times faster, frequently tracking at thousands of frames per second (FPS), while maintaining competitive precision.
Figure 3: Success Rates for SSIM using translation as well as for 8 OLTs. The former are shown with solid lines and the latter in dashed lines. The speed plot on the right has logarithmic scaling on the x axis for clarity though actual figures are also shown.

Limitations and Future Work

While the modular framework is highly effective, the authors note that their current implementations of stochastic search methods (Particle Filters and RANSAC) are not yet fully optimized for speed within their open-source framework. Additionally, because the benchmarks used in this study focused entirely on rigid objects, more complex, non-rigid state space models (such as thin-plate splines) were left unexplored. Extending this systematic decomposition to non-rigid tracking remains an open direction for future research.

Summary updated

Abstract

This paper adapts a popular image quality measure called structural similarity for high precision registration based tracking while also introducing a simpler and faster variant of the same. Further, these are evaluated comprehensively against existing measures using a unified approach to study registration based trackers that decomposes them into three constituent sub modules - appearance model, state space model and search method. Several popular trackers in literature are broken down using this method so that their contributions - as of this paper - are shown to be limited to only one or two of these submodules. An open source tracking framework is made available that follows this decomposition closely through extensive use of generic programming. It is used to perform all experiments on four publicly available datasets so the results are easily reproducible. This framework provides a convenient interface to plug in a new method for any sub module and combine it with existing methods for the other two. It can also serve as a fast and flexible solution for practical tracking needs due to its highly efficient implementation.
BibTeX
@misc{singh2016unifying,
  author = {Abhineet Singh and Mennatullah Siam and Martin Jagersand},
  title = {{Unifying Registration based Tracking: A Case Study with Structural Similarity}},
  year = {2016},
  eprint = {1607.04673},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1607.04673},
}
Figure