Quadra-Embedding: Binary Code Embedding with Low Quantization Error

Abstract

Thanks to their compact data representations and fast similarity computation, many binary code embedding techniques have been recently proposed for large-scale similarity search used in many computer vision applications including image retrieval. Most of prior techniques have centered around optimizing a set of projections for accurate embedding. In spite of active research efforts, existing solutions suffer from diminishing marginal efficiency as more code bits are used, and high quantization errors naturally coming from the binarization. In order to reduce both quantization error and diminishing efficiency we propose a novel binary code embedding scheme that assigns two bits for each projection to define four quantization regions, and a novel binary code distance function tailored specifically to our encoding scheme. Furthermore, we formulate an optimization problem of finding four quantization regions, in order to maximize benefits of our encoding scheme. Our method is directly applicable to a wide variety of binary code embedding methods. Our scheme combined with four state-of-the-art embedding methods has been evaluated with four public image benchmarks. We have observed that our scheme achieves meaningful accuracy improvement (up to 100%) in most experimental configurations under k- and e-NN search.