Iasonas Kokkinos

Michael M Bronstein

Alan Yuille

Dense Scale Invariant Descriptors for Images and Surfaces

Keywords:

Local descriptors are ubiquitous in image and shape analysis, as they allow the compact and robust description of the local content of a signal (image or 3D shape). A common problem that emerges in the computation of local descriptors is the variability of the signal scale.

The standard approach to cope with this is scale selection, which consists in estimating a characteristic scale around the few image or shape points where scale estimation can be performed reliably. However, it is often desired to have a scale-invariant descriptor that can be constructed densely, namely at every point of the image or 3D shape.

In this work, we construct scale-invariant signal descriptors by introducing a method that does not rely on scale selection; this allows us to apply our method at any point. Our method relies on a combination of logarithmic sampling with multi-scale signal processing that turns scaling in the original signal domain into a translation in a new domain. Scale invariance can then be guaranteed by computing the Fourier transform magnitude (FTM), which is unaected by signal translations.

We use our technique to construct scale-and rotation-invariant descriptors for images and scaleand isometry-invariant descriptors for 3D surfaces, and demonstrate that our descriptors outperform state-of-the-art descriptors on standard benchmarks.

Introduction

Local descriptors have decisively pushed the envelope of solutions to computer vision and pattern recognition problems during the last decade. In image analysis, the emergence of descriptors that are robust to photometric changes and small displacements, able to cope with geometric (Euclidean or ane) transformations of the image, and the ecient coding schemes developed around them have facilitated the development of highly successful retrieval and matching applications [START_REF] Sivic | Video Google: a text retrieval approach to object matching in videos[END_REF][START_REF] Fraundorfer | A binning scheme for fast hard drive based image search[END_REF][START_REF] Jégou | A contextual dissimilarity measure for accurate and ecient image search[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], while aecting the whole eld of object recognition. In 3D shape analysis, 3D shape (surface) descriptors have been developed to describe local structure in a manner that is intrinsic, and thus invariant to isometric shape deformations, and used in applications such as shape retrieval [START_REF] Bronstein | Shape google: a computer vision approach to invariant shape retrieval[END_REF].

A problem that emerges both in image and shape analysis when extracting descriptors is the variability in scale (signal resolution). Scale is a nuisance parameter, and it is commonly desirable to eliminate its eect on the descriptors. The standard approach for coping with scale has been scale selection, as in the seminal works of Lindeberg [START_REF] Lindeberg | Feature Detection with Automatic Scale Selection[END_REF] and Lowe [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF], where some low-level image processing criterion estimates a characteristic scale around a few salient interest points. This scale is then used to adapt the region over which the descriptor is computed, and thereby scale invariance is achieved. Scale selection was also used by Sun et al. [START_REF] Sun | A Concise and Provably Informative Multi-Scale Signature Based on Heat Diusion[END_REF] in their work on heat kernel signature (HKS) surface descriptors.

We argue that the scale selection strategy has many limitations both in image and shape analysis, since most structures in images and shapes do not lend themselves easily to reliable scale estimation, with the exception of some special cases. In image analysis, such cases are symmetric structures such as blobs or ridges where scale can be naturally correlated with the structure width. However, other structures such as edges are inherently 1D, so it is hard to estimate their scale. In practice, this means that when relying on a scale selection approach, scale-invariant local descriptors can be constructed only at a sparse set of points where scale can be estimated accurately. However, it is often desired to have a dense scale-invariant descriptor that can be constructed at every point of the image or 3D shape; moreover, regular sampling strategies have outperformed sparse (interest point-based) ones in an empirical evaluation [START_REF] Nowak | Sampling strategies for bag-of-features image classication[END_REF].

In this paper, we take a dierent approach and compute scale-invariant descriptors without relying on scale selection. Instead we use a logarithmic (or log-polar) transformation of the signal domain that converts signal scalings (scalings and rotations, respectively) into translations, as

shown in Figure 1. The eects of translations can then be eliminated using the properties of the Fourier transform.

We exploit this observation to build descriptors for two dierent applications. In the rst part of the paper we present a dense scale-and rotation-invariant descriptor computed around image points. We build on the Daisy [START_REF] Tola | A fast local descriptor for dense matching[END_REF] descriptor to extract dense descriptors around all image points.

Unlike Daisy, our descriptor is scale-and rotation-invariant; and unlike scale-adapted SIFT-type descriptors, our descriptor can be extracted around any image point.

Our descriptor is thus both dense and invariant to image scalings and rotations, combining two desirable properties of SIFT and Daisy descriptors. A caveat related to our method is that our descriptor can get distorted around signal boundaries -we therefore assume that we are provided with large images and discard points on the image periphery. We demonstrate on a standard descriptor matching benchmark that our method outperforms state-of-the-art descriptors under a broad range of image transformations.

In the second part of the paper we introduce a scale-invariant descriptor for 3D surfaces, building on the intrinsic heat kernel signature (HKS) descriptor of [START_REF] Sun | A Concise and Provably Informative Multi-Scale Signature Based on Heat Diusion[END_REF]. By virtue of being intrinsic, i.e. depending solely on the Riemannian metric of the surface, HKS descriptors are invariant to isometric surface deformations, which include rotations and translations as special RR n°7914

cases. Moreover, HKS descriptors are applicable to a broad range of surface representations. We combine these favorable properties of HKS with scale invariance, giving rise to scale-invariant HKS (SI-HKS) [START_REF] Bronstein | Scale-invariant heat kernel signatures for non-rigid shape recognition[END_REF]. By combining SI-HKS descriptors with a bag-of-words model [START_REF] Ovsjanikov | Shape Google: a computer vision approach to invariant shape retrieval[END_REF], we obtain excellent performance on a non-rigid shape retrieval benchmark [START_REF] Bronstein | robust large-scale shape retrieval benchmark[END_REF].

This paper presents the culmination of our early results in [START_REF] Kokkinos | Scale Invariance without Scale Selection[END_REF] and [START_REF] Bronstein | Scale-invariant heat kernel signatures for non-rigid shape recognition[END_REF]. Comparing to [START_REF] Kokkinos | Scale Invariance without Scale Selection[END_REF],

we present dierent low-level image measurements (from the monogenic signal [START_REF] Felsberg | The monogenic signal[END_REF] to a more common Daisy-based [START_REF] Tola | A fast local descriptor for dense matching[END_REF] front end), and extend the method to compute dense descriptors.

Comparing to [START_REF] Bronstein | Scale-invariant heat kernel signatures for non-rigid shape recognition[END_REF], we also study the use of volumetric intrinsic descriptors, and provide new results on the SHREC'10 benchmark [START_REF] Bronstein | robust large-scale shape retrieval benchmark[END_REF].

We start our paper with an overview of existing works on local descriptors for images and surfaces in Section 2. We continue with a concise presentation of the scale-free scale-invariance principle for the case of a one-dimensional signal in Section 3 and proceed to describe how we use this idea to compute image and surface descriptors in Sections 4 and 5, respectively. In Section 6

we evaluate our approach on image and shape benchmark datasets.

Prior work

