PaperlayerView exact revision on arXiv

Source-linked AI summary

High-Speed Tracking with Kernelized Correlation Filters

João F. Henriques, Rui Caseiro, Pedro Martins, Jorge Batista

arXiv:1404.7584v3cs.CV

TL;DR

Tracking must learn from vast numbers of environmental samples while remaining fast. The paper models translated patches as circulant matrices, diagonalizes them with the DFT, and derives KCF and DCF. On a 50-video benchmark, both outperform top-ranking trackers while running at hundreds of frames-per-second.

  • Problem

    Trackers face virtually unlimited negative samples, while Fourier-domain methods limit access to powerful features and kernel methods.

  • Method

    The paper models translated samples with circulant matrices, diagonalizes them using the DFT, and develops KCF plus a multi-channel linear-kernel DCF.

  • Results

    KCF and DCF outperform top-ranking trackers such as Struck and TLD on a 50-video benchmark while running at hundreds of frames-per-second.

  • Takeaways & Limitations

    The framework provides fast linear and kernel ridge-regression trackers that incorporate thousands of translated samples and support multiple feature channels.

  • Takeaways & Limitations

    The fast kernel approach requires kernel values to remain unchanged under unitary transformations; other kernels need more expensive sliding-window correlation.

Abstract

from arXiv · show

The core component of most modern trackers is a discriminative classifier, tasked with distinguishing between the target and the surrounding environment. To cope with natural image changes, this classifier is typically trained with translated and scaled sample patches. Such sets of samples are riddled with redundancies -- any overlapping pixels are constrained to be the same. Based on this simple observation, we propose an analytic model for datasets of thousands of translated patches. By showing that the resulting data matrix is circulant, we can diagonalize it with the Discrete Fourier Transform, reducing both storage and computation by several orders of magnitude. Interestingly, for linear regression our formulation is equivalent to a correlation filter, used by some of the fastest competitive trackers. For kernel regression, however, we derive a new Kernelized Correlation Filter (KCF), that unlike other kernel algorithms has the exact same complexity as its linear counterpart. Building on it, we also propose a fast multi-channel extension of linear correlation filters, via a linear kernel, which we call Dual Correlation Filter (DCF). Both KCF and DCF outperform top-ranking trackers such as Struck or TLD on a 50 videos benchmark, despite running at hundreds of frames-per-second, and being implemented in a few lines of code (Algorithm 1). To encourage further developments, our tracking framework was made open-source.

1 INTRODUCTION

Modern trackers learn discriminative classifiers from target and environmental patches, but the virtually unlimited negative samples create a tension between coverage and computational cost. The paper addresses this by analytically incorporating thousands of translated samples without explicitly iterating over them.

  • Tracking learns a classifier that distinguishes the target from its environment and evaluates it across many locations in subsequent frames.
  • Negative patches from different locations and scales are important because the classifier is evaluated under those conditions.
  • The virtually unlimited negative samples force trackers to balance incorporating many examples against keeping computation low, so they commonly retain only a few per frame.
  • The paper argues that undersampling negatives is the main factor inhibiting tracking performance.
  • Circulant-matrix tools enable analytical incorporation of thousands of translated samples without explicitly iterating over them.
  • The framework applies Kernel Ridge Regression at the same computational complexity as linear correlation filters and extends linear filters to multiple feature channels.

2 RELATED WORK

Related work frames tracking as online discriminative learning and contrasts Fourier-efficient correlation filters with methods that reduce candidate or training samples. The paper seeks to retain Fourier efficiency while supporting richer features and kernel methods.

  • 2.1 On tracking-by-detection: Tracking-by-detection trains an appearance classifier online and tests candidate patches to locate the target.
  • 2.1 On tracking-by-detection: Many alternative approaches reduce computation by selecting promising detections or training samples, but may require exhaustive worst-case search, expensive processing, or careful heuristic tuning.
  • 2.2 On sample translations and correlation filtering: Correlation filters achieve competitive tracking at hundreds of frames-per-second by exploiting Fourier-domain convolution and element-wise multiplication.
  • 2.2 On sample translations and correlation filtering: Fourier-domain formulations are efficient but can limit the use of powerful features, large-margin classifiers, and kernel methods.
  • 2.2 On sample translations and correlation filtering: Earlier kernelized correlation-filter work distinguished objectives with and without translation structure, while this paper motivates a deeper connection between translated patches and training algorithms.
  • 2.2 On sample translations and correlation filtering: Subsequent multi-channel correlation-filter extensions enable modern features such as HOG, building on the paper’s initial work.

