STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINES

1

Push for Quantization: Deep Fisher Hashing
Yunqiang Li? 1

1

Vision Lab, Delft University ofTechnology, Netherlands

Wenjie Pei? 22

Tencent, China

wenjiecoder@outlook.com

3

School of Computer Science,
Northwestern Polytechnical
University, Xi’an, China

y.li-19@tudelft.nl

Yufei zha∗ 3zhayufei@126.com

Jan van Gemert1
j.c.vangemert@tudelft.nl

Abstract
Current massive datasets demand light-weight access for analysis. Discrete hashingmethods are thus beneficial because they map high-dimensional data to compact binary
codes that are efficient to store and process, while preserving semantic similarity. To
optimize powerful deep learning methods for image hashing, gradient-based methods are
required. Binary codes, however, are discrete and thus have no continuous derivatives.
Relaxing the problem by solving it in a continuous space and then quantizing the solution
is not guaranteed to yield separable binary codes. The quantization needs to be includedin the optimization. In this paper we push for quantization: We optimize maximum
class separability in the binary space. To do so, we introduce a margin on distances
between dissimilar image pairs as measured in the binary space. In addition to pairwise distances, we draw inspiration from Fisher’s Linear Discriminant Analysis (Fisher
LDA) to maximize the binary distances between classes and at the same time minimize
the binary distance of images within the same class. Experimental results on CIFAR10, NUS-WIDE and ImageNet100 show that our approach leads to compact codes andcompares favorably to the current state of the art.

1

Introduction

Image hashing aims to map high-dimensional images onto compact binary codes where pairwise distances between binary codes corresponds to semantic image distances, i.e., Similar
binary codes should have similar class labels. Binary codes are efficient to store and have
low computational cost which is particularly relevant in today’s big data age where hugedatasets demand fast processing.
A problem in applying powerful deep learning methods for image hashing is that deep
nets are optimized using gradient descent while binary codes are discrete and thus have nocontinuous derivatives and cannot be directly optimized by gradient descent. The current
solution [2, 12, 20, 22, 37, 39] is to relax the discrete problem to a continuous one, and after
optimization in the continuous space, quantize it to obtain discrete codes. This approach,however, disregards the importance of the quantization, which is problematic because image? Both authors contributed equally. ∗ Corresponding Authorc 2019. The copyright of this document resides with its authors.
It may be distributed unchanged freely in print or electronic forms.

2

STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINES

class similarity in the continuous space is not necessarily preserved in the binary space, as
illustrated in Fig. 1. The quantization needs to be included in the optimization.
In this paper we go beyond preserving semantic distances in the continuous space: We
push for quantization by optimizing maximum class separability in the binary space. To doso, we introduce a margin on distances between dissimilar image pairs explicitly measured in
the binary space. In addition to pair-wise distances, we draw inspiration from Fisher’s Linear
Discriminant Analysis (Fisher LDA) to maximize the binary distances between classes andat the same time minimize the binary distance of images within the same class
We have the following contributions. 1) Adding a margin to pairwise labels pushes
dissimilar samples apart in the binary space; 2) Fisher’s criterion to maximize the betweenclass distance and to minimize the within-class distance leads to compact hash codes; 3) Weshow how to optimize this under discrete constraints and 4) We outperform state-of-the-art
methods on two datasets, being particular advantageous for a small number of hashing bits.

2

Related work

