Mining on Heterogeneous Manifolds for Zero-shot Cross-modal Image Retrieval
Fan Yang1,2 , Zheng Wang2,∗ , Jing Xiao2 , and Shin’ichi Satoh1,2
1
The University of Tokyo, Japan
National Institute of Informatics, Japan{yang, wangz, jing xiao, satoh}@nii.ac.jp
2

Abstract
Most recent approaches for the zero-shot cross-modal image
retrieval map images from different modalities into a uniform
feature space to exploit their relevance by using a pre-trainedmodel. Based on the observation that manifolds of zero-shot
images are usually deformed and incomplete, we argue thatthe manifolds of unseen classes are inevitably distorted during the training of a two-stream model that simply maps images from different modalities into a uniform space. This issue directly leads to poor cross-modal retrieval performance.
We propose a bi-directional random walk scheme to mining
more reliable relationships between images by traversing heterogeneous manifolds in the feature space of each modality. Our proposed method benefits from intra-modal distributions to alleviate the interference caused by noisy similarities in the cross-modal feature space. As a result, weachieved great improvement in the performance of the thermal v.s. visible image retrieval task. The code of this paper:https://github.com/fyang93/cross-modal-retrieval

1

Introduction

The ongoing prosperity of deep learning lowers the barrier
to produce reliable image representations. Given robust image representations, previous studies have made tremendous
progress on the task of image retrieval. Although most image retrieval tasks are enclosed in a single modality, e.g. allimages are from the RGB domain, a rising trend is to breakthrough this limitation so that images can be queried acrossdifferent modalities. However, a huge performance gap canstill be observed between intra-modal and cross-modal image retrieval tasks (Ye et al. 2018b; Wang et al. 2019;2018). We specifically focus on the zero-shot cross-modal
image retrieval where the testing images are sampled fromclasses that never appeared in the training set.
For a single-modal task, it is general to fine-tune a model
pre-trained on ImageNet (Deng et al. 2009) and extract
image features from its intermediate layers. While for across-modal task, the images come from two subsets corresponding to two different modalities. In this regard, the∗corresponding author
Copyright c 2020, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

cross-modal model usually has two streams where each ofthem handles images input from each modality. Those two
streams join together at the tail of the model, mapping
image features from two modalities into a shared feature
space, with a classifier attached afterward (Ye et al. 2018a;
2018b). Although such a model memorized how to map
training images of the same class into a concentrated cluster whichever modalities they are from, we argue that aligning classes in the training set across different modalities inevitably distorts the remaining manifolds consists of samples
of unseen classes.
Fig. 1 visualizes this phenomenon. Fig. 1a shows the feature distribution of digits 7 to 9 in the MNIST dataset wherefeatures are extracted by a single-modal model which istrained by using other digits in the MNIST dataset only.
While Fig. 1b shows the feature distribution for the SVHN
dataset. Although imperfect, it can be observed that mostimage features are concentrated around their class centers.
The cross-modal model, instead, is trained with images fromboth modalities (i.e. modalities of MNIST and SVHN) andresults in a cluttered distribution in its uniform feature space(Figs. 1c and 1d). Particularly, it can be observed that the
manifold of digit 9 in Fig. 1d is isolated into several blobs.
Needless to say, this issue directly results in poor crossmodal retrieval performance.
Some may ascribe such a phenomenon to the over-fitting,but we have another plausible interpretation. Suppose that
we have images of lemon, lime, and mango. In the color domain, lemon is more similar to mango than lime in terms ofcolor. While in the monochrome domain, lemon is closer tolime than mango in terms of shape. These domain-specificrelationships are helpful in forming the feature distribution
in every single domain. However, when we train a crossmodal model by using all images of lemon and lime, the conflicts among those relationships (lemon and lime are close in
shape but far in color) ask both domains to adapt its feature
space for each other. As a result, the feature space of eachdomain is distorted and the feature manifold of the unseenclass mango is very likely to be torn into parts.
In this work, we propose to leverage the domain-specificinformation by mining on manifolds in different singlemodal feature spaces. Our idea is straightforward. Now that

40
20

20

0

20

20

10

10

0

0

20

30

30

40

0

10

10

20

20

20

30

40

40
30

20

10

0

10

20

30

40

(a) MNIST → MNIST

40
30

20

10

0

10

20

30

40

(b) SVHN → SVHN

30
40

30

20

10

0

10

20

30

(c) SVHN → MNIST

40

20

10

0

10

20

(d) MNIST → SVHN

