FFD: Fast Feature Detector

Morteza Ghahremani, Yonghuai Liu, Bernard Tiddeman

TL;DR

FFD (Fast Feature Detector) is a mathematically optimized multiscale feature detector that is roughly 20x faster than SIFT while producing more reliable keypoints. By using undecimated wavelets and "golden" scale-space parameters, it significantly improves performance in 3D reconstruction and visual localization tasks compared to both traditional and deep-learning-based methods.

What Problem Does This Paper Address?

In computer vision, "feature detection" is the first step for tasks like stitching panoramas or navigating self-driving cars. While the classic SIFT (Scale-Invariant Feature Transform) algorithm has been the gold standard for decades, it has two major drawbacks: it is computationally expensive, and it often detects "unstable" keypoints.

These unstable points often arise from superimposition—when two edges or textures are so close that their mathematical responses merge into a single, poorly localized "blob." This leads to mismatches and errors in downstream tasks. FFD aims to solve this by creating a detector that is both theoretically grounded to avoid superimposition and architecturally designed for extreme speed.

Methods

The authors rethink the standard "Difference-of-Gaussian" (DoG) approach used by SIFT through several novel steps:

  • Mathematical Optimization of Scale-Space: Instead of using empirical values, the authors derived a closed-form solution to determine the ideal blurring ratio ($\mu$) and smoothness ($\sigma$). They identified "golden values" ($\mu=2, \sigma=0.627$) that theoretically guarantee that nearby edges will not interfere with each other, preventing the detection of phantom or shifted features.
  • Undecimated Wavelet Transform (UWT): Most detectors (like SIFT) downsample the image to create a scale pyramid. FFD instead upscales the filter kernel using the "algorithme à trous." This preserves the original image resolution across all scales, leading to much better sub-pixel localization.
  • Cubic Spline Kernels: To make the algorithm fast, they replace standard Gaussian filters with cubic spline functions, which are computationally efficient and provide a high-quality discrete approximation of the Gaussian.
  • Anisotropy-Based Suppression: To ensure they only keep high-quality "conjunctions" (corners or blobs) and ignore simple edges, they use an anisotropy metric derived from the Hessian matrix's eigenvalues.

Datasets

The authors evaluated FFD across a wide range of standard benchmarks:

  • Repeatability & Stability: Hannover, Webcam, VGG Affine, Edge Foci, and HSequences.
  • Visual Localization: The Aachen Day-Night dataset (challenging real-world localization).
  • 3D Reconstruction: Five diverse datasets including Fountain, Herzjesu, Madrid Metropolis, Gendarmenmarkt, and Tower of London.
  • Competitors: Compared against traditional methods (SIFT, SURF, KAZE, BRISK) and modern deep learning methods (SuperPoint, LIFT, D2Net, TILDE).

Key Insights and Ideas

  • The 5% Complexity Rule: Theoretically, FFD’s computational complexity is less than 5% of SIFT. This is achieved by avoiding the costly image resizing operations and using separable, efficient spline filters.
  • Resolution Matters: By using an undecimated pyramid, FFD avoids the interpolation errors that plague other detectors when they try to find sub-pixel coordinates on downsampled images.
  • Hand-crafted vs. Learned: Interestingly, FFD (a hand-crafted geometric approach) often outperformed state-of-the-art deep learning detectors in 3D reconstruction. This suggests that rigorous geometric modeling can still beat data-driven approaches in tasks requiring high precision.
  • Superimposition is the "Silent Killer": The paper highlights that many "false" features in other detectors aren't just noise; they are predictable mathematical artifacts of the scale-space itself. By tuning the kernel parameters to $\mu=2$, these artifacts are naturally suppressed.

Key Results

  • Speed: FFD processes an 800x640 image in just 29ms on a CPU. For comparison, SIFT takes 552ms, and KAZE takes 1500ms. Even the "fast" AKAZE takes 438ms.
  • Visual Localization: On the Aachen dataset, FFD achieved the highest accuracy (44.9% at the strictest threshold), outperforming SuperPoint (40.8%) and SIFT (42.9%).
  • 3D Reconstruction: FFD consistently produced the most "registered" images and the densest point clouds across all five test datasets, proving its reliability for mapping and modeling.

Limitations and Future Work

  • Descriptor Dependency: FFD is strictly a detector. For the experiments, the authors paired it with the HardNet++ descriptor. Its performance in a full pipeline depends on the choice of descriptor.
  • Viewpoint Extremes: While FFD handles viewpoint changes well, it is not explicitly "affine-invariant" in the way specialized (but much slower) detectors like ASIFT are.
  • Future Directions: The authors suggest that FFD’s speed makes it an ideal candidate for real-time applications on mobile devices or embedded systems, such as drone navigation or mobile AR, where SIFT is currently too slow.

Summary updated

Abstract

Scale-invariance, good localization and robustness to noise and distortions are the main properties that a local feature detector should possess. Most existing local feature detectors find excessive unstable feature points that increase the number of keypoints to be matched and the computational time of the matching step. In this paper, we show that robust and accurate keypoints exist in the specific scale-space domain. To this end, we first formulate the superimposition problem into a mathematical model and then derive a closed-form solution for multiscale analysis. The model is formulated via difference-of-Gaussian (DoG) kernels in the continuous scale-space domain, and it is proved that setting the scale-space pyramid's blurring ratio and smoothness to 2 and 0.627, respectively, facilitates the detection of reliable keypoints. For the applicability of the proposed model to discrete images, we discretize it using the undecimated wavelet transform and the cubic spline function. Theoretically, the complexity of our method is less than 5% of that of the popular baseline Scale Invariant Feature Transform (SIFT). Extensive experimental results show the superiority of the proposed feature detector over the existing representative hand-crafted and learning-based techniques in accuracy and computational time. The code and supplementary materials can be found at https://github.com/mogvision/FFD.
BibTeX
@article{ghahremani2021ffd,
  author = {Morteza Ghahremani and Yonghuai Liu and Bernard Tiddeman},
  title = {{FFD: Fast Feature Detector}},
  journal = {IEEE Trans. Image Process.},
  year = {2021},
  url = {https://openreview.net/forum?id=6i-rXyxNAUc},
}

Loading related content...

Figure