Xavier Corbillon
email: xavier.corbillon@imt-atlantique.fr

Alisa Devlic
email: alisa.devlic@huawei.com

Gwendal Simon
email: gwendal.simon@imt-atlantique.fr

Jacob Chakareski

Optimal Set of 360-Degree Videos for Viewport-Adaptive Streaming

Keywords: Omnidirectional Video, Quality Emphasized Region, Viewport Adaptive Streaming

With the decreasing price of Head-Mounted Displays (HMDs), 360-degree videos are becoming popular. The streaming of such videos through the Internet with state of the art streaming architectures requires, to provide high immersion feeling, much more bandwidth than the median user's access bandwidth. To decrease the need for bandwidth consumption while providing high immersion to users, scientists and specialists proposed to prepare and encode 360-degree videos into quality-variable video versions and to implement viewport-adaptive streaming. Quality-variable versions are different versions of the same video with non-uniformly spread quality: there exists some so-called Quality Emphasized Regions (QERs). With viewport-adaptive streaming the client, based on head movement prediction, downloads the video version with the high quality region closer to where the user will watch. In this paper we propose a generic theoretical model to find out the optimal set of quality-variable video versions based on traces of head positions of users watching a 360-degree video. We propose extensions to adapt the model to popular quality-variable version implementations such as tiling and offset projection. We then solve a simplified version of the model with two quality levels and restricted shapes for the QERs. With this simplified model, we show that an optimal set of four quality-variable video versions prepared by a streaming server, together with a perfect head movement prediction, allow for 45% bandwidth savings to display video with the same average quality as state of the art solutions or allows an increase of 102% of the displayed quality for the same bandwidth budget.

INTRODUCTION

Offering high-quality virtual reality immersion by streaming 360degree videos on the Internet is a challenge. The main problem is that most of the video signal information that is delivered is not displayed. Indeed, the Head-Mounted Displays (HMDs) that are used for immersion show a viewport, which represents a small fraction of the whole 360-degree video. Typically, to extract a 4K (3840 × 2160 pixels) video viewport from the whole 360-degree video, the stream should be at least a 12K (11520 × 6480 pixels) video, from which most information is ignored by the video player.

A solution researchers are exploring to limit the waste of bandwidth is to prepare and stream 360-degree videos such that their quality is not homogeneous spatially [START_REF] Corbillon | Viewport-adaptive navigable 360-degree video delivery[END_REF][START_REF] Hosseini | Adaptive 360 VR video streaming based on MPEG-DASH SRD[END_REF][START_REF] Niamut | MPEG DASH SRD: spatial relationship description[END_REF][START_REF] Sreedhar | Viewportadaptive encoding and streaming of 360-degree video for virtual reality applications[END_REF]. Instead the quality is better at the expected viewport positions than in the rest of the video frame. Two main concepts that support this solution are (i) encoding of quality-variable videos, which can be based on tiling [START_REF] Zare | Hevc-compliant tilebased streaming of panoramic video for virtual reality applications[END_REF], scalable coding [START_REF] Boyce | Overview of SHVC: scalable extensions of the high efficiency video coding standard[END_REF][START_REF] Youvalari | Efficient coding of 360-degree pseudo-cylindrical panoramic video for virtual reality applications[END_REF], and offset projections [START_REF] Zhou | A measurement study of oculus 360 degree video streaming[END_REF]; and (ii) implementation of viewport-adaptive streaming, which is to signal the different quality-variable versions of the video, to predict viewport movements, and to make sure that a given user downloads the quality-variable video such that the quality is maximum at her viewport position.

The design of efficient viewport-adaptive streaming systems requires the understanding of the complex interplay between the most probable viewport positions, the coding efficiency, and the resulting Quality of Experience (QoE) with respect to the traditional constraints of delivery systems such as bandwidth and latency. MPEG experts have proposed the concept of quality region, which is a rectangular region defined on a sphere, characterized by a quality level ranging from 1 to 100. The main idea is that the content provider determines some quality regions based on offline external information (e.g., content analysis and statistics about viewport positions), and then prepares multiple quality-variable versions of the same 360-degree video based on these quality regions.

We provide in this paper a theoretical analysis of this concept of quality regions for 360-degree videos. We present optimization models to determine the optimal quality regions, subject to a population of clients, the number of quality-variable video versions, and the bandwidth. We aim at maximizing the video quality displayed in the client viewports by identifying (i) the location of the quality region, (ii) their dimensions (or area size), and (iii) the quality inside and outside the regions. Our model enables content providers to prepare 360-degree videos based on the analytics of the head movements collected from the first content consumers. Using a dataset of real head movements captured on an HMD, we study an optimal set of video versions that are generated by our algorithms and evaluate the performance of such optimal viewport-adaptive streaming. We demonstrate that, for a given overall bit-rate video, the video quality as perceived by the user improves by 102% on average.

RELATED WORK 2.1 Quality-Variable Videos Implementation

In the literature, we distinguish two approaches to implement quality-variable 360-degree videos. We give a brief introduction to these approaches in the following, while providing more details in Sections 3.2 and 3.3 on how our model applies to these approach.

Tile-based Approach. The motion-constrained tiles are contiguous fractions of the whole frame, which can be encoded/decoded independently and can thus be seen as separated sub-videos. The concept of tiling is part of the High Efficiency Video Coding (HEVC) standardized decoder [START_REF] Misra | An overview of tiles in HEVC[END_REF] and is considered as a key supporting technology for the encoding of quality-variable video versions. The tile-based approach has been developed for other multimedia scenarios where end-users consume only a fraction of the video, especially in navigable panorama [START_REF] Gaddam | Tiling of Panorama Video for Interactive Virtual Cameras: Overheads and Potential Bandwidth Requirement Reduction[END_REF][START_REF] Sánchez | Compressed domain video processing for tile based panoramic streaming using HEVC[END_REF][START_REF] Wang | Mixing Tile Resolutions in Tiled Video: A Perceptual Quality Assessment[END_REF]. This approach has been recently extended to meet the demand of virtual reality and 360-degree video systems. In a short paper, Ochi et al. [START_REF] Ochi | Live streaming system for omnidirectional video[END_REF] have sketched a solution where the spherical video is mapped onto an equirectangular video, which is cut into 8×8 tiles. Zare et al. [START_REF] Zare | Hevc-compliant tilebased streaming of panoramic video for virtual reality applications[END_REF] provide more details on the encoding performance of tilling when applied on projected frames. This study demonstrates the theoretical gains that can be expected by a quality-variable implementation of 360-degree video. More recently, Hosseini and Swaminathan [START_REF] Hosseini | Adaptive 360 VR video streaming based on MPEG-DASH SRD[END_REF] proposed a hexaface sphere-based tiling of a 360-degree video to take into account projection distortion. They also present an approach to describe the tiles with MPEG Dynamic Adaptive Streaming over HTTP (DASH) Spatial Relationship Description (SRD) formatting principles. Quan et al. [START_REF] Quan | Optimizing 360 video delivery over cellular networks[END_REF] also propose the delivery of tiles based on a prediction of the head movements. Their main contribution is to show that the head movements can be accurately predicted for short segment sizes by using standard statistical approaches. Le Feuvre and Concolato [START_REF] Le Feuvre | Tiled-based Adaptive Streaming using MPEG-DASH[END_REF] have demonstrated the combination of HEVC tiling with 360-degree video delivery. Their main contribution is to demonstrate that current technologies enable efficient implementation of the principles of the tile-based approach. Finally, Zare et al. [START_REF] Zare | Hevc-compliant viewport-adaptive streaming of stereoscopic panoramic video[END_REF] show that, by using the extractor design for HEVC files and using constrained inter-view prediction in combination with motion-constrained tiles, it is possible to efficiently compress stereoscopic 360-degree videos while allowing clients to decode the videos simultaneously with multiple decoding instances.

