Aggregating Local Image Descriptors into Compact Codes

Hervé JégouFlorent PerronninMatthijs DouzeJorge SánchezP. PérezCordelia Schmid

article2012TPAMI1,665 citations

Proposes an image indexing framework that aggregates local descriptors into compact codes of just a few dozen bytes, enabling accurate visual search across 100 million images in roughly 250 milliseconds on a single processor core.

Listen

Modern web-scale platforms face severe scalability challenges when performing visual searches across tens or hundreds of millions of images. Standard visual search systems, such as the widely adopted bag-of-words approach, require large amounts of memory per indexed item and suffer from severe query slowdowns as databases expand. Prior methods that attempted to reduce memory consumption frequently suffered substantial losses in search accuracy or failed to handle image alterations such as cropping, rotation, and viewpoint shifts.

The article develops and evaluates an end-to-end image indexing and retrieval pipeline designed to optimize search accuracy, response speed, and memory usage simultaneously. It demonstrates how to combine advanced descriptor aggregation, dimensionality reduction, and vector quantization to enable highly accurate similarity searches at the scale of 100 million images.

To establish these results, the authors tested the proposed architecture across standard benchmark datasets (such as INRIA Holidays, UKB, and Oxford5K) and very large collections, including a 10-million-image Flickr set and a 100-million-image web corpus. The approach aggregates local image features into compact global descriptors using the Fisher kernel framework, decorrelates features with principal component analysis, and encodes the resulting representations using asymmetric product quantization paired with an inverted file index structure.

The key findings demonstrate significant performance advantages over traditional visual search architectures. First, the Fisher kernel representation achieves superior retrieval precision compared to bag-of-words across fixed signature lengths, reaching competitive search accuracy while requiring far fewer visual vocabulary clusters. Second, by jointly optimizing dimensionality reduction and vector quantization based on total reconstruction error, the system compresses images into signatures as small as 16 to 20 bytes with minimal degradation in accuracy. Third, in large-scale testing on 100 million images, the system queries the entire database in approximately 245 milliseconds on a single processor core, operating orders of magnitude faster than traditional inverted list approaches while outperforming prior compact indexing schemes.

These results demonstrate that large-scale image search can be deployed on standard hardware infrastructure without massive memory footprints. A signature size of 20 bytes allows an index of one billion images to reside entirely within 20 gigabytes of random-access memory, drastically reducing server costs, operational overhead, and latency. The findings challenge the longstanding trade-off between compact index size and high search precision, showing that high-order statistical aggregation captures visual information more effectively than sparse histogram methods.

For practical implementation, organizations managing large image repositories should replace uncompressed visual dictionaries with Fisher vector aggregation and product-quantized inverted indexing. System designers should select target code lengths based on operational budgets: a 20-byte profile offers extreme scale and fast initial shortlisting, whereas higher byte allocations (such as 68 to 324 bytes) deliver near-exhaustive accuracy for high-precision applications. If precise boundary identification is necessary, a lightweight geometric post-verification step can be added to the top retrieved shortlists.

The primary operational limitation is that extreme dimensionality reduction can degrade performance on very specific architectural or near-duplicate datasets where visual variability is minimal and fine details dominate. However, the evaluation across multiple independent benchmarks and massive distractor collections provides high confidence in the pipeline's robustness for general web-scale visual search.

feature descriptors image descriptors local image descriptors compact codes local image descriptors VLAD representations

Jégou et al (2012).pdf

Paper: Improving the Fisher Kernel for Large-Scale Image Classification, Florent Perronnin et al. (2010). This paper establishes the improved Fisher Vector representation using power and L2 normalization, which serves as the foundational vector aggregation method adapted and compressed in the source paper.
Paper: Hamming Embedding and Weak Geometric Consistency for Large Scale Image Search, Hervé Jégou et al. (2008). This work introduces Hamming Embedding to refine visual word assignments into compact binary signatures, directly inspiring the source paper's joint pursuit of compact descriptor aggregation and efficient indexing.
Paper: Exploiting Generative Models in Discriminative Classifiers, T. Jaakkola et al. (1998). This foundational paper develops the Fisher kernel framework for extracting fixed-length gradient vectors from generative models, providing the core mathematical basis for Fisher vector aggregation.
Paper: Locality-constrained Linear Coding for image classification, Jinjun Wang et al. (2010). This study introduces Locality-constrained Linear Coding for local feature aggregation, representing an important coding benchmark contrasted against Fisher and bag-of-words aggregations.
Paper: Visual categorization with bags of keypoints, Gabriella Csurka et al. (2004). This paper introduces the standard bag-of-visual-words representation that the source paper seeks to outperform through Fisher kernel aggregation.
Paper: Distinctive Image Features from Scale-Invariant Keypoints, David G. Lowe (2004). This paper introduces SIFT descriptors, which serve as the primary local image features that the source paper aggregates and compresses for large-scale search.
Paper: Similarity Search in High Dimensions via Hashing, Aristides Gionis et al. (1999). This foundational paper presents Locality-Sensitive Hashing for sublinear nearest-neighbor search, underpinning high-dimensional compact vector indexing strategies.
Paper: A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Roger Weber et al. (1998). This study provides a quantitative analysis of high-dimensional indexing degradation, motivating the source paper's focus on joint dimensionality reduction and vector quantization.