3 CONTRIBUTIONS

The paper extends its initial cyclic-shift framework with simpler derivations, multi-channel support, broader experiments, and HOG-based variants. Its KCF and DCF trackers combine strong performance with very low computational cost.

  • The initial work connected ridge regression on cyclically shifted samples with classical correlation filters, enabling O(n log n) FFT-based learning instead of expensive matrix algebra.
  • The present work re-derives the results more simply, adds multi-channel features, expands experiments from 12 to 50 videos, and introduces an HOG-based KCF variant.
  • With HOG features, linear DCF and nonlinear KCF outperform top-ranking trackers such as Struck and TLD while running at hundreds of frames-per-second.

4 BUILDING BLOCKS

The section models translated training patches with cyclic shifts, making the resulting data matrix circulant and Fourier-diagonalizable. This converts ridge regression into an efficient correlation-filter formulation with nearly linear complexity, while noting assumptions and boundary artifacts.

  • 4.2 Cyclic shifts: Cyclic shifts model translations efficiently, but wrap-around distorts boundary elements and requires padding and windowing to mitigate artifacts.The formulation can include all vertical and horizontal cyclic shifts without explicitly iterating through them.
  • 4.2 Cyclic shifts: Cyclically shifted training samples form a circulant data matrix whose structure is fully specified by the generating vector.The rows represent translations of a base sample, with cyclic wrapping producing the circulant pattern.
  • 4.3 Circulant matrices: The DFT diagonalizes every circulant matrix, allowing matrix operations to be performed element-wise in the Fourier domain.The DFT matrix is fixed across generating vectors, and the resulting diagonal structure supports closed-form manipulation.
  • 4.4 Putting it all together: Applying Fourier diagonalization to ridge regression yields a regularized correlation filter with element-wise operations and O(n log n) cost.The inverse DFT recovers the spatial-domain solution, while the Fourier transforms dominate the nearly linear computational cost.
  • 4.5 Relationship to correlation filters: The resulting formulation reduces storage and computation by several orders of magnitude compared with unstructured linear regression.The comparison treats samples and features as the same quantity because the data matrix is square.
  • 4.5 Relationship to correlation filters: The analysis provides tools for extending Fourier-domain correlation-filter methods to more complicated algorithms, including non-linear filters.The section presents circulant matrices as a bridge between classical signal processing and modern learning algorithms.

5 NON-LINEAR REGRESSION

The paper uses the kernel trick with circulant translated-patch data to retain nonlinear regression while avoiding the usual sample-dependent computational burden. This structure enables fast training and full detection over cyclic shifts.

  • 5 NON-LINEAR REGRESSION: Circulant analysis lets kernel ridge regression avoid the usual kernelization complexity and match the speed of linear correlation filters for training and evaluation.This connects nonlinear kernel regression to the fast correlation-filter formulation.
  • 5 NON-LINEAR REGRESSION: The kernel trick replaces primal weights with dual coefficients and computes feature-space dot-products through a kernel function.Kernel methods implicitly use high-dimensional features without explicitly constructing them.
  • 5 NON-LINEAR REGRESSION: Circulant kernel matrices preserve Fourier diagonalization when kernels treat all dimensions equally, including Gaussian, linear, polynomial, and additive kernels.The required condition is κ(x, x′) = κ(Mx, Mx′) for any permutation matrix M.
  • 5 NON-LINEAR REGRESSION: Using circulant structure, KCF needs only an n × 1 kernel auto-correlation vector instead of the conventional n × n kernel matrix, reducing scaling from quadratic to linear in samples.The exact structure of K permits element-wise Fourier-domain operations rather than a generic kernel algorithm.
  • 5 NON-LINEAR REGRESSION: For cyclically shifted candidate patches, the regression output is a full detection-response vector computed by Fourier-domain filtering of kernel correlations.The response contains outputs for all cyclic shifts of the candidate patch.

