IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 19, NO. 11, NOVEMBER 2017

2545

Learning Efficient Binary Codes From
High-Level Feature Representationsfor Multilabel Image Retrieval
Lei Ma, Hongliang Li, Senior Member, IEEE, Fanman Meng, Member, IEEE, Qingbo Wu, Member, IEEE,
and King Ngi Ngan, Fellow, IEEE

Abstract—Due to the efficiency and effectiveness of hashingtechnologies, they have become increasingly popular in large-scale
image semantic retrieval. However, existing hash methods supposethat the data distributions satisfy the manifold assumption thatsemantic similar samples tend to lie on a low-dimensional manifold,which will be weakened due to the large intraclass variation.
Moreover, these methods learn hash functions by relaxing thediscrete constraints on binary codes to real value, which will
introduce large quantization loss. To tackle the above problems,
this paper proposes a novel unsupervised hashing algorithm tolearn efficient binary codes from high-level feature representations.
More specifically, we explore nonnegative matrix factorization
for learning high-level visual features. Ultimately, binary codes
are generated by performing binary quantization in the highlevel feature representations space, which will map images withsimilar (visually or semantically) high-level feature representations
to similar binary codes. To solve the corresponding optimization
problem involving nonnegative and discrete variables, we develop
an efficient optimization algorithm to reduce quantization loss withguaranteed convergence in theory. Extensive experiments showthat our proposed method outperforms the state-of-the-art hashingmethods on several multilabel real-world image datasets.
Index Terms—Efficient binary codes, image semantic retrieval,nonnegative matrix factorization.

I. INTRODUCTION
HE exponential growth of big image data on the Web
has posed a great challenge for the storage, analysis, andmanagement of them. How to design an efficient and effective
algorithm for large scale image semantic retrieval task has become a hot topic. The traditional real-valued descriptors likeT

Manuscript received November 8, 2016; revised April 13, 2017; accepted
April 28, 2017. Date of publication May 10, 2017; date of current version
October 13, 2017. This work was supported in part by the National Natural
Science Foundation of China under Grant 61525102, Grant 61502084, and Grant
61601102. The associate editor coordinating the review of this manuscript andapproving it for publication was Prof. Enrico Magli. (Corresponding author:
Hongliang Li.)
L. Ma, H. Li, F. Meng, and Q. Wu are with the School of Electronic Engineering, the Intelligent Visual Information Processing and Communication Laboratory (IVIPC), University of Electronic Science and Technology of China,
Chengdu 611731, China (e-mail: leima_uestc@163.com; hlli@uestc.edu.cn;
fmmeng@uestc.edu.cn; wqb.uestc@gmail.com).
K. N. Ngan is with the Department of Electronic Engineering, The Chinese
University of Hong Kong, Hong Kong, China, and also with the School ofElectronic Engineering, University of Electronic Science and Technology ofChina, Chengdu 611731, China (e-mail: knngan@ee.cuhk.edu.hk).
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TMM.2017.2703089

LBP [1]–[4], GIST [5], BOW [6], color histogram [7], color
co-occurrence descriptor [8], etc. require huge computing andmemory cost. In contrast, the binary descriptors have a great
advantage in improving retrieving speed and reducing memory
cost, which makes them easy for large-scale image retrieval[9]–[11].
For solving a large-scale image search problem based onreal-valued descriptors, the classical tree-based methods suchas kd-tree [12] and R-tree [13] methods are proposed. However,
due to the existence of curse of dimensionality, the efficiencyof the similarity search decreases with the increased dimensionof data. In order to reduce the effects of the curse of dimensionality, some early data independent hash methods including
Locality Sensitive Hashing (LSH) [14] and its variants [15]use random linear projections to map real-valued descriptors
in a high-dimensional space into a low-dimensional Hamming
space. The main limitation of these methods is that the retrieval
performance is unsatisfactory with a small number of bits.
In order to learn more efficient and compact hash codes,
some data dependent hashing methods [9]–[11], [16], [17] aredesigned to learn hash functions via machine learning. The mainidea of data dependent methods is to learn a low-dimensional
representation of data and then quantize [9] or threshold [11],[16] them into binary codes. Existing data dependent hashingmethods can be roughly divided into three categories [18]: supervised hashing methods, semi-supervised hashing methods, andunsupervised hashing methods. The supervised hashing methods [19]–[30] make use of completely labeled data for training.
However, with the rapidly growing data, it is expensive to labela large number of training samples. In order to reduce human labor intensity, semi-supervised hashing methods [16], [31] makeuse of both labeled and unlabeled data for training. Although
the number of labeled data is reduced, semi-supervised hashing methods require experienced people to manually label sometraining samples.
Unsupervised hashing methods utilize the intrinsic data properties of the examples without using any label information tolearn binary codes. To preserve the global variance structureof the input data, Principle Component Hashing (PCAH) [16],Iterative Quantization (ITQ) [9] and Isotropic Hashing (IsoH)[32] try to identify a set of hyperplanes with anisotropic [9],[16] or isotropic [32] PCA projection based on a linear manifold assumption i.e, the underling manifold is a linear subspace.

1520-9210 © 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications standards/publications/rights/index.html for more information.

2546

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 19, NO. 11, NOVEMBER 2017

Fig. 1. Framework of the proposed method. The overall algorithm can be divided into two stages: offline training phrase and online query phrase. In the offline
training phrase, three terms including Term 1, Term 2, and Term 3 are involved in generating efficient binary codes, where Term 1 refers to the highlevel feature
representations learning term, Term 2, refers to the efficient binary codes learning term, and Term 3 refers to the out-of-sample extension term. In the online queryphrase, the hash code of the query image can be obtained from the output of the process shown below the purple dotted line. Please see text for more details.

However, the linear manifold assumption is strict to a real-world
application. Instead of assuming global linearity, Spectral Hashing (SH) [17], Anchor Graph Hashing (AGH) [10], Locally Linear Hashing (LLH) [33], and Induced Manifold Hashing (IMH)[11] make a weaker local neighborhood preserving assumption
i.e., non-linear manifold assumption that nearby points in highdimensional input space are close in the low-dimensional manifold subspace. The core idea of these methods is to learn hashfunctions based on manifold learning methods including: linear
manifold learning methods (e.g. Principle Component Analysis(PCA)) or non-linear manifold learning methods (e.g. Spectral
Clustering (SC) [34], Laplacian Eigenmaps (LE) [35], Isomap[36], Locally Linear Embedding (LLE) [37], Elastic Embedding(EE) [38], and t-Distributed Stochastic Neighbor Embedding (tSNE) [39]). However, these methods widely adopt the manifold
assumption that semantic similar samples tend to lie on a lowdimensional manifold. This assumption will be weakened when
the intra-class similarities are low.
While the impact of intra-class variations can be alleviatedby leveraging deep learning, vector quantization and nonnegative matrix factorization technologies, promising results areachieved in image retrieval [40]–[46]. Autoencoder (AE) [40],[47] and Deep Hashing (DH) [41] resort to the powerful fitting
ability of deep neural networks to learn non-linear hash functions. Outputs of the last layer are signed to obtain the resulting
binary codes, which will lead to the accumulated quantization
error [31]. In addition, these methods usually have great computational burden and are prone to overfitting. To preserve highfitting ability and circumvent the risks of overfitting, Product
Quantization (PQ) [42], Cartesian k-means (CKM) [43] andComposite Quantization (CQ) [44] turn to explore Vector Quantization (VQ) [48] technologies for learning binary codes. The
key idea of VQ based methods is that the dimensions of thedata can be separated into several disjoint subsets under theassumption of independence across dimensions, and each subset is quantized into a number of discrete state respectively.
However, the assumption of independence across dimensions
may destroy the latent semantic structure of data. To preserve

the latent semantic structure of input data, Nonnegative Matrix Factorization Hashing (NMFH) [45] and Latent Structure
Preserving Hashing (LSPH) [46] employ Nonnegative Matrix
Factorization (NMF) [49] technology to decompose a input data
matrix into a product of two nonnegative factors, which can beunderstood as the parts and the parts-based representations respectively since they only allow addition (not substraction) andits combination [50]. However, the NMF based hashing methods
choose to solve a relaxed constraint problem and the quality of
approximate solution is unsatisfactory due to the accumulated
quantization error. For a more comprehensive introduction to
the existing hashing methods, please refer to the review onhashing [51], [52].
The above unsupervised hashing methods either ignore theexisting huge inter-class variations in real-world images or release discrete constraints on binary codes in the optimization,
which may limit the effectiveness of learning efficient binary
codes for complex scene/object images retrieval task. Therefore, it is a valuable research issue to simultaneously learn
efficient binary codes and better data representation to solve
image retrieval problem on real-world image databases.
In this paper, we propose a novel unsupervised hashingmethod by learning efficient binary codes from high-level feature representations which can describe the widely varying data
distributions well. Due to the straightforward interpretabilityof NMF, it has attracted great attention recently and has been
widely applied in several applications including face recognition[45], document clustering [53], recommender systems [54], etc.
NMF can decompose the original real-value inputs into a basis
matrix and a coefficient matrix which is the high-level representations of the original real-value inputs [55]. In addition, theflexibility of matrix factorization enables dealing with widely
varying data distributions. Thus hash codes learned from highlevel feature representations via NMF are expected to be more
effective. As shown in Fig. 1, the (visually or semantically) similar images are expected to be represented as similar high-levelfeature representations via NMF and further mapped to similar binary codes. However, directly applying NMF to generateMA et al.: LEARNING EFFICIENT BINARY CODES FOR MULTILABEL IMAGE RETRIEVAL

