Oky Purwantiningsih

Arnaud Sallaberry

S Ébastien Andary

Antoine Seilles

J Ér Ôm É Az

Visual Analysis of Body Movement in Serious Games for Healthcare

Keywords: H, 3, 3 [Information Storage and Retrieval]: Information Search and Retrieval-Clustering; H, 5, 2 [Information Interfaces and Presentation]: User Interfaces-Graphical User Interfaces

The advancement of motion sensing input devices has enabled the collection of multivariate time-series body movement data. Analyzing such type of data is challenging due to the large amount of data and the task of mining for interesting temporal movement patterns.

To address this problem, we propose an interface to visualize and analyze body movement data. This visualization enables users to navigate and explore the evolution of movement over time for different movement areas. We also propose a clustering method based on hierarchical clustering to group similar movement patterns. The proposed visualization is illustrated with a case study which demonstrates the ability of the interface to analyze body movements.

INTRODUCTION

Visualizing movement data has been proved to be challenging due to the large volume of data [START_REF] Andrienko | Visual Analytics of Movement[END_REF]. This is also the case with visualizing body movement data which is usually multivariate and time oriented. The challenge in visualizing time-series data lies in finding the temporal trends or pattern in the data as has been discussed extensively in [START_REF] Aigner | Visualization of Time-Oriented Data[END_REF]. A few visualization techniques focus on timeseries body movement data (e.g. [START_REF] Bernard | MotionExplorer: Exploratory search in human motion capture data based on hierarchical aggregation[END_REF][START_REF] Chmelik | Body motion visualization in virtual environment[END_REF][START_REF] Heryadi | Grammar of dance gesture from bali traditional dance[END_REF][START_REF] Patsadu | Human gesture recognition using kinect camera[END_REF][START_REF] Raptis | Real-time classification of dance gestures from skeleton animation[END_REF][START_REF] Tashiro | A study on motion visualization system using motion capture data[END_REF]). In healthcare, such data are generated from serious games which are used for patients' rehabilitation and training. These games use motion sensing input device technologies such as Kinect and Wii Balance Board to capture players' movements. Data generated from the game are then analyzed by healthcare professionals to make a diagnosis of patients' progress. However, analyzing large amounts of data manually is long, difficult and tedious. Therefore, a visualization interface is needed. The challenge lies in determining how to visualize such data, so that healthcare professionals can evaluate progress and make decisions for the next rehabilitation step.

Currently, serious games provide some charts which visualize the player's body movements with respect to the horizontal axis and vertical axis [START_REF] Rahman | Multimedia environment toward analyzing and visualizing live kinematic data for children with hemiplegia[END_REF][START_REF] Rahman | Multisensor serious game-based therapy environment for hemiplegic patients[END_REF]. However, the information that can be gathered from the visualization is not enough for the healthcare professional to establish an informed diagnosis. It is not immediately clear how often the player moves to the right or to the left. Its also not clear which type of events (i.e., avoiding an enemy, catching the bonuses) are associated with the movements, which is crucial since the therapist needs to know if the player is able to move his body in the necessary direction. Most importantly, they need to know the evolution of the players' body movements over time to see if they have developed strategies to achieve the required movement for the rehabilitation.

To address these problems, we propose an interactive visualization allowing healthcare professionals to analyze the evolution of players' body movements throughout several sessions of a serious game. We also propose an approach to easily navigate and highlight movement patterns. It is based on a clustering algorithm that identifies similar movement patterns. New distance functions are defined to quantify similarity between movement patterns, taking into account both movement evolution and proportion of movement frequency.

DOMAIN PROBLEM CHARACTERIZATION

In order to clearly understand the problems faced by the healthcare professionals in interpreting a gameplay into a meaningful therapy routine, it is important to have an understanding of how the game is played. Based on this understanding, it will be possible to find out what kind of information is needed by defining questions usually asked by the users. In the end, visualization requirement elicitation will be done by translating each question into a list of tasks. This section discusses each one of these steps in details.

For the research, we explore data from a game called Hammer and Planks which is developed by NaturalPad1 . This game is designed so that the player has to move his body right, left, forward and backward, in order to recover full mobility. It is a vertical shooter game. The game world is in a 2D environment vertically scrolling from top to bottom in which a player navigates a ship from left to right through moving his body. While navigating the ship to collect driftwood/planks (bonuses), the player also needs to kill enemies and to avoid reefs scattered all over the ocean (obstacles).

It is possible to play Hammer and Planks in two different ways: (i) BodyTilt: The player puts both hands on his/her hips and moves the upper body (from the waist up) to the right, to the left, forward or backward to navigate the boat. (ii) HandPoint: the player lifts one of his/her forearms in front of the body with the palm facing forward. Navigating the boat can be done by moving the forearm to the right, to the left, forward, or backward. Basically, there are two types of movement directions: a horizontal movement moves the boat horizontally and a vertical movement changes the boat speed. Body movements are recorded with a Kinect. Before each session, the healthcare professionals set the number of objects (enemies, bonuses, obstacles), activity duration and repetition, as well as area in which the objects can appear. Therefore he can adjust the difficulty of the game for different sessions.

A traditional therapy routine usually involves the therapist ordering a patient to perform several movements repetitively [START_REF] Rahman | Multisensor serious game-based therapy environment for hemiplegic patients[END_REF]. By the end of the session, the therapist will analyze how the patient has performed based on the quality of movement as well as how the patient has progressed compared to the previous session. Based on this analysis, the therapist will then configure a new routine to further the patient's progress, if needed. To make his analysis, he/she needs to answer questions such as "has the patient improved in the game overtime?", "has he/she improved in a certain area overtime?" or "is there an area where the patient acts the same?". Here, we propose a tool to help him perform his analysis. In collaboration with experts, we have identified five tasks that need to be performed with the tool.

Before listing these tasks, we need to further describe the data generated from a game session. The gameplay contains information about the player, the game setting, the player's movements throughout the game and every event that occurred in the game. Each event has an event type, which is the type of action performed by a player (represented with a boat in the game) towards an object or away. The movement of the boat is considered as the movement of the player's body. We will analyze this body movement data. The following are the tasks we identified in collaboration with experts: (T1) Visualize, navigate and be able to compare the evolution of the number of events throughout all sessions within a certain xarea, (T2) Select and visualize the number of events of a certain event type in a certain x-area throughout all sessions, (T3) Visualize, navigate and be able to compare the distribution of a certain number of events over x-area among all sessions, (T4) Select and visualize the distribution of certain number of events over x-area for a certain event type throughout all sessions, (T5) Extract and visualize similar pattern of number of events evolution throughout all sessions over a certain x-area.

DATA ABSTRACTION

In this section, we discuss the design of the data structure and clustering technique used to support the visualization requirement. First, an overview of the input data generated from the game will be explained. Then a clustering algorithm proposed to be used in the visualization will be discussed.

Game Event Structure

