Source-linked AI summary
Packing and Padding: Coupled Multi-index for Accurate Image Retrieval
Liang Zheng, Shengjin Wang, Ziqiong Liu, Qi Tian
TL;DR
SIFT-based BoW retrieval produces false positives because quantization loses information and SIFT captures only local gradient distribution. The paper introduces c-MI, coupling SIFT and color features in a multi-dimensional inverted index while using Multiple Assignment to improve recall. Combined with complementary methods, c-MI reaches 85.8% mAP on Holidays and a 3.85 N-S score on Ukbench, with about half the baseline query time.
Problem
SIFT visual words have limited discriminative power because quantization loses information and SIFT describes only local gradient distribution, causing false positive matches.
Method
c-MI couples SIFT and color descriptors as dimensions of a multi-dimensional inverted index, using Multiple Assignment to improve recall and color robustness to illumination changes.
Results
85.8% mAP on Holidays and 3.85 N-S score on Ukbench are achieved with complementary methods, while c-MI uses about half the baseline’s query time.
Takeaways & Limitations
c-MI provides indexing-level SIFT-color fusion that enhances BoW visual-word discrimination and is compatible with several prior retrieval techniques.
Takeaways & Limitations
Future work is needed to explore c-MI’s intrinsic properties, feature-selection strategies, and higher-order extensions.
Abstract
from arXiv · showhide
In Bag-of-Words (BoW) based image retrieval, the SIFT visual word has a low discriminative power, so false positive matches occur prevalently. Apart from the information loss during quantization, another cause is that the SIFT feature only describes the local gradient distribution. To address this problem, this paper proposes a coupled Multi-Index (c-MI) framework to perform feature fusion at indexing level. Basically, complementary features are coupled into a multi-dimensional inverted index. Each dimension of c-MI corresponds to one kind of feature, and the retrieval process votes for images similar in both SIFT and other feature spaces. Specifically, we exploit the fusion of local color feature into c-MI. While the precision of visual match is greatly enhanced, we adopt Multiple Assignment to improve recall. The joint cooperation of SIFT and color features significantly reduces the impact of false positive matches. Extensive experiments on several benchmark datasets demonstrate that c-MI improves the retrieval accuracy significantly, while consuming only half of the query time compared to the baseline. Importantly, we show that c-MI is well complementary to many prior techniques. Assembling these methods, we have obtained an mAP of 85.8% and N-S score of 3.85 on Holidays and Ukbench datasets, respectively, which compare favorably with the state-of-the-arts.
1. Introduction
The paper targets real-time near-duplicate image retrieval, where SIFT-based BoW matching suffers from quantization loss and limited color information, producing false positives. It proposes c-MI, which couples SIFT and color features at indexing level, uses Multiple Assignment for recall, and achieves strong benchmark results with complementary techniques.
- The task is finding all database images with similar appearance to a query image in real time.
- SIFT-based BoW matching overlooks image characteristics such as color, while quantization maps different patches to the same visual word, producing false positives.
- c-MI performs indexing-level feature fusion by coupling SIFT and color features as dimensions of a multi-dimensional inverted index.
- Multiple Assignment improves recall, with a large assignment value for color features to increase robustness to illumination changes.
- 85.8% mAP on Holidays and 3.85 N-S score on Ukbench are achieved by combining c-MI with complementary prior techniques.
2. Related Work
Prior image-retrieval research improves visual matching through contextual cues, binary-feature verification, feature fusion, and indexing strategies. These approaches address precision, recall, complementary information, and retrieval efficiency from different angles.
- Matching Refinement: Large codebooks typically provide high precision but low recall, whereas small codebooks provide high recall; contextual cues help improve precision.
- Matching Refinement: Spatial context and binary features, including Hamming Embedding, refine visual matching by filtering or verifying candidate matches.
- Feature Fusion: Feature fusion supplements SIFT’s local gradient information with complementary cues such as local color and global features.
- Indexing Strategy: Inverted indexes reduce retrieval cost, while joint inverted indexes and inverted multi-indexes organize or search visual representations across multiple dimensions.
3. Proposed Approach
The proposed c-MI framework couples SIFT and color features in a two-dimensional inverted index, requiring local matches to agree across both feature spaces. Multiple Assignment and binary signatures improve recall and reduce quantization-related matching errors.
- Conventional Inverted Index Revisit: Conventional inverted indexing uses a single SIFT visual word, allowing visually dissimilar local patches to share the same quantized word.Quantization artifacts and SIFT’s limited characterization of local regions make visual-word equality an unreliable sole matching criterion.
- Coupled Multi-Index: Multiple Assignment improves recall, with larger assignment on the color side intended to address illumination variation.The framework emphasizes precision through multi-index coupling and uses Multiple Assignment to recover additional matches.
- Coupled Multi-Index: c-MI couples independently quantized SIFT and color descriptors into word pairs, creating Ks × Kc inverted-index entries that store tuple-associated metadata.Each coupled feature tuple is assigned to the nearest SIFT and color centroids, and the corresponding word-pair entry is checked during retrieval.
- Coupled Multi-Index: A c-MI local match is valid only when the two feature tuples agree in both SIFT and color quantization spaces.This joint condition rejects pairs that appear similar under SIFT alone but differ substantially in color.
- Coupled Multi-Index: Color Hamming Embedding further filters coupled matches by requiring binary-signature distance below a threshold and defining matching strength from that distance.The c-MI structure also supports IDF weighting and 2-D histogram normalization for image scoring.
4. Experiments
Experiments across five public datasets evaluate c-MI, parameter choices, compatibility with prior techniques, accuracy, scalability, query time, and memory-related trade-offs. c-MI improves retrieval over the baseline, scales favorably, and achieves strong final results when combined with graph fusion.
- Evaluation datasets and metrics: Experiments use Ukbench, Holidays, DupImage, Mobile, and MIR Flickr 1M, with dataset-specific retrieval metrics.Ukbench uses N-S score, Holidays and DupImage use mAP, Mobile uses Top-1 and Top-10 precision, and MIR Flickr 1M tests scalability.
- Parameter analysis: The color codebook of size 200 performs favorably, with MAc = 200 × 50% = 100 selected for color quantization.The experiment varies codebook sizes 100, 200, 500, and 1000 and assigns different fractions of visual words.
- Parameter analysis: The selected color Hamming Embedding parameters are σ = 4 and κ = 7 on Holidays.mAP peaks at σ = 4, while κ = 7 gives the best performance with or without weighted distance.
- Baseline comparison: +0.32 in N-S score on Ukbench, +13.2% in mAP on Holidays, and +14.3% in Top-1 precision on Mobile are reported over the baseline.The improvement is less prominent for DupImage, where mAP increases from 48.6% to 56.3%.
- Compatibility with prior methods: c-MI combines consistently with burstiness weighting, Hamming Embedding, and Multiple Assignment, reaching 3.71 N-S on Ukbench before graph fusion.For Ukbench, combining Bursts and HEs raises N-S from 3.43 to 3.69, and adding MAs reaches 3.71.
- Final evaluation and efficiency: 85.8% mAP on Holidays and 3.85 N-S on Ukbench are achieved after graph fusion, while c-MI cuts query time to about half the baseline across four datasets.The query-time reduction is attributed to shorter indexed lists and traversing 50% of the color index; fewer visited entries can reduce time further at lower accuracy.
5. Conclusion
The paper concludes that c-MI enables accurate and efficient image retrieval by coupling SIFT and color descriptors, while complementary methods yield strong benchmark performance. It also identifies future extensions of the coupled multi-index.
- Conclusion: c-MI couples SIFT and color descriptors in a multi-index, enhancing BoW discriminative power for image retrieval.Each keypoint is described by both features, with color Multiple Assignment addressing illumination changes and recall.
- Conclusion: 85.8% mAP on Holidays and 3.85 N-S score on Ukbench establish the reported benchmark performance.The system also has about half the baseline's memory and time costs, supporting large-scale settings.
- Conclusion: The authors release code and data on their website.The release is identified as an additional contribution.
- Conclusion: Future work will examine the intrinsic properties of c-MI and extend it to other descriptors, feature-selection strategies, and higher-order indices.These directions are presented as planned investigations rather than completed capabilities.