Projection-Based Approach. This approach, which has been proposed by Kuzyakov [14] and is currently implemented in practical systems [START_REF] Zhou | A measurement study of oculus 360 degree video streaming[END_REF], takes profit from the geometrical projection. Indeed, since state-of-the-art video encoding are based on two-dimensional rectangles, any 360-degree video (captured on the surface of a sphere) needs to be projected onto a two-dimensional video before encoding. Scientists have been studying spherical projection onto maps for centuries. The most common projections are equirectangular, cube map, and pyramid [START_REF] Corbillon | Viewport-adaptive navigable 360-degree video delivery[END_REF][START_REF] Yu | A Framework to Evaluate Omnidirectional Video Coding Schemes[END_REF]. The main idea introduced by Kuzyakov [START_REF] Kuzyakov | End-to-end optimizations for dynamic streaming[END_REF] is to leverage a feature of the pyramid, projection: the sampling of pixels from the spherical surface to the two-dimensional surface is irregular, which means that some parts of the spherical surface get more distortion after the projection than others. Depending on the position of the base face of the pyramid, the projection, and consequently the video encoding, is better for some parts of the spherical surface. A refined approach based on geometrical projections is the offset projection [START_REF] Zhou | A measurement study of oculus 360 degree video streaming[END_REF], where a constant directed vector is applied during the projection to change the pixel sampling in the sphere domain while keeping the same pixel sampling (resolution) in the projected domain. It results in a better quality encoding near the "offset direction" and a continuously decreasing qualities for viewports far from this direction.

Viewport-Adaptive Streaming

Several researchers have concomitantly studied solutions to stream 360-degree videos based on the same principle as in rate-adaptive streaming [START_REF] Concolato | Adaptive streaming of hevc tiled videos using mpeg-dash[END_REF][START_REF] Corbillon | Viewport-adaptive navigable 360-degree video delivery[END_REF][START_REF] Kuzyakov | Next-generation video encoding techniques for 360 video and vr. Blogpost[END_REF][START_REF] Le Feuvre | Tiled-based Adaptive Streaming using MPEG-DASH[END_REF][START_REF] Quan | Optimizing 360 video delivery over cellular networks[END_REF]. A server splits the video into different segments which duration typically vary between 1 s to 10 s. Each segment is then encoded into different representations each representation having different size (in byte) and having different quality distribution. A client decides, thanks to an adaptation algorithm using local information and predictions, which video representation (or set of representations) to download, to match the available bandwidth budget and the future position of the user viewport.

Zhou et al. [START_REF] Zhou | A measurement study of oculus 360 degree video streaming[END_REF] studied a practical implementation of viewport-adaptive streaming made for the Occulus HMD, and showed that the occulus' implementation is not efficient: 20% of the bandwidth is wasted to download video segments that are never used. Le Feuvre and Concolato [START_REF] Le Feuvre | Tiled-based Adaptive Streaming using MPEG-DASH[END_REF] and Concolato et al. [START_REF] Concolato | Adaptive streaming of hevc tiled videos using mpeg-dash[END_REF] studied practical implementation of tile-based quality-variable 360-degree videos viewport-adaptive streaming. Corbillon et al. [START_REF] Corbillon | Viewport-adaptive navigable 360-degree video delivery[END_REF] studied an optimal viewport-adaptive streaming selection algorithm based on different heuristically defined quality-variable versions of 360-degree videos. In this paper, we focus on an optimization model to generate quality-variable video versions for viewport-adaptive streaming that maximize the quality inside users' viewports when number of video versions available to the user is limited. To the best of our knowledge, nobody studied before us optimal parameters to generate limited number of quality-variable versions for 360-degree videos.

Regions of Interest

Our work has also some common roots with the literature on Region of Interest (RoI) in video delivery. The human vision system can only extract information at high resolution near the fovea, where the gaze focuses its attention; the vision resolution decreases with eccentricity. Within the same video picture, it is common that most users focus their gaze on some specific regions of the picture, named RoI. Researchers have studied saliency map, which measures the gaze location of multiple users watching the same video. The goal is to extract RoI and, if possible, to corroborate RoI with picture structures to enable automatic RoI prediction [START_REF] Borji | State-of-the-art in visual attention modeling[END_REF][START_REF] Dodge | Visual saliency prediction using a mixture of deep neural networks[END_REF]. However, the concept of saliency map should be revisited with 360-degree videos, because the head movement is the prevailing factor to determine the attention of users. To the best of our knowledge, the relation between gaze-based saliency map and head movements in HMD has not been demonstrated.

The attention-based video coding [START_REF] Boccignone | Bayesian integration of face and low-level cues for foveated video coding[END_REF][START_REF] Itti | Automatic foveation for video compression using a neurobiological model of visual attention[END_REF][START_REF] Lee | Efficient video coding based on audio-visual focus of attention[END_REF]] is a coding strategy, which takes advantage of the gaze saliency prediction. The quantization parameters of the encoder are adjusted to allocate more bits near the different RoI and less bits farther away. A live encoder can perform attention-based video coding by using either feedback from a set of specific users or predicted RoI.

We revisit this approach to 360-degree videos in this paper. Our work is both to study per-segment RoI localization based on head movement information and to generate RoI-based encoded video representations. The creation of spherical quality-variable video versions based on head movement analysis enables viewport-adaptive streaming in the same manner that saliency map and attention-based video coding enable efficient video delivery on regular planar videos [START_REF] Dodge | Visual saliency prediction using a mixture of deep neural networks[END_REF].

QUALITY-VARIABLE VIDEOS

We first introduce a model for quality-variable 360-degree videos and then provide some illustrations of this model on some implementation proposals.

Generic Model

Spherical videos. The unit sphere that underlies the 360-degree video is split into N non-overlapping areas that cover the full sphere. The set of areas is denoted by A. In essence, each area corresponds to the video signal projected on a given direction of the sphere. Let us denote by s a the surface of an area a on the sphere and observe that the smallest possible surface s a is the pixel (in which case the set A is the full signal decomposition and N is the video resolution). However, video preparation processes are generally based on a video decomposition A with larger surface s a , such as the concept of tiles in HEVC [START_REF] Misra | An overview of tiles in HEVC[END_REF]. For the preparation of 360-degree videos, any decomposition of the video into A can be considered if it respects that it covers the whole sphere, formally a ∈A s a = 4π .

Area Quality. The goal of a video encoder is to compress the information of the video signal corresponding to a given area a into a decodable byte-stream (lossy compression generating distortion when the video is eventually played). An encoder uses a compression algorithm with various parameter settings to encode the video. For a given encoder, the more compression due to the encoding settings, the more distortion in the decoded and played video. Using MPEG terminology, we use the generic term quality to express the settings of the encoding scheme on a given area, regardless of the used area encoding process. The number of different ways to encode areas is finite, which results in a set of available qualities Q for this encoder (typically the quality ranges from 1 to 100 in MPEG). The set Q is totally ordered with a transitive comparison function, noted with >.

