Guillaume Artignan
email: artignan@lirmm.fr

Mountaz Hascoët
email: mountaz@lirmm.fr

STOOG: STYLE-SHEETS-BASED TOOLKIT FOR GRAPH VISUALIZATION STOOG: STYLE-SHEETS-BASED TOOLKIT FOR GRAPH VISUALIZATION

Keywords: Graph Visualization, Style sheets, Simple Clustered Graphs, Multivariate Graphs

The information visualization process can be described as a set of transformations applied to raw data to produce interactive graphical representations of information for end-users. A challenge in information visualization is to provide flexible and powerful ways of describing and controlling this process. Most work in this domain address the problem at either application level or toolkit level. Approaches at the toolkit level are devoted to developers while approaches at the application level are devoted to end-users. Our approach build on previous work but goes one step beyond by proposing a unifying view of this process that can be used by both developers and end-users. Our contribution is a system named STOOG with a three-fold contribution: (1) a style-sheets based language for the explicit description of the transformation process at stake in information visualization, (2) an application that automatically builds interactive and graphical visualization of data based on style-sheet descriptions, (3) a user interface devoted to the conception of style sheets. In this paper, we present STOOG basic concepts and mechanisms and provide a case study to illustrate the benefits of using STOOG for the interactive and visual exploration of information.

INTRODUCTION

Over the past years, the visualization process has been described as a set of transformations that applies to data to produce interactive graphical representations. Several models including dataflow model (Card et al. 1999) can be used to describe these transformations. A large amount of systems are based on the data flow model. In (Card et al. 1999[START_REF] Baudel | Canonical Representation of Data-Linear Visualization Algorithms and its Applications[END_REF]) information visualization takes as input one or more data tables. In [START_REF] Heer | prefuse: a toolkit for interactive information visualization[END_REF] raw data is transformed to abstract data composed of entities: nodes or edges.

More precisely, we are interested in data represented by clustered graphs and multivariate graphs. A multivariate graphs is a graph where each data element, node or edge, is associated to several attributes. A simple clustered graph is a graph where each node is associated to a group named cluster. Fig. 1 shows a sample of a simple clustered and multivariate graph.

We define a dataset as a set of data elements. In our case of simple clustered graphs, data elements are either nodes, edges or clusters. We define a graphical representation as the view displayed on the computer screen. We name the coding function the description of transformations that produce graphical representations of non graphic data by, taking as input both datasets and user interactions and coding functions. The rational for these coding function has its origins in the seminal work of Bertin [START_REF] Bertin | La graphique et le traitement graphique de l'information[END_REF] on the semiology of graphics. General purpose toolkits for information visualization such as Prefuse [START_REF] Heer | prefuse: a toolkit for interactive information visualization[END_REF]) make coding function key elements for the developers eager to build interactive visualizations of information. Other approaches for building visualization such as interpreted languages like DOT (Gansner and North 2000) for example handle coding as the basis for building views.

Most approaches comes with different characterizations of these coding functions at stake. By building on previous work, our aim in this paper is to provide a powerful and flexible way for the description of coding functions for information visualization of multivariate clustered graphs both at the level of the developer or at the level of the enduser.

Our approach is a to propose a system named STOOG with a three-fold contribution: (1) a stylesheet based language for the explicit description of coding functions, (2) an application that automatically builds interactive and graphical views from on STOOG style-sheet based on coding descriptions and raw data, (3) a user interface aimed at end-users to support the conception and generation of coding functions.

The mix of the three contributions is important in order to bridge the gap between usually two complementary yet separated approaches: one the one hand the toolkit approach devoted to developers and on the other hand the application approach devoted to end-user. It is important to stress that bridging the gap between these two approaches is important to gain in flexibility and expressivity for the end-user and at the same time save efforts and development time for the developers.