The goal of Hammer and Planks game is to kill all the enemies while avoiding any attack from the enemies and obstacles [START_REF] Di Loreto | Game design for all: The example of hammer and planks[END_REF]. Along the way, players can also catch bonuses to increase their score. Based on these, we identified three different objects within the game: Bonus, Obstacle and Enemy. For each of these objects, there are certain events associated. Each event has an event type. In total, there are 7 event types: (1) Catch: when a bonus is caught (2) Miss: when a bonus is missed or a player's attack on an enemy is missed (3) Dodge: when an obstacle is avoided (4) Collision: when the player's boat collides with an enemy or an obstacle (5) Kill: when an enemy is destroyed by the player's boat (6) Hit: when the player's attack hits an enemy [START_REF] Huron | Visual sedimentation[END_REF] Hurt: when the enemy's attack hits the player's boat. Based on the level of impact of each event to the user's boat, we characterize the event by assigning it with Positive, Neutral, or Negative as shown in Table 1.

Event Type Bonus Obstacle Enemy

Positive

(1) ( 5), ( 6)

Neutral (2) (3) (2) Negative (4) (4), (7)
Table 1: Event Type grouping

Clustering

In understanding the evolution of movements among different sessions over x-area, it is interesting to see the common evolution of different sections of the x-area (T5). The idea is to cluster similar distribution of movements (which is represented by events in the game) so that consecutive sections which have similar evolutions are represented by a single representation. This section explains how the clustering is done. First, a distance function used to calculate the difference between two consecutive sections will be presented. Then, a clustering algorithm based on hierarchical clustering which incorporates this distance function will be explained.

Distance Calculation

Let S be a gameplay data set of n ses sessions. S is an ordered list of sections s i , 0 ≤ i < n sec . Each section contains events that occurred on an x axis unit among all sessions. More precisely, a section s i is a sequence of triplets s i [ j], 0 ≤ j < n ses . Each triplet represents a data set of a certain game session of a particular section s i . The triplet consists of the number of negative, neutral and positive events. The profile of each section can be represented by a matrix of n ses x 3 dimensions. For instance, the following matrices represent a gameplay with 2 sessions and 3 sections: In this example, we see that on the left part of the x axis (s 1 ), the player got 10 negative, 20 neutral and 6 positive events for the first session. He then got 20 negative, 5 neutral and 18 positive events for the second session. In the middle part of the x axis (s 2 ), on the first session he got 20 negative, 40 neutral and 10 positive events, while on the second session he got 40 negative, 10 neutral, and 30 negative events, etc.

s 1 = 10
Since the idea was to aggregate consecutive sections with similar movement patterns, a function to quantify the similarity between two sections is needed. Here, we focus on patterns described by triplets of values as described in the example. In this case, we quantify the similarity by defining a distance function. Thus, a distance equal to 0 indicates that both sections are similar, while a distance equal to 1 indicates that both sections are different. We identified that two types of distances need to be considered: (i) how different are the sections in terms of the proportion of the event types in each section (ii) how different are the sections in terms of the evolution of each event type throughout the sessions. For instance, with the (i) approach, s 2 and s 3 are similar because the triplets of each session are proportional ([20,40,10] is proportional to [START_REF] Rahman | Multimedia environment toward analyzing and visualizing live kinematic data for children with hemiplegia[END_REF]20,[START_REF] Di Loreto | Game design for all: The example of hammer and planks[END_REF] and [40,[START_REF] Rahman | Multimedia environment toward analyzing and visualizing live kinematic data for children with hemiplegia[END_REF]30] is proportional to [16,[START_REF] Chmelik | Body motion visualization in virtual environment[END_REF][START_REF] Raptis | Real-time classification of dance gestures from skeleton animation[END_REF]). With the (ii) approach, s 1 and s 2 are similar, because the corresponding event types are proportional ( [START_REF] Rahman | Multimedia environment toward analyzing and visualizing live kinematic data for children with hemiplegia[END_REF]20] is proportional to [20,40], [20,[START_REF] Di Loreto | Game design for all: The example of hammer and planks[END_REF] is proportional to [40,[START_REF] Rahman | Multimedia environment toward analyzing and visualizing live kinematic data for children with hemiplegia[END_REF], and [START_REF] Heryadi | Grammar of dance gesture from bali traditional dance[END_REF]18] is proportional to [START_REF] Rahman | Multimedia environment toward analyzing and visualizing live kinematic data for children with hemiplegia[END_REF]30]).

Thus, for each pair of consecutive sections (s 1 , s 2 ) of S, distance d(s 1 , s 2 ) is defined as weighted sum of (i) and (ii), represented as f (s 1 , s 2 ) and g(s 1 , s 2 ) in the following formula:

d(s 1 , s 2 ) = α f (s 1 , s 2 ) + (1 -α)g(s 1 , s 2 )
Distance function f (s 1 , s 2 ) is based on a Normalized Euclidean Distance (NED) between two triplets of the same session between two consecutive sections. The overall distance of both sections is the average euclidean distance of each triplets pair. To get a value of distance between 0 and 1, each Euclidean distance value is normalized by dividing it by maximum distance √ 3.

f (s 1 , s 2 ) = i<|s 1 | ∑ i=0 NED(s 1 [i], s 2 [i]) |s 1 | NED(s 1 [i], s 2 [i]) = ∑ j∈{0,1,2} (s 1 [i][ j] -s 2 [i][ j]) 2

√

In this first distance function, s 1 and s 2 represent the normalized value of s 1 and s 2 . Since the first distance is to see the difference of event type proportion in each section, the values are normalized by the maximum value of each session in each section. In this case, two consecutive sections with different number of events but similar proportions of event types will have a distance equal to 0. For example, the matrices presented previously can be normalized into the following matrices: Thus, distance f (s 1 , s 2 ) = 0.06, and distance f (s 2 , s 3 ) = 0. The second distance function g(s 1 , s 2 ) is based on a Normalized Euclidean Distance of the same event type j between different sections. The overall distance of both sections is the average euclidean distance of each event type pair. For each event type distance, there are three different distance values defined: (i) if there is no event in both event type pairs, the distance is 0 (ii) if there is at least one event in one section and no events in the other section, the distance is 1 (iii) if both event type pairs have any events then the euclidean distance is calculated. Distance (i) and (ii) are defined to isolate empty regions. Thus when both sections are empty, it will be considered similar and will be clustered together. Besides, when only one section is empty while the other has some events, it will be considered as different sessions and therefore will not be clustered together. To get a value of distance between 0 and 1, each Euclidean distance value is then normalized by dividing it by maximum distance |s 1 |.

s 1 =
g(s 1 , s 2 ) = g 0 (s 1 , s 2 ) + g 1 (s 1 , s 2 ) + g 2 (s 1 , s 2 ) 3 and for j ∈ {0, 1, 2}, g j (s 1 , s 2 ) =                    0 if s k [i][ j] = 0 for each 0 j < |s k | and k ∈ {1, 2} 1 if s k [i][ j] = 0 for each 0 j < |s k | and ∃s p [i][ j] = 0, k, p ∈ {1, 2}, k = p |s 1 | ∑ i=0 (s 1 [i][ j] -s 2 [i][ j]) 2 √ |s 1 | otherwise
Here, s 1 and s 2 represent the normalized value of s 1 and s 2 . In order to compare the evolution of the same event type between consecutive sections, the values are normalized by dividing it by maximum value of each event type in the section. Thus, the matrices presented previously can be normalized into the following:

s 1 = 1 2 1 1 3 1 1 4 1 s 2 = 1 2 1 1 3 1 1 4 1 s 3 = 5 8 1 5 12 1 1 5 1
Here, distance g(s 1 , s 2 ) = 0 and distance g(s 2 , s 3 ) = 0.06.

Clustering Algorithm