Figure 1: Visualization of feature distributions [t-SNE (Maaten and Hinton 2008)] for zero-shot digits 7 ( ), 8( ) and 9( )in single-modal spaces (a)(b) and cross-modal spaces (c)(d), while other digits (0∼6) are used for training. Samples from thequery set and the gallery set are represented by triangles and circles respectively. The subcaptions are formatted by {dataset
whose testing set (7∼9) is used as query} → {dataset whose training set (7∼9) is used as gallery}.
the manifolds of zero-shot images in the cross-modal feature space are distorted and possibly incomplete, while thesingle-modal spaces have complete yet well-shaped manifolds. We take the nearest neighbors of a query in the
cross-modal feature space as the initial state, then apply
random walk on the corresponding single-modal feature
space. In other words, we use the cross-modal feature space
as a bridge to connect heterogeneous manifolds of different modalities. Our main contributions are 1) we show the
proofs that mapping images from different modalities into a
uniform feature space distorts manifolds of unseen classes;
2) we propose a novel random walk scheme which benefits from the reliable feature distributions created by singlemodal models; 3) we validate our method on visible v.s. thermal datasets and achieves significant performance improvement.
The rest of the paper is structured as follows. After introducing the related work, we formulate our proposed bidirectional random walk scheme in Section 3. Section 4 describes our experimental settings and Section 5 demonstrates
the results, showing that our proposed method significantly
improves retrieval performance before concluding.

2

Related Works

Existing approaches for cross-modal image retrieval mainly
focused on the representation learning to coalesce feature
spaces in different modalities, such as visible and infrared
modalities. (Wu et al. 2017) introduced a deep zero-padding
framework where images from different modalities share acommon convolutional network during the feature generation. However, instead of training a common network, it
is natural to benefit from the intrinsic context inside each
modality by using a two-stream model. The literature isrich in the applications of the two-stream model with various training strategies. Some early researches trained themodel to generate hashing code as features (Cao et al. 2016;2017). Different loss functions designed for metric learning, e.g. contrastive loss, ranking loss, and sphere loss
were employed in recent works (Ye et al. 2018a; 2018b;
Hao et al. 2019). (Dai et al. 2018) adopted a generative adversarial training strategy which was first used in the text v.s.

image retrieval (Wang et al. 2017). The key idea is to update
image features to fool the discriminator so that it cannot distinguish the source modality of the feature, while the discriminator is trained to categorize features into their source
modalities at the same time. Another recent trend is to apply
data augmentation by converting images to other modalities
with generative adversarial networks (Wang et al. 2019).
Besides the representation learning performed by theabove methods, it is equivalently important to choose aproper search algorithm. Based on the k-NN search, average query expansion is a widely used technique to boost
performance (Chum et al. 2007). Other than that, a better
image retrieval performance can also be achieved throughmining on manifolds. (Zhou et al. 2004) first proposed to
conduct a random walk on an undirected graph where each
image is connected to its locally nearest neighbors. Startingfrom an initial state, such a random walk process spreads
out the weight on the query node iteratively until it reaches
a stable state. The weights on other nodes are then regarded
as the similarity scores to the query. Since the graph represents local relationships between images, it allows traversing over manifolds regardless of their shapes and ranges.
(Donoser and Bischof 2013) used the term diffusion to describe this technique. Recent works focused on improving diffusion’s speed and performance. (Bai et al. 2017a;
2017b) proposed the regularized ensemble diffusion to suppress the noisy similarities between false-positive image
pairs in the graph. (Iscen et al. 2018) extended diffusion toregional features and achieved better retrieval performance
than using global features only. (Yang et al. 2019) decoupled
diffusion into online and offline processes, making it efficient during the search time. In addition, they achieved better performance by conducting late truncation in large scale
datasets.

3

Proposed Method

We propose a bi-directional random walk scheme forcross-modal image retrieval. Such a random walk approach was also called diffusion in single-modal image
retrieval (Donoser and Bischof 2013; Iscen et al. 2017;
Yang et al. 2019). We avoid using the term diffusion sinceSubsetScoresm features

0.3 0.6 0.8 0.1

Model for
SubsetGraph

0.2

0.5 0.7 0.3 0.5 0.6
0.8 0.7 0.2 0.3 0.5

RandomWalk

Cross-modal
Model

Combine0.2 0.5 0.7
0.5 0.8 0.5

Model for
SubsetSubset0.8 0.3

0.1

0.5 0.6

0.1

0.1

n features

0.7 0.8

Figure 2: Overview of our proposed bi-directional random walk scheme. The black arrows show the pipeline to obtain the graphrepresented by an adjacency matrix, while the blue and green paths describe the random walk processes in both directions.
our problem setting is not just diffusing similarity scores in
the gallery for the given query but in both directions.