We provide some natural notations: q min (respectively q max ) is the lowest (respectively highest) possible quality for areas. The encoder processes an area a ∈ A with a quality q to generate a byte-stream of size b a,q . Given the usual strictly increasing feature of the rate-distortion performance of video encoders, we get that if a quality q 1 ∈ Q is better than a quality q 2 ∈ Q (formally q 1 > q 2 ), then we have b a,q 1 > b a,q 2 , ∀a ∈ A.

Video Version. We use the term version to represent the transportable full video signal byte-stream. It is the video as it can be delivered to clients. Based on the definitions of areas and qualities, a version is a function that associates with every area a ∈ A a unique quality q ∈ Q, which corresponds to the encoding quality of a. Let us denote by R the set of all possible versions. Please note that the number of possible versions is finite since both the set of areas A and the set of qualities Q are finite. However, the number of different versions is N |Q | . We use the notation r (a) to denote the quality q that corresponds to the quality at which the area a ∈ A is encoded in the version r ∈ R.

Let B be a positive real number. We denote by R B the subset of versions in R such that r ∈ R B satisfies that the sum of the byte-stream sizes for every area a ∈ A is equal to B. Formally, we have :

∀r ∈ R B , a ∈A b a,r (a) = B
Viewport. One of the peculiarities of 360-degree videos is that at a given time t a user u watches only a fraction of the whole video, which is generally called the viewport. The viewport displays only a subset of all the areas of the sphere. Let v u,t,a be a real number equal to the ratio of the surface of area a that is inside the viewport of user u at time t and let v u,a be the average value of v u,t,a during all time t in a video segment: v u,a = t v u,t,a /T , with T the duration of the segment. With respect to the same definition of quality, we have that the average viewport quality during a video segment can be defined as being the sum of the qualities of all the areas that are visible in the viewports, formally a v u,a • r (a). In practice, the satisfaction of the user watching a viewport is more complex since it depends not only on the visible distortion of the different areas in the viewport but also on the possible effects that different levels of distortion on contiguous areas can produce. Nevertheless, for the sake of simplicity, and with regards to the lack of formal studies dealing with subjective satisfaction evaluation of multi-encoded videos, we consider here that the satisfaction grows with the sum of qualities of the visible areas.

Illustration: Offset Projections

To apply the implementation of offset projection as presented by Zhou et al. [START_REF] Zhou | A measurement study of oculus 360 degree video streaming[END_REF] to our model, we need to introduce some additional notations. Let 0 ⩽ β ⩽ 1 be a real number, which is the magnitude of the vector used by the "offset" projection. We denote by θ the angular distance between the "offset direction" and a given point on the sphere. The variation of the sampling frequency compared to the frequency of the same projection without offset at angular distance θ is:

f (θ ) = 1 + 2β + β 2 1 + β β cos(θ ) + 1 1 + 2β cos(θ ) + β 2
If we denote by D(a1, a2) the angular distance between the centers of two areas a1 and a2, offset projections could be modeled by the set of version r ∈ R such as there exists a of f set ∈ A such as ∀a ∈ A, r (a) = f (D(a of f set , a)) • r (a of f set ).

Illustration: Tiling

We define the concept of tile and tiled partition to extend our model to tiled versions. A tile is a set of contiguous areas of A. A tiled partition T of A is a set of non overlapping tiles that cover A. A tiled version using the tiled partition T , is a version r ∈ R such that the quality is uniform on each tile of T . Formaly we have ∀τ ∈ T , |r (τ )| = 1.

Note that in the tiled scenario, the service provider can generate a version for each tile individually without offering a version for the whole video. In this case, the client has to select separately a version for each tile to generate what we denote by a tiled version in our model. This differs from the other scenarios where the service provider is the one that decides which video version to generate.

VIEWPORT-ADAPTIVE STREAMING

An adaptive streaming system is modeled as being one client and one server, where the server offers J different versions of the video, and the client periodically selects one of these versions based on a version selection algorithm.

Server. The main question is to prepare J versions in R among all the possible combinations of qualities and areas. In the practical 360-degree video streaming system described by Zhou et al. [START_REF] Zhou | A measurement study of oculus 360 degree video streaming[END_REF], the number of versions J is equal to 30, while the solution that is promoted by Niamut et al. [START_REF] Niamut | MPEG DASH SRD: spatial relationship description[END_REF] is to offer all the combinations of tiles (typically 8 × 4) and qualities (typically 3). In practice, a low number of versions J is suitable since it means less files to manage at the server side (96 files in the latter case) and less complexity in the choice of the version at the client side (more than 32 thousand combinations in the aforementioned case). The main variable of our problem is the boolean x r , which indicates whether the server decides to offer the version r ∈ R. Formally, we have:

x r =
1, if the server offers r ∈ R 0, otherwise Since the server offers only J different versions, we have r ∈R x r = J . In the following, we restrict our focus on the case of a given overall bit-rate budget B, which is a real number. The main idea is to offer several versions of the video meeting the same bandwidth requirement but with different quality distributions. All the versions have thus the same overall bit-rate "budget" but they differ by the quality of the video, which is better at some directions in the sphere than others.

Client. The version selection algorithm first determines the most suitable bit-rate, here B, and then selects one and only one versions among the J offered versions for every segment of the videos, ideally the version that is the best match to user viewport. To simplify notations, we omit in the following the subscripts related to temporal segments, and we thus denote by y u,r the binary variable that indicates that user u selects r ∈ R for the video. Formally:

y u,r = 1, if the client u selects r ∈ R 0, otherwise
Since the user selects only one offered versions, we have r ∈R y u,r • x r = 1. We consider an ideal version selection algorithm and we thus assume that the client always selects the version that maximizes the viewport quality as previously defined, which is r such that a v u,a • r (a) is maximum.

Model Formulation

Our objective is to determine, for a given set of users who request the video at bit-rate B, the J versions that should be prepared at the server side so that the quality of the viewports is maximum. In its most generic form, the problem can thus be formulated as follows.

max y u,r u r ∈R y u,r • a v u,a • r (a)
Such that:

a b a,r (a) = B ∀r ∈ R (1a) r x r ⩽ J (1b) r y u,r = 1 ∀u (1c) y u,r ⩽ x r ∀r , u (1d)
Note that with this formulation the problem is tractable.

PRACTICAL OPTIMIZATION MODEL

We take into account some practical additional constraints and some further hypothesis to formulate a tractable optimization problem, which meets key questions from content providers.

Practical Hypothesis

We first suppose that each area a ∈ A in the whole spherical video has the same coding complexity. This means we suppose that for a given quality, the byte-stream size of a area is proportional to its size. We derive the concept of surface bit-rate, which expresses in Bps/m 2 the amount of data that is required to encode an area at a given quality. We obtain that b max (respectively b min ) corresponds to the surface bit-rate for the maximum (resp. minimum) quality.

Second, we restrict our study to only two qualities per version. We follow in that spirit the MPEG experts in the Omnidirectional Media Application Format (OMAF) group [12], and notably we follow their recommendation to implement scalable tiled video coding such as HEVC Scalable Extension (SHVC) [START_REF] Boyce | Overview of SHVC: scalable extensions of the high efficiency video coding standard[END_REF] for the implementation of quality-variable 360-degree video versions. It means that for each version we distinguish a Quality Emphasized Region (QER), which is the set of areas that are at the high quality noted b qer , and the remaining areas, which are at the low quality b out . In the SHVC encoding, b qer corresponds to the video signal with the enhancement layer, while b out contains only the base layer. Let s r be the overall surface of the areas that are in QER for a given version r ∈ R. The bit-rate constraints (1a) can thus be expressed as follow:

s r • b qer + (4π -s r ) • b out = B (2)
Third, we introduce a maximum gap between both qualities. The motivation is to prevent the video to have too visible quality changes between areas. This quality gap ratio, denoted by r b , can be defined as the maximum ratio that relate the qualities b qer and hDim v Dim c

Figure 1: A rectangular region of the sphere: in blue the two small circle that delimit the region and in red the two great circles that delimit the region.

b out : b qer b out < r b (3)
Finally, we define the QER as a rectangular region defined on the sphere as shown in Figure 1. We thus adopt the restriction that has been introduced in the MPEG OMAF [12] to delimit a so-called rectangular region on the sphere. We also adopt the same way to define the region by delimiting two small circles (angular distance vDim), two great circles (angular distance hDim) and the spherical coordinates of the region center is (1, θ, φ).

In the following, we consider only video versions r ∈ R such that there exists -π ⩽ θ ⩽ π , 0 ⩽ φ ⩽ π , -π ⩽ hDim ⩽ π , and 0 ⩽ vDim ⩽ π such that for all area a ∈ A, if a is inside the rectangle characterized by (θ, φ, hDim, vDim), the bit-rate of a is b qer otherwise it is b out . We denote such a version by r θ,φ,hDim,v Dim .

Bit-Rate Computation

The objective function [START_REF] Aminlou | Testing methodology for viewport-dependent encoding and streaming[END_REF] imply that if two versions have a QERs containing the same areas, the optimal set of offered video versions can only contains the version that maximize the b qer subject to the bit-rate constraint (2) and the ratio constraint [START_REF] Borji | State-of-the-art in visual attention modeling[END_REF].

In order to simplify the complexity of the model, we pre-computed the value of b qer and b out depending on the size of the QER s r . We identify four different cases depending on the size of the QER s r . For simplicity, we provide in the following the main ideas of the algorithm and put the details of the mathematical model in the Appendix of the paper.

We first combine the constraints given by the overall bit-rate budget with Equation ( 2) and the knowledge that b min ⩽ b out < b qer ⩽ b max . There are two cases, depending on whether the QER is small or not:

• When the surface of the QER is small, i.e., s r ⩽ B-4π b min b max -b min (see in Appendix) , the constraint on the maximum surface bit-rate prevails for b qer . The surface bit-rate inside the QER can be maximum. The bit-rate budget that remains after deducing the bit-rate in the QER is B -(s r • b max ). This remaining bit-rate budget is large enough to ensure that the surface bit-rate for the areas outside the QER is greater than b min . We obtain that b qer is equal to b max and b out is derived as:

b out = B -(b max • s r ) 4π -s r (4)
• When the surface of the QER is large, i.e., s r ⩾ B-4π b min b max -b min , the constraint on the minimum surface bit-rate prevails. The surface bit-rate inside the QER cannot be b max , otherwise the remaining bit-rate that can be assigned to the video area outside the QER would not be large enough to ensure that b out is greater than b min . Here, we first have to set b out to b min and then assign the remaining budget B -(b min • (4π -s r )) to the QER area.

b qer = B -(b min • (4π -s r )) s r (5)
Next, we consider the quality gap ratio, which applies to both previously discussed cases:

• When the QER is small, setting b qer = b max and b r,out to (4) can lead to not respect Equation (3). It occurs for any QER such that (see in Appendix) : We represent in Figure 2 the algorithm with the four cases when it applies to standard settings1 of the overall bit-rate B, the maximum surface bit-rate b max , the minimum surface bit-rate b min , and the quality gap ratio r b . Finally, we show in Figure 3 how the surface bit-rates are assigned depending on the surface s r for a given parameter configuration (see in caption and in Section 6).

s r ≥ 4π • b max -B • r b (1 -r b )
Here the thin gray vertical lines correspond to the threshold at which the algorithm runs a different case.

EVALUATION -CASE STUDY 6.1 Settings

We used a custom-made C++ software publicly available on github. 2 This software uses the IBM Cplex library to solve our optimization problem.

Dataset of Head Movements. We used the public head movement dataset that we recently extracted and shared with the community [START_REF] Corbillon | 360-degree video head movement dataset[END_REF]. 3 This dataset contains the head orientation of 59 persons watching, with a HMD, five 70-second-long 360-degree videos. In this paper we used the results from only two out of the five videos available: roller-coaster and diving. We selected those videos because users exhibit different behaviors while watching them: most users focus on a single RoI in the roller-coaster video 1. The content provider generates up to K = 4 video versions and solves the optimization problem for every video segment (i.e., each video segment has its own set of versions). The parameters related to the bit-rates are similar as in Figure 3: a total bit-rate budget B of 12.56 Mbps, a maximal surface bit-rate b max of 2.1 Mbps/m 2 and a minimal surface bit-rate b min of 0.45 Mbps/m 2 . We restricted the positions of the center of the QER on the sphere to 17 possible latitudes and 17 possible longitudes. Moreover the angular distance hDim and the angular distance vDim can take 12 different values. We split the sphere into a total of N = 400 areas. We cut the videos of the dataset into 2 s long segments. We solved the optimization model independently for each video segment.

Theoretical Gains of Viewport-Adaptive Streaming

Our first goal is to evaluate the possible (theoretical) gains that the implementation of viewport-adaptive streaming can offer to the content providers. The gains can be evaluated from two perspectives: either the opportunity to save bandwidth while offering the video at the same level of quality as if the video was sent with uniform quality, or the opportunity to improve the quality of the video that is displayed at the client side for the same bit-rate as for a standard delivery. We computed the average surface bit-rate inside the viewport of the users (named visible surface bit-rate in the following) for different bit-rate budgets. The average visible surface bit-rate b vqer in the viewport during a segment can be formally written as follow, with N u the number of user:

b vqer = r,u y u,r • a v u,a • b r (a) • s a N u • a v u,a • s a (6)
Figure 4 represents the mean average visible surface bit-rate for all segments of the two selected videos. The horizontal dashed line shows the average visible surface bit-rate for the bit-rate budget of 12.56 Mbps that is uniformly spread on the sphere, while the vertical dashed line indicates the quality for a constant bit-rate of 12.56 Mbps. We also represent the gains from the two aforementioned perspectives (either bit-rate savings or quality).

For a constant average quality inside the user viewports, the delivery of optimally generated QER versions enables 45% bandwidth savings. For a constant bit-rate budget, the optimal viewport-adaptive delivery enables an average increase of visible surface bit-rate of 102%.

Video Content vs. Delivery Settings

We now study the settings of the viewport-adaptive streaming systems, especially the parameters related to the number of different versions (J ) and the segment size (T ). We compare the set of versions that are generated by the optimal solver for both selected videos. We are interested in studying whether there exists a common bestpractice setting to generate versions, regardless of the video content, or whether each video should be prepared with respect to the content by a dedicated process with its own setting. We show the results computed separately for the roller-coaster and the diving video. Recall that the roller-coaster video has a single static RoI and most of the 59 users focus on it. On the contrary, the diving video has multiple moving RoI, which most users alternatively watch. Figure 5 represents the average visible surface bit-rate b vqer of the optimal QER versions for each user and each video segment for both videos: the roller-coaster video is in plain-green lines while the diving video is in dashed-blue lines. The results are shown with a box plot, with the 10 th , 25 th , 50 th , 75 th and 90 th percentiles for the 30 segments watched by the 59 users of each video in an optimal viewport-adaptive delivery system.

