PER-PATCH METRIC LEARNING FOR ROBUST IMAGE MATCHING
Sezer Karaoglu, Ivo Everts, Jan C. van Gemert, and Theo Gevers
Intelligent Systems Lab, Amsterdam, University of Amsterdam, 1098 XH Amsterdam, The Netherlands
ABSTRACT
We propose a patch-specific metric learning method to improve matching performance of local descriptors. Existing
methodologies typically focus on invariance, by completely
considering, or completely disregarding all variations. We
propose a metric learning method that is robust to only a rangeof variations. The ability to choose the level of robustness allows us to fine-tune the trade-off between invariance and discriminative power.
We learn a distance metric for each patch independently
by sampling from a set of relevant image transformations.
These transformations give a-priori knowledge about the behavior of the query patch under the applied transformationin feature space. We learn the robust metric by either fully
generating only the relevant range of transformations, or by anovel direct metric. The matching between query patch anddata is performed with this new metric.
Results on the ALOI dataset show that the proposed
method improves performance of SIFT by 6.22% for geometric and 4.43% for photometric transformations.
1. INTRODUCTION
Viewing and lighting condition changes in real-world scenes
cause substantial variations in image feature representations.
Significant progress has been made in developing image representations that are invariant to transformations such as photometry [1, 2] or geometry [3, 4, 5, 6]. Image representations
invariant to such changes are beneficial for applications suchas object recognition, image retrieval and scene recognition.
A full invariant representation, unfortunately, leads to adecrease in discriminative power [7]. This drawback is due todistinguishing transformations that a full invariant representation cannot capture. For example, under rotational invariancea ”6” is identical to a ”9”, and under shading invariance thetexture of ”grass” turns into ”moss”. Another disadvantage ofinvariant image representations is that they negatively influence stability [8, 9, 10]. This is due to their sensitivity to noise
when the image signal is low or ambiguous. For example, arotational invariant based on the dominant orientation [5] becomes unstable when multiple equally dominant orientations
are present. Illumination invariant representations based on
intensity normalization such as normalized-rgb or hue [2] become unstable for low intensity values.

Fig. 1. 2D PCA projection of SIFT extracted from dataset
samples (blue); 1000 affine transformations of the top-left image patch (red); same-class samples (yellow). The top row is
the original space, the bottom row is after learning the metric.
Current invariant methods are always ”on”. One can either choose to use the invariance, or choose not to use it.
There is no middle-ground. It is not possible to have invariance for only some shading or only slight rotations. Theserigid properties of current invariants play a central role in the
trade-off between invariance and discriminative power. Here,
we propose to replace these binary on/off invariants, by steering the invariance to a limited range of disturbances. Sucha limited degree of invariance is called robustness. For example, in the case of rotation, the proposed method can determine that a ”6” is only invariant up to ±45o of (and thus
robust to) rotation, therefore eliminating the confusion with
”9”.
By allowing a degree of invariance, a single global image
representation cannot be used as it depends on the specificimage content how the limited transformation range will takeeffect, which is illustrated by the ”6” and ”9” example. Therefore, the proposed method is required to achieve robustness
on a per-patch basis. Fig. 1 (top) illustrates that feature distributions after a transformation depend on the patch content,
since even instances within the same class behave differently(red versus yellow). The bottom row of Fig. 1 illustrates theeffect of steerable invariance applied to each patch.
To achieve robustness, we compute a Mahalanobis metricfor each individual patch. In effect, the metric weights thesubset of feature dimensions that require robustness. For this,a relevant subset of transformations is generated and a metric that is specific for only those transformations is learned.
We present two approaches for learning the metric: (i) fulland (ii) direct. The full method generates synthetic image
patches, extracts descriptors for each patch, and obtains robustness through a metric that is learned on these descriptors.
In the direct approach, we generate a transformation map only
once, and use this map to directly estimate the metric from thepatch without explicitly generating any synthetic images.

