S Rousseau

D Helbert

P Carré

J Blanc-Talon

Compressive Pattern Matching on Multispectral Data

We introduce a new constrained minimization problem that performs template and pattern detection on a multispectral image in a compressive sensing context. We use an original minimization problem from Guo and Osher that uses L1 minimization techniques to perform template detection in a multispectral image. We first adapt this minimization problem to work with compressive sensing data. Then we extend it to perform pattern detection using a formal transform called the spectralization along a pattern. That extension brings out the problem of measurement reconstruction. We introduce shifted measurements that allow us to reconstruct all the measurement with a small overhead and we give an optimality constraint for simple patterns. We present numerical results showing the performances of the original minimization problem and the compressed ones with different measurement rates and applied on remotely sensed data.

Introduction

The compressive sensing is a recent field of signal processing. It has been introduced by Donoho [START_REF] Donoho | Compressed sensing[END_REF] and Candès, Romberg and Tao [START_REF] Candès | Stable signal recovery from incomplete and inaccurate measurements[END_REF]. The main idea is that the acquisition and the compression steps are performed simultaneously by taking a limited number of linear measurements on the signal. These linear measurements are modelled as inner products against a signal x of size n:

y i = φ i , x , i = 1, . . . , m (1)
where m is the number of linear measurements. This can be written y = Φx where the φ i 's are the columns of Φ T and Φ is referred to as the sensing matrix.

Recovering the signal x for the linear measurements y is a linear inverse problem that has more unknowns than equations because m n. But if the signal x is sparse in a known basis, it can be recovered from the measurements. The signal x is sparse in the orthonormal bases Ψ if we can decompose x as Ψu where u is sparse. In that case, the following minimization problem involving a L 0 norm 1 recovers u. arg min u u 0 s.t. ΦΨu = y.

Unfortunately, due to its combinatorial nature, that minimization problem is intractable. Several methods have been proposed to find an approximate solution. 1 The L 0 norm just counts all the nonzero entries.

1

Greedy approaches have been explored giving matching pursuit-like algorithms (see [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF][START_REF] Pati | Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[END_REF][START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF][START_REF] Blumensath | Gradient pursuits[END_REF][START_REF] Davis | Adaptive greedy approximations[END_REF][START_REF] Donoho | Stable recovery of sparse overcomplete representations in the presence of noise[END_REF]). Another way to efficiently solve this problem is to consider the closest convex problem that involves a L 1 norm called the basis pursuit problem [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] arg min u u 1 s.t. ΦΨu = y.

The L 1 norm just replaces the L 0 norm. It is proved under certain circumstances that the solutions of both problems coincides. Multispectral imagery requires the acquisition of each band of the multispectral image. In this regard, the compressive sensing paradigm becomes very interesting since the standard acquisition process generates a huge flow of data and thus requires a costly compression step. Some physical implementations have already been proposed: the single-pixel hyperspectral camera [START_REF] Duarte | Single-pixel imaging via compressive sampling[END_REF] based on digital micromirror device (DMD) or the Coded Aperture Snapshot Spectral Imaging (CASSI) [START_REF] Gehm | Single-shot compressive spectral imaging with a dual-disperser architecture[END_REF] based on two dispersive elements. Another benefit of such a new acquisition paradigm is that the signal does not need to be fully reconstructed before performing some processing task (see [START_REF] Davenport | Detection and estimation with compressive measurements[END_REF][START_REF] Wang | Subspace compressive detection for sparse signals[END_REF]). That bypassing technique has been applied to various hyperspectral image processing such as spectral unmixing [START_REF] Li | A compressive sensing and unmixing scheme for hyperspectral data processing[END_REF][START_REF] Zare | Directly measuring material proportions using hyperspectral compressive sensing[END_REF][START_REF] Golbabaee | Multichannel compressed sensing via source separation for hyperspectral images[END_REF].

In this paper, we propose to apply it for signature detection in a multispectral image. We build upon our previous work [START_REF] Rousseau | Compressive template matching on multispectral data[END_REF] that dealt with compressive template detection and propose to extend it to perform compressive pattern detection.

The outline of the paper is as follows. In section 2, we introduce the template matching minimization problem of Guo and Osher and we bring elements of a response that show why that minimization problem is succeeding. We then briefly present how we solve this minimization problem and its variants. In section 3, we explain how this minimization problem can be extended to work with compressive data and we give a few numerical experiments demonstrating the performance of the compressive template matching minimization problem. In section 4, we study how we can extend the compressive template matching minimization problem to perform compressive pattern matching and provide numerical experiments. We give conclusions and perspectives in section 5.

Template matching 2.1 L 1 -based template matching

Template detection in a multispectral image is one of the first application when dealing with multispectral data. It consists of locating a template within a multispectral image. With the constant growing of the numbers of channels, this problem becomes computationnaly challenging. Several algorithms have been proposed so far to tackle down this problem, see [START_REF] Guo | Template Matching via L1 Minimization and Its Application to Hyperspectral Data[END_REF] and references therein. On a recent paper in [START_REF] Guo | Template Matching via L1 Minimization and Its Application to Hyperspectral Data[END_REF], the following minimization problem is suggested:

arg min u≥0 u 1 s.t. X T u -s 2 < σ. (4)
In this minimization problem, X is a matrix that stores the data collected by multispectral sensors. Each column corresponds to a channel and each row is the spectrum of a pixel. The vector s is the template we want to detect. We give here intuitive arguments explaining why this minimization problem is working. First, the term X T u can be interpreted as the linear combination of the rows of X weighted by the vector u. So X T u is in fact a linear combination of the pixels of X weighted by u. Moreover, the L 1 norm promotes sparse solutions. As a result, the minimization problem is looking for a reduced set of pixels whose linear combination with coefficients in u yields s. There are three types of solutions that satisfy that constraint:

• The solutions where u has a non-zero entry at every pixel of spectral signature s. That way, we would have a linear combination of spectral signatures approaching s which would give s.

• The solutions where u has a non-zero entry at some pixels of spectral signature s but not all of them.

• The solutions that combine random pixels of X and nonetheless yields s.

