Julien Rabatel

Sandra Bringay

Pascal Poncelet

Mining Representative Frequent Patterns in a Hierarchy of Contexts

More and more data come with contextual information describing the circumstances of their acquisition. While the frequent pattern mining literature offers a lot of approaches to handle and extract interesting patterns in data, little effort has been dedicated to relevantly handling such contextual information during the mining process.

In this paper we propose a generic formulation of the contextual frequent pattern mining problem and provide the CFPM algorithm to mine frequent patterns that are representative of a context. This approach is generic w.r.t. the pattern language (e.g., itemsets, sequential patterns, subgraphs, etc.) and therefore is applicable in a wide variety of use cases. The CFPM method is experimented on real datasets with three different pattern languages to assess its performances and genericity.

Introduction

In the data mining field as well as in every data-related domain, more and more data come with contextual information detailing the circumstances under which data have been acquired. A concrete example lies in the explosion of mobile phone usage accompanied by information about the user location and user profiles. Another omnipresent example is related to the Web, where users often give some information about themselves (e.g., on forums or social media) that can be used to better understand their Web usage.

While mining patterns of very various forms and structures (itemsets, sequences, episodes, subgraphs, spatio-temporal patterns, etc.) has been studied extensively in the past two decades [START_REF] Han | Frequent pattern mining: current status and future directions[END_REF], there has been little interest in fully exploiting the surrounding data, i.e., the so-called contextual data. Many machine learning approaches can however benefit from this contextual information to finely analyze or exploit the data. In the current paper, we study and propose a solution for mining frequent patterns in the presence of contextual information. More precisely, the contributions of this paper are twofold:

-Providing a generic theoretical framework. We propose a formalism for defining contextual frequent patterns that does not depend on a particular pattern language. This framework has the ability to generalize the frequent pattern mining problem to consider available contextual information.

-Contextual frequent pattern mining algorithm. We also propose a new algorithm, so-called CFPM, which is generic w.r.t. the pattern language and the underlying mining algorithm. This approach is based on relevantly post-processing the output of existing algorithms, meaning that it can be applied in conjunction with any algorithm that aims at solving a transactional frequent pattern mining problem and offers a great applicability range.

While seminal work has already defined the basis of contextual frequent pattern mining in the case of sequential patterns [START_REF] Rabatel | Contextual sequential pattern mining[END_REF][START_REF] Rabatel | Mining sequential patterns: a context-aware approach[END_REF], the existing work has the following drawbacks: (1) its formulation is only dedicated to sequential patterns, while we are interested in providing a generic formulation applicable to most frequent patterns definitions; (2) the algorithm designed to mine contextual frequent sequential patterns uses specific techniques that make it unusable for other pattern languages. We build upon this previous work and show that the principles of mining contextual frequent patterns are not inherently associated to one pattern language, or even to one mining method, and can be used in conjunction with a lot of existing previous work for a great flexibility and applicability. Mining contextual frequent patterns only relies on pattern frequency and does not relate to how a pattern frequency contrasts with the rest of the database. Such patterns, found in the literature as discriminative patterns, contrast patterns or correlated patterns [START_REF] Bringmann | Pattern-based classification: A unifying perspective[END_REF] do not fall within the scope of this study.

The remaining is organized as follows. Section 2 defines the contextual frequent pattern mining problem. Then, Section 3 describes the proposed CFPM algorithm. Experiments are conducted in Section 4 and some conclusions and prospects are given in Section 5.

Contextual Data and Frequent Patterns

This section aims at formalizing the frequent pattern mining problem as well as its extension for handling contextual information. According to [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF], a large family of pattern mining problems can be specified with the following formulation: given a database D, a class of patterns P called a pattern language and a selection predicate q, it consists in finding the set {p ∈ P | q(D, p) is true}. This definition is refined as follows to describe the transactional frequent pattern mining problem addressed in this study.

Definition 1 (Transactional frequent pattern mining) A transaction is a couple T = (tid, o T ), where tid is a unique transaction identifier, and o T is the transaction object, i.e., an object provided in an arbitrary description space. A transactional database is a set of transactions.

The pattern language is associated with a support operator ≺, such that a transaction T supports a pattern p (or p is supported by T ) if p ≺ T . From the support operator, one can define the frequency of p in D as the fraction of transactions in D supporting p: F req

D (p) = |{T ∈D|p≺T }| |D| .
Frequent patterns are those whose frequency is above a user-specified minimum frequency threshold. In other terms, given a transactional database D, a pattern language P, a pattern support operator ≺, and a minimum frequency threshold σ, the transactional frequent pattern mining problem refers to finding the set F(P, D, ≺, σ) = {p ∈ P|F req D (p) ≥ σ}.

As an example, the well-known frequent itemset mining problem [START_REF] Rakesh Agrawal | Mining association rules between sets of items in large databases[END_REF] within this transactional setting can be: given an alphabet of items I = {a, b, c, d, e}, transaction objects are itemsets, i.e., subsets of I. The pattern language P is defined as 2 I and the support operator ≺ as the set inclusion operator between patterns and transaction itemsets. For instance, given a pattern p = {a, d} and a transaction T = (t, {a, b, d, e}), then p ≺ T because {a, d} ⊆ {a, b, d, e}.

Figure 1(a) provides an example of a transactional database of itemsets D using the alphabet I. The first column gives the identifier of each of the 14 transactions, while the second one provides the corresponding transaction itemset. The third column is not used in the transactional pattern mining setting. By considering a minimum frequency threshold σ of 0.5, we notice that the pattern p = {a, b} has a frequency F req D (p) = 8 /14 and is therefore frequent with F req D (p) ≥ σ. Such a theoretical framework is representative of a large fraction of frequent pattern mining approaches appeared in the literature in the past decades. These problems exploit a transactional view of the data, i.e., they are represented under the form of a collection of transactions and frequent patterns are those mapped to at least a given number of transactions. Among pattern mining problems that do not enter this family, an example is the relatively recent problem of mining patterns in one unique large graph or network, addressed for instance in [START_REF] Bringmann | What is frequent in a single graph?[END_REF].

We are interested in enriching this transactional setting for mining frequent patterns in the presence of contextual information, i.e., data describing some circumstances regarding each transaction. We therefore introduce the context hierarchy to manipulate this contextual information.

Definition 2 (Context hierarchy) A context hierarchy H is a directed acyclic graph (DAG), denoted by H = (V H , E H ), such that -V H is a set of vertices also called contexts, -E H ⊆ V H × V H is a set of directed edges among contexts.
H is naturally associated with a partial order < H on its vertices, defined as follows: given c 1 , c 2 ∈ V H , c 1 < H c 2 if there exists a directed path from c 2 to c 1 in H. This partial order describes a specialization relationship: c 1 is said to be more specific than c 2 if c 1 < H c 2 , and more general than

c 2 if c 2 < H c 1 . A minimal context from H is a context such that no more specific context exists in H, i.e., c ∈ V H is minimal iff c ∈ V H | c < H c. The set of minimal contexts in H is denoted as V - H .
A context hierarchy aims at offering more information about the elements of a transactional database D when mining frequent patterns. A transactional database and a context hierarchy are combined to produce a contextual transactional database D, i.e., a triple (D, H, δ) such that:

-D is a transactional database, -H is a context hierarchy, -δ is a function δ : D → V - H mapping each transaction from D to a minimal context in H.
In a contextual transactional database D, a transaction T is explicitly mapped to a minimal context given by c = δ(T ). By following the intuition that a transaction associated to a very specific context also is part of the more general contexts, we define the database induced by c, denoted by D(c), as the subset of D which is associated with c. More formally,

D(c) = {T ∈ D|(δ(T ) < H c) ∨ (δ(T ) = c)}.
Example. To illustrate the contextual database notions, let first consider Figure 1(b) which provides a visual representation of a context hierarchy. Contexts are the labels of vertices, such as contextual information is given by the age (young or old, respectively shorten to Y and O) and the season (summer or winter, respectively shorten to S and W). Some examples of contexts provided by this context hierarchy shown in Figure 1(b) are (from the more specific to the more general) YS, S, or A, respectively corresponding to "transactions associated to young people in summer ", "transactions associated to summer (regardless of the age of people)" and "all (A) the transactions regardless of the age and season". The third column of Figure 1(a) describes the δ function by mapping each transaction to a minimal context, such as the first transaction identified by t 1 associated with the context YS, i.e., δ(t 1 ) = Y S. Figure 1 hence provides a contextual transactional database D. From this δ mapping, we notice for instance that the database induced by YS (i.e., D(Y S)) is the set of transactions of identifiers t 1 , . . . , t 5 , while D(A) is the set of all transactions.

