Regularized Discriminant Embedding for Visual Descriptor Learning
Authors: Kye-Hyeon Kim, Rui Cai, Lei Zhang, Seungjin Choi
ICLR 2013

Abstract: Images can vary according to changes in viewpoint, resolution, noise, and illumination. In this paper, we aim to learn representations for an image, which are robust to wide changes in such environmental conditions, using training pairs of matching and non-matching local image patches that are collected under various environmental conditions. We present a regularized discriminant analysis that emphasizes two challenging categories among the given training pairs: (1) matching, but far apart pairs and (2) non-matching, but close pairs in the original feature space (e.g., SIFT feature space). Compared to existing work on metric learning and discriminant analysis, our method can better distinguish relevant images from irrelevant, but look-alike images.

Regularized Discriminant Embedding for Visual
Descriptor Learning
Kye-Hyeon Kim,a Rui Cai,b Lei Zhang,b Seungjin Choia∗
a Department of Computer Science, POSTECH, Pohang 790-784, Korea
b Microsoft Research Asia, Beijing 100080, China
fenrir@postech.ac.kr, {ruicai, leizhang}@microsoft.com,
seungjin@postech.ac.kr
Abstract
Images can vary according to changes in viewpoint, resolution, noise, and illu-
mination. In this paper, we aim to learn representations for an image, which are
robust to wide changes in such environmental conditions, using training pairs of
matching and non-matching local image patches that are collected under various
environmental conditions. We present a regularized discriminant analysis that em-
phasizes two challenging categories among the given training pairs: (1) matching,
but far apart pairs and (2) non-matching, but close pairs in the original feature
space (e.g., SIFT feature space). Compared to existing work on metric learning
and discriminant analysis, our method can better distinguish relevant images from
irrelevant, but look-alike images.
1 Introduction
In many computer vision problems, images are compared using their local descriptors. A local
descriptor is a feature vector, representing characteristics of an interesting local partin an image.
Scale-invariant feature transform (SIFT) [2] is popularly used for extracting interesting parts and
their local descriptors from an image. Then comparing two images is done by aggregating pairs
between each local descriptor in one image and its closest local descriptor in another image, whose
pairwise distances are below some threshold. The assumption behind this procedure is that local
descriptors corresponding to the same local part (“matching descriptors”) are usually close enough
in the feature space, whereas local descriptors belonging to different local parts (“non-matching
descriptors”) are far apart.
However, this assumption does not hold when there are signiﬁcant changes in environmental condi-
tions (e.g., viewpoint, illumination, noise, and resolution) between two images. For the same local
part, varying environment conditions can yield varying local image patches, leading to matching
descriptors far apartin the feature space. On the other hand, for different local parts, their image
patches can look similar to each other in some environmental conditions, leading to non-matching
descriptors close together. Fig. 1 shows some examples: in each triplet, the ﬁrst two image patches
belong to the same local part but captured under different environment conditions, while the third
patch belongs to a different part but looks similar to the second one, resulting that the SIFT descrip-
tors between non-matching local parts are closer than those between matching parts. Consequently,
comparing two images using their local descriptors cannot be done correctly when their are signiﬁ-
cant differences in environmental conditions between the images. Fig. 2(a) shows the cases.
In this paper, we address this problem by learning more robust representations for local image
patches where matching parts are more similar together than non-matching parts even under widely
varying environmental conditions.
∗The full version of this manuscript is currently under review in an international journal.
1
arXiv:1301.3644v1  [cs.CV]  16 Jan 2013
SIFT:    304 
LDE:     336 
Ours:    360 
SIFT:    213 
LDE:     268 
Ours:    295 
SIFT:    268 
LDE:     283 
Ours:    301 
231 
275 
425 
SIFT:    336 
LDE:     371 
Ours:    362 
> 
> 
< 
246 
314 
372 
> 
≈ 
< 
199 
264 
388 
SIFT:    267 
LDE:     240 
Ours:    257 
> 
< 
< 
257 
319 
405 
> 
< 
< 
232 
291 
335 
SIFT:    290 
LDE:     305 
Ours:    349 
> 
> 
< 
221 
278 
365 
> 
> 
< 
Figure 1: Some examples where a local part (center in each triplet) is closer to a non-matching part
(right) than a matching part (left) in terms of the Euclidean distances between their SIFT descriptors.
Using linear discriminant embedding (LDE) [1], non-matching pairs are still closer than matching
pairs in the ﬁrst three examples. Compared to existing work on metric learning and discriminant
analysis, our learning method focuses more on “far but matching” and “close but non-matching”
training pairs, so that can distinguish look-alike irrelevant parts successfully.
(a) 15 closest SIFT pairs
 (b) 15 closest RDE pairs