The latter type of solutions is ruled out because the L 1 norm of the corresponding u is likely to be greater than 1. Solutions of the first two types are then preferred. Figure 1 helps us to understand why solutions of the first type are preferred. In Fig. 1a, we display the classic compressive sensing case where the L 1 minimization problem do find a sparse solution. Figure 1b illustrates the case we are interested in where there are infinitely many solutions that minimize the L 1 norm and verify the constraint which are displayed in red. Some of the solutions are sparse (the two red points on the axis in our case) and represent solutions of the second type. The other solutions are less sparse but have the same L 1 norm and we observe that algorithms tends to select those solutions that have the largest support among those that minimize the L 1 norm. That is why solutions of the first type are preferred.

Numerical solution of the minimization problem

In the following sections, we will have to solve minimization problems of the form (4) and to improve the results, we will add a regularization term based on total variation. We then have the following minimization problem arg min

u≥0 u 1 + u TV s.t. Au -f 2 < err, (5)
Those minimizations are special cases of the more general minimization problem arg min

u≥0 φ(u) 1 s.t. Au -f 2 < err, (6)
where φ is a linear operator that yields model ( 4) when equal to the identity or model ( 5) when equal to

  Id D x D y   , ( 7
)
where Id is the identity matrix and D x and D y are respectively the linear operators giving the gradient along x and y. Due to their simplicity and flexibility, we use split Bregman algorithms [START_REF] Goldstein | The Split Bregman Method for L1-Regularized Problems[END_REF][START_REF] Cai | Split bregman methods and frame based image restoration[END_REF] to solve these minimizations. We first apply the Bregman iteration to [START_REF] Blumensath | Gradient pursuits[END_REF] which gives

   u k+1 = arg min u≥0 φ(u) 1 + β 1 2 Au -f k 2 2 ( 8a
)
f k+1 = f k + f -Au k+1 (8b)
with f 0 = f . Then, we use a splitting technique (see [START_REF] Wang | A fast algorithm for image deblurring with total variation regularization[END_REF][START_REF] Goldstein | The Split Bregman Method for L1-Regularized Problems[END_REF]) that introduces a new unknown to solve each subproblem (8a).

arg min u≥0,d

d 1 + β 1 2 Au -f k 2 2 s.t. d = φ(u). (9)
We then apply the Bregman iteration once more because we now have a constrained problem. We solve the minimization problem over u and d with an alternating minimization by first minimizing with respect to u and then with respect to d.

                     u l+1 = arg min u≥0 β 1 2 Au -f k 2 2 + β 2 2 d l -φ(u) -b l 2 2 (10a) d l+1 = arg min d d 1 + β 2 2 d -φ(u l+1 ) -b l 2 2 (10b) b l+1 = b l + φ(u l+1 ) -d l+1 (10c) Solve: arg min u≥0 φ(u) 1 s.t. Au -f 2 < err Data: φ, A, f, β 1 , β 2 ,

err

Result:

f 0 := f ; b 0 := 0; d 0 := 0; k := 0; D inv := (β 1 A T A + β 2 φ T φ) -1 ; repeat u k+1 := D inv (β 1 A T (f -f k ) + β 2 φ T (d k -b k )); u k+1 := max(u k+1 , 0); d k+1 := shrink(φ(u k+1 ) + b k , β 2 ); b k+1 := b k + φ(u k+1 ) -d k+1 ; f k+1 := f k + f -Au k+1 ; k := k + 1; until Au k+1 -f 2 < err;
Algorithm 1: Constrained Split Bregman

If we limit the number of iterations to solve u k+1 to only one in equations [START_REF] Duarte | Single-pixel imaging via compressive sampling[END_REF] and plug it back in equations ( 8), we finally have

                         u k+1 = arg min u≥0 β 1 2 Au -f k 2 2 + β 2 2 d k -φ(u) -b k 2 2 ( 11a
)
d k+1 = arg min d d 1 + β 2 2 d -φ(u k+1 ) -b k 2 2 (11b) b k+1 = b k + φ(u k+1 ) -d k+1 (11c)
f k+1 = f k + f -Au k+1 (11d)
The minimization problem (11a) is solved by first dropping the constraint u ≥ 0, solving the resulting least square problem and then forcing the solution to be non-negative. The minimization problem (11b) admits a closed-form solution using the shrinkage operator shrink defined as follows

shrink(x, λ) = sgn(x) • max(0, |x| - 1 λ ), (12)
where the operator • is the entry-wise product. The detailed algorithm is shown in Algorithm 1. In our experiments, we take A = X T , f = s, err = 10 -2 , β 1 = 1 and β 2 = 1000.

Compressive template matching

The previous template matching minimization problem needs the whole multispectral data cube to work. In this section, we propose a new minimization problem working in a compressive sensing context where we only have access to a small number of linear measurements on the multispectral image. The idea of processing signals without reconstructing them first dates back to the work of Davenport et al [START_REF] Davenport | Detection and estimation with compressive measurements[END_REF]. That bypassing idea has then been applied to multispectral image processing problems such as unmixing. Here, we wish to reconstruct the vector u solution of (4) without reconstructing the image first. This section and the following ones extends the work done in a previous article [START_REF] Rousseau | Compressive template matching on multispectral data[END_REF].

Measurement model and problem formulation

We recall that the multispectral image is stored in a matrix X where each column corresponds to a channel that is vectorized and each row is the spectrum of a pixel. We will assume that the multispectral image has n P pixels and n B bands. As a result, the matrix X has n P rows and n B columns. The acquisition model is described as

M = F X, (13)
where F is a sensing matrix. This amounts to perform independently the same measurements on each band of the image and store them is the corresponding column of M . The sensing matrix F has to verify of few properties for the recovering minimization problem to work. A popular one is the RIP condition that is known to be verified by independent and identically distributed (iid) Gaussian sensing matrix. However, these matrices are physically unrealistic and one considers simpler matrices such as Bernouilli distributed ones or Hadamard matrix. In this paper, we keep using Gaussian distributed sensing matrices as a reference but also use Gaussian distributed circulant matrices that are much more realistic from a physical point of view and that still are good sensing matrix [START_REF] Romberg | Compressive sensing by random convolution[END_REF].

We then define the measurement rate p where 0 < p < 1 (also expressed as a percentage), and what is its influence on the size of F . The measurement rate p is the fraction of the overall data that we want to acquire. It means that the number of elements of M is the number of elements of X multiplied by p. If the matrix F is of size m × n P then the sensing matrix M is of size m × n B and we have the relation

m • n B = p • n B • n P , (14)
which gives

m = p • n P . ( 15
)
The number of rows of F is an integer so we will take m = ⌊p • n P ⌋ where ⌊•⌋ is the operator mapping a number to its largest previous integer.