When should a pattern be associated with a context?

The contextual frequent pattern mining problem aims at discovering patterns whose the property of being frequent is context-dependent. In order to study and highlight the interest of exploiting contextual information within the frequent pattern mining process, we below isolate two patterns from our running example.

Case 1. Itemset {a, b} is frequent in D (F req D ({a, b}) = 8 /14). However, considering the database and its fragmentation given by contextual information, one can notice that {a, b} is frequent in the fraction of D corresponding to young people (Y) with a frequency of 7 /8 while it is infrequent in the rest of D, i.e., old people. In the following, we will state that this pattern, while frequent in A, is not general in A because it is not frequent in every context contained in A. On the other hand, this pattern is general in Y because, in addition to be frequent in Y, it is also frequent in YS (F req Y S (p) = 5 /5) and YW (F req Y W (p) = 2 /3), i.e., all contexts contained in Y.

Case 2. p = {b, d} is not frequent in D (F req D (p ) = 6 /14), while it however is frequent in O (F req O (p) = 5 /6) as well as in the contexts contained in O: its frequency is 2 /3 both in OS and OW.

Case 1 shows that simply mining frequent patterns within a context does not necessarily provide representative patterns. In addition, Case 2 shows a pattern that is representative of a given context, but mining frequent patterns in the whole database could not make such patterns emerge as the context they represent is not large enough relatively to the whole database.

The next section exploits these intuitions to formally define what types of frequent patterns are mined in a contextual database and how they relate to the context hierarchy.

Contextual Frequent Patterns: a Formal Definition

The current section applies the contextual transactional setting defined above to first reformulate the notion of frequent pattern within a context and then introduce the notions related to the contextual frequent patterns (CFPs). The CFP mining problem consists in enumerating all the context-maximal CFPs given a contextual database D and a minimum frequency threshold σ.

The set of CFPs that are context-maximal constitutes an exact condensed representation of the set of CFPs, as no CFP cannot be derived from a contextmaximal one. Indeed, following Definition 4, one may notice that if a pattern is c-general, then it is also general in all descendants of c. Therefore, mining all CFPs in D is equivalent to mining context-maximal CFPs only.

The CFP mining framework also has the advantage of associating to each context in H less patterns than what a typical transactional frequent pattern miner would provide (as being frequent in a context is only one of the requirements for a pattern to generate a CFP). To some extent,

Mining Contextual Frequent Patterns

This section describes how CFPs are mined given a contextual transactional database, by defining two approaches: (1) a baseline approach that makes direct use of the definitions given in Section 2, and (2) a more efficient approach that relies on theoretical properties emerging from the CFP mining framework.

A Baseline Approach

