Deformation and Illumination Invariant Feature Point Descriptor
Francesc Moreno-Noguer
Institut de Robòtica i Informàtica Industrial (CSIC-UPC)
08028, Barcelona, Spainamong the spatial layout of all matches [8, 9, 11, 21, 25].
Yet, none of these approaches explicitly builds a descriptor
that goes beyond affine transformations. An interesting exception is [13], that proposes embedding the image as a 3D
surface and using a Geodesic Intensity Histogram (GIH) asa feature point descriptor. However, while this approach isrobust to non-rigid deformations, its performance drops under light changes. This is because the GIH considers deformations as one-to-one mappings where image pixels onlychange their position but not their intensities.
To overcome the inherent limitation of a metric that uses
GIH distances, we propose a novel descriptor based on theHeat Kernel Signature (HKS) recently introduced for nonrigid 3D shape recognition [20, 23], and which besides invariance to deformation, it has been demonstrated to be invariant to global isotropic scalings [5]. This is particularlyinteresting in our context of images embedded on 3D surfaces, because illumination changes produce variations on
the intensity dimension that can be seen as local anisotropic
scalings, for which [5] still shows a good resilience.
Our main contribution is thus in using the tools of diffusion geometry to build a descriptor for 2D image patches invariant to non-rigid deformations and photometric changes.
More specifically, we consider an intensity image I as a surface in the (x, y, βI) space, where (x, y) are the spatial coordinates and β is a parameter which is set to an arbitrarily
large value to ensure the descriptor preserves edge information. Drawing motivation from the HKS [5, 23], we thendescribe each feature point in terms of the heat it dissipates
onto its neighborhood over time. To increase robustness
against 2D and intensity noise, we consider the heat diffusion process not only on the point of interest, but also on the
pixels of its neighborhood, accordingly weighed by a Gaussian kernel. As shown in Fig. 1, the resulting descriptor(which we call DaLI, for Deformation and Light Invariant)outperforms state-of-the-art descriptors in matching points
of interest between images that have undergone non-rigid
deformations and photometric changes.

Abstract
Recent advances in 3D shape recognition have shownthat kernels based on diffusion geometry can be effectively
used to describe local features of deforming surfaces. In
this paper, we introduce a new framework that allows using
these kernels on 2D local patches, yielding a novel featurepoint descriptor that is both invariant to non-rigid image
deformations and illumination changes.
In order to build the descriptor, 2D image patches areembedded as 3D surfaces, by multiplying the intensity levelby an arbitrarily large and constant weight that favors
anisotropic diffusion and retains the gradient magnitude
information. Patches are then described in terms of aheat kernel signature, which is made invariant to intensitychanges, rotation and scaling. The resulting feature point
descriptor is proven to be significantly more discriminative
than state of the art ones, even those which are specificallydesigned for describing non-rigid image deformations.

1. Introduction
Building invariant region descriptors is a major topic ofresearch in computer vision with a wide range of applications in areas of object recognition and 3D reconstruction. Over the last decade, great success has been achieved
in designing descriptors invariant to certain types of geometric and photometric transformations. For instance, theSIFT [16] descriptor and many of its variants [1, 10, 17, 24]
have been proven invariant to affine deformations of both
spatial and intensity domains. In addition, affine deformations can effectively approximate, at least on a local
scale, other image transformations including perspective
and viewpoint changes. However, this approximation is
no longer valid for general deformations as those occurring
when viewing an object that deforms non-rigidly [26].
In order to match points of interest under non-rigid image deformations, recent approaches propose optimizing
complex objective functions that ensure global consistence

2. Related Work

This work has been partially funded by the Spanish Ministry of Science and Innovation under projects DPI2008-06022 and Consolider Ingenio 2010 CSD2007-00018; and by the EU project GARNICS FP7-247947.

The SIFT descriptor [16] has become the main reference
among keypoint descriptors, showing great success in cap1

SIFT

DAISY

GIH

DaLI

Deform. + Light

Deformation

Input Images

