Olivier Brouard
email: olivier.brouard@univ-nantes.fr

Fabrice Delannay

Vincent Ricordel

Dominique Barba

FAST LONG-TERM MOTION ESTIMATION FOR HIGH DEFINITION VIDEO SEQUENCES BASED ON SPATIO-TEMPORAL TUBES AND USING THE NELDER-MEAD SIMPLEX ALGORITHM

Keywords: Long-Term Motion Prediction, Multi-Resolution Motion Estimation, Nelder-Mead Simplex, Spatio-Temporal Tubes

Multi-frame motion estimation is a new method incorporated into the video coding standard H.264/MPEG-4 Advanced Video Coding (AVC) to improve compression performances. Depending on content, the motion estimation can be short or long-term. For long-term motion estimation, the initial search point in the reference frame is important. In this paper 1 , we propose a new method for a fast long-term motion estimation with high definition (HD) sequences. We use an implicit uniform motion model. First we describe the multiresolution motion estimation based on spatio-temporal tubes. These tubes provide a good initial search point for the longterm motion estimation that follows. Then, the search is refined using the Nelder-Mead Simplex method. The global approach reduces computational cost and improves the accuracy of motion estimation.

INTRODUCTION

The new video coding standard H.264/MPEG-4 AVC [START_REF] Richardson | 264 and MPEG-4 video compression: Video Coding for Next-Generation Multimedia[END_REF] developed by the Joint Video Team of ISO/IEC MPEG and ITU-T Video Coding Expert Group aims at allowing a bit rate reduction of 50% compared to MPEG-2 for the same restitution quality. This higher compression efficiency is obtained using different specifications which are in particular multiprediction modes, multi-reference frames, and higher motion vector resolution. As a consequence the motion estimation represents the most time consuming part.

In order, to reduce the computational cost of motion estimation, several fast search algorithms have been proposed. Some of them use multi-resolution motion estimation [START_REF] Choi | Realtime H.264 Encoding System using Fast Motion Estimation and Mode Decision[END_REF] [START_REF] Liu | Low-Pass Filter Based VLSI Oriented Variable Block Size Motion Estimation Algorithm for H.264[END_REF]. In these methods, frames are first spatially reduced and then motion estimation is computed at the smallest resolution of the frame. The motion vector obtained for lower resolution is then used as motion vector prediction for the higher resolution. This scheme reduces the search window size and accelerates the motion estimation.

The H.264/MPEG-4 AVC encoder and decoder use two lists of previously coded/decoded pictures, which are the reference pictures for the motion estimation. Although, the utilization of multiple reference frames for motion estimation provides significant coding gain [START_REF] Wiegand | Long-Term Memory Motion-Compensated Prediction[END_REF], computational complexity increases dramatically. The stored frames in the two lists of previously coded/decoded pictures can be short or longterm reference pictures. In a video, the immediately previous frame is often highly correlated with the current frame. Thus, the search window for motion estimation is usually centered on the block of the current frame to predict. However, for long-term reference pictures, contents of the video may can undergo important displacements. With a multi-resolution approach, if the search window is still centered on the current block and not up-scaled, the computed motion vector might correspond to a local minimum of the cost function used. In [START_REF] Hsiao | Short/Long-Term Motion Vector Prediction in Multi-Frame Video Coding System[END_REF], Hsiao et al. exploit the spatial/temporal correlation in the motion vector fields to predict the initial search point for the long-term motion estimation. This initial search point accelerates the convergence speed of fast search algorithms for motion estimation.

In the following section, we present the multi-resolution motion estimation method based on tubes for HD sequences. In section 3, we describe the Nelder-Mead Simplex method. In section 4, we combine both methods to get an efficient long-term motion estimation. Finally, we show the simulation results in section 5 and give a conclusion in section 6.

MULTI-RESOLUTION MOTION ESTIMATION BASED ON TUBES

In [START_REF] Péchard | A new methodology to estimate the impact of H.264 artefacts on subjective video quality[END_REF], Pechard et al. proposed a multi-resolution motion estimation in order to accelerate motion estimation with HD frames. We describe this method because it gives the concept of spatio-temporal tubes.

The HD frames are spatially filtered and sub-sampled by a factor of six. First, the frames are sub-sampled by a factor of two, and then, by a factor of three. Before each sub-sampling step, an adequate (half-bandwidth, and then, one-third the bandwidth) low-pass filter is performed to avoid aliasing.

From the filtered and spatially sub-sampled frames, the motion estimation is computed. We use five consecutive frames, and consider a uniform motion between the frames. Thus, we create a tube between the frames. Each block is simultaneously compared to its potentially corresponding aligned blocks in the two previous frames and in the two next frames, as illustrated in Fig. 1. The global error, M SE G , is obtained by the sum of the four Mean Square Error (MSE) between the current block and its corresponding aligned blocks in the two previous frames and in the two next frames, as written in Eq. 1.

M SEG = k M SE k , k = -2, -1, +1, +2. (1)
M SE k takes into account the three YUV components of each block, as written in Eq. 2.

M SE k = 1 N ×N N -1 i,j=0 (C Y (i,j)-Rk Y (i+λ k .m,j+λ k .n)) 2 + N -1 i,j=0 (C U (i,j)-Rk U (i+λ k .m,j+λ k .n)) 2 + N -1 i,j=0 (C V (i,j)-Rk V (i+λ k .m,j+λ k .n)) 2 , (2)
with λ 0 = 2, λ 1 = 1, λ 3 = -1, and λ 4 = -2, and (m, n) the motion vector between the current frame F t and the immediately previous frame

F t-1 . C Y , C U , C V , Rk Y , Rk U ,

and

Rk V represent respectively the three YUV components of the current frame, and of the frames used as reference for motion estimation with blocks of size N × N .

search window

F t F t+1 F t+2 F t-1 F t-2 current block MV (t,t-2) b0 b1 b3 b4
Fig. 1. The five frames used to determine the motion vector of a given block. A spatio-temporal tube is obtained.

The motion vector of a block from F t is chosen such that it gives the lowest M SE G between the current block and its corresponding blocks in the surrounding four frames. The motion vectors are estimated at the lowest resolution, and then, they are up-scaled appropriately to the higher resolution to be used as an initial search point.

The alignment of the blocks induces a spatio-temporal constraint in the tubes computation. This constraint produces very smoo-th and coherent motion vectors fields for the HD video sequences. This propriety is fundamental because the tubes motion vectors will be used to initialize the long-term motion estimation (LTME).

NELDER-MEAD SIMPLEX METHOD

The Nelder-Mead Simplex (NMS) method [START_REF] Nelder | A simplex method for function minimization[END_REF] attempts to minimize a scalar-valued nonlinear function of n real variables using only function values, without any derivative information (explicit or implicit). The Nelder-Mead algorithm applied to strictly convex functions in one or two dimensions converges [START_REF] Lagarias | Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions[END_REF], so we heve adapted this method for long-term motion estimation.

The Nelder-Mead algorithm minimizes a real-valued function f (x) for x ∈ n . To define a complete NMS method, four scalar parameters must be specified : coefficients of reflection (ρ), expansion (χ), contraction (γ), and shrinkage (σ). According, to the original NMS method, these four parameters should satisfy : ρ > 0, χ > 1, χ > ρ, 0 < γ < 1, and 0 < σ < 1. We use the following values for the parameters (the nearly universal choices in the standard NMS), ρ = 1, χ = 2, γ = 1 2 , and σ = 1 2 . At the k th iteration, k ≥ 0, a non degenerate simplex ∆ k is given with its n + 1 vertices, each of which is a point in n . These vertices, labeled x k 1 , ..., x k n+1 , are ordered in the following way,

f (x (k) 1 ) ≤ f (x (k) 2 ) ≤ ... ≤ f (x (k) n+1 ).
The k th iteration generates a set of N + 1 vertices which defines a different simplex for the next iteration, so ∆ k+1 = ∆ k . As we want to minimize f , x As we use the NMS method for block matching, the function f , that we want to minimize is the MSE. Block matching is a two dimensions problem, so n = 2, and the n + 1 = 3 vertices of the simplex represent the positions of candidate blocks.

One iteration of the NMS Algorithm can be described as the following way :