gle global image representation cannot be used as the effectof transformation essentially depends on the specific image
content. Thus, a patch specific metric is proposed. (iii) we
propose two alternatives to learn per-patch metric: by either
explicitly applying transformations or obtaining directly fromthe patch.

2. RELATED WORK

3. PER-PATCH METRIC LEARNING

Approaches that aim to achieve (full) invariance either use atransformation model based on the laws of physics [1, 2] or amodel of the observed variations [3, 4, 11, 5]. The two disadvantages of invariants, stability and discriminative power, canbe addressed by propagating camera noise parameters [8] orby deriving quasi-invariants [9]. Noise propagation requires
proper noise estimation and the quasi-invariants are incomparable over different images and thus cannot be used for matching.
In contrast to employing pre-determined models, (deep)learning methods learn invariant features from unsupervised
training examples [12, 13, 14]. Such methods do not explicitly model invariance as they attain robustness from training
examples. Therefore, learning methods require large amountsof training data which is hard to obtain. Moreover, learning
approaches do not directly incorporate known physical lawsof the world. In this work, we use a hybrid approach of modeling robustness by learning from synthetically generated geometric and photometric data.
Synthetically generated data can be used to directly create variation in the train and test samples [15, 16, 17]. Other
brute-force methods like ASIFT [18] generate a full range ofaffine transformations for both training and testing images
which are used in an exhaustive matching scheme. Similar
to our work, Simard et al. [19] avoid brute-force approaches
and use synthetically generated images to learn a robust distance metric which is tangent to the manifold that is spannedby the generated transformations. We also learn a robust metric, however, where Simard et al. [19] require pixel values toestimate a manifold, our method estimates a Mahalanobis distance, which is applicable to any feature representation such
as SIFT. To improve discriminability of a local descriptor,
Cai et al [15] also propose to learn a projection matrix fora limited range of affine transformations through generated
data. However, it is important to note that the authors learn a
global projection whereas this paper proposes to learn patch
specific projections. Fig. 1 illustrates that the same transformations applied to even the same class instances has different
effects for different patches. These variations are thus patchdependent and might not reflect the appropriate effect on otherpatches from the same class.
This paper has following contributions: (i) we demonstrate that a full invariant representation leads to a decreasein the discriminative power of a descriptor. Accordingly, we
propose to limit the degree of invariance and augment the discriminativeness of a descriptor. (ii) we demonstrate that a sin-

We first develop a metric that is learned from syntheticallygenerated transformations of photometric and geometric distortions.
Geometric Transformations. Images are subject to geometric distortions introduced by perspective effects caused byview point changes. For small patches, the perspective transformation (x0 , y 0 )T can be approximated by an affine transformation for a given point (x, y)T as 0 
 
xsx cos α −τx sin α txx
y 0  =  τy sin α sy cos α ty  y  ,
(1)
1
0
0
1
1
where s denotes scale, τ represents shearing, α is the rotation angle, and t denotes translation. Sample generation
involves repetitive random selection from appropriate parameter ranges.
Photometric Transformations.
To model photometricchanges, we assume Lambertian reflection. Accordingly,
the color response (I) for the visible spectrum (λ), usinga camera with spectral sensitivity (f ) and an illumination
source with the spectral power distribution (e) can be definedZ
as(2)
I = ~n.~s e(λ)ρ(λ)f (λ)dλ.
λs, n and ρ denote the illumination direction, the surface normal and the surface albedo respectively. To obtain photometric robustness, we generate variations caused by Lambert’sLaw. For the same surface patch the viewpoint and illuminant
spectral power distribution are the same. The color response
can only vary due to changes in illumination direction (i.e. ρ,
f , e and n remain constant). Therefore, the changes in I canbe modeled by illuminating the patch from different positions(See Fig. 2).
The center of the image patches are considered to be at(0, 0, 0) and placed perpendicular to the light source position. Then, the light source position is systematically sampled
within a certain radius. The patches are sufficiently small tobe assumed planar. Hence, surface normals are equal for thepatch under consideration. Thus, the light source directionis the only factor determining the effect of the photometricalchanges.
3.1. Metric Learning
A Mahalanobis distance metric between image features xi
and xj is parameterized by the matrix M ,