Amount of supervision. Existing hashing
V2
V1
methods can be grouped on the amount of priClass 1or domain knowledge. Hashing methods without prior knowledge are applicable to any domain and include well-known methods such as
Locality-Sensitive Hashing (LSH) [7] and its extensions [5, 15, 16, 26, 28]. If some knowledge
Class 2
about the data distribution is known in the form of an unlabeled training set, this knowledge
V3
V4
can be advantageously exploited by unsuperFigure 1:
Example of two separable
vised methods [8, 10, 11, 13, 24, 25, 33] whichclasses in a continuous space. After quanlearn hash functions by preserving the training
tization (assign to grid cells) the classes
set distance distribution. With the availability ofare no longer separable. In this paper we
additional prior knowledge about how samples
aim for separability in the binary space.
should be grouped together, supervised methods [4, 9, 21, 27, 29, 30, 36] can leverage such label information. Particularly successful
supervised hashing methods use deep learning [18, 22, 23, 34, 35] to learn the feature representation. Supervision can be in the form of pairwise label information [2, 3, 19, 20, 39] orin the form of class labels [9, 19, 23, 30]. In this paper we exploit both pairwise and classlabel knowledge, leading to highly compact and discriminative hash codes.
Quantization in hashing. Several methods optimize the continue space and apply the sign
to obtain binary codes [2, 4, 12, 20, 22, 24, 37, 38, 39]. A quantization loss is proposed indeep learning based hashing [2, 12, 20, 22, 38, 39] to force the learned continuous representations to approach the desired binary codes. However, optimizing quantization alone may
not preserve class separability in the binary space. An elegant solution is to employ sigmoid
or tanh to approximate the non-smooth sign function [3, 17], but unfortunately comes withthe drawback that such activation functions have difficulty to converge when using gradient descent methods. We circumvent these limitations by imposing the quantization loss inthe discrete space, optimizing the separability in the hashing space directly while guiding
parameter optimization in the continuous space.

3

STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINES
Pairwise Similarity Learning
Training Images

Lpair

Quantized Center Learning* Pairwise label* Margin

LquantContinuously
Distribution

Fisherbinary code

LinterConvNetWithout margin

Large margin* Class label

LintraFigure 2: Images with class labels (red and green) are input to a CNN which outputs a kdimensional continues representation U. Module 1 maximizes a margin between dissimilar
images in binary space (LPair ). Module 2 minimizes binary distances within the same class(LIntra ) and pushes different classes away (LInter ) while quantizing U as binary codes (LQuant ).
Discrete optimization. Another branch of hashing methods to solve the discrete optimization is to utilize the class information to directly learn the hashing codes. For instance,
SDH [30], as well as its extensions such as FSDH [9] and DSDH [19], propose to regress
the same-class images to the same binary codes. While this kind of methods encourages aclose binary distance between samples from the same class, they cannot guarantee the separability of samples from different classes. In contrast, we propose to explicitly maximize thebinary distances between classes and at the same time minimize the binary distances within
the same class.

3

Deep Fisher Hashing with Pairwise Margin

In Fig. 2 we illustrate our model. Two components steer the discrete optimization: 1) A
Pairwise Similarity Learning module to preserve semantic similarity between image pairs
while using a margin to push similar and non-similar images further apart (Lpair ). 2) A
Quantized Center Learning module inspired by Fisher’s linear discriminant that maximizes
the distance between different-class images (Linter ) whilst minimizing the distance between
same-class images (Lintra ) where the binarization requires minimizing quantization errors
Lquant . These two modules are optimized jointly on top of a convolutional network (CNN).
For a train set of N images X = {xi }Ni=1 , with M class labels Y = {yi }Ni=n ∈ RM×N , whereyi ∈ RM is a vector with all elements ≥ 0 that sums to 1, representing the class proportion ofsample xi . For single-label (multi-class) yi reverts to a one-hot encoding {0, 1}M . If xi has mmultiple labels, each has a value of 1/m in yi . The last layer of the CNN U = {ui }Ni=1 ∈ RK×N
is the learned representations of X. The output codes B = {bi }Ni=1 ∈ {−1, 1}K×N are thediscretized binary values corresponding to U with each image encoded by K binary bits.

3.1

Pairwise Similarity Learning

The main goal of hashing is to have small distances between similar image pairs and large
distances between dissimilar image pairs in the binary representation. For binary vectors
bi , bj ∈ {−1, 1}K , the Hamming distance DH (bi , b j ) = 21 (K − b|i · b j ) = 14 DE (bi , b j ). Since
K is a constant, it can be left out and we define the dissimilarity D(bi , b j ) = − 21 (b|i · b j ).
Note that larger dissimilarity D indicates larger Hamming distance and less similarity.

4

STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINES
15

10
Same-class, m = 3
Same-class, m = 6
Different-class, m = 3
Different-class, m = 6