1. Order the 3 vertices to satisfy f (x 1 ) ≤ f (x 2 ) ≤ f (x 3 ).

Compute the reflection point

x r from xr = x + ρ(x -x3) = (1 + ρ)x -ρx3, where x = 2 i=1 x i /2 is the centroid of the 2 best points. If f (x 1 ) ≤ f (x r ) < f (x 2 )
, accept the reflected point x r and terminate the iteration.

If

f (x r ) < f (x 1 ), calculate the expansion point x e , xe = x + χ(xr -x) = (1 + ρχ)x -ρχx3,
if f (x e ) < f (x r ), accept x e and terminate the iteration; otherwise accept x r and terminate the iteration.

4. If f (x r ) ≥ f (x 2 ), perform a contraction between x and the better of x 3 and x r

• a) If f (x 2 ) ≤ f (x r ) < f (x 3 ), perform an outside contraction,

xc = x + γ(xr -x) = (1 + ργ)x -ργx3, if f (x c ) ≤ f (x r )
, accept x c and terminate the iteration; otherwise go to step 5.

• b) If f (x r ) ≥ f (x 3 ), perform an inside contrac- tion, xcc = x + γ(x -x3) = (1 -γ)x + γx3), if f (x cc ) < f (x 3
), accept x cc and terminate the iteration; otherwise go to step 5.

Evaluate f at the 2 points

v i = x 1 + σ(x i -x 1 ), i = 2, 3.
The unordered vertices simplex at the next iteration consist of x 1 , v 2 , and v 3 (shrinkage).

Figure 2 shows the effects of reflection, expansion, contraction and shrinkage.

LONG-TERM MOTION ESTIMATION

Our goal is now to improve the long-term motion estimation using both fast methods : the spatio-temporal tube to find an optimal initial search point, and the NMS method to achieve the long-term motion estimation.

If the reference frame, used for motion estimation of the current frame, is the immediately previous frame, these two frames are highly temporally correlated and the motion vector will remain weak. Thus, the search window does not need to be too large and is centered on the current block to be estimated. But, if the reference frame is temporally far from the current one, the spatial correlation decreases. In this case, it is important to predict a good initial search point for motion estimation that will not obtain a local minimum of the cost function and reduces the calculation time.

Considering the current frame F t , our strategy is to first use the motion vector of the tube to get an optimal initial search point for the long-term motion estimation. This motion estimation is realized using the multi-resolution motion estimation method explained in section 2. The motion vector obtained, M V (t,t-1) , is then up-scaled by the time interval between the current frame and the long-term reference (see Eq. 3).

M V pred(t,t-k) = k × M V (t,t-1) . (3)
The predicted motion vector, M V pred(t,t-k) is used as the initial search point for long-term motion estimation, as illustrated in Fig. 3. For the long-term motion estimation, we use the NMS method described in section 3 to refine the motion vector.

search window F t F t+1 F t+2 F t-1 F t-2 current block initial search point F t-k MV (t,t-1)
Fig. 3. Initialization of the long-term motion estimation.

SIMULATION RESULTS

We used 1080p HD sequences (blue sky, pedestrian, station, rush hour) from SVT [START_REF] Svt | Overall-quality assessment when targeting wide xga flat panel displays[END_REF]. These videos can be classified in two categories according to their motion and their content. The first category with high motion contains the two sequences pedestrian, and rush hour. The other category contains sequences with slow motion like blue sky, and station.

For the motion estimation the blocks size is about 16 × 16.

The best motion vector is obtained by a search on integer-pel positions with a search window of size 20 × 20 (±20 pixels in each direction) for the Full Search method. Table 1 and Table 2 show the comparison results in term of computing times and PSNR, between our long-term motion estimation (LTME) method, a Full Search (FS) method centered on the block, and a Full Search method with an initial search point (FSI). This initial search point is obtained using a Full Search between the current frame and the immediately previous frame, the motion vector obtained is then extrapolated to the long term reference frame using equation 3. We want to show that our method is faster, and more accurate than a FS method but also performs almost as well as the FSI. The PSNR is computed between the current frame F t and the frame F t-k that is motion compensated using the computed long-term vectors. The encoding speed has been measured as the relative variation in computation time (see Eq. 4) between the considered methods (T ) and the FS method (T F S ):

T (%) = T -TF S TF S × 100. (4)
According to tables 1 and 2, our method can accelerate the motion estimation up to 46% and performs better than Full Search centered on the current block. If the video contains important and irregular motions (pedestrian and rush hour) our LTME method performs better in terms of PSNR and computing time than the FSI. Indeed with the NMS algorithm, the motion estimation is not forced by a search window and can find a better distant block. As illustrated in figure 4, the simulations results show, that we obtained better compensated frames (PSNR) with our LTME when the video contains important motions, whatever the time interval between the current frame and the long-term frame used as reference.

CONCLUSIONS

In this paper, we presented a new fast long-term motion estimation (LTME) method for HD sequences. First, a multiresolution motion estimation is realized in order to obtain a tube as an initial search point for the long-term reference. Then, we use the Nelder-Mead Simplex (NMS) method to refine the motion vectors between the current and long-term reference frames. The results obtained with our LTME are better in terms of computing time and PSNR compared to a Full Search method. We also compare our LTME with a Full Search method using a initial search point obtained from a full search on the previous frame and extrapolated to the long-term reference frame. In case of important and irregular motions in the video sequence, our LTME obtains more accurate results owing to the the NMS algorithm which is not limited by a search window and can search for a better distant point.

  n+1 are respectively the best point, the n th best point, and the worst point.

Fig. 2 .

 2 Fig. 2. Nelder-Mead simplices after different steps. The original simplex is shown with a dashed line.

Fig. 4 .

 4 Fig. 4. PSNR comparisons for the different methods with different time intervals for the sequence pedestrian.

Table 1 .

 1 Comparison of PSNR (dB) and coding speed with a long time interval of five frames between F t and F t-k .

	Sequence	FS		LTME		FSI
		PSNR	∆T(%)	PSNR	∆T(%)	PSNR	∆T(%)
	pedestrian	21.54	-	27.05	-28.55	23.91	99.36
	rush hour 27.67	-	30.65	-27.20	30.36	98.70
	station	31.93	-	34.24	-46.00	36.63	98.22
	blue sky	22.48	-	28.80	-42.37	31.61	98.50
	Sequence	FS		LTME		FSI
		PSNR	∆T(%)	PSNR	∆T(%)	PSNR	∆T(%)
	pedestrian	19.37	-	25.08	-27.95	20.79	96.89
	rush hour	23.54	-	27.94	-26.87	26.00	96.94
	station	28.58	-	31.04	-46.14	34.16	92.63
	blue sky	20.14	-	24.56	-42.82	28.92	96.30

Table 2 .

 2 Comparison of PSNR (dB) and coding speed with a long time interval of ten frames between F t and F t-k .

This research was carried out within the framework of the ArchiPEG project financed by the ANR (convention N • ANR05RIAM01401).


Olivier Brouard
email: olivier.brouard@univ-nantes.fr

Fabrice Delannay

Vincent Ricordel

Dominique Barba

ROBUST MOTION SEGMENTATION FOR HIGH DEFINITION VIDEO SEQUENCES USING A FAST MULTI-RESOLUTION MOTION ESTIMATION BASED ON SPATIO-TEMPORAL TUBES

Keywords: Robust Motion Segmentation, Global Motion Estimation, Multi-Resolution Motion Estimation, Spatio-Temporal Tubes

Motion segmentation methods are effective for tracking video objects. However, objects segmentation methods based on motion need to know the global motion of the video in order to back-compensate it before computing the segmentation. In this paper 1 , we propose a method which estimates the global motion of a High Definition (HD) video shot and then segments it using the remaining motion information. First, we develop a fast method for multi-resolution motion estimation based on spatio-temporal tubes. So we get a homogeneous motion vectors field (one vector per tube). From this motion field, we use a robust approach to estimate the parameters of the affine model that characterizes the global motion of the shot. After back-compensation of the video shot global motion, the remaining motion vectors are used to achieve the motion segmentation and extract the video objects.

INTRODUCTION

