Gonéri Le Cozannet

Jeremy Rohmer

Anny Cazenave

Déborah Idier

Franck Lavigne

Carlos Oliveros

Communicating uncertainties of future coastal impacts for decision making

come   L'archive ouverte pluridisciplinaire

Abstract content

As sea-level rises, coastal hazards and risks such as extreme flooding or erosion are changing. For accurate assessments, several factors must be considered, such as the variability of sea-level rise and storm surge patterns. We proceed to a global sensitivity analysis of future coastal impacts of sea-level rise, in order to provide quantitative insight into the relative importance of contributing uncertainties over the coming decades. The method is applied for typical coastal settings of high-and lowenergy coasts. Storm surge propagation processes, then sea-level variability, and, later, global sea-level rise scenarios become successively important source of uncertainties over the 21st century. This defines research priorities that depend on the target period of interest. On the long term, scenarios RCP 6.0 and 8.0 challenge local capacities of adaptation for the considered sites. For decision makers concerned with adaptation to climate change in coastal areas, this approach provides quantitative insight into three key issues related to: (1) the timeliness of coastal adaptation planning (2) the identification of periods by which rising sea-levels cause rapid obsolescence of regular adaptation measures (3) the constraints imposed by different future climate change scenarios for long-term adaptation planning.


Andrei Bursuc

Giorgos Tolias

Hervé Jégou

Kernel Local Descriptors with Implicit Rotation Matching

Keywords: I.4.10 [Image Processing and Computer Vision]: Image Representation Algorithms and Experimentation local descriptor, kernel descriptor, rotation invariance

In this work we design a kernelized local feature descriptor and propose a matching scheme for aligning patches quickly and automatically. We analyze the SIFT descriptor from a kernel view and identify and reproduce some of its underlying benefits. We overcome the quantization artifacts of SIFT by encoding pixel attributes in a continuous manner via explicit feature maps. Experiments performed on the patch dataset of Brown et al. [3] show the superiority of our descriptor over methods based on supervised learning.

INTRODUCTION

In this paper we deal with the design of a local descriptor, which is one of the fundamental problems in computer vision. A variety of tasks, such as image classification, retrieval, detection, and registration, rely on descriptors derived from local patches. The local patches can be originated from dense sampling [START_REF] Fei-Fei | A bayesian hierarchical model for learning natural scene categories[END_REF] or from a sparse feature detector [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] which is co-variant to certain image transformations.

A variety of local descriptors builds upon image gradients. A standard choice is to build a histogram of gradient orientations, as in SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Another example concerns methods that rely on pixel intensities, e.g. by pairwise comparisons [START_REF] Calonder | Brief: Binary robust independent elementary features[END_REF]. Learning [START_REF] Brown | Discriminative learning of local image descriptors[END_REF] based on pairs of similar and nonsimilar patches is employed to select the spatial pooling regions and for dimensionality reduction [START_REF] Simonyan | Learning local feature descriptors using convex optimisation[END_REF].

In this work, we focus on a kernelized view of patch descriptors. In particular, we are motivated by the kernel descriptor of Bo et al. [START_REF] Bo | Kernel descriptors for visual recognition[END_REF]. However, in our method we encode pixels in polar coordinates and rely on explicit feature maps [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF], which provide a better approximation by Fourier series. We present a kernelized framework for local descriptors, out of which, known descriptors such as SIFT and our proposed descriptor are derived. This viewpoint of SIFT highlights some of its advantages and drawbacks: namely the encoding of the pixel position and the hard assignment which inevitably inserts some artifacts. We rather offer continuous encoding of pixel position and gradient orientations.

