Sylvain Boltz

Ariane Herbulot

Eric Debreuve
email: debreuve@i3s.unice.fr

Michel Barlaud
email: barlaud@i3s.unice.fr

Gilles Aubert
email: gaubert@math.unice.fr

É Debreuve

Motion and

Keywords: Spatio-temporal segmentation, nonparametric distribution, joint entropy, active contour

come

Introduction

Video segmentation aims at partitioning some video frames into objects and background. (For simplicity, it will be supposed that there is a single object.) This task can be performed without motion computation. If reference values of some descriptors are available (e.g., mean color, color variance, color distribution. . . of the object of interest), an object can be segmented by minimizing a distance between the actual values of the descriptors computed on a candidate object domain and the reference values [START_REF] Freedman | Active contours for tracking distributions[END_REF]. However, the lack of sensitivity of some descriptors near the object boundary (e.g., the color distribution might not vary significantly if the candidate domain is slightly deformed) and the degree of freedom of the object motion (a priori infinite) may increase the number of potential solutions. Therefore, the segmentation framework involving motion computation will be considered.

Let us first consider the motion estimation task. Dense flow field estimation (i.e., one motion vector per pixel) is an underdetermined problem. Moreover, when using the first order approximation of the brightness/color constancy constraint, only the motion component in the direction of the image gradient can be estimated. This limitation is known as the aperture problem. Motion estimation is therefore an ill-posed problem. It needs to be regularized, i.e., constrained. On the one hand, the so-called global methods estimate a dense flow field while imposing the solution to be smooth [START_REF] Alvarez | A scalespace approach to nonlocal optical flow calculations[END_REF][START_REF] Brox | High accuracy optical flow estimation based on a theory for warping[END_REF][START_REF] Weickert | Variational optic flow computation with a spatio-temporal smoothness constraint[END_REF]. On the other hand, local methods constrain the motion to follow a parametric model (e.g., translation, affine motion, homography) with constant parameters, either in the whole image or within blocks or regions [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF][START_REF] Odobez | Robust multiresolution estimation of parametric motion models[END_REF][START_REF] Wu | A gradient-based method for general motion estimation and segmentation[END_REF]. Both approaches have also been combined [START_REF] Bruhn | Combining the advantages of local and global optic flow methods[END_REF]. Given the link between motion estimation and object segmentation in a video, it can be noted that global methods require anisotropic smoothing to preserve object boundaries [START_REF] Weickert | Variational optic flow computation with a spatio-temporal smoothness constraint[END_REF] whereas local methods are characterized by a chicken-and-egg dilemma: (i) estimating motion knowing the object boundary while (ii) the boundary is defined as an optimal partition knowing the motion of the object and its neighborhood. This suggests to perform motion estimation and segmentation jointly [START_REF] Cremers | Motion competition: A variational framework for piecewise parametric motion segmentation[END_REF], which will be the approach followed here.

Focusing on motion estimation again, imposing the brightness/color constancy constraint is equivalent, in variational terms, to minimizing a function of the motion compensation error (MCE), or of its first order approximation, as already mentioned. There is a correspondence between the choice of one such function and an assumption on the distribution of the MCE, e.g., the square function and the assumption of a Gaussian distribution or the absolute value [START_REF] Wu | A gradient-based method for general motion estimation and segmentation[END_REF] and the assumption of a Laplacian distribution. This point of view will be referred to as parametric since the underlying distribution is characterized by a small set of parameters. In contrast, it is proposed to get rid of the parametric assumption on the data by trying to estimate the actual distribution as proposed for various related problems [START_REF] Comaniciu | Real-time tracking of non-rigid objects using mean shift[END_REF][START_REF] Aubert | Image segmentation using active contours: Calculus of variations or shape gradients?[END_REF][START_REF] Kim | A nonparametric statistical method for image segmentation using information theory and curve evolution[END_REF][START_REF] Mittal | Motion-based background subtraction using adaptive kernel density estimation[END_REF] or in the context of shape prior [START_REF] Cremers | Kernel density estimation and intrinsic alignment for shape priors in level set segmentation[END_REF][START_REF] Leventon | Statistical shape influence in geodesic active contour[END_REF]. This approach will be referred to as nonparametric. Distribution approximation methods have been developed in statistics, most notably Parzen windowing [START_REF] Parzen | On the estimation of a probability density function and mode[END_REF][START_REF] Silverman | Density Estimation for Statistics and Data Analysis[END_REF][START_REF] Scott | Multivariate Density Estimation: Theory, Practice, and Visualization[END_REF] and the k th -nearest neighbor (kNN) framework [START_REF] Fukunaga | Introduction to statistical pattern recognition[END_REF][START_REF] Goria | A new class of random vector entropy estimators and its applications in testing statistical hypotheses[END_REF].

In this nonparametric framework, we propose to use a unique statistical measure to both estimate the motion and segment the object. (A review of statistical methods in image segmentation was done recently [START_REF] Cremers | A review of statistical approaches to level set segmentation: Integrating color, texture, motion and shape[END_REF].) Among the popular measures such as entropy [START_REF] Neemwuchwala | Entropic Graphs for Registration[END_REF], mutual information [START_REF] Wells | Multi-modal volume registration by maximization of mutual information[END_REF], or the Kullback-Leibler divergence [START_REF] Rubner | The earth mover's distance as a metric for image retrieval[END_REF], the entropy [START_REF] Boltz | Entropy-based space-time segmentation in video sequences[END_REF][START_REF] Herbulot | Robust motion-based segmentation in video sequences using entropy estimator[END_REF] was chosen for its interesting properties (it is a measure of dispersion and it is robust to outliers -see Section 3.1) and because manipulating a single distribution (the distribution of the MCE) was preferred over taking the reference/target distribution comparison approach.

Motion-based segmentation can fail in areas insufficiently textured. In particular, the MCE is equal to zero in any homogeneous region. Therefore, adding such a region to, or subtracting it from, a given segmentation still produces potential solutions. This can be solved with the help of shape regularization [START_REF] Cremers | Motion competition: A variational framework for piecewise parametric motion segmentation[END_REF], by adding spatial terms to the motion-based energy [START_REF] Brox | Unsupervised segmentation incorporating colour, texture, and motion[END_REF][START_REF] Paragios | Geodesic active regions: A new framework to deal with frame partition problems in computer vision[END_REF], or by processing color and motion sequentially [START_REF] Dórea | Generation of long-term color and motion coherent partitions[END_REF]. This last alternative is interesting but asks the difficult question of ordering the features, say, by importance (especially if involving even more features). The first two ones often requires a nontrivial adjustment of the weighting of the different terms. It will be shown that, using joint distributions, an objective choice of the weighting of the motion term and the spatial term can be made (namely, equal weighting or, equivalently, weight-free).

In brief, we propose to define a single spatiotemporal energy1 to perform joint motion estimation and segmentation. To account for noise and model mismatch, the energy will be based on a statistical measure, namely entropy. In order to adapt to the data, no assumption will be made on the MCE or color distributions; they will be estimated using a nonparametric method. Finally, it will be shown that, with the proposed approach, the motion term need not be weighted relative to the spatial term. In a way, this offers a solution to the implementation of the operator AND between several properties (related here to motion "and" color) jointly describing the object of interest.

Also note that, although some equations below have some similarities with existing, likelihood-based or Bayesian methods, the philosophy here is different and somewhat more general. Bayesian methods are directly tied to the definition of the probability of the (observed) image or sequence given a segmentation. Assuming independence between the pixels, an energy is derived, which usually writes as a sum or integral of log probabilities. In the proposed approach, each region of the segmentation is regarded as a set of samples or realizations. The energy is defined as a function of a multivariate distribution in order to best fit the needs of the specific application. The link between the energy and the samples is then made through a nonparametric, Parzen-like or variable-size kernel-based distribution estimation. This allows for example to keep the same energy definition while using different object features or different assumptions on the features. In particular, one could think of discarding the assumption of independence between the pixels and use a patch-based (or neighborhood-based) approach [START_REF] Awate | Unsupervised, Information-Theoretic, Adaptive Image Filtering for Image Restoration[END_REF] to change the spatial information from color to texture.

The paper is organized as follows: Section 2 details the problem statement. In Section 3, the classical parametric assumption on the MCE distribution is discarded and the proposed nonparametric framework for video segmentation, involving the actual residual and color distributions, is described. A single spatiotemporal energy is proposed to perform motion estimation and motion-based segmentation simultaneously. A piecewise motion model is introduced to allow enough flexibility for segmenting articulated objects. An active contour procedure is proposed in Section 4 to minimize the energy. Finally, Section 5 presents some results on synthetic and natural video sequences.

Problem Statement

The motion of an object domain Ω can be computed by choosing a motion model and finding the motion parameters that minimize a function of the MCE over Ω. At a pixel level, making the assumption of brightness/color constancy, the MCE is classically equal to the following residual

e n (v(x), x) = I n (x) -I n+1 (x + v(x)) (1)
where x is a pixel of Ω, I n is the n th grayscale or color frame of the sequence, and v(x) is the apparent motion between I n and I n+1 at x (known as the optical flow).

Ideally, e n (v(x), x) is equal to zero up to some noise. In grayscale, this condition provides a single equation for two unknowns (the components of v(x)) and, both in grayscale and color, it is likely that several pixels y have the same value I n+1 (y). As a consequence, the motion estimation problem cannot be solved without additional constraints. A possible way to constrain the problem is to assume that the motion is coherent with a chosen model inside Ω [START_REF] Wu | A gradient-based method for general motion estimation and segmentation[END_REF]. Then, the motion estimate v can be computed as