The main purpose of local descriptors in image and shape analysis is to summarize the information contained in the neighborhood of a point on a signal (image or 3D shape) into some low-dimensional feature vector, designed to be invariant to a certain class of transformations.

For instance, image descriptors employ image derivatives and normalization to deal with additive and multiplicative illumination variations, respectively, while surface descriptors deal with isometric surface deformations by relying on intrinsic geometric quantities such as heat kernels. In what follows we concisely describe the state-of-the-art in local image and 3D shape descriptors, and point out their shortcomings that our work aims at addressing.

Image Descriptors

Two seminal works in the development of image descriptors have been the Scale-Invariant Feature Transform (SIFT) [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF] and Shape Contexts [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF]. These descriptors perform `soft' perceptual grouping, aggregating boundary information into a statistical description amenable to subsequent tasks, such as shape matching and object recognition.

These works have been rened and extended in multiple ways. Geometric Blur descriptors [5] extended Shape contexts to work with image gradients instead of shape contours. GLOH descriptors [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF] used a log-polar grid to construct SIFT-like descriptors, SURF descriptors [3] used integral images for eciency, while [START_REF] Winder | Picking the best daisy[END_REF] used a search algorithm for the optimal combination of feature extraction, post-processing, and pooling. Moreover, dimensionality reduction [START_REF] Ke | PCA-SIFT: A More Distinctive Representation for Local Image Descriptors[END_REF], as well as linear [START_REF] Hua | Discriminant embedding for local image descriptors[END_REF][START_REF] Cai | Learning linear discriminant projections for dimensionality reduction of image descriptors[END_REF][START_REF] Brown | Discriminative learning of local image descriptors[END_REF] and nonlinear [START_REF] Philbin | Descriptor learning for ecient retrieval[END_REF][START_REF] Strecha | LDAHash: Improved matching with smaller descriptors[END_REF] metric learning techniques have led to performance improvements, while using low-dimensional descriptors.

An important recent development includes the construction of dense descriptors over the whole image domain instead of single points. The computational complexity is handled using efcient convolution operations, both for rectangular [START_REF] Fulkerson | Localizing objects with smart dictionaries[END_REF] and for log-polar grids [START_REF] Tola | A fast local descriptor for dense matching[END_REF]. We note that these methods do not guarantee scale-invariance, since the descriptor scale is xed beforehand.

Our method addresses this shortcoming.

Inria

Coming to scale invariance, a two-stage process is commonly used, following the seminal work of [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF]. First, a front end system is used to estimate local image scale, e.g. by using a scale-adapted dierential operator [START_REF] Lindeberg | Feature Detection with Automatic Scale Selection[END_REF]. Then, the estimated scale is used to adapt the domain over which the descriptor is computed. Variants of this idea include the identication of stable regions [START_REF] Matas | Robust wide-baseline stereo from maximally stable extremal regions[END_REF], entropy maximizing regions [START_REF] Kadir | Saliency, scale and image description[END_REF] or scale-invariant corners using the second momentmatrix [START_REF] Mikolajczyk | Scale and Ane Invariant Interest Point Detectors[END_REF]. In all cases a front-end process picks a certain scale which is then used for descriptor construction.

As we have argued in Section 1, this two-stage approach can often be problematic. In particular, around edges (and more generally, around non-symmetric points), there is no low-level criterion to reliably estimate image scale. Some notable exceptions include the works of [START_REF] Ling | Using the inner-distance for classication of articulated shapes[END_REF][START_REF] Mikolajczyk | Shape recognition with edge-based features[END_REF][START_REF] Dorkó | Maximally stable local description for scale selection[END_REF],

which, however, either implicitly exploit symmetry in order to work on edges ( [START_REF] Mikolajczyk | Shape recognition with edge-based features[END_REF]), or require time-demanding operations to achieve invariance ( [START_REF] Dorkó | Maximally stable local description for scale selection[END_REF][START_REF] Ling | Using the inner-distance for classication of articulated shapes[END_REF]). Instead, our approach provides a generic, feature-independent process to estimate scale-invariant descriptors, does not rely on adhoc scale-selection criteria, and can be eciently implemented using the Fast Fourier Transform.

Shape Descriptors

The success of feature-based methods in image analysis has driven a more recent trend of developing similar methods for the analysis of 3D shapes in the computer graphics and geometry processing communities. Feature descriptors play an important role in shape correspondence and matching [START_REF] Thorstensen | Non-rigid shape matching using geometry and photometry[END_REF][START_REF] Huang | Reassembling fractured objects by geometric matching[END_REF] and retrieval [START_REF] Mitra | Probabilistic ngerprints for shapes[END_REF][START_REF] Ovsjanikov | Shape Google: a computer vision approach to invariant shape retrieval[END_REF][START_REF] Toldo | Visual vocabulary signature for 3D object retrieval and partial matching[END_REF], where the bag of features paradigm [START_REF] Sivic | Video Google: a text retrieval approach to object matching in videos[END_REF][START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF] has been successfully employed.

On the one hand, it is possible to apply almost straightforwardly some successful image analysis methods to 3D shapes. Notable examples of feature detectors and descriptors that follow analogous methods in image analysis include corners [START_REF] Sipiran | A robust 3D interest points detector based on Harris operator[END_REF] and edges [START_REF] Kolomenkin | On edge detection on surfaces[END_REF], histograms of gradients [START_REF] Zaharescu | Surface feature detection and description with applications to mesh matching[END_REF] (akin to the use of [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF] for images), 3D integral invariants [START_REF] Gelfand | Robust global registration[END_REF] (rst proposed in images in [START_REF] Manay | Integral invariant signatures[END_REF]), and maximally stable extremal regions (MSER) [START_REF] Digne | The Level Set Tree on Meshes[END_REF][START_REF] Litman | Diusion-geometric maximally stable component detection in deformable shapes[END_REF].

On the other hand, it is possible to use 3D shape specic geometric structures for designing feature detectors and descriptors that have no direct image analogs. An ideal feature descriptor should be invariant to shape embedding in the 3D space, which includes Euclidean invariance, namely invariance to rotation and translation, and deformation invariance, namely invariance to inelastic deformations that preserve the metric structure of the surface (isometries). As deformation invariance guarantees Euclidean invariance, we focus on the former. Second, a descriptor should cope with missing parts, and also be insensitive to topological noise and connectivity changes in the shape (referred together as topological invariance). Third, it should work across dierent shape representations and formats (e.g. point clouds and meshes) and be insensitive to sampling (representation invariance). Finally, the descriptor should be invariant to global and local shape scaling (scale invariance).

Rotation and translation invariance can be achieved using volume and area descriptors [START_REF] Zhang | Ecient feature extraction for 2D/3D objects in meshrepresentation[END_REF],

spherical harmonics [START_REF] Kazhdan | Rotation invariant spherical harmonic representation of 3D shape descriptors[END_REF], geometric moments [START_REF] Tal | Content based retrieval of VRML objects -an iterative and interactive approach[END_REF], and distribution of pair-wise Euclidean distances [START_REF] Osada | Shape distributions[END_REF].

Deformation invariance is more challenging. In [START_REF] Elad | Bending invariant representations for surfaces[END_REF], and later [START_REF] Mémoli | A theoretical and computational framework for isometry invariant recognition of point cloud data[END_REF][START_REF] Bronstein | Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching[END_REF] shapes were modeled as metric spaces with geodesic distances, which are invariant to inelastic deformations. This framework was used in [START_REF] Ling | Using the inner-distance for classication of articulated shapes[END_REF] and [START_REF] Bronstein | Analysis of twodimensional non-rigid shapes[END_REF] with a metric dened by internal distances in 2D shapes, while [START_REF] Reuter | Laplace-spectra as ngerprints for shape matching[END_REF][START_REF] Reuter | Discrete LaplaceBeltrami operators for shape analysis and segmentation[END_REF] used the Laplacian spectra as intrinsic shape descriptors.

In [START_REF] Coifman | Diusion maps[END_REF] the authors popularize the notion of diusion geometry, arising from the analysis of heat diusion processes on manifolds and giving rise to intrinsic local and global structures. In [START_REF] Rustamov | Laplace-Beltrami eigenfunctions for deformation invariant shape representation[END_REF][START_REF] Mahmoudi | Three-dimensional point cloud recognition via distributions of geometric distances[END_REF][START_REF] Bronstein | A Gromov-Hausdor framework with diusion geometry for topologically-robust non-rigid shape matching[END_REF][START_REF] Bronstein | Shape recognition with spectral distances[END_REF] global shape representations using dierent diusion distances were proposed.

In [4] a conformal factor scalar descriptor is used, which is scale-invariant, but applicable RR n°7914

0 10 20 -1 0 1 f(x) -4 -2 0 2 -0.5 0 0.5 f 1 (x)
Figure 1: Demonstration of how the logarithmic transformation turns scalings into translations: on the left we have two functions f (x) = cos(x) (red),g(x) = cos(2x) (blue), diering by a scaling factor of two. By employing the signal transformation fa(x) = f (log(ax)) we obtain f1(x) = cos(log(x)), g1(x) = cos(log(x) -log 2), which only dier by a translation.

to shapes of xed (e.g. sphere-like) topology and thus not topology-invariant. In [START_REF] Sun | A Concise and Provably Informative Multi-Scale Signature Based on Heat Diusion[END_REF] (and independently, [START_REF] Gebal | Shape analysis using the auto diusion function[END_REF]), local multiscale heat kernel signature (HKS) descriptors were constructed using the heat diusion equation. This approach was later generalized to shapes with texture in [START_REF] Kovnatsky | Photometric heat kernel signatures[END_REF]. HKS descriptors satisfy all of the above desired properties with the exception of scale invariance. In [2] the Shrödinger equation instead of the heat equation is considered, resulting in wave kernel signatures (WKS). Finally, [START_REF] Aalo | Deformable shape retrieval by learning diusion kernels[END_REF]6] show that both HKS and WKS can be regarded as a lter applied to the Laplace-Beltrami eigenvalues, and show that an optimal lter can be designed from examples by means of supervised learning.

In this paper, we show how to build a scale-invariant HKS descriptor. Our approach can be extended to other descriptors based on the Laplace-Beltrami operator.

3 Scale-Free Scale Invariance

Consider that we want to describe a one-dimensional signal f (x), x > 0 in a manner that does not change when the signal is scaled as f (x/a), a > 0. For this we consider a logarithmic transformation h(x) = log(x) of the domain. Denoting by f a the transformation of f (x/a), i.e. f a (h(x)) . = f (x/a), we have:

f a (h(ax)) = f (x) = f 1 (h(x)) (1)
Since a > 0, x > 0 we can rewrite (1) as:

f a (x ′ + log(a)) = f 1 (x ′ ), (2)
where x ′ = log(x). As illustrated in Figure 1, scaling the signal f (x) by a thus amounts to translating the signal f 1 (x ′ ) by -log(a). We can then obtain a scale-invariant description of f (x) in terms of the Fourier transform of f 1 (x ′ ); applying the shifting-in-time property of the Fourier transform to (2) gives:

F a (ω)e j log(a)ω = F 1 (ω), (3)
|F a (ω)| = |F 1 (ω)|, (4)

Inria

where F a (ω) is the Fourier transform of f a (x). As per (4), the dependency on a has vanished.

This idea underlies the Fourier Transform Magnitude (FTM) technique, which has been used

to deal with global image rotation and scaling in the context of image registration [START_REF] Casasent | Position, rotation, and scale invariant optical correlation[END_REF][START_REF] Wolberg | Robust image registration using log-polar transform[END_REF] and texture classication [START_REF] Porat | The generalized gabor scheme of image representation in biological and machine vision[END_REF]. One of our main contributions lies in applying this idea locally, at the level of local feature descriptors.

Discrete descriptors

So far our treatment has considered continuous signals. To deal with discrete signals we need to take into account the eects of sampling.

To avoid aliasing, the signals must be smoothed prior to sampling [START_REF] Oppenheim | Discrete-Time Signal Processing[END_REF]. For equispaced samples the proper amount of smoothing is determined by the Nyquist theorem: the smoothing acts as a low-pass lter that cuts o the signal spectral content above the Nyquist frequency.

However, in our case we sample the signal irregularly, namely at a set of locations forming a geometric progression, as detailed below in (6). We show that in our setting we can guarantee scale-invariance if we use a multi-scale smoothing scheme, where points close to 0 are subjected to small amount of smoothing, and points further out to stronger smoothing; this relates to the `foveal' scale space of [START_REF] Lindeberg | Foveal scale-space and the linear increase of receptive feld size as a function of eccentricity[END_REF] as well as to Geometric Blur [5].