The clustering algorithm follows Hierarchical Clustering algorithm [START_REF] Maimon | Data Mining and Knowledge Discovery Handbook[END_REF], which is a clustering analysis method used to build a hierarchy of clusters. Overall, the clustering is done as follows: initially, the data set is divided into sections the size of x axis unit. Then, the distances of consecutive sections are calculated. Two consecutive sections with a distance below a specified threshold are then merged. Thus resulting in a new set of sections. Then, the distance of each pair of consecutive sections of this new set of sections are calculated and again, if the new distance satisfies the threshold, the sections will be merged. This process is repeated until there is no distance falling below the threshold.

VISUAL MAPPINGS AND INTERACTIVE FUNCTIONALITIES

This section presents the visualization and interaction methods developed based on the visualization requirements and data abstraction discussed in Sections 2 and 3. Since users are interested in the evolution of movement over a certain x-area, the visualization is divided into sections of x-area. There are three ways of division: by the range of x-area, by the number of events within an area, and by clustering. The following explains the three approaches and its interaction technique in detail.

Visualization by range of x-area

To fulfill (T1), a streamgraph metaphor is chosen to show the evolution of movement (represented by events) over time. Time is often displayed on x axis, but here, x axis represents the x axis of the screen, so time is displayed on the y axis. Some visualizations are also based on this approach, like Visual Sedimentation [START_REF] Huron | Visual sedimentation[END_REF]. Here, sessions represent time with the earliest one shown at the bottom and the latest one shown at the top. The x axis is then divided into sections of the same range based on user input. For each section, events are then filtered to the one which happened within the section x boundary. The filtered events are grouped based on the session number and the event category. The number of events within this group is then presented in the vertical streamgraph layout. Each event category is represented as an area with different colors: red (Negative), Yellow (Neutral), and Green (Positive). For each section, it is possible to see which session has the most or least number of events by comparing the total length of all event categories in one session (see Figure 1.a) .

Visualization by number of events

This second type of Summary Visualization uses the same approach explained previously. However, a section is calculated based on the total number of positive and negative events instead of the range of x axis (T3). Therefore, based on the distribution of positive and negative events, one section in the chart may have bigger x range than the other section. Only by comparing the size of the sections, it's possible to know in which area most of the events are concentrated. Figure 1.c shows that the events are more concentrated in the right area of the screen.

Visualization by clustering

This third type of visualization fulfills (T4). Initially the chart is divided into sections with range equals to an x axis unit. Depending on the threshold value inputted by the user, consecutive sections with a distance below the threshold will be merged. This process is repeated until there is no pair of sections with a distance below the threshold. The input threshold ranges from 0 to 1. Thus, when user inputted threshold = 0, none of the sections will be merged. Besides, when user inputted threshold = 1, all of the sections will be merged. Figure 1.b shows when user input threshold = 0, while Figure 1.d shows threshold = 0.35. As we can see, there are some sections which are merged, indicated by a bigger section size.

Interaction Technique

On top of the chart, an interaction bar is provided where the user can interact with and change some variables in the chart. In the first panel of the interaction bar (Figure 1.e), three sliders are provided: (i) a slider to input the number of slices so that each section will have the same x range (ii) a slider to input the number of slices so that each section will have the same total number of positive and negative events (iii) a slider to input a threshold so that each section will have a cluster of similar movement evolution. When a user uses slider (i) and (ii), the value on the slider defines the number of sections on the chart. For (i), the more number of sections, the smaller the x range. While for (ii), the value selected on the slider is a denominator. The input is calculated by dividing the total number of all positive and negative events by the value selected on the slider. Thus, the smaller the number chosen on the slider, the bigger the number of events. In the second panel, the user has the options to choose which event type to show on the chart. This fulfills requirements (T2) and (T4). By default all event types will be shown.

Once the chart is generated, the user has the ability to slide/drag the line between each session or the small triangle at the bottom of the line to the right or left to change the range of its neighboring sections (T1,T3). While dragging, the text on top of the line changes based on the current x value of the dragged line. When a line is dragged over another line, the two sections will be merged creating a new section with a different x range. Therefore, the user may be able to determine areas in which a certain type of event appears. It is also possible to divide a section into two sections by clicking the top area of the chart in between the lower and upper section boundary text. This allows the user to know the distribution of event type within a section.

CASE STUDY

To evaluate the visualization functionality developed in this article, a case study will be presented. In this case study we use data set from games played by patients. These data sets are collected by NaturalPad. Unfortunately, it is not possible to get information concerning the patients' pathology due to confidentiality reasons. This case study is based on a patient dataset containing 15 sessions which are played over the course of 3 weeks. These sessions are of two game types: HandPoint (6 sessions) and BodyTilt (9 sessions). Here, only the 6 sessions of HandPoint exercise will be discussed.

The visualizations in Figure 1 show that the patient mostly moved to the right side. Figure 1.a shows the evolution of neutral events T2. Here, we can see that there are more neutral events on the left side compared to the right throughout all sessions. In 1.b, we can see that four sections between 0 and 4 have similar neutral event evolutions. Therefore, the sections are merged together forming one section T5 (see Figure 1.d). Consistent with all the previous visualizations, Figure 1.c shows that the movements are concentrated more on the right side [T3,T5]. In particular, for sessions 4, 10, 11 and 13, the patient did not move to the left side (only neutral events). From session 14 to 15, movements on the left side appear indicated by a small number of negative and positive events T1. We can assume that the patient has his left side of the body affected (hemi-neglect), but he/she starts recovering. The therapist is able to detect this evolution and proposes new sessions or exercises adapted to the patient's state.

CONCLUSION

In this paper we presented a visualization interface to help healthcare professionals analyze gameplay of Hammer and Planks, a serious game which is used to rehabilitate patients with balance disorder. In order to identify movement patterns of interest, we propose new metrics for the evaluation of distances between sequences of patient movements. The purpose is to aggregate similar movement patterns over consecutive sections. We also propose an interface which allows the therapist to interactively explore the patterns by dynamically changing aggregation parameters. Therapists can then discover the movement patterns.

For future work, we plan to perform evaluations to validate the metrics and the visualization. We also want to develop new visualization features and to study how these techniques could be extended to other kinds of data.

Figure 1 :

 1 Figure 1: Visualization divided by x range filtered with Neutral events (a), clustered with threshold=0 (b), divided by total number of Positive and Negative events (c), clustered with threshold=0.35 (d), and navigation bar (e)

www.naturalpad.fr


Wahabou Abdou
email: wahabou.abdou@u-bourgogne.fr

Christelle Bloch

Damien Charlet

NICE-MRP: a Near-Optimal Radio-Interference Aware Multi-path Routing Protocol for MANETs

Nowadays, with the miniaturization of communication devices, dense and highly mobile ad-hoc networks are very common. Besides, more and more devices have several radio interfaces. In such an environment, multi-path routing should be considered. Yet, only few multi-path ad-hoc routing protocols take into account the radio-interferences which might arise between two geographically close routes. Moreover, they generally only forbid the addition of interfering paths rather than looking for a different, more optimized, solution. This paper presents NICE-MRP, a novel multi-path routing protocol for mobile adhoc networks giving efficient solutions with respect to physical radio-interferences between paths. This protocol discovers and stores several combinations of non-interfering multi-path routes. The best multi-path route is used to transmit data, whereas alternative multi-path routes are kept to dynamically react to route breakages due to mobility and node failures. Compared to other well-known protocols, NICE-MRP presents good qualities in terms of latency, overhead and packet losses. Besides, these results end to be rather independent from the degree of mobility.

