  Hashing is at the heart of large-scale image similarity search, and recent
methods have been substantially improved through deep learning techniques. Such
algorithms typically learn continuous embeddings of the data. To avoid a
subsequent costly binarization step, a common solution is to employ loss
functions that combine a similarity learning term (to ensure similar images are
grouped to nearby embeddings) and a quantization penalty term (to ensure that
the embedding entries are close to binarized entries, e.g., -1 or 1). Still,
the interaction between these two terms can make learning harder and the
embeddings worse. We propose an alternative quantization strategy that
decomposes the learning problem in two stages: first, perform similarity
learning over the embedding space with no quantization; second, find an optimal
orthogonal transformation of the embeddings so each coordinate of the embedding
is close to its sign, and then quantize the transformed embedding through the
sign function. In the second step, we parametrize orthogonal transformations
using Householder matrices to efficiently leverage stochastic gradient descent.
Since similarity measures are usually invariant under orthogonal
transformations, this quantization strategy comes at no cost in terms of
performance. The resulting algorithm is unsupervised, fast, hyperparameter-free
and can be run on top of any existing deep hashing or metric learning
algorithm. We provide extensive experimental results showing that this approach
leads to state-of-the-art performance on widely used image datasets, and,
unlike other quantization strategies, brings consistent improvements in
performance to existing deep hashing algorithms.