The methods for tracking video objects are efficient to encode a video shot. Indeed, one possible strategy is to use adapted coding parameters for coding a given video object during all its lifespan. By video object, we mean typically, a spatiotemporal shape characterized by its texture, its color, and its own motion that differs from the global motion of the shot.

In order to track spatio-temporal objects in a video sequence, they need to be segmented. In the literature, several kinds of methods are described. These different methods use spatial and/or temporal [START_REF] Megret | A survey of spatio-temporal grouping techniques[END_REF][START_REF] Porikli | Automatic Video Object Segmentation Using Volume Growing and Hierarchical Clustering[END_REF][START_REF] Wang | Moving Object Tracking in Video[END_REF] information to segment the objects. In the case of temporal information, it is necessary (when the camera moves) to know the global motion of the video to perform an effective video objects segmentation. Horn and Schunck [START_REF] Horn | Determining Optical Flow[END_REF] proposed to determine the optical flow between two frames. Thus, it allows to obtain information about the moving objects. Otherwise, the motion parametric model of the successive frames can be estimated [START_REF] Odobez | Robust Multiresolution Estimation of Parametric Motion Models[END_REF]. Once the motion model is known, the global motion is backcompensated, and only the moving objects remain with their local motion information. In our method, we use a motion information per block, but for a group of frames (GOF), to estimate the global motion and realize the motion segmentation. This motion estimation needs to reflect as much as possible the real motion (i.e. the motion vectors of the scene real objects) of the block to give the right information to be processed. Exactly we use a motion estimation method which, considering several successive reference frames, estimates the motion of spatio-temporal tubes [START_REF] Péchard | A new methodology to estimate the impact of H.264 artefacts on subjective video quality[END_REF], with the hypothesis of an uniform motion along the GOF. Once, we have the motion vectors of the tubes, the second step is the estimation of the global motion. We adapt the motion vectors accumulation method described by Coudray [START_REF] Coudray | Global Motion Estimation for MPEG-Encoded Streams[END_REF] to estimate robustly the parameters of an affine motion model from the obtained motion vectors. Then, the global motion is compensated, and only the vectors which belong to moving objects remain non null. For the last step we realize the motion segmentation from them.

In the following section, we present the fast multi-resolution motion estimation method based on tubes. In section 3, we describe the robust computation of the global motion parameters, and in section 4, the motion segmentation method is given. Finally, we show the simulation results in section 5, and we conclude in section 6.

FAST MULTI-RESOLUTION MOTION ESTIMATION BASED ON TUBES

To obtain motion information correlated with the motions of real life objects in the video shot, we consider several successive frames and we make the assumption of an uniform motion between them. The fixing's time of the Human Visual System (SVH) is about 200 ms [START_REF] Le Meur | A Coherent Computational Approach to Model Bottom-Up Visual Attention[END_REF], so as the next generation of HDTV will use 1920×1080 as frame definition in progressive mode with a frame rate of 50 Hz, our method will use a GOF composed of nine frames (180ms). Thus, we ensure the coherence of the motion along a perceptually significant duration. The current frame is at the center of the GOF. So, four past frames, and four future frames are located around it. We use the information along these nine frames to constrain the motion estimation, and obtain motion vectors more correlated with the real motion. In practice, we use only five frames from the GOF to evaluate the motion vectors, as illustrated in figure 1. We consider an uniform motion and we create a spatiotemporal tube. The tube allows to track a given block aligned on several successive frames. This constraint produces a motion vectors field more homogeneous (smoother) and more correlated with the real motion.

current block search window F F F F F F F F F t-4 t-3 t-2 t-1 t t+1 t+2 t+3 t+4 b4 b1 b0 b3
Fig. 1. Spatio-temporal tube: the five frames used to determine the motion vector of a given block.

We adapt the multi-resolution motion estimation method introduced by Péchard et al. [START_REF] Péchard | A new methodology to estimate the impact of H.264 artefacts on subjective video quality[END_REF] because it is well suited to deal with HD videos. The HD frames are spatially filtered and sub-sampled by a factor of six (first the frames are sub-sampled by a factor of two, and then by a factor of three), because the cutting in radial frequencies of the HVS is not dyadic and the angular selectivity varies with the radial frequency. Before each sub-sampling step, an appropriate (half-bandwidth, and then one-third bandwidth) low-pass filter is performed to avoid aliasing. From the filtered and spatially sub-sampled frames, we compute the motion estimation. Each block is simultaneously compared to its potentially corresponding blocks aligned in the previous frames and in the next frames, as illustrated in figure 1. The global error, M SE G = k M SE k with k = -4, -2, +2, +4, is the sum of the four Mean Square Errors (MSE) between the current block and its corresponding blocks in the previous frames and in the next frames. The index k represents the positions of the reference frames in comparison to the current frame. M SE k takes into account the three YUV components of each block. The chosen motion vector of a tube gives the lowest M SE G between the current block and its corresponding blocks in the four frames. The motion vectors are first estimated at the lowest resolution. Then, they are up-scaled appropriately to the higher resolution to be used as an initial search point for the motion estimation at the new resolution. These aligned blocks constitute a spatio-temporal tube.

Finally we get a motion vectors field with one vector per tube, each motion vector is applied to the block of the image F t in the center of the tube. This motion vectors field is the input of the next process : the global motion estimation.

ROBUST GLOBAL MOTION ESTIMATION

Once we computed the motion estimation, the obtained motion vectors reflect more effectively the motion of the real life objects. The next step is to identify the parameters of the global motion of the GOF from this motion vectors field. Several models exist to estimate the global motion of a video, we use an affine model with six parameters as written in Eq. 1:

Vx Vy = a1 a2 a3 a4 x y + tx ty , (1)
where a i (i = 1 . . . 4) are the deformation parameters (exactly a 1 and a 4 characterized the zoom, and a 2 and a 3 the rotation), t x and t y are the translation parameters. V x , V y , x and y are respectively the horizontal and vertical components of each motion vector, and the spatial position of the block in the image F t .

Global motion parameters estimation

We adapt the method introduce by Coudray [START_REF] Coudray | Global Motion Estimation for MPEG-Encoded Streams[END_REF] who estimated the global motion from a MPEG2 stream. For us the basic information used to estimate the global motion is a motion vectors field, one motion vector per tube. We estimate the parameters of the affine model from the motion vectors field using the following equations: (

) 2
The global motion is often due to the camera motion, which can be relatively complex. As a zoom or a rotation affects the estimation of the translation parameters (because all these parameters are correlated), the global motion estimation (GME) is realized in two steps. First, we compute the deformation parameters from each motion vector. Each calculated derivative produces an assumption for the corresponding global motion parameters. To find the main assumption (with the highest probability) that matches the global motion parameter, the unit assumptions are accumulated in an histogram (one respective histogram for each global parameter). In order to gather the close assumptions, they are weighted using a Gaussian distribution.

The localization of the main peak of a given histogram produces the value retained for the corresponding parameter of the global motion model. To refine the localization of a main parameter, a least squares method is used to estimate the bend around the found position. Once the deformation parameters have been identified, they are used to compensate the original motion vectors field. Thus, the remaining vectors correspond only to the translation motions. These remaining motion vectors are then accumulated in a two dimensions histogram using a weighted Gaussian distribution (see Eq. 3):

G(x, y) = 1 2πσ 2 e - x 2 +y 2 2σ 2 , (3)
where x and y represent the compensated components of the motion vectors V x and V y respectively. The main values of the translation parameters are obtained by the localization of the main peak in the two dimensions histogram. For the last step the motion vectors are also compensated with the obtained translation parameters.

Weights of confidence for a robust estimation

For a given block of F t (see figure 1), the motion vector obtained from the motion estimation minimizes the MSE. If the blocks of the tube are located inside a uniform region in the images, the matching of blocks is not confident. Thus, the blocks of the tube are not necessarily the blocks that belong to the real object. In this case, the motion vector associated with the tube could not reflect the real motion. To be robust, such motion vectors should not contribute to the GME. For this reason the motion vector contribution has to be weighted in function of the spatio-temporal content of the blocks belonging to the tube. Briefly, the motion vectors from highly textured and oriented areas give more reliable information about the real motion than those which belong to uniform areas. Hence we exploit the spatial activity of the tube to qualify it. To compute the spatial activity of the blocks, we use spatial gradients. The higher the spatial gradients of the tube blocks, the more confident its motion vector is.