I. INTRODUCTION

Building routes in a wireless network is a complex task. In fact, there are various topologies for a wireless network, according to the network density (low or high) and the mobility of nodes (static or mobile). Most of the routing protocols build a single path from one source to one destination. Since the updating of routes can generate a lot of messages in the network, well-known protocols try to limit signalling traffic. Nevertheless, building more than one path from a source to a destination may use up roughly the same amount of power as for a one-path routing. Multi-path routing protocols can get new properties, such as fastest adaptation to mobility or node failure, bandwidth improvement or a better consumption balance between nodes. However, multi-paths in wireless networks differ from multi-paths in wired networks because of interferences. An efficient multi-path routing protocol must avoid interferences between neighboring nodes in case of the simultaneous use of two paths or more.

This paper proposes a new strategy called NICE-MRP to efficiently build multi-paths between a source and a destination in a wireless network. The ns-2 simulator was used to assess the performances of this protocol in realistic contexts including mobility and link loss between nodes.

The remainder of this paper is organized as follows. Section 2 is a survey on single and multi-path routing protocols. Section 3 describes the NICE-MRP protocol. The simulated results of the comparison between NICE-MRP and SMR [START_REF] Shu | Secure data collection in wireless sensor networks using randomized dispersive routes[END_REF] is outlined in section 4.

II. STATE OF THE ART

Many ad-hoc routing protocols have been proposed in the literature to tackle the specificity of MANETs. Some of them only seek one route (single-path routing protocols) whereas others seek several routes. The following sections will briefly describe well-known single and multi-path routing protocols.

A. Single-path Routing Protocols for Ad-hoc Networks

There are two main classes of single-path routing protocols; the are classified according to how they build routing tables: proactive ones and reactive ones.

1) Proactive protocols: Proactive protocols discover and maintain pre-computed routes by regularly exchanging topological information. Each node fills up a routing table to reach all the hosts in the network. Several algorithms have been proposed to better compromise between network overhead and quality of routes (reliability, availability, latency). DSDV [START_REF] Perkins | Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers[END_REF] and OLSR [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF] are two of the best-known tabledriven protocols. DSDV is a distance vector protocol. It uses the well-known distributed Bellman-Ford (DBF) algorithm [START_REF] Bertsekas | Data Networks[END_REF] to compute the best paths between nodes. One-hop neighbors partially or totally exchange their routing tables to update information if necessary. This ensures the reliability of the computed distances. Besides, DSDV assigns a sequence number to each route in order to differentiate obsolete paths from updated ones. Frequent information exchanges permit to keep routes up-to-date in highly mobile networks, which prevents from data transfer failure. But they also increase the use of network resources and reduce the bandwidth available to transmit data packets. OLSR (Optimized Link State Routing protocol) lies on the optimized broadcasting of discovery and maintenance messages, using Multi-Point Relays (MPRs). Each node chooses its MPRs among its one-hop neighbors so that it can reach all its two-hop neighbors. Only MPRs broadcast link state messages. And each MPR only gives the state of its links to the nodes that chooses it. So, the number of MPRs must be minimized to limit overhead.

2) Reactive protocols: Reactive routing protocols limit routing overhead by building and maintaining routes only when needed. DSR [START_REF] Johnson | The dynamic source routing protocol (DSR) for mobile ad hoc networks for ipv4[END_REF] and AODV [START_REF] Perkins | Ad hoc on-demand distance vector (AODV) routing[END_REF] are two of the most widely used reactive protocols. In DSR (Dynamic Source Routing protocol), the source node sends a route request (RREQ) for each route discovery. Every neighbor eventually forwards this RREQ until it reaches the destination or an intermediate node which has an entry for this destination in its routing cache. The source receives a route reply (RREP) which contains the identification of all the intermediate nodes. The list of intermediate identifiers is included in data packets. This list might be very long in large networks. The route discovery process of AODV, the Ad-hoc On-Demand Distance Vector protocol, is nearly the same as in DSR. But AODV does not use source routing. Each node on the path caches a pointer to the neighbor from which it received the RREP.

B. Multi-path Routing Protocols

In the last years many scientific works focused on multi-path routing protocols. Such protocols seek and maintain several routes between the source and destination nodes, either to split traffic between several paths or to keep alternative routes available to be used in case of failures. Generally, they lie either on DSR (source routing) or on AODV (distance vector routing), and they attempt to find disjoint paths in order to limit interference. The following sections present some wellknown protocols belonging to these two classes.

1) Source-based routing protocols: SMR (Split Multipath Routing) [START_REF] Shu | Secure data collection in wireless sensor networks using randomized dispersive routes[END_REF] is an on-demand routing protocol which allows to split traffic between several routes. It is based on DSR, but intermediate nodes do not reply to RREQs. The destination selects several paths among the different copies of the RREQs it receives. The first selected route is the one with the shortest delay, then the second is maximally-disjoint to the first one. In case of equality, the number of hops is used as a secondary criterion to be minimized. Traffic allocation uses per-packet granularity. The multi-Path Dynamic Source Routing protocol (MP-DSR) [START_REF] Patil | Ondemand multipath routing protocols for mobile ad hoc networks issues and comparison[END_REF] is a routing protocol with QoS support, based on a metric named end-to-end reliability. This metric represents the probability to successfully send packets from source to destination within a given time interval. During route discovery, the source node computes the number of routes nb routes and the reliability level for each of them, which permits to satisfy a required value of this metric. nb routes RREQs are used to build paths which comply with these reliability requirements. The destination node finally selects a set of disjoint paths through which it sends RREPs. IZM-DSR [START_REF] Javan | IZM-DSR: A new zone-disjoint multi-path routing algorithm for mobile adhoc networks[END_REF] builds several zone-disjoint paths. It uses the notion of ActiveNeighborCount (AN C) introduced in ZD-MPDSR [START_REF] Javan | Reducing end-to-end delay in multi-path routing algorithms for mobile ad hoc networks[END_REF]. This value estimates the risks of interference in each node of the computed paths. Thus the source node selects the paths corresponding to the minimal values of (AN C) in the various RREPs it receives.

2) Distance vector-based protocols: AOMDV (Ad-hoc Ondemand Multipath Distance Vector) [START_REF] Patil | Ondemand multipath routing protocols for mobile ad hoc networks issues and comparison[END_REF] provides fault tolerance by building, for each destination, a set of acyclic link disjoint (or node disjoint) paths. When it exchanges route information, a node only gives, for each destination, an advertised hop count (which is the maximal hop count for all the paths). Each new information about a destination is an available alternative route. In order to ensure loop freedom, nodes only accept routes that have a lower hop count than the one advertised for this destination. Adaptive Ad-hoc Ondemand Multipath Distance Vector (A 2 OMDV) [START_REF] Shin | A2OMDV: An adaptive ad hoc on-demand multipath distance vector routing protocol using dynamic route switching[END_REF] is an extension of AOMDV which dynamically adapts itself to network conditions such as congestion. Route discovery begins like in AOMDV, but A 2 OMDV further selects the first found path as a primary route. This selection is regularly updated using values of Round Trip Time (RTT). Zone-disjoint Ad-hoc On-demand Multi-path Distance Vector (ZD-AOMDV) [START_REF] Javan | ZD-AOMDV: A new routing algorithm for mobile ad-hoc networks[END_REF] computes zone-disjoint routes. It adds a few fields in the RREQs and RREPs used in AODV, and uses additional control packets. This allows each node to estimate how many nodes among its neighbors received a RREQ, and to increment the corresponding parameter (called ActiveNeighbourCount) in the RREQ. The source node waits until it has received several RREPs before sending data packets. Then it selects the routes with the lowest ActiveNeighbourCount to split traffic between disjoint paths.