In this regard, our approach compares to the approach of Tableau Sotware (Hanrahan, 2007) project (http://www.tableausoftware.com/). The main differences between their approach and our contribution lies in the fact that we consider multilevel graphs as the basis for representing data and that we propose to make the style-sheet language that describes the coding functions both explicit and open.

Hence, STOOG presents several strengths over existing work. Firstly, the high level language makes semiotic analysis possible thanks to the manipulation of abstract concepts. Secondly, STOOG interprets the description language and builds an interactive visualization of any data set accordingly. Thirdly, the user interface makes dynamic customizations of existing representation possible and easy.

The style-sheet based language of STOOG enables the manipulation of high level concepts such as graphical representations, graphical structures or properties by the user. Four mechanisms are proposed in this language: (1) the matching mechanism which makes possible the association of one or more representations to a set of data elements, (2) the coding mechanism corresponding to the association of data attributes and visual variables,

(3) the cascading mechanism implementing the inheritance of properties and structures and (4) the interaction mechanism defining the representation of data during the interaction.

It is important to stress that these mechanisms were meant to be coherent with other approaches where form are explicitly described independently of its content such as in HTML/CSS or XML/XSLT approaches but our approach is STOOG is different and more general because the data handled in STOOG is not limited to HTML/XML documents. Indeed, STOOG handles any raw data set. Another analogy with STOOG style sheets can be found in SVG stylesheets but here again, SVG style sheets are limited to SVG documents. They do not handle the coding functions for any set of multivariate and clustered data as is the case of STOOG.

STOOG is implemented using Java and supports the generation of views from raw data and coding functions. It further supports the rendering and interaction with these views. Moreover, if useful, extending STOOG style-sheet based language can be performed by a developper to account for more specific types of coding. STOOG is available for download on the web and directly reusable in any Java application.

This paper is divided in five sections. We firstly present related works. Secondly, we define STOOG style sheet language, the concepts and the mechanisms to handle these concepts. Thirdly, we present STOOG throught a use case. Fourthly we expose the user interface devoted to the conception and generation of style sheets for end-users. We then conclude and discuss future work.

RELATED WORK

Over the past year, several approaches have demonstrated the importance of providing adapted tools for data visualization. We detail previous work on tools for data visualization and situate our contribution in the domain.

Visualization Tools

Jeffrey Heer has shown in [START_REF] Heer | prefuse: a toolkit for interactive information visualization[END_REF]) the interest of providing toolkits for interactive visualization of information. One of the first toolkit that he proposed called Prefuse, transforms raw data to abstract data and, thanks to actions, further transforms abstract data to visual items. The visual items are finally drawn thanks to renderers. The toolkit is used by a lot of visualization application that build on top of Prefuse for visualizaing data in various domains: graph community visualization [START_REF] Perer | Balancing Systematic and Flexible Exploration of Social Networks[END_REF], lexical visualization [START_REF] Collins | DocuBurst: Document Content Visualization Using Language Structure[END_REF], cartographic visualization (Phan et al. 05), collaborative visualization [START_REF] Heer | Voyagers and voyeurs: supporting asynchronous collaborative information visualization[END_REF] etc.

In [START_REF] Adar | GUESS: a language and interface for graph exploration[END_REF]) Guess is another system devoted to graph visualization. Guess highlights the need to have interfaces for customizing rendering by visual attributes. The graph rendering is determined by the user thanks to queries. These queries are written in Gython an extension of the Jython system (a Java interpreter for the Python language). The tool supports generation of charts, computation of convex hulls. Selection of data elements helped on data values criterion or topology criterion.

In GraphViz (Gansner and North 2000) authors present the DOT language that supports the generation of views. Graphs are first described in a file using DOT language, the file is further interpreted by GraphViz which gives the rendering and layout. The DOT language is used mainly for its simplicity.

The Protovis toolkit (Bostock and Heer 09) builds upon lessons learned from Prefuse and proposes visualization by composing simple graphical marks. Protovis is implemented in JavaScript with rendering in HTML, SVG and Flash. The Protovis toolkit constitutes an excellent way to produce aesthetic charts for websites.

In (Mackinlay et al. 07) ShowMe is described as a set of user interface commands for the automatic generation of presentations. Presentations are further integrated into Tableau Software. Views are specified in an algebraic language: the VizQL language. In (Cammarano et al. 07) the authors propose an automatic technique for the visualization of heterogeneous data. The authors are more precisely interested to match data attributes to visualization attributes. The authors use the RDF format.

In [START_REF] Pietriga | Semantic web data visualization with graph style sheets[END_REF]) the GSS language is presented Graph Style Sheet language for semantic web data visualization. The system offers visualization of RDF data as a directed labeled graph. The author introduces the idea of using style sheets for graph visualization.

Cascading style sheets (W3C 2006) are used for the presentation of HTML documents but also used in languages as Flex [START_REF] Kazoun | Programming Flex 2: the Comprehensive Guide to Creating Rich Media Applications with Adobe Flex[END_REF] or in formats as SVG [START_REF] Eisenberg | An open graph visualization system and its applications to software engineering[END_REF].

In [START_REF] Baudel | Browsing through an information visualization design space[END_REF]) the ILOG Discovery tool is proposed. The tool proposes the description of interactive charts using style sheets. The tool is based on model defined in [START_REF] Baudel | Canonical Representation of Data-Linear Visualization Algorithms and its Applications[END_REF]. The model is declarative and defines fixed dataflow architecture.

Our contribution

In this section we situate our contribution amongst the previously detailed contributions. Over the past decades several toolkits such as Prefuse or Guess [START_REF] Heer | prefuse: a toolkit for interactive information visualization[END_REF][START_REF] Adar | GUESS: a language and interface for graph exploration[END_REF][START_REF] Bostock | Protovis: A Graphical Toolkit for Visualization[END_REF]) have provided very thoughtful ways of describing coding functions.

Most toolkit provide flexible and powerful ways of describing coding but their usage is devoted to developers not end-users. Therefore to suit the needs of end-users, applications have to be developed for different application context and users. Even if these new toolkits help a lot, this is still very time consuming for developers and frustrating for end-users. Indeed, our own experiments with end-users shows that the key object of interest for many end-users is the coding functions.