We consider the scale-space f (x, s) formed by convolving f (x) with a set of kernels g s (x) =

1 s g 1 (x/s): f (x, s) = f (x) * g s (x). (5)
We propose to sample f (x) through f (x, s) as follows:

f [n] = f (c 0 α n , cα n ), (6)
where f [n] is the sampled version of our original signal f (x). As mentioned above, we use a geometric spacing of samples while smoothing proportionally to the distance from 0.

Denoting by f α [n] the signal obtained by sampling f (x/α), we prove in the Appendix that Finally, since we work with nitely supported signals, we face signal boundary eects; we discuss these as appropriated to image and surface descriptors. 4 Scale-Invariant Image Descriptors

f α k [n] = f 1 [n -k],
In Section 3 we have described a general approach to achieving scale-invariance for 1D signals.

We now elaborate on how we exploit this to achieve scale-and rotation-invariance on images.

For this, we construct a descriptor around a point by sampling its neighborhood with a log-polar grid, as shown in Figure 2. This sampling scheme turns image rotations/scalings into translations, allowing us to use the FTM technique to achieve rotation-and scale-invariance. We note that the log-polar transform has already been used to deal with global scale and rotation changes [START_REF] Casasent | Position, rotation, and scale invariant optical correlation[END_REF][START_REF] Porat | The generalized gabor scheme of image representation in biological and machine vision[END_REF][START_REF] Wolberg | Robust image registration using log-polar transform[END_REF][START_REF] Kannan | Fast transformation-invariant factor analysis[END_REF], while in [START_REF] Schwartz | Spatial mapping in the primate sensory projection: analytic structure and relevance to perception[END_REF] it is associated with the foveal sampling pattern of the retina. Our contribution lies in exploiting this scheme for local descriptor construction.

