Randomized locality sensitive vocabularies for bag-of-features model

Yadong Mu, Ju Sun, Tony X. Han, Loong Fah Cheong, Shuicheng Yan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations


Visual vocabulary construction is an integral part of the popular Bag-of-Features (BOF) model. When visual data scale up (in terms of the dimensionality of features or/and the number of samples), most existing algorithms (e.g. k-means) become unfavorable due to the prohibitive time and space requirements. In this paper we propose the random locality sensitive vocabulary (RLSV) scheme towards efficient visual vocabulary construction in such scenarios. Integrating ideas from the Locality Sensitive Hashing (LSH) and the Random Forest (RF), RLSV generates and aggregates multiple visual vocabularies based on random projections, without taking clustering or training efforts. This simple scheme demonstrates superior time and space efficiency over prior methods, in both theory and practice, while often achieving comparable or even better performances. Besides, extensions to supervised and kernelized vocabulary constructions are also discussed and experimented with.

Original languageEnglish (US)
Title of host publicationComputer Vision, ECCV 2010 - 11th European Conference on Computer Vision, Proceedings
PublisherSpringer Verlag
Number of pages14
EditionPART 3
ISBN (Print)364215557X, 9783642155574
StatePublished - 2010
Externally publishedYes
Event11th European Conference on Computer Vision, ECCV 2010 - Heraklion, Crete, Greece
Duration: Sep 10 2010Sep 11 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 3
Volume6313 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th European Conference on Computer Vision, ECCV 2010
CityHeraklion, Crete

Bibliographical note

Funding Information:
Support of IDMPO Grant R-705-000-018-279 Singapore and NRF/IDM Program under research Grant NRF2008IDMIDM004-029 are gratefully acknowledged.


Dive into the research topics of 'Randomized locality sensitive vocabularies for bag-of-features model'. Together they form a unique fingerprint.

Cite this