nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Local Orthogonal-Group Testing

verfasst von : Ahmet Iscen, Ondřej Chum

Erschienen in: Computer Vision – ECCV 2018

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This work addresses approximate nearest neighbor search applied in the domain of large-scale image retrieval. Within the group testing framework we propose an efficient off-line construction of the search structures. The linear-time complexity orthogonal grouping increases the probability that at most one element from each group is matching to a given query. Non-maxima suppression with each group efficiently reduces the number of false positive results at no extra cost. Unlike in other well-performing approaches, all processing is local, fast, and suitable to process data in batches and in parallel. We experimentally show that the proposed method achieves search accuracy of the exhaustive search with significant reduction in the search complexity. The method can be naturally combined with existing embedding methods.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel ForestHash: Semantic Hashing with Shallow Random Forests and Tiny Convolutional Networks

Nächstes Kapitel Rolling Shutter Pose and Ego-Motion Estimation Using Shape-from-Template

Nur mit Berechtigung zugänglich

Matlab source code provided in supplementary material.

Sivic, J., Zisserman, A.: Video Google: a text retrieval approach to object matching in videos. In: ICCV (2003)

Philbin, J., Chum, O., Isard, M., Sivic, J., Zisserman, A.: Object retrieval with large vocabularies and fast spatial matching. In: CVPR, June 2007

Philbin, J., Chum, O., Isard, M., Sivic, J., Zisserman, A.: Lost in quantization: improving particular object retrieval in large scale image databases. In: CVPR, June 2008

Jégou, H., Douze, M., Schmid, C.: Improving bag-of-features for large scale image search. IJCV 87(3), 316–336 (2010)CrossRef

Jégou, H., Schmid, C., Harzallah, H., Verbeek, J.: Accurate image search using the contextual dissimilarity measure. IEEE Trans. PAMI 32(1), 2–11 (2010)CrossRef

van Gemert, J.C., Veenman, C., Smeulders, A.W., Geusebroek, J.: Visual word ambiguity. IEEE Trans. PAMI 32(7), 1271–1283 (2010)CrossRef

Babenko, A., Lempitsky, V.: The inverted multi-index. In: CVPR, June 2012

Jégou, H., Douze, M., Schmid, C., Pérez, P.: Aggregating local descriptors into a compact image representation. In: CVPR, June 2010

Perronnin, F., Dance, C.R.: Fisher kernels on visual vocabularies for image categorization. In: CVPR, June 2007

10.

Perronnin, F., Sánchez, J., Mensink, T.: Improving the fisher kernel for large-scale image classification. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010. LNCS, vol. 6314, pp. 143–156. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15561-1_11CrossRef

11.

Babenko, A., Slesarev, A., Chigorin, A., Lempitsky, V.: Neural codes for image retrieval. In: Fleet, D., Pajdla, T., Schiele, B., Tuytelaars, T. (eds.) ECCV 2014. LNCS, vol. 8689, pp. 584–599. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10590-1_38CrossRef

12.

Tolias, G., Sicre, R., Jégou, H.: Particular object retrieval with integral max-pooling of CNN activations. In: ICLR (2016)

13.

Gordo, A., Almazán, J., Revaud, J., Larlus, D.: Deep image retrieval: learning global representations for image search. In: Leibe, B., Matas, J., Sebe, N., Welling, M. (eds.) ECCV 2016. LNCS, vol. 9910, pp. 241–257. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46466-4_15CrossRef

14.

Radenović, F., Tolias, G., Chum, O.: CNN image retrieval learns from BoW: unsupervised fine-tuning with hard examples. In: Leibe, B., Matas, J., Sebe, N., Welling, M. (eds.) ECCV 2016. LNCS, vol. 9905, pp. 3–20. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46448-0_1CrossRef

15.

Radenović, F., Tolias, G., Chum, O.: Fine-tuning CNN image retrieval with no human annotation. arXiv preprint arXiv:1711.02512 (2017)

16.

Muja, M., Lowe, D.G.: Scalable nearest neighbor algorithms for high dimensional data. IEEE Trans. PAMI 36, 2227–2240 (2014)CrossRef

17.

Nistér, D., Stewénius, H.: Scalable recognition with a vocabulary tree. In: CVPR, pp. 2161–2168, June 2006

18.

Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: STOC, pp. 604–613 (1998)

19.

Gionis, A., Indyk, P., Motwani, R.: Similarity search in high dimension via hashing. In: VLDB, pp. 518–529 (1999)

20.

Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.: Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Symposium on Computational Geometry (2004)

21.