Figure 1. Comparing DaLI against other descriptors. Top: Matching under Non-Rigid Deormations. We compare DaLI, against
SIFT [16], DAISY [24] and GIH [13]. Colored circles indicate the match has been correctly found among the first n top candidates,
where n ≤ 10 is parameterized by the legend on the right. A feature is considered as mismatched when n > 10 and we indicate this with across. Note that GIH, which is specifically designed for handling non-rigid deformations, yields very good results, similar to our approach.
Bottom: Matching under Non-Rigid Deformations and Light Changes. Under this situation, only our approach remains robust.

turing local affine deformations including scaling, rotationand certain lighting changes. Since it is relatively slow tocompute, most of the subsequent works have focused in developing faster descriptors [1, 6, 10, 17, 24]. However, little
effort has been dedicated in building descriptors robust to
more general deformations.
The limitations of the affine-invariant descriptors whensolving correspondences under non-rigid deformations arecompensated by enforcing global consistency, both spatial
and photometric, among all the features [2, 3, 8, 9, 11, 21,25]. Thus, all these methods do not handle the non-rigid
nature of the problem, and rely on solving complex optimization functions for establishing matches.
An alternative approach, is to directly build a deformation invariant descriptor. With that purpose, recent approaches in two-dimensional shape analysis have proposedusing different types of intrinsic geometry. For example, [4, 14] define metrics based on the inner-distance, and[15] proposes using geodesic distances. However, all thesemethods require the shapes to be segmented out and represented by binary images, which is difficult to hold in practice. In [13], it was shown that geodesic distances, in combination with an appropriate 3D embedding of the image,were adequate to achieve deformation invariance in intensity images. Yet, this method assumes that pixels onlychange its position and not its intensity and, as shown in
Fig. 1, becomes unreliable under illumination changes.
Motivated by [13], we represent the images as 2D surfaces embedded in the 3D space. In fact, this is quite an
old idea, although it has been mostly employed for low
level vision tasks such as image denoising [22, 29] and segmentation [28]. The fundamental difference between our
approach and [13] is that we then describe each featurepoint on the embedded surface considering the heat diffusion over time [5, 23] instead of using a Geodesic Intensity

Histogram. As we will show in the results section this yields
substantially improved robustness, especially to lightingchanges. Again, the heat diffusion theory has been used inseveral early approaches for 3D shape analysis [12, 19, 20],
but to the best of our knowledge, it has never been used fordescribing image patches in intensity images.

3. Deformation and Light Invariant Descriptor
Our approach is inspired by current methods [5, 23] thatsuggest using the diffusion geometry for 3D shape recognition. In this section we show how this theory may be
adapted for describing 2D local patches of images that undergo non-rigid deformations and photometric changes.

3.1. Invariance to Non-Rigid Deformations
Let us assume we want to describe a 2D image patch P ,of size S × S and centered on a point of interest p. In
order to apply the diffusion geometry theory on intensity
patches we regard them as 2D surfaces embedded in 3D
space (Fig. 2 Top-left). More formally, let f : P → M
be the mapping of the patch P to a 3D Riemannian manifold M . We explicitly define this mapping by:
f : x → (x, y, βP (x)) ∀x ∈ P ,(1)

where P (x) is the pixel intensity at x = (x, y) , and β is aparameter that, as we will discuss later, controls the amountof gradient magnitude preserved in the descriptor.
Several recent methods [12, 19, 20, 23] have used theheat diffusion geometry for capturing the local properties of
3D surfaces and performing shape recognition. Along theselines, we describe each patch P based on the heat diffusion
equation over the manifold M :∂u(x, t) = 0 ,
(2)
M +
∂t
2

DaLI Descriptor Slices at Frequencies w = {0, 2, 4, 6}

Image Embedding

y1

x

1

Descriptor for single pixels
xSI−HKS

6

1

y1
4

x

2

y2

0
0

z2
x

2

y

2

2

z2
5

10

Freq(w)

15

20

