Noname manuscript No.
(will be inserted by the editor)

DaLI: Deformation and Light Invariant Descriptor
Edgar Simo-Serra · Carme Torras · Francesc Moreno-Noguer

Received: date / Accepted: date

Abstract Recent advances in 3D shape analysis andrecognition have shown that heat diﬀusion theory canbe eﬀectively used to describe local features of deforming and scaling surfaces. In this paper, we show how
this description can be used to characterize 2D image
patches, and introduce DaLI, a novel feature point descriptor with high resilience to non-rigid image transformations and illumination changes. In order to build
the descriptor, 2D image patches are initially treatedas 3D surfaces. Patches are then described in terms ofa heat kernel signature, which captures both local andglobal information, and shows a high degree of invariance to non-linear image warps. In addition, by further
applying a logarithmic sampling and a Fourier transform, invariance to photometric changes is achieved.
Finally, the descriptor is compacted by mapping it onto
a low dimensional subspace computed using Principal
Component Analysis, allowing for an eﬃcient matching.
A thorough experimental validation demonstrates that
DaLI is significantly more discriminative and robust toilluminations changes and image transformations thanstate of the art descriptors, even those specifically designed to describe non-rigid deformations.
Keywords local image descriptors · diﬀusion equation · heat kernel descriptors · deformation andillumination invariance

E. Simo-Serra · C. Torras · F. Moreno-Noguer (Corresponding
author)Institut de Robòtica i Informàtica Industrial
CSIC-UPC
08028, Barcelona, Spain
Tel.: +34-93-4015806
E-mail: {esimo,torras,fmoreno}@iri.upc.edu

1 Introduction
Building invariant feature point descriptors is a central
topic in computer vision with a wide range of applications such as object recognition, image retrieval and3D reconstruction. Over the last decade, great successhas been achieved in designing descriptors invariant tocertain types of geometric and photometric transformations. For instance, the SIFT descriptor [30] and manyof its variants [3,21,31,32,46] have been proven to berobust to aﬃne deformations of both spatial and intensity domains. In addition, aﬃne deformations caneﬀectively approximate, at least on a local scale, otherimage transformations including perspective and viewpoint changes. However, as shown in Fig. 1, this approximation is no longer valid for arbitrary deformations occurring when viewing an object that deforms
non-rigidly.
In order to match points of interest under non-rigid
image transformations, recent approaches propose optimizing complex objective functions that enforce global
consistency in the spatial layout of all matches [12,13,
24,40,41,47]. Yet, none of these approaches explicitly
builds a descriptor that goes beyond invariance to aﬃnetransformations. An interesting exception is [26], that
proposes embedding the image in a 3D surface and using a Geodesic Intensity Histogram (GIH) as a featurepoint descriptor. However, while this approach is robust
to non-rigid deformations, its performance drops underlight changes. This is because a GIH considers deformations as one-to-one image mappings where image pixels
only change their position but not the magnitude of
their intensities.
To overcome the inherent limitation of using geodesic
distances, we propose a novel descriptor based on theHeat Kernel Signature (HKS) recently introduced for2
Reference Image

Edgar Simo-Serra et al.
SIFT

DAISY

LIOP

GIH

DaLI

n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n=10
Fig. 1 Comparing DaLI against SIFT [30], DAISY [46], LIOP [53] and GIH [26]. Input images correspond to diﬀerent appearancesof the object shown in the reference images, under the eﬀect of non-rigid deformations and severe changes of illumination. 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 a cross. Note that the DaLI descriptor yields
a significantly larger number of correct matches.

non-rigid 3D shape recognition [16,39,44], and which
besides invariance to deformation, has been demonstrated
to be robust to global isotropic [7] and even aﬃne scalings [37]. In general, the HKS is particularly interesting in our context of images embedded on 3D surfaces,
because illumination changes produce variations on theintensity dimension that can be seen as local anisotropic
scalings, for which [7] still shows a good resilience.
Our main contribution is thus using the tools ofdiﬀusion geometry to build a descriptor for 2D image
patches that is invariant to non-rigid deformations andphotometric changes. To construct our descriptor weconsider an image patch P surrounding a point of interest, as a surface in the (x, y, I(x)) space, where (x, y)
are the spatial coordinates, I(x) is the intensity value
at (x, y), and is a parameter which is set to a large
value to favor anisotropic diﬀusion and retain the gradient magnitude information. Drawing inspiration fromthe HKS [16,44], we then describe each patch in termsof the heat it dissipates onto its neighborhood overtime. To increase robustness against 2D and intensity
noise, we use multiple such descriptors in the neighborhood of a point, and weigh them by a Gaussian kernel.
As shown in Fig. 1, the resulting descriptor (which wecall DaLI, for Deformation and Light Invariant) outperforms state-of-the-art descriptors in matching points ofinterest between images that have undergone non-rigid
deformations and photometric changes.
A preliminary version of this paper was already published in [33]. In the current work, we propose alternatives to both alleviate the high cost of the heat kernel
computation and to reduce the dimensionality of thedescriptor. More specifically, while in [33] the 3D embedding was performed considering a mesh with a uniform distribution of vertices in the (x, y) domain, here
we investigate topologies with varying vertex densities.

This allows reducing the eﬀective size of the underlying
mesh, and hence to speed up the DaLI computation
time by a factor of over 4. In addition, we have also
compacted the size of the final descriptor by a factorof 50⇥ using a Principal Component Analysis (PCA)
for dimensionality reduction. As a result, the descriptor
we propose here can be computed and matched much
faster when compared to [33], while preserving the discriminative power. For evaluation, we acquired a challenging dataset that contains 192 pairs of real images,
manually annotated, of diverse materials under diﬀerent degrees of deformation and being illuminated byvery diﬀerent illumination conditions. Fig. 1-left shows
two samples of our dataset. We believe this is the first
deformation and illumination dataset for evaluating image descriptors using real-world objects, and have madethe dataset along with the code of the DaLI descriptor
publicly available1 .

2 Related WorkThe SIFT descriptor [30] has become the main reference
among feature point descriptors, showing great successin capturing local aﬃne deformations including scaling,rotation, viewpoint change and certain lighting changes.
Since it is relatively slow to compute, most of the subsequent works have focused on developing faster descriptors [3,10,21,31,46]. Scale and rotation invariance has
also been demonstrated in [22] using a combination oflogarithmic sampling and multi-scale signal processing,although that requires large image patches which makethe resulting descriptor more sensitive to other deformations. Indeed, as discussed in [52], little eﬀort has
1

http://www.iri.upc.edu/people/esimo/research/dali/

DaLI: Deformation and Light Invariant Descriptor

3

, 
' 

' () *

+ ,'()+

! "!#$ % &+ ,+

- "." #
      


Fig. 2 Flowchart of the algorithm used to calculate the DaLI and DaLI-PCA descriptors. The percentages below each of the steps
indicate the total amount of the contribution of that step to the computation time. Observe that 99% of the computation timecorresponds to the Heat Kernel Signature calculation and specifically almost entirely to the eigendecomposition of the Laplace-Beltrami
operator.

been devoted to building descriptors robust to moregeneral deformations.
The limitations of the aﬃne-invariant descriptors
when solving correspondences between images of objects that have undergone non-rigid deformations arecompensated by enforcing global consistency, both spatial and photometric, among all features [4,5,12,13,
24,40,41,47], or introducing segmentation information
within the descriptor itself [48,49]. In any event, noneof these methods specifically handles the non-rigid nature of the problem, and they 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 proposed using diﬀerent types of intrinsic geometry. For example, [6,27] define metrics based on the inner-distance,and [28] proposes using geodesic distances. However,
all these methods require the shapes to be segmented
out from the background and represented by binary
images, which is diﬃcult to do in practice. In [26], 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. Nonetheless, this method assumes that pixels
only change their image locations and not their intensities and, as shown in Fig. 1, is prone to failure underillumination changes.
There have also been eﬀorts to build illumination invariant descriptors. Such works consider strategies basedon intensity ordering and spatial sub-division [15,17,19,
18,20,45,53]. While these approaches are invariant tomonotonically increasing intensity changes, their success rapidly falls when dealing with photometric artifacts produced by complex surface reflectances or strong
shadows.
The DaLI descriptor we propose can simultaneously
handle such relatively complex photometric and spatial warps. Following [26], we represent the images as
2D surfaces embedded in the 3D space. This is in fact