Lv, Q., Charikar, M., Li, K.: Image similarity search with compact data structures. In: CIKM, pp. 208–217, November 2004

22.

Norouzi, M., Punjani, A., Fleet, D.J.: Fast search in hamming space with multi-index hashing. In: CVPR (2012)

23.

Weiss, Y., Torralba, A., Fergus, R.: Spectral hashing. In: NIPS, December 2009

24.

Raginsky, M., Lazebnik, S.: Locality-sensitive binary codes from shift-invariant kernels. In: NIPS (2010)

25.

Jégou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. IEEE Trans. PAMI 33(1), 117–128 (2011)CrossRef

26.

Ge, T., He, K., Ke, Q., Sun, J.: Optimized product quantization for approximate nearest neighbor search. In: CVPR, June 2013

27.

Kalantidis, Y., Avrithis, Y.: Locally optimized product quantization for approximate nearest neighbor search. In: CVPR, (2014)

28.

Jain, H., Zepeda, J., Pérez, P., Gribonval, R.: Subic: a supervised, structured binary code for image search. In: ICCV (2017)

29.

Jain, H., Zepeda, J., Pérez, P., Gribonval, R.: Learning a complete image indexing pipeline (2018)

30.

Dorfman, R.: The detection of defective members of large populations. The Ann. Math. Stat. 14(4), 436–440 (1943)CrossRef

31.

Iscen, A., Furon, T., Gripon, V., Rabbat, M., Jégou, H.: Memory vectors for similarity search in high-dimensional spaces. IEEE Trans. Big Data 4(1), 65–77 (2018)CrossRef

32.

Shi, M., Furon, T., Jégou, H.: A group testing framework for similarity search in high-dimensional spaces. In: ACM Multimedia, November 2014

33.

Iscen, A., Amsaleg, L., Furon, T.: Scaling group testing similarity search. In: ACM ICMR (2016)

34.

Iscen, A., Rabbat, M., Furon, T.: Efficient large-scale similarity search using matrix factorization. In: CVPR (2016)

35.

Rao, C.R., Mitra, S.K.: Generalized inverse of a matrix and its applications. In: Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability: Theory of Statistics, vol. 1 (1972)

36.

Aldridge, M., Baldassini, L., Johnson, O.: Group testing algorithms: bounds and simulations. IEEE Trans. Inform Theory 60, 3671–3687 (2014)MathSciNetCrossRef

37.

Bickson, D., Baron, D., Ihler, A., Avissar, H., Dolev, D.: Fault identification via nonparametric belief propagation. IEEE Trans. Signal Process. 59(6), 2602–2613 (2011)MathSciNetCrossRef

38.

Cheraghchi, M., Hormati, A., Karbasi, A., Vetterli, M.: Compressed sensing with probabilistic measurements: a group testing solution. In: 47th Annual Allerton Conference on Communication, Control, and Computing (2009)

39.

Gilbert, A., Indyk, P.: Sparse recovery using sparse matrices. Proc. IEEE 98(6), 937–947 (2010)CrossRef

40.

Sejdinovic, D., Johnson, O.: Note on noisy group testing: asymptotic bounds and belief propagation reconstruction. In: 48th Annual Allerton Conference on Communication, Control, and Computing (2010)

41.

Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.: Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. In: ASILOMAR, pp. 40–44 (1993)

42.

Davis, G.M., Mallat, S.G., Zhang, Z.: Adaptive time-frequency decompositions with matching pursuit. In: SPIE’s International Symposium on Optical Engineering and Photonics in Aerospace Sensing, pp. 402–413 (1994)

43.

Radenović, F., Iscen, A., Tolias, G., Avrithis, Y., Chum, O.: Revisiting oxford and paris: large-scale image retrieval benchmarking. In: CVPR (2018)

44.

Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. ACM 51(4), 606–635 (2004)MathSciNetCrossRef

45.

Feldman, D., Feigin, M., Sochen, N.: Learning big (image) data via coresets for dictionaries. J. Math. Imaging Vis. 46(3), 276–291 (2013)MathSciNetCrossRef

46.

Johnson, J., Douze, M., Jégou, H.: Billion-scale similarity search with GPUs. arXiv preprint arXiv:1702.08734 (2017)

47.

Malkov, Y.A., Yashunin, D.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. arXiv preprint arXiv:1603.09320 (2016)

Titel: Local Orthogonal-Group Testing
verfasst von: Ahmet Iscen
Ondřej Chum
Verlag: Springer International Publishing
Buch: Computer Vision – ECCV 2018
Print ISBN: 978-3-030-01215-1

Electronic ISBN: 978-3-030-01216-8

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-01216-8_28

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"