v = arg min w Ω ϕ(e n (w, x)) dx (2)
where ϕ can be, for example, the square function, the absolute value, or a function typical of the robust estimation framework [START_REF] Black | The robust estimation of multiple motions: parametric and piecewise-smooth flow fields[END_REF][START_REF] Charbonnier | Deterministic edge-preserving regularization in computed imaging[END_REF]. The motion-based segmentation of frame I n can be formulated as the largest domain Ω inside which the motion is coherent with model (2), formally,

     Ω = arg min Ω Ω ϕ(e n (v(Γ), x)) dx v(Γ) = arg min w Ω ϕ(e n (w, x)) dx ( 3
)
where Γ is the boundary ∂Ω of Ω. Note that writing v(Γ) or v(Ω) is only a matter of notation since Ω is completely determined by Γ and conversely. Let us denote by E t the following domain energy 2

E t (Γ) = Ω ϕ(e n (v(Γ), x)) dx . (4)
Choosing ϕ results in making an assumption on the distribution of the residual e n in Ω. For example, if ϕ is equal to the square function, the motion estimation is performed based on the assumption that the distribution is Gaussian; if ϕ is equal to the absolute 2 Subscript t stands for temporal.

value, the distribution is assumed to be Laplacian3 . However, these assumptions may not be appropriate. In particular, the presence of outliers in the residual (e.g., due to occlusions, mismatch between the chosen motion model and the actual motion, variation of luminance. . . ) may result in a complex, multimode distribution. As a consequence, the motion estimator in (3) may be biased, leading to a loss of accuracy of the motion-based segmentation.

Proposed segmentation energy

Three steps will be taken to derive the proposed energy: the definition of an ideal energy, its simplification, and its "symmetrization" (Sections 3.1, 3.2 and 3.3, respectively).

Nonparametric, entropy-based energy

To account for the true distribution of the residual e n , and in general any feature that will be used for segmenting, it is proposed to make the energy depend on an estimation of the feature distributions rather than on the features themselves as it was the case in (4) concerning the residual. For the present segmentation task, the residual e n will be combined with the spatial feature I n (similar combinations of geometry and radiometry have been proposed [START_REF] Elgammal | Probabilistic tracking in joint feature-spatial spaces[END_REF][START_REF] Leventon | Level set based segmentation with intensity and curvature priors[END_REF]). The proposed energy has the following form

   E(Γ) = - 1 |Ω| Ω log f (e n (v(Γ), x), I n (x)) dx v(Γ) = arg min w E Γ (w) ( 5
)
where f is the joint distribution of the residual e n (v(Γ)) and the image color I n inside the object domain Ω, and

E Γ (w) = - 1 |Ω| Ω log f (e n (w, x), I n (x)) dx . (6)
Energy ( 5) is the continuous version of the Ahmad-Lin approximation of differential entropy [START_REF] Ahmad | A nonparametric estimation of the entropy for absolutely continuous distributions[END_REF]. In both ( 5) and ( 6), f is the joint distribution of the residual and the color. The residual being a function of the motion, f is itself a function of v(Γ) in the former and w in the latter.

Let us see why this choice of energy is interesting. First, entropy is a measure of dispersion. If the segmentation is optimal, the residual should be distributed around zero with a minimal dispersion. Similarly, if the object is assumed to be piecewise homogeneous, the color distribution has a small dispersion. Moreover, entropy coincides locally asymptotically with likelihood at the optimum4 . Thus, a minimum entropy criterion should have near optimal performances in case of a parametric distribution while being able to adapt to nonparametric cases. In particular, entropy appears to be less sensitive to outliers in practice.

Note that this approach defines a general framework for multimodal segmentation: the joint entropy allows to combine an arbitrary number of features/modalities. In practice, though, the number of modalities that can be combined together is limited by the number of samples available, i.e., the number of pixels of the image or sequence frame. Indeed, if the samples fill the distribution space too sparsely, then the entropy (or any other statistical measure) cannot be approximated accurately. This problem, known as the curse of dimensionality, can be solved to a certain extent by the use of estimators based on the k th -nearest neighbor (kNN) framework [START_REF] Boltz | Highdimensional statistical distance for region-ofinterest tracking: Application to combining a soft geometric constraint with radiometry[END_REF][START_REF] Fukunaga | Introduction to statistical pattern recognition[END_REF][START_REF] Goria | A new class of random vector entropy estimators and its applications in testing statistical hypotheses[END_REF].

Simplification using marginal distributions

A fixed-size kernel-based procedure will be employed to estimate the distributions (see Section 3.5). To avoid that the entropy estimation be biased as an effect of the curse of dimensionality, energy (5) will be "simplified". Thus, the residual and the color will be assumed to be independent (See Appendix B). As a consequence, energy (5) can be rewritten as the following sum involving the marginal distributions

E(Γ) = - 1 |Ω| Ω log f t (e n (v(Γ), x)) dx - 1 |Ω| Ω log f s (I n (x)) dx (7) = E t (Γ) + E s (Γ) (8)
where subscript t, respectively s, in f t and E t , respectively f s and E s , stands for temporal, respectively spatial. Note that the second integral in [START_REF] Boltz | Entropy-based space-time segmentation in video sequences[END_REF] was proposed for image segmentation [START_REF] Kim | A nonparametric statistical method for image segmentation using information theory and curve evolution[END_REF].

The temporal energy in ( 7) is of the form

E t (Γ) = Ω ψ(f t (e n (v(Γ), x))) dx . (9)
One can say that the parametric approach ( 4) is extended to nonparametric distributions by substituting for a function of the residual ϕ(e n ) a function of its distribution ψ(f t (e n )). By making the assumption of independence, one obtains a sum of two energies, meeting the philosophy usually adopted when one want to simultaneously minimize several energies. However, in general, weighting parameters are introduced to tune the influence of the respective energies whereas, here, there are no such weights (it seems indeed natural not to favor any of the two terms since they have the same unit).

As suggested at the end of Section 3.1, this energy simplification might not be necessary if the distributions were estimated using the kNN framework [START_REF] Fukunaga | Introduction to statistical pattern recognition[END_REF][START_REF] Goria | A new class of random vector entropy estimators and its applications in testing statistical hypotheses[END_REF] as opposed to using the Parzen windowing approach (see Section 3.5). There is one concern about using the kNN framework in the present case though: as will be shown in Section 4.1, estimation of the distributions will be necessary for the proposed active contour process while kNN-based estimations are known to be noisy.

Region competition

In practice, due to approximations and roundoff errors, energy [START_REF] Boltz | Entropy-based space-time segmentation in video sequences[END_REF] might have the empty set as a unique global minimizer. A common solution is known as region competition: the energy of the background is added to the energy (7) of the object. It is not mandatory to use the same energy for the object and the background. However, it can be appropriate to do so. As a result, the segmentation will represent a tradeoff between the minimization of the object energy and the minimization of the background energy. It can also be interpreted as the maximal separation between object and background descriptors [START_REF] Yezzi | A fully global approach to image segmentation via coupled curve evolution equations[END_REF], here, the respective joint distributions.

To account for the relative areas of the object and the background, or, in other words, to account for the probability of a pixel to belong to either of them, the following weighted sum will be used

E rc (Γ) = |Ω| |D| E(Γ) + |Ω c | |D| E(Γ c ) ( 10
)
where Ω c is the complement of Ω in D, the image domain, and Γ c is its boundary ∂Ω c (the division by |D| of |Ω| and |Ω c | can be omitted since it has no influence on the minimization). Energy ( 10) can be rewritten as

E rc (Γ) = p(C = 1) E(Γ) + p(C = 0) E(Γ c ) ( 11
)
where C is the characteristic function of the object and p(C = i) denotes the probability of the event C = i. As defined in [START_REF] Black | The robust estimation of multiple motions: parametric and piecewise-smooth flow fields[END_REF], energy E(Γ) is (an approximation of) the joint entropy of the residual and the color conditional on C = 1. Let us denote it by H(e n , I n |C = 1).

Equivalently, E(Γ c ) is equal to H(e n , I n |C = 0). Then, Eq. ( 11) is equal to

E rc (Γ) = i∈{0,1} p(C = i) H(e n , I n |C = i) (12)
Therefore, energy ( 10) is equal5 to the conditional joint entropy of the residual and the color H(e n , I n |C).

Motion estimation

As mentioned in Section 2, the motion v is assumed to follow a given model inside Ω. For example, it can be defined by a set of parameters p [START_REF] Odobez | Robust multiresolution estimation of parametric motion models[END_REF]. Then, estimating v in ( 9) is only a matter of estimating p. This task is certainly made easier if the relation between v and p is linear

v(Γ) = M p(Γ) ( 14
)
where M is a 2 × l matrix if p is an l-vector. Even if the motion model is complex, it will hardly account for general motions such as motions of articulated objects, and if it does, solving for the model parameters is likely to be an ill-posed inverse problem. Instead, we propose to keep the model simple while solving for its parameters locally. Frame I n is divided into k blocks B i of identical size, where k depends on the frame size.

Let Ω i be the intersection of Ω with B i and let Γ i be the boundary ∂Ω i of Ω i (see Fig. 1). The temporal energy ( 9) is replaced with