C. Current Limitations of Multi-path Routing Protocols

Most of the multi-path routing protocols designed for MANET try to establish paths as disjoint as possible at the node level, and only differ in their path selection criteria. Yet, most of the multi-path protocols derived from standard routing protocols optimize hop counts, as they postulate that the shorter the route is, the better, with respect to both latency (each hop increases costs) and fault tolerance (fewer nodes means smaller fault probability). Nevertheless, in a physically deployed MANET, a multi-path routing protocol should not build its solution upon the shortest path nor work at the node level, as this may lead to low quality solutions. As an example, in a given MANET environment with three routes, if the shortest path radio-interferes with the other two paths, traditional multi-path routing protocol algorithms will only give a single path (the shortest path), whereas the two other routes could have been used together and simultaneously, giving additional bandwidth, redundancy and availability.

Moreover, path combination can be computed on three levels: node, link and zone-disjoints. Node (respectively link) disjoint routes have no node (respectively link) in common. In case of zone-disjoint routes, there is no intersection between the global coverages of the selected paths. The first two types can be easily computed and thus are used in most routing protocols in literature. Yet, in physically deployed radio networks, link and node-disjoint algorithms are not sufficient, as two link/node disjoint paths may be geographically close, and generate radio interferences. In such a situation, the multipath solution may perform worse than a single path routing protocol [START_REF] Waharte | Totally disjoint multipath routing in multihop wireless networks[END_REF].

Therefore, an effective multi-path routing protocol for MANETs should not only rely on the shortest path. It should carefully select the most effective and radio-interference-free path combination.

III. A NEW INTERFERENCE-AWARE MULTI-PATH ROUTING PROTOCOL

This section describes NICE-MRP (Non-Interfering Coverage arEa Multi-path Routing Protocol), a new multi-path routing protocol for MANETs. It is a reactive routing protocol working on the zone-disjoint level. NICE-MRP computes several optimal and/or suboptimal sets of zone-disjoint paths to connect two nodes. Zone-disjoint routes reduce the probability of generating interference when multiple paths are used simultaneously. Thus, this approach allows load balancing and a potential increase of the throughput. In addition, NICE-MRP uses two routing tables, which allows the protocol to adapt to topology changes or node / link failure without necessarily sending routing packets.

A. Overview

The classical zone-disjoint algorithms in literature [START_REF] Natarajan | Performance comparison of link, node and zone disjoint multi-path routing strategies and minimum hop single path routing for mobile ad hoc networks[END_REF] use the knowledge of the neighborhood of each node to assess the risk of interference. Usually, the zone-disjoint multipath routing protocols use Hello messages to acquire this knowledge. However, regularly sending such packets generates additional signaling traffic. To limit the consumption of network resources, NICE-MRP does not use Hello packets. The proposed protocol takes advantage of route discovery packets to establish a list of neighbors for each node.

Like any reactive protocol, NICE-MRP is run only when data have to be transferred from a source node (s) to a destination node (d). If s does not have a known route to reach d, it sends a Route REQuest (RREQ) packet. This packet will be relayed exactly once by each intermediate node and will propagate up to the target node (d). Then d will reply by sending one Route REPly (RREP) packet or more. The RREPs will follow the reverse path of the ones used by the RREQs. Upon reception of the first RREP, s will begin sending data packets. When several RREPs are received, s can compute disjoint routes which may be used simultaneously. The computation of the disjoint paths will be detailed in section III-C. The best set of non-interfering routes is stored in the main routing table (called active routing table), while the other disjoint routes are stored in the secondary table (called passive routing table). The latter is not used for routing packets; it is used to cache potentially usable routes (e.g. in case of link failure).

When a path in the active routing table is no longer usable, NICE-MRP looks up alternative non-interfering paths in its passive routing table. If alternative paths are found, they are moved to the active routing table and they replace the previous ones used to reach the same destination. If there is no path to the destination, NICE-MRP tries to discover new routes.

In short, NICE-MRP aims to:

• Determine several sets of non-interfering routes;

• Limit the routing overheads;

• Reduce the end-to-end delay when transfering data;

• Swiftly and efficiently respond to the node / link failures.

B. Route Discovery

The route discovery is the first step of the NICE-MRP protocol. It is made up of two main processes: route request and route reply.

1) Route Request: When s has a packet to send to d and it does not have a route to reach the destination, s sends an RREQ. Each RREQ is uniquely identified by a pair of identifiers: the sequence number of the RREQ and the address of the node originating the RREQ. The header of an RREQ is depicted in Figure 1. The path field contains the list of intermediate nodes between s and d. This list is empty when s issues the RREQ. Then the path field will be updated during the propagation of the RREQ. Each relay node will add its own address in the list of intermediate nodes. This list allows to prevent routing loops and helps to build a return path for sending the reply to this RREQ1 . Since NICE-MRP is a source routing, the list of intermediate nodes is also used by the source node to specify the whole path for data packets (the path will be encapsulated in data packets). To collect as much information as possible regarding the paths (including information about the neighboring nodes) and preserve their reliability, the intermediate nodes are not allowed to reply to RREQs. All this information will be used for computing zone-disjoint paths. However, to limit the number of redundant RREQs and to avoid the broadcast storm problem [START_REF] Ni | The broadcast storm problem in a mobile ad hoc network[END_REF], the intermediate nodes are only allowed to relay the first copy of each RREQ. When an intermediate node receives the first copy of a RREQ, it saves this request in an RREQ cache. Then the node adds its address in the list of intermediates and forwards the RREQ. Upon reception of a redundant copy of an RREQ, the intermediate node ensures that its own address is not already part of the list of intermediates nodes (the path field) to avoid routing loops before saving the RREQ in the RREQ cache.

At the same time as the RREQs are processed, NICE-MRP allows each node to acquire a knowledge of its neighborhood. To reduce the routing overhead, Hello packets are not used. Upon reception of every copy of an RREQ, each node updates its neighbor list by adding the address of the neighbor that transmitted the packet. In order to avoid obsolete entries, a removal timeout mechanism is involved, where a counter decreases over time, and is reinitialized upon reception of a new packet from the same source.

When an RREQ is received by the final destination node, the latter replies by sending an RREP.

2) Route Reply: The intermediate nodes are not allowed to reply to the RREQ packets. Thus, only d is allowed to send an RREP (route reply) packet described in Figure 3. RREP headers are similar to RREQ ones, with two added fields: a route reply sequence number (distinct from the RREQ sequence number) and a list of path-neighboring nodes.

Fig. 3: NICE-MRP RREP header