The viewport-adaptive streaming systems make that the higher the number of QER versions offered by the content provider, the better the average quality watched by the users because the set of versions covers more user behaviors. However, we notice that there exists a threshold value after which increasing the number of versions does not significantly improve the quality of the viewport of the users. This threshold depends on the video content. For the roller-coaster video, the limit is four QER versions while this limit is eight for the diving video. Please note that both threshold are significantly lower than the thirty versions that are generated by state-of-the-art viewport-adaptive delivery systems [START_REF] Kuzyakov | End-to-end optimizations for dynamic streaming[END_REF].

In Figure 7 we fix the number of QER versions to four and we evaluate the impact of the segment size on the generated QER versions. Like for Figure 5 the results are displayed with a box plot, which follows the same color code. The median quality decreases while the size of the segments increases. Indeed, the higher the segments size, the wider are the head movements of the users. But, similarly as in the number of video versions, we notice that the median average displayed quality for the diving video is more sensitive to the segment size than for the roller-coaster video. For the latter, the quality decreases for segments longer than 2 s while for the diving, the quality decreases for segment longer than 1 s.

QER Dimensions vs. Overall Bit-rate

We study the main characteristics of the generated QER versions with a focus on the impact of the global bit-rate budget on the dimensions. We evaluate both the size of the QER inside each video version and the shape of the QERs.

Figure 7 represents the cumulative density function (CDF) of the surface of the QER inside each generated optimal version, for different global bit-rate budget, for both video. The dashed vertical black line represents the surface of the viewports of the users as it is seen in the HMD.

The size of the QERs increases with the overall bit-rate budget. If the bit-rate budget is small, the size of each QERs is smaller than the surface of the viewports. It means that no user has a viewport with full quality everywhere. The optimal solver prefers here to keep a high quality on an area that is common to the viewport of many users. If we increase the available bit-rate budget, the surface of the optimal QERs increases and is now wider than the viewport, so when a user who moves the head can nevertheless still have a viewport within the QER. Figure 8 represents the probability density function (PDF) of the difference between the horizontal and vertical dimensions of the generated QERs. For instance, Figure 8a indicates that 21 % of the QERs have a horizontal size hDim that is within the range [-1 + vDim, -0.5 + vDim). The more occurrences of QER on the right, the more horizontal QERs are generated by the optimal solver.

QERs have often a squared shape (the horizontal dimension is close to the vertical dimension), and are mostly more horizontal than vertical. The horizontal shape can be explained by the fact that users move more often horizontally than vertically (they often stay close to the horizon). Moreover, when the bit-rate budget is limited, shapes are less often squared. Our interpretation is that, given that the generated QERs are narrower, the optimal solver generates QERs that cover various positions, corresponding to more users whose attention is on various positions around the horizon.

CONCLUSION

This paper investigates some theoretical models for the preparation of 360-degree video for viewport-adaptive streaming systems. Viewport-adaptive streaming has recently received a growing attention from both academic [START_REF] Corbillon | Viewport-adaptive navigable 360-degree video delivery[END_REF][START_REF] Ochi | Live streaming system for omnidirectional video[END_REF][START_REF] Quan | Optimizing 360 video delivery over cellular networks[END_REF] and industrial [START_REF] Aminlou | Testing methodology for viewport-dependent encoding and streaming[END_REF][START_REF] Di | Adaptive streaming for fov switching[END_REF][START_REF] Thomas | Draft for ve on region and point description in omnidirectional content[END_REF] communities. Despite some promising proposal, no previous work has explored the interplay between the parameters that characterize the video area in which the quality should be better. We denote this special video area a QER. In this paper, we address, on a simplified version of our theoretical model, the fundamental trade-off between spatial size of the QERs and the aggregate video bit-rate. We show that some new concepts, such as the surface bit-rate, can be introduced to let the content provider efficiently prepare the content to be delivered. Finally, we demonstrate the potential benefits of viewport-adaptive streaming: the gains compared to streaming of a video version with a uniform quality are greater than 102% in terms of displayed quality to a user given a constant bit-rate budget, and a bit-rate budget reduction for more than 45% for the same displayed video quality.

In this paper, we assumed that content provider already has some user head movement statistics. In future work we will study the generic QERs parameters that the provider can use to generate initial video versions of a 360-degree video, without video specific statistics. When the provider receives enough analytic, he will be able to generate versions adapted to real user behavior on each video segment. Such functionality would be required in both the processed and the live video viewport-adaptive streaming. Additionally, in this paper we studied only a simplified version of the theoretical model with only two different levels of quality per versions. We plan to study smoother decreasing of the quality inside video versions. Extra bit-rate assignment. In some cases, the algorithm obtains (at the step 3 in Figure 2) some so-called extra bit-rate, which comes from the quality gap ratio. This extra bit-rate must be assigned to both the QER and non-QER areas while still maintaining the constraints. Let E be the extra-bit-rate. Let y be the ratio of the extra bit-rate that is assigned to the non-QER areas. Let b int be an intermediate surface bit-rate computed as in the step 1 in Figure 2.

APPENDIX

We have:

b out = b int + y • E 4π -s r b qer = r b • b int + (1 -y) • E s r
Given that the quality gap ratio is the prevailing constraint in the considered cases, b qer = r b • b out . We thus obtain:

r b • b int + (1 -y) • E s r = r b • b int + y • E 4π -s r y = 4π -s r 4π + s r • (r b -1)

  • b max The surface bit-rate b qer should be instead reset as b qer = r b • b out . This constraint makes that some extra bit-rate are not assigned: s r • (b max -r b • b out ). These extra bit-rates can thus be re-assigned to both b qer and b r,out (see in Appendix) . • When the QER is large, setting b out = b min and b r,qer with Equation (5) can also lead to not respect Equation (3). It occurs for any QER such that: s r ⩽ 4π • b min -B (1 -r b ) • b min Similarly as in the previous case, resetting b qer with respect to the quality gap ratio leads to release of some extra bit-rates, which can be re-assigned to both b out and b qer .

( 1 )Figure 2 :Figure 3 :

 123 Figure2: Algorithm for surface bit-rates in and out of the QER. The algorithm depends on the surface of the QER s r . We show here the four different cases, for various surfaces (smallest to largest from left to right).

2 )Figure 4 :

 24 Figure 4: Visible surface bit-rate depending on the global bit-rate B. The horizontal red arrow shows the difference in total bit-rate to deliver viewports with the same average quality as a user would observe with a video encoded with a uniform quality. The vertical red arrow indicates the gain in quality (measure in surface bit-rate) compared to viewports extracted at the same position on a video with uniform quality with the same total bit-rate.

Figure 5 :

 5 Figure 5: Visible surface bit-rate depending on the number of offered QER versions. The dark red line representes the visible surface bit-rate of a video encoded with the same overall bitrate but with uniform quality.

Figure 6 :Figure 7 :

 67 Figure 6: Visible surface bit-rate depending on the size of the segment. The dark red line representes the visible surface bit-rate of a video encoded with the same overall bitrate but with uniform quality.

Figure 8 :

 8 Figure 8: Difference between the horizontal and vertical dimension of the QERs

  Limits in the Optimal Bit-Rate Algorithm Constraint on maximum and minimum bit-rate. Let set b qer = b max , which makes that s r • b max bit-rate are used for the QER. The remaining bit-rate can be used to the non-QER: b out = B-(s r •b max ) 4π -s r . We know that b min ⩽ b out . So: b min ⩽ B -(s r • b max ) 4π -s r s r ⩽ B -4πb min b max -b min Constraint on the quality gap ratio. Let set b qer = b max and b out be computed from Equation (4). However, for some s r , it can happen that r b • b out is lower than b max :r b • Bb max • s r 4π -s r ⩽ b max s r ⩾ 4πb max -r b • B (1 -r b )b max

