Quantization Schemes for Low Bitrate Compressed Histogram of Gradients Descriptors

We study different quantization schemes for the Com-pressed Histogram of Gradients (CHoG) image feature de-scriptor. We propose a scheme for compressing distribu-tions called Type Coding, which offers lower complexity and higher compression efficiency compared to tree-based quantization schemes proposed in prior work. We construct optimal Entropy Constrained Vector Quantization (ECVQ) code-books and show that Type Coding comes close to achieving optimal performance. The proposed descriptors are 16 × smaller than SIFT and perform on par. We im-plement the descriptor in a mobile image retrieval system and for a database of 1 million CD, DVD and book covers, we achieve 96 % retrieval accuracy using only 4 kilobytes of data per query image. 1