As illustrated in Figure 2, we construct a descriptor around a point x = (x 1 , x 2 ) by sampling its neighborhood along K rays leaving x at equal angle increments θ k = 2πk/K. Along each ray we sample the image at N points with distances r n = c 0 a n from x, using distance-dependent RR n°7914

h +,0 [k, n] h +,2 [k, n] Scale index, k Scale index, k Ray index, n Ray index, n
Figure 2: Eect of scale and orientation changes on log-polar descriptors. On the left we show as needle diagrams the descriptors computed on a point before and after scaling and rotating an image; needle length is proportional to the quantity in [START_REF] Bronstein | Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching[END_REF]. In the next two columns we show two of the descriptor components computed by [START_REF] Bronstein | Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching[END_REF]. The eect of scaling and rotation amounts to a translation, which can be eliminated by using the 2D Fourier transform. As the point is arbitrary (i.e. not a corner/junction/blob center), performing scale selection around it would be far from obvious.

Inria Figure 3: The orientations used in directional derivative computation are set relative to ray orientation, so that image rotation will amount to feature translation; here we show the rst two directions on four dierent rays.

smoothing with a 2D Gaussian kernel of standard deviation σ n = αr n . These measurements form a K × N matrix:

h[k, n] = f αrn [x 1 + r n cos(θ k ), x 2 + r n sin(θ k )] , (7)
where f σ denotes the sampled eld f smoothed by σ.

Since we sample according to Section 3.1, rescaling the signal f will amount to shifting h along the second (n/scale) dimension. Moreover, since the rays are equally spaced, rotating the image around x by 2π K amounts to shifting h along the rst (k/orientation) dimension by one. Image scalings and rotations thus turn into horizontal and vertical translations of h.

We can therefore use the FTM technique to locally describe the image in a scale-and rotationinvariant manner. In specic, from the time-shifting property of the DTFT [START_REF] Oppenheim | Discrete-Time Signal Processing[END_REF], we know that if h[k, n] F ↔ H(jω k , jω n ) are a DTFT pair, we will then have:

h[k -c, n -d] F ↔ H(jω k , jω n )e -j(ω k c+ωnd) (8)
so taking the absolute of the DTFT yields a scale-and rotation-invariant quantity.

In practice our descriptor is not perfectly invariant to scale changes, due to the limited number of scales considered. As the right columns of Figure 2 illustrate, scaling an image introduces new observations at ne scales and removes others at coarse scales. As experimentally demonstrated in Section 6, despite this approximation, our descriptor systematically outperforms SIFT for scale changes up to an order of 3.

Furthermore, descriptors lying close to the image boundaries can be largely aected by boundary eects; we restrain our evaluation to descriptors lying suciently far from the boundaries, leaving the proper imputation of missing values to future work.

Directional Derivative Information

The descriptor described so far is scale-and rotation-invariant, but not illumination invariant.