Figure 2. DaLI descriptor. Top Left: Our central idea is to embed image patches on 3D surfaces and describe them based on heat diffusion
processes. We represent the heat diffusion as a stack of images in the frequency domain. Right: Various slices of our descriptor for
two different patches. Bottom Left: Value of the descriptor for the pixels marked by color circles in the images on the right. Note that
corresponding pixels have very similar signatures. However, the signature may change from one pixel to its immediate neighbor. For
instance, z2 is at one pixel distance from x2 , but their signature is rather different. As a consequence, using the signature of a single
point as a descriptor is prone to be very sensitive to 2D noise in the feature detection process. We address this issue by simultaneously
considering the signature of all the pixels within the patch, weighted by a Gaussian function of the distance to the center of the patch.

where M is the Laplace-Beltrami operator, a generalization of the Laplacian to non-Euclidean spaces. The solution
k(x, y, t) of the heat equation is called the heat kernel, andrepresents the amount of heat that is diffused between points
x and y at time t, considering a unit heat source at x at time
t = 0. For a compact manifold M , the heat kernel can be
expressed by following spectral expansion [7, 19]:k(x, y, t) =∞e−λi t φi (x)φi (y) ,where G(x; p, σ) is a 2D Gaussian function with mean p
and standard deviation σ, evaluated at x.
The price we pay for achieving increased robustness
to 2D noise is an additional complexity of the descriptor.
That is, if HKS(p, t) is a function defined on the temporal domain R+ , the new descriptor DI(p, t) is defined on
S×S×R+ , the product of the spatial and temporal domains.
However, note that for our purposes this is still feasible, because we do not need to compute a descriptor for every pixelof the image, but just for a few hundreds of points of interest. Furthermore, as we will next discuss, the descriptor
may be highly compacted if we represent it in frequency
domain instead of time domain.

(3)

i=0

where {λi } and {φi } are the eigenvalues and eigenvectorsof M . Based on this expansion, [23] proposes describing
a point p on M using the Heat Kernel Signature
HKS(p, t) = k(p, p, t) =

∞


e

−λi t

φ2i (p) ,3.2. Invariance to Illumination Changes
An intrinsic limitation of the descriptor introduced in
Eq. 5 is that it is not illumination invariant. This is becauselight changes, scale the manifold M along the intensity axis,and HKS is sensitive to scaling. Indeed, it can be shown that
an isotropic scaling of the manifold M by a factor α, scales
the eigenvectors and eigenvalues of Eq. 3 by factors 1/α
and 1/α2 , respectively [19]. The HKS of a point αp ∈ αM
can then be written as

(4)

i=0

which is shown to be isometrically-invariant, and adequate
for capturing both the local properties of the shape around p(when t → 0) and the global structure of M (when t → ∞).
However, while on smooth surfaces the HKS of neighboring points are expected to be very similar, when dealing
with the irregular shapes that may result from embedding
image patches, the heat kernel turns to be highly unstable
along the spatial domain (Fig. 2 Bottom-left). This makes
the HKS particulary sensitive to noise in the 2D coordinatesof the keypoints. To handle this situation, we build the descriptor of a point p by assembling the HKS of all points x
within the patch P , properly weighted by a Gaussian function of the distance to the center of the patch. Thus, wedefine the following Deformation Invariant (DI) descriptor:
DI(p, t) = [HKS(x, t) · G(x; p, σ)]∀x∈P ,∞2
λi φ (p)1te− α2 t i 2 = 2 HKS(p, 2 ) , (6)HKS(αp, t)=
α
α
α
i=0

which is an amplitude and time scaled version of the original HKS.
Nonetheless, under isotropic scalings, several alternatives have been proposed to remove the dependence of HKS
to the scale parameter α. For instance, [19] suggests normalizing the eigenvalues in Eq. 3. [5] proposes applying
three consecutive transformations on the HKS. First, the

(5)
3

100

Descriptor Change(%)

90

Def11

DaLI
DI

Def10
Def9

80

Def8

70

Figure 4. Left: Image patch. Center: Representation of the patch
as a triangular mesh. For clarity of presentation we only depict
the (x, y) dimension of the mesh. Note that besides the vertices
placed on the center of the pixels (black circles) we have introduced additional intra-pixel vertices (white circles), that provide
finer heat diffusion results and higher tolerance to in-plane rotations. Right: Definition of the angles used to compute the discrete
Laplace-Beltrami operator.