hash codes will result in two problems: 1) the solution of NMF
problem is in general not unique [56], i.e., the basis matrix andthe coefficient matrix are not unique, and as a result the resulting hashing codes are not unique; 2) there is no straightforward
extension scheme for computing high-level feature representations of inputs in the test set, i.e., the problem of out-of-sample
extension. From the point of view of information theory, allinformation bits in the resulting hash codes should be equallyprobable and independent of each other. In other words, efficienthash codes should simultaneously satisfy bits balance property,
i.e., each bit has a 50% chance of being one or zero, and bits independence property, i.e., different bits are independent of eachother [17]. Interestingly, the bits balance and bits independence
constraints can be approximated by constraining the high-levelfeature representations with equal isotropic covariance, i.e., adiagonal matrix with all diagonal elements being the same.
With this isotropic constraint, we can obtain unique solutionof NMF problem like [57]. For the problem out-of-sample extension, we can introduce an explicit mapping between the original real-value inputs and the high-level feature representations.
Therefore, we model our problem within a NMF framework,
which includes the following three terms: a high-level feature
representations learning term, an efficient binary code learning term, and an out-of-sample extension term. The first termaims to learn the high-level feature representations of input data.
The second term aims to learn efficient binary codes. The lastterm aims to learn an explicit mapping from the input space
to the high-level embedding space so that the high-level representations of the items in the test set can be computed directly.
The introduction of the independence and balance constraints
renders the optimization problem more complex and difficult.
The problem can be simplified by relaxing the independence
and balance constraints to one isotropic constraint on the highlevel feature representations. However, the relaxed optimization
problem is still a challenge optimization problem which contains
nonnegative variables, continuous variables, a discrete variable
and orthogonal constraints. Therefore, we develop an efficient
coordinate descent algorithm to solve this challenge optimization problem. The convergent property of our proposed algorithm can be well guaranteed by a theoretical analysis. We evaluate our proposed algorithm on several multi-label real-worldimage datasets. The experimental results verify the effectivenessof our method.
The rest of this paper is organized as follows. In Section II, we
present the details of the proposed method. Section III reports
the experimental results by comparing with existing state-ofthe-art methods on several real-world datasets. The conclusion
is given in Section IV.

II. LEARNING EFFICIENT BINARY CODES FROM HIGH-LEVELFEATURE REPRESENTATIONSAssume that we have a database X = {x1 , . . . , xn } ∈ Rd×n ,where xi is a d-dimensional image descriptor of the i-th sample
and n is the number of images. The purpose of image hashingis to learn hash functions H : Rd → {−1, 1}k to map a training
example xi to a k-dimensional binary hash code bi = H(xi ) in

2547

Fig. 2. Schematic illustration of the motivation. NMF can reconstruct the
input nonegative real-value features with a basis matrix and a coefficient matrix,
where each row in the coefficient matrix corresponds to a high-level feature
representation of the original real-value inputs. The (visually or semantically)
similar images are expected to have similar high-level feature representations,
i.e., the distance between them in the high-level embedding space is small,while the distances are large for dissimilar images. The goal is to learn the hashcodes which can preserve the neighborhood relationship from the high-level
embedding space into the Hamming space.

the Hamming space, while maintaining some notion of similarity evaluated in the real-value feature space.
In this section, we solve the hashing learning problem bylearning efficient binary codes from high-level feature representations, of which the flowchart is shown in Fig. 2. As is
illustrated in Fig. 2, the proposed method includes two stages:
the offline training phase and the online query phrase. In the offline training phrase, a d-dimensional real-value visual feature
is extracted from each image firstly. These features constitute an
input data matrix X ∈ Rd×n . We expect to learn a basis matrix
U ∈ Rd×k and the high-level feature representations V ∈ Rk ×n
from X ∈ Rd×n . V is zero-centered by subtracting the mean ineach feature dimension, and further rotated by an orthogonal rotation matrix R to narrow down the gap between zero-centered
V and binary codes B ∈ {−1, 1}k ×n . The isotropic constraint
on V is introduced to approximate the bits balance and bits
independence constraints. As a result, we can obtain efficientbinary codes from the zero-centered and rotated V. Meanwhile,
we learn a projection matrix P ∈ Rd×k from X to V for facilitating encoding new image features into high-level feature
representations. Finally, the hash function learning can be formulated as the following optimization objective function:
L(U, V, P, B, R) = L1 (U, V) + αL2 (B, R, V) + βL3 (P, V).

(1)
Where α, β are two parameters to balance the effects of corresponding terms. The objective function includes three terms: thefirst term is the high-level feature representations learning term,
which means that the (visually or semantically) similar examples
can have similar high-level feature representations; the second
term is the efficient binary codes learning term, which meansthat similar high-level feature representations should be mapped
to similar binary codes and the learned hash codes should satisfy the properties of bits balance and independence; the third
term is an out-of-sample extension term, which implies that thehigh-level feature representations of new input data can be computed by a straightforward projection from the input space tothe high-level embedding space. In the online query phrase, a
new query image is characterized as xt . Next, we project xt into
the high-level embedding space as vt = PT xt , followed by atruncation operator as v̂t = max(0, vt ). We further subtract themean of V from v̂t and rotate the result with R. Finally, we2548

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 19, NO. 11, NOVEMBER 2017

encode the real-value output into a binary code bt by a sgn(·)
function, where sgn(x) = 1 if x > 0 and −1 otherwise.
In this paper, we use a bold uppercase fonts to denote matrix and a bold lowercase fonts to denote a vector. In addition,
given a matrix X = {xij }, we utilize xj to denote j-th column
respectively. The inverse of X is represented as X−1 , and its
transpose is denoted as XT . The Frobenius norm of X is denoted as X2F . Ik is the identity matrix of size k. 1n is the
all-ones vector of size n.
A. Learning High-Level Feature Representations
We utilize the nonnegative factorization method [49], [50],[55] to learn high-level feature representations. Specifically,
NMF can decompose the original real-value inputs X into
two matrices U and V which have only nonnegative elements.
The nature of NMF is to minimize the reconstruction error
as follows:
min L1 (U, V) = ||X − UV||2Fs.t.

U ≥ 0, V ≥ 0

(2)
k ×n

and V ∈ R
where the two nonnegative factors U ∈ Rdenote the basis matrix and the the coefficient matrix respectively. H = In − n1 1n 1Tn is the centering projection
matrix which is also a symmetric and idempotent matrix, i.e.,
H = HT = HHT . Each column of U corresponds to a basis
and each column of V is a high-level feature representationfor each training example [55]. The number of hash bits corresponds to the number of bases, i.e., each hash bit corresponds
to a latent basis in U.
d×k

where R ∈ Rk ×k is an orthogonal matrix that brings the zerocentered high-level feature representations VH closely to thenearest vertex of the binary hypercube {−1, 1}k . The reasonof using the orthogonality constraint is that the orthogonal R
can balance the variance of different dimensions of the zerocentered V which will benefit the reduction of the quantization
error [9]. Here, V is zero-centered to eliminate the difference
between the center of V and the center of B. According to(3), each data point in V is mapped to the nearest vertex of
the binary hypercube {−1, 1}k . In other words, the smaller thequantization loss in (3), the better the locality structure of thedata points in V will preserved in the corresponding Hamming
space B.
C. Out-of-Sample Extension
There is no straightforward extension scheme for computing
high-level feature representations of inputs in the test set via
NMF. Therefore, we have to learn an explicit mapping between
the inputs and the high-level feature representations in the training phrase. Now, assume that we are given the training examples
X and their corresponding high-level feature representations V.
Then the mapping from X to V can be considered as a regression problem. We leverage a simple linear regression to model
the relationship between X and V as f (xi ) = PT xi , whereP ∈ Rd×k is the parameter of the linear regression model f .
In order to optimize P, we choose to minimize the following
function:min L3 (V, P) =The solution of NMF problem is in general not unique [56],i.e., the basis matrix and the coefficient matrix are not unique.
Therefore, the resulting hashing codes learned from the highlevel feature representations are not unique. There may exist
redundant and correlated information in the bits of the obtained
various hashing codes. However, from the information-theoretic
point of view, the information provided by each bit of the resulting hashing codes is expected to be maximal and different bits
are independent of each other, i.e., the resulting hashing codes
are efficient binary codes. To obtain efficient binary codes, we
require that the hash bits satisfy two constraints, i.e. bits balance B1n = 0 and bits independence n1 BBT = Ik , the former
requires that each bit has a 50% chance of being one or zeroand the latter requires that different bits are independent ofeach other [17]. In addition, we expect that similar (visually or
semantically) high-level feature representations should bemapped to similar binary codes [9]. We model the binary codes
learning problem by minimizing the following binary quantization error:B ∈ {−1, 1}k ×n(4)

The function include two terms: the first term is a linear regression term to reduce the regression error, and the second term
is a regularization term to avoid overfitting. The parameter γ1
is used to balance the importance of the two terms. By a simple algebraic calculation, the matrix form of the out-of-sample
extension term is given as
min L3 (V, P) = V − PT X2F + γ1 P2F .

The overall objective function consists of three terms including learning high-level feature representations term, learning efficient binary codes term and the out-of-sample extension term,
i.e.,
min

U,V ,P,B,R||X − UV||2F + αB − RVH2F+ βV − PT X2F + γP2F
RT R = Ik , B1n = 0,

1
BBT = Ikn

U ≥ 0, V ≥ 0, B ∈ {−1, 1}k ×n1
BBT = Ik
n
(3)

(5)

D. Overall Objective Functions.t.

min L2 (B, R, V) = ||B − RVH||2F
RT R = Ik , B1n = 0,

vi − PT xi 2F + γ1 P2F .

i=1

B. Learning Efficient Binary Codes

s.t.

n


(6)

where α, β, γ = βγ1 are the tradeoff parameters which are utilized to balance the importance of the three terms.

MA et al.: LEARNING EFFICIENT BINARY CODES FOR MULTILABEL IMAGE RETRIEVAL

E. Optimization
The optimization problem in (6) is non-smooth and nonconvex. The reasons are that: 1) the optimization problem involves one discrete variable and two discrete constraints; 2) the
overall objective function and the real-value orthogonal constraint are non-convex. In addition, the bits balance and bits
independence constraints make the problem NP hard [17]. Intuitively, we can relax the bits balance and bits independence
constraints and use an alternative optimization algorithm to obtain an approximate solution. One way is to ignore the bits
balance and bits independence constraints in (6). The hashcodes will be computed with B = sgn(RVH). However, theresulting hash codes may be unbalanced or dependent of eachother. The other way is to approximate B with the magnitude
of RVH. Then, the bits balance and the bits independence
constraints will be RVH1n = 0 and n1 RVHHT VT RT = Ik .
We can see that: 1) the bits balance constraint can be satisfied naturally according to the definition of the centering projection matrix H; 2) the bits independence constraint can befurther simplified as n1 VHVT = Ik , where the invertible property of orthogonal matrix R: R−1 = RT , and a property ofidempotent matrix H: HHT = H are used. Therefore, the bits
balance constraint B1n = 0 and bits independence constraint
1
T
n BB = Ik in (6) can be approximated by one orthogonal constraint n1 VHVT = Ik . The overall objective function can be
rewritten asmin

U,V ,P,B,R||X − UV||2F + αB − RVH2F + β V − PT X2F

+ γ P2F
s.t.

RT R = Ik ,1
VHVT = Ikn

U ≥ 0, V ≥ 0, B ∈ {−1, 1}k ×n .

(7)