Following [5,[START_REF] Brown | Discriminative learning of local image descriptors[END_REF][START_REF] Tola | A fast local descriptor for dense matching[END_REF], we combine the computation of directional derivatives with polarization, i.e. separating the negative and positive parts. Directional derivatives are invariant to additive intensity changes and provide information about the signal's dominant orientations. Polarization gave consistent improvements [START_REF] Brown | Discriminative learning of local image descriptors[END_REF], which can be attributed to segregating upwards and downwards trends in the signal values.

Using directional derivatives has two implications. First, we need to align the directional derivatives with the ray directions as shown in Figure 3; this ensures that image rotation amounts RR n°7914 to feature translation -i.e. the features are rotation-covariant. Concretely, on ray k we use as d-th feature orientation the angle θ

d,k = k 2π K + d 2π D .
The computation of directional derivatives at all angles is eciently performed by exploiting the steerability of directional derivatives of the Gaussian.

Second, the magnitude of the derivative signals will decrease for larger scales, as the derivated signal becomes increasingly smooth. An analysis similar to [START_REF] Lindeberg | Feature Detection with Automatic Scale Selection[END_REF] therefore suggests scaling the output of smoothing by the root of the kernel's standard deviation, σ.

Coming to the treatment of multiplicative image changes, we normalize by dividing with the L 2 norm of the descriptor elements. As also mentioned in [START_REF] Tola | A fast local descriptor for dense matching[END_REF], we have observed that normalizing over each ring separately gives better results than normalizing over all rings.

Descriptor Construction

We rst briey summarize the steps used for the construction of our descriptor. We omit some technical implementation aspects, as we make our image descriptor code publicly available.

For a given scale n we smooth the image at a scale σ n = ar n , r n = c 0 a n , giving rise to I σn . To gather samples on ray k and scale n we compute the directional derivatives of

I σn for D orientations, θ d,k = k 2π K + d 2π D ,
h ±,d x [k, n] = σ n f ±,θ d,k σn [x 1 + r n cos(θ k ), x 2 + r n sin(θ k )] , (9)
where k ∈ {1, . . . K}, n ∈ {1, . . . N }, with K the number of rays and N the number of rings. Put together, this gives a 2KDN -dimensional descriptor per point. We form our descriptor at x by (a) computing the 2D Discrete Fourier Transform (DFT) for every [±, j] combination, (b) keeping the DFT elements corresponding to DTFT frequencies (ω k , ω n ) ∈ [0, 2π] × [0, π) -due to the symmetry of the Fourier transform and (c) concatenating all components in a single vector.

We use N = 36 rays, D = 4 orientations and K = 28 rings, which results in a 7168dimensional descriptor. This descriptor is largely redundant and could be compressed using dimensionality reduction techniques [START_REF] Hua | Discriminant embedding for local image descriptors[END_REF][START_REF] Cai | Learning linear discriminant projections for dimensionality reduction of image descriptors[END_REF][START_REF] Philbin | Descriptor learning for ecient retrieval[END_REF][START_REF] Brown | Discriminative learning of local image descriptors[END_REF][START_REF] Strecha | LDAHash: Improved matching with smaller descriptors[END_REF] -we leave this for future work.

Coming to computational cost, we note that the features required to form our descriptor in [START_REF] Bronstein | Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching[END_REF] can be obtained in batch mode with ecient recursive ltering [START_REF] Geusebroek | Fast anisotropic gauss ltering[END_REF] and steering. As an indicative measure of relative time performance, we report the timings for the demo script contained in our distribution: for an image of size 700x1000 all convolutions cost approximately 0.8 seconds; the formation of ∼ 23000 (136× 170 regularly-spaced) descriptor elements 1.2 seconds; steering and normalization 6.2 seconds; and the FFT 3 seconds. In sum, we obtain 23000 scale-invariant descriptors in close to 10 seconds. The most time-consuming part is Matlab-based, and could be accelerated in C, while the descriptor construction is easy to parallelize.

In Figure 4 we show the values of the lowest frequency (and highest-energy) coecients of densely computed descriptors, as evaluated on two images. We see that their values are eectively invariant to image rotations and scalings, despite a scaling factor in the order of 2. In the bottom row, we use the two points on the left image as references and `query' the right one for points having similar descriptors. We then show the similarity of `query' point descriptors to the red (left) and the green (right) reference points, which indicates the discriminative ability of the descriptor -even though locally the structures are similar, the context helps disambiguate them.

A thorough experimental evaluation of our descriptor follows in Section 6.1.

Inria

Reference Image Query Image

Dense Descriptors, ωn = 1,

ω k = 1, d ∈ {1, 2, 3} Dense Descriptors, ωn = 1, ω k = 2, d ∈ {1, 2, 3}
Query similarity to red (left) and green (right) reference points. In this Section we detail how Scale-Free Scale-Invariance can be applied to the computation of scale-invariant local shape descriptors. As mentioned in Section 2, the Heat Kernel Signatures of [START_REF] Sun | A Concise and Provably Informative Multi-Scale Signature Based on Heat Diusion[END_REF] satisfy deformation invariance and representation invariance, but not scale invariance.

Our contribution consists in making HKS scale-invariant. We rst provide a concise description of HKS alongside with their numerical computation, and then describe our scale-invariant modication of HKS.

Heat Kernel Signatures

Let us model the shape of a 3D physical object as a connected and compact region X ⊂ R 3 , whose boundary ∂X is a closed connected two-dimensional Riemannian manifold. Traditionally, shape deformations are modeled as isometries of the 2D boundary surface ∂X preserving its Riemannian metric structure ∂X (we refer to such deformations as boundary isometries). Such

RR n°7914

Figure 5: Invariance of the rst three components of the HKS (shown as R, G, and B channels, respectively), for a shape undergoing isometric transformations.

deformations can bend the surface of the shape but not stretch it; however, the volume bounded by ∂X can change. Works on feature descriptors thus mainly focus on dening such geometric structure that would be intrinsic (i.e., expressible solely in terms of the Riemannian metric of

∂X) and consequently, invariant to boundary isometries of ∂X.

A recent line of works [START_REF] Reuter | Laplace-spectra as ngerprints for shape matching[END_REF][START_REF] Coifman | Diusion maps[END_REF][START_REF] Lévy | Laplace-Beltrami eigenfunctions towards an algorithm that understands geometry[END_REF][START_REF] Rustamov | Laplace-Beltrami eigenfunctions for deformation invariant shape representation[END_REF][START_REF] Ovsjanikov | Global intrinsic symmetries of shapes[END_REF][START_REF] Sun | A Concise and Provably Informative Multi-Scale Signature Based on Heat Diusion[END_REF][START_REF] Bronstein | Scale-invariant heat kernel signatures for non-rigid shape recognition[END_REF] studied intrinsic descriptions of shapes by analyzing heat diusion processes on ∂X. Such processes give rise to the so-called diusion geometry and arise from the heat equation

( ∂ ∂t + ∆ ∂X ) u(t, x) = 0, (10)
where u(t, x) : [0, ∞) × ∂X → [0, ∞] is the heat value at a point x in time t, and ∆ ∂X is the positive-semidenite Laplace-Beltrami operator associated with the Riemannian metric of ∂X.

The Laplace-Beltrami operator ∆ ∂X is intrinsic to the two-dimensional manifold ∂X, meaning that it is expressible in terms of the metric of ∂X. Consequently, it is invariant under boundary isometries.

The solution h t (x, y) of ( 10) corresponding to a point initial condition u(0, x) = δ(x, y), is called the heat kernel and represents the amount of heat transferred on ∂X from x to y in time t due to the diusion process.

In particular, the diagonal of the heat kernel h t (x, x) (i.e., setting x = y, also referred to as the auto-diusivity) describes the amount of heat remaining at point x after time t. Its value is related to the Gaussian curvature K(x) through h t (x, x) ≈ 1 4πt

( 1 + 1 6 K(x)t + O(t 2 )
)

, expressing the well-known property that heat tends to diuse slower at points with positive curvature, and faster at points with negative curvature.

The spectral decomposition of the Laplace-Beltrami operator ∆ ∂X produces a set of orthonormal eigenfunctions ϕ 0 = const, ϕ 1 , ϕ 2 , ... and corresponding eigenvalues λ 0 = 0 ≤ λ 1 ≤ λ 2 ... satisfying ∆ ∂X ϕ i = λ i ϕ i . These eigenfunctions form a basis on L 2 (∂X) analogous to the Fourier Inria basis on Euclidean domains, where the heat kernel has the following expansion [START_REF] Lévy | Laplace-Beltrami eigenfunctions towards an algorithm that understands geometry[END_REF]:

h t (x, y) = ∑ i≥0 e -λit ϕ i (x)ϕ i (y). (11)
Sun et al. [START_REF] Sun | A Concise and Provably Informative Multi-Scale Signature Based on Heat Diusion[END_REF] used the diagonal of the heat kernel as a local surface descriptor referred to as heat kernel signature (HKS). The HKS descriptor at each point x of the surface ∂X is dened as a q-dimensional vector H(x) = (h t1 (x, x), ..., h tq (x, x)), [START_REF] Bronstein | Shape recognition with spectral distances[END_REF] where t 1 , ..., t q is a set of time scales. As illustrated in Figure 5, H(x) captures shape curvature information in a isometry-invariant manner. Furthermore, by virtue of being intrinsic, the HKS is invariant to boundary isometries of ∂X. Equation ( 11) allows for ecient computation of the heat kernel, which in practice requires computing the rst few eigenpairs of the Laplace-Beltrami operator.

Volumetric Heat Kernel Signatures

Raviv et al. [START_REF] Raviv | Volumetric heat kernel signatures[END_REF] argued that a smaller class of volume isometries preserving the metric structure inside the volume X are more suitable for modeling realistic shape deformations that boundary isometries, which preserve the area of ∂X, but not necessarily the volume of X (volume isometries are necessarily boundary isometries, but not vice versa). Thus, instead of considering diusion processes on the boundary surface ∂X, diusion inside the volume X, arising from the Euclidean volumetric heat equation with Neumann boundary conditions,

( ∂ ∂t + ∆ ) U (t, x) = 0 x ∈ int(X); ⟨∇U (t, x), n(x)⟩ = 0 x ∈ ∂X, ( 13
)
was considered in [START_REF] Raviv | Volumetric heat kernel signatures[END_REF] (here, U (t, x) : [0, ∞) × R 3 → [0, ∞] is the volumetric heat distribution, ∆ is the Euclidean positive-semidenite Laplacian, and n(x) is the normal to the surface ∂X at point x. In the following, we use capital letter to denote the volumetric quantities). The heat kernel of the volumetric heat equation ( 13) is given, similarly to (11) by

H t (x, y) = ∑ i≥0 e -Λit Φ i (x)Φ i (y), (14)
where Φ i and Λ i are the eigenfunctions and eigenvalues of ∆ satisfying ∆Φ i = Λ i ϕ i and the boundary conditions ⟨∇Φ i (x), n(x)⟩ = 0. The diagonal of the heat kernel H t (x, x) gives rise to the volumetric HKS (vHKS) descriptor [START_REF] Raviv | Volumetric heat kernel signatures[END_REF], which is invariant to volume isometries of X.

Compared to the 2D HKS, such descriptors were shown to be less sensitive to geometric and topological noise [START_REF] Raviv | Volumetric heat kernel signatures[END_REF].

Scale invariance

A notable disadvantage of heat kernel descriptors (both HKS and vHKS) is their sensitivity to scale. Given a shape X and its version X ′ uniformly scaled by the factor of a, it is easy to establish that the eigenfunctions and eigenvalues are scaled inversely proportionally to the area

The rst relation stems from normalization of the Laplace-Beltrami operator; the second relation stems from the unit norm of the eigenfunctions, of ∂X (∝ a 2 ) or the volume of X (∝ a 3 ), respectively. Thus, the new set of the eigenfunctions and eigenvalues of X ′ is given by

∥ϕ i ∥ L 2 (∂X) = ∥Φ i ∥ L 2 (X) = 1.

RR n°7914

λ ′ = a -2 λ; ϕ ′ = a -1 ϕ; (15) Λ ′ = a -2 Λ; Φ ′ = a -3/2 Φ, (16)
so the corresponding heat kernels satisfy

h ′ t (x) = ∞ ∑ i=0 e -λia -2 t ϕ 2 i (x)a -2 = a -2 h a -2 t (x), (17)
H ′ t (x) = ∞ ∑ i=0 e -Λia -2 t Φ 2 i (x)a -3 = a -3 H a -2 t (x), (18)
relating the signature h ′ (respectively, H ′ ) at time t for X ′ with the signature h (respectively, H) at time a -2 t for X.

Typically, the scaling factor a is unknown a priori. Scale dependence can be removed by global normalization, for example, dividing the eigenfunctions and eigenvalues by the rst non-zero eigenvalues,

λ i = λ i λ -1 1 and ϕ i = ϕ i λ -1 1 (Λ i = Λ i Λ -1 1 and Φ i = Φ i Λ -1
1 , respectively). However, global normalization does not work in cases when the shape undergoes transformations changing its global geometry, such as removing signicant parts in these cases, the resulting eigenvalues and eigenfunctions can be very dierent. One thus has to resort to local normalization.

One possibility is to locally normalize the metric structure of the manifold. This approach has been explored by Raviv et al. [START_REF] Raviv | Ane-invariant diusion geometry for the analysis of deformable 3d shapes[END_REF], who constructed an ane-invariant Riemannian metric tensor on the manifold (rather then using the metric induced by the embedding) and derived an ane-invariant diusion geometry form the associated Laplace-Beltrami operator. Another possibility is, similarly to image descriptors, to estimate scale locally from a feature detection algorithm. However, in shape analysis there is no clear analogue for features such as blobs or corners, and such an estimation is not always possible. Moreover, as mentioned before, in many cases we are interested in dense descriptors computed at all points. Inria HKS SI-HKS We observe that the SI-HKS descriptors are substantially more robust to the deformations and stay closer to the null shape descriptor.

Scale-invariant Heat Kernel Signatures

We now describe a method to discard the dependence of h (or H) on the unknown scaling factor a following the approach outlined in Section II, resulting in a scale-invariant heat kernel signature (SI-HKS). We develop our construction for the HKS; scale-invariant vHKS can be obtained in a similar way.

First, at each point x we sample the heat kernel scale logarithmically with some basis α, denoted here as h(τ ) = h α τ (x, x). In this scale-space, the heat kernel of the scaled shape becomes h ′ (τ ) = a -2 h(τ + 2 log α a) (Fig. 6, left). Second, in order to remove the dependence on the multiplicative constant a -2 , we take the logarithm of the signal and then dierentiate it w.r.t. the scale variable,

d dτ log h ′ (τ ) = d dτ (-2 log a + log h(τ + 2 log α a)) = d dτ h(τ + 2 log α a) h(τ + 2 log α a) . ( 19
)
Denoting

h(τ ) = d dτ h(τ ) h(τ ) = - ∑ i≥0 λ i α τ log αe -λiα τ ϕ 2 i (x) ∑ i≥0 e -λiα τ ϕ 2 i (x)
, we thus have a new function h which transforms as h′ (τ ) = h(τ + 2 log α a) as a result of scaling (Fig. 6, center). Finally, using the idea of Section II, we apply the Fourier transform to h and take its absolute value,

F[ h′ ](ω) = H′ (ω) = H(ω)e -jω2 log α a , ( 20
) | H′ (ω)| = | H(ω)|, (21)
producing a scale-invariant descriptor (Fig. 6, right).

RR n°7914

One caveat of this approach could be that scaling the shape and then resampling the function ḣ[τ ] makes the samples at the boundaries change. Fortunately, the HKS is smooth at low-and high-scales and therefore its derivative is equal to zero for a broad range of τ s at the beginning and end of ḣ. In Fig. 6 we show the intermediate signals involved in the construction of the SI-HKS.

Numerical computation

Due to the possibility to express the heat kernel in the spectral domain, the practical computation of HKS or vHKS and their scale-invariant versions boils down to discretizing the Laplacian of the shape, computing its rst eigenvectors and eigenvalues, and approximating formulae [START_REF] Bronstein | Shape google: a computer vision approach to invariant shape retrieval[END_REF] or ( 14) using a nite number of terms (since the exponential coecients, only a small number of eigenfunctions and eigenvalues is required). Since there exists a plethora of methods for Laplacian discretization on dierent representations of shapes (in particular, meshes, point clouds, volumes, and implicit surfaces), the heat kernel descriptors are very versatile and, up to errors of the particular Laplacian approximation, representation-invariant.

In the case of surfaces represented as point clouds V = {v 1 , ..., v N } ⊂ ∂X or triangular meshes, the discretization of the Laplace-Beltrami operator of the surface ∂X can be written in the generic matrix-vector form as

∆ ∂X f = A -1 W f , where f = f (v i ) is a vector of values of a scalar function f : ∂X → R sampled on the vertices, W = diag ( ∑ l̸ =i w il ) -(w ij
) is a zero-mean N × N matrix of weights, and A = diag(a i ) is a diagonal matrix of normalization coecients [START_REF] Floater | Surface parameterization: a tutorial and survey[END_REF][START_REF] Wardetzky | Discrete Laplace operators: no free lunch[END_REF]. A particular choice that is popular in computer graphics for triangular meshes is the cotangent weight scheme [START_REF] Pinkall | Computing discrete minimal surfaces and their conjugates[END_REF][START_REF] Meyer | Discrete dierential-geometry operators triangulated 2-manifolds[END_REF], where

w ij = { (cot α ij + cot β ij )/2 (v i , v j ) is an edge; 0 else, (22)
where α ij and β ij are the two angles opposite to the edge between vertices v i and v j in the two triangles sharing the edge, and a i are the discrete area elements. The eigenfunctions and eigenvalues of ∆ ∂X are found by solving the generalized eigendecomposition problem W ϕ i = Aϕ i λ i [START_REF] Lévy | Laplace-Beltrami eigenfunctions towards an algorithm that understands geometry[END_REF].

In the volumetric case, the shapes are rasterized and represented as arrays of voxels on a regular Cartesian grid, allowing to use the standard Euclidean Laplacian. In [START_REF] Raviv | Volumetric heat kernel signatures[END_REF], the volumetric Laplacian was discretized using a 6-neighborhood stencil, and boundary conditions were enforced using the shadow variables technique.

6 Results

Image Descriptor Evaluation

We use the dataset, code and protocol of [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF] to evaluate descriptor performance: ground truth correspondences between two images of an identical scene are used to evaluate interest point matches found based on descriptor similarities. Even though our descriptors can be computed densely, we use the Hessian-and Harris-Laplace interest point operators of [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF], in order to compare with SIFT descriptors on equal grounds. We do not compare with Hessian-and Harrisane detectors, as our descriptors are not designed to cope with ane transformations.

An issue regarding evaluation is that these two detectors provide as output points associated with scale (`regions'), while our descriptor is only using point information in its construction.

Two points lying at the same location (modulo the transformation registering the images), but Inria

d i,j < θ d (Ours ) d i,j ≥ θ d (Ours ×) O i,j ≥ θ 0 (SIFT ) × O i,j < θ 0 (SIFT ×) × Table 1:
Conditions for incorporating pair i, j in the evaluation. di,j stands for the Euclidean distance between the centers of points i, j and Oi,j for the overlap of their regions, while θ d and θO are the respective thresholds.

with very dierent scales are considered dierent by the evaluation approach of [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF]: a match of two such points is declared a false positive. However, as far as our descriptors can tell, these two such points are identical, as they correspond to the same scene point. On the ip side, due to the log-polar sampling, our descriptors are location-sensitive, while SIFT descriptors of large regions are less aected by displacements.

To make the two methods of computing scale-invariant descriptors commensurate we distinguish four cases, as indicated in Table 1. In our evaluation we only consider pairs of points where either both criteria are met (point centers are close, and their areas overlap substantially), or both criteria are violated (points centers are far, and their areas have low overlap). We exclude points where one criterion is met, while another is not (e.g. having close centers, but low area overlap).

This amounts to some 5-10% of positive point pairs being excluded from the evaluation.

Moreover, as mentioned in Section 4.2, our descriptor gets distorted around the image boundaries. One obvious remedy could be to decrease the size of the used log-polar grid. This comes at the cost of reducing the contextual information captured by our descriptor, while limiting the range of scale changes that can be dealt with.

In our experiments we use images of approximately 700x1000 and 1000x1000 pixels, while our descriptor's maximal ring size is at a radius of 230 pixels. In our evaluation we only consider descriptors of points which lie at least 100 pixels from the closest image boundary, accounting for roughly 60%-85% of points within an image. This ensures that the associated descriptors are not largely distorted, and deconvolves the evaluation of our descriptors scale-invariance from the boundary eects. When cutting the pixel distance from 100 down to 50 we observed a deterioration of our results, in particular for large scale changes.

Three alternative methods are proposed in [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF] to nd correspondences. The simplest one (`similarity') computes all distances between the descriptors in the two images and declares as matches all pairs of points whose distance is below a given threshold. A more elaborate technique (`k-nearest') rst solves a linear assignment problem, allowing a descriptor in one image to match at most with a single descriptor in the other. For a given value of k, the k best-matching descriptors are computed according to this procedure. Finally the most elaborate technique (`distance ratio') normalizes the distances between a descriptor and descriptors in another image by the distance of the descriptor to its nearest-neighbor in the other image. We report results using all three criteria, in the form of Precision-Recall curves; we obtain these curves from the software of [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF], adapted to include the evaluation modications described above.

In Figure 8 we rst examine the robustness of our descriptors to transformations other than scaling and rotation, including blurring due to a change of camera focus, jpeg compression, and perspective transformations. We observe that according to all three criteria, our descriptor outperforms SIFT.

To assess the robustness of our descriptor to scale and rotation changes we use all of the images in [START_REF] Mikolajczyk | Scale and Ane Invariant Interest Point Detectors[END_REF] and subject them to a common set of synthetic transformations. In the original dataset only two out of eight images were subjected to scaling and rotation, and the amounts of scaling were not common across the two images; this hindered the thorough evaluation of our RR n°7914 method, and led us to use this more controllable setting instead.

In Figure 10 we demonstrate how our descriptor compares to SIFT, for increasingly large changes in scale. We observe that our descriptor largely outperforms SIFT according to all three criteria, up to a scale change in the order of 3 (green color). Above that level, the results become ambiguous, with SIFT performing equally well or better on most images.

In summary, the results verify that our descriptor has excellent performance for a broad range of scales -at least up to three-, despite being only approximately scale invariant (due to the use of a limited number of rings/scales). This complements the main merit of our approach, namely than unlike SIFT, or other descriptors which rely on scale selection, our descriptor can be evaluated anywhere over the image domain.

Shape Descriptor Evaluation

We used the SHREC 2010 robust large-scale shape retrieval benchmark, simulating a retrieval scenario, in which the queries include multiple modications and transformations of the same shape [START_REF] Bronstein | robust large-scale shape retrieval benchmark[END_REF]. The shapes were represented as triangular meshes with the number of vertices ranging approximately between 300 and 30,000. The dataset consisted of two parts: 715 shapes from 13 shape classes with simulated transformation (55 per shape) used as queries and the remaining 456 shapes. The query set consisted of 13 shapes taken from the dataset (null shapes), with simulated transformations of dierent type and strength applied to them. Each query had only one correct corresponding null shape in the dataset.

Performance was evaluated using mean average precision and the receiver operating characteristic (ROC). Precision P (r) is dened as the percentage of relevant shapes in the rst r top-ranked retrieved shapes. In the present benchmark, a single relevant shape existed in the database for each query. Mean average precision (mAP) is dened as mAP = ∑ r P (r) • rel(r),

(rel(r) is the relevance of a given rank), and ideally should be 100%. The receiver operating characteristic (ROC) curve is another performance criterion, representing a tradeo between the percentages of similar shapes correctly identied as similar (true positives rate -TPR) and of dissimilar shapes wrongfully identied as similar (false positive rate -FPR).

Heat kernel signatures (HKS) and the proposed scale-invariant heat kernel signatures (SI-HKS), respectively, were used as local shape descriptors. In both cases, the cotangent weight scheme was used to discretize the surface Laplace-Beltrami operator ∆ ∂X . The heat kernel was approximated using the k = 100 largest eigenvalues and eigenvectors. For HKS, we used the parameters of [START_REF] Ovsjanikov | Shape Google: a computer vision approach to invariant shape retrieval[END_REF] (six scales 1024, 1351, 1783, 2353, 3104 and 4096), which were experimentally found to give optimal performance. We construct the SI-HKS as described in Section 5, using a logarithmic base α = 2 and τ ranging from 1 to 25 with increments of 1/16. The rst 6 lowest frequencies of the Fourier transforms were used.

Bag-of-features shape descriptors were constructed using bags of geometric words proposed in [START_REF] Ovsjanikov | Shape Google: a computer vision approach to invariant shape retrieval[END_REF]. For HKS and SI-HKS, a geometric vocabulary of size 48 was built using clustering in the signature space (six-dimensional in both cases). The HKS and SI-HKS at each point of the shape were replaced by the closest geometric word from the vocabulary using soft vector quantization. The distribution of geometric words (48-dimensional bag of features) was used as the shape descriptor. The L 1 distance was used to compare the bags of features.

Tables 23 show the performance of shape retrieval using bags of features based on HKS and Figure 11 shows a few examples of retrieved shapes, ordered by relevance, which is inversely proportional to the distance from the query shape. Using HKS, all the matches for scale and mixed transformations queries (rows 2 -3 and 4) are incorrect (middle column). On the other hand, using the SI-HKS the results are mostly correct (right column).

Conclusion

In this paper we have introduced a method to construct scale invariant descriptors without relying on scale selection. Our experimental results demonstrate that these descriptors compare favorably to current state-of-the-art alternatives when evaluated on standard datasets. Moreover, by virtue of being independent of scale selection, our descriptors can be computed densely over

RR n°7914

the signal domain.

In future work we intend to explore several avenues to expand their usefulness. In specic, we intend to pursue the use of scale-invariant image descriptors for object recognition, both for Bag-of-Words classiers and for part-based models. We also intend to pursue the integration of Self-Similarity Descriptors [START_REF] Shechtman | Matching local self-similarities across images and videos[END_REF] with our approach, as well as the construction of scale-invariant

surface descriptors from open, noisy surfaces, such as those delivered by depth sensors.

Appendix

Denoting by I α [n] the signal obtained by sampling I(x/α) as in ( 6), we prove that I α [n] = I 1 [n -1], ∀n:

I α [n] = I α (c 0 α n , cα n ) = I α (x) * g cα n (x)| x=c0α n = ∫ t I α (t -c 0 α n )g cα n (t)dt = ∫ t I 1 (t/α -c 0 α n-1 )αg cα n-1 (t/α)dt t ′ =t/α = ∫ t ′ I 1 (t ′ -c 0 α n-1 )g cα n-1 (t ′ )dt ′ = I 1 [n -1] (23)

Furthermore, local descriptors

  can often deal graciously with occlusions, or boundary eects, where global descriptors, such as high-dimensional moments, fail. At the same time, it is substantially more challenging to deal with transformations of the signal domain such as scaling, or more generally, ane transformations.

  ∀n, k. This allows us to adapt the technique described in the previous subsection and use the Discrete-Time Fourier Transform (DTFT)[START_REF] Oppenheim | Discrete-Time Signal Processing[END_REF] of f α [n] and f 1 [n] instead of the Continuous-Time Fourier Transform discussed above.

Figure 4 :

 4 Figure 4: Visualization of dense scale-and rotation-invariant descriptors: we show some our descriptor dimensions as R, G, and B channels, and compare the resulting images over a reference image and the corresponding locations of a query image. In the bottom row we superimpose on the image hue maps (red and colorful is larger) indicating the similarity of descriptors in the query image to the points on the reference image. Based on context information, our descriptor can discriminate among locally similar structures.

Figure 6 :

 6 Figure 6: Construction of the SI-HKS. Left: HKS computed at the same point, for a shape that is scaled by a factor of 11. Middle: the signal ḣ[τ ], where the eects of scale change have been converted into a shifting in time. Right: the rst 20 components of |H(Ω)| for the two signals; the two descriptors are virtually identical.

Figure 7 :

 7 Figure 7: Top: three components of the HKS (left) and the proposed SI-HKS (right), represented as RGB color and shown for dierent shape transformations (null, isometric deformation+scale, missing part, topological transformation). Bottom: HKS (left) and SI-HKS (right) descriptors at three points of the four shapes (dierent points are coded with red, green, and blue; dashed line shows the null shape descriptor). We observe that the SI-HKS descriptors are substantially more robust to the deformations and stay closer to the null shape descriptor.

RecallFigure 8 :RecallFigure 9 :RecallFigure 10 : 29 HKSFigure 11 :

 89102911 Figure 8: Precision-Recall curves for transformations other than scale and rotation: we compare SIFT (dashed) to our descriptors (solid) on Harris-Laplace (green) and Hessian-Laplace interest points (red).

HKS

Figure 12 :

 12 Figure 12: ROC curves showing shape retrieval performance using bags of features based on HKS and SI-HKS.

  scale them by σ n and split them into positive and negative parts. This gives 2D signals, f ±,θ d,k σn , where ± stands for polarity, θ d,k indicates the derivative orientation, and σ n the smoothing scale.

These signals are then used instead of f in

[START_REF] Bronstein | Analysis of twodimensional non-rigid shapes[END_REF]

, giving rise to 2D measurements per

[k, n]

combination:

Table 2 :

 2 SI-HKS local descriptors. SI-HKS shows dramatic improvement (from 27.42% to 98.21% MAP and from 30.34% to 65.07%) in the scale and mixed transformations classes, respectively, and a small improvement (from 80.22% to 82.08% and from 2.95% to 6.61%) in the local scale and partial classes, respectively. An insignicant performance degradation is manifested in topology, holes, and sampling. Overall in all transformation classes and strengths in the SHREC benchmark, Inria SI-HKS performs better than HKS (90% vs 85.00%). These results are consistent with the ROC curves shown in Figure12.Performance (mAP in %) of ShapeGoogle using bags of features of size 48 based on HKS local descriptor.

				Strength
	Transform. Isometry Topology Holes Micro holes 100.00 100.00 100.00 100.00 100.00 1 ≤2 ≤3 ≤4 ≤5 100.00 100.00 100.00 100.00 100.00 100.00 98.08 97.44 96.79 96.41 100.00 100.00 97.44 95.19 90.13 Scale 0.98 40.68 43.31 33.72 27.42 Local scale 100.00 100.00 98.72 89.38 80.22 Sampling 100.00 100.00 100.00 100.00 99.23 Noise 100.00 100.00 100.00 100.00 100.00 Shot noise 100.00 100.00 100.00 100.00 100.00 Partial 7.54 5.70 4.51 3.58 2.95 Mixed 53.13 55.86 47.77 37.54 30.34
	Average	94.94	93.12	90.84	87.82	85.00

Table 3 :

 3 Performance (mAP in %) of ShapeGoogle using bags of features of size 48 based on SI-HKS local descriptor.

				Strength
	Transform. Isometry Topology Holes Micro holes 100.00 100.00 100.00 100.00 100.00 1 ≤2 ≤3 ≤4 ≤5 100.00 100.00 100.00 100.00 100.00 96.15 96.15 94.87 93.27 92.69 100.00 100.00 100.00 94.71 89.97 Scale 91.03 95.51 97.01 97.76 98.21 Local scale 100.00 100.00 97.44 89.38 82.08 Sampling 100.00 100.00 100.00 100.00 97.69 Noise 100.00 100.00 100.00 100.00 100.00 Shot noise 100.00 100.00 100.00 100.00 100.00 Partial 17.43 10.31 9.57 8.06 6.61 Mixed 56.47 57.44 63.59 67.47 65.07
	Average	97.05	95.16	94.03	92.54	90.79

Kokkinos & Bronstein & Yuille