Table 1 :

 1 Default evaluation settings Content Provider Case Study. The default parameters are summarized in Table

In some configurations, it is possible that some of the presented cases do not hold since the threshold for the cases can be negative, greater than 4π , or interfering with a prevailing constraint. This however does not occur for the most common configuration parameters such that a quality gap ratio not too large and consistent values for both b min and b max .

https://github.com/xmar/optimal-set-representation-viewport-adaptive-streaming

http://dash.ipv6.enstb.fr/headMovements/


Wilfrid Perruquetti

Thierry Floquet

Emmanuel Moulay

Finite time observers: application to secure communication

Keywords: Finite time observers, finite time synchronization, two-channel transmission, secure communication

come

I. INTRODUCTION

A lot of encryption methods involving chaotic dynamics have been proposed in the literature since the 90's. Most of them consists of transmitting informations through an insecure channel, with a chaotic system. The synchronization mechanism of the two chaotic signals is known as chaos synchronization and has been developed for instance in [START_REF] Pecora | Synchronization in chaotic systems[END_REF]. The idea is to use the output of the drive system to control the response system so that they oscillate in a synchronized manner. wilfrid.perruquetti@ec-lille.fr, thierry.floquet@ec-lille.fr) E. Moulay is with IRCCyN (UMR-CNRS 6597), 1 rue de la Noë, B.P. 92 101, 44321 Nantes CEDEX 03, France (e-mail: Emmanuel.Moulay@irccyn.ec-nantes.fr) October 4, 2007 DRAFT Since the work [START_REF] Nijmeijer | An observer looks at synchronization[END_REF], the synchronization can be viewed as a special case of observer design problem, i.e the state reconstruction from measurements of an output variable under the assumption that the system structure and parameters are known. This approach leads to a systematic tool which guarantees chaos synchronization of a class of observable systems. Different observer based methods were developed: adaptive observers [START_REF] Fradkov | Adaptive observer-based synchronization for communication[END_REF], backstepping design [START_REF] Mascolo | Controlling chaos via backstepping design[END_REF], Hamiltonian forms [5] or sub-Lyapunov exponents [START_REF] Pecora | Synchronization in chaotic systems[END_REF]. Nevertheless, during the chaos synchronization of continuous systems, the convergence of the error is always asymptotic as in [START_REF] Grassi | Nonlinear observer design to synchronize hyperchaotic systems via a scalar signal[END_REF]. Instead of attempting the construction of an asymptotic nonlinear observer for the transmitter or coding system, a finite time chaos synchronization for continuous systems (in the sense that the error reaches the origin in finite time) can be developed. Finite time observers for nonlinear systems that are linearizable up to output injection have been proposed in [START_REF] Engel | A continuous-time observer which converges in finite time[END_REF] and [8] using delays or in [START_REF] Drakunov | Sliding mode observers. tutorial[END_REF] and [START_REF] Perruquetti | A note on sliding observer and controller for generalized canonical forms[END_REF] using discontinuous injection terms. Recently, an algebraic method (using module theory and non-commutative algebra) leading to the non asymptotic estimation of the system states has been developed in [START_REF] Fliess | Reconstructeurs dŠetat[END_REF] and applied to chaotic synchronization in [START_REF] Sira-Ramírez | An algebraic state estimation approach for the recovery of chaotically encrypted messages[END_REF]. In this work, an homogeneous finite time observer is introduced. This observer yields the finite time convergence of the error variables without using delayed or discontinuous terms. Then, it is applied to the finite time synchronization of chaotic systems and combined with the conventional cryptographic method called two-channel transmission in order to design a cryptosystem. The technique of two channel transmission has been proposed in [START_REF] Jiang | A note on chaotic secure communication systems[END_REF]. Other cryptography techniques for secure communications exist such as the parameter modulation developed in [START_REF] Yang | Secure communication via chaotic parameter modulation[END_REF].

The paper is organized as follows. The problem statement and some definitions are given in Section II. An homogeneous finite time observer is developed in Section III. On the basis of this observer, a two-channel transmission cryptosystem is built and is applied in Section IV to the Chua's circuit that is relevant to secure communications (see e.g. [START_REF] Lozi | Secure communications via chaotic synchronization in chua's circuit and bonhoeffer-van der pol equation: numerical analysis of the errors of the recovered signal[END_REF] and [START_REF] Itoh | Performance of yamakawa's chaotic chips and chua's circuits for secure communications[END_REF]).

II. PROBLEM STATEMENT AND DEFINITIONS

Let us consider a nonlinear system of the form:

ẋ = η (x, u) (1)
y = h(x) (2)
ż = Az + f (y, u, u, ..., u (r) ) (3)
y = Cz (4)
where z ∈ R n is the state, r ∈ N >0 and

A =           a 1 1 0 0 0 a 2 0 1 0 0 . . . . . . . . . . . . . . . a n-1 0 0 0 1 a n 0 0 0 0           , C = 1 0 ... 0 . (5)
The transformations involved in such a linearization method for different classes of systems with n = d can be found in [18], [START_REF] Krener | Linearization by output injection and nonlinear observers[END_REF], [START_REF] Krener | Nonlinear observers with linearizable error dynamics[END_REF], [START_REF] Xia | Nonlinear observer design by observer error linearization[END_REF]. One can have n > d in the case of system immersion [START_REF] Back | Dynamic observer error linearization[END_REF], [START_REF] Jouan | Immersion of nonlinear systems into linear systems modulo output injection[END_REF].

Then, the observer design is quite simple since all nonlinearities are function of the output and known inputs. Asymptotic stability can be obtained using a straightforward generalization of a linear Luenberger observer. Finite time sliding mode observers have already been designed

for system (3)-( 4) (see e.g. [START_REF] Drakunov | Sliding mode observers. tutorial[END_REF], [START_REF] Perruquetti | A note on sliding observer and controller for generalized canonical forms[END_REF]). However, they rely on discontinuous output injections and on a step-by-step procedure that can be harmful for high order systems. In this paper, a finite time observer based on continuous output injections is introduced.

Notions about finite time stability and homogeneity are recalled hereafter.

Finite time stability

Consider the following ordinary differential equation:

ẋ = g (x) , x ∈ R n . (6)
Note φ x 0 (t) a solution of the system (6) starting from x 0 at time zero.

October 4, 2007 DRAFT Definition 1: The system ( 6) is said to have a unique solution in forward time on a neighbourhood U ⊂ R n if for any x 0 ∈ U and two right maximally defined solutions of (6),