scores to each other:A=

3.1

Problem Definition

For cross-modal image retrieval, we have two subsets containing images of two different modalities. We name the two
subsets X = {x1 , . . . , xm } and Y = {y1 , . . . , yn }. For
each subset, we train a single-modal model to obtain feature
representations. We denote fx : X 7→ Rd and fy : Y 7→ Rd
as feature extraction operations for each subset using thecorresponding models. We also train a cross-modal model,
serving as a bridge to relate two subsets, to project all images
to feature vectors in a uniform space where the inputs fromtwo modalities are mapped into. This operation is denotedby fu : {X , Y} 7→ Rd .
Now that the cross-modal image retrieval problem is depicted as ranking the images in Y by their similarities to
the given query image xi ∈ X , or ranking X by the given
query yj ∈ Y. A naive solution is to apply k-NN searchin {fu (x1 ), . . . , fu (xn )} ({fu (y1 ), . . . , fu (yn )}) with thequery fu (yi ) (fu (xi )). However, as we mentioned in Section 1, the manifolds of unseen classes in the uniform feature space are very likely to be deformed during the trainingof a two-stream model. In severe cases such as searching for
digit 7 in SVHN by the given queries in MNIST (see Fig. 1d,blue), k-NN search can find either a small portion of thepositive samples or negative ones. To alleviate this issue,
we propose to construct graphs for heterogeneous manifolds
in the single-modal spaces and apply a random walk across
them.

3.2

Graph Construction

We first consider a large graph representing affinities between all images, then show how to split it up. The entire
dataset {X , Y} contains m + n images, so we allocate aR(m+n)×(m+n) adjacency matrix to record their similarity


Axx
Ayx


Axy
,
Ayy

(1)

where Axx ∈ Rm×m , Axy ∈ Rm×n , Ayx ∈ Rn×m , andAyy ∈ Rn×n .
To benefit from the domain-specific information, we compute Axx and Ayy by using their features from two isolated
single-modal models. This process is shown in Fig. 2 by
black arrows. Following (Iscen et al. 2017), we set elementaij (i 6= j) in Axx to hfx (xi ), fx (xj )i only if fx (xi ) andfx (xj ) are in each other’s k nearest neighbors, and 0 otherwise. We omit the description to obtain Ayy since it is alike.
Notice that Axy and Ayx are used to save the similarity
scores between images from different modalities. Therefore,
it requires a measurement in a shared feature space. As aresult, element aij (i 6= j) in Axy is hfu (xi ), fu (yj )i only
if fu (xi ) and fu (yj ) are in each other’s k nearest neighbors,and 0 otherwise. Ayx is the transposition of Axy .
Since we only concern about the affinities between each
image and its locally nearest neighbors, the adjacency matrix
is sparse and costs a limited amount of memory.

3.3

Random Walk