However, lots of visualization applications provide less control over these functions to the end-users than what is possible at the toolkit level.

Therefore our contribution is to build on previous work to provide both end-users and developers with ways of understanding and expressing coding functions.

STOOG can be used to generate views pluggable in other applications or web sites. The view is initialized by two parameters: graph data and a style sheet. The aim of the style sheet is to describe the coding functions.

Style-sheet concepts are easy to understand and use for both end-users and programmers. STOOG style sheets can be created and changed on the fly by end-users. STOOG can either be used as a STOOG standalone application by end-users or be integrated in other applications by developers. The style-sheet language definition of STOOG can also be extended by developers.

Contrary to toolkits where coding is implemented in the code, like in Prefuse [START_REF] Heer | prefuse: a toolkit for interactive information visualization[END_REF], the style-sheet approach makes it possible to handle different encoding without recompiling applications. We also propose a representation based on the composition of graphical representations or shapes. In the system proposed in [START_REF] Adar | GUESS: a language and interface for graph exploration[END_REF]), the only shape can be associated to each data element.

In [START_REF] Bostock | Protovis: A Graphical Toolkit for Visualization[END_REF][START_REF] Baudel | Canonical Representation of Data-Linear Visualization Algorithms and its Applications[END_REF]) the systems proposed are dedicated to data visualization and more precisely to charts.

Contrary to [START_REF] Eisenberg | An open graph visualization system and its applications to software engineering[END_REF], we propose dynamic links between data attribute and visual variables. We also use a mechanism selecting a subset of data elements and associating a graphical representation.

The approach by Pietriga on graph style sheets (GSS) [START_REF] Pietriga | Semantic web data visualization with graph style sheets[END_REF]) can be considered as very similar to our approach. However, there are several differences that justifies in our contribution. We firstly propose to account for interaction in coding function rather than static coding. Secondly, we are not limited to a set of predefined shapes, STOOG supports the composition of shapes. Thirdly, the data managed in [START_REF] Pietriga | Semantic web data visualization with graph style sheets[END_REF]) are RDF databases which can be represented by a simple labeled graph. We also consider more general models of clustered graph and multivariate graphs. Fourthly, our proposed toolkit is pluggable in a web browser or an existing application. Lastly, we have implemented the cascading mechanism proposed in CSS for our style sheets. Moreover, we have improved the mechanism by adding cascading of graphical representations.

STYLE SHEET LANGUAGE

In [START_REF] Bertin | La graphique et le traitement graphique de l'information[END_REF], Bertin outlines six visual variables: shape, size, value, grain, color and orientation. Similarly, our style sheet language makes the definition of visual variable possible thanks to concepts such as graphical representations, graphical structures and attributes. In this section, we outline the four core mechanisms that we found useful for STOOG style-sheets: matching, coding, cascading and interaction. These mechanisms enables the association between data and visual variables.

Basic Principles

A style sheet describes graphical representations. Each representation is associated to a class of data elements. In the precise case of graphs, data elements are Nodes, Edges or Clusters.

An important difference between our approach and other approaches like [START_REF] Adar | GUESS: a language and interface for graph exploration[END_REF] is the possibility of composing data element representations with graphical structures. Graphical structures are defined by attributes. Each attribute is associated to a list of values.

In order to illustrate our discussion, we present a style sheet sample (Fig. 2) applied on the graph (Fig. 1) and the associated generated visualization (Fig. 3). The Fig. 1 presents visits of websites by internet users. We decide to represent internet users and websites by labeled nodes visits and references by labeled edges. Fig. 3 presents the result after the application of the style sheet. Internet users are represented by a schematic person. Internet websites are represented by thumbs. Visits are represented by links in blue, the thickness is proportional with the time spent by a given user on a given website. References are represented by links in green. Internet users in pink have an IP address beginning by '184.188'. In this style sheet language, edges can be linked to any structure. When the creation of an edge representation is done we must specify the name of the source port and the name of the target port for binding the edge representation. The name is given by the anchor-name property.

This section has shown how to define graphical representations. We are now interested in the four proposed mechanisms: coding mechanism, matching mechanism, cascading mechanism and interaction mechanism.

Figure 3: A simple sample of transformed graph using a style sheet.

Coding Mechanism

The coding mechanism consists in defining how data attributes are represented by visual attributes. Each visual attribute value is described by an expression. An expression can be:

-a constant, -a data attribute or -a binary operation with two operands themselves expressions, -an arithmetic function parameterized by expressions.

Fig. 4 shows the grammar for arithmetic expression, an example of accepted expression and the associated abstract syntax tree.

Matching Mechanism

The matching mechanism consists in associating a set of data elements (i.e. nodes, edges or clusters) to a set of representations. The associated elements are selected thanks to Boolean expressions. If a Boolean expression is satisfied, we associate a given representation to a set of selected data elements.