The problem is then to solve the following minimization

arg min u≥0 u 1 s.t. X T u -s 2 < σ M = F X , (16)
where we add the constraint coming from the measurements. The problem is to eliminate X from those two constraints since we no longer have access to the multispectral data.

Compressive template minimization

One way to eliminate X from the two constraints X T u = s and M = F X in ( 16) is to introduce a matrix between X T and u of the form F T A so we could replace X T F T by M T and eliminate X. This matrix should theoretically be equal to the identity. However that is impossible because F T A is not invertible. Given a matrix F , we have to find a matrix A such that F T A ≈ I n P . In the following, we will consider two candidates for A. The first candidate comes from the observation that if F is a Gaussian distributed matrix, we have 1 m F T F ≈ I n P as showed in [START_REF] Rudelson | Random vectors in the isotropic position[END_REF]. We can then take A = 1 m F and we will refer to this type of matrix as type 1 (T1).

One other candidate for A is obtained by solving the following minimization arg min

A F T A -I n P F , (17)
where • F is the Frobenius norm which is basically the Euclidean norm of the vectorized matrix. This is a well know problem involving the pseudo-inverse of A. One can show that the solution writes A = (F T ) + where the + operator is the pseudo-inverse. Given that F is a sensing matrix, we will always suppose that it is of full rank. In that case, A has an explicit formulation, A = (F F T ) -1 F . However, that minimization does not help us determining F . In fact, we can show that if F is of full rank, the norm

F T (F F T ) -1 F -I np F
is constant and is equal to √ n P -m. Among all matrices of full rank F , some are obviously better than others for a sensing matrix. For example, the matrix

F = I m 0 , (18)
is a very bad candidate because we have

F T (F F T ) -1 F = I m 0 0 0 , (19)
We note that the distance to I np is concentrated in a few entries which is why this is a terrible choice for a sensing matrix. Rather, we would like the error to be equally shared between all the entries of F . We then choose the max norm instead of the L 2 norm. Keeping (F F T ) -1 F as a possible candidate, we are now interested in the minimization arg min

λ λF T (F F T ) -1 F -I n P ∞ , (20)
λ λF T (F F T ) -1 F -I np ∞ Figure 2: λ minimizing maximum error
where • ∞ denotes the maximum norm. The solution is the right scaling of the candidate (F F T ) -1 F so as to minimize the maximum error. If F is iid Gaussian, we have already seen that F F T ≈ n P I m . We have also F T F ≈ mI n P . This suggests that λ = n P m . This is indeed what we find in Fig. 2 where m = 30 and n P = 100, the minimum error is at λ ≈ 3 ≈ n P m . We have two candidates. Type 1 (T1) is 1 m F and type 2 (T2) is n P m (F F T ) -1 F . Figure 3 depicts the maximum error for the two types of matrix A. We also try two types of sensing matrix F : iid Gaussian and iid Gaussian circulant. Circulant matrices are used as sensing matrices because it has been shown to be almost as effective as the Gaussian random matrix for CS encoding/decoding [START_REF] Yin | Practical compressive sensing with toeplitz and circulant matrices[END_REF][START_REF] Romberg | Compressive sensing by random convolution[END_REF]. Even if candidate of type 1 come from a minimization of the Frobenius norm, it is actually performing better than type 2. Quite surprisingly, the smallest error is obtained when F is the first m rows of a circulant matrix generated from a iid Gaussian vector. An intuitive explanation of this is that choosing a reduced set of Gaussian coefficients for a circulant matrix (the first line only) rather than a whole matrix reduces the chance of hitting a large number in absolute value that would give a large inner product (an entry in F F T or F T (F F T ) -1 F ). This large entry is then the final error since we are calculating the max norm.

From now on, we will consider matrix A of type 2. We can now eliminate X from X T u = s and M = F X. We have

X T n P m F T (F F T ) -1 F u = s, (21)
and then, using M = F X, we have