Paper: NetVLAD: CNN Architecture for Weakly Supervised Place Recognition, Relja Arandjelović et al. (2015). This paper translates vector aggregation principles from VLAD and Fisher vectors into an end-to-end differentiable CNN layer for large-scale visual retrieval.
Paper: Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval, Yunchao Gong et al. (2013). This work advances compact code generation by introducing Iterative Quantization to learn optimal binary projections directly from aggregated visual representations like Fisher vectors.
Paper: Billion-Scale Similarity Search with GPUs, Jeff Johnson et al. (2019). This research builds on product quantization and compact vector indexing by engineering high-throughput GPU algorithms for billion-scale similarity search in FAISS.
Paper: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, Suhas Jayaram Subramanya et al. (2019). This paper scales billion-point approximate nearest neighbor search to a single machine by coupling graph traversal with product-quantized in-memory distance approximations.
Paper: Fine-Tuning CNN Image Retrieval with No Human Annotation, Filip Radenovic et al. (2017). This work modernizes compact image representation and retrieval pipelines by learning global pooling and descriptor whitening within deep neural network architectures.
Paper: Return of the Devil in the Details: Delving Deep into Convolutional Nets, Ken Chatfield et al. (2014). This study explicitly benchmarks deep convolutional network features against the improved Fisher vector pipelines developed in the source era.
Paper: Describing Textures in the Wild, Mircea Cimpoi et al. (2014). This paper applies Fisher vector aggregation of local descriptors to the task of describing and recognizing complex texture attributes in natural scenes.

Cover for Aggregating Local Image Descriptors into Compact Codes

Abstract

This paper addresses the problem of large-scale image search. Three constraints have to be taken into account: search accuracy, efficiency, and memory usage. We first present and evaluate different ways of aggregating local image descriptors into a vector and show that the Fisher kernel achieves better performance than the reference bag-of-visual words approach for any given vector dimension. We then jointly optimize dimensionality reduction and indexing in order to obtain a precise vector comparison as well as a compact representation. The evaluation shows that the image representation can be reduced to a few dozen bytes while preserving high accuracy. Searching a 100 million image dataset takes about 250 ms on one processor core.

Topics

feature descriptors image descriptors local image descriptors

Keywords

compact codes local image descriptors VLAD representations Fisher kernel framework large scale image search nearest neighbor search Locality-Sensitive Hashing spectral hashing SIFT descriptors vector compression

I. INTRODUCTION
II. DATASETS AND EVALUATION PROTOCOL
III. IMAGE VECTOR REPRESENTATION
A. Bag-of-features
B. Fisher vector
C. VLAD: non probabilistic Fisher Kernel
D. Dimensionality reduction on local descriptors
IV. EVALUATION OF THE AGGREGATION METHODS
V. FROM VECTORS TO CODES
A. Approximate nearest neighbor
B. Indexation-aware dimensionality reduction
VI. EXPERIMENTS
A. Dimensionality reduction and indexation
B. Comparison with the state of the art
C. Large-scale experiments
VII. CONCLUSION
ACKNOWLEDGEMENTS
REFERENCES

Knowls

Knowl 1 — Fisher Vector Representation for Aggregating Local Descriptors
model/method
The Fisher Vector (FV) aggregates an unordered set of $T$ local $d$ -dimensional descriptors $X = \{x_1, \dots, x_T\} \subset \mathbb{R}^d$ extracted from an image into a fixed-length signature. The generation process of local descriptors across images is modeled by a Gaussian Mixture Model (GMM) with $K$ components:

$u_\lambda(x) = \sum_{i=1}^K w_i u_i(x)$