E local t (Γ) = - 1 |Ω| Ω log f t (e n (v 1 , . . . , v k , x)) dx (15)
where v i is a short notation for v(Γ i ), the motion of Ω i . (The consequence of using this local approach is discussed in Appendix D.) In this context, the motion model can simply be translation. Therefore, Eq. ( 1) is replaced with

e n (v i , x) = I n (x) -I n+1 (x + v i ), x ∈ Ω i . (16)
This local approach will be used when the object of interest is articulated (see Section 5.4). In the other experiments, a global translation will be used. It corresponds to decomposing I n into a single block B 1 covering the whole frame. Note that in the following, for clarity, the notations E t and e n (v(Γ), x) will be preferred over E local t and e n (v 1 , . . . , v k , x), respectively. Finally, to minimize the influence of occlusions, expression ( 16) is regarded as the forward residual and compared with the backward version as follows 17) where min abs is equal to

e n (v, x) = min abs {I n (x)-I n+1 (x+v), I n (x)-I n-1 (x-v)} (
min abs {a, b} = a if min{|a|, |b|} = |a| b if min{|a|, |b|} = |b| . (18)
Function ( 18) is not differentiable. However, in the present work, it does not need to be differentiated (see Appendix C).

Distribution estimation

Parzen windowing is a classical distribution estimation procedure [START_REF] Parzen | On the estimation of a probability density function and mode[END_REF]. The following continuous version was used

f (r) = 1 |Ω| Ω K σ (r -g(x)) dx ( 19
)
where |Ω| is the measure of Ω, K σ is a Gaussian kernel with zero mean and a variance equal to σ 2 , and g is a random variable whose distribution is to be estimated (i.e., e n (v(Γ)) or I n ). It is usual to adapt σ 2 to the data [START_REF] Silverman | Density Estimation for Statistics and Data Analysis[END_REF][START_REF] Scott | Multivariate Density Estimation: Theory, Practice, and Visualization[END_REF].

Segmentation using active contours 4.1 Shape gradient of the energy

Minimization of energy [START_REF] Boltz | Entropy-based space-time segmentation in video sequences[END_REF] requires the computation of its derivative with respect to Γ. There exists an infinite number of ways of deforming Γ. The shape derivative [START_REF] Delfour | Shapes and geometries: Analysis, differential calculus and optimization[END_REF][START_REF] Hintermuller | A second order shape optimization approach for image segmentation[END_REF][START_REF] Jehan-Besson | DREAM 2 S: deformable regions driven by an eulerian accurate minimization method for image and video segmentation[END_REF][START_REF] Aubert | Image segmentation using active contours: Calculus of variations or shape gradients?[END_REF]] of ( 7) can be interpreted as the derivative in a direction F , a vector field defined on Γ. It can be shown that the shape derivative of ( 9) is equal to (see Appendix C)

dE t (Γ, F ) = 1 |Ω| Γ log f t (e n (v(Γ), s)) -1 + E t (Γ) + 1 |Ω| Ω K σ (e n (v(Γ), s) -e n (v(Γ), x)) f t (e n (v(Γ), x)) dx N (s) • F (s) ds ( 20
)
where N is the inward unit normal of Γ. Note that the distribution f t appears explicitly in [START_REF] Elgammal | Probabilistic tracking in joint feature-spatial spaces[END_REF], hence the necessity to estimate it even though the kNN framework allows to compute (9) without computation of the underlying distribution [START_REF] Fukunaga | Introduction to statistical pattern recognition[END_REF][START_REF] Goria | A new class of random vector entropy estimators and its applications in testing statistical hypotheses[END_REF].

The expression of dE s is similar to [START_REF] Elgammal | Probabilistic tracking in joint feature-spatial spaces[END_REF] (see Appendix C). Finally, the shape derivative of [START_REF] Boltz | Entropy-based space-time segmentation in video sequences[END_REF]

is equal to dE(Γ, F ) = dE t (Γ, F ) + dE s (Γ, F ) . (21)
The shape derivative [START_REF] Freedman | Active contours for tracking distributions[END_REF] has the following form

dE(Γ, F ) = Γ ((α t (s) + α s (s)) N (s)) • F (s) ds(22) = α N, F (23)
where , is the L 2 -inner product on Γ. Therefore, α N is, by definition, the gradient of ( 7) at Γ associated with this inner product.

Region competition

The shape derivative of ( 10) can be obtained by applying the traditional differentiation rule (u v) ′ = u ′ v + u v ′ and determining the shape derivative of |Ω| (see Appendix C.3). The terms related to the object and the terms related to the background can be gathered together by noting that Γ and Γ c are identical up to a change of orientation. In particular, the inward unit normal N c of Γ c is equal to -N .

Evolution equation

Based on the notion of gradient defined in Section 4.1, energy (10) can be minimized using a steepest descent procedure in the space of contours. The following contour evolution process is known as the active contour technique [START_REF] Caselles | Geodesic active contours[END_REF][START_REF] Hintermuller | A second order shape optimization approach for image segmentation[END_REF]: an initial contour 6 is iteratively deformed in the opposite direction of the gradient until a convergence condition is met. The evolution equation of the active contour is written as follows

   Γ(τ = 0) = Γ 0 ∂Γ ∂τ = (α c -α) N ( 24
)
where τ is the evolution parameter and α c has the same expression as α but is evaluated on Ω c . The convergence condition is α c -α = 0.

5 Experimental results

Test settings

As a reminder, the proposed segmentation energy has the following form

E rc (Γ) = |Ω| E(Γ) + |Ω c | E(Γ c ) ( 25
)
6 For example, a user-defined contour.

where

E(Γ) = E t (Γ) + E s (Γ) . (26)
For comparison purposes, energy (25) will also be used in two incomplete forms: when E s is removed from the definition of E in [START_REF] Jehan-Besson | DREAM 2 S: deformable regions driven by an eulerian accurate minimization method for image and video segmentation[END_REF], the energy will be called temporal energy; when E t is removed from the definition of E, the energy will be called spatial energy. In its complete form, it was already defined as the spatiotemporal energy.

The tests were performed on synthetic and natural sequences composed of 300 × 300-pixel frames and cif7 frames, respectively, all defined in the Y U V -color space. The V channel was discarded. Therefore, the distributions of I n and e n are functions from R 2 to R with support [0, 255] 2 and [-255, 255] 2 , respectively. In computing e n , I n+1 (x + v) was bilinearly interpolated. Independence between spatial and temporal information was assumed in Section 3.2 in order to write E as the sum of E t and E s . The computation of these two components was also simplified by assuming independence between the channels Y and U . As a consequence, E t and E s were themselves estimated as the sum of a Y -based entropy and a U -based entropy.

The standard deviation σ of the Parzen kernel (see Eq. ( 19)) was adapted to the data8 by using the empirical standard deviation σ of the residual or the color in Ω σ = 0.9 min(σ, p/1.34) |Ω| -1/5 [START_REF] Kim | A nonparametric statistical method for image segmentation using information theory and curve evolution[END_REF] where p is the interquartile range of the data in Ω. Therefore, σ should be regarded as a function of Ω. This would add some terms to the shape derivative dE since expression (52) would not be valid anymore. However, these terms can be neglected because σ does not change significantly between two iterations of the active contour process. As mentioned in Section 3.4, translation was chosen as the motion model. The motion estimation in (9) was performed by fast, suboptimal (as opposed to exhaustive) search [START_REF] Zhu | A new diamond search algorithm for fast block-matching motion estimation[END_REF] within a search window of -12/+12 pixels in both directions and a quarter of a pixel precision. This procedure was used whether the motion was estimated globally in Ω or locally in each Ω i .

In the following, "segmentation" refers to object detection with an initialization far from the solution (typically a circle) while "tracking" refers to object detection with an initialization obtained by translating by v global the object contour as detected in the previous frame, where v global is the motion of Ω computed by the suboptimal procedure described above.

Temporal only

Spatial only Spatio-temporal

Comparing spatial, temporal, and spatio-temporal energies

In this section, motion is estimated globally on Ω (see Section 3.4).

Synthetic sequences

Several synthetic sequences were designed by combining different textures and homogeneous areas with a given motion scenario: an object is translating horizontally by -3 pixels over a background translating horizontally by 1 pixel. Segmentation was performed with the spatial energy, the temporal energy, and the spatiotemporal energy (see Fig. 2). These results suggest that the temporal energy is adapted whenever there is texture. On the contrary, the spatial energy seems more reliable in homogeneous areas. Finally, the combination of temporal and spatial information appears appropriate for segmenting sequences that contain homogeneous areas, textured areas, or both.

Initialization Temporal only

Spatial only Spatio-temporal

Figure 3: Segmentation of frame 237 of sequence 'Flowers and garden' accounting for motion, color, or both.

Standard test sequences

The same comparison as in Section 5.2.1 was performed with standard test sequences 'Flowers and garden' and 'Soccer'.

In sequence 'Flowers and garden', the sky bordering the tree is rather homogeneous (see Fig. 3). Therefore, oversegmentation occurs with the temporal energy, as noted in Appendix A. With the spatial energy, the segmentation process also fails because part of the houses in the background have colors similar to the tree. Finally, the spatio-temporal segmentation mostly excludes the sky since it has a different color (spatial information) and also excludes the houses since they have a different motion (temporal information).

