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:
Visual Tracking by Local Superpixel Matching with Markov Random Field Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Sparse Matrix Based Hashing for Approximate Nearest Neighbor Search

Authors : Min Wang, Wengang Zhou, Qi Tian, Houqiang Li

Published in: Advances in Multimedia Information Processing - PCM 2016

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Binary hashing has been widely studied for approximate nearest neighbor (ANN) search with its compact representation and efficient comparison. Many existing hashing methods aim at improving the accuracy of ANN search, but ignore the complexity of generating binary codes. In this paper, we propose a new unsupervised hashing method based on a sparse matrix, named as Sparse Matrix based Hashing (SMH). There are only three kinds of elements in our sparse matrix, i.e., +1, \(-1\) and 0. We learn the sparse matrix by optimizing a new pair-wise distance-preserving objective, in which the linear projection on the Euclidean distance and the corresponding Hamming distance is preserved. With the special form of the sparse matrix, the optimization can be solved by a greedy algorithm. The experiments on two large-scale datasets demonstrate that SMH expedites the process of generating binary codes, and achieves competitive performance with the state-of-the-art unsupervised hashing methods.

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 Saliency-Based Objective Quality Assessment of Tone-Mapped Images
next chapter Piecewise Affine Sparse Representation via Edge Preserving Image Smoothing
Footnotes
1
a, b are scalars, the multiplication between a and \({\mathbf {E}}\) is element-wise multiplication between a and each element of \({\mathbf {E}}\), and the subtraction to b is also element-wise, we omit the \({\mathbf {1}}\) vector for concise.
 
Literature
1.
Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.S.: Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry, pp. 253–262. ACM (2004)
2.
Kulis, B., Grauman, K.: Kernelized locality-sensitive hashing. PAMI 34, 1092–1104 (2012)CrossRef
3.
Raginsky, M., Lazebnik, S.: Locality-sensitive binary codes from shift-invariant kernels. In: NIPS, pp. 1509–1517 (2009)
4.
Gong, Y., Lazebnik, S.: Iterative quantization: a procrustean approach to learning binary codes. In: CVPR, pp. 817–824 (2011)
5.
Heo, J., Lee, Y., He, J., Chang, S., Yoon, S.: Spherical hashing. In: CVPR, pp. 2957–2964 (2012)
6.
Erin Liong, V., Lu, J., Wang, G., Moulin, P., Zhou, J.: Deep hashing for compact binary codes learning. In: CVPR, pp. 2475–2483 (2015)
7.
He, K., Wen, F., Sun, J.: K-means hashing: an affinity-preserving quantization method for learning binary compact codes. In: CVPR, pp. 2938–2945 (2013)
8.
Weiss, Y., Torralba, A., Fergus, R.: Spectral hashing. In: NIPS, pp. 1753–1760 (2009)
9.
Kulis, B., Darrell, T.: Learning to hash with binary reconstructive embeddings. In: NIPS, pp. 1042–1050 (2009)
10.
Norouzi, M., Fleet, D.J.: Minimal loss hashing for compact binary codes. In: ICML, pp. 353–360 (2011)
11.
Carreira-Perpinán, M.A., Raziperchikolaei, R.: Hashing with binary autoencoders. In: CVPR, pp. 557–566 (2015)
12.
Ambai, M., Yoshida, Y.: CARD: compact and real-time descriptors. In: ICCV, pp. 97–104 (2011)
13.
Jegou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. PAMI 33, 117–128 (2011)CrossRef
14.
Wang, J., Kumar, S., Chang, S.: Semi-supervised hashing for large-scale search. PAMI 34, 2393–2406 (2012)CrossRef
15.
Liu, W., Wang, J., Ji, R., Jiang, Y., Chang, S.: Supervised hashing with kernels. In: CVPR, pp. 2074–2081 (2012)
16.
Xia, R., Pan, Y., Lai, H., Liu, C., Yan, S.: Supervised hashing for image retrieval via image representation learning. In: AAAI (2014)
17.
Zhang, M., Shen, F., Zhang, H., Xie, N., Yang, W.: Hashing with inductive supervised learning. In: PCM, pp. 447–455 (2015)
18.
Xie, H., Chen, Z., Liu, Y., Tan, J., Guo, L.: Data-dependent locality sensitive hashing. In: Ooi, W.T., Snoek, C.G.M., Tan, H.K., Ho, C.-K., Huet, B., Ngo, C.-W. (eds.) PCM 2014. LNCS, vol. 8879, pp. 284–293. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-13168-9_​32
19.
Li, P., Wang, M., Cheng, J., Xu, C., Lu, H.: Spectral hashing with semantically consistent graph for image indexing. TMM 15(1), 141–152 (2013)
20.
Zhou, W., Yang, M., Wang, X., Li, H., Lin, Y., Tian, Q.: Scalable feature matching by dual cascaded scalar quantization for image retrieval. PAMI 38(1), 159–171 (2016)CrossRef
21.
Zhou, W., Li, H., Hong, R., Lu, Y., Tian, Q.: BSIFT: towards data-independent codebook for large scale image search. TIP 24(3), 967–979 (2015)MathSciNet
22.
Zhou, W., Yang, M., Li, H., Wang, X., Lin, Y., Tian, Q.: Towards codebook-free: scalable cascaded hashing for mobile image search. TMM 16(3), 601–611 (2014)
23.
Liu, Z., Li, H., Zhou, W., Zhao, R., Tian, Q.: Contextual hashing for large-scale image search. TIP 23(4), 1606–1614 (2014)MathSciNet
24.
Zhou, W., Lu, Y., Li, H., Tian, Q.: Scalar quantization for large scale image search. In: MM (2012)
25.
Zhou, W., Lu, Y., Li, H., Song, Y., Tian, Q.: Spatial coding for large scale partial-duplicate web image search. In: MM, pp. 131–140 (2010)
Metadata
Title
Sparse Matrix Based Hashing for Approximate Nearest Neighbor Search
Authors
Min Wang
Wengang Zhou
Qi Tian
Houqiang Li
Copyright Year
2016
Book
Advances in Multimedia Information Processing - PCM 2016

Print ISBN: 978-3-319-48889-9

Electronic ISBN: 978-3-319-48890-5

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-48890-5_55