A Boolean expression can be -a constant (True or False), -an operator (Not, And, Or) with for each operand a Boolean expression, -a comparison (<=, <, >, >=, <>) composed of two compared expressions cf. Fig 4, -an operator testing the existence of an attribute given as a parameter. The Fig. 5 presents the followed grammar for Boolean expression, an example of accepted Boolean expression and the associated abstract syntax tree. The cascading of a set of N representations is done by a successive cascade of one representation after another. Fig. 6 depicts the cascading done during the rendering of the view (Fig. 3).

Interaction Mechanism

The interaction mechanism corresponds to the modification of the representation during the interaction. For each possible interaction we select data elements thanks to Boolean expressions. We affect to these previously selected data elements a new representation. Some interactions are not fully compatible the cascading mechanism as explained in the previous section. We use the notion of dynamic cascading. Dynamic cascading does not replace the previous representation by a new representation but cascade it. In the precise case of interaction as the selection interaction we want sometimes to add a colored filter in order to mean that the data element is selected. The dynamic cascading makes this modification possible without knowing in advance the previous representation. This kind of cascading is implemented only for the selection of elements. Dynamic cascading proved to be very useful and might extend to other situations. Therefore, we plan to support it in a more general way in future versions of the system. We would then add a keyword in future version in order to explicit the type of cascading desired.

GRAPH VIEWER

In this section, we present the viewer which is the part of STOOG responsible for rendering. The viewer is implemented in Java. Hence the viewer can be pluggable in any web browser supporting applets. This section is divided in three parts. Firstly, we present the properties of the viewer. Secondly, we expose the simplest interactions. Lastly, through a use case, we present advanced interactions.

Properties

The viewer is decomposable in three parts: the parser transforming style sheets on a syntax tree, the interpreter transforming this syntax tree on the structured model, the renderer displaying elements on the screen.

The parsing process is implemented using the SableCC tool. It is a compiler compiler taking in parameter a grammar and generating the Java parser for this grammar. This parser is used to create the abstract syntax trees of ours style sheets.

The interpreter takes the graph structure underlying the data to display as a parameter and the abstract syntax tree issued from the graph style sheet. It transforms the abstract syntax tree in a graphical representation model and associates each data element to a graphical representation. The renderer generates the interactive visualization on the screen in relation with the model. It is in charge of: drawing the graph, modifying the representations during the user interaction, and displaying animations such as layout algorithms or zoom.

The most important aspects of our style sheet graph viewer are its extensible capacities. The tool supports dynamic management of structures. Structures are imported dynamically using the Java introspection. Each structure must determine the attributes available and its own rendering. The Figure 6: A sample illustrate cascading mechanism arithmetic and Boolean functions, available in expression, are dynamic and improvable by specifying the classes containing the functions. A developer can therefore determine new kinds of structures. For instance, we can imagine structures using internet such as the structure URL (Fig. 2) which creates a thumb of web site.

Simple Usage

A simple way to use our viewer is in the applet functionality. Indeed, the toolkit is pluggable in a web browser as an applet parameterized by two parameters: the graph to display, the graph stylesheet to use. Other optional parameters are available as the layout. During the execution both style sheets and graph can be changed on-the-fly using drag and drop.

Advanced Usages

We present in this part the use of STOOG through a project. This project aims to study user classification of documents. Each user creates this own database of web documents. The documents are in relationship thanks to a similarity function parameterized by two documents and given a score between 0 and 1. The score is near to zero if the two documents are far semantically. The score is close to one if the two documents are similar. We are interested to visualize and clusters these documents. The obtained result is visible in the Fig. 7. The STOOG tool is integrated as a Java component. The documents are represented by thumbs. Clusters are represented by bubbles shapes around documents. Links between documents are visible on mouse over. Documents drawn in blue, red and green are in three different sets of selection. Menus have been added on the left side and on the right side to offer functionalities for selections, layout, manual clustering and automated clustering.

The clusters can be created either manually or automatically. Clusters are created manually using the STOOG selection or automatically using the Java implementation of the MCL algorithm (Stijn van Dongen 2000). Some interactions are not implementable using the graph style sheet such as the display of incident edges on mouse hover. For this kind of interaction it is possible to define the representation using the graph style sheet with a name of interaction not predefined. The developer must then simply specify the name of the modification of representation and of the data element to modify during the interaction.

STYLE SHEET EDITOR

Our style sheet editor is divided in two parts: a creator and a graph style sheet editor. The creator makes the creation of representations on-the-shelf possible. The graph style sheet editor gives a list of representations possible and enables the association between data and visual attributes.

Representation on-the-shelf

The creator (Fig. 8) proposes the construction of representations on-the-shelf. It is divided in three sections: (A) the list of structures, (B) the draw panel, (C) the list of attributes.

The list of structures is defined using the import button. The import button triggers input dialog asking for a structure class name. The structure is imported thanks to the Java introspection mechanism. The list of structures is stored in a for further uses.

The draw panel makes the positioning of structures possible. It offers a preview of the representation.

The list of attributes shows all available attributes for each structure placed on the draw panel. For each attribute the user can specify predefined values, the visibility of the attribute (private or not), the visible name and the input method. For instance the attribute fill_color of the instance of polygon is public (i.e. it will appear in the graph style sheet editor), the visible name is 'Color Body'. The color is typed using a color chooser. When the button "ok" is pressed the representation is available on-the-shelf.