𝑳𝟏

𝑳𝟏

𝑳𝟐

𝒑

𝒑

𝑳𝟐
𝒑

Fig. 2. Illustration of photometric changes. The color response of point p changes due the angle between the incident
light (L) and surface normal (yellow arrow) at the point p.
According to Lambertian law, if this angle becomes smaller,
the color response becomes brighter.
qdM (xi , xj ) = (xi − xj )T M (xi − xj ),(3)

where M is a positive semi-definite matrix. A straightforward approach to compute M is to use M = C −1 where C isthe empirical feature covariance of the training data [20, 21].
The rationale behind using the inverse covariance as a metricis that a high variance in a feature dimension means that thisdimension is not very stable. The most informative dimensions are those that have low variances.
For large-scale matching it is convenient to use fast indexing techniques such as trees [22]. Such techniques typicallywork with the Euclidean distance. To this end, the metric canbe rewritten to(xi − xj )T W T W (xi − xj ) = ||W xi − W xj ||2 ,(4)

1

where W = M − 2 . This effectively scales the feature
space with an affine transformation W to allow the Euclidean
distance to be used for metric M .
Robustness is obtained by generating a limited range oftransformations for a single patch. From these generated samples C is estimated, which is then used to compute M .
We coin this simple method for metric learning the full
approach, since it needs to fully generate a large number oftransformations for a patch in order to extract the image features and estimate the covariance matrix.
3.2. Direct Metric Estimation
Instead of using the brute-force approach of computing C
by explicitly generating patches and extracting features fromthem, we propose a direct approach to estimate the metricper-patch. In the direct approach, the covariance is estimatedfrom a single patch.
Let x be an image feature vector as a column, with N dimensions. For clarity, we start with pixel values to explain the
direct metric estimation, i.e. x is a vector of pixels. Later weshow our method readily applies to other descriptors.
Pixel Values. The direct metric is a combination of two terms,
a transformation probability DT that a pixel moves to a different position after transformation T , and the patch-specificcovariance term V of the feature values.

Let DT be a symmetric matrix of size N xN , containing
the probabilities PT (i|j) of a pixel at position j affecting theposition of pixel i under a transformation T . Note that thistransformation is independent of the actual feature values.
Matrix DT represents the per-pixel transformation probability
which is determined by simulating a large set of transformations and comparing the transformed patch with the groundtruth location obtained through the homography in eq 1.
The matrix V of size N xN is the variance matrix with elements σ(i, j) representing the covariance of pixel values at
position i with respect to position j. To compute the covariance matrix, we need the expected average weighted pixel
value xi at position i after the transformation T , which is
given by:2

E[xT (i)] =NX

PT (i|j)x(j) = DT xT ,

(5)

j=0

where xT represents the pixel vector x after the transformation T . The expected value of the transformed image xTis denoted by E[xT (i)] and represents the average image of
all transformations that are present in DT . The covarianceσ(i, j) after transformation T is thenσ(i, j) = E E[xT (i)] − xT (i) E[xT (j)] − xT (j) . (6)Note that in the transformation of xT (i) and xT (j) it is allowed for pixels to move independently to other pixels. Eq 6
can be rewritten in matrix form to obtain V directly
WV = [[DT > 0]] • DT x1T − (xT 1)T ,
(7)
1
(8)
V = 2 DT • WV WVT ,N
where 1 is a column vector of all ones, • denotes elementwise multiplication and [[·]] indicate Iverson brackets which
resolves a (matrix) element to 1 when the argument is true,and 0 otherwise. The metric is computed by M = V −1 , and1
the transformation by W = V − 2 .
SIFT. For other descriptors, the DT matrix of transformation
probabilities can be reused and is not required to be recomputed. The V matrix, however, has to be adapted to the specific form of the descriptor. In the case of SIFT, DT is converted to DTsift of size 128x128. In contrast to generating all
possible sift values, DTsift has to be computed once only.
The 128 dimensions of SIFT comprise of a 4x4 spatial
grid and 8 angular bins (4x4x8). We use the pixel-based transformation probabilities DT to directly calculate the probability PTsift (i|j) for spatial SIFT bins i and j with2