M T (F F T ) -1 F u = m n P s. (22
M T (F F T ) -1 F u - m n P s 2 < σ ′ , (23)
with σ ′ = n P m σ. Finally, this minimization problem is a modified version of (4) but instead of using X T we use the matrix M T (F F T ) -1 F that is an approximation of X T .

Numerical experiments

In this section, we illustrate both the regular template matching minimization problem and its compressive counterpart onto two images. We test both minimization problems with a measurement rate varying from 1 to 40 percent. In both cases, once the algorithm finished, we apply the Lloyd-Max clustering algorithm [START_REF] Max | Quantizing for minimum distortion[END_REF] on the recovered u to decide whether the detection is positive or not for each pixel. We then count the number of errors by comparing the resulting mask with the desired mask result. This reference mask is calculated manually by choosing all the pixels that have a signature approaching the one we want to detect. To improve the readability of the results, the images are inverted before display. The algorithm runs in less than a minute on a classic computer.

The first image is a 64 × 64 color image of Giza, Egypt2 displayed in Fig. 4a. The spectral signature s we want to detect is extracted from sandy areas. The result of the template matching minimization (4) is shown in Fig. 4b. The shape of all three sandy areas is well recovered. Figure 4c shows the compressive template matching [START_REF] Rudelson | Random vectors in the isotropic position[END_REF] with a L 1 regularizer for a measurement rate of 30%. We see that the detected pixels are scattered in the image. We improve the detection by mixing the L 1 regularizer with a geometrical one as we can see in Fig. 4d where a T V /L 1 regularizer is used. Figure 5 shows the results when the measurement rate is varying. As a reference, the percentage of wrong detection of the template matching minimization (4) is 0.03 %. The minimization performs best when the sensing matrix is Gaussian and the regularizer is T V /L 1 . Increasing the measurement rate after 10% does not improve much the detection. The more realistic case where the sensing matrix is circulant is doing quite well when the measurement rate is under 10%. Again, increasing the measurement rate after 10% does more harm than good. On the contrary, the L 1 regularizer shows a constantly decreasing error rate as the measurement rate increases. Another indicator that shows that Gaussian circulant sensing matrices are good sensing matrices is that pure Gaussian sensing matrices perform only slightly better than Gaussian circulant sensing matrices. The second multispectral image is extracted from the Moffett Field AVIRIS multispectral image3 . We selected 16 bands out of the 224 available and extracted a 64 × 64 image of interest shown in Fig. 7a. We would like to detect the spectral signature of buildings shown in Fig. 6. Figure 7 shows some of the results. As a reference, the percentage of wrong detection of the template matching minimization (4) is 0.3 %.

L 1 , circulant T V /L 1 , circulant L 1 , Gaussian T V /L 1 , Gaussian Template matching
Again, according to Fig. 8, the compressive template minimization performs best when the sensing matrix is Gaussian and the regularizer is T V /L 1 . However, the difference is less obvious than in the previous experiment but we can still see that T V /L 1 -based results show a better detection of connected objects.

Compressive pattern detection

In the previous section, we developed a minimization problem to detect the location of a known spectral signature from a limited number of measurements without reconstructing the image. The purpose of this section is to generalize that minimization problem to deal with pattern detection. We first introduce a formal transform on a multispectral image called spectralization that depends on the pattern P we wish to find. That formal transform essentially adds the pattern information as spectral information in the new image. Then, we use the previous minimization problem to detect signatures in this new image which are in fact patterns in the original image. As we will see, we need to reconstruct measurements because in fact we only have measurements on the original image and not on the spectralized one.

Image spectralization along a pattern

We first have to define the structure of the pattern we wish to detect before proceeding. It can be modelled as a finite subset of Z 2 . For example, if the

We then need to fix an order on that subset. The first point which will serve as a reference point is always the point (0, 0). The pattern's structure is now a n-tuple of couples. In the previous example, we choose P = ((0, 0), (1, 0), (1, 1)). ( 25)

Now that we have an ordered structure of the pattern P , we can define the spectralization of an image I with respect to P . Roughly speaking, the spectralization of I is just stacked copies of I that are shifted according to the ordered pattern we choose. This can be generalized to multispectral images. Let us first introduce some definitions and convenient notations related to image shifting and matrix stacking. We will then define the spectralized image of a grayscale image and extend it to multispectral images.

L 1 , circulant T V /L 1 , circulant L 1 , Gaussian T V /L 1 , Gaussian Template matching
Given an element p = (i, j) of Z 2 , we define the operator S p on a matrix which shifts all its entries by p. For example, the entry at (1, 1) is shifted to the place (i + 1, j + 1). More formally, if I is of size N × P we have [S p (I)] ab = I (a+i-1 mod N )+1,(b+j-1 mod P )+1 .

(

) 26
We have the obvious properties that S (0,0) is the identity, S (0,0) = id and that composing S p1 and S p2 yields S p1+p2 , S p1+p2 = S p1 • S p2 . If the pattern's structure is

P = (p 1 , . . . , p |P | ), (27)
with the convention that p 1 = (0, 0), we will consider the |P | corresponding shifting functions S p1 = id, S p2 , . . . , S p |P | where |P | denotes the number of elements of P . The operator S p is acting on I; the corresponding matrix acting on vec(I), the vectorized version of the matrix I, is denoted Q p and we have vec(S p (I)) = Q p (vec(I)).

(28)

Since the matrix Q p is a permutation matrix, it is orthogonal and we have

Q -p = Q -1 p = Q T p . (29)
We will also need to stack and merge matrices. If A and B are matrices with the same number of rows, [A, B] will denote the concatenation of A and B along their columns. If A and B are two matrices of the same size, A ∧ B will denote the 3-dimensional matrix obtained by stacking them along a third dimension.

We can now give a precise definition of the spectralization of the matrix I with respect to the pattern P = (p 1 , . . . , p |P | ). It is a 3-dimensional matrix obtained by stacking the matrices S -p1 (I), . . . , S -p |P | (I). For example, if the image I and the pattern P are defined as follows

I =   1 2 3 4 5 6 7 8 9   , (30)
              (36)
Thus, if we want to detect the pattern

2 ⋆ 5 6 , (37)
corresponding to the structure P in the image I, it suffices to look for the signature [START_REF] Candès | Stable signal recovery from incomplete and inaccurate measurements[END_REF][START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF][START_REF] Blumensath | Gradient pursuits[END_REF] in the spectralized image (36). Figure 9 shows the spectralization of a grayscale image. The pattern used is shown in Fig. 9a. The spectralization of the image along this pattern is shown in Fig. 9b. As in the previous example, we see that the spectralized image is formed by copies of the original image put side by side. Each of these copies is shifted.

Following the last writing of spec P (I), we define the spectralized image of a multispectral image X with respect to P . Given a multispectral image X and a pattern structure P , the spectralized image spec P (X) is the matrix,

[X, Q -p2 X, . . . , Q -p |P | X].

Measurements reconstruction

We have just established that a pattern detection on a multispectral image X is equivalent to a signature detection on the spectralized image of X denoted by spec P (X). The problem is that we need measurements on spec P (X) to solve the minimization problem and the only measurements we have are on X. We somehow have to reconstruct measurements on spec P (X) based on X's ones.

To measure the efficiency of the reconstruction of measurements, we introduce the following ratio depending on a given pattern P α(P ) = effective measurements virtual measurements .

The effective measurements are measurements performed on the real image. These are measurements that we could use in our calculations. On the contrary, virtual measurements are measurements on the fictive image spec P (X) that ought to be reconstructed from the effective ones. The ratio α(P ) measures how many more measurements we need to make to fully reconstruct measurements on spec P (X). The ratio α(P ) has simple bounds. Indeed, one virtual measurement requires at least one effective measurement to be reconstructed. As a result we have α(P ) ≥ 1. On the other hand, one virtual measurement requires at most |P | measurements on X because spec P (X) has |P | times more bands than X.

We then have α(P ) ≤ |P |. In conclusion, we have

1 ≤ α(P ) ≤ |P |. ( 39
)
For example, if we wish to detect the hook pattern consisting of 3 pixels, we have to make at most three times more measurements to reconstruct all virtual measurements in order to apply the minimization. If we want a measurement rate of 30% of the virtual image we need at most a 90% measurement rate on the original image. Fortunately, this upper bound can be lowered by properly choosing the measurements to make.

Reconstruction using shifted measurements

The first idea that comes to mind is to take measurements that are not independent but shifted from one another. Indeed, a shifted measurement on a shifted image could be the same as the original measurement on the original image. One effective measurement could be used to reconstruct more than one virtual measurement.

Let us first see how a measurement vector f that is shifted by a vector e writes. Let B be the measurement matrix that is the 2-dimensional version of the measurement vector f . We then have vec(B) = f. If the measurement matrix B is shifted by a vector e, it becomes S e (B). The vectorized form is vec(S e (B)). According to (28), the shifted measurement vector f e is then

f e = vec(S e (B)) = Q e vec(B) = Q e f. (40)
Suppose all our virtual measurements are a shifted version of one measurement f . The shifting information is modelled as a subset E of Z 2 containing the point (0, 0). The point (0, 0) represents the original measurement. All the other points represent shifted measurements of the original one. According to (29), the measurements writes

m e = (Q e f ) T spec P (X) = f T Q -e spec P (X),
for all e ∈ E. This can be written M virt = F virt spec P (X) where

E = {e 1 , . . . , e |E| }, and
M virt =    m e1 . . . m e |E|    and F virt =      f T f T Q -e2 . . . f T Q -e |E|      (41)
Further, we have

M virt =      f T f T Q -e2
. . .

f T Q -e |E|      X, Q -p2 X, . . . , Q -p |P | X = f T Q -ei Q -pj X 1≤i≤|E| 1≤j≤|P | = (Q ei+pj f ) T X 1≤i≤|E| 1≤j≤|P | . (42)
In other words, to reconstruct M virt that gathers the results of measurements on the virtual image spec P (X), we need to take the shifted measurements represented by E ′ = E + P where E + P denotes the set

{e i + p j | e i ∈ E, 1 ≤ i ≤ |E|, p j ∈ P, 1 ≤ j ≤ |P |} . (43)
Therefore, we choose

F eff =       f T f T Q -e ′ 2 . . . f T Q -e ′ |E ′ |       , (44)
as an effective sensing matrix, so we have

M eff = F eff X =       f T X (Q e ′ 2 f ) T X . . . (Q e ′ |E ′ | f ) T X       . (45)
The matrix M eff gathers the measurements taken on the real image X by the sensing matrix F eff and it contains all the information we need to reconstruct the matrix M virt in (42).

We are now able to write the measurement reconstruction ratio

α(P ) = |E + P | |E| , (46)
which reflects the fact that we have to take |E + P | effective measurements to reconstruct the |E| virtual ones.

Proposition 4.1. For a fixed pattern P we have

inf E |E + P | |E| = 1.
Proof. We already know that |E + P | ≥ |E| and hence |E+P | |E| ≥ 1. Let R be a a rows and b columns rectangle containing the pattern P . For n ≥ 1, let E be a na rows and nb columns rectangle. It is easy to see that E + R is a (n + 1)a -1 rows and (n + 1)b -1 columns rectangle. Thus we have

|E + R| |E| = ((n + 1)a -1) ((n + 1)b -1)) n 2 ab n -→ +∞ 1.
This proposition suggests that we choose E so that |E| has the highest possible value. Unfortunately, we have |E| ≤ |E +P | and the number of effective measurements |E + P | is limited by the size of the image: we cannot take too many measurements.