a common practice, although it has been mostly employed for low level vision tasks such as image denoising [43,56] or segmentation [55]. The fundamental difference between our approach and [26] is that we thendescribe each feature point on the embedded surface
considering the heat diﬀusion over time [16,25,44] instead of using a Geodesic Intensity Histogram. As wewill show in the results section this yields substantially
improved robustness, especially to illumination changes.
Heat diﬀusion theory has been used by several approaches for the analysis of 3D textured [23] and non-textured
shapes [14,25,38,39], but to the best of our knowledge,
it has not been used before to describe patches in intensity images.
One of the main limitations of the methods basedon the heat diﬀusion theory is the high complexity costthey require. The bottleneck of their computation lies
on an eigendecomposition of a nv ⇥ nv Laplacian matrix (see Fig. 3), where nv is the number of verticesof the underlying mesh. This has been addressed bypropagating the eigenvectors across diﬀerent mesh resolutions [42,54] or using matrix exponential approximations [50]. In this paper, an annular multiresolution
grid will be used to improve the eﬃciency of the DaLI
computation. Additionally, PCA will be used to reducethe dimensionality of the original DaLI descriptor [33],hence speeding up the matching process as well.

3 Deformation and Light Invariant Descriptor
Our approach is inspired by current methods [16,44]
that suggest using diﬀusion geometry for 3D shape recognition. In this section we show how this theory can beadapted to describe 2D local patches of images that undergo non-rigid deformations and photometric changes.
A general overview of the diﬀerent steps needed to compute the DaLI and DaLI-PCA descriptors can be seenin Fig. 2 and are explained more in detail below.

4

Edgar Simo-Serra et al.
DaLI Descriptor Slices at Frequencies w = {0, 2, 4, 6}

y

x

1

z
2
x

1

where 4M is the Laplace-Beltrami operator, a generalization of the Laplacian to non-Euclidean spaces, andu(x, t) is the amount of heat on the surface point x attime t.
The solution k(x, y, t) of the heat equation with an
initial heat distribution uo (x, t) = (x y) is called theheat kernel, and represents the amount of heat that is
diﬀused between points x and y at time t, considering aunit heat source at x at time t = 0. For a compact manifold M , the heat kernel can be expressed by following
spectral expansion [11,38]:

y

2

2

Descriptor
PixelsDescriptorfor
for Single
single pixels

Image Embedding

x1

SI−HKS

6

y1
4

x2
y2

2
0
0

z2
5

10

Freq(w)

15

20

k(x, y, t) =Fig. 3 DaLI descriptor. Our central idea is to embed image
patches in 3D surfaces and describe them based on heat diﬀusion
processes. We represent the heat diﬀusion as a stack of images
in the frequency domain. The top images show various slices ofour descriptor for two diﬀerent patches. The bottom-right graphdepicts the value of the descriptor for the pixels marked by color
circles in the upper images. Note that corresponding pixels havevery similar signatures. However, the signature may significantly
change from one pixel to its immediate neighbor. For instance, z2
is at one pixel distance from x2 , but their signatures are rather
diﬀerent. As a consequence, using the signature of a single point
as a descriptor is very sensitive to 2D noise in the feature detection process. We address this by simultaneously considering
the signature of all the pixels within the patch, weighted by aGaussian function of the distance to the center of the patch.

3.1 Invariance to Non-Rigid Deformations
Let us assume we want to describe a 2D image patch P ,of size SP ⇥ SP and centered on a point of interest p.
In order to apply the diﬀusion geometry theory to intensity patches we regard them as 2D surfaces embedded in 3D space (Fig. 3 bottom-left). More formally,
let f : P ! M be the mapping of the patch P to a
3D Riemannian manifold M . We explicitly define thismapping by:
f : x ! (x, y, I(x))

8x 2 P ,diﬀusion equation over the manifold M :
✓
◆
@
4M +
u(x, t) = 0 ,@t(1)where I(x) is the pixel intensity at x = (x, y)> , andis a parameter that, as we will discuss later, controls
the amount of gradient magnitude preserved in the descriptor.
Several recent methods [16,25,38,39,44] have used
the heat diﬀusion geometry for capturing the local properties of 3D surfaces and performing shape recognition.
Similarly, we describe each patch P based on the heat

1
X

e

it

i (x)

(2)

i (y) ,

i=0

where { i } and { i } are the eigenvalues and eigenfunctions of 4M , and i (x) is the value of the eigenfunction
i at the point x. Based on this expansion, [44] proposes describing a point p on M using the Heat Kernel
Signature
HKS(p, t) = k(p, p, t) =

1
X

e

it

2
i (p) ,

(3)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 structureof M (when t ! 1).
However, while on smooth surfaces the HKS of neighboring points are expected to be very similar, when
dealing with the wrinkled shapes that may result fromembedding image patches, the heat kernel turns to behighly unstable along the spatial domain (Fig. 3 bottomright). This makes the HKS particularly sensitive tonoise in the 2D location of the keypoints. To handle
this situation, we build the descriptor of a point p byconcatenating 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. We therefore define thefollowing Deformation Invariant (DI) descriptor:
DI(p, t) = [HKS(x, t) · G(x; p, )]8x2P ,(4)

where G(x; p, ) is a 2D Gaussian function centered on
p having a standard deviation , evaluated at x. Notethat for a specific time instance t, DI(p, t) is a SP ⇥ SP
array.
The price we pay for achieving robustness to 2D
noise is an increase of the descriptor size. That is, if
HKS(p, t) is a function defined on the temporal domain

DaLI: Deformation and Light Invariant Descriptor

5

100
90

Descriptor Change(%)

Deformation Level

Illumination Changes

Def11

DaLI
DI

Def10
Def9

80

Def8

70

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

Fig. 4 Invariance of the DaLI and DI descriptors to non-rigid
deformations and illumination changes. Top row and left column images: Diﬀerent degrees of deformation and light changes
applied on the top left reference patch P0 . Deformations are applied according to a function Def(·) 2 {Def0, . . . , Def11}, where
Def11 corresponds to the maximal deformation. Light changes
are produced by scaling the intensity of P0 by a gain g 2 [0, 1].
Bottom Graph: Given a deformation Def(·) and a gain factor
g, we compute the percentage of change of the DI descriptor bykDI(P0 ) DI(Def(gP0 ))k/kDI(P0 )k. The percentage of change
for DaLI is computed in a similar way. Observe that DaLI is muchless sensitive than DI, particularly to illumination changes.

R+ discretized into nt equidistant intervals, the complete DI descriptor DI(p) = [DI(p, t1 ), . . . , DI(p, tnt )]will be defined on SP ⇥ SP ⇥ nt , the product of the spatial and temporal domains. However, note that for our
purposes this is still feasible, because we do not needto compute a descriptor for every pixel of the image,but just for a few hundreds of points of interest. Furthermore, as we will next discuss, the descriptor may behighly compacted if we represent it in frequency domain
instead of time domain and even further compacted byusing dimensionality reduction techniques such as Principal Component Analysis (PCA).
3.2 Invariance to Illumination Changes
An inherent limitation of the descriptor introduced in
Eq. (4) is that it is not illumination invariant. This isbecause light changes scale the manifold M along theintensity axis, and the HKS is sensitive to scaling. It canbe shown that an isotropic scaling of the manifold M
by a factor ↵, scales the eigenvectors and eigenvalues ofEq. (2) by factors 1/↵ and 1/↵2 , respectively [38]. TheHKS of a point ↵p 2 ↵M can then be written as
1
X
HKS(↵p, t)=
e
i=0

i t
↵2

2
1
t
i (p)
= 2 HKS(p, 2 ) ,
2
↵
↵
↵

(5)

which is an amplitude and time scaled version of theoriginal HKS.

Nonetheless, under isotropic scalings, several alternatives have been proposed to remove the dependenceof the HKS on the scale parameter ↵. For instance, [38]suggests normalizing the eigenvalues in Eq. (2). In thispaper we followed [7], that applies three consecutive
transformations on the HKS. First, the time-dimension
is logarithmically sampled, which turns the time scaling
into a time-shift, that is, the right-hand side of Eq. (5)begets ↵ 2 HKS(p, 2 log ↵ + log t). Second, the amplitude scaling factor is removed by taking logarithm andderivative w.r.t. log t. The Heat Kernel then becomes@@ log t log HKS(p, 2 log ↵ + log t). The time-shift term
2 log ↵ is finally removed using the magnitude of theFourier 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 is concentrated in the low-frequency components,
the size of the descriptor can be highly reduced compared to that of HKS(p, t) by eliminating the highfrequency components past a certain frequency threshold wmax .
As we will show in the results section, another advantage of the SI-HKS signature is that although it
is specifically designed to remove the dependence ofthe HKS on isotropic scalings, it is quite resilient toanisotropic transformations, such as those produced byphotometric changes that only aﬀect the intensity dimension of the manifold M . Thus, we will use this signature to define our Deformation and Light Invariant(DaLI) descriptor:
DaLI(p, w) = [SI-HKS(x, w) · G(x; p, )]8x2P .
Again, the full DaLI(p) descriptor is defined as a concatenation of wmax slices in the frequency domain, eachof size SP ⇥ SP .
Fig. 3-top shows several DaLI slices at diﬀerent frequencies for a patch and a deformed version of it. As
said above, observe that most of the signal is concentrated in the low frequency components. In Fig. 4 wecompare the sensitivity of the DI and DaLI descriptors to deformation and light changes, simulated hereby a uniform scaling of the intensity channel. Note that
DaLI, in contrast to DI, remains almost invariant tolight changes, and it also shows a better performance
under deformations. In the results section, we will showthat this invariance is also accompanied by a high discriminability, yielding significantly better results in keypoint matching than existing approaches.
In order to get deeper insight about the properties of
the DaLI descriptor, we have further evaluated the HKS
and SI-HKS descriptor variants on a synthetic experiment, in which we have rendered various sequences ofimages of a textured 3D wave-like mesh under diﬀerent