LossSimilar images should share many binary
values while dissimilar images should share few
binary values. Given the dissimilarity D(·, ·) ∈(− 21 K, 12 K), a dissimilarity of 0 between binary
vectors bi and b j means that half of their bits are different. To encourage more overlapping
bits for similar images and less overlapping bits
for dissimilar images, we add a margin m to asymmetric logistic loss centered at 0:

5

0

-5

0

5

Dissimilarity

Figure 3:
Our symmetric large marLS (D) = log(1+eD+m ); LD (D) = log(1+e−D+m ). gin logistic loss of both same-class and(1) different-class cases as a function of the
The hyper-parameter m > 0 controls separation dissimilarity with different margin m.
between similar pairs S and dissimilar pairs D. Larger m encourages separation.
When m = 0, our model will turn into the classical way used in [19, 20]. Fig. 3 illustrates the loss curves of same-class pairs and differentclass pairs as a function of dissimilarity calculated by our dissimilarity measure with various
values of m. Larger margin can help to pull same-class pairs together while push differentclass pairs far away.
The Pairwise Similarity module minimizes the large margin logistic loss:
Lpair =

∑ LS (D (bi , b j )) + ∑ LD (D (bi , b j ))(i, j)∈S(i, j)∈D(2)

K

s.t. bi , b j ∈ {−1, 1} , i, j = 1, ..., N.
Since bi and b j are discretized hashing codes from the continuous output of the CNN (uiand u j ), thus it is hard to back-propagate gradients from L pair to parameters of the CNN.
To make the CNN trainable with L pair , we introduce an auxiliary variable ui = bi . Then weapply Lagrange multipliers to get the Lagrangian:NL̃pair =∑ LS (D (ui , u j )) + ∑ LD (D (ui , u j )) + ψ ∑ kui − bi k22 ,(i, j)∈S(i, j)∈D

i=1(3)

s.t. bi , b j ∈ {−1, 1}K , i, j = 1, ..., N,
where ψ is the Lagrange multiplier. The term ∑Ni=1 kui − bi k22 can be viewed as a constraint
to minimize the discrepancy between the binary space and the continuous space.

3.2

Quantized Center Learning

The Quantized Center Learning module, see Fig. 4, maximizes the inter-class distances
whilst minimizing the intra-class distances in a quantized setting. To represent class-distances
K×M , where each cenwe learn a center for each of the M classes: C = {ci }M
i=1 ∈ {−1, 1}
ter c is encoded by K bits of binary codes. Let u be the network output representation.
We then encourage the learned binary code(vertex) of each representation to be close to thecorresponding class center while the distance between different class centers is maximized,
taking quantization to binary vectors into account.

5

STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINES

Minimizing intra-class distances (Lintra ). This minimizes the sum of Euclidean distance between the binary codes bi of the N training images to their class center:
N

Lintra = ∑ kbi − Cyi k22 ,

(4)

i=1

where all class centers C are indexed by bi ’s class membership vector yi .
Maximizing inter-class distances (Linter ). We maximize the sum of pairwise Euclidean
distance between different class centers to maximize the inter-class distance of training data:
N

N

N

N

∑ ∑ kci − c j k22 = ∑ ∑ (2K − 2c|i c j ).

i=1 j=1, j6=i

(5)

i=1 j=1, j6=i

Since ci , c j ∈ {−1, 1}K and c|i c j6=i ≥ −K, maximizing Eq. (5) is equivalent to minimizingNN∑ ∑ (c|i c j − (−K))2 = kC| C − K(2I − JK )k2F ,(6)

i=1 j=1, j6=iwhere k·kF denotes the Frobenius norm, I is the identity matrix and JK is the all-ones matrix.
Simplifying the notation where A replaces K(2I − JK ) yields
Linter = kC| C − Ak2F .

(7)

Minimizing quantization cost (Lquant ). The Center Learning module exploits label
information to learn binary codes by minimizing Lintra and Linter simultaneously. We alsoneed to encourage the learned representation to be close to the quantized binary codes. Lquantminimizes the total quantization cost in moving representations ui towards the desired bi ,N

Lquant = ∑ kbi − ui k22 .

(8)

i=1

4

Optimization