where $\lambda = \{w_i, \mu_i, \sigma_i\}_{i=1}^K$ denotes the parameters: mixture weights $w_i > 0$ (with $\sum_{i=1}^K w_i = 1$ ), mean vectors $\mu_i \in \mathbb{R}^d$ , and diagonal covariance matrices with variances $\sigma_i \in \mathbb{R}^d$ .

The soft assignment probability $\gamma_t(i)$ of local descriptor $x_t$ to Gaussian component $i$ is:

$\gamma_t(i) = \frac{w_i u_i(x_t)}{\sum_{j=1}^K w_j u_j(x_t)}$

Using a diagonal closed-form approximation of the Fisher information matrix $F_\lambda$ , the whitened gradient of the log-likelihood of $X$ with respect to the mean vector $\mu_i$ of Gaussian $i$ is:

$G_i^X = \frac{1}{T \sqrt{w_i}} \sum_{t=1}^T \gamma_t(i) \sigma_i^{-1} (x_t - \mu_i)$

where $\sigma_i^{-1}$ denotes component-wise division by the standard deviation vector $\sigma_i$ . The complete Fisher Vector $G_\lambda^X$ is the concatenation of the $d$ -dimensional gradient vectors across all $K$ Gaussians:

$G_\lambda^X = \left[ (G_1^X)^\top, (G_2^X)^\top, \dots, (G_K^X)^\top \right]^\top$

producing a representation of dimension $Kd$ .
Knowl 2 — Vector of Locally Aggregated Descriptors (VLAD)
algorithm
The Vector of Locally Aggregated Descriptors (VLAD) aggregates a set of $T$ local $d$ -dimensional descriptors $X = \{x_1, \dots, x_T\} \subset \mathbb{R}^d$ into a single $Kd$ -dimensional vector using a visual codebook $\{\mu_1, \dots, \mu_K\} \subset \mathbb{R}^d$ learned via $k$ -means clustering. For each centroid $\mu_i$ , the difference vectors $x_t - \mu_i$ are accumulated for all local descriptors whose nearest codebook centroid is $\mu_i$ :

$v_i = \sum_{x_t : \text{NN}(x_t) = i} (x_t - \mu_i)$

The subvectors $v_1, \dots, v_K$ are concatenated into a $Kd$ -dimensional vector $V$ , which is then normalized component-wise by signed power normalization ( $f(z) = \text{sign}(z)|z|^\alpha$ , with $\alpha = 0.5$ ) and globally normalized by its Euclidean ( $L_2$ ) norm.
Input: Local descriptors $x_1, \dots, x_T \in \mathbb{R}^d$ , centroids $\mu_1, \dots, \mu_K \in \mathbb{R}^d$ , power exponent $\alpha \in (0, 1]$
Output: Normalized VLAD vector $V \in \mathbb{R}^{Kd}$
for $i = 1$ to $K$ do
     $v_i \leftarrow 0_d$
end for
for $t = 1$ to $T$ do
     $i \leftarrow \arg\min_{j \in \{1, \dots, K\}} \|x_t - \mu_j\|_2$
     $v_i \leftarrow v_i + (x_t - \mu_i)$
end for
$V \leftarrow [v_1^\top, v_2^\top, \dots, v_K^\top]^\top$
for $u = 1$ to $Kd$ do
     $V_u \leftarrow \text{sign}(V_u) |V_u|^\alpha$
end for
$V \leftarrow \frac{V}{\|V\|_2}$
return $V$
Knowl 3 — VLAD as a Non-Probabilistic Limiting Case of the Fisher Vector
theoretical result
The Vector of Locally Aggregated Descriptors (VLAD) is an exact non-probabilistic limiting case of the Fisher Vector representation under three specific assumptions regarding the underlying Gaussian Mixture Model (GMM):
1. Uniform mixture weights: $w_i = \frac{1}{K}$ for all components $i = 1, \dots, K$ .
2. Isotropic covariance matrices: $\sigma_i = \epsilon I_d$ for all $i = 1, \dots, K$ , where $I_d$ is the $d \times d$ identity matrix and $\epsilon > 0$ .
3. Vanishing variance limit: The variance scale parameter $\epsilon$ tends to zero ( $\epsilon \to 0$ ).
Under assumptions (1) and (2), the Fisher Vector gradient with respect to the mean $\mu_i$ simplifies to:

$G_i^X \propto \sum_{t=1}^T \gamma_t(i) (x_t - \mu_i)$

As $\epsilon \to 0$ , each Gaussian distribution $u_i(x)$ converges to a Dirac delta distribution centered at $\mu_i$ , causing the soft posterior assignments $\gamma_t(i)$ to collapse into hard nearest-neighbor indicators:

$\lim_{\epsilon \to 0} \gamma_t(i) = \begin{cases} 1 & \text{if } i = \arg\min_j \|x_t - \mu_j\|_2 \\ 0 & \text{otherwise} \end{cases}$

Substituting this binary assignment into the gradient expression yields:

$G_i^X \propto \sum_{x_t : \text{NN}(x_t) = i} (x_t - \mu_i)$

which matches the unnormalized accumulation formula of VLAD up to a constant scalar factor eliminated by $L_2$ normalization.
Knowl 4 — Implicit Background Information Removal in Fisher Vectors
theoretical result
Let $X = \{x_1, \dots, x_T\}$ be independent and identically distributed local descriptors extracted from an image, generated by a distribution $p(x)$ that is a convex combination of an image-independent background distribution $u_\lambda(x)$ and an image-specific distribution $q(x)$ :

$p(x) = \omega q(x) + (1 - \omega) u_\lambda(x)$

where $\omega \in [0, 1]$ is the proportion of image-specific content in the image.

By the law of large numbers, as the number of local descriptors $T \to \infty$ , the sample Fisher Vector gradient converges to the expected gradient under $p(x)$ :

$G_\lambda^X = \frac{1}{T} \sum_{t=1}^T \nabla_\lambda \log u_\lambda(x_t) \approx \nabla_\lambda \mathbb{E}_{x \sim p}[\log u_\lambda(x)]$

Substituting the mixture distribution $p(x)$ gives:

$G_\lambda^X \approx \omega \nabla_\lambda \mathbb{E}_{x \sim q}[\log u_\lambda(x)] + (1 - \omega) \nabla_\lambda \mathbb{E}_{x \sim u_\lambda}[\log u_\lambda(x)]$

Because the generative parameters $\lambda$ are estimated via Maximum Likelihood Estimation (MLE) on generic background training data, the expected gradient under the generative model itself is approximately zero at the optimum:

$\nabla_\lambda \mathbb{E}_{x \sim u_\lambda}[\log u_\lambda(x)] \approx 0$

Consequently:

$G_\lambda^X \approx \omega \nabla_\lambda \mathbb{E}_{x \sim q}[\log u_\lambda(x)]$

This proves that the Fisher Vector automatically eliminates image-independent background information and isolates the image-specific signature without explicit foreground/background segmentation.
Knowl 5 — Relation Between Fisher Vector and Bag-of-Words with Intrinsic IDF
theoretical result
Let $X = \{x_1, \dots, x_T\}$ be a set of local descriptors extracted from an image. Let the soft Bag-of-Words (BOW) component weight $w_i^X$ and the weighted mean descriptor $\mu_i^X$ for Gaussian component $i \in \{1, \dots, K\}$ be defined as:

$w_i^X = \frac{1}{T} \sum_{t=1}^T \gamma_t(i), \qquad \mu_i^X = \frac{\sum_{t=1}^T \gamma_t(i) x_t}{\sum_{t=1}^T \gamma_t(i)}$

where $\gamma_t(i)$ is the posterior soft-assignment probability of descriptor $x_t$ to component $i$ .

The Fisher Vector gradient component $G_i^X \in \mathbb{R}^d$ with respect to the component mean $\mu_i$ can be factored as:

$G_i^X = \frac{w_i^X}{\sqrt{w_i}} \sigma_i^{-1} (\mu_i^X - \mu_i)$

where $w_i$ is the prior mixture weight and $\sigma_i$ is the diagonal standard deviation vector of Gaussian component $i$ .

This factorization establishes two properties:
1. The Fisher Vector extends Bag-of-Words by coupling zero-order soft counts ( $w_i^X$ ) with first-order displacement vectors $(\mu_i^X - \mu_i)$ , capturing the average position of local descriptors within each Voronoi region relative to the component center $\mu_i$ and normalized by variance $\sigma_i$ .
2. The divisor $\frac{1}{\sqrt{w_i}}$ acts as an intrinsic inverse document frequency (IDF) term, automatically discounting frequently occurring visual words without requiring empirical heuristics.
Knowl 6 — Power and Euclidean Normalization of Aggregated Descriptors
model/method
Aggregated vector representations (both Fisher Vectors and VLAD) undergo two sequential normalization operations prior to distance calculation:
1. Component-wise Power Normalization: Every scalar element $z$ of the aggregated vector is mapped via the function:
$f(z) = \text{sign}(z) |z|^\alpha$