Def7

60

Def6
50
Def5
40

Def4

30

Def3

20

Def2

10
0
1.0

Def1
0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0.01

Def0

Intensity Gain

Figure 3. Invariance of the DaLI and DI descriptors to non-rigid
deformations and illumination changes. Top and Left Images:
Different degrees of deformation and light changes applied on
the top left reference patch P0 . Deformations are applied according to a function Def(·) ∈ {Def0, . . . , Def11}, where Def11
corresponds to the maximal deformation. Light changes are produced by scaling the intensity of P0 by a gain g ∈ [0, 1]. Bottom Graph: Given a deformation Def(·) and a gain factor g,
we compute the percentage of change of the DI descriptor by
DI(P0 ) − DI(Def(gP0 ))/DI(P0 ). The percentage of change
for DaLI is computed in a similar way. Observe that the DaLI ismuch less sensitive than DI, particularly to lighting changes.

mation and light changes. Note that DaLI, in contrast DI,
remains almost invariant to light changes, and it also showsa better performance under deformations. In the results section, we will show that this invariance is also accompanied
by a high discriminability, yielding significantly better results in keypoint matching than existing approaches.

3.3. Handling in-Plane Rotation and Scaling
Although DaLI tolerates certain amounts of in-plane rotation and scaling, it is not designed for these purposes.
This is because with the aim of increasing robustness to 2D
noise, we built the descriptor using all the pixels within thepatch, and their spatial relations have been retained. Thus,
if the patch is rotated or scaled, so will be the descriptor.
In order to handle this situation, during the matching process we will consider several rotated and scaled copies ofthe descriptors. Therefore, given DaLI(p1 ) and DaLI(p2 )we will compare them based on the following metrictime-dimension is logarithmically sampled, which turns thetime scaling into a time-shift, that is, the right-hand sideof Eq. 6 begets α−2 HKS(p, −2 log α + log t). Second,
the amplitude scaling factor is removed by taking the logarithm and a derivative w.r.t. log t. The Heat kernel then∂becomes ∂ log
t HKS(p, −2 log α + log t). The time-shiftterm −2 log α is finally removed using the magnitude of
the Fourier transform, which yields SI-HKS(p, w), a scale
invariant version of the original HKS in the frequency domain. In addition, since most of the signal information isconcentrated in the low-frequency components, the complexity of the descriptor may be highly reduced comparedto that of the HKS(p, t).
Another advantage of the SI-HKS signature is that although it is specifically designed to remove the dependenceof the HKS to isotropic scalings, it is quite resilient toanisotropic transformations, such as those produced by intensity changes, that only affect the intensity dimension of
the manifold M . Thus, we will use this signature to define
our Deformation and Light Invariant (DaLI) descriptor1 :DaLI(p, w) = [SI-HKS(x, w) · G(x; p, σ)]∀x∈P .

d(p1 , p2 ) = arg min Tθi ,sj (DaLI(p1 )) − DaLI(p2 ) (8){θi ,sj }where · denotes the L2 norm and Tθi ,sj (DaLI(p)) rotatesand scales DaLI(p) by an angle θi and a scale parameter sj ,respectively. These parameters are chosen among a discrete
set of values θ and s.

3.4. Implementation Details
We next describe a number of important details to beconsidered for the implementation of the DaLI descriptor.
Geometry of the embedding
For the numerical computation of the heat diffusion, it isnecessary to discretize the problem. Thus, the manifold
M on which the image patch is embedded is represented
by a triangulated mesh. Since it is known that the way
the heat diffusion behaves depends on the geometry of thismesh [27], we examined different triangulations: structured
with either 6 or 8 neighbors per vertex, and unstructured.
Fig. 4 shows the representation we use for all the experiments. Although it requires introducing additional vertices(7)

Fig. 2 shows several slices of the DaLI descriptor at different frequencies for a patch and a deformed version of it.
As said above, observe that most of the signal is concentrated on the low frequency components. In Fig. 3 we compare the sensitivity of the DI and DaLI descriptors to defor1 In the rest of the paper we will indistinctly use DaLI(p, w) ≡DaLI(p) ≡ DaLI(P ).