Our proposed Pairwise Similarity module and Quantized Center Learning module are optimized jointly in an alternating fashion where their gradients are back-propagated to train the
upstream CNN. Combining the loss functions L̃ pair in Eq. (3), Lintra in Eq. (4), Linter in Eq. (7)and Lquant in Eq. (8), the optimization of the whole framework ishmin ϕ ∑ LS (D (ui , u j )) + ∑ LD (D (ui , u j ))bi ,ui ,C(i, j)∈S(i, j)∈Di
NN+ µ ∑ kbi − Cyi k22 + νkC| C − Ak2F + ∑ kbi − ui k22 ,
i=1

(9)

i=1

s.t. C ∈ {−1, 1}K×M , bi ∈ {−1, 1}K , i = 1, 2, . . . , N,
where ϕ, µ and ν are hyper-parameters that balance the effect of three objective functions.
Optimizing Eq. (9) involves the interaction of two types of variables: discrete variables{B = {bi }Ni=1 , C} and continuous variables U = {ui }Ni=1 . A typical solution to such multivariable optimization problem is to alternate between two steps. In particular: 1) optimize U
while fixing B and C focusing on Lpair in the Pairwise Similarity Learning module, 2) fixing
U and optimize discrete variables B and C in the Quantized Center Learning.

6

STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINES
2

2

2
Class 1
Class 2

Class 1
Class 20Class 1
Class 2

0

-2
-2

0

2

0

-2
-2

(a): Input

0

-2
-2

2

(b): Only Lintra

02(c): Lintra + LinterFigure 4: Illustration of Quantized Center learning. All points denote 2D representations
extracted by a CNN model from randomly selected two classes samples of CIFAR-10, for
100 samples per class. Binarization is illustrated by quantization sgn(·) (black lines). (a):Inefficient hashing: Binarization will assign same-class points to different bins, while assigning different-class points to the same bins. (b): Using Lintra clusters classes together andhashing is improved since binarization will assign the classes to different, neighboring bins:
class 1 to [−1, 1] and class 2 to [1, 1]. (c): Using Lintra + Linter also pushes the classes awayfrom each other, improving the hashing further since after binarization class 1 is [−1, 1] andclass 2 is [1, −1] making the difference between class samples two bit flips.

4.1

Optimizing Pairwise Similarity Learning

Given B = {bi }Ni=1 , it is straightforward to optimize U = {ui }Ni=1 by minimizing the subproblem resolved from Eq. (9) corresponding to Lpair by gradient descent:mmin ∑ kbi − ui k22 + ϕ
U∑ LS (D (ui , u j )) + ∑ LD (D (ui , u j ))i=1(i, j)∈S(10)(i, j)∈D

Since U is the output of the last layer of the upstream CNN, which is denoted as ui =W| FCNNs (xi ; θ ) + v. Here W is the transformation matrix of the last fully connected layer
and v is the bias term. θ is the parameters of CNNs before the last layer. For simplicity, we denote all parameters of CNNs models as Θ = {W, v, Θ}. The CNN parameters areU, where L is the Loss function correoptimized by gradient back-propagation: ∂∂ΘL = ∂∂ UL ∂∂ Θ
sponding to Eq. (10).

4.2

Optimizing Quantized Center Learning

With fixed CNN parameters Θ, we learn B and C by optimizing the Quantized Center Learning module, as:NN

min µ ∑ kbi − Cyi k22 + νkC| C − Ak2F + ∑ kbi − ui k22 ,
B,C

i=1

K×M

s.t. C ∈ {−1, 1}

,

i=1
N
B = {bi }i=1 ∈ {−1, 1}K×N .

(11)

We solve this problem by calling alternating optimization strategy again: optimize variables
B and C by updating one variable with the other fixed.
Initialization of bi and C. Given the representations ui , we initialize bi as bi = sgn(ui ). In
the first iteration we initialize the class centers C with the class mean of the output representations, later we update C directly.

STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINES

7

Fix bi , update C. Keeping bi fixed in Eq. (11) reduces this sub-problem toNmin µ ∑ kbi − Cyi k22 + νkC| C − Ak2F ,C

i=1

s.t. C ∈ {−1, 1}

K×M

(12)

.