In sequence 'Soccer', the soccer player has a complex, articulated motion (see Fig. 4). The temporal energy only captures the rigid part of the body while the spatial energy does not capture the head as it has colors similar to the background. The spatio-temporal energy provides a good tradeoff, although it sometimes miss a foot of the player (see Fig. 9) for which both the temporal information and the spatial information (the color of the shoe is similar to background colors in the Y U -color space) are unreliable. This satisfying result can be explained by the fact that the spatial energy helps the temporal term when the motion model mismatches the actual motion, and the temporal energy helps the spatial term when the color is not discriminating.

Initialization

Temporal only

Spatial only Spatio-temporal

Figure 4: Segmentation of frame 162 of sequence 'Soccer' accounting for motion, color, or both.

Parametric vs. nonparametric

In this section, motion is estimated globally on Ω (see Section 3.4).

One can wonder the practical benefits of relying on nonparametric estimations of the residual distribution and the color distribution as opposed to using classical error terms corresponding to parametric assumptions. For a fair comparison, the parametric assumptions for the residual and the color distributions have to be chosen appropriately. The residual is corrupted by outliers mainly due to noise, illumination variations, motion model mismatch, and occlusion. The Sum of Absolute Differences (SAD) [START_REF] Wu | A gradient-based method for general motion estimation and segmentation[END_REF] was chosen since it is robust to outliers. Note that it follows from a Laplacian assumption (see Appendix E.1).

It is clear that there is no ideal parametric assumption concerning the spatial term. Nevertheless, noting that the spatial entropy in ( 7) can be interpreted as a piecewise color homogeneity criterion, it seems reasonable to make the assumption of a Gaussian distribution 9 (see Appendix E.2).

The continuous form of criteria ( 80) and ( 82) can be linearly combined to define a parametric, space-time segmentation energy

E p (Γ) = Ω (I n (x) -µ I (Γ)) 2 dx +α Ω |I n (x) -I n+1 (x + v(Γ))| dx (28)
9 To be coherent with the piecewiseness property of entropy, a mixture of Gaussians would be more appropriate. However, the purpose of this section is to compare the proposed approach with classical error terms such as the Sum of Squared Differences (SSD).

Spatial only Temporal only

Spatio-temporal with α = 1 Spatio-temporal with α ≃ 9 29) and α is a positive constant. The nonparametric energy [START_REF] Boltz | Entropy-based space-time segmentation in video sequences[END_REF] does not weight the spatial term relatively to the temporal term. Therefore, to be coherent, α should be equal to one. However, the results on sequence 'Flowers and garden' suggest to choose α greater than one (see Fig. 5). In each experiment, the optimal value was determined empirically. Moreover, to give an idea of the behavior of each term of the parametric energy [START_REF] Leventon | Statistical shape influence in geodesic active contour[END_REF], segmentation was also performed using each term separately (same procedure as in Section 5.2). The parametric approach was also tested on the other, more challenging sequence 'Football'. Even when assigning a higher weight to the temporal term, the segmentation is not satisfying (see Figs. 6, 7, and8).

In light of these results, three intuitive conclusions can be made. (i) As expected, when the parametric assumptions are roughly in accordance with the actual distributions (sequence 'Flowers and garden'), the parametric approach can perform well. (ii) The Laplacian assumption for the residual distribution is more reliable than the Gaussian assumption for the color distribution. Indeed, with sequence 'Flowers and garden', the correct segmentation is obtained only when the temporal term is weighted significantly more Temporal only Spatial only

Spatio-temporal

Figure 8: Segmentation of frame 72 of sequence 'Football' with the nonparametric approach using the same initialization as in Fig. 6.

Initialization Temporal only

Spatial only Spatio-temporal than the spatial term. (iii) Again, as expected, when the parametric assumptions clearly mismatch the actual distributions for the motion being complex or the object and background being composed of several colors (sequence 'Football'), the parametric approach fails, as opposed to the proposed nonparametric approach (see Figs. 3 and4).

Tracking and piecewise motion estimation

In this section, an object of interest is tracked in two standard test sequences using the proposed method.

In both sequences, the object of interest is composed of several colors and has a complex, articulated motion. Therefore, they are appropriate for comparing the global (on Ω) motion approach and the local (on Ω i ) motion approach (see Section 3.4). Sequence 'Soccer' (already seen in Section 5.2.2) is less complex than sequence 'Football' (already seen in Section 5.3) since the latter suffers from motion blur. For the piecewise motion estimation, each frame was divided into 16 × 16 blocks B i of size 22 × 18 pixels. As a reminder, domain Ω i is defined as Ω ∩ B i . The comparison between the two approaches is presented in Figs. 9 and 10. Although the local approach clearly improves the segmentation, it is not perfect in sequence 'Football'. This can be explained by the combined effects of motion blur and a domain Ω i too small (which may happen for blocks B i that intersect Γ), resulting in a less reliable local motion estimate.

Conclusion

The addressed problem was the segmentation of a video sequence. A spatio-temporal approach was chosen in order to make use of both spatial and temporal coherence. As opposed to the classical approach consisting in dealing with time by involving the MCE directly, the proposed method is based on the use of the distribution of the MCE. This allowed to combine temporal and spatial information coherently using joint distributions. The distributions were estimated nonparametrically to fit the data. Entropy was chosen as the energy to minimize, in particular because, in practice, it is robust to outliers. In order to make the motion model complex enough to describe articulated objects, it was proposed to keep it simple (namely, translation) while estimating its parameters locally. The proposed method was qualitatively compared with a classical, parametric approach followed by some existing methods. Thorough comparison with specific methods is out of scope of this paper, though. Nevertheless, on sequence 'Flowers and garden', our results (see Fig. 3) are comparable to those of recent segmentation methods [START_REF] Cremers | Variational space-time motion segmentation[END_REF][START_REF] Schoenemann | Near real-time motion segmentation using graph cuts[END_REF], Fig. 4 in both articles.

A Disambiguation using spatial information

Energy ( 9) is well suited for segmenting objects over a textured background. However, it might cause segmentation to include homogeneous or quasi-homogeneous areas of the background. Indeed, this type of areas has a low residual even if compensated with the motion estimated for the object, at least as long as the motion-compensated object domain remains in the homogeneous area. Therefore, the energy might increase only negligibly when expanding in such areas. Since the notions of object and background are arbitrary and can be swapped for one another, one can note that an equivalent undersegmentation phenomenon can occur if the object contains homogeneous areas near its boundary.

On the other hand, the entropy of the object color increases if the object domain includes some background since it adds new colors to the object 10 and, therefore, increases the dispersion of its color distribution. Consequently, the joint entropy of the residual and the color also increases.

B "Independence" between residual and color

Let us consider the following sequence model

I n+1 (x) = I n (T (x)) + n(x) (30)
where T is a transformation and n is a Gaussian white noise. The residual is equal to

e n (v(x), x) = I n (x) -I n+1 (v(x)) . (31)
If the transformation T exists and the motion is perfectly estimated, then v is equal to T -1 and e n (v(x), x) = -n(T -1 (x)), which is independent of I n . However, model ( 30) is an approximation: in general, there is no such transformation T , frame I n+1 being a projection on a two-dimensional plane of a threedimensional scene. Often, some parts of objects in I n become invisible in I n+1 while others become visible. Therefore, frame I n+1 cannot be deduced entirely from I n . In the unpredictable areas, the residual is by definition independent of I n . Overall, whether a transformation T exists or not, if the motion v(Γ) is fairly well estimated, then the assumption of independence should be acceptable. 10 If the background has the same color as the object near the boundary, there is no objective information to find the object boundary.

C Energy derivative C.1 Temporal energy

The temporal energy is equal to

E t (Γ) = - 1 |Ω| Ω log f t (e n (v(Γ), x)) dx (32)
where

                   f t (r) = 1 |Ω| Ω K σ (e n (v(Γ), x) -r) dx e n (v(Γ), x) = min abs (I n (x) -I n+1 (x + v(Γ)), I n (x) -I n-1 (x -v(Γ))) v(Γ) = arg min w - 1 |Ω| Ω log f t (e n (w, x)) dx . ( 33
) Note that, for simplicity, residual e n has been defined for a translation motion model. However, the following development is valid for any motion model.

The definition of the shape derivative of ( 32) is based on a domain transformation T whose amplitude continuously depends on a parameter τ such that T (Ω, τ = 0) is equal to Ω and T (Ω, τ ) is equal to Ω(τ ) [START_REF] Delfour | Shapes and geometries: Analysis, differential calculus and optimization[END_REF][START_REF] Hintermuller | A second order shape optimization approach for image segmentation[END_REF][START_REF] Jehan-Besson | DREAM 2 S: deformable regions driven by an eulerian accurate minimization method for image and video segmentation[END_REF][START_REF] Aubert | Image segmentation using active contours: Calculus of variations or shape gradients?[END_REF]. Functions of Ω, or Γ, can then be rewritten as functions of τ . In this context, the shape derivative of

E(Γ) = Ω G(Γ, x) dx (34)
is equal to

dE(Γ, F ) = dE dτ (τ = 0) (35)
=

Ω ∂G ∂τ (τ = 0, x) dx - Γ G(Γ, s) N (s) • F (s) ds ( 36
)
where F is a vector field defined on Γ and linked to T , s is the arclength parameter of Γ, G(Γ, s) is a short notation for G(Γ, Γ(s)), and N is the inward unit normal of Γ.

Let us define E t as follows

E t (Γ, w) = - 1 |Ω| Ω log f t (e n (w, x)) dx . (37)
Hence,