It is worth noting that the covariance of matrix V is n1 VHVT
which is required to be isotropic [32], i.e., isotropic constraint.
According to [32], it is unreasonable to use the same length ofbinary codes for different embedding dimensions with unequalvariances since larger-variance dimensions will carry more information. Hence, the high-level feature representations withisotropic variances will be better than those with anisotropic
variances for hashing. Moreover, the orthogonal constraint on
the covariance of matrix V can enhance the discriminative
property of V.
The introduction of the isotropic (orthogonal) constraint
1
T
VHV= Ik further increases the difficulty of the optimizantion problem. There are two typical approximate solutions forsolving the objective function in (7) with the isotropic constraint
1
T
n VHV = Ik by introducing different orthogonality penalty
terms. One uses the Lagrangian multiplier method as presented
in [58] by introducing a trace-penalty term. The other employs
an orthogonal subspace method as done in [57] by introducinga 2 -norm penalty term. The former requires huge computation
cost in updating the Lagrange multiplier which is a symmetricmatrix with many parameters. The latter decreases the computational complexity by introducing a single parameter. Here, we2549

introduce a 2 -norm penalty term in the objective function to replace the orthogonal constraint as done in [57]. The optimization
problem in (7) can be rewritten asmin

U,V ,P,B,R

O(U, V, P, B, R)= ||X − UV ||2F + αB − RVH2F + β V − PT X2F

2

η 1
T

VHV
+ γ P2F + 
−
I
k

2 n
F

s.t.

U ≥ 0, V ≥ 0, RT R = Ik , B ∈ {−1, 1}k ×n(8)where η is the penalty parameter which penalizes for the deviations from the identity matrix.
We utilize the Lagrangian multiplier method to transform theabove nonnegative constrained optimization problem in (8) into
an unconstrained one with respect to U and V as follows:
L(Θ) = ||X − UV||2F + αB − RVH2F + βV − PT X2F

2

1
η
2
T
T

+ γPF +  VHV − Ik 
 + Tr(ΦU )2 nF+ Tr(ΨVT )= X2F − 2Tr(XT UV) + Tr(UVVT UT ) + αB2F− 2αTr(BT RVH) + βTr(VT V) −2βTr(VT PT X)+ βTr(PT XXT P) + γTr(PT P)ηη
Tr(VHVT )+ 2 Tr(VHVT VHVT ) + α −2nnη+ Ik 2F + Tr(ΦUT ) + Tr(ΨVT )(9)2where Φ and Ψ are the dual variables, Θ involves all variables U,
V, P, B, R, Φ and Ψ in (9). The derivation of (8) uses the orthogonal property of matrix R: RT R = RRT = Ik , some properties of idempotent matrix H: H = HT = HHT , and the matrixtrace properties: Tr(A) = Tr(AT ), Tr(AC) = Tr(CA), andA2F = Tr(AT A).
In order to solve the problem in (9), an efficient coordinate descent algorithm is developed to alteratively optimize unknown
variables Θ until convergence. The detail optimization procedure works as follows.
1) Fix V, P, B, R and set the derivative w.r.t. U to zero. We
have∇U L = 2UVVT − 2XVT + Φ = 0.

(10)

By using the Karush-Kuhn-Tucker (KKT) complementarity condition Φ  U = 0, where  means the Hadamard
product (entrywise product), we can multiply U on theentries of (10) and obtain(UVVT − XVT )  U = 0.

(11)

We get the following updating rule:
U←U

XVT
.
U(VVT )

(12)

2550

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 19, NO. 11, NOVEMBER 2017

2) Fix U, P, B, R and set the derivative w.r.t. V to zero. We
have

η
∇V L = 2UT UV − 2UT X + 2 α −VHn− 2αRT BH + 2βV − 2βPT X+

2η
VHVT VH + Ψ = 0.
n2

(13)

By using the Karush-Kuhn-Tucker (KKT) complementarity condition Ψ  V = 0, we can multiply V on theentries of (12) and obtainη
VH − αRT BH + βV
UT UV − UT X + α −nη− βPT X + 2 VHVT VH  V = 0 (14)nwhere RT BH and PT X are mixed sign, which not only
includes negative sign but also positive sign. We can use
the following operator to decompose the mixed sign matrix M into a positive part and a negative part, i.e. M =[M]+ − [M]− , where [M]+ = (M + |M|)/2, [M]− =(|M| − M)/2. Then, we can get the following updating rule as in (15), as shown at the bottom of the page,
where Q1 = (V1n )(V1n )T V, Q2 = (VVT )(V1n )1Tn ,and Q3 = (V1n )((V1n )T V1n )1Tn .
3) Fix U, V, B, R and set the derivative w.r.t. P to zero. We
have∇P L = 2(βXXT + γId )P − 2βXVT = 0.

(16)

Then we get the following updating rule:P = β(βXXT + γId )−1 XVT .

(17)4) Fix U, V, P, R and update B by
B = sgn(RVH).

(18)5) Fix U, V, P, B and update R by solving an orthogonal
procrustes problem presented as in [9]. We get the following updating rule:R = (MN)T(19)

where M, N are the left and right singular values of thematrix VHBT with its SVD as MΣN.
After the convergence of the algorithm, we can obtain the
average of the low-dimensional parts-based representations of
training examples v̄ = n1 V1n . For a test sample xt , we canobtain the latent embedding representation v̂t as follows:v̂t = max (0, (P∗ )T xt )(20)

where P∗ is the optimal solution of P. Here, the negative entriesof (P∗ )T xt are considered as embedding noise. The binary codeV← VAlgorithm 1: Learning Efficient Binary Codes From HighLevel Feature Representations
Input: The training data X ∈ Rd×n , the parametersα, β, γ, η, μ.
Output: The optimal P∗ , R∗ , and v̄.
Initialization:
Initialize U, V, P, B, R;
1: repeat
2: Update U according to (12);3: Update V according to (15);4: Update P according to (17);5: Update B according to (18);
6: Update R according to (19);7: until convergence or reaching the maximum number of
iterations.
8: return P∗ , R∗ , and v̄.
of xt can be obtained by
bt = sgn(R∗ (v̂t − v̄))(21)

where R∗ is the optimal solution of R. Then the hash function
can be defined as
H(xi ) = sgn(R∗ (max(0, (P∗ )T xi ) − v̄)).

(22)

The whole optimization procedure is summarized in
Algorithm 1.
The objective function in (8) is non-increasing under the updating rules in (12), (15), (17), (18) and (19). In addtion, theobjective is obviously bounded. Therefore, the successive iteration of Algorithm 1 will converge (see Appendix A).
The solution of NMF is nonunique in general. Assume that
we have two matrices Y ∈ Rk ×k and Z ∈ Rk ×k which meet thefollowing conditions:
YZ = Ik , UY ≥ 0, ZV ≥ 0.

(23)

We can find that (UY, ZV) is also the solution with the same
residue X − UV2F . With the isotropic (orthogonal) constraint, the uniqueness of NMF can be given as in the following
proposition.
Proposition 1: With the isotropic constraint n1 VHVT = Ik
in the NMF, there exist no matrices Y and Z that meet both(23) and the isotropic constraint n1 ZVHVT ZT = Ik , except
when Y and Z are permutation matrices, i.e., Y = Q, Z =QT where QT Q = I, qi,j = 0 or 1.
Proof: Please refer to the proof of Proposition 1 in [58].
F. Complexity Analysis
The updating of U requires O((d + k)kn). The main computational cost in updating V lies in computing RT BH,
which takes O(kn2 ) to compute it directly. To reduce theUT X + αn (V1n )1Tn + α[RT BH]+ + β[PT X]+ + nη3 Q1 + nη V + nη3 Q2(UT U)V + (α + β)V + α[RT BH]− + β[PT X]− + nη2 (V1n )1Tn + nη2 (VVT )V + nη4 Q3(15)

MA et al.: LEARNING EFFICIENT BINARY CODES FOR MULTILABEL IMAGE RETRIEVAL

computational complexity, we turn to computing RT BH as
RT B − n1 (RT (B1n ))1Tn . The updating of V requires O((d +k)kn). The updating of P requires O(nd(d + k)). The updating of B takes O((k 2 + k)n), which takes the similarcalculating trick as in updating V to reduce the computational complexity. The computational cost of updating of R
can be reduced to O((k 2 + 2k)n) by replacing VHBT with
VBT − n1 (V1n )(B1n )T . We assume that the number of iterations needed for convergence is T . The overall computational complexity of the proposed method is O(T (d + k)kn).
For space complexity, the proposed approach requires O(d × r)
for storing U, O(d × n) for X, O(r × n) for V, O(k × n) for
B, and O(k × k) for R. We can easily store all the variables
in memory for large-scale image retrieval problem. We can seethat the computational and storage cost is linear to the numberof training samples n.
G. Relationship Between the Proposed Method and Principal
Component Analysis (PCA)
The Principal Component Analysis [59], [60] technology
projects data points X ∈ Rd×n to the k-dimensional subspace U ∈ Rd×k , i.e., the principal directions, and obtains kdimensional data representations V ∈ Rk ×n in the subspace.
The objective function of the PCA method can be defined asmin X − UV2F .
U,Vs.t. UT U = Ik .

(24)

The objective function in (24) can be transformed into the following objective function:
max Tr (UT XXT U).
Us.t. UT U = Ik .

(25)

The above function is the well-known PCA optimization objective function, which can be solved by eigenvalue decompositionof the correlation matrix XXT and output the eigenvectors forthe k largest eigenvalues.
The goals of PCA and NMF are both to find new data representations by minimizing the reconstruction error. PCA chooses
to maximize variance among all directions of the projected data.
However, unlike PCA, an isotropic covariance constraint on thehigh-level feature representations is induced by the efficientcoding hypothesis in the paper. In addition, PCA requires orthogonality of basis U, while the proposed method has no such
constraint.
Compared with the proposed method, there are three main
shortcomings in the PCA based hashing method [16]. First, since
PCA assumes the subspace U to be orthogonal, the number ofdesired PCA embeddings or hash bits cannot be greater thanthe dimension d of the original input data, i.e., k ≤ d. Second,the Hamming Accumulated Errors [31] will be accumulatedwith the real-value principal components converted into binary
codes as the code length increasing. Third, the variances ofdifferent PCA projected dimensions are different and, as a result,
it is unreasonable to encode the different projected dimensions
with the same number of bits. On the contrary, the proposed
method can generate longer codes whose code lengths can belarger than the dimension d of the input data, i.e., k > d. In
addition, the Hamming Accumulated Errors can be reduced by

2551