d replies to all the RREQs by sending a unicast RREP packet with an empty neighbor list. Indeed, the neighbors of the source node (which originates the RREQ) and those of the destination node (which originates the RREP) are not taken into account for the computation of zone-disjoint paths (see Section III-C). d sends an RREP to all its neighbors that have transmitted the RREQ. As shown on Figure 4, each intermediate node which receives the RREP ensures that there is no routing loop in the path (if there is a loop, the RREP is dropped). If there is no loop, the intermediate node updates the message by adding (i) its own address to the path field and (ii) its list of neighbors to the neighbors field. The updated RREP is then forwarded by the intermediate node to its neighbors from which it has received the route request (this list is available in the RREQ cache). The RREP propagates until it is received by s.

C. Computation of Non-Interfering Paths

1) Collecting single routes: Upon reception of the first RREP for a given destination, s saves the path in both its active routing table and its RREP cache. Then s starts sending data. The data are transmitted immediately to reduce the end-to-end delay. s also starts a countdown. During that time, s might receive other RREPs (each of them representing a different path) which will also be recorded in the local RREP cache. Fig. 4: NICE-MRP RREP processing algorithm Thus, at the end of countdown, s has the local knowledge of all the available routes between s and d. Moreover, RREP packets also give information on neighboring nodes via the neighbors field. When the cuntdown expires, s computes the multi-path routes as described in the next section.

2) Computing multi-path routes: Using the RREP cache, s is able to compute zone-disjoint multi-path routes. For each p path to the destination d in the RREP cache, the algorithm used by NICE-MRP for computing multi-path routes selects only mutually non-interfering paths. This set of paths built from p should have no common intermediate node or neighborhood. Indeed, single routes may be combined into a multi-path route if their paths have no common node with (i) the other paths and (ii) the union of the neighboring nodes from all the paths.

Once all sets of non-interfering multi-path are computed, the best set is chosen to replace the route recorded in the active routing table. The other sets are recorded in the passive routing table for later use (e.g. in case of path failure). A common sorting strategy for multi-path routing is the size of the set of paths (i.e., the more paths in the route, the better). In the basic version of NICE MRP, the multi-path sets are classified according to the number of paths they contain. Some other criteria may be used, including the available bandwidth or an energy-based criterion. Another efficient strategy makes use of the expected transmission count (ETX) metric [START_REF] De Couto | A highthroughput path metric for multi-hop wireless routing[END_REF]. The ETX metric is a measure of the quality of a path between two nodes in a wireless network (i.e., the number of expected transmissions necessary to send a data packet to a destination without error). In a multi-hop wireless network, the ETX is the sum of all the ETX on the path. Thus, path sorting may be refined with respect to the ETX. Whatever the criteria used, this has no significant impact on the non-interfering multipath selection algorithm. But some particular criteria could be used to ensure the fulfillment of quality of service. The results presented in this paper are obtained using the basic criterion, i.e. the number of non-interfering paths.

Unlike the classical methods for computing disjoint routes which define a single set of disjoint paths (often based on the first path which is discovered), NICE-MRP takes into account Fig. 5: Protocol reconfiguration scenario all the route replies (RREPs). This increases the probability of getting non-interfering multi-path. Since the computation of non-interfering paths is done after the beginning of data transfer, it does not increase the end-to-end delay. For the purpose of optimization, and when the node architecture allows it, the algorithm of non-interfering paths can be parallelized (RREP cache entries are mutually independent).

In short, the algorithm of disjoint paths used by NICE-MRP does not depend on the first path discovered, but all the received RREPs.

D. Maintenance Strategies

Over time, routing protocols need periodic maintenance as several factors may influence the quality of the active route, or even render it useless. Node failure is a common cause, even if it will not happen too often. Nowadays, the miniaturization of the mobile devices used in MANETs increases the frequency of node mobility, which further generates frequent link disruptions. Therefore, a routing protocol suitable for adhoc networks should critically take care of mobility tolerance and reconfiguration after link loss.

To illustrate the mechanism used in NICE-MRP, an example scenario of link failure caused by source mobility is depicted in figure 5. In this environment, routing paths must be chosen between two similar zone-disjoint multi-path solutions: "r1 → r5" + "r3 → r6" and "r2 → r5" + "r4 → r6". Figure 5(a) shows that "r1 → r5" + "r3 → r6" where chosen, and communication is balanced over these two paths. In Figure 5(b), the source node s moves south, going out of r1's range. However, as it is a multi-path route and r3 is still in the range of s, the communication doesn't cease, but its quality decreases. Before declaring r1 as lost, s will try to initiate three re-acknowledgments. If necessary, the active routing table is updated accordingly. This is the same mechanism as the one used in the case of hardware failure.

As long as one path is still available, the communication still progresses in a degraded mode. NICE-MRP will maintain the remaining paths and try to add further paths to the active route. That is, s parses its passive routing cache to find previously recorded multi-path routes containing r3, while not containing r1. Simultaneously, all the records containing r1 are removed. In our example, there is no other solution containing r3 without r1. Later, the passive routing table is browsed again, to try to find a better solution than the currently active one, even if a more important change in topology has to occur. This is depicted in Figure 5(c), where the communication via r3 is stopped to initiate the new multipath solution: "r2 → r5" + "r4 → r6". The active routing table must be updated accordingly.

IV. PERFORMANCE EVALUATION OF NICE-MRP

This section describes the performance evaluation of NICE-MRP, and a comparison with another multi-path routing protocol (SMR). These evaluations were conducted with the ns-2 network simulator [START_REF]The Network Simulator Project -ns-2[END_REF]. NICE-MRP is compared with two different versions of SMR : SMR with link disjoint algorithm (SMR ld) and SMR with node disjoint algorithm (SMR nd) [START_REF] Parissidis | Multi-path routing protocols in wireless mobile ad hoc networks: A quantitative comparison[END_REF].

A. Experimental procedure

The simulated network contains 30 nodes with a radio range limited to 250 meters. The nodes move in a 1000 m x 300 m area during 900 seconds. The mobility model is random waypoint with a pause time varying from 0 to 900 seconds: 0 means permanent mobility while 900 means no mobility. All nodes have the same pause time value during a simulation run. The nodes are first randomly placed on the grid, which is the studied area. They remain in these positions until the end of the pause time, then each node chooses a random destination point and tries to reach it with uniformly distributed speed chosen between 0 and 10 m.s -1 . Once the destination is reached, the node remains stationary for a period of pause time seconds before choosing a new destination. This is repeated until the end of the simulation (duration 900 seconds). Among the 30 nodes, 10 pairs are randomly chosen to exchange data packets. The traffic is modeled with a CBR (Constant Bit Rate) stream, sending data at a rate of 4 packets (512 bytes) persecond.

B. Performance metrics

Three widely used metrics were chosen to assess the performance of each protocol: end-to-end delay, packet loss rate and routing overhead.

• End-to-end delay is the packet transmission time. It begins once a packet is sent by upper layers and ends when the packet is received by the destination's corresponding layers. So, it includes route discovery time, the waiting time due to the WiFi MAC layer standard (including the backoff algorithm), the packet propagation time on the radio channel, the packet buffering and reordering (if required by the routing protocol) time. • Packet loss rate. A packet is considered to be lost when a data packet sent on the radio channel earlier has not been received by the final destination. For each pair "sourcedestination", packet loss rate is the ratio of lost packets to the total number of packets sent. • Routing overhead is the number of packets generated and transmitted by the routing protocol to fulfill its own purposes. Any routing information is taken into account, without discriminating sent packets from relayed packets. NICE-MRP was compared with SMR, as regards the simulation results published by Parissidis et al. [START_REF] Parissidis | Multi-path routing protocols in wireless mobile ad hoc networks: A quantitative comparison[END_REF], so the simulations were carried out in the same experimental conditions.