The problem is then to find the structure of E minimizing the ratio with |E| bounded. For a fixed pattern P , the problem is arg min

|E|=A |E + P | |E| . (47)
The problem (47) is a difficult one due to its combinatorial nature. Still, we can solve it if the pattern P has a simple shape. Suppose that P is a rectangle. To minimize α(P ), the measurement pattern E should also be a rectangle that has the same shape as the pattern P . This result is formalized in the following proposition. The details of the proof are shown in appendix. Proposition 4.2. Suppose that the pattern P is a rectangle. Then, a measurement pattern E such that |E| = A minimizing the ratio (46) is obtained when E is rectangular-shaped and its height h minimizes the functional

(a -1) A h + (b -1)h,
where a and b are respectively the height and the width of P and ⌈•⌉ is the operator mapping a number to its smallest following integer.

For example, suppose we wish to detect a rectangular pattern P of size 6×10 in a 128 × 128 color image. The spectralized image is then of size 128 × 128 and has 6 × 10 × 3 = 180 bands. Suppose we want a 25% virtual measurement rate, we then need 128 × 128 × 25/100 = 4096 different measurement vectors according to [START_REF] Zare | Directly measuring material proportions using hyperspectral compressive sensing[END_REF]. Given that we use shifted measurements, if E denotes the shifting pattern of the virtual measurements, we have |E| = 4096. According to equation (46), we need to perform the effective measurements denoted by the shifting pattern E + P to be able to reconstruct all the virtual measurements. The pattern P is rectangular so to minimize α(P ) and according to proposition 4.2 the measurement pattern E should be rectangular-shaped and contained in a rectangle of height 50 and width 82. That way, we have |E| = 4096 and E + P , as defined in (43), is obtained by shifting the pattern Data: Pattern P , Measurement rate p, Image X, Spectralized signature s Result: Compute the measurement pattern E that minimizes α(P ); Generate a random measurement f ; Take the effective measurements according to

E + P ; Reconstruct M virt from M eff ; Compute A = M T virt (F virt F T virt ) -

Numerical experiments

In this section, we illustrate our compressive pattern matching minimization. The detailed algorithm is described in Algorithm 2. Given the pattern P and the measurement rate p, we first compute the measurement pattern E that minimizes α(P ). For a rectangular-shaped pattern, the proposition 4.2 gives us the optimal solution. For more complex patterns, if they are compact, they can be approximated by their enclosing rectangle and the proposition 4.2 applies.

We then generate the effective measurements M eff from the shifting pattern E + P and a random measurement f . The results of those measurements are stored in M eff . We showed that M virt can be reconstructed from M eff : it consists essentially in duplicating and reordering entries of M eff . However, that process can be tricky to perform in an efficient way especially in Matlab.

For convenience and testing purposes, we rather build the spectralized image spec P (X) and compute M virt = F virt spec P (X) to more easily get the matrix M virt . Of course, given the size of spec P (X) which can be huge, this method shows its limits and we therefore limit ourselves to images of maximum size 64 × 64. The reconstructed M virt allows us to compute the matrix A that is used in our algorithm. To improve the readability of the results, the images are inverted before display. The algorithm runs in less than a minute on a classic computer.

