Compressing Feature Sets with Digital Search Trees

Abstract

State-of-the-art image retrieval pipelines are based on “bag-of-words” matching. We note that the original order in which features are extracted from the image is discarded in the “bag-of-words” matching pipeline. As a result, a set of features extracted from a query image can be transmitted in any order. A set of m unique features has m! orderings, and if the order of transmission can be discarded, one can reduce the query size by an additional log 2 (m!) bits. We propose a coding scheme based on Digital Search Trees that reduces size of a set of features by approximately log 2 (m!) bits. We perform analysis of the scheme, and show how it applies to any set of symbols in which order can be discarded. We illustrate how the scheme can be applied to a set of low bitrate Compressed Histogram of Gradients (CHoG) descriptors.

Original document

The different versions of the original document can be found in:

• http://reznik.org/papers/IWMV2011_CHOGDST.pdf

• http://vijaychan.github.io/Publications/2011%20-%20Compressing%20Feature%20Sets%20with%20Digital%20Search%20Trees.pdf,

https://dblp.uni-trier.de/db/conf/iccvw/iccvw2011.html#ChandrasekharRTCTGG11,

http://yadda.icm.edu.pl/yadda/element/bwmeta1.element.ieee-000006130219,

http://www.reznik.org/papers/IWMV2011_CHOGDST.pdf,

https://www.researchgate.net/profile/Yuriy_Reznik/publication/221429973_Compressing_Feature_Sets_with_Digital_Search_Trees/links/540ed6130cf2d8daaace2bd5.pdf,

https://academic.microsoft.com/#/detail/2039743183

• http://xplorestaging.ieee.org/ielx5/6114268/6130192/06130219.pdf?arnumber=6130219,

http://dx.doi.org/10.1109/iccvw.2011.6130219