W-Tree Indexing for Fast Visual Word Generation

Miaojing Shi, Ruixin Xu, Dacheng Tao, Chao Xu

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

The bag-of-visual-words representation has been widely used in image retrieval and visual recognition. The most time-consuming step in obtaining this representation is the visual word generation, i.e., assigning visual words to the corresponding local features in a high-dimensional space. Recently, structures based on multibranch trees and forests have been adopted to reduce the time cost. However, these approaches cannot perform well without a large number of backtrackings. In this paper, by considering the spatial correlation of local features, we can significantly speed up the time consuming visual word generation process while maintaining accuracy. In particular, visual words associated with certain structures frequently co-occur; hence, we can build a co-occurrence table for each visual word for a large-scale data set. By associating each visual word with a probability according to the corresponding co-occurrence table, we can assign a probabilistic weight to each node of a certain index structure (e.g., a KD-tree and a K-means tree), in order to re-direct the searching path to be close to its global optimum within a small number of backtrackings. We carefully study the proposed scheme by comparing it with the fast library for approximate nearest neighbors and the random KD-trees on the Oxford data set. Thorough experimental results suggest the efficiency and effectiveness of the new scheme.
Original languageEnglish
Pages (from-to)1209-1222
Number of pages14
JournalIEEE Transactions on Image Processing
Issue number3
Publication statusPublished - 1 Mar 2013


Dive into the research topics of 'W-Tree Indexing for Fast Visual Word Generation'. Together they form a unique fingerprint.

Cite this