E t (Γ) = E t (Γ, v(Γ)) (38)
and v(Γ) = arg min

w E t (Γ, w) . (39)
Then, the shape derivative of ( 32) is equal to

dE t (Γ, F ) = dE t dτ (τ, v(τ ))| τ =0 (40)
= ∂E t ∂τ (τ, v(τ ))| τ =0 + ∂E t ∂w (τ, v(τ ))| τ =0 dv dτ (τ = 0) . ( 41
)
Recalling that τ = 0 corresponds to Γ and according to [START_REF] Scott | Multivariate Density Estimation: Theory, Practice, and Visualization[END_REF], the second term in ( 41) is equal to zero. Therefore, expression ( 41) is equal to

dE t (Γ, F ) = ∂E t ∂τ (τ, v(τ ))| τ =0 . (42)
Note that the derivative of E t is taken with respect to the first variable, v(τ ) being considered as a constant (including in all the following calculations). The classical rule for differentiating a product leads to (see Section C.3 for the shape derivative of 1 |Ω| )

dE t (Γ, F ) = E t (Γ) |Ω| Γ N (s) • F (s) ds - 1 |Ω| d dτ Ω(τ ) log f t (e n (v(Γ), x)) dx τ =0 (43) = 1 |Ω| Γ E t (Γ) N (s) • F (s) ds -A (44)
where f t is also seen as a function of τ

f t (e n (v(Γ), x)) = 1 |Ω(τ )| Ω(τ ) K σ (e n (v(Γ), y) -e n (v(Γ), x)) dy . (45)
Remember that v(Γ) is considered as a constant and not as a function of τ as a result of the decoupling [START_REF] Schoenemann | Near real-time motion segmentation using graph cuts[END_REF]. Therefore, for clarity, e n (v(Γ), •) will be denoted by e n (•). Term A can be computed by applying the general rule [START_REF] Rubner | The earth mover's distance as a metric for image retrieval[END_REF] successively

A = Ω ∂ log f t ∂τ (τ = 0, x) dx - Γ log f t (e n (s)) N (s) • F (s) ds (46) = Ω B dx - Γ log f t (e n (s)) N (s) • F (s) ds . (47)
Then,

B = ∂ft ∂τ (τ = 0, x) f t (e n (x)) (48) = 1 f t (e n (x)) f t (e n (x)) |Ω| Γ N (s) • F (s) ds + 1 |Ω| d dτ Ω(τ ) K σ (e n (y) -e n (x)) dy τ =0 (49) = 1 |Ω| Γ N (s) • F (s) ds + C f t (e n (x)) . (50)
Finally,