PTSIFT (i|j) =NX[[f (x) = i]][[f (y) = j]]PT (x|y),

(9)

y=0

where the function f (x) maps the pixel at location x to thecorrect SIFT-bin i. For the angular transformation probabilities, we assume independence with the spatial bins. The unit

circle is sampled with 360 vectors and transformations are applied to these vectors. Since the original orientation is known,
this results in counting how often a vector switches bins after
the transformations. The joint 128x128 matrix DTsift is calculated by multiplying the angular probabilities with the spatial
probabilities.
4. EXPERIMENTS
Dataset and Implementation Details. The full and direct
metric methods are evaluated on the ALOI dataset [23] for
SIFT descriptor robustness against geometric and photometric distortions. The ALOI dataset contains 1000 objects under varying imaging conditions. We use variations due tocamera viewpoint and illumination direction as geometric andphotometric distortions respectively. To annotate matchingpairs, the same procedure is followed as in [24]. In total 8300
matching pairs are extracted of which 200 are used for validation. Classification is performed by feature matching in a
1-NN classification scheme.
4.1. Geometric Robustness
First, we evaluate per-patch metric learning under geometric distortions. The performance of the proposed methods iscompared against the original SIFT and other methods.
The optimal parameter ranges are obtained on the validation set. Parameters are repetitively sampled (1500 times)
from various ranges to either generate and apply geometrictransformations in the full approach or to estimate the transformation probabilities PT (i|j) in the direct approach. A
joint optimization of parameters on the validation set yields
a translation in [-2:2] and shearing in [-.1:.1] for the SIFT descriptors. Scale and orientation do not affect the performanceas the positional difference between viewpoints does not yieldlarge scale and orientation variations.
The results in Table 1 show that the proposed full and direct methods have a significant improvement of 6.57% and6.22% over the SIFT performance respectively. The significance is validated by t-test a (p < 0.001). The substantial
performance increase is due to the fact that viewpoint variations degrade the SIFT performance for matching. Considering full-rotation invariance for SIFT leads to a dramatic performance loss as the most discriminative information is ignored and due to the visual complexity it is harder to estimate
a dominant gradient orientation.
Additionally, we evaluate raw pixels and tangent distance(T D) [19] on this set. We obtain a classification rate of
16.54% and 23.47% respectively. As discussed in Section 2,
Simard et al. invoke prior information by generating small
global transformations. The performance improvement overraw pixel values supports our idea of exploiting prior information for steering the invariance. However, as expected,
the raw pixel matching performance is far beyond the SIFT
performance which makes T D less applicable when it isnecessary to use features except raw pixel values.

SIFT+Rot. Inv.

Proposed full

Proposed direct

54.85%

13.86%

61.42%

61.07%

Table 1. Matching performance on geometric distortions.
Left to right: original SIFT descriptor, full-rotation invariant
SIFT descriptor, proposed full(synthetic) and direct methods.
Note that full-rotation invariance is unstable whereas limited
range of invariance is stable.
4.2. Photometric Robustness
We evaluate the proposed full and direct metric methods forphotometric robustness. The full method operates by generating synthetic samples as explained in Photometric transformations. The results are shown in Table 2. The proposed
full method significantly outperforms the SIFT performance(t-test with p < 0.001). Moreover, the direct method does notrely on synthetic photometric data generation and it outperforms the SIFT as well. Thus, the direct approach, which isdeveloped for achieving robustness against geometric transformations, is also applicable in the context of photometricvariations.
SIFT

Proposed full

Proposed direct

73.4%

77.86%

76.88%

Table 2. Matching performance on photometric distortions.
Note that both methods perform similar, where ”direct” ismuch faster.