Due to the discrete constraints on the class centers C, the minimization of above problem is adiscrete optimization problem which is hard to optimize directly. We introduce an auxiliary
variable V with the constrain C = V, and adding the Lagrange multiplier, the optimizationof Eq. (12) is:N

min µ ∑ kbi − Vyi k22 + νkV| V − Ak2F + ηkC − Vk2F ,
C,V

s.t.

i=1

K×M

C ∈ {−1, 1}

(13)

.

Fixing V, since the optimal solution for C for minimizing kC − Vk2F is C = sgn(V),hence kC − Vk2F in Eq. (13) can be replaced with ksgn(V) − Vk2F . Let L2 denote the loss
function after applying Lagrange multipliers, then the gradient w.r.t. V is calculated as:∂ L2= 2µ(VY − B)Y| + 4νV(V| V − A) + 2η(V − sgn(V)),
∂V

(14)

approximating the class center C with the learned V.
Fix C, update bi . With the variable C fixed in Eq. (11), we optimize the binary code bi withthe sub-problem
NN

min µ ∑ kbi − Cyi k22 + ∑ kbi − ui k22 ,
bi

i=1

i=1

(15)

K

s.t. bi ∈ {−1, 1} , i = 1, . . . , N.
We have the closed-form solution of problem (15):B = sgn(µCY + U).

(16)

See the supplementary for the detailed proof. By defining F = µCY + U as the Fisher’stransformed representations, we note that F is a translation transformation of original representations U which pushes different-class points to different vertex and pulls same-classpoints to same vertex, while F does not change the relative position between same class. The
learned center C determines where the corresponding class translates to. The 2D example inFig. 4 shows that the shape within a class does not change, yet the classes do translate.

4.3

Joint Optimization

We update the two modules jointly, see supplementary material. In each iteration, the Pairwise Similarity Learning module and Quantized Center Learning module are optimized in analternating way to learn the continuous variable U and discrete variables {B, C}, respectively.

8

5

STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINES

Experiments

Datasets. We conduct experiments on three datasets: CIFAR-10, NUS-WIDE and ImageNet100. CIFAR-10 consists of 60k color images with the resolution of 32 × 32 categorized
into 10 classes. Each image has a single label. NUS-WIDE is a multi-label dataset, whichcontains 269,648 color images collected from Flickr. There are 81 classes, where each image is annotated with one or multiple class labels. Following [17, 19, 24], we use a subset of
195,834 images associated with 21 most frequent classes (concepts) for evaluation, among
which 105,972 images has more than two labels and 89,862 images have a single label. Eachclass contains at least 5,000 samples. ImageNet100 consists of 130K single labelled images
from 100 categories, which is a subset of the large benchmark ImageNet [6].
Experimental settings. Following [19, 20], 100 random images per class in CIFAR-10
form the test query set and 500 images per class are the training set. For NUS-WIDE, we
randomly select 100 images per class as test queries and 500 images per class as the training
set. The pairwise ground truth for two images sharing at least one common label is similar
and otherwise dissimilar. Following [3], we sample 100 images per class for ImageNet100
to construct a training set, and all the images in the validation set are used as the test set.
Evaluation metrics. We evaluate retrieval performance using: mean Average Precision(MAP), precision of the top N returned examples (P@N), Precision-Recall curves (PR) and
Recall curves (R@N). All compared methods use identical training and test sets for fair comparison. For NUS-WIDE, we adopt MAP@5000 and MAP@50000 for the small-data setting
and large-data setting, respectively. We show the results of MAP@1000 for ImageNet100.
Network and parameter settings. To have a fair comparison with previous methods [19,20, 32], we fine-tune the VGG-F[19, 20] architecture for the experiments on CIFAR-10
and NUS-WIDE while the AlexNet architecture [14] is fine-tuned for the experments on
ImageNet100. Both deep network architectures are pre-trained on ImageNet. The hyperparameters {ϕ, µ, η, ν, } are tuned by cross-validation on a validation set and the margin m
is chosen from {0.5, 1, 1.5, 2}. Stochastic Gradient Descent (SGD) is used for optimization.

5.1

Exp 1: Effect of Quantized Center Learning