For each block, we use two spatial gradients, ∆V and ∆H, which are respectively the average vertical and the average horizontal gradients. Depending on these features, a block may be labeled as a smooth, a fairly textured, or a highly textured area.

A block labeled as a highly textured area, can be it in only one direction, i.e. one of the two spatial gradients is high and the other is low. If the global motion is a translation in the same direction (vertical or horizontal) as the textured area, then the motion vectors of the blocks located in that region are not confident. So we distinguish the two spatial gradients. In practice, the confidence granted to the two components of the motion vector is calculated in a suitable way according to the blocks spatial gradients (Ψ(∆H) and Ψ(∆V )). The function Ψ, to obtain the weights according to the spatial gradients, is computed as following (as illustrated in figure 2):

Ψ(x) = ( x 8 ) 3 /2, x ≤ 8 1 -Ψ(16 -x), 8 < x < 16 1 otherwise (4)
Figure 2 shows the weights of confidence for a GOF of the HD video sequence Shields. We observe that the maps that illustrate the weights of confidence of the GOF are different according to the orientations of the spatial gradients.

From now, to achieve a robust estimation of the global motion parameters, instead of the derivatives of the tube motion vectors, we use their weighted versions for their accumulation as described in the previous sub-section.

MOTION-BASED SEGMENTATION

For the GME, we determined the translation parameters by the localization of the maximum in the accumulation histogram of the already compensated motion vectors. Assuming that each histogram peak represents an object motion, we do not retain only the main peak but all of them to segment the GOF.

In practice the first step consists of eliminating the noise. A reject threshold is defined empirically and all the values under it are fixed to zero. From the first detected peak which corresponds to the global maximum in the accumulation space, for all the positions connected to this peak, a local gradient is computed. This gradient is the difference between the populations of the two connected cells but in the direction of the maximum. As long as the gradient is positive, the tested position is considered as belonging to the peak, and the algorithm is iterated with the connected cells. At the end, all the positions belonging to the main peak are labeled. A new maximum is then detected among all the remaining (not labeled) cells, and the algorithm is iterated as long as there remain non null cells without label. If one cell is labeled as belonging to several peaks, it is linked to the closest peak.

SIMULATION RESULTS

We used one 1080p (Tractor), and two 720p (Shields and New mobile calendar) HD sequences from SVT [START_REF] Svt | Overall-quality assessment when targeting wide xga flat panel displays[END_REF]. These video sequences present different motions of the camera, and they contain one or several moving objects. We compare the results of our GME method to those from the Motion2D software [START_REF]Motion2D[END_REF]. Motion2D processes from a dense motion vectors field, and estimates robustly the parameters of the global motion using a multi-resolution least mean squares method (it is currently the reference method for the GME). As Motion2D computes the parameters of the global motion for two successive frames, we combine the obtained parameters for nine consecutive frames in order to compare them with ours. Figure 3 shows some characteristic results obtained with the New mobile calendar video sequence. The x-axis represents the GOF index. The global deformation parameters for the zoom (a 1 and a 4 ) are not presented because they are estimated as near from zero according to the two methods. Excepted a slow zoom out, the only motions of the camera are translations. The two distinct objects (the calendar and the train) have their own translational motion. As result, Motion2D estimates the combination of the two objects translations as a global rotation, our method performs better and find only the objects translations. As a consequence, our estimation of the global translation is more accurate too. This result is specially due to the high regularity of our motion vectors field based on spatio-temporal tubes. Figure 4 shows the results of the motion segmentation afour GME method for the three GOF. In the map (a), we observe clearly two different regions, which are the background and the moving man. The map (b) shows the result of the motion segmentation for one GOF of the video sequence Tractor. As the motion of the camera is a translation, uncovered areas appear on the sides of the map. So, the blocks located on these sides are not correctly segmented. But we observe that the tractor is clearly segmented in respect to the background. The tractor itself is segmented in different regions which are its "body" and the seeder. However, the wheels are not correctly segmented. Indeed, their motion is complex, as it is a combination of a rotation and a translation. In the last map (c), we observe clearly the different objects of the GOF (the background, the calendar and the train), but there are still some isolated blocks. Indeed, the motion vectors from these uniform areas are not confident for motion segmentation.

! "! #! $! %! &! !!'" !!'!& ! !'!& !'" ()*+,-./0 1# ! "! #! $! %! &! !!'" !!'!& ! !'!& !'"

CONCLUSIONS

In this paper, we presented a motion segmentation method for HD sequences. First, a fast multi-resolution motion estimation based on spatio-temporal tubes using several reference frames is realized in order to obtain a field of motion vectors (one vector per tube) for the GOF (nine frames, with the assumption that the motion is uniform along it). The (derivatives) motion vectors are weighted according to the spatial activity of the tube, and accumulated in histograms. Then, we estimate robustly the global motion parameters of an affine model. The global motion is then back-compensated, and from the remaining accumulated motion vectors (with the assumption that each peak represents one object motion) the other peaks are extracted in order to achieve the motion based segmentation.

  a1 = ∂Vx ∂x , a4 = ∂Vy ∂y , a2 = ∂Vx ∂y , a3 = ∂Vy ∂x , tx = Vx -a1.x -a2.y, ty = Vy -a3.x -a4.y.

  Picture from the video sequence Shields. Exactly this picture is used as Ft. (c) Map of the weights for the horizontal gradients (white = 1, black = 0). (d) Map of the weights for the vertical gradients (white = 1, black = 0).

Fig. 2 .

 2 Fig. 2. Illustration of the confidence function.