Overall, NICE-MRP has lower latency than the two versions of SMR (Figure 6). This can be explained by the fast dissemination of requests for NICE-MRP. Since each node retransmits each RREQ only once, the radio channel availability is increased and the dissemination of route discovery packets is faster. One can also note that higher mobility (i.e., low pause time) increases latency. This is because of the fact that when nodes move, some of the links break. Routing protocols require a slight reaction time to rediscover new routes or switch to the backup routes.

Regarding packet loss (Figure 7), NICE-MRP has an almost constant rate because it dynamically updates its main route table (active route table) before all routes break, as described in Section III-D.

For SMR nd and SMR ld, when loss rate increases, a peak of routing packets is observed (Figure 8). Packet losses trigger the sending of new route discovery packets. NICE-MRP, using two route tables, more rarely executes its route discovery process. Indeed, when the routes of the active table are broken, the protocol looks for alternative routes in the passive table.

V. CONCLUSION

This paper assessed a new efficient strategy to identify multi-paths in wireless network. The results show that NICE-MRP reacts faster than SMR in case of link loss. Our contribution will allow to identify multi-paths without radio interference between nodes of different paths with common source and destination. This property is necessary to potentially improve overall bandwidth between two nodes that are using more than one path simultaneously.

Fig. 1 :Fig. 2 :

 12 Fig. 1: NICE-MRP RREQ header

  Fig. 6: End-to-end delay

It is assumed in this paper that the links are symmetric


Jacques M Bahi
email: jacques.bahi@femto-st.fr

Jean-Franc ¸ois Couchot
email: jean-francois.couchot@femto-st.fr

Nicolas Friot
email: nicolas.friot@femto-st.fr

Christophe Guyeux
email: christophe.guyeux@femto-st.fr

Kamel Mazouzi
email: kamel.mazouzi@univ-fcomte.fr

Quality Studies of an Invisible Chaos-Based Watermarking Scheme with Message Extraction

Keywords: Invisible Watermarking, Chaos, Robustness, Correct and Complete message extraction

This paper takes place in the field of invisible chaos-based watermarking schemes. It addresses the quality study of an already pyblished algorithm by focusing on three class of properties. Its robustness is experimentally shown against classical attacks on a large set of image instances and image transformations. It correctness and completness are formally proven. Due to this main advantages, this process is fitted for practical use.

Recently, chaos has become an usual technique to define schemes used for encryption or watermarking [START_REF] Dawei | A chaosbased robust wavelet-domain watermarking algorithm[END_REF], [START_REF] Yantao | A robust chaosbased dct-domain watermarking algorithm[END_REF]. In this context, embedded watermarks can be either visible or invisible. In the former case, the mark overlays the image host and is thus visible. In the later case, the mark is embedded in such a way that the differences between the original host and the watermarked one are perceptually unnoticeable.

Our invisible chaos-based watermarking scheme proposed in this research work uses such kind of techniques. It is an extension of a previously released information hiding method [START_REF] Friot | Chaotic iterations for steganography -stego-security and chaos-security[END_REF] initialy used for steganography, and adapted here in a watermarking framework in the direction of quality analysis. Its robustness facing geometrical attacks and signal processing is studied.

The remainder of this document is organized as follows. In Section I, the watermarking scheme is given. Furthermore, the correctness and the completeness of the approach has been proven. This is the first contribution of the paper. Then, in Section II, the robustness of CI is studied facing geometrical and signal processing attacks through a large number of experiments. This is the second contribution. The documents ends with a conclusion section, where our contribution is summarized and intended future researches are presented.

I. THE INFORMATION HIDING SCHEME CI

This section recalls basics of CI formerly defined in [START_REF] Friot | Chaotic iterations for steganography -stego-security and chaos-security[END_REF]. The set of all k-strategies is furthere denoted as to S k . For k ∈ N * , a k-strategy is a sequence which elements belong into 0, k -1 . The term "strategy" will be used instead of k-strategy when the context will easily allow to recover k. The following notations are also used in the sequel: 0; N = {0, 1, . . . , N }, B = {0, 1}, S n denotes the n th term of a sequence S, and V i is for the i th component of a vector V .

A. Notations used for CI

• x 0 ∈ B N is the representation of the chosen Least Significant Coefficients (LSCs) of a given host media where the watermark will be embedded. They are expressed as a vector of N Boolean values. In this work and in experimentations, x 0 is defined as the Least Significat Bits (LSBs) of the host content, since we want the scheme to produce an invisible watermark. • m 0 ∈ B P is the watermark message to embed into x 0 . This is a vector of P Boolean values. This sequence gives which element of the watermark is switched at each iteration. In what follows, x 0 and m 0 are sometimes replaced by x and m for the sake of brevity, when such abridge does not introduce confusion.

B. The CI scheme

With this material and for all (n, i, j) in N * × 0; N -1 × 0; P -1 , the CI process is defined by:

                 x n i = x n-1 i if S n p = i m n-1 S n c if S n p = i. m n j =    m n-1 j if S n m = j m n-1 j if S n m = j.
where m n-1 j is the Boolean negation of m n-1 j . The stegocontent is the Boolean vector y = x l ∈ B N provided the following constraints are applied:

1) The number l of iterations is sufficiently large (see details below). 2) Let ℑ(S p ) be the set {S 1 p , S 2 p , . . . , S l p } of cardinality k, k ≤ l (repetitions are removed in a set). This set contains all the elements of x that have been modified along the iteration process. Let us consider ℑ(S c ) |D defined by {S d1 c , S d2 c , . . . , S d k c } where d i is the last iteration that has modified the element i ∈ ℑ(S p ). We require that this set is equal to 0; P -1 .

Let us discuss the constraints given above. The first one implies that the number of iterations is greater than a given threshold. This requirement has both practical and theoretical reasons. Theoretically speaking, the ability to successfully pass statistical tests is directly linked to this number of iterations. And, in practice, this value is bounded by the size of the host content. The second constrain, for its part, addresses the method's completeness and correctness, as detailed below.

C. Correctness and Completeness Studies

Without attack, the scheme has to ensure that the user can always extract a message and that this latter is the watermark, provided the user has the correct keys. These two demands correspond respectively to the study of completeness and of correctness for the proposed approach. To achieve this study, let us firstly prove the following assessment.

Proposition 1: In section I-B, item 2 is a necessary and sufficient condition to allow message to be extracted from the host.

Proof: For sufficiency, let d i be the last iteration (date) the element i ∈ ℑ(S p ) of x has been modified:

d i = max{j|S j p = i}. Let D = {d i |i ∈ ℑ(S p )}. The set ℑ(S c ) |D is thus the restriction of the image of S c to D.
The host that results from this iteration scheme is thus (x l 0 , . . . , x l N-1 ) where x l i is either x di i if i belongs to ℑ(S p ) or x 0 i otherwise. Moreover, for each i ∈ ℑ(S p ), the element

x di i is equal to m di-1 S d i c
. Thanks to constraint 2, all the indexes j ∈ 0; P -1 belong to ℑ(S c ) |D . Let then j ∈ 0; P -1 s.t. S di c = j. Thus we have all the elements m . j of the vector m. Let us focus now on some m di-1 j . Thus the value of m 0 j can be immediately deduced by counting in S c how many times the component j has been switched before d i -1.