5. CONCLUSION
In this paper, we propose a generic patch-specific robust
metric learning method to improve matching performance of
local descriptors. We show that a full invariant representation
leads to a decrease in discriminative power of descriptors.
Therefore, we propose a per-patch metric learning methodthat is invariant to only a range of variations. We propose
to learn a patch specific a Mahalanobis metric. Two approaches for learning the metric are presented: (i) full and(ii) direct. The proposed approaches are validated on ALOI
dataset for two different image transformations, namely, geometric and photometric. It has been shown that the proposed
approaches outperform the original SIFT descriptor matching
performance.

Acknowledgment
This research was supported by the Dutch national program
COMMIT.

6. REFERENCES[1] J. Geusebroek, R. van den Boomgaard, A. Smeulders,and H. Geerts, “Color invariance,” TPAMI, 2001.
[2] T. Gevers and W. M. A. Smeulders, “Color based object
recognition,” Pattern recognition, 1999.
[3] A. Baumberg, “Reliable feature matching across widely
separated views,” in CVPR, 2000.
[4] T. Lindeberg, “Feature detection with automatic scaleselection,” IJCV, 1998.
[5] K. Mikolajczyk and C. Schmid, “Scale & affine invariant interest point detectors,” IJCV, 2004.
[6] L. Zhang, Z. Lei, Z. Guo, and D. Zhang, “Monogeniclbp: A new approach for rotation invariant texture classification.,” in ICIP, 2010.
[7] M. Varma and D. Ray, “Learning the discriminative
power-invariance trade-off,” in ICCV, 2007.
[8] T. Gevers and H. Stokman, “Robust histogram construction from color invariants for object recognition,”
TPAMI, 2004.
[9] J. van de Weijer, T. Gevers, and J. M. Geusebroek,“Edge and corner detection by photometric quasiinvariants,” TPAMI, 2005.
[10] I. Everts, J. C. van Gemert, T. E. J. Mensink, and T. Gevers, “Robustifying descriptor instability using fisher
vectors,” TIP, 2014.
[11] D. G. Lowe, “Distinctive image features from scaleinvariant keypoints,” IJCV, 2004.
[12] K. Kavukcuoglu, M. Ranzato, R. Fergus, and Y. LeCun,“Learning invariant features through topographic filter
maps,” in CVPR, 2009.
[13] M. Ranzato and G. E. Hinton, “Modeling pixel meansand covariances using factorized third-order boltzmann
machines,” in CVPR, 2010.
[14] U. Schmidt and S. Roth, “Learning rotation-aware features: From invariant priors to equivariant descriptors,”in CVPR, 2012.
[15] H. Cai, K. Mikolajczyk, and J. Matas, “Learning linear
discriminant projections for dimensionality reduction ofimage descriptors,” TPAMI, 2011.
[16] D. Gavrila and J. Giebel, “Virtual sample generation fortemplate-based shape matching,” in CVPR, 2001.
[17] Y. LeCun, F. J. Huang, and L. Bottou, “Learning methods for generic object recognition with invariance topose and lighting,” in CVPR, 2004.

[18] J. M. Morel and G. Yu, “Asift: A new framework forfully affine invariant image comparison,” SIAM J. Imaging Sciences, 2009.
[19] P. Simard, Y. LeCun, J. S. Denker, and Victorri
B., “Transformation invariance in pattern recognitiontangent distance and tangent propagation,” in Neural
Networks: Tricks of the Trade, 1996.
[20] A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall,“Learning a mahalanobis metric from equivalence constraints,” JMLR, 2005.
[21] M. Kostinger, M. Hirzer, P. Wohlhart, P. M. Roth, and
H. Bischof, “Large scale metric learning from equivalence constraints,” in CVPR, 2012.
[22] K. Mikolajczyk and J. Matas, “Improving descriptors
for fast tree matching by optimal linear projection,” in
ICCV, 2007.
[23] J. Geusebroek, G. Burghouts, and A. Smeulders, “Theamsterdam library of object images,” IJCV, 2005.
[24] I. Everts, J. C. van Gemert, and T. Gevers, “Per-patch
descriptor selection using surface and scene properties,”
in ECCV, 2012.