the introduction of the binary quantization error term in the
proposed method.
III. EXPERIMENTS
In this section, we evaluate the proposed method for semantic retrieval task on three multi-label benchmark real-world
datasets including MIRFlickr,1 ADE20K2 and NUS-WIDE,3and two single-label benchmark real-world datasets including
CIFAR-104 and Tiny-1M [16], [22]. We compare our methodwith seven state-of-the-art unsupervised hashing methods forimage retrieval task, including Iterative Quantization (ITQ) [9],Isotropic Hashing (IsoH) [32], Inductive Hashing on Manifolds(IMH) [11], Anchor Graph Hashing (AGH) [10], Spectral Hashing (SH) [17], Principal Component Analysis Hashing (PCAH)[16], and Locality Sensitive Hashing (LSH) [14].
1) Iterative Quantization (ITQ) [9] learns hash codes by minimizing the quantization error of mapping PCA-projected
data to vertices of the binary hypercube.
2) Isotropic Hashing (IsoH) [32] learns projection functions
with isotropic variances for different dimensions of PCAprojected data, where lift and projection (LP) learningalgorithm is adopted to obtain the resulting binary codes.
3) Inductive Hashing on Manifolds (IMH) [11] employs theintrinsic manifolds structure to learn compact binary embeddings, where the t-SNE [61] is utilized to capture theintrinsic manifolds structure.
4) Anchor Graph Hashing (AGH) [10] extends the traditional
spectral hashing by utilizing anchor graphs to approximately compute pairwise similarity matrix.
5) Spectral Hashing (SH) [17] learns hash codes throughsolving the eigenvectors of the graph Laplacian.
6) Principal Component Analysis Hashing (PCAH) [16]learns hash codes by maximizing the variance of eachbit.
7) Locality Sensitive Hashing (LSH) [14] utilizes random
linear projections to map real-value input to binary codes.
In addition, we also compare the proposed method with Euclidean distance based retrieval method (L2-scan), which adopts
the original real-value features and Euclidean distance basedsimilarity metric for image retrieval.
A. Experimental Settings
1) Dataset Settings: The MIRFlickr dataset consists of
25,000 images from the Flickr website with 24 concepts including stuffs like sky, flower, beach, and discrete objects likepeople, dog and bird. The dataset is randomly split into a collection of 24,000 training images and 1,000 test images. The
ADE20K dataset consists of 20,210 images for training, and
2,000 images for validation. There are a total of 150 semantic
categories in the dataset, which include stuffs like sea, sky, tree,lake, and discrete objects like people, dog, car. We mix the training set with the validation set. The data are randomly split into a
1 [Online]. Available: http://press.liacs.nl/mirflickr/
2 [Online]. Available: http://groups.csail.mit.edu/vision/datasets/ADE20K/
3 [Online]. Available: http://lms.comp.nus.edu.sg/research/NUS-WIDE.htm
4 [Online]. Available: https://www.cs.toronto.edu/ kriz/cifar.html

2552

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 19, NO. 11, NOVEMBER 2017

collection of 21,210 training images and 1,000 test images. The
NUS-WIDE dataset contains 269,648 images and the associated
81 concepts collected from the Flickr website. We choose the
21 most frequent concepts including a total of 195,834 images
as the groundtruth labels, where each of these concepts contains
at least 5,000 images. We randomly sample 100 images fromeach concept as the test queries and the remaining images fortraining. The CIFAR-10 dataset consists of 60,000 natural images grouped into 10 classes with 6,000 images for each class.
Following [9], we randomly sample 1000 images to serve as test
queries and and the remaining images for training. The Tiny-1M
dataset is a subset of the 80M tiny image benchmark5 [62], which
does not include any semantic label. We sample a subset of one
million images to construct the training set and a separate subset
of 2K images as query test [16], [22]. The returned top 5% nearest neighbors in the training set closest to each query in termsof the Euclidean distance are considered groundtruth neighbors.
So each query has 50K groundtruth neighbors.
For MIRFlickr, ADE20K and CIFAR-10 datasets, we extract 320-dimensional GIST features [5] from each image as
the visual feature for image representation. For the NUS-WIDE
dataset, we use the 128-dimensional wavelet texture features
which have been extracted for each image. The global 384dimensional GIST descriptors of the images in the Tiny-1M
dataset are publicly available. For all the compared methods,
the features are rescaled to zero mean and unit variance. For
the proposed method, we rescale the range of the features to[0, 1] along each feature dimension. In the test phase, the retrieval images are regarded as the true neighbours if they shareat least two semantic labels with the query for the three multilabel datasets (MIRFlickr, ADE20K, and NUS-WIDE) and thesame label with the query for single-label dataset CIFAR-10.
The image retrieval performance is evaluated using the Mean
Average Precision (MAP) metric [10], [11]. In addition, we employ Average Cumulative Gain (ACG) [27], Normalized Discounted Cumulative Gain (NDCG) [27] metrics to evaluate theHamming ranking quality. As the computation of MAP is slow
on NUS-WIDE and Tiny-1M datasets, the top-50,000 returned
neighbours are used to evaluate the MAP performance of all
methods.
MAP is defined as the mean of the average precision (AP)of all queries, where average precision (AP) of top R retrieved
instances is defined as
1 
P (r)δ(r).
N r =1
R

AP =

(26)

N denotes the number of relevant instances in retrieved set.
P (r) denotes the precision of top r retrieved instances. δ(i) is aindicator function, i.e., if i-th retrieved instance is a relevant trueneighbor of the given query, δ(i) = 1, and otherwise δ(i) = 0.
For a single query q, ACG is defined as the averageof the similarity levels of the returned data points within

5 [Online]. Available: http://groups.csail.mit.edu/vision/TinyImages/

top-p positions:1ri
ACG@p =
p i=1
p

(27)

where ri is the similarity level of the returned data point at thei-th position in the ranking list of the query q.
NDCG is a popular ranking measure in the information retrieval community, which is defined as1  2r i − 1
Z i=1 log(i + 1)p

N DCG@p =(28)

where Z is normalization factor to ensure the NDCG score forthe correct ranking is one. The final ranking performance isgiven by averaging the ACG and NDCG scores of all queries.
The first criterion MAP reflects the change of the percentage of retrieved relevant instances with respect to the numberof retrieved instances. The second criterion ACG shows theprecision weighted by the similarity level of each retrieved instance. The third criterion NDCG evaluates the ranking qualityof retrieved instances by giving bigger penalty for the incorrect
higher ranked items.
2) Implementation Details: We initialize U and V as two
random matrices whose elements are uniformly distributedin the interval (0,1). P can be initialized by (16). R is initialized as a random orthogonal matrix, and B is initializedby sgn(RVH). For the proposed method, we empirically set
α = 1, β = 10−2 , γ = 10, η = 107 . The maximum number of
iterations in the following experiments is set to 100. For AGH,
and IMH, 1,000 anchor points are generated by K-means clustering. All experiments are conducted using Matlab 2015a on
a server with Intel(R) Xeon(R) CPU E5-2690@2.90 GHz and
128 G of RAM, running the 64-bit Linux system. We run theexperiments on three multi-label datasets and CIFAR-10 dataset
30 times, while 10 times experiments are conducted for Tiny-1M
by considering the tradeoff between the efficiency and the computation cost. The mean performances over all repetitions arereported. For each run, we randomly split the datasets into training and test sets with the datasets setting reported above.
B. Experimental Results and Analyses
In this section, we compare our proposed method with stateof-the-art hashing methods for multi-label image semantic retrieval task.
1) Results on MIRFlickr: The results on MIRFlickr are
shown in Table I. The proposed method performs better than thecompared hashing methods for all cases. The improvement of
the performances can be attributed to the efficient hash codes
learned from the high-level feature representations extraction
via NMF. In addition, the proposed method can surpass L2scan, e.g., from 32 bits to 256 bits for MAP and ACG@ 100
metrics and from 64 bits to 256 bits for NDCG@ 100 metric.
The reason is that the proposed method can reduce redundant
information in the original real-value inputs. On the other hand,
it also verifies the effectiveness of the proposed method. With
the increment of the codes length, the performance of the pro-MA et al.: LEARNING EFFICIENT BINARY CODES FOR MULTILABEL IMAGE RETRIEVAL

2553

TABLE IRETRIEVAL PERFORMANCE OF DIFFERENT METHODS ON THREE MULTILABEL DATASETS FROM 16 BITS TO 256 BITS

posed method climbs up due to the increasing representative
ability of the resulting binary codes. It is worth noting that the
representative ability of the learned high-level feature representations will also increase with the increment of the codes length.
However, the performances of PCAH and SH degrade as thenumber of bits increases. The main reason is that the eigendecomposition solution in PCAH will make the bit’s discriminative
power lower with longer codes, and the assumption that data aresampled from a multidimensional uniform distribution in SH
is too restrictive in practice. AGH ultizes a low-rank method
to approximate the adjacency matrix and performs better than
PCAH and SH. The performances of LSH, ITQ, IsoH, and IMH
increase as the increasement of hash bits since the larger hashbits improve the representative ability of binary codes. However, they are inferior to the proposed method: LSH is a data
independent method which does not use any information fromthe data, ITQ and IsoH resort to a heuristic two-stage approach
including a dimension reduction via PCA stage and a rotation
stage to obtain the binary codes which will make the resulting
binary codes suboptimal, and IMH relies initial anchors selection which will affect the performance of the resulting binary
codes.
2) Results on ADE20K: The results on ADE20K areshown in Table I. The retrieval performances of all the methods
on ADE20K are better than MIRFlickr. The main reason isthat the number of images is close while the number of images
with the same category or co-occurrence categories on MIRFlickr is larger than ADE20K as shown in Fig. 3. The proposed
method performs better than the baseline hashing methods formost cases. However, for the NDCG@100 metric at 32 bits,
the proposed method performs slightly inferior to ITQ. This
result can be attributed to the slightly weak representative ability of the learned 32-dimensional high-level feature representations (NMF tends to produce sparse factor matrices due tononnegativity constraints, and as a result, PCA is more optimal

Fig. 3. Sematic categories histograms on (a) MIRFlickr and (c) ADE20K.
The categories co-occurrence matrix on (b) MIRFlickr and (d) ADE20K.

than NMF in terms of the reconstructed error). ITQ and IsoH
perform better than IMH, PCAH, AGH, SH and LSH in thisdataset, but is still inferior to the proposed method. The experimental performances in this dataset are similar to those on
MIRFlickr dataset.
3) Resultson
NUS − WIDE: The
resultson
NUS − WIDE are shown in Table I. Since the feature
representation of NUS-WIDE is somewhat weak, the performances of all the methods on NUS-WIDE are inferior to2554

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 19, NO. 11, NOVEMBER 2017

TABLE IIAVERAGE OFFLINE TRAINING AND THE ONLINE HASHING TIME OF ALL EVALUATED METHODS ON THE THREE MULTILABEL DATASETS
Datasets