Figure 2: (a) When two images of the same scene are captured under considerably different con-
ditions, many irrelevant pairs of local parts are chosen as closest pairs in the local feature space,
which may lead to undesirable results of comparison. (b) In our RDE space, matching pairs are
successfully chosen as closest pairs.
2 Proposed Method
In descriptor learning [1, 3], a projection is obtained from training pairs of matching and non-
matching descriptors in order to map given local descriptors (e.g., SIFT) to a new feature space
where matching descriptors are closer to each other and non-matching descriptors are farther from
each other. Traditional techniques for supervised dimensionality reduction, including linear discrim-
inant analysis (LDA) and local Fisher discriminant analysis (LFDA) [4], can be applied to descriptor
learning after a slight modiﬁcation. For example, linear discriminant embedding (LDE) [1] is come
from LDA with a simple modiﬁcation for handling pairwise training data.
We propose a regularized learning framework in order to further emphasize (1) matching, but far
apart pairs and (2) non-matching, but look-alike pairs, under wide environmental conditions. First,
we divide given training pairs of local descriptors into four subsets, Relevant-Near (Rel-Near),
Relevant-Far (Rel-Far), Irrelevant-Near (Irr-Near), and Irrelevant-Far (Irr-Far). For example, the
“Irr-Near” subset consists of irrelevant (i.e., non-matching), but near pairs. We deﬁne an irrelevant
pair (xi,xj) as “near” ifxi is one of the knearest descriptors1 among all non-matching descriptors
of xj or vice versa. Similarly, a relevant pair (xi,xj) is called “near” if xi is one of knearest de-
scriptors among all matching descriptors of xj. All the other pairs belong to “Irr-Far” or “Rel-Far”.
Then we seek a linear projection T that maximizes the following regularized ratio:
J(T) =
βIN
∑
(i,j)∈PIN
dij(T) +βIF
∑
(i,j)∈PIF
dij(T)
βRN
∑
(i,j)∈PRN
dij(T) +βRF
∑
(i,j)∈PRF
dij(T) , (1)
1In our experiments, setting 1 ≤ k ≤ 10 achieved a reasonable performance improvement.
2
−1 −0.5 0 0.5 1
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
 
 
LDE
LFDA
RDE
(a)
−1 −0.5 0 0.5 1
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
 
 
LDE
LFDA
RDE (b)
Figure 3: Toy examples of projections learned by LDE, LFDA, and our RDE.
0 100 200 300 400 500 600 7000
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
Distance
The number of pairs
 
 
Err (Rel vs Irr) = 15.58%
Err (RFar vs INear) = 29.92%
RelNear
IrrFar
IrrNear
RelFar
(a) SIFT feature space
0 100 200 300 400 500 600 7000
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
Distance
The number of pairs
 
 
Err (Rel vs Irr) = 13.99%
Err (RFar vs INear) = 27.00%
RelNear
IrrFar
IrrNear
RelFar (b) LDE feature space
0 100 200 300 400 500 600 7000
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
Distance
The number of pairs
 
 
Err (Rel vs Irr) = 8.34%
Err (RFar vs INear) = 16.30%
RelNear
IrrFar
IrrNear
RelFar (c) Our RDE feature space
Figure 4: Distribution of Euclidean distance in a given feature space for each subset of pairs. Err
(Rel vs Irr)measures the proportion of overlapping region between {Rel-Near, Rel-Far}and {Irr-
Near, Irr-Far}, while Err (RFar vs INear)measures the overlap between Rel-Far and Irr-Near. In
our RDE space, non-matching pairs are well distinguished from matching pairs.
where dij(T) denotes the squared distance ||T(xi −xj)||2 between two local descriptors xi and xj
in the projected space, and PRN ,PRF ,PIN ,PIF denote the subsets of Rel-Near, Rel-Far, Irr-Near,
and Irr-Far, respectively. Four regularization constantsβRN ,βRF ,βIN ,βIF control the importance
of each subset.
• In LDE, all pairs are equally important, i.e., βRN = βRF = βIN = βIF = 1.
• In LFDA , “near” pairs are more important, i.e.,βRN ≫βRF and βIN ≫βIF .
• In our method, we propose to emphasize Rel-Far (matching but far apart) and Irr-Near
(non-matching but close) pairs, i.e., βRN ≪βRF and βIN ≫βIF .
Fig. 3 shows when and why our method can better distinguish Irr-Near pairs from Rel-Far pairs.
In Fig. 3(a), the global intra-class distribution forms a diagonal, while each local cluster has no
meaningful direction of scattering. Since LFDA focuses on “near” pairs, it cannot capture the true
intra-class scatter well, leading to the undesirable projection. In Fig. 3(b), LDE obtains a projection
that maximizes the inter-class variance, but the shape of the class boundary cannot be considered
well, leading to an overlap between two classes. In this case, focusing more on Irr-Near pairs (i.e.,
the pairs of opposite clusters near the class boundary) can preserve the separability of classes.
Fig. 4 shows the distance distribution of local descriptors, where 20,000 pairs of each subset are
randomly chosen from 500,000 local patches of Flickr images. As shown in Fig. 4(a), Rel-Near
and Irr-Far pairs are already well separated in the SIFT space, but Rel-Far and Irr-Near pairs are
not distinguished well ( ∼30% overlapped) and many Rel-Far pairs lie farther than Irr-Near pairs.
Learning by LDE can achieve only a marginal improvement (Fig. 4(b)). By contrast, our RDE
achieves a signiﬁcant improvement in the separability between matching and non-matching pairs,
especially two challenging subsets, Rel-Far and Irr-Near (Fig. 4(c)). Fig. 1 and 2 also show the
superiority of our method over the existing work.
3
References
[1] G. Hua, M. Brown, and S. Winder, “Discriminant embedding for local image descriptors,” in Proceedings
of the International Conference on Computer Vision (ICCV), 2007, pp. 1–8.
[2] D. G. Lowe, “Object recognition from local scale-invariant features,” in Proceedings of the International
Conference on Computer Vision (ICCV), 1999, pp. 1150–1157.
[3] J. Philbin, M. Isard, J. Sivic, and A. Zisserman, “Descriptor learning for efﬁcient retrieval,” inProceedings
of the European Conference on Computer Vision (ECCV), 2010, pp. 677–691.
[4] M. Sugiyama, “Dimensionality reduction of multimodal labeled data by local Fisher discriminant analysis,”
Journal of Machine Learning Research, vol. 5, pp. 1027–1061, 2007.
4