(Fig. 3 .

 3 Fig. 3. Estimation of the global rotation parameters and the global translation parameters using our GME method (•) or Motion2D (+) for the New mobile calendar video sequence.

  (a) Map for the GOF of Shields sequence (b) Map for the GOF of Tractor sequence (c) Map for the GOF of New mobile calendar sequence

Fig. 4 .

 4 Fig. 4. Motion segmentation maps for the three GOF.

This research was carried out within the framework of the ArchiPEG project financed by the ANR (convention N • ANR05RIAM01401).


Benoît Vermersch

Jean Claude Garreau

Emergence of nonlinear behavior in the dynamics of ultracold bosons

Keywords: numbers: 03.75.Lm, 05.45.a, 03.75.Kk

We study the evolution of a system of interacting ultracold bosons, which presents nonlinear, chaotic, behaviors in the limit of very large number of particles. Using the spectral entropy as an indicator of chaos and three different numerical approaches : Exact diagonalization, truncated Husimi method and mean-field (Gross-Pitaevskii) approximation, we put into evidence the destructive impact of quantum noise on the emergence of the nonlinear dynamics.

I. INTRODUCTION

Ultracold atoms are clean, controllable, highly flexible experimental systems, that can often be modeled from first principles. For such reasons they have become in recent years a preferred testing ground for quantum many-body effects [1]. A particularly interesting example is the emergence of chaotic behaviors in quantum systems : The Schrödinger equation is linear and hence cannot display chaotic behavior in the classical sense (i.e. chaos associated to a sensitivity to initial conditions), however, the classical world very often display chaos. Bose-Einstein condensates can be produced in laboratories at mesoscopic sizes (up to 10 8 atoms) [2] in intrinsically quantum-coherent states, they are thus ideal systems for the study of the transition form quantum to classical behavior, and, in particular, the emergence of chaotic behaviors. The corresponding quantum many-body problem (with binary contact interactions) can be treated by decomposing the matter-wave field ψ in a macroscopic part describing a single particle wave function ψ(x, t), called "condensed fraction", plus a fluctuating quantum field corresponding to the excitations of the matter-wave field. The wave function ψ(x, t) obeys the well-known Gross-Pitaevskii equation (GPE), which includes a nonlinear term [3][START_REF] Cohen-Tannoudji | Advances In Atomic Physics: An Overview[END_REF][START_REF] Pethick | Bose-Einstein Condensation in Dilute Gases[END_REF] :

i ∂ψ(x, t) ∂t = H 1 + gN |ψ(x, t)| 2 ψ(x, t), (1)
where g is the nonlinear parameter proportional to the swave scattering length, N is the number of particles and H 1 is the one-particle Hamiltonian. The nonlinear term models the "mean effect" of particle-particle interactions, and is simply proportional to the spatial probability density |ψ(x, t)| 2 [START_REF]The form (1) of the GPE corresponds to the normalization choice[END_REF]. Replacing the many-body operator ψ by a single-particle wave function ψ which leads to the effective equation (1) implies neglecting quantum fluctuation, but preserves the long-range order supposed to be an essential property of condensates. It turns out that in a large variety of interesting situations this rather rough approach gives a very good description of the condensate dynamics [3]. It can nevertheless be surprising that a linear exact problem can be accurately modeled by a nonlinear effective equation which may present a qualitatively different dynamics (e.g. sensitivity to initial conditions and chaos). The mean-field approximation hides the "microscopic" origin of the nonlinearity, and one is left with a situation similar to that encountered in statistical physics : The macroscopic dynamics of a gas can present qualitatively different characteristics (e.g. irreversibility) from the microscopic dynamics of individual molecules (which is reversible). The averaging over the microscopic dynamics leads to a loss of symmetry and to a qualitatively different behavior in the macroscopic scale. One can speculate that the nonlinear behavior of a condensate arises in an analog way : Averaging over the microscopic (quantum) dynamics produces a qualitatively different behavior. A particularly spectacular manifestation of this is the "quasiclassical" chaos that can appear in the dynamics of a condensate [START_REF] Thommen | [END_REF][7][8][9][10], that is, chaos related to sensitivity to initial conditions. In the present work, we will use a simple model displaying quasiclassical chaos in the mean-field approximation and will compare it to the solutions of the many-body problem. By adequately choosing the representation of the dynamics we will show that one can observe "traces" of the quasiclassical chaos in the behavior of the many-body system even with a limited number of atoms.

II. THE MODEL

The toy model used here consists in a ultracold boson gas placed in an accelerated (or tilted) optical potential [11,12] corresponding to the single-particle Hamiltonian

H 1 = - 1 π 2 ∂ 2 ∂x 2 + V 0 cos(2πx) + F x (2)
where we used normalized units [START_REF] Thommen | [END_REF] such that the lattice constant of the periodic part of the potential is 1, energies are measured in units of the so-called recoil energy

( ω r = 2 k 2 L /2M , with k L = π/d
where d is the lattice constant of the periodic part of the potential and M is the mass of the atoms) and we have set = 1. In presence of interactions, a nonlinear term g |ψ(x, t)| 2 is added to the above Hamiltonian leading to Eq. (1). We confine the dynamics to three adjacent sites s = -1, 0, 1 placed at x = -1, 0, 1 with Dirichlet boundary conditions [27] and restrict the dynamics to the lowest band of the system ; one can then write the solution of Eq. (2) in the form ψ(x, t) = c -1 e iF t w(x+1)+c 0 w(x)+c 1 e -iF t w(x-1) (3) where w(x) is the Wannier-Stark function [eigenstate of (2)] of the fundamental ladder [START_REF]As long as gN ´w4 (x)dx ≪ V0 the coupling to higher ladders is negligible[END_REF] associated to the x = 0 site [13]. In the case g = 0 , we keep the above form, but we let the coefficients c s depend on time. Then, inserting Eq. (3) in Eq. (1) one obtains a set of coupled differential equations that can be integrated numerically :

i ċs = F sc s + U N |c s | 2 c s + J ± N 2|c s | 2 c s±1 + |c s∓1 | 2 c s∓1 + c * s±1 c 2 s ( 4
)
with c -2 = c 2 = 0. The first term is simply the energy of site s, the second term [with U = g ´dxw 4 (x)] accounts for interactions of particles at the same site, and the two last terms correspond to the exchange of particles between neighbor sites, with [29]

J + =g ˆdxw 3 (x)w(x + 1) J -=g ˆdxw(x)w 3 (x + 1). (5)
It is useful to write the wave function components as amplitude-phase variables, defined by c s = √ I s e iθs . The dynamics of such system has been studied in previous works [START_REF] Thommen | [END_REF]8,14,15], where it was in particular showed that quasiclassical chaos in the above system has the structure prescribed by the Kolmogorov-Arnold-Moser theorem, which becomes apparent in a Poincaré section of the dynamics, Fig. 1a. We represented in Fig. 1b the same dynamics described in terms of the spectral entropy S. Given a dynamical function f (t ∈ [0, t max ]) (e.g. the average position x (t)), the spectral entropy is related to the power spectrum

F (ν) of f (t) by S = - 1 ln n ν ν F (ν) ln F (ν),
where n ν = 1 + t max /δt is the number of frequency components of f (t) (with δt the corresponding resolution). Roughly speaking, the spectral entropy gives the number of significant frequency components present in the spectrum, and is thus a good indicator of (quasi)classical chaos. The aim of the present work, is to understand how the (linear) dynamics of the exact many-body problem can approach the (quasiclassical) chaotic behavior observed in Fig. 1.

III. NUMERICAL APPROACHES

The exact many-body problem can be described by the Bose-Hubbard Hamiltonian [START_REF] Cohen-Tannoudji | Advances In Atomic Physics: An Overview[END_REF]16,[START_REF] Meystre | Atom Optics[END_REF]. The singleparticle Hamiltonian corresponds to Eq. ( 2), whereas binary atom-atom contact interactions arise from a term (g/2) ´dx ψ † (x) ψ † (x) ψ(x) ψ(x) where ψ(x) is the matterwave field, which is expanded in the Wannier-Stark basis ψ = s w(x -s)a s where a s is the boson annihilation operator for the site s. This leads to a Bose-Hubbard Hamiltonian

H BH = s F sn s + U 2 n s (n s -1) + J + a † s a s+1 n s + J -a † s a s-1 n s + h.c. (6)
where n s = a † s a s is the number operator for site s. Note that the two "kinetic energy" terms on the second line are different from those of the usual Bose-Hubbard Hamiltonian as, contrary to Wannier functions of a periodic potential, Wannier-Stark functions are eigenstates of the one-particle Hamiltonian Eq. ( 2). Transport here is due to interactions between neighbor sites, not to tunnel effect, and is thus proportional to the interaction strength g [cf. Eq. ( 5)]. One can convince oneself that the Bose-Hubbard Hamiltonian describes the many-body Wannier-Stark problem by noticing that the mean-field approximation which consists in replacing the operators a s by c-numbers c s leads to a classical Hamiltonian whose equations of motions correspond to the GPE, Eq.( 4). In the following, we will compare the solution of the manybody Schrödinger equation

i ∂|ψ BH ∂t = H BH |ψ BH , (7)
to the solution of Eq. ( 4). It is challenging to directly diagonalize Eq. ( 6) which is of dimension (N +1)(N +2)/2 ∼ N 2 for atom numbers N larger than a few tens, so we used the so-called "Lanczos diagonalization" (LD) [START_REF] Lanczos | [END_REF][START_REF] Manmana | AIP Conf. Proc[END_REF][START_REF] Carleo | [END_REF], which consists in using a truncated many-body evolution operator over a short time interval dt :

U (dt) = n K n=0 (-iH BH dt) n n! . (8)
In the Lanczos scheme, in order to evolve the wave function |ψ BH (t) during dt one first builds an orthonormal basis |l 1 , .., |l n K of the subspace spanned by n K "Krylov vectors" defined as

|ψ BH (t) , H|ψ BH (t) , H 2 |ψ BH (t) , .., H n K |ψ BH (t) .
The resulting tridiagonal Hamiltonian of dimension n K ∼ 10 -20 ≪ N 2 can be then diagonalized to obtain the Lanczos eigenvectors |ν 1 , .., |ν n K and eigenvalues α 1 , .., α n K . The propagation of the wave function is then approximated as : As the error in this approximation can be controlled by adjusting the time step dt, the Lanczos procedure is considered as an "exact diagonalization" technique. Each time step implies the diagonalization of a n K × n K matrix thus the method is only interesting if n K ≪ N 2 . The Lanczos procedure allows us to treat the many-body problem with atom numbers N 500 in reasonable computer times.