Methods Times(s)

LSH

PCAH

SH

AGH

ITQ

IsoH

IMH

Proposed method

MIRFlickr

Training time
Test time
Training time
Test time
Training time
Test time

0.002
0.004
0.004
0.004
0.001
0.003

0.138
0.004
0.140
0.004
0.069
0.003

0.760
0.137
0.823
0.137
0.849
0.067

1.235
0.031
0.668
0.024
5.774
0.048

7.261
0.006
7.077
0.007
20.532
0.005

4.429
0.006
4.451
0.005
1.451
0.004

10.8670.018
13.5850.014
14.4850.022

129.334
0.007
120.4090.007
402.644
0.005

ADE20K
NUS-WIDE

Fig. 4. MAP versus parameters α, β, γ, and η. (a) β = 10−2 , γ = 10, η = 10 7 . (b) α = 1, γ = 10, η = 107 . (c) α = 1, β = 10 −2 , η = 10 7 . (d) α = 1, β =10 −2 , γ = 10.

MIRFlickr and ADE20K datasets. Similarity, the proposed
method outperforms state-of-the-art hashing methods for allcases. The code length of ITQ, IsoH, PCAH, and SH on
NUS-WIDE can’t be greater than the dimension of the original
input data, since they require PCA preprocessing of the input
data at first. LSH performs better than ITQ and IsoH. Thiscan be because the data distribution tends to the uniform
distribution with large intra-class variation. Therefore, themanifold assumption will be weakened. The manifold basedhashing methods such as IMH, AGH, PCAH and SH perform
worse than LSH.
C. Comparison of Training and Hashing Time
In order to demonstrate the efficiency of the proposed method,
we list the average offline training time and the online hashing(encoding) time of different methods on the three datasets inTable II, where all the comparison hash methods are executed
30 times with randomly generated training and test sets. We
evaluate the average offline training time and the online time of
all these methods with the code length of 256 bits on MIRFlickr
and ADE20K and 128 bits on NUS-WIDE. Note that L2-scan
is not included in Table II, due to the fact that L2-scan utilizes
the original real-value features for image retrieval and doses
not generate hash codes. Although, it needs more training time
to make the proposed algorithm converge than the comparedmethods, the online hashing time of the proposed method is lessthan SH, AGH and IMH, which verifies the efficiency of the
proposed method.
D. Parameter Sensitivity
There are four parameters in the proposed method, including α, β, γ and η in the objective function. We tune theparameters on MIRFlickr, ADE20K and NUS-WIDE by varying the value from 10−8 to 108 . For the parameter sensitivity analysis, we fix the code length to 64 bits. In previous
experiments, we utilize the fixed hyper-parameter configurations (α = 1, β = 10−2 , γ = 10, η = 107 ). Here, we use thetraditional approach of varying one parameter at a time while
holding the others fixed to investigate the effects of different
parameter settings on the algorithm performance. The experiments are conducted 30 times and the average experimental performances of MAP, ACG@ 100 and ADCG@ 100 are reported
in Figs. 4–6 respectively. From Figs. 4–6, we can observe thatthe parameters α, β and γ are more sensitive compared to η.
The reasons are that 1) α controls the quantization error loss
in the offline training phrase which is essential for generating
the resulting hash codes; 2) β and γ control the out-of-sample
extension term which is a critical term for generating the hashcodes of the test samples. More specifically, α controls thequantization error. It can be observed from Figs. 4(a), 5(a), and6(a) that as α increases the experimental performances first increase and then decrease. The experimental results demonstratethat small α [e.g., α ∈ [10−8 , 10−2 ] in Fig. 6(a)] will introduce
large quantization error, while large α [e.g., α ∈ [105 , 108 ] inFig. 6(a)] will affect the balance of all components. β controls the correspondence between the original real-value features and the high-level feature representations, where smallvalues of β (e.g., β ∈ [103 , 108 ] in Figs. 4–6) can weaken thecorrespondence relations between the original real-value features and the high-level feature representations, while large β(e.g., β ∈ [10−8 , 10−2 ] in Figs. 4–6) will affect the balance of thecomponents in the model. In addition, γ controls the complexityof the proposed method, where large γ (e.g., β ∈ [102 , 108 ] inFigs. 4–6) will lead to under-fitting and small γ can lead to overfitting. η can enforce the discrimination of the the high-levelMA et al.: LEARNING EFFICIENT BINARY CODES FOR MULTILABEL IMAGE RETRIEVAL

2555

Fig. 5. ACG@100 versus parameters α, β, γ, and η. (a) β = 10−2 , γ = 10, η = 10 7 . (b) α = 1, γ = 10, η = 107 . (c) α = 1, β = 10 −2 , η = 10 7 .
(d) α = 1, β = 10 −2 , γ = 10.

Fig. 6. NDCG@100 versus parameters α, β, γ, and η. (a) β = 10−2 , γ = 10, η = 10 7 . (b) α = 1, γ = 10, η = 10 7 . (c) α = 1, β = 10 −2 , η = 10 7 .
(d) α = 1, β = 10 −2 , γ = 10.

Fig. 7.

Convergence curves on MIRFlickr, ADE20K, and NUS-WIDE datasets at 256 bits.

feature representations and generate efficient binary codes. η canbe chosen from large values [e.g., γ ∈ [106 , 107 ] in Fig. 6(d)].
E. Convergence Study
The convergence of the iterative update rules in Algorithm 1
can be seen in Appendix A. Here, we also experimentally verify
our analysis. Fig. 7 shows the objective value of the proposed
method along the number of iterations. For each figure, the yaxis is the objective function value and x-axis is the number of
iterations. It can be seen that the objective function decreases at
each iteration and converges within 100 iterations. The objectivefunction value is not decreasing smoothly after the third andthe fifth iterations. The reason is that the objective function in(8) is non-smooth.

(V) includes five terms, where {Oi }5i=1 correspond successively to all the terms in (8). Since the high-level feature
representations learning term O1 (U, V), out-of-sample
extension term O3 (V, P) + γ1 O4 (P), and binary codes
generation term O3 (B, R, V) are indispensable part of the
proposed model, we include O1 (U, V), O3 (V, P), O4 (P) andO2 (B, R, V) in the baselines defined as follows:
1) B1 : Learning binary codes from O1 (U, V) +αO2 (B, R, V) + βO3 (V, P) + γO4 (P), i.e.,
min O(Θ1 ) = ||X − UV||2F + αB − RVH2F
Θ1+ βV − PT X2F + γP2F
s.t. RT R = Ik , B ∈ {−1, 1}k ×n
U ≥ 0, V ≥ 0

F. The Contributions of Different Terms
The overall objective function O(U, V, P, B, R) =O1 (U, V) + αO2 (B, R, V) + βO3 (V, P) + γO4 (P) + ηO5(29)

where Θ1 = {U, V, P, B, R}.
2) T1 : Decomposing B1 into two separate steps including
O1 (U, V) + βO3 (V, P) + γO4 (P) and O2 (B, R, V),2556

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 19, NO. 11, NOVEMBER 2017

TABLE IIIRETRIEVAL PERFORMANCE OF THE PROPOSED METHOD AND OTHER BASELINES ON THREE MULTILABELDATASETS WITH THE MAP, ACG@ 100, AND NDCG@ 100 EVALUATION CRITERIONS AT 256 BITS
DatasetMIRFlickr

ADE20K

NUS-WIDE

Metric

B1

T1

T2

Proposed method

MAP
ACG@100
NDCG@100
MAP
ACG@100
NDCG@100
MAP
ACG@100
NDCG@100

0.3320 ± 0.0054
1.2555 ± 0.0330
0.2081 ± 0.0042
0.4963 ± 0.0072
2.5232 ± 0.0451
0.1372 ± 0.0046
0.2042 ± 0.0051
1.0071 ± 0.0159
0.1783 ± 0.0029

0.3248 ± 0.0055
1.2095 ± 0.0286
0.2011 ± 0.0040
0.4875 ± 0.0064
2.5105 ± 0.0520
0.1365 ± 0.0036
0.1929 ± 0.0053
0.9569 ± 0.0177
0.1678 ± 0.0030

0.3284 ± 0.0069
1.2338 ± 0.0335
0.2079 ± 0.0053
0.4913 ± 0.0061
2.5325 ± 0.0410
0.1392 ± 0.0040
0.1980 ± 0.0058
0.9856 ± 0.0152
0.1741 ± 0.0026

0.3362 ± 0.0061
1.2635 ± 0.0241
0.2089 ± 0.0052
0.4973 ± 0.0073
2.5740 ± 0.0438
0.1417 ± 0.0040
0.2088 ± 0.0047
1.0216 ± 0.0140
0.1798 ± 0.0032

i.e.,

(30)

that the isotropic variance constraint can improve the binary
codes learning performance. In addition, the performance ofthe proposed method is better than the other baselines which
demonstrates that incorporating them into a joint optimization
framework can further improve the experimental performancefor multi-label image retrieval.

(31)

G. Single Label Image Semantic Retrieval andNearest-Neighbor Retrieval

min O(Θ2 ) = ||X − UV||2F + βV − PT X2F
Θ2+ γP2F
s.t. U ≥ 0, V ≥ 0
min O(Θ3 ) = B − RVH2F
Θ3s.t.

RT R = Ik , B ∈ {−1, 1}k ×nwhere Θ2 = {U, V, P} and Θ3 = {B, R}.
3) T2 : Decomposing the whole learning procedure into two
steps including O1 (U, V) + βO3 (V, P) + γO4 (P) +ηO5 (V) and O2 (B, R, V), i.e.,
min O(Θ4 ) = ||X − UV||2F + βV − PT X2F
Θ4+ γP2F +


2

η
 1 VHVT − Ik 


2 n
F

s.t. U ≥ 0, V ≥ 0(32)

min O(Θ5 ) = B − RVH2F
Θ5

s.t. RT R = Ik , B ∈ {−1, 1}k ×n(33)where Θ4 = {U, V, P} and Θ5 = {B, R}.
B1 is the baseline without the isotropic constraint and T1 is thecorresponding two-step extension of B1 . The baseline B1 can besolved by setting η in Algorithm 1 to zero. We can solve T1 with
two steps. The first step alternatively optimizes U, V, and P
from the subproblem in (30) with the same updating rule asin (12), (15) and (17) by setting α and η to zero. The second
step alternatively optimizes B and R from the subproblem in(31) with the same updating rule as in (18) and (19). A similar
optimization procedure can be applied to the T2 . We compare theproposed method and other three baselines on the three multilabel datasets with the three evaluation criterions at 256 bits.
The experimental results are shown in Table III. From this table
we can see that the joint optimization methods including B1 andthe proposed method performs better than two-step methods T1
and T2 . It demonstrates that the joint optimization methods canlearn optimal binary codes. The performances of the proposed
method and T2 are consistently better than B1 and T1 . It verifies