There are local descriptors that are rotation invariant by construction [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF]. An alternative approach is to rely on the dominant orientation [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] of the patch in order to provide rotation invariance. The patches are rotated with respect to this dominant angle and transformed to up-right. Therefore, such descriptors are sensitive to this angle. In addition, in several tasks it is necessary to detect several multiple angles per patch, which further increases the computational cost of the procedures that follow. We adapt the latter choice of up-right patches and develop a fast patch alignment method with respect to rotation. Patch similarity is computed for multiple rotations at a slight increase of the computational cost. It allows us to handle the sensitivity to dominant orientation estimation and to dispense with the need for multiple dominant angles. This procedure is similar to the trigonometric polynomial of Tolias et al. [START_REF] Tolias | Orientation covariant aggregation of local descriptors with embeddings[END_REF], but at a patch level. It further resembles the way that Henriques et al. [START_REF] Henriques | Beyond hard negative mining: Efficient detector learning via block-circulant decomposition[END_REF] speed-up learning with multiple shifted versions of negative samples, instead of performing costly sliding window based mining.

Our contribution includes a novel kernel local descriptor that encodes pixel position and gradient orientation in a continuous manner. It is also accompanied by an efficient way to compute patch similarity for multiple rotations, which constitutes our second contribution.

LOCAL DESCRIPTORS: KERNEL VIEW

Match kernels have gained an increasing interest after it was shown that it is possible to approximate non-linear kernels with linear ones by using an appropriate feature map [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF][START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF]. Similarity of sets can be efficiently computed with match kernels just by embedding the features in a suitable feature space in advance. Match kernels provide new grounds for designing better similarity functions.

Here, we define kernel descriptors over sets of pixels belonging to the same patch. An image patch can be considered as a set of pixels X = {x}. Without loss of generality we assume that we are dealing with grayscale patches. The relative position of a pixel x with respect to the patch center is expressed in polar coordinates and denoted by (ϕx, ρx). We employ gradient information, thus each pixel is described by the gradient magnitude mx and the gradient orientation θx. The latter is expressed relatively to the angle ϕx (Figure 3). The pixel position and its gradient information are referred as pixel attributes in the following. Two patches X and Y can be now compared via a match kernel of the form

K(X , Y) = γ(X )γ(Y) x∈X y∈Y k(x, y), (1)
where k is the local kernel and γ is the normalization factor ensuring that self-similarity K(X , X ) = 1. The local kernel computes the similarity between two pixels x and y, while the global kernel K accumulates similarities of all pairs of pixels. An interesting option is to obtain such a kernel by mapping pixels attributes to a higher-dimensional space with a feature map ψ : x → ψ(x), such that the inner product evaluates the local kernel k(x, y) = ψ(x)|ψ(y) . The match kernel can be now expressed as:

K(X , Y) = γ(X )γ(Y) x∈X y∈Y ψ(x)|ψ(y) = X|Y , (2)
where X = γ(X ) x∈X ψ(x) and Y = γ(Y) y∈Y ψ(y) are the local descriptors of patches X and Y, respectively. Note that all the pairwise similarities are never explicitly enumerated; the linearity of the inner-product allows us to aggregate in advance the pixel feature vectors per patch. Several popular methods for patch and image description can be actually described by this framework, among which SIFT. The SIFT descriptor is arguably one of the most popular and effective local feature descriptors in various computer vision applications. Some of the underlying advantages of SIFT can be emphasized better from a kernel perspective.

In the case of SIFT, consider that each pixel x is mapped to ψ(x) ∈ R 128 , which is a sparse feature map due to the quantization of gradient orientation and spatial location. The aggregation of all pixel feature maps ψ(x) results to the SIFT descriptor. The similarity of two SIFT descriptors can be then computed via inner product. The quantization to the spatial grid and to the orientation bins enforces to take into account only pixels with similar gradient orientations and spatial positions. The hard assignment in the quantization process inevitably inserts some artifacts and leads to a loss in the selectivity of the similarity function.

In the following, we design a kernelized local descriptor that imitates some of the advantages of the SIFT descriptor. At the same time, we alleviate some of drawbacks related to the quantization artifacts by encoding pixel position and gradient orientation in a continuous manner.

METHOD

We want to exploit jointly the photometric and position information of all patch elements (pixels). We target a kernel function for patch elements that reflects their resemblance in terms of gradients and their proximity in terms of their spatial position. To this effect, the local kernel k(x, y) can be decomposed into k θ (θx, θy) kϕ(ϕx, ϕy) kρ(ρx, ρy). It captures the similarity of the gradients with k θ , and the spatial proximity on each coordinate separately with kϕ and kρ. Our match kernel now becomes

