Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Angry Crowds: Detecting Violent Events in Videos Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Approximate Search with Quantized Sparse Representations

Authors : Himalaya Jain, Patrick Pérez, Rémi Gribonval, Joaquin Zepeda, Hervé Jégou

Published in: Computer Vision – ECCV 2016

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper tackles the task of storing a large collection of vectors, such as visual descriptors, and of searching in it. To this end, we propose to approximate database vectors by constrained sparse coding, where possible atom weights are restricted to belong to a finite subset. This formulation encompasses, as particular cases, previous state-of-the-art methods such as product or residual quantization. As opposed to traditional sparse coding methods, quantized sparse coding includes memory usage as a design constraint, thereby allowing us to index a large collection such as the BIGANN billion-sized benchmark. Our experiments, carried out on standard benchmarks, show that our formulation leads to competitive solutions when considering different trade-offs between learning/coding time, index size and search quality.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter FigureSeer: Parsing Result-Figures in Research Papers
next chapter Sympathy for the Details: Dense Trajectories and Hybrid Classification Architectures for Action Recognition
Footnotes
1
Throughout we use the terminology codebook for a collection of vectors, the codewords, that can be added, and dictionary for a collection of normalized vectors, the atoms, which can be linearly combined.
 
2
Not maximum absolute inner-product as in matching pursuit. This permits to get a tighter distribution of weights, which will make easier their subsequent quantization.
 
3
Alternate refinement of the vector dictionaries \(C^m\)s and of the coefficient codebook A led to no improvement. A possible reason is that dictionaries update does not take into account that the coefficients are vector quantized, and we do not see a principled way to do so.
 
4
VLAD vectors, as kindly provided by Relja Arandjelović, are PCA-compressed to 128 dimensions and unit \(\ell ^2\)-normalized; SIFT vectors are 128-dimensional and have almost constant \(\ell ^2\)-norm of 512, yielding almost identical nearest-neighbors for cosine similarity and \(\ell ^2\) distance.
 
5
Note also that CKM/OPQ improve on PQ in a way that is complimentary to \(\text {Q}\alpha \text {-PQ}\). In experiments not reported here, we observed that using OPQ instead of PQ within \(\text {Q}\alpha \text {-PQ}\) gives similar gains as OPQ gives over PQ.
 