Let us focus now on necessity. If ℑ(S c ) |D 0; P -1 , there exist a j ∈ 0; P -1 that does not belong to ℑ(S c ) |ℑ(Sp) . Thus m j is not present in x l and the message cannot be extracted.

When the constraint 2 is satisfied, we obtain a scheme that always finds the original message provided the watermarked media has not been modified. In that context, correctness and completeness are established.

Thanks to constraint 2, the cardinality k of ℑ(S p ) is larger than P. Otherwise the cardinality of D would be smaller than P and similar to the cardinality of ℑ(S c ) |D , which is contradictory.

One bit of index j of the original message m 0 is thus embedded at least twice in x l . By counting the number of times this bit has been switched in S m , the value of m j can be deduced in many places. Without attack, all these values are equal and the message is immediately obtained. After an attack, the value of m j is obtained as mean value of all its occurrences. The scheme is thus complete. Notice that if the cover is not attacked, the returned message is always equal to the original due to the definition of the mean function.

D. Deciding whether a Media is Watermarked

Let us consider a media y that is watermarked with a message m. Let us consider y ′ that is an altered version of y, i.e., where some bits have been modified. Let m ′ be the message that is extracted from y ′ .

Let us now check how far the extracted message m ′ is from m. To achieve this, let us consider M = {i|m i = 1} of the Boolean vector message m and similarly the set M ′ for the message m ′ . Most of similarity measures depend on the functions a, b, c, and d, all from B P × B P to N, and respectively equal to a(m, m According to [START_REF] Rifqi | Discrimination power of measures of resemblance[END_REF] the Fermi-Dirac measure M FD is the one that has higher discrimination power, i.e., which allows a clear separation between correlated vectors and uncorrelated ones. The measure is recalled hereafter with respect to the previously defined scalars a, b, and c.

′ ) = |M ∩ M ′ |, b(m, m ′ ) = |M \ M ′ |, c(m, m ′ ) = |M ′ \ M |,
M FD (ϕ) = F FD (ϕ) -F FD ( π 2 ) F FD (0) -F FD ( π 2 ) , F FD (ϕ) = 1 1 + exp( ϕ -ϕ 0 γ )
, where ϕ = arctan( b + c a ), ϕ 0 is π/4, and γ is 0.1. The distance between m and m ′ is then computed as 1 -M FD (m, m ′ ) and is thus a real number in [0; 1]. The Table I gives an example of the relation between modified watermarked and the computed distance. If such a distance is behind a threshold, y ′ will be declared as watermarked and not watermarked otherwise. Next section presents a practical evaluation of this approach.

II. ROBUSTNESS STUDY OF CI

This section is devoted to the robustness study of our scheme. This one has to ensure that the watermark withstands against different types of active attacks that modify the watermarked image.

For the whole experiment, a set of 100 images is randomly extracted from the database taken from the BOSS contest [START_REF] Bas | break our steganographic system": The ins and outs of organizing boss[END_REF]. In this set, each cover is a 512 × 512 grayscale digital image. The considered watermark m is given in Table I. Testing the robustness of the approach is achieved by successively applying on watermarked images attacks like cropping, compression, geometric transformations,. . . Remark 1: On the following figures, the difference percentage corresponds to the distance between the retrieved and the original watermarks.

Robustness of the approach is evaluated by applying different percentages of cropping: from 0.25% to 90%. Results are given in Fig. 1, which presents effects of such an attack. All the percentage differences are so far less than 97% and thus robustness is established. Robustness against compression is addressed by studying both JPEG and JPEG 2000 image compression. Results are respectively presented in Fig. 2(a) and Fig. 2(b). It is not hard to see that robustness is well established for JPEG2000 compression: for all the ratio larger than 10%, the watermark is retrieved. However, our scheme is not robust against JPEG compression for a ratio inferior to 90%.

A potential solution in order to improve this result should be to insert the watermark in least significant coefficient of the image described in frequency domain as for example with discrete cosine transform or with wavelet transform. This study will be described in future works. Among geometric transformations, we focus on rotations, i.e., when two opposite rotations of angle θ are successively applied around the center of the image. In these geometric transformations, angles range from 2 to 60 degrees. Results are presented in Fig. 3. Thanks to an efficient embedding, our scheme is resistant to all these types of attacks. Let us first recall that this scheme has defined x as the LSBs of the host and is thus based on LSBs modifications. This part focuses on two types of attacks modifying these set of LSBs (see Fig 4). The former consists in setting to zero a subset of this one. Results are expressed in Fig. 4(a) and show that the scheme is robust, unless 95% of the LSBs is erased. In this case the image is really damaged. The latter consists in applying again this scheme on the watermarked image but with another message. Results of Fig. 4(b) show that this scheme is robust against that type of attack, provided the number of iterations is lesser than 1.75 times the number of pixels. With more iterations, the image is dramatically modified: more than 50% of the LSB is switched. Finally a receiver Operating Characteristic approach has been implemented to find the most adapted threshold w.r.t. the separation between watermarked images and other ones.

The Figure 5 is the Receiver Operating Characteristic (ROC) curve. This curve is close to the ideal one that is without False Positive and False Negative answer. The threshold with best results is a distance equal to 0,97. With such a value, we can give some confidence intervals for most of evaluated attacks. The approach is resistant to all the cropping where percentage is less than 90, to JPEG200 compression where quality ratio is greater than 5%, to all the rotation attacks, to LSB erasing when less than 95% are set to 0, a second application of the scheme with less than 1.75 iterations per pixel.

III. CONCLUSION AND FUTURE WORK

In this research work, a complete quality study of our scheme [START_REF] Friot | Chaotic iterations for steganography -stego-security and chaos-security[END_REF] has been given, namely robustness, completness, and correctness. This scheme is now ready for practical use.

To improve again the robustness, notice that the definition of x can be changed as follows: at worst, any process which always returns the same set of bits for a given image would return an amanable vector. However, the most fine would be the set of bits whose modifications minimize a distortion function. Following such idea we plan to combine this bit selection step with feature extraction function. We are aware that in the field of information hiding it is known that embedding in LSBs is not a good choice. They are used in this work in order to validate the concept which remains valid with an other choice. So in future work these better choice will be explored.

  and d(m, m ′ ) = |M ∩ M ′ | (|Γ| and Γ respectively denote the cardinality and the complementary of any set Γ). In what follows a, b, c, and d respectively stand for a(m, m ′ ), b(m, m ′ ), c(m, m ′ ), and d(m, m ′ ).

Figure 1 .

 1 Figure 1. Cropping Results

Figure 2 .

 2 Figure 2. Compression Results

Figure 3 .

 3 Figure 3. Rotation Attack Results

  (a) LSB Erasing Effect (b) Applying Algorithm twice

Figure 4 .

 4 Figure 4. LSB Modifications

Figure 5 .

 5 Figure 5. ROC Curves for DWT or DCT Embeddings

  • S p ∈ S N is a strategy called place strategy. Lastly, S m ∈ S P is a strategy called mixing strategy.

	Intuitively,
	this sequence defines which element of x is modified
	at each iteration.
	• S c ∈ S P is a strategy called choice strategy. It defines
	which element of the watermark is embedded at each
	iteration.

•