Fried binary embedding: From high-dimensional visual features to high-dimensional binary codes

Most existing binary embedding methods prefer compact binary codes (b-dimensional) to avoid high computational and memory cost of projecting high-dimensional visual features (d-dimensional, b < d). We argue that long binary codes (b ∼ O(d)) are critical to fully utilize the discriminative power of high-dimensional visual features, and can achieve better results in various tasks such as approximate nearest neighbor search. Generating long binary codes involves large projection matrix and high-dimensional matrix-vector multiplication, thus is memory and compute intensive. We propose Fried binary embedding (FBE) and Supervised Fried Binary Embedding (SuFBE), to tackle these problems. FBE is suitable for most of the practical applications in which the labels of training data are not given, while SuFBE can significantly boost the accuracy in the cases that the training labels are available. The core idea is to decompose the projection matrix using adaptive Fastfood transform, which is the multiplication of several structured matrices. As a result, FBE and SuFBE can reduce the computational complexity from O(d²) to O(d log d), and memory cost from O(d²) to O(d), respectively. More importantly, by using the structured matrices, FBE and SuFBE can well regulate projection matrix by reducing its tunable parameters and lead to even better accuracy than using either unconstrained projection matrix (like ITQ) or sparse matrix such as SP and SSP with the same long code length. Experimental comparisons with state-of-the-art methods over various visual applications demonstrate both the efficiency and performance advantages of FBE and SuFBE.