Literature
1.
Ge, T., He, K., Ke, Q., Sun, J.: Optimized product quantization for approximate nearest neighbor search. In: CVPR (2013)
2.
Jégou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. 33(1), 117–128 (2011)CrossRef
3.
Norouzi, M., Fleet, D.: Cartesian k-means. In: CVPR (2013)
4.
Ai, L., Yu, J., Wu, Z., He, Y., Guan, T.: Optimized residual vector quantization for efficient approximate nearest neighbor search. Multimed. Syst. 1–13 (2015). doi:10.​1007/​s00530-015-0470-9
5.
Chen, Y., Guan, T., Wang, C.: Approximate nearest neighbor search by residual vector quantization. Sensors 10(12), 11259–11273 (2010)CrossRef
6.
Jégou, H., Tavenard, R., Douze, M., Amsaleg, L.: Searching in one billion vectors: re-rank with source coding. In: ICASSP (2011)
7.
Martinez, J., Hoos, H.H., Little, J.J.: Stacked quantizers for compositional vector compression. arXiv preprint arXiv:​1411.​2173 (2014)
8.
Zhang, T., Du, C., Wang, J.: Composite quantization for approximate nearest neighbor search. In: ICML (2014)
9.
Zhang, T., Qi, G.J., Tang, J., Wang, J.: Sparse composite quantization. In: CVPR (2015)
10.
Vedaldi, A., Zisserman, A.: Sparse kernel approximations for efficient classification and detection. In: CVPR (2012)
11.
Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: STOC (1998)
12.
Charikar, M.S.: Similarity estimation techniques from rounding algorithms. In: STOC (2002)
13.
Wang, J., Liu, W., Kumar, S., Chang, S.: Learning to hash for indexing big data - A survey. CoRR (2015)
14.
Lv, Q., Charikar, M., Li, K.: Image similarity search with compact data structures. In: CIKM (2004)
15.
Norouzi, M., Punjani, A., Fleet, D.J.: Fast search in hamming space with multi-index hashing. In: CVPR (2012)
16.
Torralba, A., Fergus, R., Weiss, Y.: Small codes and large image databases for recognition. In: CVPR (2008)
17.
Wang, J., Kumar, S., Chang, S.F.: Semi-supervised hashing for large scale search. IEEE Trans. Pattern Anal. Mach. Intell. 34(12), 2393–2406 (2012)CrossRef
18.
Xu, H., Wang, J., Li, Z., Zeng, G., Li, S., Yu, N.: Complementary hashing for approximate nearest neighbor search. In: ICCV (2011)
19.
Gersho, A., Gray, R.M.: Vector Quantization and Signal Compression, vol. 159. Springer Science & Business Media, New York (2012)MATH
20.
Heo, J.P., Lin, Z., Yoon, S.E.: Distance encoded product quantization. In: CVPR (2014)
21.
Babenko, A., Lempitsky, V.: Additive quantization for extreme vector compression. In: CVPR (2014)
22.
Babenko, A., Lempitsky, V.: Tree quantization for large-scale similarity search and classification. In: CVPR (2015)
23.
Barnes, C.F., Rizvi, S., Nasrabadi, N.: Advances in residual vector quantization: a review. IEEE Trans. Image Process. 5(2), 226–262 (1996)CrossRef
24.
Juang, B.H., Gray, A.J.: Multiple stage vector quantization for speech coding. In: ICASSP (1982)
25.
Elad, M.: Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer, New York (2010)CrossRefMATH
26.
Mairal, J., Bach, F., Ponce, J., Sapiro, G.: Online learning for matrix factorization and sparse coding. J. Mach. Learn. Res. 11, 19–60 (2010)MathSciNetMATH
27.
Wright, J., Ma, Y., Mairal, J., Sapiro, G., Huang, T.S., Yan, S.: Sparse representation for computer vision and pattern recognition. Proc. IEEE 98(6), 1031–1044 (2010)CrossRef
28.
Ge, T., He, K., Sun, J.: Product sparse coding. In: CVPR (2014)
29.
Zepeda, J., Guillemot, C., Kijak, E.: Image compression using sparse representations and the iteration-tuned and aligned dictionary. IEEE J. Sel. Top. Sig. Process. 5, 1061–1073 (2011)CrossRef
30.
Zepeda, J., Guillemot, C., Kijak, E.: The iteration-tuned dictionary for sparse representations. In: IEEE Workshop on Multimedia Signal Processing (2010)
31.
Frossard, P., Vandergheynst, P., Kunt, M., et al.: A posteriori quantization of progressive matching pursuit streams. IEEE Trans. Sig. Process. 52(2), 525–535 (2004)MathSciNetCrossRef
32.
Yaghoobi, M., Blumensath, T., Davies, M.: Quantized sparse approximation with iterative thresholding for audio coding. In: ICASSP (2007)
33.
34.
Mallat, S.G., Zhang, Z.: Matching pursuits with time-frequency dictionaries. IEEE Trans. Sig. Process. 41(12), 3397–3415 (1993)CrossRefMATH
35.
Jégou, H., Douze, M., Schmid, C.: Searching with quantization: approximate nearest neighbor search using short codes and distance estimators. Technical report (2009)
36.
Arandjelovic, R., Zisserman, A.: All about VLAD. In: CVPR (2013)
37.
Babenko, A., Lempitsky, V.: The inverted multi-index. In: CVPR (2012)
Metadata
Title
Approximate Search with Quantized Sparse Representations
Authors
Himalaya Jain
Patrick Pérez
Rémi Gribonval
Joaquin Zepeda
Hervé Jégou
Copyright Year
2016
Book
Computer Vision – ECCV 2016

Print ISBN: 978-3-319-46477-0

Electronic ISBN: 978-3-319-46478-7

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-46478-7_42

Premium Partner

    Image Credits