K(X , Y) ∝ x∈X y∈Y mx my k θ (θx, θy) kϕ(ϕx, ϕy) kρ(ρx, ρy),
where the magnitude mx = G(ρx, σ) * √ mx is weighted by a Gaussian window in order to give higher importance to the patch center. In this fashion, our match kernel turns into scalar value comparison, such as angles and radii. Typically, non-linear functions are employed for such a comparison.

Feature maps for pixel attributes

We employ a normalized version of the Von Mises distribution [START_REF] Tolias | Orientation covariant aggregation of local descriptors with embeddings[END_REF] (normal distribution for angles) in order to compare two angles:

k VM (θ1, θ2) = k VM (∆θ) = exp(κ cos(∆θ)) -exp(-κ) 2 sinh(κ) . (3)
This is a stationary kernel that depends only on the difference of the two angles ∆θ = θ1 -θ2. The selectivity of the function is controlled by parameter κ.

We define a mapping φ : [-π, π] → R M of an angle θ to a vector φ(θ) such that the inner product of two such vectors approximates the target function, that is φ(θ1) φ(θ2) = kVM (θ1, θ2) ≈ k VM (θ1, θ2). For this purpose we make use of explicit feature maps [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF] and follow the methodology of Tolias et al. [START_REF] Tolias | Orientation covariant aggregation of local descriptors with embeddings[END_REF]. The desired mapping is

φ(θ) = ( √ γ0, √ γ1 cos(θ), √ γ1 sin(θ), . . . , √ γN cos(N θ), √ γN sin(N θ)) , (4)
where γi is the i-th Fourier coefficient of Von Mises (3). The approximation by N Fourier coefficients (coresponding to N frequencies) produces a vector of M = 2N + 1 dimensions.

The number of frequencies influences the accuracy of the approximation. Figure 1 illustrates the target function and its approximation for different values of N . We choose the Von Mises to implement all 3 local kernels k θ , kϕ and kρ. The mapping of Equation ( 4) is trivially used on local kernels k θ and kϕ, since they deal with angles. We further map the radius of pixel x to an angle by ρx = ρxπ, with ρx ∈ [0, 1]. In this way, we are now able to use the same mapping of scalar to vectors for the radius also. In Figure 2 we visualize the combination of the two local kernels kρ and kϕ (by their product) that evaluate the spatial proximity. Both radius ρ and angle θ remain unchanged, while only angle ϕ changes.

Wrapping up the descriptor

Each patch element x is now associated to three vectors describing its attributes, namely φ(θx), φ(ϕx) and φ(ρx). In order to obtain a single descriptor we propose to describe x by the Kronecker product of these vectors, defined by ψ(x) = mxφ(θx) ⊗ φ(ϕx) ⊗ φ(ρx). By aggregating such vectors for all patch elements, the patch descriptor is now formed by X ∝ x∈X ψ(x).

By using the Kronecker product properties we can show that comparing two such local descriptors via inner product is equivalent to the approximation of our match kernel:

X|Y ∝ x∈X ψ(x) y∈Y ψ(y) = x∈X y∈Y ψ(x) ψ(y) ≈ x∈X y∈Y mx my k θ (θx, θy) kϕ(ϕx, ϕy) kρ(ρx, ρy) = K(X , Y). (5)
The desired property of our mapping is the linearity of the inner product used to compare two vectors, which approximates a non-linear function comparing two angles. The pixel representation can be then aggregated in advance for each patch. The dimensionality of the local descriptor is equal to (2N θ + 1)(2Nϕ + 1)(2Nρ + 1), where different number of frequencies can be used for each pixel attribute (N θ , Nϕ and Nρ) depending on the use-case. The descriptor is subsequently square-rooted and L2-normalized.

Fast rotation alignment

At this stage, our match kernel and, equivalently, the kernel descriptor assume that all patches have the same global orientation. Patches are typically orientated to up-right position according to their dominant orientation. We adopt the same choice. However, this type of alignment can be quite noisy. We propose a method for identifying the rotation that maximizes the patch similarity and aligns them in an optimal way. We achieve this without explicitly computing the descriptors for all possible rotations.