By relying on the requirements listed in Definition 4, Algorithm 1 provides a baseline approach to extract context-maximal CFPs. This approach relies on the following steps: (1) extracting frequent patterns from every possible context (lines 2-4), (2) for each context c and each pattern p frequent in c, checking the c-generality and context-maximality of (c, p) (lines [START_REF] Fournier-Viger | Spmf: Opensource data mining platform[END_REF][START_REF] Han | Frequent pattern mining: current status and future directions[END_REF][START_REF] Hansen | Benchmark data set for in silico prediction of ames mutagenicity[END_REF][START_REF] Jindal | Opinion spam and analysis[END_REF][START_REF] Kuramochi | Frequent subgraph discovery[END_REF][START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF][START_REF] Pei | Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth[END_REF].

Mining all the contexts in order to enumerate all their frequent patterns obviously is very time-consuming, as it requires to run an external pattern miner for each context separately. We therefore study in the following some theoretical properties in order to allow a more efficient extraction of CFPs. for p ∈ Fc do 7:

Algorithm 1 A Baseline Approach

if p is c-general and context-maximal then 8:

C ← C ∪ {(p, c)} // generate and store the contextual pattern 9:

end if 10:

end for 11: end for

CFPM: A More Efficient Post-Processing Approach

The approach described in Algorithm 1 trivially exploits the definition of contextual data and CFPs and leads to costly calculation, in particular by first extracting frequent patterns from each possible context. We highlight some interesting properties to reduce redundant calculations, in particular by reducing the executions of the frequent pattern miner. As opposed to [START_REF] Rabatel | Contextual sequential pattern mining[END_REF][START_REF] Rabatel | Mining sequential patterns: a context-aware approach[END_REF], we focus in this paper on providing a generic post-processing algorithm that, from the output of existing frequent pattern miners, generates the CFPs.

Additional properties of contextual general patterns. A context can be uniquely described by its minimal descendants in H. To this end, we consider the decomposition of a context c in H as the set of minimal contexts in H being more specific than c, i.e., decomp(c,

H) = {c ∈ V - H |(c < H c) ∨ (c = c)}. For instance, decomp(Y ) = {Y S, Y W } and decomp(Y S) = {Y S}. Property 1 p is c-general iff p is c -frequent ∀c ∈ decomp(c).
Property 1 (whose proof can be found in [START_REF] Rabatel | Contextual sequential pattern mining[END_REF] and adapted to the current framework) is essential by allowing the reformulation of the c-generality property w.r.t. minimal contexts only. The checking of c-generality requirements for a context thus becomes much simpler: a pattern p is c-general if and only if the set of minimal contexts where p is frequent includes the decomposition of c. Extending this property to context-maximal CFPs is straightforward. CFPM, as presented in Algorithm 2, exploits this property. It can be decomposed into the following consecutive steps:

Mining. (lines 2-4) Frequent patterns are extracted from each minimal context.

As opposed to Algorithm 1, CFPM does not mine non-minimal contexts. The cost of this step mainly lies on intensive I/O processing.

Coverage Computation and Pattern Generation. (lines 9-15) During this step, each key of K is given to the maxContexts routine (line 10) which performs a bottom-up traversal of the vertices of H in order to return the set of maximal contexts among {c ∈ V H | decomp(c) ⊆ l}. This is the coverage computation step. Then, for each pattern p such that l = l p (line 11) and each context returned by maxContexts (line 10 ), one context-maximal CFP is generated and stored (line 12 ). Two patterns p and p frequent in the same minimal contexts (i.e., l p = l p ) are general in the same contexts. They will generate the same result via the maxContexts routine. By using the hash table K to store the patterns that are frequent in the same minimal contexts, the number of calls to maxContexts is greatly reduced to the number of keys in K rather than the number of distinct patterns discovered during the mining step.

Discussion. Mining minimal contexts only is an essential advantage over the baseline approach. CFPM's post-processing oriented design also offers the possibility to use it with any transactional frequent pattern miner, whatever the structure of mined patterns (e.g., subgraphs, episodes, sequential patterns, itemsets, etc.). This genericity also is the main advantage over previous work [START_REF] Rabatel | Contextual sequential pattern mining[END_REF][START_REF] Rabatel | Mining sequential patterns: a context-aware approach[END_REF].

The implementation of the algorithm is divided into two parts. First, a Ruby wrapper is in charge of running external pattern miners, reading their output, and eventually generating the CFPs. Ruby's flexibility is particularly relevant for designing a generic approach, where final users should be able to add new components with very little effort to support new pattern languages. Second, a C++ module is in charge of the maxContexts routine of Algorithm 2, as it offers better performances without any drawbacks regarding genericity or usability.

The CFPM approach has been extensively experimented in order to assess its main features. Therefore, we have performed experiments implying real datasets and three common pattern languages, namely itemsets [START_REF] Rakesh Agrawal | Mining association rules between sets of items in large databases[END_REF], sequential patterns [START_REF] Agrawal | Mining sequential patterns[END_REF] and subgraphs [START_REF] Kuramochi | Frequent subgraph discovery[END_REF]. Each of these pattern languages involves different theoretical frameworks and algorithms. Experiments have been conducted on an Intel i7-3520M 2.90GHz CPU, with 16 GB memory.

Contextual Frequent Itemsets. First, in order to study the behavior of CFPM when considering the frequent itemset mining problem [START_REF] Rakesh Agrawal | Mining association rules between sets of items in large databases[END_REF], we have used the APriori algorithm as implemented in [START_REF] Fournier-Viger | Spmf: Opensource data mining platform[END_REF]. The dataset used for this experiment initially comes from [START_REF] Jindal | Opinion spam and analysis[END_REF]. It consists of 100, 000 product reviews published on the amazon.com website. Reviews have been lemmatized and grammatically filtered 3 . The remaining words compose the item alphabet and each review is represented as a transaction. Contextual information associated with the reviews is composed of the type of product, the rating given by the user and the proportion of positive feedbacks received. The resulting context hierarchy contains 210 contexts, whose 48 are minimal. The interested user may refer to [START_REF] Rabatel | Contextual sequential pattern mining[END_REF] for details.

Contextual Frequent Sequential Patterns. The second pattern mining problem addressed with CFPM considers frequent sequential patterns as defined in [START_REF] Agrawal | Mining sequential patterns[END_REF]. To this end, CFPM uses the PrefixSpan [START_REF] Pei | Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth[END_REF] algorithm as implemented in the SPMF project [START_REF] Fournier-Viger | Spmf: Opensource data mining platform[END_REF]. The used dataset is the same as the one described above for frequent itemset mining, except that reviews have been converted to sequences of itemsets 4 . It is also the same as the one previously used in [START_REF] Rabatel | Contextual sequential pattern mining[END_REF].

Contextual Frequent Subgraphs. In order to address the subgraph pattern language [START_REF] Kuramochi | Frequent subgraph discovery[END_REF], we use a dataset that has been constructed to study the mutagenicity property of some molecules [START_REF] Hansen | Benchmark data set for in silico prediction of ames mutagenicity[END_REF]. It contains 6, 512 molecular graphs, such that each one is associated with a label that indicates whether it is mutagene or not. Contextual information is composed of the mutagenicity label, the molecular weight, and the source dataset from which the molecule has been extracted. The merging of these pieces of information produces a context hierarchy containing 39 contexts whose 10 are minimal. Results. First of all, Figures 2(A1,B1,C1) show a large difference of runtimes when comparing the baseline approach with CFPM, for every used dataset and pattern language. This gap of runtime is mainly due to the fact that the baseline approach first requires to mine frequent patterns from each context, while CFPM only mines minimal contexts, that are less numerous and smaller. Then, Figures 2(A1,B1,C1) provide a view on how the runtime of CFPM is decomposed according to the algorithm steps. The largest fraction of time corresponds to the mining step, i.e., running pattern miners for each minimal context. This fraction systematically increases while the minimum frequency threshold decreases. Of course, this fraction of runtime also depends on the underlying implementations and algorithms. For instance, the time required to mine sequential patterns is relatively much larger (cf. Figure 2(B1)).

Figures 2(A2,B2,C2) show the total amount of patterns regarding their type. First, let consider the number of distinct patterns (i.e., the distinct frequent patterns discovered during the mining step) compared with the number of contextmaximal CFPs. As expected, the latter is always greater than or equal to the number of distinct patterns since every distinct pattern generates at least one CFP. On the other hand, the total number of CFPs (i.e., not necessarily contextmaximal ones) is much higher, therefore demonstrating the interest of proposing a condensed representation of contextual frequent patterns.

Conclusion and Prospects

In this paper, we adapt the transactional setting for mining frequent patterns by considering the contextual information associated with transactions. We therefore define a theoretical framework for CFP mining and propose a relevant algorithm for mining such patterns in a totally generic way regarding the pattern language. By generalizing the typical transactional setting and by post-processing the output of existing frequent pattern miners, the proposed approach provides the benefit of being able to be used in conjunction with any such frequent pattern miner developed during the last decades. Such an approach provides opportunities to be exploited in numerous application domains where data are often accompanied with contextual information, e.g., the mining of mobile data where spatial and temporal information may be used as contextual data or user profiling on the Web, where user activities may be mined under the scope of contextual information about the user such as location, age, etc.

The contextual pattern mining approach offers numerous prospects, such as for instance adapting it to the case of relying on discriminative patterns rather than frequent patterns in the context hierarchy, or considering the case where contextual information is imprecise (i.e., some transactions are mapped to a non-minimal context).

Fig. 1 :

 1 Fig. 1: A transactional contextual database composed of (a) a transactional database of itemsets with the associated minimal contexts, and (b) a context hierarchy.

Definition 3 (

 3 c-frequent pattern) A pattern p is frequent in c, or c-frequent, iff p is frequent in D(c), i.e., if F req D(c) (p) ≥ σ. For the sake of readability, we denote F req D(c) (p) with F req c (p).As discussed in the previous section, we are interested in patterns being representative of a context, i.e., such that their frequency property holds for all the descendants of this context. Such patterns are called general patterns and are used to define CFPs. Definition 4 (c-general pattern) A pattern p is general in c, or c-general, iff p is c-frequent and p is c -frequent ∀c | c < H c. Definition 5 (Contextual frequent pattern) A contextual frequent pattern is a couple α = (c, p), such that p is c-general. α is said to be generated by p. (c, p) is context-maximal if there does not exist another context c more general than c and such that (c , p) is a CFP, i.e., c ∈ V H |(c < H c ) and p is c -general.

  Require: A contextual database D, a minimum frequency threshold σ Ensure: Set of contextual frequent patterns in D 1: C ← ∅ // initialize the set of discovered CFPs 2: for c ∈ D do 3: Fc ← frequent patterns in c 4: end for 5: for c ∈ D do 6:

Fig. 2 :

 2 Fig.2: Time consumption for mining CFPs for itemsets (A1), sequential patterns (B1) and subgraphs (C1), and number of distinct patterns and contextual patterns for itemsets (A2), sequential patterns (B2) and subgraphs (C2).

  Algorithm 2 CFPM: Contextual Frequent Pattern Mining Output files from previous step are read and patterns p are indexed by the set of minimal contexts where they are frequent, i.e., l p .

	Require: A contextual database D, a minimum frequency threshold σ
	Ensure: Set of contextual frequent patterns in D
	1: C ← ∅ // initialize the set of discovered CFPs
	2: for c ∈ V -H do
	3:	Fc ← frequent patterns in c
	4: end for
	5: for p ∈	Fc do
		c∈V -H
	6:	lp ← {c ∈ V -H | p ∈ Fc}
	7:	K[lp] ← K[lp] ∪ {p}
	8: end for
	9: for l a key in K do
	10:	for c ∈ maxContexts(l, H) do
	11:	for p ∈ K[l] do
	12:	C ← C ∪ (p, c) // generate and store a CFP
	13:	end for
	14:	end for
	15: end for
	Reading. (lines 5-8)

Then, K is a hash table with keys being sets of minimal contexts and values being sets of patterns, such as K[l] containing the patterns p such that l p = l.

Remaining terms are non-modal verbs, nouns, adjectives and adverbs.

The conversion follows the principle that each sentence of the review is an itemset, and the order of itemsets in a sequence results from the order of sentences.


A Ouled Zaid

M Hachani
email: meha.hachani@gmail.com

W Puech

Wavelet-based high-capacity watermarking of 3-D irregular meshes

Keywords: Three-dimensional meshes, Watermarking, Wavelet transform, Quantization index modulation 1 Introduction

Digital watermarking can be used as data hiding technique to interleave cover content with auxiliary information before transmitting and storing applications. While image and video watermarking has been widely studied, much less attention has been paid to its application in 3D mesh models. This is principally due to their intrinsic irregular sampling nature. This paper proposes a high-capacity watermarking scheme for the purpose of inserting meta-data into 3D triangle meshes. Our proposal can be applied to meshes with arbitrary topology by using irregular wavelet-based analysis. The watermark is embedded in an appropriate resolution level by quantizing the norms of wavelet coefficient vectors. To ensure robustness to similarity transformation, a robust synchronization (indexing) mechanism is performed on the 3D model after irregular wavelet analysis. Experimental results show that our watermarking framework is robust to common geometric attacks and can provide relatively high data embedding rate whereas keep a relative lower distortion.

the community [START_REF] Alface | From 3D mesh data hiding to 3D shape blind and robust watermarking: A survey[END_REF][START_REF] Chen | A high-capacity steganographic approach for 3D polygonal meshes[END_REF][START_REF] Wang | A comprehensive survey on three-dimensional mesh watermarking[END_REF][START_REF] Yang | A data hiding scheme based on local coordinate system for 3D triangle mesh models[END_REF]. Specifically, high-capacity (H-C) mesh watermarking and data hiding systems are sometimes very useful. They carry a large amount of auxiliary information (metadata) in the cover mesh to enhance its utility or to provide an additional service. The challenge is to design H-C watermarking techniques reaching the trade off among imperceptibility (the enrichment process should not alter the perceptual quality of the host mesh), robustness (the metadata resistance against possible attacks) and data payload (the amount of metadata to be inserted).

The existing mesh watermarking algorithms can be subdivided into two classes depending on whether the hidden message is inserted in the spatial domain, by modifying the geometry or the connectivity, or in the transform domain, by modifying the coefficients obtained after a certain transformation.

It is well known that image watermarking methods, based on spectral analysis, provide better robustness and imperceptibility. However, for 3D meshes, there does not yet exist an efficient spectral analysis tool [START_REF] Wang | A comprehensive survey on three-dimensional mesh watermarking[END_REF]. Besides the direct mesh spectral domain, obtained by direct frequency analysis, we also find embedding algorithms based on multiresolution analysis. In the case of 3-D meshes, multiresolution analysis seems more flexible than the other spectral-like transforms, in sense that it provides different embedding locations that can satisfy different application requirements.

Moreover, the mesh multiresolution analysis based on discret wavelet transform (DWT) is a very suitable tool for constructing an imperceptible and high-capacity watermarking system. Based on the regular wavelet analysis, Kanai et al. [START_REF] Kanai | Digital watermarking for 3D polygon using multiresolution wavelet decomposition[END_REF], proposed a non-blind watermarking algorithm for 3-D meshes. Uccheddu et al. [START_REF] Uccheddu | Wavelet-based blind watermarking of 3D models[END_REF] extends [START_REF] Kanai | Digital watermarking for 3D polygon using multiresolution wavelet decomposition[END_REF] to achieve a blind watermark detection. Recently, Wang et al. [START_REF] Wang | Hierarchical watermarking of semiregular meshes based on wavelet transform[END_REF] developed a hierarchical watermarking framework based on wavelet transform of semi-regular meshes. The aforementioned wavelet based watermarking schemes cannot process irregular meshes directly. They can embed the watermark into an irregular mesh by using remeshing that converts an irregular mesh into a semi-regular one. But, the remeshed model cannot be seen as identical to the original, as it corresponds to a different sampling of the underlying 3-D surface. Consequently, the watermark robustness and imperceptibility may be degraded due to this remeshing preprocessing. Using the direct irregular mesh wavelet analysis tool [START_REF] Valette | Multiresolution analysis of irregular surface meshes[END_REF], Kim et al. [START_REF] Kim | Watermarking of 3D irregular meshes based on wavelet multiresolution analysis[END_REF] proposed a similar correlation-based scheme as in [START_REF] Uccheddu | Wavelet-based blind watermarking of 3D models[END_REF] to embed watermark components in bins (groups) of wavelet coefficient vectors (WCVs). Despite its robustness against various geometric attacks, Kim et al. method is penalized by its limited capacity (the maximal data payload) and quality degradation.

Recently In the present work, we propose a watermarking technique for enrichment applications of 3-D surface meshes. The motivation is to design a blind watermarking system, taking into account the capacity-imperceptibility-robustness requirements. For this purpose, we employ a substitutive embedding approach based on Quantization Index Modulation (QIM) [START_REF] Chen | Quantization index modulation, a class of provably good methods for digital watermarking and information embedding[END_REF] and applied in the wavelet transform domain. Our proposal can be applied to irregular as well as regular meshes by using irregular wavelet analysis introduced by Valette and Prost [START_REF] Valette | Multiresolution analysis of irregular surface meshes[END_REF]. The chosen watermarking primitive is the L2 norm of the geometric wavelet coefficient vector (WCV), at a certain appropriate resolution level. Each L2 norm is independently quantized to encode one bit of the watermark message.

To ensure invariance of the wavelet coefficients after inverse wavelet transform, we synchronize the connectivity by re-ordering the coefficients depending on the length of the related edges. It is worth mentioning that Kim et al. [START_REF] Kim | Watermarking of 3D irregular meshes based on wavelet multiresolution analysis[END_REF] watermarking algorithm, which is based on an additive approach, synchronizes the connectivity by re-ordering the vertex indexes from a reference vertex. Another important difference is that Kim et al. [START_REF] Kim | Watermarking of 3D irregular meshes based on wavelet multiresolution analysis[END_REF] algorithm divides the histogram of the L2 norm of WCVs in the approximation mesh, into regular bins. Each bin is used as unit to insert one bit of the watermark.

The rest of this paper is organized as follows. In Section 2, we provide a brief review of high-capacity mesh watermarking techniques. In Section 3, we explain our watermarking approach in detail. In Section 4, we present the extended version of our embedding scheme to ensure high robustness to some similarity transformations. Next, in Section 5, the particular scenarios simulated are described and the results obtained are presented and discussed. Finally, in Section 6, we conclude and mention potential improvement in future work.

Brief review of high-capacity mesh watermarking techniques

The basic idea of high-capacity mesh watermarking is to embed a large amount of additional information within the host model to enrich its content. As a result, high-capacity mesh watermarking schemes can be used in data hiding applications. In particular, blind high-capacity watermarking algorithms are of special interest as they provide automatic retrieving of the payload without any kind of assistance. High-capacity watermarks are often fragile, embedded in the spatial domain, taking the individual vertex coordinates as the watermarking primitives. In their work, Cayre and Macq [START_REF] Cayre | Data hiding on (3-D) triangle meshs[END_REF] developed a high-capacity blind data-hiding algorithm for triangular meshes. The chosen watermarking primitive is the projection of a vertex on its opposite edge in a triangle. The embedding capacity is about 0.4 to 0.8 bit/vertex.

Similarly, Maret and Ebrahimi [START_REF] Maret | Data hiding on (3D) polygonal meshs[END_REF] developed a high-capacity method to embed information into the geometry of a 3-D polygonal mesh. To guarantee robustness against rotation, scaling and translation attacks, the model geometry is transformed into a similarity-invariant space resulting in a non-uniformly sampled function on the unit sphere. The resulting samples are then modified in order to embed the message. Simulation results showed that the embedding capacity of the proposed technique is about 0.5 bit/vertex for an error-free extraction. Bors [START_REF] Wang | Watermarking mesh-based representations of 3-D objects using local moments[END_REF] also developed a blind algorithm using the relative position of a vertex to its 1-ring neighbors as primitive. A two-state space division is established and the vertex is assumed to be moved into the correct subspace according to the next watermark bit. Recently, Yang and Yao [START_REF] Yang | A data hiding scheme based on local coordinate system for 3D triangle mesh models[END_REF], proposed a high capacity data hiding algorithm that combines the local coordinate system, constructed by the vertex and its 1-ring neighbors with a special quantization technique. Message is embedded by modifying coordinate of the central vertex without changing the coordinate systems.

Wang and Cheng [START_REF] Wang | An efficient information hiding algorithm for polygon models[END_REF] proposed a high-capacity steganographic approach for 3-D polygonal meshes which is characterized by its robustness to affine transformations. An embedding capacity of about 3 bits per vertex, is achieved by applying a multi-level embedding procedure. This procedure consists of modifying successively the parallel, vertical, and rotary positions of a vertex related to its opposite edge in a triangular face. To enhance the invisibility of their embedding method, Cheng and Wang [8] extended their high-capacity mesh watermarking algorithm. The basic idea is to use a new representation rearrangement procedure (RRP) that allows to adaptively embed more bits in rough regions of the mesh surface. Bogomjakov et al. [4] proposed to embed watermarks by modifying the orders of the vertices and faces in the cover mesh. The embedding capacity attains ((log 2 n!)n + 1) bits on a polygonal mesh of n vertices or faces. Chung et al. [START_REF] Chung | A robust high capacity affine-transformation-invariant scheme for watermarking 3D geometric models[END_REF] realized a high-capacity embedding scheme that consists on rearranging the vertex and face representation information in the cover mesh. For a model with n vertices, the proposed method can yield an embedding capacity of approximately 3 lg n bits per vertex.

Recently, Gao et al. [START_REF] Gao | Multiresolution analysis for surfaces of arbitrary topological type[END_REF] proposed a robust and high capacity watermarking method for 3D Meshes with any topological connectivity. Before the embedding stage, the authors used a cryptographic hash table with a secret key to generate a binary sequence, and then they converted it to an octal sequence. The hidden message is divided into sequential groups. The watermark embedding process is performed in the spatial domain based on affine transformations. Each group of the octal sequence is inserted by slightly modifying the length ratios of one diagonal segment to the residing diagonal intersected by the other one in a coplanar convex quadrilateral. During this stage the quadrilaterals coplanar are keeping unchanged. In the recovery stage, the message is extracted by combining all the sequential groups through majority voting. The proposed approach is considered as affine-transformationinvariant while provides a higher embedding capacity. More Recently, authors in [START_REF] Lin | A high-capacity distortion-free information hiding algorithm for 3D polygon models[END_REF] developed a new high capacity hiding algorithm for 3-D polygonal meshes. The hidden message is embedded in the representation domain by modifying both geometry and connectivity information. This approach called representation permutation can embed a large amount of payload (at least 45 bits/per vertex) by permuting vertex/triangle representation orders and connectivity information. The proposed algorithm provides high hiding capacity with negligible distortion.

To summarize, the existing high-capacity mesh watermarking schemes can be classified as geometry-based or order-based methods. The latter naturally leads to a relatively poor robustness, whereas capacity increases. Geometry-based methods can easily achieve the robustness against the content-preserving operations but their capacity is somewhat limited. Wang et al. [START_REF] Wang | Hierarchical watermarking of semiregular meshes based on wavelet transform[END_REF] proposed a blind and high-capacity watermarking scheme that combines the ideas of both kinds of methods. The watermark embedding was specifically proposed for semi-regular meshes and applied on the wavelet transform domain to take advantage of the multiresolution representation. As mentioned above, watermarking methods, based on the multiresolution analysis, are of specific interest since they are able to embed the watermark information in the coefficients of a suitable scale (or resolution), depending on the application requirements.

Presentation of the proposed high capacity watermarking framework

In this work, we propose a high capacity watermarking scheme based on multiresolution analysis of meshes with arbitrary topology. Our method considers direct replacement of specific wavelet transform coefficients of the cover mesh using quantization watermarking approach. Specifically, the message is embedded by slightly modifying the norms of WCVs Fig. 1 Main building blocks of the proposed embedding-recovery scheme associated with a specific resolution level, using non-linear scaling QIM (NLS-QIM) watermark design. The developed watermarking system is depicted in a block diagram form as shown in Fig. 1.

It is worth mentioning that QIM method is a practical implementation of the ideal Costa coding scheme [START_REF] Costa | Writing on dirty paper[END_REF]. It is a widely used quantization-based embedding technique for image, audio and video watermarking, due to its ease of implementation, computational flexibility and large data payloads.

Multiresolution analysis

Multiresolution analysis of 3D meshes is of crucial importance since it gives efficient representation of 3D model at multiple levels-of-detail with many inherent advantages including progressive compression depending on the storage conditions and displaying capacity of the available resource, and level-of-details display accelerating the rendering.

3D mesh multiresolution analysis produces a coarse mesh that represents the basic shape of the model and a list of details information at different resolution levels. During the dual synthesis stage, a series of reconstructed meshes is constructed. The reconstructed meshes represent the same 3-D model but with different resolutions. Wavelet transform is one of the most commonly used multiresolution representation methods. The mathematical formulation of the wavelet analysis and synthesis of 3-D meshes was introduced by Lounsbery et al. [START_REF] Lounsbery | Multiresolution analysis for surfaces of arbitrary topological type[END_REF]. Valette and Prost [START_REF] Valette | Multiresolution analysis of irregular surface meshes[END_REF] proposed an irregular subdivision scheme derived from the Lounsbery's approach, allowing multiresolution decomposition of irregularly subdivided triangular meshes. Based on Valette and Prost approach, each face of a mesh can be subdivided into four (Lounsbery approach), three or two faces, or remains unchanged. For a given mesh M j having n j faces and v j vertices, there are 11 n j possible subdivision schemes. In order to apply multiresolution analysis by the wavelet decomposition to the mesh M j , the subdivision scheme S j +1 leads to the mesh M j +1 using the following relationship:

S j +1 M j +1 = M j , (1)
Irregular wavelet analysis scheme simplifies the original mesh by reversing the irregular subdivision principle. Once the simplification is complete, one can build a hierarchical relationship between the original mesh M j and the simplified one M j +1 (its approximate). Consequently, the geometry of M j can be computed by applying the wavelet decomposition, with two analysis filters A j and B j . Let's denote by C j the v j × 3 matrix giving the coordinates of each vertex of M j having v j vertices. To reconstruct C j from C j +1 , it's necessary to calculate the wavelet coefficients in D j +1 by using the following equations:

C j +1 = A j C j D j +1 = B j C j C j = P j C j +1 + Q j D j +1 (2)
with P j and Q j designate the synthesis filters. The (analysis/synthesis) matrix filters A j , B j , P j and Q j are calculated based on the lifting scheme to make the mesh approximation M j as close as possible to the original mesh M j +1 . The lifting scheme [START_REF] Sweldens | The lifting scheme: a construction of second generation wavelets[END_REF] decomposes the filters in simple matrices. Thereby, the analysis stage is deduced from the synthesis one by using simple sign inversion and ordering of these matrices.

In our work, we used the 3-D multiresolution representation proposed in [START_REF] Valette | Multiresolution analysis of irregular surface meshes[END_REF] wich is based on irregular subdivisions. By using irregular wavelet analysis, our watermarking scheme can be applied for both regular and irregular 3-D meshes. The proposed embedding/extraction approaches will be discussed throughout the next sections.

Watermark embedding stage

As cited earlier, our embedding process is based on QIM watermarking approach. In their work, Chen and Wornell [START_REF] Chen | Quantization index modulation, a class of provably good methods for digital watermarking and information embedding[END_REF] presented the dithered quantization as a special case of quantization index modulation (QIM). Let q(.) be a basic quantizer, and m the watermark message. In dither quantization, a dither vector d(m) is added to the host signal s prior to quantization. The number of possible values of m determines the number of required quantizers. Therefore, m acts as an index which is assigned to a fixed quantizer value. The output of the quantization operation is denoted by:

x = q(s + d(m)) -d(m) = q m (s)
For binary dither modulation with uniform scalar quantization (m ∈ {0, 1}), the output levels of the quantizers are given by:

x = c 0 k = k × + 4 if m = 0 c 1 k = k × -4 if m = 1 (3)
where k ∈ N and is a quantizer step size. The above dither modulation approach can be extended to a sequence of quantizers q(s), where each q m is a mapping from the real line R to a codebook C = {c m 1 , c m 2 , . . . , c m L }, where L is the size of codebook. The output values {c m k , 1 ≤ k ≤ L} are referred to as reconstruction points. The robustness requirement suggests that all codebooks should be disjoint, otherwise it is not possible to determine the value of m. Due to the distortion constraint and imperceptibility requirement in data hiding applications, the reconstruction points should be close to the host signal. In our work we designed a watermarking scheme, based on dither modulation strategy, meeting these conflicting requirements. For the embedding purpose, we only consider the set D j = [d 0 , d 1 , . . . , d N-1 ] t of WCVs associated with the j th intermediate wavelet decomposition level. The Cartesian coordinates of the coefficients d i , i ∈ {0, . . . , N -1} are converted to spherical coordinates [r i , θ i , φ i ] t where, r i = d i denotes norm of wavelet coefficient vector d i . It should be noted that the watermark embedding in the spherical coordinate system, especially in the radial component

r i = x 2 i + y 2 i + z 2 i
, has the advantage to be invariant to rotation and translation attacks.

Let us consider the watermark message as a binary sequence assigned by m = {m 0 , . . . , m i , . . . , m N-1 }, with m i ∈ {0, 1}. The watermark message is inserted by quantizing the WCV norms r i according to r i = r i × . The binary decision results on two watermarked components c 0 and c 1 depending on the quantizer value and the scaling parameter α. When m i = 0 is considered, the binary decision results on the watermarked component c 0 , given by:

if r i ∈ [ r i + α, r i + 2 -α] → c 0 = r i ; if r i ∈ [ r i , r i + α] →c 0 = r i + α; if r i > r i + 2 -α → c 0 = r i + 2 -α; (4) Otherwise, if m i = 1 is considered, c 1 is given by: if r i ∈ [ r i + 2 , r i + 2 + α] →c 1 = r i + 2 + α; if r i ∈ [ r i + 2 + α, r i + -α] → c 1 = r i if r i > r i + -α → c 1 = r i + -α;
(5)

This results in the watermarked component r i , that yields maximum correlation with r i for a given scaling parameter α. The use of non linear scaling results in shifted versions of the reconstruction points, which are highly correlated with the original host components. It is worth mentioning that this modification of the embedding algorithm does not affect the watermark robustness ensured by the basic QIM watermarking design.

Based on the work presented in [START_REF] Chen | Quantization index modulation, a class of provably good methods for digital watermarking and information embedding[END_REF], the probability density functions of the quantization error, in the QIM scheme, are assumed to be similar. Consequently, during the recovery step, the distortion-compensation is considered as noise and is statistically independent of the embedded message m. A decrease of scaling parameter α, leads obviously to better robustness under channel perturbations. But, increases the interference, due to the distortion-compensation. To alleviate this problem, authors in [START_REF] Chen | Quantization index modulation, a class of provably good methods for digital watermarking and information embedding[END_REF] use the scaling parameter α that maximizes the "signal-to-noise ratio" which is given by the following formula:

SNR = d 2 1 /α 2 (1 -α) 2 D s α 2 + σ 2 n , (6)
being SNR the ratio between the squared minimum distance among quantizers and the overall interference energy that results from distortion-compensation interference and channel interference. d 1 corresponds to the minimum distance for α = 1. As a results, the optimal scaling parameter α, that maximizes the SNR, is giving by the following expression:

α opt imal = D s σ 2 n D s σ 2 n + 1 , ( 7
)
where D s σ 2 n denotes the distortion, due to the embedding process. In our embedding scheme, we propose to use the aforementioned concept, introduced by Chen and Wornell [START_REF] Chen | Quantization index modulation, a class of provably good methods for digital watermarking and information embedding[END_REF], regarding the α parameter, in order to minimize the induced distortion while keeping a good trade-off between imperceptibility and watermark message resistance.

Watermark recovery stage

We have developed a blind watermarking system, so the recovery stage is only made from watermarked mesh without needing the original mesh. A given reconstructed WCV norm ŕi , positioned in the same resolution level chosen for the embedded stage j , is manipulated using (8) to obtain Q 0 and Q 1 indices.

Q 0 = ŕi Q 1 = ŕi + 2 . ( 8
)
At this step, we measure the distance between ŕi and its approximation, as follows:

if | ŕi -(Q 1 × )| < | ŕi -(Q 0 × )| → m i = 1 ( 9 ) else → m i = 0
The capacity of our watermarking approach is equal to the number of wavelet coefficients N in the considered resolution level. In our experiments, the embedding level (EL) corresponds to the third resolution level (j = 3).

Preprocessing of wavelet coefficient vectors

Despite its efficiency, our embedding method is vulnerable to similarity transformation, which is considered as content-preserving operation. Indeed, similarity transformation is considered as routine operation since it does not affect the mesh shape. To be invariant to this kind of attack, one just needs to make the watermark synchronization scheme independent of the combinatorial element orders represented in the mesh file.

As an extension to our embedding scheme, we propose to establish a robust synchronization (indexing) mechanism. A re-ordering process is applied on the 3-D model after irregular wavelet analysis. In more detail, the re-ordering is performed on the N wavelet coefficient vectors, localized in the j th resolution level that was selected for embedding purpose. The wavelet coefficients are indexed according to the lengths of their associated edges. First, we sort the edge lengths in ascending order, then we reorder the N WCVs according to the edge length indices. Next the cartesian coordinates of the re-ordered coefficients are converted to spherical coordinates to apply the quantization based embedding as explained in Section 3.2. The inverse re-ordering of the preprocessed WCVs is required in order to apply the inverse DWT and obtain the watermarked 3-D mesh. Figure 2 depicts the extended version of our high capacity watermarking approach, taking into account the re-ordering strategy.

It is worth pointing out that even with the re-ordering of the wavelet coefficients, the proposed embedding method is not invariant to all the content-preserving operations, because the norm of wavelet coefficient (the watermarking primitive) is not invariant to uniform scaling. The re-ordering only makes the algorithm invariant to vertex re-ordering.

Experimental results

We have tested our high-capacity watermarking algorithm on several irregular meshes: Venus (100759 vertices), Rabbit (70658 vertices), Horse (112642 vertices), Bunny (34835 vertices). Quality assessment was carried out using two evaluation criteria, maximum root mean square error (MRMS) [START_REF] Aspert | Mesh: measuring errors between surfaces using the Hausdorff distance 4. Bogomjakov A[END_REF], and mesh structural distortion measure (MSDM) [START_REF] Lavoué | Perceptually driven 3D distance metrics with application to watermarking[END_REF]. The Fig. 2 Extended version of our embedding-recovery scheme MRMS is an objective surface-to-surface distance between the original mesh M and its modified version M . It is defined as follows:

d MRMS = max(d RMS (M, M ), d RMS (M , M))
where d RMS (M, M ) is the root mean square error (RMS) from M to M given by:

d RMS (M, M ) = 1 |M| p∈M d(p, M ) 2 dM,
with p is a point on surface M, |M| is the area of M, and d(p, M ) designates the pointto-surface distance between p and M . It is important to note that the RMS distance is not symmetric.

The MSDM [START_REF] Lavoué | Perceptually driven 3D distance metrics with application to watermarking[END_REF] is a perceptual metric that measures the perceptual distance between two 3D models. It is based on the concept of structural similarity that was proposed by Wang et al. [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF] for 2D image quality assessment. The robustness is evaluated by the normalized correlation (corr) [START_REF] Cox | Digital watermarking and steganography[END_REF] between the extracted binary message and the original embedded one. The correlation coefficient between recovered watermark bits m " n and the original watermark m n is calculated by means of

corr(m " n , m n ) = N-1 n=0 (m " n -m" )(m n -m) N-1 n=0 (m " n -m" ) 2 × N-1 n=0 (m n -m) 2 (10)
where m indicates the average of the watermark and corr varies in the range of

[-1, 1].
It is well known that for 3-D mesh watermarking, transform-domain-based techniques that modify the low frequency parts are both more robust, to signal processing attacks, and more imperceptible than the other techniques. On the other hand, towards the medium and high frequencies, the number of wavelet coefficients increases. The purpose of our method is to embed a large amount of information in the cover mesh while maintaining a good compromise between the imperceptibility and the robustness.

Concerning the parameter setting, for the QIM based embedding, we tested several settings of the quantized value and the scaling parameter α. For all tested values, the watermark was entirely recovered without any confusion with a binary error rate (BER) of a NULL value (corr = 1). Nevertheless, the use of largest and α values was paid by noticeable mesh quality degradation. In the following tests, the quantizer step size and the scaling parameter α are fixed at 8 and 0.2 respectively. This choice, offers the best compromise between robustness and watermark invisibility.

To understand the impact of the selected EL on imperceptibility and data payload we compared our algorithm's performance with itself at different resolution levels (EL). In our experiments, the watermark message length corresponds to the number of wavelet coefficients in the considered EL. Six resolution levels have been tested for embedding. It should be noted that the total number of resolution levels is dependent on the number of vertices of original mesh. Tables 1 and2 present payload, MRMS and MSDM variation as function of the considered EL. Based on results reported in these tables, we can notice that the obtained MRMS values increase with the EL. This is principally due to the fact that modification of wavelet coefficients, at high resolution levels, for the embedding purpose will induce modification of the positions of the involved vertices at the lower resolution levels, resulting on high-amplitude objective modifications. It can also be observed from the tables that MSDM perceptual distances between the watermarked and original models decreases for the upper embedding levels. This can be explained by the fact that the amount of induced distortion in Since the watermark message length corresponds to the number of wavelet coefficients in the considered resolution level, the watermark payload decreases rapidly with the increase of EL. In the next subsections, the 3 rd resolution level, which leads to a satisfactory compromise between distortion and payload, is considered for embedding purpose.

Basic simulations

Tables 3 and4 illustrate the baseline evaluations of the proposed H-C watermarking scheme. From the results reported in these tables, it can be seen that, for all the tested 3D models, our method introduces relatively high-amplitude deformation while keeping it imperceptible (the induced MSDM is less than 0.078). This point is also confirmed in Fig. 3, where three close-ups of original and watermarked meshes are depicted. We can hardly observe any visual difference between the cover and watermarked models. In practice, perceptual distortion measurement is considered more important than the objective distortion measurement since it does not always correctly reflect the visual difference between two meshes. It is worthwhile pointing out that 3D mesh applications have different constrains on the objective and perceptual distortions caused by the watermark insertion. For example, computer-aided

design and medical imaging applications require a very small objective distortion, while the visual quality of the watermarked model is generally less important. On the contrary, in digital entertainment applications, the induced distortion should not be noticeable by human eyes, while the amount of the objective distortion is of minor importance.

The results reported in Tables 3 and4 also compare the data payload, the watermark correlation (corr), and the MRMS measures provided by our method with those provided by two existing watermarking methods (without any robustness consideration): Wang et al. method [START_REF] Wang | Hierarchical watermarking of semiregular meshes based on wavelet transform[END_REF] (for Venus, Rabbit, Horse meshes), and Lee et al. method [START_REF] Lee | Joint reversible watermarking and progressive compression of 3D meshes[END_REF] (for Horse, Bunny, and Venus meshes). It should be noted that in the case of Wang et al. watermarking algorithm, the tested mesh is first remeshed to construct a semi-regular mesh before passing through the wavelet decomposition process. The watermarking algorithm presented in [START_REF] Lee | Joint reversible watermarking and progressive compression of 3D meshes[END_REF] consists in modifying the vertices geometry information based on histogram bin shifting.

Figure 4 illustrates the maps of the objective distortions between original and watermarked Rabbit mesh using our method and Wang et al. watermarking scheme [START_REF] Wang | Hierarchical watermarking of semiregular meshes based on wavelet transform[END_REF]. The distance between original and watermarked mesh varies from 0 to 0.001. From Fig. 4, we can see that the distortion introduced by our embedding scheme is globally well balanced. Compared to Wang et al. scheme, the distortion induced by our method is of low frequency.

Robustness under geometric attacks

In this section, we assess the resistance of the embedded message under various geometric attacks, including noise addition, smoothing, and lossy compression. Surface smoothing is a common operation used to remove the noises introduced during the mesh generation process but in this case significant shape distortion may be introduced. The Laplacian smoothing aims to move the vertices positions based on local information such as the neighbor positions without changing the connectivity of the faces. Only internal vertices are simultaneously moved while keeping the boundry vertices positions. Indeed, Laplacian smoothing is an iterative process. In each step, the vertices converge to the barycenter of their neighbors. The shape undergoes significant deformations whenever a large number of Laplacian smoothing iterations are performed. In our work, we retained a Laplacian smoothing with different iteration numbers, and we have chosen to add pseudo-random noises on vertex coordinates. Tables 5, 6 and 7 presents the robustness evaluation results of our method, regardless WCV index re-ordering step , in terms of the normalized correlation (corr). The distortion induced by attacks is also measured by MRMS and MSDM measures. The results of the robust watermarking method in [START_REF] Wang | Hierarchical watermarking of semiregular meshes based on wavelet transform[END_REF], based on manifold harmonics transform, are presented in parentheses. It can be seen that with a roughly comparable robustness level, Wang et al. [START_REF] Wang | Hierarchical watermarking of semiregular meshes based on wavelet transform[END_REF] embedding technique introduces higher geometric and perceptual distortions than our method. Additionally, the watermark message length is relatively short, of about 64 bits, which is still negligible compared to our watermarking approach's capacity. Consequently, we can assume that our watermarking scheme has a better trade-off between the robustness, the induced distortion and the capacity payload.

In Table 8, the robustness and imperceptibility of our system, integrating the re-ordering process, are evaluated. Compared with the results reported in Tables 5, 6 and 7, we can notice that the WCVs re-ordering brings on a slight improvement of the watermark imperceptibility. Furthermore, the gain in terms of robustness is notable. When comparing our results with those obtained by the method of Lee et al., we find that our embedding system exhibits superior robustness and quality performance. Also, based on the results reported in Table 4, the reference method is limited to watermarks with very small data payloads of about 52 bits for Horse mesh, which still negligible compared to our watermarking approach's capacity (about 5406 bits for the same mesh).

Watermark robustness under similarity transformation

Similarity transformation is considered as a common geometry operation on a 3-D mesh rather than a malicious attack. To achieve invariance of our watermarking method to this routine operation we extended our embedding technique by integrating the re-ordering process which was discussed in detail in Section 4.

To assess the robustness of our method against the similarity transformation, we applied the operations of translation, rotation and uniform scaling on watermarked meshes. Table 9 presents the obtained robustness evaluation results against the considered operations. It can be observed that experimentally our extended scheme possesses a strong robustness to translation and rotation transformations. However, the attack-induced distortions, in terms of MRMS and MSDM, are very high. The results reported in Table 9 also confirm what was said in Section 4 about the low resistance against uniform scaling.

Robustness under connectivity attacks

Table 10 shows the robustness results of our method, in terms of normalized correlation (corr), against connectivity attacks. For comparison purpose, the results of the watermarking method presented in [START_REF] Ai | A new digital watermarking scheme for 3D triangular mesh models[END_REF] are also shown in the same Table . It is important to note that the authors in [START_REF] Ai | A new digital watermarking scheme for 3D triangular mesh models[END_REF], employ an existing 2D image watermarking algorithm to embed the watermark information. Their method consists on partitioning a 3D mesh model into Voronoi patches. In the embedding stage, the message is inserted by modifying the vertices in each patch according to its corresponding range image. From the results reported in Table 10, we can notice that the normalized correlation values, obtained by our method, are higher than those obtained by the reference method.

Complexity evaluation

In order to assess the time complexity of our watermarking scheme, execution-time tests were conducted employing executables generated by Visual Studio 9.0 operating in release mode. The source code was written in C++. All tests were conducted on a laptop with an Intel Core 3 CPU M350 at 2.23 GHz, and operating system Windows 7 SP 1. Table 11 presents the execution times for embedding/extraction stages applied on 6 test models: venus, rabbit, horse, bunny, david head and hand. It is worth mentioning that the added complexity induced by the reordering process has been considered. From the reported results we can deduce that our watermarking system is computationally efficient depending on the number of wavelet coefficient in the third resolution level. The full embedding time varies from 0.0291 and 0.0347 seconds. Based on the same results reported in Table 10 we found that the extraction delay varies between 0.00576 and 0.00659 seconds. Thus the extraction process is five times faster than the watermark insertion.

Conclusion

In this paper, we have reported a new blind and high-capacity watermarking framework of 3D meshes. Our watermarking technique consists on extended version of QIM based embedding approach applied to the norms of wavelet coefficient vectors. Experimental results show that despite its simplicity, our approach is characterized by large payload, high visual quality reconstruction, and robustness to several geometric attack scenarios. The invariance to similarity transformation is attained by re-ordering the wavelet coefficient vectors. A satisfying robustness is also achieved against some connectivity attacks.

In our future work, we plan to apply a re-ordering process (vertices and facets) on the original model before irregular wavelet analysis to ensure a good robustness against connectivity re-ordering attacks.

Fig. 3

 3 Fig. 3 The original irregular meshes a Rabbit, b Horse, and c Venus. The corresponding close-ups of the original irregular meshes are provided as d-f. The corresponding close-ups of the watermarked meshes are also provided as g-i for comparison

Fig. 4

 4 Fig. 4 Maps of the objective distortions introduced by our method (right side) and Wang et al. scheme (left side)

Table 1

 1 Payload, MRMS and MSDM results of embedding binary messages with varying embedding resolution level for Vennus and Rabbit meshes

	Model	Vennus			Rabbit
	EL	Payload (kbits)	MRMS (10 -3 )	MSDM	Payload (kbits)	MRMS (10 -3 )	MSDM
	1	54.55	0.17	0.14	51.75	0.27	0.077
	2	23.47	0.19	0.08	12.93	0.34	0.068
	3	10.65	0.2	0.04	3.23	0.38	0.021
	4	4.82	0.22	0.03	0.8	0.39	0.02
	5	2.21	0.22	0.02	0.2	0.44	0.015
	6	1.13	0.24	0.02	0.03	0.41	0.011
	low frequency localisations does not degrade too much the visual quality of the deformed
	object.

Table 2

 2 Payload, MRMS and MSDM results of embedding binary messages with varying embedding resolution level for Vennus and Rabbit meshes

	Model	Vennus			Rabbit
	EL	Payload	MRMS	MSDM	Payload	MRMS	MSDM
		(kbits)	(10 -3 )		(kbits)	(10 -3 )
	1	21.52	0.24	0.074	84.48	0.32	0.063
	2	6.82	0.26	0.024	21.12	0.36	0.057
	3	2.91	0.3	0.024	5.28	0.4	0.038
	4	1.36	0.32	0.023	1.32	0.47	0.034
	5	0.63	0.33	0.023	0.33	0.51	0.031
	6	0.29	0.34	0.021	0.055	0.56	0.028

Table 3

 3 Baseline evaluations of the proposed watermarking framework and Wang's methods for Venus, Rabbit and Horse meshes (in the parentheses are the results of Wang et al H-C watermarking method[START_REF] Wang | Hierarchical watermarking of semiregular meshes based on wavelet transform[END_REF])

		Venus	Rabbit	Horse
	EL	3 (4)	3 (4)	3 (4)
	Payload (kbits)	10.65 (7.632)	3.23(3.18)	5.28(5.247)
	MRMS (10 -3 )	0.2 (0.22)	0.38(0.2)	0.4(0.15)
	MSDM	0.04 (0.045)	0.021 (0.039)	0.038(0.058)
	corr	1

Table 4

 4 Baseline evaluations of the proposed watermarking framework and Lee's methods for Horse, Bunny and Venus meshes (in the parentheses are the results of Lee et al.[START_REF] Lee | Joint reversible watermarking and progressive compression of 3D meshes[END_REF] method)

		Horse	Bunny	Venus
	EL	3	3	3
	Payload (kbits)	5.28 (0.051)	2.91(0.072)	10.65(0.128)
	MRMS (10 -3 )	0.4 (1.03)	0.3(1.52)	0.2(1.77)
	MSDM	0.038	0.024	0.04
	corr	1 (0.98)	1 (0.98)	1 (0.85)

Table 5

 5 Robustness against the random additive noise addition (in the parentheses are the results of Wang et al. robust watermarking method[START_REF] Wang | Hierarchical watermarking of semiregular meshes based on wavelet transform[END_REF])

	Model	Noise	corr	MSDM
		0.05 %	0.99 (0.85)	0.097 (0.28)
	Venus	0.25	0.99 (0.59)	0.108 (0.7)
		0.5 %	0.99 (0.31)	0.119 (0.83)
		0.05 %	0.99 (0.92)	0.099 (0.18)
	Rabbit	0.25 %	0.99 (0.59)	0.105 (0.6)
		0.5 %	0.99 (0.31)	0.111 (0.77)
		0.05 %	0.99 (0.69)	0.105 (0.23)
	Horse	0.25 %	0.99 (0.5)	0.114 (0.64)
		0.5 %	0.98 (0.08)	0.12 (0.78)

Table 6

 6 Robustness against the Laplacian smoothing in the parentheses are the results of Wang et al. robust watermarking method[START_REF] Wang | Hierarchical watermarking of semiregular meshes based on wavelet transform[END_REF]

	Model	Iterations	corr	MSDM
		10	0.99 (0.74)	0.101 (0.15)
	Venus	30	0.99 (0.71)	0.117 (0.27)
		50	0.98 (0.62)	0.135 (0.34)
		10	0.99 (0.90)	0.08 (0.15)
	Rabbit	30	0.99 (0.71)	0.11 (0.26)
		50	0.99 (0.45)	0.142 (0.31)
		10	0.99 (0.97)	0.092 (0.15)
	Horse	30	0.99 (0.5)	0.102 (0.23)
		50	0.99 (0.35)	0.135 (0.28)

Table 7

 7 Robustness against coordinate quantization (in the parentheses are the results of Wang et al. robust watermarking method [26])

	Model	Quantization	corr	MSDM
		9-bits	0.99 (0.93)	0.12 (0.49)
	Venus	8-bits	0.98 (0.70)	0.26 (0.66)
		7-bits	0.97 (0.63)	0.42 (0.79)
		9-bits	0.99 (0.84)	0.09 (0.44)
	Rabbit	8-bits	0.99 (0.59)	0.29 (0.61)
		7-bits	0.98 (0.05)	0.53 (0.76)
		9-bits	0.99 (0.61)	0.11 (0.44)
	Horse	8-bits	0.97 (0.25)	0.36 (0.60)
		7-bits	0.97 (0.17)	0.51 (0.73)

Table 8

 8 Robustness against the random additive noise RNA amplitude , Laplacian smoothing LS numberof iteration and coordinates quantization CQ numberof bitplane (in the parentheses are the results given from Lee et al.[START_REF] Lee | Joint reversible watermarking and progressive compression of 3D meshes[END_REF] watermarking method)

		Horse	Bunny	Venus
		corr	MRMS	corr	MRMS	corr	MRMS
	RNA 0.5%	0.98 (0.91)	0.32 (3.82)	1 (0.93)	0.26 (3.52)	0.99 (0.91)	0.42 (4)
	LS 30	0.99 (0.96)	0.24 (2.22)	0.99 (0.93)	0.23 (2.35)	0.98 (0.99)	0.37 (2.59)
	CQ 7	0.97 (0.93)	0.37 (3.18)	0.99 (0.91)	0.31 (3.33)	0.97 (0.77)	0.39 (4.18)

Table 9

 9 Robustness against similarity transformation (Uniform Scaling US(scalingf actor) , T (x,y,z) and R Rotationangle(x,y,z) )

	Models
			Bunny	Horse	Rabbit
		MRMS	0.102	0.064	0.152
	US (1.5)	MSDM	0.66	0.64	0.89
		corr	0.98	0.99	0.992
		MRMS	0.0064	0.005	0.0082
	T (0.5,0.5,1.5)	MSDM	0.53	0.19	0.23
		corr	1	1	1
		MRMS	0.0105	0.008	0.026
	R 30 • (0.1,0.1,0.1)	MSDM	0.58	0.51	0.43
		corr	1	1	1

Table 10

 10 Robustness against connectivity attacks (in the parentheses are the results given from Ai et al.[START_REF] Ai | A new digital watermarking scheme for 3D triangular mesh models[END_REF] watermarking method)

	Corr

Table 11

 11 Execution times for both embedding and extraction stages

		Venus	Rabbit	Horse	Bunny	David	Hand
	Embedding time (s)	0.0302	0.0291	0.0297	0.0341	0.0347	0.0339
	Extraction time (s)	0.00666	0.00576	0.00612	0.00654	0.00659	0.00661