where $\alpha \in [0, 1]$ . Setting $\alpha = 0.5$ (signed square root) consistently produces near-optimal retrieval accuracy across codebook sizes. Power normalization mitigates the visual burstiness phenomenon (where repetitive visual textures produce disproportionately large descriptor values) and acts as a variance-stabilizing transform for compound Poisson distributions.
1. Euclidean ( $L_2$ ) Normalization: Following power normalization, the entire vector $V \in \mathbb{R}^{Kd}$ is projected onto the unit hypersphere:
$V \leftarrow \frac{V}{\|V\|_2}$

This guarantees that the inner product between two representations corresponds to their cosine similarity and ensures that self-queries attain a maximum similarity score of $1$ .
Knowl 7 — Joint Optimization of PCA Dimensionality Reduction and Product Quantization
model/method
To compress a $D$ -dimensional aggregated image vector $x \in \mathbb{R}^D$ into a fixed budget of $B = m b_s$ bits, PCA projection and Product Quantization (PQ) are jointly optimized by minimizing total mean squared reconstruction error.

A PCA matrix $M \in \mathbb{R}^{D' \times D}$ (the top $D'$ principal components) maps $x$ to $x' = M x \in \mathbb{R}^{D'}$ . In the original space $\mathbb{R}^D$ , this corresponds to projection $x_p = M^\top M x = x - \epsilon_p(x)$ , where $\epsilon_p(x) \in \text{Null}(M)$ is the projection error. The projected vector $x'$ is quantized into $m$ subvectors of length $D'/m$ with $b_s$ bits each via an asymmetric product quantizer $q(x')$ , producing in $\mathbb{R}^D$ the approximation $q(x_p) = x - \epsilon_p(x) - \epsilon_q(x_p)$ , where $\epsilon_q(x_p) \in \text{Null}(M)^\perp$ is the quantization error.

Because the errors reside in orthogonal subspaces, the total squared error decomposes additively:

$\|x - q(x_p)\|^2 = \|\epsilon_p(x)\|^2 + \|\epsilon_q(x_p)\|^2$

The optimal dimension $D'$ (constrained to be a multiple of $m$ ) is chosen by minimizing the empirical mean squared error $e(D')$ over a training set $\mathcal{L}$ :

$e(D') = \frac{1}{|\mathcal{L}|} \sum_{x \in \mathcal{L}} \left( \|\epsilon_p(x)\|^2 + \|\epsilon_q(x_p)\|^2 \right)$

This balances the trade-off: larger $D'$ decreases PCA truncation error $\epsilon_p(x)$ but increases per-component quantization distortion $\epsilon_q(x_p)$ for a fixed bit budget $B$ .
Knowl 8 — Variance Balancing across PCA Subspaces for Product Quantization
model/method
Product Quantization partitions a PCA-reduced vector $x' \in \mathbb{R}^{D'}$ into $m$ subvectors of equal length $D'/m$ and assigns an equal number of bits $b_s$ to each subvector. Because PCA orders components by strictly decreasing variance, the first subvectors exhibit significantly higher energy than later subvectors, leading to coarse quantization and severe distortion in the most energetic components.

To balance variance across all dimensions without changing pairwise Euclidean distances, an orthogonal transformation $R \in \mathbb{R}^{D' \times D'}$ ( $R^\top R = I$ ) is applied after PCA:

$\tilde{x} = R x' = R M x$

Applying a random orthogonal rotation matrix $R$ balances the variance evenly across all subvectors, achieving the same retrieval accuracy improvement as explicitly optimizing a Householder balancing matrix.
Knowl 9 — Asymmetric Distance Computation and Inverted File Indexing for Compact Image Codes
model/method
In Asymmetric Distance Computation (ADC), database vectors $y_i \in \mathbb{R}^{D'}$ are quantized into $m$ subvectors $q(y_i) = [q_1(y_i^1), \dots, q_m(y_i^m)]$ using sub-quantizers with $k_s = 2^{b_s}$ centroids each, while query vectors $x \in \mathbb{R}^{D'}$ remain uncompressed.

The squared Euclidean distance between query $x$ and database code $q(y_i)$ is computed via lookup tables:

$\|x - q(y_i)\|^2 = \sum_{j=1}^m \|x^j - q_j(y_i^j)\|^2$