Graph style sheet editor

The graph style sheet editor Fig. 9 is divided in four parts: (A) data, (B) representations, (C) rules and (D) rendering.

The data section makes the specification of a dataset possible. The data is considered as an instance nevertheless enables functionalities as autocompletion of data attributes.

The representation section exposes a set of available representations for graph style sheets. One click triggers the association of the representation to the selected rule and the adding of a tab in the rendering section.

The rule section exposes a set of rules created by the user. The rule is defined by a name, a condition of application named expression, an application mode and a kind of data element.

The rendering section presents the visual variables associated to the representation.

In the example in Fig. 9 the user has created a rule named "visitor". The rule is applied on the visitor node. The rendering associated to the rule is a visitor representation created (Fig. 8). The generated form concatenates the fields of all structures in the graphical representation. Only public attributes are visible, with the input method and the name chosen during the conception.

CONCLUSION

In this paper we have proposed a toolkit for graph visualization, more precisely for the visualization of multivariate graphs and clustered graphs. Our approach is based on style sheets. We have introduced a new language for the definition of style sheets which proposes new concepts and four mechanisms in order to handle these concepts: the matching, the coding, the cascading, and the interaction. By providing and integrating (1) an extensible language for style-sheet definition, (2) both a standalone application and an API supporting the rendering and interaction of visualization resulting from encoding raw data according to STOOG Style sheets and (3) a user to facilitate the creation and reuse of style-sheets. We believe that by using STOOG, both end-users and developers will save time and efforts in their attempts to visually explore large amounts of information.

PERSPECTIVE

In the future we plan to extend our language with more complex interactions. We are interested in extending our toolkit for graph hierarchies. Finally we plan to conduct controlled experiments on different users.

Figure 1 :

 1 Figure 1: A simple sample of multivariate graph

Figure 2 :

 2 Figure 2: A sample of style sheet

Figure 4 :

 4 Figure 4: Simplified grammar for arithmetic expressions

Figure 5 :

 5 Figure 5: Simplified grammar of Boolean expressions3.4 Cascading MechanismCascaded representations are processed when a data element is associated to several representations. The cascading algorithm takes an ordered set of

Figure 7 :

 7 Figure 7: A sample of visualization using STOOG

Figure

  Figure 9: Graph Style Sheet Editor


Marc Chaumont

A Novel Embedding Technique For Dirty Paper Trellis Codes Watermarking

Keywords: Watermarking, Dirty Paper Trellis Codes, High rate, Informed-coding, Informed-embedding, Robustness, Secure embedding space, Rotation-based embedding, RB-DPTC

Dirty Paper Trellis Codes (DPTC) watermarking, published in 2004, is a very efficient high rate scheme. Nevertheless, it has two strong drawbacks: its security weakness and its CPU computation complexity. We propose an embedding space at least as secure and a faster embedding. The embedding space is built on the projections of some wavelet coefficients onto secret carriers. It keeps a good security level and has also good psycho-visual properties. The embedding is based on a dichotomous rotation in the Cox, Miller and Boom Plane. It gives better performances than previous fast embedding approaches. Four different attacks are performed and revealed good robustness and rapidity performances.

INTRODUCTION

The generation of watermarking schemes named informed schemes or side information schemes appeared around 1998 when Costa's work has been rediscovered. [START_REF] Costa | Writing on dirty paper[END_REF] The two principal techniques' categories for multi-bits watermarking are the lattice codes also named quantized based watermarking schemes (DC-QIM, 2 SCS.. [START_REF] Eggers | Scalar Costa Scheme for Information Embedding[END_REF] ) and the Dirty Paper Trellis Codes (DPTC). [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF] The original DPTC algorithm is known for its good robustness and its high embedding payload but own two strong weaknesses: the informed embedding step uses a Monte Carlo approach which is very CPU time consuming and the scheme owns security weakness facing collusion attack. [START_REF] Bas | Evaluation of an Optimal Watermark Tampering Attack Against Dirty Paper Trellis Schemes[END_REF] In that paper, we thus propose a DPTC at least as secure and less complex.