φ x 0 : [0, T φ [ → R n and ψ x 0 : [0, T ψ [ → R n , there exists 0 < T x 0 ≤ min {T φ , T ψ } such that φ x 0 (t) = ψ x 0 (t) for all t ∈ [0, T x 0 [.
Let us consider the system (6) where g ∈ C 0 (R n ), g(0) = 0 and where g has a unique solution in forward time. Let us recall the notion of finite time stability involving the settling-time function

given in [24, Definition 2.2] and [START_REF] Bacciotti | Liapunov Functions and Stability in Control Theory[END_REF].

Definition 2: The origin of the system ( 6) is Finite Time Stable (FTS) if:

1) there exists a function T :

V \ {0} → R + (V is a neighbourhood of the origin) such that for all x 0 ∈ V \ {0}, φ x 0 (t) is defined (and unique) on [0, T (x 0 )), φ x 0 (t) ∈ V \ {0} for all t ∈ [0, T (x 0 )) and lim t→T (x 0 ) φ x 0 (t) = 0.
T is called the settling-time function of the system (6).

2) for all ǫ > 0, there exists δ (ǫ) > 0 such that for every

x 0 ∈ (δ (ǫ) B n \ {0}) ∩ V, φ x 0 (t) ∈ ǫB n for all t ∈ [0, T (x 0 )).
The following result gives a sufficient condition for system (6) to be FTS (see [START_REF] Moulay | Finite time stability of non linear systems[END_REF], [START_REF] Perruquetti | Finite time stability and stabilisation[END_REF] for ODE, and [START_REF] Moulay | Finite time stability of differential inclusions[END_REF] for differential inclusions):

Theorem 3: Let the origin be an equilibrium point for the system (6), and let r be a continuous

function on an open neighborhood V of the origin. If there exist a Lyapunov function V : V → R + and a function r : R + → R + such that

V (x) ≤ -r(V (x)), (7)
along the solutions of ( 6) and ε > 0 such that

ε 0 dz r(z) < +∞, (8)
then the origin is FTS.

The interested reader can find more details on finite time stability in [START_REF] Bhat | Geometric homogeneity with applications to finite-time stability[END_REF], [START_REF] Haimo | Finite time controllers[END_REF], [START_REF] Hong | On an output feedback finite-time stabilization problem[END_REF], [START_REF] Moulay | Finite-time stability and stabilization: state of the art[END_REF], [START_REF]Finite time stability and stabilization of a class of continuous systems[END_REF], [START_REF] Orlov | Finite time stability of homogeneous switched systems[END_REF].

Homogeneity

Definition 4: A function V : R n → R is homogeneous of degree d with respect to the weights

(r 1 , . . . , r n ) ∈ R n >0 if V (λ r 1 x 1 , . . . , λ rn x n ) = λ d V (x 1 , . . . , x n ) October 4, 2007 DRAFT
for all λ > 0.

Definition 5: A vector field g is homogeneous of degree d with respect to the weights (r 1 , . . . , r n ) ∈ R n >0 if for all 1 ≤ i ≤ n, the i-th component g i is a homogeneous function of degree r i + d, that is

g i (λ r 1 x 1 , . . . , λ rn x n ) = λ r i +d g i (x 1 , . . . , x n )
for all λ > 0. The system ( 6) is homogeneous of degree d if the vector field g is homogeneous of degree d.

Theorem 6: [25, Theorem 5.8 and Corollary 5.4] Let g be defined on R n and be a continuous vector field homogeneous of degree d < 0 (with respect to the weights (r 1 , . . . , r n )). If the origin of ( 6) is locally asymptotically stable, it is globally FTS.

III. A CONTINUOUS FINITE TIME OBSERVER

Assume that the system (1)-( 2) can be put into the observable canonical form (3)-( 4). An observer for this system is designed as follows

     dẑ 1 dt . . . dẑn dt      = A        z 1 ẑ2 . . . ẑn        + f (y, u, u, ..., u (r) ) -        χ 1 (z 1 -ẑ1 ) χ 2 (z 1 -ẑ1 )
. . .

χ n (z 1 -ẑ1 )        (9)
where the functions χ i will be defined in such a way that the observation error e = z -ẑ tends to zero in finite time. Set e = e 1 e 2

                   ė1 = e 2 + χ 1 (e 1 )
ė2 = e 3 + χ 2 (e 1 ) . . .

ėn-1 = e n + χ n-1 (e 1 ) ėn = χ n (e 1 ) (10)
Denote ⌈x⌋ α = |x| α sgn (x) for all x ∈ R and for α > 0. The following result holds:

October 4, 2007 DRAFT Lemma 7: Let d ∈ R and (k 1 , . . . , k n ) ∈ R n >0 . Define (r 1 , . . . , r n ) ∈ R n >0 and (α 1 , . . . , α n ) ∈ R n >0 such that r i+1 = r i + d, 1 ≤ i ≤ n -1, (11)
α i = r i+1 r 1 , 1 ≤ i ≤ n -1, (12)
α n = r n + d r 1 , (13)
and set

χ i (e 1 ) = -k i ⌈e 1 ⌋ α i , 1 ≤ i ≤ n.
Then, the system ( 10) is homogeneous of degree d with respect to the weights (r 1 , . . . , r n ) ∈ R n >0 . Proof of Lemma 7 is obvious.

Denote α 1 = α. Lemma 8: If α > 1 -1
n-1 , the system ( 10) is homogeneous of degree α -1 with respect to the weights

{(i -1) α -(i -2)} 1≤i≤n and α i = iα -(i -1) , 1 < i ≤ n.
Proof: Let us normalize the weights by setting r 1 = 1. Then r 2 = α and

d = r 2 -r 1 = α -1.
From ( 11) and ( 12)-( 13), one obtains recursively that:

r i = (i -1) α -(i -2) , 1 < i ≤ n, α i = iα -(i -1) , 1 < i ≤ n.
Since r 1 > . . . > r n > 0, one has:

α > n -2 n -1 = 1 - 1 n -1 .
The result follows from Lemma 7.

The system (10) is then given by:

                   ė1 = e 2 -k 1 ⌈e 1 ⌋ α ė2 = e 3 -k 2 ⌈e 1 ⌋ 2α-1 . . . ėn-1 = e n -k n-1 ⌈e 1 ⌋ (n-1)α-(n-2) ėn = -k n ⌈e 1 ⌋ nα-(n-1) (14)
W × Y about {x 0 } × Y , where W is a neighborhood of x 0 in X.
Theorem 10: Set the gains (k 1 , . . . , k n ) such that the matrix

A o =           -k 1 1 0 0 0 -k 2 0 1 0 0 . . . . . . . . . . . . . . . -k n-1 0 0 0 1 -k n 0 0 0 0          
is Hurwitz. Then, there exists ǫ ∈ 1 -1 n-1 , 1 such that for all α ∈ (1ǫ, 1), the system ( 15) is globally finite time stable.

Proof: Set 1 - 1 n -1 < α < 1.
Homogeneity: From Lemma 8, the system ( 15) is homogeneous of degree α -1 < 0 with respect to the weight {(i -1) α -(i -2)} 1≤i≤n .

Asymptotic stability: Consider the following differentiable positive definite function

V (α, e) = y T P y (16)
where

y =              ⌈e 1 ⌋ 1 q ⌈e 2 ⌋ 1 αq . . . ⌈e i ⌋ 1 [(i-1)α-(i-2)]q . . . ⌈e n ⌋ 1 [(n-1)α-(n-2)]q              , q = n-1 i=1 ((i -1) α -(i -2)
) is the product of the weights and P is the solution of the following Lyapunov equation

A T o P + P A o = -I. October 4, 2007 DRAFT As V is proper, S = {e ∈ R n : V (1, e) = 1}
is a compact set of R n . Define the function

ϕ : R >0 × S → R (α, e) → ∇V (α, e) , ψ(α, e)
Since A o is Hurwitz, the system

ė = A o e
is globally asymptotically stable and corresponds to the system (15

) with α = 1. Since ϕ is continuous, ϕ -1 (R <0
) is an open subset of Λ×S containing the slice {1}×S. Since S is compact, it follows from the Tube Lemma 9 that ϕ -1 (R <0 ) contains some tube (1

-ǫ 1 , 1 + ǫ 2 ) × S about {1} × S. For all (α, e) ∈ (1 -ǫ 1 , 1 + ǫ 2 ) × S ∇V (α, e) , ψ(α, e) < 0.
Thus, the system ( 15) is locally asymptotically stable. It can also be shown to be globally asymptotically stable as follows. Note that

V (α, λ r 1 e 1 , . . . , λ rn e n ) = λ 1 q 2 V (α, e 1 , . . . , e n ) with r i = (i -1) α -(i -2) for 1 ≤ i ≤ n. Thus e → V (α, e)
is homogeneous of degree 1 q 2 with respect to the weights {(i -1) α -(i -2)} 1≤i≤n . From [START_REF] Rosier | Homogeneous Lyapunov function for homogeneous continuous vector field[END_REF], it can be deduced that e → ∇V (α, e) , ψ(α, e) is homogeneous of degree 1 q 2 + α -1 with respect to the weights {(i -1) α -(i -2)} 1≤i≤n and thus is negative definite. This imply that, for α ∈ (1

-ǫ 1 , 1 + ǫ 2 ), e → V (α, e)
is a Lyapunov function for the system [START_REF] Lozi | Secure communications via chaotic synchronization in chua's circuit and bonhoeffer-van der pol equation: numerical analysis of the errors of the recovered signal[END_REF].

From Theorem 6, it follows that the system is globally finite time stable. October 4, 2007 DRAFT IV. CRYPTOSYSTEM AND ITS APPLICATION TO THE CHUA'S CIRCUIT Several chaotic systems, as the three-dimensional Genesio-Tesi system [START_REF] Chen | General synchronization of genesio-tesi systems[END_REF], the Lur'e-like system or the Duffing equation [START_REF] Feki | Observer-based exact synchronization of ideal and mismatched chaotic systems[END_REF], belong to the class of systems [START_REF] Fradkov | Adaptive observer-based synchronization for communication[END_REF][START_REF] Mascolo | Controlling chaos via backstepping design[END_REF]. Let us show that the proposed observer can be useful to perform finite time synchronization of this class of chaotic systems and secure data transmission. For a two-channel transmission, the system governing the transmitter is given by:

ż = A z + f (y) (17)
y = z 1 (18) s (t) = ν e (z(t), m(t)) . (19)
The first channel is used to convey the output y = z 1 of the chaotic system (17). The function ν e encrypts the message m (t) and delivers the signal s (t) which is transmitted via the second channel. The receiver gets z 1 (t) on the first channel. An observer is designed as follows:

     dẑ 1 dt . . . dẑn dt      = A        z 1 ẑ2 . . . ẑn        + f (y) + O n (y -ẑ1 ) (20)
where

O n (y -ẑ1 ) =        k 1 ⌈z 1 -ẑ1 ⌋ α k 2 ⌈z 1 -ẑ1 ⌋ 2α-1 . . . k n ⌈z 1 -ẑ1 ⌋ nα-(n-1)        .
The error dynamics e = z -ẑ is given by the system [START_REF] Lozi | Secure communications via chaotic synchronization in chua's circuit and bonhoeffer-van der pol equation: numerical analysis of the errors of the recovered signal[END_REF]. With a good choice of α and {k i } 1≤i≤n , Theorem [START_REF] Perruquetti | A note on sliding observer and controller for generalized canonical forms[END_REF] implies that the error dynamic e (t) converges to the origin in finite time. As a consequence, the message m (t) can be completely recovered after the finite time synchronization by the system

         System (20) ŷ = ẑ1 m = ν d (ẑ, s)
.

where the decoding function ν d is defined by ν d (z (t) , s (t)) = m (t).

October 4, 2007 DRAFT

The Chua's circuit belongs to the class of chaotic systems which can be put into the observable canonical form. ( 3)-( 4) The equations of a Chua's oscillator are given by:

         C 1 ẋ1 = 1 R (x 2 -x 1 ) + h (x 1 ) C 2 ẋ2 = 1 R (x 1 -x 2 ) + x 3 L ẋ3 = -x 2 -rx 3 (21)
where L is a linear inductor, R and r two linear resistors, C 1 and C 2 two linear capacitors,

h (x) = G 2 x 1 + 1 2 (G 1 -G 2 ) (|x 1 + B| -|x 1 -B|)
is the piecewise linear Chua's function. The chosen output is y = x 1 .

Using the transformation z = T x with 21) is transformed into the observable canonical form (17)-( 18) with

T =      1 0 0 1 C 2 R + r L 1 C 1 R 0 1 C 2 L 1 + r R r C 1 LR 1 C 1 C 2 R      the system (
A =      -1 C 1 R -1 C 2 R -r L 1 0 -1 L r C 1 R + r C 2 R + 1 C 2 0 1 -1 C 1 C 2 RL 0 0      , f (y) =      1 C 1 1 C 1 1 C 2 R + r L 1 C 1 C 2 L 1 + r R      h (y) .
In the simulations, the numerical values of the Chua's circuit are C

1 = 10.04 nF, C 2 = 102.2 nF, R = 1747 Ω, r = 20Ω, L = 18.8 mH, G 1 = -0.756 mS, G 2 = -0.409 mS, H = 1 V.
The gains of the observer have been set as follows: α = 0.7, k 1 = 1000, k 2 = 240, k 3 = 24. The observation error dynamics e = z -ẑ is then given by

         ė1 = e 2 -1000 ⌈e 1 ⌋ 0.7 ė2 = e 3 -240 ⌈e 1 ⌋ 0.4 ė3 = -24 ⌈e 1 ⌋ 0.1 . ( 22
)
and e (t) converges to the origin in finite time (see Fig. 1 and2). A message m (t) can be sent and recovered after the delay due to the finite time synchronization by using the previous algorithm (see Fig. 3).

October 4, 2007 DRAFT Remark 11: It is possible to increase the security of the transmission by introducing some observation singularities in the system (17). In this case, finite time convergence is a useful property (see [START_REF] Barbot | Observability Normal Forms in[END_REF]).

V. CONCLUSION

In this paper, a continuous finite time observer based on homogeneity properties has been designed for the observation problem of nonlinear systems that are linearizable up to output injection. It does not involve any discontinuous output injections and step-by-step procedure, as it is the case, for instance, for sliding mode observers. It has been applied to finite time chaos synchronization and to secure data transmission using the two-channel transmission method.

W.

  Perruquetti and T. Floquet are with the LAGIS (UMR CNRS 8146), Ecole Centrale de Lille, Cité Scientifique, 59651 Villeneuve d'Ascq Cedex, France and with Centre de recherche INRIA futurs, Equipe Projet ALIEN. (e-mail:

Lemma 9 (

 9 Tube Lemma): Consider the product space X × Y , where Y is compact. If N is an open set of X × Y containing the slice {x 0 } × Y of X × Y , then N contains some tube

3 Fig. 1 .

 31 Fig. 1. State of the system (21) and its estimate

3 Fig. 2 .

 32 Fig. 2. Observation error

  R d is the state, u ∈ R m is a known and sufficiently smooth control input, and y(t) ∈ R is the output. η : R d × R m → R d is a known continuous vector field. It is assumed

	where x ∈ that the system (1)-(2) is locally observable [17] and that there exist a local state coordinate
	transformation and an output coordinate transformation which transform the nonlinear system
	(1)-(2) into the following canonical observable form:
	October 4, 2007	DRAFT