Precomputing the lookup table of squared distances between each query subvector $x^j$ and the $k_s$ centroids of quantizer $q_j$ requires $\mathcal{O}(D' k_s)$ operations. Subsequent query-to-database distance evaluations require only $m$ table lookups and additions per vector.

In Inverted File ADC (IVFADC) for web-scale databases:
1. The search space is partitioned into $K_{\text{ivf}}$ coarse centroids (e.g., $K_{\text{ivf}} = 8192$ ) using an inverted index.
2. For a query $x$ , only the database vectors assigned to the $w$ closest coarse centroids (e.g., $w = 64$ lists visited) are scanned using ADC on the residual vectors.
3. Each indexed vector requires $m b_s$ bits for the residual PQ code plus 4 bytes to store the image identifier explicitly, delivering one to two orders of magnitude faster query times than exhaustive ADC.
Knowl 10 — Dimensionality Reduction of Local SIFT Descriptors for Fisher Vector Estimation
empirical result
Applying Principal Component Analysis (PCA) to reduce local SIFT descriptors from 128 dimensions to $d = 64$ dimensions prior to Gaussian Mixture Model (GMM) estimation and Fisher Vector calculation consistently improves image retrieval mean Average Precision (mAP).

Two mechanisms explain this performance gain:
1. SIFT descriptor dimensions are correlated; PCA decorrelates the features, significantly improving the fit of GMMs that employ diagonal covariance matrices $\sigma_i$ .
2. Discarding the least energetic principal components suppresses noise, improving the stability of Maximum Likelihood parameter estimation for the GMM.
Applying a random rotation after PCA (which disrupts feature decorrelation) or performing PCA rotation without dimension reduction (retaining all 128 components) degrades retrieval accuracy. In contrast, local PCA dimension reduction does not improve VLAD performance, as VLAD does not assume diagonal covariance matrices.

Knowl 11 — Image Retrieval Performance Comparison of BOW, Fisher Vectors, and VLAD

data/table

The table below compares Bag-of-Words (BOW), Fisher Vectors (FV), VLAD, and global GIST representations on the University of Kentucky Benchmark (UKB, scored as $4 \times \text{recall}@4$ , maximum 4.0), INRIA Holidays (mean Average Precision, mAP %), Oxford5K Buildings (mAP %), and INRIA Copydays with 10k Flickr distractors (mAP %). Local SIFT descriptors are reduced to 64 dimensions for FV and VLAD.

Descriptor	GIST	BOW 200k	BOW 20k (128D)	Fisher 64 (raw)	Fisher 64 (128D)	VLAD 64 (128D)
UKB ( $4 \times \text{R@4}$ )	1.62	2.81	2.95	3.35	3.33	3.35
Holidays (mAP %)	36.5	54.0	45.2	59.5	56.5	55.7
Oxford (mAP %)	36.4	31.9	15.9	31.7	24.3	25.7
Copydays Crop 50% (+10k)	67.8	97.3	100.0	98.7	92.7	94.2
Copydays Strong (+10k)	27.7	70.7	26.9	59.6	41.2	42.7

The evaluation demonstrates that:

Fisher Vectors with $K=64$ components reduced to $D'=128$ dimensions (the size of a single SIFT descriptor) obtain 56.5% mAP on Holidays and 3.33 on UKB, outperforming full uncompressed 200k BOW (54.0% mAP on Holidays, 2.81 on UKB) while using several orders of magnitude less memory.
Global GIST descriptors perform poorly on object/location retrieval compared to local aggregation methods.
Dimensionality reduction of Fisher Vectors and VLAD to $D'=128$ preserves the majority of the retrieval performance of full-dimensional representations ( $D=4096$ ) while enabling compact product quantization indexing.

Knowl 12 — Large-Scale Image Retrieval Performance and Query Latency on 10M and 100M Datasets
empirical result
When evaluated on large-scale datasets merged with distractor images (INRIA Holidays with up to 10 million images from Flickr10M, and INRIA Copydays with up to 100 million images from Exalead100M):
1. Retrieval Accuracy on 10 Million Images: On Holidays combined with Flickr10M, a Fisher Vector ( $K=64$ ) reduced to $D'=96$ dimensions and indexed by IVFADC with $16 \times 8$ codes (16 bytes PQ code + 4 bytes image identifier = 20 bytes total per image) achieves 27.9% mAP on 1 million images (compared to 6.6% mAP for miniBOF at 20 bytes). A higher-capacity configuration ( $K=256$ , $D'=2048$ , $256 \times 10$ codes = 324 bytes) achieves 37.0% mAP on 1 million images.
2. Search Latency on 100 Million Images: Querying a 100 million image database using IVFADC ( $64 \times 8$ codes, visiting 64 lists out of 8192) takes 245 ms on a single processor core. This is more than two orders of magnitude faster than Bag-of-Words inverted index search (which requires 620 ms on a quad-core processor for 1 million images with a 200k vocabulary) while requiring only 68 bytes per image in RAM.