To investigate the effect of LIntra (minimizing intra-class distances) and LInter (maximizing
inter-class distances) in the Quantized Center Learning module, we conduct an ablation study
in the small-data setting which starts with the Pairwise Similarity Learning module Lpair
in Eq. (3) in the model and then augment the model incrementally with Lintra in Eq. (4) and
LInter in Eq. (7). In Table 1 we show the experimental results. We observe that both LIntra and
LInter contribute substantially to the performance of the whole model.

5.2

Exp 2: Functionality of different modules

We evaluate the effect of combining modules on both CIFAR-10 and ImageNet100 datasets
using precision and recall curves for top 5,000 returned images for different number of bits.
In Fig. 5 we compare on CIFAR-10 and ImageNet100. We observe that each module adds
value. The only exception is Fisher-only, which outperforms the combined Pairwise+Fisher
model for a code size of 48. Second, the combined models can get relatively well for fewer
bits, while the single models need more bits to achieve the same performance.
The results on ImageNet100 shown in Fig. 5 indicate that the Quantized Center Learning module improves the performance substantially. One potential explanation is that the9

STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINES

Baseline

Components
LIntra LInter
×
X
X

Lpair

CIFAR-10
12 Bits 24 Bits

ImageNet100
16 Bits 48 Bits

0.730
0.746
0.772

0.431
0.543
0.576

×
×
X

0.787
0.802
0.809

0.572
0.696
0.726

Table 1: Comparative results for our model with different components of the Quantized Center Learning module on CIFAR-10 and ImageNet100 . We start with the Pairwise Similarity
Learning (Lpair ) and augment incrementally with two components: LIntra in Eq. (4) and LInterin Eq. (7). For 24-bits in CIFAR-10 the performance seems already saturated; for all othersettings, each added component brings an advantage.

0.75

P
C
P+C
P+M
P+C+M

0.7

0.7

0.65

0.68

0.6

0.66
0.64
P
C
P+C
P+M
P+C+M

0.62
0.6

8

12

16

24

32

48

8

12

16

24

32

0.55
0.5
P
C
P+C
P+M
P+C+M

0.4

48

0.45

0.4

0.35

0.35
16

Number of bits

Number of bits

0.5

0.45

0.58

0.7

0.55

Recall@1000

0.72

Precision@1000

0.8

Recall@5000

Precision@5000

0.85

32

48

64

0.25
16

32

48

Number of bits

Number of bits

CIFAR-10

P
C
P+C
P+M
P+C+M

0.3

ImageNet100

Figure 5: Evaluating different modules on two datasets. Herein P refers to the Pairwise
Similarity Learning module without margin while C refers to the Quantized Center Learning
module. P + M denotes the Pairwise Similarity Learning module with tuned margin.
Pairwise Similarity Learning module (L̃pair ) is sensitive to the balance between the positive
and negative training sample pairs, which is hard to achieve in the data with large numberof classes. In contrast, the Quantized Center Learning module does not suffer from thislimitation. The sensitivity of the margin m is in the supplemental.

5.3

Exp 3: Comparison with others

In Table 2 we show results on both CIFAR-10 and NUS-WIDE datasets in the small-datasetting. In particular for a few number of bits, our model compares well to others. It is worth
noting that the performance comparison among VGG-F and AlexNet networks is considered
to be fair [31], since both architectures have the same network composition.

MethodOurs
DSDH [19]Greedy Hash [31]DPSH [20]DQN [1]DTSH [32]
NINH [18]CNNH [34]

12 bits

CIFAR-10
24 bits
32 bits

48 bits

0.803
0.740
0.774
0.713
0.554
0.710
0.552
0.439

0.825
0.786
0.795
0.727
0.558
0.750
0.566
0.511

0.844
0.820
0.822
0.757
0.580
0.774
0.581
0.522

0.831
0.801
0.810
0.744
0.564
0.765
0.558
0.509

MethodOurs
DSDH [19]Greedy Hash [31]DPSH [20]DQN [1]DTSH [32]
NINH [18]CNNH [34]

12 bits

NUS-WIDE
24 bits
32 bits

48 bits

0.795
0.776
–
0.752
0.768
0.773
0.674
0.611