We first test our algorithm on a publicly available color image of Giza, Egypt. We extract a 64 × 64 image shown in Fig. 13a and we want to detect the locations where there is sand surrounded by vegetation. For that purpose, we use a pattern whose shape is described in Fig. 10. The centre of the pattern i j Figure 10: Pattern to detect on the Giza image detects the sand and the four other squares detects the vegetation. The pattern is included in a square of size 12 × 12 so we use the measurement pattern as stated in the proposition 4.2. The minimization problem is first tested for several virtual measurement rates ranging from 1 to 40 percent. Figure 11 depicts the effective measurement rate with respect to the virtual measurement rate for the pattern. As pointed out by proposition 4.1, α which is the ratio of these two values decreases to 1 as the virtual measurements increases. Virtual measurement rate (%) Effective measurement rate (%) Figure 11: Effective measurement rate with respect to virtual measurement rate for the pattern displayed in Fig. 10 Figures 13b, 13c and13d show the results of the compressive pattern detection algorithm for a virtual measurement rate of respectively, 10%, 20% and 30%. The locations are well recovered for a virtual measurement rate of 20% and 30%. Only one target seems to be detected when a 10% measurement rate is taken. More precisely, the graph in Fig. 12 describes the number of pattern detection for various virtual measurement rate. We test two types of measurements and for each effective measurement rate we take the average number of errors of 10 minimizations. The random measurements serve as a reference since using them would require a huge effective measurement rate and thus totally defeats the purpose of compressive sensing. We then test the same image contaminated with Gaussian noise. Figure 14 sums up the our results. We fixed the virtual measurement rate to 20% and add Gaussian noise ranging from 0 to 10%. The minimization problem appears to be stable when it comes to Gaussian noise. This is not surprising since the minimization without noise is operating on M T (F F T ) -1 F which is already a noisy version of the original image X T .

On the next numerical experiments, we use a real-world multispectral image collected by ACTIMAR as part of the HYPLITT project, supported by the DGA (General Directorate for Armament), France. See [START_REF] Jay | Underwater target detection with hyperspectral data: Solutions for both known and unknown water quality[END_REF]. The study site is located in Quiberon Peninsula, on the West coast of France.

From the original image of size 316 × 302 with 160 bands, we extracted a 100 × 100 image and selected 12 bands. We wish to detect the checkered pattern in the top left corner. This time, the structure of the pattern used is P = ((0, 0), (0, 3), (0, 6), (3, 0), (3, 3), [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF][START_REF] Blumensath | Gradient pursuits[END_REF], (6, 0), (6, 3), (6, 6))

Since the pattern structure is a scaled square, to minimize α(P ) the measurement pattern should be a scaled square as well. The results of the different minimizations are shown in Fig. 15. Figure 15a is the multispectral image in false color. We first apply the template detection minimization (4) that is able to recover the checkered structure. The compressive template detection minimization problem in Fig. 15c fails to detect the checkered structure. By contrast,

Conclusions and perspectives

After a brief introduction of a new minimization problem from Guo and Osher that performs template matching on a multispectral image, we first provide evidence that explains why that minimization problem is working. Then, we extend it in several ways. We first show that this minimization problem can be adapted to work with compressive sensing data. Basically, we obtained comparable results but with limited number of measurements on the image. Then, we extend the minimization problem to perform pattern detection with compressive sensing data. For this purpose, we introduce a formal transformation called the spectralization that depends on the structure of the pattern we want to detect. Numerical experiments are conducted on both synthetic and real-world images that validates both approaches. Future work could consider choosing a sensing matrix that could ease the computation of the matrix A in algorithm 2. This would allow us to test our algorithms on larger images with a large number of bands. In particular, we could consider circulant matrices and orthogonal circulant matrices. One can also study if the recovery is better if the sensing matrix is built with several different measurements that are then shifted instead of only one.

Acknowledgement

This work was supported by the french General Directorate for Armament (DGA). Moreover, we would like to thank ACTIMAR, which conducted the field measurement campaign HYPLITT. We would also like to thank the reviewers for their helpful comments and insights.

Proof of proposition 4.2. Without loss of generality, we suppose that the pattern P is defined by P = {(i, j), 0 ≤ i < a, 0 ≤ j < b} .

Let E be a measurement pattern such that |E| = A and let n i and m i be respectively the number of elements of E + P and E of ordinate i. We have

i∈Z n i = |E + P | , (49)
Summing n i for i ∈ Z, we have Lemma .1. Let a be a non-negative integer, u a non-negative integer valued sequence indexed by Z such that i∈Z u i = A ≥ h and φ defined by (51). We have

|E + P | ≥ i∈Z (φ a (m)) i + i∈Z ni =0 b -1 (52)
inf |u|=h i∈Z (φ a (u)) i = A + (a -1) A h , (56)
and a minimizing sequence is

v i =      q + 1 if 0 ≤ i < r, q if r ≤ i < h, 0 otherwise,
where q and r are respectively the quotient and the remainder in the Euclidean division of A by h. for all u such that |u| = h and i∈Z u i = A ≥ h. Without loss of generality we can suppose that the support of u is a contiguous subset of Z and that this subset is 0, h -1 . We then divide our problem into two cases:

2 (

 2 b) Solutions to X T u = s minimizing the L1 norm

Figure 1 :

 1 Figure 1: Comparison with the classic compressive sensing case

  Figure 3: Maximum error

Figure 4 :

 4 Figure 4: Signature detection on the Giza image

Figure 5 :

 5 Figure 5: Percentage of wrong detection for different measurement rate, sensing matrix and regularizer on the Giza image

Figure 6 :

 6 Figure 6: Spectral signature of buildings

  (a) Moffett field image in false color (b) Template matching on Fig. a (c) Compressive template matching, 30% of data, L1 regularizer (d) Compressive template matching, 30% of data, T V /L1 regularizer

Figure 7 :

 7 Figure 7: Signature detection on Moffett field image

Figure 8 :

 8 Figure 8: Percentage of wrong detection for different measurement rate, sensing matrix and regularizer on the Moffett image

Definition 1 .

 1 spectralized image spec P (I) of I with respect to the pattern's structure P is the 3-dimensional matrix [I ∧ S -(1,0) (I) ∧ S -(1,1) (I)]. In its linearized form, we have spec P (I) = [vec(I), vec(S -(1,0) (I)), vec(S -(1,1) (I))] which can also be written [vec(I), Q -(1,0) vec(I), Q -(1,1) vec(I)] using (28). We then have the following definition. Given a gray-scale image I and a pattern structure P , the spectralized image spec P (I) is the matrix [vec(I), Q -p2 vec(I), . . . , Q -p |P | vec(I)].

  (a) Grayscale image (b) Spectralization along the hook pattern