Lin et al. [START_REF] Lin | An Efficient Algorithm for Informed Embedding of Dirty Paper Trellis Codes for Watermarking[END_REF] propose to replace the Monte Carlo approach with a non-optimal technique but of low complexity. We propose an even more efficient solution. We use the wavelet domain which gives less blocking effects than the DCT domain. In order to counter-attack the security hole given in, [START_REF] Bas | Evaluation of an Optimal Watermark Tampering Attack Against Dirty Paper Trellis Schemes[END_REF] we embed in a secret space. Finally, since our technique is rapid and the space well adapted, we increase the trellis size (i.e. the codebook' size) and thus the robustness-distortion efficiency. [START_REF] Wang | Toward a Better Understanding of Dirty Paper Trellis Codes[END_REF] In Section 2, we remind the principle of the original Dirty Paper Trellis Codes (DPTC). [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF] In Section 3 we present the embedding space and the embedding algorithm. In Section 4 we compare the original DPTC, 4 the Lin et al. approach 6 and our rotation-based approach (RB-DPTC).

DPTC WATERMARKING SCHEME

The original DPTC scheme applied on a N = 240 × 368 image is shown on Fig. 1. The first step of the scheme is the image transformation into a spatio-frequential space (DCT transformation) in order to obtain the host signal x. In the original scheme, an image is 8 × 8 DCT transformed, the twelve first ACs coefficients of each DCT blocks are extracted and pseudo-randomly ordered in a vector x of size 12 × N/64 = 3 × N/16. The second step of the DPTC scheme is the informed coding. The input message m is coded into a codeword c * by taking into account the host signal x. The last step of the DPTC scheme is the informed embedding. It consists in modifying the host signal x in order to "put-it" in the Voronoï region of the codeword c * . Let's now define more precisely the trellis structure, the informed coding and the informed embedding. In DPTC, 4 a special trellis is used. In this trellis, each state owns multiple possible transitions given an input bit. Each transition generates outputs coefficients. Fig. 2 gives an example of a trellis with 4 states and 4 arcs per state. With this trellis, an input sequence owns multiple possible output codewords (a codeword is the result of the concatenation of outputs coefficients) since for each state there is multiple possible transitions for the same input bit. This signifies that an input sequence may be coded with different codewords. This property is essential in informed watermarking. In the original DPTC algorithm, the trellis own 64 states, 64 arcs per state and there is N arc = 12 real coefficients pseudo-randomly generated as output arcs values.

Trellis structure

Informed coding

The set of all the trellis paths i.e. all the possible outputs sequences, is the codebook C of the coder. A codeword c i ∈ C is the resultant coding of a message m. The informed coding is a way to choose the codeword c i (encoding a given message m) the closest (for a given distance) to the host signal x. Thus, informed coding allows to encode a message m by taking into account the host signal x.

In the DPTC algorithm, given a message m, the informed coding is achieved:

• by pruning the trellis in order to keep the only valid paths. Thus, for a given transition, there is only the 0 input arcs or the 1 input arcs;

• by running a Viterbi decoder algorithm on this prune trellis in order to find the closest codeword c * . The distance used in order to compare the codewords with the original host x is the scalar product (the scalar product is a classical correlation measure). The Viterbi decoder thus retains the path (i.e. the codeword c * ) of highest correlation with the host signal x.

Informed embedding

In the original DPTC algorithm, 4 a Monte Carlo approach is used in order to displace the host signal x into the Voronoï region of the codeword c * . This embedding is achieved in order to meet a given robustness. Moreover the modification of x is achieved by taking into account the psycho-visual degradation by using the Watson perceptual measure. [START_REF] Watson | DCT Quantization Matrices Optimized for Individual Images[END_REF] The Monte Carlo principle is iterative and consists to attack and counter-attack a watermarked signal y.

The Monte Carlo approach requires to run the Viterbi algorithm a high number of times. Even with the proposed optimizations in, [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF] the time complexity is very high and this is at present a strong brake for intensive experiments studies and also for its use in industry. The DPTC watermarking scheme is thus seriously competed with faster quantization-based approaches. 2, 3

NEW EMBEDDING APPROACH

In this section, we present our new embedding space, our embedding approach and discuss about our proposition.

Embedding space

The recent work of Bas and Doërr 5 about security of DPTC shows that in the Kerckhoffs's framework, [START_REF] Kerckhoffs | La Cryptographie Militaire[END_REF] i.e. when embedding and extracting algorithms are known by an attacker, the trellis codebook may be retrieved by observing a large number of watermarked images. Those conclusions are drawn based on a simplified version of the DPTC algorithm (non pseudo-random-ordering of DCT coefficients) but show a certain security weakness of DPTC. [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF] The private space, that we use in this paper, allows to hide the structure of the trellis. A security attack based on the principle exposed in 5 is thus at least as difficult to lead with our proposition. Moreover, it is certainly very difficult to estimate the secret projections in the same way as 10 since there is a high number of codewords (with a trellis made of 128 states and 128 arcs per state and with a payload of 1024 bits, there is more than 10 387 codewords). Fig. 3 illustrates our proposition : the Rotation-Based Dirty Trellis Codes (RB-DPTC). Our new embedding space is obtained by first, a wavelet transform of the image, and second, projections of the host signal x of dimension N wlt (x is the concatenation of sub-bands coefficients except LL sub-band's coefficients) onto N sec carriers (noted u i with i ∈ [1, N sec ]). Note that a projection is just a scalar product. The obtained vector v x of dimension N sec may then be used for the informed-coding (see Section 2.2) and informed-embedding (see Section 2.3). This embedding space is at least as secure than the original one and it allows to spread the watermark signal on almost all the frequency domain (no super-robustness 11 ). Moreover, the projections onto N sec carriers give to the embedding space a Gaussian aspect which is known for its good property for the channel capacity. [START_REF] Costa | Writing on dirty paper[END_REF] Finally, the wavelet domain is known for its good psycho-visual properties and is less disturbing than the block effects present in the DPTC. [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF]