0.823
0.808
–
0.790
0.776
0.808
0.697
0.618

0.842
0.829
–
0.812
0.792
0.824
0.715
0.608

0.833
0.820
–
0.794
0.783
0.812
0.713
0.625

Table 2: MAP for various methods for the small-data setting for CIFAR-10 and NUS-WIDE.
The best performance is boldfaced. For NUS-WIDE, the top 5,000 is used for the MAP.

64

10

STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINESThe state-of-the-art DSDH [19] model also uses pairwise labels and classification labels.
The major difference between is in using the classification label: DSDH [19] learns hashcodes by maximizing the classification performance while our model learns centers to model
between-class and between-sample distances. While DSDH performs excellent, our model
outperforms DSDH in all experiments.
Another interesting observation is that SDH [30], which is based on sole classification
label information, performs competitively on NUS-WIDE but not as good on CIFAR-10. In
contrast, our model and DSDH [19] that leverage two types of information, perform much
more robust. It reveals the necessity of incorporating the pairwise label information.
We also conduct experiments to compare our method to other baseline models on ImageNet100 and the results are presented in Table 3. It is observed that our model achieves thebest performance on all bits except for the 16 bits.
MethodImageNet100 (mAP@1K)
16 Bits 32 Bits 48 Bits 64 Bits

CNNH [34]
NINH [18]
DHN [39]
HashNet [3]Greedy Hash [31]
Ours

0.281
0.290
0.311
0.506
0.625
0.590

0.450
0.461
0.472
0.630
0.662
0.697

0.525
0.530
0.542
0.663
0.682
0.726

0.554
0.565
0.573
0.683
0.688
0.747

Table 3: MAP@1K results on ImageNet100 using AlexNet.

6

Conclusion

We present a supervised deep binary hashing method focusing on binary separability througha pair-wise margin and inspired by Fisher’s linear discriminant which minimizes within-classdistances while maximizing between-class distances. For medium-sized datasets with muchtraining data –where larger hash codes can be used– our method performs on par or only
slightly better than other methods. Our method is most suitable for extremely large datasetswith few training data where only tiny bit codes can be used; there our method compares
most favorably to others.

STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINES

11

References[1] Yue Cao, Mingsheng Long, Jianmin Wang, Han Zhu, and Qingfu Wen. Deep quantization network for efficient
image retrieval. In AAAI, 2016.
[2] Yue Cao, Mingsheng Long, Liu Bin, and Jianmin Wang. Deep cauchy hashing for hamming space retrieval.
In CVPR, 2018.
[3] Zhangjie Cao, Mingsheng Long, Jianmin Wang, and Philip S Yu. Hashnet: Deep learning to hash by continuation. 2017.
[4] Shih Fu Chang. Supervised hashing with kernels. In CVPR, 2012.
[5] Mayur Datar and Piotr Indyk. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the ACM Symposium on Computational Geometry, pages 253–262. ACM Press, 2004.
[6] Jia Deng, Wei Dong, R Socher, and Li Jia Li. Imagenet: A large-scale hierarchical image database. In CVPR,
2009.
[7] Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In
Proceedings of International Conference on Very Large Databases, pages 518–529, 2000.
[8] Yunchao Gong and Svetlana Lazebnik. Iterative quantization: A procrustean approach to learning binary
codes. In CVPR, 2011.
[9] J. Gui, T. Liu, Z. Sun, D. Tao, and T. Tan. Fast supervised discrete hashing. IEEE Transactions on PatternAnalysis Machine Intelligence, PP(99):1–1, 2018.
[10] Kaiming He, Fang Wen, and Jian Sun. K-means hashing: An affinity-preserving quantization method forlearning binary compact codes. In CVPR, 2013.
[11] Qing Yuan Jiang and Wu Jun Li. Scalable graph hashing with feature transformation. In International Conference on Artificial Intelligence, 2015.
[12] Qing-Yuan Jiang and Wu-Jun Li. Deep cross-modal hashing. In CVPR, 2017.
[13] Weihao Kong and Wu Jun Li. Isotropic hashing. In NIPS, 2012.
[14] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional
neural networks. In NIPS. 2012.
[15] Brian Kulis and Kristen Grauman. Kernelized locality-sensitive hashing for scalable image search. In ICCV,2009.
[16] Brian Kulis, Prateek Jain, and Kristen Grauman. Fast similarity search for learned metrics. IEEE Transactions
on Pattern Analysis Machine Intelligence, 31(12):2143, 2009.
[17] H. Lai, Y. Pan, Ye Liu, and S. Yan. Simultaneous feature learning and hash coding with deep neural networks.
In CVPR, 2015.
[18] Hanjiang Lai, Yan Pan, Ye Liu, and Shuicheng Yan. Simultaneous feature learning and hash coding with deepneural networks. In CVPR, 2015.
[19] Qi Li, Zhenan Sun, Ran He, and Tieniu Tan. Deep supervised discrete hashing. In NIPS. 2017.
[20] Wu-Jun Li, Sheng Wang, and Wang-Cheng Kang. Feature learning based deep supervised hashing withpairwise labels. In IJCAI, 2016.
[21] Guosheng Lin, Chunhua Shen, Qinfeng Shi, Anton Van Den Hengel, and David Suter. Fast supervised hashingwith decision trees for high-dimensional data. In CVPR, 2014.
[22] Haomiao Liu, Ruiping Wang, Shiguang Shan, and Xilin Chen. Deep supervised hashing for fast image
retrieval. CVPR, 2016.