Figure 9 :

 9 Figure 9: Spectralization of a grayscale image along the hook pattern

Figure 12 :

 12 Figure 12: Average number of pattern detection errors with respect to virtual measurement rate

  (a) Giza image (b) Compressive pattern matching, 10% of data (c) Compressive pattern matching, 20% of data (d) Compressive pattern matching, 30% of data

Figure 13 :

 13 Figure 13: Pattern detection on Peppers image

Figure 14 :

 14 Figure 14: Average error detection with respect to noise percentage for a fixed measurement rate of 30%

  (m)) i + (|m| + a -1)(b -1). (53)If we take the lower bound on the left side of the inequality for all possible measurement patterns E such that |E| = A, we have|E + P | ≥ inf h≥1 inf |m|=h i∈Z (φ a (m)) i + (h + a -1)(b -1) . (54)Using lemma .1 and plugging it back in (54) we have|E + P | ≥ A + (a -1)(b -1) + inf h≥1 (a -1) A h + (b -1)h.(55)

Proof.

  It is easy to show that v obeysi∈Z v i = A and i∈Z (φ a (v)) i = A + (a -1) A h .Then, it suffices to show that,i∈Z (φ a (u)) i ≥ i∈Z (φ a (v)) i ,

  Compressive Pattern Matching algorithm E with every element of P . The pattern E + P is then rectangular-shaped and contained in a rectangle of height 50 + 6 -1 and width 82 + 10 -1. More precisely, we have |E + P | = 5001 which gives α(P ) ≈ 1.22. The effective measurement rate is then 1.22 × 25 ≈ 31% which means that we have to take effective measurements at a rate of 31% on the color image to be able to run the pattern matching minimization problem with a 25% measurement rate on the spectralized image.

			1 F virt ;
	Solve arg min u≥0	φ(u) 1 s.t.	Au -s 2 < err;
	Algorithm 2:

Available at http://opticks.org/confluence/display/opticks/Sample+Data#SampleData

Available at http://aviris.jpl.nasa.gov/html/aviris.freedata.html

We also remark that for all i ∈ Z and j ∈ {i, i -1, . . . , i -a + 1}, we have