Imagine that a patch X is rotated by an angle ϕ δ into patch X δ , and denote the descriptor of the rotated patch by X δ . The only pixel attribute that changes is the angle ϕ, shifted by ϕ δ , as illustrated in the toy example of Figure 3. Under this point of view and with respect to variable ϕ, it can be seen that local descriptor X is decomposed into the following sub-vectors [X0 , X1,c , X1,s , . . . , XN,c , XN,s ] . X0 is constant for any patch rotation. The sub-vectors Xi,c and Xi,s are related to components of the form cos(iϕx) and sin(iϕx), respectively, for frequency i. Interestingly, by using simple trigonometric identities, it turns out [START_REF] Tolias | Orientation covariant aggregation of local descriptors with embeddings[END_REF] that the similarity of two patches, when one of them undergoes rotation, forms a trigonometric polynomial:

X δ |Y = X 0 |Y 0 + Nϕ n=1 cos(nϕ δ ) ( Xn,c|Yn,c + Xn,s|Yn,s ) + Nϕ n=1 sin(nϕ δ ) (-Xn,c|Yn,s + Xn,s|Yn,c ) . (6)
The complexity of computation of the polynomial coefficients in Equation ( 6) is less than twice the cost to compute the standard similarity between two kernel descriptors, while the cost to evaluate similarity for multiple angles ϕ δ is negligible. In Figure 4 we present an example of the similarity of two patches under multiple rotations. The rotation of maximum similarity is used to align the patches.

EXPERIMENTS

We compare our descriptor against the state-of-the-art RootSIFT [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF], and its counterpart rotated by PCA, noted as RootSIFT-PCA in the following. We further compare with the learned descriptors of Simonyan et al. [START_REF] Simonyan | Learning local feature descriptors using convex optimisation[END_REF] and the ones of Brown et al. [START_REF] Brown | Discriminative learning of local image descriptors[END_REF] that rely on pairs of known related and nonrelated patches. We do not consider in our evaluation the descriptor of Bo et al. [START_REF] Bo | Kernel descriptors for visual recognition[END_REF] as it is optimized to be used in image level aggregated manner for image classification, whereas we test patch similarities. We use a patch dataset [START_REF] Brown | Discriminative learning of local image descriptors[END_REF] comprising three subsets, Notre Dame, Liberty and Yosemite, corresponding to different landmarks on which 3D reconstruction was performed. Each subset consists of 450k image patches of size 64 × 64 which are derived from keypoints detected with Difference-of-Gaussians. They are normalized with respect to scale and rotation. The ground-truth denotes the groups of similar patches, and two patches are considered similar if they are projections of the same 3D point.

Implementation details

We refer to our kernel descriptor as KDN θ ,Nϕ,Nρ and evaluate for different number of frequencies. Parameter κ is always fixed and equal to 8, except for the case of Nρ = 1 when κ is 2. In order to avoid artifacts for the computation of the rotated patches, we keep only the pixels inside the circle inscribed in the patch, as shown in Fig. 4. Post-processing. The patch descriptor is power-law normalized with the power-law exponent α set to 0.5. For the PCA rotated variant, we obtain better results for α = 1. For this case, we apply powerlaw normalization with α = 0.5 after the projection. We proceed similarly for RootSIFT-PCA.

Orientation alignment. In order to align two patches we test up to 64 fixed rotations on each direction with a step of π/128. We find a good trade-off for rotations in the interval [-π/8, π/8]. Since the patches are already up-right, our algorithm reduces the quantization errors in the computation of the dominant orientations.

Hypothesis test

We evaluate our kernel descriptors following the standard protocol, generate the ROC curves and report false positive rate (FPR) at 95% recall. In Figure 5 we illustrate how performance improves by evaluating similarities for multiple patch rotations. After some extent performance decreases, since patches are already up-right by the rough dominant orientation and we are only introducing noisy matches.