6

Edgar Simo-Serra et al.

Def.+Ill.

Def.

Ill. (Def.)

Ill. (No Def.)

Normalized DaLI (SI−HKS)

Def.+Ill.
Def.
Ill. (Def.)
Ill. (No Def.)

6
Distance

Distance

8
6

60

150

Def.+Ill.
Def.
Ill. (Def.)
Ill. (No Def.)

Def.+Ill.
Def.
Ill. (Def.)
Ill. (No Def.)4

4

Def.+Ill.
Def.
Ill. (Def.)
Ill. (No Def.)

50
40

100
Distance

10

Normalized DaLI (HKS)

DaLI (HKS)8Distance

DaLI (SI−HKS)
12

30
20

50

2
2
0

10

0

50

100

150
Frame

200

250

300

0

0

50

100

150
Frame

200

250

300

0

0

100

200

300

0

0

Frame

50

100

150
Frame

200

250

300

Fig. 5 Evaluation of the descriptor robustness on synthetic sequences. In the top-left we show two sample images (the reference image
and one specific frame) from all four diﬀerent scenarios we consider. In the top-right we show an 3D view of the rendering process,with the light position placed near the mesh and producing patterns of diﬀerent brightness on top of the surface. The bottom row
depicts the descriptor distance between every input frame and the reference image for diﬀerent descriptor variants.

degrees of deformation and varying illumination conditions. The surface’s reflectance is assumed to be Lambertian and the light source is moved near the surface,
producing lighting patterns that combine both shading
and the eﬀects of the inverse-square falloﬀ law.

tensity of the input images so that the pixels follow a
distribution N (0, 1), and directly using the input image
intensities. The most interesting outcome of this experiment is to observe how the non-normalized SI-HKS descriptor has comparable distances for all the scenarios.
We have analyzed four particular situations: Def.+Ill., On the other hand, the normalized versions (SI-HKS
and HKS) seem to distinguish largely whether there isvarying both deformation and the light source position;or there is not deformation. It is also worth noting thatDef., varying deformation and keeping the light source
this normalization creates some instability at the earat infinity; Ill. (Def.), starting with a largely deformedlier frames while the non-normalized SI-HKS descriptor
state which is kept constant along the sequence andstarts at nearly 0 error and increases smoothly for all
varying the light source position; and Ill. (No Def.),
scenarios. Note also the low performance of the nonvarying the light source position while keeping the surnormalized HKS descriptor under illumination changes
face flat. The mesh deformation in the first two seas seen by the exponential curves for the illuminationquences, corresponds to a sinusoidal warp, in which thescenarios Ill. (Def ) and Ill. (No Def ), and the large
amplitude of the deformation increases with the frame
fluctuations for both the deformation Def and the illunumber. The varying lighting conditions in all expermination changing scenario Def. + Ill . This indicatesiments except the second, are produced by smoothly
the importance of the logarithmic sampling and Fourier
moving the light source on a hemisphere very close totransform process we apply to make HKS illumination
the surface. Two frames from each of these sequences
invariant.
are shown in the top-left of Fig. 5.
For the evaluation, we computed the L2-norm distance between pairs of descriptors at the center of thefirst and n-th frames of the sequence. The results are
depicted in Fig. 5-bottom. When computing the distances, we consider two situations: normalizing the in-

3.3 Handling In-Plane Rotation
Although DaLI tolerates certain amounts of in-planerotation, it is not designed for this purpose. This is be-

DaLI: Deformation and Light Invariant Descriptor

7

Representation of an Image Patch

(a)

(b)

(c)

Diﬀerent Mesh Triangulations(d) Dense Square(e) Dense Circular(f ) AnnularFig. 6 Left: Patch representation. (a) Image patch. (b) 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 (filled
circles) we have introduced additional intra-pixel vertices (empty circles), that provide finer heat diﬀusion results and higher tolerance
to in-plane rotations. (c) Definition of the angles used to compute the discrete Laplace-Beltrami operator. Right: Several meshtriangulations. Upper half of three diﬀerent triangulations of a 11 ⇥ 11 image patch. The shading on the left half of the mesh
indicates the density of the meshing. Dark red shading indicates high density and lighter red shading corresponds to low density. (d)Dense Square Mesh, with the same topology as in (b). By using circular meshes (e, f ), we reduce the number of vertices and thus, thecomputation time of the heat kernel. In the case of the annular mesh (f ), a further reduction of the number of nodes is achieved byhaving a variable resolution of the mesh that is more dense at the center. The edges of the annular mesh preserve symmetry aroundthe central point in order to favor uniform heat diﬀusion.

cause 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, the descriptor will also be
rotated.
In order to handle this situation, during the matching process we will consider several rotated copies of thedescriptors. Therefore, given DaLI(p1 ) and DaLI(p2 )we will compare them based on the following metric

Table 1 DaLI computation time and mesh complexity for diﬀerent triangulations of a circular patch with outer radius S = 20,
and inner radius So = 10 (for the Annular mesh).

d(p1 , p2 ) = arg min kR✓i (DaLI(p1 ))small amounts of rotation, and more uniform diﬀusions
than other configurations.
As seen in Fig. 2, nearly all the computation timeof the DaLI descriptor is spent calculating the LaplaceBeltrami eigenfunctions of the triangulated mesh. In
the following subsection we will show that this computation turns to have a cubic cost on the number ofvertices of the mesh, hence, important speed gains canbe achieved by lowering this number. For this purpose
we further considered a circular mesh (Fig. 6(e)), anda mesh with a variable density, like the one depicted inFig. 6(f), where a lower resolution annulus is used forthe pixels further away from the center.
By using an annular mesh with an inner radius So =S/2, where S is the size of the outer radius, we were able
to speed up the computation of the DaLI descriptor bya factor of four compared to the Dense Squared configuration (see Table 1). Most importantly, this increasein speed did not result in poorer recognition rates.
Another important variable of our design is the magnitude of the parameter in Eq. (1), that controls theimportance of the intensity coordinate with respect tothe (x, y) coordinates. In particular, as shown in Fig. 7,
large values of allow our descriptor to preserve edge
information. This is a remarkable feature of the DaLI
descriptor, because besides being deformation and il-✓i

DaLI(p2 )kwhere k · k denotes the L2 norm and R✓i (DaLI(p)) rotates DaLI(p) by an angle ✓i . This parameter is chosen
among a discrete set of values ✓.
This rotation handling will not be necessary whenusing Principal Component Analysis to compress thedescriptor size as we describe in Section 5.2.
3.4 Implementation Details
We next describe a number of important details to beconsidered for the implementation of the DaLI descriptor.
3.4.1 Geometry of the embedding
For the numerical computation of the heat diﬀusion,
it is necessary to discretize the surface. We therefore
represent the manifold M on which the image patch isembedded using a triangulated mesh. Fig. 6(b) shows
the underlying structured 8-neighbour representation
we use. Although it requires introducing additional virtual vertices between the pixels, its symmetry with respect to the x and y directions provides robustness to

Mesh Type# Pixels# Vertices# FacesTime(n v )(nf )(s)Dense Square

1681

3281

6400

1.988

Dense Circular

1345

2653

5144

1.509

Annular

1345

1661

3204

0.460

8

Edgar Simo-Serra et al.

w=2

w=4

w=6

w=8

β = 1000

β = 100

β = 10w=0

Fig. 7 Preserving edge information. Larger values of theparameterin 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 diﬀerent value ofcomputed on the
car image from Fig. 3. Observe that for low values of there isblurring on the higher frequencies of the descriptor.