12

STUDENT, PROF, COLLABORATOR: BMVC AUTHOR GUIDELINES[23] Haomiao Liu, Ruiping Wang, Shiguang Shan, and Xilin Chen. Learning multifunctional binary codes for bothcategory and attribute oriented retrieval tasks. In CVPR, 2017.
[24] Wei Liu, Jun Wang, and Shih fu Chang. Hashing with graphs. In ICML, 2011.
[25] Wei Liu, Sanjiv Kumar, Sanjiv Kumar, and Shih Fu Chang. Discrete graph hashing. In NIPS, 2014.
[26] Yadong Mu and Shuicheng Yan. Non-metric locality-sensitive hashing. In AAAI, 2010.
[27] Mohammad Norouzi and David J. Fleet. Minimal loss hashing for compact binary codes. In ICML, 2011.
[28] M Raginsky. Locality-sensitive binary codes from shift-invariant kernels. 2009.
[29] Ramin Raziperchikolaei and Miguel Á Carreira-Perpiñán. Optimizing affinity-based binary hashing using
auxiliary coordinates. In NIPS, 2016.
[30] Fumin Shen, Chunhua Shen, Wei Liu, and Heng Tao Shen. Supervised discrete hashing. In CVPR, 2015.
[31] Shupeng Su, Chao Zhang, Kai Han, and Yonghong Tian. Greedy hash: Towards fast optimization for accuratehash coding in cnn. In Advances in Neural Information Processing Systems, pages 798–807, 2018.
[32] Xiaofang Wang, Yi Shi, and Kris M Kitani. Deep supervised hashing with triplet labels. Asian Conference on
Computer Vision, 2016.
[33] Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral hashing. In NIPS, 2008.
[34] Rongkai Xia, Yan Pan, Hanjiang Lai, Cong Liu, and Shuicheng Yan. Supervised hashing for image retrieval
via image representation learning. In AAAI, 2014.
[35] Ting Yao, Fuchen Long, Tao Mei, and Yong Rui. Deep semantic-preserving and ranking-based hashing forimage retrieval. In IJCAI, 2016.
[36] Peichao Zhang, Wei Zhang, Wu Jun Li, and Minyi Guo. Supervised hashing with latent factor models. In
SIGIR, 2014.
[37] Ziming Zhang, Yuting Chen, and Venkatesh Saligrama. Efficient training of very deep neural networks forsupervised hashing. In CVPR, 2016.
[38] Fang Zhao, Yongzhen Huang, Liang Wang, and Tieniu Tan. Deep semantic ranking based hashing for multilabel image retrieval. In CVPR, 2015.
[39] Han Zhu, Mingsheng Long, Jianmin Wang, and Yue Cao. Deep hashing network for efficient similarity
retrieval. In AAAI, 2016.