Spherical Hashing

by Jae-Pil Heo, Youngwoon Lee, Junfeng He, Shih-Fu Chang, and Sung-eui Yoon.

IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012


Partitioning example of spherical hashing Comparison between our method and the state-of-the-art methods

Abstract

Many binary code encoding schemes based on hashing have been actively studied recently, since they can provide efficient similarity search, especially nearest neighbor search, and compact data representations suitable for handling large scale image databases in many computer vision problems. Existing hashing techniques encode high dimensional data points by using hyperplane-based hashing functions. In this paper we propose a novel hypersphere- based hashing function, spherical hashing, to map more spatially coherent data points into a binary code compared to hyperplane-based hashing functions. Furthermore, we propose a new binary code distance function, spherical Hamming distance, that is tailored to our hypersphere-based binary coding scheme, and design an efficient iterative optimization process to achieve balanced partitioning of data points for each hash function and independence between hashing functions. Our extensive experiments show that our spherical hashing technique significantly outperforms six state-of-the-art hashing techniques based on hyperplanes across various image benchmarks of sizes ranging from one to 75 million of GIST descriptors. The performance gains are consistent and large, up to 100% improvements. The excellent results confirm the unique merits of the proposed idea in using hyperspheres to encode proximity regions in high-dimensional spaces. Finally, our method is intuitive and easy to implement.


Contents

Paper: Paper (PDF, 0.5MB), Supplementary report (PDF, 0.2MB), Slide (PDF, 1.9MB)

Source Codes (C++, Matlab)

Journal Version (PDF, 1.3MB)
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015 (accepted)





Dept. of Computer Science
KAIST
373-1 Guseong-dong, Yuseong-gu, Daejeon, 305-701
South Korea
sglabkaist dot gmail dot com