Besides the experiments on three multi-label datasets, we
also conduct comparison experiments on CIFAR-10 for singlelabel image retrieval and Tiny-1M for nearest neighbor retrieval.
We employ the widely used MAP metric in single label image
retrieval task and nearest neighbor retrieval to evaluate the performance of various methods. The experiments are conducted
30 times and 10 times for CIFAR-10 and Tiny-1M respectively.
The average experimental performance of MAP is reported.
The performances of different methods for single-label image
semantic retrieval task are evaluated on CIFAR-10. The experimental results are shown in Table IV.
As we can see in Table IV, the proposed method achieves
the best performance at 512 bits and surpasses the comparedmethods. The performances of different methods for nearestneighbor retrieval task are evaluated on Tiny-1M. The experimental results are shown in Table V.
From Table V, we can observe that ITQ performs best at
32 bits and 64 bits, IsoH performs best at 128 bits and 256
bits, and LSH performs best at 320 bits and 512 bits. The
proposed method achieves competitive performance with LSHfrom 320 bits to 512 bits. Let us make additional observations
about the experiments on three multi-label datasets (MIRFlickr,
ADE20K, and NUS-WIDE), CIFAR-10 and Tiny-1M. The proposed method performs better on the multi-label datasets withdispersed and complex classes in each image, while ITQ using
PCA to extract low-dimensional feature representations performs well from 32 bits to 256 bits in the following two tasks:
1) the image semantic retrieval on single-label datasets with one
compact class in each image, 2) nearest-neighbor retrieval. The
reason can be that PCA is more optimal than NMF in termsof the reconstructed error (since NMF tends to produce sparsefactor matrices due to nonnegativity constraints) which will
benefit the single-label image retrieval and nearest-neighbor re-MA et al.: LEARNING EFFICIENT BINARY CODES FOR MULTILABEL IMAGE RETRIEVAL

2557

TABLE IV
MAP PERFORMANCE OF DIFFERENT METHODS ON CIFAR10 FROM 32 BITS TO 512 BITS

32 bits
64 bits
128 bits
256 bits
320 bits
512 bits

Ours

ITQ

IsoH

IMH

AGH

LSH

PCAH

SH

0.1622 ± 0.0044
0.1719 ± 0.0042
0.1801 ± 0.0039
0.1866 ± 0.0032
0.1876 ± 0.0031
0.1899 ± 0.0030

0.1737 ± 0.0019
0.1792 ± 0.0020
0.1840 ± 0.0023
0.1883 ± 0.0023
0.1896 ± 0.0024–

0.1664 ± 0.0023
0.1720 ± 0.0021
0.1770 ± 0.0021
0.1817 ± 0.0023
0.1832 ± 0.0023–

0.1538 ± 0.0068
0.1575 ± 0.0052
0.1554 ± 0.0063
0.1556 ± 0.0061
0.1542 ± 0.0065
0.1538 ± 0.0068

0.1497 ± 0.0017
0.1425 ± 0.0014
0.1372 ± 0.0012
0.1318 ± 0.0009
0.1300 ± 0.0009
0.1270 ± 0.0008

0.1441 ± 0.0046
0.1564 ± 0.0031
0.1666 ± 0.0036
0.1766 ± 0.0025
0.1793 ± 0.0023
0.1827 ± 0.0025

0.1317 ± 0.0010
0.1245 ± 0.0008
0.1182 ± 0.0005
0.1132 ± 0.0004
0.1118 ± 0.0004–

L2-scan

0.1342 ± 0.0010 0.1724 ± 0.0022
0.1329 ± 0.0009
0.1304 ± 0.0008
0.1273 ± 0.0008
0.1258 ± 0.0008–

TABLE V
MAP PERFORMANCE OF DIFFERENT METHODS ON TINY1M FROM 32 BITS TO 512 BITS

32 bits
64 bits
128 bits
256 bits
320 bits
512 bits

Ours

ITQ

IsoH

IMH

AGH

LSH

PCAH

SH

0.1802 ± 0.0059
0.2223 ± 0.0040
0.3055 ± 0.0061
0.3676 ± 0.0008
0.3940 ± 0.0014
0.4069 ± 0.0037

0.3184 ± 0.0044
0.3477 ± 0.0044
0.3635 ± 0.0051
0.3721 ± 0.0053
0.3779 ± 0.0052–

0.3008 ± 0.0058
0.3383 ± 0.0044
0.3689 ± 0.0044
0.3932 ± 0.0035
0.1151 ± 0.0004–

0.1049 ± 0.0019
0.1049 ± 0.0042
0.1054 ± 0.0026
0.1059 ± 0.0015
0.1052 ± 0.0012
0.1058 ± 0.0038

0.2877 ± 0.0039
0.2951 ± 0.0026
0.2857 ± 0.0021
0.2616 ± 0.0014
0.2432 ± 0.0009
0.2290 ± 0.0008

0.2029 ± 0.0085
0.2633 ± 0.0042
0.3244 ± 0.0101
0.3738 ± 0.0075
0.3942 ± 0.0098
0.4073 ± 0.0038

0.1367 ± 0.0005
0.1199 ± 0.0005
0.1030 ± 0.0003
0.0872 ± 0.0001
0.0791 ± 0.0001–

0.1606 ± 0.0017
0.1799 ± 0.0020
0.2124 ± 0.0013
0.2280 ± 0.0016
0.2242 ± 0.0016–

trieval, whereas NMF can provide a better characterization of
the intra-latent information (data-driven latent attributes, e.g.,clusterings) which will benefit uncovering the common latent
structure shared by multi-label images.
H. Discussion
This paper has considered the problem of learning efficienthash codes from high-level feature representations. The basic
idea behind the proposed method is that the extracted high-levelfeature representations should capture the intra-latent structureof data and the resulting hash codes learned from the high-levelfeature representations are expected to be efficient (bits balanceand bits independence constraints are satisfied). In designing
the proposed method, we explore a joint NMF optimization
framework to learn the high-level feature representations andefficient hash codes.
Compared to existing methods, the proposed method has
several advantages. The data independent hashing methods(e.g. LSH) require relatively long hash codes to produce good
performance, which will lead to longer query time as well as alarger storage cost than would otherwise be necessary. Different
from the data independent hashing methods, the proposed
method can generate compact binary codes which will lead tofaster query time with fewer memory cost. The manifold-basedhashing methods (e.g. IMH, AGH, PCAH, SH, IsoH and ITQ)
widely adopt non-linear or linear manifold assumption thatsemantic similar samples tend to lie on a low-dimensional
manifold. For muti-label with dispersed and complex classes
in each image, the manifold assumption will be weakened
due to the large intra-class variation. Different from nonlinear
manifold-based hashing methods, we do not need to make any
assumption about the data distributions except the nonnegativity of the input data and data-driven latent attributes (e.g.,inherent clustering property) of the data can be mined via NMF
which make our method more suitable to perform complex(multi-label) image retrieval. In addition, It is worth noting that
ITQ and IsoH utilize two separate steps to learn hash functions,which will lead to suboptimal binary codes. On the contrary,
the proposed method adopts a joint optimization framework forlearning hashing functions, which can generate optimal binary
codes. Therefore, the proposed method outperforms previous
work for multi-label image semantic retrieval task.
In consideration of computational and memory cost, the geometrical structure of the data space is not exploited in the
proposed method. As a result, it would be helpful to explicitly model such information by constructing a nearest neighbor
graph to further improve the performance. In addition, considering reducing model complexity, we utilize single-layer NMF(factorizing the inputs into two factors) in the paper. However,the deep multi-layer NMF can generate more informational
high-level representations as in [55]. It is promising to incorporate the deep multi-layer NMF structure into the model to learn
higher-level representations. In order to reduce human labor, we
introduce a novel method for completely unsupervised hashinglearning. However, the performance is not satisfactory for some
practical applications. Therefore, label information can be utilized to further improve the image retrieval performance.
IV. CONCLUSION
In this paper, we propose an effective unsupervised hashing to learn efficient binary codes using NMF. The inspirations
for this work lie in that NMF can produce high-level feature
representations, and the higher-level features are expected togenerate effective and efficient hash codes. However, directly
applying NMF to generate hash codes will result in two problems: 1) the solution of NMF problem is in general not unique;2) there is no straightforward extension scheme for computing
high-level feature representations of inputs in the test set. Therefore, we introduce three terms into our model, i.e., a high-levelfeature representations learning term to learn high-level feature

2558

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 19, NO. 11, NOVEMBER 2017

representations, an efficient binary code learning term to learn
efficient binary codes while ensuring that similar (visually or semantically) high-level feature representations should be mapped
to similar binary codes, and an out-of-sample extension term tofacilitate the encoding of new samples. To solve the non-convex
and non-smooth problem, an efficient optimization algorithm
is developed which can decrease quantization loss and guarantee the convergence of the proposed algorithm in theory. Extensive experimental results on several benchmark real-worldimage datasets demonstrate the effectiveness of the proposed
method.
APPENDIX A
PROOFS OF CONVERGENCE
In order to prove the convergence of our proposed algorithm,
we only need to prove that the objective value decreases in thealternate iteration procedure, i.e.,

Lemma 2: Function
 (t) (t) 

 (t)
t
t 2
+ v − vij·G v, vij = Fij vij + Fij vij v − vij((UT U)V + (α + β)V + α[RT BH]−ηη
+ β[PT X]− + 2 VVT V + 2 (V1n )1Tn
n
n

η
t
+ 4 (V1n ) (V1n )T V1n 1Tn )ij /vij.
(39)nis an auxiliary function for Fij (v).
Proof: Since G(v, v) = Fij (v) is obvious, we need only ver(t)ify that G(v, vij ) ≥ Fij (v). To verify this, we compare the
Taylor series expansion of Fij (v) (t) (t) (t)(t) 2
Fij (v) = Fij vij + Fij vij v − vij + v − vij ·
(UT U)ii + αhj j + β

η
T
2
(40)
+ 2 ((VHV )ii hj j + (VH)ii − nhj j )nO(Ut−1, Vt−1, Pt−1, Bt−1, Rt−1 ) ≥O(Ut , Vt−1 , Pt−1 , Bt−1 , Rt−1 ) ≥O(Ut , Vt , Pt−1 , Bt−1 , Rt−1 ) ≥ · · · O(Ut, Vt, Pt, Bt, Rt ).
(34)
The main difficulty in proving the convergence lies in the proofsof the first two inequalities. We choose to prove the second inequality, since the proofs of the first two inequalities are similar.
The proofs of the other inequalities are omitted because they are
well-known. We use an auxiliary function similar to that in [49],[57]. The definition of auxiliary function is given as follows:
Definition 1: [49] G(h, ĥ) is an auxiliary function for F (h)if the conditions
G(h, ĥ) ≥ F (h), G(h, h) = F (h)(35)

