Pruning tree-structured vector quantizer towards low bit rate mobile visual search

Coming with the proliferation of mobile devices, mobile visual search emerges. One fundamental issue here is the query transmission latency, especially in a bandwidth constraint wireless link. Towards low bit rate retrieval, recent works have proposed to extract compact visual descriptors directly on the mobile end, where the vocabulary tree based bag-of-words representation has shown superior performance in producing compact descriptors [2][9]. However, the corresponding tree-structure vector quantizer is extremely large against a mobile end implementation. In this paper, we propose two alternatives to prune this tree structure based on the subtree discriminability analysis, where either information gain based or ranking based pruning are investigated. Furthermore, we have unveiled that the tree structure can be even discarded while retaining only the discriminative leaves together with their radii in practice. We evaluate our tree pruning on Android HTC Desire G7, with application to low bit rate mobile landmark search in a 10-million landmark photo collection, where over 10 scale memory reduction with almost identical search accuracy is reported.