FFD: Fast Feature Detector

Morteza Ghahremani, Yonghuai Liu, Bernard Tiddeman

Abstract

Scale-invariance, good localization, and robustness to noise are essential for local feature detectors. However, many existing methods detect unstable keypoints that hinder matching performance and increase computational overhead. This paper introduces FFD (Fast Feature Detector), which identifies robust keypoints in a specific scale-space domain. By mathematically modeling the "superimposition problem" using Difference-of-Gaussian (DoG) kernels, we derive optimal scale-space parameters ($\mu=2, \sigma=0.627$) that ensure reliable detection. FFD utilizes the undecimated wavelet transform and cubic spline functions for efficient discretization. Theoretically, FFD’s complexity is less than 5% of SIFT. Experimental results demonstrate that FFD outperforms both traditional and learning-based techniques in accuracy and speed across tasks like 3D reconstruction and visual localization.

Introduction: The Superimposition Problem

Feature detection is a cornerstone of computer vision, yet even standard algorithms like SIFT often produce "unstable" keypoints. These instabilities frequently stem from superimposition—a phenomenon where the mathematical responses of two adjacent edges or textures merge in the scale-space. This merging creates phantom features or significantly shifts the detected location of real features, leading to downstream errors.

Visualizing the superimposition problem: as edges get closer relative to the kernel width (d < ωD), their responses merge and displace the detected feature location.

FFD addresses this by formulating a mathematical model for multiscale analysis that explicitly accounts for and mitigates superimposition.

Methodology

The FFD algorithm rethinks the Difference-of-Gaussian (DoG) approach through theoretical optimization and architectural efficiency.

Optimal Scale-Space Parameters

The authors identified "golden values" for the scale-space pyramid: a blurring ratio ($\mu$) of 2 and a smoothness ($\sigma$) of 0.627. These values are derived from a closed-form solution that guarantees nearby edges will not interfere with each other, thereby suppressing the detection of unstable artifacts.

Zero-crossing error analysis for different values of μ and λ, demonstrating how the error behaves as parameters change.

Fast and Accurate Discretization

To maintain high performance on discrete images, FFD incorporates:

  • Undecimated Wavelet Transform (UWT): By upscaling the filter kernel rather than downsampling the image (the "algorithme à trous"), FFD preserves full image resolution across all scales, leading to superior sub-pixel localization.
  • Cubic Spline Kernels: Replacing standard Gaussians with cubic spline functions allows for a high-quality approximation that is computationally inexpensive.
  • Anisotropy-Based Suppression: An anisotropy metric derived from the Hessian matrix's eigenvalues is used to filter out simple edges, ensuring only stable conjunctions (like corners) are kept.

Evaluation and Results

FFD was evaluated against a suite of traditional and deep-learning-based detectors (e.g., SIFT, SURF, SuperPoint, D2Net) on standard benchmarks for repeatability, visual localization, and 3D reconstruction.

Computational Efficiency

Theoretically, FFD's complexity is less than 5% of SIFT. In practice, it processes an 800x640 image in just 29ms on a CPU, compared to 552ms for SIFT and 438ms for AKAZE.

Robustness and Accuracy

  • Visual Localization: On the Aachen Day-Night dataset, FFD achieved 44.9% accuracy at the strictest threshold, surpassing both SIFT (42.9%) and SuperPoint (40.8%).
  • 3D Reconstruction: FFD consistently produced the most registered images and densest point clouds across five diverse datasets (e.g., Fountain, Madrid Metropolis), proving its reliability for high-precision mapping.

Conclusion

FFD demonstrates that rigorous geometric modeling can still outperform data-driven approaches in precision-critical tasks. Its combination of theoretical grounding and extreme speed makes it an ideal candidate for real-time applications on resource-constrained devices, such as drones and mobile AR systems.

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~{\url{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},
}
Figure