Peer review:
[Review]:
We sincerely appreciate all the reviewers for their time and comments to this manuscript.
We fully agree that it is really hard to find maningful contributions from this short paper, while we tried our best to emphasize them. As we have noted, the full version of this manuscript is currently under review in an international journal. In order to avoid violating the dual-submission policy of the journal, we could not include most of the details and empirical results - only the main idea and some simple examples could be remained in this workshop track submission.

We promise that all the details omitted in this version will be presented clearly in the workshop, e.g., the choice of the weighting of each split, the training dataset used in our experiments, and conclusive empirical comparisons.
For example, we compared the image retrieval performance for landmark buildings in Oxford (http://www.robots.ox.ac.uk/~vgg/data/oxbuildings/) and Paris (http://www.robots.ox.ac.uk/~vgg/data/parisbuildings/). A nonlinear variant of LFDA implemented using deep belief networks (DBN) and a kernelized version of LDE (KDE) were compared to our method. In terms of the mean average precision (mAP) score, we observed significant improvements using our method (mAP: 0.678 on Oxford / 0.700 on Paris) over raw SIFT (0.611 / 0.649), KDE (0.656 / 0.673), DBN (0.662 / 0.678), under the same number of the learned features and the same size of visual vocabulary.

Thanks to all the reviewers again.