Embedding algorithm

The informed coding in our approach is the same than the original one (see section 2.2) but is achieved with the host vector v x (secret space). After achieving the informed coding, the codeword c * is extracted. The Lin et al. [START_REF] Lin | An Efficient Algorithm for Informed Embedding of Dirty Paper Trellis Codes for Watermarking[END_REF] solution, in order to speed-up the embedding, and keeps a good robustness-distortion tradeoff, is not satisfying since the degradation is too strong. Our solution is not optimal but gives better results (The Lin et al. solution is also non optimal). Remember that at the decoder, the most correlated codeword c * is obtained by running the Viterbi algorithm. This codeword c * belongs to the codebook C and maximizes the correlation with the attackedwatermarked vector ṽy such that:

c * = arg c i max ∀c i ∈C ( ṽy .c i ) = arg c i max ∀c i ∈C (|| ṽy ||.||c i ||.cosθ i ),
with θ i the angle between ṽy and c i . Thus, the highest correlation gives the closest codeword c * and the retrieved message m .

Knowing that all the codewords own the same norm, the Viterbi algorithm extracts the codeword c i owning the smallest angle with ṽy . The idea, in order to embed the message m at the coder side, is thus to reduce the angle between the host vector v x and the codeword c * until obtaining the smallest angle regarding all the other angles (v x , c i ).

In order to reduce the angle between v x and c * , we first express these two vectors in the Miller, Cox and Bloom plane (abbr. MCB plane). 12 Fig. 4 illustrates this MCB plane. The MCB plane is defined by an ortho-normalize basis (v 1 , v 2 ) such that v x and c * belong to that plane (Gram-Schmidt algorithm):

v 1 = c * ||c * || , v 2 = v x -(v x .v 1 )v 1 ||v x -(v x .v 1 )v 1 || .
In the MCB plane, the 2D coordinates of the host vector v x are:

v 2D x (1) = v x .v 1 , v 2D x (2) = v x .v 2 ,
and the 2D coordinates of the codeword c * are:

c * 2D (1) = ||c * ||, c * 2D (2) = 0.
A rotation of the host vector v 2D x of a θ angle in the MCB plane is such that:

v 2D y (1) = cosθ.v 2D x (1) -sinθ.v 2D x (2), v 2D y (2) = sinθ.v 2D x (1) + cosθ.v 2D x (2).
If we reduce the absolute angle between the host vector v x and the codeword c * in the MCB plane, it increases the correlation v x .c * . With a dichotomous approach on rotation angle, one can rapidly found a Voronoï frontier. The algorithm for obtaining this Voronoï frontier is iterative and dichotomous (there is less than 10 trials): 3. modify (dichotomous approach) the rotation angle depending on Voronoï region's belonging. Return to 1.

Once the frontier angle θ f in the MCB is found, we improve the embedding robustness by penetrate inside the Voronoï region with a given angle θ R . Our informed embedding is thus a rotation of v x of an oriented angle equals to the max(θ f + θ R , ( v x , c * )). Fig. 4 illustrates v x , v y , θ f and θ R in the MCB plane.

RESULTS

Tests were carried on the first 100 images of the BOWS2 data-base * with images resized to 256 × 256 † . Those images are 8-bits grey-level images and are personal photos.

The trellis structure owns 128 (resp. 64) states with 128 (resp. 64) arcs per states for Lin et al. cone-based algorithm and our rotation-based algorithm (resp. for the original DPTC). Outputs arcs labels are drawn from a Gaussian distribution and there are 12 coefficients by output arc. The payload is 1 bit for 64 pixels which is the same as the original DPTC algorithm. [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF] The number of embedded bits is thus 1024 bits.

For Lin et al. cone-based algorithm and our rotation-based algorithm, Wavelet transform is a 9/7 Daubechies with l = 3 decompositions levels. Except the LL sub-band, all the other sub-bands are used to form the host signal x. With 256 × 256 images, the wavelet space size is thus N wlt = 64 512 coefficients. Knowing that the payload is 1/64 bits per pixel and that the number of outputs coefficients for an arc is N arc = 12 coefficients, the private space size is thus N sec = 1024 × 12 = 12 288 coefficients. The carriers u i are built from normalized bipolar pseudo-random sequences.

Four kinds of robustness attacks have been applied: Gaussian noise attack, Gaussian filtering attack, valumetric attack and jpeg attack. The Bit Error Rate (BER) is the number of erroneous extracted bits divided by the total number of embedded bits. The BER is computed for each attack. Three algorithms are competing: the original DPTC with an average embedding PSNR = 42.6 dB, the Lin et al. cone-based algorithm with the robustness set to a noise power of n 2 = 1 (it corresponds to R t = 1 in the paper [START_REF] Lin | An Efficient Algorithm for Informed Embedding of Dirty Paper Trellis Codes for Watermarking[END_REF] ) and an average embedding PSNR = 34.2 dB (Note that it is impossible to increase the Lin et al. PSNR. Indeed, their technique is really sub-optimal with real images), and our rotation-based algorithm with the inside angle penetration set to θ R = 0.1 radian and an average embedding PSNR = 42.4 dB.