we can write (φ a (m)

• If not, let i 0 ∈ 0, h-1 be an index such that u i0 ≥ 2+u i for all i = i 0 . We choose another index j 0 distinct from i 0 and we construct a new sequence u ′ corresponding to the measurement pattern E ′ as follows

We remark that

By induction on u i0 we are reduced to the first case.

Thus, for all u such that |u| = h, we have i∈Z (φ a (u)) i ≥ A + (a -1) A h , which concludes the proof.


Laure Vieu

On the compositionality of temporal locating adverbial modification

Semantic puzzles raised by temporal locating adverbials -e.g., ce soir-là (that evening), à huit heures (at eight), pendant la réunion (during the meeting), deux jours plus tard (two days later)-have been less focused on than those involving temporal quantificational or duration adverbials -à toutes les réunions (during every meeting), en une heure (in one hour) [START_REF] Hitzeman | Temporal adverbials and the syntax-semantics interface[END_REF][START_REF] Pratt | Temporal prepositions and temporal generalized quantifiers[END_REF][START_REF] De | Aspect shift and coercion[END_REF]. But these adverbials, whose semantics amounts to the location of a single eventuality with respect to a time or another eventuality, are involved in phenomena apparently jeopardizing the compositionality of adverbial modification. In this paper, we focus on French data for which we propose an account in Segmented Discourse Representation Theory (SDRT [START_REF] Asher | Logics of Conversation[END_REF]).

The compositionality issue we are interested in here appears for our approach to locating adverbials, which assumes that the location relation is contributed by the adverbial itself [START_REF] Michel Aurnague | The syntax and semantics of locating adverbials[END_REF][START_REF] Vieu | Locating adverbials in discourse[END_REF]. This is against the standard view of, e.g., [START_REF] Dowty | Tenses, time adverbs and compositional semantic theory[END_REF][START_REF] Kamp | From Discourse to Logic[END_REF][START_REF] Reyle | Ups and downs in the theory of temporal reference[END_REF] which assumes that the adverbial simply qualifies a temporal referent systematically introduced along with the location relation by the tense. The standard approach is unable to grasp the semantics of those locating adverbials that involve distance and other temporal relations than simple inclusion. It also cannot account for the fact that temporal NPs such as that evening, monday, the following day are referential expressions and should introduce themselves temporal referents.

As in DRT and SDRT, we use the coarse binary event / state ontological distinction among eventualities. Such a distinction is generally marked by tense (e.g., Imparfait and Passé simple) in French narrative texts, but possibly results from a combination of the Aktionsart of the argument-predicate structure, tense and aspect, and even the larger discourse context (see e.g., [START_REF] Kamp | From Discourse to Logic[END_REF][START_REF] De | Contraintes aspectuelles et réinterprétation contextuelle[END_REF] ). It might be argued that finer-grained distinctions are needed [START_REF] De | Aspect shift and coercion[END_REF][START_REF] Caudal | Stage structure and stage salience for event semantics[END_REF] but for the purposes of this paper, this binary distinction suffices.

We focus here on two sides of the compositionality issue: the change of the location relation in the semantics of the adverbial when combined with an event or a state as in (1) (see [START_REF] Kamp | From Discourse to Logic[END_REF][START_REF] Reyle | Ups and downs in the theory of temporal reference[END_REF]), and the change of eventuality category introduced by the semantics of the Plus-que-parfait when the locating adverbial changes position in the sentence as in [START_REF] Asher | Setting the background in discourse[END_REF] (see e.g., [START_REF] Dickey | The processing of tense[END_REF]).

(1) a. Ce soir-là (t), Marie alla au cinéma (e) (That evening, Mary went to the movies) e is temporally included in t b. Ce soir-là (t), il pleuvait (s) (That evening, it was raining) s and t temporally overlap

(2) a. Marie était rentrée à la maison à 8h (Marie had come home at 8) location of the coming home event b. A 8h, Marie était rentrée à la maison (At 8, Marie had come home) ambiguous between location of the coming home event and location of the resulting state of having come home (i.e., being at home)1 [START_REF] Dowty | Tenses, time adverbs and compositional semantic theory[END_REF][START_REF] Kamp | From Discourse to Logic[END_REF], as most formal semantic works on locating adverbials, disregarded the effects of different positions in the sentence. More recent work [START_REF] Hitzeman | Temporal adverbials and the syntax-semantics interface[END_REF][START_REF] De | Focus. Linguistic, cognitive and computational perspectives[END_REF][START_REF] Dickey | The processing of tense[END_REF] follow syntacticians [START_REF] Reinhart | Definite NP anaphora and C-command domains[END_REF] who have shown that, although PPs usually are VP-adjuncts, preposed PPs2 are not VP-adjuncts that have moved, but IP-adjuncts. 3 In particular, [START_REF] De | Focus. Linguistic, cognitive and computational perspectives[END_REF] shows that these different syntactic positions affect information partition, as illustrated by the different questions under discussion (QUD) in (3). However, this doesn't suffice to explain the changes in (1) and ( 2).

(3) a. John arrived at 8 : When did John arrive? b. At 8, John arrived : What happened at 8?

Other areas of linguistics have focused on the discursive implications of the IP-adjunct position of adverbials, something to be expected given their role external to the clause. In preposed IP-adjunct position, locating adverbials may take scope over several clauses grouped together in so-called "frames" thus transforming them in "frame introducers" [START_REF] Charolles | L'encadrement du discours : univers, champs, domaines et espaces[END_REF]. In addition, preposed adverbials have a role in discourse segmentation as markers of discourse topic shifts [START_REF] Bestgen | Temporal adverbials as segmentation markers in discourse comprehension[END_REF]. In [START_REF] Vieu | Locating adverbials in discourse[END_REF] we proposed a formal account of both the framing and the topic-shift roles within Segmented Discourse Representation Theory (SDRT [START_REF] Asher | Logics of Conversation[END_REF]), on the basis of a new, "forward-looking", use of discourse topics, originally introduced in SDRT for summarizing previous discourse. [START_REF] Asher | Setting the background in discourse[END_REF] shows that forward-looking topics are also involved in "inversed" occurrences of the discourse relation Background, as in (4-b) and as opposed to the standard (4-a), a discourse relation implying a spatio-temporal overlap between an event and a state. The present paper aims at showing that these two proposals can be combined and extended to explain the meaning changes involved in ( 1) and ( 2), preserving compositionality of adverbial modification.

Following [START_REF] Vieu | Locating adverbials in discourse[END_REF], we assume that a standard existential closure on the semantics of an adverbial like à 8h in preposed IP-adjunct position yields an implicit clause (a new basic segment), corresponding to a new discourse topic. This forward-looking topic with initial propositional content "some event happened at eight", similar to the QUD in (3-b), is expecting a segment to come (e.g., the clause modified by the adverbial and possibly others) to attach with the Elaboration relation to it.

Following [START_REF] Asher | Setting the background in discourse[END_REF] and classical studies on the anaphoricity of the French Imparfait, we assume that when a state is described in null context, there is an expectation that a foreground (an event or a sequence of events) is to come in the stage thus set. Indeed, (1-a) can stand alone and make a very short discourse, while (1-b) cannot. So, state-describing clauses in a null context also introduce a forward-looking topic segment (an event clause) expecting to be elaborated by some other event clause, and the state clause is attached by Background to this topic.

We now further assume that "non-spanning" locating adverbials, like those seen above, require that the eventuality they locate be an event, in contrast with "spanning" locating adverbials, like those built with the preposition depuis (since), which require to be combined with states. The location relation involved in a non-spanning adverbial like ce soir-là or à 8h is the temporal inclusion of the event in the time it refers to. This yields the standard interpretation of (1-a), even though the adverbial is IP-adjunct, because the main clause introduces an event and attaches to the topic with Elaboration, which also implies temporal inclusion, a transitive relation. When a non-spanning locating adverbial is IP-adjunct of a state-describing clause, as in (1-b), the main clause which introduces a state attaches to the topic (which is an event clause because of the adverbial) with Background instead (because of an ontological constraint of homogeneity imposed by the parthood relation in the semantics effects of Elaboration). This yields an overlap with the topic event, and so an overlap with the time ce soir-là refers to and in which the topic event is included, again recovering the standard interpretation. Note that the topic still expects some event-describing clause to elaborate it, which predicts that (1-b) cannot stand alone in null context.

Finally, to explain (2), we standardly [START_REF] Kamp | From Discourse to Logic[END_REF][START_REF] De | Contraintes aspectuelles et réinterprétation contextuelle[END_REF] assume that a perfect tense introduces both a past event and its resulting state. In a SDRT account, one eventuality must be identified as the "main eventuality"4 and since authors consider that the resulting state is focused on, it would seem natural to have the resulting state as the main eventuality, something adequate for the present perfect and the past perfect. For French Passé Composé and Plus-que-parfait, however, whether the main eventuality actually is the event or the state is decided by the discourse context, as seen in (2-b), and thus left underspecified.

When in VP-adjunct position, the composition process enables the adverbial expecting an event to locate the event that will be provided by the tense, a process in which the main eventuality label plays no role. When in IP-adjunct position, the attachment depends on the choice of the main eventuality (which depends on the context): if the event is chosen, the main clause will elaborate the topic segment generated by the adverbial, which is an event clause (because à 8h is non-spanning); if the state is chosen, the main clause will not elaborate the topic segment, it will attach by Background instead, with the expected semantic effects as above.

To sum up, our approach assumes a unique semantics for the adverbials and the tenses, and acknowledges the contribution of IP-level composition in discourse representation construction.

  Marie rentra à la maison. Il pleuvait. (Marie came home. It was raining.) b. Il pleuvait. Marie rentra à la maison. (It was raining. Marie came home.)

These two interpretations occur in contexts such as: Qu'avait fait Marie ce soir-là ? (What had Marie done that evening?) / Où était Marie à 8h ? (Where was Marie at 8?). Note that in English, the present perfect is not ambiguous (only resulting state reading).

A right dislocation, as in Marie était rentrée à la maison, à 8h, something prosodically marked, is temporally interpreted as (2-b) and analyzed as IP-adjunct too.

Locating adverbials do not have a fixed syntactic position, contrary to most adverbials. For instance, manner adverbials are always VP-adjuncts, and evaluative adverbials are always IP-adjuncts[START_REF] Bonami | Adverb classification[END_REF].

The main eventuality is a label on one eventuality of the segment, to be used at the semantics-pragmatics interface, i.e., at the discourse level, but this label plays no role within the semantics of the segment itself.