C = Ω dK σ (e n (y) -e n (v(x)) dτ (τ = 0) dy - Γ K σ (e n (s) -e n (v(x)) N (s) • F (s) ds (51) = - Γ K σ (e n (s) -e n (x)) N (s) • F (s) ds (52)
since K σ (. . .) does not depend on τ . Gathering all the intermediate results together, the shape derivative of ( 32) is equal to

dE t (Γ, F ) = 1 |Ω| Γ E t (Γ) -1 + log f t (e n (s)) + 1 |Ω| Ω K σ (e n (s) -e n (x)) f t (e n (x)) dx N (s) • F (s) ds . (53)

C.2 Spatial energy

The spatial energy is equal to

E s (Γ) = - 1 |Ω| Ω log f s (I n (x)) dx (54)
where

f s (r) = 1 |Ω| Ω K σ (I n (x) -r) dx . (55)
Following the same approach as in Section C.1, it can be shown that the shape derivative of (54) is equal to

dE s (Γ, F ) = 1 |Ω| Γ E s (Γ) -1 + log f s (I n (s)) + 1 |Ω| Ω K σ (I n (s) -I n (x)) f s (I n (x)) dx N (s) • F (s) ds . (56)
C.3 Shape derivative of |Ω| and 1

|Ω|

The shape derivative of |Ω| is equal to

d(|Ω|)(Γ, F ) = d Ω dx (Γ, F ) (57) = d dτ Ω(τ ) dx τ =0 (58) = Ω ∂1 ∂τ (τ = 0, x) dx - Γ N (s) • F (s) ds (59) = - Γ N (s) • F (s) ds . (60)
The shape derivative of 1 |Ω| is equal to

d(1/|Ω|)(Γ, F ) = d dτ 1 |Ω(τ )| τ =0 (61) = - 1 |Ω| 2 d dτ Ω(τ ) dx τ =0 (62) = 1 |Ω| 2 Γ N (s) • F (s) ds . (63)

D Piecewise motion decomposition

The following development should give some intuitions to study the validity of the piecewise motion decomposition. As will be clear from the concluding remarks, it does not provide a full and rigorous analysis.

The frame I n is divided into blocks B i of identical size. Let Ω i be the intersection of Ω with B i and let Γ i be the boundary ∂Ω i of Ω i (see Fig. 1). For clarity, v(Γ i ) will be denoted by v i . Energy (32) is replaced with

E local t (Γ) = - 1 |Ω| Ω log f t (e n (v 1 , . . . , v k , x)) dx (64)
where

                           f t (r) = 1 |Ω| Ω K σ (e n (v 1 , . . . , v k , x) -r) dx e n (v 1 , . . . , v k , x) = min abs (I n (x) -I n+1 (x + v i ), I n (x) -I n-1 (x -v i )) if x ∈ Ω i v i = arg min w - 1 |Ω| Ωi log f t (e n (v 1 , . . . , v i-1 , w, v i+1 , . . . , v k , x)) dx .
(65) Note that the motions v j , j = i, in the energy minimized to solve for v i are irrelevant constants since they are not used in the computation of the residual e n on Ω i .

Let us define E i t as follows

E i t (Γ, w 1 , . . . , w k ) = - 1 |Ω| Ωi log f t (e n (w 1 , . . . , w k , x)) dx . (66)
According to the remark on the residual above, it can be concluded that E i t is independent of w j , j = i. Energy (64) is equal to,

E local t (Γ) = i E i t (Γ, v 1 , . . . , v k )) (67)
and

v i = arg min w E i t (Γ, v 1 , . . . , v i-1 , w, v i+1 , . . . , v k ) . (68)
Then, the shape derivative of (64) is equal to

dE local t (Γ, F ) = i dE i t dτ (τ, v 1 (τ ), . . . , v k (τ ))| τ =0 (69) = i ∂E i t ∂τ (τ, v 1 (τ ), . . . , v k (τ ))| τ =0 + i j ∂E i t ∂w j (τ, v 1 (τ ), . . . , v k (τ ))| τ =0 A i j × dv j dτ (τ = 0) . (70)
Recalling that τ = 0 corresponds to Γ (and, therefore, v i (τ = 0) = v i ), A i j is equal to zero if j is equal to i because of (68). Moreover, according to the independence of E i t with respect to w j , j = i, A i j is also equal to zero if j is not equal to i. Therefore, expression (70) is equal to

dE local t (Γ, F ) = i ∂E i t ∂τ (τ, v 1 (τ ), . . . , v k (τ ))| τ =0 .
(71) By definition, the shape derivative is based on a domain transformation T operating on Ω (see Appendix C.1). Energy E i t is an integral over Ω i . Its shape derivative is naturally related with the restriction of T to Ω i . However, f t is still an integral over Ω. Keeping that in mind, the approach of Section C.1 can be followed to determine the shape derivative of (64)

dE local t (Γ, F ) = E local t (Γ) |Ω| Γ N (s) • F (s) ds - 1 |Ω| × i d dτ Ωi(τ ) log f t (e n (v(Γ), x)) dx τ =0 (72) = 1 |Ω| Γ E local t (Γ) N (s) • F (s) ds - i A i . (73)
For clarity, e n (v 1 , . . . , v k , •) will be denoted by e n (•). Term A i is equal to

A i = Ωi ∂ log
Let B i and B j be 2 adjacent blocks with boundaries Γ i and Γ j , respectively. On their common boundary, log f t (e n ) and F are uniquely defined. However, N i and N j have opposite directions, each pointing inward relatively to its (oriented) boundary. Therefore, the sum of the integrals over Γ i and Γ j in S on this common boundary is equal to zero. When considering all the blocks, the only portions of integral that remain of S are the ones which are not in common with any other block boundary. These portions sum to Γ. The normals N i on these portions are equal to N . In conclusion, shape derivative (77) is identical to (53): it seems that this hierarchical motion decomposition approach can be safely used with minimal changes to the implementation (only the residual computation changes). However, one condition has not been mentioned so far. The shape derivative framework is valid for smooth contours. In particular, the presence of the contour normal in the expressions implicitly requires that the contour be at least continuously differentiable. Unfortunately, the contours Ω i of the proposed partition of Ω are not smooth, independently of the smoothness of Ω. Actually, any paving of Ω using patches contains multiple junctions. As a consequence, the previous development is theoretically invalid. Nevertheless, the set of singularities is finite and it might be possible to rigorously confirm the result by studying the limit of a related, smooth setting similar to some works on classification [START_REF] Samson | A level set model for image classification[END_REF]. Moreover, in practice, the (wrongly) obtained result can be easily implemented since it does not involve these singularities.

E Parametric assumptions E.1 Residual

If the residual e n is a spatially uncorrelated random field with a Laplacian distribution with mean µ e and scale σ, the probability of having a given field, conditional to a motion v, is equal to

p(e n |v) = 1 (2σ) |Ω| x∈Ω exp - |e n (v, x) -µ e | σ . (78)
The maximum log-likelihood estimation of v is given by arg min

v x∈Ω |e n (v, x) -µ e | . (79)
In practice, choosing µ e different from zero can only be motivated by a global change of illumination occurring between frames I n and I n+1 . Making the assumption that the global illumination remains constant, µ e will be set to zero. Therefore, estimation (79) is equivalent to arg min

v x∈Ω |I n (x) -I n+1 (x + v)| (80)
which is the SAD criterion.

E.2 Color

If the color I n is a spatially uncorrelated random field with a Gaussian distribution with mean µ I and standard deviation σ, the probability of having a given field, conditional to a motion v, is equal to

p(I n |v) = 1 √ 2π σ x∈Ω exp - (I n (x) -µ I ) 2 2σ 2 . (81)
The maximum likelihood estimation of v is then equivalent to minimizing the Sum of Squared Differences (SSD) arg min v x∈Ω

(I n (x) -µ I ) 2 . ( 82
)
In practice, µ I can be approximated by the mean of I n in Ω [START_REF] Jehan-Besson | DREAM 2 S: deformable regions driven by an eulerian accurate minimization method for image and video segmentation[END_REF].

Figure 1 :

 1 Figure 1: Solid line: contour Γ = ∂Ω; Dashed blocks: B i ; Gray-filled block: an example of a domain Ω i with boundary Γ i .

Figure 2 :

 2 Figure 2: Segmentation of synthetic sequences accounting for motion, color, or both. First row: homogeneous object over homogeneous background; second row: homogeneous object over textured background; third row: textured object over homogeneous background; last row: textured object over textured background.

Figure 5 :

 5 Figure 5: Segmentation of frame 237 of sequence 'Flowers and garden' assuming parametric distributions and using the same initialization as in Fig. 3. (Lower left) The spatio-temporal energy relies equally on space and time and (Lower right) the spatiotemporal energy favors the temporal term.

Figure 6 :

 6 Figure 6: Segmentation of frame 72 of sequence 'Football' assuming parametric distributions. The spatio-temporal energy relies equally on space and time (α = 1).

Figure 7 :

 7 Figure 7: Segmentation of frame 72 of sequence 'Football' assuming parametric distributions. The spatio-temporal energy favors the temporal term (α ≃ 9).

Figure 9 :

 9 Figure 9: Tracking on sequence 'Soccer': comparison between the global motion approach (first column) and the local motion approach (second column) on frames 162, 172, 182, 192, and 202. The segmentation is more accurate with the local motion approach (the main differences are highlighted by circles).

Figure 10 :

 10 Figure 10: Tracking on sequence 'Football': comparison between global motion approach (first column) and local motion approach (second column) on frames 73, 77, 81, 85, and 89. The segmentation is more accurate with the local motion approach (the main differences are highlighted by circles).

  i is the inward unit normal of Γ i . Term B is identical to the corresponding term (50) in Appendix C.1, i.e.,

	B =	1 |Ω| Γ	1 -	K σ (e n (s) -e n (x)) f t (e n (x))	N (s) • F (s) ds . (76)
	Gathering all the intermediate results together, the
	shape derivative of (64) is equal to
					
	dE t (Γ, F ) =	1 |Ω|	     Γ	E local t	(Γ) -1
			+	1 |Ω| Ω	K S	     	.
						∂τ	f t	(τ = 0, x) dx
						-

Γi

log f t (e n (s)) N i (s) • F (s) ds (74) = Ωi B dx -Γi log f t (e n (s)) N i (s) • F (s) ds

(75)

where N σ (e n (s) -e n (x))

f t (e n (x)) dx ×N (s) • F (s) ds i Γi log f t (e n (s)) N i (s) • F (s) ds

Note that, here, the usage of the terms "temporal" and "spatio-temporal" should be understood as "motion-based" and "based on motion and color", respectively. "Spatio-temporal" more typically refers to a process performed in the xyt-space where x and y are video frame coordinates and t is the time coordinate. As far as active contours are concerned, such a process would manipulate a tube oriented along the time dimension as opposed to a planar curve here.

Approach (3) is referred to as parametric since the underlying distributions are defined by a small number of parameters.

This is interesting since the maximum likelihood estimator is optimal when the distribution of data is parametric.

In fact, would be equal if the assumption of independence between en and In had not been made (see Section 3.2).

The frame size cif corresponds to 352 × 288 pixels.

Adapting the kernel bandwidth to the data is known as a plug-in procedure[START_REF] Silverman | Density Estimation for Statistics and Data Analysis[END_REF].


Oralie Cattan

Christophe Servan

Sophie Rosset

On the cross-lingual transferability of multilingual prototypical models across NLU tasks

Supervised deep learning-based approaches have been applied to task-oriented dialog and have proven to be effective for limited domain and language applications when a sufficient number of training examples are available. In practice, these approaches suffer from the drawbacks of domain-driven design and under-resourced languages. Domain and language models are supposed to grow and change as the problem space evolves. On one hand, research on transfer learning has demonstrated the cross-lingual ability of multilingual Transformers-based models to learn semantically rich representations. On the other, in addition to the above approaches, meta-learning have enabled the development of task and language learning algorithms capable of far generalization. Through this context, this article proposes to investigate the cross-lingual transferability of using synergistically few-shot learning with prototypical neural networks and multilingual Transformers-based models. Experiments in natural language understanding tasks on MultiATIS++ corpus shows that our approach substantially improves the observed transfer learning performances between the low and the high resource languages. More generally our approach confirms that the meaningful latent space learned in a given language can be can be generalized to unseen and underresourced ones using meta-learning.

Introduction

Traditionally, Natural Language Understanding (NLU) is an intermediate module between the user interface and the dialogue management module in a dialogue system. It aims to extract semantic information from a user's query or utterance to fill slots in a domain specific semantic frame. Domain classification, intent detection and slot filling are three core components belonging to the NLU. They are in charge of determining the domain or service of a users query, its underlying goal or intent and asso-ciating utterance segments with conceptual labels, called slots, similar to named entity recognition.

NLU is usually defined as a supervised learning problem, involving conventional machine learning models on massive amount of annotated training data, which are language dependent. This prerequisite has prevented its widespread adoption for poorly endowed languages and for small technology companies that do not benefit from millions of users to gather data. Besides the requirement of a large amount of annotated data being available, domains, intents and slots are language dependent. Consequently, in practice, the resulting systems are hardly adaptable to expand to new languages.

As a solution to this problem, cross-lingual transfer approaches were developed to leverage the knowledge from well-resourced languages, with task specific data available to under-resourced languages with little or no data. Recent efforts focused on training Transformer models multilingually such as the multilingual version of BERT [START_REF] Devlin | BERT: Pre-training of deep bidirectional transformers for language understanding[END_REF]. While earlier work demonstrated the effectiveness of multilingual models to learn representations which are transferable across languages, they show limitations when applied to low-resource languages [START_REF] Pires | How multilingual is multilingual BERT?[END_REF][START_REF] Conneau | Unsupervised cross-lingual representation learning at scale[END_REF]. From another perspective lowshot learning such as few-shot and zero-shot, aims to transfer knowledge learned from one language to another when the training data is limited or is missing some task labels.

As a core contribution, we explore the potential for cross-lingual transferability of multilingual Transformer-based model [START_REF] Vaswani | Attention is all you need[END_REF] (mBERT) combined with a few-shot learning algorithm based on prototypical representations. We also introduce a zero-shot scenario, where models are trained on multiple languages and evaluated on another. Our proposed approach relies on appending a mBERT encoder module to the prototypical neural network, which is a proven few-shot model, originally designed for image classification. Our experimental results show that the generated model trained with a limited number of annotated training examples outperforms the transfer learning based approach on MultiATIS++ dataset [START_REF] Xu | End-to-end slot alignment and recognition for crosslingual NLU[END_REF][START_REF] Upadhyay | almost) zero-shot cross-lingual spoken language understanding[END_REF] and can be applied to unseen languages directly with decent performance.

Related work

The availability of large datasets has enabled deep learning methods to achieve great success in a variety of fields. However, most of these successes are based on supervised learning approaches, which require lots of labeled data to train. Most datasets are only available in English. Only a few other languages are supported, and most of them are considered as under-resourced languages.

Recently, meta-learning approaches have enabled the development of task-agnostic learning algorithms capable of far generalizations (crossdomain or cross-lingual) in the context of having a low-data regime. Because literature on low-shot learning is vast and diverse, only the most relevant approaches to this work are presented and we refer the reader to [START_REF] Vanschoren | Meta-Learning[END_REF] and [START_REF] Wang | A survey of zero-shot learning: Settings, methods, and applications[END_REF] for a surveys of earlier work.

Low-shot learning

Humans manifest a capacity of learning new concepts from few stimuli quickly and efficiently by utilizing prior knowledge and experience. Inspired by this ability, there has been a resurgence of interest in designing specialized models to perform low-shot learning. An example of this form of learning is metric-based approaches founded on the simple idea of learning a discriminative metric space in which similar samples are mapped close to each other and dissimilar ones distant. Siamese [START_REF] Gregory | Siamese neural networks for one-shot image recognition[END_REF], Matching [START_REF] Vinyals | Matching networks for one shot learning[END_REF] or Prototypical [START_REF] Snell | Prototypical networks for few-shot learning[END_REF] networks belong to this category.

Supervised generalization