6 FAST KERNEL CORRELATION

The remaining bottleneck is computing kernel correlations across all relative shifts. For dot-product and Gaussian kernels, Fourier-domain formulations reduce this operation to O(n log n) time, while other kernels may require sliding-window evaluation.

  • 6 FAST KERNEL CORRELATION: Kernel correlation is the last bottleneck because naively evaluating n kernels for signals of size n has quadratic complexity.The cyclic-shift model exposes redundancy that can be exploited computationally.
  • 6 FAST KERNEL CORRELATION: O(n log n) time computes full kernel correlations for dot-product kernels using a few DFT, inverse DFT, and element-wise operations.The formulation diagonalizes the vector of kernel values across all relative shifts.
  • 6 FAST KERNEL CORRELATION: O(n log n) time also computes full kernel correlations for Gaussian kernels because their distance-based form reduces to a dot-product kernel.Parseval’s theorem makes the norms invariant under cyclic permutation, enabling the same Fourier-domain method.
  • 6 FAST KERNEL CORRELATION: The fast correlation method does not apply to every kernel: kernels whose values are not preserved by unitary transformations may require a more expensive sliding-window method.Fast training and detection remain available, but kernel-correlation evaluation becomes slower for such kernels.

7 MULTIPLE CHANNELS

The dual formulation supports multiple feature channels by summing their Fourier-domain correlations, yielding the Dual Correlation Filter for linear kernels. This provides element-wise multi-channel training under a specific data configuration.

  • 7 MULTIPLE CHANNELS: Multiple channels can be integrated by summing channel-wise kernel correlations in the Fourier domain, without making inference more difficult.The formulation supports features such as 31 HOG orientation bins.
  • 7 MULTIPLE CHANNELS: The linear multi-channel formulation is called the Dual Correlation Filter, or DCF, because it trains a linear classifier in the dual space.With a linear kernel, the channel combination reduces to element-wise operations.
  • 7 MULTIPLE CHANNELS: Earlier multi-channel correlation filters use more expensive matrix inversions, whereas the dual linear-kernel formulation uses only element-wise operations.This difference follows from using one base sample, whose n × n kernel matrix is diagonalizable by the n-point DFT basis.
  • 7 MULTIPLE CHANNELS: For fast element-wise operations, the method can support multiple channels in the dual or multiple base samples in the primal, but not both simultaneously.The general multi-base-sample, multi-channel case requires more expensive computation and is mainly suited to offline training.

8 EXPERIMENTS

The experiments evaluate KCF and DCF on 50 videos using raw-pixel and HOG variants, precision curves, and speed measurements. HOG variants outperform top-ranking trackers, while the methods retain high speed and show robustness across several sequence attributes.

  • 8.3 Experiments on the full dataset: KCF achieves competitive raw-pixel performance, while its Gaussian kernel gives a distinct advantage over DCF.The raw-pixel KCF also yields a noticeable increase over the corresponding linear-filter results.
  • 8.3 Experiments on the full dataset: With HOG features, KCF and DCF surpass TLD and Struck by a relatively large margin.The comparison uses precision results over the 50-video benchmark.
  • 8.3 Experiments on the full dataset: The closed-form solutions have O(n log n) complexity, supporting tracker speeds of hundreds of frames per second.Reported timing includes feature computation, including HOG.
  • 8.3 Experiments on the full dataset: KCF and DCF process all 50 videos, approximately 29,000 frames, in less than 2 minutes on four desktop CPU cores.The implementation tracks a region 2.5 times larger than the target on average, and reducing it would improve speed but hurt performance.
  • 8.4 Experiments with sequence attributes: HOG variants are robust to non-rigid deformation and occlusion, while raw-pixel KCF performs almost as well as Struck and TLD.The Gaussian kernel compensates for shortcomings of raw-pixel features in this comparison.
  • 8.4 Experiments with sequence attributes: Out-of-view targets challenge the tracker because it lacks a failure-recovery mechanism, although KCF and DCF still outperform TLD in this setting.TLD performs better than most other trackers for this attribute because it emphasizes re-detection and failure recovery.
  • 8.4 Experiments with sequence attributes: The proposed trackers are generally the most robust to six of seven reported challenges, except low resolution.Background clutter affects almost all other trackers severely, whereas the proposed variants remain near optimal even with raw pixels.