Coverage note — None was omitted; all primary theoretical models, algorithms, joint optimization methods, and large-scale experimental results have been captured.

References

1.J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, “Object retrieval with large vocabularies and fast spatial matching,” in CVPR, June 2007.
2.D. Nistér and H. Stewénius, “Scalable recognition with a vocabulary tree,” in CVPR, pp. 2161–2168, June 2006.
3.Z. Wu, Q. Ke, M. Isard, and J. Sun, “Bundling features for large scale partial-duplicate web image search,” in CVPR, pp. 25–32, 2009.
4.J. Law-To, L. Chen, A. Joly, I. Laptev, O. Buisson, V. Gouet-Brunet, N. Boujemaa, and F. Stentiford, “Video copy detection: a comparative study,” in CIVR, (New York, NY, USA), pp. 371–378, ACM, 2007.
5.M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman, “The PASCAL visual object classes (VOC) challenge,” International Journal of Computer Vision, vol. 88, pp. 303–338, June 2010.
6.J. Sivic and A. Zisserman, “Video Google: A text retrieval approach to object matching in videos,” in ICCV, pp. 1470–1477, October 2003.
7.D. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91–110, 2004.
8.K. Mikolajczyk and C. Schmid, “A performance evaluation of local descriptors,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 10, pp. 1615–1630, 2005.
9.S. Winder and M. Brown, “Learning local image descriptors,” in CVPR, June 2007.
10.S. Winder, G. Hua, and M. Brown, “Picking the best Daisy,” in CVPR, June 2009.
11.A. Torralba, R. Fergus, and Y. Weiss, “Small codes and large databases for recognition,” in CVPR, June 2008.
12.H. Jégou, M. Douze, and C. Schmid, “Packing bag-of-features,” in ICCV, September 2009.
13.O. Chum, M. Perdoch, and J. Matas, “Geometric min-hashing: Finding a (thick) needle in a haystack,” in CVPR, June 2009.
14.O. Chum, J. Philbin, and A. Zisserman, “Near duplicate image detection: min-hash and tf-idf weighting,” in BMVC, September 2008.
15.L. Torresani, M. Szummer, and A. Fitzgibbon, “Learning query-dependent prefilters for scalable image retrieval,” in CVPR, June 2009.
16.A. Oliva and A. Torralba, “Modeling the shape of the scene: a holistic representation of the spatial envelope,” International Journal of Computer Vision, vol. 42, no. 3, pp. 145–175, 2001.
17.B. Kulis and K. Grauman, “Kernelized locality-sensitive hashing for scalable image search,” in ICCV, October 2009.
18.Y. Weiss, A. Torralba, and R. Fergus, “Spectral hashing,” in NIPS, 2008.
19.M. Douze, H. Jégou, H. Singh, L. Amsaleg, and C. Schmid, “Evaluation of GIST descriptors for web-scale image search,” in CIVR, July 2009.
20.T. Jaakkola and D. Haussler, “Exploiting generative models in discriminative classifiers,” in NIPS, 1998.
21.F. Perronnin and C. R. Dance, “Fisher kernels on visual vocabularies for image categorization,” in CVPR, June 2007.
22.F. Perronnin, Y. Liu, J. Sanchez, and H. Poirier, “Large-scale image retrieval with compressed Fisher vectors,” in CVPR, June 2010.
23.H. Jégou, M. Douze, C. Schmid, and P. Pérez, “Aggregating local descriptors into a compact image representation,” in CVPR, June 2010.
24.H. Jégou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,” IEEE Transactions on Pattern Analysis & Machine Intelligence, vol. 33, pp. 117–128, January 2011.
25.K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, J. Matas, F. Schaffalitzky, T. Kadir, and L. V. Gool, “A comparison of affine region detectors,” International Journal of Computer Vision, vol. 65, no. 1/2, pp. 43–72, 2005.
26.H. Jégou, M. Douze, and C. Schmid, “Hamming embedding and weak geometric consistency for large scale image search,” in ECCV, October 2008.
27.J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, “Lost in quantization: Improving particular object retrieval in large scale image databases,” in CVPR, June 2008.
28.J. van Gemert, C. Veenman, A. Smeulders, and J. Geusebroek, “Visual word ambiguity,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 32, pp. 1271–1283, July 2010.
29.H. Jégou, M. Douze, and C. Schmid, “On the burstiness of visual elements,” in CVPR, June 2009.
30.J. Winn, A. Criminisi, and T. Minka, “Object categorization by learned universal visual dictionary,” in ICCV, 2005.
31.F. Perronnin, J. Sánchez, and Y. Liu, “Large-scale image categorization with explicit data embedding,” in CVPR, 2010.
32.A. Vedaldi and A. Zisserman, “Efficient additive kernels via explicit feature maps,” in CVPR, 2010.
33.X. Zhang, Z. Li, L. Zhang, W. Ma, and H.-Y. Shum, “Efficient indexing for large-scale visual search,” in ICCV, October 2009.
34.C. M. Bishop, Pattern Recognition and Machine Learning. Springer, 2007.
35.H. Jégou, M. Douze, and C. Schmid, “Improving bag-of-features for large scale image search,” International Journal of Computer Vision, vol. 87, pp. 316–336, February 2010.
36.M. Datar, N. Immorlica, P. Indyk, and V. Mirrokni, “Locality-sensitive hashing scheme based on p-stable distributions,” in Proceedings of the Symposium on Computational Geometry, pp. 253–262, 2004.
37.M. Muja and D. G. Lowe, “Fast approximate nearest neighbors with automatic algorithm configuration,” in VISAPP, February 2009.
38.G. Shakhnarovich, T. Darrell, and P. Indyk, Nearest-Neighbor Methods in Learning and Vision: Theory and Practice, ch. 3. MIT Press, March 2006.