In recent years, several approaches have been introduced and refined to overcome the issue of datalimited regime. As an example, the Prototypical Neural Networks (PNNs), developed by [START_REF] Snell | Prototypical networks for few-shot learning[END_REF] originally for image classification, were used to extract representative characteristics of the data by mapping data points into an embedding space where each sample will cluster around their respective prototype representation. [START_REF] Fort | Gaussian prototypical networks for few-shot learning on omniglot[END_REF] proposed to extend their work by adding a confidence region around prototypes with the help of Gaussian covariance models.With the aim of improving the generalization capacity of metric-based methods, [START_REF] Wang | Large margin few-shot learning[END_REF] proposed to enforce a large margin between the class prototypes by modifying the standard softmax loss function.

Semi-supervised generalization

Other approaches, closely related to the aforementioned ones, proposed to take advantage of labeled and unlabeled data. Among them, [START_REF] Boney | Semisupervised few-shot learning with prototypical networks[END_REF] extended PNNs to address semi-supervised image classification problems. They applied a hard clustering to assign the class for the unlabeled examples within the latent space learned by the PNNs. A close method was developed by [START_REF] Ren | Metalearning for semi-supervised few-shot classification[END_REF] to refine the prototype generation process with clustering. The authors introduced distractor classes with the aim of handling unlabeled samples not belonging to any of the known classes.

Most of these approaches have mainly been explored in the field of computer vision, and a few of them were applied to NLP fields, such like Natural Language Understanding (NLU).

NLU using low-shot learning

A number of different deep learning approaches have been applied to the problem of language understanding in recent years. For a thorough overview of deep learning methods in conversational language understanding, we refer the readers to [START_REF] Gao | Neural approaches to conversational ai[END_REF]. In the context of relying on limited training resources, few-shot learning has been used for NLU tasks. [START_REF] Yazdani | A model of zero-shot learning of spoken language understanding[END_REF] proposes a method to leverage unlabeled data in order to find the separating hyperplanes that divide the utterances with the same label from those with different labels. Sun et al. ( 2019) extended PNNs for intent classification using hierarchical attention mechanisms when generating the prototype representations.

Slot filling using few-shot models has also been explored. [START_REF] Ferreira | Online adaptative zero-shot learning spoken language understanding using wordembedding[END_REF] presented a zeroshot approach based on a knowledge base and on word representations learned from unlabeled data. [START_REF] Fritzler | Few-shot classification in named entity recognition task[END_REF] applied PNNs to few-shot named entity recognition by training a separate model for each entity type and [START_REF] Hou | Few-shot sequence labeling with label dependency transfer[END_REF] proposed a conditional random forest-based approach enhanced with transfer mechanisms that implicitly incorporate label dependencies and sim-ilarities. More recently, [START_REF] Dou | Investigating meta-learning algorithms for low-resource natural language understanding tasks[END_REF], Bansal et al. (2020a) and Bansal et al. (2020b) applied various meta-learned models to few-shot NLU across domains and tasks.

Finally, besides the approaches of [START_REF] Gu | Meta-learning for lowresource neural machine translation[END_REF] and [START_REF] Zhang | Improving massively multilingual neural machine translation and zero-shot translation[END_REF] that focus on handling new and low-resource languages for machine translation, to the best of our knowledge, there are no approaches that combine cross-lingual transfer and meta-learning methods for NLU tasks.

Approach

In this section, we present the design of a Prototypical Neural Network and its episodic training procedure before introducing our approach.

Prototypical Neural Networks

Prototypical Neural Networks [START_REF] Snell | Prototypical networks for few-shot learning[END_REF] or PNNs are based on the computation of distance measures between seen-class prototypes to unseen ones. More specifically, a D-dimensional embedding is generated for each example x ∈R D using a neural network based function f (•) parameterized by Θ. This function enhances the encoding process with better separability properties through a non-linear mapping f Θ :R D →R M . The Mdimensional prototype of each class is formed as the centroid c i of their embedded support points as seen in Equation (1):

c i = 1 |S i | (x j ,y j )∈S i f Θ (x j ), (1)
where S i represents the set of examples labeled with class i and y j the corresponding label of x j . Equation (2) shows how, given a query (that is, a new and an unlabeled sample) q i , the probability distribution over the prototypes is computed from d(•, •), an arbitrary similarity measures function such as the squared euclidean distance or cosine similarity.

p Θ (y i |q i ) = exp(-d(f Θ (q i ), c i )) i exp(-d(f Θ (q i ), c i )) (2)
Finally, the class with the highest probability is chosen by a softmax over the distances and at optimization time, the negative log-probability J(Θ) = -log p Θ (y i |q i ) of the true class of each query point is minimized by stochastic gradient descent during an episodic learning process described in the next subsection.

Episodic learning

With the aim of generalizing unseen classes from zero to few training examples per class, PNNs is trained from a collection of N -way, k-shot classification tasks through an episodic training procedure [START_REF] Vinyals | Matching networks for one shot learning[END_REF]. Specifically, each episode is one mini-batch consisting of k examples from each of the N classes (both randomly sampled), used to form a labeled (support S) and an unlabeled set of examples (query Q). The parameter k often takes a very small value, meaning we have zero-tok labeled samples. During training, the model is fed with S to construct the class prototypes using Equation (1). Its parameters are learned in order to minimize the prototypical loss of its predictions for the examples in the given Q according to Equation (3) of Section 3.1. The evaluation is done by averaging the classification performances on query sets of many testing episodes.

Transformer-based PNNs

Studies have demonstrated that contextualized representations produced by language models such as ELMo [START_REF] Peters | Deep contextualized word representations[END_REF] or BERT [START_REF] Devlin | BERT: Pre-training of deep bidirectional transformers for language understanding[END_REF] gave neural networks a better training initializations. Rather than training the initialized encoder of PNNs with feature extractors such as convolution or recurrent networks we propose to induce robustness of the pre-trained multilingual BERT (mBERT) to test the distinctiveness of the representation of each class accross languages. The embedding layer is initialized with the pre-trained mBERT embeddings and fine-tuned together with a dense linear layer that defines the embedding space where the prototype-based classifier operates. This latent space is used to learn prototypes of each class by estimating their mean and the chosen class is derived from the output layer of the network based on a softmax over distance to the class prototypes. The motivation behind fine-tuning the encoder with prototypical loss is to induce better generalization properties at test-time to new class labels not seen during training given only a few examples.

The cross-lingual way

As introduced earlier, even though recent works demonstrate strong cross-lingual transfer capability of multilingual pretrained BERT, they exhibit limitations when applied to low-resource languages [START_REF] Pires | How multilingual is multilingual BERT?[END_REF][START_REF] Conneau | Unsupervised cross-lingual representation learning at scale[END_REF] scenario, we construct mutiple episodic batches E.

From the available data, we draw the task sets by sampling a subset of labels to form a support set from data in the high-resources languages and a query set from data in the low-resource languages to be evaluated. NLU data consists of utterances composed of sentence-level intent labels and sequences of slot labels annotated in BIO format [START_REF] Ramshaw | Text chunking using transformation-based learning[END_REF] to define the boundary of slots. The N -way k-shot NLU task is then defined as follows: given an input query utterance in a new language q i and a k-shot support set S as references, find the most appropriate intent label or slot label sequence y: argmax E θ (q i ,y i )∈Q log p θ (y i |q i , S).

(3)

Experiments

Our NLU experiments in cross-lingual and fewshot learning for under-resources languages are conducted on MultiATIS++ [START_REF] Xu | End-to-end slot alignment and recognition for crosslingual NLU[END_REF][START_REF] Upadhyay | almost) zero-shot cross-lingual spoken language understanding[END_REF] corpus, whose description follows.

The MultiATIS++ corpus

MultiATIS++ [START_REF] Upadhyay | almost) zero-shot cross-lingual spoken language understanding[END_REF][START_REF] Xu | End-to-end slot alignment and recognition for crosslingual NLU[END_REF] is the multilingual extension of the ATIS corpus [START_REF] Charles T Hemphill | The atis spoken language systems pilot corpus[END_REF]

Models

We use the fine-tuning procedure [START_REF] Devlin | BERT: Pre-training of deep bidirectional transformers for language understanding[END_REF] of the original mBERT model as our baseline. In sequence-level and token-level classification tasks, it takes the final hidden states (the last layer output of the multi-head Transformer) of the first [CLS] sequence token or each individual token representation as input of the prediction layer to compute classification scores. Since we plan to use transfer learning in the context of PNNs, we finetune the pre-trained mBERT model together with a dense linear layer that defines the embedding space (Section 3.3).

Training configurations

We perform three sets of experiments: target only, multilingual and multilingual zero-shot.

• target only: this configuration consists of using only the target language data.

We also considered two cross-lingual classification tasks with a varying quantity of data between source and target languages to investigate the behaviour of different types of knowledge transfer.

• multilingual: where the training strategy aims to train a network on the concatenation of all of the nine languages and testing the model for each target language. datasets from all languages except the one we want to test. This works only for the baseline approach (mBERT), but with our PNNs approach (mBERT+PNN), we performs few-shot learning. This means we use only a few training data in the considered language (target only and multilingual configurations).

For instance, when we evaluate our approach in the English task, we consider only a fraction of the English training dataset to train our mBERT+PNN model in the target only. In the multilingual configuration, our few-shot approach (mBERT+PNN) is trained using only a fraction of all the examples provided for each language.

Training details