We now consider each of the six possible combinations of training and test sets and we test 100k pairs for each run. Table 1 compares the error rates of our kernel descriptor against other local descriptors. Our descriptor is better than RootSIFT and RootSIFT-PCA and its performance is reaching that of learned descriptors [START_REF] Simonyan | Learning local feature descriptors using convex optimisation[END_REF]. While our kernel descriptor is higher dimensional, it doesn't require any training. We further evaluate it with PCA learned on a different dataset in order to obtain more compact descriptors. Although we cannot test multiple rotations anymore, the performance improves significantly outperforming more sophisticated methods trained over annotated pairs of similar and non-similar patches.

Nearest neighbors

We further evaluate our descriptor on a nearest neighbor search task using the patch dataset. We randomly select 1,000 query patches and report recall at the top R retrieved patches. This task is performed on a single subset at a time. Results for using Notre Dame as test set and Yosemite as learning set are reported in Table 2. Our kernel descriptors appear to perform the best, while the rotation alignment improves once more.

CONCLUSIONS

We proposed a kernel descriptor equipped with continuous encoding and a fast rotation alignment process. Inter- estingly, it achieves superior performance even compared to methods that employ supervised learning. 1

  kVM , N = 1 kVM , N = 3 kVM , N = 10

Figure 1 :

 1 Figure 1: Target weighting function (Von Mises) and the corresponding approximations with 1, 3 and 10 frequencies.

Figure 2 :

 2 Figure 2: Visualization of the 2D weighting function for 3 sample pixels (shown by a cross). Colors reflect the spatial similarity to other pixels. Red (yellow) color corresponds to maximum (minimum) similarity. Blue color corresponds to the area that is neglected by our descriptor.

Figure 3 :

 3 Figure 3: A sample patch and a corresponding pixel denoted by red rectangle. The gradient vector is shown by a blue arrow. The initial patch (left), is rotated by angle ϕ δ (right). Both radius ρ and angle θ remain unchanged, while only angle ϕ changes.

Figure 4 :

 4 Figure 4: Two sample patches (top) and their similarity (bottom) for multiple rotations of patch A. At the (top) right, patch A is rotated by the optimal orientation.

Figure 5 :

 5 Figure5: Impact of the rotation alignment on the performance. We evaluate patch similarity for 0, 4, 8, 16, 24 and 32 fixed rotations at each direction (clockwise and counterclockwise). Results reported on Notre Dame dataset.

Table 1 :

 1 False positive rate (%) at 95% recall. Learning type: N -none, U S-unsupervised, S-supervised. KD 3,3,1 (No rotations) 9.1 24.7 34.6 64.9 80.8 91.3 KD 3,3,1 (16 rotations) 8.8 26.2 37.3 68.3 84.4 93.1 KD 3,3,1 -P CA 9.4 24.9 35.2 66.4 82.9 92.4

	TrainTest	R o o tS IF T	R o o tS IF T -P C A	S im o n y a n [1 0 ]	B ro w n [3 ]	K D 2, 3, 1	K D 3, 3, 1	K D 3, 2, 2 -P C A
	ND Lib Yos Lib	29.64	19.34 12.42 16.85 21.58 20.06 19.95 14.58 18.27	13.17 14.53
	ND Yos Lib Yos	26.69	18.37 10.08 13.55 11.07 9.66 19.52 11.18 N/A	8.31 9.65
	Lib ND Yos ND	22.06	13.90 13.98	7.22 N/A 7.99 7.00 6.82 11.98	6.36 6.50
	Mean	26.14 17.51 10.38 15.16 13.55 12.24 9.75
	Dimensions	128	80 73-77 29-36	105	147	80
	Learning	N	US	S	S	N	N	US
	R		1	5	10	100 1000 10000
	RootSIFT		8.5 24.4 33.0 62.9 79.7	90.6
	RootSIFT-PCA		8.8 23.9 32.7 61.4 78.4	90.4

Table 2 :

 2 Recall computed at R top ranked patches for 1000 randomly selected patch queries on Notredame dataset. Learning for PCA is performed on Yosemite dataset, and the dimensionality is reduced to 80 components.

This work was supported by ERC grant Viamass no. 336054 and ANR project Fire-ID.