Citation

MLA

Jegou, H., et al. “Aggregating Local Image Descriptors into Compact Codes”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, no. 9, 2012, pp. 1704–16, https://doi.org/10.1109/TPAMI.2011.235.

APA

Jegou, H., Perronnin, F., Douze, M., Sanchez, J., Perez, P., & Schmid, C. (2012). Aggregating Local Image Descriptors into Compact Codes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(9), 1704–1716. https://doi.org/10.1109/TPAMI.2011.235

Chicago

Jegou, H., F. Perronnin, M. Douze, J. Sanchez, P. Perez, and C. Schmid. 2012. “Aggregating Local Image Descriptors into Compact Codes”. IEEE Transactions on Pattern Analysis and Machine Intelligence 34 (9): 1704–16. https://doi.org/10.1109/TPAMI.2011.235.

Harvard

Jegou, H. et al. (2012) “Aggregating Local Image Descriptors into Compact Codes”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(9), pp. 1704–1716. Available at: https://doi.org/10.1109/TPAMI.2011.235.

Vancouver

1. Jegou H, Perronnin F, Douze M, Sanchez J, Perez P, Schmid C (2012) Aggregating Local Image Descriptors into Compact Codes. IEEE Transactions on Pattern Analysis and Machine Intelligence 34:1704–1716

BibTeX

@article{Jegou_2012, title={Aggregating Local Image Descriptors into Compact Codes}, volume={34}, ISSN={2160-9292}, url={http://dx.doi.org/10.1109/TPAMI.2011.235}, DOI={10.1109/tpami.2011.235}, number={9}, journal={IEEE Transactions on Pattern Analysis and Machine Intelligence}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Jegou, H. and Perronnin, F. and Douze, M. and Sanchez, J. and Perez, P. and Schmid, C.}, year={2012}, month=Sept, pages={1704–1716} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Aggregating Local Image Descriptors into Compact Codes

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Fisher Vector Representation for Aggregating Local Descriptors

Knowl 2 — Vector of Locally Aggregated Descriptors (VLAD)

Knowl 3 — VLAD as a Non-Probabilistic Limiting Case of the Fisher Vector

Knowl 4 — Implicit Background Information Removal in Fisher Vectors

Knowl 5 — Relation Between Fisher Vector and Bag-of-Words with Intrinsic IDF

Knowl 6 — Power and Euclidean Normalization of Aggregated Descriptors

Knowl 7 — Joint Optimization of PCA Dimensionality Reduction and Product Quantization

Knowl 8 — Variance Balancing across PCA Subspaces for Product Quantization

Knowl 9 — Asymmetric Distance Computation and Inverted File Indexing for Compact Image Codes

Knowl 10 — Dimensionality Reduction of Local SIFT Descriptors for Fisher Vector Estimation

Knowl 11 — Image Retrieval Performance Comparison of BOW, Fisher Vectors, and VLAD

Knowl 12 — Large-Scale Image Retrieval Performance and Query Latency on 10M and 100M Datasets

References

Citation

BibTeX

Access the Paper