are satisfied.
Lemma 1 ([49]): If G is an auxiliary function, then F isnonincreasing under the updateh(t+1) = arg max G(h, h(t) ).
h

(t+1)

(36)

(t+1)

) ≤ G(h, h(t) ) ≤ G(h(t) , h(t) ) =Proof: F (h(t)

F (h ).
Considering any element vij in V, Fij is used to denotethe part of O, which is only relevant to vij . By defining thet) for Fij , the updating
appropriate auxiliary function G(v, vij
rule in (15) easily follows (36). The first-order and second-orderderivatives of Fij with respect to vij are shown as follows:



∂O
Fij =
= − 2UT X + 2UT UV + 2αVH
∂V ij
− 2αRT BH + 2βV − 2βPT X

2η
2η
(37)
+ 2 VHVT VH − VHnnij
Fij = 2(UT U)ii + 2αhj j + 2β2η 
+ 2 (VHVT )ii hj j + (VH)2ii − nhj j .
nwith (39). We can have the following inequalities:(UT UV)ij =

k


(t)

(t)

(UT U)il vlj ≥ (UT U)ii vij(t)αvij ≥ αhj j vij(42)α([RT BH]− )ij ≥ 0, β([PT X]− )ij ≥ 0(43)(VV T V)ij



1 
+ 2 (V1n ) (V1n )T V1n 1Tn+ (V1n )1Tn
ij
n
=

n


(VV T )il vlj +l=1

≥ (VV T )ii +

1
n2

n



vil 1n 1Tn V T V1n 1Tn

l=1

1 
1n 1Tn V T V1n 1Tn
n2(t)= (VV T )ii vij +



+
1
vij
jj

ij
lj +

n


vil

l=1

1 (t) T T(t)v 1 V V1n + vij
n2 ij n(t)

≥ (VHV T )ii hj j + (VH)2ii − nhj j vij(44)

where the second inequality in (44) holds because of the condition n1 (VHVT )ii = 1, and

2
n
n
1 
1
2
2
(VH)2ii = V − V1n 1Tn= vii−
vil + 2
vil
n
n
n
ii
l=1

2
≤ vii
+

1
n2

n


2

≤ (VV T )ii +

vil

l=1

2

l=1

1 T T
1 V V1n .
n2 n

(45)
(t)

Thus the inequality G(v, vij ) ≥ Fij (v) holds.

(38)

(41)

l=1



(t)
Replacing G(v, vij ) in (36) by (39) and setting the derivation(t)of G(v, vij ) with respect to v to zero result in the followingMA et al.: LEARNING EFFICIENT BINARY CODES FOR MULTILABEL IMAGE RETRIEVAL

update rule:
(t+1)
vij


 (t)
(t)
(t)
= vij − vij Fij vij / (UT U)V + (α + β)V+ α[RT BH]− + β[PT X]−ηη+ 2 (VVT )V + 2 (V1n )1Tn
n
n

η
T
T
+ 4 (V1n)((V1n) V1n)1n . (46)nij
By simple algebra manipulations, we can have the same updat(t)ing rule as in (15). Since G(v, vij ) is an auxiliary function,
Fij (v) is nonincreasing under the updating rule in (15). The
other inequalities in (34) hold under the corresponding updating rules. The convergence of the proposed method is proved.
REFERENCES[1] T. Song and H. Li, “Wavelbp based hierarchical features for image classification,” Pattern Recog. Lett., vol. 34, no. 12, pp. 1323–1328, 2013.
[2] T. Song, H. Li, B. Zeng, and M. Gabbouj, “Texture classification using joint
statistical representation in space-frequency domain with local quantizedpatterns,” in Proc. IEEE Int. Symp. Circuits Syst., Jun. 2014, pp. 886–889.
[3] T. Song and H. Li, “Local polar DCT features for image description,”
IEEE Signal Process. Lett., vol. 20, no. 1, pp. 59–62, Jan. 2013.
[4] T. Song et al., “Noise-robust texture description using local contrast patterns via global measures,” IEEE Signal Process. Lett., vol. 21, no. 1,
pp. 93–96, Jan. 2014.
[5] A. Oliva and A. Torralba, “Modeling the shape of the scene: A holistic
representation of the spatial envelope,” Int. J. Comput. Vis., vol. 42, no. 3,
pp. 145–175, 2001.
[6] F. Li and P. Perona, “A Bayesian hierarchical model for learning naturalscene categories,” in Proc. IEEE Comput. Soc. Conf. Comput. Vis. Pattern
Recog., Jun. 2005, vol. 2, pp. 524–531.
[7] F. Meng, H. Li, G. Liu, and K. N. Ngan, “Object co-segmentation basedon shortest path algorithm and saliency model,” IEEE Trans. Multimedia,
vol. 14, no. 5, pp. 1429–1441, Oct. 2012.
[8] H. Li, F. Meng, and K. N. Ngan, “Co-salient object detection from multiple
images,” IEEE Trans. Multimedia, vol. 15, no. 8, pp. 1896–1909, Dec.
2013.
[9] Y. Gong, S. Lazebnik, A. Gordo, and F. Perronnin, “Iterative quantization: A procrustean approach to learning binary codes for large-scale
image retrieval,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 35, no. 12,
pp. 2916–2929, Dec. 2013.
[10] W. Liu, J. Wang, S. Kumar, and S. Chang, “Hashing with graphs,” in Proc.
Int. Conf. Mach. Learn., 2011, pp. 1–8.
[11] F. Shen, C. Shen, Q. Shi, A. van den Hengel, and Z. Tang, “Inductive
hashing on manifolds,” in Proc. IEEE Conf. Comput. Pattern Recog.,
Jun. 2013, pp. 1562–1569.
[12] J. H. Friedman, J. L. Bentley, and R. A. Finkel, “An algorithm for finding
best matches in logarithmic expected time,” ACM Trans. Math. Softw.,
vol. 3, no. 3, pp. 209–226, 1977.
[13] A. Guttman, “R-trees: A dynamic index structure for spatial searching,”
in Proc. Annu. Meet., 1984, pp. 47–57.
[14] A. Gionis, P. Indyk, and R. Motwani, “Similarity search in high dimensions
via hashing,” in Proc. Int. Conf. Very Large Data Bases, 1999, pp. 518–
529.
[15] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni, “Locality-sensitive
hashing scheme based on p-stable distributions,” in Proc. ACM Symp.
Comput. Geometry, 2004, pp. 253–262.
[16] J. Wang, S. Kumar, and S. F. Chang, “Semi-supervised hashing for largescale search,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 34, no. 12,
pp. 2393–2406, Dec. 2012.
[17] Y. Weiss, A. Torralba, and R. Fergus, “Spectral hashing,” in Proc. Adv.
Neural Inf. Process. Syst., 2008, pp. 1753–1760.
[18] Y. Sun, M. K. Ng, and Z. Zhou, “Multi-instance dimensionality reduction,”in Proc. 24th AAAI Conf. Artif. Intell., 2010, pp. 587–592.

2559[19] B. Kulis and T. Darrell, “Learning to hash with binary reconstructive
embeddings,” in Proc. Adv. Neural Inf. Process. Syst., 2009, pp. 1042–
1050.
[20] C. Strecha, A. M. Bronstein, M. M. Bronstein, and P. Fua, “Ldahash:Improved matching with smaller descriptors,” IEEE Trans. Pattern Anal.
Mach. Intell., vol. 34, no. 1, pp. 66–78, Jan. 2012.
[21] M. Norouzi and D. J. Fleet, “Minimal loss hashing for compact binary
codes,” in Proc. Int. Conf. Mach. Learn., 2011, pp. 353–360.
[22] W. Liu, J. Wang, R. Ji, Y. Jiang, and S. Chang, “Supervised hashing withkernels,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., Jun. 2012,
pp. 2074–2081.
[23] T. Ge, K. He, and J. Sun, “Graph cuts for supervised binary coding,” inProc. Eur. Conf. Comput. Vis., 2014, pp. 250–264.
[24] Y. Yang, W. Chen, Y. Luo, F. Shen, J. Shao, and H. T. Shen, “Zero-shothashing via transferring supervised knowledge,” in Proc. ACM Multimedia
Conf., 2016, pp. 1286–1295.
[25] F. Shen, C. Shen, W. Liu, and H. T. Shen, “Supervised discrete hashing,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., Jun. 2015,
pp. 37–45.
[26] R. Xia, Y. Pan, H. Lai, C. Liu, and S. Yan, “Supervised hashing for image
retrieval via image representation learning,” in Proc. Conf. Artif. Intell.,
2014, pp. 2156–2162.
[27] F. Zhao, Y. Huang, L. Wang, and T. Tan, “Deep semantic ranking basedhashing for multi-label image retrieval,” in Proc. IEEE Conf. Comput. Vis.
Pattern Recog., Jun. 2015, pp. 1556–1564.
[28] K. Lin, H. Yang, J. Hsiao, and C. Chen, “Deep learning of binary hashcodes for fast image retrieval,” in Proc. Conf. Comput. Vis. Pattern Recog.
Workshops, Jun. 2015, pp. 27–35.
[29] H. Lai et al., “Instance-aware hashing for multi-label image retrieval,”
IEEE Trans. Image Process., vol. 25, no. 6, pp. 2469–2479, Jan. 2016.
[30] Z. Chen, J. Lu, J. Feng, and J. Zhou, “Nonlinear discrete hashing,” IEEE
Trans. Multimedia, vol. 19, no. 1, pp. 123–135, Jan. 2017.
[31] C. Wu, J. Zhu, D. Cai, C. Chen, and J. Bu, “Semi-supervised nonlinear hashing using bootstrap sequential projection learning,” IEEE Trans.
Knowl. Data Eng., vol. 25, no. 6, pp. 1380–1393, Jun. 2013.
[32] W. Kong and W. Li, “Isotropic hashing,” in Proc. Conf. Neural Inf. Process.
Syst., 2012, pp. 1655–1663.
[33] G. Irie, Z. Li, X. Wu, and S. Chang, “Locally linear hashing for extracting
non-linear manifolds,” in Proc IEEE Conf. Comput. Vis. Pattern Recog.,
Jun. 2014, pp. 2123–2130.
[34] Y. Weiss, “Segmentation using eigenvectors: A unifying view,” in Proc.
7th IEEE Int. Conf. Comput. Vis., Sep. 1999, pp. 975–982.
[35] M. Belkin and P. Niyogi, “Laplacian eigenmaps for dimensionality reduction and data representation,” Neural Comput., vol. 15, no. 6, pp. 1373–
1396, 2003.
[36] J. B. Tenenbaum, V. de Silva, and J. C. Langford, “A global geometricframework for nonlinear dimensionality reduction,” Science, vol. 290,
no. 5500, pp. 2319–2323, 2000.
[37] S. T. Roweis and L. K. Saul, “Nonlinear dimensionality reduction by
locally linear embedding,” Science, vol. 290, pp. 2323–2326, 2000.
[38] M. Á. Carreira-Perpiñán, “The elastic embedding algorithm for dimensionality reduction,” in Proc. Int. Conf. Mach. Learn., 2010, pp. 167–174.
[39] L. van der Maaten and G. Hinton, “Visualizing high-dimensional datausing t-sne,” J. Mach. Learn. Res., vol. 25, no. 9, pp. 2579–2605, 2008.
[40] G. Hinton and R. Salakhutdinov, “Reducing the dimensionality of datawith neural networks,” Science, vol. 313, no. 5786, pp. 504–507, 2006.
[41] V. E. Liong, J. Lu, G. Wang, P. Moulin, and J. Zhou, “Deep hashing forcompact binary codes learning,” in Proc. IEEE Conf. Comput. Vis. Pattern
Recog., Jun. 2015, pp. 2475–2483.
[42] H. Jégou, M. Douze, and C. Schmid, “Product quantization for nearest
neighbor search,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 1,
pp. 117–128, Jan. 2011.
[43] M. Norouzi and D. J. Fleet, “Cartesian k-means,” in Proc. IEEE Conf.
Comput. Vis. Pattern Recog., Jun. 2013, pp. 3017–3024.
[44] T. Zhang, C. Du, and J. Wang, “Composite quantization for approximate
nearest neighbor search,” in Proc. Int. Conf. Mach. Learn., 2014, pp. 838–846.
[45] L. Mukherjee, S. N. Ravi, V. K. Ithapu, T. Holmes, and V. Singh, “AnNMF perspective on binary hashing,” in Proc. IEEE Int. Conf. Comput.
Vis., Dec. 2015, pp. 4184–4192.
[46] Z. Cai, L. Liu, M. Yu, and L. Shao, “Latent structure preserving hashing,”
in Proc. Brit. Mach. Vis. Conf., 2015, pp. 172-1–172-11.
[47] D. Wang, P. Cui, M. Ou, and W. Zhu, “Learning compact hash codes for
multimodal representations using orthogonal deep structure,” IEEE Trans.
Multimedia, vol. 17, no. 9, pp. 1404–1416, Sep. 2015.

2560[48] R. Gray and D. Neuhoff, “Quantization,” IEEE Trans. Inf. Theory, vol. 44,
no. 6, pp. 2325–2384, Oct. 1998.
[49] D. D. Lee and H. S. Seung, “Algorithms for non-negative matrix factorization,” in Proc. Conf. Neural Inf. Process. Syst., 2000, pp. 556–562.
[50] D. D. Lee and H. S. Seung, “Learning the parts of objects by nonnegative
matrix factorization,” Nature, vol. 401, pp. 788–791, 1999.
[51] J. Wang, W. Liu, S. Kumar, and S. Chang, “Learning to hash for indexing
big data— survey,” Proc. IEEE, vol. 104, no. 1, pp. 34–57, Jan. 2016.
[52] J. Wang, T. Zhang, J. Song, N. Sebe, and H. T. Shen, “A survey on learning
to hash,” IEEE Trans. Pattern Anal. Mach. Intell., vol. PP, no. 99, p. 1,
2017.
[53] M. W. Berry and M. Browne, “Email surveillance using non-negative
matrix factorization,” Comput. Math. Org. Theory, vol. 11, no. 3, pp. 249–
264, 2005.
[54] Y. Bao, H. Fang, and J. Zhang, “Topicmf: Simultaneously exploiting ratings and reviews for recommendation,” in Proc. 28th AAAI Conf. Artif.
Intell., 2014, pp. 2–8.
[55] G. Trigeorgis, K. Bousmalis, S. Zafeiriou, and B. W. Schuller, “A deepsemi-nmf model for learning hidden representations,” in Proc. Int. Conf.
Mach. Learn., 2014, pp. 1692–1700.
[56] K. Huang, N. D. Sidiropoulos, and A. Swami, “Non-negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition,” IEEE Trans. Signal Process., vol. 62, no. 1, pp. 211–224, Jan.
2014.
[57] Z. Li, X. Wu, and H. Peng, “Nonnegative matrix factorization on orthogonal subspace,” Pattern Recog. Lett., vol. 31, no. 9, pp. 905–911, 2010.
[58] C. Ding, T. Li, W. Peng, and H. Park, “Orthogonal nonnegative matrix
t-factorizations for clustering,” in Proc. Int. Conf. Knowl. Discovery Data
Mining, 2006, pp. 126–135.
[59] M. Collins, S. Dasgupta, and R. E. Schapire, “A generalization of principal
components analysis to the exponential family,” in Proc. Conf. Neural Inf.
Process. Syst., 2001, pp. 617–624.
[60] I. Jolliffe, Principal Component Analysis, 2nd ed. New York, NY, USA:
Springer, 2002.
[61] L. van der Maaten and G. E. Hinton, “Visualizing high-dimensional datausing t-sne,” J. Mach. Learn. Res., vol. 9, pp. 2579–2605, 2008.
[62] A. Torralba, R. Fergus, and W. T. Freeman, “80 million tiny images:
A large data set for nonparametric object and scene recognition,” IEEE
Trans. Pattern Anal. Mach. Intell., vol. 30, no. 11, pp. 1958–1970, Nov.
2008.
Lei Ma received the B.Sc. degree in communicationengineering from Hubei University, Wuhan, China,
in 2012, and is currently working toward the Ph.D
degree in signal and information processing at the Intelligent Visual Information Processing and Communication Laboratory, University of Electronic Scienceand Technology of China, Chengdu, China.
His research interests include large-scale multimedia indexing and retrieval, computer vision, patternrecognition, and machine learning.
Hongliang Li (M’06–SM’11) received the Ph.D. degree in electronics and information engineering fromXian Jiaotong University, Xian, China, in 2005.
From 2005 to 2006, he was with the Visual Signal Processing and Communication Laboratory, Chinese University of Hong Kong (CUHK), Hong Kong,
China, as a Research Associate. From 2006 to 2008,
he was a Postdoctoral Fellow with the same laboratory at CUHK. He is currently a Professor with the
School of Electronic Engineering, University of Electronic Science and Technology of China, Chengdu,
China. He has authored or coauthored numerous technical articles in well-known
international journals and conferences. He is a co-editor of the book Video Segmentation and its Applications (Springer, 2011). His research interests include
image segmentation, object detection, image and video coding, visual attention,and multimedia communication systems.
Prof. Li was involved in many professional activities. He is a Member ofthe Editorial Board of the Journal on Visual Communications and Image Representation, and the Area Editor of Signal Processing: Image Communication,
Elsevier Science. He served as a Technical Program Co-Chair for VCIP2016
and ISPACS 2009, General Co-Chair of the ISPACS 2010, Publicity Co-Chair
of IEEE VCIP 2013, Local Chair of the IEEE ICME 2014, and a TPC member
in a number of international conferences, e.g., ICME 2013, ICME 2012, ISCAS
2013, PCM 2007, PCM 2009, and VCIP 2010.

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 19, NO. 11, NOVEMBER 2017

Fanman Meng (S’12–M’13) received the Ph.D. degree in signal and information processing from the
University of Electronic Science and Technology ofChina, Chengdu, China, in 2014.
From July 2013 to July 2014, he was with the Division of Visual and Interactive Computing, Nanyang
Technological University, Singapore, Singapore, asa Research Assistant. He is currently an Associate
Professor with the School of Electronic Engineering,
University of Electronic Science and Technology ofChina. He has authored or coauthored numerous technical articles in international journals and conferences. His research interests
include image segmentation and object detection.
Prof. Meng is a member of the IEEE CAS society. He was the recipient of
the “Best Student Paper Honorable Mention Award” for the 12th Asian Conference on Computer Vision (ACCV 2014) in Singapore and the “Top 10% Paper
Award” in the IEEE International Conference on Image Processing (ICIP 2014)
at Paris, France.

Qingbo Wu (S’12–M’15) received the B.E. degreein education of applied electronic technology from
Hebei Normal University, Shijiazhuang, China, in
2009, and the Ph.D. degree in signal and information processing from the University of Electronic Science and Technology of China, Chengdu, China, in2015.
From February 2014 to May 2014, he was a Research Assistant with the Image and Video Processing (IVP) Laboratory, Chinese University of Hong
Kong, Hong Kong, China. Then, from October 2014
to October 2015, he served as a Visiting Scholar with the Image & Vision
Computing (IVC) Laboratory, University of Waterloo, Waterloo, ON, Canada.
He is currently a Lecturer with the School of Electronic Engineering, University of Electronic Science and Technology of China. His research interests
include image/video coding, quality evaluation, and perceptual modeling andprocessing.

King Ngi Ngan (M’79–S’79–M’82–SM’91–F’00)
received the Ph.D. degree in electrical engineering from Loughborough University, Loughborough,U.K., in 1982.
He is currently a Chair Professor with the Department of Electronic Engineering, Chinese Universityof Hong Kong, Hong Kong, China. He was previously a Full Professor with the Nanyang Technological University, Singapore, and the University ofWestern Australia, Crawley, WA, Australia. He has
been appointed a Chair Professor at the University
of Electronic Science and Technology, Chengdu, China, under the National
Thousand Talents Program since 2012. He holds honorary and visiting professorships of numerous universities in China, Australia, and South East Asia.
He has published extensively, including 3 authored books, 7 edited volumes,
more than 400 refereed technical papers, and edited 9 special issues in journals. In addition, he holds 15 patents in the areas of image/video coding andcommunications.
Prof. Ngan is a Fellow of IET (U.K.) and IEAust (Australia), and was anIEEE Distinguished Lecturer from 2006–2007. He served as an Associate Editorof IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY,
Journal on Visual Communications and Image Representation, EURASIP Journal of Signal Processing: Image Communication, and Journal of Applied Signal
Processing. He chaired and co-chaired a number of prestigious international
conferences on image and video processing including the 2010 IEEE International Conference on Image Processing, and served on the advisory and technicalcommittees of numerous professional organizations.