Abstract
In this paper, we evaluate the performance of data-dependent hashing methods on binary data. The primary objective is to identify a hashing method capable of effectively producing lower-dimensional binary representations of 512-bit FREAK descriptors. A representative sample of recent unsupervised, semi-supervised, and supervised hashing methods was experimentally evaluated on large datasets of labeled binary FREAK feature descriptors.
Introduction
In computer vision applications such as Structure-from-Motion (SfM), matching thousands of local features across millions of images represents a significant computational bottleneck, particularly on mobile devices with constrained hardware. Binary descriptors like FREAK are widely adopted due to their compactness and the efficiency of Hamming distance comparisons. However, as datasets scale, even 512-bit descriptors can become computationally burdensome.
While hashing is a well-established technique for mapping high-dimensional real-valued descriptors (e.g., SIFT) into shorter binary codes, its efficacy on data that is already binary remained largely unexplored. This study investigates whether data-dependent hashing can further reduce the dimensionality of FREAK descriptors without compromising matching precision.
Methodology and Datasets
We evaluated three categories of data-dependent hashing methods:
- Unsupervised: Spectral Hashing (SH), Iterative Quantization (ITQ), and Isotropic Hashing (IsoH).
- Semi-supervised: Sequential Projection Learning (SPLH).
- Supervised: Fast supervised hashing (FastHash).
These methods were benchmarked against a naive baseline: bit truncation, which involves simply retaining the first $k$ bits of the original 512-bit FREAK descriptor.
The evaluation utilized large-scale datasets from the Google Tango project, consisting of 512-bit FREAK descriptors associated with over 40,000 unique landmarks. Precision@1 was used as the primary metric, calculated via a linear scan in Hamming space for 20,000 sampled elements.
Comparative Analysis
The Truncation Baseline
FREAK descriptors are designed such that the most discriminative binary tests are positioned at the beginning of the string. This inherent structure makes simple bit truncation a formidable baseline. For 256-bit codes, no tested hashing method outperformed truncation, suggesting that the noise introduced by learning a new projection often outweighs the signal preserved when the input is already a high-quality binary string.
Performance of Unsupervised Methods
Hashing becomes beneficial primarily when storage is highly restricted and very short codes (64 bits or less) are required. In these regimes, learning-based approaches can capture global structures that simple truncation misses.
As shown in the figure above:
- 128-bit codes: IsoH, Spherical Hashing (SpH), and SH showed marginal improvements (1-2%) over truncation.
- 64-bit codes: Isotropic Hashing (IsoH) was the most effective, yielding a 15% improvement in precision over truncation.
- 32-bit codes: Precision dropped by over 40% across all methods, indicating that 32 bits are insufficient for maintaining descriptor uniqueness.
Failure of Kernel-Based Methods
Kernel-based hashing methods (e.g., KLSH) performed significantly worse than the truncation baseline. This failure is attributed to the nature of Hamming space, where a high proportion of points are equidistant from randomly selected anchor points, rendering clustering-based approaches ineffective for binary-to-binary reduction.
Conclusion
Our findings indicate that while unsupervised hashing (specifically IsoH) offers advantages for very short codes, simple bit truncation remains superior for longer codes due to the optimized design of the FREAK descriptor. Furthermore, supervised and semi-supervised methods struggled with scalability and overfitting when applied to large-scale landmark data. Future work should explore supervised dimensionality reduction techniques, such as Mahalanobis metric learning, to better handle the constraints of mobile hardware and large-scale binary feature matching.
Summary updated