lumination invariant, edge information is useful to discriminate among diﬀerent patches.
3.4.2 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 [36]. We next detail the main steps.
Let {p1 , . . . , pnv } be the vertices of a triangularmesh, 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 nv ⇥ nv sparse
matrix computed by:
8P< k mik if i = j
Mij =mij if pi and pj are adjacent:0
otherwise++
where mij = cot ij+cot ij , and ij
and ij are the two
opposite angles depicted in Fig. 6(c), and the subscript‘k’ refers to all neighboring vertices of pi .
The eigenvectors and eigenvalues of the discrete Laplace-Beltrami operator can then be computed from thesolution of the generalized eigenproblem M = ⇤A ,where ⇤ is a diagonal matrix with the eigenvalues { i }and the columns ofcorrespond to the eigenvectors{ i } in Eq. (2).
Note that the computational cost of the eigendecomposition is cubic in the size of M, i.e., O(n3v ). As
discussed in the previous subsection, we mitigate thiscost by choosing mesh topologies where the numberof vertices is reduced. In addition, since the eigenvectors i with smallest eigenvalues have the most importance when calculating the HKS from Eq. (3), we canTable 2 DaLI Parameters
SymbolParameter Description. (Default Value)S

Outer radius of the annulus. (20)So

Inner radius of the annulus. (10)Magnitude of the embedding. (500)Standard deviation of Gaussian weighting. ( S)2n# of eigenvectors of the Laplace-Beltrami operator. (100)nt# of intervals in the temporal domain. (100)

wmax
✓i
nv

# of frequency components used. (10)Rotation angles({ 5, 0, +5})

for

descriptor

comparison.

# of mesh vertices.(1661)

nf# of triangular faces in the mesh. (3204)

npca# of PCA components for the DaLI-PCA. (256)approximate the actual value by only using a subset
formed by the n eigenvectors with smallest eigenvalues. Both these strategies allow the HKS calculation to
be tractable in terms of memory and computation time.
Finally, Table 2 summarizes all the parameters that
control the shape and size of the DaLI descriptor. The
way we set their default values, shown between theparentheses, will be discussed in Section 5.1.

4 Deformation and Varying Illumination
DatasetIn order to properly evaluate the deformation and illumination invariant properties of the DaLI descriptor
and compare it against other state-of-the-art descriptors, we have collected and manually annotated a newdataset of deformable objects under varying illumination conditions. The dataset consists of twelve objects ofdiﬀerent materials with four deformation levels and four
illumination conditions each, for a total of 192 uniqueimages. All images have a resolution of 640 ⇥ 480 pixels
and are grayscale.
The types of objects in the dataset are 4 shirts, 4newspapers, 2 bags, 1 pillowcase and 1 backpack. They
were chosen in order to evaluate all methods against
as many diﬀerent types of deformation as possible. The
objects can be seen in the top of Fig. 8.

4.1 Deformation and Illumination Conditions
The pipeline to acquire the images of each object consisted of, while keeping the deformation constant, changing the illumination before proceeding to the next deformation level. All images were taken in laboratory

DaLI: Deformation and Light Invariant Descriptor

Shirt #1

Shirt #2

Newspaper #1

Newspaper #2

9Reference Images
Shirt #3
Shirt #4

Newspaper #3

Newspaper #4

Deformation Level
Deform. Level #0 Deform. Level #1 Deform. Level #2 Deform. Level #3

Bag #1

Bag #2

Backpack

Pillowcase

Manual Annotationof Correspondences

Illumination Changes
Ill. Conditions #0 Ill. Conditions #1 Ill. Conditions #2 Ill. Conditions #3
Light
Sources
CameraObjectFig. 8 Deformable and Varying Illumination dataset. Top: Reference images of the twelve objects in the dataset. Each object
has four deformation levels and four illumination levels yielding a total of 16 unique images per object. Middle-left: Sample seriesof images with increasing deformation levels, and constant illumination. Bottom-left: Sample images of the diﬀerent illumination
conditions taken for a deformation level of each object. The illumination conditions #0, #1, #2 and #3 correspond to no illumination,
global illumination, global+local illumination, and local illumination, respectively. Middle-right and bottom-right: Examples offeature points matched across image pairs. The first column corresponds to the reference image for the object. These feature points
are detected using Diﬀerences of Gaussians (DoG) and are matched by manual annotation. Each feature point consists of image
coordinates, scale coordinates and orientation.

10
Original Patch

Edgar Simo-Serra et al.
RotatedScaledCroppedFig. 9 Top: Outline of the process used to obtain patches forevaluating image descriptors. For each feature point, we initiallyextract a square patch centered on the feature, and whose size is
proportional to the scale factor of the interest point. The patchis then rotated according to the orientation of the feature point,
and finally scaled to a constant size and cropped to be in a circular shape. Bottom: Sample patches from the dataset, alreadyrotated and scaled to a constant size in order to make them rotation and scale invariant.

conditions in order to fully control the settings for asuitable evaluation.
The reference image was acquired from an initialconfiguration where the object was straightened out asmuch as possible. While deformations are fairly subjective, as they were done incrementally over the previous
deformation level, they are representative of increasinglevels of deformation. Diﬀerent deformation levels of an
object with the same illumination conditions are shownin the middle-left of Fig. 8.
The illumination changes were produced by using
two high power focus lamps. The first one was placed
vertically over the object, at a suﬃcient distance toguarantee a uniform global illumination of the object’s
surface. The second lamp was placed at a small elevation angle and close to the object, in order to produce
harsh shadows and local illumination artifacts. By alternating the states of these lamps, four diﬀerent illumination levels are achieved: no illumination, global
illumination, global with local illumination, and local
illumination. The diﬀerent illumination conditions forconstant deformation levels can be seen in the bottomleft of Fig. 8. Note that even with moderate deformations, the presence of the local illumination causes severe appearance changes.

