Quadra-Embedding: Binary Code Embedding with Low Quantization Error

Youngwoon Lee, Jae-Pil Heo, and Sung-eui Yoon
KAIST
To appear Asian Conference on Computer Vision (ACCV), 2012


Quantization scheme and distance metric of Quadra Embedding

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.

Publication

Quadra-Embedding: Binary Code Embedding with Low Quantization Error [PDF][SLIDES][CODE]
Youngwoon Lee, Jae-Pil Heo, and Sung-Eui Yoon
Computer Vision and Image Understanding (CVIU), 2014 [PDF]
To appear Asian Conference on Computer Vision (ACCV), Daejeon, Korea, November 2012.

Related Links

Spherical Hashing