|ψ BH (t + dt) = n K i=1 ν i |ψ BH (t) e -iαidt |ν i . I 0 -I 1 (a)
Describing the system by a set of complex numbers c s instead of quantum operators a s , the GPE potentially neglects two important effects : (i) quantum noise, i.e the quantum fluctuations around the expectation value of a s (ii) quantum interferences, the fact that two different trajectories can interfere [30]. The truncated Husimi method (THM) allows one to reinsert quantum noise in a GPE description by propagating independently sets of initial conditions whose distribution reflects the quantum noise. However, the THM neglects quantum interference effects that may occur between the different trajectories and is thus an intermediary approach between the GPE and the exact solution of the many-body system particularly suited to identify the role of the quantum noise [10,21,22]. One thus needs to choose a rule relating the complex variables {c ′ s } serving as initials conditions to the GPE to the many-body problem, i.e to choose a family of manybody states able to connect a many-body state |Ω ({c s }) and the corresponding set of GPE initial conditions {c ′ s }. With M sites (M = 3 in this work), one can choose the so-called SU (M ) coherent states [23] with finite total number of atoms N , which are defined, in the Fock basis, as

|Ω ({c s }) = √ N ! n1+..+n M =N s c ns s √ n s ! |n 1 , .., n s with s |c s | 2 = 1.
The advantage of SU (M ) states, as compared to the usual Glauber coherent states, is that the total number of atoms N is fixed :

N -N 2 =
0, with N = s n s , which is a situation closer to the that encountered in a real experiment. We then need to choose a quantity to characterize the quantum noise in the system. In this work we use the Husimi function Q Ω which, given a coherent state |Ω ({c s }) , is simply defined as its projection over all possible states :

Q Ω ({c ′ s }) = | Ω ′ ({c ′ s })| Ω ({c s }) | 2 .
The width of this function decreases as N -1/2 and thus gives a good representation of the quantum noise. For a given initial manybody state |Ω {c s } , we generate the corresponding distribution of one-particle initial conditions D (c s ) ≡ {c ′ s } which mimics the Husimi representation of the |Ω {c s } . Each of these states is then propagated independently according to the GPE and observables are obtained by averaging over the distribution of final states. For large enough N , the width of the Husimi distribution tends to 0 and one recovers the results of the GPE. Hence, the THM allows one to use the GPE to simulate the evolution of not so large number of atoms (including quantum noise but not interference effects), and it turns out to be a convenient tool to study of the emergence of chaos in our system as the number of atoms increases.

IV. EMERGENCE OF QUASICLASSICAL CHAOS

We compare in Fig. 2 the time evolution of the system -represented here by the average position of the wave packet -calculated according to the different methods described in sec. III, for a small N = 30 [plot (a)] and a larger (but not large) N = 500 [plot (b)] number of atoms. In order to have a pertinent comparison with the GPE, gN is the same for all simulations. The GPE calculation displays a clear irregular behavior associated to the presence of quasiclassical chaos. No such behavior is observed for N = 30 atoms either with the LD or the THM. In plot (b), with N = 500, one sees that the GPE result "sticks" to the many-body calculations for times t 150, and that the many-body calculations even display the first oscillations observed in the GPE evolution.

In order to observe the emergence of quasiclassical chaos as the number of particles increases, we calculated the spectral entropy for a complete set of initial SU (3) states using both LD and THM. The width of the Husimi function corresponding to a given initial condition is determined, and we assume that for any initial condition {c s }, the Husimi function can be approximated by a square distribution with same width centered around {c s }. We checked numerically that this approximation has no impact on our results. Figure 3 compares the distribution of the spectral entropy computed by LD and by the THM for N = 30 and N = 400 atoms, and shows that not only the results become more similar when the atom number increases, but also that the characteristic features observed in the quasiclassical Poincaré section Fig. 1a tend to emerge (this trend is confirmed for intermediate atom numbers). These results show that THM provides a good representation of the exact many-body behavior for large atom numbers and can advantageously used for comparisons with the quasiclassical behavior.

In figure 4 we present a calculation of the variance of the wave packet position -which is an indication of the erratic character of the dynamics, that is quasiclassical chaos -by the three methods and for N = 30 (top row) and N = 400 (bottom row). The GPE picture (first column) is obviously independent of the atom number (provided gN is constant). Both LD (center column) and THM (right column) instead show a clear dependence in N and are rather different, both in shape as in the amplitude, from the GPE result, which shows that quasiclassical chaos is not fully developed for such atom numbers. However, one can see however that the higher the number of atoms the closer the result is from the one obtained with GPE. The amplitude of the variances increases by a factor 2 for THM and by a factor 3.8 for the LD when the number of atoms is changed from 30 to 400, and the surface of the chaotic zones (in yellow and red) also increases significantly. Thus, even if the atom numbers considered here are clearly too small to allow a definite conclusion, one can reasonably expect a much better convergence with the GPE for larger values of N .

V. CONCLUSION

In conclusion, we showed that the dynamics exhibited by the many-body problem as described by both exact diagonalization and the truncated Husimi method tends to converge to the quasiclassical chaos displayed by the mean-field approximation as the atom number increases. Our result suggests the existence of a "nonlinear characteristic time" increasing with some (monotonous) function of N , during which the prediction of the mean-field ap- proximation and of the exact many-body problem agree. One may conjecture that this time is related to the typical time for particle number fluctuations to affect significantly the dynamics, but we are presently unable to give a verifiable estimation of such time. In particular, THM appears to approach very well the exact dynamics, which suggests that the essential effect leading to the emergence of quasiclassical chaos as the number of particles increases is the reduction of quantum noise. It would be interesting to analyze the influence of quantum interferences and diffusion as done e.g. by Carvalho et al. [24], who compared the phase space structure of the classical chaotic one-body delta-kicked harmonic oscillator to the Wigner representation of its quantum counterpart, and showed that both decoherence and classical diffusion lead to a similarity of the two representations. Weiss and Teichmann [25], using a many-body system (with N = 1000) slightly different from ours, attributed the observed differences between the mean-field and the many-body dynamics to the existence of entanglement in the many-body problem, and showed that these differences are reduced if decoherence is added to the system. The present work sheds a different light on the problem of the quantum-classical transition in a system displaying quasiclassical chaos, suggesting the quantum noise is the main cause of the differences. In order to reach more definitive conclusions, however, simulations of the many-body problem with atom numbers larger by (at least) one order of magnitude would be necessary. This is a fascinating yet challenging goal for future work.

1 Figure 1 :

 11 Figure 1: Quasiclassical chaos in a tilted lattice, obtained by integrating the Gross-Pitaevskii equation (4). (a) Poincaré section corresponding to I-1 = 0.1, θ0 -θ-1 = 0. (b) Spectral entropy calculated between t = 0 and t = 800. Parameters are V0 = 5, F = 0.25, gN = 0.2.

1 xFigure 2 :

 12 Figure 2: Evolution of the average position of a wave packet calculated with different methods : Gross-Pitaevskii equation (cyan), Lanczos diagonalization (green), and the truncated Husimi method (red), for (a) N = 30 and (b) N = 500. In panel (a), we also represented by blue circles the result obtained by direct diagonalization of the full many-body problem, which is in perfect agreement with the result of the Lanczos method, illustrating the accuracy of the later. The initial state is a SU (3) coherent state with c-1 = √ 0.5, c0 = √ 0.25 and c1 = i √ 0.25. Other parameters are gN = 0.2, V0 = 7, F = 0.1.

1 Figure 3 :

 13 Figure 3: Spectral entropy distribution in phase space obtained by LD (left column) and by THM (right column) with N = 30 (top row) N = 400 (bottom row) and same parameters as Fig. 1. When N increases, the THM provides a quite good representation of the mean-field behavior for large N , and the phase-space structure of the many-body problem becomes similar to the Poincaré section obtained from the GPE, plot (a) of Fig. 1.

1 Figure 4 :

 14 Figure 4: Variance of the wave packet position calculated between t = 0 and t = 800 from the GPE (left column), LD (center column), and THM (right column) with N = 30 (top row) and N = 400 (bottom row) and the same parameters as Fig. 1.

Acknowledgments