4

w=2

w=4

w=6

w=8

β = 1000

β = 100

β = 10

w=0

Figure 5. Preserving edge information. Larger values of the parameter β in Eq. 1 allow the descriptor to retain edge information. Each row depicts the DaLI descriptor at frequencies w =0, 2, 4, 6, 8 for a different value of β.

Figure 6. DaLI performance for different values of the parameters S, β, σ and wmax . We compute and average the matching rate for the two pairs of images shown in Fig. 1 usingS ∈ {10, 20, 40, 60, 80} pixels, β ∈ {10, 102 , 103 , 2×103 , 104 },S S S S, 8 , 4 , 2 , S} and wmax ∈ {5, 10, 20, 30}. The graphσ ∈ { 16
depicts the results of this 4D parameter exploration, where thecolor of each square represents the percentage of mismatchedpoints for a specific combination of the parameters.

between the pixels, its symmetry with respect to the x and y
directions provides robustness to small amounts of rotation,and more uniform diffusions than other configurations.
Another important variable of our design is the magnitude of the parameter β in Eq. 1, that controls the importance of the intensity coordinate with respect to the (x, y)
coordinates. In particular, as shown in Fig. 5, large valuesof β allow our descriptor to preserve edge information. Thisis a remarkable feature of the DaLI descriptor, because besides being deformation and illumination invariant, edge information is useful to discriminate among different patches.

4.1. Choosing Descriptor’s Parameters
Before doing the comparison we will take a closer lookat the parameters that control the performance of our descriptor, namely the size S of the patch, the magnitude β ofthe embedding, the degree σ of smoothing within the patch,and the dimensionality wmax of the descriptor in the frequency domain. In order to find their optimal values, weused the images shown in Fig. 1, and computed mismatch
rates for a wide range of values for each of the parameters.
The results of this parameter sweeping experiment are
shown in Fig. 6. It can be seen that the most influential
parameters are the size of the patch and the magnitude ofthe embedding. In particular, the best matching results are
obtained for 40 ≥ S ≥ 60 and 1000 ≥ β ≥ 2000. Notethat these levels of β, ensure that the image gradient is retained by the descriptor. In fact, this was already expected,
as the gradient is an important clue for recognition. On
the other hand, the influence of the smoothing parameterσ and especially of the number of components necessaryis rather limited. Yet, Fig. 6 still shows some pattern forthese parameters, such that the best results are obtained forSS
8 ≥ σ ≥ 4 and 10 ≥ wmax ≥ 30. Based on this analysis,in all the experiments we report in the next section we set
S = 60, β = 2000, σ = S4 and wmax = 20. In addition,
by setting the rotation and scaling parameters of Eq. 8 to
φ = {−20, 10, 0, 10, 20} and s = {0.8, 1, 1.2}, we allow
descriptor rotations of 40 degrees and scalings up to 20%.

Discretization of the Laplace-Beltrami operator
In order to approximate the Laplace-Beltrami eigenfunctions on the triangular mesh we use the cotangent scheme
described in [18]. We next detail the main steps.
Let {p1 , . . . , pnv } be the vertices of a triangular mesh,associated to an image patch embedded on a 3D manifold.
We approximate the discrete Laplacian by a nv × nv matrix
L = A−1 M where A is a diagonal matrix in which Aii
is proportional to the area of all triangles sharing the vertex
pi . M is a sparse matrix computed by:⎧ 
if i = j⎨k mij
if pi and pj are adjacent
−mij
Mij =
(9)
⎩
0
otherwise+−+−+ cot γij
, and γij
and γij
are the two
where mij = cot γij
opposite angles depicted in Fig.4-Right. The eigenvectors
and eigenvalues of the discrete Laplace-Beltrami operator
may then be computed from the solution of the generalized
eigenproblem MΦ = ΛAΦ, where Λ is a diagonal matrix, in which the eigenvalues {λi } and the columns of Φ
correspond to the eigenvectors {φi } in Eq. 3.

4. Experimental Results

4.2. Comparison with Other Approaches

In this section we compare DaLI against other descriptors for matching points of interest in images that have undergone non-rigid deformations and illumination changes.

We compare the performance of our descriptor to thatof the SIFT [16], DAISY [24] and GIH [13]. The first5Real Deformations

Light Changes

Synthetic Deformations

Figure 7. Left: Sample images from the test set used for comparison. The dataset includes both synthetic and real deformations, andconsiders different situations and levels of complexity, from the sharp deformations of a piece of cloth under wind to the smooth distortions
produced when an object is reflected on the water. In this case, we manually segmented the area of the image belonging to the object fromits reflection and performed matching between these two regions (Top-right). For the synthetic deformations we made sure to produce
highly non-linear transformations, in order to assess the robustness of the descriptors to non-affine deformations. Right: For evaluating
the method to light changes, the intensity of the images was non-linearly transformed as a sinusoidal function of increasing amplitude. In
the following we denote them as Light Condition #i where i ∈ {0, 1, 2, 3, 4}. The case i = 0 implies no light change.

two, are representative examples of local region descriptors designed for robustness to affine deformations and certain lighting changes. The GIH, instead, is specificallydesigned to handle non-rigid image deformations, but as
pointed previously, it assumes these deformations are theresult of changing the position of the pixels within the image, but not their intensity. This makes GIH sensitive tolight changes. In order to address this issue, [13] proposes
introducing a scale parameter and compute the GIH descriptor for different magnitudes of the intensity domain. Whensmall light changes are expected this parameter is assumed
to change within the interval [0.95, 1.05]. Since we want
to deal with relatively large illumination changes, we also
consider the case that this parameter changes within the interval [0.25, 1.75]. The GIHs computed in each case will bedenoted by GIH[0.95, 1.05] and GIH[0.25, 1.75].

tion and photometric changes. Fig. 7 shows a few samples.
Given an image pair, we then compute the recognition
rate of each descriptor as follows: (1) Using the SIFT detector, we pick 100≥N ≥200 points of interest in the first image, and estimate their ground truth position in the second
image. (2) We then compute the descriptor for all keypoints
in the two images. (3) Based on the descriptor-specific metrics, we estimate the n top matches for each keypoint in thefirst image, and compute the detection rate as
Detection Rate(n) = 100 · Nc (n)/N ,(10)

where Nc (n) is the number of keypoints from the first image, that have the correct match among the top n candidates.
Fig. 8-Top shows the detection rate for the synthetic
dataset. Note that when no light changes are considered,
the GIH[0.95, 1.05] yields almost identical results as ourapproach. However, its performance rapidly drops whenphotometric changes are introduced. In fact, even the
GIH[0.25, 1.75] does not provide satisfactory results, showing that increasing the representation capabilities of the
GIH is not necessarily correlated with a higher discrimination power. DaLI also consistently outperforms SIFT and
DAISY, which are not specifically designed to tackle non-For evaluating the descriptors, we acquired a dataset of
non-rigidly deformed pairs of images, of 640 × 480 pixels,
containing 10 real and 11 synthetic deformations. In addition, for each pair of images, the intensity of one of them
was progressively modified (in 5 steps) in order to simulate
photometric variations. As a result, the whole database ismade of 105 image pairs under different levels of deforma6

Synthetic Deformations

60
40
20
0

2

4

n

6

SIFT
DAISY
GIH[0.25,1.75]
GIH[0.95,1.05]
DaLI
8
10

80
60
40
20
0

Light Conditions #3

2

4

n

6

SIFT
DAISY
GIH[0.25,1.75]
GIH[0.95,1.05]
DaLI
8
10

100

80
60
40
20
0

2

4

n

6

SIFT
DAISY
GIH[0.25,1.75]
GIH[0.95,1.05]
DaLI
8
10

80
60
40
20
0

Light Conditions #4
100

2

4

n

6

SIFT
DAISY
GIH[0.25,1.75]
GIH[0.95,1.05]
DaLI
8
10

Mean Detect. Rate (%)

80

Light Conditions #2
100

Mean Detect. Rate (%)

100

Mean Detect. Rate (%)

Mean Detect. Rate (%)

100

Light Conditions #1
Mean Detect. Rate (%)

Light Conditions #0

80
60
40
20
0

2

4

n

6

SIFT
DAISY
GIH[0.25,1.75]
GIH[0.95,1.05]
DaLI
8
10

Real Deformations

60
40
20
0

2

4

n

6

SIFT
DAISY
GIH[0.25,1.75]
GIH[0.95,1.05]
DaLI
8
10

80
60
40
20
0

Light Conditions #3

2

4

n

6

SIFT
DAISY
GIH[0.25,1.75]
GIH[0.95,1.05]
DaLI
8
10

100

80
60
40
20
0

2

4

n

6

SIFT
DAISY
GIH[0.25,1.75]
GIH[0.95,1.05]
DaLI
8
10

80
60
40
20
0

Light Conditions #4
100

2

4

n

6

SIFT
DAISY
GIH[0.25,1.75]
GIH[0.95,1.05]
DaLI
8
10

Mean Detect. Rate (%)

80

Light Conditions #2
100

Mean Detect. Rate (%)

100

Mean Detect. Rate (%)

Mean Detect. Rate (%)

100

Light Conditions #1
Mean Detect. Rate (%)

Light Conditions #0

80
60

SIFT
DAISY
GIH[0.25,1.75]
GIH[0.95,1.05]
DaLI

40
20
0

2

4

n

6

8

10

Figure 8. Mean detection rate on the synthetic and real deformation data sets, and for increasing amounts of light change.
Small Deformations

linear deformations as those we evaluate in the synthetic
experiments.
Under real deformations (Fig. 8-Bottom), the DAISY
and GIH approaches change their roles. From one hand,when no light change is considered, DAISY performs almost equally as our approach. This is because most of
the deformations of our real dataset can be locally approximated by affine transformations, for which both DAISY
and SIFT have been proven to be robust. These methods
can also tolerate certain photometric changes, but muchless than DaLI. On the other hand, the GIH performs quite
poorly for real deformations, even when no light changes
are considered. This reveals another limitation of this approach, in that it assumes the effect of deformations is tolocally change the position of image pixels, while in real
deformations some of the pixels may disappear due to occlusions. Although our approach does not explicitly address
occlusions, we can partially handle them by weighing thecontribution of the pixels within each patch, by a functionof the distance to the center. This makes that most of the information of our descriptor is concentrated in a small region
surrounding the point of interest, and hence, being less sensitive to occlusions. Fig. 9 shows the results for a few pairsof input images. Observe how DaLI clearly outperforms theother approaches.

80

60

40

20

0

Large Deformations
100

Mean Detection Rate (%)

Mean Detection Rate (%)

100

Light #0 Light #1 Light #2 Light #3 Light #4

SIFT
DAISY
GIH[0.25,1.75]
GIH[0.95,1.05]
DaLI

80

60

40

20

0

Light #0 Light #1 Light #2 Light #3 Light #4

Figure 10. Detection Rates for small and large deformations, considering just the best candidate (n = 1).

5. Conclusion and Future WorkHeat diffusion theory has been recently shown effective
for 3D shape recognition tasks. In this paper, we have proposed using these tools to build the DaLI, a feature point
descriptor for 2D image patches, that is invariant to nonrigid deformations and light changes. The advantages of our
method with respect to state-of-the-art have been demonstrated by extensively testing on images containing both realand synthetic deformations.
There are still some issues that may be improved and areleft for future work. For instance, we are currently representing the descriptor as a 3D array defined on the spatial
and frequency domains. As a future work we will investigate different techniques for compacting this representation to allow for faster matching while retaining recognition
rates. In addition, the technique we use to handle in-planerotations and scaling searches within a wide range of values. This step can be readily speeded up, by incorporating
prior orientation and scale estimation into our descriptor, as
it is done for the SIFT descriptor.

An finally, in Fig. 10 we compare the methods when only
the best candidate is taken, that is, considering n = 1 in
Eq. 10. In addition, since our dataset contains repetitions of
the same experiments with increasing amounts of deformation, we split the analysis into small and large deformations.
Again, we show that our approach clearly does better thanother methods, especially under illumination changes.
7Input Images

SIFT

DAISY

GIH

DaLI

Figure 9. Matching results for a few samples from the test set. As in Fig. 1 the color of the circles indicates the position n of the correct
match among the top candidates. If n > 10 we consider the point as unmatched and mark it with a cross.

References[15] H. Ling, X. Yang, and L. Latecki. Balancing deformability
and discriminability for shape matching. In ECCV, 2010.
[16] D. G. Lowe. Distinctive image features from scale-invariant
keypoints. IJCV, 2004.
[17] K. Mikolajczyk and C. Schmid. A performance evaluationof local descriptors. PAMI, 10(27):1615–1630, 2005.
[18] U. Pinkall and K. Polthier. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics, 1993.
[19] M. Reuter, F. Wolter, and N. Peinecke. Laplace-beltrami
spectra as ’shape-dna’ of surfaces and solids. CAD, 2006.
[20] R. Rustamov. Laplace-beltrami eigenfunctions for deformation invariant shape representation. In ESGP, 2007.
[21] J. Sanchez, J. Ostlund, P. Fua, and F. Moreno-Noguer. Simultaneous pose, correspondence and non-rigid shape. In
CVPR, 2010.
[22] N. Sochen, R. Kimmel, and R. Malladi. A general framework
for low level vision. Trans. on Image Processing, 1998.
[23] J. Sun, M. Ovsjanikov, and L. Guibas. A concise and provably informative multi-scale signature based on heat diffusion. In Eurographics Symp. on Geometry Processing, 2009.
[24] E. Tola, V. Lepetit, and P. Fua. Daisy: An efficient dense
descriptor applied to wide-baseline stereo. PAMI, 2010.
[25] L. Torresani, V. Kolmogorov, and C. Rother. Feature correspondence via graph matching: Models and global optimization. In ECCV, 2008.
[26] A. Vedaldi and S. Soatto. Features for recognition: Viewpoint invariance for non-planar scenes. In ICCV, 2005.
[27] G. Xu. Discrete laplace-beltrami operators and their convergence. Computer Aided Geometric Design, 2004.
[28] S. Yanowitz and A. Bruckstein. A new method for image
segmentation. Comp. Vision, Graph. and Image Proc., 1989.
[29] A. Yezzi. Modified curvature motion for image smoothing
and enhancement. Trans. on Image Processing, 1998.

[1] H. Bay, T. Tuytelaars, and L. V. Gool. SURF: Speeded up
robust features. In ECCV, 2006.
[2] S. Belongie, J. Malik, and J. Puzicha. Shape matching andobject recognition using shape contexts. PAMI, 2002.
[3] A. Berg, T. Berg, J. Malik. Shape matching and object recognition using low distortion correspondences. In CVPR, 2005.
[4] A. Bronstein, M. Bronstein, A. Bruckstein, and R. Kimmel.
Analysis of two-dimensional non-rigid shapes. IJCV, 2007.
[5] M. Bronstein and I. Kokkinos. Scale-invariant heat kernel
signatures for non-rigid shape recognition. In CVPR, 2010.
[6] M. Calonder, V. Lepetit, and P. Fua. BRIEF: Binary robust
independent elementary features. In ECCV, 2010.
[7] I. Chavel. Eigenvalues in Riemannian Geometry. London
Academic Press, 1984.
[8] H. Cheng, Z. Liu, N. Zheng, and J. Yang. A deformable local
image descriptor. In CVPR, 2008.
[9] M. Cho, J. Lee, and K. Lee. Feature correspondence and deformable object matching via agglomerative correspondence
clustering. In ICCV, 2009.
[10] Y. Ke and R. Sukthankar. PCA-SIFT: a more distinctive representation for local image descriptors. In CVPR, 2004.
[11] M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In ICCV,2005.
[12] B. Levy. Laplace-beltrami eigenfunctions towards an algorithm that “understands” geometry. In ICSMA, 2006.
[13] H. Ling and D. Jacobs. Deformation invariant image matching. In ICCV, 2005.
[14] H. Ling and D. Jacobs. Shape classification using the innerdistance. PAMI, 2007.

8