In Figure 5, 6, 7, 8 we observe the different BER results for the four different attacks. The Lin et al. curves just give an idea of the BER bound. They may not be used for fair comparison, since the average embedding PSNR is only of 34.2 dB. We should conclude that Lin et al. algorithm may not be used as a faster DPTC 4 substitute, since it is not able to achieved a reasonable PSNR of 42 dB. Comparison are thus only achieved between the original DPTC and the rotation-based algorithm.

For the comparison, we just look at BER below 10% which is large enough. With this criteria, the rotationbased algorithm performs identical or close results to the original DPTC algorithm for filtering and Gaussian attack. The two approaches strongly differ with jpeg and valumetric scaling. For the jpeg attack, the original DPTC performs very good robustness whereas the rotation-based is not robust at all. Results are opposite for the valumeric scaling, since the rotation-based is really better than the original DPTC.

We should then conclude that our rotation-based approach is the currently best approach in order to reduce the original DPTC complexity. Moreover, our approach assures a good security by using a secure embedding space as in. [START_REF] Furon | Broken Arrows[END_REF] The approach should nevertheless be improved in order to be robust to jpeg compression.

CONCLUSION

In that paper, we introduce a new Dirty Trellis Paper Codes algorithm (the Rotation-Based Dirty Paper Trellis Codes : RB-DPTC). Compared to the original algorithm, the wavelet domain is used instead of the DCT one. The security is assured by the add of a secret embedding space. This secret space is obtained by projecting the wavelet coefficients onto quasi-orthogonal carriers. Those projections also ensure (during the retro-projections) a spreading of the watermark on the majority of wavelet coefficients. Another interesting point is the embedding proposition based on a penetration into the Voronoï region of interest. This penetration necessitate first, to localize a frontier thanks to few rotations trials and second, to rotate of a fixed angle. The obtained results are good in comparison to the state of the art original DPTC. [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF] We explained how to reduce CPU complexity of the projections step in. [START_REF] Chaumont | Fast Embedding Technique For Dirty Paper Trellis Watermarking[END_REF] We also studied the psychovisual aspects in. [START_REF] Chaumont | Psychovisual Rotation-based DPTC Watermarking Scheme[END_REF] Future work will improve the robustness to the jpeg attack. The trellis structure and the codeword construction should also be clarified as exposed in. [START_REF] Wang | Trellis Coded Modulation to Improve Dirty Paper Trellis Watermarking[END_REF] Security of our approach should also be evaluated as it has been done for the original DPTC in 5 and for the Broken Arrows algorithm in. [START_REF] Bas | Two Key Estimation Techniques for the Broken-Arrows Watermarking Scheme[END_REF]

Figure 1 .

 1 Figure 1. Dirty Paper Trellis Codes apply on a 240 × 368 image.

Figure 2 .

 2 Figure 2. Dirty paper code's trellis with 4 states and 4 arcs per state.

Figure 3 .

 3 Figure 3. Our Rotation-Based Dirty Paper Trellis Codes (RB-DPTC) scheme.

Figure 4 .

 4 Figure 4. Rotation-based embedding in the Miller, Cox and Bloom plane.

1 .

 1 rotate v x and obtain v y in the MCB, 2. run the Viterbi algorithm to check if v y belongs or not to the Voronoï region of c * i.e. that the decoded vector is equal or not to c * .

Figure 5 .

 5 Figure 5. BER for Gaussian noise attack on the original DPTC algorithm (average PSNR = 42.6 dB), on Lin et al. cone-based algorithm (average PSNR = 34.2 dB) and on our rotation-based algorithm (average PSNR = 42.4 dB).

Figure 6 .

 6 Figure 6. BER for Gaussian filtering attack on the original DPTC algorithm (average PSNR = 42.6 dB), on Lin et al. cone-based algorithm (average PSNR = 34.2 dB) and on our rotation-based algorithm (average PSNR = 42.4 dB).

Figure 7 .

 7 Figure 7. BER for valumetric up and down scaling attack on the original DPTC algorithm (average PSNR = 42.6 dB), on Lin et al. cone-based algorithm (average PSNR = 34.2 dB) and on our rotation-based algorithm (average PSNR = 42.4 dB).

Figure 8 .

 8 Figure 8. BER for jpeg attack on the original DPTC algorithm (average PSNR = 42.6 dB), on Lin et al. cone-based algorithm (average PSNR = 34.2 dB) and on our rotation-based algorithm (average PSNR = 42.4 dB).

ACKNOWLEDGMENTS

This investigation was supported by the VOODDO project which is a French national project of the ANR (Agence Nationale de la Recherche) "Contenu et Interaction". We would also like to thank the Languedoc-Roussillon Region.