Now we have constructed the graph represented by an adjacency matrix. We still need to convert it to a transition matrix for the next random walk. This step is called normalization. Since the adjacency matrix consists of blocks containing similarity scores measured in different spaces, here webreak down the adjacency matrix and apply normalizationindividually to each block. Specifically, Axx and Ayy are
symmetrically normalized by
−1/2
−1/2
−1/2
Sxx = D−1/2
xx Axx Dxx , Syy = Dyy Ayy Dyy , (2)where elements on the diagonal of Dxx and Dyy are therow-wise sums of Axx and Ayy respectively, while the offdiagonal elements are all zeros. On the other hand, Axy andAyx are `1 normalized to Sxy and Syx by row. Similar tothe structure of the adjacency matrix, the transition matrix isdefined as


S
Sxy
S = xx.
(3)
Syx SyyOnce the transition matrix is prepared, we can start the
random walk from any wanted initial states. The state vector>>
at t-th step of random walk is denoted by f t = [fxt , fyt ]> ,where fxt ∈ Rm and fyt ∈ Rn . On each random walk stage,
we concern about the retrieval result of one query image.
Therefore, we set the initial state f 0 as a one-hot vector,
where the position of 1 implies the index of the query. Another parameter α ∈ (0, 1) is introduced to ensure that the
random walk can finally converge to a stable state. Theneach iteration step of random walk is defined asf t+1 = αSf t + (1 − α)f 0 .

shared space(a) Query-guided truncation(4)

After assigning Eq. (3) into Eq. (4), we obtainfxt+1 = αSxx fxt + αSxy fyt + (1 − α)fx0 ,fyt+1 = αSyx fxt + αSyy fyt + (1 − α)fy0 .

shared space(5)

When the query image lies in the subset X (Y), we only
concern the similarity scores between the query and each
image in subset Y (X ). It means that we only need to compute either fx∞ or fy∞ rather than both of them. For instance,
during the computation of fy∞ , Sxx and Sxy are regarded aszero matrices so that fxt is always fixed. Similarly, fyt is fixedduring the computation of fx∞ . As a result, we obtain theclosed-form solution for fx∞ and fy∞ :gallery space(b) Gallery-guided truncation

Figure 3: Comparison between the query-guided truncationand the gallery-guided truncation, where the query is in dark
blue while the gallery samples are in light blue. The pinkarea represents the final range to search in.

where fx0 and fy0 are one-hot vectors representing the index
of query image in subset X and Y.

it is preferable to apply truncation in the single-modal spaceof the gallery side instead of the noisy cross-modal space.
Therefore, our solution is to look for a few nearest neighbors of the query in the cross-modal space and then apply
the gallery-guided truncation in the single-modal space.
From the perspective of math, the truncation can be either
achieved by slicing the matrices to only reserve concernedrows and columns or simply replacing the similarities out ofinterest to zeros. For simplicity, we do not revise the notations of matrices to refer to the truncated ones. Unless otherwise stated, Laplacian matrices (Lxx and Lyy ) are truncatedby default throughout this paper.

3.4

3.5

fx∞ = α(1 − α)(I − αSxx )−1 Sxy fy0 ,fy∞ = α(1 − α)(I − αSyy )−1 Syx fx0 .

(6)

For brevity, the constant scale α(1 − α) is ignored and I −αS(·) is denoted by L(·) by convention. Eventually, Eq. (6)is simplified to0∞−10
fx∞ ∝ L−1
xx Sxy fy , fy ∝ Lyy Syx fx ,(7)

Graph Truncation

Truncation is a necessary technique in applying random
walk to large datasets. The key idea is to search in a proper
range of the query’s neighborhood rather than the entire
gallery. Recently, (Yang et al. 2019) showed that truncation can not only enhance efficiency but also improves retrieval performance by ruling out potential false-positive
samples. There are two main types of truncation (Iscen etal. 2018; Yang et al. 2019). Fig. 3 demonstrates the difference between them. The query-guided truncation conducts a k-NN search and uses found samples as the truncated gallery. This requires the query and the gallery to bein the same space. While the gallery-guided truncation decides the search range by combining several neighborhood
ranges around the query’s nearest neighbors. In other words,
a few nearest neighbors of the query can help to apply truncation in another feature space (see Fig. 3b). In our scenario,

Bi-directional Retrieval

As afore-mentioned, we aim at the bi-directional retrieval
instead of the unidirectional retrieval from the query side to
the gallery side. That means we view both subsets X andY equivalently, and each of them can be either the query or
the gallery. In this regard, we exploit heterogeneous manifolds of both modalities by conducting random walk on theconstructed graphs.
Eq. (7) shows the convergence of the random walk process. Scores in the final state of the random walk are important cues for ranking images by their similarities to the queryon manifolds. For instance, starting from the i-th query image in the subset Y, the final state vector fx∞ is the i-th column vector of the matrix L−1
xx Sxy whose elements are also
viewed as scores for the subsequent ranking. In other words,
m×n
n×m
L−1
and L−1
consists of thexx Sxy ∈ R
yy Syx ∈ Rsimilarity scores of each query image in Y and X respec-where λ is weight for balancing the scores obtained fromboth directions. Note that we do not choose to normalize
similarity scores. In the later experiment (see Fig. 5), weshow that normalizing similarity scores for each query has
no positive effect on the performance.

MNIST and SVHN are both digit datasets. The MNIST
dataset (LeCun et al. 1998) consists of handwitten digit images from 0 to 9 of size 28×28. Among them, 60,000 binary
images are in the training set and 10,000 in the testing set.
The SVHN (Street View House Numbers) dataset (Netzer et
al. 2011), as implied by its name, consists of RGB images ofdigits. It contains 73,257 training and 26,032 testing imagesof size 32 × 32.
RegDB contains images of 412 persons. 10 visible images
and 10 thermal images were captured for each person by adual-camera system (Nguyen et al. 2017). We take the evaluation protocol in (Ye et al. 2018b) where the entire dataset
was divided into a training set and a testing set. On the testing stage, query images and gallery images are from different modalities for evaluating the cross-modal image retrieval. Since the dataset was randomly split, it is recommended to run the whole procedure for 10 trials to obtainstatistically stable results.
SYSU-MM01 consists of visible and thermal images of
491 identities captured by 6 cameras including 4 RGB cameras and 2 infrared cameras (Wu et al. 2017). Those RGB
cameras and IR cameras work in light and dark scenarios respectively. The training set contains 22,258 visible images
and 11,909 thermal images of 395 persons. The testing set
contains 3,803 thermal query images where 96 persons appeared, and 301 visible images randomly sampled for each
person as the gallery set. Following the evaluation protocolin (Ye et al. 2018b; Wang et al. 2019), we adopt the mostchallenging single-shot all-search mode evaluation protocol. However, it should be clarified that we adopt the entire gallery set during the graph construction, and randomly
select 301 entries for each person in the result of our bidirectional retrieval for the subsequent evaluation.

Model Fine-tuning

Our main concern is to exploit the manifolds in feature distributions rather than features themselves. So we merely
adopt two baseline models (see Fig. 4) for feature extraction. Fig. 4a shows the model for images in a single modality, while Fig. 4b shows the cross-modal model taking images from two different modalities as input. ResNet18 serves
as the backbone CNN for MNIST and SVHN datasets, while

CNN

FC2

Triplet Loss
FC2

Datasets

We first introduce two well-known digit classification
datasets briefly, then describe two person re-identification
datasets with both visible and thermal (infrared) images.

4.2

CNN
FC1

4.1

Datasets and Setup

Identity Loss LossClassification(a) Single-modal model

LeakyReLU

4

LeakyReLU

CNN

BN

(8)

BN

−1
>
B = λL−1
xx Sxy + (1 − λ)(Lyy Syx ) ,FC1

tively. We define the result of our bi-directional retrieval as

Classification Loss(b) Cross-modal model

Figure 4: Overview of our adopted models. The batchnormalization is only used for RegDB and SYSU-MM01
datasets. For digit images, we use features extracted fromthe FC1 layer, while for person images, we use features extracted from the batch normalization layer.
ResNet50 is used for RegDB and SYSU-MM01 datasets (Heet al. 2016). Both of them are pre-trained on the ImageNet
dataset. We take the backbone’s convolutional layers followed by an adaptive average pooling layer as the feature provider. The rest part of the models is shared. Following (Ye et al. 2018a), image features flow into a fullyconnected layer (FC1), followed by a batch normalization
block and a leaky ReLU. Here, the dimension of the output of FC1 is set to 512 for all datasets. Notice that we only
use batch normalization in training models for RegDB and
SYSU-MM01 datasets. At the end of the model, an FC layer(FC2) is attached for classification.
We then fine-tune the models for each dataset. For eachclass, we fine-tune a single-modal model by using crossentropy as the criterion for classification. These fine-tuned
single-modal models function as fx and fy defined in Section 3.1 where we take image representations from the FC1
layer for digit images and the batch normalization block forperson images. The training of the cross-modal model is a
bit more difficult. As shown in Fig. 4b, average pooled features from two streams are mapped into a uniform space bya shared FC1 layer. Besides the classification loss, i.e. crossentropy, a batch hard triplet loss (Hermans, Beyer, and Leibe2017) is introduced to push features of the same class togather closer. The overall loss function for the cross-modal
model isL = Lclass + βLtri ,(9)where β is a weight on the triplet loss. In our experiments,
we consistently set β = 0.2 and the margin of triplet loss to
0.6 through validation.
During the training, 7 digits (0 to 6) are used for the
MNIST and SVHN datasets only. The remaining three digits are then regarded as zero-shot classes, which is coherent

GalleryRank-1

Rank-5

Rank-10

mAP

MNIST
SVHN
SVHN
MNIST

MNIST
SVHN
MNIST
SVHN

96.4%
89.0%
59.0%
45.2%

98.5%
97.0%
80.0%
83.3%

99.0%
98.5%
84.9%
95.6%

69.1%
65.4%
48.3%
46.7%

Table 1: Intra-modal and cross-modal image retrieval performance by using k-NN search on digit datasets.
with Fig. 1.

5

Experiments

We show the effectiveness of the proposed method on theabove datasets by conducting cross-modal image retrieval
in this section. We particularly explain the way we perform retrieval on the MNIST and SVHN datasets. Those
two datasets are made for classification rather than retrieval,
therefore we have to manually set up two subsets for eachof them, i.e. the query set and the gallery set. As describedin Fig. 1, we use the training set of digits 7 to 9 as thegallery, while samples in the testing set are used as queries.
In the MNIST dataset, the numbers of images in the queryand gallery set are 3,011 and 18,065 respectively. While the
SVHN dataset has 15,299 images in the gallery and 5,274
query images.
In addition to the proposed bi-directional random walkon heterogeneous manifolds, we also conduct experiments
on homogeneous manifolds for comparison. It only differsfrom the heterogeneous way in constructing graphs, namely,
it computes Axx and Ayy by using cross-modal features.
Here, the homogeneous manifolds refer to manifolds in the
cross-modal uniform feature space. Although they consist offeatures from different modalities, we regarded them as homogeneous manifolds since all the images are intentionallymapped into a uniform feature space.

5.1

Digit Image Retrieval

We first perform the naive k-NN search for all combinationsof two digit datasets. Table 1 shows the results. The gap between the performance of intra-modal and cross-modal is
obvious. As we discussed, the distortion on manifolds of
unseen classes caused by aligning classes in the training set
from different modalities is part of the reason.
Table 2 shows the retrieval performance by using the proposed bi-directional random walk scheme. The results are
obtained by mining on homogeneous manifolds in the crossmodal feature only or by mining on heterogeneous manifolds in the single-modal feature spaces bridged by thecross-modal feature space. It is obvious that mining on heterogeneous manifolds outperforms mining on homogeneous
manifolds in terms of rank-1 and mAP. Some may notice thatthe values of rank-5 to rank-20 are sometimes even lower
when mining on heterogeneous manifolds. The explanationof this issue lies in the pipeline of our approach. The proposed method tries to look for true-positive samples among
the single-modal feature space guided by a few locally nearest neighbors of the query found in the cross-modal feature

Manifold

Rank-1

Rank-5

Rank-10

mAP

S→M
S→M

Homo
Hetero

61.0%
61.7%

76.2%
74.0%

81.7%
79.4%

52.0%
58.4%

M→S
M→S

Homo
Hetero

46.7%
47.1%

84.0%
83.8%

96.4%
92.2%

51.7%
60.3%

Table 2: Cross-modal digit image retrieval performance bymining on homogeneous and heterogeneous manifolds using the proposed bi-directional random walk scheme. The
MNIST and SVHN datasets are denoted by their initials andthe first column implies the search direction formatted by{dataset of query} → {dataset of gallery}.
58.0%
56.0%

mAP

Query

54.0%

w/o normalization
normalized by query

52.0%
0.0

0.2

0.4

0.6

0.8

1.0

Figure 5: Performance v.s. the hyperparameter λ. The blue
curve is plotted by ensembling similarity scores obtained
from both search directions without normalization. While
the orange one is plotted by ensembling similarity scores
normalized by each query.

space. This means that our method can obtain reliable retrieval results if only some true-positive samples exist in theinitial search results in the cross-modal feature space, but
still fails when none of the true-positives are found in thevery first step. After all, our work focuses on filtering noisy
similarities by mining on heterogeneous manifolds but notcorrecting the cross-modal feature distribution. Mining onheterogeneous manifolds fails when the initial k-NN search
results contain none of the true-positives, while mining on
homogeneous manifolds performs the random walk inside
the cross-modal feature space and may find the first truepositive sample on the manifold which is not included in thenearest neighbors measured by the Euclidean distance. It is
possible that we use the results of mining on homogeneous
manifolds as the initial state for the random walk processof mining on heterogeneous manifolds, but it will double
the computational cost which is not worthy. The improvements on mAP are more convincing. Mining on heterogeneous manifolds achieved 9.1% (48.3% to 57.4%) and 5.4%
(52.0% to 57.4%) improvement compared with the baseline and mining on homogeneous manifolds when searching SVHN’s query images in MNIST’s gallery. Correspondingly, it outperforms the baseline and mining on homogeneous manifolds by 13.6% (46.7% to 60.3%) and 8.6%
(51.7% to 60.3%) when searching MNIST’s query images
in SVHN’s gallery.

40

20

60
30

10

40

20
10

0

20

0
10

0

10
20
20

20

40

30
40

30

20

10

0

10

20

30

40

(a) Thermal image feature space

30

20

10

0

10

20

30

(b) Visible image feature space

40

30

20

10

0

10

20

30

40

(c) Cross-modal uniform feature space

Figure 6: Visualization of feature distributions in the thermal, visible, and cross-modal spaces. Images of 10 identities in SYSUMM01’s testing set are sampled and used to provide features. Features from the thermal and visible modalities are separately
denoted by circles and triangles.
DatasetMethodRank-1

Rank-5

Rank-10

Rank-20

mAP

RegDB

One-stream (Wu et al. 2017)
Two-stream (Wu et al. 2017)
Zero-Padding (Wu et al. 2017)
TONE (Ye et al. 2018a)
HCML (Ye et al. 2018a)
Baseline
Proposed (homogeneous)
Proposed (heterogeneous)

13.1%
12.4%
17.8%
16.9%
24.4%
24.5%
30.1%
31.1%

–
–
–
–
–
36.8%
45.5%
42.3%

33.0%
30.4%
34.2%
34.0%
47.5%
44.4%
53.1%
47.0%

42.5%
41.0%
44.3%
44.1%
56.8%
55.1%
66.8%
58.6%

14.0%
13.4%
18.9%
14.9%
20.8%
23.9%
29.3%
32.1%

SYSU-MM01

One-stream (Wu et al. 2017)
Two-stream (Wu et al. 2017)
Zero-Padding (Wu et al. 2017)
TONE (Ye et al. 2018a)
HCML (Ye et al. 2018a)
BDTR (Ye et al. 2018b)
cmGAN (Dai et al. 2018)
Baseline
Proposed (homogeneous)
Proposed (heterogeneous)

12.0%
11.7%
14.8%
12.5%
14.3%
17.0%
26.9%
25.3%
33.9%
35.9%

–
–
–
–
–
–
–
51.5%
60.3%
61.5%

49.7%
48.0%
54.1%
50.7%
53.2%
55.4%
67.5%
65.7%
75.6%
73.0%

66.7%
65.5%
71.3%
68.6%
69.2%
72.0%
80.6%
80.2%
83.8%
86.1%

13.7%
12.9%
16.0%
14.4%
16.2%
19.7%
27.8%
26.7%
34.9%
38.0%

Table 3: Performance comparison with our baseline and previous works.
In addition, Fig. 5 shows the effect of the hyperparameter
λ defined in Eq. (8) by measuring the mAP when searching
digits from SVHN in MNIST. Usually, the two single-modal
feature spaces are complementary and combining them bycertain weights performs better than each side only (in thecase λ = 0 or 1), which can also be interpreted as an ensemble trick. Since the graphs are normalized before the random
walk, the similarity scores obtained from both directions areat the same numerical scale. It is observed that normalizing
the scores again does not help improve the performance.

5.2

Person Image Retrieval

To provide more evidence of the effectiveness of our proposed method, we also conduct experiments on person reidentification datasets. Since persons in the testing set of two
selected datasets never appear in their training set, it is fair
to regard the person re-identification on these two datasets

as zero-shot image retrieval tasks.
Fig. 6 visualizes the feature distributions for the SYSUMM01 dataset. In the single-modal spaces of thermal andvisible images, features of each identity are relatively
grouped in clusters. However, in the cross-modal feature
space, some samples are off the manifolds of their corresponding classes. We show this issue by highlighting two
typical cases in Fig. 6c for identity #49 (in green) and identity #85 (in red). This, again, supports our assumption thatmapping images from different modalities into a uniform
space distorts the manifolds of zero-shot data.
Table 3 shows the retrieval performance of our proposed
method and other previous works. We did not put much
effort into training the baseline but it is still comparable
to some methods we list. Mining on heterogeneous manifolds outperforms our baseline and mining on homogeneous
manifolds in the cross-modal feature space only, which isin coherence with the results in Table 2. As discussed in
the above section, the proposed method (heterogeneous)fails when the initial k-NN search results contain none of
the true-positives, while mining on homogeneous manifolds
performs the random walk inside the cross-modal feature
space and may find the first true-positive sample on the
manifold which is not included in the nearest neighbors
measured by the Euclidean distance. This issue sometimes
leads to worse rank-5 to rank-20 in the RegDB dataset. Unlike the rank values on the cumulative match characteristic (CMC) curve (DeCann and Ross 2013), the mAP protocol cares about both the precision and the recall. Our proposed method improved the mAP by 8.2% (23.9% to 32.1%)
and 11.3% (26.7% to 38.0%) in the RegDB and SYSUMM01 datasets respectively, which are no doubt significant
improvements.

6

Conclusion

In this paper, we propose a novel bi-directional random walk
scheme for zero-shot cross-modal image retrieval to exploit the heterogeneous manifolds in different single-modal
spaces. To the best of our knowledge, this is the very firsttime that the random walk on manifolds is used in the crossmodal retrieval task. We show by experiments that our approach consistently achieves better retrieval performance on
digit datasets as well as person re-identification datasets.

Acknowledgement
This study is supported by CREST (JPMJCR 1686).

References
Bai, S.; Bai, X.; Tian, Q.; and Latecki, L. J. 2017a. Regularized diffusion process for visual retrieval. In AAAI, 3967–
3973.
Bai, S.; Zhou, Z.; Wang, J.; Bai, X.; Jan Latecki, L.; andTian, Q. 2017b. Ensemble diffusion for retrieval. In ICCV,
774–783.
Cao, Y.; Long, M.; Wang, J.; Yang, Q.; and Yu, P. S. 2016.
Deep visual-semantic hashing for cross-modal retrieval. In
ACM SIGKDD, 1445–1454.
Cao, Y.; Long, M.; Wang, J.; and Liu, S. 2017. Collective deep quantization for efficient cross-modal retrieval. In
AAAI, 3974–3980.
Chum, O.; Philbin, J.; Sivic, J.; Isard, M.; and Zisserman,
A. 2007. Total recall: Automatic query expansion with agenerative feature model for object retrieval. In ICCV, 1–8.
Dai, P.; Ji, R.; Wang, H.; Wu, Q.; and Huang, Y. 2018. Crossmodality person re-identification with generative adversarial
training. In IJCAI, 677–683.
DeCann, B., and Ross, A. 2013. Relating roc and cmc curves
via the biometric menagerie. In BTAS, 1–8. IEEE.
Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and FeiFei, L. 2009. Imagenet: A large-scale hierarchical image
database. In CVPR, 248–255.
Donoser, M., and Bischof, H. 2013. Diffusion processes for
retrieval revisited. In CVPR, 1320–1327.

Hao, Y.; Wang, N.; Li, J.; and Gao, X. 2019. Hsme: Hypersphere manifold embedding for visible thermal person reidentification. In AAAI, 8385–8392.
He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016. Deep residual
learning for image recognition. In CVPR, 770–778.
Hermans, A.; Beyer, L.; and Leibe, B. 2017. In defense of
the triplet loss for person re-identification. arXiv preprint
arXiv:1703.07737.
Iscen, A.; Tolias, G.; Avrithis, Y.; Furon, T.; and Chum, O.
2017. Efficient diffusion on region manifolds: Recovering
small objects with compact cnn representations. In CVPR,
2077–2086.
Iscen, A.; Tolias, G.; Avrithis, Y.; and Chum, O. 2018. Mining on manifolds: Metric learning without labels. In CVPR,
7642–7651.
LeCun, Y.; Bottou, L.; Bengio, Y.; Haffner, P.; et al. 1998.
Gradient-based learning applied to document recognition.
Proc. IEEE 86(11):2278–2324.
Maaten, L. v. d., and Hinton, G. 2008. Visualizing data using
t-sne. Journal of machine learning research 9(Nov):2579–
2605.
Netzer, Y.; Wang, T.; Coates, A.; Bissacco, A.; Wu, B.; andNg, A. Y. 2011. Reading digits in natural images with unsupervised feature learning.
Nguyen, D.; Hong, H.; Kim, K.; and Park, K. 2017. Person
recognition system based on a combination of body images
from visible light and thermal cameras. Sensors 17(3):605.
Wang, B.; Yang, Y.; Xu, X.; Hanjalic, A.; and Shen, H. T.
2017. Adversarial cross-modal retrieval. In ACM Multimedia, 154–162.
Wang, Z.; Ye, M.; Yang, F.; Bai, X.; and Satoh, S. 2018.
Cascaded sr-gan for scale-adaptive low resolution person reidentification. In IJCAI, 3891–3897.
Wang, Z.; Wang, Z.; Zheng, Y.; Chuang, Y.-Y.; and Satoh,S. 2019. Learning to reduce dual-level discrepancy for
infrared-visible person re-identification. In CVPR, 618–626.
Wu, A.; Zheng, W.-S.; Yu, H.-X.; Gong, S.; and Lai, J.
2017. Rgb-infrared cross-modality person re-identification.
In ICCV, 5380–5389.
Yang, F.; Hinami, R.; Matsui, Y.; Ly, S.; and Satoh, S. 2019.
Efficient image retrieval via decoupling diffusion into online
and offline processing. In AAAI, volume 33, 9087–9094.
Ye, M.; Lan, X.; Li, J.; and Yuen, P. C. 2018a. Hierarchical discriminative learning for visible thermal person reidentification. In AAAI.
Ye, M.; Wang, Z.; Lan, X.; and Yuen, P. C. 2018b. Visible
thermal person re-identification via dual-constrained topranking. In IJCAI, 1092–1099.
Zhou, D.; Weston, J.; Gretton, A.; Bousquet, O.; andSchölkopf, B. 2004. Ranking on data manifolds. In
NeurIPS, 169–176.