For all the baseline models built, we use the publicly available mBERT models pre-trained on over a hundred different languages [START_REF] Devlin | BERT: Pre-training of deep bidirectional transformers for language understanding[END_REF]. We trained it using 20 epochs like [START_REF] Xu | End-to-end slot alignment and recognition for crosslingual NLU[END_REF].

PNNs training was done using a number of 1000 episodes using Euclidean distance as suggested by the original authors [START_REF] Snell | Prototypical networks for few-shot learning[END_REF]. We consider a configuration parameter and tried a 5way k-shot intent classification with k ∈ [1, 10] (5w1s and 5w10s) and 5-way 10-shots slot filling.

For all approaches we use AdamW optimizer [START_REF] Loshchilov | Fixing weight decay regularization in adam[END_REF] using a learning rate of 5e-5 to apply gradients with respect to the loss and weight decay.

All results are reported using the average performances of over 30 runs for intent classification and over 5 runs for slot filling (fewer amount of runs because of higher training time).

Results

Our experimental findings are summarized in Tables 2 and 3 for the intent classification and the slot-filling tasks, respectively.

Intent classification results

Using the target only configuration, the baseline obtains optimal scores when applied to high resource languages, e.g. English (en), French (fr) or German (de) reaching nearly identical high scores. We obtain the highest baseline scores with an accuracy of 98.8 on the French model, followed by the English model with an accuracy of 98.5. Unlike other mainstream languages, the baseline is less accurate on under-resourced languages, with a loss of 7 to 15 points for intent classification on Hindi (hi) and Turkish (tr) respectively.

In multilingual configuration, baseline models perform reasonably well over all the high-resource languages with a significant performance boost due to the availability of additional data. The mBERT + PNN (5w10s) models outperformed the baseline for all languages, except for the Turkish (tr) language.

When transferring from all languages to an unseen one (multilingual zero-shot configuration) we observe the best results for the mBERT model, except Portuguese (pt) and English (en) languages, in which the mBERT + PNN (5w10s) is 0.5 points better.

Finally, within the framework of the intent classification task, the mBERT + PNN (5w10s) model achieves better overall performances in the multilingual configuration, especially in the case of underresourced languages with a gain up to 9 points of accuracy, compared to the target-only configuration and an average of one point compared to the best model in the multilingual zero-shot configuration.

Slot-filling results

Slot-filling result trends in the target only configuration are about one point better of F1 score for the mBERT + PNN (5w10s) model compared to the baseline model (mBERT). The mBERT + PNN (5w10s) model even outperformed the baseline by more than 4 points of F1 in the Turkish task (tr).

We can observe the same trend in the multilingual configuration: our approach outperformed the baseline in all languages.

On the contrary, the mBERT + PNN (5w10s) fails in most of language tasks in the multilingual zero-shot configuration, except for the Hindi (hi) and the Turkish (tr) languages.

Finally, like the intent classification task, the mBERT + PNN (5w10s) model achieves better overall performance in the multilingual configuration for all languages.

Result analysis

First, our baseline results are on par with those obtained by [START_REF] Qin | A stack-propagation framework with token-level intent detection for spoken language understanding[END_REF] and [START_REF] Xu | End-to-end slot alignment and recognition for crosslingual NLU[END_REF] when they trained BERT-based models using only English training data (en) with intent accuracy scores of 97.5% and 96.08% while we obtain 98.5%. This is the same in our slot-filling experiment in which they report 94.7 F1 points while we obtain 95.6. This difference comes from our results averaging between 30 and 5 runs for intent classification and slot filling, while previous works only performed 5 runs. We also observe that, just like [START_REF] Xu | End-to-end slot alignment and recognition for crosslingual NLU[END_REF], slot filling on Spanish (es) leads to lower results, similar to those obtained in our few-shot setting.

When transferring from all languages to an unseen one (multilingual zero-shot configuration in both tables 2 and 3) we obtained lower scores than the multilingual configurations. This means the multilingual representation captured in mBERT is efficient enough when data is available in several languages and none are available in the target considered language. But, in both cases, the combination of mBERT+PNN performs better when fewer data is available using the few-shot approach (the multilingual configuration). This means that our approach quickly adapts to the considered target language with only a few examples available and enhances the mBERT multilingual transfer learning capabilities. This is especially true in the case of slot filling with gains in terms of F1-scores ranging from 2 to 5 points.

Finally, using the mBERT baseline model, transfer learning to French or German has performance scores similar to English while using the Turkish (tr) or Hindi (hi) yielded significant loss. This leads us to the same conclusion as [START_REF] Xu | End-to-end slot alignment and recognition for crosslingual NLU[END_REF]: exploiting language interrelationships learnt with transfer learning improve the model performances. This may come from the fact that French, English and German are similar and share some vocabulary while Turkish or Hindi are dissimilar to European languages [START_REF] Henrich | Language history, language change, and language relationship: An introduction to historical and comparative linguistics[END_REF].

A detailed inspection of the PNNs results shows that in the target only and in the multilingual configurations, there is an overall and important reduction in recall values, which is balanced by an improvement of the precision values. If we analyze deeper the mislabeled examples we can observe that applying PNNs help to prevent overlapping and annotation mismatch cases that occur in the data.

We observed that MultiAtis++ corpus seems to be a highly unbalanced labeled dataset with the number of training examples per class varying from 1 to 3300. This impacts the model performance, and it could explain why we observe a lower recall and an improvement in precision using our approach, since it is based on the reduction of the amount of data.

Conclusions

In this paper, we demonstrate the opportunities in leveraging mBERT-based modeling using few-shot learning for both intent classification and slot filling tasks on under-resource languages. We found that our approach model is a highly effective technique for training models for low-resource languages. This illustrates the performance gains that can be achieved by exploiting language interrelationships learnt with transfer learning, a conclusion further emphasised by the fact that multilingual results outperformed other configuration models (target only and specifically multilingual zero-shot) regardless of the approach. Overall, PNNs models outperform mBERT-based transfer learning approach, enabling us to train competitive NLU systems for underresources languages with only a fraction of training examples.

From this work a new challenge naturally comes up and a possible direction is to adapt a few-shot setting to a joint approach of intent detection and slot filling, like in [START_REF] Zhang | A joint model of intent determination and slot filling for spoken language understanding[END_REF], [START_REF] Liu | Attention-based recurrent neural network models for joint intent detection and slot filling[END_REF] and [START_REF] Zhang | Joint slot filling and intent detection via capsule neural networks[END_REF], which demonstrates that performing these two tasks jointly improves the performance of both of them.

Table 1 :

 1 . To enable cross-lingual transfer according to our few-shot Details of the MultiATIS++ corpus.

	Language	# utterances train dev test	train	# tokens dev	test	# intents # slot types
	English			50755	5445	9164
	Spanish			55197	5927 10338
	Portuguese			55052	5909 10228
	German	4488 490 893	51111	5517	9383	18	84
	French			55909	5769 10511
	Chinese			88194	9652 16710
	Japanese			133890 14416 25939
	Hindi	1440 160 893	16422	1753	9755	17	75
	Turkish	578	60 715	6132	686	7683	17	71

Table 2 :

 2 Averaged intent accuracies obtained with PNNs on 5-way k-shot classification k ∈ [1, 10] (best scores are marked in bold) and baseline results.

	config.	encoder	en	es	de	zh	ja	pt	fr	hi	tr
	target only	mBERT	98.54 97.31 98.43 97.09 97.20 97.54 98.88 90.93 83.36
		mBERT + PNN (5w1s)	97.46 95.14 97.18 96.35 95.53 96.80 97.11 84.95 85.17
		mBERT + PNN (5w10s) 98.77 96.97 98.54 97.0 96.64 97.42 97.98 91.33 89.33
	multilingual	mBERT	98.42 97.98 98.59 97.65 97.45 98.3 98.46 95.33 93.93
		mBERT + PNN (5w1s)	95.33 93.71 95.93 95.89 94.42 94.00 94.78 91.4 90.91
		mBERT + PNN (5w10s) 99.87 98.54 98.60 98.67 98.54 98.32 98.66 95.49 92.61
	multilingual (zero shot) mBERT	96.42 97.98 97.54 96.71 97.45 97.42 97.87 94.37 91.61
		mBERT + PNN (5w1s)	93.73 92.02 93.27 95.62 91.73 93.51 93.28 90.51 89.92
		mBERT + PNN (5w10s) 96.47 97.87 96.86 97.65 96.64 98.10 97.45 93.17 90.67

• multilingual zero-shot: where the training relies on the concatenation of all training

Table 3 :

 3 .52 94.88 92.93 93.13 91.71 92.78 85.12 78.22 mBERT + PNN (5w10s) 95.76 87.40 95.63 93.45 93.93 92.22 93.13 85.70 82.67 multilingual mBERT 96.02 88.03 95.03 93.63 93.01 92.31 91.18 87.39 86.83 mBERT + PNN (5w10s) 98.40 92.09 97.12 95.50 97.24 95.81 96.80 89.59 88.39 multilingual (zero shot) mBERT 94.10 87.14 94.23 92.17 92.61 91.59 90.79 86.14 85.86 mBERT + PNN (5w10s) 93.25 86.99 93.57 91.82 92.38 91.19 90.39 87.49 86.83 Averaged slot F1s obtained with PNNs on 5-way 10-shot and baseline results (highest scores are marked in bold).

	config.	encoder	en	es	de	zh	ja	pt	fr	hi	tr
	target only	mBERT	95.64 85