Aggregation of Binary Feature Descriptors for Compact Scene Model Representation in Large Scale Structure-from-Motion Applications

Jacek Komorowski, Tomasz Trzcinski

TL;DR

This paper introduces a method to drastically compress 3D scene models in Structure-from-Motion (SfM) by aggregating multiple binary feature descriptors into a single, low-dimensional "prototype" vector. By using neural network embeddings, the authors achieve significant memory savings while maintaining high matching accuracy, making large-scale mapping much more feasible for resource-constrained mobile devices.

What Problem Does This Paper Address?

In large-scale Structure-from-Motion (SfM) and SLAM (Simultaneous Localization and Mapping), systems build 3D models by detecting "landmarks" across thousands of images. To recognize these landmarks later (for loop closure or localization), the system usually stores a list of every feature descriptor (like SIFT or FREAK) ever associated with that point.

When you scale this up to millions of points, the memory requirements explode. While binary descriptors (like FREAK) are popular because they are fast and compact, they present a unique challenge: you can't easily "average" them. A simple bit-wise average followed by thresholding (a "quantized mean") doesn't allow for incremental updates as new data arrives—once you discard the original descriptors, you lose the "voting history" needed to update the mean correctly. This paper seeks a way to represent many descriptors as one compact, updatable "prototype" without losing the ability to match them accurately.

Methods

The authors propose using a neural network to transform high-dimensional binary descriptors into a low-dimensional, real-valued embedding space.

  1. Embedding: A neural network $f(x)$ maps a 512-bit binary descriptor (FREAK) to a $k$-dimensional real-valued vector (where $k$ is small, like 16 or 32).
  2. Aggregation: For a specific 3D landmark, the "prototype" is simply the arithmetic mean of the embeddings of all descriptors linked to it.
  3. Incremental Updates: Because the prototype is real-valued, it can be updated using a simple weighted average formula whenever a new frame provides a new descriptor for that landmark.
  4. Matching: When a new image is processed, its descriptors are embedded using the same network and then matched against the stored prototypes using standard Euclidean distance. This allows the use of efficient libraries like FLANN for fast approximate nearest neighbor searches.

The researchers compared two training strategies: Triplet Networks (which learn to push different classes apart and pull similar ones together) and Prototypical Networks (which explicitly optimize for a prototype-based classification space).

Datasets

The experiments utilized data captured via a Google Tango tablet, which provides built-in SfM capabilities.

  • Training Set: Over 4 million FREAK descriptors from ~10,000 keyframes.
  • Validation/Test Sets: Approximately 2 million descriptors each from ~5,000 keyframes.
  • Ground Truth: Camera poses and sparse 3D point clouds reconstructed using reliable, standard SfM methods served as the baseline for "correct" matches.

Key Insights and Ideas

  • Triplet Loss Wins: Surprisingly, Triplet Networks consistently outperformed Prototypical Networks for this task, despite the latter being specifically designed for prototype-based learning.
  • Shallow is Sufficient: The best results came from relatively shallow, three-layer fully connected networks. Deeper architectures didn't provide a significant performance boost.
  • The "Funnel" vs. "Fat" Architecture: The authors tested "fat" networks (constant width) and "funnel" networks (decreasing width). Both performed similarly when trained with Triplet loss, suggesting the embedding quality is robust to the specific layer configuration.
  • Real-Valued Flexibility: By moving from binary space to a real-valued embedding space, the system gains the ability to use more sophisticated matching algorithms that don't work well with Hamming distance (the standard for binary data).

Key Results

The proposed method offers a compelling trade-off between memory and precision:

Method NN Search Precision
Unaggregated descriptors (Baseline) 0.796
32-dimensional prototypes (Proposed) 0.750
16-dimensional prototypes (Proposed) 0.676
Quantized mean (512 bits) 0.671
Mean of PCA projection (16 dims) 0.581
Random sample (512 bits) 0.526

Memory Savings: A 32-dimensional prototype (using 4-byte floats) takes up about as much space as two 512-bit FREAK descriptors. Since landmarks in practical applications often have between 3 and 15 descriptors associated with them, this represents a massive reduction in the memory footprint of the 3D model.

Limitations and Future Work

  • Initialization Period: The authors note that in practice, you still need to store raw descriptors for the first few frames to allow for initial triangulation and landmark construction before switching to the prototype model.
  • Missing Metadata: Currently, the network only looks at the descriptor itself. The authors suggest that incorporating keypoint metadata—such as the scale and orientation estimated by the detector—could make the prototypes even more discriminative.
  • Hardware Constraints: While the final prototypes are compact, the process requires running a neural network inference for every detected keypoint, which adds a computational overhead during the "front-end" processing of each frame.

Summary updated

Abstract

In this paper we present an efficient method for aggregating binary feature descriptors to allow compact representation of 3D scene model in incremental structure-from-motion and SLAM applications. All feature descriptors linked with one 3D scene point or landmark are represented by a single low-dimensional real-valued vector called a prototype. The method allows significant reduction of memory required to store and process feature descriptors in large-scale structure-from-motion applications. An efficient approximate nearest neighbours search methods suited for real-valued descriptors, such as FLANN [19], can be used on the resulting prototypes to speed up matching processed frames.
BibTeX
@inproceedings{komorowski2018aggregation,
  author = {Jacek Komorowski and Tomasz Trzcinski},
  title = {{Aggregation of Binary Feature Descriptors for Compact Scene Model Representation in Large Scale Structure-from-Motion Applications}},
  booktitle = {ICCVG},
  year = {2018},
  url = {https://openreview.net/forum?id=cL76kPRTIPG},
}

Loading related content...

Figure