4.2 Manual Annotations
To build the ground truth annotations, we initially detected interest points in all images using a multi-scale
Diﬀerence of Gaussians filter [30]. This yielded approximately between 500 600 feature points per image, eachconsisting of a 2D image coordinate and its associatedscale.
These feature points were then manually matched
for each deformation level against the undeformed reference image, resulting in three pairs of matched feature points. All matches were done with top-light illumination conditions (Ill. Conditions #1, Fig. 8) to facilitate the annotation task and maximize the numberof repeated features between each pair of images. The
matching process yielded between 100 and 200 point
correspondences for each pair of reference and deformed
images. The same feature points are used for all illumination conditions for each deformation level. The
middle-right images of Fig. 8 show a few samples of ourannotation. Note that the matched points are generally
not near the borders of the image to avoid having toclip when extracting image patches.
As we will discuss in the experimental section, in
this paper we seek to compare the robustness of the
DaLI and other descriptors to only deformation andlight changes. Yet, although the objects in the dataset
are not globally rotated, the deformations do produce
local rotations. In order to compensate for this we use
the SIFT descriptor as done in [31] to compute the orientation of each feature point, and align all corresponding features. When a feature point has more than one
dominant orientation, we consider each of them to augment the set of correspondences.

4.3 Evaluation Criteria
In order to perform fair comparisons, we have developed a framework to evaluate local image descriptors
on even grounds. This is done by converting each feature point into a small image patch which is then used
to compute descriptors. This allows the evaluation of
the exact same set of patches for diﬀerent descriptors.
For each feature point we initially extract a square
patch around it, with a size proportional to the featurepoint’s scale. In the Experimental Section 5.3 we discuss
the value of the proportionality constant we use. The
patch is then rotated by the feature point’s orientation
using bilinear interpolation, and scaled to a constantsize, which we have set to 41 ⇥ 41 pixels as done in [31].
Finally, the patch is cropped to a circular shape. This
results in a scale and rotation invariant circular image

DaLI: Deformation and Light Invariant Descriptor

11

So

Illumination OnlySo

67%

[0,5,10,15,20] [0,5,10,15,20] [0,5,10,15,20] [0,5,10,15,20]

β=500 β=1000 β=2000[5,10,15,20]

β=250

So

β=125

β=250

So

So

So

88%

Illumination [0,5,10,15,20] [0,5,10,15,20] [0,5,10,15,20] [0,5,10,15,20] [0,5,10,15,20]
Only

wmax
wmax

σ=S

β=125

So

58%

β=500 β=1000 β=2000

σ=2S

So

[5,10,15,20]

wmax

So

wmax

[5,10,15,20]

σ=S

wmax

[5,10,15,20]

64%

wmax

wmax
wmax

Deformation
Only

σ=2S

[5,10,15,20]

σ=S
σ=S/2

wmax

[5,10,15,20][5,10,15,20]

Deformation Only

71%

σ=S/2

S

σ=2S

S

σ=S/2

S

[5,10,15,20]

S[5,10,15,20]

Deformation + Illumination ChangesooooDeformation[0,5,10,15,20] [0,5,10,15,20] [0,5,10,15,20] [0,5,10,15,20]
Illumination
Combined β=125 β=250 β=500 β=1000 β=2000

80%

Fig. 10 DaLI performance for diﬀerent values of the parameters So , , and wmax . We compute and average the matching rate
for the Shirt #1 and the Newspaper #1 objects in the dataset using So 2 {0, 5, 10, 15, 20} pixels, 2 {125, 250, 500, 1000, 2000},
2 {S, S, 2S} and wmax 2 {5, 10, 15, 20} for three scenarios: both deformation and illumination changes, only deformation changes,2
and only illumination changes. The graphs depict the results of this 4D parameter exploration, where the color of each square represents
the percentage of correctly matched points for a specific combination of the parameters. In order to visualize the diﬀerences, we scale
the values separately for each scenario. The best parameters for each scenario are marked in red and can be seen to vary greatly
amongst themselves. We use a compromise, and for all the experiments in this section we set these parameters (highlighted in green)
to = 500, So = 10, = S
and wmax = 10.
2

patch with a diameter of 41 pixels. The steps for extracting the patches are outlined in the top of Fig. 9,
and the bottom of the figure shows a few examples ofpatches from the dataset.
Given these “normalized patches” we then assess theperformance of the descriptors as follows. For each pairof reference/deformed images, we extract the descriptors of all feature points in both images. We then compute the L2 distance between all descriptors from thereference and the deformed image. This gives a distance matrix, which is rectangular instead of square
due to the creation of additional feature points when
there are multiple dominant orientations. Patches thathave diﬀerent orientations but share the same location
are treated as a unique patch. As evaluation metric we
use a descriptor-independent detection rate, which isdefined for the n top matches as:
Detection Rate(n) =100 · Nc (n)
,
N

(6)

where Nc (n) is the number of feature points from thereference image that have the correct match among the
top n candidates in the deformed image, and N is thetotal number of feature points in the reference image.
For the experimental results we will discuss in thefollowing section, we consider three diﬀerent evaluation
scenarios: deformation and illumination, only deformation, and only illumination. In the first case we compare all combinations of deformation and illumination
with respect to the reference image which has no additional illumination (ill. conditions #0) and no deformation (deform. level #0). This represents a total of 15
comparisons for each object. In the second case we consider only varying levels of deformation for each illumination condition, which yields 12 diﬀerent comparisons
per object (three comparisons per illumination level).

When only considering illumination, each deformationlevel is compared to all illumination conditions. Again,
this gives rise to 12 comparisons per object (three comparisons per deformation level).

5 Experimental Results
We next present the experimental results, in which we
discuss the following main issues: an optimization of
the descriptor parameters, a PCA-based strategy forcompressing the descriptor representation, and the actual comparison of DaLI against other state-of-the-art
descriptors, for matching points of interest in the proposed dataset. Finally, we analyze specific aspects suchas the performance of all descriptors in terms of theirsize, the benefits of normalizing the intensity of input
images, and a real application in which the descriptors
are compared when matching points of interest in real
sequences of a deforming cloth and a bending paper.

5.1 Choosing Descriptor’s Parameters
We next study the influence and set the values of the
DaLI parameters of Table 2. As the size SP of the patch
is fixed, causing the descriptor radius S to be also fixed,
we will look at finding the appropriate value of otherparameters, namely the magnitude of the embedding,the degree of smoothing within the patch, the inner
radius of the annulus So and the dimensionality wmaxof the descriptor in the frequency domain. In order tofind their optimal values, we used two objects in thedataset (Shirt #1 and Newspaper #1), and computed
matching rates of their feature points for a wide rangeof values for each of these parameters.

12

PCA

Edgar Simo-Serra et al.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

w=0
w=1
w=2
w=3
w=4
w=5
w=6
Fig. 11 The first 7 frequencies of the first 20 components of the PCA basis computed from images of two objects from the dataset(Shirt #1 and Newspaper #1). Each vector is normalized for visualization purposes. Positive values are displayed in green while
negative values are displayed in blue. Most of the components do not contain much information at frequencies w > 6 and thus they
are not displayed, although they are considered in the DaLI-PCA descriptor.

5.2 Compression with PCA
The DaLI descriptor has the downside of having a very
high dimensionality, as its size is proportional to theDef.+Ill.

0.85

Precision

Illumination
0.8

Deformation
Mean

0.75

0.7

0.65
100

200

300

400

500

600

700

800

900

1000

Dimension

w=1

w=2 w=3

w=4

w=5

w=6

PCA

DaLI

w=0

Diﬀ.

It is worth to point out that the number of eigenvectors n of the Laplace-Beltrami operator was set to
100 in all cases. Note that this value represents a verysmall portion of all potential eigenvectors, in the orderof two thousands (equal to the number of vertices nv ).
Using a lesser number of them would eventually deteriorate the results, while not providing a significant gainin eﬃciency, and using more of them, almost did not
improve the performance. Similarly, the number nt ofintervals in which the temporal domain is split is set
to 100. Again, this parameter had almost no influence,neither in the performance of the descriptor nor in its
computation time.
Fig. 10 depicts the results of the parameter sweeping
experiment. We display the rates for three scenarios:
when considering both deformation and illumination
changes, only deformation changes, and only illumination changes. The most influential parameters are theweighting factor and to a lesser extent the magnitudeof the embedding . We see that for a wide range ofparameters, the results obtained are very similar when
considering both illumination and deformation, however, there is a balance to be struck between both deformation and illumination invariance. By increasing deformation invariance, illumination invariance is reduced
and vice-versa. Finally we use a compromise, and theparameters we choose for all the rest of experiments are= 500, So = 10, = S2 and wmax = 10, besides then = 100 and nt = 100 we mentioned earlier.

Fig. 12 Top: DaLI-PCA performance for diﬀerent compression
levels. Note that the overall mean precision does not vary muchfor npca > 256 components. Bottom: Comparison of an original
DaLI descriptor with its compressed DaLI-PCA version obtainedusing 256 PCA components. For visualization purposes the values
are normalized and the diﬀerence shown in the third row is scaledby 5⇥.

product of the number of vertices nv used to represent
the patch and the number of frequency components
wmax . For instance, using patches with a diameter of
41 pixels and considering the first 10 frequency slices,
results in a 13450-dimensional descriptor (1345 pixels
by 10 frequency slices), requiring thus large amounts ofmemory and yielding slow comparisons. However, since

DaLI: Deformation and Light Invariant Descriptor

13

80
DaLI
DAISY
SIFT
LIOP
Pixel Diff.
NCC
GIH

Mean Detect. Rate (%)

70
60

the experiments in this section. In Fig. 12-bottom wecompare the frequency slices for an arbitrary DaLI descriptor and its approximation with 256 PCA-modes.
Observe that the diﬀerences are almost negligible.

50

5.3 Comparison with Other Approaches

40
30
20

3x

5x

7x

9x

Support Region Scale Factor

Fig. 13 Mean detection rates obtained by scaling regions of interest with diﬀerent factors. While a 3⇥ scale factor does lower
the overall performance, the diﬀerence between a 5⇥, 7⇥ or 9⇥
scale factor is minimum for descriptors other than weighted pixel
diﬀerences (Pix. Diﬀ.) or normalized cross covariance (NCC),
which do improve as interest regions increase in size. The resultsof the graph correspond to the average of the mean detection
rates with Deformation+Illumination changes, Illumination-onlychanges and Deformation-only changes.

the descriptor is largely redundant, it can be compactedusing dimensionality reduction techniques such as [8,9,35].
In this paper, as a simple proof of concept, we haveused Principal Component Analysis for performing suchcompression. The PCA covariance matrix is estimatedon 10436 DaLI descriptors extracted from images of the
Shirt #1 and Newspaper #1. The npca ⌧ nv · wmax
largest eigenvectors are then used for compressing an
incoming full-size DaLI descriptor. The resulting compacted descriptor, which we call DaLI-PCA, can be efficiently compared with other descriptors using the Euclidean distance. Fig. 11 shows the first 7 frequencies ofthe first 20 vectors of the PCA-basis. It is interesting
to note that most of the information can be seen to bein the lower frequencies. This can be considered an experimental justification for the frequency cut oﬀ appliedwith the wmax parameter, which we have previously set
to 10.
In order to choose the appropriate dimension npcaof the PCA-basis, we have used our dataset to evaluate
the matching rate of DaLI-PCA descriptors for diﬀerent compression levels. The results are summarized inFig. 12-top, and show that using fewer dimensions favors deformation invariance (actually, PCA can be understood as a smoothing that undoes some of the harmof deformations) while using more dimensions favors
illumination invariance. The response to joint deformation and illumination changes does not improve afterusing between 200 300 components, and this has been
the criterion we used to set npca = 256 for the rest of

We compare the performance of our descriptors (both
DaLI and DaLI-PCA) to that of SIFT [30], DAISY[46], LIOP [53], GIH [26], Normalized Cross Correlation(NCC) and Gaussian-weighted Pixel Diﬀerence. SIFT
and DAISY are both descriptors based on Diﬀerences ofGaussians (DoG) and spatial binning which have beenshown to be robust to aﬃne deformations and to certain
amount of illumination changes. LIOP is a recently proposed descriptor based on intensity ordering making it
fully invariant to monotonic illumination changes. GIH
is a descriptor specifically designed to handle non-rigid
image deformations, but as pointed out previously, it
assumes these deformations are the result of changing
the position of the pixels within the image and nottheir intensity. NCC is a standard region-based metric known to possess illumination-invariant properties.
Finally, we compare against a Gaussian-weighted pixel
diﬀerence using the same convolution scheme as used
for the DaLI descriptor. Standard parameters suggested
in the original papers are used for all descriptors except for the LIOP descriptor in which using a larger
number of neighboring sample points (8 instead of 4neighbors) results in a higher performance at the costof a larger descriptor (241920 instead of 144 dimensions). The LIOP and SIFT implementations are provided by VLfeat [51]. We use the authors’ implementation of DAISY and GIH.
The evaluation is done on the dataset presented in
Section 4. All the descriptors are therefore tested on
exactly the same image patches in order to exclusively
judge the capacity of local feature representation. Yet,as mentioned in Sec. 4.3, the dataset still requires setting the scale factor to use for the points of interest.
This value corresponds to the relative size of each image
patch with respect to the scale value obtained from the
DoG feature point detector. For this purpose, we evaluated the response of all descriptors for scale factors of3⇥, 5⇥, 7⇥ and 9⇥. The results are shown in Fig. 13.
Although the SIFT implementation uses a default valueof 3⇥, we have observed that the performance of all
descriptors improves by increasing the patch size. Notethat this does not result in a higher computational cost,
as the final size of the patch is normalized to a circular shape with a diameter of 41 pixels. The maximum
global response for all descriptors is achieved when us-

14

Edgar Simo-Serra et al.

100

DaLI
DAISY
SIFT
LIOP
Pixel Diff.
NCC
GIH

100

50

0
2

4

6

8

100

50

0

10

2

4

0
6

8

50

0

10

2

4

50

0
4

6

8

0
2

4

8

4

0
6

8

10

8

2

4

2

4

6

8

n

10

8

10

6

8

10

6

8

10

n

0
4

6

8

50

0

10

2

4

n

100

0

6

0

10

n

50

10

100

2

Mean Detect. Rate (%)

50

6

50

10

100

n

2

n
Mean Detect. Rate (%)

Mean Detect. Rate (%)

6

8

50

n

50

10

100

4

0

100

n

2

50

10

Mean Detect. Rate (%)

Mean Detect. Rate (%)

Mean Detect. Rate (%)

Deform. Level #2

8

100

2

Deform. Level #3

6

6

100

n

100

4

n

100

n

2

Mean Detect. Rate (%)

4

0

10

Mean Detect. Rate (%)

2

8

Mean Detect. Rate (%)

100

50

6

50

n
Mean Detect. Rate (%)

Mean Detect. Rate (%)

Mean Detect. Rate (%)

Deform. Level #1

n100

Ill. Conditions #3
Mean Detect. Rate (%)

DaLI−PCA

Ill. Conditions #2
Mean Detect. Rate (%)

Ill. Conditions #1
Mean Detect. Rate (%)

Deform. Level #0

Ill. Conditions #0

100

50

0
2

4

6

n

8

10

50

0
2

4

n

Fig. 14 Detection rate when simultaneously varying deformation level and illumination conditions. Each graph represents the averageof the mean detection rate between the reference image (ill. conditions #0 and deform. level #0) and all images in the dataset under
specific light and deformation conditions.

ing a 7⇥ scale factor, which is the value we use for all
the experiments reported below.
The results for concurrent deformation and illumination are summarized in Fig. 14. DaLI consistently
outperforms all other descriptors, although the morefavorable results are obtained under large illumination

changes. The performance of DAISY is very similar tothat of DaLI when images are not aﬀected by illumination artifacts. In this situation, the detection rates
of DAISY are approximately between 2 5% below
to those obtained by DaLI. However, when illumination artifacts become more severe, the performance of

DaLI: Deformation and Light Invariant Descriptor

15

SIFT
LIOP
Pixel Diff.
NCC
GIH

100

50

0
4

6

8

100

50

0

10

2

4

6

8

50

0

10

2

4

6

8

10

n

n

n

Ill. Conditions #1

Ill. Conditions #2

Ill. Conditions #3

Mean Detect. Rate (%)

Mean Detect. Rate (%)

Illumination-only

2

DaLI−PCA
DaLI
DAISY
SIFT
LIOP
Pixel Diff.
NCC
GIH

Mean Detect. Rate (%)

DAISY

100

Deform. Level #3

100

Mean Detect. Rate (%)

DaLI

Deform. Level#2
Mean Detect. Rate (%)

DaLI−PCA

Mean Detect. Rate (%)

Deformation-only

Deform. Level #1

100

50

0
2

4

6

8

10

n

100

50

0
2

4

6

n

8

10

50

0
2

4

6

8

10

n

Fig. 15 Top: Results when varying only the deformation while keeping the illumination conditions constant. It can be seen thatboth DaLI and DAISY largely outperform the rest of descriptors. Bottom: Results of varying only the illumination conditions while
keeping the deformation level constant. Note that only DaLI remains robust to illumination changes. The performance of DAISY falls
roughly a 20% compared to DaLI.

DAISY rapidly drops, yielding detection rates which are
more than 20% below DaLI. SIFT, LIOP, and Pixel Difference yield similar results, with SIFT being better at
weak illumination changes and LIOP better at handlingstrong illumination changes. Yet, these three methods
are one step behind DaLI and DAISY. NCC generally
performs worse except in situations with large illumination changes, where it even outperforms DAISY. On
the other hand, GIH performs quite poorly even when
no light changes are considered. This reveals anotherlimitation of this approach, in that it assumes the effect of deformations is to locally change the positionof image pixels, while in real deformations some of the
pixels may disappear due to occlusions. Although ourapproach does not explicitly address occlusions, we canpartially handle them by weighing the contribution of
the pixels within each patch, by a function decreasing
with the distance to the center. Thus, most of the information of our descriptor is concentrated in a small
region surrounding the point of interest, hence making
it less sensitive to occlusions. The results also show thatthe compressed DaLI-PCA follows a similar pattern as
DaLI, and specially outperforms DAISY under severe
illumination conditions.
In Fig. 15 we give stronger support to our arguments by independently evaluating deformations andillumination changes. These graphs confirm that under deformation-only changes, DaLI outperforms DaLIPCA and DAISY by a small margin of roughly 3%.
Next, SIFT, LIOP, and Pixel Diﬀerence yield similar results, roughly 20% below DaLI in absolute terms. GIH
and NCC yield also similar results, although their performance is generally very poor. When only illumination changes are considered, both DaLI and DaLI-PCA
significantly outperform other descriptors, by a margin larger than 20% when dealing with complex illumination artifacts. The only notable diﬀerence in this
scenario is that the NCC descriptor outperforms SIFT
and Pixel Diﬀerence. As GIH is not invariant to illumination changes, it obtains poor results. Similarly, since
LIOP is designed to be invariant to monotonic lighting

16

Edgar Simo-Serra et al.

Reference Image

SIFT

DAISY

LIOP

GIH

DaLI

n 10
n=10

n=9

n=8

n=7
n=8
n=6

n=5

n=4

n=3

n=2

n=1
Fig. 16 Sample results from the dataset. 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.

Table 3 Evaluation results on the dataset for all descriptors. Results are obtained by averaging the first match percentage values
over all images being tested under all diﬀerent conditions.
Descriptor

Deformation

Illumination

Deformation+
Illumination

DaLI-PCA

67.42585.12268.368

DaLI

70.57789.89572.912

DAISY

67.37375.40266.197SIFT

55.82260.76053.431

LIOP

58.76360.01452.176

Pixel Diﬀ.

54.71465.61054.382NCC

38.64362.04241.998GIH

37.45928.55631.230

True Positive Pairs

False Positive Pairs

False Negative Pairs

True Negative Pairs

Fig. 17 Some of the true positive, false positive, false negative
and true negative image patch pairs obtained using the DaLI
descriptor on the dataset. Note that most of the false negatives
are due to large orientation changes across feature points.

changes, it does not perform that well in real images
that undergo complex illumination artifacts.

ditionally, numeric results for the best candidate (n = 1
in Eq. 6) under diﬀerent conditions for all descriptors
are shown in Table 3.

In summary, the experiments have shown that DaLI
globally obtains the best performance. Its best relative
response when compared with other descriptors is obtained when the deformations are mild and the lightchanges drastic. Some sample results on particular images taken from the dataset can be seen in Fig. 16. Ad-

Finally, examples of particular patch matches are
depicted in Fig. 17. The true positives pairs can be seen
to be matched despite large changes. On the other hand,the false negatives seem largely generated by diﬀerencesin orientations of the feature points: they correspond to
the same patch, only rotated. The false positives share

DaLI: Deformation and Light Invariant Descriptor

17

Deforming Cloth

Paper Bending

DaLI

100

DAISY
SIFT

80

Mean Detect. Rate (%)

Mean Detect. Rate (%)

100

60

40

20
20

40

60

80

100

120

140

160

Frame

80

60
DaLI
DAISY

40

SIFT
20
20

40

60

80

100

120

140

160

Frame

Fig. 18 Mean detection accuracy on two real world videos from [34]. In the top row we show three example frames from each video.
In the bottom row we plot the accuracy for each frame for three descriptors: DaLI, DAISY and SIFT. Additionally the mean for each
descriptor is displayed as a dashed line.

Table 4 Comparison of performance and descriptor size.
Descriptor

Size

Deform.

Illum.

DaLI-PCA
SIFT
LIOP
DAISY
GIH
DaLI-PCA

128
128
144
200
176
256

67.45
55.82
54.01
67.37
37.46
67.43

82.34
60.76
44.89
75.40
28.56
85.12

Deformation+
Illumination
67.71
53.43
44.45
66.20
31.23
68.37

some similarity, although they are mainly from heavily
deformed images.

5.4 Descriptor Size Performance
Since larger descriptors may a priori have an unfair advantage, we next provide results of an additional experiment in which we compare descriptors having similar
sizes. The LIOP we calculate in this case uses 4 neighbours instead of the 8 neighbours we considered before,
which results in a smaller size, although also in a lower
performance. GIH is originally 176-dimensional, thus
the results are the same as in Table 3. NCC and PixelDiﬀ, are not considered for this experiment as their sizeis 41 ⇥ 41 = 1681.
Results are shown in Table 4. We can see that the
128-dimensional DaLI-PCA outperforms all other descriptors except the 256-dimensional DaLI-PCA. It is
worth noting the large performance gain obtained overthe standard SIFT descriptor.

5.5 Benefits of Intensity Normalization
We next extend the analysis we introduced in Sect. 3.2
in which we evaluated SI-HKS and HKS with and without pre-normalizing the intensity of input images. We
will also consider SIFT and DAISY, which have been
the most competitive descriptors in previous experiments. Since SIFT/DAISY implementations require thepixels to be in a [0, 1] range, we have normalized each
image patch so that the pixels follow the distribution
N (0.5, (2 · 1.956) 1 ). This makes it so that on average
95% of the pixels will fall in [0, 1]. Pixels outside of thisrange are set to either 0 or 1.
We compare the DaLI descriptor (both its SI-HKS
and HKS variants), DAISY and SIFT, with and withoutnormalization. Results are shown in Table 5. We can seethat for DAISY and SIFT, since they perform a final
normalization stage, the results do not have any significant change. In the case of the DaLI descriptor, though,we see that there is a rather significant performance increase when using the SI-HKS variant over the HKS
one, even with patch normalization. This demonstrates
again that the role of the Fourier Transforms applied in
HKS to make it illumination invariant go far beyond a
simple normalization. In addition, SI-HKS compresses
the descriptor in the frequency domain and is one orderof magnitude smaller than the HKS variant.
5.6 Evaluation on Real World Sequences
This section describes additional experiments on two
real world sequences of deforming objects, taken from [34].
One consists of a T-Shirt being waved in front of acamera (Deforming Cloth) and the other consists of a

18

Edgar Simo-Serra et al.

Table 5 Eﬀect of normalizing image patches for various descriptors.
Descriptor
DaLI (SI-HKS)
DaLI (SI-HKS)
DaLI (HKS)
DaLI (HKS)
DAISY
DAISY
SIFT
SIFT

Normalization?
No
Yes
No
Yes
No
Yes
No
Yes

Deformation
70.58
70.38
66.27
67.20
67.37
67.08
55.82
55.05

piece of paper being bended in front of a camera (Paper
Bending). We use points of interest computed with theDiﬀerences of Gaussians detector (DoG) and follow thesame patch extraction approach as in the rest of thepaper. The points of interest are calculated for the first
frame in each sequence and then propagated using theprovided 3D ground truth to the other frames. We use
the same descriptor parameters as in the rest of the experiments, and seek to independently match the points
of interest in the first frame to those of all the otherframes.
As we can observe in Fig. 18, DaLI outperforms
both DAISY and SIFT2 . We obtain a 5.5% improvement over DAISY on the Deforming Cloth sequence anda 4.1% improvement on the Paper Bending sequence.
Note that these sequences do not have as complicated illumination artifacts as our dataset, an unfavorable situation for our descriptor. Yet, DaLI still consistently outperforms other approaches along the whole sequence.

6 Discussion and Conclusions
Heat diﬀusion theory has been recently shown eﬀective for 3D shape recognition tasks. In this paper, wehave proposed using these tools to build DaLI, a feature point descriptor for 2D image patches, that is very
robust to both non-rigid deformations and illumination
changes. The advantages of our method with respect tothe state-of-the-art have been demonstrated by extensively testing them on a new deformation and varying
illumination evaluation dataset3 .
We have also shown that simple dimensionality reduction techniques such as PCA can be eﬀectively used
to reduce dimensionality while maintaining similar performance. This seems to give the intuition that further
improvements can be obtained by using more advanced
and powerful techniques such as LDAHash [8]. Work
2 Again, we only compare against DAISY and SIFT, as these
are the descriptors which have been more competitive in the experiments with the full dataset.
3 http://www.iri.upc.edu/people/esimo/research/dali/

Illumination
89.90
88.60
84.21
84.62
75.40
75.59
60.76
61.83

Deformation+Illumination
72.91
72.28
67.83
69.42
66.20
66.27
53.43
53.21

has also been done in optimizing the calculation speedby means of more complex meshing to reduce the costof computing the eigenvectors of the Laplace-Beltrami
operator.
As part of future work we will investigate recent andpromising alternatives to the Heat Kernel Signatures(HKS), such as the Wave Kernel Signature (WKS) [2],and strategies to directly learn spectral descriptors in asupervised manner [1,29]. Using labeled training data
would likely further increase the performance of ourdescriptor.
Additionally we will intend to make DaLI invariant
to scale and rotations without the need to explore awide range of discrete values. We will investigate twoalternatives for this purpose: 1) incorporating prior information of the orientation and scale within each frequency slice, as it is done for the SIFT descriptor; 2)
using a logarithmic sampling and Fourier Transform
Modulus (FTM) as in [22].
Finally, we also plan to look into the function toweight the pixels within each patch. We are currently
using a Gaussian distribution centered on the patch.
However, there have been recent alternatives that compute similar functions based on segmentation information, which have shown to significantly improve the performance of standard descriptors [48,49].

7 Acknowledgements
This work has been partially funded by the Spanish
Ministry of Economy and Competitiveness under projects
ERA-Net Chistera project ViSen PCIN-2013-047 and
PAU+ DPI2011-27510, and by the EU project IntellAct FP7-ICT2009-6-269959 .

References
1. Yonathan Aflalo, Er M. Bronstein, Michael M. Bronstein,
and Ron Kimmel. Deformable shape retrieval by learning
diﬀusion kernels. In International Conference on Scale Spaceand Variational Methods in Computer Vision, 2011.

DaLI: Deformation and Light Invariant Descriptor
2. M. Aubry, U. Schlickewei, and D. Cremers. The wave kernel
signature: A quantum mechanical approach to shape analysis. In Computer Vision Workshops (ICCV Workshops),
IEEE International Conference on, pages 1626–1633, Nov
2011.
3. H. Bay, T. Tuytelaars, and L. Van Gool. SURF: Speeded
up robust features. In European Conference on Computer
Vision, pages 404–417, 2006.
4. S. Belongie, J. Malik, and J. Puzicha. Shape matching andobject recognition using shape contexts. IEEE Transactions
Pattern Analysis and Machine Intelligence, 24(4):509–522,
2002.
5. A. Berg, T. Berg, and J. Malik. Shape matching and object
recognition using low distortion correspondences. In IEEE
Conference on Computer Vision and Pattern Recognition,
pages 26–33, 2005.
6. A. Bronstein, M. Bronstein, A. Bruckstein, and R. Kimmel.
Analysis of two-dimensional non-rigid shapes. International
Journal of Computer Vision, 78(1):67–88, 2007.
7. M. Bronstein and I. Kokkinos. Scale-invariant heat kernel
signatures for non-rigid shape recognition. In IEEE Conference on Computer Vision and Pattern Recognition, pages
1704–1711, 2010.
8. M. Bronstein C. Strecha, A. Bronstein and Pascal Fua. LDAHash: Improved matching with smaller descriptors. IEEE
Transactions Pattern Analysis and Machine Intelligence,34(1), 2012.
9. H. Cai, K. Mikolajczyk, and J. Matas. Learning linear discriminant projections for dimensionality reduction of image
descriptors. IEEE Transactions Pattern Analysis and Machine Intelligence, 33(2):338–352, 2011.
10. M. Calonder, V. Lepetit, M. Ozuysa, T. Trzcinski,
C. Strecha, and P. Fua. BRIEF: Computing a local binary
descriptor very fast. IEEE Transactions Pattern Analysis
and Machine Intelligence, 34(7):1281–1298, 2012.
11. I. Chavel. Eigenvalues in Riemannian Geometry. London
Academic Press, 1984.
12. H. Cheng, Z. Liu, N. Zheng, and J. Yang. A deformable local
image descriptor. In IEEE Conference on Computer Vision
and Pattern Recognition, 2008.
13. M. Cho, J. Lee, and K. Lee. Feature correspondence and deformable object matching via agglomerative correspondence
clustering. In International Conference on Computer Vision,
pages 1280–1287, 2009.
14. Fernando de Goes, Siome Goldenstein, and Luiz Velho. A hierarchical segmentation of articulated bodies. In Proceedingsof the Symposium on Geometry Processing, pages 1349–1356,
2008.
15. Bin Fan, Fuchao Wu, and Zhanyi Hu. Rotationally invariant
descriptors using intensity order pooling. IEEE Transactions
Pattern Analysis and Machine Intelligence, 34(10):2031–
2045, Oct 2012.
16. K. Gębal, J. A. Bærentzen, H. Aanæs, and R. Larsen. Shapeanalysis using the auto diﬀusion function. In Proceedings of
the Symposium on Geometry Processing, pages 1405–1413,
2009.
17. R. Gupta and A. Mittal. Illumination and Aﬃne-Invariant
Point Matching using an Ordinal Approach. In International
Conference on Computer Vision, 2007.
18. R. Gupta, H. Patil, and A. Mittal. Robust order-based methods for feature description. In IEEE Conference on Computer Vision and Pattern Recognition, 2010.
19. Raj Gupta and Anurag Mittal. Smd: A locally stable monotonic change invariant feature descriptor. In European Conference on Computer Vision, pages 265–277, 2008.
20. Marko Heikkilä, Matti Pietikäinen, and Cordelia Schmid. Description of interest regions with local binary patterns. Pattern Recognition, 42(3):425–436, March 2009.

19
21. Y. Ke and R. Sukthankar. PCA-SIFT: a more distinctive
representation for local image descriptors. In IEEE Conference on Computer Vision and Pattern Recognition, pages
506–513, 2004.
22. Iasonas Kokkinos, Michael Bronstein, and Alan Yuille. Dense
Scale Invariant Descriptors for Images and Surfaces. Research Report RR-7914, INRIA, March 2012.
23. A. Kovnatsky, M. Bronstein, A. Bronstein, and R. Kimmel.
Photometric heat kernel signatures. In International Conference on Scale Space and Variational Methods in Computer
Vision, pages 616–627, 2011.
24. M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In International Conference on Computer Vision, pages 1482–1489,
2005.
25. Bruno Lévy. Laplace-Beltrami Eigenfunctions: Towards an
Algorithm that Understands Geometry. In IEEE International Conference on Shape Modeling and Applications,page 13, June 2006.
26. H. Ling and D. Jacobs. Deformation invariant image matching. In International Conference on Computer Vision, pages
1466–1473, 2005.
27. H. Ling and D. Jacobs. Shape classification using the innerdistance. IEEE Transactions Pattern Analysis and MachineIntelligence, 29(2):286–299, 2007.
28. H. Ling, X. Yang, and L. Latecki. Balancing deformability
and discriminability for shape matching. In European Conference on Computer Vision, 2010.
29. R. Litman and AM. Bronstein. Learning spectral descriptors
for deformable shape correspondence. Pattern Analysis andMachine Intelligence, IEEE Transactions on, 36(1):171–180,
Jan 2014.
30. D. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91–
110, 2004.
31. K. Mikolajczyk and C. Schmid. A performance evaluation of
local descriptors. IEEE Transactions Pattern Analysis andMachine Intelligence, 10(27):1615–1630, 2005.
32. J. Morel and G. Yu. ASIFT: A new framework for fully aﬃneinvariant image comparison. SIAM Journal on Imaging Sciences, 2(2):438–469, 2009.
33. F. Moreno-Noguer. Deformation and illumination invariant
feature point descriptor. In IEEE Conference on Computer
Vision and Pattern Recognition, pages 1593–1600, 2011.
34. F. Moreno-Noguer and P. Fua. Stochastic exploration of ambiguities for nonrigid shape recovery. Pattern Analysis andMachine Intelligence, IEEE Transactions on, 35(2):463–475,
Feb 2013.
35. J. Philbin, M. Isard, J. Sivic, and A. Zisserman. Descriptor
learning for eﬃcient retrieval. In European Conference on
Computer Vision, pages 677–691, 2010.
36. U. Pinkall and K. Polthier. Computing discrete minimal
surfaces and their conjugates. Experimental Mathematics,
2(1):15–36, 1993.
37. Dan Raviv, Michael M. Bronstein, Nir Sochen, Alexander M.
Bronstein, and Ron Kimmel. Aﬃne-invariant diﬀusion geometry for the analysis of deformable 3d shapes. In IEEE
Conference on Computer Vision and Pattern Recognition,
2011.
38. M. Reuter, F. Wolter, and N. Peinecke. Laplace-beltrami
spectra as ’shape-dna’ of surfaces and solids. Computer Aided
Design, 38(4):342–366, 2006.
39. R. Rustamov. Laplace-beltrami eigenfunctions for deformation invariant shape representation. In Eurographics Symposium on Geometry Processing, pages 225–233, 2007.
40. J. Sanchez, J. Ostlund, P. Fua, and F. Moreno-Noguer. Simultaneous pose, correspondence and non-rigid shape. In

20IEEE Conference on Computer Vision and Pattern Recognition, pages 1189–1196, 2010.
41. E. Serradell, P. Glowacki, J. Kybic, F. Moreno-Noguer, andP. Fua. Robust non-rigid registration of 2d and 3d graphs. In
IEEE Conference on Computer Vision and Pattern Recognition, 2012.
42. L. Shi, Y. Yu, and N. Belland W.-W. Feng. A fast multigrid algorithm for mesh deformation. ACM SIGGRAPH,
25(3):1108–1117, 2006.
43. N. Sochen, R. Kimmel, and R. Malladi. A general framework
for low level vision. IEEE Transactions on Image Processing,7(3):310–318, 1998.
44. J. Sun, M. Ovsjanikov, and L. Guibas. A concise and provably informative multi-scale signature based on heat diﬀusion. In Eurographics Symposium on Geometry Processing,pages 1383–1392, 2009.
45. F. Tang, S. Hwan Lim, N. Chang, and H. Tao. A novel featuredescriptor invariant to complex brightness changes. In IEEE
Conference on Computer Vision and Pattern Recognition,
pages 2631–2638, 2009.
46. E. Tola, V. Lepetit, and P. Fua. Daisy: An eﬃcient dense descriptor applied to wide-baseline stereo. IEEE Transactions
Pattern Analysis and Machine Intelligence, 32(5):815–830,
2010.
47. L. Torresani, V. Kolmogorov, and C. Rother. Feature correspondence via graph matching: Models and global optimization. In European Conference on Computer Vision, pages
596–609, 2008.
48. Eduard Trulls, Iasonas Kokkinos, Alberto Sanfeliu, andFrancesc Moreno-Noguer. Dense segmentation-aware descriptors. In IEEE Conference on Computer Vision and
Pattern Recognition, 2013.
49. Eduard Trulls, Stavros Tsogkas, Iasonas Kokkinos, Alberto
Sanfeliu, and Francesc Moreno-Noguer. Segmentation-aware
deformable part models. In IEEE Conference on Computer
Vision and Pattern Recognition, 2014.
50. A. Vaxman, M. Ben-Chen, and C. Gotsman. A multiresolution approach to heat kernels on discrete surfaces.
ACM SIGGRAPH, 29(4):121, 2010.
51. A. Vedaldi and B. Fulkerson. VLFeat: An open and portablelibrary of computer vision algorithms. http://www.vlfeat.
org/, 2008.
52. A. Vedaldi and S. Soatto. Features for recognition: Viewpoint
invariance for non-planar scenes. In International Conference
on Computer Vision, pages 1474–1481, 2005.
53. Z. Wang, B. Fan, and F. Wu. Local intensity order pattern for feature description. In International Conference on
Computer Vision, pages 603 –610, 2011.
54. P. Wesseling. An Introduction to Multigrid Methods. John
Wiley & Sons, 2004.
55. S. Yanowitz and A. Bruckstein. A new method for image
segmentation. Computer Vision, Graphics, and Image Processing, 46(1):82–95, 1989.
56. A. Yezzi. Modified curvature motion for image smoothing
and enhancement. IEEE Transactions on Image Processing,7(3):345–352, 1998.

Edgar Simo-Serra et al.