Laboratoire de Physique des Lasers, Atomes et Molécules is UMR 8523 of CNRS. Work partially supported by Agence Nationale de la Recherche (grants LAKRIDI ANR-11-BS04-0003,2 K-BEC ANR-13-BS04-0001-01) and the Labex CEMPI (ANR-11-LABX-0007-01). JCG thanks the Max-Planck Institute for the Physics of Complex Systems, Dresden, for support in the framework of the Advanced Study Group on Optical Rare Events.


Othmane Alaoui-Fdili

Patrick Corlay

Youssef Fakhri

Franc ¸ois-Xavier Coudoux

Driss Aboutajdine

A Cross-Layer Approach for Video Delivery over Wireless Video Sensor Networks

In this paper, we propose a novel cross-layer approach for video delivery over Wireless Video Sensor Networks (WVSN)s. We adopt an energy efficient and adaptive video compression scheme dedicated to the WVSNs, based on the H.264/AVC video compression standard. The encoder operates using two modes. In the first mode, the nodes capture the scene following a low frame rate. When an event is detected, the encoder switches to the second mode with a higher frame rate and outputs two different types of macroblocks, referring to the region of interest and the background respectively. Furthermore, we propose an Energy and Queue Buffer Size Aware MMSPEEDbased protocol for reliably and energy efficiently routing both regions towards the destination. Simulations results prove that the proposed approach is energy efficient and delivers good quality video streams. In addition, the proposed routing protocol EQBSA-MMSPEED outperforms its predecessors, the QBSA-MMSPEED and the MMSPEED, providing 33% of lifetime extension and 3 dBs of video quality enhancement.

I. INTRODUCTION

With the recent advances in image and video processing, wireless sensor nodes are doted of new capabilities that enable them the capture and the processing of visual information. Networks of such interconnected devices are called Wireless Video Sensor Networks (WVSN)s. They are actually investigated for various monitoring applications, for indoor and outdoor environments [START_REF] Liu | A survey on wireless camera sensor networks[END_REF]. In the WVSN, the video nodes collaborate in order to deliver visual information about an area on interest, to a destination called the sink, via multihops short range transmissions. The nodes operate with respect to the available and limited resources. In fact, these units are battery powered. The management of this component is therefore a crucial issue in the Wireless Sensor Network (WSN) context in general, and in the WVSN context in particular. In brief, the energy consumption has to be efficiently managed in all of the protocol stack's layers.

In the WVSNs, the video nodes compress the video streams prior to the transmission. Several works have been conducted in order to propose video compression schemes adapted to the WVSNs. In some works [START_REF] Politis | Power efficient video multipath transmission over wireless multimedia sensor networks[END_REF]- [START_REF] Zhang | Cross-layer optimization for video streaming over wireless multimedia sensor networks[END_REF], the authors use a video compression standard as is and try to enhance the energy consumption in lower layers. While others [START_REF] Aghdasi | An energyefficient and high-quality video transmission architecture in wireless video-based sensor networks[END_REF]- [START_REF] Bambang | Energy efficient multiple description coding for video sensor network[END_REF] prefer to slightly modify the standard to make it more appropriate to the video nodes.

In [START_REF] Alaoui-Fdili | Energy efficient adaptive video compression scheme for WVSNs[END_REF], we adopt the second choice and propose an energy efficient and adaptive video compression scheme dedicated to the WVSNs. Actually this scheme relies on the H.264/AVC video compression standard [START_REF] Richardson | H.264 and MPEG-4 video compression[END_REF] in its intra-only mode. In addition it outputs two macroblocks categories depending on which region each one belongs, namely the Region Of Interest (ROI) or the Background (BKGD). This is done to introduce the differentiated service paradigm that is strongly recommended for WVSN. The simulations results have proven the energy efficiency of the proposed scheme.

Consequently, for efficiently transferring the output streams, the underlying routing protocol has to be able to manage and serve different classes of packets at the same time. The authors in [START_REF] Felemban | MMSPEED: Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks[END_REF] propose a Multipath Multi-SPEED protocol (MMSPEED) that is able to handle multiple traffic classes. Actually, it considers two quality domains, namely the timeliness and the reliability. In the first one, MMSPEED tries to maintain a given packet's Progression Speed (PS) across the network in order to meet the desired delay. Thereafter, to offer a Desired Reliability (DR), a Total Reaching Probability (TRP) is computed by injecting the Reaching Probability (RP) of each of the candidate nodes until the TRP reaches the DR.

In [START_REF] Alaoui-Fdili | Impact of queue buffer size awareness on single and multi service real-time routing protocols for WSNs[END_REF], we investigate the MMSPEED protocol and show the gain that can be observed in timeliness and reliability domains when considering the Available Buffer Size (ABS) in the node's queue during the routing process. In fact, taking into account the ABS of neighbour nodes handles the congestion and leads to a decrease of the packets' experienced delay as well as the ratio of the dropped packets. Nevertheless, there is still a need to the consideration of the energy during the routing process.

Therefore, in this paper, we first present a cross-layer approach for video delivery over WVSNs based on the video compression scheme presented in [START_REF] Alaoui-Fdili | Energy efficient adaptive video compression scheme for WVSNs[END_REF] and the routing protocol presented in [START_REF] Alaoui-Fdili | Impact of queue buffer size awareness on single and multi service real-time routing protocols for WSNs[END_REF]. Then, we propose an Energy and Queue Buffer Size Aware MMSPEED (EQBSA-MMSPEED) protocol that introduces the residual energy as new routing metric in order to decrease the energy consumption and hence extending the network lifetime. In addition, EQBSA-MMSPEED proposes a way to enhance the packet delivery ratio, called the Last Chance Procedure (LCP).

The rest of this paper is organized as follows. In section II the main contributions of this paper are in detail explained. Section III, presents and discusses the simulations results in terms of energy consumption, delay, reliability and received video quality. Finally, section IV concludes the paper.

II. PROPOSED APPROACH

In this Section we present in detail the proposed approach which is based on an energy efficient video compression scheme and an Energy and Queue Buffer Size Aware routing protocol.

A. Energy Efficient Adaptive Video Compression Scheme

As shown on Fig. 1 , the video compression scheme operates using two modes: the Standby and the Rush modes. In the first mode, the nodes capture the scene following a low Frame Rate (FR) to preserve their energies. Then, they compress the video signal with a given Quantization parameter (QP). In addition, they use the intra-only mode that has proven its efficiency and suitability to the WVSN context. In fact, the authors in [START_REF] Al | Quality and complexity comparison of H.264 intra mode with JPEG2000 and JPEG[END_REF] propose a comparative study concerning the H.264/AVC intra mode against JPEG and JPEG2000. They conclude that the H.264/AVC intra mode offers an interesting compromise in terms of complexity, quality and coding efficiency. When an event occurs, the concerned nodes switch to the Rush mode. First, they adopt a higher frame rate to report the event. Then, the Flexible Macroblock Ordering (FMO) tool is used to produce two service differentiated streams corresponding to the ROI and the BKGD. Moreover, the nodes keep the same QP and apply a Frequency Selectivity (FS) bit rate adaptation in order to decrease the energy consumed for the transmission. Actually it consists on keeping a number of the coefficients, FP, after the transform operation. Note that the FS is a logical operation that doesn't add any complexity to the encoder, unlike the case when a requantization is used. Finally, the residual coefficients are entropy coded by the Context-Adaptive Variable-Length Coding (CAVLC) that can approach the entropy of the source with a reduced complexity, compared to the Context-Based Adaptive Binary Arithmetic Coding (CABAC).

B. Energy and Queue Buffer Size Aware MMSPEED Routing Protocol (EQBSA-MMSPEED)

Now that the video streams are encoded in two different categories, we need to transfer them to the sink. For this purpose, a service differentiated routing protocol is needed to serve each flow according to its traffic class (ROI or BKGD). In addition, this routing protocol has to consider the compulsory energy constraint, especially when dealing with energy consuming streams.

First of all, let us mathematically define some terms that will be used. The first one is the Forwarding Set (FS), regrouping the nodes that are in the communication range and closer to the destination D than the current node i, and it is formulated as follows:

F S i (D) = {j ∈ N S i /dist(i, D) -dist(j, D) > 0} (1)
where dist(i, D) and dist(j, D) are the Euclidean distances between i and D, j and D respectively, and N S i is the neighbourhood set that contains the one-hop reachable neighbours. The Progression Speed (PS) of a packet towards the destination D, if the node i forwards it to the node j is given as follows [START_REF] Felemban | MMSPEED: Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks[END_REF] :

Speed ij (D) = dist(i, D) -dist(j, D) Delay ij (2)
The Reaching Probability (RP) of a packet to the destination D, if the node i forwards it to the node j is given by [START_REF] Felemban | MMSPEED: Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks[END_REF]:

RP D ij = (1 -e ij )(1 -e ij ) [ dist(j,D) dist(i,j) ] (3)
where e ij corresponds to the rate of lost packets sent to j.

Then, the Total Reaching Probability (TRP) is given by [START_REF] Felemban | MMSPEED: Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks[END_REF]:

T RP N ew = 1 -(1 -T RP Old )(1 -RP D ij ) (4)
In order to consider the energy consumption during the routing process, we propose to inject the information about the residual energy in the delay packets that are periodically broadcasted by each node in its neighbourhood. Thus, the delay beacon in the proposed EQBSA-MMSPEED protocol has the following structure, reported by Fig 2. Consequently, when a node receives a delay packet, it updates the different fields of its neighbouring table that now contains the field of the remaining energy (see Fig. 3).

Fig. 3. Neighbour Table in EQBSA-MMSPEED

When a node receives a data packet of traffic class l to be routed, the node processes it as follows. The proposed EQBSA-MMSPEED protocol starts by constructing the FS, then the subsets F S high and F S low that contains respectively the nodes with PS higher and lower than the requested one. Afterwards, a score is assigned to each of the nodes of the F S high subset. Actually, in the EQBSA-MMSPEED protocol, this score is based on three metrics: the Residual Energy (RE), the Available Buffer Size (ABS) and the RP. The calculation of a neighbour node j's score is given by:

score(j) = α×RP D ij +β×ABS l (j)+(1-α-β)×RE(j) (5)
where α and β are weighting coefficients to be fixed, and ABS l is the information about the available buffer space in node j's queue at level l. Once the nodes are sorted according to the calculated scores, they are presented to the equation 4 one by one until the TRP reaches the DR for the packet's traffic class. When the node fails to find forwarding nodes belonging to F S high , MMSPEED protocol probabilistically drops the packet or forwards it to the best node in the F S low in terms of the PS. Therefore, in the proposed EQBSA-MMSPEED protocol, a new procedure called the Last Chance Procedure (LCP), is introduced. The purpose of this procedure is doing more network lifetime extension and achieving proper reliability even in such cases. The LCP consists in first dividing the subset F S low in two subsets, namely F S LC low and F S Rescue low . Formally, F S LC low can be defined as follows:

F S LC low = {j ∈ F S low /P S(j) ≥ P S avg } (6)
Hence, the F S LC low contains the nodes of the F S low that are able to offer a packet's PS higher than the average PS in F S low . Otherwise, the node belongs to F S Rescue low . Subsequently, the nodes of F S LC low are sorted according to their scores, calculated by the equation 5. Then, they are injected in the equation 4 until the TRP reaches the DR for the packet's traffic class. Finally, in case the presented nodes are not sufficient to meet the DR, the best nodes in terms of reliability in F S Rescue low are selected one by one. In summary, the proposed EQBSA-MMSPEED protocol compared to its predecessors, is able to (1) meet the required deadlines since the nodes are chosen -when possible-from the F S high , (2) to extend the network lifetime by taking into account the residual energy of the nodes and (3) tries to offer an acceptable packet delivery ratio as much as possible thanks to the LCP.

III. SIMULATIONS RESULTS

In order to validate the proposed approach, we conducted several simulations using the JSIM [START_REF] Sobeih | J-Sim: a simulation and emulation environment for wireless sensor networks[END_REF] simulator. We considered 100 nodes uniformly deployed in an area of interest where 50% of them are video nodes. First, the nodes starts exchanging control packets for a given duration XD. Then the video nodes start the Standby mode, capturing the scene following a low FR, F R SM , and compress it using a given QP . Each frame is then subdivided into a number of packets to be routed towards the sink according to a given packet rate, P R SM . At the event time, the node that has detected it switches to the Rush mode following a higher FR , F R RM . Each of the macroblocks of the captured frames is categorized as belonging to ROI or BKGD thanks to the FMO option. The BKGD component is then bit rate adapted using the FS of parameter F P . Afterwards, the ROI and the BKGD are encapsulated into packets to be routed towards the sink according to a packet rate, P R RM , with suitable reliability and delay constraints.

For reliable evaluation, the source nodes are randomly designated in each realisation. We evaluate the performances of the proposed approach during the video transmission until the last deliverable packet reaches the sink. Table I Fig. 4 shows the average number of alive nodes during the video transmission over 50 realisations. We compare here three routing protocols: MMSPEED [START_REF] Felemban | MMSPEED: Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks[END_REF], QBSA-MMSPEED [START_REF] Alaoui-Fdili | Impact of queue buffer size awareness on single and multi service real-time routing protocols for WSNs[END_REF] and the proposed EQBSA-MMSPEED. As can be seen, the proposed protocol extends the network lifetime of about 33%. 5 reports the results in the timeliness domain during the Rush mode. One can observe that the three protocols treat the ROI and the BKGD differently. In addition, we observe the slight enhancement in the delays that is achieved by the EQBSA-MMSPEED. This can be explained by the introduced load balance thanks to the consideration of the residual energy. Hence, nodes with appropriate delay and ABS are not always selected to not lead them to the state of congestion, thus having less packets to be processed. 6 depicts the packet delivery ratio during the Rush mode. We can observe that the proposed EQBSA-MMSPEED Fig. 6. Packet delivery ratio during the Rush mode achieves interesting performances; this is due to four main reasons. The first one is, as said before, introducing new metric enables more load balancing. The second one is, even in worst cases, packet drop is avoided as much as possible while considering the energy consumption, thanks to the LCP. The third one is related to the fact that ignoring the remaining energy, in MMSPEED and QBSA-MMSPEED protocols, leads to a sort of acceleration in nodes' death. This fact creates holes specially in regions that are next to the destination, and this last becomes isolated. Consequently this leads to not receiving the packets at the sink. The last one is that the source nodes play also the role of forwarding nodes of others nodes' packets. Not considering their remaining energies accelerate their death as well, leading to their inability to send the whole video stream. Note that, at the reception, a simple spatial error concealment procedure is applied to the received streams which exploits the inherent temporal correlation feature of the video signals. The proposed EQBSA-MMSPEED protocol allows the achievement of an average overall video quality enhancement of 3 dBs against MMSPEED and QBSA-MMSPEED.

IV. CONCLUSION

In this paper, a cross-layer approach for video delivery in the WVSNs is proposed. The approach relies on a energy efficient and adaptive video compression scheme that has proven its efficiency in both video quality and energy domains. The scheme is based on the H.264/AVC standard and uses simple techniques in order to be energy efficient. Finally, it outputs two macroblock categories namely the region of interest and the background. These lasts are handled by an Energy and Queue Buffer Size Aware MMSPEED protocol that is able to offer differentiated service with the consideration of the available space in the queue buffer size of adjacent nodes, their remaining energy as well as their reliability. The proposed protocol achieves 33% of lifetime extension and 3 dBs of video quality enhancement.

Fig. 1 .

 1 Fig. 1. Block diagram of the proposed scheme

Fig. 2 .

 2 Fig. 2. Delay beacon structure in EQBSA-MMSPEED

Fig. 4 .

 4 Fig. 4. Number of alive nodes at runtime Fig.5reports the results in the timeliness domain during the Rush mode. One can observe that the three protocols treat the ROI and the BKGD differently. In addition, we observe the slight enhancement in the delays that is achieved by the EQBSA-MMSPEED. This can be explained by the introduced load balance thanks to the consideration of the residual energy. Hence, nodes with appropriate delay and ABS are not always selected to not lead them to the state of congestion, thus having less packets to be processed.

Fig. 5 .

 5 Fig. 5. Delays during the Rush mode

Fig. 7 .

 7 Fig. 7. PSNR values of the displayed stream

  reports the used simulations parameters.