Image Retrieval Framework Based on Dual Representation Descriptor

Yuichi Yoshida, Tsuyoshi ToyofukuIEICE Trans. Information and Systems 2017 · OpenReview

Abstract

Descriptor aggregation techniques such as the Fisher vector and vector of locally aggregated descriptors (VLAD) are standard in modern image retrieval frameworks. However, these systems face a significant trade-off: real-valued descriptors like SIFT provide high accuracy but require substantial storage for geometric verification and significant time for extraction. Conversely, binary descriptors are efficient but often suffer from reduced retrieval performance when aggregated. This paper proposes a dual representation descriptor framework that leverages the advantages of both. By utilizing the CARD (Compact And Real-time Descriptor), the system aggregates real-valued descriptors into a VLAD for high-accuracy search while using binary representations for efficient geometric verification. Evaluated on the Holidays, ukbench, and SMVSD datasets, the framework achieves accuracy comparable to SIFT-based systems while maintaining the speed and storage efficiency of binary-based approaches.

Introduction

Modern image retrieval follows a four-stage pipeline: local descriptor extraction, aggregation into an image signature, database searching, and geometric verification. Engineers typically face a frustrating choice between accuracy and scalability. Real-valued descriptors (like SIFT) are highly accurate but slow to compute and massive in terms of storage, often making geometric verification for large databases prohibitively expensive. Binary descriptors (like ORB) are fast and compact but perform poorly during the aggregation stage, leading to lower overall retrieval precision.

The researchers aim to break this trade-off by targeting the storage bottleneck in the geometric verification stage without sacrificing the fidelity of the initial search.

Methods: The Dual Representation Approach

The core innovation is the Dual Representation Descriptor. Instead of choosing between real or binary formats, the framework extracts both from the same keypoint simultaneously. The authors implemented this using the Compact And Real-time Descriptor (CARD), which computes real-valued gradient histograms using a lookup table (LUT) to maintain high computation speeds.

The dual representation framework architecture, showing the parallel processing of real-valued and binary descriptors for search and verification.

As illustrated in Figure 1, the framework utilizes a dual-path processing strategy:

  • Path A (Search): The real-valued components of the CARD descriptor are aggregated into a VLAD vector. This high-fidelity signature is used for the initial database search to identify candidate images.
  • Path B (Verification): The real values are converted into binary strings using a sparse random projection. These compact strings are stored in the database and used during the final geometric verification stage (using RANSAC) to confirm the spatial arrangement of features.

Because the binary version is derived directly from the real-valued version already being calculated, the computational overhead is negligible.

Experimental Results

The framework was evaluated on three standard benchmarks: Holidays (scenery), ukbench (household objects), and Stanford Mobile Visual Search (SMVSD) (planar objects like book covers).

ROC curves comparing the proposed method with a baseline that lacks geometric verification across three datasets.

Key Performance Metrics

  • Accuracy: As shown in the ROC curves in Figure 2, the dual-representation framework matched the accuracy of SIFT-based systems across all datasets. Interestingly, CARD outperformed SIFT on the SMVSD dataset, likely due to its corner-based detector being more stable on text-heavy planar surfaces.
  • Speedup: Local descriptor extraction was roughly 16x faster than SIFT (10ms vs. 160ms per image). Total retrieval time was approximately halved compared to traditional SIFT-based pipelines.
  • Storage Efficiency: This is the headline result. The database size required for geometric verification was reduced to just 4% of SIFT's requirements. A CARD binary descriptor requires only 16 bytes, compared to 512 bytes for a standard SIFT descriptor.

Conclusion and Future Work

The proposed dual representation framework successfully bridges the gap between accuracy and efficiency. By keeping real-valued data for the aggregation step, the system maintains a high-fidelity image signature, while the binary representation slashes the memory footprint of geometric verification. While highly effective, the authors note that the CARD descriptor is theoretically less robust than SIFT regarding extreme rotation invariance. Future research will explore more compact binarization techniques to handle "web-scale" databases containing billions of images.

Summary updated

Abstract

Descriptor aggregation techniques such as the Fisher vector and vector of locally aggregated descriptors (VLAD) are used in most image retrieval frameworks. It takes some time to extract local descriptors, and the geometric verification requires storage if a real-valued descriptor such as SIFT is used. Moreover, if we apply binary descriptors to such a framework, the performance of image retrieval is not better than if we use a real-valued descriptor. Our approach tackles these issues by using a dual representation descriptor that has advantages of being both a real-valued and a binary descriptor. The real value of the dual representation descriptor is aggregated into a VLAD in order to achieve high accuracy in the image retrieval, and the binary one is used to find correspondences in the geometric verification stage in order to reduce the amount of storage needed. We implemented a dual representation descriptor extracted in semi-real time by using the CARD descriptor. We evaluated the accuracy of our image retrieval framework including the geometric verification on three datasets (holidays, ukbench and Stanford mobile visual search). The results indicate that our framework is as accurate as the framework that uses SIFT. In addition, the experiments show that the image retrieval speed and storage requirements of our framework are as efficient as those of a framework that uses ORB.
BibTeX
@article{yoshida2017image,
  author = {Yuichi Yoshida and Tsuyoshi Toyofuku},
  title = {{Image Retrieval Framework Based on Dual Representation Descriptor}},
  journal = {IEICE Trans. Information and Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=JW2IyFGNNc},
}
Figure