9 CONCLUSIONS AND FUTURE WORK

The paper models translated samples analytically so that data and kernel matrices become circulant and can be diagonalized by the DFT. This yields fast linear and kernel ridge-regression trackers while identifying extensions and assumptions for future work.

  • 9 CONCLUSIONS AND FUTURE WORK: Under some conditions, translated-image data and kernel matrices become circulant and can be diagonalized by the DFT.The resulting blueprint supports algorithms that handle translations efficiently.
  • 9 CONCLUSIONS AND FUTURE WORK: The framework produces state-of-the-art trackers that run at hundreds of frames per second and require only a few lines of code.The paper applies the approach to linear and kernel ridge regression.
  • 9 CONCLUSIONS AND FUTURE WORK: Future work includes relaxing periodic-boundary assumptions and extending the framework to other objectives, operators, and more robust loss functions.Suggested operators include affine transformations and non-rigid deformations.

A.1 Implementation details

The implementation uses cosine-windowed patches, Gaussian regression targets, and Fourier-domain conventions tailored to cyclically shifted training samples. These choices provide context, smooth targets, and correct spatial alignment for the correlation-filter pipeline.

  • A.1 Implementation details: The tracked region is 2.5 times the target size, providing context and additional negative samples.Input patches are weighted by a cosine window to reduce boundary discontinuities from the cyclic assumption.
  • A.1 Implementation details: Gaussian regression targets peak at one for the centered target and smoothly decay toward zero for other shifts.Their smoothness reduces ringing artifacts in the Fourier domain compared with binary labels.
  • A.1 Implementation details: Experiments use fixed parameters where n and m denote target width and height measured in pixels or HOG cells.The parameter table covers the settings used across the experiments.
  • A.1 Implementation details: The centered Gaussian target is placed at the top-left output element because Fourier-domain cross-correlation returns that alignment there.This differs from the intuitive choice of the output-plane center.
  • A.1 Implementation details: The implementation must account for non-unitary FFT scaling because the standard transform does not preserve signal L2 norms.The paper introduces a correction factor when expressing the unitary DFT.

A.2 Proof of Theorem 1

The derivations exploit circulant structure and Fourier diagonalization to reduce regression and kernel-regression computations to element-wise operations. The same approach extends to multiple cyclically shifted samples and multi-channel filters.

  • Regression-target placement: The regression target’s Gaussian peak belongs at the top-left element because that location represents zero shift after Fourier-domain cross-correlation.Wrapping the target around preserves the centered detection output, whereas centering the peak in the output plane shifts detection by half a window.
  • Proof of Theorem 1: Circulant matrices are characterized by entries depending only on (j −i) mod n, and the kernel matrix K is circulant under the theorem’s permutation-invariance assumption.The proof uses the cyclic permutation matrix and its periodic powers to establish this dependence.
  • Kernel regression derivation: Fourier diagonalization converts kernel ridge regression into element-wise products after substituting the circulant kernel matrix and using the unitarity of F.The derivation proceeds from K = C(kxx) and simplifies products involving diagonal matrices.
  • Linear regression derivation: The linear ridge-regression derivation follows the same Fourier-domain simplification, replacing matrix algebra with diagonal and element-wise operations.The text explicitly parallels the kernel derivation and invokes the unitarity of F.
  • Multi-sample and multi-channel extension: The single-sample formulation differs from MOSSE because MOSSE minimizes error over cyclic shifts of multiple base samples, while the dual formulation supports multiple channels.The multi-sample extension represents each set of cyclic shifts with a circulant matrix and then applies the same diagonalization steps.
Loading 1404.7584v3…